{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T19:07:47Z","timestamp":1779131267001,"version":"3.51.4"},"reference-count":62,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"DOI":"10.13039\/501100001459","name":"Ministry of Education - Singapore","doi-asserted-by":"publisher","award":["Tier 1 grant (RS32\\\/25)"],"award-info":[{"award-number":["Tier 1 grant (RS32\\\/25)"]}],"id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001475","name":"Nanyang Technological University","doi-asserted-by":"publisher","award":["Start-up Grant"],"award-info":[{"award-number":["Start-up Grant"]}],"id":[{"id":"10.13039\/501100001475","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2026,5,18]]},"abstract":"<jats:p>Structural decomposition methods offer powerful theoretical guarantees for join evaluation, yet they are rarely used in real-world query optimizers. A major reason is the difficulty of combining cost-based plan search and structure-based evaluation. In this work, we bridge this gap by introducing meta-decompositions for acyclic queries, a novel representation that succinctly represents all possible join trees and enables their efficient enumeration. Meta-decompositions can be constructed in polynomial time and have sizes linear in the query size. We design an efficient polynomial-time cost-based optimizer based directly on the meta-decomposition, without the need to explicitly enumerate all possible join trees. We characterize plans found by this approach using a novel notion of width, which effectively implies the theoretical worst-case asymptotic bounds of intermediate result sizes and running time of any query plan. Experimental results demonstrate that, in practice, the plans in our class are consistently comparable to\u2014even in many cases better than\u2014the optimal ones found by the state-of-the-art dynamic programming approach, especially on large and complex queries, while our planning process runs by orders of magnitude faster, comparable to the time taken by common heuristic methods.<\/jats:p>","DOI":"10.1145\/3802117","type":"journal-article","created":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T18:19:16Z","timestamp":1779128356000},"page":"1-27","source":"Crossref","is-referenced-by-count":0,"title":["Succinct Structure Representations for Efficient Query Optimization"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-0989-5926","authenticated-orcid":false,"given":"Zhekai","family":"Jiang","sequence":"first","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0959-5536","authenticated-orcid":false,"given":"Qichen","family":"Wang","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9130-7205","authenticated-orcid":false,"given":"Christoph","family":"Koch","sequence":"additional","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,5,18]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Foundations of Databases","author":"Abiteboul Serge","unstructured":"Serge Abiteboul, Richard Hull, and Victor Vianu. 1996. Foundations of Databases. Addison-Wesley, Reading, MA, USA."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902280"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056105"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74915-8_18"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/3742728.3742737"},{"key":"e_1_2_1_6_1","volume-title":"Ioannidis","author":"Bennett Kristin","year":"1991","unstructured":"Kristin Bennett, Michael C. Ferris, and Yannis E. Ioannidis. 1991. A genetic algorithm for database query optimization. Technical Report #1004. Center for Parallel Optimization. https:\/\/minds.wisconsin.edu\/bitstream\/handle\/1793\/59438\/TR1004.pdf"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322238"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/3681954.3681995"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.18420\/BTW2025-09"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00778-019-00558-9"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319894"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3534678.3539303"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-58907-4_6"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3555041.3589715"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3695838"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/3484224.3484234"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0054528"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902309"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/11604686_1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.34726\/5396"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1006\/JCSS.2001.1809"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00030-8"},{"key":"e_1_2_1_23_1","volume-title":"The Cascades Framework for Query Optimization","author":"Graefe Goetz","year":"1995","unstructured":"Goetz Graefe. 1995. The Cascades Framework for Query Optimization. IEEE Data(base) Engineering Bulletin, Vol. 18 (1995), 19-29."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.1993.344061"},{"key":"e_1_2_1_25_1","unstructured":"Marc H. Graham. 1979. On the universal relation. Technical Report. University of Toronto."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/3503585.3503586"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3725241"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589298"},{"key":"e_1_2_1_29_1","unstructured":"Zhekai Jiang Qichen Wang and Christoph Koch. 2026 a. metaDecomp. GitHub repository. https:\/\/github.com\/epfldata\/metaDecomp"},{"key":"e_1_2_1_30_1","unstructured":"Zhekai Jiang Qichen Wang and Christoph Koch. 2026 b. Succinct Structure Representations for Efficient Query Optimization. arXiv:2603.15465 [cs.DB] https:\/\/arxiv.org\/abs\/2603.15465"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902293"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/352958.352982"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2026.21"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0480-7"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/3696435.3696440"},{"key":"e_1_2_1_36_1","volume-title":"Algorithms for Optimizing Acyclic Queries. In 29th International Conference on Database theory (ICDT","author":"Luo Zheng","year":"2026","unstructured":"Zheng Luo, Wim Van den Broeck, Guy Van den Broeck, and Yisu Remy Wang. 2026. Algorithms for Optimizing Acyclic Queries. In 29th International Conference on Database theory (ICDT 2026)."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517871"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452838"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376672"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183733"},{"key":"e_1_2_1_41_1","first-page":"742","article-title":"Neuer Beweis eines Satzes \u00fcber Permutationen","volume":"27","author":"Pr\u00fcfer Heinz","year":"1918","unstructured":"Heinz Pr\u00fcfer. 1918. Neuer Beweis eines Satzes \u00fcber Permutationen. Archiv der Mathematischen Physik, Vol. 27 (1918), 742-744.","journal-title":"Archiv der Mathematischen Physik"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3320212"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.10.010"},{"key":"e_1_2_1_44_1","unstructured":"Wolfgang Scheufele and Guido Moerkotte. 1996. Constructing Optimal Bushy Processing Trees for Join Queries is NP-hard. Technical Report. Universit\u00e4t Mannheim."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/582095.582099"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3698809"},{"key":"e_1_2_1_47_1","unstructured":"Transaction Processing Council (TPC). 2022. TPC Benchmark H. Available: https:\/\/tpc.org\/tpc_documents_current_versions\/pdf\/tpc-h_v3.0.1.pdf."},{"key":"e_1_2_1_48_1","unstructured":"Bennet Vance. 1998. Join-order optimization with Cartesian products. Ph.D. Dissertation. Oregon Graduate Institute of Science and Technology. https:\/\/digitalcollections.ohsu.edu\/record\/177"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/233269.233317"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3725423"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654971"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517830"},{"key":"e_1_2_1_53_1","volume-title":"Predicate Transfer: Efficient Pre-Filtering on Multi-Join Queries. In 14th Annual Conference on Innovative Data Systems Research (CIDR '24)","author":"Yang Yifei","year":"2024","unstructured":"Yifei Yang, Hangdong Zhao, Xiangyao Yu, and Paraschos Koutris. 2024. Predicate Transfer: Efficient Pre-Filtering on Multi-Join Queries. In 14th Annual Conference on Innovative Data Systems Research (CIDR '24)."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517885"},{"key":"e_1_2_1_55_1","first-page":"82","volume-title":"Algorithms for Acyclic Database Schemes. In VLDB '81: Proceedings of the seventh international conference on Very Large Data Bases","volume":"7","author":"Yannakakis Mihalis","year":"1981","unstructured":"Mihalis Yannakakis. 1981. Algorithms for Acyclic Database Schemes. In VLDB '81: Proceedings of the seventh international conference on Very Large Data Bases, Vol. 7. 82-94."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/CMPSAC.1979.762509"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","unstructured":"Tao Yu Rui Zhang Kai Yang Michihiro Yasunaga Dongxu Wang Zifan Li James Ma Irene Li Qingning Yao Shanelle Roman Zilin Zhang and Dragomir Radev. 2018. Spider: A Large-Scale Human-Labeled Dataset for Complex and Cross-Domain Semantic Parsing and Text-to-SQL Task. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing Ellen Riloff David Chiang Julia Hockenmaier and Jun'ichi Tsujii (Eds.). Association for Computational Linguistics Brussels Belgium 3911-3921. https:\/\/doi.org\/10.18653\/v1\/D18-1425","DOI":"10.18653\/v1\/D18-1425"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3725321"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3651138"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3725283"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.14778\/3485450.3485456"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.14778\/3611540.3611633"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3802117","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T18:34:11Z","timestamp":1779129251000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3802117"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,18]]},"references-count":62,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,5,18]]}},"alternative-id":["10.1145\/3802117"],"URL":"https:\/\/doi.org\/10.1145\/3802117","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,18]]}}}