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: 5294
Venue: SIGMOD
Year: 2016
Pagerank: 5.6641994e-05
Overall Rank: 7,242 | 50.32%
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,112	Speeding Up Set Intersections in Graph Algorithms using SIMD Instructions	2018	SIGMOD	9.1514258e-05
4,483	Accelerating Raw Data Analysis with the ACCORDA Software and Hardware Architecture	2019	VLDB	6.6724044e-05
7,774	Building Advanced SQL Analytics From Low-Level Plan Operators	2021	SIGMOD	5.5468469e-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.00069513174
14	MonetDB/X100: Hyper-Pipelining Query Execution	2005	CIDR	0.0006312782
209	Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs	2009	VLDB	0.00024932174
252	Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited	2014	VLDB	0.00023242719
423	Massively Parallel Sort-Merge Joins in Main Memory Multi-Core Database Systems	2012	VLDB	0.00018725853
428	HYRISE—A Main Memory Hybrid Storage Engine	2011	VLDB	0.00018633493
634	Rethinking SIMD Vectorization for In-Memory Databases	2015	SIGMOD	0.00015533814
678	Fast Sort on CPUs and GPUs: A Case for Bandwidth Oblivious SIMD Sort	2010	SIGMOD	0.00015061068
712	Efficient Implementation of Sorting on Multi-Core SIMD CPU Architecture	2008	VLDB	0.0001468812
721	Database Architecture Evolution: Mammals Flourished long before Dinosaurs became Extinct	2009	VLDB	0.00014631814
735	Profiling, What-if Analysis, and Cost-based Optimization of MapReduce Programs	2011	VLDB	0.00014522606
870	BitWeaving: Fast Scans for Main Memory Data Processing	2013	SIGMOD	0.0001350293
925	Dictionary-based Order-preserving String Compression for Main Memory Column Stores	2009	SIGMOD	0.00013182044
1,177	A Comprehensive Study of Main-Memory Partitioning and its Application to Large-Scale Comparison- and Radix-Sort	2014	SIGMOD	0.00011808761
1,315	Fast Updates on Read-Optimized Databases Using Multi-Core CPUs	2012	VLDB	0.00011181796
1,450	Row-wise Parallel Predicate Evaluation	2008	VLDB	0.00010746714
1,761	ByteSlice: Pushing the Envelop of Main Memory Data Processing with a New Storage Layout	2015	SIGMOD	9.8154969e-05
2,232	Database Compression on Graphics Processors	2010	VLDB	8.8970926e-05
2,599	WideTable: An Accelerator for Analytical Data Processing	2014	VLDB	8.3583572e-05
4,021	PARADIS: An Efficient Parallel Algorithm for In-place Radix Sort	2015	VLDB	6.9501893e-05
4,177	SIMD- and Cache-Friendly Algorithm for Sorting an Array of Structures	2015	VLDB	6.8499317e-05
5,122	A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew	2015	SIGMOD	6.3573169e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,106	Skipping-oriented Partitioning for Columnar Layouts	2017	VLDB
2	1,315	Fast Updates on Read-Optimized Databases Using Multi-Core CPUs	2012	VLDB
3	678	Fast Sort on CPUs and GPUs: A Case for Bandwidth Oblivious SIMD Sort	2010	SIGMOD
4	4,177	SIMD- and Cache-Friendly Algorithm for Sorting an Array of Structures	2015	VLDB
5	4,607	Adaptive NUMA-aware data placement and task scheduling for analytical workloads in main-memory column-stores	2017	VLDB
6	6,009	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB
7	712	Efficient Implementation of Sorting on Multi-Core SIMD CPU Architecture	2008	VLDB
8	7,705	A Study of Sort Algorithms for Multiprocessor Database Machines	1986	VLDB
9	1,177	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