Skip to content

Commit dd0fa23

Browse files
committed
fix: return a query error for correlated scalar subquery with outer-column HAVING over count aggregates
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. 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. Keeping the condition in the join ON conflates the two cases, and moving it into the compensation CASE needs the condition evaluated against the defaults for an unmatched row and against the actual output for a matched one, so either choice is wrong for the rows the other one covers. Record the outer-reference conditions of filters that sit directly above a count-bug aggregate during decorrelation, and fail the query when the subquery's output column needs a compensation expression: an error beats a number nobody can trust. An output whose own default is NULL needs no compensation and keeps filtering in the ON, and a HAVING that reads no outer column is still handled by the existing having arm. Closes apache#26503
2 parents 16fbc31 + c18e5d9 commit dd0fa23

22 files changed

Lines changed: 2641 additions & 1089 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/decorrelate.rs‎

Lines changed: 9 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -82,11 +82,12 @@ pub struct PullUpCorrelatedExpr {
8282
/// pull up having expr, which must be evaluated after the Join
8383
pub pull_up_having_expr: Option<Expr>,
8484
/// Outer-reference conditions from a `Filter` that sits directly above a
85-
/// count-bug `Aggregate` — i.e. a `HAVING` clause (or an outer-only
86-
/// filter) that filters the aggregate *output*. Unlike `join_filters`,
87-
/// these do not merely correlate the two sides: when the LEFT JOIN is
88-
/// unmatched because one of them failed, the subquery produced no row and
89-
/// a scalar subquery must yield NULL rather than the empty-input default.
85+
/// count-bug `Aggregate`: a `HAVING` clause (or an outer-only filter)
86+
/// that filters the aggregate *output*. Unlike `join_filters`, these do
87+
/// not merely correlate the two sides: an unmatched LEFT JOIN row may
88+
/// mean one of them rejected the group rather than that no group
89+
/// matched, and a scalar subquery must yield NULL for a rejected group.
90+
/// `build_join` uses them to reject such queries up front.
9091
pub having_like_join_filters: Vec<Expr>,
9192
/// whether we have converted a scalar aggregation into a group aggregation. When unnesting
9293
/// lateral joins, we need to produce a left outer join in such cases.
@@ -417,10 +418,9 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
417418
// its outer-reference conditions filter the aggregate *output*,
418419
// so a LEFT JOIN row can be unmatched either because the
419420
// correlation matched no group or because one of them rejected
420-
// the group. Record them for the scalar count-bug
421-
// compensation, which re-checks them itself so that both cases
422-
// give the subquery's real answer: the empty-input default
423-
// when they hold on it, NULL otherwise. A `Filter` below the
421+
// the group. Record them so the scalar rewrite can tell the
422+
// two apart; where the output needs count-bug compensation it
423+
// rejects the query instead of guessing. A `Filter` below the
424424
// aggregate only prunes input rows and is left out.
425425
if self
426426
.collected_count_expr_map

‎datafusion/optimizer/src/scalar_subquery_to_join.rs‎

Lines changed: 29 additions & 88 deletions
Original file line numberDiff line numberDiff line change
@@ -362,41 +362,37 @@ fn build_join(
362362
.alias(subquery_alias.to_string())?
363363
.build()?;
364364

365-
// 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,
382-
};
383-
384-
// With the HAVING-like conditions out of the ON, an unmatched row means
385-
// the correlation matched no group, and the compensation CASE checks the
386-
// conditions in both directions instead.
387-
let join_filters = if having_in_compensation {
388-
pull_up
389-
.join_filters
390-
.iter()
391-
.filter(|join_filter| !pull_up.having_like_join_filters.contains(join_filter))
392-
.cloned()
393-
.collect()
394-
} else {
395-
pull_up.join_filters
365+
// A HAVING or outer-only filter recorded from above the aggregate cannot
366+
// be rewritten into the join when the output column gets a compensation
367+
// CASE below. Kept in the ON, a row the condition rejects looks unmatched
368+
// and falls back to the empty-input default, which is the issue's wrong 0. Checked
369+
// in the compensation CASE instead, the condition would have to be
370+
// evaluated twice, against the defaults for an unmatched row and against
371+
// the actual output for a matched one, and neither evaluation is right
372+
// for the rows the other one covers. The gate looks at the output column
373+
// alone because the map also holds aggregates that appear only in the
374+
// HAVING, whose NULL defaults need no CASE; an output whose own default
375+
// is NULL (the subquery projects `max`, say) keeps filtering in the ON as
376+
// before, which is correct there because an unmatched row is NULL either
377+
// way. Rather than guess, reject the query.
378+
let output_name = subquery_plan.schema().field(0).name();
379+
let output_needs_compensation = match collected_count_expr_map
380+
.as_ref()
381+
.and_then(|expr_map| expr_map.get(output_name))
382+
{
383+
Some(default_expr) => {
384+
!evaluates_to_null(default_expr.clone(), default_expr.column_refs())?
385+
}
386+
None => false,
396387
};
388+
if output_needs_compensation && !pull_up.having_like_join_filters.is_empty() {
389+
return plan_err!(
390+
"Unsupported correlated scalar subquery: a HAVING or filter above a count-like aggregate reads outer columns, and this rewrite cannot evaluate it against both the group and the empty input without risking wrong results. Move the condition outside the subquery"
391+
);
392+
}
397393

398394
let join_filter_opt = build_join_filter(
399-
join_filters,
395+
pull_up.join_filters,
400396
pull_up.correlated_subquery_cols_map.values().flatten(),
401397
subquery_alias,
402398
)?;
@@ -425,45 +421,6 @@ fn build_join(
425421
// introduced is the untyped `Null` of the HAVING arm. The expressions
426422
// themselves come from a plan `TypeCoercion` has already coerced.
427423
let mut expr_rewrite = TypeCoercionRewriter::new(new_plan.schema());
428-
// When the HAVING-like conditions are checked here instead of in the
429-
// join ON, evaluate them twice: against the empty-input defaults for
430-
// an unmatched row, where the group does not exist, and against the
431-
// actual aggregate output for a matched one. Only columns qualified
432-
// with the subquery alias are replaced by the defaults, so an outer
433-
// column that happens to share the aggregate's output name is left
434-
// alone.
435-
let (having_on_default, having_actual) =
436-
if having_in_compensation && !pull_up.having_like_join_filters.is_empty() {
437-
let having_actual = build_join_filter(
438-
pull_up.having_like_join_filters.clone(),
439-
pull_up.correlated_subquery_cols_map.values().flatten(),
440-
subquery_alias,
441-
)?;
442-
let having_on_default = having_actual
443-
.clone()
444-
.map(|requalified| -> Result<Expr> {
445-
let substituted = requalified
446-
.transform_up(|e| {
447-
if let Expr::Column(Column {
448-
relation: Some(relation),
449-
name,
450-
..
451-
}) = &e
452-
&& relation.table() == subquery_alias
453-
&& let Some(default_val) = expr_map.get(name)
454-
{
455-
return Ok(Transformed::yes(default_val.clone()));
456-
}
457-
Ok(Transformed::no(e))
458-
})
459-
.data()?;
460-
substituted.rewrite(&mut expr_rewrite).data()
461-
})
462-
.transpose()?;
463-
(having_on_default, having_actual)
464-
} else {
465-
(None, None)
466-
};
467424
let having_arm = pull_up
468425
.pull_up_having_expr
469426
.as_ref()
@@ -482,26 +439,10 @@ fn build_join(
482439
// outer table has a column with the same name as the aggregate.
483440
let value_col = Column::new(Some(subquery_alias), name);
484441

485-
// An unmatched row means the correlation matched no group, so
486-
// return the empty-input default only when the HAVING-like
487-
// conditions also hold on the defaults; otherwise the subquery
488-
// produced no row and the result is NULL.
489-
let unmatched_value = match &having_on_default {
490-
Some(having_default) => when(having_default.clone(), result.clone())
491-
.otherwise(lit(ScalarValue::Null))?,
492-
None => result,
493-
};
494-
let mut builder =
495-
when(Expr::Column(indicator_col).is_null(), unmatched_value);
442+
let mut builder = when(Expr::Column(indicator_col).is_null(), result);
496443
if let Some((when_expr, then_expr)) = &having_arm {
497444
builder = builder.when(when_expr.clone(), then_expr.clone());
498445
}
499-
// A matched group the HAVING-like conditions reject gives no row
500-
// either.
501-
if let Some(having_actual) = &having_actual {
502-
builder = builder
503-
.when(having_actual.clone().is_not_true(), lit(ScalarValue::Null));
504-
}
505446
let compensation_expr = builder.otherwise(Expr::Column(value_col.clone()))?;
506447
compensation_exprs.insert(
507448
value_col,

0 commit comments

Comments
 (0)