Repository navigation
Commit c4910e0
authored
fix: refuse memory-limited NestedLoopJoin fallback for left-emission joins with a multi-partition probe side (apache#24675)
## Which issue does this PR close?
- Closes apache#22641.
## Rationale for this change
The memory-limited fallback returns wrong rows for join types whose
final emission reads the visited-left bitmap (LEFT, LEFT SEMI, LEFT
ANTI, LEFT MARK) when the probe side has more than one partition. The
fallback rebuilds a per-partition `JoinLeftData` per left chunk with
`probe_threads_counter == 1` and a per-partition bitmap, so every
partition believes it is the last to finish probing and emits its own
unmatched set, from a bitmap that only saw its own right rows. Unmatched
rows are emitted once per partition, and rows matched only in another
partition are emitted as unmatched.
Proof, using this file's own `build_table` / `prepare_join_filter` /
`multi_partitioned_join_collect` fixtures (4 right partitions) with a
100-byte memory limit versus unbounded:
```rust
for join_type in [JoinType::Left, JoinType::LeftAnti] {
// unbounded memory -> correct; 100-byte pool -> memory-limited fallback
let (_, correct, _) = multi_partitioned_join_collect(left, right, &join_type, Some(filter), ample_ctx).await?;
let (_, wrong, _) = multi_partitioned_join_collect(left, right, &join_type, Some(filter), tight_ctx).await?;
}
// Left: correct=19 memory_limited=49
// LeftAnti: correct=1 memory_limited=31
```
The existing gate covers only FULL. This extends it to every
`need_produce_result_in_final` type, so an over-budget build side fails
with `ResourcesExhausted` instead of returning wrong rows. Right-side
emission types (RIGHT, RIGHT SEMI, RIGHT ANTI, RIGHT MARK) keep the
fallback: each partition owns its right rows exclusively, so their
bitmaps are complete per partition. Proper cross-partition coordination
of the left bitmap, which would re-enable the fallback for these types,
is apache#22038.
## What changes are included in this PR?
The `full_join_multi_partition` condition in
`NestedLoopJoinExec::execute` becomes
`need_produce_result_in_final(self.join_type) && right_partition_count >
1`, with the comment updated to describe the failure mode.
`test_overallocation` moves LEFT/LEFT SEMI/LEFT ANTI/LEFT MARK from the
succeed-via-fallback group (which collected but never checked the row
values) into the must-OOM group alongside FULL.
## Are these changes tested?
`test_overallocation` now asserts the `ResourcesExhausted` refusal for
all five gated join types with a multi-partition probe side, and still
asserts fallback success for Inner and the right-emission types. All 42
`nested_loop_join` tests pass; `./dev/rust_lint.sh` is clean.
## Are there any user-facing changes?
Left-family nested loop joins with a multi-partition probe side whose
build side exceeds the memory budget now fail with `ResourcesExhausted`
instead of returning incorrect results. No API changes.1 parent d1fc4b3 commit c4910e0
1 file changed
Lines changed: 136 additions & 35 deletions
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
658 | 658 | | |
659 | 659 | | |
660 | 660 | | |
661 | | - | |
662 | | - | |
663 | | - | |
664 | | - | |
665 | | - | |
666 | | - | |
667 | | - | |
668 | | - | |
669 | | - | |
670 | | - | |
671 | | - | |
672 | | - | |
| 661 | + | |
| 662 | + | |
| 663 | + | |
| 664 | + | |
| 665 | + | |
| 666 | + | |
| 667 | + | |
| 668 | + | |
| 669 | + | |
| 670 | + | |
| 671 | + | |
| 672 | + | |
| 673 | + | |
| 674 | + | |
| 675 | + | |
673 | 676 | | |
674 | | - | |
| 677 | + | |
675 | 678 | | |
676 | 679 | | |
677 | 680 | | |
| |||
4000 | 4003 | | |
4001 | 4004 | | |
4002 | 4005 | | |
| 4006 | + | |
| 4007 | + | |
4003 | 4008 | | |
4004 | 4009 | | |
4005 | | - | |
4006 | | - | |
4007 | | - | |
4008 | | - | |
4009 | 4010 | | |
4010 | 4011 | | |
4011 | 4012 | | |
| |||
4030 | 4031 | | |
4031 | 4032 | | |
4032 | 4033 | | |
4033 | | - | |
4034 | | - | |
4035 | | - | |
4036 | | - | |
4037 | | - | |
4038 | | - | |
4039 | | - | |
4040 | | - | |
4041 | | - | |
4042 | | - | |
4043 | | - | |
4044 | | - | |
4045 | | - | |
4046 | | - | |
4047 | | - | |
4048 | | - | |
4049 | | - | |
4050 | | - | |
| 4034 | + | |
| 4035 | + | |
| 4036 | + | |
| 4037 | + | |
| 4038 | + | |
| 4039 | + | |
| 4040 | + | |
| 4041 | + | |
| 4042 | + | |
| 4043 | + | |
| 4044 | + | |
| 4045 | + | |
| 4046 | + | |
| 4047 | + | |
| 4048 | + | |
| 4049 | + | |
| 4050 | + | |
| 4051 | + | |
| 4052 | + | |
| 4053 | + | |
| 4054 | + | |
| 4055 | + | |
| 4056 | + | |
| 4057 | + | |
| 4058 | + | |
| 4059 | + | |
| 4060 | + | |
| 4061 | + | |
4051 | 4062 | | |
4052 | 4063 | | |
4053 | 4064 | | |
| |||
4160 | 4171 | | |
4161 | 4172 | | |
4162 | 4173 | | |
| 4174 | + | |
| 4175 | + | |
| 4176 | + | |
| 4177 | + | |
| 4178 | + | |
| 4179 | + | |
| 4180 | + | |
| 4181 | + | |
| 4182 | + | |
| 4183 | + | |
| 4184 | + | |
| 4185 | + | |
| 4186 | + | |
| 4187 | + | |
| 4188 | + | |
| 4189 | + | |
| 4190 | + | |
| 4191 | + | |
| 4192 | + | |
| 4193 | + | |
| 4194 | + | |
| 4195 | + | |
| 4196 | + | |
| 4197 | + | |
| 4198 | + | |
| 4199 | + | |
| 4200 | + | |
| 4201 | + | |
| 4202 | + | |
| 4203 | + | |
| 4204 | + | |
| 4205 | + | |
| 4206 | + | |
| 4207 | + | |
| 4208 | + | |
| 4209 | + | |
| 4210 | + | |
| 4211 | + | |
| 4212 | + | |
| 4213 | + | |
| 4214 | + | |
| 4215 | + | |
| 4216 | + | |
| 4217 | + | |
| 4218 | + | |
| 4219 | + | |
| 4220 | + | |
| 4221 | + | |
| 4222 | + | |
| 4223 | + | |
| 4224 | + | |
| 4225 | + | |
| 4226 | + | |
| 4227 | + | |
| 4228 | + | |
| 4229 | + | |
| 4230 | + | |
| 4231 | + | |
| 4232 | + | |
| 4233 | + | |
| 4234 | + | |
| 4235 | + | |
| 4236 | + | |
| 4237 | + | |
| 4238 | + | |
| 4239 | + | |
| 4240 | + | |
| 4241 | + | |
| 4242 | + | |
| 4243 | + | |
| 4244 | + | |
| 4245 | + | |
| 4246 | + | |
| 4247 | + | |
| 4248 | + | |
| 4249 | + | |
| 4250 | + | |
| 4251 | + | |
| 4252 | + | |
| 4253 | + | |
| 4254 | + | |
| 4255 | + | |
| 4256 | + | |
| 4257 | + | |
| 4258 | + | |
| 4259 | + | |
| 4260 | + | |
| 4261 | + | |
| 4262 | + | |
| 4263 | + | |
4163 | 4264 | | |
4164 | 4265 | | |
4165 | 4266 | | |
| |||
0 commit comments