Repository navigation
Commit f800da5
authored
perf: emit unmatched build rows in batch_size chunks in HashJoinExec (apache#25028)
## Which issue does this PR close?
- Related to apache#24768 (bounded-memory hash join) and apache#18942 (hash join
operator optimizations); no dedicated issue.
## Rationale for this change
For join types that emit build-side rows after the probe side is
exhausted (`Left`, `Full`, `LeftAnti`, `LeftSemi`, `LeftMark`),
`HashJoinExec` computed the final indices over the *whole* build side
and materialized them as **one** `RecordBatch` before handing it to the
output coalescer.
That batch is not bounded by `batch_size`, and it is not covered by the
memory reservation. Worse, `LimitedBatchCoalescer` configures arrow's
`BatchCoalescer` with `biggest_coalesce_batch_size = batch_size / 2`,
which passes any larger batch through untouched. So a `LEFT ANTI` join
over a 10M-row build side with few matches emitted a single ~10M-row
batch downstream, regardless of `datafusion.execution.batch_size`.
`NestedLoopJoinExec` already emits its unmatched build rows in
`batch_size` chunks; this PR brings `HashJoinExec` in line.
## What changes are included in this PR?
- `HashJoinStream` gets a new state, `EmitUnmatchedBuildRows`, entered
from `ExhaustedProbeSide` by the last probe partition. It holds a
`BooleanBuffer` snapshot of the visited bitmap (taken once, after every
partition reported completion, so the lock is not held while emitting)
and a cursor.
- `next_final_indices_chunk` scans the snapshot from the cursor and
returns at most `batch_size` final indices per call (`LeftMark` emits
every row, so its chunks are plain ranges). Null-aware
`LeftAnti`/`LeftMark` post-processing and `fetch` handling are unchanged
and now run per chunk.
- `input_batches` is still bumped once for the final phase and
`input_rows` once per chunk, so metric values are identical to before.
- `get_final_indices_from_bit_map` /
`get_final_indices_from_shared_bitmap` in `joins/utils.rs` had no other
callers and are removed.
- New benchmark cases in `hash_join_semi_anti.rs` with a 1M-row build
side and a 100K-row probe side (`left_semi_build1m_h10`,
`left_anti_build1m_h10`, `left_build1m_h10`).
Benchmark (this branch vs. `main`, Apple Silicon, `cargo bench --bench
hash_join_semi_anti -- build1m`):
| case | main | this PR | change |
|---|---|---|---|
| left_semi_build1m_h10 | 2.05 ms | 1.97 ms | -4% |
| left_anti_build1m_h10 | 6.21 ms | 4.75 ms | -24% |
| left_build1m_h10 | 7.37 ms | 6.79 ms | -8% |
Peak RSS of the `left_anti_build1m_h10` bench binary: ~369 MB on `main`
vs ~160 MB on this branch (`/usr/bin/time -l`, 1M build rows, 900K
unmatched).
## Are these changes tested?
- New `join_emits_final_build_rows_in_batch_size_chunks` test
(Left/Full/LeftAnti/LeftSemi/LeftMark × batch sizes 1/7/8192 ×
perfect-hash-join on/off) asserts the output rows and that every output
batch respects `batch_size`. On `main` 14 of its 30 cases fail the
batch-size assertion.
- New `join_fetch_stops_final_build_rows_mid_chunk` test checks a
`fetch` that is reached in the middle of the final rows.
- Existing hash join unit tests (493), join sqllogictests (`joins`,
`join_limit_pushdown`, `join_disable_repartition_joins`, `subquery`),
and the core join fuzz tests pass.
## Are there any user-facing changes?
No result changes. Output batches of the affected join types are now
bounded by `batch_size` instead of arriving as one batch holding every
unmatched build row.1 parent 2a42140 commit f800da5
4 files changed
Lines changed: 374 additions & 77 deletions
File tree
- datafusion/physical-plan
- benches
- src/joins
- hash_join
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
380 | 380 | | |
381 | 381 | | |
382 | 382 | | |
| 383 | + | |
| 384 | + | |
| 385 | + | |
| 386 | + | |
| 387 | + | |
| 388 | + | |
| 389 | + | |
| 390 | + | |
| 391 | + | |
| 392 | + | |
| 393 | + | |
| 394 | + | |
| 395 | + | |
| 396 | + | |
| 397 | + | |
| 398 | + | |
| 399 | + | |
| 400 | + | |
| 401 | + | |
| 402 | + | |
| 403 | + | |
| 404 | + | |
| 405 | + | |
| 406 | + | |
| 407 | + | |
| 408 | + | |
| 409 | + | |
| 410 | + | |
| 411 | + | |
| 412 | + | |
| 413 | + | |
| 414 | + | |
| 415 | + | |
| 416 | + | |
| 417 | + | |
| 418 | + | |
| 419 | + | |
| 420 | + | |
| 421 | + | |
| 422 | + | |
| 423 | + | |
| 424 | + | |
| 425 | + | |
| 426 | + | |
| 427 | + | |
| 428 | + | |
| 429 | + | |
| 430 | + | |
| 431 | + | |
| 432 | + | |
| 433 | + | |
| 434 | + | |
| 435 | + | |
| 436 | + | |
| 437 | + | |
| 438 | + | |
| 439 | + | |
| 440 | + | |
| 441 | + | |
383 | 442 | | |
384 | 443 | | |
385 | 444 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
3041 | 3041 | | |
3042 | 3042 | | |
3043 | 3043 | | |
3044 | | - | |
| 3044 | + | |
3045 | 3045 | | |
3046 | 3046 | | |
3047 | 3047 | | |
3048 | | - | |
| 3048 | + | |
3049 | 3049 | | |
3050 | 3050 | | |
3051 | 3051 | | |
| |||
4127 | 4127 | | |
4128 | 4128 | | |
4129 | 4129 | | |
| 4130 | + | |
| 4131 | + | |
| 4132 | + | |
| 4133 | + | |
| 4134 | + | |
| 4135 | + | |
| 4136 | + | |
| 4137 | + | |
| 4138 | + | |
| 4139 | + | |
| 4140 | + | |
| 4141 | + | |
| 4142 | + | |
| 4143 | + | |
| 4144 | + | |
| 4145 | + | |
| 4146 | + | |
| 4147 | + | |
| 4148 | + | |
| 4149 | + | |
| 4150 | + | |
| 4151 | + | |
| 4152 | + | |
| 4153 | + | |
| 4154 | + | |
| 4155 | + | |
| 4156 | + | |
| 4157 | + | |
| 4158 | + | |
| 4159 | + | |
| 4160 | + | |
| 4161 | + | |
| 4162 | + | |
| 4163 | + | |
| 4164 | + | |
| 4165 | + | |
| 4166 | + | |
| 4167 | + | |
| 4168 | + | |
| 4169 | + | |
| 4170 | + | |
| 4171 | + | |
| 4172 | + | |
| 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 | + | |
| 4264 | + | |
| 4265 | + | |
| 4266 | + | |
| 4267 | + | |
| 4268 | + | |
| 4269 | + | |
| 4270 | + | |
| 4271 | + | |
| 4272 | + | |
| 4273 | + | |
| 4274 | + | |
| 4275 | + | |
| 4276 | + | |
| 4277 | + | |
| 4278 | + | |
| 4279 | + | |
| 4280 | + | |
| 4281 | + | |
| 4282 | + | |
| 4283 | + | |
| 4284 | + | |
| 4285 | + | |
| 4286 | + | |
| 4287 | + | |
4130 | 4288 | | |
4131 | 4289 | | |
4132 | 4290 | | |
| |||
0 commit comments