Skip to content

Commit 28cefb7

Browse files
authored
fix: match functional dependencies by column position, not by name (apache#26150)
## Which issue does this PR close? - None yet. The bug and its repro are below. ## Rationale for this change If `x` is a primary key, the optimizer treats `CAST(x AS ...)` as `x`. It then drops the other ORDER BY or GROUP BY keys that `x` determines, so the query returns wrong results: ```sql CREATE TABLE t (x DOUBLE, y VARCHAR, PRIMARY KEY (x)) AS VALUES (1.1, 'b'), (1.2, 'a'), (2.1, 'c'); SELECT x, y FROM t ORDER BY CAST(x AS INT), y; -- main: 1.1 b / 1.2 a / 2.1 c (`y` is dropped from the sort) -- expected: 1.2 a / 1.1 b / 2.1 c SELECT CAST(x AS INT) k, count(*) n FROM t GROUP BY CAST(x AS INT), y; -- main: (1, 2) / (2, 1) (`y` is dropped from the grouping) -- expected: (1, 1) / (1, 1) / (2, 1) SELECT y, count(*) FROM t GROUP BY CAST(x AS INT); -- main: accepted -- expected: Error: Column in SELECT must be in GROUP BY or an aggregate function ``` `CAST(x AS INT)` is named `t.x`, because casts are left out of expression names. The functional dependency helpers matched GROUP BY and ORDER BY expressions to key columns by comparing names, so the cast matched the key `t.x`. The same happens with `TRY_CAST`, with a `UNIQUE NOT NULL` key, and with a key that comes from an inner GROUP BY. The ORDER BY case comes from the sort key pruning added in apache#21362 (54.0.0). ## What changes are included in this PR? - **Index-based helpers.** The four helpers in `functional_dependencies.rs` now take, for each GROUP BY or ORDER BY expression, the index of the input field it references (`Option<usize>`) instead of its name. A computed expression has no index, so it never matches a key. The new `datafusion_expr::utils::passthrough_field_index` returns the index for a column reference, aliased or not. - **One GROUP BY list.** The dependencies of an `Aggregate`'s output use the GROUP BY list that its schema is built from (`grouping_set_to_exprlist`). Before, they used a list de-duplicated by name, which merged `CAST(x AS INT)` and `x`. - **Projections resolve columns.** A projection now finds each input column with `DFSchema::index_of_column_by_name` instead of comparing `"qualifier.name"` strings. The unit test `projection_duplicate_flattened_name_uses_first_input_index` asserted the old string behaviour: a column named `"orders.id"` got the dependency of the different field `orders.id`. It is renamed and now asserts that each column keeps its own dependency. ## What is the testing strategy for this PR? - **New tests.** Section 6 of `functional_dependencies.slt` has one query for each user of the helpers: - ORDER BY pruning; - GROUP BY pruning; - `Aggregate` output dependencies; - GROUP BY expansion. On `main`, each of these returns a wrong result or accepts an invalid query. The same queries also run over `TRY_CAST` on a `UNIQUE NOT NULL` key and over a key from an inner GROUP BY. One more query pins that a widening cast (`INT` to `BIGINT`) of a key does not carry its dependencies. - **New unit tests.** `passthrough_field_index` resolves an ambiguous unqualified column to nothing. A key that is in the GROUP BY list two times (`id, id AS k`, builder API only) still determines the row. - **Existing tests** are unchanged, apart from the rewritten unit test. - **Planning time.** Planning is not slower. The `sql_planner` TPC-H and TPC-DS benchmarks, whose tables have primary keys, are about 5% faster, because the new code no longer renders expression names. <details><summary>Benchmark numbers (3 interleaved runs per side)</summary> | Benchmark | `main` | This PR | |---|---|---| | `physical_plan_tpch_all` | 17.3 / 17.8 / 18.0 ms | 16.1 / 17.0 / 17.2 ms | | `physical_plan_tpcds_all` | 291 / 300 / 301 ms | 276 / 280 / 282 ms | </details> ## Are there any user-facing changes? - **Results.** The queries above return correct results. - **Rejected queries.** Only a column reference to a key carries its dependencies. A query that selects other columns while grouping by an expression over the key is now rejected, even when the expression keeps distinct values distinct, like `GROUP BY CAST(x AS BIGINT)` over an `INT` key. `main` accepts it and its result is correct. PostgreSQL and DuckDB reject it too. Group by the key column itself instead. - **API change.** Four `pub` functions in `datafusion_common` take `&[Option<usize>]` instead of `&[String]`: - `aggregate_functional_dependencies` - `get_target_functional_dependencies` - `get_required_group_by_exprs_indices` - `get_required_sort_exprs_indices` The upgrade guide has a migration note.
1 parent 6023600 commit 28cefb7

8 files changed

Lines changed: 307 additions & 103 deletions

File tree

‎datafusion/common/src/functional_dependencies.rs‎

Lines changed: 49 additions & 48 deletions
Original file line numberDiff line numberDiff line change
@@ -452,9 +452,15 @@ impl Deref for FunctionalDependencies {
452452
}
453453

454454
/// Calculates functional dependencies for aggregate output, when there is a GROUP BY expression.
455+
///
456+
/// `group_by_input_indices[i]` is the index of the input field that GROUP BY
457+
/// expression `i` passes through unchanged (a column reference), or `None` if
458+
/// the expression computes a new value. Only a column reference can carry an
459+
/// input dependency; a computed expression such as `CAST(pk AS INT)` cannot,
460+
/// even though its output name may equal the column's name.
455461
pub fn aggregate_functional_dependencies(
456462
aggr_input_schema: &DFSchema,
457-
group_by_expr_names: &[String],
463+
group_by_input_indices: &[Option<usize>],
458464
aggr_schema: &DFSchema,
459465
) -> FunctionalDependencies {
460466
let mut aggregate_func_dependencies = vec![];
@@ -466,10 +472,9 @@ pub fn aggregate_functional_dependencies(
466472
// The loop below only re-expresses input dependencies. Skip it when the
467473
// input has none. The GROUP BY-key dependency below always runs.
468474
if !func_dependencies.is_empty() {
469-
let aggr_input_fields = aggr_input_schema.field_names();
470475
// Compute once: this does not change in the loop.
471476
let existing_target_indices =
472-
get_target_functional_dependencies(aggr_input_schema, group_by_expr_names);
477+
get_target_functional_dependencies(aggr_input_schema, group_by_input_indices);
473478
for FunctionalDependence {
474479
source_indices,
475480
nullable,
@@ -480,24 +485,24 @@ pub fn aggregate_functional_dependencies(
480485
{
481486
// Indices into the GROUP BY list for this determinant:
482487
let mut new_source_indices = vec![];
483-
let mut new_source_field_names = vec![];
484-
let source_field_names = source_indices
485-
.iter()
486-
.map(|&idx| &aggr_input_fields[idx])
487-
.collect::<Vec<_>>();
488-
489-
for (idx, group_by_expr_name) in group_by_expr_names.iter().enumerate() {
490-
// When one of the input determinant expressions matches with
491-
// the GROUP BY expression, add the index of the GROUP BY
492-
// expression as a new determinant key:
493-
if source_field_names.contains(&group_by_expr_name) {
488+
let mut new_source_input_indices = vec![];
489+
for (idx, input_idx) in group_by_input_indices.iter().enumerate() {
490+
// When one of the input determinant columns is a GROUP BY
491+
// expression, add the index of the GROUP BY expression as a new
492+
// determinant key:
493+
if let Some(input_idx) = input_idx
494+
&& source_indices.contains(input_idx)
495+
// A key column can be in the GROUP BY list more than one
496+
// time (`x, x AS k`). Count it one time.
497+
&& !new_source_input_indices.contains(&Some(*input_idx))
498+
{
494499
new_source_indices.push(idx);
495-
new_source_field_names.push(group_by_expr_name.clone());
500+
new_source_input_indices.push(Some(*input_idx));
496501
}
497502
}
498503
let new_target_indices = get_target_functional_dependencies(
499504
aggr_input_schema,
500-
&new_source_field_names,
505+
&new_source_input_indices,
501506
);
502507
let mode = if existing_target_indices == new_target_indices
503508
&& new_target_indices.is_some()
@@ -513,7 +518,7 @@ pub fn aggregate_functional_dependencies(
513518
// GROUP BY treats NULLs as equal: a determinant covering the
514519
// complete grouping key gets at most one output row per NULL too.
515520
let output_null_equality =
516-
if new_source_indices.len() == group_by_expr_names.len() {
521+
if new_source_indices.len() == group_by_input_indices.len() {
517522
NullEquality::NullEqualsNull
518523
} else {
519524
*null_equality
@@ -533,8 +538,8 @@ pub fn aggregate_functional_dependencies(
533538

534539
// When we have a GROUP BY key, we can guarantee uniqueness after
535540
// aggregation:
536-
if !group_by_expr_names.is_empty() {
537-
let count = group_by_expr_names.len();
541+
if !group_by_input_indices.is_empty() {
542+
let count = group_by_input_indices.len();
538543
let source_indices = (0..count).collect::<Vec<_>>();
539544
let nullable = source_indices
540545
.iter()
@@ -566,32 +571,30 @@ pub fn aggregate_functional_dependencies(
566571

567572
/// Returns target indices, for the determinant keys that are inside
568573
/// group by expressions.
574+
///
575+
/// `group_by_input_indices` holds, for each GROUP BY expression, the index of
576+
/// the `schema` field it references, or `None` for a computed expression.
569577
pub fn get_target_functional_dependencies(
570578
schema: &DFSchema,
571-
group_by_expr_names: &[String],
579+
group_by_input_indices: &[Option<usize>],
572580
) -> Option<Vec<usize>> {
573581
let dependencies = schema.functional_dependencies();
574582
if dependencies.is_empty() {
575583
return None;
576584
}
577585
let mut combined_target_indices = HashSet::new();
578-
let field_names = schema.field_names();
579586
for FunctionalDependence {
580587
source_indices,
581588
target_indices,
582589
..
583590
} in &dependencies.deps
584591
{
585-
let source_key_names = source_indices
586-
.iter()
587-
.map(|id_key_idx| &field_names[*id_key_idx])
588-
.collect::<Vec<_>>();
589592
// If the GROUP BY expression contains a determinant key, we can use
590593
// the associated fields after aggregation even if they are not part
591594
// of the GROUP BY expression.
592-
if source_key_names
595+
if source_indices
593596
.iter()
594-
.all(|source_key_name| group_by_expr_names.contains(source_key_name))
597+
.all(|source_idx| group_by_input_indices.contains(&Some(*source_idx)))
595598
{
596599
combined_target_indices.extend(target_indices.iter());
597600
}
@@ -605,19 +608,18 @@ pub fn get_target_functional_dependencies(
605608

606609
/// Returns indices for the minimal subset of GROUP BY expressions that are
607610
/// functionally equivalent to the original set of GROUP BY expressions.
611+
///
612+
/// `group_by_input_indices` holds, for each GROUP BY expression, the index of
613+
/// the `schema` field it references, or `None` for a computed expression. If
614+
/// any GROUP BY expression is computed, returns `None`.
608615
pub fn get_required_group_by_exprs_indices(
609616
schema: &DFSchema,
610-
group_by_expr_names: &[String],
617+
group_by_input_indices: &[Option<usize>],
611618
) -> Option<Vec<usize>> {
612619
let dependencies = schema.functional_dependencies();
613-
let field_names = schema.field_names();
614-
let mut groupby_expr_indices = group_by_expr_names
620+
let mut groupby_expr_indices = group_by_input_indices
615621
.iter()
616-
.map(|group_by_expr_name| {
617-
field_names
618-
.iter()
619-
.position(|field_name| field_name == group_by_expr_name)
620-
})
622+
.copied()
621623
.collect::<Option<Vec<_>>>()?;
622624

623625
groupby_expr_indices.sort_unstable();
@@ -642,33 +644,32 @@ pub fn get_required_group_by_exprs_indices(
642644
groupby_expr_indices
643645
.iter()
644646
.map(|idx| {
645-
group_by_expr_names
647+
group_by_input_indices
646648
.iter()
647-
.position(|name| &field_names[*idx] == name)
649+
.position(|input_idx| *input_idx == Some(*idx))
648650
})
649651
.collect()
650652
}
651653

652654
/// Returns indices for the minimal subset of ORDER BY expressions that are
653655
/// functionally equivalent to the original set of ORDER BY expressions.
656+
///
657+
/// `sort_input_indices` holds, for each ORDER BY expression, the index of the
658+
/// `schema` field it references, or `None` for a computed expression.
654659
pub fn get_required_sort_exprs_indices(
655660
schema: &DFSchema,
656-
sort_expr_names: &[String],
661+
sort_input_indices: &[Option<usize>],
657662
) -> Vec<usize> {
658663
let dependencies = schema.functional_dependencies();
659-
let field_names = schema.field_names();
660664

661-
let mut known_field_indices = HashSet::with_capacity(sort_expr_names.len());
662-
let mut required_sort_expr_indices = Vec::with_capacity(sort_expr_names.len());
665+
let mut known_field_indices = HashSet::with_capacity(sort_input_indices.len());
666+
let mut required_sort_expr_indices = Vec::with_capacity(sort_input_indices.len());
663667

664-
for (sort_expr_idx, sort_expr_name) in sort_expr_names.iter().enumerate() {
665-
// If the sort expression doesn't correspond to a known schema field
666-
// (e.g. a computed expression), we can't reason about it via functional
668+
for (sort_expr_idx, field_idx) in sort_input_indices.iter().enumerate() {
669+
// If the sort expression doesn't reference a schema field (e.g. a
670+
// computed expression), we can't reason about it via functional
667671
// dependencies, so conservatively keep it.
668-
let Some(field_idx) = field_names
669-
.iter()
670-
.position(|field_name| field_name == sort_expr_name)
671-
else {
672+
let Some(field_idx) = *field_idx else {
672673
required_sort_expr_indices.push(sort_expr_idx);
673674
continue;
674675
};

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

Lines changed: 9 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -41,7 +41,7 @@ use crate::utils::{
4141
Columnizer, can_hash, check_all_columns_from_schema, compare_sort_expr,
4242
expand_qualified_wildcard, expand_wildcard, expr_to_columns,
4343
find_valid_equijoin_key_pair, group_window_expr_by_sort_keys,
44-
split_conjunction_owned,
44+
passthrough_field_index, split_conjunction_owned,
4545
};
4646
use crate::{
4747
BinaryExpr, DmlStatement, ExplainOption, Expr, ExprSchemable, Operator,
@@ -1988,22 +1988,20 @@ pub fn add_group_by_exprs_from_dependencies(
19881988
return Ok(group_expr);
19891989
}
19901990

1991-
// Names of the fields produced by the GROUP BY exprs for example, `GROUP BY
1992-
// c1 + 1` produces an output field named `"c1 + 1"`
1993-
let mut group_by_field_names = group_expr
1991+
// The input field that each GROUP BY expression passes through, or `None`
1992+
// for a computed expression such as `c1 + 1`
1993+
let mut group_by_input_indices = group_expr
19941994
.iter()
1995-
.map(|e| e.schema_name().to_string())
1995+
.map(|e| passthrough_field_index(e, schema))
19961996
.collect::<Vec<_>>();
19971997

19981998
if let Some(target_indices) =
1999-
get_target_functional_dependencies(schema, &group_by_field_names)
1999+
get_target_functional_dependencies(schema, &group_by_input_indices)
20002000
{
20012001
for idx in target_indices {
2002-
let expr = Expr::Column(Column::from(schema.qualified_field(idx)));
2003-
let expr_name = expr.schema_name().to_string();
2004-
if !group_by_field_names.contains(&expr_name) {
2005-
group_by_field_names.push(expr_name);
2006-
group_expr.push(expr);
2002+
if !group_by_input_indices.contains(&Some(idx)) {
2003+
group_by_input_indices.push(Some(idx));
2004+
group_expr.push(Expr::Column(Column::from(schema.qualified_field(idx))));
20072005
}
20082006
}
20092007
}

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

Lines changed: 47 additions & 37 deletions
Original file line numberDiff line numberDiff line change
@@ -44,7 +44,7 @@ use crate::utils::{
4444
check_aggregate_and_window_nesting, check_no_window_functions,
4545
enumerate_grouping_sets, expr_to_columns, exprlist_to_fields,
4646
find_out_reference_exprs, grouping_set_expr_count, grouping_set_to_exprlist,
47-
merge_schema, split_conjunction,
47+
merge_schema, passthrough_field_index, split_conjunction,
4848
};
4949
use crate::{
5050
BinaryExpr, CreateMemoryTable, CreateView, Execute, Expr, ExprSchemable, GroupingSet,
@@ -69,7 +69,6 @@ use datafusion_common::{
6969
aggregate_functional_dependencies, assert_eq_or_internal_err, assert_or_internal_err,
7070
internal_err, plan_datafusion_err, plan_err, validate_range_split_points,
7171
};
72-
use indexmap::IndexSet;
7372
use itertools::Itertools as _;
7473

7574
// backwards compatibility
@@ -4386,15 +4385,14 @@ fn calc_func_dependencies_for_aggregate(
43864385
// that GROUP BY expression results will be unique.
43874386
// - Otherwise, it may be possible to propagate functional dependencies.
43884387
if !contains_grouping_set(group_expr) {
4389-
let group_by_expr_names = group_expr
4390-
.iter()
4391-
.map(|item| item.schema_name().to_string())
4392-
.collect::<IndexSet<_>>()
4388+
// One entry per GROUP BY output field, in the order of `aggr_schema`
4389+
let group_by_input_indices = grouping_set_to_exprlist(group_expr)?
43934390
.into_iter()
4391+
.map(|item| passthrough_field_index(item, input.schema()))
43944392
.collect::<Vec<_>>();
43954393
let aggregate_func_dependencies = aggregate_functional_dependencies(
43964394
input.schema(),
4397-
&group_by_expr_names,
4395+
&group_by_input_indices,
43984396
aggr_schema,
43994397
);
44004398
Ok(aggregate_func_dependencies)
@@ -4420,19 +4418,9 @@ fn calc_func_dependencies_for_project(
44204418
return Ok(FunctionalDependencies::empty());
44214419
}
44224420

4423-
// Map each input field name to its first index so that projection
4424-
// expressions resolve with a hash lookup instead of a linear scan.
4425-
let input_fields = input.schema().field_names();
4426-
let mut input_index_by_name: HashMap<&str, usize> =
4427-
HashMap::with_capacity(input_fields.len());
4428-
for (index, name) in input_fields.iter().enumerate() {
4429-
input_index_by_name.entry(name.as_str()).or_insert(index);
4430-
}
4431-
let input_index = |name: &str| {
4432-
input_index_by_name
4433-
.get(name)
4434-
.copied()
4435-
.unwrap_or(COMPUTED_EXPR_INDEX)
4421+
let input_schema = input.schema();
4422+
let input_index = |expr: &Expr| {
4423+
passthrough_field_index(expr, input_schema).unwrap_or(COMPUTED_EXPR_INDEX)
44364424
};
44374425

44384426
// Map each projection output position to its input column index.
@@ -4453,16 +4441,14 @@ fn calc_func_dependencies_for_project(
44534441
wildcard_fields
44544442
.into_iter()
44554443
.map(|(qualifier, f)| {
4456-
let flat_name = qualifier
4457-
.map(|t| format!("{}.{}", t, f.name()))
4458-
.unwrap_or_else(|| f.name().clone());
4459-
input_index(&flat_name)
4444+
input_schema
4445+
.index_of_column_by_name(qualifier.as_ref(), f.name())
4446+
.unwrap_or(COMPUTED_EXPR_INDEX)
44604447
})
44614448
.collect::<Vec<_>>(),
44624449
)
44634450
}
4464-
Expr::Alias(alias) => Ok(vec![input_index(&format!("{}", alias.expr))]),
4465-
_ => Ok(vec![input_index(&format!("{expr}"))]),
4451+
_ => Ok(vec![input_index(expr)]),
44664452
})
44674453
.collect::<Result<Vec<_>>>()?
44684454
.into_iter()
@@ -5565,16 +5551,37 @@ mod tests {
55655551
}
55665552

55675553
#[test]
5568-
fn projection_duplicate_flattened_name_uses_first_input_index() -> Result<()> {
5554+
fn aggregate_group_by_repeated_key_keeps_key_dependency() -> Result<()> {
5555+
let constraints =
5556+
Constraints::new_unverified(vec![Constraint::PrimaryKey(vec![0])]);
5557+
let source = Arc::new(
5558+
LogicalTableSource::new(Arc::new(employee_schema()))
5559+
.with_constraints(constraints),
5560+
);
5561+
// `id` is in the GROUP BY list two times: as itself and as `k`.
5562+
let plan = LogicalPlanBuilder::scan("employee_csv", source, None)?
5563+
.aggregate(
5564+
vec![col("id"), col("state"), col("id").alias("k")],
5565+
Vec::<Expr>::new(),
5566+
)?
5567+
.build()?;
5568+
5569+
// `id` alone still determines the row.
5570+
let deps = plan.schema().functional_dependencies();
5571+
assert_eq!(deps.len(), 1);
5572+
assert_eq!(deps[0].source_indices, vec![0]);
5573+
assert_eq!(deps[0].target_indices, vec![0, 1, 2]);
5574+
5575+
Ok(())
5576+
}
5577+
5578+
#[test]
5579+
fn projection_resolves_columns_not_flattened_names() -> Result<()> {
55695580
// Build an input schema where a qualified field (`orders`.`id`) and an
5570-
// unqualified field that is literally named `"orders.id"` flatten to
5571-
// the exact same lookup key that `calc_func_dependencies_for_project`
5572-
// uses to resolve projection expressions against input fields. This is
5573-
// the only way two entries of `DFSchema::field_names()` can collide
5574-
// (`DFSchema::check_names` otherwise forbids duplicate names), and it
5575-
// pins that the hash-map based lookup resolves such a collision to the
5576-
// *first* matching index, exactly like the linear `position()` scan it
5577-
// replaces.
5581+
// unqualified field that is literally named `"orders.id"` (the name of
5582+
// e.g. `CAST(orders.id AS INT)`) have the same flattened name. The
5583+
// projection must resolve the column it references, not the first
5584+
// field with the same flattened name.
55785585
let schema = DFSchema::new_with_metadata(
55795586
vec![
55805587
(
@@ -5597,11 +5604,14 @@ mod tests {
55975604
schema: Arc::new(schema),
55985605
});
55995606

5600-
// References the *unqualified* second field, whose flattened name
5601-
// ("orders.id") collides with the first (qualified) field's.
5607+
// References the *unqualified* second field, which is not a key.
56025608
let exprs = vec![Expr::Column(Column::new_unqualified("orders.id"))];
56035609
let deps = calc_func_dependencies_for_project(&exprs, &input)?;
5610+
assert!(deps.is_empty());
56045611

5612+
// References the qualified first field, which is a key.
5613+
let exprs = vec![Expr::Column(Column::new(Some("orders"), "id"))];
5614+
let deps = calc_func_dependencies_for_project(&exprs, &input)?;
56055615
assert_eq!(deps.len(), 1);
56065616
assert_eq!(deps[0].source_indices, vec![0]);
56075617

0 commit comments

Comments
 (0)