Repository navigation
Commit b9c8b3d
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
- projection_subquery
- queries
- datafusion
- optimizer/src
- sqllogictest/test_files
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
48 | 48 | | |
49 | 49 | | |
50 | 50 | | |
51 | | - | |
| 51 | + | |
52 | 52 | | |
53 | 53 | | |
54 | 54 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
1 | | - | |
| 1 | + | |
2 | 2 | | |
3 | 3 | | |
4 | 4 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
1 | | - | |
2 | | - | |
3 | | - | |
| 1 | + | |
| 2 | + | |
| 3 | + | |
4 | 4 | | |
5 | 5 | | |
6 | 6 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
30 | 30 | | |
31 | 31 | | |
32 | 32 | | |
33 | | - | |
| 33 | + | |
34 | 34 | | |
35 | 35 | | |
36 | 36 | | |
| |||
76 | 76 | | |
77 | 77 | | |
78 | 78 | | |
| 79 | + | |
| 80 | + | |
| 81 | + | |
| 82 | + | |
| 83 | + | |
| 84 | + | |
| 85 | + | |
| 86 | + | |
| 87 | + | |
| 88 | + | |
| 89 | + | |
| 90 | + | |
| 91 | + | |
| 92 | + | |
| 93 | + | |
79 | 94 | | |
80 | 95 | | |
81 | 96 | | |
| |||
97 | 112 | | |
98 | 113 | | |
99 | 114 | | |
| 115 | + | |
100 | 116 | | |
101 | 117 | | |
102 | 118 | | |
| |||
186 | 202 | | |
187 | 203 | | |
188 | 204 | | |
| 205 | + | |
| 206 | + | |
| 207 | + | |
| 208 | + | |
| 209 | + | |
| 210 | + | |
189 | 211 | | |
190 | 212 | | |
191 | 213 | | |
| |||
195 | 217 | | |
196 | 218 | | |
197 | 219 | | |
| 220 | + | |
| 221 | + | |
| 222 | + | |
| 223 | + | |
| 224 | + | |
198 | 225 | | |
199 | 226 | | |
200 | 227 | | |
| |||
548 | 575 | | |
549 | 576 | | |
550 | 577 | | |
| 578 | + | |
| 579 | + | |
| 580 | + | |
| 581 | + | |
| 582 | + | |
| 583 | + | |
| 584 | + | |
| 585 | + | |
| 586 | + | |
| 587 | + | |
| 588 | + | |
| 589 | + | |
| 590 | + | |
| 591 | + | |
| 592 | + | |
| 593 | + | |
| 594 | + | |
| 595 | + | |
| 596 | + | |
| 597 | + | |
| 598 | + | |
551 | 599 | | |
552 | 600 | | |
553 | 601 | | |
| |||
0 commit comments