[EPIC] Experiment with some different shuffle implementations

[andygrove]

What is the problem the feature request solves?

Following on from the refactors to move shuffle code into a separate crate in #3749 and #3772, and the new standalone shuffle benchmark binary in #3752, I propose that we start evaluating some different shuffle approaches to better understand the trade offs in terms of throughput and memory usage of different approaches.

This is a very open-ended epic. There are some ideas that I am planning on experimenting with, such as moving away from the current interleave batches approach, which keeps batches buffered for a long time, and moving to a more immediate scatter approach that removes the need to buffer the input batches for such a long time. I expect other contributors may also have ideas that they would like to explore.

There is a already a trait for the shuffle partition-and-write operation, so it should be trivial to support different implementations behind a config for testing and evaluation, and allow the standalone benchmark to compare performance characteristics across implementations.

What issues would this help with?

• Current shuffle format has too much overhead with default batch size #3882
• Optimize native shuffle to write schema once per output partition instead of once per batch #2928
• Shuffle memory pool accounting: peak RSS significantly exceeds configured memory limit #3821

Describe the potential solution

Here some experimental PRs:

• feat: Add immediate mode option for native shuffle #3845
• feat: reduce shuffle format overhead with one IPC stream per partition [experimental] #3883
• feat: replace custom shuffle block format with Arrow IPC streams #3911
• feat: Add batch spill limit to improve shuffle writer throughput [experimental] #3941

Additional context

No response

[andygrove]

I created a Google document to start tracking some of the experiments.

https://docs.google.com/document/d/1u6pBb9Gs1P95FfnC2X_O8LFk6RYR7vu_ZleAGGRM57o/edit?usp=sharing