Skip to content

Commit b86f1f2

Browse files
authored
fix: preserve functional dependencies across unnest (apache#25892)
## Which issue does this PR close? - Closes apache#25844 ## Rationale for this change A list UNNEST can produce several rows for one input key. Retaining the input's functional dependencies makes a later DISTINCT or GROUP BY discard unnested values, and can make an ordered window use the wrong frame. These queries return incorrect results. ## What changes are included in this PR? - Remap inherited dependency indices to output positions after struct expansion. - Downgrade dependencies after list unnest, remove unnested list outputs from dependency targets, and discard dependencies whose determinants are unnested. - Add SQL and plan-level regressions for distinct, grouping, window frames, and shifted indices. ## What is the testing strategy for this PR? - cargo fmt --all --check - cargo test -p datafusion-expr --lib unnest_remaps_functional_dependencies - cargo test --profile ci --test sqllogictests -- functional_dependencies.slt ## Are there any user-facing changes? Yes. A list unnest followed by DISTINCT, GROUP BY, or an ordered window now returns the expected result.
1 parent fbf7737 commit b86f1f2

2 files changed

Lines changed: 203 additions & 3 deletions

File tree

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

Lines changed: 116 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -5261,8 +5261,47 @@ impl Unnest {
52615261

52625262
let metadata = input_schema.metadata().clone();
52635263
let df_schema = DFSchema::new_with_metadata(fields, metadata)?;
5264-
// We can use the existing functional dependencies:
5265-
let deps = input_schema.functional_dependencies().clone();
5264+
let list_indices: HashSet<_> =
5265+
list_columns.iter().map(|(index, _)| *index).collect();
5266+
// Struct unnest may replace one input column with several output columns,
5267+
// so remap dependencies using the input index of each output column.
5268+
let remap_indices = |indices: &[usize], exclude_lists: bool| {
5269+
dependency_indices
5270+
.iter()
5271+
.enumerate()
5272+
.filter_map(|(output_index, input_index)| {
5273+
(indices.contains(input_index)
5274+
&& (!exclude_lists || !list_indices.contains(input_index)))
5275+
.then_some(output_index)
5276+
})
5277+
.collect()
5278+
};
5279+
let deps = FunctionalDependencies::new(
5280+
input_schema
5281+
.functional_dependencies()
5282+
.iter()
5283+
// A list input no longer determines the rows produced by unnest.
5284+
// A struct input is also unsafe as a source: a null struct and
5285+
// a non-null struct with all-null fields have the same outputs.
5286+
.filter(|dep| {
5287+
dep.source_indices.iter().all(|index| {
5288+
!list_indices.contains(index) && !struct_columns.contains(index)
5289+
})
5290+
})
5291+
.map(|dep| FunctionalDependence {
5292+
source_indices: remap_indices(&dep.source_indices, false),
5293+
// The unnested values are not determined by the input key.
5294+
target_indices: remap_indices(&dep.target_indices, true),
5295+
// One input row can produce multiple output rows.
5296+
mode: if list_indices.is_empty() {
5297+
dep.mode
5298+
} else {
5299+
Dependency::Multi
5300+
},
5301+
..dep.clone()
5302+
})
5303+
.collect(),
5304+
);
52665305
let schema = Arc::new(df_schema.with_functional_dependencies(deps)?);
52675306

52685307
Ok(Unnest {
@@ -5368,7 +5407,7 @@ mod tests {
53685407
use datafusion_common::tree_node::{
53695408
TransformedResult, TreeNodeRewriter, TreeNodeVisitor,
53705409
};
5371-
use datafusion_common::{Constraint, not_impl_err};
5410+
use datafusion_common::{Constraint, RecursionUnnestOption, not_impl_err};
53725411
use insta::{assert_debug_snapshot, assert_snapshot};
53735412
use std::hash::DefaultHasher;
53745413

@@ -5448,6 +5487,80 @@ mod tests {
54485487
])
54495488
}
54505489

5490+
#[test]
5491+
fn unnest_remaps_functional_dependencies() -> Result<()> {
5492+
let schema = Arc::new(Schema::new(vec![
5493+
Field::new_struct(
5494+
"s",
5495+
vec![
5496+
Field::new("a", DataType::Int32, true),
5497+
Field::new("b", DataType::Int32, true),
5498+
],
5499+
true,
5500+
),
5501+
Field::new("k", DataType::Int32, false),
5502+
Field::new_list(
5503+
"xs",
5504+
Field::new_list(
5505+
"item",
5506+
Field::new_list_field(DataType::Int32, true),
5507+
true,
5508+
),
5509+
true,
5510+
),
5511+
Field::new("payload", DataType::Utf8, true),
5512+
]));
5513+
let constraints = Constraints::new_unverified(vec![
5514+
Constraint::PrimaryKey(vec![1]),
5515+
Constraint::Unique(vec![0]),
5516+
Constraint::Unique(vec![2]),
5517+
]);
5518+
let source: Arc<dyn TableSource> =
5519+
Arc::new(LogicalTableSource::new(schema).with_constraints(constraints));
5520+
5521+
// Expanding a struct preserves row count and remaps keys and targets,
5522+
// but a dependency sourced from the struct itself cannot be kept.
5523+
let struct_only = LogicalPlanBuilder::scan("t", Arc::clone(&source), None)?
5524+
.unnest_column("s")?
5525+
.build()?;
5526+
assert_eq!(
5527+
struct_only.schema().functional_dependencies(),
5528+
&FunctionalDependencies::new(vec![
5529+
FunctionalDependence::new(vec![2], vec![0, 1, 2, 3, 4], false)
5530+
.with_mode(Dependency::Single),
5531+
FunctionalDependence::new(vec![3], vec![0, 1, 2, 3, 4], true)
5532+
.with_mode(Dependency::Single),
5533+
])
5534+
);
5535+
5536+
// The two recursion outputs both replace the same list input. Neither
5537+
// is determined by k, and a list-sourced dependency is no longer valid.
5538+
let options = UnnestOptions::default()
5539+
.with_recursions(RecursionUnnestOption {
5540+
input_column: "xs".into(),
5541+
output_column: "xs_depth_1".into(),
5542+
depth: 1,
5543+
})
5544+
.with_recursions(RecursionUnnestOption {
5545+
input_column: "xs".into(),
5546+
output_column: "xs_depth_2".into(),
5547+
depth: 2,
5548+
});
5549+
let plan = LogicalPlanBuilder::scan("t", source, None)?
5550+
.unnest_columns_with_options(vec!["s".into(), "xs".into()], options)?
5551+
.build()?;
5552+
assert_eq!(plan.schema().fields().len(), 6);
5553+
assert_eq!(
5554+
plan.schema().functional_dependencies(),
5555+
&FunctionalDependencies::new(vec![
5556+
FunctionalDependence::new(vec![2], vec![0, 1, 2, 5], false,)
5557+
.with_mode(Dependency::Multi)
5558+
])
5559+
);
5560+
5561+
Ok(())
5562+
}
5563+
54515564
#[test]
54525565
fn projection_with_leading_computed_column_preserves_pk() -> Result<()> {
54535566
let constraints =

‎datafusion/sqllogictest/test_files/functional_dependencies.slt‎

Lines changed: 87 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -466,6 +466,93 @@ SELECT y, count(*) FROM (SELECT x, max(y) AS y FROM t_inner GROUP BY x) GROUP BY
466466
statement ok
467467
drop table t_inner;
468468

469+
##########
470+
## List unnest invalidates dependencies on the input row
471+
##########
472+
473+
statement ok
474+
CREATE TABLE t_unnest_fd (k VARCHAR, v INT) AS VALUES ('a', 1), ('a', 2), ('b', 3);
475+
476+
# DISTINCT must retain the unnested value in its grouping key.
477+
query I
478+
WITH g AS (SELECT k, array_agg(v) AS vs FROM t_unnest_fd GROUP BY k),
479+
u AS (SELECT k, unnest(vs) AS v FROM g)
480+
SELECT count(*) AS n FROM (SELECT DISTINCT k, v FROM u);
481+
----
482+
3
483+
484+
# The equivalent GROUP BY must also retain the unnested value.
485+
query I
486+
WITH g AS (SELECT k, array_agg(v) AS vs FROM t_unnest_fd GROUP BY k),
487+
u AS (SELECT k, unnest(vs) AS v FROM g)
488+
SELECT count(*) AS n FROM (SELECT k, v FROM u GROUP BY k, v);
489+
----
490+
3
491+
492+
# There is no projection between Unnest and DISTINCT to discard a stale target.
493+
query I
494+
WITH g AS (SELECT k, array_agg(v) AS vs FROM t_unnest_fd GROUP BY k)
495+
SELECT count(*) AS n FROM (SELECT DISTINCT * FROM (SELECT k, unnest(vs) FROM g));
496+
----
497+
3
498+
499+
# An unnested list of structs also creates multiple values per input key.
500+
query I
501+
WITH g AS (
502+
SELECT k, array_agg(named_struct('id', v)) AS rs
503+
FROM t_unnest_fd GROUP BY k
504+
), u AS (SELECT k, unnest(rs) AS r FROM g)
505+
SELECT count(*) AS n FROM (SELECT DISTINCT k, r['id'] FROM u);
506+
----
507+
3
508+
509+
# Struct expansion shifts the following list output onto an old dependency
510+
# target index. DISTINCT must still include the list output.
511+
query I
512+
WITH g AS (
513+
SELECT k, named_struct('x', min(v), 'y', max(v)) AS s,
514+
array_agg(v) AS vs, sum(v) AS n
515+
FROM t_unnest_fd GROUP BY k
516+
)
517+
SELECT count(*) FROM (
518+
SELECT DISTINCT * FROM (SELECT k, unnest(s), unnest(vs), n FROM g)
519+
);
520+
----
521+
3
522+
523+
# ORDER BY k has ties after unnest. Its default RANGE frame includes both rows with k = 'a'.
524+
query I
525+
WITH g AS (SELECT k, array_agg(v) AS vs FROM t_unnest_fd GROUP BY k),
526+
u AS (SELECT k, unnest(vs) AS v FROM g)
527+
SELECT count(DISTINCT s) AS n FROM (SELECT sum(v) OVER (ORDER BY k) AS s FROM u);
528+
----
529+
2
530+
531+
# Expanding a struct before k shifts the inherited dependency's column indices.
532+
# The two sy values tie, so their default RANGE frames have the same sum.
533+
query I
534+
WITH g AS (
535+
SELECT named_struct('x', min(v), 'y', length(k)) AS s,
536+
k, sum(v) AS n
537+
FROM t_unnest_fd GROUP BY k
538+
), u(sx, sy, k, n) AS (SELECT unnest(s), k, n FROM g)
539+
SELECT count(DISTINCT running_sum) FROM (
540+
SELECT sum(n) OVER (ORDER BY sy) AS running_sum FROM u
541+
);
542+
----
543+
1
544+
545+
# A row-preserving, single-element unnest remains correct.
546+
query I
547+
SELECT count(*) AS n
548+
FROM (SELECT DISTINCT k, v
549+
FROM (SELECT k, unnest(make_array(v)) AS v FROM t_unnest_fd));
550+
----
551+
3
552+
553+
statement ok
554+
drop table t_unnest_fd;
555+
469556
##########
470557
## Cleanup
471558
##########

0 commit comments

Comments
 (0)