External Merge Sort for Top-K Queries: Eager input filtering guided by histograms

Summary: Introduces an external top-k algorithm with histogram-guided eager filtering to prune input before sorting, even when memory is insufficient. Implemented in F1 Query; reduces I/O and yields up to 11× speedup over external sorts in production. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6006
Venue: SIGMOD
Year: 2020
Pagerank: 5.3092396e-05
Overall Rank: 9,172 | 37.08%
DOI: 10.1145/3318464.3389729

Incoming Non-self Citations Over Time

Authors

1. Yannis Chronis (Google; University of Wisconsin)
2. Thanh Do (Google)
3. Goetz Graefe (Google)
4. Keith Peters (Google)

BibTeX Citation

@inproceedings{chronis_sigmod20,
        title = {{External Merge Sort for Top-K Queries: Eager input filtering guided by histograms}},
        author = {Chronis, Yannis and Do, Thanh and Graefe, Goetz and Peters, Keith},
        series = {{SIGMOD} '20},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3318464.3389729},
        url = {https://dl.acm.org/doi/10.1145/3318464.3389729},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
11,183	Relational Algorithms for Top-k Query Evaluation	2024	SIGMOD	5.093636e-05
11,348	Cache-Efficient Top-k Aggregation over High Cardinality Large Datasets	2024	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
43	The Case for Learned Index Structures	2018	SIGMOD	0.00046060254
215	AlphaSort: A RISC Machine Sort	1994	SIGMOD	0.00024507963
360	Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs	2011	SIGMOD	0.00020182846
447	ALEX: An Updatable Adaptive Learned Index	2020	SIGMOD	0.00018322593
744	Fundamental Techniques for Order Optimization	1996	SIGMOD	0.00014411295
973	RankSQL: Query Algebra and Optimization for Relational Top-k Queries	2005	SIGMOD	0.00012874284
1,059	On B-tree Indices for Skewed Distributions	1992	VLDB	0.00012377809
1,544	Reducing the Braking Distance of an SQL Query Engine	1998	VLDB	0.00010410466
2,222	Efficiently Searching In-Memory Sorted Arrays: Revenge of the Interpolation Search?	2019	SIGMOD	8.9255716e-05
2,889	F1 Query: Declarative Querying at Scale	2018	VLDB	7.9935046e-05
4,117	Schedule Optimization for Data Processing Flows on the Cloud	2011	SIGMOD	6.8919486e-05
7,370	Efficient Top-K Query Processing on Massively Parallel Hardware	2018	SIGMOD	5.6313494e-05
9,251	Optimal Score Aggregation Algorithms	2016	PODS	5.2978375e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,308	Optimal Top-k Generation of Attribute Combinations based on Ranked Lists	2012	SIGMOD
2	1,967	IO-Top-k: Index-access Optimized Top-k Query Processing	2006	VLDB
3	12,028	Efficient Top-k Indexing via General Reductions	2016	PODS
4	3,317	Ad-hoc Top-k Query Answering for Data Streams	2007	VLDB
5	12,163	A Dynamic I/O-Efficient Structure for One-Dimensional Top-k Range Reporting	2014	PODS
6	1,513	Continuous Monitoring of Top-k Queries over Sliding Windows	2006	SIGMOD
7	8,281	Efficient Top-K Processing Over Query-Dependent Functions	2008	VLDB
8	4,708	Memory-Adaptive External Sorting	1993	VLDB
9	8,173	Dynamic Top-K Range Reporting in External Memory	2012	PODS
10	7,550	Processing Top-k Join Queries	2010	VLDB