Skip to content

Commit fb7bca4

Browse files
adriangbclaude
andcommitted
feat: push filters that all references share into the body of a materialized CTE
The new logical optimizer rule PushDownMaterializedCteFilter runs after PushDownFilter. If each scan of a materialized CTE has a filter directly above it, the rule puts the disjunction of these filters on top of the body of the CTE. Each scan keeps its filter. PushDownFilter then moves the new filter into the body in the subsequent pass. The rule uses only the deterministic terms of a filter that have no subquery and no outer reference. A body with a volatile expression is not changed, because the physical filter pushdown can give a copy of the filter, with the volatile expression in it, to the data source. MaterializedCte has the new field pushed_filter, which records the filter that the rule added, so that the rule does not add the same filter again in a subsequent optimizer pass. Closes apache#26239. Co-Authored-By: Claude Opus 5.5 <[email protected]>
1 parent 0356f37 commit fb7bca4

8 files changed

Lines changed: 1380 additions & 26 deletions

File tree

‎datafusion/core/src/optimizer_rule_reference.md‎

Lines changed: 8 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -56,13 +56,14 @@ Rule order matters. The default pipeline may change between releases.
5656
| 17 | `eliminate_outer_join` | Rewrites outer joins to inner joins when later filters reject the NULL-extended rows. |
5757
| 18 | `push_down_limit` | Moves literal limits closer to scans and unions and merges adjacent limits. |
5858
| 19 | `push_down_filter` | Moves filters as early as possible through filter-commutative operators. |
59-
| 20 | `eliminate_aggregate_distinct` | Drops the `DISTINCT` modifier from aggregates whose result cannot change, such as `min`, `max` and `bit_or`. |
60-
| 21 | `single_distinct_aggregation_to_group_by` | Rewrites single-column `DISTINCT` aggregations into two-stage `GROUP BY` plans. |
61-
| 22 | `eliminate_group_by_constant` | Removes constant or functionally redundant expressions from `GROUP BY`. |
62-
| 23 | `common_sub_expression_eliminate` | Computes repeated subexpressions once and reuses the result. |
63-
| 24 | `extract_leaf_expressions` | Pulls cheap leaf expressions closer to data sources so later pruning and filter rules can act earlier. |
64-
| 25 | `push_down_leaf_projections` | Pushes the helper projections created by leaf extraction toward leaf inputs. |
65-
| 26 | `optimize_projections` | Prunes unused columns and removes unnecessary logical projections. |
59+
| 20 | `push_down_materialized_cte_filter` | Filters the body of a materialized CTE with the disjunction of the filters of its references, if each reference has one. |
60+
| 21 | `eliminate_aggregate_distinct` | Drops the `DISTINCT` modifier from aggregates whose result cannot change, such as `min`, `max` and `bit_or`. |
61+
| 22 | `single_distinct_aggregation_to_group_by` | Rewrites single-column `DISTINCT` aggregations into two-stage `GROUP BY` plans. |
62+
| 23 | `eliminate_group_by_constant` | Removes constant or functionally redundant expressions from `GROUP BY`. |
63+
| 24 | `common_sub_expression_eliminate` | Computes repeated subexpressions once and reuses the result. |
64+
| 25 | `extract_leaf_expressions` | Pulls cheap leaf expressions closer to data sources so later pruning and filter rules can act earlier. |
65+
| 26 | `push_down_leaf_projections` | Pushes the helper projections created by leaf extraction toward leaf inputs. |
66+
| 27 | `optimize_projections` | Prunes unused columns and removes unnecessary logical projections. |
6667

6768
### Physical Optimizer Rules
6869

‎datafusion/expr/src/logical_plan/materialized_cte.rs‎

Lines changed: 37 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -26,7 +26,9 @@
2626
//!
2727
//! The scans are leaves, so filters and projections of one reference are not
2828
//! pushed into the shared body. This is the same optimization fence that
29-
//! PostgreSQL applies to `MATERIALIZED` CTEs.
29+
//! PostgreSQL applies to `MATERIALIZED` CTEs. One exception: if each
30+
//! reference has a filter, the optimizer filters the body with the disjunction
31+
//! of these filters (see [`MaterializedCte::pushed_filter`]).
3032
3133
use std::cmp::Ordering;
3234
use std::fmt;
@@ -37,7 +39,7 @@ use std::sync::atomic::{AtomicU64, Ordering as AtomicOrdering};
3739
use datafusion_common::tree_node::TreeNodeRecursion;
3840
use datafusion_common::{DFSchemaRef, Result};
3941

40-
use crate::LogicalPlan;
42+
use crate::{Expr, LogicalPlan};
4143

4244
/// Identifies one materialized CTE and binds its scans to it.
4345
///
@@ -94,6 +96,9 @@ pub struct MaterializedCte {
9496
pub cte: Arc<LogicalPlan>,
9597
/// The query that declared the CTE and reads it
9698
pub continuation: Arc<LogicalPlan>,
99+
/// The filter that the optimizer added to `cte` from the filters of the
100+
/// scans, if any. See [`Self::pushed_filter`].
101+
pub pushed_filter: Option<Expr>,
97102
}
98103

99104
impl MaterializedCte {
@@ -122,6 +127,7 @@ impl MaterializedCte {
122127
name,
123128
cte,
124129
continuation,
130+
pushed_filter: None,
125131
})
126132
}
127133

@@ -156,8 +162,19 @@ impl MaterializedCte {
156162
MaterializedCteScan::find_in(&self.continuation, self.id)
157163
}
158164

159-
/// Return a node with the same id and name, and new inputs. The schemas
160-
/// of the scans are not checked again.
165+
/// The filter that the optimizer added to the body from the filters of
166+
/// the scans, with the columns that the body had at that time.
167+
///
168+
/// This is a record only, and it is not an expression of the node. The
169+
/// filter itself is in the body, where other rules can move or change it.
170+
/// The optimizer uses the record so that it does not add the same filter
171+
/// to the body again in a subsequent pass.
172+
pub fn pushed_filter(&self) -> Option<&Expr> {
173+
self.pushed_filter.as_ref()
174+
}
175+
176+
/// Return a node with the same id, name and [`Self::pushed_filter`], and
177+
/// new inputs. The schemas of the scans are not checked again.
161178
pub fn with_new_inputs(
162179
&self,
163180
cte: Arc<LogicalPlan>,
@@ -168,6 +185,7 @@ impl MaterializedCte {
168185
name: self.name.clone(),
169186
cte,
170187
continuation,
188+
pushed_filter: self.pushed_filter.clone(),
171189
}
172190
}
173191
}
@@ -315,10 +333,25 @@ mod tests {
315333
name: "c".to_string(),
316334
cte: empty(false),
317335
continuation: empty(false),
336+
pushed_filter: None,
318337
};
319338
let mut b = a.clone();
320339
assert_eq!(a.partial_cmp(&b), Some(Ordering::Equal));
321340

341+
// The record of the pushed filter is part of the node, and stays when
342+
// the inputs are replaced.
343+
b.pushed_filter = Some(crate::lit(true));
344+
assert_ne!(a, b);
345+
assert_eq!(a.partial_cmp(&b), None);
346+
assert_eq!(b.with_new_inputs(empty(false), empty(false)), b);
347+
let plan = LogicalPlan::MaterializedCte(MaterializedCtePlan::Cte(b.clone()));
348+
assert_eq!(
349+
plan.with_new_exprs(vec![], vec![(*empty(false)).clone(); 2])
350+
.unwrap(),
351+
plan
352+
);
353+
b.pushed_filter = None;
354+
322355
b.continuation = empty(true);
323356
assert_ne!(a, b);
324357
assert_eq!(a.partial_cmp(&b), None);

‎datafusion/expr/src/logical_plan/tree_node.rs‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -382,6 +382,7 @@ impl TreeNode for LogicalPlan {
382382
name,
383383
cte,
384384
continuation,
385+
pushed_filter,
385386
})) => {
386387
(cte, continuation)
387388
.map_elements(f)?
@@ -392,6 +393,7 @@ impl TreeNode for LogicalPlan {
392393
name,
393394
cte,
394395
continuation,
396+
pushed_filter,
395397
},
396398
))
397399
})

‎datafusion/optimizer/src/lib.rs‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -66,6 +66,7 @@ pub mod optimizer;
6666
pub mod propagate_empty_relation;
6767
pub mod push_down_filter;
6868
pub mod push_down_limit;
69+
pub mod push_down_materialized_cte_filter;
6970
pub mod replace_distinct_aggregate;
7071
pub mod rewrite_set_comparison;
7172
pub mod scalar_subquery_to_join;

‎datafusion/optimizer/src/optimizer.rs‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -61,6 +61,7 @@ use crate::plan_signature::LogicalPlanSignature;
6161
use crate::propagate_empty_relation::PropagateEmptyRelation;
6262
use crate::push_down_filter::PushDownFilter;
6363
use crate::push_down_limit::PushDownLimit;
64+
use crate::push_down_materialized_cte_filter::PushDownMaterializedCteFilter;
6465
use crate::replace_distinct_aggregate::ReplaceDistinctWithAggregate;
6566
use crate::rewrite_set_comparison::RewriteSetComparison;
6667
use crate::scalar_subquery_to_join::ScalarSubqueryToJoin;
@@ -306,6 +307,7 @@ impl Optimizer {
306307
// Filters can't be pushed down past Limits, we should do PushDownFilter after PushDownLimit
307308
Arc::new(PushDownLimit::new()),
308309
Arc::new(PushDownFilter::new()),
310+
Arc::new(PushDownMaterializedCteFilter::new()),
309311
Arc::new(EliminateAggregateDistinct::new()),
310312
Arc::new(SingleDistinctToGroupBy::new()),
311313
// The previous optimizations added expressions and projections,

0 commit comments

Comments
 (0)