Multi-Criteria Query Optimization in the Presence of Result Size and Quality Tradeoffs

In this paper, we present novel multi-criteria query optimization techniques for performing query optimization in databases, such as multimedia and web databases, which rely on imperfect access mechanisms and top-k predicates. We present an optimization model that (1) takes into account different binding patterns associated with query predicates, (2) considers the variations in the expected query result sizes as a function of query execution plans, and (3) considers the expected result qualities of the execution orders. We address the complexity and the well-known NP-complete nature of the query optimization problem by adaptively reducing the granularity of the search space. For this purpose, unlike the data histograms which capture the data distribution, we propose opt-histograms that capture the distribution of sub-query-plan values over many optimization tasks.