Skip to content

Commit ac78aa0

Browse files
authored
feat: extend SLT tests for hash join vs PWMJ, hash join vs SMJ (apache#24805)
## Which issue does this PR close? <!-- We generally require a GitHub issue to be filed for all bug fixes and enhancements and this helps us generate change logs for our releases. You can link an issue to this PR using the GitHub syntax. For example `Closes apache#123` indicates that this PR will close issue apache#123. --> - Closes apache#24641 . ## Rationale for this change `PiecewiseMergeJoinExec` and `SortMergeJoinExec` must return the same results as the mature join implementations they can be swapped for, across every batch boundary. Today that equivalence is checked ad hoc. Using the `# configMatrix:` directive from apache#24493, one `.slt` file can assert it directly: run the same queries once per join implementation and once per batch size, and require identical output. <!-- Why are you proposing this change? If this is already explained clearly in the issue then this section is not needed. Explaining clearly why changes are proposed helps reviewers understand your changes and offer better suggestions for fixes. Please explain the problem you are trying to solve in terms of the user-visible behavior, rather than the implementation. For example, "The code in `foo.rs` doesn't handle nulls" is a symptom of the implementation. "COUNT(DISTINCT) returns wrong results when the column contains nulls" is the user-visible problem. --> ## What changes are included in this PR? <!-- There is no need to duplicate the description in the issue here, but it is sometimes worth providing a summary of the individual changes in this PR. --> ## What is the testing strategy for this PR? <!-- We typically require tests for all PRs in order to: 1. Prevent the code from being accidentally broken by subsequent changes 2. Serve as another way to document the expected behavior of the code Briefly describe how this PR is tested, and point to the specific tests you added. For example: 'This new feature is covered by the `sqllogictest` cases added in `foo.slt`'. If this PR does not add tests, explain why. For example, if the change is already covered by existing tests, please mention it. You should also check the `codecov` bot reply on this PR to confirm the changed code is exercised. --> ## Are there any user-facing changes? <!-- If there are user-facing changes then we may require documentation to be updated before approving the PR. If there are any breaking changes to public APIs, please add the `api change` label. -->
1 parent da89c7c commit ac78aa0

5 files changed

Lines changed: 1346 additions & 0 deletions

File tree

Lines changed: 202 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,202 @@
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+
# Mark-join correctness across a config matrix. A mark join adds a boolean `mark`
19+
# per left row and comes from EXISTS/IN/NOT EXISTS/NOT IN inside a disjunction
20+
# (`WHERE <pred> OR EXISTS(..)`; see mark_join in decorrelate_predicate_subquery.rs).
21+
# For an equijoin mark, prefer_hash_join toggles the operator: false ->
22+
# SortMergeJoinExec LeftMark, true -> HashJoinExec RightMark (inputs swapped), so
23+
# sweeping {true,false} x batch_size {1,2,100,8192} cross-checks both directions
24+
# and must agree row-for-row. Range mark joins run on NestedLoopJoin regardless
25+
# (Part 2, batch_size only). SMJ needs target_partitions>1 and repartition_joins,
26+
# set below (not swept). Matrix rules: no EXPLAIN, no in-file SET of a swept knob,
27+
# rowsort every multi-row query.
28+
29+
# configMatrix: datafusion.optimizer.prefer_hash_join=true,false
30+
# configMatrix: datafusion.execution.batch_size=1,2,100,8192
31+
32+
statement ok
33+
set datafusion.execution.target_partitions = 4;
34+
35+
statement ok
36+
set datafusion.optimizer.repartition_joins = true;
37+
38+
# ------------------------------------------------------------------
39+
# Fixtures: duplicate and NULL keys on the subquery side, a NULL key and an
40+
# unmatched key on the outer side.
41+
# ------------------------------------------------------------------
42+
statement ok
43+
CREATE TABLE mk_l(k INT, v INT) AS VALUES
44+
(1, 10), (2, 20), (3, 30), (4, 40), (NULL, 50);
45+
46+
statement ok
47+
CREATE TABLE mk_r(k INT) AS VALUES (1), (2), (2), (NULL);
48+
49+
# mk_r without the NULL, for NOT IN cases that would otherwise be swallowed by
50+
# three-valued logic.
51+
statement ok
52+
CREATE TABLE mk_r_nn(k INT) AS VALUES (1), (2), (2);
53+
54+
statement ok
55+
CREATE TABLE mk_empty(k INT);
56+
57+
# ==================================================================
58+
# Part 1: Equijoin mark joins (LeftMark on SMJ vs RightMark on HashJoin)
59+
# ==================================================================
60+
61+
# EXISTS in a disjunction with a sometimes-true predicate. mark(EXISTS k in
62+
# {1,2}) is true for k=1,2; the predicate v>35 is true for k=4 and k=NULL.
63+
query II rowsort
64+
SELECT l.k, l.v FROM mk_l l
65+
WHERE l.v > 35 OR EXISTS (SELECT 1 FROM mk_r r WHERE l.k = r.k);
66+
----
67+
1 10
68+
2 20
69+
4 40
70+
NULL 50
71+
72+
# NOT EXISTS in a disjunction: mark is negated, true for k not in {1,2}.
73+
query II rowsort
74+
SELECT l.k, l.v FROM mk_l l
75+
WHERE l.v > 35 OR NOT EXISTS (SELECT 1 FROM mk_r r WHERE l.k = r.k);
76+
----
77+
3 30
78+
4 40
79+
NULL 50
80+
81+
# Predicate never true (no negative k), so the result isolates the mark: the
82+
# EXISTS rows k in {1,2}. Exercises the mark column with the OR contributing
83+
# nothing.
84+
query II rowsort
85+
SELECT l.k, l.v FROM mk_l l
86+
WHERE l.k < 0 OR EXISTS (SELECT 1 FROM mk_r r WHERE l.k = r.k);
87+
----
88+
1 10
89+
2 20
90+
91+
# Same, negated: isolates NOT EXISTS. The NULL-keyed left row never matches, so
92+
# it is kept.
93+
query II rowsort
94+
SELECT l.k, l.v FROM mk_l l
95+
WHERE l.k < 0 OR NOT EXISTS (SELECT 1 FROM mk_r r WHERE l.k = r.k);
96+
----
97+
3 30
98+
4 40
99+
NULL 50
100+
101+
# IN in a disjunction: same matches as EXISTS here; the NULL in the subquery adds
102+
# no true values.
103+
query II rowsort
104+
SELECT l.k, l.v FROM mk_l l
105+
WHERE l.v > 35 OR l.k IN (SELECT r.k FROM mk_r r);
106+
----
107+
1 10
108+
2 20
109+
4 40
110+
NULL 50
111+
112+
# NOT IN over a NULL-free subquery: mark(NOT IN) is true for k not in {1,2}.
113+
query II rowsort
114+
SELECT l.k, l.v FROM mk_l l
115+
WHERE l.v > 35 OR l.k NOT IN (SELECT r.k FROM mk_r_nn r);
116+
----
117+
3 30
118+
4 40
119+
NULL 50
120+
121+
# https://github.com/apache/datafusion/issues/24854
122+
# query II rowsort
123+
# SELECT l.k, l.v FROM mk_l l
124+
# WHERE l.v > 35 OR l.k NOT IN (SELECT r.k FROM mk_r r);
125+
# ----
126+
# 4 40
127+
# NULL 50
128+
129+
# Empty subquery: EXISTS is always false, so the result is just the predicate.
130+
query II rowsort
131+
SELECT l.k, l.v FROM mk_l l
132+
WHERE l.v > 35 OR EXISTS (SELECT 1 FROM mk_empty r WHERE l.k = r.k);
133+
----
134+
4 40
135+
NULL 50
136+
137+
# Empty subquery, negated: NOT EXISTS is always true, so every row survives.
138+
query II rowsort
139+
SELECT l.k, l.v FROM mk_l l
140+
WHERE l.k < 0 OR NOT EXISTS (SELECT 1 FROM mk_empty r WHERE l.k = r.k);
141+
----
142+
1 10
143+
2 20
144+
3 30
145+
4 40
146+
NULL 50
147+
148+
# Multiple equi keys in the mark correlation.
149+
statement ok
150+
CREATE TABLE mk2_l(k1 INT, k2 INT, v INT) AS VALUES
151+
(1, 1, 10), (1, 2, 20), (2, 2, 30), (3, 3, 40);
152+
153+
statement ok
154+
CREATE TABLE mk2_r(k1 INT, k2 INT) AS VALUES (1, 1), (2, 2), (1, 9);
155+
156+
query III rowsort
157+
SELECT l.k1, l.k2, l.v FROM mk2_l l
158+
WHERE l.v > 35 OR EXISTS (SELECT 1 FROM mk2_r r WHERE l.k1 = r.k1 AND l.k2 = r.k2);
159+
----
160+
1 1 10
161+
2 2 30
162+
3 3 40
163+
164+
# Cross-table filter in the correlation (regression #21197): unmatched mark rows
165+
# produce null right indices that must not corrupt non-nullable left columns.
166+
# EXISTS holds for the k=2 rows (partner (2,99) differs in d); k=1's partner
167+
# equals its d, so false.
168+
statement ok
169+
CREATE TABLE mkf_l(k INT, d INT) AS VALUES (1, 10), (2, 20), (2, 25), (3, 30);
170+
171+
statement ok
172+
CREATE TABLE mkf_r(k INT, d INT) AS VALUES (1, 10), (2, 20), (2, 99);
173+
174+
query II rowsort
175+
SELECT l.k, l.d FROM mkf_l l
176+
WHERE l.d < 0 OR EXISTS (SELECT 1 FROM mkf_r r WHERE l.k = r.k AND r.d <> l.d);
177+
----
178+
2 20
179+
2 25
180+
181+
# ==================================================================
182+
# Part 2: Range mark joins (RightMark on NestedLoopJoin)
183+
# ==================================================================
184+
# No equi key, so these run on NestedLoopJoin in both combinations; only
185+
# batch_size varies. mk_r non-null keys = {1,2,2}.
186+
187+
# EXISTS l.k > r.k is true for k>1, i.e. k in {2,3,4}. Predicate never true.
188+
query II rowsort
189+
SELECT l.k, l.v FROM mk_l l
190+
WHERE l.v > 100 OR EXISTS (SELECT 1 FROM mk_r r WHERE l.k > r.k);
191+
----
192+
2 20
193+
3 30
194+
4 40
195+
196+
# NOT EXISTS of the same range: true for k=1 (no smaller r) and the NULL key.
197+
query II rowsort
198+
SELECT l.k, l.v FROM mk_l l
199+
WHERE l.k < 0 OR NOT EXISTS (SELECT 1 FROM mk_r r WHERE l.k > r.k);
200+
----
201+
1 10
202+
NULL 50
Lines changed: 103 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,103 @@
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+
# Plan proof for piecewise_merge_join_matrix.slt. Not a matrix file: it fixes
19+
# batch_size=2 and enable_piecewise_merge_join=true so it can EXPLAIN what the
20+
# matrix relies on but cannot check itself -- the streamed side is a range
21+
# LazyMemoryExec with batch_size=2 (so range(3,8), 5 rows, arrives as 3 batches)
22+
# feeding a PiecewiseMergeJoin, not a fallback. A VALUES source would not show
23+
# batch_size in the plan.
24+
25+
statement ok
26+
set datafusion.optimizer.enable_piecewise_merge_join = true;
27+
28+
statement ok
29+
set datafusion.execution.batch_size = 2;
30+
31+
statement ok
32+
CREATE TABLE pb_l(id INT, v INT) AS
33+
SELECT CAST(value AS INT) AS id, CAST(value AS INT) AS v FROM range(1, 11);
34+
35+
# Existence (LeftSemi): range streamed side (batch_size=2) -> LeftSemi PWMJ.
36+
query TT
37+
EXPLAIN SELECT count(*) FROM pb_l l WHERE EXISTS (SELECT 1 FROM range(3, 8) r WHERE l.v > r.value);
38+
----
39+
logical_plan
40+
01)Projection: count(Int64(1)) AS count(*)
41+
02)--Aggregate: groupBy=[[]], aggr=[[count(Int64(1))]]
42+
03)----Projection:
43+
04)------LeftSemi Join: Filter: CAST(l.v AS Int64) > __correlated_sq_1.value
44+
05)--------SubqueryAlias: l
45+
06)----------TableScan: pb_l projection=[v]
46+
07)--------SubqueryAlias: __correlated_sq_1
47+
08)----------SubqueryAlias: r
48+
09)------------TableScan: range() projection=[value]
49+
physical_plan
50+
01)ProjectionExec: expr=[count(Int64(1))@0 as count(*)]
51+
02)--AggregateExec: mode=Final, gby=[], aggr=[count(Int64(1))]
52+
03)----CoalescePartitionsExec
53+
04)------AggregateExec: mode=Partial, gby=[], aggr=[count(Int64(1))]
54+
05)--------ProjectionExec: expr=[]
55+
06)----------PiecewiseMergeJoin: operator=Gt, join_type=LeftSemi, on=(CAST(v AS Int64) > value)
56+
07)------------SortPreservingMergeExec: [CAST(v@0 AS Int64) ASC]
57+
08)--------------SortExec: expr=[CAST(v@0 AS Int64) ASC], preserve_partitioning=[true]
58+
09)----------------DataSourceExec: partitions=4, partition_sizes=[2, 1, 1, 1]
59+
10)------------RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1
60+
11)--------------LazyMemoryExec: partitions=1, batch_generators=[range: start=3, end=8, batch_size=2]
61+
62+
# Same result the matrix asserts (v > min(3) -> {4..10} = 7).
63+
query I
64+
SELECT count(*) FROM pb_l l WHERE EXISTS (SELECT 1 FROM range(3, 8) r WHERE l.v > r.value);
65+
----
66+
7
67+
68+
# Classic Inner: same range streamed side -> Inner PWMJ.
69+
query TT
70+
EXPLAIN SELECT count(*) FROM pb_l l JOIN range(3, 8) r ON l.v < r.value;
71+
----
72+
logical_plan
73+
01)Projection: count(Int64(1)) AS count(*)
74+
02)--Aggregate: groupBy=[[]], aggr=[[count(Int64(1))]]
75+
03)----Projection:
76+
04)------Inner Join: Filter: CAST(l.v AS Int64) < r.value
77+
05)--------SubqueryAlias: l
78+
06)----------TableScan: pb_l projection=[v]
79+
07)--------SubqueryAlias: r
80+
08)----------TableScan: range() projection=[value]
81+
physical_plan
82+
01)ProjectionExec: expr=[count(Int64(1))@0 as count(*)]
83+
02)--AggregateExec: mode=Final, gby=[], aggr=[count(Int64(1))]
84+
03)----CoalescePartitionsExec
85+
04)------AggregateExec: mode=Partial, gby=[], aggr=[count(Int64(1))]
86+
05)--------ProjectionExec: expr=[]
87+
06)----------PiecewiseMergeJoin: operator=Lt, join_type=Inner, on=(CAST(v AS Int64) < value)
88+
07)------------SortPreservingMergeExec: [CAST(v@0 AS Int64) DESC]
89+
08)--------------SortExec: expr=[CAST(v@0 AS Int64) DESC], preserve_partitioning=[true]
90+
09)----------------DataSourceExec: partitions=4, partition_sizes=[2, 1, 1, 1]
91+
10)------------RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1
92+
11)--------------LazyMemoryExec: partitions=1, batch_generators=[range: start=3, end=8, batch_size=2]
93+
94+
query I
95+
SELECT count(*) FROM pb_l l JOIN range(3, 8) r ON l.v < r.value;
96+
----
97+
20
98+
99+
statement ok
100+
RESET datafusion.execution.batch_size;
101+
102+
statement ok
103+
RESET datafusion.optimizer.enable_piecewise_merge_join;

0 commit comments

Comments
 (0)