Skip to content

Commit ef0a207

Browse files
jayzhan211alexanderbianchi
authored andcommitted
fix: keep probe-side constants in join equivalence properties (apache#26459)
- Closes apache#26283. 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. - `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. - `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. Queries like the one in apache#26283 plan and run instead of failing. There are no API changes. (cherry picked from commit bd219dc)
1 parent a89b540 commit ef0a207

3 files changed

Lines changed: 187 additions & 4 deletions

File tree

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

Lines changed: 50 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
}
@@ -791,7 +793,16 @@ impl EquivalenceGroup {
791793
self.iter().cloned().chain(
792794
right_equivalences
793795
.iter()
794-
.map(|cls| cls.try_with_offset(left_size as _))
796+
.map(|cls| {
797+
let mut cls = cls.try_with_offset(left_size as _)?;
798+
// Rows without a match on the right side are
799+
// padded with NULLs, so its constants no
800+
// longer hold.
801+
if matches!(join_type, JoinType::Left | JoinType::Full) {
802+
cls.constant = None;
803+
}
804+
Ok(cls)
805+
})
795806
.collect::<Result<Vec<_>>>()?,
796807
),
797808
);
@@ -1245,4 +1256,41 @@ mod tests {
12451256

12461257
Ok(())
12471258
}
1259+
1260+
fn abc_schema() -> Arc<Schema> {
1261+
Arc::new(Schema::new(vec![
1262+
Field::new("a", DataType::Int32, false),
1263+
Field::new("b", DataType::Int32, false),
1264+
Field::new("c", DataType::Int32, false),
1265+
Field::new("d", DataType::Int32, false),
1266+
]))
1267+
}
1268+
1269+
/// A constant on the right side of a join stays constant in the join
1270+
/// output, unless unmatched rows pad the right side with NULLs.
1271+
/// <https://github.com/apache/datafusion/issues/26283>
1272+
#[test]
1273+
fn test_join_keeps_right_constants() -> Result<()> {
1274+
let schema = abc_schema();
1275+
let mut right = EquivalenceGroup::default();
1276+
right.add_constant(ConstExpr::from(col("a", &schema)?));
1277+
// `a` of the right side is column 4 of the join output
1278+
let right_a: Arc<dyn PhysicalExpr> = Arc::new(Column::new("a", 4));
1279+
1280+
for (join_type, expected) in [
1281+
(JoinType::Inner, true),
1282+
(JoinType::Right, true),
1283+
(JoinType::Left, false),
1284+
(JoinType::Full, false),
1285+
] {
1286+
let joined = EquivalenceGroup::default().join(&right, &join_type, 4, &[])?;
1287+
assert_eq!(
1288+
joined.is_expr_constant(&right_a).is_some(),
1289+
expected,
1290+
"{join_type}"
1291+
);
1292+
}
1293+
1294+
Ok(())
1295+
}
12481296
}

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

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

‎datafusion/sqllogictest/test_files/order.slt‎

Lines changed: 133 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1969,3 +1969,136 @@ DROP TABLE sort_key_sink;
19691969

19701970
statement ok
19711971
DROP TABLE t2;
1972+
1973+
# `k` is constant on the probe side of the join, so the join output reports
1974+
# it as constant and no sort on `k` is needed.
1975+
# https://github.com/apache/datafusion/issues/26283
1976+
statement ok
1977+
CREATE TABLE probe_constant_t(a INT, b INT) AS VALUES (1, 1), (2, 2), (3, 3), (4, 4);
1978+
1979+
statement ok
1980+
CREATE TABLE probe_constant_u(a INT) AS VALUES (1);
1981+
1982+
statement ok
1983+
CREATE TABLE probe_constant_v(x INT) AS VALUES (1), (2);
1984+
1985+
query II
1986+
SELECT s.k, s.a
1987+
FROM (
1988+
SELECT probe_constant_t.a, -2 AS k
1989+
FROM probe_constant_t JOIN probe_constant_v ON probe_constant_t.b <> probe_constant_v.x
1990+
) s
1991+
JOIN probe_constant_u ON s.a = probe_constant_u.a
1992+
ORDER BY s.k DESC;
1993+
----
1994+
-2 1
1995+
1996+
query TT
1997+
EXPLAIN SELECT s.k, s.a
1998+
FROM (
1999+
SELECT probe_constant_t.a, -2 AS k
2000+
FROM probe_constant_t JOIN probe_constant_v ON probe_constant_t.b <> probe_constant_v.x
2001+
) s
2002+
JOIN probe_constant_u ON s.a = probe_constant_u.a
2003+
ORDER BY s.k DESC;
2004+
----
2005+
logical_plan
2006+
01)Sort: s.k DESC NULLS FIRST
2007+
02)--Projection: s.k, s.a
2008+
03)----Inner Join: s.a = probe_constant_u.a
2009+
04)------SubqueryAlias: s
2010+
05)--------Projection: probe_constant_t.a, Int64(-2) AS k
2011+
06)----------Inner Join: Filter: probe_constant_t.b != probe_constant_v.x
2012+
07)------------TableScan: probe_constant_t projection=[a, b]
2013+
08)------------TableScan: probe_constant_v projection=[x]
2014+
09)------TableScan: probe_constant_u projection=[a]
2015+
physical_plan
2016+
01)CoalescePartitionsExec
2017+
02)--HashJoinExec: mode=CollectLeft, join_type=Inner, on=[(a@0, a@0)], projection=[k@2, a@1]
2018+
03)----DataSourceExec: partitions=1, partition_sizes=[1]
2019+
04)----RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1
2020+
05)------ProjectionExec: expr=[a@0 as a, -2 as k]
2021+
06)--------NestedLoopJoinExec: join_type=Inner, filter=b@0 != x@1, projection=[a@1]
2022+
07)----------DataSourceExec: partitions=1, partition_sizes=[1]
2023+
08)----------DataSourceExec: partitions=1, partition_sizes=[1]
2024+
2025+
statement ok
2026+
SET datafusion.execution.target_partitions = 1;
2027+
2028+
query ITI
2029+
SELECT s.a, s.k, row_number() OVER (PARTITION BY s.a ORDER BY s.k) AS r
2030+
FROM probe_constant_u JOIN (SELECT a, 'x' AS k FROM probe_constant_t) AS s
2031+
ON s.a = probe_constant_u.a;
2032+
----
2033+
1 x 1
2034+
2035+
query TT
2036+
EXPLAIN SELECT s.a, s.k, row_number() OVER (PARTITION BY s.a ORDER BY s.k) AS r
2037+
FROM probe_constant_u JOIN (SELECT a, 'x' AS k FROM probe_constant_t) AS s
2038+
ON s.a = probe_constant_u.a;
2039+
----
2040+
logical_plan
2041+
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
2042+
02)--WindowAggr: windowExpr=[[row_number() PARTITION BY [s.a] ORDER BY [s.k ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW]]
2043+
03)----Projection: s.a, s.k
2044+
04)------Inner Join: probe_constant_u.a = s.a
2045+
05)--------TableScan: probe_constant_u projection=[a]
2046+
06)--------SubqueryAlias: s
2047+
07)----------Projection: probe_constant_t.a, Utf8("x") AS k
2048+
08)------------TableScan: probe_constant_t projection=[a]
2049+
physical_plan
2050+
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]
2051+
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]
2052+
03)----HashJoinExec: mode=CollectLeft, join_type=Inner, on=[(a@0, a@0)], projection=[a@1, k@2]
2053+
04)------DataSourceExec: partitions=1, partition_sizes=[1]
2054+
05)------SortExec: expr=[a@0 ASC NULLS LAST], preserve_partitioning=[false]
2055+
06)--------FilterExec: DynamicFilter [ empty ]
2056+
07)----------ProjectionExec: expr=[a@0 as a, x as k]
2057+
08)------------DataSourceExec: partitions=1, partition_sizes=[1]
2058+
2059+
# Unmatched rows of a left join pad the probe side with NULLs, so `k` is not
2060+
# constant in the join output and the sort on `k` is kept.
2061+
query TT
2062+
EXPLAIN SELECT u.a, s.k
2063+
FROM (VALUES (1), (10)) AS u(a) LEFT JOIN (SELECT a, 'x' AS k FROM probe_constant_t) AS s
2064+
ON s.a = u.a
2065+
ORDER BY s.k DESC NULLS FIRST, u.a;
2066+
----
2067+
logical_plan
2068+
01)Sort: s.k DESC NULLS FIRST, u.a ASC NULLS LAST
2069+
02)--Projection: u.a, s.k
2070+
03)----Left Join: u.a = CAST(s.a AS Int64)
2071+
04)------SubqueryAlias: u
2072+
05)--------Projection: column1 AS a
2073+
06)----------Values: (Int64(1)), (Int64(10))
2074+
07)------SubqueryAlias: s
2075+
08)--------Projection: probe_constant_t.a, Utf8("x") AS k
2076+
09)----------TableScan: probe_constant_t projection=[a]
2077+
physical_plan
2078+
01)SortExec: expr=[k@1 DESC, a@0 ASC NULLS LAST], preserve_partitioning=[false]
2079+
02)--HashJoinExec: mode=CollectLeft, join_type=Left, on=[(a@0, CAST(s.a AS Int64)@2)], projection=[a@0, k@2]
2080+
03)----ProjectionExec: expr=[column1@0 as a]
2081+
04)------DataSourceExec: partitions=1, partition_sizes=[1]
2082+
05)----ProjectionExec: expr=[a@0 as a, x as k, CAST(a@0 AS Int64) as CAST(s.a AS Int64)]
2083+
06)------DataSourceExec: partitions=1, partition_sizes=[1]
2084+
2085+
query IT
2086+
SELECT u.a, s.k
2087+
FROM (VALUES (1), (10)) AS u(a) LEFT JOIN (SELECT a, 'x' AS k FROM probe_constant_t) AS s
2088+
ON s.a = u.a
2089+
ORDER BY s.k DESC NULLS FIRST, u.a;
2090+
----
2091+
10 NULL
2092+
1 x
2093+
2094+
statement ok
2095+
SET datafusion.execution.target_partitions = 4;
2096+
2097+
statement ok
2098+
DROP TABLE probe_constant_t;
2099+
2100+
statement ok
2101+
DROP TABLE probe_constant_u;
2102+
2103+
statement ok
2104+
DROP TABLE probe_constant_v;

0 commit comments

Comments
 (0)