Skip to content

Commit bb6ff16

Browse files
alambclaude
authored andcommitted
test: add functional_dependencies.slt covering functional dependency driven optimizations (apache#23821)
## Which issue does this PR close? This PR adds test coverage rather than closing an issue. It documents the current behavior of these bugs so that fixing them shows up as a test change: - apache#23634 - apache#23818 - apache#23819 - apache#23820 ## Rationale for this change While reviewing apache#23636 @neilconway and I kept coming up with more examples of bad plans, and it was not obvious which of the surrounding wrong answers were pre-existing and which the PR introduced. ## What changes are included in this PR? A new `datafusion/sqllogictest/test_files/functional_dependencies.slt` with one section per consumer of functional dependencies: 1. `ReplaceDistinctWithAggregate` — removing `DISTINCT` 2. `eliminate_duplicated_expr` — dropping trailing `ORDER BY` keys 3. `optimize_projections` — dropping `GROUP BY` expressions 4. `add_group_by_exprs_from_dependencies` — selecting non-grouped columns 5. `GROUP BY` derived keys on the NULL-padded side of an outer join Cases that currently return wrong answers are labelled `BUG` with the expected result and a link to the issue: | Case | Symptom | Issue | | --- | --- | --- | | 1.2 | `DISTINCT` over a nullable `UNIQUE` column returns both `NULL` rows | apache#23634 | | 2.2 | `ORDER BY x, y` drops the `y` key, so the `NULL` rows come back unordered | apache#23818 | | 3.2 | `GROUP BY x, y` drops `y`, merging the two `NULL` groups and losing a row | apache#23819 | | 4.2 | `SELECT x, y ... GROUP BY x` returns two rows for the `x = NULL` group | apache#23820 | ## Are these changes tested? CI ## Are there any user-facing changes? No. --------- Co-authored-by: Claude Opus 4.8 (1M context) <[email protected]>
1 parent 825953c commit bb6ff16

1 file changed

Lines changed: 314 additions & 0 deletions

File tree

Lines changed: 314 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,314 @@
1+
# Licensed to the Apache Software Foundation (ASF) under one
2+
# or more contributor license agreements. See the NOTICE file
3+
# distributed with this work for additional information
4+
# regarding copyright ownership. The ASF licenses this file
5+
# to you under the Apache License, Version 2.0 (the
6+
# "License"); you may not use this file except in compliance
7+
# with the License. You may obtain a copy of the License at
8+
#
9+
# http://www.apache.org/licenses/LICENSE-2.0
10+
#
11+
# Unless required by applicable law or agreed to in writing,
12+
# software distributed under the License is distributed on an
13+
# "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14+
# KIND, either express or implied. See the License for the
15+
# specific language governing permissions and limitations
16+
# under the License.
17+
18+
##########
19+
# Tests for functional dependencies
20+
# (`datafusion/common/src/functional_dependencies.rs`)
21+
#
22+
# A functional dependency records that one set of columns (the *determinant*)
23+
# determines the values of the others. DataFusion derives them from PRIMARY
24+
# KEY / UNIQUE constraints and from GROUP BY keys, and four optimizer rules
25+
# consume them to remove redundant work, each tested here in a different section.
26+
#
27+
# NULL handling is (as always) important:
28+
#
29+
# * A PRIMARY KEY is unique AND not nullable.
30+
# * A `UNIQUE` constraint permits *multiple NULL rows*, because NULLs
31+
# compare distinct.
32+
#
33+
# It is important not to mix `UNIQUE` columns with `DISTINCT` or `GROUP BY`,
34+
# which treat NULLs as equal and can produce wrong answers.
35+
##########
36+
37+
# These rules all run during logical optimization, so show only logical plans.
38+
statement ok
39+
set datafusion.explain.logical_plan_only = true;
40+
41+
# Set target_partitions explicitly so query results are stable.
42+
statement ok
43+
set datafusion.execution.target_partitions = 4;
44+
45+
##########
46+
## Test tables
47+
##########
48+
49+
statement ok
50+
CREATE TABLE t_pk (x INT, y INT, PRIMARY KEY (x)) AS VALUES (1, 10), (2, 20);
51+
52+
statement ok
53+
CREATE TABLE t_uniq (x INT UNIQUE, y INT) AS VALUES (NULL, 2), (NULL, 1), (1, 3);
54+
55+
query II rowsort
56+
SELECT x, y FROM t_uniq;
57+
----
58+
1 3
59+
NULL 1
60+
NULL 2
61+
62+
63+
# 1.1 PRIMARY KEY: rows are unique; the DISTINCT is removed and no
64+
# Aggregate appears in the plan.
65+
query TT
66+
EXPLAIN SELECT DISTINCT x FROM t_pk;
67+
----
68+
logical_plan TableScan: t_pk projection=[x]
69+
70+
# 1.2 Nullable UNIQUE: the DISTINCT must be KEPT. UNIQUE allows several NULL
71+
# rows, but DISTINCT treats NULLs as equal and has to collapse them into one.
72+
#
73+
# BUG: the DISTINCT is removed and both NULL rows are returned.
74+
# Expected: `1`, `NULL`.
75+
# Issue: https://github.com/apache/datafusion/issues/23634
76+
query I
77+
SELECT DISTINCT x FROM t_uniq ORDER BY x NULLS LAST;
78+
----
79+
1
80+
NULL
81+
NULL
82+
83+
query TT
84+
EXPLAIN SELECT DISTINCT x FROM t_uniq;
85+
----
86+
logical_plan TableScan: t_uniq projection=[x]
87+
88+
# 1.3 A PRIMARY KEY downgraded to a non-unique dependency by a LEFT JOIN
89+
# so the DISTINCT must be KEPT.
90+
# Fixed by: https://github.com/apache/datafusion/pull/23548
91+
statement ok
92+
CREATE TABLE t_orders (x INT, amount INT) AS VALUES (1, 10), (1, 20), (2, 30);
93+
94+
query I
95+
SELECT DISTINCT p.x FROM t_pk p LEFT JOIN t_orders o ON p.x = o.x ORDER BY p.x;
96+
----
97+
1
98+
2
99+
100+
query TT
101+
EXPLAIN SELECT DISTINCT p.x FROM t_pk p LEFT JOIN t_orders o ON p.x = o.x;
102+
----
103+
logical_plan
104+
01)Aggregate: groupBy=[[p.x]], aggr=[[]]
105+
02)--Projection: p.x
106+
03)----Left Join: p.x = o.x
107+
04)------SubqueryAlias: p
108+
05)--------TableScan: t_pk projection=[x]
109+
06)------SubqueryAlias: o
110+
07)--------TableScan: t_orders projection=[x]
111+
112+
statement ok
113+
drop table t_orders;
114+
115+
# 1.4 DISTINCT over a GROUP BY output. Grouping collapses the multiple NULL
116+
# rows, (NULL included) and the DISTINCT can be removed.
117+
query I
118+
SELECT DISTINCT x FROM (SELECT x FROM t_uniq GROUP BY x) ORDER BY x NULLS LAST;
119+
----
120+
1
121+
NULL
122+
123+
query TT
124+
EXPLAIN SELECT DISTINCT x FROM (SELECT x FROM t_uniq GROUP BY x);
125+
----
126+
logical_plan
127+
01)Aggregate: groupBy=[[t_uniq.x]], aggr=[[]]
128+
02)--TableScan: t_uniq projection=[x]
129+
130+
131+
# 2.1 PRIMARY KEY: `x` determines `y`, so `ORDER BY x, y` is equivalent to
132+
# `ORDER BY x` and the `y` key is dropped from the plan.
133+
query TT
134+
EXPLAIN SELECT x, y FROM t_pk ORDER BY x, y;
135+
----
136+
logical_plan
137+
01)Sort: t_pk.x ASC NULLS LAST
138+
02)--TableScan: t_pk projection=[x, y]
139+
140+
# 2.2 Nullable UNIQUE: `x` does NOT determine `y` across the two NULL rows,
141+
# so the `y` sort key must be kept.
142+
#
143+
# BUG:
144+
# Expected: `1 3`, `NULL 1`, `NULL 2`.
145+
# Issue: https://github.com/apache/datafusion/issues/23818
146+
query II
147+
SELECT x, y FROM t_uniq ORDER BY x NULLS LAST, y;
148+
----
149+
1 3
150+
NULL 2
151+
NULL 1
152+
153+
query TT
154+
EXPLAIN SELECT x, y FROM t_uniq ORDER BY x NULLS LAST, y;
155+
----
156+
logical_plan
157+
01)Sort: t_uniq.x ASC NULLS LAST
158+
02)--TableScan: t_uniq projection=[x, y]
159+
160+
# 2.3 After `GROUP BY x` the `x` does determine `cnt`, so can drop `cnt` from sort
161+
query TT
162+
EXPLAIN SELECT x, cnt FROM (SELECT x, count(*) AS cnt FROM t_uniq GROUP BY x) ORDER BY x, cnt;
163+
----
164+
logical_plan
165+
01)Sort: t_uniq.x ASC NULLS LAST
166+
02)--Projection: t_uniq.x, count(Int64(1)) AS cnt
167+
03)----Aggregate: groupBy=[[t_uniq.x]], aggr=[[count(Int64(1))]]
168+
04)------TableScan: t_uniq projection=[x]
169+
170+
171+
# 3.1 PRIMARY KEY: `x` determines `y`, and `y` is not selected, so grouping
172+
# by `x, y` is the same as grouping by `x`.
173+
query TT
174+
EXPLAIN SELECT x FROM t_pk GROUP BY x, y;
175+
----
176+
logical_plan
177+
01)Aggregate: groupBy=[[t_pk.x]], aggr=[[]]
178+
02)--TableScan: t_pk projection=[x]
179+
180+
# 3.2 Nullable UNIQUE: grouping by `x, y` is NOT the same as grouping by
181+
# `x` -- two NULL rows differ in `y` and belong in separate groups.
182+
#
183+
# BUG: `y` is dropped from the GROUP BY and the two NULL groups are merged,
184+
# so one row goes missing.
185+
# Expected: `1`, `NULL`, `NULL` (three rows).
186+
# Issue: https://github.com/apache/datafusion/issues/23819
187+
query I rowsort
188+
SELECT x FROM t_uniq GROUP BY x, y;
189+
----
190+
1
191+
NULL
192+
193+
query TT
194+
EXPLAIN SELECT x FROM t_uniq GROUP BY x, y;
195+
----
196+
logical_plan
197+
01)Aggregate: groupBy=[[t_uniq.x]], aggr=[[]]
198+
02)--TableScan: t_uniq projection=[x]
199+
200+
# 3.3 The same grouping, but with `y` selected so the parent needs it: no
201+
# column can be dropped and the answer is right.
202+
query II rowsort
203+
SELECT x, y FROM t_uniq GROUP BY x, y;
204+
----
205+
1 3
206+
NULL 1
207+
NULL 2
208+
209+
# 4.1 PRIMARY KEY: `x` determines `y`, so `y` has a single well-defined
210+
# value per group and one row is returned per `x`.
211+
query II rowsort
212+
SELECT x, y FROM t_pk GROUP BY x;
213+
----
214+
1 10
215+
2 20
216+
217+
query TT
218+
EXPLAIN SELECT x, y FROM t_pk GROUP BY x;
219+
----
220+
logical_plan
221+
01)Aggregate: groupBy=[[t_pk.x, t_pk.y]], aggr=[[]]
222+
02)--TableScan: t_pk projection=[x, y]
223+
224+
# 4.2 Nullable UNIQUE: `x` does NOT determine `y`, so there is no
225+
# well-defined `y` for the `x = NULL` group.
226+
#
227+
# BUG: `y` is appended to the GROUP BY anyway, so `GROUP BY x` returns TWO
228+
# rows for `x = NULL`.
229+
# Expected: one row per distinct `x` (or a planning error -- postgres
230+
# rejects this query, and accepts the 4.1 PRIMARY KEY form).
231+
# Issue: https://github.com/apache/datafusion/issues/23820
232+
query II rowsort
233+
SELECT x, y FROM t_uniq GROUP BY x;
234+
----
235+
1 3
236+
NULL 1
237+
NULL 2
238+
239+
query TT
240+
EXPLAIN SELECT x, y FROM t_uniq GROUP BY x;
241+
----
242+
logical_plan
243+
01)Aggregate: groupBy=[[t_uniq.x, t_uniq.y]], aggr=[[]]
244+
02)--TableScan: t_uniq projection=[x, y]
245+
246+
247+
statement ok
248+
CREATE TABLE t_null (x INT) AS VALUES (NULL), (NULL);
249+
250+
statement ok
251+
CREATE TABLE t_probe (z INT) AS VALUES (0), (2);
252+
253+
# 5.1 Grouping by `g.x, g.cnt` must keep both columns: `g.x` alone does not
254+
# determine `g.cnt` after NULL padding.
255+
query II
256+
SELECT g.x, count(*) AS c
257+
FROM t_probe a
258+
LEFT JOIN (SELECT x, count(*) AS cnt FROM t_null GROUP BY x) g
259+
ON a.z = g.cnt
260+
GROUP BY g.x, g.cnt
261+
ORDER BY c;
262+
----
263+
NULL 1
264+
NULL 1
265+
266+
query TT
267+
EXPLAIN SELECT g.x, count(*) AS c
268+
FROM t_probe a
269+
LEFT JOIN (SELECT x, count(*) AS cnt FROM t_null GROUP BY x) g
270+
ON a.z = g.cnt
271+
GROUP BY g.x, g.cnt;
272+
----
273+
logical_plan
274+
01)Projection: g.x, count(Int64(1)) AS count(*) AS c
275+
02)--Aggregate: groupBy=[[g.x, g.cnt]], aggr=[[count(Int64(1))]]
276+
03)----Projection: g.x, g.cnt
277+
04)------Left Join: CAST(a.z AS Int64) = g.cnt
278+
05)--------SubqueryAlias: a
279+
06)----------TableScan: t_probe projection=[z]
280+
07)--------SubqueryAlias: g
281+
08)----------Projection: t_null.x, count(Int64(1)) AS count(*) AS cnt
282+
09)------------Aggregate: groupBy=[[t_null.x]], aggr=[[count(Int64(1))]]
283+
10)--------------TableScan: t_null projection=[x]
284+
285+
# 5.2 The ORDER BY variant: `g.x` is NULL for both rows, so the `g.cnt`
286+
# tie-breaker is what orders them.
287+
query II
288+
SELECT g.x, g.cnt
289+
FROM t_probe a
290+
LEFT JOIN (SELECT x, count(*) AS cnt FROM t_null GROUP BY x) g
291+
ON a.z = g.cnt
292+
ORDER BY g.x, g.cnt;
293+
----
294+
NULL 2
295+
NULL NULL
296+
297+
statement ok
298+
drop table t_null;
299+
300+
statement ok
301+
drop table t_probe;
302+
303+
##########
304+
## Cleanup
305+
##########
306+
307+
statement ok
308+
drop table t_pk;
309+
310+
statement ok
311+
drop table t_uniq;
312+
313+
statement ok
314+
RESET datafusion.explain.logical_plan_only;

0 commit comments

Comments
 (0)