RFAL

Reviewable status: complete! 0 of 0 LGTMs obtained

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @msirek and @rytaft)

pkg/sql/opt/memo/statistics_builder.go line 3181 at r2 (raw file):

	scalarProps := filter.ScalarProps()
	constrainedCols.UnionWith(scalarProps.OuterCols)
	if scalarProps.Constraints != nil {

(This isn't really a comment on this PR, just something that is confusing me. Maybe this is a question for @rytaft or @mgartner.) I find this condition very confusing. There is something implicit connecting the existence of scalarProps.Constraints with not needing to handle these disjunctions, but I don't understand what it is. Can't constraints also describe disjunctions? And why does the first branch of this condition modify histograms and distinct counts, while the second branch modifies row count and selectivity? Shouldn't both branches modify the same parts of the statistics?

pkg/sql/opt/memo/statistics_builder.go line 4308 at r2 (raw file):

// The independence assumption may not be correct in all cases.
// Would using the full formula lead to more errors since the independence
// assumption is used in more terms in that formula?

Maybe I'm misunderstanding this comment or doing the math wrong, but isn't this iterative approach exactly the same as the textbook solution when using the independence assumption? In other words, assuming P(A and B) = P(A) * P(B) then both P((A or B) and C) from the iterative approach and the equivalent terms P(A and C) + P(B and C) - P(A and B and C) from the textbook solution become P(A)P(C) + P(B)P(C) - P(A)P(B)P(C). I think they only differ when not making the independence assumption. (Maybe that's exactly what this comment is saying?)

This is great, and the idea makes sense. It's just taking me some time to understand the code.

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @msirek and @rytaft)

nice clean solution!

Reviewed 13 of 13 files at r2, all commit messages.
Reviewable status: complete! 1 of 0 LGTMs obtained (waiting on @mgartner and @msirek)

pkg/sql/opt/memo/statistics_builder.go line 3181 at r2 (raw file):

Can't constraints also describe disjunctions?

Yes they can, but I think the idea is that if scalarProps.Constraints is not nil, it means the constraints library has already done the hard work of figuring out how the disjunction (or whatever the predicate is) maps to a constraint. We already know how to use a constraint to update the stats, so we fall back to that approach if it's available.

And why does the first branch of this condition modify histograms and distinct counts

It's clear how constraints modify the histograms and distinct counts, whereas I don't think it's so obvious for generic disjunctions. For example, I don't think you can say anything about the distinct counts / histograms of either x or y given the predicate x = 1 OR y = 1. I think we apply the resulting selectivity to the distinct count / histogram later on, which just reduces all buckets according to the selectivity.

Does this help?

pkg/sql/opt/memo/statistics_builder.go line 3203 at r2 (raw file):

		var selectivities []props.Selectivity
		selectivities = make([]props.Selectivity, 0, len(constraintUnion)+numUnappliedDisjuncts)

nit: no need to declare the var above, can just do selectivities := make(...

pkg/sql/opt/memo/statistics_builder.go line 3207 at r2 (raw file):

		// temporary stats struct, and combine the disjunct selectivities.
		// union the selectivity and row counts.
		sb.constrainExpr(e, constraintUnion[0], relProps, &unionStats)

you don't need this line anymore, and you can get rid of unionStats

pkg/sql/opt/memo/statistics_builder.go line 3221 at r2 (raw file):

		// constraintUnion.
		disjunctionSelectivity := combineOredSelectivities(selectivities)
		s.RowCount = disjunctionSelectivity.AsFloat() * s.RowCount

super nit: could use *=

pkg/sql/opt/memo/testdata/stats/select line 3857 at r2 (raw file):

           └── (((((c0:1 = 1) OR (c1:2 = 1)) OR (c2:3 = 1)) OR (c3:4 = 1)) OR (c4:5 = 1)) OR (c5:6 = 1) [type=bool, outer=(1-6)]

# Expected row count 0.19

It's 0.16 -- is that ok?

Reviewed all commit messages.
Reviewable status: complete! 1 of 0 LGTMs obtained (waiting on @mgartner and @msirek)

pkg/sql/opt/memo/statistics_builder.go line 3181 at r2 (raw file):

Yes, it does. Thank you!

For posterity: constraint.Set can only describe disjunctions within one column, not disjunctions across columns. And histogram and distinct counts are column-level stats, whereas selectivity and row count are table-level stats. So if our disjunction is entirely within one column, we'll have a constraint set and we can apply it to column-level stats. If our disjunction is across columns we won't have a constraint set ((*constraint.Set).Union returns an unconstrained set, which turns into nil in (*memo.logicalPropsBuilder).buildFiltersItemProps) and can only change table-level stats.

Cool!

Reviewed 10 of 13 files at r2.
Reviewable status: complete! 2 of 0 LGTMs obtained (waiting on @mgartner and @msirek)

pkg/sql/opt/memo/testdata/stats/join line 1753 at r2 (raw file):

 ├── scan classrequest
 │    ├── columns: studentid:6(int!null) firstchoiceclassid:7(int) secondchoiceclassid:8(int) thirdchoiceclassid:9(int)
 │    ├── stats: [rows=1000, distinct(8)=100, null(8)=10]

This is interesting, I wonder why this has the distinct and null counts now?

pkg/sql/opt/memo/testdata/stats/select line 3609 at r2 (raw file):

            "num_eq": 1,
            "num_range": 10,
            "upper_bound": "10"

num_range and distinct_range should be 9 here and in all the histograms below (assuming these histograms represent the numbers {1 .. 10}).

pkg/sql/opt/memo/testdata/stats/select line 3613 at r2 (raw file):

    ],
    "histo_col_type": "INT8",
    "avg_size": 3

nit: not strictly necessary, but these objects should each also have "histo_version": 2, "null_count": 0

Reviewable status: complete! 2 of 0 LGTMs obtained (waiting on @mgartner, @michae2, and @rytaft)

pkg/sql/opt/memo/statistics_builder.go line 3203 at r2 (raw file):

Fixed

Code quote:

selectivities = make([]props.Selectivity, 0, len(constraintUnion)+numUnappliedDisjuncts)

pkg/sql/opt/memo/statistics_builder.go line 3207 at r2 (raw file):

Fixed

Code quote:

sb.constrainExpr(e, constraintUnion[0], relProps, &unionStats)

pkg/sql/opt/memo/statistics_builder.go line 3221 at r2 (raw file):

modified as suggested

Code quote:

s.RowCount = disjunctionSelectivity.AsFloat() * s.RowCount

pkg/sql/opt/memo/statistics_builder.go line 4308 at r2 (raw file):

Thanks for looking at this in detail. Your math looks correct, and I worked through it as well. Previously, I thought I had an example where the results from the fully-expanded formula and iterative approach differed, but I could not find it or reconstruct it. I've updated the comments.

pkg/sql/opt/memo/testdata/stats/join line 1753 at r2 (raw file):

It is due to the following diff in buildDisjunctionConstraints():

If any non-tight disjuncts were found, we'd give up building any disjunction constraints. Maybe the default when there is no constraint does not initialize a default number of nulls and distinct values? Do you think we should be?

pkg/sql/opt/memo/testdata/stats/select line 3609 at r2 (raw file):

Fixed

Code quote:

"distinct_range": 10,

pkg/sql/opt/memo/testdata/stats/select line 3613 at r2 (raw file):

Added

Code quote:

"histo_col_type": "INT8",

pkg/sql/opt/memo/testdata/stats/select line 3857 at r2 (raw file):

Not sure what changed, but it's back to 0.19 in the latest code.

Code quote:

Expected row count 0.19

Reviewed 2 of 13 files at r2, 3 of 3 files at r3, all commit messages.
Reviewable status: complete! 0 of 0 LGTMs obtained (and 2 stale) (waiting on @mgartner, @msirek, and @rytaft)

pkg/sql/opt/memo/testdata/stats/join line 1753 at r2 (raw file):

It seems fine the way it is now (using the defaults).

Reviewed 3 of 3 files at r3, all commit messages.
Reviewable status: complete! 1 of 0 LGTMs obtained (and 1 stale) (waiting on @mgartner and @msirek)

Very nice!

Reviewed 10 of 13 files at r2, 2 of 3 files at r3, 1 of 1 files at r4, all commit messages.
Reviewable status: complete! 0 of 0 LGTMs obtained (and 2 stale)