Skip to content

Commit bd219dc

Browse files
authored
fix: keep probe-side constants in join equivalence properties (apache#26459)
## Which issue does this PR close? - Closes apache#26283. ## Rationale for this change A query that orders by a column that is constant on the probe side of a join fails to plan: ```text SanityCheckPlan caused by Error during planning: Plan: ["SortPreservingMergeExec: [k@0 DESC]", " HashJoinExec: ..."] does not satisfy order requirements: [k@0 DESC]. Child-0 order: [] ``` `EquivalenceClass::try_with_offset` builds a new class from the expressions and does not copy `constant`. `EquivalenceGroup::join` uses it for every class of the right side, so the join output forgets that `k` is constant. `EnsureRequirements` removes the sort because `k` is constant below the join, and `SanityCheckPlan` then rejects the plan because the join output no longer says so. ## What changes are included in this PR? - `try_with_offset` keeps the class's constant value. - `EquivalenceGroup::join` clears the right side's constants for `Left` and `Full` joins. Unmatched rows pad that side with NULLs, so a constant there no longer holds. Without this, copying the constant would drop a sort that is needed. The first version of this PR added a sort in `EnsureRequirements` wherever the requirement could not be proven. Following review, it now fixes the join instead. The plan for apache#26283 then has no sort at all, instead of a sort on a constant column. The same problem exists the other way round: the left side's constants are kept for `Right` and `Full` joins, where that side is padded with NULLs too. For example, this returns `5` before the NULLs: ```sql CREATE TABLE t(a INT) AS VALUES (1), (2), (3); CREATE TABLE u(a INT) AS VALUES (9), (10), (1); SELECT s.k, u.a FROM (SELECT a, 5 AS k FROM t) s RIGHT JOIN u ON s.a = u.a ORDER BY s.k DESC NULLS FIRST; ``` This PR does not change the left side, because apache#26042 already rebuilds the classes of the side that is padded with NULLs, which drops these constants as well. ## What is the testing strategy for this PR? - `class.rs`: a unit test that a right-side constant stays constant after `Inner` and `Right` joins, and not after `Left` and `Full` joins. - `order.slt`: both queries from apache#26283, with results and `EXPLAIN`. Without the change, both fail to plan. - `order.slt`: a `LEFT JOIN` where the probe-side constant is padded with NULLs. If the constant is not cleared, the sort on it is dropped and the rows come back in the wrong order. ## Are there any user-facing changes? Queries like the one in apache#26283 plan and run instead of failing. There are no API changes.
1 parent c76ed53 commit bd219dc

3 files changed

Lines changed: 178 additions & 4 deletions

File tree

‎datafusion/physical-expr/src/equivalence/class.rs‎

Lines changed: 41 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -245,7 +245,8 @@ impl EquivalenceClass {
245245
}
246246

247247
/// Adds the given offset to all columns in the expressions inside this
248-
/// class. This is used when schemas are appended, e.g. in joins.
248+
/// class, keeping its constant value. This is used when schemas are
249+
/// appended, e.g. in joins.
249250
pub fn try_with_offset(&self, offset: isize) -> Result<Self> {
250251
let mut cls = Self::default();
251252
for expr_result in self
@@ -256,6 +257,7 @@ impl EquivalenceClass {
256257
{
257258
cls.push(expr_result?);
258259
}
260+
cls.constant.clone_from(&self.constant);
259261
Ok(cls)
260262
}
261263
}
@@ -823,7 +825,16 @@ impl EquivalenceGroup {
823825
self.iter().cloned().chain(
824826
right_equivalences
825827
.iter()
826-
.map(|cls| cls.try_with_offset(left_size as _))
828+
.map(|cls| {
829+
let mut cls = cls.try_with_offset(left_size as _)?;
830+
// Rows without a match on the right side are
831+
// padded with NULLs, so its constants no
832+
// longer hold.
833+
if matches!(join_type, JoinType::Left | JoinType::Full) {
834+
cls.constant = None;
835+
}
836+
Ok(cls)
837+
})
827838
.collect::<Result<Vec<_>>>()?,
828839
),
829840
);
@@ -1351,6 +1362,34 @@ mod tests {
13511362
Ok(())
13521363
}
13531364

1365+
/// A constant on the right side of a join stays constant in the join
1366+
/// output, unless unmatched rows pad the right side with NULLs.
1367+
/// <https://github.com/apache/datafusion/issues/26283>
1368+
#[test]
1369+
fn test_join_keeps_right_constants() -> Result<()> {
1370+
let schema = abc_schema();
1371+
let mut right = EquivalenceGroup::default();
1372+
right.add_constant(ConstExpr::from(col("a", &schema)?));
1373+
// `a` of the right side is column 4 of the join output
1374+
let right_a: Arc<dyn PhysicalExpr> = Arc::new(Column::new("a", 4));
1375+
1376+
for (join_type, expected) in [
1377+
(JoinType::Inner, true),
1378+
(JoinType::Right, true),
1379+
(JoinType::Left, false),
1380+
(JoinType::Full, false),
1381+
] {
1382+
let joined = EquivalenceGroup::default().join(&right, &join_type, 4, &[])?;
1383+
assert_eq!(
1384+
joined.is_expr_constant(&right_a).is_some(),
1385+
expected,
1386+
"{join_type}"
1387+
);
1388+
}
1389+
1390+
Ok(())
1391+
}
1392+
13541393
#[test]
13551394
fn test_has_same_classes_ignores_the_map() -> Result<()> {
13561395
// `map` indexes into `classes`, so equal classes must imply equal

‎datafusion/physical-plan/src/joins/cross_join.rs‎

Lines changed: 4 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -149,13 +149,15 @@ impl CrossJoinExec {
149149
right: &Arc<dyn ExecutionPlan>,
150150
schema: SchemaRef,
151151
) -> Result<PlanProperties> {
152-
// Calculate equivalence properties
152+
// Calculate equivalence properties. A cross join is an inner join
153+
// without keys: no side is padded with NULLs, so the constants of
154+
// both sides still hold.
153155
// TODO: Check equivalence properties of cross join, it may preserve
154156
// ordering in some cases.
155157
let eq_properties = join_equivalence_properties(
156158
left.equivalence_properties().clone(),
157159
right.equivalence_properties().clone(),
158-
&JoinType::Full,
160+
&JoinType::Inner,
159161
schema,
160162
&[false, false],
161163
None,

‎datafusion/sqllogictest/test_files/order.slt‎

Lines changed: 133 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2333,3 +2333,136 @@ DROP TABLE spm_orderings;
23332333

23342334
statement ok
23352335
set datafusion.execution.target_partitions = 4;
2336+
2337+
# `k` is constant on the probe side of the join, so the join output reports
2338+
# it as constant and no sort on `k` is needed.
2339+
# https://github.com/apache/datafusion/issues/26283
2340+
statement ok
2341+
CREATE TABLE probe_constant_t(a INT, b INT) AS VALUES (1, 1), (2, 2), (3, 3), (4, 4);
2342+
2343+
statement ok
2344+
CREATE TABLE probe_constant_u(a INT) AS VALUES (1);
2345+
2346+
statement ok
2347+
CREATE TABLE probe_constant_v(x INT) AS VALUES (1), (2);
2348+
2349+
query II
2350+
SELECT s.k, s.a
2351+
FROM (
2352+
SELECT probe_constant_t.a, -2 AS k
2353+
FROM probe_constant_t JOIN probe_constant_v ON probe_constant_t.b <> probe_constant_v.x
2354+
) s
2355+
JOIN probe_constant_u ON s.a = probe_constant_u.a
2356+
ORDER BY s.k DESC;
2357+
----
2358+
-2 1
2359+
2360+
query TT
2361+
EXPLAIN SELECT s.k, s.a
2362+
FROM (
2363+
SELECT probe_constant_t.a, -2 AS k
2364+
FROM probe_constant_t JOIN probe_constant_v ON probe_constant_t.b <> probe_constant_v.x
2365+
) s
2366+
JOIN probe_constant_u ON s.a = probe_constant_u.a
2367+
ORDER BY s.k DESC;
2368+
----
2369+
logical_plan
2370+
01)Sort: s.k DESC NULLS FIRST
2371+
02)--Projection: s.k, s.a
2372+
03)----Inner Join: s.a = probe_constant_u.a
2373+
04)------SubqueryAlias: s
2374+
05)--------Projection: probe_constant_t.a, Int64(-2) AS k
2375+
06)----------Inner Join: Filter: probe_constant_t.b != probe_constant_v.x
2376+
07)------------TableScan: probe_constant_t projection=[a, b]
2377+
08)------------TableScan: probe_constant_v projection=[x]
2378+
09)------TableScan: probe_constant_u projection=[a]
2379+
physical_plan
2380+
01)CoalescePartitionsExec
2381+
02)--HashJoinExec: mode=CollectLeft, join_type=Inner, on=[(a@0, a@0)], projection=[k@2, a@1]
2382+
03)----DataSourceExec: partitions=1, partition_sizes=[1]
2383+
04)----RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1
2384+
05)------ProjectionExec: expr=[a@0 as a, -2 as k]
2385+
06)--------NestedLoopJoinExec: join_type=Inner, filter=b@0 != x@1, projection=[a@1]
2386+
07)----------DataSourceExec: partitions=1, partition_sizes=[1]
2387+
08)----------DataSourceExec: partitions=1, partition_sizes=[1]
2388+
2389+
statement ok
2390+
SET datafusion.execution.target_partitions = 1;
2391+
2392+
query ITI
2393+
SELECT s.a, s.k, row_number() OVER (PARTITION BY s.a ORDER BY s.k) AS r
2394+
FROM probe_constant_u JOIN (SELECT a, 'x' AS k FROM probe_constant_t) AS s
2395+
ON s.a = probe_constant_u.a;
2396+
----
2397+
1 x 1
2398+
2399+
query TT
2400+
EXPLAIN SELECT s.a, s.k, row_number() OVER (PARTITION BY s.a ORDER BY s.k) AS r
2401+
FROM probe_constant_u JOIN (SELECT a, 'x' AS k FROM probe_constant_t) AS s
2402+
ON s.a = probe_constant_u.a;
2403+
----
2404+
logical_plan
2405+
01)Projection: s.a, s.k, row_number() PARTITION BY [s.a] ORDER BY [s.k ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW AS r
2406+
02)--WindowAggr: windowExpr=[[row_number() PARTITION BY [s.a] ORDER BY [s.k ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW]]
2407+
03)----Projection: s.a, s.k
2408+
04)------Inner Join: probe_constant_u.a = s.a
2409+
05)--------TableScan: probe_constant_u projection=[a]
2410+
06)--------SubqueryAlias: s
2411+
07)----------Projection: probe_constant_t.a, Utf8("x") AS k
2412+
08)------------TableScan: probe_constant_t projection=[a]
2413+
physical_plan
2414+
01)ProjectionExec: expr=[a@0 as a, k@1 as k, row_number() PARTITION BY [s.a] ORDER BY [s.k ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW@2 as r]
2415+
02)--BoundedWindowAggExec: wdw=[row_number() PARTITION BY [s.a] ORDER BY [s.k ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW: Field { "row_number() PARTITION BY [s.a] ORDER BY [s.k ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW": UInt64 }, frame: RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW], mode=[Sorted]
2416+
03)----HashJoinExec: mode=CollectLeft, join_type=Inner, on=[(a@0, a@0)], projection=[a@1, k@2]
2417+
04)------DataSourceExec: partitions=1, partition_sizes=[1]
2418+
05)------SortExec: expr=[a@0 ASC NULLS LAST], preserve_partitioning=[false]
2419+
06)--------FilterExec: DynamicFilter [ empty ]
2420+
07)----------ProjectionExec: expr=[a@0 as a, x as k]
2421+
08)------------DataSourceExec: partitions=1, partition_sizes=[1]
2422+
2423+
# Unmatched rows of a left join pad the probe side with NULLs, so `k` is not
2424+
# constant in the join output and the sort on `k` is kept.
2425+
query TT
2426+
EXPLAIN SELECT u.a, s.k
2427+
FROM (VALUES (1), (10)) AS u(a) LEFT JOIN (SELECT a, 'x' AS k FROM probe_constant_t) AS s
2428+
ON s.a = u.a
2429+
ORDER BY s.k DESC NULLS FIRST, u.a;
2430+
----
2431+
logical_plan
2432+
01)Sort: s.k DESC NULLS FIRST, u.a ASC NULLS LAST
2433+
02)--Projection: u.a, s.k
2434+
03)----Left Join: u.a = CAST(s.a AS Int64)
2435+
04)------SubqueryAlias: u
2436+
05)--------Projection: column1 AS a
2437+
06)----------Values: (Int64(1)), (Int64(10))
2438+
07)------SubqueryAlias: s
2439+
08)--------Projection: probe_constant_t.a, Utf8("x") AS k
2440+
09)----------TableScan: probe_constant_t projection=[a]
2441+
physical_plan
2442+
01)SortExec: expr=[k@1 DESC, a@0 ASC NULLS LAST], preserve_partitioning=[false]
2443+
02)--HashJoinExec: mode=CollectLeft, join_type=Left, on=[(a@0, CAST(s.a AS Int64)@2)], projection=[a@0, k@2]
2444+
03)----ProjectionExec: expr=[column1@0 as a]
2445+
04)------DataSourceExec: partitions=1, partition_sizes=[1]
2446+
05)----ProjectionExec: expr=[a@0 as a, x as k, CAST(a@0 AS Int64) as CAST(s.a AS Int64)]
2447+
06)------DataSourceExec: partitions=1, partition_sizes=[1]
2448+
2449+
query IT
2450+
SELECT u.a, s.k
2451+
FROM (VALUES (1), (10)) AS u(a) LEFT JOIN (SELECT a, 'x' AS k FROM probe_constant_t) AS s
2452+
ON s.a = u.a
2453+
ORDER BY s.k DESC NULLS FIRST, u.a;
2454+
----
2455+
10 NULL
2456+
1 x
2457+
2458+
statement ok
2459+
SET datafusion.execution.target_partitions = 4;
2460+
2461+
statement ok
2462+
DROP TABLE probe_constant_t;
2463+
2464+
statement ok
2465+
DROP TABLE probe_constant_u;
2466+
2467+
statement ok
2468+
DROP TABLE probe_constant_v;

0 commit comments

Comments
 (0)