Adaptive rank-aware query optimization in relational databases
Authors:
Open Access
- 1 December 2006
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Database Systems
- Vol. 31 (4) , 1257-1304
Abstract
Rank-aware query processing has emerged as a key requirement in modern applications. In these applications, efficient and adaptive evaluation of top-kqueries is an integral part of the application semantics. In this article, we introduce a rank-aware query optimization framework that fully integrates rank-join operators into relational query engines. The framework is based on extending the System R dynamic programming algorithm in both enumeration and pruning. We define ranking as an interesting physical property that triggers the generation of rank-aware query plans. Unlike traditional join operators, optimizing for rank-join operators depends on estimating the input cardinality of these operators. We introduce a probabilistic model for estimating the input cardinality, and hence the cost of a rank-join operator. To our knowledge, this is the first effort in estimating the needed input size for optimal rank aggregation algorithms. Costing ranking plans is key to the full integration of rank-join operators in real-world query processing engines.Since optimal execution strategies picked by static query optimizers lose their optimality due to estimation errors and unexpected changes in the computing environment, we introduce several adaptive execution strategies for top-kqueries that respond to these unexpected changes and costing errors. Our reactive reoptimization techniques change the execution plan at runtime to significantly enhance the performance of running queries. Since top-kquery plans are usually pipelined and maintain a complex ranking state, altering the execution strategy of a running ranking query is an important and challenging task.We conduct an extensive experimental study to evaluate the performance of the proposed framework. The experimental results are twofold: (1) we show the effectiveness of our cost-based approach of integrating ranking plans in dynamic programming cost-based optimizers; and (2) we show a significant speedup (up to 300%) when using our adaptive execution of ranking plans over the state-of-the-art mid-query reoptimization strategies.Keywords
This publication has 30 references indexed in Scilit:
- Supporting top-k join queries in relational databasesThe VLDB Journal, 2004
- Evaluating refined queries in top-k retrieval systemsIEEE Transactions on Knowledge and Data Engineering, 2004
- Lifting the Burden of History from Adaptive Query Processing2004
- Supporting Top-k Join Queries in Relational Databases2003
- Optimal aggregation algorithms for middleware2001
- Ripple joins for online aggregation1999
- Combining Fuzzy Information from Multiple SystemsJournal of Computer and System Sciences, 1999
- Cost-based query scrambling for initial delays1998
- Dataflow query execution in a parallel main-memory environmentDistributed and Parallel Databases, 1993
- Optimization of parallel query execution plans in XPRSDistributed and Parallel Databases, 1993