Skip to content

Commit 909f4ce

Browse files
committed
fix: correlated scalar subquery returns NULL when HAVING filters out the row
A scalar subquery that aggregates with count(*) compensates unmatched LEFT JOIN rows with the empty-input aggregate result, so outer rows with no matching inner row get 0. That is correct in general, but when the subquery has a HAVING clause (or a filter above the aggregate) that references an outer column, an unmatched row can also mean the condition rejected the aggregate output: the subquery produced no row, and the scalar subquery must evaluate to NULL. Leaving the condition in the join ON conflates the two cases, so a row whose real count fails the HAVING still receives the default whenever the condition passes on it. Record the outer-reference conditions of filters that sit directly above a count-bug aggregate during decorrelation, leave them out of the join ON when the subquery's output column gets a compensation expression, and check them in the compensation CASE instead: the default (0 for count(*)) when they hold on the defaults for an unmatched row, NULL when they reject a matched group, and the actual output otherwise. An output whose own default is NULL has no compensation expression to check them in, so for those the conditions keep filtering in the ON. Closes apache#26503
2 parents 16fbc31 + c18e5d9 commit 909f4ce

21 files changed

Lines changed: 2610 additions & 980 deletions

File tree

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

Lines changed: 145 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -43,7 +43,7 @@ use datafusion_physical_expr_common::sort_expr::{
4343
LexOrdering, PhysicalSortExpr, PhysicalSortRequirement, OrderingRequirements
4444
};
4545
use datafusion_physical_expr::{Distribution, Partitioning, PhysicalExpr};
46-
use datafusion_physical_expr::expressions::{col, BinaryExpr, Column, NotExpr};
46+
use datafusion_physical_expr::expressions::{col, is_not_null, BinaryExpr, Column, NotExpr};
4747
use datafusion_physical_plan::joins::{HashJoinExec, PartitionMode};
4848
use datafusion_physical_plan::limit::{GlobalLimitExec, LocalLimitExec};
4949
use datafusion_physical_plan::repartition::RepartitionExec;
@@ -359,6 +359,150 @@ async fn test_do_not_remove_sort_with_limit() -> Result<()> {
359359
Ok(())
360360
}
361361

362+
#[test]
363+
fn test_do_not_remove_sort_with_limit_after_projection() -> Result<()> {
364+
let schema = create_test_schema()?;
365+
let source = parquet_exec(Arc::clone(&schema));
366+
let sort = sort_exec([sort_expr("non_nullable_col", &schema)].into(), source);
367+
// Dropping the sort key hides the output ordering, but preserves the row
368+
// sequence that determines which rows a limit skips or returns.
369+
let projection = projection_exec(
370+
vec![(col("nullable_col", &schema)?, "nullable_col".to_string())],
371+
sort,
372+
)?;
373+
assert!(projection.output_ordering().is_none());
374+
375+
let mut config = ConfigOptions::new();
376+
config.execution.target_partitions = 1;
377+
let filter = filter_exec(
378+
is_not_null(col("nullable_col", &projection.schema())?)?,
379+
Arc::clone(&projection),
380+
);
381+
for input in [projection, filter] {
382+
for plan in [
383+
global_limit_exec(Arc::clone(&input), 1, None),
384+
global_limit_exec(Arc::clone(&input), 1, Some(1)),
385+
global_limit_exec(Arc::clone(&input), 0, Some(1)),
386+
local_limit_exec(input, 1),
387+
] {
388+
let optimized =
389+
EnsureRequirements::new().optimize(Arc::clone(&plan), &config)?;
390+
let optimized = SanityCheckPlan::new().optimize(optimized, &config)?;
391+
assert_eq!(get_plan_string(&optimized), get_plan_string(&plan));
392+
}
393+
}
394+
Ok(())
395+
}
396+
397+
#[test]
398+
fn test_required_sort_after_projection() -> Result<()> {
399+
let schema = create_test_schema()?;
400+
let source = parquet_exec(Arc::clone(&schema));
401+
let sort = sort_exec([sort_expr("non_nullable_col", &schema)].into(), source);
402+
let projection = projection_exec(
403+
vec![(col("nullable_col", &schema)?, "nullable_col".to_string())],
404+
sort,
405+
)?;
406+
let filter = filter_exec(
407+
is_not_null(col("nullable_col", &projection.schema())?)?,
408+
projection,
409+
);
410+
let mut config = ConfigOptions::new();
411+
config.execution.target_partitions = 1;
412+
413+
for with_limit in [false, true] {
414+
let input = if with_limit {
415+
global_limit_exec(Arc::clone(&filter), 1, None)
416+
} else {
417+
Arc::clone(&filter)
418+
};
419+
let window = bounded_window_exec(
420+
"nullable_col",
421+
[sort_expr("nullable_col", &input.schema())],
422+
input,
423+
);
424+
let optimized = EnsureRequirements::new().optimize(window, &config)?;
425+
let optimized = SanityCheckPlan::new().optimize(optimized, &config)?;
426+
let twice =
427+
EnsureRequirements::new().optimize(Arc::clone(&optimized), &config)?;
428+
assert_eq!(get_plan_string(&twice), get_plan_string(&optimized));
429+
430+
if with_limit {
431+
// The window needs its own sort, but OFFSET still depends on the
432+
// hidden sort to select rows.
433+
assert_snapshot!(displayable(optimized.as_ref()).indent(true), @r#"
434+
BoundedWindowAggExec: wdw=[count: Field { "count": Int64 }, frame: RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW], mode=[Sorted]
435+
SortExec: expr=[nullable_col@0 ASC], preserve_partitioning=[false]
436+
GlobalLimitExec: skip=1, fetch=None
437+
FilterExec: nullable_col@0 IS NOT NULL
438+
ProjectionExec: expr=[nullable_col@0 as nullable_col]
439+
SortExec: expr=[non_nullable_col@1 ASC], preserve_partitioning=[false]
440+
DataSourceExec: file_groups={1 group: [[x]]}, projection=[nullable_col, non_nullable_col], file_type=parquet
441+
"#);
442+
} else {
443+
// Without a limit, the window's ordering supersedes the hidden sort.
444+
assert_snapshot!(displayable(optimized.as_ref()).indent(true), @r#"
445+
BoundedWindowAggExec: wdw=[count: Field { "count": Int64 }, frame: RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW], mode=[Sorted]
446+
SortExec: expr=[nullable_col@0 ASC], preserve_partitioning=[false]
447+
FilterExec: nullable_col@0 IS NOT NULL
448+
ProjectionExec: expr=[nullable_col@0 as nullable_col]
449+
DataSourceExec: file_groups={1 group: [[x]]}, projection=[nullable_col, non_nullable_col], file_type=parquet
450+
"#);
451+
}
452+
}
453+
Ok(())
454+
}
455+
456+
#[tokio::test]
457+
async fn test_do_not_remove_sort_below_fetch_after_projection() -> Result<()> {
458+
let batch =
459+
record_batch!(("a", Int32, [30, 10, 20, 40]), ("b", Int32, [2, 4, 1, 3]))?;
460+
let schema = batch.schema();
461+
let source = Arc::new(DataSourceExec::new(Arc::new(
462+
datafusion::datasource::memory::MemorySourceConfig::try_new(
463+
&[vec![batch]],
464+
Arc::clone(&schema),
465+
None,
466+
)?,
467+
))) as Arc<dyn ExecutionPlan>;
468+
let sort = sort_exec([sort_expr("b", &schema)].into(), source);
469+
let filter = filter_exec(is_not_null(col("a", &schema)?)?, sort)
470+
.with_fetch(Some(2))
471+
.unwrap();
472+
let projection =
473+
projection_exec(vec![(col("a", &schema)?, "a".to_string())], filter)?;
474+
assert!(projection.output_ordering().is_none());
475+
476+
// The window needs a new ordering, but the filter's embedded limit still
477+
// depends on the hidden sort to select a=20 and a=30.
478+
let window =
479+
bounded_window_exec("a", [sort_expr("a", &projection.schema())], projection);
480+
let mut config = ConfigOptions::new();
481+
config.execution.target_partitions = 1;
482+
let optimized = EnsureRequirements::new().optimize(window, &config)?;
483+
let optimized = SanityCheckPlan::new().optimize(optimized, &config)?;
484+
let twice = EnsureRequirements::new().optimize(Arc::clone(&optimized), &config)?;
485+
assert_eq!(get_plan_string(&twice), get_plan_string(&optimized));
486+
487+
for plan in [optimized, twice] {
488+
let results =
489+
datafusion_physical_plan::collect(plan, Arc::new(TaskContext::default()))
490+
.await?;
491+
datafusion_common::assert_batches_eq!(
492+
[
493+
"+----+-------+",
494+
"| a | count |",
495+
"+----+-------+",
496+
"| 20 | 1 |",
497+
"| 30 | 2 |",
498+
"+----+-------+",
499+
],
500+
&results
501+
);
502+
}
503+
Ok(())
504+
}
505+
362506
#[tokio::test]
363507
async fn test_union_inputs_sorted() -> Result<()> {
364508
let schema = create_test_schema()?;

‎datafusion/optimizer/src/scalar_subquery_to_join.rs‎

Lines changed: 15 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -363,22 +363,21 @@ fn build_join(
363363
.build()?;
364364

365365
// A HAVING-like condition recorded from a filter above the aggregate can
366-
// leave the join ON only when every empty-input default gets a
367-
// compensation CASE below: an aggregate whose default is NULL has no CASE
368-
// to check such a condition in, so for those it keeps filtering in the
369-
// ON as before.
370-
let having_in_compensation = match &collected_count_expr_map {
371-
Some(expr_map) if !expr_map.is_empty() => expr_map.values().try_fold(
372-
true,
373-
|all_compensated, default_expr| -> Result<bool> {
374-
Ok(all_compensated
375-
&& !evaluates_to_null(
376-
default_expr.clone(),
377-
default_expr.column_refs(),
378-
)?)
379-
},
380-
)?,
381-
_ => false,
366+
// leave the join ON only when the subquery's output column gets a
367+
// compensation CASE below, because that CASE is what checks the condition
368+
// for an unmatched row. The map also holds aggregates that appear only in
369+
// the HAVING, whose NULL defaults need no CASE of their own, so the gate
370+
// looks at the output column alone; an output whose own default is NULL
371+
// (the subquery projects `max`, say) keeps filtering in the ON as before.
372+
let output_name = subquery_plan.schema().field(0).name();
373+
let having_in_compensation = match collected_count_expr_map
374+
.as_ref()
375+
.and_then(|expr_map| expr_map.get(output_name))
376+
{
377+
Some(default_expr) => {
378+
!evaluates_to_null(default_expr.clone(), default_expr.column_refs())?
379+
}
380+
None => false,
382381
};
383382

384383
// With the HAVING-like conditions out of the ON, an unmatched row means

‎datafusion/optimizer/src/single_distinct_to_groupby.rs‎

Lines changed: 39 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -30,7 +30,7 @@ use datafusion_expr::builder::project;
3030
use datafusion_expr::expr::AggregateFunctionParams;
3131
use datafusion_expr::expr_schema::ExprSchemable;
3232
use datafusion_expr::{
33-
AggregateUDF, Expr, col,
33+
AggregateUDF, Expr, cast, col,
3434
expr::AggregateFunction,
3535
lit,
3636
logical_plan::{Aggregate, LogicalPlan},
@@ -402,6 +402,12 @@ impl OptimizerRule for SingleDistinctToGroupBy {
402402
.map(|(expr, _)| expr.clone())
403403
.collect();
404404

405+
let outer_aggr = LogicalPlan::Aggregate(Aggregate::try_new(
406+
Arc::new(inner_agg),
407+
outer_group_exprs,
408+
outer_aggr_exprs,
409+
)?);
410+
405411
// so the aggregates are displayed in the same way even after the rewrite
406412
// this optimizer has two kinds of alias:
407413
// - group_by aggr
@@ -417,15 +423,16 @@ impl OptimizerRule for SingleDistinctToGroupBy {
417423
.chain(outer_proj_exprs.into_iter().enumerate().map(|(idx, expr)| {
418424
let idx = idx + group_size;
419425
let (qualifier, field) = schema.qualified_field(idx);
426+
let current_type = outer_aggr.schema().field(idx).data_type();
427+
let expr = if current_type != field.data_type() {
428+
cast(expr, field.data_type().clone())
429+
} else {
430+
expr
431+
};
420432
expr.alias_qualified(qualifier.cloned(), field.name())
421433
}))
422434
.collect();
423435

424-
let outer_aggr = LogicalPlan::Aggregate(Aggregate::try_new(
425-
Arc::new(inner_agg),
426-
outer_group_exprs,
427-
outer_aggr_exprs,
428-
)?);
429436
Ok(Transformed::yes(project(outer_aggr, alias_expr)?))
430437
}
431438
_ => Ok(Transformed::no(plan)),
@@ -1310,4 +1317,30 @@ mod tests {
13101317
",
13111318
)
13121319
}
1320+
1321+
#[test]
1322+
fn sum_decimal_with_distinct_preserves_declared_type() -> Result<()> {
1323+
let schema = Schema::new(vec![
1324+
Field::new("d", DataType::Decimal128(5, 2), false),
1325+
Field::new("x", DataType::Int32, false),
1326+
]);
1327+
let table_scan = table_scan(Some("test"), &schema, None)?.build()?;
1328+
1329+
let plan = LogicalPlanBuilder::from(table_scan)
1330+
.aggregate(
1331+
Vec::<Expr>::new(),
1332+
vec![sum(col("d")), count_distinct(col("x"))],
1333+
)?
1334+
.build()?;
1335+
1336+
let rule: Arc<dyn OptimizerRule + Send + Sync> =
1337+
Arc::new(SingleDistinctToGroupBy::new());
1338+
let optimizer = Optimizer::with_rules(vec![rule]);
1339+
let optimized_plan = optimizer
1340+
.optimize(plan.clone(), &RegistryOptimizerContext::new(), |_, _| {})
1341+
.expect("failed to optimize plan");
1342+
1343+
assert_eq!(plan.schema().as_ref(), optimized_plan.schema().as_ref());
1344+
Ok(())
1345+
}
13131346
}

‎datafusion/physical-optimizer/src/ensure_requirements/enforce_sorting/mod.rs‎

Lines changed: 12 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -102,8 +102,9 @@ fn update_sort_ctx_children_data(
102102
child_node.data = if is_sort(child_plan) {
103103
// child is sort
104104
true
105-
} else if is_limit(child_plan) {
106-
// There is no sort linkage for this path, it starts at a limit.
105+
} else if is_limit(child_plan) || child_plan.fetch().is_some() {
106+
// Removing a sort below a row limit can change which rows survive,
107+
// including limits embedded in operators such as FilterExec.
107108
false
108109
} else {
109110
// If a descendent is a sort, and the child maintains the sort.
@@ -427,16 +428,14 @@ pub fn ensure_sorting(
427428
.zip(requirements.children)
428429
.enumerate()
429430
{
430-
let physical_ordering = child.plan.output_ordering();
431-
432431
if let Some(required) = required_ordering {
433432
let eq_properties = child.plan.equivalence_properties();
434433
let req = required.into_single();
435434
if !eq_properties.ordering_satisfy_requirement(req.clone())? {
436-
// Make sure we preserve the ordering requirements:
437-
if physical_ordering.is_some() {
438-
child = update_child_to_remove_unnecessary_sort(idx, child, plan)?;
439-
}
435+
// The new sort supersedes linked sorts even when a projection
436+
// hides their keys. Explicit and embedded limits stop sort
437+
// linkage, preserving sorts that determine which rows survive.
438+
child = update_child_to_remove_unnecessary_sort(idx, child, plan)?;
440439
child = add_sort_above(
441440
child,
442441
req,
@@ -446,9 +445,11 @@ pub fn ensure_sorting(
446445
);
447446
child = update_sort_ctx_children_data(child, true)?;
448447
}
449-
} else if physical_ordering.is_none() || !plan.maintains_input_order()[idx] {
450-
// We have a `SortExec` whose effect may be neutralized by another
451-
// order-imposing operator, remove this sort:
448+
} else if !plan.maintains_input_order()[idx] {
449+
// Remove linked sorts only when this operator does not preserve
450+
// their row order. A projection can hide the sort key, making
451+
// output_ordering() None, while a later LIMIT or OFFSET still
452+
// depends on that order to select rows.
452453
child = update_child_to_remove_unnecessary_sort(idx, child, plan)?;
453454
}
454455
updated_children.push(child);

0 commit comments

Comments
 (0)