Skip to content

Commit 260b243

Browse files
discord9lukekim
authored andcommitted
fix: preserve aggregate filter pushdown order (apache#22926)
## Which issue does this PR close? - Closes apache#22925. ## Rationale for this change `FilterPushdown` maps each child pushdown result back to its original parent filter by position. `AggregateExec::gather_filters_for_pushdown` previously split parent filters into safe and unsafe buckets and then concatenated the results, which changed their order. For example, in `cnt@2 = 1 AND b@1 = bar`, the grouping-column predicate on `b` can cross the aggregate, while the predicate on aggregate output `cnt` must remain above it. Reordering the returned results could make the optimizer associate the pushed-down `b` result with the `cnt` predicate and incorrectly remove the latter. Aggregate pushdown also needs to account for empty-input semantics. A global aggregate, or a grouping-sets aggregate containing `()`, can emit a row even when its input is empty. Moving any parent predicate below such an aggregate — including a column-free predicate such as `false` — can therefore change the result. ## What changes are included in this PR? - Preserve parent-filter order by constructing each child description once with `ChildFilterDescription::from_child_with_allowed_indices`. - Allow only grouping-output columns that are present in every grouping set; aggregate-result columns remain above the aggregate. - Mark all parent filters unsupported for global aggregates and grouping sets containing an empty grouping set, while retaining aggregate-generated dynamic filters. - Validate that every child returns one parent-filter result per input filter before positional remapping. - Add physical optimizer and SQL regression coverage for mixed filter order, global-aggregate name collisions, constant predicates, and grouping sets. ## Are these changes tested? Yes: - `cargo test -p datafusion --test core_integration physical_optimizer::filter_pushdown` - `cargo fmt --all -- --check` - `cargo check -p datafusion-physical-plan -p datafusion-physical-optimizer` - `git diff --check upstream/main` - Full GitHub CI, including Rust tests, clippy, and sqllogictests ## Are there any user-facing changes? There are no public API changes. Filter pushdown now preserves mixed aggregate predicates correctly and avoids moving predicates across aggregates when doing so could change empty-input results. (cherry picked from commit 2f25454)
1 parent 6a4a698 commit 260b243

6 files changed

Lines changed: 253 additions & 91 deletions

File tree

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

Lines changed: 171 additions & 28 deletions
Original file line numberDiff line numberDiff line change
@@ -41,8 +41,13 @@ use datafusion_datasource::{
4141
use datafusion_execution::object_store::ObjectStoreUrl;
4242
use datafusion_expr::ScalarUDF;
4343
use datafusion_functions::math::random::RandomFunc;
44-
use datafusion_functions_aggregate::{count::count_udaf, min_max::min_udaf};
45-
use datafusion_physical_expr::{LexOrdering, PhysicalSortExpr, expressions::col};
44+
use datafusion_functions_aggregate::{
45+
count::count_udaf,
46+
min_max::{max_udaf, min_udaf},
47+
};
48+
use datafusion_physical_expr::{
49+
LexOrdering, PhysicalSortExpr, expressions::col, utils::conjunction,
50+
};
4651
use datafusion_physical_expr::{
4752
Partitioning, ScalarFunctionExpr, aggregate::AggregateExprBuilder,
4853
};
@@ -819,6 +824,65 @@ fn test_pushdown_through_aggregates_on_grouping_columns() {
819824
);
820825
}
821826

827+
#[test]
828+
fn test_pushdown_through_aggregates_preserves_parent_filter_order() {
829+
// AggregateExec may push filters on grouping columns to its input, but must
830+
// keep filters on aggregate outputs above itself. The parent-filter result
831+
// order must match the incoming filter order, otherwise an unsupported
832+
// aggregate-output filter can be reported as pushed down and removed.
833+
let scan = TestScanBuilder::new(schema()).with_support(true).build();
834+
835+
let aggregate_expr = vec![
836+
AggregateExprBuilder::new(count_udaf(), vec![col("a", &schema()).unwrap()])
837+
.schema(schema())
838+
.alias("cnt")
839+
.build()
840+
.map(Arc::new)
841+
.unwrap(),
842+
];
843+
let group_by = PhysicalGroupBy::new_single(vec![
844+
(col("a", &schema()).unwrap(), "a".to_string()),
845+
(col("b", &schema()).unwrap(), "b".to_string()),
846+
]);
847+
let aggregate = Arc::new(
848+
AggregateExec::try_new(
849+
AggregateMode::Final,
850+
group_by,
851+
aggregate_expr,
852+
vec![None],
853+
scan,
854+
schema(),
855+
)
856+
.unwrap(),
857+
);
858+
859+
let aggregate_schema = aggregate.schema();
860+
let aggregate_output_filter = col_lit_predicate(
861+
"cnt",
862+
ScalarValue::Int64(Some(1)),
863+
aggregate_schema.as_ref(),
864+
);
865+
let grouping_key_filter = col_lit_predicate("b", "bar", aggregate_schema.as_ref());
866+
let predicate = conjunction(vec![aggregate_output_filter, grouping_key_filter]);
867+
let plan = Arc::new(FilterExec::try_new(predicate, aggregate).unwrap());
868+
869+
insta::assert_snapshot!(
870+
OptimizationTest::new(plan, FilterPushdown::new(), true),
871+
@r"
872+
OptimizationTest:
873+
input:
874+
- FilterExec: cnt@2 = 1 AND b@1 = bar
875+
- AggregateExec: mode=Final, gby=[a@0 as a, b@1 as b], aggr=[cnt]
876+
- DataSourceExec: file_groups={1 group: [[test.parquet]]}, projection=[a, b, c], file_type=test, pushdown_supported=true
877+
output:
878+
Ok:
879+
- FilterExec: cnt@2 = 1
880+
- AggregateExec: mode=Final, gby=[a@0 as a, b@1 as b], aggr=[cnt], ordering_mode=PartiallySorted([1])
881+
- DataSourceExec: file_groups={1 group: [[test.parquet]]}, projection=[a, b, c], file_type=test, pushdown_supported=true, predicate=b@1 = bar
882+
"
883+
);
884+
}
885+
822886
/// Test various combinations of handling of child pushdown results
823887
/// in an ExecutionPlan in combination with support/not support in a DataSource.
824888
#[test]
@@ -1834,6 +1898,16 @@ fn col_lit_predicate(
18341898
))
18351899
}
18361900

1901+
fn assert_parent_filter_remains_above_aggregate(plan: Arc<dyn ExecutionPlan>) {
1902+
let mut config = ConfigOptions::default();
1903+
config.execution.parquet.pushdown_filters = true;
1904+
let optimized = FilterPushdown::new().optimize(plan, &config).unwrap();
1905+
assert!(
1906+
optimized.downcast_ref::<FilterExec>().is_some(),
1907+
"parent filter must remain above aggregate"
1908+
);
1909+
}
1910+
18371911
// ==== Aggregate Dynamic Filter tests ====
18381912
//
18391913
// The end-to-end min/max dynamic filter cases (simple/min/max/mixed/all-nulls)
@@ -2078,13 +2152,65 @@ fn test_pushdown_grouping_sets_filter_on_common_column() {
20782152
);
20792153
}
20802154

2155+
#[tokio::test]
2156+
async fn test_no_pushdown_through_global_aggregate_with_name_collision() {
2157+
let input_schema =
2158+
Arc::new(Schema::new(vec![Field::new("a", DataType::Int64, false)]));
2159+
let scan = TestScanBuilder::new(Arc::clone(&input_schema))
2160+
.with_support(true)
2161+
.with_batches(vec![record_batch!(("a", Int64, [1, 20])).unwrap()])
2162+
.build();
2163+
let aggregate_expr = vec![
2164+
AggregateExprBuilder::new(max_udaf(), vec![col("a", &input_schema).unwrap()])
2165+
.schema(Arc::clone(&input_schema))
2166+
.alias("a")
2167+
.build()
2168+
.map(Arc::new)
2169+
.unwrap(),
2170+
];
2171+
let aggregate = Arc::new(
2172+
AggregateExec::try_new(
2173+
AggregateMode::Single,
2174+
PhysicalGroupBy::new_single(vec![]),
2175+
aggregate_expr,
2176+
vec![None],
2177+
scan,
2178+
input_schema,
2179+
)
2180+
.unwrap(),
2181+
);
2182+
2183+
// This is a physical filter above the aggregate, not a SQL WHERE clause.
2184+
// Pushing it through would evaluate input `a` instead of MAX(a).
2185+
let predicate = Arc::new(BinaryExpr::new(
2186+
col("a", aggregate.schema().as_ref()).unwrap(),
2187+
Operator::Lt,
2188+
Arc::new(Literal::new(ScalarValue::Int64(Some(10)))),
2189+
));
2190+
let plan = Arc::new(FilterExec::try_new(predicate, aggregate).unwrap());
2191+
2192+
let mut config = ConfigOptions::default();
2193+
config.execution.parquet.pushdown_filters = true;
2194+
let optimized = FilterPushdown::new().optimize(plan, &config).unwrap();
2195+
assert!(optimized.downcast_ref::<FilterExec>().is_some());
2196+
2197+
let session_ctx = SessionContext::new();
2198+
session_ctx.register_object_store(
2199+
ObjectStoreUrl::parse("test://").unwrap().as_ref(),
2200+
Arc::new(InMemory::new()),
2201+
);
2202+
let batches = collect(optimized, session_ctx.state().task_ctx())
2203+
.await
2204+
.unwrap();
2205+
assert!(
2206+
batches.is_empty(),
2207+
"MAX(a) = 20 must be filtered out instead of applying a < 10 to input rows"
2208+
);
2209+
}
2210+
20812211
#[test]
2082-
fn test_pushdown_with_empty_group_by() {
2083-
// Test that filters can be pushed down when GROUP BY is empty (no grouping columns)
2084-
// SELECT count(*) as cnt FROM table WHERE a = 'foo'
2085-
// There are no grouping columns, so the filter should still push down
2212+
fn test_no_pushdown_constant_false_through_global_aggregate() {
20862213
let scan = TestScanBuilder::new(schema()).with_support(true).build();
2087-
20882214
let aggregate_expr = vec![
20892215
AggregateExprBuilder::new(count_udaf(), vec![col("c", &schema()).unwrap()])
20902216
.schema(schema())
@@ -2093,41 +2219,58 @@ fn test_pushdown_with_empty_group_by() {
20932219
.map(Arc::new)
20942220
.unwrap(),
20952221
];
2222+
let aggregate = Arc::new(
2223+
AggregateExec::try_new(
2224+
AggregateMode::Final,
2225+
PhysicalGroupBy::new_single(vec![]),
2226+
aggregate_expr,
2227+
vec![None],
2228+
scan,
2229+
schema(),
2230+
)
2231+
.unwrap(),
2232+
);
2233+
let predicate = Arc::new(Literal::new(ScalarValue::Boolean(Some(false))));
2234+
let plan = Arc::new(FilterExec::try_new(predicate, aggregate).unwrap());
20962235

2097-
// Empty GROUP BY - no grouping columns
2098-
let group_by = PhysicalGroupBy::new_single(vec![]);
2236+
assert_parent_filter_remains_above_aggregate(plan);
2237+
}
20992238

2239+
#[test]
2240+
fn test_no_pushdown_constant_false_through_empty_grouping_set() {
2241+
let scan = TestScanBuilder::new(schema()).with_support(true).build();
2242+
let group_by = PhysicalGroupBy::new(
2243+
vec![(col("a", &schema()).unwrap(), "a".to_string())],
2244+
vec![(
2245+
Arc::new(Literal::new(ScalarValue::Utf8(None))),
2246+
"a".to_string(),
2247+
)],
2248+
vec![vec![true]],
2249+
true,
2250+
);
2251+
let aggregate_expr = vec![
2252+
AggregateExprBuilder::new(count_udaf(), vec![col("c", &schema()).unwrap()])
2253+
.schema(schema())
2254+
.alias("cnt")
2255+
.build()
2256+
.map(Arc::new)
2257+
.unwrap(),
2258+
];
21002259
let aggregate = Arc::new(
21012260
AggregateExec::try_new(
21022261
AggregateMode::Final,
21032262
group_by,
2104-
aggregate_expr.clone(),
2263+
aggregate_expr,
21052264
vec![None],
21062265
scan,
21072266
schema(),
21082267
)
21092268
.unwrap(),
21102269
);
2111-
2112-
// Filter on 'a'
2113-
let predicate = col_lit_predicate("a", "foo", &schema());
2270+
let predicate = Arc::new(Literal::new(ScalarValue::Boolean(Some(false))));
21142271
let plan = Arc::new(FilterExec::try_new(predicate, aggregate).unwrap());
21152272

2116-
// The filter should be pushed down even with empty GROUP BY
2117-
insta::assert_snapshot!(
2118-
OptimizationTest::new(plan, FilterPushdown::new(), true),
2119-
@r"
2120-
OptimizationTest:
2121-
input:
2122-
- FilterExec: a@0 = foo
2123-
- AggregateExec: mode=Final, gby=[], aggr=[cnt]
2124-
- DataSourceExec: file_groups={1 group: [[test.parquet]]}, projection=[a, b, c], file_type=test, pushdown_supported=true
2125-
output:
2126-
Ok:
2127-
- AggregateExec: mode=Final, gby=[], aggr=[cnt]
2128-
- DataSourceExec: file_groups={1 group: [[test.parquet]]}, projection=[a, b, c], file_type=test, pushdown_supported=true, predicate=a@0 = foo
2129-
"
2130-
);
2273+
assert_parent_filter_remains_above_aggregate(plan);
21312274
}
21322275

21332276
#[test]

‎datafusion/physical-optimizer/src/filter_pushdown.rs‎

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -486,6 +486,14 @@ fn push_down_filters(
486486
// currently. `self_filters` are the predicates which are provided by the current node,
487487
// and tried to be pushed down over the child similarly.
488488

489+
assert_eq_or_internal_err!(
490+
parent_filters.len(),
491+
parent_filtered.len(),
492+
"Filter pushdown expected {} to return one parent filter result per input filter for child {}",
493+
node.name(),
494+
child_idx
495+
);
496+
489497
// Filter out self_filters that contain volatile expressions and track indices
490498
let self_filtered = FilteredVec::new(&self_filters, allow_pushdown_for_expr);
491499

‎datafusion/physical-plan/src/aggregates/mod.rs‎

Lines changed: 27 additions & 63 deletions
Original file line numberDiff line numberDiff line change
@@ -28,15 +28,14 @@ use crate::aggregates::{
2828
use crate::execution_plan::{CardinalityEffect, EmissionType};
2929
use crate::filter_pushdown::{
3030
ChildFilterDescription, ChildPushdownResult, FilterDescription, FilterPushdownPhase,
31-
FilterPushdownPropagation, PushedDownPredicate,
31+
FilterPushdownPropagation,
3232
};
3333
use crate::metrics::{ExecutionPlanMetricsSet, MetricsSet};
3434
use crate::{
3535
DisplayFormatType, Distribution, ExecutionPlan, InputOrderMode,
3636
SendableRecordBatchStream, Statistics, check_if_same_properties,
3737
};
3838
use datafusion_common::config::ConfigOptions;
39-
use datafusion_physical_expr::utils::collect_columns;
4039
use parking_lot::Mutex;
4140
use std::collections::{HashMap, HashSet};
4241

@@ -1649,70 +1648,35 @@ impl ExecutionPlan for AggregateExec {
16491648
// This optimization is NOT safe for filters on aggregated columns (like filtering on
16501649
// the result of SUM or COUNT), as those require computing all groups first.
16511650

1652-
// Build grouping columns using output indices because parent filters reference the
1653-
// AggregateExec's output schema where grouping columns in the output schema. The
1654-
// grouping expressions reference input columns which may not match the output schema.
1655-
//
1656-
// It is safe to assume that the output_schema contains group by columns in the same order
1657-
// as the group by expression. See [`create_schema`] and [`AggregateExec`].
1658-
let output_schema = self.schema();
1659-
let grouping_columns: HashSet<_> = (0..self.group_by.expr().len())
1660-
.map(|i| Column::new(output_schema.field(i).name(), i))
1661-
.collect();
1662-
1663-
// Analyze each filter separately to determine if it can be pushed down
1664-
let mut safe_filters = Vec::new();
1665-
let mut unsafe_filters = Vec::new();
1666-
1667-
for filter in parent_filters {
1668-
let filter_columns: HashSet<_> =
1669-
collect_columns(&filter).into_iter().collect();
1670-
1671-
// Check if this filter references non-grouping columns
1672-
let references_non_grouping = !grouping_columns.is_empty()
1673-
&& !filter_columns.is_subset(&grouping_columns);
1674-
1675-
if references_non_grouping {
1676-
unsafe_filters.push(filter);
1677-
continue;
1678-
}
1679-
1680-
// For GROUPING SETS, verify this filter's columns appear in all grouping sets
1681-
if self.group_by.groups().len() > 1 {
1682-
let filter_column_indices: Vec<usize> = filter_columns
1683-
.iter()
1684-
.filter_map(|filter_col| {
1685-
grouping_columns.get(filter_col).map(|col| col.index())
1686-
})
1687-
.collect();
1688-
1689-
// Check if any of this filter's columns are missing from any grouping set
1690-
let has_missing_column = self.group_by.groups().iter().any(|null_mask| {
1691-
filter_column_indices
1692-
.iter()
1693-
.any(|&idx| null_mask.get(idx) == Some(&true))
1694-
});
1695-
1696-
if has_missing_column {
1697-
unsafe_filters.push(filter);
1698-
continue;
1699-
}
1700-
}
1701-
1702-
// This filter is safe to push down
1703-
safe_filters.push(filter);
1651+
// Grouping columns are output before aggregate columns, in the same order
1652+
// as the grouping expressions. A grouping-set null mask marks grouping
1653+
// columns that are not available in that set.
1654+
let mut allowed_indices: HashSet<usize> =
1655+
(0..self.group_by.expr().len()).collect();
1656+
for null_mask in self.group_by.groups() {
1657+
allowed_indices.retain(|idx| null_mask.get(*idx) != Some(&true));
17041658
}
17051659

1706-
// Build child filter description with both safe and unsafe filters
17071660
let child = self.children()[0];
1708-
let mut child_desc = ChildFilterDescription::from_child(&safe_filters, child)?;
1709-
1710-
// Add unsafe filters as unsupported
1711-
child_desc.parent_filters.extend(
1712-
unsafe_filters
1713-
.into_iter()
1714-
.map(PushedDownPredicate::unsupported),
1715-
);
1661+
// Global aggregates and grouping sets containing an empty grouping set
1662+
// emit a row even when their input is empty. Parent filters therefore
1663+
// cannot be pushed below them, including filters without column
1664+
// references.
1665+
let may_emit_on_empty_input = self.group_by.is_true_no_grouping()
1666+
|| self
1667+
.group_by
1668+
.groups()
1669+
.iter()
1670+
.any(|null_mask| null_mask.iter().all(|is_null| *is_null));
1671+
let mut child_desc = if may_emit_on_empty_input {
1672+
ChildFilterDescription::all_unsupported(&parent_filters)
1673+
} else {
1674+
ChildFilterDescription::from_child_with_allowed_indices(
1675+
&parent_filters,
1676+
allowed_indices,
1677+
child,
1678+
)?
1679+
};
17161680

17171681
// Include self dynamic filter when it's possible
17181682
if phase == FilterPushdownPhase::Post

‎datafusion/physical-plan/src/execution_plan.rs‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -578,6 +578,12 @@ pub trait ExecutionPlan: Any + Debug + DisplayAs + Send + Sync {
578578
/// There are two different phases in filter pushdown, which some operators may handle the same and some differently.
579579
/// Depending on the phase the operator may or may not be allowed to modify the plan.
580580
/// See [`FilterPushdownPhase`] for more details.
581+
///
582+
/// Implementations must preserve the order of `parent_filters` in the
583+
/// returned child [`FilterDescription`]: each child parent-filter result is
584+
/// matched back to the corresponding input parent filter by position.
585+
/// Unsupported filters should therefore be marked unsupported in place,
586+
/// rather than removed or appended after supported filters.
581587
fn gather_filters_for_pushdown(
582588
&self,
583589
_phase: FilterPushdownPhase,

0 commit comments

Comments
 (0)