Repository navigation
Commit d0d993d
authored
fix: NestedLoopJoinExec emits spurious unmatched-left rows with multiple probe partitions (apache#22791)
## Problem
`NestedLoopJoinExec` can return incorrect and non deterministic results
for LEFT, RIGHT and FULL joins when the probe side has more than one
partition (the common case for any join whose condition is not a pure
equijoin). Some unmatched left rows are emitted twice: once correctly
and once again as an extra NULL padded row.
## Proof
Correct answer is 5 (every t1 row is unmatched). Verify with
`target_partitions = 1`. With multiple partitions an unpatched build
intermittently returns 6, 7 or 8. Because it is a scheduling race, run
it a few times to observe the divergence.
```sql
set datafusion.execution.target_partitions = 4;
set datafusion.execution.batch_size = 2;
create table t1(v bigint) as values (4),(72),(41),(98),(91);
create table t2(s varchar, w bigint) as values
('aaaaaaaaaaaaaaaa', 1),('bbbbbbbbbbbbbbbb', 2),('cccccccccccccccc', 3);
select count(*) as left_join_rows
from t1 left join t2 on (t1.v < t2.w and t2.s <= 'A');
```
## Solution
The probe streams share a `probe_threads_counter`; the stream that
drives it to 0 is the one that emits unmatched left rows, after all
partitions finish probing. In `handle_emit_left_unmatched`, after
`process_left_unmatched` returns `Ok(false)`,
`maybe_flush_ready_batch()` can return early with a ready batch before
the state advances to `Done`. The stream stays in `EmitLeftUnmatched`,
so the next poll re enters `process_left_unmatched` with `left_emit_idx
== 0` and decrements the counter a second time. The counter then reaches
0 before every partition has finished probing, so a partition emits
unmatched left rows early.
The fix decrements the counter at most once per probe stream using a new
`probe_completed_reported` flag (reset per chunk in the memory limited
path). All 42 existing `nested_loop_join` tests pass.
This is separate from apache#22641, which covers the memory limited spill
fallback path; this bug reproduces with unbounded memory and with
spilling disabled.1 parent 8036b94 commit d0d993d
2 files changed
Lines changed: 83 additions & 5 deletions
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
1064 | 1064 | | |
1065 | 1065 | | |
1066 | 1066 | | |
| 1067 | + | |
| 1068 | + | |
| 1069 | + | |
| 1070 | + | |
| 1071 | + | |
| 1072 | + | |
| 1073 | + | |
| 1074 | + | |
| 1075 | + | |
| 1076 | + | |
| 1077 | + | |
1067 | 1078 | | |
1068 | 1079 | | |
1069 | 1080 | | |
| |||
1337 | 1348 | | |
1338 | 1349 | | |
1339 | 1350 | | |
| 1351 | + | |
1340 | 1352 | | |
1341 | 1353 | | |
1342 | 1354 | | |
| |||
1863 | 1875 | | |
1864 | 1876 | | |
1865 | 1877 | | |
| 1878 | + | |
| 1879 | + | |
| 1880 | + | |
| 1881 | + | |
1866 | 1882 | | |
1867 | 1883 | | |
1868 | 1884 | | |
| |||
2341 | 2357 | | |
2342 | 2358 | | |
2343 | 2359 | | |
2344 | | - | |
| 2360 | + | |
| 2361 | + | |
| 2362 | + | |
2345 | 2363 | | |
2346 | 2364 | | |
2347 | 2365 | | |
| |||
2350 | 2368 | | |
2351 | 2369 | | |
2352 | 2370 | | |
2353 | | - | |
2354 | | - | |
2355 | | - | |
| 2371 | + | |
| 2372 | + | |
| 2373 | + | |
| 2374 | + | |
| 2375 | + | |
| 2376 | + | |
| 2377 | + | |
| 2378 | + | |
| 2379 | + | |
| 2380 | + | |
| 2381 | + | |
| 2382 | + | |
| 2383 | + | |
| 2384 | + | |
| 2385 | + | |
| 2386 | + | |
| 2387 | + | |
| 2388 | + | |
| 2389 | + | |
2356 | 2390 | | |
2357 | 2391 | | |
2358 | 2392 | | |
| |||
2368 | 2402 | | |
2369 | 2403 | | |
2370 | 2404 | | |
2371 | | - | |
| 2405 | + | |
2372 | 2406 | | |
2373 | 2407 | | |
2374 | 2408 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
5527 | 5527 | | |
5528 | 5528 | | |
5529 | 5529 | | |
| 5530 | + | |
| 5531 | + | |
| 5532 | + | |
| 5533 | + | |
| 5534 | + | |
| 5535 | + | |
| 5536 | + | |
| 5537 | + | |
| 5538 | + | |
| 5539 | + | |
| 5540 | + | |
| 5541 | + | |
| 5542 | + | |
| 5543 | + | |
| 5544 | + | |
| 5545 | + | |
| 5546 | + | |
| 5547 | + | |
| 5548 | + | |
| 5549 | + | |
| 5550 | + | |
| 5551 | + | |
| 5552 | + | |
| 5553 | + | |
| 5554 | + | |
| 5555 | + | |
| 5556 | + | |
| 5557 | + | |
| 5558 | + | |
| 5559 | + | |
| 5560 | + | |
| 5561 | + | |
| 5562 | + | |
| 5563 | + | |
| 5564 | + | |
| 5565 | + | |
| 5566 | + | |
| 5567 | + | |
| 5568 | + | |
| 5569 | + | |
| 5570 | + | |
| 5571 | + | |
| 5572 | + | |
| 5573 | + | |
0 commit comments