Rank-aware query optimization

ABSTRACT

Ranking is an important property that needs to be fully supported by current relational query engines. Recently, several rank-join query operators have been proposed based on rank aggregation algorithms. Rank-join operators progressively rank the join results while performing the join operation. The new operators have a direct impact on traditional query processing and optimization.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 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 paper is the first effort in estimating the needed input size for optimal rank aggregation algorithms. Costing ranking plans, although challenging, is key to the full integration of rank-join operators in real-world query processing engines. We experimentally evaluate our framework by modifying the query optimizer of an open-source database management system. The experiments show the validity of our framework and the accuracy of the proposed estimation model.

References

1. Sihem Amer-Yahia, SungRan Cho, and Divesh Srivastava. Tree pattern relaxation. In EDBT, 2002.
2. J.C. Borda. M.émoire sur les élections au scrutin. Histoire de l'Académie Royale des Sciences, 1781.
3. Nicolas Bruno, Surajit Chaudhuri, and Luis Gravano. Top-k selection queries over relational databases: Mapping strategies and performance evaluation. TODS, 27(2), 2002.
4. Nicolas Bruno, Luis Gravano, and Amelie Marian. Evaluating top-k queries over web-accessible databases. In ICDE, 2002.
5. Michael J. Carey and Donald Kossmann. Reducing the braking distance of an SQL query engine. In VLDB.
6. Michael J. Carey and Donald Kossmann. On saying "Enough already!" in SQL. In SIGMOD, 1997.
7. Kevin Chen-Chuan Chang and Seung won Hwang. Minimal probing: supporting expensive predicates for top-k queries. In SIGMOD, 2002.
8. Yuan-Chi Chang, Lawrence Bergman, Vittorio Castelli, Chung-Sheng Li, Ming-Ling Lo, and John R. Smith. The onion technique: indexing for linear optimization queries. In SIGMOD, pages 391--402, 2000.
9. Surajit Chaudhuri, Luis Gravano, and Amelie Marian. Optimizing top-k selection queries over multimedia repositories. IEEE Transactions on Knowledge and Data Engineering, to appear.
10. M.-J. Condorcet. Éssai sur l'application de l'analyse à la probabilité des décisions rendues à la puralité des voix, 1785.
11. Donko Donjerkovic and Raghu Ramakrishnan. Probabilistic optimization of top N queries. In VLDB, 1999.
12. Cynthia Dwork, S. Ravi Kumar, Moni Naor, and D. Sivakumar. Rank aggregation methods for the web. In World Wide Web, 2001.
13. Ronald Fagin. Combining fuzzy information from multiple systems. Journal of Computer and System Sciences (JCSS), 58(1), Feb 1999.
14. Ronald Fagin, Amnon Lotem, and Moni Naor. Optimal aggregation algorithms for middleware. In PODS, Santa Barbara, California, May 2001.
15. G. Graefe and W. J. McKenna. The volcano optimizer generator: Extensibility and efficient search. In ICDE, 1993.
16. Goetz Graefe and David J. DeWitt. The exodus optimizer generator. In SIGMOD, 1987.
17. Ulrich Güntzer, Wolf-Tilo Balke, and Werner Kießling. Optimizing multi-feature queries for image databases. In VLDB, 2000.
18. Ulrich Güntzer, Wolf-Tilo Balke, and Werner Kießling. Towards efficient multi-feature queries in heterogeneous environments. In ITCC, 2001.
19. Peter J. Haas and Joseph M. Hellerstein. Ripple joins for online aggregation. In SIGMOD, june 1999.
20. W. Hong and M. Stonebraker. Optimization of parallel query execution plans in XPRS. Distributed and Parallel Databases, 1(1), Jan. 1993.
21. Vagelis Hristidis, Luis Gravano, and Yannis Papakonstantinou. Efficient ir-style keyword search over relational databases. In VLDB, 2003.
22. Vagelis Hristidis, Nick Koudas, and Yannis Papakonstantinou. Prefer: A system for the efficient execution of multi-parametric ranked queries. In SIGMOD, 2001.
23. Ihab F. Ilyas, Walid G. Aref, and Ahmed K. Elmagarmid. Joining ranked inputs in practice. In VLDB, 2002.
24. Ihab F. Ilyas, Walid G. Aref, and Ahmed K. Elmagarmid. Supporting top-k join queries in relational databases. In VLDB, 2003.
25. Guy M. Lohman. Grammar-like functional rules for representing query optimization alternatives. In SIGMOD, 1988.
26. Apostol Natsev, Yuan-Chi Chang, John R. Smith, Chung-Sheng Li, and Jeffrey S. Vitter. Supporting incremental join queries on ranked inputs. In VLDB, 2001.
27. Surya Nepal and M. V. Ramakrishna. Query processing issues in image (multimedia) databases. In ICDE, 1999.
28. P. G. Selinger, M. M. Astrahan, D. D. Chamberlin, R. A. Lorie, and T. G. Price. Access path election in a relational database management system. In SIGMOD, 1979.
29. Panayiotis Tsaparas, Themistoklis Palpanas, Yannis Kotidis, Nick Koudas, and Divesh Srivastava. Ranked join indices. In ICDE, 2003.
30. Annita N. Wilschut and Peter M. G. Apers. Dataflow query execution in a parallel main-memory environment. Distributed and Parallel Databases, 1(1), 1993.

• Information systems

  • Data management systems

    • Database management system engines

  • Information retrieval

• Theory of computation

  • Theory and algorithms for application domains

    • Database theory