{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:14:36Z","timestamp":1779174876920,"version":"3.51.4"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2024,12,18]],"date-time":"2024-12-18T00:00:00Z","timestamp":1734480000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,12,18]]},"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 C\n                    <jats:sub>max<\/jats:sub>\n                    cost function is up to 30x faster than DPccp for large clique queries.\n                  <\/jats:p>","DOI":"10.1145\/3698809","type":"journal-article","created":{"date-parts":[[2024,12,20]],"date-time":"2024-12-20T16:40:35Z","timestamp":1734712835000},"page":"1-26","source":"Crossref","is-referenced-by-count":2,"title":["DPconv: Super-Polynomially Faster Join Ordering"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8843-3374","authenticated-orcid":false,"given":"Mihail","family":"Stoian","sequence":"first","affiliation":[{"name":"UTN, Nuremberg, DE"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3463-0564","authenticated-orcid":false,"given":"Andreas","family":"Kipf","sequence":"additional","affiliation":[{"name":"UTN, Nuremberg, DE"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,12,20]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Dynamic Programming","author":"Bellman R.","unstructured":"R. Bellman, R.E. Bellman, and Rand Corporation. 1957. Dynamic Programming. Princeton University Press. lc57005444 https:\/\/books.google.ro\/books?id=rZW4ugAACAAJ"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250801"},{"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\/3313276.3316373"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543650"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.1995.380392"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/362384.362685"},{"key":"e_1_2_1_8_1","volume-title":"An algorithm for the machine calculation of complex Fourier series. Mathematics of computation","author":"Cooley James W","year":"1965","unstructured":"James W Cooley and John W Tukey. 1965. An algorithm for the machine calculation of complex Fourier series. Mathematics of computation, Vol. 19, 90 (1965), 297--301."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--319--21275--3_10"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247567"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/NET.3230010302"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00778-017-0476--3"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFB0054528"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767901"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.235"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.27"},{"key":"e_1_2_1_17_1","volume-title":"Fomin and Dieter Kratsch","author":"Fedor","year":"2010","unstructured":"Fedor V. Fomin and Dieter Kratsch. 2010. Exact Exponential Algorithms 1st ed.). Springer-Verlag, Berlin, Heidelberg."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588927"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSSC.1968.300136"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1270.1498"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649605"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63475"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/352958.352982"},{"key":"e_1_2_1_24_1","volume-title":"VLDB'86 Twelfth International Conference on Very Large Data Bases, August 25--28","author":"Krishnamurthy Ravi","year":"1986","unstructured":"Ravi Krishnamurthy, Haran Boral, and Carlo Zaniolo. 1986. Optimization of Nonrecursive Queries. In VLDB'86 Twelfth International Conference on Very Large Data Bases, August 25--28, 1986, Kyoto, Japan, Proceedings, Wesley W. Chu, Georges Gardarin, Setsuo Ohsuga, and Yahiko Kambayashi (Eds.). Morgan Kaufmann, 128--137. http:\/\/www.vldb.org\/conf\/1986\/P128.PDF"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/50202.50204"},{"key":"e_1_2_1_27_1","volume-title":"Joint Proceedings of Workshops at the 49th International Conference on Very Large Data Bases (VLDB","author":"Marcus Ryan","year":"2023","unstructured":"Ryan Marcus. 2023. Learned Query Superoptimization. In Joint Proceedings of Workshops at the 49th International Conference on Very Large Data Bases (VLDB 2023), Vancouver, Canada, August 28 - September 1, 2023 (CEUR Workshop Proceedings, Vol. 3462), Rajesh Bordawekar, Cinzia Cappiello, Vasilis Efthymiou, Lisa Ehrlinger, Vijay Gadepally, Sainyam Galhotra, Sandra Geisler, Sven Groppe, Le Gruenwald, Alon Y. Halevy, Hazar Harmouch, Oktie Hassanzadeh, Ihab F. Ilyas, Ernesto Jim\u00e9nez-Ruiz, Sanjay Krishnan, Tirthankar Lahiri, Guoliang Li, Jiaheng Lu, Wolfgang Mauerer, Umar Farooq Minhas, Felix Naumann, M. Tamer \u00d6zsu, El Kindi Rezig, Kavitha Srinivas, Michael Stonebraker, Satyanarayana R. Valluri, Maria-Esther Vidal, Haixun Wang, Jiannan Wang, Yingjun Wu, Xun Xue, Mohamed Za\"it, and Kai Zeng (Eds.). CEUR-WS.org. https:\/\/ceur-ws.org\/Vol-3462\/AIDB5.pdf"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3211954.3211957"},{"key":"e_1_2_1_29_1","unstructured":"Guido Moerkotte. 2023. Building Query Compilers (Draft \/ Under Construction). https:\/\/pi3.informatik.uni-mannheim.de\/%7Emoer\/querycompiler.pdf"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/1182635.1164207"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376672"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476259"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559889"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183733"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213565"},{"key":"e_1_2_1_36_1","volume-title":"Lohman","author":"Ono Kiyoshi","year":"1990","unstructured":"Kiyoshi Ono and Guy M. Lohman. 1990. Measuring the Complexity of Join Enumeration in Query Optimization. In 16th International Conference on Very Large Data Bases, August 13--16, 1990, Brisbane, Queensland, Australia, Proceedings, Dennis McLeod, Ron Sacks-Davis, and Hans-J\u00f6rg Schek (Eds.). Morgan Kaufmann, 314--325. http:\/\/www.vldb.org\/conf\/1990\/P314.PDF"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--540--79228--4_43"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.18420\/BTW2019-05"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1287\/IJOC.2021.1087"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3555041.3589677"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626246.3653395"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588946"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/11415770_1"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/582095.582099"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/S007780050040"},{"key":"e_1_2_1_46_1","unstructured":"Mihail Stoian. 2024. Sinking an Algorithmic Isthmus: (1 epsilon)-Approximate Min-Sum Subset Convolution. arxiv: 2404.11364 [cs.DS]"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064039"},{"key":"e_1_2_1_48_1","volume-title":"Join-order Optimization with Cartesian Products. Ph.,D. Dissertation","author":"Vance Bennet","unstructured":"Bennet Vance. 1998. Join-order Optimization with Cartesian Products. Ph.,D. Dissertation. Oregon Graduate Institute of Science and Technology."},{"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.1109\/ICDE.2018.00156"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3579142.3594299"},{"key":"e_1_2_1_52_1","volume-title":"The Design and Analysis of Factorial Experiments","author":"Yates Frank","year":"1937","unstructured":"Frank Yates. 1937. The Design and Analysis of Factorial Experiments. Imperial Bureau of Soil Science (1937)."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3698809","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3698809","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T17:45:59Z","timestamp":1774979159000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3698809"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,18]]},"references-count":52,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,12,18]]}},"alternative-id":["10.1145\/3698809"],"URL":"https:\/\/doi.org\/10.1145\/3698809","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,18]]}}}