Skip to content

Commit fa59434

Browse files
buraksennOmega359
authored andcommitted
fix: do not prune ORDER BY keys using nullable UNIQUE constraints (apache#23918)
## Which issue does this PR close? - Closes apache#23818. ## Rationale for this change Please check the issue for details, but the main idea is that a nullable `UNIQUE` column permits multiple NULL rows, so it does not determine later sort keys across them and they must not be pruned. ## What changes are included in this PR? - `FunctionalDependence` gets a `null_equality` field that records the NULL semantics under which the dependency holds. The default is `NullEqualsNothing`. - Sort-key pruning only uses a dependency that holds when NULLs are treated as equal (for example a GROUP BY key), has a non-nullable determinant, or whose source columns are all `NOT NULL`. - A primary key that is downgraded on the NULL-padded side of an outer join keeps `NullEqualsNull`, because padded rows are NULL in every column on that side. - The dependency for the whole GROUP BY key is no longer skipped because of a narrower dependency that doesn't hold across NULLs. ## Are these changes tested? Yes. Regression tests are added in `functional_dependencies.slt` for nullable `UNIQUE`, `NOT NULL UNIQUE`, LEFT JOIN with a primary key, and GROUP BY over a nullable `UNIQUE` column. ## Are there any user-facing changes? Yes: incorrect results are fixed. There is also an API change: the public `FunctionalDependence` struct has a new `null_equality` field, so code that builds it with a struct literal must switch to `FunctionalDependence::new(..)`. This is documented in the 56.0.0 upgrade guide.
1 parent d08fd07 commit fa59434

4 files changed

Lines changed: 151 additions & 16 deletions

File tree

‎datafusion/common/src/functional_dependencies.rs‎

Lines changed: 58 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -23,7 +23,7 @@ use std::ops::Deref;
2323
use std::vec::IntoIter;
2424

2525
use crate::utils::{merge_and_order_indices, set_difference};
26-
use crate::{DFSchema, HashSet, JoinType};
26+
use crate::{DFSchema, HashSet, JoinType, NullEquality};
2727

2828
/// This object defines a constraint on a table.
2929
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Hash)]
@@ -144,6 +144,13 @@ pub struct FunctionalDependence {
144144
/// such as after LEFT JOIN or RIGHT JOIN operations, this property may
145145
/// change.
146146
pub nullable: bool,
147+
/// The NULL-comparison semantics under which this dependency holds. The
148+
/// conservative default, [`NullEquality::NullEqualsNothing`], means it
149+
/// holds only across rows whose determinant contains no NULLs; e.g. a
150+
/// nullable `UNIQUE` constraint permits multiple NULL rows that may differ.
151+
/// [`NullEquality::NullEqualsNull`] means it also holds when NULL
152+
/// determinant values are treated as equal; e.g. a `GROUP BY` key.
153+
pub null_equality: NullEquality,
147154
// The functional dependency mode:
148155
pub mode: Dependency,
149156
}
@@ -168,6 +175,8 @@ impl FunctionalDependence {
168175
source_indices,
169176
target_indices,
170177
nullable,
178+
// Assume the dependency does not hold across NULL rows by default:
179+
null_equality: NullEquality::NullEqualsNothing,
171180
// Start with the least restrictive mode by default:
172181
mode: Dependency::Multi,
173182
}
@@ -177,6 +186,25 @@ impl FunctionalDependence {
177186
self.mode = mode;
178187
self
179188
}
189+
190+
pub fn with_null_equality(mut self, null_equality: NullEquality) -> Self {
191+
self.null_equality = null_equality;
192+
self
193+
}
194+
195+
/// Returns `true` if this dependency remains usable for operations that
196+
/// treat NULL determinant values as equal (`GROUP BY`, `DISTINCT` and
197+
/// sorting, which place all NULL keys together): it must hold under
198+
/// NULLs-are-equal semantics, have a non-nullable determinant (e.g. a
199+
/// `PRIMARY KEY`), or have no nullable source field in the given `schema`.
200+
pub fn is_valid_across_nulls(&self, schema: &DFSchema) -> bool {
201+
self.null_equality == NullEquality::NullEqualsNull
202+
|| !self.nullable
203+
|| self
204+
.source_indices
205+
.iter()
206+
.all(|&source_idx| !schema.field(source_idx).is_nullable())
207+
}
180208
}
181209

182210
/// This object encapsulates all functional dependencies in a given relation.
@@ -301,6 +329,7 @@ impl FunctionalDependencies {
301329
source_indices,
302330
target_indices,
303331
nullable,
332+
null_equality,
304333
mode,
305334
} in &self.deps
306335
{
@@ -321,7 +350,8 @@ impl FunctionalDependencies {
321350
new_target_indices,
322351
*nullable,
323352
)
324-
.with_mode(*mode);
353+
.with_mode(*mode)
354+
.with_null_equality(*null_equality);
325355
projected_func_dependencies.push(new_func_dependence);
326356
}
327357
}
@@ -386,7 +416,12 @@ impl FunctionalDependencies {
386416
fn downgrade_dependencies(&mut self) {
387417
// Delete nullable dependencies, since they are no longer valid:
388418
self.deps.retain(|item| !item.nullable);
389-
self.deps.iter_mut().for_each(|item| item.nullable = true);
419+
// Survivors had a non-null determinant, so every new NULL comes from a
420+
// padded row whose targets are all NULL too:
421+
self.deps.iter_mut().for_each(|item| {
422+
item.nullable = true;
423+
item.null_equality = NullEquality::NullEqualsNull;
424+
});
390425
}
391426

392427
/// This function ensures that functional dependencies involving uniquely
@@ -432,6 +467,7 @@ pub fn aggregate_functional_dependencies(
432467
for FunctionalDependence {
433468
source_indices,
434469
nullable,
470+
null_equality,
435471
mode,
436472
..
437473
} in &func_dependencies.deps
@@ -470,13 +506,22 @@ pub fn aggregate_functional_dependencies(
470506
};
471507
// All of the composite indices occur in the GROUP BY expression:
472508
if new_source_indices.len() == source_indices.len() {
509+
// GROUP BY treats NULLs as equal: a determinant covering the
510+
// complete grouping key gets at most one output row per NULL too.
511+
let output_null_equality =
512+
if new_source_indices.len() == group_by_expr_names.len() {
513+
NullEquality::NullEqualsNull
514+
} else {
515+
*null_equality
516+
};
473517
aggregate_func_dependencies.push(
474518
FunctionalDependence::new(
475519
new_source_indices,
476520
target_indices.clone(),
477521
*nullable,
478522
)
479-
.with_mode(mode),
523+
.with_mode(mode)
524+
.with_null_equality(output_null_equality),
480525
);
481526
}
482527
}
@@ -497,13 +542,17 @@ pub fn aggregate_functional_dependencies(
497542
// The following simple comparison is working well because
498543
// GROUP BY expressions come here as a prefix.
499544
item.source_indices.iter().all(|idx| idx < &count)
545+
// A dependency that is not valid across NULLs cannot replace
546+
// the whole GROUP BY key dependency:
547+
&& item.is_valid_across_nulls(aggr_schema)
500548
}) {
501549
// Add a new functional dependency associated with the whole table:
502550
// Use nullable property of the GROUP BY expression:
503551
aggregate_func_dependencies.push(
504-
// Use nullable property of the GROUP BY expression:
505552
FunctionalDependence::new(source_indices, target_indices, nullable)
506-
.with_mode(Dependency::Single),
553+
.with_mode(Dependency::Single)
554+
// Grouping collapses NULL keys into a single group:
555+
.with_null_equality(NullEquality::NullEqualsNull),
507556
);
508557
}
509558
}
@@ -617,15 +666,15 @@ pub fn get_required_sort_exprs_indices(
617666
};
618667

619668
// A sort expression is removable if its value is functionally determined
620-
// by fields that already appear earlier in the sort order: if the earlier
621-
// fields are fixed, this one's value is fixed too, so it adds no ordering
622-
// information.
669+
// by fields that already appear earlier in the sort order (and the
670+
// dependency remains valid across NULL rows).
623671
let removable = dependencies.deps.iter().any(|dependency| {
624672
dependency.target_indices.contains(&field_idx)
625673
&& dependency
626674
.source_indices
627675
.iter()
628676
.all(|source_idx| known_field_indices.contains(source_idx))
677+
&& dependency.is_valid_across_nulls(schema)
629678
});
630679

631680
if removable {

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

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -3235,7 +3235,8 @@ mod tests {
32353235
FunctionalDependence::new(vec![0], vec![0, 1, 2, 3], false)
32363236
.with_mode(Dependency::Single),
32373237
FunctionalDependence::new(vec![2], vec![2, 3], true)
3238-
.with_mode(Dependency::Multi),
3238+
.with_mode(Dependency::Multi)
3239+
.with_null_equality(NullEquality::NullEqualsNull),
32393240
])
32403241
);
32413242
Ok(())

‎datafusion/sqllogictest/test_files/functional_dependencies.slt‎

Lines changed: 68 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -136,24 +136,35 @@ logical_plan
136136
# 2.2 Nullable UNIQUE: `x` does NOT determine `y` across the two NULL rows,
137137
# so the `y` sort key must be kept.
138138
#
139-
# BUG:
140-
# Expected: `1 3`, `NULL 1`, `NULL 2`.
141-
# Issue: https://github.com/apache/datafusion/issues/23818
142139
query II
143140
SELECT x, y FROM t_uniq ORDER BY x NULLS LAST, y;
144141
----
145142
1 3
146-
NULL 2
147143
NULL 1
144+
NULL 2
148145

149146
query TT
150147
EXPLAIN SELECT x, y FROM t_uniq ORDER BY x NULLS LAST, y;
151148
----
152149
logical_plan
153-
01)Sort: t_uniq.x ASC NULLS LAST
150+
01)Sort: t_uniq.x ASC NULLS LAST, t_uniq.y ASC NULLS LAST
154151
02)--TableScan: t_uniq projection=[x, y]
155152

156-
# 2.3 After `GROUP BY x` the `x` does determine `cnt`, so can drop `cnt` from sort
153+
# 2.3 A UNIQUE determinant remains usable when its source column is NOT NULL.
154+
statement ok
155+
CREATE TABLE t_uniq_not_null (x INT NOT NULL UNIQUE, y INT) AS VALUES (1, 10), (2, 20);
156+
157+
query TT
158+
EXPLAIN SELECT x, y FROM t_uniq_not_null ORDER BY x, y;
159+
----
160+
logical_plan
161+
01)Sort: t_uniq_not_null.x ASC NULLS LAST
162+
02)--TableScan: t_uniq_not_null projection=[x, y]
163+
164+
statement ok
165+
drop table t_uniq_not_null;
166+
167+
# 2.4 After `GROUP BY x` the `x` does determine `cnt`, so can drop `cnt` from sort
157168
query TT
158169
EXPLAIN SELECT x, cnt FROM (SELECT x, count(*) AS cnt FROM t_uniq GROUP BY x) ORDER BY x, cnt;
159170
----
@@ -163,6 +174,57 @@ logical_plan
163174
03)----Aggregate: groupBy=[[t_uniq.x]], aggr=[[count(Int64(1))]]
164175
04)------TableScan: t_uniq projection=[x]
165176

177+
# 2.5 A PRIMARY KEY on the NULL-padded side of a LEFT JOIN: every new NULL in
178+
# `p.a` comes from a padded row, where `p.b` is NULL too. So `p.a` still
179+
# determines `p.b` and the `p.b` sort key can be dropped.
180+
statement ok
181+
CREATE TABLE t_left (k INT) AS VALUES (1), (3), (4);
182+
183+
statement ok
184+
CREATE TABLE t_right_pk (a INT, b INT, PRIMARY KEY (a)) AS VALUES (1, 10), (2, 20);
185+
186+
query II
187+
SELECT p.a, p.b FROM t_left l LEFT JOIN t_right_pk p ON l.k = p.a ORDER BY p.a, p.b DESC;
188+
----
189+
1 10
190+
NULL NULL
191+
NULL NULL
192+
193+
query TT
194+
EXPLAIN SELECT l.k, p.a, p.b FROM t_left l LEFT JOIN t_right_pk p ON l.k = p.a ORDER BY p.a, p.b;
195+
----
196+
logical_plan
197+
01)Sort: p.a ASC NULLS LAST
198+
02)--Left Join: l.k = p.a
199+
03)----SubqueryAlias: l
200+
04)------TableScan: t_left projection=[k]
201+
05)----SubqueryAlias: p
202+
06)------TableScan: t_right_pk projection=[a, b]
203+
204+
statement ok
205+
drop table t_left;
206+
207+
statement ok
208+
drop table t_right_pk;
209+
210+
# 2.6 After `GROUP BY x, y` the pair `(x, y)` is unique (NULLs included), so
211+
# it determines `cnt` even though the nullable UNIQUE `x` alone does not.
212+
query III
213+
SELECT x, y, cnt FROM (SELECT x, y, count(*) AS cnt FROM t_uniq GROUP BY x, y) ORDER BY x, y DESC, cnt;
214+
----
215+
1 3 1
216+
NULL 2 1
217+
NULL 1 1
218+
219+
query TT
220+
EXPLAIN SELECT x, y, cnt FROM (SELECT x, y, count(*) AS cnt FROM t_uniq GROUP BY x, y) ORDER BY x, y, cnt;
221+
----
222+
logical_plan
223+
01)Sort: t_uniq.x ASC NULLS LAST, t_uniq.y ASC NULLS LAST
224+
02)--Projection: t_uniq.x, t_uniq.y, count(Int64(1)) AS cnt
225+
03)----Aggregate: groupBy=[[t_uniq.x, t_uniq.y]], aggr=[[count(Int64(1))]]
226+
04)------TableScan: t_uniq projection=[x, y]
227+
166228

167229
# 3.1 PRIMARY KEY: `x` determines `y`, and `y` is not selected, so grouping
168230
# by `x, y` is the same as grouping by `x`.

‎docs/source/library-user-guide/upgrading/56.0.0.md‎

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -668,6 +668,29 @@ Wire compatibility is directional:
668668
ignores the unknown field but cannot preserve the qualifier required by the
669669
expressions, which can cause resolution failure or incorrect rebinding.
670670

671+
### `FunctionalDependence` has a new `null_equality` field
672+
673+
`FunctionalDependence` now records the NULL semantics its dependency holds under.
674+
Build it with `FunctionalDependence::new(..)` and, when needed,
675+
`.with_null_equality(NullEquality::NullEqualsNull)` instead of a struct literal.
676+
677+
**Migration guide:**
678+
679+
```rust,ignore
680+
// Before
681+
let dep = FunctionalDependence {
682+
source_indices,
683+
target_indices,
684+
nullable,
685+
mode: Dependency::Single,
686+
};
687+
688+
// After
689+
let dep = FunctionalDependence::new(source_indices, target_indices, nullable)
690+
.with_mode(Dependency::Single)
691+
.with_null_equality(NullEquality::NullEqualsNull);
692+
```
693+
671694
### `FileSource::exact_filter` controls scan equivalence properties
672695

673696
`FileScanConfig` no longer derives equivalence properties (constant columns

0 commit comments

Comments
 (0)