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

pkg/bench/rttanalysis/orm_queries_bench_test.go line 319 at r3 (raw file):

		{
			Name: "hasura column descriptions 8 tables",

in #92929 the preceding test case was also skipped, so could you unskip it when this PR is good to go?

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

pkg/bench/rttanalysis/orm_queries_bench_test.go line 319 at r3 (raw file):

Done.

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

pkg/sql/opt/norm/decorrelate_funcs.go line 1072 at r4 (raw file):

// valid to push down a filter on those non-outer columns. If a reference to the
// outer column is discovered during this traversal, it is valid to replace it
// with one of the non-outer columns in the set.

Is there a reason that we can't do a single traversal and replace any of the outer columns we find?

pkg/sql/opt/norm/decorrelate_funcs.go line 1096 at r4 (raw file):

					// This outer-column reference can be remapped.
					succeeded = true
					return c.f.ConstructVariable(replaceCol)

Do we need any logic to prevent making a substitution that actually drops a filter? For example, how do we prevent replacing the expression non_outer_col = outer_col with non_outer_col = non_outer_col?

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

pkg/sql/opt/norm/decorrelate_funcs.go line 1072 at r4 (raw file):

Hm, that might be possible with an EquivSet. I'll check it out.

pkg/sql/opt/norm/decorrelate_funcs.go line 1096 at r4 (raw file):

Do you mean a case where there are two non_outer_col = outer_col filters to start with, one above the other in the tree?

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

pkg/sql/opt/norm/decorrelate_funcs.go line 1072 at r4 (raw file):

Update: it should be possible, but would introduce some complexity, since we can no longer restrict the set of columns we're considering to just non-outer columns - we would also need to keep track of which outer columns are equal to which non-outer columns, but only those outer columns that were "outer" in the original matched expression. Additionally, it would require more allocations since ColSet copies would become slice copies.
So my feeling is that if the query is complex enough to make the number of traversals significant, doing a single traversal would cause the number of allocations to be significant. Do you have any strong opinions about this?

This is great! I tried to find problem cases involving composite sensitive columns of different data types, but these seem to not be comparable with each other in an IN or NOT IN subquery clause, so that seems to prevent the introduction of column comparisons of data types which didn't exist in the un-rewritten query, for example, float with int, which didn't exist before. For example:

create table t5 (a float, b dec);
create table t6 (a float, b float);
select * from t6 where (b) in (select a from t5 where t5.b = t6.b);

This derives a t5.a = t5.b term, but since t6.b and t5.a are equivalent, and of the same data type (in the IN clause), we're not introducing a new term comparing different data types.

Honestly, it's a little difficult to tell if any problem cases are possible just from examining the code. I wonder if it would make sense to put in a sanity check that the type family of the column we're mapping to matches that of the "from" column.

For the TPCH Q2 regression, maybe it would be good to open an issue for that. These new decorrelation rules should have a very positive impact on other queries so a regression here or there seems acceptable and may highlight other issues which need addressing (like stats accuracy of groupby, as you mentioned). One alternative solution could be to derive new terms instead of just mapping them, and link them. When one term in the pair is applied, mark the other as not requiring evaluation. This could help prevent some beneficial rewrite rules from no longer being able to fire after these rewrites. But maybe such an approach is too complex and could lead to more stats inaccuracies due to redundant terms. Just throwing it out there to ponder.

You may wish to get at least one more approval due to the complexity of this PR, but it looks good to me.

Reviewed 3 of 3 files at r1, 7 of 7 files at r2, 1 of 2 files at r3, 1 of 1 files at r4, all commit messages.
Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @DrewKimball, @mgartner, and @rafiss)

pkg/sql/opt/norm/decorrelate_funcs.go line 1096 at r4 (raw file):

Maybe the question being asked here is, could we ever drop a filter which is still needed? It seems that if the non_outer_col is already in the same equivalence set with outer_col due to IN or NOT IN subquery connecting conditions, it is OK to generate a non_outer_col = non_outer_col filter because the filtering would be done by the IN or NOT IN. This mapped term gets normalized into something like non_outer_col IS DISTINCT FROM CAST(NULL AS INT8).
e.g.

explain select * from t1 where a in (select a from t3 where t3.a = t1.a);
                                          info
----------------------------------------------------------------------------------------
  distribution: local
  vectorized: true

  • hash join (semi)
  │ estimated row count: 1
  │ equality: (a) = (a)
  │
  ├── • filter
  │   │ estimated row count: 1
  │   │ filter: a IS DISTINCT FROM CAST(NULL AS INT8)
  │   │
  │   └── • scan
  │         estimated row count: 1 (100% of the table; stats collected 51 minutes ago)
  │         table: t1@t1_pkey
  │         spans: FULL SCAN
  │
  └── • filter
      │ estimated row count: 1
      │ filter: a IS DISTINCT FROM CAST(NULL AS INT8)
      │
      └── • scan
            estimated row count: 1 (100% of the table; stats collected 34 minutes ago)
            table: t3@t3_pkey
            spans: FULL SCAN

just wondering if this PR is still planned for 23.1?

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @DrewKimball and @mgartner)

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

pkg/sql/opt/norm/decorrelate_funcs.go line 1072 at r4 (raw file):

@mgartner friendly ping on this point - TL;DR is that we could do it in one pass with more allocations.

pkg/sql/opt/norm/decorrelate_funcs.go line 1096 at r4 (raw file):

As Mark says, we only make the replacement in cases where it doesn't affect the result at the level of the matched filter. I'll add a test case that leads to a column being set equal to itself.

This is very cool. Nice work!

Reviewed 1 of 3 files at r1, 4 of 7 files at r2, 1 of 1 files at r4, 7 of 7 files at r5, all commit messages.
Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @DrewKimball and @rafiss)

pkg/sql/opt/norm/decorrelate_funcs.go line 1072 at r4 (raw file):

Thanks for the explanation. No need to change this.

pkg/sql/opt/norm/decorrelate_funcs.go line 1096 at r4 (raw file):

I see. I think my original concern is void - this would only happen if we had something like an inner filter of inner_col = outer_col and an outer filter of outer_col = inner_col - I don't even know if that's possible with other normalization rules that should eliminate one of those filters, but even if it were, we'd never eliminate the outer filter.

pkg/sql/opt/norm/decorrelate_funcs.go line 1091 at r5 (raw file):

		// candidateCols is the set of input columns for which it may be possible to
		// push a filter constraining the column to be equal to an outer column.
		candidateCols := input.Relational().FuncDeps.ComputeEquivGroup(col)

super nit: Can you think of a better name for candidateCols (and associated functions with "candidate" in the name)? It's mildly confusing because it's unclear if they represent columns that are candidates to be replaced or candidates to replace with. Maybe substituteCols?

pkg/sql/opt/norm/decorrelate_funcs.go line 1095 at r5 (raw file):

			candidateCols = filters[i].ScalarProps().FuncDeps.ComputeEquivClosureNoCopy(candidateCols)
		}
		candidateCols.DifferenceWith(input.Relational().OuterCols)

nit: candidateCols.DifferenceWith(outerCols)

pkg/sql/opt/norm/decorrelate_funcs.go line 1104 at r5 (raw file):

			}
			if v, ok := e.(*memo.VariableExpr); ok && v.Col == col {
				if replaceCol, ok := candidateCols.Next(0); ok {

nit: You could use candidateCols.SingleColumn() here instead and avoid the if.

pkg/sql/opt/norm/decorrelate_funcs.go line 1111 at r5 (raw file):

			}
			switch t := e.(type) {
			case memo.RelExpr:

nit: I think you can mix structs and interfaces in a type switch, for example:

switch t := e.(type) {
case *memo.VariableExpr:
  // ...
case memo.RelExpr:
  // ...
case opt.ScalarExpr:
  // ...
}

pkg/sql/opt/norm/decorrelate_funcs.go line 1125 at r5 (raw file):

			// If we made it here, candidateCols has been modified so that calling the
			// replace function on the current expression is valid.
			return c.f.Replace(e, replaceFn)

Don't we need to reset candidate cols to what it was before we called getCandidateColsRelExpr? For example, if we recurse into the left side of a join and mutate the candidate columns, don't we want to revert the candidate columns when we pop back up and recurse into the right side of a join?

pkg/sql/opt/norm/decorrelate_funcs.go line 1216 at r5 (raw file):

	// both inputs. We filter out non-output columns from candidateCols on
	// each recursive call to TryRemapOuterCols, so we don't need to remove any
	// columns here.

I don't fully understand this last sentence. Don't we need to filter out the SetPrivate.OutCols for the recursion with the replaceFn so that we don't replace an outer column with another outer column (from the perspective of the set's left or right child)? I think a test with replacement in two sides of a setop might reveal this.

pkg/sql/opt/norm/rules/decorrelate.opt line 86 at r5 (raw file):

# decorrelation rules because it does not perform any transformations beyond the
# variable replacement. This prevents situations where decorrelation rules make
# the plan worse in their attempts to decorrelate the query.

nit: elaborating on this last sentence or adding an example might be helpful. Or is it obvious how the plans can become worse, and I'm not seeing it?

pkg/sql/opt/norm/rules/decorrelate.opt line 101 at r5 (raw file):

# TryRemapJoinOuterColsLeft is similar to TryRemapJoinOuterColsRight, but it
# applies to the right input of a join.

nit "right input" => "left input"

pkg/sql/opt/norm/testdata/rules/decorrelate line 6154 at r5 (raw file):

# Case with a LeftJoin. The filter can be mapped to the right input.
norm expect=TryRemapJoinOuterColsRight format=hide-all
SELECT * FROM xy INNER JOIN LATERAL (SELECT * FROM ab LEFT JOIN (SELECT u, v + x FROM uv) ON a = u) ON a = x

Can you add a case like this were the remap cannot happen because the join filter doesn't have an equality filter with a column on the right?

Can you also add a case where both the left and right side of the join should have columns remapped? I think that might expose the need to reset candidateCols (see my previous comment).

pkg/sql/opt/norm/testdata/rules/decorrelate line 6293 at r5 (raw file):

# Case with a Union.
norm expect=TryRemapJoinOuterColsRight format=hide-all
SELECT * FROM xy INNER JOIN LATERAL (SELECT * FROM ab UNION (SELECT u, v+x FROM uv)) ON a = x

Can you also add some setop cases where both the left and right side of the setop should have columns remapped? I think that might expose the need to reset candidateCols (see my previous comment).

pkg/sql/opt/norm/testdata/rules/decorrelate line 6308 at r5 (raw file):

# Case with an Intersect.
norm expect=TryRemapJoinOuterColsRight format=hide-all
SELECT * FROM xy INNER JOIN LATERAL (SELECT * FROM ab Intersect (SELECT u, v+x FROM uv)) ON a = x

nit: Intersect => INTERSECT

pkg/sql/opt/norm/testdata/rules/decorrelate line 6323 at r5 (raw file):

# Case with an Except.
norm expect=TryRemapJoinOuterColsRight format=hide-all
SELECT * FROM xy INNER JOIN LATERAL (SELECT * FROM ab Except (SELECT u, v+x FROM uv)) ON a = x

nit: Except => EXCEPT

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @mgartner and @rafiss)

pkg/sql/opt/norm/decorrelate_funcs.go line 1096 at r4 (raw file):

Done.

pkg/sql/opt/norm/decorrelate_funcs.go line 1091 at r5 (raw file):

substituteCols sounds good to me. Done.

pkg/sql/opt/norm/decorrelate_funcs.go line 1095 at r5 (raw file):

Done.

pkg/sql/opt/norm/decorrelate_funcs.go line 1104 at r5 (raw file):

SingleColumn panics if there isn't exactly one column, and there could be multiple possible substitute columns.

pkg/sql/opt/norm/decorrelate_funcs.go line 1111 at r5 (raw file):

Nice, done.

pkg/sql/opt/norm/decorrelate_funcs.go line 1125 at r5 (raw file):

Really good catch. In practice this meant we'd end up firing the rule more often than needed (e.g. once per correlated input of a join/set op). I've refactored the traversal logic so that the new substituteCols gets captured by the replaceFunc definition without also setting the old one.

pkg/sql/opt/norm/decorrelate_funcs.go line 1216 at r5 (raw file):

I think this comment was outdated - when getSubstituteColsRelExpr is called for the left input, substituteColumns will be restricted to just the left columns and vice versa for the right input. Additionally, it is possible for OutCols and LeftCols to be the same - say for an Intersect. That being said, I think the clearest thing will be to just construct the new substituteCols from scratch. Let me know what you think.

pkg/sql/opt/norm/rules/decorrelate.opt line 86 at r5 (raw file):

Added some elaboration, let me know what you think.

pkg/sql/opt/norm/rules/decorrelate.opt line 101 at r5 (raw file):

Good catch, done.

pkg/sql/opt/norm/testdata/rules/decorrelate line 6154 at r5 (raw file):

Done.

pkg/sql/opt/norm/testdata/rules/decorrelate line 6293 at r5 (raw file):

Done.

pkg/sql/opt/norm/testdata/rules/decorrelate line 6308 at r5 (raw file):

Done.

pkg/sql/opt/norm/testdata/rules/decorrelate line 6323 at r5 (raw file):

Done.

Reviewed 3 of 3 files at r6, all commit messages.
Reviewable status: complete! 1 of 0 LGTMs obtained (waiting on @DrewKimball and @rafiss)

pkg/sql/opt/norm/decorrelate_funcs.go line 1104 at r5 (raw file):

Oh right, sorry for the noise.

pkg/sql/opt/norm/decorrelate_funcs.go line 1125 at r5 (raw file):

💯

pkg/sql/opt/norm/decorrelate_funcs.go line 1216 at r5 (raw file):

LGTM.

pkg/sql/opt/norm/decorrelate_funcs.go line 1133 at r6 (raw file):

		// outer-column remapping within (the children of) a RelExpr. Note that
		// getSubstituteColsRelExpr copies substituteCols before modifying it, so
		// different branches of the traversal don't interact.

nit: "dont' interact on the same column set."

pkg/sql/opt/norm/rules/decorrelate.opt line 86 at r5 (raw file):

👍

pkg/sql/opt/norm/testdata/rules/decorrelate line 6343 at r6 (raw file):

 │         ├── scan uv
 │         └── projections
 │              └── v + u

It's tricky to see why it's valid to replace v+x with v+u. I think it might be more obvious if you alias the result of the union and qualify it in the join condition, e.g.:

SELECT * FROM xy INNER JOIN LATERAL (SELECT * FROM (SELECT a, b+x FROM ab) UNION (SELECT u, v+x FROM uv)) AS rhs ON rhs.a = x

You might want to do the same with the other set test cases.

Reviewable status: complete! 0 of 0 LGTMs obtained (and 1 stale) (waiting on @mgartner and @rafiss)

pkg/sql/opt/norm/decorrelate_funcs.go line 1133 at r6 (raw file):

Done.

pkg/sql/opt/norm/testdata/rules/decorrelate line 6343 at r6 (raw file):

I added an alias to each of the Set ops foo(a, b) and had the filter reference it. Hopefully that clears things up.