Interactive data analysis is often conveniently done on personal computers that have limited memory. Current analytical data management systems rely almost exclusively on main memory for computation. When the data size exceeds the memory limit, many systems cannot complete queries or resort to an external execution strategy that assumes a high I/O cost. These strategies are often much slower than the in-memory strategy. However, I/O cost has gone down: Most modern laptops have fast NVMe storage. We believe that the diference between in-memory and external does not have to be this big. We implement a parallel external sorting operator in DuckDB that demonstrates this. Experimental results with our implementation show that even when the data size far exceeds the memory size, the performance loss is negligible. From this result, we conclude that it is possible to have a graceful degradation from in-memory to external sorting.
It is not uncommon for database systems to have hundreds or even thousands of gigabytes of RAM at their disposal. High-performance systems such as HyPer [1], and ClickHouse [2] fully utilize the available memory and perform much better on analytical workloads than their traditional disk-based counterparts. Because these systems usually run on machines with such large memory capacities, the assumption is often that the workload ifts in memory.
capacity, their physical design has limited space. Therefore they typically have only 16GB of memory. Laptops are often used in interactive data analysis, with tools like Pandas [3] and dplyr [4], showing that there is a need for analytical data management technology that runs on a laptop. However, these tools operate only in memory. As a result, users cannot process datasets that are slightly larger than memory, on their own machine. have long solved the problem of processing larger-thanmemory datasets. These systems are generally much slower than in-memory systems on analytical workloads. When a user wants to process a larger-than-memory dataset using an in-memory system, usually one of two things happens 1) The system throws an error stating it is out of memory, 2) The system switches to an external strategy that is much less eficient than the in-memory strategy, which results in a slow execution time, even when, for example, the input is only 10% larger than 0x0003 0x0005 intA 37 37 42
Row Layout stringA 0x0001 0x0003 0x0005 intB 42 66 66 stringB 0x0002 0x0004 0x0006
Row Heap radix CWI
pointer swizzling DuckDBLabs goose memory. Fast queries may become slow or run into an error when a table grows in size, creating a frustrating experience for users.
ators such that they optimally use the amount of available memory and only write data to disk when this is necessary. I/O quickly becomes the bottleneck on machines with low-bandwidth storage devices. However, most modern laptops have nVME storage with high write
erator in DuckDB [5] that demonstrates this. Our implementation seamlessly transitions from in-memory to external sorting by storing data in bufer-managed blocks that are ofloaded to disk using a least-recently-used queue, similar to LeanStore [6].
sible by DuckDB’s unified internal row layout, shown in Figure 1, which can be spilled to disk using pointer swizzling [7].
systems using an improvised relational sorting benchmark on two tables from TPC-DS [8]. Our implementation achieves excellent performance when data fits in memory and shows a graceful degradation in performance as we go over the limit of available memory.
Sorting is one of the most well studied problems in computing science. Research in this area forms the basis of sorting in database systems but focuses mostly on sorting large arrays or key/value pairs. Sorting is more complex for relational data as many diferent types need to be supported, as well as NULL values. There can also be Figure 2: Binary string encoding. The original data in (a) multiple order clauses. Besides sorting the order clause is represented as (b) on a little-endian machine. It is en(key) columns, all other selected (payload) columns need coded as (c) when ordered for a query with order clauses to be re-ordered as well. c_birth_country DESC, c_birth_year ASC. Descending order
In 2006, Goetz Graefe surveyed sorting in database sys- flips the bits. The string “GERMANY” is padded to ensure tems [9]. The most important takeaway from this survey fixed size. when it comes to performance is that the cost of sorting is dominated by comparing values and re-ordering data. Anything that makes either of these two operations cheaper will have an impact on the overall speed.
There are two obvious ways to go about implementing a comparator in a column-store when we have multiple O R D E R B Y clauses:
such as joins and aggregations. For vectorized execution engines, it is common practice to physically convert vectors to and from a row layout for these operators using scatter-gather. We argue that this layout should be used for sorting, as sorting is also a row-based operator.
We show DuckDB’s row layout in Figure 1. Rows have a fixed size that can be easily re-ordered while sorting.
We represent variable-sized columns with pointers into a string heap where the data resides. The heap data does not have to be re-ordered while sorting in memory. Each ifxed-size row has an additional p o i n t e r field that points to its “heap row”. This pointer is not used for in-memory sorting but is crucial for external sorting, which we will explain in section 2.2. 1. Iterate through the clauses: Compare columns until we find one that is not equal, or until we have compared all columns. This comparator jumps between columns, causing random access in memory. 2. Sort the data entirely by the first clause, then sort by the second clause, but only where the ifrst clause was equal, and so on. This approach requires multiple passes over the data.
The binary string comparison technique [10] improves sorting performance by simplifying the comparator. It 2.1. Parallel Sorting encodes all columns in the ORDER BY clause into a single binary sequence that, when compared using m e m c m p will DuckDB uses Morsel-Driven Parallelism [11], a frameyield the correct overall sorting order. This encoding work for parallel query execution. For the sorting operalso yields the correct order with a byte-by-byte Radix ator, this means that multiple threads collect a roughly sort. Although this technique has existed since the days equal amount of data, in parallel, from the input table. of System R, not many systems use it today and opt for We use this parallelism by letting each thread sort its one of the ways listed above. collected data using Radix sort. After this initial sorting
We implement this comparator and opt for fixed-size phase, each thread has one or more sorted blocks of data, encodings, which can be more easily re-ordered. For which must be combined into the final sorted result using variable-size types such as strings, we can therefore only merge sort. encode a prefix. We compare the whole string only when There are two main ways of implementing merge sort: prefixes are equal. The encoding is shown in Figure 2. K-way and Cascade merge. The K-way merge merges
Not shown in the figure are NULL values and colla- lists into one sorted list in one pass and is traditionally tions. NULL values are handled by prefixing each value used for external sorting because it minimizes I/O [12]. with an additional byte denoting whether the value is Cascade merge is used for in-memory sorting because it NULL. Collations are handled by evaluating the collation is more eficient than K-way merge. It merges two lists of function before encoding the prefix of the string. sorted data at-a-time until only one sorted list remains.
The other high cost of sorting is re-ordering data. Sys- Recent work on K-way external merge sort [13] on tems that use columnar storage must re-order all selected devices with flash memory reduces execution time by columns, which causes a random access pattern for each. 20% to 35% compared to standard external merge sort. Row-based systems only have to pay the cost of this ran- Salah et al. [14]show that K-way merge can achieve better dom access pattern once. When we select many columns, performance than cascaded merge when it comes to inthis becomes a considerable advantage. place sorting. This work on K-way merging may seem 3. Evaluation
ofset, which denotes where the strings of this row reside in the heap block. We also replace the pointers to the string values within the row with an 8-byte relative ofset. TPC-DS tables are challenging for sorting implemenThis ofset denotes how far this particular string is located tations because they are wide (many columns, unlike the from the start of this row’s heap row. Using relative tables in TPC-H) and have a mix of fixed- and variableofsets within rows rather than absolute ofsets is very sized types. c a t a l o g _ s a l e s has 34 columns, all fixed-size useful during sorting: These relative ofsets stay constant types: integer and double. c u s t o m e r has 18 columns, and do not need to be updated when we copy the row. ifxed- and variable-size: 10 integers, 8 strings.
With this dual-purpose row-wise representation, we We sort the c a t a l o g _ s a l e s table on c s _ q u a n t i t y and achieve an almost seamless transition between in- c s _ i t e m _ s k , and select an increasing number of payload memory and external sorting. The only diference be- columns. This experiment tests both the system’s ability tween the two is swizzling and unswizzling each pointer to sort and re-order the payload. We show the results of once and re-ordering the heap during sorting. this experiment in Figure 4.
1https://github.com/lnkuiper/experiments/tree/master/sorting 10.0 )s 7.5 ( iem5.0 t 2.5 400 200 0 HyPer 3 ) s (2 e m it 1 5 10 15 20 25 30 number of payload columns ClickHouse DuckDB 5 10 15 20 25 30 number of payload columns
Pandas SQLite
As expected, sorting by strings is slower than sorting by integers for most systems. In this experiment, the payload also includes string columns. Pandas has an advantage here because it already has the strings in memory, and most likely only needs to re-order pointers to these strings. The database systems need to copy strings twice: Once when reading the input table, and again when creating the output table. Profiling in DuckDB reveals that the actual sorting takes less than a second at SF300, and most time is spent on (de)serializing strings. See [17] for more details on the diference between integers and strings.
The table fits in memory at SF10, and the systems’ performances are in the same ballpark, except for SQLite, and DuckDB is the clear winner. At SF100, around 14 selected payload columns, the input table takes up 50% of memory. It is common for systems to not sort data in place, but copy it to a new location, which requires double the amount of memory. The figure clearly shows this: All systems except DuckDB and SQLite run into an error due to running out of memory and are unable to complete the benchmark.
ClickHouse switches to an external sorting strategy, which is much slower than its in-memory strategy. Therefore, adding a few payload columns results in a runtime that is orders of magnitude higher. Despite switching 4. Conclusion and Future Work strategy, ClickHouse runs into an out-of-memory error.
HyPer uses the m m a p system call, which creates a map- In this paper, we presented our parallel external sortping between a block of memory and a file, which allows ing implementation in DuckDB. We compared it against HyPer to continue for a while when the data no longer four data management systems using a relational sorting ifts in memory, before running into an error as well. As benchmark based on TPC-DS. Three of the four systems we can see, the runtime becomes very slow before HyPer perform well in memory, but crash as the data goes over runs out of memory: Random memory access becomes the amount of available memory. DuckDB is the only sysrandom disk access. tem under benchmark that performs well both in memory
Surprisingly, Pandas can load the dataset at SF100 be- and external. These results demonstrate that it is possicause macOS dynamically increases swap size. Most ble to implement a sorting operator that is eficient in operating systems do not do this, and Pandas will not memory and has a graceful degradation in performance load the dataset at all. Pandas relies on NumPy’s [19] as the input size exceeds the memory limit. single-threaded quicksort implementation. Pandas shows impressive performance, partly because it already has 4.1. Future Work the input data fully materialized in memory and does not have to stream data through an execution pipeline from It is unclear how each technique contributed to end-tothe input to the output table like most DBMSes. end performance. Quantifying these contributions e.g.
Meanwhile, DuckDB and SQLite do not show a visible through simulation is an area of future research. diference in performance when where data no longer fits Our sorting implementation uses a row layout that can in memory. SQLite always opts for a traditional external be ofloaded to storage using pointer swizzling. Other sorting strategy, resulting in a robust, but overall slower blocking operators could benefit from this layout. For inperformance than DuckDB. stance, join, aggregation and window. Incorporating this
In our next benchmark, on the c u s t o m e r table, we test layout would enable external computation for these ophow well the systems can sort by strings and by integers. erators as well. Implementing these operators such that Both comparing and re-ordering strings are much more their performance degrades gracefully as the input size expensive than comparing and re-ordering numeric types. exceeds the memory limit is an area of future research. https://doi.org/10.1145/564691.564759. doi:1 0 . 1 1 4 5 / 5 6 4 6 9 1 . 5 6 4 7 5 9 . [1] A. Kemper, T. Neumann, HyPer: A hybrid [9] G. Graefe, Implementing Sorting in Database OLTP&OLAP main memory database system based Systems, ACM Comput. Surv. 38 (2006) 10–es. on virtual memory snapshots, in: S. Abiteboul, URL: https://doi.org/10.1145/1132960.1132964. K. Böhm, C. Koch, K. Tan (Eds.), Proceedings of the doi:1 0 . 1 1 4 5 / 1 1 3 2 9 6 0 . 1 1 3 2 9 6 4 . 27th International Conference on Data Engineering, [10] M. W. Blasgen, R. G. Casey, K. P. Eswaran, An ICDE 2011, April 11-16, 2011, Hannover, Germany, Encoding Method for Multifield Sorting and InIEEE Computer Society, 2011, pp. 195–206. URL: dexing, Commun. ACM 20 (1977) 874–878. URL: https://doi.org/10.1109/ICDE.2011.5767867. doi:1 0 . https://doi.org/10.1145/359863.359892. doi:1 0 . 1 1 4 5 / 1 1 0 9 / I C D E . 2 0 1 1 . 5 7 6 7 8 6 7 . 3 5 9 8 6 3 . 3 5 9 8 9 2 . [2] B. Imasheva, A. Nakispekov, A. Sidelkovskaya, [11] V. Leis, P. Boncz, A. Kemper, T. Neumann, MorselA. Sidelkovskiy, The Practice of Moving to Big Driven Parallelism: A NUMA-Aware Query EvaluData on the Case of the NoSQL Database, Click- ation Framework for the Many-Core Age, in: ProHouse, in: H. A. L. Thi, H. M. Le, T. P. Dinh (Eds.), ceedings of the 2014 ACM SIGMOD International Optimization of Complex Systems: Theory, Models, Conference on Management of Data, SIGMOD Algorithms and Applications, WCGO 2019, World ’14, Association for Computing Machinery, New Congress on Global Optimization, Metz, France, 8- York, NY, USA, 2014, p. 743–754. URL: https://doi. 10 July, 2019, volume 991 of Advances in Intelligent org/10.1145/2588555.2610507. doi:1 0 . 1 1 4 5 / 2 5 8 8 5 5 5 . Systems and Computing, Springer, 2019, pp. 820–828. 2 6 1 0 5 0 7 .
URL: https://doi.org/10.1007/978-3-030-21803-4_82. [12] D. Knuth, The Art Of Computer Programming, vol. doi:1 0 . 1 0 0 7 / 9 7 8 - 3 - 0 3 0 - 2 1 8 0 3 - 4 \ _ 8 2 . 3: Sorting And Searching, Addison-Wesley, 1973. [3] W. McKinney, et al., Data structures for statistical [13] R. Jackson, J. Gresl, R. Lawrence, Eficient Extercomputing in Python, in: Proceedings of the 9th nal Sorting for Memory-Constrained Embedded DePython in Science Conference, volume 445, Austin, vices with Flash Memory, ACM Trans. Embed. ComTX, 2010, pp. 51–56. put. Syst. 20 (2021). URL: https://doi.org/10.1145/ [4] H. Wickham, R. François, L. Henry, K. Müller, 3446976. doi:1 0 . 1 1 4 5 / 3 4 4 6 9 7 6 . dplyr: A Grammar of Data Manipulation, 2021. URL: [14] A. Salah, K. Li, Q. Liao, M. Hashem, Z. Li, A. T. https://CRAN.R-project.org/package=dplyr, r pack- Chronopoulos, A. Y. Zomaya, A Time-Space Efiage version 1.0.7. cient Algorithm for Parallel k-Way In-Place Merg[5] M. Raasveldt, H. Mühleisen, DuckDB: An Em- ing Based on Sequence Partitioning and Perfect beddable Analytical Database, in: Proceedings Shufle, ACM Trans. Parallel Comput. 7 (2020). of the 2019 International Conference on Manage- URL: https://doi.org/10.1145/3391443. doi:1 0 . 1 1 4 5 / ment of Data, SIGMOD ’19, Association for Com- 3 3 9 1 4 4 3 . puting Machinery, New York, NY, USA, 2019, p. [15] O. Green, S. Odeh, Y. Birk, Merge Path - A 1981–1984. URL: https://doi.org/10.1145/3299869. Visually Intuitive Approach to Parallel Merging, 3320212. doi:1 0 . 1 1 4 5 / 3 2 9 9 8 6 9 . 3 3 2 0 2 1 2 . CoRR abs/1406.2628 (2014). URL: http://arxiv.org/ [6] V. Leis, M. Haubenschild, A. Kemper, T. Neumann, abs/1406.2628. a r X i v : 1 4 0 6 . 2 6 2 8 .
LeanStore: In-Memory Data Management beyond [16] R. D. Hipp, SQLite, 2021. URL: https://www.sqlite. Main Memory, in: 34th IEEE International Confer- org/index.html. ence on Data Engineering, ICDE 2018, Paris, France, [17] L. Kuiper, Fastest table sort in the West - RedesignApril 16-19, 2018, IEEE Computer Society, 2018, pp. ing DuckDB’s sort, 2021. URL: https://duckdb.org/ 185–196. URL: https://doi.org/10.1109/ICDE.2018. 2021/08/27/external-sorting.html. 00026. doi:1 0 . 1 1 0 9 / I C D E . 2 0 1 8 . 0 0 0 2 6 . [18] M. Raasveldt, H. Mühleisen, Don’t Hold My Data [7] A. Kemper, D. Kossmann, Adaptable Pointer Swiz- Hostage: A Case for Client Protocol Redesign, Proc. zling Strategies in Object Bases: Design, Real- VLDB Endow. 10 (2017) 1022–1033. URL: https: ization, and Quantitative Analysis, VLDB J. 4 //doi.org/10.14778/3115404.3115408. doi:1 0 . 1 4 7 7 8 / (1995) 519–566. URL: http://www.vldb.org/journal/ 3 1 1 5 4 0 4 . 3 1 1 5 4 0 8 .
VLDBJ4/P519.pdf. [19] C. R. Harris, K. J. Millman, S. J. van der Walt, R. Gom[8] M. Poess, B. Smith, L. Kollar, P. Larson, TPC-DS, mers, P. Virtanen, D. Cournapeau, E. Wieser, J. TayTaking Decision Support Benchmarking to the next lor, S. Berg, N. J. Smith, R. Kern, M. Picus, S. Hoyer, Level, in: Proceedings of the 2002 ACM SIGMOD M. H. van Kerkwijk, M. Brett, A. Haldane, J. F. del International Conference on Management of Data, Río, M. Wiebe, P. Peterson, P. Gérard-Marchant, SIGMOD ’02, Association for Computing Machin- K. Sheppard, T. Reddy, W. Weckesser, H. Abbasi, ery, New York, NY, USA, 2002, p. 582–587. URL: C. Gohlke, T. E. Oliphant, Array programming