A complete solution for stable and safe sort with spill

[zhuqi-lucas]

Is your feature request related to a problem or challenge?

This is a follow-up for #14644:

See details in #14644 (comment) cc @alamb @Kontinuation

We need a complete solution about stable sort with spill, several issues until now:

1. Ensuring we can always spill data (now spilling will sometimes fail if we run out of memory to sort the batches in)
2. Ensuring that we can always merge the data that was spilled, even if it had a really wide fanout (like 1000 of spill files)

The problem 1 could be solved by potentially spilling unsorted batches (and then sorting them separately). This would be less efficient (read/write some tuples twice but would work.

Problem 2 could use the multi-pass merge:

We can implement a more complicated multi-stage merging phase which merges a small portion of streams each time, and perform multiple rounds of merges to produce the final merged stream.

Describe the solution you'd like

The problem 1 could be solved by potentially spilling unsorted batches (and then sorting them separately). This would be less efficient (read/write some tuples twice but would work.

Problem 2 could use the multi-pass merge:

We can implement a more complicated multi-stage merging phase which merges a small portion of streams each time, and perform multiple rounds of merges to produce the final merged stream.

Describe alternatives you've considered

No response

Additional context

No response

[alamb]

Thank you for filing this @zhuqi-lucas . I have also added it to our list here

• [Epic] A collection of items related to processing larger than memory datasets (via spilling, externalized algorithm, etc) #14077

[2010YOUY01]

This is a reproducer for an external sort query failure under a very low memory limit #15028
Discord discussion:https://discord.com/channels/885562378132000778/1346514274734051412
I think this reproducer is only possible to get executed after implementing multi-pass merge, if wd don't set the memory limit higher.

[alamb]

I started collecting sort larger than RAM related things here:

• [EPIC] A collection of tickets for improving sorting larger than memory datasets / spilling sorts #15271

[qstommyshu]

This is a reproducer for an external sort query failure under a very low memory limit #15028 Discord discussion:discord.com/channels/885562378132000778/1346514274734051412 I think this reproducer is only possible to get executed after implementing multi-pass merge, if wd don't set the memory limit higher.

Can some provide a instruction for me to reproduce it and let me know which part of the code has the external sort algorithm? I can take a look at it.

I probably can help if implementing a multi-pass external sort is the need, I've implemented multi-pass external sort before in python (just for fun). I hope it wouldn't be too hard to extend from current one-pass algorithm.

[2010YOUY01]

This is a reproducer for an external sort query failure under a very low memory limit #15028 Discord discussion:discord.com/channels/885562378132000778/1346514274734051412 I think this reproducer is only possible to get executed after implementing multi-pass merge, if wd don't set the memory limit higher.

Can some provide a instruction for me to reproduce it and let me know which part of the code has the external sort algorithm? I can take a look at it.

If there is any trouble reproducing, you can ask in the bug-tracking issue.

I probably can help if implementing a multi-pass external sort is the need, I've implemented multi-pass external sort before in python (just for fun). I hope it wouldn't be too hard to extend from current one-pass algorithm.

Thank you. Just a heads-up, I think this issue is a bit tricky, we have to also look into the performance after implementing the algorithm.

[qstommyshu]

This issue looks interesting to me. I'll try to work on it!

[qstommyshu]

take

[alamb]

Thanks @qstommyshu ! I think @2010YOUY01 has been working on this one most recently, so I would recommend checking in with them before coding too mich

[qstommyshu]

Thanks @qstommyshu ! I think @2010YOUY01 has been working on this one most recently, so I would recommend checking in with them before coding too mich

Sounds good, no problem. I didn't see another assignee for this issue, so I decided to take it . I won't start coding immediately, I'll check with @2010YOUY01 and think about the problem first, then start working on the code once I can reproduce the error and have a general idea of what the solution is.

[alamb]

There is a bunch of work ongoing in this area, most of which is linked from

• [EPIC] A collection of tickets for improving sorting larger than memory datasets / spilling sorts #15271

[2010YOUY01]

This issue is receiving a lot of attention (tbh, users complaining the feature is not working), so I did a POC. Feel free to chime in @qstommyshu For major features, it’s always great to see alternative approaches to refine the work.

[qstommyshu]

Got it @2010YOUY01 ,

Since you are already working on this issue, I won't take it from you then. I'll try my best to provides some feedbacks to your PR (if there is any).