You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "NoahKusaba (via GitHub)" <gi...@apache.org> on 2026/09/01 15:54:05 UTC

[PR] feat(core): order shuffle reads round-robin across producers, staggered per consumer [datafusion-ballista]

NoahKusaba opened a new pull request, #2406:
URL: https://github.com/apache/datafusion-ballista/pull/2406

   # Which issue does this PR close?
   
   Closes #2403 
   
    # Rationale for this change
   
   Look at the linked issue to understand the problem being solved.
   
   Performance improvements + AI Benchmarking:
   
   **Fetch ordering is cheaper than what it replaces.** The old path sorted all M
   blocks and then ran an O(M) shuffle over them. `interleave_by_executor` sorts
   only the N producers. Per `execute()` call, on the synchronous setup path
   before any fetch is issued:
   
   | M | N | old (sort + shuffle) | new (round-robin) |
   |---|---|---|---|
   | 1000 | 20 | 837 us | 285 us |
   | 5000 | 50 | 2.59 ms | 1.45 ms |
   | 20000 | 200 | 16.96 ms | 6.11 ms |
   
   **Draining off the driver.** 24 blocks of ZSTD-compressed Arrow IPC, 337 KiB
   per block on the wire, decoded in `poll_next` as `BlockDataStream` does, driven
   from a single task through `buffer_unordered`:
   
   | drain | wall time (4 runs) |
   |---|---|
   | inline, in the driver | 58.8, 61.0, 61.5, 63.2 ms |
   | `collect_off_task` | 11.5, 12.5, 14.4, 19.1 ms |
   
   Inline, all 24 decodes serialize onto one worker while the rest of the runtime
   idles. This is why the single driver issues requests but does not drain them.
   
   **Help wanted: cluster numbers.** The ordering benefit itself is unmeasured. I
   do not have the hardware, and it cannot be reproduced on one machine: a
   single-executor standalone cluster reads every block locally so the remote path
   never runs, and loopback has no contention to avoid. Everything above is CPU
   cost, not the producer spread this PR exists to improve.
   
   If you have a multi-executor cluster, the numbers I would find most useful,
   against `main` on a shuffle-heavy query such as TPC-H q4 or q18:
   
   - `ShuffleReaderExec`'s `permit_wait_time` and `fetch_time` metrics, which is
     where converging on one producer shows up
   - reduce-stage wall time, especially its spread across tasks: the change is
     aimed at tail latency more than the mean
   - whether more executors widens or narrows the gap, since N is what the
     round-robin has to spread across
   
   A confirmation that nothing regresses would be just as valuable as a win.
   
   
   # What changes are included in this PR?
   
   **Ordering.** `interleave_by_executor` replaces the sort-then-shuffle. Blocks
   are round-robined across the executors that produced them, starting at the
   producer the consumer's own index selects. A skewed producer keeps its turn
   each round, then drains alone.
   
   **Peer identity.** New `ShuffleReaderExecNode.output_partition_indices`
   (proto field 8), stamped by `restrict_plan_to_partitions` alongside the slice
   it selects. Absent on the wire decodes to the identity mapping, so a plan from
   an older encoder is unaffected; a stamp that is not parallel to `partition` is
   a decode error rather than a silent fallback.
   
   **One fetch driver instead of a task per block.** Ordering only matters if it
   survives to the wire. With a task per block, M tasks race to acquire `req_sem`
   and the admitted subset is up to the runtime, so the round-robin is computed
   and then discarded. A single driver over `buffer_unordered` initiates in list
   order; completion stays unordered.
   
   **Decode off the driver.** IPC decode and decompression are CPU and hold the
   polling thread, so `collect_off_task` drains each stream on its own task. The
   request is still issued from the driver, so fetch order is unaffected.
   
   **Separate local and remote lanes.** A queued local result pins an open fd and
   a 256 KB buffer, so locals get a depth-1 lane; remotes mirror `req_sem`. The
   two are merged with `select`, so locals arrive interleaved rather than
   serialized behind remotes.
   
   `permit_wait_time` now times from when a block becomes eligible rather than
   from when the buffer constructs its future, keeping the metric comparable with
   the previous task-per-block version. 
   
   `itertools` is no longer used by `ballista-core` and can be dropped.
   
   # Tests
   
   Ordering: `interleave_visits_every_executor_once_per_round`,
   `interleave_drains_a_skewed_producer_last`, `interleave_preserves_the_fetch_set`,
   `producer_order_is_independent_of_input_order`, `interleave_handles_no_locations`,
   `stamped_peers_round_robin_across_producers`,
   `rotation_comes_from_the_stamp_not_the_local_index`.
   
   Reaching the wire: `remote_fetches_reach_the_wire_in_list_order` records fetch
   order through a stub client pool, on both sides of the governor window.
   
   Concurrency: `decode_does_not_run_on_the_callers_task` fails unless the drains
   run on threads of their own; `local_reads_do_not_run_ahead_of_the_consumer`
   counts open descriptors under the work dir.
   
   Stamping: `restriction_stamps_the_global_output_partition_indices`,
   `stamp_stays_parallel_when_an_index_is_out_of_range`,
   `broadcast_reader_under_a_collected_join_is_still_stamped`, plus codec
   roundtrips for the stamped, absent, mismatched, and broadcast cases.
   
   Every test above was checked by mutation: reverting the behavior it covers
   fails that test and no other.
   
   # Are there any user-facing changes?
   No
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] feat(core): order shuffle reads round-robin across producers, staggered per consumer [datafusion-ballista]

Posted by "NoahKusaba (via GitHub)" <gi...@apache.org>.
NoahKusaba commented on PR #2406:
URL: https://github.com/apache/datafusion-ballista/pull/2406#issuecomment-5516583926

   > **Cluster numbers, as requested in the PR description.**
   > 
   > **Setup.** 4 × `r6i.24xlarge` in EKS, 32 executor pods at 8 vCPU / 64 GiB each (`--vcores=8`, `--memory-pool-size=48103633715`, 1000 GiB gp3 shuffle volume), TPC-H SF1000 Parquet+ZSTD on S3, `target_partitions=256`, `max_partitions_per_task=1`, AQE on — the shape in `docs/source/contributors-guide/benchmarking.md`. Baseline is `b0dfd259`, this PR's merge base; treatment is `7684d651`. Same client image both arms.
   > 
   > **Method.** Counterbalanced ABBA (base → pr → pr → base), because a first sequential base→pr pair showed a gap that partly disappeared once the order was balanced. 5 iterations per query per run, first dropped as cold, so n = 8 warm iterations per arm.
   > query 	metric 	base 	pr 	Δ 	Welch t
   > q4 	wall (s) 	10.32 ± 0.97 	10.68 ± 0.99 	+3.5% 	0.70
   > q4 	`fetch_time` (s) 	6,773 ± 578 	8,172 ± 1,571 	+20.7% 	2.36
   > q4 	`permit_wait_time` (s) 	43,219 ± 4,523 	46,082 ± 12,478 	+6.6% 	0.61
   > q18 	wall (s) 	38.09 ± 0.76 	38.69 ± 1.09 	+1.6% 	1.19
   > q18 	`fetch_time` (s) 	59,751 ± 3,207 	63,844 ± 3,248 	+6.9% 	2.54
   > q18 	`permit_wait_time` (s) 	527,109 ± 21,846 	579,635 ± 29,380 	+10.0% 	4.06
   > 
   > Metric columns are stage sums over 256 partitions.
   > 
   > **Wall clock is indistinguishable in either direction** (t = 0.70, 1.19). `fetch_time` is higher on both queries at t > 2.3.
   > 
   > **`permit_wait_time` is not strictly comparable across the arms.** This PR starts the timer at a single `queued_at` taken before the loop, where main starts each block's timer when its spawned task first runs, so blocks now accumulate wait from an earlier instant. Some of the +10% is definitional. `fetch_time` and wall clock keep their definitions.
   > 
   > **Tail spread** — per-task `exec_duration` across the 256 tasks of the shuffle-reading stage, which is what the change targets. q4: `max/median` 3.53 → 3.74, `cv` 0.372 → 0.376. q18: `max/median` 1.13 → 1.16, `cv` 0.069 → 0.073. No tightening. q18's baseline is already `cv = 0.069` across 256 tasks, so there is little imbalance available to remove at this shape.
   > 
   > **Scope.** One shape only: 32 producers, 256 consumers. The PR asks whether more executors widens or narrows the gap; that is untested here.
   > 
   > 🤖 Run and written by [Claude Code](https://claude.com/claude-code) on @avantgardnerio's cluster. Raw logs and per-stage metric dumps available on request.
   
   Thank you for your time, I suspected this might not amount to much, but I got a bit caught up imagining what an optimal implementation would be when I saw the sort -> shuffle. 
   
   I'll just make a new PR to delete the useless sort instead and leave it alone.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] feat(core): order shuffle reads round-robin across producers, staggered per consumer [datafusion-ballista]

Posted by "avantgardnerio (via GitHub)" <gi...@apache.org>.
avantgardnerio commented on PR #2406:
URL: https://github.com/apache/datafusion-ballista/pull/2406#issuecomment-5516296214

   **Cluster numbers, as requested in the PR description.**
   
   **Setup.** 4 × `r6i.24xlarge` in EKS, 32 executor pods at 8 vCPU / 64 GiB each (`--vcores=8`, `--memory-pool-size=48103633715`, 1000 GiB gp3 shuffle volume), TPC-H SF1000 Parquet+ZSTD on S3, `target_partitions=256`, `max_partitions_per_task=1`, AQE on — the shape in `docs/source/contributors-guide/benchmarking.md`. Baseline is `b0dfd259`, this PR's merge base; treatment is `7684d651`. Same client image both arms.
   
   **Method.** Counterbalanced ABBA (base → pr → pr → base), because a first sequential base→pr pair showed a gap that partly disappeared once the order was balanced. 5 iterations per query per run, first dropped as cold, so n = 8 warm iterations per arm.
   
   | query | metric | base | pr | Δ | Welch t |
   |---|---|---:|---:|---:|---:|
   | q4 | wall (s) | 10.32 ± 0.97 | 10.68 ± 0.99 | +3.5% | 0.70 |
   | q4 | `fetch_time` (s) | 6,773 ± 578 | 8,172 ± 1,571 | +20.7% | 2.36 |
   | q4 | `permit_wait_time` (s) | 43,219 ± 4,523 | 46,082 ± 12,478 | +6.6% | 0.61 |
   | q18 | wall (s) | 38.09 ± 0.76 | 38.69 ± 1.09 | +1.6% | 1.19 |
   | q18 | `fetch_time` (s) | 59,751 ± 3,207 | 63,844 ± 3,248 | +6.9% | 2.54 |
   | q18 | `permit_wait_time` (s) | 527,109 ± 21,846 | 579,635 ± 29,380 | +10.0% | 4.06 |
   
   Metric columns are stage sums over 256 partitions.
   
   **Wall clock is indistinguishable in either direction** (t = 0.70, 1.19). `fetch_time` is higher on both queries at t > 2.3.
   
   **`permit_wait_time` is not strictly comparable across the arms.** This PR starts the timer at a single `queued_at` taken before the loop, where main starts each block's timer when its spawned task first runs, so blocks now accumulate wait from an earlier instant. Some of the +10% is definitional. `fetch_time` and wall clock keep their definitions.
   
   **Tail spread** — per-task `exec_duration` across the 256 tasks of the shuffle-reading stage, which is what the change targets. q4: `max/median` 3.53 → 3.74, `cv` 0.372 → 0.376. q18: `max/median` 1.13 → 1.16, `cv` 0.069 → 0.073. No tightening. q18's baseline is already `cv = 0.069` across 256 tasks, so there is little imbalance available to remove at this shape.
   
   **Scope.** One shape only: 32 producers, 256 consumers. The PR asks whether more executors widens or narrows the gap; that is untested here.
   
   ---
   🤖 Run and written by [Claude Code](https://claude.com/claude-code) on @avantgardnerio's cluster. Raw logs and per-stage metric dumps available on request.
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] feat(core): order shuffle reads round-robin across producers, staggered per consumer [datafusion-ballista]

Posted by "avantgardnerio (via GitHub)" <gi...@apache.org>.
avantgardnerio commented on PR #2406:
URL: https://github.com/apache/datafusion-ballista/pull/2406#issuecomment-5516862851

   Thanks for trying it out! I'm sorry this one didn't pan out, but the next one will. Happy to throw some resources at it.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] feat(core): order shuffle reads round-robin across producers, staggered per consumer [datafusion-ballista]

Posted by "NoahKusaba (via GitHub)" <gi...@apache.org>.
NoahKusaba closed pull request #2406: feat(core): order shuffle reads round-robin across producers, staggered per consumer
URL: https://github.com/apache/datafusion-ballista/pull/2406


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org