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.5091753e-05
Overall Rank: 7,495 | 49.61%
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
2,019	Speeding Up Set Intersections in Graph Algorithms using SIMD Instructions	2018	SIGMOD	9.1750421e-05
4,573	Accelerating Raw Data Analysis with the ACCORDA Software and Hardware Architecture	2019	VLDB	6.5265033e-05
7,866	Building Advanced SQL Analytics From Low-Level Plan Operators	2021	SIGMOD	5.4365876e-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.00068998927
14	MonetDB/X100: Hyper-Pipelining Query Execution	2005	CIDR	0.00064031282
210	Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs	2009	VLDB	0.00024851502
251	Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited	2014	VLDB	0.00023143736
423	Massively Parallel Sort-Merge Joins in Main Memory Multi-Core Database Systems	2012	VLDB	0.00018491327
431	HYRISE—A Main Memory Hybrid Storage Engine	2011	VLDB	0.00018403783
627	Rethinking SIMD Vectorization for In-Memory Databases	2015	SIGMOD	0.00015460957
661	Fast Sort on CPUs and GPUs: A Case for Bandwidth Oblivious SIMD Sort	2010	SIGMOD	0.00015003815
702	Database Architecture Evolution: Mammals Flourished long before Dinosaurs became Extinct	2009	VLDB	0.00014673738
722	Efficient Implementation of Sorting on Multi-Core SIMD CPU Architecture	2008	VLDB	0.00014488003
753	Profiling, What-if Analysis, and Cost-based Optimization of MapReduce Programs	2011	VLDB	0.00014237583
873	BitWeaving: Fast Scans for Main Memory Data Processing	2013	SIGMOD	0.00013338838
910	Dictionary-based Order-preserving String Compression for Main Memory Column Stores	2009	SIGMOD	0.00013123912
1,116	A Comprehensive Study of Main-Memory Partitioning and its Application to Large-Scale Comparison- and Radix-Sort	2014	SIGMOD	0.00011962096
1,335	Fast Updates on Read-Optimized Databases Using Multi-Core CPUs	2012	VLDB	0.0001099401
1,459	Row-wise Parallel Predicate Evaluation	2008	VLDB	0.00010585108
1,723	ByteSlice: Pushing the Envelop of Main Memory Data Processing with a New Storage Layout	2015	SIGMOD	9.7931223e-05
2,185	Database Compression on Graphics Processors	2010	VLDB	8.8948351e-05
2,628	WideTable: An Accelerator for Analytical Data Processing	2014	VLDB	8.2053454e-05
4,065	PARADIS: An Efficient Parallel Algorithm for In-place Radix Sort	2015	VLDB	6.8227646e-05
4,225	SIMD- and Cache-Friendly Algorithm for Sorting an Array of Structures	2015	VLDB	6.7207703e-05
5,213	A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew	2015	SIGMOD	6.2250048e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,392	Selection Pushdown in Column Stores using Bit Manipulation Instructions	2023	SIGMOD
2	1,335	Fast Updates on Read-Optimized Databases Using Multi-Core CPUs	2012	VLDB
3	661	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,702	Adaptive NUMA-aware data placement and task scheduling for analytical workloads in main-memory column-stores	2017	VLDB
6	6,106	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB
7	722	Efficient Implementation of Sorting on Multi-Core SIMD CPU Architecture	2008	VLDB
8	7,854	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	423	Massively Parallel Sort-Merge Joins in Main Memory Multi-Core Database Systems	2012	VLDB