Fast Multi-Column Sorting in Main-Memory Column-Stores

Summary: Proposes code massaging, a bit-level cross-column reordering technique to reduce the number of sorting rounds for multi-column ORDER BY/GROUP BY in main-memory column-stores. Delivers up to 4.7x (TPC-H), 4.7x (TPC-H skew), 4x (TPC-DS), and 3.2x (real workloads) speedups by increasing SIMD parallelism. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h48145bf844f65cb6
Venue: SIGMOD
Year: 2016
Pagerank: 5.5162245e-05
Overall Rank: 7,473 | 49.78%
DOI: 10.1145/2882903.2915205

Incoming Non-self Citations Over Time

Authors

1. Wenjian Xu (Hong Kong Polytechnic University)
2. Ziqiang Feng (Hong Kong Polytechnic University)
3. Eric Lo (Chinese University of Hong Kong)

BibTeX Citation

@inproceedings{xu_sigmod16,
        title = {{Fast Multi-Column Sorting in Main-Memory Column-Stores}},
        author = {Xu, Wenjian and Feng, Ziqiang and Lo, Eric},
        series = {{SIGMOD} '16},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2882903.2915205},
        url = {https://dl.acm.org/doi/10.1145/2882903.2915205},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,853	Speeding Up Set Intersections in Graph Algorithms using SIMD Instructions	2018	SIGMOD	9.499042e-05
4,575	Accelerating Raw Data Analysis with the ACCORDA Software and Hardware Architecture	2019	VLDB	6.5234168e-05
7,871	Building Advanced SQL Analytics From Low-Level Plan Operators	2021	SIGMOD	5.434014e-05

Outgoing Citations (Sorted by Pagerank)

Showing 22 of 22 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
12	C-Store: A Column-oriented DBMS	2005	VLDB	0.0006897844
14	MonetDB/X100: Hyper-Pipelining Query Execution	2005	CIDR	0.00064013679
210	Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs	2009	VLDB	0.00024844328
251	Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited	2014	VLDB	0.00023136934
425	Massively Parallel Sort-Merge Joins in Main Memory Multi-Core Database Systems	2012	VLDB	0.00018485358
431	HYRISE—A Main Memory Hybrid Storage Engine	2011	VLDB	0.00018400856
627	Rethinking SIMD Vectorization for In-Memory Databases	2015	SIGMOD	0.00015454197
663	Fast Sort on CPUs and GPUs: A Case for Bandwidth Oblivious SIMD Sort	2010	SIGMOD	0.00014997516
702	Database Architecture Evolution: Mammals Flourished long before Dinosaurs became Extinct	2009	VLDB	0.00014668058
723	Efficient Implementation of Sorting on Multi-Core SIMD CPU Architecture	2008	VLDB	0.00014507399
754	Profiling, What-if Analysis, and Cost-based Optimization of MapReduce Programs	2011	VLDB	0.00014231311
873	BitWeaving: Fast Scans for Main Memory Data Processing	2013	SIGMOD	0.00013334067
910	Dictionary-based Order-preserving String Compression for Main Memory Column Stores	2009	SIGMOD	0.00013122392
1,116	A Comprehensive Study of Main-Memory Partitioning and its Application to Large-Scale Comparison- and Radix-Sort	2014	SIGMOD	0.00011957053
1,332	Fast Updates on Read-Optimized Databases Using Multi-Core CPUs	2012	VLDB	0.00010993664
1,458	Row-wise Parallel Predicate Evaluation	2008	VLDB	0.00010583148
1,718	ByteSlice: Pushing the Envelop of Main Memory Data Processing with a New Storage Layout	2015	SIGMOD	9.7983307e-05
2,187	Database Compression on Graphics Processors	2010	VLDB	8.891124e-05
2,628	WideTable: An Accelerator for Analytical Data Processing	2014	VLDB	8.2027948e-05
4,065	PARADIS: An Efficient Parallel Algorithm for In-place Radix Sort	2015	VLDB	6.8199976e-05
4,225	SIMD- and Cache-Friendly Algorithm for Sorting an Array of Structures	2015	VLDB	6.7180565e-05
5,213	A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew	2015	SIGMOD	6.222614e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,395	Selection Pushdown in Column Stores using Bit Manipulation Instructions	2023	SIGMOD
2	1,332	Fast Updates on Read-Optimized Databases Using Multi-Core CPUs	2012	VLDB
3	663	Fast Sort on CPUs and GPUs: A Case for Bandwidth Oblivious SIMD Sort	2010	SIGMOD
4	4,225	SIMD- and Cache-Friendly Algorithm for Sorting an Array of Structures	2015	VLDB
5	4,704	Adaptive NUMA-aware data placement and task scheduling for analytical workloads in main-memory column-stores	2017	VLDB
6	6,108	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB
7	723	Efficient Implementation of Sorting on Multi-Core SIMD CPU Architecture	2008	VLDB
8	7,858	A Study of Sort Algorithms for Multiprocessor Database Machines	1986	VLDB
9	1,116	A Comprehensive Study of Main-Memory Partitioning and its Application to Large-Scale Comparison- and Radix-Sort	2014	SIGMOD
10	425	Massively Parallel Sort-Merge Joins in Main Memory Multi-Core Database Systems	2012	VLDB