Optimizing Ranked Retrieval

Ranked retrieval plays an important role in explorative querying, where the user is interested in the top k results of complex ad-hoc queries. In such a scenario, response times are very important, but at the same time, tuning techniques, such as materialized views, are hard to use. However, it would be highly desirable for the query optimizer to exploit the top-k property of the query, i.e., to optimize query execution such that the top-k results are produced as fast as possible. We present a novel approach to optimize ad-hoc top-k queries, extending the classical approach of equivalent rewrites by explicitly exploiting the top-k nature of the queries for performance optimizations. Our experimental results support our claim that integrating top-k processing into algebraic optimization greatly reduces the query execution times and provides strong evidence that the resulting execution plans are robust against statistical misestimations