NoahKusaba opened a new pull request, #2414:
URL: https://github.com/apache/datafusion-ballista/pull/2414
The sort grouped partition locations by executor and interleaved them, then
the next line shuffled the result, discarding the ordering entirely. Take the
locations directly and keep the shuffle. `sorted_by` was ballista-core's only
`itertools` use, so the dependency goes with it.
# Which issue does this PR close?
Closes #2403
# Rationale for this change
The sort is uniformly random (Durstenfeld's Fisher-Yates) , so sorting
before the random shuffle does nothing.
AI Verification:
Checked empirically as well, reimplementing both pipelines over 4 blocks (24
permutations) at 480,000 trials each and counting how often each permutation
came out:
┌────────────────────────┬────────────────┬──────────────┐
│ input │ pipeline │ chi² (df=23) │
├────────────────────────┼────────────────┼──────────────┤
│ 2 executors × 2 blocks │ sort + shuffle │ 23.07 │
├────────────────────────┼────────────────┼──────────────┤
│ 2 executors × 2 blocks │ shuffle only │ 12.08 │
├────────────────────────┼────────────────┼──────────────┤
│ skewed, 3 blocks + 1 │ sort + shuffle │ 18.68 │
├────────────────────────┼────────────────┼──────────────┤
│ skewed, 3 blocks + 1 │ shuffle only │ 24.90 │
└────────────────────────┴────────────────┴──────────────┘
The 5% critical value is 35.17, so all four are consistent with uniform.
Every
trial also asserted the output is a permutation of the input, so the set of
blocks fetched is preserved. The skewed shape is included because that is
where
the interleave and the raw list order differ most.
# What changes are included in this PR?
- Delete inert sort for partition_locations in shuffle reader.
- Delete now unused itertools crate.
# 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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
