{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T18:45:52Z","timestamp":1776969952266,"version":"3.51.4"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMOD Rec."],"published-print":{"date-parts":[[2026,4,23]]},"abstract":"<jats:p>\n                    We revisit the join ordering problem in query optimization. The standard exact algorithm, DPccp, has a worst-case running time of O(3\n                    <jats:sup>n<\/jats:sup>\n                    ). This is prohibitively expensive for large queries, which are not that uncommon anymore. We develop a new algorithmic framework based on subset convolution. DPconv achieves a super-polynomial speedup over DPccp, breaking the O(3\n                    <jats:sup>n<\/jats:sup>\n                    ) time-barrier for the first time. We show that the framework instantiation for the Cmax cost function is up to 30x faster than DPccp for large clique queries.\n                  <\/jats:p>","DOI":"10.1145\/3810900.3810902","type":"journal-article","created":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T18:16:38Z","timestamp":1776968198000},"page":"8-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["DPconv: Super-Polynomially Faster Join Ordering"],"prefix":"10.1145","volume":"55","author":[{"given":"Mihail","family":"Stoian","sequence":"first","affiliation":[{"name":"University of Technology Nuremberg, Nuremberg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas","family":"Kipf","sequence":"additional","affiliation":[{"name":"University of Technology Nuremberg, Nuremberg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,4,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1954-09848-8"},{"key":"e_1_2_1_2_1","first-page":"67","volume-title":"Proceedings of the 39th Annual ACM Symposium on Theory of Computing","author":"Bj\u00a8orklund A.","year":"2007","unstructured":"A. Bj\u00a8orklund, T. Husfeldt, P. Kaski, and M. Koivisto. Fourier meets m\u00a8obius: fast subset convolution. In D. S. Johnson and U. Feige, editors, Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, pages 67-74. ACM, 2007."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/070683933"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543650"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.1995.380392"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/362384.362685"},{"key":"e_1_2_1_7_1","first-page":"321","volume-title":"Algebraic techniques: sieves, convolutions, and polynomials","author":"Cygan M.","year":"2015","unstructured":"M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Algebraic techniques: sieves, convolutions, and polynomials, pages 321-355. Springer International Publishing, Cham, 2015."},{"key":"e_1_2_1_8_1","first-page":"785","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data","author":"DeHaan D.","year":"2007","unstructured":"D. DeHaan and F. W. Tompa. Optimal top-down join enumeration. In C. Y. Chan, B. C. Ooi, and A. Zhou, editors, Proceedings of the ACM SIGMOD International Conference on Management of Data, Beijing, China, June 12-14, 2007, pages 785-796. ACM, 2007."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010302"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/648311.754892"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 27th International Conference on Data Engineering, ICDE 2011","author":"Fender P.","year":"2011","unstructured":"P. Fender and G. Moerkotte. A new, highly efficient, and easy to implement top-down join enumeration algorithm. In S. Abiteboul, K. B\u00a8ohm, C. Koch, and K. Tan, editors, Proceedings of the 27th International Conference on Data Engineering, ICDE 2011, April 11-16, 2011, Hannover, Germany, pages 864-875. IEEE Computer Society, 2011."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.235"},{"key":"e_1_2_1_13_1","first-page":"414","volume-title":"IEEE 28th International Conference on Data Engineering (ICDE 2012","author":"Fender P.","year":"2012","unstructured":"P. Fender, G. Moerkotte, T. Neumann, and V. Leis. Effective and robust pruning for top-down join enumeration algorithms. In A. Kementsietsidis and M. A. V. Salles, editors, IEEE 28th International Conference on Data Engineering (ICDE 2012), Washington, DC, USA (Arlington, Virginia), 1-5 April, 2012, pages 414-425. IEEE Computer Society, 2012."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16533-7"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588927"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSSC.1968.300136"},{"key":"e_1_2_1_17_1","first-page":"546","volume-title":"Proceedings of the 23rd International Conference on Extending Database Technology, EDBT","author":"Havenstein D.","year":"2020","unstructured":"D. Havenstein, P. Lysakovski, N. May, G. Moerkotte, and G. Steidl. Fast Entropy Maximization for Selectivity Estimation of Conjunctive Predicates on CPUs and GPUs. In A. Bonifati, Y. Zhou, M. A. V. Salles, A. B\u00a8ohm, D. Olteanu, G. H. L. Fletcher, A. Khan, and B. Yang, editors, Proceedings of the 23rd International Conference on Extending Database Technology, EDBT 2020, Copenhagen, Denmark, March 30 - April 02, 2020, pages 546-554. OpenProceedings.org, 2020."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1270.1498"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649605"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63475"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/352958.352982"},{"key":"e_1_2_1_22_1","volume-title":"VLDB\u201986 Twelfth International Conference on Very Large Data Bases","author":"Krishnamurthy R.","year":"1986","unstructured":"R. Krishnamurthy, H. Boral, and C. Zaniolo. Optimization of nonrecursive queries. In W. W. Chu, G. Gardarin, S. Ohsuga, and Y. Kambayashi, editors, VLDB\u201986 Twelfth International Conference on Very Large Data Bases, August 25-28, 1986, Kyoto, Japan, Proceedings, pages 128-137. Morgan Kaufmann, 1986."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/50202.50204"},{"key":"e_1_2_1_24_1","unstructured":"R. Marcus. Learned query superoptimization. In R. Bordawekar C. Cappiello V. Efthymiou L. Ehrlinger V. Gadepally S. Galhotra S. Geisler S. Groppe L. Gruenwald A. Y. Halevy H. Harmouch O. Hassanzadeh I. F. Ilyas E. Jim\u00b4enez-Ruiz S. Krishnan T. Lahiri G. Li J. Lu W. Mauerer U. F. Minhas F. Naumann M. T. \u00a8Ozsu E. K. Rezig K. Srinivas M. Stonebraker S. R. Valluri M. Vidal H. Wang J. Wang Y. Wu X. Xue M. Za\u00a8t and K. Zeng editors Joint Proceedings of Workshops at the 49th International Conference on Very Large Data Bases (VLDB 2023) Vancouver Canada August 28 - September 1 2023 volume 3462 of CEUR Workshop Proceedings. CEUR-WS.org 2023."},{"key":"e_1_2_1_25_1","first-page":"1","volume-title":"Proceedings of the First International Workshop on Exploiting Artificial Intelligence Techniques for Data Management, aiDM@SIGMOD 2018","author":"Marcus R.","year":"2018","unstructured":"R. Marcus and O. Papaemmanouil. Deep reinforcement learning for join order enumeration. In R. Bordawekar and O. Shmueli, editors, Proceedings of the First International Workshop on Exploiting Artificial Intelligence Techniques for Data Management, aiDM@SIGMOD 2018, Houston, TX, USA, June 10, 2018, pages 3:1-3:4. ACM, 2018."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/1182635.1164207"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376672"},{"key":"e_1_2_1_28_1","first-page":"403","volume-title":"U. \u00b8Cetintemel","author":"Neumann T.","year":"2009","unstructured":"T. Neumann. Query simplification: graceful degradation for join-order optimization. In U. \u00b8Cetintemel, S. B. Zdonik, D. Kossmann, and N. Tatbul, editors, Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2009, Providence, Rhode Island, USA, June 29 - July 2, 2009, pages 403-414. ACM, 2009."},{"key":"e_1_2_1_29_1","first-page":"677","volume-title":"Proceedings of the 2018 International Conference on Management of Data, SIGMOD Conference 2018","author":"Neumann T.","year":"2018","unstructured":"T. Neumann and B. Radke. Adaptive optimization of very large join queries. In G. Das, C. M. Jermaine, and P. A. Bernstein, editors, Proceedings of the 2018 International Conference on Management of Data, SIGMOD Conference 2018, Houston, TX, USA, June 10-15, 2018, pages 677-692. ACM, 2018."},{"key":"e_1_2_1_30_1","first-page":"37","volume-title":"Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2012","author":"Ngo H. Q.","year":"2012","unstructured":"H. Q. Ngo, E. Porat, C. R\u00b4e, and A. Rudra. Worst-case optimal join algorithms: [extended abstract]. In M. Benedikt, M. Kr\u00a8otzsch, and M. Lenzerini, editors, Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2012, Scottsdale, AZ, USA, May 20-24, 2012, pages 37-48. ACM, 2012."},{"key":"e_1_2_1_31_1","first-page":"314","volume-title":"16th International Conference on Very Large Data Bases, August 13-16, 1990, Brisbane, Queensland, Australia, Proceedings","author":"Ono K.","year":"1990","unstructured":"K. Ono and G. M. Lohman. Measuring the complexity of join enumeration in query optimization. In D. McLeod, R. Sacks-Davis, and H. Schek, editors, 16th International Conference on Very Large Data Bases, August 13-16, 1990, Brisbane, Queensland, Australia, Proceedings, pages 314-325. Morgan Kaufmann, 1990."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-79228-4_43"},{"key":"e_1_2_1_33_1","series-title":"LNI","first-page":"57","volume-title":"Datenbanksysteme f\u00a8ur Business, Technologie und Web (BTW","author":"Radke B.","year":"2019","unstructured":"B. Radke and T. Neumann. Lindp++: Generalizing linearized DP to crossproducts and non-inner joins. In T. Grust, F. Naumann, A. B\u00a8ohm, W. Lehner, T. H\u00a8arder, E. Rahm, A. Heuer, M. Klettke, and H. Meyer, editors, Datenbanksysteme f\u00a8ur Business, Technologie und Web (BTW 2019), 18. Fachtagung des GI-Fachbereichs \u201d Datenbanken und Informationssysteme\u201d (DBIS), 4.-8. M\u00a8arz 2019, Rostock, Germany, Proceedings, volume P-289 of LNI, pages 57-76. Gesellschaft f\u00a8ur Informatik, Bonn, 2019."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3555041.3589677"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626246.3653395"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588946"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/11415770_1"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/582095.582099"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780050040"},{"issue":"6","key":"e_1_2_1_40_1","first-page":"1","volume":"2","author":"Stoian M.","year":"2024","unstructured":"M. Stoian and A. Kipf. DPconv: Super-Polynomially Faster Join Ordering. Proc. ACM Manag. Data, 2(6):234:1-234:26, 2024.","journal-title":"DPconv: Super-Polynomially Faster Join Ordering. Proc. ACM Manag. Data"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064039"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/926005"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/233269.233317"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00156"},{"key":"e_1_2_1_45_1","first-page":"1","volume-title":"Proceedings of the International Workshop on Big Data in Emergent Distributed Environments, BiDEDE 2023","author":"Winker T.","year":"2023","unstructured":"T. Winker, U. \u00b8Calikyilmaz, L. Gruenwald, and S. Groppe. Quantum machine learning for join order optimization using variational quantum circuits. In S. Groppe, L. Gruenwald, and C. Hsu, editors, Proceedings of the International Workshop on Big Data in Emergent Distributed Environments, BiDEDE 2023, Seattle, WA, USA, 18 June 2023, pages 5:1-5:7. ACM, 2023."},{"key":"e_1_2_1_46_1","volume-title":"The design and analysis of factorial experiments","author":"Yates F.","year":"1937","unstructured":"F. Yates. The design and analysis of factorial experiments. Imperial Bureau of Soil Science, 1937. 18 SIGMOD"}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3810900.3810902","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T18:17:16Z","timestamp":1776968236000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3810900.3810902"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,23]]},"references-count":46,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,4,23]]}},"alternative-id":["10.1145\/3810900.3810902"],"URL":"https:\/\/doi.org\/10.1145\/3810900.3810902","relation":{},"ISSN":["0163-5808"],"issn-type":[{"value":"0163-5808","type":"print"}],"subject":[],"published":{"date-parts":[[2026,4,23]]},"assertion":[{"value":"2026-04-23","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}