{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T10:41:01Z","timestamp":1782902461367,"version":"3.54.5"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2006,12]]},"abstract":"<jats:p>Rank-aware query processing has emerged as a key requirement in modern applications. In these applications, efficient and adaptive evaluation of top-<jats:italic>k<\/jats:italic>queries 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-<jats:italic>k<\/jats:italic>queries 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-<jats:italic>k<\/jats:italic>query 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.<\/jats:p>","DOI":"10.1145\/1189769.1189772","type":"journal-article","created":{"date-parts":[[2007,1,16]],"date-time":"2007-01-16T19:38:29Z","timestamp":1168976309000},"page":"1257-1304","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":44,"title":["Adaptive rank-aware query optimization in relational databases"],"prefix":"10.1145","volume":"31","author":[{"given":"Ihab F.","family":"Ilyas","sequence":"first","affiliation":[{"name":"University of Waterloo, Waterloo, Ontario, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Walid G.","family":"Aref","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, IN"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ahmed K.","family":"Elmagarmid","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, IN"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hicham G.","family":"Elmongui","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, IN"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rahul","family":"Shah","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, IN"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jeffrey Scott","family":"Vitter","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, IN"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2006,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Amsaleg L. Franklin M. J. Tomasic A. and Urhan T. 1996. Scrambling query plans to cope with unexpected delays. Distrib. Parall. Datab. Syst. 208--219. Amsaleg L. Franklin M. J. Tomasic A. and Urhan T. 1996. Scrambling query plans to cope with unexpected delays. Distrib. Parall. Datab. Syst. 208--219.","DOI":"10.1109\/PDIS.1996.568681"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335420"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564722"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/568518.568519"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 18th International Conference on Data Engineering. 153--187","author":"Bruno N.","unstructured":"Bruno , N. , Gravano , L. , and Marian , A . 2002. Evaluating top-k queries over web-accessible databases . In Proceedings of the 18th International Conference on Data Engineering. 153--187 . Bruno, N., Gravano, L., and Marian, A. 2002. Evaluating top-k queries over web-accessible databases. In Proceedings of the 18th International Conference on Data Engineering. 153--187."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253302"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 24th International Conference on Very Large Data Bases. 158--169","author":"Carey M. J.","unstructured":"Carey , M. J. and Kossmann , D . 1998. Reducing the braking distance of an SQL query engine . In Proceedings of the 24th International Conference on Very Large Data Bases. 158--169 . Carey, M. J. and Kossmann, D. 1998. Reducing the braking distance of an SQL query engine. In Proceedings of the 24th International Conference on Very Large Data Bases. 158--169."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2004.1269602"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564731"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 30 International Conference on Very Large Data Bases. 948--959","author":"Deshpande A.","unstructured":"Deshpande , A. and Hellerstein , J. M . 2004. Lifting the burden of history from adaptive query processing . In Proceedings of the 30 International Conference on Very Large Data Bases. 948--959 . Deshpande, A. and Hellerstein, J. M. 2004. Lifting the burden of history from adaptive query processing. In Proceedings of the 30 International Conference on Very Large Data Bases. 948--959."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 25th International Conference on Very Large Data Bases.","author":"Donjerkovic D.","unstructured":"Donjerkovic , D. and Ramakrishnan , R . 1999. Probabilistic optimization of top N queries . In Proceedings of the 25th International Conference on Very Large Data Bases. Donjerkovic, D. and Ramakrishnan, R. 1999. Probabilistic optimization of top N queries. In Proceedings of the 25th International Conference on Very Large Data Bases."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/371920.372165"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1600"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/375551.375567"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/38713.38734"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/645478.757691"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 26th International Conference on Very Large Data Bases. 419--428","author":"G\u00fcntzer U.","unstructured":"G\u00fcntzer , U. , Balke , W.-T. , and Kie\u00dfling , W . 2000. Optimizing multi-feature queries for image databases . In Proceedings of the 26th International Conference on Very Large Data Bases. 419--428 . G\u00fcntzer, U., Balke, W.-T., and Kie\u00dfling, W. 2000. Optimizing multi-feature queries for image databases. In Proceedings of the 26th International Conference on Very Large Data Bases. 419--428."},{"key":"e_1_2_1_18_1","volume-title":"International Symposium on Information Technology (ITCC). 622--628","author":"G\u00fcntzer U.","unstructured":"G\u00fcntzer , U. , Balke , W.-T. , and Kie\u00dfling , W . 2001. Towards efficient multi-feature queries in heterogeneous environments . In International Symposium on Information Technology (ITCC). 622--628 . G\u00fcntzer, U., Balke, W.-T., and Kie\u00dfling, W. 2001. Towards efficient multi-feature queries in heterogeneous environments. In International Symposium on Information Technology (ITCC). 622--628."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304208"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01277518"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 29th International Conference on Very Large Data Bases.","author":"Hristidis V.","unstructured":"Hristidis , V. , Gravano , L. , and Papakonstantinou , Y . 2003. Efficient IR-style keyword search over relational databases . In Proceedings of the 29th International Conference on Very Large Data Bases. Hristidis, V., Gravano, L., and Papakonstantinou, Y. 2003. Efficient IR-style keyword search over relational databases. In Proceedings of the 29th International Conference on Very Large Data Bases."},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 28th International Conference on Very Large Data Bases. 950--961","author":"Ilyas I. F.","unstructured":"Ilyas , I. F. , Aref , W. G. , and Elmagarmid , A. K . 2002. Joining ranked inputs in practice . In Proceedings of the 28th International Conference on Very Large Data Bases. 950--961 . Ilyas, I. F., Aref, W. G., and Elmagarmid, A. K. 2002. Joining ranked inputs in practice. In Proceedings of the 28th International Conference on Very Large Data Bases. 950--961."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 29th International Conference on Very Large Data Bases. 754--765","author":"Ilyas I. F.","unstructured":"Ilyas , I. F. , Aref , W. G. , and Elmagarmid , A. K . 2003. Supporting top-k join queries in relational databases . In Proceedings of the 29th International Conference on Very Large Data Bases. 754--765 . Ilyas, I. F., Aref, W. G., and Elmagarmid, A. K. 2003. Supporting top-k join queries in relational databases. In Proceedings of the 29th International Conference on Very Large Data Bases. 754--765."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-004-0128-2"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007593"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276315"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066173"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/50202.50204"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007642"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 27th International Conference on Very Large Data Bases. 281--290","author":"Natsev A.","unstructured":"Natsev , A. , Chang , Y.-C. , Smith , J. R. , Li , C.-S. , and Vitter , J. S . 2001. Supporting incremental join queries on ranked inputs . In Proceedings of the 27th International Conference on Very Large Data Bases. 281--290 . Natsev, A., Chang, Y.-C., Smith, J. R., Li, C.-S., and Vitter, J. S. 2001. Supporting incremental join queries on ranked inputs. In Proceedings of the 27th International Conference on Very Large Data Bases. 281--290."},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 15th International Conference on Data Engineering. 22--29","author":"Nepal S.","unstructured":"Nepal , S. and Ramakrishna , M. V . 1999. Query processing issues in image (multimedia) databases . In Proceedings of the 15th International Conference on Data Engineering. 22--29 . Nepal, S. and Ramakrishna, M. V. 1999. Query processing issues in image (multimedia) databases. In Proceedings of the 15th International Conference on Data Engineering. 22--29."},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 19th International Conference on Data Engineering. 353--387","author":"Raman V.","unstructured":"Raman , V. , Deshpande , A. , and Hellerstein , J. M . 2003. Using state modules for adaptive query processing . In Proceedings of the 19th International Conference on Data Engineering. 353--387 . Raman, V., Deshpande, A., and Hellerstein, J. M. 2003. Using state modules for adaptive query processing. In Proceedings of the 19th International Conference on Data Engineering. 353--387."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/582095.582099"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 27th International Conference on Very Large Data Bases. 19--28","author":"Stillger M.","unstructured":"Stillger , M. , Lohman , G. M. , Markl , V. , and Kandil , M . 2001. LEO---DB2's learning optimizer . In Proceedings of the 27th International Conference on Very Large Data Bases. 19--28 . Stillger, M., Lohman, G. M., Markl, V., and Kandil, M. 2001. LEO---DB2's learning optimizer. In Proceedings of the 27th International Conference on Very Large Data Bases. 19--28."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276317"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01277522"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007617"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1189769.1189772","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,13]],"date-time":"2025-01-13T00:40:37Z","timestamp":1736728837000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1189769.1189772"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,12]]},"references-count":37,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2006,12]]}},"alternative-id":["10.1145\/1189769.1189772"],"URL":"https:\/\/doi.org\/10.1145\/1189769.1189772","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,12]]},"assertion":[{"value":"2006-12-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}