Skip to content

Commit 2c2ecae

Browse files
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/optimizer_rule_reference.md‎

Lines changed: 20 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -73,22 +73,23 @@ in multiple phases.
7373
| ----- | ------------------------------ | ----------------------- | ------------------------------------------------------------------------------------------------------------ |
7474
| 1 | `OutputRequirements` | add phase | Adds helper nodes so output requirements survive later physical rewrites. |
7575
| 2 | `aggregate_statistics` | - | Uses exact source statistics to answer some aggregates without scanning data. |
76-
| 3 | `join_selection` | - | Chooses join implementation, build side, and partition mode from statistics and stream properties. |
77-
| 4 | `LimitedDistinctAggregation` | - | Pushes limit hints into grouped distinct-style aggregations when only a small result is needed. |
78-
| 5 | `FilterPushdown` | pre-optimization phase | Pushes supported physical filters down toward data sources before distribution and sorting are enforced. |
79-
| 6 | `WindowTopN` | - | Replaces eligible row-number window and filter patterns with per-partition TopK execution. |
80-
| 7 | `EnsureRequirements` | - | Enforces both distribution and sorting requirements in a single idempotent rule. |
81-
| 8 | `CombinePartialFinalAggregate` | - | Collapses adjacent partial and final aggregates when the distributed shape makes them redundant. |
82-
| 9 | `OptimizeAggregateOrder` | - | Updates aggregate expressions to use the best ordering once sort requirements are known. |
83-
| 10 | `ProjectionPushdown` | early pass | Pushes projections toward inputs before later physical rewrites add more limit and TopK structure. |
84-
| 11 | `OutputRequirements` | remove phase | Removes the temporary output-requirement helper nodes after requirement-sensitive planning is done. |
85-
| 12 | `LimitAggregation` | - | Passes a limit hint into eligible aggregations so they can keep fewer accumulator buckets. |
86-
| 13 | `LimitPushPastWindows` | - | Pushes fetch limits through bounded window operators when doing so keeps the result correct. |
87-
| 14 | `HashJoinBuffering` | - | Adds buffering on the probe side of hash joins so probing can start before build completion. |
88-
| 15 | `LimitPushdown` | - | Moves physical limits into child operators or fetch-enabled variants to cut data early. |
89-
| 16 | `TopKRepartition` | - | Pushes TopK below hash repartition when the partition key is a prefix of the sort key. |
90-
| 17 | `ProjectionPushdown` | late pass | Runs projection pushdown again after limit and TopK rewrites expose new pruning opportunities. |
91-
| 18 | `PushdownSort` | - | Pushes sort requirements into data sources that can already return sorted output. |
92-
| 19 | `EnsureCooperative` | - | Wraps non-cooperative plan parts so long-running tasks yield fairly. |
93-
| 20 | `FilterPushdown(Post)` | post-optimization phase | Pushes dynamic filters at the end of optimization, after plan references stop moving. |
94-
| 21 | `SanityCheckPlan` | - | Validates that the final physical plan meets ordering, distribution, and infinite-input safety requirements. |
76+
| 3 | `EliminateConstantJoin` | - | Replaces inner joins against a single row of literals with a filter that keeps the other input's order. |
77+
| 4 | `join_selection` | - | Chooses join implementation, build side, and partition mode from statistics and stream properties. |
78+
| 5 | `LimitedDistinctAggregation` | - | Pushes limit hints into grouped distinct-style aggregations when only a small result is needed. |
79+
| 6 | `FilterPushdown` | pre-optimization phase | Pushes supported physical filters down toward data sources before distribution and sorting are enforced. |
80+
| 7 | `WindowTopN` | - | Replaces eligible row-number window and filter patterns with per-partition TopK execution. |
81+
| 8 | `EnsureRequirements` | - | Enforces both distribution and sorting requirements in a single idempotent rule. |
82+
| 9 | `CombinePartialFinalAggregate` | - | Collapses adjacent partial and final aggregates when the distributed shape makes them redundant. |
83+
| 10 | `OptimizeAggregateOrder` | - | Updates aggregate expressions to use the best ordering once sort requirements are known. |
84+
| 11 | `ProjectionPushdown` | early pass | Pushes projections toward inputs before later physical rewrites add more limit and TopK structure. |
85+
| 12 | `OutputRequirements` | remove phase | Removes the temporary output-requirement helper nodes after requirement-sensitive planning is done. |
86+
| 13 | `LimitAggregation` | - | Passes a limit hint into eligible aggregations so they can keep fewer accumulator buckets. |
87+
| 14 | `LimitPushPastWindows` | - | Pushes fetch limits through bounded window operators when doing so keeps the result correct. |
88+
| 15 | `HashJoinBuffering` | - | Adds buffering on the probe side of hash joins so probing can start before build completion. |
89+
| 16 | `LimitPushdown` | - | Moves physical limits into child operators or fetch-enabled variants to cut data early. |
90+
| 17 | `TopKRepartition` | - | Pushes TopK below hash repartition when the partition key is a prefix of the sort key. |
91+
| 18 | `ProjectionPushdown` | late pass | Runs projection pushdown again after limit and TopK rewrites expose new pruning opportunities. |
92+
| 19 | `PushdownSort` | - | Pushes sort requirements into data sources that can already return sorted output. |
93+
| 20 | `EnsureCooperative` | - | Wraps non-cooperative plan parts so long-running tasks yield fairly. |
94+
| 21 | `FilterPushdown(Post)` | post-optimization phase | Pushes dynamic filters at the end of optimization, after plan references stop moving. |
95+
| 22 | `SanityCheckPlan` | - | Validates that the final physical plan meets ordering, distribution, and infinite-input safety requirements. |
Lines changed: 201 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,201 @@
1+
// Licensed to the Apache Software Foundation (ASF) under one
2+
// or more contributor license agreements. See the NOTICE file
3+
// distributed with this work for additional information
4+
// regarding copyright ownership. The ASF licenses this file
5+
// to you under the Apache License, Version 2.0 (the
6+
// "License"); you may not use this file except in compliance
7+
// with the License. You may obtain a copy of the License at
8+
//
9+
// http://www.apache.org/licenses/LICENSE-2.0
10+
//
11+
// Unless required by applicable law or agreed to in writing,
12+
// software distributed under the License is distributed on an
13+
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14+
// KIND, either express or implied. See the License for the
15+
// specific language governing permissions and limitations
16+
// under the License.
17+
18+
//! Integration tests for the [`EliminateConstantJoin`] physical optimizer rule.
19+
//! Cases that SQL can express are in `eliminate_constant_join.slt`.
20+
21+
use std::collections::HashMap;
22+
use std::sync::Arc;
23+
24+
use arrow::array::{Int64Array, RecordBatch};
25+
use arrow::compute::concat_batches;
26+
use arrow::datatypes::{DataType, Field, Schema};
27+
use arrow::util::pretty::pretty_format_batches;
28+
use datafusion::datasource::MemTable;
29+
use datafusion::datasource::memory::MemorySourceConfig;
30+
use datafusion::execution::session_state::SessionStateBuilder;
31+
use datafusion::prelude::{SessionConfig, SessionContext};
32+
use datafusion_common::config::ConfigOptions;
33+
use datafusion_common::{JoinSide, JoinType, Result};
34+
use datafusion_expr::Operator;
35+
use datafusion_physical_expr::expressions::{BinaryExpr, Column, lit};
36+
use datafusion_physical_optimizer::PhysicalOptimizerRule;
37+
use datafusion_physical_optimizer::eliminate_constant_join::EliminateConstantJoin;
38+
use datafusion_physical_plan::joins::NestedLoopJoinExec;
39+
use datafusion_physical_plan::joins::utils::{ColumnIndex, JoinFilter};
40+
use datafusion_physical_plan::placeholder_row::PlaceholderRowExec;
41+
use datafusion_physical_plan::projection::ProjectionExec;
42+
use datafusion_physical_plan::{ExecutionPlan, collect};
43+
44+
/// A placeholder emits one row per partition, so a two-partition constant input
45+
/// matches every row twice.
46+
#[tokio::test]
47+
async fn keeps_join_with_multi_row_constant() -> Result<()> {
48+
let schema = Arc::new(Schema::new(vec![Field::new("t", DataType::Int64, true)]));
49+
let batch = RecordBatch::try_new(
50+
Arc::clone(&schema),
51+
vec![Arc::new(Int64Array::from(vec![10, 30]))],
52+
)?;
53+
let events = MemorySourceConfig::try_new_exec(&[vec![batch]], schema, None)?;
54+
let constant = Arc::new(ProjectionExec::try_new(
55+
[(lit(25i64), "cutoff".to_string())],
56+
Arc::new(PlaceholderRowExec::new(Arc::new(Schema::empty())).with_partitions(2)),
57+
)?);
58+
let filter = JoinFilter::new(
59+
Arc::new(BinaryExpr::new(
60+
Arc::new(Column::new("t", 0)),
61+
Operator::Lt,
62+
Arc::new(Column::new("cutoff", 1)),
63+
)),
64+
vec![
65+
ColumnIndex {
66+
index: 0,
67+
side: JoinSide::Left,
68+
},
69+
ColumnIndex {
70+
index: 0,
71+
side: JoinSide::Right,
72+
},
73+
],
74+
Arc::new(Schema::new(vec![
75+
Field::new("t", DataType::Int64, true),
76+
Field::new("cutoff", DataType::Int64, false),
77+
])),
78+
);
79+
let join: Arc<dyn ExecutionPlan> = Arc::new(NestedLoopJoinExec::try_new(
80+
events,
81+
constant,
82+
Some(filter),
83+
&JoinType::Inner,
84+
None,
85+
)?);
86+
87+
let optimized = EliminateConstantJoin::new()
88+
.optimize(Arc::clone(&join), &ConfigOptions::new())?;
89+
assert_eq!(rows(optimized).await?, rows(join).await?);
90+
Ok(())
91+
}
92+
93+
/// Lambda variables are numbered after the join filter's own columns, so a filter
94+
/// over the wider input would read the wrong columns.
95+
#[tokio::test]
96+
async fn keeps_join_with_lambda_filter() -> Result<()> {
97+
// Plan without optimizer rules: projection pushdown cannot yet plan lambdas in
98+
// nested-loop join filters.
99+
let config =
100+
SessionConfig::new().set_str("datafusion.sql_parser.dialect", "databricks");
101+
let ctx = SessionContext::new_with_state(
102+
SessionStateBuilder::new()
103+
.with_config(config)
104+
.with_default_features()
105+
.with_physical_optimizer_rules(vec![])
106+
.build(),
107+
);
108+
ctx.sql(
109+
"CREATE TABLE lists AS \
110+
SELECT * FROM (VALUES ([1, 30], 'a', 7), ([40], 'b', 8)) AS v(l, k, n)",
111+
)
112+
.await?
113+
.collect()
114+
.await?;
115+
let join = ctx
116+
.sql(
117+
"SELECT s.k, s.n FROM (SELECT 25 AS cutoff) c \
118+
JOIN lists s ON array_any_match(s.l, x -> x < c.cutoff)",
119+
)
120+
.await?
121+
.create_physical_plan()
122+
.await?;
123+
124+
let optimized = EliminateConstantJoin::new()
125+
.optimize(Arc::clone(&join), &ConfigOptions::new())?;
126+
assert_eq!(rows(optimized).await?, rows(join).await?);
127+
Ok(())
128+
}
129+
130+
/// The rewritten plan keeps the schema metadata that came from the constant input;
131+
/// otherwise the optimizer's schema check fails the query.
132+
#[tokio::test]
133+
async fn keeps_metadata_of_constant_input() -> Result<()> {
134+
// With `*`, no projection above the join keeps the metadata.
135+
let sql = "SELECT * FROM (SELECT count(*) AS n FROM tagged) c \
136+
JOIN events e ON e.t >= c.n";
137+
let expected = rows(
138+
metadata_session(false)?
139+
.sql(sql)
140+
.await?
141+
.create_physical_plan()
142+
.await?,
143+
)
144+
.await?;
145+
let ctx = metadata_session(true)?;
146+
let plan = ctx.sql(sql).await?.create_physical_plan().await?;
147+
assert_eq!(rows(plan).await?, expected);
148+
Ok(())
149+
}
150+
151+
/// Registers `events` and `tagged`, a table whose schema carries metadata, with the
152+
/// default rules, without [`EliminateConstantJoin`] unless `eliminate` is set.
153+
fn metadata_session(eliminate: bool) -> Result<SessionContext> {
154+
let mut state = SessionStateBuilder::new().with_default_features().build();
155+
if !eliminate {
156+
let rules = state
157+
.physical_optimizers()
158+
.iter()
159+
.filter(|rule| rule.name() != EliminateConstantJoin::new().name())
160+
.cloned()
161+
.collect();
162+
state = SessionStateBuilder::new_from_existing(state)
163+
.with_physical_optimizer_rules(rules)
164+
.build();
165+
}
166+
let ctx = SessionContext::new_with_state(state);
167+
for (name, metadata) in [
168+
("events", HashMap::new()),
169+
(
170+
"tagged",
171+
HashMap::from([("source".to_string(), "tagged".to_string())]),
172+
),
173+
] {
174+
let schema = Arc::new(Schema::new_with_metadata(
175+
vec![Field::new("t", DataType::Int64, true)],
176+
metadata,
177+
));
178+
let batch = RecordBatch::try_new(
179+
Arc::clone(&schema),
180+
vec![Arc::new(Int64Array::from(vec![1, 2, 3]))],
181+
)?;
182+
ctx.register_table(
183+
name,
184+
Arc::new(MemTable::try_new(schema, vec![vec![batch]])?),
185+
)?;
186+
}
187+
Ok(ctx)
188+
}
189+
190+
/// Runs `plan` and formats its rows in sorted order.
191+
async fn rows(plan: Arc<dyn ExecutionPlan>) -> Result<Vec<String>> {
192+
let schema = plan.schema();
193+
let batches = collect(plan, Arc::new(Default::default())).await?;
194+
let mut rows = pretty_format_batches(&[concat_batches(&schema, &batches)?])?
195+
.to_string()
196+
.lines()
197+
.map(str::to_string)
198+
.collect::<Vec<_>>();
199+
rows.sort_unstable();
200+
Ok(rows)
201+
}

‎datafusion/core/tests/physical_optimizer/mod.rs‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -20,6 +20,7 @@
2020
#[expect(clippy::needless_pass_by_value)]
2121
mod aggregate_statistics;
2222
mod combine_partial_final_agg;
23+
mod eliminate_constant_join;
2324
#[expect(clippy::needless_pass_by_value)]
2425
mod enforce_distribution;
2526
mod enforce_sorting;

0 commit comments

Comments
 (0)