{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T19:49:41Z","timestamp":1774986581706,"version":"3.50.1"},"reference-count":75,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"name":"Hong Kong Research Grant Council","award":["12200524, 16205422, 16204223, 16203924, C2004-21GF, C2003-23Y"],"award-info":[{"award-number":["12200524, 16205422, 16204223, 16203924, C2004-21GF, C2003-23Y"]}]},{"name":"Alibaba Cloud"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,6,17]]},"abstract":"<jats:p>Acyclic conjunctive queries form the backbone of most analytical workloads, and have been extensively studied in the literature from both theoretical and practical angles. However, there is still a large divide between theory and practice. While the 40-year-old Yannakakis algorithm has strong theoretical running time guarantees, it has not been adopted in real systems due to its high hidden constant factor. In this paper, we strive to close this gap by proposing Yannakakis+, an improved version of the Yannakakis algorithm, which is more practically efficient while preserving its theoretical guarantees. Our experiments demonstrate that Yannakakis+ consistently outperforms the original Yannakakis algorithm by 2x to 5x across a wide range of queries and datasets.<\/jats:p>\n                  <jats:p>Another nice feature of our new algorithm is that it generates a traditional DAG query plan consisting of standard relational operators, allowing Yannakakis+ to be easily plugged into any standard SQL engine. Our system prototype currently supports four different SQL engines (DuckDB, PostgreSQL, SparkSQL, and AnalyticDB from Alibaba Cloud), and our experiments show that Yannakakis+ is able to deliver better performance than their native query plans on 160 out of the 162 queries tested, with an average speedup of 2.41x and a maximum speedup of 47,059x.<\/jats:p>","DOI":"10.1145\/3725423","type":"journal-article","created":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:23:29Z","timestamp":1750281809000},"page":"1-28","source":"Crossref","is-referenced-by-count":5,"title":["Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0959-5536","authenticated-orcid":false,"given":"Qichen","family":"Wang","sequence":"first","affiliation":[{"name":"Hong Kong Baptist University, Hong Kong, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7960-6328","authenticated-orcid":false,"given":"Bingnan","family":"Chen","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology, Hong Kong, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-5438-7288","authenticated-orcid":false,"given":"Binyang","family":"Dai","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology, Hong Kong, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2178-3716","authenticated-orcid":false,"given":"Ke","family":"Yi","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology, Hong Kong, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-0770-5775","authenticated-orcid":false,"given":"Feifei","family":"Li","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-0431-1534","authenticated-orcid":false,"given":"Liang","family":"Lin","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}]}],"member":"320","published-online":{"date-parts":[[2025,6,18]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"DuckDB. https:\/\/duckdb.org\/."},{"key":"e_1_2_2_2_1","unstructured":"IMDB. http:\/\/www.imdb.com\/."},{"key":"e_1_2_2_3_1","unstructured":"PostgreSQL. https:\/\/www.postgre.org\/."},{"key":"e_1_2_2_4_1","unstructured":"SNAP. https:\/\/snap.stanford.edu\/snap\/."},{"key":"e_1_2_2_5_1","unstructured":"SparkSQL. https:\/\/spark.apache.org\/sql\/."},{"key":"e_1_2_2_6_1","unstructured":"TPC-H. https:\/\/www.tpc.org\/tpch\/."},{"key":"e_1_2_2_7_1","unstructured":"Yannakakis: Practical Acyclic Query Evaluation with Theoretical Guarantees Code Repository. https:\/\/github.com\/hkustDB\/Yannakakis-Plus."},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3129246"},{"key":"e_1_2_2_9_1","volume-title":"Foundations of databases","author":"Abiteboul Serge","unstructured":"Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of databases. Addison-Wesley Longman Publishing Co., Inc."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902280"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056105"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745754.2745772"},{"key":"e_1_2_2_13_1","unstructured":"Renzo Angles J\u00e1nos Benjamin Antal Alex Averbuch Peter A. Boncz Orri Erling Andrey Gubichev Vlad Haprian Moritz Kaufmann Josep-Llu\u00eds Larriba-Pey Norbert Mart\u00ednez-Bazan J\u00f3zsef Marton Marcus Paradies Minh-Duc Pham Arnau Prat-P\u00e9rez Mirko Spasic Benjamin A. Steer G\u00e1bor Sz\u00e1rnyas and Jack Waudby. 2020. The LDBC Social Network Benchmark. CoRR abs\/2001.02299 (2020). arXiv:2001.02299 http:\/\/arxiv.org\/abs\/2001.02299"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.43"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74915-8_18"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322389"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3190662"},{"key":"e_1_2_2_18_1","volume-title":"Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores. arXiv preprint arXiv:2411.04042","author":"Bekkers Liese","year":"2024","unstructured":"Liese Bekkers, Frank Neven, Stijn Vansummeren, and Yisu Remy Wang. 2024. Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores. arXiv preprint arXiv:2411.04042 (2024)."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3681954.3681995"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319894"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450263"},{"key":"e_1_2_2_22_1","volume-title":"VLDB","volume":"97","author":"Chaudhuri Surajit","year":"1997","unstructured":"Surajit Chaudhuri and Vivek R Narasayya. 1997. An efficient, cost-driven index selection tool for Microsoft SQL server. In VLDB, Vol. 97. San Francisco, 146--155."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035921"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247567"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3324957"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322390"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556565"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407797"},{"key":"e_1_2_2_29_1","volume-title":"Cem Okulmus, Reinhard Pichler, and Alexander Selzer.","author":"Gottlob Georg","year":"2023","unstructured":"Georg Gottlob, Matthias Lanzinger, Davide Mario Longo, Cem Okulmus, Reinhard Pichler, and Alexander Selzer. 2023. Structure-Guided Query Evaluation: Towards Bridging the Gap from Theory to Practice. arXiv preprint arXiv:2303.02723 (2023)."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.303979"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1568318.1568320"},{"key":"e_1_2_2_32_1","volume-title":"On the universal relation","author":"Graham MH","unstructured":"MH Graham. 1980. On the universal relation. University of Toronto. Computer Systems Research Group."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2636918"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-003-0090--4"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742795"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/645921.673295"},{"key":"e_1_2_2_37_1","volume-title":"Join query optimization with deep reinforcement learning algorithms. CoRR abs\/1911.11689","author":"Stockinger K","year":"2019","unstructured":"Stockinger K Heitz J. 2019. Join query optimization with deep reinforcement learning algorithms. CoRR abs\/1911.11689 (2019). arXiv:1911.11689 [cs.DB]"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196911"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/3384345.3384349"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589298"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064027"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902293"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687723"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/3303753.3303757"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350269"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342644"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3211954.3211957"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3461837.3464516"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/1182635.1164207"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376672"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476259"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.14778\/3583140.3583164"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3635138.3654765"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3180143"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/235968.233342"},{"key":"e_1_2_2_57_1","unstructured":"RelationalAI. Accessed: 01.10.2024. Worst-case Optimal Join Algorithms. https:\/\/relational.ai\/resources\/worst-case-optimal-join-algorithms"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/1386118.1386121"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/582095.582099"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380584"},{"key":"e_1_2_2_61_1","volume-title":"Proceedings of the 4th International Conference on Extending Database Technology: Advances in Database Technology","author":"Swami Arun","unstructured":"Arun Swami and K. Bernhard Schiefer. 1994. On the estimation of join result sizes. In Proceedings of the 4th International Conference on Extending Database Technology: Advances in Database Technology (Cambridge, United Kingdom) (EDBT '94). Springer-Verlag, Berlin, Heidelberg, 287--300."},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-012-0293--7"},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824051"},{"key":"e_1_2_2_64_1","volume-title":"Yannakakis: Practical Acyclic Query Evaluation with Theoretical Guarantees. arXiv preprint","author":"Wang Qichen","year":"2025","unstructured":"Qichen Wang, Bingnan Chen, Binyang Dai, Ke Yi, Feifei Li, and Liang Lin. 2025. Yannakakis: Practical Acyclic Query Evaluation with Theoretical Guarantees. arXiv preprint (2025)."},{"key":"e_1_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.14778\/3579075.3579080"},{"key":"e_1_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654971"},{"key":"e_1_2_2_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517830"},{"key":"e_1_2_2_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452808"},{"key":"e_1_2_2_69_1","doi-asserted-by":"publisher","DOI":"10.14778\/3291264.3291267"},{"key":"e_1_2_2_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882914"},{"key":"e_1_2_2_71_1","volume-title":"Predicate Transfer: Efficient Pre-Filtering on Multi-Join Queries. In 14th Conference on Innovative Data Systems Research, CIDR 2024","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 Conference on Innovative Data Systems Research, CIDR 2024, Chaminade, HI, USA, January 14--17, 2024. www.cidrdb.org. https:\/\/www.cidrdb.org\/cidr2024\/papers\/p22-yang.pdf"},{"key":"e_1_2_2_72_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.","journal-title":"VLDB"},{"key":"e_1_2_2_73_1","volume-title":"Proceedings. Computer Software and The IEEE Computer Society's Third International Applications Conference","author":"Yu Clement Tak","year":"1979","unstructured":"Clement Tak Yu and Meral Z Ozsoyoglu. 1979. An algorithm for tree-query membership of a distributed query. In COMPSAC 79. Proceedings. Computer Software and The IEEE Computer Society's Third International Applications Conference, 1979. IEEE, 306--312."},{"key":"e_1_2_2_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463701"},{"key":"e_1_2_2_75_1","doi-asserted-by":"crossref","unstructured":"Junyi Zhao Kai Su Yifei Yang Xiangyao Yu Paraschos Koutris and Huanchen Zhang. 2025. Debunking the Myth of Join Ordering: Toward Robust SQL Analytics. In SIGMOD.","DOI":"10.1145\/3725283"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725423","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T18:56:05Z","timestamp":1774983365000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725423"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,17]]},"references-count":75,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,6,17]]}},"alternative-id":["10.1145\/3725423"],"URL":"https:\/\/doi.org\/10.1145\/3725423","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,17]]}}}