You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
Research performance improvements in N-way merging #2148
Hi @jackwener, currently @richox has two efforts trying to achieve this:
The first one intended to use peek_mut instead of pop in SortPreserveMerging for less comparison but seems suffering performance regression at the moment. #2134
We (Influxdb IOx in general and myself in particular) are very interested in this as well because the SortPreservingMerge is one of the key bottlenecks we see when sorting out data.
Here is what I was thinking about how to proceed:
Create a benchmark for merging (including multi-column keys and variable length (Utf8) keys)
Figure out how to parallelize both the merge (the DuckDB blog has some hints) as well as the creation of RecordBatches from the inputs. I have thought about this but need more time to think through how it would work.
One other thing to throw into the mix would be to optimise sorts of dictionary encoded columns. If the dictionary is sorted, the savings could be significant as you only need to compare the integer keys.
Even if the dictionary isn't sorted it might be faster to sort the dictionary first, and then sort the now sorted keys.
Just an idea as at least in the case of IOx, we will only be sorting on dictionary encoded string columns and not plain columns.
During my school days, I tried to implement an external sorting algorithm using the loser tree, I don't know if this is a good idea because I didn't go to compare. In principle, it will perform better than min heap.
Closing this ticket as I believe it is not tracking anything anymore, feel free to reopen if I am mistaken.
SortPreservingMerge is now implemented as an n-way tournament tree making use of an order-preserving row encoding for multi-column sorts, and specialized cursors for single column sorts. I'm not aware of any major low-hanging fruit to make it run faster
Activity
jackwener commentedon Apr 5, 2022
I'm interested in this. Is there more information/context about it?
yjshen commentedon Apr 5, 2022
Hi @jackwener, currently @richox has two efforts trying to achieve this:
The first one intended to use
peek_mutinstead ofpopin SortPreserveMerging for less comparison but seems suffering performance regression at the moment. #2134The second attempt tries to use
BTreeinstead of the currentMinHeapand is still a work in progress. https://github.com/richox/arrow-datafusion/tree/sort_memory_2_peekmut_popPerhaps you guys could discuss this to see if it's possible to come up with a faster solution?
yjshen commentedon Apr 5, 2022
I created this issue from an item @alamb has listed in the umbrella PR. Maybe @alamb can also share some insights here.
alamb commentedon Apr 5, 2022
alamb commentedon Apr 5, 2022
Thoughts on N-way merging:
We (Influxdb IOx in general and myself in particular) are very interested in this as well because the
SortPreservingMergeis one of the key bottlenecks we see when sorting out data.Here is what I was thinking about how to proceed:
Areas for investigation / things to spike out:
[u8]rather than array accesscc @tustvold
tustvold commentedon Apr 5, 2022
One other thing to throw into the mix would be to optimise sorts of dictionary encoded columns. If the dictionary is sorted, the savings could be significant as you only need to compare the integer keys.
Even if the dictionary isn't sorted it might be faster to sort the dictionary first, and then sort the now sorted keys.
Just an idea as at least in the case of IOx, we will only be sorting on dictionary encoded string columns and not plain columns.
yjshen commentedon Apr 6, 2022
I filed an issue for this #2150
jackwener commentedon Apr 6, 2022
During my school days, I tried to implement an external sorting algorithm using the
loser tree, I don't know if this is a good idea because I didn't go to compare. In principle, it will perform better than min heap.tustvold commentedon Apr 29, 2023
Closing this ticket as I believe it is not tracking anything anymore, feel free to reopen if I am mistaken.
SortPreservingMerge is now implemented as an n-way tournament tree making use of an order-preserving row encoding for multi-column sorts, and specialized cursors for single column sorts. I'm not aware of any major low-hanging fruit to make it run faster