Repository navigation
Commit 00eba79
authored
feat(pwmj): support LeftSemi/LeftAnti existence joins via classic scan (#23870)
## Which issue does this close?
Part of #17427 (Make `PiecewiseMergeJoin` work in DataFusion). Adds
`LeftSemi` / `LeftAnti` support, one of the epic's checklist items.
Supersedes the stale #18392, taking the alternative approach that
@2010YOUY01 suggested there (reuse the classic join path for generality)
rather than a dedicated existence stream.
## Rationale for this change
An inequality-correlated `EXISTS` / `NOT EXISTS` (e.g. `WHERE EXISTS
(SELECT 1 FROM r WHERE l.x < r.y)`) has no equi-key, so it decorrelates
to a `LeftSemi` / `LeftAnti` join with a single range predicate. Today
`PiecewiseMergeJoinExec` rejects existence joins (`not_impl_err!`) and
these queries fall back to `NestedLoopJoinExec`, which is O(n*m).
Microbenchmark (20K × 20K rows, single inequality,
`enable_piecewise_merge_join`
on vs off), added in this PR as `piecewise_merge_join_semi_anti`:
| Case | PWMJ | NestedLoopJoin | Speedup |
|------------------------------|----------|----------------|---------|
| LeftSemi, high selectivity | ~0.50 ms | ~75 ms | ~150× |
| LeftAnti, high selectivity | ~0.44 ms | ~75 ms | ~170× |
| LeftSemi, low selectivity | ~0.48 ms | ~76 ms | ~158× |
| LeftAnti, low selectivity | ~0.48 ms | ~75 ms | ~155× |
## What changes are included in this PR?
**Existence joins (`LeftSemi` / `LeftAnti`) for `PiecewiseMergeJoin`:**
- Route `LeftSemi` / `LeftAnti` with a single range predicate to
`PiecewiseMergeJoinExec` in the physical planner (still gated behind
`enable_piecewise_merge_join`, default `false`).
- Reuse the classic scan: on the first match, mark the matching
buffered-row suffix in the visited bitmap and emit from it in the final
pass (`LeftSemi` = marked rows, `LeftAnti` = unmarked; NULL join keys
are never marked, so they are correctly excluded from Semi and included
in Anti). Only left-side columns are produced.
- `RightSemi` / `RightAnti` / `Mark` remain unsupported (they require
swapping the inputs); they are still rejected in `try_new` and excluded
in the planner. Left as a follow-up.
- Two small optimizations so existence marking stays O(buffered), not
O(n*m): stop scanning a batch after the first match (the marked suffix
is maximal), and a cross-batch low-water mark so later batches only mark
not-yet-marked rows.
- Updated the operator docstring to describe the implemented
classic-reuse path and keep the min/max fast-path as a documented
follow-up.
## Are these changes tested?
Yes.
- 33 unit tests in `classic_join.rs` covering `LeftSemi` / `LeftAnti`
across `<`, `<=`, `>`, `>=`; NULL join keys; all-null streamed side;
empty inputs; `Date32` keys; multi-batch and multi-partition streamed
inputs; and the low-water-mark skip branch.
- End-to-end SLT coverage in `pwmj.slt` for `EXISTS` / `NOT EXISTS`
(including NULLs) with `EXPLAIN` assertions confirming the plan uses
`PiecewiseMergeJoin`.
- The multi-partition test also guards the final-pass counter fix.
## Are there any user-facing changes?
No behaviour change by default: `enable_piecewise_merge_join` remains
`false`. When enabled, single-range-predicate `LeftSemi` / `LeftAnti`
joins are planned as `PiecewiseMergeJoin` instead of `NestedLoopJoin`.
No API changes.1 parent 9f377c4 commit 00eba79
7 files changed
Lines changed: 1939 additions & 25 deletions
File tree
- datafusion
- core
- src
- tests/fuzz_cases
- physical-plan/src/joins/piecewise_merge_join
- sqllogictest/test_files
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
1602 | 1602 | | |
1603 | 1603 | | |
1604 | 1604 | | |
| 1605 | + | |
| 1606 | + | |
| 1607 | + | |
| 1608 | + | |
1605 | 1609 | | |
1606 | 1610 | | |
1607 | | - | |
1608 | | - | |
1609 | | - | |
| 1611 | + | |
1610 | 1612 | | |
1611 | 1613 | | |
1612 | 1614 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
34 | 34 | | |
35 | 35 | | |
36 | 36 | | |
37 | | - | |
| 37 | + | |
| 38 | + | |
38 | 39 | | |
| 40 | + | |
| 41 | + | |
39 | 42 | | |
40 | 43 | | |
| 44 | + | |
41 | 45 | | |
42 | 46 | | |
43 | 47 | | |
44 | 48 | | |
45 | 49 | | |
| 50 | + | |
46 | 51 | | |
47 | 52 | | |
48 | 53 | | |
| 54 | + | |
49 | 55 | | |
50 | 56 | | |
51 | 57 | | |
| |||
1347 | 1353 | | |
1348 | 1354 | | |
1349 | 1355 | | |
| 1356 | + | |
| 1357 | + | |
| 1358 | + | |
| 1359 | + | |
| 1360 | + | |
| 1361 | + | |
| 1362 | + | |
| 1363 | + | |
| 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 | + | |
| 1393 | + | |
| 1394 | + | |
| 1395 | + | |
| 1396 | + | |
| 1397 | + | |
| 1398 | + | |
| 1399 | + | |
| 1400 | + | |
| 1401 | + | |
| 1402 | + | |
| 1403 | + | |
| 1404 | + | |
| 1405 | + | |
| 1406 | + | |
| 1407 | + | |
| 1408 | + | |
| 1409 | + | |
| 1410 | + | |
| 1411 | + | |
| 1412 | + | |
| 1413 | + | |
| 1414 | + | |
| 1415 | + | |
| 1416 | + | |
| 1417 | + | |
| 1418 | + | |
| 1419 | + | |
| 1420 | + | |
| 1421 | + | |
| 1422 | + | |
| 1423 | + | |
| 1424 | + | |
| 1425 | + | |
| 1426 | + | |
| 1427 | + | |
| 1428 | + | |
| 1429 | + | |
| 1430 | + | |
| 1431 | + | |
| 1432 | + | |
| 1433 | + | |
| 1434 | + | |
| 1435 | + | |
| 1436 | + | |
| 1437 | + | |
| 1438 | + | |
| 1439 | + | |
| 1440 | + | |
| 1441 | + | |
| 1442 | + | |
| 1443 | + | |
| 1444 | + | |
| 1445 | + | |
| 1446 | + | |
| 1447 | + | |
| 1448 | + | |
| 1449 | + | |
| 1450 | + | |
| 1451 | + | |
| 1452 | + | |
| 1453 | + | |
| 1454 | + | |
| 1455 | + | |
| 1456 | + | |
| 1457 | + | |
| 1458 | + | |
| 1459 | + | |
| 1460 | + | |
| 1461 | + | |
| 1462 | + | |
| 1463 | + | |
| 1464 | + | |
| 1465 | + | |
| 1466 | + | |
| 1467 | + | |
| 1468 | + | |
| 1469 | + | |
| 1470 | + | |
| 1471 | + | |
| 1472 | + | |
| 1473 | + | |
| 1474 | + | |
| 1475 | + | |
| 1476 | + | |
| 1477 | + | |
| 1478 | + | |
| 1479 | + | |
| 1480 | + | |
| 1481 | + | |
| 1482 | + | |
| 1483 | + | |
| 1484 | + | |
| 1485 | + | |
| 1486 | + | |
| 1487 | + | |
| 1488 | + | |
| 1489 | + | |
| 1490 | + | |
| 1491 | + | |
| 1492 | + | |
| 1493 | + | |
| 1494 | + | |
| 1495 | + | |
| 1496 | + | |
| 1497 | + | |
| 1498 | + | |
| 1499 | + | |
| 1500 | + | |
| 1501 | + | |
| 1502 | + | |
| 1503 | + | |
| 1504 | + | |
| 1505 | + | |
| 1506 | + | |
| 1507 | + | |
| 1508 | + | |
| 1509 | + | |
| 1510 | + | |
| 1511 | + | |
| 1512 | + | |
| 1513 | + | |
| 1514 | + | |
| 1515 | + | |
| 1516 | + | |
| 1517 | + | |
| 1518 | + | |
| 1519 | + | |
| 1520 | + | |
| 1521 | + | |
| 1522 | + | |
| 1523 | + | |
| 1524 | + | |
| 1525 | + | |
| 1526 | + | |
| 1527 | + | |
| 1528 | + | |
| 1529 | + | |
| 1530 | + | |
| 1531 | + | |
| 1532 | + | |
| 1533 | + | |
| 1534 | + | |
| 1535 | + | |
| 1536 | + | |
| 1537 | + | |
| 1538 | + | |
| 1539 | + | |
| 1540 | + | |
| 1541 | + | |
| 1542 | + | |
| 1543 | + | |
| 1544 | + | |
| 1545 | + | |
| 1546 | + | |
| 1547 | + | |
| 1548 | + | |
| 1549 | + | |
| 1550 | + | |
| 1551 | + | |
| 1552 | + | |
| 1553 | + | |
| 1554 | + | |
| 1555 | + | |
| 1556 | + | |
| 1557 | + | |
| 1558 | + | |
| 1559 | + | |
| 1560 | + | |
| 1561 | + | |
| 1562 | + | |
| 1563 | + | |
| 1564 | + | |
| 1565 | + | |
| 1566 | + | |
| 1567 | + | |
| 1568 | + | |
| 1569 | + | |
| 1570 | + | |
0 commit comments