{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T05:46:53Z","timestamp":1768456013380,"version":"3.49.0"},"reference-count":51,"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>The performance of worst-case optimal join algorithms depends on the order in which the join attributes are processed. Selecting good orders before query execution is hard, due to the large space of possible orders and unreliable execution cost estimates in case of data skew or data correlation. We propose ADOPT, a query engine that combines adaptive query processing with a worst-case optimal join algorithm, which uses an order on the join attributes instead of a join order on relations. ADOPT divides query execution into episodes in which different attribute orders are tried. Based on run time feedback on attribute order performance, ADOPT converges quickly to near-optimal orders. It avoids redundant work across different orders via a novel data structure, keeping track of parts of the join input that have been successfully processed. It selects attribute orders to try via reinforcement learning, balancing the need for exploring new orders with the desire to exploit promising orders. In experiments with various data sets and queries, it outperforms baselines, including commercial and open-source systems using worst-case optimal join algorithms, whenever queries become complex and therefore difficult to optimize.<\/jats:p>","DOI":"10.14778\/3611479.3611489","type":"journal-article","created":{"date-parts":[[2023,8,25]],"date-time":"2023-08-25T02:08:08Z","timestamp":1692929288000},"page":"2805-2817","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["ADOPT: Adaptively Optimizing Attribute Orders for Worst-Case Optimal Join Algorithms via Reinforcement Learning"],"prefix":"10.14778","volume":"16","author":[{"given":"Junxiong","family":"Wang","sequence":"first","affiliation":[{"name":"Cornell University, Ithaca, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Immanuel","family":"Trummer","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ahmet","family":"Kara","sequence":"additional","affiliation":[{"name":"University of Zurich, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dan","family":"Olteanu","sequence":"additional","affiliation":[{"name":"University of Zurich, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,8,24]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00048"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915213"},{"key":"e_1_2_1_3_1","first-page":"1","article-title":"Relational Artificial Intelligence","volume":"2368","author":"Aref Molham","year":"2019","unstructured":"Molham Aref . 2019 . Relational Artificial Intelligence . In Datalog , Vol. 2368. 1 . http:\/\/ceur-ws.org\/Vol-2368\/invited1.pdf Molham Aref. 2019. Relational Artificial Intelligence. In Datalog, Vol. 2368. 1. http:\/\/ceur-ws.org\/Vol-2368\/invited1.pdf","journal-title":"Datalog"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742796"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/110859440"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335420"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556579"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-72401-0_8"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1409360.1409380"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/974121.974129"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407797"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2220357.2220363"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3329859.3329876"},{"key":"e_1_2_1_15_1","unstructured":"Guodong Jin Nafisa Anzum and Semih Salihoglu. 2022. GRainDB: A Relational-core Graph-Relational DBMS. In CIDR. https:\/\/www.cidrdb.org\/cidr2022\/papers\/p57-jin.pdf  Guodong Jin Nafisa Anzum and Semih Salihoglu. 2022. GRainDB: A Relational-core Graph-Relational DBMS. In CIDR. https:\/\/www.cidrdb.org\/cidr2022\/papers\/p57-jin.pdf"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3093754.3093757"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1186\/s40649-021-00087-y"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/11871842_29"},{"key":"e_1_2_1_19_1","first-page":"43","article-title":"Mapping networks of terrorist cells","volume":"24","author":"Krebs Valdis E","year":"2002","unstructured":"Valdis E Krebs . 2002 . Mapping networks of terrorist cells . Connections 24 , 3 (2002), 43 -- 52 . Valdis E Krebs. 2002. Mapping networks of terrorist cells. Connections 24, 3 (2002), 43--52.","journal-title":"Connections"},{"key":"e_1_2_1_20_1","unstructured":"Sanjay Krishnan Zongheng Yang Ken Goldberg Joseph Hellerstein and Ion Stoica. 2020. Learning to Optimize Join Queries with Deep Reinforcement Learning. In aiDM. 1--6. http:\/\/arxiv.org\/abs\/1808.03196  Sanjay Krishnan Zongheng Yang Ken Goldberg Joseph Hellerstein and Ion Stoica. 2020. Learning to Optimize Join Queries with Deep Reinforcement Learning. In aiDM. 1--6. http:\/\/arxiv.org\/abs\/1808.03196"},{"key":"e_1_2_1_21_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data.  Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/3352063.3352129"},{"key":"e_1_2_1_23_1","volume-title":"Proc. Workshop on Database Query Optimization","volume":"13","author":"Lohman Guy","year":"2014","unstructured":"Guy Lohman . 2014 . Is Query Optimization a \"Solved\" Problem? . In Proc. Workshop on Database Query Optimization , Vol. 13 . 10. Guy Lohman. 2014. Is Query Optimization a \"Solved\" Problem?. In Proc. Workshop on Database Query Optimization, Vol. 13. 10."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342644"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3542700.3542702"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/3425879.3425882"},{"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 . 383--402. https:\/\/dl.gi.de\/handle\/20.500.12116\/2418 Thomas Neumann and Alfons Kemper. 2015. Unnesting Arbitrary Queries. In BTW (LNI), Vol. P-241. 383--402. https:\/\/dl.gi.de\/handle\/20.500.12116\/2418"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2022.1"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3180143"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2590989.2590991"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764947.2764948"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3003665.3003667"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2656335"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature03607"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367848"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882939"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/582095.582099"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/16894.16888"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/s1364-6613(99)01331-5"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517843"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3300088"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3464389"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/3450980.3450992"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5441\/002\/icdt.2014.13"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452754"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/3484224.3484236"},{"key":"e_1_2_1_48_1","volume-title":"ADOPT: Adaptively Optimizing Attribute Orders for Worst-Case Optimal Join Algorithms via Reinforcement Learning. Technical Report","author":"Wang Junxiong","year":"2023","unstructured":"Junxiong Wang , Immanuel Trummer , Ahmet Kara , and Dan Olteanu . 2023 . ADOPT: Adaptively Optimizing Attribute Orders for Worst-Case Optimal Join Algorithms via Reinforcement Learning. Technical Report . http:\/\/arxiv.org\/abs\/2307.16540. Junxiong Wang, Immanuel Trummer, Ahmet Kara, and Dan Olteanu. 2023. ADOPT: Adaptively Optimizing Attribute Orders for Worst-Case Optimal Join Algorithms via Reinforcement Learning. Technical Report. http:\/\/arxiv.org\/abs\/2307.16540."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/3574245.3574272"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526128"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00116"},{"key":"e_1_2_1_52_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.3611489","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,23]],"date-time":"2023-09-23T22:19:43Z","timestamp":1695507583000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3611479.3611489"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7]]},"references-count":51,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2023,7]]}},"alternative-id":["10.14778\/3611479.3611489"],"URL":"https:\/\/doi.org\/10.14778\/3611479.3611489","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"}}]}}