{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,8]],"date-time":"2026-02-08T03:42:58Z","timestamp":1770522178759,"version":"3.49.0"},"reference-count":58,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T00:00:00Z","timestamp":1742947200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"},{"start":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T00:00:00Z","timestamp":1742947200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2025,5]]},"DOI":"10.1007\/s00778-025-00906-y","type":"journal-article","created":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T21:59:31Z","timestamp":1743199171000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Join optimization revisited: a novel DP algorithm for join&sort order selection"],"prefix":"10.1007","volume":"34","author":[{"given":"Rui","family":"Li","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zongyan","family":"He","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeffrey Xu","family":"Yu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,3,26]]},"reference":[{"key":"906_CR1","unstructured":"TPC-DS, 2012. https:\/\/www.tpc.org\/tpcds\/"},{"issue":"1\u20133","key":"906_CR2","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/S0012-365X(99)00108-9","volume":"205","author":"M Aigner","year":"1999","unstructured":"Aigner, M.: A characterization of the bell numbers. Discrete Math. 205(1\u20133), 207\u2013210 (1999)","journal-title":"Discrete Math."},{"issue":"10","key":"906_CR3","first-page":"1064","volume":"5","author":"M Albutiu","year":"2012","unstructured":"Albutiu, M., Kemper, A., Neumann, T.: Massively parallel sort-merge joins in main memory multi-core database systems. PVLDB 5(10), 1064\u20131075 (2012)","journal-title":"PVLDB"},{"issue":"2","key":"906_CR4","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1145\/320455.320457","volume":"1","author":"MM Astrahan","year":"1976","unstructured":"Astrahan, M.M., Blasgen, M.W., Chamberlin, D.D., Eswaran, K.P., Gray, J.N., Griffiths, P.P., King, W.F., Lorie, R.A., McJones, P.R., Mehl, J.W., Putzolu, G.R., Traiger, I.L., Wade, B.W., Watson, V.: System R: relational approach to database management. TODS 1(2), 97\u2013137 (1976)","journal-title":"TODS"},{"key":"906_CR5","doi-asserted-by":"crossref","unstructured":"Balkesen, C., Alonso, G., Teubner, J., \u00d6zsu, M.T.: Multi-core main-memory joins: sort vs. hash revisited. PVLDB 7(1), 85\u201396 (2013)","DOI":"10.14778\/2732219.2732227"},{"key":"906_CR6","doi-asserted-by":"crossref","unstructured":"Cao, Y., Bramandia, R., Chan, C., Tan, K.: Optimized query evaluation using cooperative sorts. In: Proceedings of ICDE\u201910, (2010)","DOI":"10.1109\/ICDE.2010.5447894"},{"issue":"3","key":"906_CR7","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/s00778-011-0251-9","volume":"21","author":"Y Cao","year":"2012","unstructured":"Cao, Y., Bramandia, R., Chan, C., Tan, K.: Sort-sharing-aware query processing. VLDB J. 21(3), 411\u2013436 (2012)","journal-title":"VLDB J."},{"key":"906_CR8","doi-asserted-by":"crossref","unstructured":"Chaudhuri, S.: An overview of query optimization in relational systems. In: Proceedings of PODS\u201998 (1998)","DOI":"10.1145\/275487.275492"},{"issue":"3","key":"906_CR9","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1007\/s007780000030","volume":"9","author":"J Clau\u00dfen","year":"2000","unstructured":"Clau\u00dfen, J., Kemper, A., Kossmann, A., Wiesner, C.: Exploiting early sorting and early partitioning for decisionsupport query processing. VLDB J. 9(3), 190\u2013213 (2000)","journal-title":"VLDB J."},{"key":"906_CR10","doi-asserted-by":"crossref","unstructured":"Cluet, S., Moerkotte, G.: On the complexity of generating optimal left-deep processing trees with cross products. In: Proceedings of ICDT\u201995, (1995)","DOI":"10.1007\/3-540-58907-4_6"},{"key":"906_CR11","doi-asserted-by":"crossref","unstructured":"DeHaan, D., Tompa, F.W.: Optimal top-down join enumeration. In: Proceedings of SIGMOD\u201907, (2007)","DOI":"10.1145\/1247480.1247567"},{"key":"906_CR12","doi-asserted-by":"crossref","unstructured":"Fender, P., Moerkotte, G.: A new, highly efficient, and easy to implement top\u2013down join enumeration algorithm. In Proceedings of ICDE\u201911, (2011)","DOI":"10.1109\/ICDE.2011.5767901"},{"issue":"10","key":"906_CR13","first-page":"1803","volume":"24","author":"P Fender","year":"2012","unstructured":"Fender, P., Moerkotte, G.: Reassessing top-down join enumeration. TKDE 24(10), 1803\u20131818 (2012)","journal-title":"Reassessing top-down join enumeration. TKDE"},{"issue":"14","key":"906_CR14","doi-asserted-by":"publisher","first-page":"1822","DOI":"10.14778\/2556549.2556565","volume":"6","author":"P Fender","year":"2013","unstructured":"Fender, P., Moerkotte, G.: Counter strike: generic top-down join enumeration for hypergraphs. Proc. VLDB Endow. 6(14), 1822\u20131833 (2013)","journal-title":"Proc. VLDB Endow."},{"key":"906_CR15","doi-asserted-by":"crossref","unstructured":"Fender, P., Moerkotte, G.: Top\u2013down plan generation: from theory to practice. In: Proceedings of ICDE\u201913, (2013)","DOI":"10.1109\/ICDE.2013.6544901"},{"key":"906_CR16","doi-asserted-by":"crossref","unstructured":"Fender, P., Moerkotte, G., Neumann, T., Leis, V.: Effective and robust pruning for top-down join enumeration algorithms. In: Proceedings of ICDE\u201912, (2012)","DOI":"10.1109\/ICDE.2012.27"},{"key":"906_CR17","volume-title":"Query Processing For Advanced Database Systems","author":"JC Freytag","year":"1994","unstructured":"Freytag, J.C., Maier, D., Vossen, G.: Query Processing For Advanced Database Systems. Morgan Kaufmann, Burlington (1994)"},{"key":"906_CR18","volume-title":"Database Systems: The Complete Book","author":"H Garcia-Molina","year":"2002","unstructured":"Garcia-Molina, H., Ullman, J.D., Widom, J.: Database Systems: The Complete Book, international edn. Pearson Education, Pearson (2002)","edition":"international"},{"issue":"2","key":"906_CR19","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1145\/152610.152611","volume":"25","author":"G Graefe","year":"1993","unstructured":"Graefe, G.: Query evaluation techniques for large databases. ACM Comput. Surv. 25(2), 73\u2013169 (1993)","journal-title":"ACM Comput. Surv."},{"issue":"3","key":"906_CR20","first-page":"19","volume":"18","author":"G Graefe","year":"1995","unstructured":"Graefe, G.: The cascades framework for query optimization. IEEE Data Eng. Bull. 18(3), 19\u201329 (1995)","journal-title":"IEEE Data Eng. Bull."},{"key":"906_CR21","doi-asserted-by":"crossref","unstructured":"Graefe, G., Linville, A., Shapiro, L.D.: Sort versus hash revisited. TKDE, 6(6), (1994)","DOI":"10.1109\/69.334883"},{"key":"906_CR22","unstructured":"Graefe, G., McKenna, W.: The volcano optimizer generator: extensibility and efficient search. In: Proceedings of ICDE\u201993, (1993)"},{"key":"906_CR23","doi-asserted-by":"crossref","unstructured":"Guravannavar, R., Sudarshan, S.: Reducing order enforcement cost in complex query plans. In: Proceedings of ICDE\u201907, (2007)","DOI":"10.1109\/ICDE.2007.367931"},{"issue":"1","key":"906_CR24","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/s00778-011-0240-z","volume":"21","author":"R Guravannavar","year":"2012","unstructured":"Guravannavar, R., Sudarshan, S., Diwan, A.A., Babu, C.S.: Which sort orders are interesting? VLDB J. 21(1), 145\u2013165 (2012)","journal-title":"VLDB J."},{"issue":"3","key":"906_CR25","doi-asserted-by":"publisher","first-page":"482","DOI":"10.1145\/1270.1498","volume":"9","author":"T Ibaraki","year":"1984","unstructured":"Ibaraki, T., Kameda, T.: On the optimal nesting order for computing n-relational joins. TODS 9(3), 482\u2013502 (1984)","journal-title":"TODS"},{"key":"906_CR26","doi-asserted-by":"crossref","unstructured":"Ioannidis, Y.E.: Query optimization. ACM Comput. Surv., 28(1), 1996","DOI":"10.1145\/234313.234367"},{"key":"906_CR27","doi-asserted-by":"crossref","unstructured":"Jarke, M., Koch, J.: Query optimization in database systems. ACM Comput. Surv., 16(2), 1984","DOI":"10.1145\/356924.356928"},{"key":"906_CR28","doi-asserted-by":"crossref","unstructured":"Kim, C., Sedlar, E., Chhugani, J., Kaldewey, T., Nguyen, A.D., Blas, A.D., Lee, V.W., Satish, N., Dubey, P.: Sort vs. hash revisited: Fast join implementation on modern multi-core cpus. PVLDB 2(2), 1378\u20131389 (2009)","DOI":"10.14778\/1687553.1687564"},{"key":"906_CR29","volume-title":"Query Processing in Database Systems","year":"1985","unstructured":"Kim, W., Reiner, D.S., Batory, D.S. (eds.): Query Processing in Database Systems. Springer, New York (1985)"},{"issue":"1","key":"906_CR30","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1145\/352958.352982","volume":"25","author":"D Kossmann","year":"2000","unstructured":"Kossmann, D., Stocker, K.: Iterative dynamic programming: a new class of query optimization algorithms. TODS 25(1), 43\u201382 (2000)","journal-title":"TODS"},{"issue":"3","key":"906_CR31","doi-asserted-by":"publisher","first-page":"204","DOI":"10.14778\/2850583.2850594","volume":"9","author":"V Leis","year":"2015","unstructured":"Leis, V., Gubichev, A., Mirchev, A., Boncz, P., Kemper, A., Neumann, T.: How good are query optimizers, really? Proc. VLDB Endow. 9(3), 204\u2013215 (2015)","journal-title":"Proc. VLDB Endow."},{"issue":"10","key":"906_CR32","first-page":"1058","volume":"8","author":"V Leis","year":"2015","unstructured":"Leis, V., Kundhikanjana, K., Kemper, A., Neumann, T.: Efficient processing of window functions in analytical SQL queries. PVLDB 8(10), 1058\u20131069 (2015)","journal-title":"PVLDB"},{"issue":"5","key":"906_CR33","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1007\/s00778-017-0480-7","volume":"27","author":"V Leis","year":"2018","unstructured":"Leis, V., Radke, B., Gubichev, A., Mirchev, A., Boncz, P.A., Kemper, A., Neumann, T.: Query optimization through the looking glass, and what we found running the join order benchmark. VLDB J. 27(5), 643\u2013668 (2018)","journal-title":"VLDB J."},{"key":"906_CR34","doi-asserted-by":"crossref","unstructured":"Lerner, A., Shasha, D.E.: Aquery: Query language for ordered data, optimization techniques, and experiments. In Proceedings of VLDB\u201903, (2003)","DOI":"10.1016\/B978-012722442-8\/50038-0"},{"key":"906_CR35","doi-asserted-by":"crossref","unstructured":"Maier, D., Vance, B.: A call to order. In: Proceedings of PODS\u201993, 1993","DOI":"10.1145\/153850.153851"},{"issue":"10","key":"906_CR36","first-page":"1069","volume":"11","author":"A Meister","year":"2018","unstructured":"Meister, A., Moerkotte, G., Saake, G.: Errata for \u201canalysis of two existing and one new dynamic programming algorithm for the generation of optimal bushy join trees without cross products\". PVLDB 11(10), 1069\u20131070 (2018)","journal-title":"PVLDB"},{"key":"906_CR37","doi-asserted-by":"crossref","unstructured":"Mishra, P., Eich, M.H.: Join processing in relational databases. ACM Comput. Surv. 24(1), (1992)","DOI":"10.1145\/128762.128764"},{"key":"906_CR38","unstructured":"Moerkotte, G.: Building query compilers. (2020). https:\/\/pi3.informatik.uni-mannheim.de\/~moer\/querycompiler.pdf"},{"key":"906_CR39","unstructured":"Moerkotte, G., Neumann, T.: Analysis of two existing and one new dynamic programming algorithm for the generation of optimal bushy join trees without cross products. In: PVLDB (2006)"},{"key":"906_CR40","doi-asserted-by":"crossref","unstructured":"Nam, Y., Han, D., Kim, M.: SPRINTER: A fast n-ary join query processing method for complex OLAP queries. In: Proceedings of SIGMOD\u201920, (2020)","DOI":"10.1145\/3318464.3380565"},{"key":"906_CR41","doi-asserted-by":"crossref","unstructured":"Neumann, T.: Query simplification: graceful degradation for join-order optimization. In: Proceedings of SIGMOD\u201909, (2009)","DOI":"10.1145\/1559845.1559889"},{"key":"906_CR42","doi-asserted-by":"crossref","unstructured":"Neumann, T., Moerkotte, G.: A combined framework for grouping and order optimization. In: Proceedings of VLDB\u201904, (2004)","DOI":"10.1016\/B978-012088469-8.50084-X"},{"key":"906_CR43","unstructured":"Neumann, T., Moerkotte, G.: An efficient framework for order optimization. In: Proceedings of ICDE\u201904, (2004)"},{"key":"906_CR44","doi-asserted-by":"crossref","unstructured":"Neumann, T., Radke, B.: Adaptive optimization of very large join queries. In: Proceedings of SIGMOD\u201918, (2018)","DOI":"10.1145\/3183713.3183733"},{"key":"906_CR45","unstructured":"Ono, K., Lohman, G.M.: Measuring the complexity of join enumeration in query optimization. In: Proceedings of VLDB\u201990, (1990)"},{"key":"906_CR46","unstructured":"Pellenkoft, A., Galindo-Legaria, C.A., Kersten, M.L.: The complexity of transformation-based join enumeration. In: Proceedings of VLDB\u201997, (1997)"},{"key":"906_CR47","unstructured":"Ramakrishnan, R., Donjerkovic, D., Ranganathan, A., Beyer, K.S., Krishnaprasad, M.: SRQL: sorted relational query language. In: Proceedings of SSDM\u201998, (1998)"},{"key":"906_CR48","doi-asserted-by":"crossref","unstructured":"Schuh, S., Chen, X., Dittrich, J.: An experimental comparison of thirteen relational equi-joins in main memory. In: Proceedings of SIGMOD\u201916, (2016)","DOI":"10.1145\/2882903.2882917"},{"key":"906_CR49","doi-asserted-by":"crossref","unstructured":"Selinger, P.G., Astrahan, M.M., Chamberlin, D.D., Lorie, R.A., Price, T.G.: Access path selection in a relational database management system. In: Proceedings of SIGMOD\u201979, (1979)","DOI":"10.1145\/582096.582099"},{"key":"906_CR50","doi-asserted-by":"crossref","unstructured":"Shanbhag, A., Sudarshan, S.: Optimizing join enumeration in transformation-based query optimizers. PVLDB 7(12), (2014)","DOI":"10.14778\/2732977.2732997"},{"key":"906_CR51","doi-asserted-by":"crossref","unstructured":"Simmen, D.E., Shekita, E.J., Malkemus, T.: Fundamental techniques for order optimization. In: Proceedings of SIGMOD\u201996, (1996)","DOI":"10.1145\/233269.233320"},{"issue":"1","key":"906_CR52","first-page":"21","volume":"13","author":"G Slivinskas","year":"2001","unstructured":"Slivinskas, G., Jensen, C.S., Snodgrass, R.T.: A foundation for conventional and temporal query optimization addressing duplicates and ordering. TKDE 13(1), 21\u201349 (2001)","journal-title":"TKDE"},{"issue":"2","key":"906_CR53","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1145\/565117.565119","volume":"31","author":"G Slivinskas","year":"2002","unstructured":"Slivinskas, G., Jensen, C.S., Snodgrass, R.T.: Bringing order to query optimization. SIGMOD Rec. 31(2), 5\u201314 (2002)","journal-title":"SIGMOD Rec."},{"issue":"1","key":"906_CR54","doi-asserted-by":"publisher","first-page":"85","DOI":"10.14778\/3485450.3485459","volume":"15","author":"J Sun","year":"2021","unstructured":"Sun, J., Zhang, J., Sun, Z., Li, G., Tang, N.: Learned cardinality estimation: a design space exploration and a comparative evaluation. Proc. VLDB Endowment 15(1), 85\u201397 (2021)","journal-title":"Proc. VLDB Endowment"},{"key":"906_CR55","unstructured":"Vance, B.: Join-order Optimization with Cartesian Products. Ph.D. thesis, Oregon Graduate Institute of Science and Technology, (1998)"},{"key":"906_CR56","doi-asserted-by":"crossref","unstructured":"Vance, B., Maier, D.: Rapid bushy join-order optimization with cartesian products. In: Proceedings of SIGMOD\u201996, (1996)","DOI":"10.1145\/233269.233317"},{"key":"906_CR57","doi-asserted-by":"crossref","unstructured":"Wang, X., Cherniack, M.: Avoiding sorting and grouping in processing queries. In: Proceedings of VLDB\u201993, (2003)","DOI":"10.1016\/B978-012722442-8\/50078-1"},{"key":"906_CR58","volume-title":"Principles of Database Query Processing for Advanced Applications","author":"CT Yu","year":"1998","unstructured":"Yu, C.T., Meng, W.: Principles of Database Query Processing for Advanced Applications. Morgan Kaufmann, Burlington (1998)"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-025-00906-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00778-025-00906-y","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-025-00906-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T05:23:05Z","timestamp":1770441785000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00778-025-00906-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,26]]},"references-count":58,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,5]]}},"alternative-id":["906"],"URL":"https:\/\/doi.org\/10.1007\/s00778-025-00906-y","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,3,26]]},"assertion":[{"value":"17 June 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 December 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 February 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 March 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 February 2026","order":6,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":7,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The original online version of this article was revised due to retrospective open access order.","order":8,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"31"}}