Database Paper Browser

Back to papers

The Case for a Learned Sorting Algorithm

Summary: A learned distribution sort maps keys to positions via a CDF model, then finishes with a near-sorted pass. Up to 1B doubles, normally distributed, it yields 3.38x STL, 1.49x Radix, 5.54x TimSort, showing learned sorting as a practical primitive. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
5967
Venue
SIGMOD
Year
2020
Pagerank
6.4551616e-05
Overall Rank
4,097 | 71.50%
DOI
10.1145/3318464.3389752

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank Citing Paper Year Venue Pagerank
1,703 Are We Ready For Learned Cardinality Estimation? 2021 VLDB 0.00010836769
2,552 Updatable Learned Index with Precise Positions 2021 VLDB 8.5530411e-05
3,611 SNARF: A Learning-Enhanced Range Filter 2022 VLDB 6.9191399e-05
5,671 LSched: A Workload-Aware Learned Query Scheduler for Analytical Database Systems 2022 SIGMOD 5.3803919e-05
6,297 Towards instance-optimized data systems 2021 VLDB 5.1227886e-05
7,395 MOST: Model-Based Compression with Outlier Storage for Time Series Data 2023 SIGMOD 4.7420041e-05
7,894 LITS: An Optimized Learned Index for Strings 2024 VLDB 4.6240341e-05
8,020 The Holon Approach for Simultaneously Tuning Multiple Components in a Self-Driving Database Management System with Machine Learning via Synthesized Proto-Actions 2024 VLDB 4.6040862e-05
8,417 The Case for Learned In-Memory Joins 2023 VLDB 4.5194164e-05
8,650 HAP: An Efficient Hamming Space Index Based on Augmented Pigeonhole Principle 2022 SIGMOD 4.4761716e-05
9,346 Can Learned Indexes be Built Efficiently? A Deep Dive into Sampling Trade-offs 2024 SIGMOD 4.3532026e-05
9,806 The Image Calculator: 10x Faster Image-AI Inference by Replacing JPEG with Self-designing Storage Format 2024 SIGMOD 4.2805224e-05
10,087 High Performance or Low Memory? An Updatable Learned Index Framework for Time-Space Tradeoff 2026 SIGMOD 4.1945683e-05
10,216 The Case For Language Model Approximated LIKE Predicate 2026 SIGMOD 4.1945683e-05
11,481 Efficient String Sort with Multi-Character Encoding and Adaptive Sampling 2021 SIGMOD 4.1945683e-05
11,504 LES3: Learning-based Exact Set Similarity Search 2021 VLDB 4.1945683e-05
Previous Page 1 / 1 Next

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
102 The Case for Learned Index Structures 2018 SIGMOD 0.00049545203
204 Learned Cardinalities: Estimating Correlated Joins with Deep Learning 2019 CIDR 0.00034784455
333 Neo: A Learned Query Optimizer 2019 VLDB 0.00027206884
404 Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited 2014 VLDB 0.00024143076
801 SageDB: A Learned Database System 2019 CIDR 0.00016505496
826 ALEX: An Updatable Adaptive Learned Index 2020 SIGMOD 0.00016224841
930 Fast Sort on CPUs and GPUs: A Case for Bandwidth Oblivious SIMD Sort 2010 SIGMOD 0.00015238545
1,375 FITing-Tree: A Data-aware Index Structure 2019 SIGMOD 0.00012303141
2,083 Towards a Learning Optimizer for Shared Clouds 2019 VLDB 9.5834572e-05
2,732 Efficiently Searching In-Memory Sorted Arrays: Revenge of the Interpolation Search? 2019 SIGMOD 8.2087602e-05
4,042 PARADIS: An Efficient Parallel Algorithm for In-place Radix Sort 2015 VLDB 6.5026989e-05
4,655 SIMD- and Cache-Friendly Algorithm for Sorting an Array of Structures 2015 VLDB 6.0221672e-05
Previous Page 1 / 1 Next

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
946 Efficient Implementation of Sorting on Multi-Core SIMD CPU Architecture 2008 VLDB 0.0001513324
1,460 Benchmarking Learned Indexes 2021 VLDB 0.00011887068
1,607 A Comprehensive Study of Main-Memory Partitioning and its Application to Large-Scale Comparison- and Radix-Sort 2014 SIGMOD 0.00011162682
6,174 Percentile Finding Algorithm for Multiple Sorted Runs 1989 VLDB 5.1696569e-05
930 Fast Sort on CPUs and GPUs: A Case for Bandwidth Oblivious SIMD Sort 2010 SIGMOD 0.00015238545
4,655 SIMD- and Cache-Friendly Algorithm for Sorting an Array of Structures 2015 VLDB 6.0221672e-05
11,832 A Study of Sorting Algorithms on Approximate Memory 2016 SIGMOD 4.1945683e-05
3,151 A Memory Bandwidth-Efficient Hybrid Radix Sort on GPUs 2017 SIGMOD 7.4720668e-05
11,481 Efficient String Sort with Multi-Character Encoding and Adaptive Sampling 2021 SIGMOD 4.1945683e-05