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 , Divesh Srivastava, Tree Pattern Relaxation, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.496-513, March 25-27, 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 , Luis Gravano, Top-k selection queries over relational databases: Mapping strategies and performance evaluation, ACM Transactions on Database Systems (TODS), v.27 n.2, p.153-187, June 2002 [doi>10.1145/568518.568519]
• 4: Nicolas Bruno, Luis Gravano, and Amelie Marian. Evaluating top-k queries over web-accessible databases. In ICDE, 2002.
• 5: Michael J. Carey , Donald Kossmann, Reducing the Braking Distance of an SQL Query Engine, Proceedings of the 24rd International Conference on Very Large Data Bases, p.158-169, August 24-27, 1998
• 6: Michael J. Carey , Donald Kossmann, On saying “Enough already!” in SQL, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.219-230, May 11-15, 1997, Tucson, Arizona, United States
• 7: Kevin Chen-Chuan Chang , Seung-won Hwang, Minimal probing: supporting expensive predicates for top-k queries, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564731]
• 8: Yuan-Chi Chang , Lawrence Bergman , Vittorio Castelli , Chung-Sheng Li , Ming-Ling Lo , John R. Smith, The onion technique: indexing for linear optimization queries, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.391-402, May 15-18, 2000, Dallas, Texas, United States
• 9: Surajit Chaudhuri , Luis Gravano , Amelie Marian, Optimizing Top-k Selection Queries over Multimedia Repositories, IEEE Transactions on Knowledge and Data Engineering, v.16 n.8, p.992-1009, August 2004 [doi>10.1109/TKDE.2004.30]
• 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 , Raghu Ramakrishnan, Probabilistic Optimization of Top N Queries, Proceedings of the 25th International Conference on Very Large Data Bases, p.411-422, September 07-10, 1999
• 12: Cynthia Dwork , Ravi Kumar , Moni Naor , D. Sivakumar, Rank aggregation methods for the Web, Proceedings of the 10th international conference on World Wide Web, p.613-622, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372165]
• 13: Ronald Fagin, Combining fuzzy information from multiple systems, Journal of Computer and System Sciences, v.58 n.1, p.83-99, Feb. 1999 [doi>10.1006/jcss.1998.1600]
• 14: Ronald Fagin , Amnon Lotem , Moni Naor, Optimal aggregation algorithms for middleware, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.102-113, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375567]
• 15: Goetz Graefe , William J. McKenna, The Volcano Optimizer Generator: Extensibility and Efficient Search, Proceedings of the Ninth International Conference on Data Engineering, p.209-218, April 19-23, 1993
• 16: Goetz Graefe , David J. DeWitt, The EXODUS optimizer generator, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.160-172, May 27-29, 1987, San Francisco, California, United States
• 17: Ulrich Güntzer , Wolf-Tilo Balke , Werner Kießling, Optimizing Multi-Feature Queries for Image Databases, Proceedings of the 26th International Conference on Very Large Data Bases, p.419-428, September 10-14, 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 , Joseph M. Hellerstein, Ripple joins for online aggregation, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.287-298, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 20: Wei Hong , Michael Stonebraker, Optimization of parallel query execution plans in XPRS, Distributed and Parallel Databases, v.1 n.1, p.9-32, Jan. 1993 [doi>10.1007/BF01277518]
• 21: Vagelis Hristidis, Luis Gravano, and Yannis Papakonstantinou. Efficient ir-style keyword search over relational databases. In VLDB, 2003.
• 22: Vagelis Hristidis , Nick Koudas , Yannis Papakonstantinou, PREFER: a system for the efficient execution of multi-parametric ranked queries, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.259-270, May 21-24, 2001, Santa Barbara, California, United States
• 23: Ihab F. Ilyas, Walid G. Aref, and Ahmed K. Elmagarmid. Joining ranked inputs in practice. In VLDB, 2002.
• 24: F. Ilyas , G. Aref , K. Elmagarmid, Supporting top-k join queries in relational databases, The VLDB Journal — The International Journal on Very Large Data Bases, v.13 n.3, p.207-221, September 2004 [doi>10.1007/s00778-004-0128-2]
• 25: Guy M. Lohman, Grammar-like functional rules for representing query optimization alternatives, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.18-27, June 01-03, 1988, Chicago, Illinois, United States
• 26: Apostol Natsev , Yuan-Chi Chang , John R. Smith , Chung-Sheng Li , Jeffrey Scott Vitter, Supporting Incremental Join Queries on Ranked Inputs, Proceedings of the 27th International Conference on Very Large Data Bases, p.281-290, September 11-14, 2001
• 27: Surya Nepal and M. V. Ramakrishna. Query processing issues in image (multimedia) databases. In ICDE, 1999.
• 28: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• 29: Panayiotis Tsaparas, Themistoklis Palpanas, Yannis Kotidis, Nick Koudas, and Divesh Srivastava. Ranked join indices. In ICDE, 2003.
• 30: Annita N. Wilschut , Peter M. G. Apers, Dataflow query execution in a parallel main-memory environment, Distributed and Parallel Databases, v.1 n.1, p.103-128, Jan. 1993 [doi>10.1007/BF01277522]