Skip to content

Commit b376290

Browse files
authored
fix: map pushed-down filter columns by position instead of by name (apache#25259)
## Which issue does this PR close? - Closes apache#25244. - Closes apache#25262. - Closes apache#25263. - Closes apache#25264. - Closes apache#21246. - Closes apache#25296. ## Rationale for this change Enabling `datafusion.optimizer.enable_join_dynamic_filter_pushdown` can silently drop matching rows when the probe side of a join contains several columns with the same name, for example `a.id` and `b.id` from a nested join. Physical filter pushdown resolved a pushed filter's columns in the child schema by name, so a predicate on the second `id` column was rewritten to the first `id` column, which holds a different value. The same name-based mapping also affects TopK dynamic filters under the default configuration (apache#25296). For a nested join of orders and payments that both expose `amount`, `ORDER BY p.amount LIMIT 1` can push the payment threshold onto `orders.amount`. Later matching orders are incorrectly pruned, returning `(100, 30)` instead of `(300, 10)`. Every operator that forwards parent filters had the same weakness, in slightly different forms: - `HashJoinExec` computed which output columns belong to each side by position, but then resolved the child column by name. - `FilterExec`, `SortExec`, `RepartitionExec`, `CoalesceBatchesExec`, `UnionExec` and similar nodes used the generic name lookup even though their output positions equal their input positions. - `FilterExec` with an embedded projection resolved unconsumed parent filters back into input coordinates by name. - `ProjectionExec` looked up output aliases by name to find the expression to substitute, so two outputs aliased `id` both mapped to the first. - `AggregateExec` restricted pushdown to grouping positions but resolved the input column by name. The join-filter regression queries return one row with dynamic filtering disabled and zero rows with it enabled across these shapes. The `FilterExec`, `ProjectionExec` and `AggregateExec` cases were found while auditing the remaining name-based paths for apache#25244; they share the root cause, so this PR fixes them together. The TopK case in apache#25296 is fixed by the same positional mapping. ## What changes are included in this PR? Built-in operators now remap filter columns by position. The deprecated public API retains its historical name-based resolution for compatibility. - `FilterRemapper` uses a `ColumnMapping` enum: `Identity` preserves positions and checks that names match; `Explicit` uses a caller-supplied parent-output to child-input mapping and allows names to differ. - `ChildFilterDescription::from_child` now maps by position. New `ChildFilterDescription::from_child_with_column_mapping` takes an explicit `HashMap<usize, usize>`. - `HashJoinExec` builds the explicit mapping from its `column_indices` and output projection. For semi joins, output join keys on the emitted side are mapped to the paired key on the other side, which also supports differently named keys. - `FilterExec` maps through its embedded projection in both pushdown phases and when folding unconsumed parent filters back into its predicate. - `ProjectionExec` substitutes the expression at each output position instead of looking the alias up in the output schema. - `AggregateExec` maps each grouping output position to the input column that grouping expression reads; non-column grouping expressions are not forwarded, as before. - `ChildFilterDescription::from_child_with_allowed_indices` is kept as a deprecated wrapper that preserves name-based resolution to the first matching child field. It translates allowed parent column references into an explicit positional mapping; new callers should supply positions directly to avoid ambiguous duplicate names. ## What is the testing strategy for this PR? - `dynamic_filter_pushdown_config.slt` gains four regression queries over two small Parquet tables, run once with join dynamic filtering disabled and once enabled, asserting identical rows: nested joins with `RepartitionExec` between them (the query from apache#25244), a `FilterExec` with an embedded projection, a `ProjectionExec` with duplicate aliases, and an `AggregateExec` grouping on same-named columns. All four return zero rows on `main` with dynamic filtering enabled. - `dynamic_filter_pushdown_config.slt` also covers apache#25296 using nested joins of orders, payments and customers, with one row per batch and one row per orders Parquet row group. The query returns `(300, 10)` with TopK dynamic filtering disabled, enabled, and enabled together with Parquet filter pushdown. On `main` at `85d4cbb0a9`, both enabled cases reproduce the incorrect `(100, 30)` result; all three pass on this branch. - `datafusion/core/tests/physical_optimizer/filter_pushdown.rs` gains focused tests that call `gather_filters_for_pushdown` directly on `RepartitionExec`, `HashJoinExec` (duplicate child columns with and without projection, both semi join directions with differently named keys, and a semi join whose key is not a plain column), `FilterExec` with a projection in both phases, `ProjectionExec` with duplicate aliases, and `AggregateExec` with reordered same-named grouping columns. Further tests cover the deprecated `from_child_with_allowed_indices` wrapper preserving the first name match, accepting allowed parent indices outside the child schema, and rejecting unresolvable names, the identity mapping rejecting a column whose name differs from the child field at that position, and `FilterExec` rejecting an unconsumed parent filter outside its projection. Passed locally on the updated implementation: - `cargo fmt --all` - `./ci/scripts/doc_prettier_check.sh --write --allow-dirty` - `cargo test --profile ci -p datafusion --test core_integration physical_optimizer::filter_pushdown` — 70 tests passed. - `cargo test --profile ci --test sqllogictests -- dynamic_filter_pushdown_config.slt` — passed. - The isolated apache#25296 regression fails on `main` in both TopK-enabled configurations with the expected wrong-result mismatch. ## Are there any user-facing changes? Queries that push join or TopK dynamic filters through operators with duplicate column names now return the correct rows, including the default-configuration TopK query in apache#25296. API change in `datafusion-physical-plan`: `ChildFilterDescription::from_child_with_allowed_indices` is deprecated in favour of `from_child` and the new `from_child_with_column_mapping`; the deprecated function preserves its previous name-based behavior. Callers should migrate to explicit positions because duplicate names make name resolution ambiguous. `ChildFilterDescription::from_child` also resolves by position, which only affects callers that used it on a node whose output positions differ from its child's.
1 parent ec97d1c commit b376290

8 files changed

Lines changed: 942 additions & 168 deletions

File tree

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

Lines changed: 397 additions & 0 deletions
Large diffs are not rendered by default.

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

Lines changed: 25 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -178,7 +178,7 @@ use crate::{
178178
};
179179
use datafusion_common::config::ConfigOptions;
180180
use parking_lot::Mutex;
181-
use std::collections::{HashMap, HashSet};
181+
use std::collections::HashMap;
182182

183183
use arrow::array::{ArrayRef, UInt8Array, UInt16Array, UInt32Array, UInt64Array};
184184
use arrow::datatypes::{DataType, Field, Schema, SchemaRef};
@@ -2205,13 +2205,27 @@ impl ExecutionPlan for AggregateExec {
22052205
// the result of SUM or COUNT), as those require computing all groups first.
22062206

22072207
// Grouping columns are output before aggregate columns, in the same order
2208-
// as the grouping expressions. A grouping-set null mask marks grouping
2209-
// columns that are not available in that set.
2210-
let mut allowed_indices: HashSet<usize> =
2211-
(0..self.group_by.expr().len()).collect();
2212-
for null_mask in self.group_by.groups() {
2213-
allowed_indices.retain(|idx| null_mask.get(*idx) != Some(&true));
2214-
}
2208+
// as the grouping expressions. Map each grouping output position to the
2209+
// input column it reads, by position rather than by name, so that
2210+
// same-named grouping columns stay distinct. Only grouping expressions
2211+
// that are plain input columns can be mapped; a grouping-set null mask
2212+
// marks grouping columns that are not available in that set.
2213+
let column_mapping: HashMap<usize, usize> = self
2214+
.group_by
2215+
.expr()
2216+
.iter()
2217+
.enumerate()
2218+
.filter(|(idx, _)| {
2219+
self.group_by
2220+
.groups()
2221+
.iter()
2222+
.all(|null_mask| null_mask.get(*idx) != Some(&true))
2223+
})
2224+
.filter_map(|(idx, (expr, _))| {
2225+
expr.downcast_ref::<Column>()
2226+
.map(|column| (idx, column.index()))
2227+
})
2228+
.collect();
22152229

22162230
let child = self.children()[0];
22172231
// Global aggregates and grouping sets containing an empty grouping set
@@ -2227,9 +2241,9 @@ impl ExecutionPlan for AggregateExec {
22272241
let mut child_desc = if may_emit_on_empty_input {
22282242
ChildFilterDescription::all_unsupported(&parent_filters)
22292243
} else {
2230-
ChildFilterDescription::from_child_with_allowed_indices(
2244+
ChildFilterDescription::from_child_with_column_mapping(
22312245
&parent_filters,
2232-
allowed_indices,
2246+
column_mapping,
22332247
child,
22342248
)?
22352249
};
@@ -3175,6 +3189,7 @@ pub fn evaluate_group_by(
31753189

31763190
#[cfg(test)]
31773191
mod tests {
3192+
use std::collections::HashSet;
31783193
use std::task::{Context, Poll};
31793194

31803195
use super::*;

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

Lines changed: 55 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -33,7 +33,7 @@ use crate::common::can_project;
3333
use crate::execution_plan::{CardinalityEffect, replace_children_if_necessary};
3434
use crate::filter_pushdown::{
3535
ChildFilterDescription, ChildPushdownResult, FilterDescription, FilterPushdownPhase,
36-
FilterPushdownPropagation, PushedDown,
36+
FilterPushdownPropagation, FilterRemapper, PushedDown,
3737
};
3838
use crate::limit::LocalLimitExec;
3939
use crate::metrics::{MetricBuilder, MetricType};
@@ -57,7 +57,8 @@ use datafusion_common::config::ConfigOptions;
5757
use datafusion_common::stats::Precision;
5858
use datafusion_common::tree_node::TreeNodeRecursion;
5959
use datafusion_common::{
60-
DataFusionError, Result, ScalarValue, internal_err, plan_err, project_schema,
60+
DataFusionError, Result, ScalarValue, internal_datafusion_err, internal_err,
61+
plan_err, project_schema,
6162
};
6263
use datafusion_execution::TaskContext;
6364
use datafusion_expr::Operator;
@@ -66,7 +67,7 @@ use datafusion_physical_expr::expressions::{
6667
BinaryExpr, Column, InListExpr, IsNotNullExpr, Literal, lit,
6768
};
6869
use datafusion_physical_expr::intervals::utils::check_support;
69-
use datafusion_physical_expr::utils::{collect_columns, reassign_expr_columns};
70+
use datafusion_physical_expr::utils::collect_columns;
7071
use datafusion_physical_expr::{
7172
AcrossPartitions, AnalysisContext, ConstExpr, ExprBoundaries, PhysicalExpr, analyze,
7273
conjunction, split_conjunction,
@@ -316,6 +317,29 @@ impl FilterExec {
316317
self.default_selectivity
317318
}
318319

320+
/// Describe which parent filters (in this node's output coordinates) can
321+
/// be forwarded to the input, remapped into input coordinates.
322+
///
323+
/// With an embedded projection the output position `i` reads input column
324+
/// `projection[i]`; without one the positions are identical. Mapping by
325+
/// position keeps same-named input columns distinct.
326+
fn parent_filters_for_input(
327+
&self,
328+
parent_filters: &[Arc<dyn PhysicalExpr>],
329+
) -> Result<ChildFilterDescription> {
330+
if parent_filters.is_empty() {
331+
return Ok(ChildFilterDescription::empty());
332+
}
333+
match self.projection.as_ref() {
334+
Some(projection) => ChildFilterDescription::from_child_with_column_mapping(
335+
parent_filters,
336+
projection.iter().copied().enumerate().collect(),
337+
self.input(),
338+
),
339+
None => ChildFilterDescription::from_child(parent_filters, self.input()),
340+
}
341+
}
342+
319343
/// Projection
320344
pub fn projection(&self) -> &Option<ProjectionRef> {
321345
&self.projection
@@ -697,21 +721,18 @@ impl ExecutionPlan for FilterExec {
697721
parent_filters: Vec<Arc<dyn PhysicalExpr>>,
698722
_config: &ConfigOptions,
699723
) -> Result<FilterDescription> {
700-
if phase != FilterPushdownPhase::Pre {
701-
let child =
702-
ChildFilterDescription::from_child(&parent_filters, self.input())?;
703-
return Ok(FilterDescription::new().with_child(child));
724+
let mut child = self.parent_filters_for_input(&parent_filters);
725+
if phase == FilterPushdownPhase::Pre {
726+
child = child.map(|child| {
727+
child.with_self_filters(
728+
split_conjunction(&self.predicate)
729+
.into_iter()
730+
.cloned()
731+
.collect(),
732+
)
733+
});
704734
}
705-
706-
let child = ChildFilterDescription::from_child(&parent_filters, self.input())?
707-
.with_self_filters(
708-
split_conjunction(&self.predicate)
709-
.into_iter()
710-
.cloned()
711-
.collect(),
712-
);
713-
714-
Ok(FilterDescription::new().with_child(child))
735+
child.map(|child| FilterDescription::new().with_child(child))
715736
}
716737

717738
fn handle_child_pushdown_result(
@@ -735,12 +756,25 @@ impl ExecutionPlan for FilterExec {
735756

736757
// If this FilterExec has a projection, the unsupported parent filters
737758
// are in the output schema (after projection) coordinates. We need to
738-
// remap them to the input schema coordinates before combining with self filters.
739-
if self.projection.is_some() {
740-
let input_schema = self.input().schema();
759+
// remap them to the input schema coordinates before combining with self
760+
// filters. Map by position through the projection: the input may
761+
// contain several columns with the same name.
762+
if let Some(projection) = self.projection.as_ref()
763+
&& !unsupported_parent_filters.is_empty()
764+
{
765+
let remapper = FilterRemapper::with_column_mapping(
766+
self.input().schema(),
767+
projection.iter().copied().enumerate().collect(),
768+
);
741769
unsupported_parent_filters = unsupported_parent_filters
742770
.into_iter()
743-
.map(|expr| reassign_expr_columns(expr, &input_schema))
771+
.map(|expr| {
772+
remapper.try_remap(&expr)?.ok_or_else(|| {
773+
internal_datafusion_err!(
774+
"Parent filter {expr} references a column that is not in the FilterExec projection {projection:?}"
775+
)
776+
})
777+
})
744778
.collect::<Result<Vec<_>>>()?;
745779
}
746780

0 commit comments

Comments
 (0)