Fastest table sort in the West – Redesigning DuckDB's sort
duckdb.org
duckdb.org
> When a heap block is offloaded to disk, the pointers pointing into it are invalidated. When we load the block back into memory, the pointers will have changed.
> The machine has an Intel(R) Xeon(R) W-2145 CPU @ 3.70GHz, which has 8 cores (up to 16 virtual threads), and 128 GB of RAM, so this time the data fits fully in memory.
However, the M1 + SSD is basically cheating on that trend, because that beats most of my server hardware on both memory latency & ssd. Though that fits with how people will use duckdb for local analytics.
But otherwise this is page-fault hell.
> catalog_sales table is selecting 1 column ... always ordering by cs_quantity and cs_item_sk
The choice of sort keys is a bit odd for a comparison like this, because that tuple has a lot of duplicates. So one of the tricks my code in Tez uses to sort faster is the gallop borrowed from Tim Sort, which skips over the identical key sections when doing the merge-sort to do fewer comparisons over all.
If you sorted on the primary key for catalog_sales, which is (cs_item_sk, cs_order_number), then that is actually used to store data in-order for sort-merge-joins out of disk (against catalog_returns).
And if you get into storage ordering optimizations, you might see a massive difference between ordering them by swapping the order of those columns - if you pull the radix out, then putting the most variable keys in the beginning to skew the bits changing to the first word of the key.
The M1 + SSD performs really well here. We tried to an external sort experiment on the x86 machine, but the SSD is old and only has a write speed of 150MB/s (compared to the MacBook's 3GB/s) and it was incredibly slow. So you definitely need a fast SSD for this.
The columns we chose to sort by are rather arbitrary, but we shuffled the table before running the experiments to make sure there is no ordering left from the generation in there.
I like the merge sort trick you described!
But then, do you have your own cache competing with the OS cache? Or you use O_DIRECT to disable the filesystem cache (at least on Linux)?
[0]: https://news.ycombinator.com/item?id=24669902 [1]: https://news.ycombinator.com/item?id=27878401 [2]: https://news.ycombinator.com/item?id=26825096 [3}: https://news.ycombinator.com/item?id=26588029 [4]: https://news.ycombinator.com/item?id=26476649 [5]: https://news.ycombinator.com/item?id=24534795 [6]: https://news.ycombinator.com/item?id=24534721 [7]: https://news.ycombinator.com/item?id=24338671
I've just come up through the SQL side of analytics and I'm moving into Data Science and I feel like DuckDB is a superpower for people with my background.
Does that help? Happy to answer any other questions!
It's not unusual for happy, unaffiliated users to post enthusiastically, or even evangelise a bit, about the software they love most.
Case in point, I often pop up in TimescaleDB threads to sing it's praise regarding real-world usage, but I'm not affiliated with the TimescaleDB folks in any way.
Is this just when avoiding using in-memory databases in SQLite [0]? It seems like SQLite pretty clearly does support fully in-memory operations.
The use-case for in-memory SQLite is significantly narrower so that may be why it was not considered in this study. But I'd still be curious how an in-memory SQLite db compares to the others trialed here.
Unless I'm getting something totally mixed up.
Furthermore the article explicitely says:
> We will use customer at SF100 and SF300, which fits in memory at every scale factor.
We chose to remove SQLite from the results because it was so much slower. The plots are much less readable when they are stretched out by something that is slower by an order of magnitude
Didn't prevent using pandas which had to rely on dynamic swapping? Or is in-memory sqlite unable to use that much memory?
> We chose to remove SQLite from the results because it was so much slower. The plots are much less readable when they are stretched out by something that is slower by an order of magnitude
So you're using on-disk sqlite because it fits in memory (unlike pandas which also fits in memory) but you're dropping it anyway because it's too slow when it works on-disk?
However, I would not expect much improved performance, because I do not believe that SQLite has a different sorting strategy when running in memory. It would only save some i/o operations, which are very cheap on the macbook anyway.
Either way, would be an interesting experiment.
I think per default it's only 2MiB, increasing it might help. Probably won't beat the other contenders but sqlite has defaults for being a good citizen.
My intuition is that the performance of large sorts (100 millions of rows) are not that important for most analytical workloads compared to the performance of doing scans, group-bys and joins. Top-sorts (ORDER BY X LIMIT N) are much more popular, but most databases use different algorithms for those.
There are order-dependent window functions in there though, which did show a speed up.
I don't understand what this is saying. Is it just using a lot of words to note that as the number of columns increase so do the comparator's cost?
1- std::sort is single threaded
2- std::sort is unable to efficiently sort by multiple columns
I would hope it is quite obvious that is not what I have an issue with.
> 2- std::sort is unable to efficiently sort by multiple columns
It's asserting that with an explanation which is not one, and I'm asking what it is actually saying. "unable to efficiently sort by multiple columns because function call overhead would quickly dominate sorting time." is not an actual explanation.
std::sort is a template in C++. Which means that in most cases, I'd expect std::sort to inline the comparator and not have any function call overhead at all. (And even further: that the optimizer can make optimizations to std::sort + comparator together since they've been inlined)
So you have a good point. Function overhead is in qsort, not in std::sort. The line reads kinda nonsensically to me now that I think of it.