Skip to content

Commit b9c8b3d

Browse files
adriangbclaude
andauthored
perf: use one null-aware mark join for hashable IN subqueries in projections (#25338)
## Which issue does this PR close? - Closes #25341. This PR supersedes #21363 by @crm26. It reuses the single mark join approach from that PR, and @crm26 is a co-author of the main commit. It also builds on #24972, which added the decorrelation of `IN` subqueries in a projection. ## Rationale for this change An `IN` or `NOT IN` subquery in a SELECT list gives correct results today, but the plan is quadratic. The optimizer builds three mark joins for each subquery. Two of them have no join predicate, so they run as nested loop joins over all outer rows and all inner rows. `COALESCE` duplicates the expression, so that shape gets six mark joins. This PR keeps one hash mark join for each subquery. The join is null-aware when a key can be NULL. A non-equality correlation (Q6 below) stays a residual filter of that join, which the null-aware hash join applies since #25339. | Shape | Query | main | this PR | Result rows identical | | --- | --- | --- | --- | --- | | Q1 | Bare `IN` in the SELECT list | 12.893 s | 0.005 s | yes | | Q2 | `COALESCE((x IN (...))::boolean, false)` | 36.430 s | 0.014 s | yes | | Q3 | Correlated `IN` with an equality predicate | 0.278 s | 0.008 s | yes | | Q4 | Two `IN` subqueries in separate columns | 20.904 s | 0.011 s | yes | | Q5 | Correlated `EXISTS` | 0.005 s | 0.003 s | yes | | Q6 | Correlated `IN` with a non-equality predicate | 2.489 s | 0.018 s | yes | The table is one run of the script below after the rebase onto `main` at `39ca2c74a9`, `datafusion-cli` built with `--profile release-nonlto` and the default `target_partitions`. Q6 in 3 more interleaved runs: `main` 2.57 s to 3.18 s, this PR 0.022 s to 0.058 s. These shapes are the `projection_subquery` benchmark suite from #25346. <details> <summary>Reproduction with datafusion-cli: script, plans and timings for each shape</summary> Run the script with `datafusion-cli -f mre.sql`. It creates two tables with 200000 rows each, then for each shape it prints `EXPLAIN` and runs the query. `datafusion-cli` prints the elapsed time after each statement. The result rows of every query are identical between the two builds. The plans and times for Q1 to Q5 below are from the first version of this PR, with `main` at 22651d2 and `target_partitions = 4`. The plans of this PR for those shapes did not change with the rebase. Q6 was captured again after the rebase. ```sql SET datafusion.execution.target_partitions = 4; CREATE TABLE outer_t AS SELECT CAST(v AS INT) AS id, CAST(v % 1000 AS INT) AS z FROM (SELECT unnest(generate_series(1, 200000)) AS v); CREATE TABLE inner_t AS SELECT CASE WHEN v % 97 = 0 THEN NULL ELSE CAST(v * 2 AS INT) END AS id, CAST(v % 1000 AS INT) AS z FROM (SELECT unnest(generate_series(1, 200000)) AS v); SELECT 'Q1' AS shape; EXPLAIN SELECT id, id IN (SELECT id FROM inner_t) AS m FROM outer_t; SELECT count(*) FILTER (WHERE m), count(*) FILTER (WHERE m IS NULL) FROM (SELECT id, id IN (SELECT id FROM inner_t) AS m FROM outer_t); SELECT 'Q2' AS shape; EXPLAIN SELECT id, COALESCE((id IN (SELECT id FROM inner_t))::boolean, false) AS m FROM outer_t; SELECT count(*) FILTER (WHERE m) FROM (SELECT id, COALESCE((id IN (SELECT id FROM inner_t))::boolean, false) AS m FROM outer_t); SELECT 'Q3' AS shape; EXPLAIN SELECT id, id IN (SELECT i.id FROM inner_t i WHERE i.z = o.z) AS m FROM outer_t o; SELECT count(*) FILTER (WHERE m), count(*) FILTER (WHERE m IS NULL) FROM (SELECT id, id IN (SELECT i.id FROM inner_t i WHERE i.z = o.z) AS m FROM outer_t o); SELECT 'Q4' AS shape; EXPLAIN SELECT id IN (SELECT id FROM inner_t) AS a, id IN (SELECT id FROM inner_t WHERE z < 500) AS b FROM outer_t; SELECT count(*) FILTER (WHERE a), count(*) FILTER (WHERE b) FROM (SELECT id IN (SELECT id FROM inner_t) AS a, id IN (SELECT id FROM inner_t WHERE z < 500) AS b FROM outer_t); SELECT 'Q5' AS shape; EXPLAIN SELECT id, EXISTS (SELECT 1 FROM inner_t i WHERE i.id = o.id) AS e FROM outer_t o; SELECT count(*) FILTER (WHERE e) FROM (SELECT id, EXISTS (SELECT 1 FROM inner_t i WHERE i.id = o.id) AS e FROM outer_t o); SELECT 'Q6' AS shape; EXPLAIN SELECT id, id IN (SELECT i.id FROM inner_t i WHERE i.z < o.z) AS m FROM outer_t o; SELECT count(*) FILTER (WHERE m), count(*) FILTER (WHERE m IS NULL) FROM (SELECT id, id IN (SELECT i.id FROM inner_t i WHERE i.z < o.z) AS m FROM outer_t o); ``` <details> <summary>Q1: Bare `IN` in the SELECT list, plans on main and on this PR</summary> **main**, query time 190.730 s ``` logical_plan Projection: outer_t.id, __correlated_sq_1.mark IS NOT DISTINCT FROM Boolean(true) OR (__correlated_sq_2.mark OR outer_t.id IS NULL AND __correlated_sq_3.mark) IS NOT DISTINCT FROM Boolean(true) AND __correlated_sq_1.mark IS DISTINCT FROM Boolean(true) AND Boolean(NULL) AS m LeftMark Join: LeftMark Join: LeftMark Join: outer_t.id = __correlated_sq_1.id null_aware TableScan: outer_t projection=[id] SubqueryAlias: __correlated_sq_1 TableScan: inner_t projection=[id] SubqueryAlias: __correlated_sq_2 Filter: inner_t.id IS NULL TableScan: inner_t projection=[id] SubqueryAlias: __correlated_sq_3 TableScan: inner_t projection=[id] physical_plan ProjectionExec: expr=[id@0 as id, mark@1 IS NOT DISTINCT FROM true OR (mark@2 OR id@0 IS NULL AND mark@3) IS NOT DISTINCT FROM true AND mark@1 IS DISTINCT FROM true AND NULL as m] NestedLoopJoinExec: join_type=LeftMark CoalescePartitionsExec NestedLoopJoinExec: join_type=RightMark CoalescePartitionsExec FilterExec: id@0 IS NULL DataSourceExec: partitions=4, partition_sizes=[7, 6, 6, 6] HashJoinExec: mode=CollectLeft, join_type=LeftMark, on=[(id@0, id@0)], null_aware CoalescePartitionsExec DataSourceExec: partitions=4, partition_sizes=[7, 6, 6, 6] DataSourceExec: partitions=4, partition_sizes=[7, 6, 6, 6] DataSourceExec: partitions=4, partition_sizes=[7, 6, 6, 6] ``` **this PR**, query time 0.034 s ``` logical_plan Projection: outer_t.id, __correlated_sq_1.mark AS m LeftMark Join: outer_t.id = __correlated_sq_1.id null_aware TableScan: outer_t projection=[id] SubqueryAlias: __correlated_sq_1 TableScan: inner_t projection=[id] physical_plan ProjectionExec: expr=[id@0 as id, mark@1 as m] HashJoinExec: mode=CollectLeft, join_type=LeftMark, on=[(id@0, id@0)], null_aware CoalescePartitionsExec DataSourceExec: partitions=4, partition_sizes=[7, 6, 6, 6] DataSourceExec: partitions=4, partition_sizes=[7, 6, 6, 6] ``` </details> <details> <summary>Q2: `COALESCE((x IN (...))::boolean, false)`, plans on main and on this PR</summary> **main**, query time 351.579 s ``` logical_plan Projection: outer_t.id, CAST(__correlated_sq_1.mark IS NOT DISTINCT FROM Boolean(true) OR (__correlated_sq_2.mark OR outer_t.id IS NULL AND __correlated_sq_3.mark) IS NOT DISTINCT FROM Boolean(true) AND __correlated_sq_1.mark IS DISTINCT FROM Boolean(true) AND Boolean(NULL) AS Boolean) IS NOT NULL AND CAST(__correlated_sq_4.mark IS NOT DISTINCT FROM Boolean(true) OR (__correlated_sq_5.mark OR outer_t.id IS NULL AND __correlated_sq_6.mark) IS NOT DISTINCT FROM Boolean(true) AND __correlated_sq_4.mark IS DISTINCT FROM Boolean(true) AND Boolean(NULL) AS Boolean) AS m LeftMark Join: LeftMark Join: LeftMark Join: outer_t.id = __correlated_sq_4.id null_aware LeftMark Join: LeftMark Join: LeftMark Join: outer_t.id = __correlated_sq_1.id null_aware TableScan: outer_t projection=[id] SubqueryAlias: __correlated_sq_1 TableScan: inner_t projection=[id] SubqueryAlias: __correlated_sq_2 Filter: inner_t.id IS NULL TableScan: inner_t projection=[id] SubqueryAlias: __correlated_sq_3 TableScan: inner_t projection=[id] SubqueryAlias: __correlated_sq_4 TableScan: inner_t projection=[id] SubqueryAlias: __correlated_sq_5 Filter: inner_t.id IS NULL TableScan: inner_t projection=[id] SubqueryAlias: __correlated_sq_6 TableScan: inner_t projection=[id] physical_plan ProjectionExec: expr=[id@0 as id, mark@1 IS NOT DISTINCT FROM true OR (mark@2 OR id@0 IS NULL AND mark@3) IS NOT DISTINCT FROM true AND mark@1 IS DISTINCT FROM true AND NULL IS NOT NULL AND (mark@4 IS NOT DISTINCT FROM true OR (mark@5 OR id@0 IS NULL AND mark@6) IS NOT DISTINCT FROM true AND mark@4 IS DISTINCT FROM true AND NULL) as m] NestedLoopJoinExec: join_type=LeftMark CoalescePartitionsExec NestedLoopJoinExec: join_type=RightMark CoalescePartitionsExec FilterExec: id@0 IS NULL DataSourceExec: partitions=4, partition_sizes=[7, 6, 6, 6] HashJoinExec: mode=CollectLeft, join_type=LeftMark, on=[(id@0, id@0)], null_aware CoalescePartitionsExec NestedLoopJoinExec: join_type=LeftMark CoalescePartitionsExec NestedLoopJoinExec: join_type=RightMark CoalescePartitionsExec FilterExec: id@0 IS NULL DataSourceExec: partitions=4, partition_sizes=[7, 6, 6, 6] HashJoinExec: mode=CollectLeft, join_type=LeftMark, on=[(id@0, id@0)], null_aware CoalescePartitionsExec DataSourceExec: partitions=4, partition_sizes=[7, 6, 6, 6] DataSourceExec: partitions=4, partition_sizes=[7, 6, 6, 6] DataSourceExec: partitions=4, partition_sizes=[7, 6, 6, 6] DataSourceExec: partitions=4, partition_sizes=[7, 6, 6, 6] DataSourceExec: partitions=4, partition_sizes=[7, 6, 6, 6] ``` **this PR**, query time 0.054 s ``` logical_plan Projection: outer_t.id, CAST(__correlated_sq_1.mark AS Boolean) IS NOT NULL AND CAST(__correlated_sq_2.mark AS Boolean) AS m LeftMark Join: outer_t.id = __correlated_sq_2.id null_aware LeftMark Join: outer_t.id = __correlated_sq_1.id null_aware TableScan: outer_t projection=[id] SubqueryAlias: __correlated_sq_1 TableScan: inner_t projection=[id] SubqueryAlias: __correlated_sq_2 TableScan: inner_t projection=[id] physical_plan ProjectionExec: expr=[id@0 as id, mark@1 IS NOT NULL AND mark@2 as m] HashJoinExec: mode=CollectLeft, join_type=LeftMark, on=[(id@0, id@0)], null_aware CoalescePartitionsExec HashJoinExec: mode=CollectLeft, join_type=LeftMark, on=[(id@0, id@0)], null_aware CoalescePartitionsExec DataSourceExec: partitions=4, partition_sizes=[7, 6, 6, 6] DataSourceExec: partitions=4, partition_sizes=[7, 6, 6, 6] DataSourceExec: partitions=4, partition_sizes=[7, 6, 6, 6] ``` </details> <details> <summary>Q3: Correlated `IN` with an equality predicate, plans on main and on this PR</summary> **main**, query time 1.372 s ``` logical_plan Projection: o.id, __correlated_sq_1.mark IS NOT DISTINCT FROM Boolean(true) OR (__correlated_sq_2.mark OR o.id IS NULL AND __correlated_sq_3.mark) IS NOT DISTINCT FROM Boolean(true) AND __correlated_sq_1.mark IS DISTINCT FROM Boolean(true) AND Boolean(NULL) AS m LeftMark Join: o.z = __correlated_sq_3.z LeftMark Join: o.z = __correlated_sq_2.z LeftMark Join: o.id = __correlated_sq_1.id, o.z = __correlated_sq_1.z null_aware SubqueryAlias: o TableScan: outer_t projection=[id, z] SubqueryAlias: __correlated_sq_1 SubqueryAlias: i TableScan: inner_t projection=[id, z] SubqueryAlias: __correlated_sq_2 SubqueryAlias: i Projection: inner_t.z Filter: inner_t.id IS NULL TableScan: inner_t projection=[id, z] SubqueryAlias: __correlated_sq_3 SubqueryAlias: i TableScan: inner_t projection=[z] physical_plan ProjectionExec: expr=[id@0 as id, mark@1 IS NOT DISTINCT FROM true OR (mark@2 OR id@0 IS NULL AND mark@3) IS NOT DISTINCT FROM true AND mark@1 IS DISTINCT FROM true AND NULL as m] HashJoinExec: mode=CollectLeft, join_type=RightMark, on=[(z@0, z@1)], projection=[id@0, mark@2, mark@3, mark@4] CoalescePartitionsExec DataSourceExec: partitions=4, partition_sizes=[7, 6, 6, 6] HashJoinExec: mode=CollectLeft, join_type=RightMark, on=[(z@0, z@1)] CoalescePartitionsExec FilterExec: id@0 IS NULL, projection=[z@1] DataSourceExec: partitions=4, partition_sizes=[7, 6, 6, 6] HashJoinExec: mode=CollectLeft, join_type=LeftMark, on=[(id@0, id@0), (z@1, z@1)], null_aware CoalescePartitionsExec DataSourceExec: partitions=4, partition_sizes=[7, 6, 6, 6] DataSourceExec: partitions=4, partition_sizes=[7, 6, 6, 6] ``` **this PR**, query time 0.091 s ``` logical_plan Projection: o.id, __correlated_sq_1.mark AS m LeftMark Join: o.id = __correlated_sq_1.id, o.z = __correlated_sq_1.z null_aware SubqueryAlias: o TableScan: outer_t projection=[id, z] SubqueryAlias: __correlated_sq_1 SubqueryAlias: i TableScan: inner_t projection=[id, z] physical_plan ProjectionExec: expr=[id@0 as id, mark@1 as m] HashJoinExec: mode=CollectLeft, join_type=LeftMark, on=[(id@0, id@0), (z@1, z@1)], projection=[id@0, mark@2], null_aware CoalescePartitionsExec DataSourceExec: partitions=4, partition_sizes=[7, 6, 6, 6] DataSourceExec: partitions=4, partition_sizes=[7, 6, 6, 6] ``` </details> <details> <summary>Q4: Two `IN` subqueries in separate columns, plans on main and on this PR</summary> **main**, query time 296.676 s ``` logical_plan Projection: __correlated_sq_1.mark IS NOT DISTINCT FROM Boolean(true) OR (__correlated_sq_2.mark OR outer_t.id IS NULL AND __correlated_sq_3.mark) IS NOT DISTINCT FROM Boolean(true) AND __correlated_sq_1.mark IS DISTINCT FROM Boolean(true) AND Boolean(NULL) AS a, __correlated_sq_4.mark IS NOT DISTINCT FROM Boolean(true) OR (__correlated_sq_5.mark OR outer_t.id IS NULL AND __correlated_sq_6.mark) IS NOT DISTINCT FROM Boolean(true) AND __correlated_sq_4.mark IS DISTINCT FROM Boolean(true) AND Boolean(NULL) AS b LeftMark Join: LeftMark Join: LeftMark Join: outer_t.id = __correlated_sq_4.id null_aware LeftMark Join: LeftMark Join: LeftMark Join: outer_t.id = __correlated_sq_1.id null_aware TableScan: outer_t projection=[id] SubqueryAlias: __correlated_sq_1 TableScan: inner_t projection=[id] SubqueryAlias: __correlated_sq_2 Filter: inner_t.id IS NULL TableScan: inner_t projection=[id] SubqueryAlias: __correlated_sq_3 TableScan: inner_t projection=[id] SubqueryAlias: __correlated_sq_4 Projection: inner_t.id Filter: inner_t.z < Int32(500) TableScan: inner_t projection=[id, z] SubqueryAlias: __correlated_sq_5 Projection: inner_t.id Filter: inner_t.z < Int32(500) AND inner_t.id IS NULL TableScan: inner_t projection=[id, z] SubqueryAlias: __correlated_sq_6 Projection: inner_t.id Filter: inner_t.z < Int32(500) TableScan: inner_t projection=[id, z] physical_plan ProjectionExec: expr=[mark@1 IS NOT DISTINCT FROM true OR (mark@2 OR id@0 IS NULL AND mark@3) IS NOT DISTINCT FROM true AND mark@1 IS DISTINCT FROM true AND NULL as a, mark@4 IS NOT DISTINCT FROM true OR (mark@5 OR id@0 IS NULL AND mark@6) IS NOT DISTINCT FROM true AND mark@4 IS DISTINCT FROM true AND NULL as b] NestedLoopJoinExec: join_type=LeftMark CoalescePartitionsExec NestedLoopJoinExec: join_type=RightMark CoalescePartitionsExec FilterExec: z@1 < 500 AND id@0 IS NULL, projection=[id@0] DataSourceExec: partitions=4, partition_sizes=[7, 6, 6, 6] HashJoinExec: mode=CollectLeft, join_type=LeftMark, on=[(id@0, id@0)], null_aware CoalescePartitionsExec NestedLoopJoinExec: join_type=LeftMark CoalescePartitionsExec NestedLoopJoinExec: join_type=RightMark CoalescePartitionsExec FilterExec: id@0 IS NULL DataSourceExec: partitions=4, partition_sizes=[7, 6, 6, 6] HashJoinExec: mode=CollectLeft, join_type=LeftMark, on=[(id@0, id@0)], null_aware CoalescePartitionsExec DataSourceExec: partitions=4, partition_sizes=[7, 6, 6, 6] DataSourceExec: partitions=4, partition_sizes=[7, 6, 6, 6] DataSourceExec: partitions=4, partition_sizes=[7, 6, 6, 6] FilterExec: z@1 < 500, projection=[id@0] DataSourceExec: partitions=4, partition_sizes=[7, 6, 6, 6] FilterExec: z@1 < 500, projection=[id@0] DataSourceExec: partitions=4, partition_sizes=[7, 6, 6, 6] ``` **this PR**, query time 0.063 s ``` logical_plan Projection: __correlated_sq_1.mark AS a, __correlated_sq_2.mark AS b LeftMark Join: outer_t.id = __correlated_sq_2.id null_aware LeftMark Join: outer_t.id = __correlated_sq_1.id null_aware TableScan: outer_t projection=[id] SubqueryAlias: __correlated_sq_1 TableScan: inner_t projection=[id] SubqueryAlias: __correlated_sq_2 Projection: inner_t.id Filter: inner_t.z < Int32(500) TableScan: inner_t projection=[id, z] physical_plan ProjectionExec: expr=[mark@0 as a, mark@1 as b] HashJoinExec: mode=CollectLeft, join_type=LeftMark, on=[(id@0, id@0)], projection=[mark@1, mark@2], null_aware CoalescePartitionsExec HashJoinExec: mode=CollectLeft, join_type=LeftMark, on=[(id@0, id@0)], null_aware CoalescePartitionsExec DataSourceExec: partitions=4, partition_sizes=[7, 6, 6, 6] DataSourceExec: partitions=4, partition_sizes=[7, 6, 6, 6] FilterExec: z@1 < 500, projection=[id@0] DataSourceExec: partitions=4, partition_sizes=[7, 6, 6, 6] ``` </details> <details> <summary>Q5: Correlated `EXISTS`, plans on main and on this PR</summary> **main**, query time 0.021 s ``` logical_plan Projection: o.id, __correlated_sq_1.mark AS e LeftMark Join: o.id = __correlated_sq_1.id SubqueryAlias: o TableScan: outer_t projection=[id] SubqueryAlias: __correlated_sq_1 SubqueryAlias: i TableScan: inner_t projection=[id] physical_plan ProjectionExec: expr=[id@0 as id, mark@1 as e] HashJoinExec: mode=CollectLeft, join_type=LeftMark, on=[(id@0, id@0)] CoalescePartitionsExec DataSourceExec: partitions=4, partition_sizes=[7, 6, 6, 6] DataSourceExec: partitions=4, partition_sizes=[7, 6, 6, 6] ``` **this PR**, query time 0.021 s ``` logical_plan Projection: o.id, __correlated_sq_1.mark AS e LeftMark Join: o.id = __correlated_sq_1.id SubqueryAlias: o TableScan: outer_t projection=[id] SubqueryAlias: __correlated_sq_1 SubqueryAlias: i TableScan: inner_t projection=[id] physical_plan ProjectionExec: expr=[id@0 as id, mark@1 as e] HashJoinExec: mode=CollectLeft, join_type=LeftMark, on=[(id@0, id@0)] CoalescePartitionsExec DataSourceExec: partitions=4, partition_sizes=[7, 6, 6, 6] DataSourceExec: partitions=4, partition_sizes=[7, 6, 6, 6] ``` </details> <details> <summary>Q6: Correlated `IN` with a non-equality predicate, plans on main and on this PR</summary> **main** (`39ca2c74a9`), query time 2.489 s ``` logical_plan Projection: o.id, CASE WHEN __correlated_sq_1.mark THEN Boolean(true) WHEN __correlated_sq_2.mark OR o.id IS NULL AND __correlated_sq_3.mark THEN Boolean(NULL) ELSE Boolean(false) END AS m LeftMark Join: Filter: __correlated_sq_3.z < o.z LeftMark Join: Filter: __correlated_sq_2.z < o.z LeftMark Join: o.id = __correlated_sq_1.id Filter: __correlated_sq_1.z < o.z null_aware SubqueryAlias: o TableScan: outer_t projection=[id, z] SubqueryAlias: __correlated_sq_1 SubqueryAlias: i TableScan: inner_t projection=[id, z] SubqueryAlias: __correlated_sq_2 SubqueryAlias: i Projection: inner_t.z Filter: inner_t.id IS NULL TableScan: inner_t projection=[id, z] SubqueryAlias: __correlated_sq_3 SubqueryAlias: i TableScan: inner_t projection=[z] physical_plan ProjectionExec: expr=[id@0 as id, CASE WHEN mark@1 THEN true WHEN mark@2 OR id@0 IS NULL AND mark@3 THEN NULL ELSE false END as m] NestedLoopJoinExec: join_type=LeftMark, filter=z@1 < z@0, projection=[id@0, mark@2, mark@3, mark@4] CoalescePartitionsExec NestedLoopJoinExec: join_type=RightMark, filter=z@1 < z@0 CoalescePartitionsExec FilterExec: id@0 IS NULL, projection=[z@1] DataSourceExec: partitions=12, partition_sizes=[3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2] HashJoinExec: mode=CollectLeft, join_type=LeftMark, on=[(id@0, id@0)], filter=z@1 < z@0, null_aware CoalescePartitionsExec DataSourceExec: partitions=12, partition_sizes=[3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2] DataSourceExec: partitions=12, partition_sizes=[3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2] DataSourceExec: partitions=12, partition_sizes=[3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2] ``` **this PR**, query time 0.018 s ``` logical_plan Projection: o.id, __correlated_sq_1.mark AS m LeftMark Join: o.id = __correlated_sq_1.id Filter: __correlated_sq_1.z < o.z null_aware SubqueryAlias: o TableScan: outer_t projection=[id, z] SubqueryAlias: __correlated_sq_1 SubqueryAlias: i TableScan: inner_t projection=[id, z] physical_plan ProjectionExec: expr=[id@0 as id, mark@1 as m] HashJoinExec: mode=CollectLeft, join_type=LeftMark, on=[(id@0, id@0)], filter=z@1 < z@0, projection=[id@0, mark@2], null_aware CoalescePartitionsExec DataSourceExec: partitions=12, partition_sizes=[3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2] DataSourceExec: partitions=12, partition_sizes=[3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2] ``` </details> </details> ## What changes are included in this PR? 1. `build_join` now reports whether the mark column of the `LeftMark` join is exact under three-valued logic. It is exact when no side of the `IN` predicate can be NULL in scope, or when the join is null-aware and the `IN` equality is its first key. A residual non-equality filter does not change this, because the null-aware hash join applies it when it decides whether a NULL makes the mark UNKNOWN (#25339). `in_subquery_value_mark_join` builds this join first. If the mark is exact, it returns the mark column alone, or `NOT mark` for `NOT IN`. The three join materialization stays for the other cases. 2. The rule decides null-awareness from one question: can the `IN` value or the subquery output be NULL inside the scope of an outer row? Only then can `IN` be UNKNOWN. - The test uses the key expressions, not the columns they reference. A key such as `NULLIF(id, 1)` or `TRY_CAST(s AS INT)` can be NULL over a `NOT NULL` column. - `PullUpCorrelatedExpr` now records every correlated conjunct, before it drops the conjunct that repeats the `IN` predicate. A conjunct such as `y = x`, `y > x` or `y IS NOT NULL` is never TRUE for a NULL `y`, so it keeps a NULL `y` out of the scope. The conjuncts keep their outer references, so a subquery column with the same qualified name as an outer column is not mistaken for the outer value. - A correlation key that is NULL only empties the scope, so it never makes the join null-aware. - The recorded conjuncts are cleared when the pull up passes an outer join, a union or a grouping set, because such a node can put a NULL back into the column. With `ROLLUP`, the grand-total row is a NULL for every outer row. 3. A `NOT IN` filter uses the same scope-aware nullability for its null-aware `LeftAnti` join. If the `IN` equality does not become the first key of that join, the rule gives up and the `NOT IN` becomes the mark joins, which give the correct result. 4. The regression test for #24574 in `projection_pushdown.slt` now uses a correlated subquery with `LIMIT 1`. The subquery then still reaches `ExtractLeafExpressions`, and the alias generator still starts at 2 inside it. The earlier version of the test let the subquery be flattened, so it no longer exercised the scan inside a subquery path. 5. New sqllogictest cases in `subquery_projection.slt`: - `EXPLAIN` guards: one hash mark join for each subquery, one null-aware mark join with a residual filter, a null-aware `LeftAnti` join with two keys, and with one key and a residual filter. - NULL semantics: `IN` and `NOT IN` with a NULL in the subquery, a NULL outer value, `NOT` inside `CASE`, a projection over an aggregate, the `COALESCE` and cast shape, and the residual filter shape. - Nullable key expressions over `NOT NULL` columns: a `NULLIF` value, a `TRY_CAST` value and a `NULLIF` subquery output, in a projection and in a `WHERE` clause. - A correlation that repeats the `IN` predicate, and a subquery column with the same qualified name as the outer value. - The same correlation below a `ROLLUP`, as a projected `IN` with an `EXPLAIN` guard and as a `NOT IN` filter. The expected results agree with DuckDB 1.5.2, and the earlier cases also with PostgreSQL. 6. The `projection_subquery` benchmark docs no longer describe q07 as the nested-loop control. ## DuckDB comparison For an absolute reference, the same seven queries in `datafusion-cli` and in DuckDB 1.5.2, on the same two tables, release build, Apple M4 Pro. `main` is the merge-base `64871d9` and "this PR" is `3af87370c1`. The later commits of this PR change the correlated and `NOT IN` filter paths, and, after the rebase onto #25339, the plan of q07. q07 is measured again below. The tables are the ones the suite builds, at its default of 30,000 rows each. Each number is the median of 7 runs. One round runs one session per engine, and the rounds interleave the three engines. | Query | `main` | this PR | DuckDB | | --- | --- | --- | --- | | q01 bare `IN` | 533 ms | 2 ms | 2 ms | | q02 `COALESCE` over `IN` | 1352 ms | 3 ms | 2 ms | | q03 correlated `IN`, equality | 14 ms | 3 ms | 3 ms | | q04 two `IN` columns | 1026 ms | 3 ms | 2 ms | | q05 bare `NOT IN` | 646 ms | 1 ms | 2 ms | | q06 correlated `EXISTS` | 4 ms | 2 ms | 2 ms | | q07 correlated `IN`, non-equality | 117 ms | 93 ms | 458 ms | All three engines give the same result for all seven queries, and the counts are the ones in the suite's checked-in result files. For the four quadratic shapes, q01, q02, q04 and q05, `main` is 270x to 680x slower than DuckDB. This PR puts them at DuckDB's cost. These times are at the 1 ms resolution of both command line tools, so the exact factor is approximate; the size of the difference is not. q07 now uses one null-aware mark join with the `<` correlation as a residual filter. Measured again after the rebase, median of 7 runs at 30,000 rows: `main` at `39ca2c74a9` 78 ms, this PR 3 ms, DuckDB 404 ms. The counts are the same in all three. A second run at 100,000 rows per table gives the same picture: `main` takes 2741 ms to 6355 ms for q01, q02, q04 and q05, this PR takes 2 ms to 4 ms and DuckDB 3 ms to 4 ms. All three engines again give the same counts. <details><summary>How to run it</summary> The queries are the suite's own `benchmarks/sql_benchmarks/projection_subquery/queries/q0*.sql`, with an alias added to the derived table. The load SQL needs one change for DuckDB, because `generate_series` gives a column of that name there and a column named `value` in DataFusion: ```sql CREATE TABLE outer_t AS SELECT CAST(value AS INT) AS id, CAST(value % 1000 AS INT) AS z FROM generate_series(1, 30000) AS g(value); CREATE TABLE inner_t AS SELECT CASE WHEN value % 97 = 0 THEN NULL ELSE CAST(value * 2 AS INT) END AS id, CAST(value % 1000 AS INT) AS z FROM generate_series(1, 30000) AS g(value); ``` `datafusion-cli` reports the time of each statement as `Elapsed`, and `duckdb` reports it as `Run Time (s): real` after `.timer on`. </details> ## What is the testing strategy for this PR? - Unit tests in `datafusion/optimizer/src/decorrelate_predicate_subquery.rs`. The updated snapshots show a single mark join. New tests cover a residual filter, `NOT IN`, nullable key expressions, a correlation that repeats the `IN` predicate, and the same correlation below a `ROLLUP`. The last one fails without the clearing in item 2. - The new sqllogictest cases in `subquery_projection.slt` listed above. - The full sqllogictest suite, the optimizer crate and workspace clippy are green locally. - The benchmark numbers above. ## Are there any user-facing changes? Plans for projected `IN` and `NOT IN` subqueries are much faster. There are no changes to any public API, and no documentation change is needed. Some query results change, and each change is a correction. DuckDB 1.5.2 gives the new results: - An `IN` or `NOT IN` whose key is an expression that can be NULL over a `NOT NULL` column, such as `NULLIF(id, 1)`. For a projected `IN`, `main` returns `false` instead of `NULL`. For a `NOT IN` filter, `main` keeps rows that it must drop. The correlated form of that is #25347. - A correlated `NOT IN` whose correlation repeats the `IN` predicate, `x NOT IN (SELECT y FROM t WHERE y = x)`. `main` drops rows that it must keep (#25480). - A projected `IN` whose correlation repeats the `IN` predicate below a `ROLLUP`, `k IN (SELECT i.k FROM i WHERE i.k = o.k GROUP BY ROLLUP(i.k))`. `main` fails to plan it since #25529. It now gives NULL for a miss, as DuckDB does. 🤖 Generated with [Claude Code](https://claude.com/claude-code) --------- Co-authored-by: Claude Opus 5.5 <[email protected]>
1 parent 953518c commit b9c8b3d

8 files changed

Lines changed: 1192 additions & 161 deletions

File tree

‎benchmarks/sql_benchmarks/README.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -48,7 +48,7 @@ in the community:
4848
| `predicate_eval` | Conjunctive (AND) filter-evaluation micro-benchmarks; each subgroup is a different predicate pattern, to test how an adaptive predicate-ordering system behaves across them ([#11262](https://github.com/apache/datafusion/issues/11262)). Subgroups (`--subgroup`): `costsel`, `cost`, `selectivity`, `cardinality`, `width`, `scale`, `neutral`, `correlation`, `drift`, `nulls`. The suite sets no engine config of its own, so by default it measures DataFusion's built-in left-deep `AND` short-circuit; point it at a system under test by exporting that system's own DataFusion setting (the harness builds its `SessionConfig` with `SessionConfig::from_env`). Every query is a `count(*)`, and the counts are checked in under `predicate_eval/results/`, so `--result-mode validate` also checks that a reordering under test still returns the same rows; the checked-in counts were persisted at the suite defaults (`PRED_ROWS=1000000`, `PRED_FILL=30`), so validation assumes those (the `scale` and `width` subgroups pin their own values per query and validate at any setting). |
4949
| `parquet_row_filter_skip` | Micro-benchmark for the per-row-group fully-matched RowFilter skip on Parquet scans ([#23696](https://github.com/apache/datafusion/issues/23696)). Subgroups (`--subgroup`): `skip` (clustered key, most row groups fully matched by statistics so the per-row filter is skipped), `control` (scrambled key, no row group is ever fully matched). Size the data with `PRED_ROWS` and the row-group size with `RG_SIZE`. |
5050
| `spill_views` | Sort and `GROUP BY` queries that spill `StringView` and `BinaryView` columns read from Parquet ([#23564](https://github.com/apache/datafusion/issues/23564)). Each query sets its own memory limit and `target_partitions = 4`, so it spills in any environment. Subgroups (`--subgroup`): `repeated` (sort with a low-cardinality payload that shares one dictionary buffer, where spill compaction can remove data), `distinct` (sort and `GROUP BY` on all-distinct strings, where compaction cannot remove data). Set the memory limit of each subgroup with `SPILL_VIEWS_LIMIT_REPEATED` (default `40M`) and `SPILL_VIEWS_LIMIT_DISTINCT` (default `96M`), for example to let both sides of a comparison finish when one of them runs out of memory at the default. The queries must still spill, so check a raised limit with `EXPLAIN ANALYZE` and keep it well below the working set: `q05` stops spilling at about `192M`. Give a whole number of K, M or G units, because the run asserts the limit that the memory pool reports back. |
51-
| `projection_subquery` | `IN`, `NOT IN` and `EXISTS` subqueries that sit in the `SELECT` list instead of a filter ([#25341](https://github.com/apache/datafusion/issues/25341)). Every query projects the boolean subquery result and aggregates it, so the measured cost is the decorrelation plan and not the size of the output. `q07` correlates on `<` instead of `=`, so it keeps the nested-loop plan and is the control that must not change. Size the two inline tables with `PSQ_ROWS` (default `30000`). The counts are checked in under `projection_subquery/results/`, so `--result-mode validate` also proves that a change to the decorrelation still returns the same rows; the checked-in counts were persisted at the default `PSQ_ROWS`, so validation assumes that value. |
51+
| `projection_subquery` | `IN`, `NOT IN` and `EXISTS` subqueries that sit in the `SELECT` list instead of a filter ([#25341](https://github.com/apache/datafusion/issues/25341)). Every query projects the boolean subquery result and aggregates it, so the measured cost is the decorrelation plan and not the size of the output. `q07` correlates on `<` instead of `=`, so the correlation stays a residual filter of the mark join. Size the two inline tables with `PSQ_ROWS` (default `30000`). The counts are checked in under `projection_subquery/results/`, so `--result-mode validate` also proves that a change to the decorrelation still returns the same rows; the checked-in counts were persisted at the default `PSQ_ROWS`, so validation assumes that value. |
5252

5353
# Running Benchmarks
5454

‎benchmarks/sql_benchmarks/projection_subquery/projection_subquery.suite‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
description = "IN / NOT IN / EXISTS subqueries that appear in the SELECT list instead of a filter (apache/datafusion#25341). Each query projects the boolean result of a subquery and aggregates it, so the measured work is the decorrelation plan and not the output size. The decorrelation turns one projected IN into mark joins; when the join predicate is not hashable, or the correlation is not an equality, the plan keeps a nested-loop mark join and the cost grows with outer rows times inner rows. Query 07 correlates on `<` and stays on that path, so it is the control that must not change. The two tables are built inline by the load SQL and are sized with PSQ_ROWS."
1+
description = "IN / NOT IN / EXISTS subqueries that appear in the SELECT list instead of a filter (apache/datafusion#25341). Each query projects the boolean result of a subquery and aggregates it, so the measured work is the decorrelation plan and not the output size. The decorrelation turns one projected IN into mark joins. Query 07 correlates on `<`, so the correlation stays a residual filter of the mark join. The two tables are built inline by the load SQL and are sized with PSQ_ROWS."
22

33
query_pattern = "q{QUERY_ID_PADDED}.benchmark"
44

‎benchmarks/sql_benchmarks/projection_subquery/queries/q07.sql‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
1-
-- Shape: IN correlated on `<` instead of `=`. There is no equality to hash on,
2-
-- so this query keeps the nested-loop mark joins. It is the control: its cost
3-
-- must stay the same when the hashable cases get faster.
1+
-- Shape: IN correlated on `<` instead of `=`. The `IN` equality is the hash key
2+
-- and the `<` correlation stays a residual filter of the one null-aware mark
3+
-- join, which applies it when it decides whether a NULL makes the mark UNKNOWN.
44
SELECT
55
count(*) FILTER (WHERE m) AS true_count,
66
count(*) FILTER (WHERE m IS NULL) AS null_count

‎datafusion/optimizer/src/decorrelate.rs‎

Lines changed: 49 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -30,7 +30,7 @@ use datafusion_common::{
3030
Column, DFSchemaRef, HashMap, Result, ScalarValue, assert_or_internal_err, plan_err,
3131
};
3232
use datafusion_expr::expr::{Alias, GroupingSet};
33-
use datafusion_expr::logical_plan::Join;
33+
use datafusion_expr::logical_plan::{Join, JoinType};
3434
use datafusion_expr::simplify::SimplifyContext;
3535
use datafusion_expr::utils::{
3636
collect_subquery_cols, conjunction, find_join_exprs, split_conjunction,
@@ -76,6 +76,21 @@ pub struct PullUpCorrelatedExpr {
7676
/// whether we have converted a scalar aggregation into a group aggregation. When unnesting
7777
/// lateral joins, we need to produce a left outer join in such cases.
7878
pub pulled_up_scalar_agg: bool,
79+
/// Every correlated conjunct that a `Filter` of the subquery applies,
80+
/// before `remove_duplicated_filter` drops the ones that the `IN`
81+
/// predicate already covers. The outer references are kept, so that a
82+
/// subquery column and an outer column with the same qualified name stay
83+
/// apart.
84+
///
85+
/// `join_filters` holds only the conjuncts that the join still needs.
86+
/// This list is what the subquery enforces on its own rows. The caller
87+
/// uses it to tell if a join key can be NULL inside the scope of an outer
88+
/// row: `x IN (SELECT y FROM .. WHERE y = x)` keeps every NULL `y` out of
89+
/// its result, although `join_filters` no longer says so.
90+
///
91+
/// The list is cleared when the pull up passes a node that can put a NULL
92+
/// back into such a column: an outer join, a union or a grouping set.
93+
pub correlated_filters: Vec<Expr>,
7994
}
8095

8196
impl Default for PullUpCorrelatedExpr {
@@ -97,6 +112,7 @@ impl PullUpCorrelatedExpr {
97112
collected_count_expr_map: HashMap::new(),
98113
pull_up_having_expr: None,
99114
pulled_up_scalar_agg: false,
115+
correlated_filters: Vec::new(),
100116
}
101117
}
102118

@@ -186,6 +202,12 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
186202
}
187203

188204
fn f_up(&mut self, plan: LogicalPlan) -> Result<Transformed<LogicalPlan>> {
205+
// A node that null-extends or regroups rows can put a NULL back into
206+
// a column that a correlated filter below it rejected, so the filters
207+
// recorded so far no longer bound what the subquery returns.
208+
if !self.correlated_filters.is_empty() && may_reintroduce_nulls(&plan) {
209+
self.correlated_filters.clear();
210+
}
189211
let subquery_schema = plan.schema();
190212
match &plan {
191213
LogicalPlan::Filter(plan_filter) => {
@@ -195,6 +217,11 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
195217
.iter()
196218
.filter(|e| e.contains_outer())
197219
.all(|&e| can_pullup_over_aggregation(e));
220+
for expr in &subquery_filter_exprs {
221+
if expr.contains_outer() && !self.correlated_filters.contains(expr) {
222+
self.correlated_filters.push((*expr).clone());
223+
}
224+
}
198225
let (mut join_filters, subquery_filters) =
199226
find_join_exprs(subquery_filter_exprs)?;
200227
if let Some(in_predicate) = &self.in_predicate_opt {
@@ -548,6 +575,27 @@ impl PullUpCorrelatedExpr {
548575
}
549576
}
550577

578+
/// Whether `plan` can output a NULL in a column that a filter below it keeps
579+
/// free of NULLs: an outer join fills the columns of its unmatched side with
580+
/// NULL, a union adds the rows of its other inputs, and a grouping set fills
581+
/// the columns it leaves out with NULL, such as the grand total row of `ROLLUP`.
582+
fn may_reintroduce_nulls(plan: &LogicalPlan) -> bool {
583+
match plan {
584+
LogicalPlan::Join(join) => {
585+
matches!(
586+
join.join_type,
587+
JoinType::Left | JoinType::Right | JoinType::Full
588+
)
589+
}
590+
LogicalPlan::Union(_) => true,
591+
LogicalPlan::Aggregate(aggregate) => aggregate
592+
.group_expr
593+
.iter()
594+
.any(|expr| matches!(expr, Expr::GroupingSet(_))),
595+
_ => false,
596+
}
597+
}
598+
551599
/// Whether every input of `join` that holds outer references is a side whose
552600
/// rows the join preserves, so a correlated filter below it can be pulled above
553601
/// the join without changing the result.

0 commit comments

Comments
 (0)