A general and efficient algorithm for “top” queries
Goetz Graefe · 2008
"Top K" queries reduce a query result to the most interesting or the most urgent items. In many cases, e.g., when the result size is unbounded due to duplicate key values, a "top" operation cannot be implemented using the standard algorithm based on an in-memory priority queue. The default alternative is a full sort. External merge sort admits multiple novel optimizations specific to "top" operations. These are simple to implement yet greatly reduce the data volume written to runs on temporary storage. Experiments demonstrate substantial performance improvements, in one case exceeding three orders of magnitude.