Repository navigation
Commit 2c2ecae
authored
feat: rewrite inner joins against a single constant row into a filter (apache#26404)
## Which issue does this PR close?
- Closes apache#26349.
## Rationale for this change
`AggregateStatistics` can answer a scalar subquery such as `(SELECT
min(ts) FROM live)` from statistics and replace it with a row of
literals. A join against that row still runs as a `NestedLoopJoinExec`,
or as a `CrossJoinExec` when the join has no condition.
That join only filters its other input, but neither join operator
preserves its inputs' ordering. Operators above it therefore lose the
input's ordering. For example, an aggregation grouped by the input's
sort key can no longer emit each group as soon as its sort key changes
(`group_clustering_mode=Full`) and must hold every group until the end.
The literal bound is also not pushed into the scan for pruning.
## What changes are included in this PR?
A new physical optimizer rule, `EliminateConstantJoin`, runs right after
`AggregateStatistics`. It applies when one input of an inner
`NestedLoopJoinExec` or a `CrossJoinExec` is provably a single row of
literals: projections over a single-partition `PlaceholderRowExec`. The
rule substitutes the literals into the join filter. It then replaces the
join with a `FilterExec` over the other input, under a `ProjectionExec`
that restores the join's output schema and metadata. A cross join has no
filter, so it becomes only the projection. Besides dropping ordering,
`CrossJoinExec` buffers its other input as the build side when that
input has no statistics.
At this point in the optimizer, a folded `min(ts) AS first_ts` is still
an alias projection over the literal projection, so the rule follows
stacked projections. Expressions over a folded value, such as `min(ts) +
1`, only become constant at this point, so the rule folds them with
`PhysicalExprSimplifier`.
The rule leaves the join unchanged when:
- the join is not an inner join;
- the placeholder has more than one partition, because it emits one row
per partition;
- a value does not fold to a literal; for example, `random()` would then
be evaluated per row instead of once;
- the join filter contains a lambda, because lambda variables are
numbered after the filter's own columns, not the other input's.
## What is the testing strategy for this PR?
- `eliminate_constant_join.slt` has plans and results for four rewrites:
a scalar folded from Parquet statistics, an expression over it (`min(ts)
+ 1`), a cross join, and a literal subquery. In the first and the cross
join, the aggregation becomes `group_clustering_mode=Full`; the bound is
pushed into the Parquet scan. The file also checks that a left join and
a `random()` constant keep the join.
- `physical_optimizer/eliminate_constant_join.rs` covers cases SQL
cannot reach:
- a multi-partition placeholder;
- a lambda join filter, planned without optimizer rules because
projection pushdown cannot plan it yet (apache#26399);
- schema metadata that comes from the constant input.
- `explain.slt`: `EXPLAIN VERBOSE` lists the new rule.
- `cte.slt`, `joins.slt`: `j1, LATERAL (SELECT 1)` now plans a
projection instead of a `CrossJoinExec`.
## Are there any user-facing changes?
Queries that join against a row folded from statistics, or against a
literal subquery, now plan a filter and a projection instead of a nested
loop join or cross join. `EXPLAIN VERBOSE` and
`PhysicalOptimizer::new()` include the new rule. There are no API
changes.1 parent 3ee3e39 commit 2c2ecae
10 files changed
Lines changed: 655 additions & 25 deletions
File tree
- datafusion
- core
- src
- tests/physical_optimizer
- physical-optimizer/src
- sqllogictest/test_files
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
73 | 73 | | |
74 | 74 | | |
75 | 75 | | |
76 | | - | |
77 | | - | |
78 | | - | |
79 | | - | |
80 | | - | |
81 | | - | |
82 | | - | |
83 | | - | |
84 | | - | |
85 | | - | |
86 | | - | |
87 | | - | |
88 | | - | |
89 | | - | |
90 | | - | |
91 | | - | |
92 | | - | |
93 | | - | |
94 | | - | |
| 76 | + | |
| 77 | + | |
| 78 | + | |
| 79 | + | |
| 80 | + | |
| 81 | + | |
| 82 | + | |
| 83 | + | |
| 84 | + | |
| 85 | + | |
| 86 | + | |
| 87 | + | |
| 88 | + | |
| 89 | + | |
| 90 | + | |
| 91 | + | |
| 92 | + | |
| 93 | + | |
| 94 | + | |
| 95 | + | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
| 1 | + | |
| 2 | + | |
| 3 | + | |
| 4 | + | |
| 5 | + | |
| 6 | + | |
| 7 | + | |
| 8 | + | |
| 9 | + | |
| 10 | + | |
| 11 | + | |
| 12 | + | |
| 13 | + | |
| 14 | + | |
| 15 | + | |
| 16 | + | |
| 17 | + | |
| 18 | + | |
| 19 | + | |
| 20 | + | |
| 21 | + | |
| 22 | + | |
| 23 | + | |
| 24 | + | |
| 25 | + | |
| 26 | + | |
| 27 | + | |
| 28 | + | |
| 29 | + | |
| 30 | + | |
| 31 | + | |
| 32 | + | |
| 33 | + | |
| 34 | + | |
| 35 | + | |
| 36 | + | |
| 37 | + | |
| 38 | + | |
| 39 | + | |
| 40 | + | |
| 41 | + | |
| 42 | + | |
| 43 | + | |
| 44 | + | |
| 45 | + | |
| 46 | + | |
| 47 | + | |
| 48 | + | |
| 49 | + | |
| 50 | + | |
| 51 | + | |
| 52 | + | |
| 53 | + | |
| 54 | + | |
| 55 | + | |
| 56 | + | |
| 57 | + | |
| 58 | + | |
| 59 | + | |
| 60 | + | |
| 61 | + | |
| 62 | + | |
| 63 | + | |
| 64 | + | |
| 65 | + | |
| 66 | + | |
| 67 | + | |
| 68 | + | |
| 69 | + | |
| 70 | + | |
| 71 | + | |
| 72 | + | |
| 73 | + | |
| 74 | + | |
| 75 | + | |
| 76 | + | |
| 77 | + | |
| 78 | + | |
| 79 | + | |
| 80 | + | |
| 81 | + | |
| 82 | + | |
| 83 | + | |
| 84 | + | |
| 85 | + | |
| 86 | + | |
| 87 | + | |
| 88 | + | |
| 89 | + | |
| 90 | + | |
| 91 | + | |
| 92 | + | |
| 93 | + | |
| 94 | + | |
| 95 | + | |
| 96 | + | |
| 97 | + | |
| 98 | + | |
| 99 | + | |
| 100 | + | |
| 101 | + | |
| 102 | + | |
| 103 | + | |
| 104 | + | |
| 105 | + | |
| 106 | + | |
| 107 | + | |
| 108 | + | |
| 109 | + | |
| 110 | + | |
| 111 | + | |
| 112 | + | |
| 113 | + | |
| 114 | + | |
| 115 | + | |
| 116 | + | |
| 117 | + | |
| 118 | + | |
| 119 | + | |
| 120 | + | |
| 121 | + | |
| 122 | + | |
| 123 | + | |
| 124 | + | |
| 125 | + | |
| 126 | + | |
| 127 | + | |
| 128 | + | |
| 129 | + | |
| 130 | + | |
| 131 | + | |
| 132 | + | |
| 133 | + | |
| 134 | + | |
| 135 | + | |
| 136 | + | |
| 137 | + | |
| 138 | + | |
| 139 | + | |
| 140 | + | |
| 141 | + | |
| 142 | + | |
| 143 | + | |
| 144 | + | |
| 145 | + | |
| 146 | + | |
| 147 | + | |
| 148 | + | |
| 149 | + | |
| 150 | + | |
| 151 | + | |
| 152 | + | |
| 153 | + | |
| 154 | + | |
| 155 | + | |
| 156 | + | |
| 157 | + | |
| 158 | + | |
| 159 | + | |
| 160 | + | |
| 161 | + | |
| 162 | + | |
| 163 | + | |
| 164 | + | |
| 165 | + | |
| 166 | + | |
| 167 | + | |
| 168 | + | |
| 169 | + | |
| 170 | + | |
| 171 | + | |
| 172 | + | |
| 173 | + | |
| 174 | + | |
| 175 | + | |
| 176 | + | |
| 177 | + | |
| 178 | + | |
| 179 | + | |
| 180 | + | |
| 181 | + | |
| 182 | + | |
| 183 | + | |
| 184 | + | |
| 185 | + | |
| 186 | + | |
| 187 | + | |
| 188 | + | |
| 189 | + | |
| 190 | + | |
| 191 | + | |
| 192 | + | |
| 193 | + | |
| 194 | + | |
| 195 | + | |
| 196 | + | |
| 197 | + | |
| 198 | + | |
| 199 | + | |
| 200 | + | |
| 201 | + | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
20 | 20 | | |
21 | 21 | | |
22 | 22 | | |
| 23 | + | |
23 | 24 | | |
24 | 25 | | |
25 | 26 | | |
| |||
0 commit comments