Repository navigation
Commit bd219dc
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
- physical-plan/src/joins
- sqllogictest/test_files
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
245 | 245 | | |
246 | 246 | | |
247 | 247 | | |
248 | | - | |
| 248 | + | |
| 249 | + | |
249 | 250 | | |
250 | 251 | | |
251 | 252 | | |
| |||
256 | 257 | | |
257 | 258 | | |
258 | 259 | | |
| 260 | + | |
259 | 261 | | |
260 | 262 | | |
261 | 263 | | |
| |||
823 | 825 | | |
824 | 826 | | |
825 | 827 | | |
826 | | - | |
| 828 | + | |
| 829 | + | |
| 830 | + | |
| 831 | + | |
| 832 | + | |
| 833 | + | |
| 834 | + | |
| 835 | + | |
| 836 | + | |
| 837 | + | |
827 | 838 | | |
828 | 839 | | |
829 | 840 | | |
| |||
1351 | 1362 | | |
1352 | 1363 | | |
1353 | 1364 | | |
| 1365 | + | |
| 1366 | + | |
| 1367 | + | |
| 1368 | + | |
| 1369 | + | |
| 1370 | + | |
| 1371 | + | |
| 1372 | + | |
| 1373 | + | |
| 1374 | + | |
| 1375 | + | |
| 1376 | + | |
| 1377 | + | |
| 1378 | + | |
| 1379 | + | |
| 1380 | + | |
| 1381 | + | |
| 1382 | + | |
| 1383 | + | |
| 1384 | + | |
| 1385 | + | |
| 1386 | + | |
| 1387 | + | |
| 1388 | + | |
| 1389 | + | |
| 1390 | + | |
| 1391 | + | |
| 1392 | + | |
1354 | 1393 | | |
1355 | 1394 | | |
1356 | 1395 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
149 | 149 | | |
150 | 150 | | |
151 | 151 | | |
152 | | - | |
| 152 | + | |
| 153 | + | |
| 154 | + | |
153 | 155 | | |
154 | 156 | | |
155 | 157 | | |
156 | 158 | | |
157 | 159 | | |
158 | | - | |
| 160 | + | |
159 | 161 | | |
160 | 162 | | |
161 | 163 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
2333 | 2333 | | |
2334 | 2334 | | |
2335 | 2335 | | |
| 2336 | + | |
| 2337 | + | |
| 2338 | + | |
| 2339 | + | |
| 2340 | + | |
| 2341 | + | |
| 2342 | + | |
| 2343 | + | |
| 2344 | + | |
| 2345 | + | |
| 2346 | + | |
| 2347 | + | |
| 2348 | + | |
| 2349 | + | |
| 2350 | + | |
| 2351 | + | |
| 2352 | + | |
| 2353 | + | |
| 2354 | + | |
| 2355 | + | |
| 2356 | + | |
| 2357 | + | |
| 2358 | + | |
| 2359 | + | |
| 2360 | + | |
| 2361 | + | |
| 2362 | + | |
| 2363 | + | |
| 2364 | + | |
| 2365 | + | |
| 2366 | + | |
| 2367 | + | |
| 2368 | + | |
| 2369 | + | |
| 2370 | + | |
| 2371 | + | |
| 2372 | + | |
| 2373 | + | |
| 2374 | + | |
| 2375 | + | |
| 2376 | + | |
| 2377 | + | |
| 2378 | + | |
| 2379 | + | |
| 2380 | + | |
| 2381 | + | |
| 2382 | + | |
| 2383 | + | |
| 2384 | + | |
| 2385 | + | |
| 2386 | + | |
| 2387 | + | |
| 2388 | + | |
| 2389 | + | |
| 2390 | + | |
| 2391 | + | |
| 2392 | + | |
| 2393 | + | |
| 2394 | + | |
| 2395 | + | |
| 2396 | + | |
| 2397 | + | |
| 2398 | + | |
| 2399 | + | |
| 2400 | + | |
| 2401 | + | |
| 2402 | + | |
| 2403 | + | |
| 2404 | + | |
| 2405 | + | |
| 2406 | + | |
| 2407 | + | |
| 2408 | + | |
| 2409 | + | |
| 2410 | + | |
| 2411 | + | |
| 2412 | + | |
| 2413 | + | |
| 2414 | + | |
| 2415 | + | |
| 2416 | + | |
| 2417 | + | |
| 2418 | + | |
| 2419 | + | |
| 2420 | + | |
| 2421 | + | |
| 2422 | + | |
| 2423 | + | |
| 2424 | + | |
| 2425 | + | |
| 2426 | + | |
| 2427 | + | |
| 2428 | + | |
| 2429 | + | |
| 2430 | + | |
| 2431 | + | |
| 2432 | + | |
| 2433 | + | |
| 2434 | + | |
| 2435 | + | |
| 2436 | + | |
| 2437 | + | |
| 2438 | + | |
| 2439 | + | |
| 2440 | + | |
| 2441 | + | |
| 2442 | + | |
| 2443 | + | |
| 2444 | + | |
| 2445 | + | |
| 2446 | + | |
| 2447 | + | |
| 2448 | + | |
| 2449 | + | |
| 2450 | + | |
| 2451 | + | |
| 2452 | + | |
| 2453 | + | |
| 2454 | + | |
| 2455 | + | |
| 2456 | + | |
| 2457 | + | |
| 2458 | + | |
| 2459 | + | |
| 2460 | + | |
| 2461 | + | |
| 2462 | + | |
| 2463 | + | |
| 2464 | + | |
| 2465 | + | |
| 2466 | + | |
| 2467 | + | |
| 2468 | + | |
0 commit comments