A Comprehensive Study of Main-Memory Partitioning and its Application to Large-Scale Comparison- and Radix-Sort

Summary: Comprehensive study of main-memory partitioning across the memory hierarchy, revisiting in-cache pitfalls and introducing out-of-cache, in-place, and NUMA-aware partitioning variants. Proposes three NUMA-aware sorts—stable LSB radix, in-place MSB radix, and a wide-fanout comparison-sort with a cache-resident range index—achieving fastest billion-scale performance for dense and sparse keys and enabling building other ops (joins, aggregation). (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4893
Venue: SIGMOD
Year: 2014
Pagerank: 0.00011162682
Overall Rank: 1,607 | 88.83%
DOI: 10.1145/2588555.2610522

Incoming Non-self Citations Over Time

Authors

1. Orestis Polychroniou
2. Kenneth A. Ross

Incoming Citations (Sorted by Pagerank)

Showing 35 of 35 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
958	Rethinking SIMD Vectorization for In-Memory Databases	2015	SIGMOD	0.00015045316
1,361	The End of Slow Networks: It's Time for a Redesign	2016	VLDB	0.00012379741
2,040	A Study of the Fundamental Performance Characteristics of GPUs and CPUs for Database Analytics	2020	SIGMOD	9.7057698e-05
2,390	ByteSlice: Pushing the Envelop of Main Memory Data Processing with a New Storage Layout	2015	SIGMOD	8.9084657e-05
2,526	Track Join: Distributed Joins with Minimal Network Traffic	2014	SIGMOD	8.5968612e-05
2,742	Cache-Efficient Aggregation: Hashing Is Sorting	2015	SIGMOD	8.1906104e-05
3,151	A Memory Bandwidth-Efficient Hybrid Radix Sort on GPUs	2017	SIGMOD	7.4720668e-05
3,721	To Partition, or Not to Partition, That is the Join Question in a Real System	2021	SIGMOD	6.8179379e-05
3,933	RUMA has it: Rewired User-space Memory Access is Possible!	2016	VLDB	6.617914e-05
4,042	PARADIS: An Efficient Parallel Algorithm for In-place Radix Sort	2015	VLDB	6.5026989e-05
4,161	Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe?	2017	SIGMOD	6.3938006e-05
4,655	SIMD- and Cache-Friendly Algorithm for Sorting an Array of Structures	2015	VLDB	6.0221672e-05
5,178	FPGA-based Data Partitioning	2017	SIGMOD	5.6438393e-05
5,314	Can Learned Models Replace Hash Functions?	2023	VLDB	5.5724608e-05
5,376	Holistic Indexing in Main-memory Column-stores	2015	SIGMOD	5.5417421e-05
5,653	On the Surprising Difficulty of Simple Things: the Case of Radix Partitioning	2015	VLDB	5.3889513e-05
6,525	Database Technology for the Masses: Sub-Operators as First-Class Entities	2021	VLDB	5.027205e-05
6,540	Data Partitioning for In-Memory Systems: Myths, Challenges, and Opportunities	2019	CIDR	5.0219214e-05
6,574	Robust Performance of Main Memory Data Structures by Configuration	2020	SIGMOD	5.0055505e-05
6,777	Revisiting Reuse in Main Memory Database Systems	2017	SIGMOD	4.9288776e-05
7,097	Fast Multi-Column Sorting in Main-Memory Column-Stores	2016	SIGMOD	4.8336115e-05
7,155	Evaluating Multi-GPU Sorting with Modern Interconnects	2022	SIGMOD	4.8149812e-05
7,335	MorphStore: Analytical Query Engine with a Holistic Compression-Enabled Processing Model	2020	VLDB	4.7603723e-05
7,546	Is Perfect Hashing Practical for OLAP Systems?	2024	CIDR	4.7148429e-05
8,094	Modularis: Modular Relational Analytics over Heterogeneous Distributed Platforms	2021	VLDB	4.5867812e-05
8,626	Adaptive Code Generation for Data-Intensive Analytics	2021	VLDB	4.4829152e-05
8,720	Entropy-Learned Hashing: Constant Time Hashing with Controllable Uniformity	2022	SIGMOD	4.4609699e-05
9,767	Adaptive Indexing of Objects with Spatial Extent	2023	VLDB	4.2856106e-05
9,823	Thriving in the No Man’s Land between Compilers and Databases	2019	CIDR	4.2754485e-05
10,121	TQEx: Tensor-based Query Engine Enhanced by Bridging the Gap	2026	SIGMOD	4.1945683e-05
10,989	High-Performance Query Processing with NVMe Arrays: Spilling without Killing Performance	2024	SIGMOD	4.1945683e-05
11,142	Cache-Efficient Top-k Aggregation over High Cardinality Large Datasets	2024	VLDB	4.1945683e-05
11,237	Cracking-Like Join for Trusted Execution Environments	2023	VLDB	4.1945683e-05
11,381	Origami: A High-Performance Mergesort Framework	2022	VLDB	4.1945683e-05
11,832	A Study of Sorting Algorithms on Approximate Memory	2016	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
241	DB2 with BLU Acceleration: So Much More than Just a Column Store	2013	VLDB	0.00031420034
305	SIMD-Scan: Ultra Fast in-Memory Table Scan using on-Chip Vector Processing Units	2009	VLDB	0.00028248614
351	Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs	2009	VLDB	0.0002636504
381	FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs	2010	SIGMOD	0.00024873637
404	Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited	2014	VLDB	0.00024143076
540	Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs	2011	SIGMOD	0.0002063443
585	Massively Parallel Sort-Merge Joins in Main Memory Multi-Core Database Systems	2012	VLDB	0.00019706145
930	Fast Sort on CPUs and GPUs: A Case for Bandwidth Oblivious SIMD Sort	2010	SIGMOD	0.00015238545
946	Efficient Implementation of Sorting on Multi-Core SIMD CPU Architecture	2008	VLDB	0.0001513324
1,079	What happens during a Join? Dissecting CPU and Memory Optimization Effects	2000	VLDB	0.00014233415
1,543	NUMA-aware algorithms: the case of data shuffling	2013	CIDR	0.0001145318
3,655	CloudRAMSort: Fast and Efficient Large-Scale Distributed RAM Sort on Shared-Nothing Cluster	2012	SIGMOD	6.8718304e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,460	A Study of Sort Algorithms for Multiprocessor Database Machines	1986	VLDB	4.7241128e-05
7,097	Fast Multi-Column Sorting in Main-Memory Column-Stores	2016	SIGMOD	4.8336115e-05
404	Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited	2014	VLDB	0.00024143076
5,109	Adaptive NUMA-aware data placement and task scheduling for analytical workloads in main-memory column-stores	2017	VLDB	5.6908086e-05
6,540	Data Partitioning for In-Memory Systems: Myths, Challenges, and Opportunities	2019	CIDR	5.0219214e-05
3,151	A Memory Bandwidth-Efficient Hybrid Radix Sort on GPUs	2017	SIGMOD	7.4720668e-05
4,655	SIMD- and Cache-Friendly Algorithm for Sorting an Array of Structures	2015	VLDB	6.0221672e-05
930	Fast Sort on CPUs and GPUs: A Case for Bandwidth Oblivious SIMD Sort	2010	SIGMOD	0.00015238545
5,653	On the Surprising Difficulty of Simple Things: the Case of Radix Partitioning	2015	VLDB	5.3889513e-05
585	Massively Parallel Sort-Merge Joins in Main Memory Multi-Core Database Systems	2012	VLDB	0.00019706145