Enabling Cost-based Optimization for Top-k Queries: 
                   A Unified Framework

This talk presents cost-based optimization for top-k queries. While
``taken for granted'' for SQL, such techniques are clearly missing for
top-k queries. By dynamic search over a space of algorithms,
cost-based optimization is general across a wide range of access
scenarios, yet adaptive to the specific one at run time.

Enabling such optimization is challenging: To begin with, what is the
space of algorithms to search over? Such a space must be both
general, to encompass all comparable algorithms, and specific, to
enable efficient search. Further, how to actually optimize in this
space? I will describe our framework, which achieves these goals. With
dynamic cost-based optimization, this framework indeed unifies the
existing algorithms, by adapting to their specific scenarios, and
further, generalizing beyond their unexplained heuristics.