A Memory Bandwidth-Efficient Hybrid Radix Sort on GPUs

Summary: Memory-bandwidth-aware hybrid GPU radix sort halves transfers, delivering ~2.3× speedup on uniform data. A pipelined heterogeneous mode handles off-GPU/large inputs, enabling strong end-to-end gains over CPU radix sort on large key-value workloads. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5481
Venue: SIGMOD
Year: 2017
Pagerank: 8.2756346e-05
Overall Rank: 2,667 | 81.71%
DOI: 10.1145/3035918.3064043

Incoming Non-self Citations Over Time

Authors

1. Elias Stehle (Technical University of Munich)
2. Hans-Arno Jacobsen (Technical University of Munich)

BibTeX Citation

@inproceedings{stehle_sigmod17,
        title = {{A Memory Bandwidth-Efficient Hybrid Radix Sort on GPUs}},
        author = {Stehle, Elias and Jacobsen, Hans-Arno},
        series = {{SIGMOD} '17},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3035918.3064043},
        url = {https://dl.acm.org/doi/10.1145/3035918.3064043},
        year = {2017}
}

Incoming Citations (Sorted by Pagerank)

Showing 22 of 22 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,466	A Study of the Fundamental Performance Characteristics of GPUs and CPUs for Database Analytics	2020	SIGMOD	0.0001068941
1,977	HetExchange: Encapsulating heterogeneous CPU-GPU parallelism in JIT compiled engines	2019	VLDB	9.3641101e-05
2,566	Pump Up the Volume: Processing Large Data on GPUs with Fast Interconnects	2020	SIGMOD	8.4116562e-05
3,791	Hardware-conscious Query Processing in GPU-accelerated Analytical Engines	2019	CIDR	7.1235328e-05
4,144	Tile-based Lightweight Integer Compression in GPU	2022	SIGMOD	6.8744592e-05
4,243	Orchestrating Data Placement and Query Execution in Heterogeneous CPU-GPU DBMS	2022	VLDB	6.8073248e-05
4,535	Triton Join: Efficiently Scaling to a Large Join State on GPUs with Fast Interconnects	2022	SIGMOD	6.6419266e-05
4,603	The Art of Balance: A RateupDB Experience of Building a CPU/GPU Hybrid Database Product	2021	VLDB	6.6105578e-05
6,012	Parallel Index-based Stream Join on a Multicore CPU	2020	SIGMOD	6.0102675e-05
6,143	ColumnML: Column-Store Machine Learning with On-The-Fly Data Transformation	2019	VLDB	5.9622615e-05
6,161	Data Partitioning for In-Memory Systems: Myths, Challenges, and Opportunities	2019	CIDR	5.9537202e-05
6,774	Evaluating Multi-GPU Sorting with Modern Interconnects	2022	SIGMOD	5.7778738e-05
7,058	BOSS - An Architecture for Database Kernel Composition	2024	VLDB	5.7154673e-05
7,217	ParPaRaw: Massively Parallel Parsing of Delimiter-Separated Raw Data	2020	VLDB	5.668373e-05
7,370	Efficient Top-K Query Processing on Massively Parallel Hardware	2018	SIGMOD	5.6313494e-05
8,374	SPRINTER: A Fast n-ary Join Query Processing Method for Complex OLAP Queries	2020	SIGMOD	5.4399097e-05
8,808	Scaling your Hybrid CPU-GPU DBMS to Multiple GPUs	2024	VLDB	5.3661351e-05
9,182	A Case for Ecological Efficiency in Database Server Lifecycles	2025	CIDR	5.3058708e-05
9,333	Efficiently Joining Large Relations on Multi-GPU Systems	2025	VLDB	5.2887551e-05
10,102	Distributed Stream KNN Join	2021	SIGMOD	5.1488731e-05
10,985	Scaling GPU-Accelerated Databases beyond GPU Memory Size	2025	VLDB	5.093636e-05
11,231	Accelerating Merkle Patricia Trie with GPU	2024	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
105	Quickly Generating Billion-Record Synthetic Databases	1994	SIGMOD	0.00033877899
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
305	GPUTeraSort: High Performance Graphics Co-processor Sorting for Large Database Management	2006	SIGMOD	0.00021872796
389	One Trillion Edges: Graph Processing at Facebook-Scale	2015	VLDB	0.00019386526
423	Massively Parallel Sort-Merge Joins in Main Memory Multi-Core Database Systems	2012	VLDB	0.00018725853
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
1,177	A Comprehensive Study of Main-Memory Partitioning and its Application to Large-Scale Comparison- and Radix-Sort	2014	SIGMOD	0.00011808761
3,368	CloudRAMSort: Fast and Efficient Large-Scale Distributed RAM Sort on Shared-Nothing Cluster	2012	SIGMOD	7.4713287e-05
3,378	A Hybrid B+-tree as Solution for In-Memory Indexing on CPU-GPU Heterogeneous Computing Platforms	2016	SIGMOD	7.4587887e-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
6,113	Patience is a Virtue: Revisiting Merge and Sort on Modern Processors	2014	SIGMOD	5.9715554e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,033	A Study of Sorting Algorithms on Approximate Memory	2016	SIGMOD
2	712	Efficient Implementation of Sorting on Multi-Core SIMD CPU Architecture	2008	VLDB
3	7,591	Efficiently Processing Joins and Grouped Aggregations on GPUs	2025	SIGMOD
4	7,370	Efficient Top-K Query Processing on Massively Parallel Hardware	2018	SIGMOD
5	4,177	SIMD- and Cache-Friendly Algorithm for Sorting an Array of Structures	2015	VLDB
6	1,177	A Comprehensive Study of Main-Memory Partitioning and its Application to Large-Scale Comparison- and Radix-Sort	2014	SIGMOD
7	9,333	Efficiently Joining Large Relations on Multi-GPU Systems	2025	VLDB
8	6,774	Evaluating Multi-GPU Sorting with Modern Interconnects	2022	SIGMOD
9	305	GPUTeraSort: High Performance Graphics Co-processor Sorting for Large Database Management	2006	SIGMOD
10	678	Fast Sort on CPUs and GPUs: A Case for Bandwidth Oblivious SIMD Sort	2010	SIGMOD