{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:50:13Z","timestamp":1773481813742,"version":"3.50.1"},"reference-count":59,"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>\n            There have been many decades of work on optimizing query processing in database management systems. Recently, modern machine learning (ML), and specifically reinforcement learning (RL), has gained increased attention as a means to develop a query optimizer (QO). In this work, we take a closer look at two recent state-of-the-art (SOTA) RL-based QO methods to better understand their behavior. We find that these RL-based methods do not generalize as well as it seems at first glance. Thus, we ask a simple question:\n            <jats:italic>How do SOTA RL-based QOs compare to a simple, modern, adaptive query processing approach?<\/jats:italic>\n            To answer this question, we choose two simple adaptive query processing techniques and implemented them in PostgreSQL. The first adapts an individual join operation on-the-fly and switches between a Nested Loop Join algorithm and a Hash Join algorithm to avoid sub-optimal join algorithm decisions. The second is a technique called\n            <jats:italic>Lookahead Information Passing<\/jats:italic>\n            (LIP), in which adaptive semijoin techniques are used to make a pipeline of join operations execute efficiently. To our surprise, we find that this simple adaptive query processing approach is not only competitive to the SOTA RL-based approaches but, in some cases, outperforms the RL-based approaches. The adaptive approach is also appealing because it does not require an expensive training step, and it is fully interpretable compared to the RL-based QO approaches. Further, the adaptive method works across complex query constructs that RL-based QO methods currently cannot optimize.\n          <\/jats:p>","DOI":"10.14778\/3611479.3611501","type":"journal-article","created":{"date-parts":[[2023,8,25]],"date-time":"2023-08-25T02:08:08Z","timestamp":1692929288000},"page":"2962-2975","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Simple Adaptive Query Processing vs. Learned Query Optimizers: Observations and Analysis"],"prefix":"10.14778","volume":"16","author":[{"given":"Yunjia","family":"Zhang","sequence":"first","affiliation":[{"name":"University of Wisconsin-Madison"}]},{"given":"Yannis","family":"Chronis","sequence":"additional","affiliation":[{"name":"University of Wisconsin-Madison"}]},{"given":"Jignesh M.","family":"Patel","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University"}]},{"given":"Theodoros","family":"Rekatsinas","sequence":"additional","affiliation":[{"name":"ETH Zurich"}]}],"member":"320","published-online":{"date-parts":[[2023,8,24]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"pg_hint_plan. Retrieved","year":"2023","unstructured":"2012. pg_hint_plan. Retrieved July 15, 2023 from https:\/\/pghintplan.osdn.jp\/pg_hint_plan.html 2012. pg_hint_plan. Retrieved July 15, 2023 from https:\/\/pghintplan.osdn.jp\/pg_hint_plan.html"},{"key":"e_1_2_1_2_1","volume-title":"Retrieved","year":"2023","unstructured":"2019. Adaptive join in Microsoft SQL Server . Retrieved July 15, 2023 from https:\/\/techcommunity.microsoft.com\/t5\/sql-server-blog\/introducing-batch-mode-adaptive-joins\/ba-p\/385411 2019. Adaptive join in Microsoft SQL Server. Retrieved July 15, 2023 from https:\/\/techcommunity.microsoft.com\/t5\/sql-server-blog\/introducing-batch-mode-adaptive-joins\/ba-p\/385411"},{"key":"e_1_2_1_3_1","volume-title":"Retrieved","year":"2023","unstructured":"2020. Bao source code repository . Retrieved July 15, 2023 from https:\/\/github.com\/learnedsystems\/BaoForPostgreSQL 2020. Bao source code repository. Retrieved July 15, 2023 from https:\/\/github.com\/learnedsystems\/BaoForPostgreSQL"},{"key":"e_1_2_1_4_1","volume-title":"Retrieved","year":"2023","unstructured":"2020. Hints used by Bao . Retrieved July 15, 2023 from https:\/\/rmarcus.info\/appendix.html 2020. Hints used by Bao. Retrieved July 15, 2023 from https:\/\/rmarcus.info\/appendix.html"},{"key":"e_1_2_1_5_1","volume-title":"Retrieved","year":"2023","unstructured":"2022. Balsa source code repository . Retrieved July 15, 2023 from https:\/\/github.com\/balsa-project\/balsa\/ 2022. Balsa source code repository. Retrieved July 15, 2023 from https:\/\/github.com\/balsa-project\/balsa\/"},{"key":"e_1_2_1_6_1","volume-title":"Retrieved","year":"2023","unstructured":"2022. IMDB dataset . Retrieved July 15, 2023 from https:\/\/www.imdb.com\/interfaces\/ 2022. IMDB dataset. Retrieved July 15, 2023 from https:\/\/www.imdb.com\/interfaces\/"},{"key":"e_1_2_1_7_1","volume-title":"Retrieved","year":"2023","unstructured":"2022. Overview of PostgreSQL Internals . Retrieved July 15, 2023 from https:\/\/www.postgresql.org\/docs\/15\/executor.html 2022. Overview of PostgreSQL Internals. Retrieved July 15, 2023 from https:\/\/www.postgresql.org\/docs\/15\/executor.html"},{"key":"e_1_2_1_8_1","volume-title":"Retrieved","year":"2023","unstructured":"2022. Overview of PostgreSQL Query Optimizer . Retrieved July 15, 2023 from https:\/\/www.postgresql.org\/docs\/12\/planner-optimizer.html 2022. Overview of PostgreSQL Query Optimizer. Retrieved July 15, 2023 from https:\/\/www.postgresql.org\/docs\/12\/planner-optimizer.html"},{"key":"e_1_2_1_9_1","volume-title":"PostgreSQL user-defined C functions. Retrieved","year":"2023","unstructured":"2022. PostgreSQL user-defined C functions. Retrieved July 15, 2023 from https:\/\/www.postgresql.org\/docs\/current\/xfunc-c.html 2022. PostgreSQL user-defined C functions. Retrieved July 15, 2023 from https:\/\/www.postgresql.org\/docs\/current\/xfunc-c.html"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/304181.304198"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/PDIS.1996.568681"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335420"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/320064.320065"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007615"},{"key":"e_1_2_1_15_1","unstructured":"Pete Belknap Ali Cakmak Sunil Chakkappen Immanuel Chan Deba Chatterjee Dinesh Das Leonidas Galanis Bruce Golbus Shantanu Joshi Tom Kyte etal 2013. Oracle Database SQL Tuning Guide 12c Release 1 (12.1) E15858-15. (2013).  Pete Belknap Ali Cakmak Sunil Chakkappen Immanuel Chan Deba Chatterjee Dinesh Das Leonidas Galanis Bruce Golbus Shantanu Joshi Tom Kyte et al. 2013. Oracle Database SQL Tuning Guide 12c Release 1 (12.1) E15858-15. (2013)."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322238"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2008.160"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113294"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376710"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/191839.191874"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/191839.191874"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/191839.191872"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Amol Deshpande Joseph M Hellerstein etal 2004. Lifting the burden of history from adaptive query processing. In VLDB. Citeseer 948--959.  Amol Deshpande Joseph M Hellerstein et al. 2004. Lifting the burden of history from adaptive query processing. In VLDB. Citeseer 948--959.","DOI":"10.1016\/B978-012088469-8.50083-8"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000001"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389769"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/3329772.3329780"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1739041.1739066"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/3554821.3554842"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/152610.152611"},{"key":"e_1_2_1_31_1","volume-title":"Technologie und Web (BTW)","author":"Graefe Goetz","year":"2011","unstructured":"Goetz Graefe . 2011. A generalized join algorithm. Datenbanksysteme f\u00fcr Business , Technologie und Web (BTW) ( 2011 ). Goetz Graefe. 2011. A generalized join algorithm. Datenbanksysteme f\u00fcr Business, Technologie und Web (BTW) (2011)."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/67544.66960"},{"key":"e_1_2_1_33_1","first-page":"7","article-title":"Adaptive query processing: Technology in evolution","volume":"23","author":"Hellerstein Joseph M.","year":"2000","unstructured":"Joseph M. Hellerstein , Michael J. Franklin , Sirish Chandrasekaran , Amol Deshpande , Kris Hildrum , Samuel Madden , Vijayshankar Raman , and Mehul A. Shah . 2000 . Adaptive query processing: Technology in evolution . IEEE Data Eng. Bull. 23 , 2 (2000), 7 -- 18 . Joseph M. Hellerstein, Michael J. Franklin, Sirish Chandrasekaran, Amol Deshpande, Kris Hildrum, Samuel Madden, Vijayshankar Raman, and Mehul A. Shah. 2000. Adaptive query processing: Technology in evolution. IEEE Data Eng. Bull. 23, 2 (2000), 7--18.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Benjamin Hilprecht Andreas Schmidt Moritz Kulessa Alejandro Molina Kristian Kersting and Carsten Binnig. 2020. DeepDB: Learn from Data not from Queries! Proceedings of the VLDB Endowment 13 7 992--1005.  Benjamin Hilprecht Andreas Schmidt Moritz Kulessa Alejandro Molina Kristian Kersting and Carsten Binnig. 2020. DeepDB: Learn from Data not from Queries! Proceedings of the VLDB Endowment 13 7 992--1005.","DOI":"10.14778\/3384345.3384349"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780050037"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497486"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276315"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/3368289.3368292"},{"key":"e_1_2_1_39_1","volume-title":"Learned cardinalities: Estimating correlated joins with deep learning. arXiv preprint arXiv:1809.00677","author":"Kipf Andreas","year":"2018","unstructured":"Andreas Kipf , Thomas Kipf , Bernhard Radke , Viktor Leis , Peter Boncz , and Alfons Kemper . 2018. Learned cardinalities: Estimating correlated joins with deep learning. arXiv preprint arXiv:1809.00677 ( 2018 ). Andreas Kipf, Thomas Kipf, Bernhard Radke, Viktor Leis, Peter Boncz, and Alfons Kemper. 2018. Learned cardinalities: Estimating correlated joins with deep learning. arXiv preprint arXiv:1809.00677 (2018)."},{"key":"e_1_2_1_40_1","volume-title":"Learning to Optimize Join Queries With Deep Reinforcement Learning. arXiv preprint arXiv:1808.03196","author":"Krishnan Sanjay","year":"2018","unstructured":"Sanjay Krishnan , Zongheng Yang , Ken Goldberg , Joseph Hellerstein , and Ion Stoica . 2018. Learning to Optimize Join Queries With Deep Reinforcement Learning. arXiv preprint arXiv:1808.03196 ( 2018 ). Sanjay Krishnan, Zongheng Yang, Ken Goldberg, Joseph Hellerstein, and Ion Stoica. 2018. Learning to Optimize Join Queries With Deep Reinforcement Learning. arXiv preprint arXiv:1808.03196 (2018)."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/2886444.2886453"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/16894.16863"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3542700.3542703"},{"key":"e_1_2_1_45_1","volume-title":"Neo: A learned query optimizer. arXiv preprint arXiv:1904.03711","author":"Marcus Ryan","year":"2019","unstructured":"Ryan Marcus , Parimarjan Negi , Hongzi Mao , Chi Zhang , Mohammad Alizadeh , Tim Kraska , Olga Papaemmanouil , and Nesime Tatbul . 2019 . Neo: A learned query optimizer. arXiv preprint arXiv:1904.03711 (2019). Ryan Marcus, Parimarjan Negi, Hongzi Mao, Chi Zhang, Mohammad Alizadeh, Tim Kraska, Olga Papaemmanouil, and Nesime Tatbul. 2019. Neo: A learned query optimizer. arXiv preprint arXiv:1904.03711 (2019)."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3211954.3211957"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1147\/sj.421.0098"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/3199517.3199518"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/369275.369291"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/582095.582099"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.14778\/3436905.3436907"},{"key":"e_1_2_1_52_1","unstructured":"Apache Spark. 2018. Spark SQL DataFrames and datasets guide.  Apache Spark. 2018. Spark SQL DataFrames and datasets guide."},{"key":"e_1_2_1_53_1","volume-title":"An end-to-end learning-based cost estimator. arXiv preprint arXiv:1906.02560","author":"Sun Ji","year":"2019","unstructured":"Ji Sun and Guoliang Li. 2019. An end-to-end learning-based cost estimator. arXiv preprint arXiv:1906.02560 ( 2019 ). Ji Sun and Guoliang Li. 2019. An end-to-end learning-based cost estimator. arXiv preprint arXiv:1906.02560 (2019)."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3236263"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/348.318590"},{"key":"e_1_2_1_56_1","volume-title":"SQL Server 2019 Revealed: Including Big Data Clusters and Machine Learning","author":"Ward Bob","unstructured":"Bob Ward . 2019. SQL Server 2019 Revealed: Including Big Data Clusters and Machine Learning . Springer . Bob Ward. 2019. SQL Server 2019 Revealed: Including Big Data Clusters and Machine Learning. Springer."},{"key":"e_1_2_1_57_1","volume-title":"Balsa: Learning a Query Optimizer Without Expert Demonstrations. arXiv preprint arXiv:2201.01441","author":"Yang Zongheng","year":"2022","unstructured":"Zongheng Yang , Wei-Lin Chiang , Sifei Luan , Gautam Mittal , Michael Luo , and Ion Stoica . 2022 . Balsa: Learning a Query Optimizer Without Expert Demonstrations. arXiv preprint arXiv:2201.01441 (2022). Zongheng Yang, Wei-Lin Chiang, Sifei Luan, Gautam Mittal, Michael Luo, and Ion Stoica. 2022. Balsa: Learning a Query Optimizer Without Expert Demonstrations. arXiv preprint arXiv:2201.01441 (2022)."},{"key":"e_1_2_1_58_1","first-page":"82","article-title":"Algorithms for acyclic database schemes","volume":"81","author":"Yannakakis Mihalis","year":"1981","unstructured":"Mihalis Yannakakis . 1981 . Algorithms for acyclic database schemes . In VLDB , Vol. 81. 82 -- 94 . Mihalis Yannakakis. 1981. Algorithms for acyclic database schemes. In VLDB, Vol. 81. 82--94.","journal-title":"VLDB"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.14778\/3090163.3090167"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3611479.3611501","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,23]],"date-time":"2023-09-23T22:24:49Z","timestamp":1695507889000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3611479.3611501"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7]]},"references-count":59,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2023,7]]}},"alternative-id":["10.14778\/3611479.3611501"],"URL":"https:\/\/doi.org\/10.14778\/3611479.3611501","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"}}]}}