You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "zhuqi-lucas (via GitHub)" <gi...@apache.org> on 2025/02/16 06:53:43 UTC
[I] A complete solution for stable and safe sort with spill [datafusion]
zhuqi-lucas opened a new issue, #14692:
URL: https://github.com/apache/datafusion/issues/14692
### Is your feature request related to a problem or challenge?
This is a follow-up for https://github.com/apache/datafusion/pull/14644:
See details in https://github.com/apache/datafusion/pull/14644#discussion_r1957155614 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 think 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
_No response_
### Describe alternatives you've considered
_No response_
### Additional context
_No response_
--
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.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: [I] A complete solution for stable and safe sort with spill [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #14692:
URL: https://github.com/apache/datafusion/issues/14692#issuecomment-2779016719
There is a bunch of work ongoing in this area, most of which is linked from
- https://github.com/apache/datafusion/issues/15271
--
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: [I] A complete solution for stable and safe sort with spill [datafusion]
Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on issue #14692:
URL: https://github.com/apache/datafusion/issues/14692#issuecomment-2702697221
This is a reproducer for an external sort query failure under a very low memory limit https://github.com/apache/datafusion/issues/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.
--
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: [I] A complete solution for stable and safe sort with spill [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #14692:
URL: https://github.com/apache/datafusion/issues/14692#issuecomment-2668835909
Thank you for filing this @zhuqi-lucas . I have also added it to our list here
- https://github.com/apache/datafusion/issues/14077
--
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: [I] A complete solution for stable and safe sort with spill [datafusion]
Posted by "qstommyshu (via GitHub)" <gi...@apache.org>.
qstommyshu commented on issue #14692:
URL: https://github.com/apache/datafusion/issues/14692#issuecomment-2783589078
Got it @2010YOUY01 ,
Since you are already working on this issue, I won't do it then. I'll try my best to provides some feedbacks (if there is any).
--
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: [I] A complete solution for stable and safe sort with spill [datafusion]
Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on issue #14692:
URL: https://github.com/apache/datafusion/issues/14692#issuecomment-2781990793
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.
--
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: [I] A complete solution for stable and safe sort with spill [datafusion]
Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 closed issue #14692: A complete solution for stable and safe sort with spill
URL: https://github.com/apache/datafusion/issues/14692
--
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: [I] A complete solution for stable and safe sort with spill [datafusion]
Posted by "qstommyshu (via GitHub)" <gi...@apache.org>.
qstommyshu commented on issue #14692:
URL: https://github.com/apache/datafusion/issues/14692#issuecomment-2778461103
> 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 think about it first, and start working on the code once I can reproduce the error and have a general idea of what the solution is.
--
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: [I] A complete solution for stable and safe sort with spill [datafusion]
Posted by "qstommyshu (via GitHub)" <gi...@apache.org>.
qstommyshu commented on issue #14692:
URL: https://github.com/apache/datafusion/issues/14692#issuecomment-2777376142
take
--
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: [I] A complete solution for stable and safe sort with spill [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #14692:
URL: https://github.com/apache/datafusion/issues/14692#issuecomment-2729485594
I started collecting sort larger than RAM related things here:
- https://github.com/apache/datafusion/issues/15271
--
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: [I] A complete solution for stable and safe sort with spill [datafusion]
Posted by "qstommyshu (via GitHub)" <gi...@apache.org>.
qstommyshu commented on issue #14692:
URL: https://github.com/apache/datafusion/issues/14692#issuecomment-2771022723
> This is a reproducer for an external sort query failure under a very low memory limit [#15028](https://github.com/apache/datafusion/issues/15028) Discord discussion:[discord.com/channels/885562378132000778/1346514274734051412](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.
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 can help, I've implemented multi-pass external sort algorithm before in python (just for fun). I hope it wouldn't be too hard to extend from current one-pass algorithm.
--
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: [I] A complete solution for stable and safe sort with spill [datafusion]
Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on issue #14692:
URL: https://github.com/apache/datafusion/issues/14692#issuecomment-2771604094
> > This is a reproducer for an external sort query failure under a very low memory limit [#15028](https://github.com/apache/datafusion/issues/15028) Discord discussion:[discord.com/channels/885562378132000778/1346514274734051412](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.
>
> 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.
--
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: [I] A complete solution for stable and safe sort with spill [datafusion]
Posted by "qstommyshu (via GitHub)" <gi...@apache.org>.
qstommyshu commented on issue #14692:
URL: https://github.com/apache/datafusion/issues/14692#issuecomment-2777376035
This issue looks interesting to me. I'll try to work on 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: [I] A complete solution for stable and safe sort with spill [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #14692:
URL: https://github.com/apache/datafusion/issues/14692#issuecomment-2778254506
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
--
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