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: 5944
Venue: SIGMOD
Year: 2020
Pagerank: 4.3920263e-05
Overall Rank: 9,123 | 36.54%
DOI: 10.1145/3318464.3389729

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,970	Relational Algorithms for Top-k Query Evaluation	2024	SIGMOD	4.1945683e-05
11,142	Cache-Efficient Top-k Aggregation over High Cardinality Large Datasets	2024	VLDB	4.1945683e-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
84	AlphaSort: A RISC Machine Sort	1994	SIGMOD	0.00053866006
102	The Case for Learned Index Structures	2018	SIGMOD	0.00049545203
540	Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs	2011	SIGMOD	0.0002063443
638	On B-tree Indices for Skewed Distributions	1992	VLDB	0.00018798677
826	ALEX: An Updatable Adaptive Learned Index	2020	SIGMOD	0.00016224841
907	Fundamental Techniques for Order Optimization	1996	SIGMOD	0.00015435983
1,262	RankSQL: Query Algebra and Optimization for Relational Top-k Queries	2005	SIGMOD	0.00012986539
1,789	Reducing the Braking Distance of an SQL Query Engine	1998	VLDB	0.00010555087
2,732	Efficiently Searching In-Memory Sorted Arrays: Revenge of the Interpolation Search?	2019	SIGMOD	8.2087602e-05
3,355	F1 Query: Declarative Querying at Scale	2018	VLDB	7.1829142e-05
4,700	Schedule Optimization for Data Processing Flows on the Cloud	2011	SIGMOD	5.9882572e-05
7,551	Efficient Top-K Query Processing on Massively Parallel Hardware	2018	SIGMOD	4.7134746e-05
9,113	Optimal Score Aggregation Algorithms	2016	PODS	4.3938681e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,111	Optimal Top-k Generation of Attribute Combinations based on Ranked Lists	2012	SIGMOD	4.1945683e-05
2,009	IO-Top-k: Index-access Optimized Top-k Query Processing	2006	VLDB	9.7977564e-05
11,825	Efficient Top-k Indexing via General Reductions	2016	PODS	4.1945683e-05
3,665	Ad-hoc Top-k Query Answering for Data Streams	2007	VLDB	6.8633354e-05
11,965	A Dynamic I/O-Efficient Structure for One-Dimensional Top-k Range Reporting	2014	PODS	4.1945683e-05
1,784	Continuous Monitoring of Top-k Queries over Sliding Windows	2006	SIGMOD	0.00010567363
4,741	Memory-Adaptive External Sorting	1993	VLDB	5.95905e-05
7,963	Efficient Top-K Processing Over Query-Dependent Functions	2008	VLDB	4.613363e-05
7,846	Dynamic Top-K Range Reporting in External Memory	2012	PODS	4.6365341e-05
7,692	Processing Top-k Join Queries	2010	VLDB	4.6761366e-05