{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,24]],"date-time":"2025-07-24T11:44:38Z","timestamp":1753357478314},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2023,7]]},"abstract":"<jats:p>Query optimization is essential for the efficient execution of queries. The necessary analysis, if we can and should apply optimizations and transform the query plan, is already challenging. Traditional techniques focus on the availability of columns at individual operators, which does not scale for analysis of data flow through the query. Tracking available columns per operator takes quadratic space, which can result in multi-second optimization time for deep algebra trees. Instead, we need to re-think the na\u00efve algebra representation to efficiently support data flow analysis.<\/jats:p>\n          <jats:p>\n            In this paper, we introduce\n            <jats:italic>Indexed Algebra<\/jats:italic>\n            , a novel representation of relational algebra that makes common optimization tasks efficient. Indexed Algebra enables efficient reasoning with an auxiliary index structure based on link\/cut trees that support dynamic updates and queries in\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            ). This approach not only improves the asymptotic complexity, but also allows elegant and concise formulations for the data flow questions needed for query optimization. While large queries see theoretically unbounded improvements, Indexed Algebra also improves optimization time of the relatively harmless queries of TPC-H and TPC-DS by more than 1.8\u00d7.\n          <\/jats:p>","DOI":"10.14778\/3611479.3611505","type":"journal-article","created":{"date-parts":[[2023,8,25]],"date-time":"2023-08-25T02:08:08Z","timestamp":1692929288000},"page":"3018-3030","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Asymptotically Better Query Optimization Using Indexed Algebra"],"prefix":"10.14778","volume":"16","author":[{"given":"Philipp","family":"Fent","sequence":"first","affiliation":[{"name":"Technische Universit\u00e4t M\u00fcnchen"}]},{"given":"Guido","family":"Moerkotte","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Mannheim"}]},{"given":"Thomas","family":"Neumann","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t M\u00fcnchen"}]}],"member":"320","published-online":{"date-parts":[[2023,8,24]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.14778\/2336664.2336670"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3459244"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3190662"},{"key":"e_1_2_1_4_1","volume-title":"TPCTC (Lecture Notes in Computer Science)","author":"Boncz Peter A.","unstructured":"Peter A. Boncz , Thomas Neumann , and Orri Erling . 2013. TPC-H Analyzed: Hidden Messages and Lessons Learned from an Influential Benchmark . In TPCTC (Lecture Notes in Computer Science) , Vol. 8391 . Springer , 61--76. Peter A. Boncz, Thomas Neumann, and Orri Erling. 2013. TPC-H Analyzed: Hidden Messages and Lessons Learned from an Influential Benchmark. In TPCTC (Lecture Notes in Computer Science), Vol. 8391. Springer, 61--76."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687553.1687572"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Philipp Fent Altan Birler and Thomas Neumann. 2022. Practical planning and execution of groupjoin and nested aggregates. VLDB J. (2022).  Philipp Fent Altan Birler and Thomas Neumann. 2022. Practical planning and execution of groupjoin and nested aggregates. VLDB J. (2022).","DOI":"10.1007\/s00778-022-00765-x"},{"key":"e_1_2_1_7_1","volume-title":"Freitag and Thomas Neumann","author":"Michael","year":"2019","unstructured":"Michael J. Freitag and Thomas Neumann . 2019 . Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates . In CIDR. www.cidrdb.org. Michael J. Freitag and Thomas Neumann. 2019. Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates. In CIDR. www.cidrdb.org."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.273032"},{"key":"e_1_2_1_9_1","first-page":"19","article-title":"The Cascades Framework for Query Optimization","volume":"18","author":"Graefe Goetz","year":"1995","unstructured":"Goetz Graefe . 1995 . The Cascades Framework for Query Optimization . IEEE Data Eng. Bull. 18 , 3 (1995), 19 -- 29 . Goetz Graefe. 1995. The Cascades Framework for Query Optimization. IEEE Data Eng. Bull. 18, 3 (1995), 19--29.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_10_1","volume-title":"DeWitt","author":"Graefe Goetz","year":"1987","unstructured":"Goetz Graefe and David J . DeWitt . 1987 . The EXODUS Optimizer Generator. In SIGMOD. ACM Press , 160--172. Goetz Graefe and David J. DeWitt. 1987. The EXODUS Optimizer Generator. In SIGMOD. ACM Press, 160--172."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564705"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213024"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551801"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-020-00643-4"},{"key":"e_1_2_1_15_1","volume-title":"Klein and Shay Mozes","author":"Philip","year":"2021","unstructured":"Philip N. Klein and Shay Mozes . 2021 . Optimization Algorithms for Planar Graphs . https:\/\/planarity.org. Philip N. Klein and Shay Mozes. 2021. Optimization Algorithms for Planar Graphs. https:\/\/planarity.org."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882925"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_2_1_18_1","unstructured":"Zhenghua Lyu Huan Hubert Zhang Gang Xiong Gang Guo Haozhou Wang Jinbao Chen Asim Praveen Yu Yang Xiaoming Gao Alexandra Wang Wen Lin Ashwin Agrawal Junfeng Yang Hao Wu Xiaoliang Li Feng Guo Jiang Wu Jesse Zhang and Venkatesh Raghavan. 2021. Greenplum: A Hybrid Database for Transactional and Analytical Workloads. In SIGMOD. ACM 2530--2542.  Zhenghua Lyu Huan Hubert Zhang Gang Xiong Gang Guo Haozhou Wang Jinbao Chen Asim Praveen Yu Yang Xiaoming Gao Alexandra Wang Wen Lin Ashwin Agrawal Junfeng Yang Hao Wu Xiaoliang Li Feng Guo Jiang Wu Jesse Zhang and Venkatesh Raghavan. 2021. Greenplum: A Hybrid Database for Transactional and Analytical Workloads. In SIGMOD. ACM 2530--2542."},{"key":"e_1_2_1_19_1","volume-title":"BTW (LNI)","author":"May Norman","unstructured":"Norman May , Alexander B\u00f6hm , and Wolfgang Lehner . 2017. SAP HANA - The Evolution of an In-Memory DBMS from Pure OLAP Processing Towards Mixed Workloads . In BTW (LNI) , Vol. P-265 . GI , 545--563. Norman May, Alexander B\u00f6hm, and Wolfgang Lehner. 2017. SAP HANA - The Evolution of an In-Memory DBMS from Pure OLAP Processing Towards Mixed Workloads. In BTW (LNI), Vol. P-265. GI, 545--563."},{"key":"e_1_2_1_20_1","unstructured":"Guido Moerkotte. 2020. Building Query Compilers. http:\/\/pi3.informatik.uni-mannheim.de\/~moer\/querycompiler.pdf.  Guido Moerkotte. 2020. Building Query Compilers. http:\/\/pi3.informatik.uni-mannheim.de\/~moer\/querycompiler.pdf."},{"key":"e_1_2_1_21_1","unstructured":"Raghunath Othayoth Nambiar and Meikel Poess. 2006. The Making of TPC-DS. In VLDB. ACM 1049--1058.  Raghunath Othayoth Nambiar and Meikel Poess. 2006. The Making of TPC-DS. In VLDB. ACM 1049--1058."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/2002938.2002940"},{"key":"e_1_2_1_23_1","volume-title":"Reasoning in the Presence of NULLs","author":"Neumann Thomas","unstructured":"Thomas Neumann . 2018. Reasoning in the Presence of NULLs . In ICDE. IEEE Computer Society , 1682--1683. Thomas Neumann. 2018. Reasoning in the Presence of NULLs. In ICDE. IEEE Computer Society, 1682--1683."},{"key":"e_1_2_1_24_1","unstructured":"Thomas Neumann. 2020. Linear Time Liveness Analysis. https:\/\/databasearchitects.blogspot.com\/2020\/04\/linear-time-liveness-analysis.html.  Thomas Neumann. 2020. Linear Time Liveness Analysis. https:\/\/databasearchitects.blogspot.com\/2020\/04\/linear-time-liveness-analysis.html."},{"key":"e_1_2_1_25_1","unstructured":"Thomas Neumann. 2020. Taming Deep Recursion. https:\/\/databasearchitects.blogspot.com\/2020\/11\/taming-deep-recursion.html.  Thomas Neumann. 2020. Taming Deep Recursion. https:\/\/databasearchitects.blogspot.com\/2020\/11\/taming-deep-recursion.html."},{"key":"e_1_2_1_26_1","volume-title":"Freitag","author":"Neumann Thomas","year":"2020","unstructured":"Thomas Neumann and Michael J . Freitag . 2020 . Umbra : A Disk-Based System with In-Memory Performance. In CIDR. www.cidrdb.org. Thomas Neumann and Michael J. Freitag. 2020. Umbra: A Disk-Based System with In-Memory Performance. In CIDR. www.cidrdb.org."},{"key":"e_1_2_1_27_1","volume-title":"BTW (LNI)","author":"Neumann Thomas","unstructured":"Thomas Neumann and Alfons Kemper . 2015. Unnesting Arbitrary Queries . In BTW (LNI) , Vol. P-241 . GI , 383--402. Thomas Neumann and Alfons Kemper. 2015. Unnesting Arbitrary Queries. In BTW (LNI), Vol. P-241. GI, 383--402."},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Thomas Neumann and Bernhard Radke. 2018. Adaptive Optimization of Very Large Join Queries. In SIGMOD. ACM 677--692.  Thomas Neumann and Bernhard Radke. 2018. Adaptive Optimization of Very Large Join Queries. In SIGMOD. ACM 677--692.","DOI":"10.1145\/3183713.3183733"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007686"},{"key":"e_1_2_1_30_1","volume-title":"Gandiva Initiative: Improving SQL Performance by 70x. https:\/\/www.dremio.com\/gandiva-performance-improvements-production-query\/.","author":"Pindikura Ravindra","year":"2018","unstructured":"Ravindra Pindikura . 2018 . Gandiva Initiative: Improving SQL Performance by 70x. https:\/\/www.dremio.com\/gandiva-performance-improvements-production-query\/. Ravindra Pindikura. 2018. Gandiva Initiative: Improving SQL Performance by 70x. https:\/\/www.dremio.com\/gandiva-performance-improvements-production-query\/."},{"key":"e_1_2_1_31_1","volume-title":"SIGMOD Conference. ACM, 23--34","author":"Selinger Patricia G.","unstructured":"Patricia G. Selinger , Morton M. Astrahan , Donald D. Chamberlin , Raymond A. Lorie , and Thomas G. Price . 1979. Access Path Selection in a Relational Database Management System . In SIGMOD Conference. ACM, 23--34 . Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, and Thomas G. Price. 1979. Access Path Selection in a Relational Database Management System. In SIGMOD Conference. ACM, 23--34."},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Hesam Shahrokhi and Amir Shaikhha. 2023. Building a Compiled Query Engine in Python. In CC. ACM 180--190.  Hesam Shahrokhi and Amir Shaikhha. 2023. Building a Compiled Query Engine in Python. In CC. ACM 180--190.","DOI":"10.1145\/3578360.3580264"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915244"},{"key":"e_1_2_1_34_1","unstructured":"Daniel Dominic Sleator. 2011. Submission #860934 - Codeforces. https:\/\/codeforces.com\/contest\/117\/submission\/860934.  Daniel Dominic Sleator. 2011. Submission #860934 - Codeforces. https:\/\/codeforces.com\/contest\/117\/submission\/860934."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90006-5"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3835"},{"key":"e_1_2_1_37_1","unstructured":"Mohamed A. Soliman Lyublena Antova Venkatesh Raghavan Amr El-Helw Zhongxian Gu Entong Shen George C. Caragea Carlos Garcia-Alvarado Foyzur Rahman Michalis Petropoulos Florian Waas Sivaramakrishnan Narayanan Konstantinos Krikellas and Rhonda Baldwin. 2014. Orca: a modular query optimizer architecture for big data. In SIGMOD. ACM 337--348.  Mohamed A. Soliman Lyublena Antova Venkatesh Raghavan Amr El-Helw Zhongxian Gu Entong Shen George C. Caragea Carlos Garcia-Alvarado Foyzur Rahman Michalis Petropoulos Florian Waas Sivaramakrishnan Narayanan Konstantinos Krikellas and Rhonda Baldwin. 2014. Orca: a modular query optimizer architecture for big data. In SIGMOD. ACM 337--348."},{"key":"e_1_2_1_38_1","volume-title":"Revisited. In SIGMOD Conference. ACM, 307--322","author":"Tahboub Ruby Y.","year":"2018","unstructured":"Ruby Y. Tahboub , Gr\u00e9gory M. Essertel , and Tiark Rompf . 2018 . How to Architect a Query Compiler , Revisited. In SIGMOD Conference. ACM, 307--322 . Ruby Y. Tahboub, Gr\u00e9gory M. Essertel, and Tiark Rompf. 2018. How to Architect a Query Compiler, Revisited. In SIGMOD Conference. ACM, 307--322."},{"key":"e_1_2_1_39_1","first-page":"1","article-title":"Get Real: How Benchmarks Fail to Represent the Real World. In DBTest@SIGMOD","volume":"1","author":"Vogelsgesang Adrian","year":"2018","unstructured":"Adrian Vogelsgesang , Michael Haubenschild , Jan Finis , Alfons Kemper , Viktor Leis , Tobias M\u00fchlbauer , Thomas Neumann , and Manuel Then . 2018 . Get Real: How Benchmarks Fail to Represent the Real World. In DBTest@SIGMOD . ACM , 1 : 1 -- 1 :6. Adrian Vogelsgesang, Michael Haubenschild, Jan Finis, Alfons Kemper, Viktor Leis, Tobias M\u00fchlbauer, Thomas Neumann, and Manuel Then. 2018. Get Real: How Benchmarks Fail to Represent the Real World. In DBTest@SIGMOD. ACM, 1:1--1:6.","journal-title":"ACM"},{"key":"e_1_2_1_40_1","volume-title":"BTW (LNI)","author":"Vogelsgesang Adrian","unstructured":"Adrian Vogelsgesang , Tobias M\u00fchlbauer , Viktor Leis , Thomas Neumann , and Alfons Kemper . 2019. Domain Query Optimization: Adapting the General-Purpose Database System Hyper for Tableau Workloads . In BTW (LNI) , Vol. P-289 . Gesellschaft f\u00fcr Informatik, Bonn , 313--333. Adrian Vogelsgesang, Tobias M\u00fchlbauer, Viktor Leis, Thomas Neumann, and Alfons Kemper. 2019. Domain Query Optimization: Adapting the General-Purpose Database System Hyper for Tableau Workloads. In BTW (LNI), Vol. P-289. Gesellschaft f\u00fcr Informatik, Bonn, 313--333."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3611479.3611505","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,23]],"date-time":"2023-09-23T22:23:31Z","timestamp":1695507811000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3611479.3611505"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7]]},"references-count":40,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2023,7]]}},"alternative-id":["10.14778\/3611479.3611505"],"URL":"https:\/\/doi.org\/10.14778\/3611479.3611505","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,7]]},"assertion":[{"value":"2023-08-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}