{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T20:55:31Z","timestamp":1767905731837,"version":"3.49.0"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,3,1]],"date-time":"2024-03-01T00:00:00Z","timestamp":1709251200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,3,18]],"date-time":"2024-03-18T00:00:00Z","timestamp":1710720000000},"content-version":"vor","delay-in-days":17,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004168","name":"Universit\u00e4t zu L\u00fcbeck","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004168","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Datenbank Spektrum"],"published-print":{"date-parts":[[2024,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The join order has a\u00a0huge impact on the execution time of a\u00a0query, such that finding an optimal join order plays a\u00a0crucial role in query optimization. However, join order optimization is known to be NP-hard. Hence, in this paper, we propose an approach for accelerating join order optimization by quantum computers. We extend our previous approach supporting bushy join trees by splitting the search space of possible join orders and solving each of these subspaces on currently available quantum computers to optimize the join of more relations than our previous approach. We have integrated our approach to quantum query optimization in the relational database management system PostgreSQL to conduct studies with real-world queries. In our experiments, we show that we can perform join order optimization up to 7 relations for real-world queries using quantum annealing and up to 8 relations for artificial queries using simulated annealing with a\u00a0reasonable number of QUBO problems solved by D\u2011Wave\u2019s Quantum Annealer. Furthermore, we show that our approach can be also used to perform join-order for queries joining five relations on circuit-based quantum computers running the quantum approximate optimization algorithm (QAOA) and variational quantum eigensolver (VQE) approaches.<\/jats:p>","DOI":"10.1007\/s13222-024-00468-3","type":"journal-article","created":{"date-parts":[[2024,3,18]],"date-time":"2024-03-18T14:01:44Z","timestamp":1710770504000},"page":"21-32","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Quantum Join Ordering by Splitting the Search Space of QUBO Problems"],"prefix":"10.1007","volume":"24","author":[{"given":"Nitin","family":"Nayak","sequence":"first","affiliation":[]},{"given":"Tobias","family":"Winker","sequence":"additional","affiliation":[]},{"given":"Umut","family":"\u00c7al\u0131ky\u0131lmaz","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5196-1117","authenticated-orcid":false,"given":"Sven","family":"Groppe","sequence":"additional","affiliation":[]},{"given":"Jinghua","family":"Groppe","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,3,18]]},"reference":[{"key":"468_CR1","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1145\/263661.263687","volume-title":"Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on principles of database systems","author":"W Scheufele","year":"1997","unstructured":"Scheufele W, Moerkotte G (1997) On the complexity of generating optimal plans with cross products. In: Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on principles of database systems, pp 238\u2013248"},{"key":"468_CR2","first-page":"1","volume-title":"Proceedings of the international workshop on big data in emergent distributed environments","author":"N Nayak","year":"2023","unstructured":"Nayak N, Rehfeld J, Winker T, Warnke B, \u00c7alikyilmaz U, Groppe S (2023) Constructing optimal bushy join trees by solving qubo problems on quantum hardware and simulators. In: Proceedings of the international workshop on big data in emergent distributed environments, pp 1\u20137"},{"key":"468_CR3","unstructured":"Lewis MW, Glover FW (2017) Quadratic unconstrained binary optimization problem preprocessing: theory and empirical analysis. https:\/\/arxiv.org\/abs\/1705.09844 (CoRR abs\/1705.09844). Accessed 14.03.2024"},{"key":"468_CR4","doi-asserted-by":"publisher","DOI":"10.1038\/ncomms5213","author":"A Peruzzo","year":"2014","unstructured":"Peruzzo A, McClean J, Shadbolt P, Yung M-H, Zhou X-Q, Love PJ, Aspuru-Guzik A, O\u2019Brien JL (2014) A\u00a0variational eigenvalue solver on a\u00a0photonic quantum processor. Nat Commun. https:\/\/doi.org\/10.1038\/ncomms5213","journal-title":"Nat Commun"},{"key":"468_CR5","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.1411.4028","author":"E Farhi","year":"2014","unstructured":"Farhi E, Goldstone J, Gutmann S (2014) A\u00a0quantum approximate optimization algorithm. ArXiv. https:\/\/doi.org\/10.48550\/ARXIV.1411.4028 (https:\/\/arxiv.org\/abs\/1411.4028)","journal-title":"ArXiv"},{"key":"468_CR6","volume-title":"The d\u2011wave advantage system: an overview","author":"C McGeoch","year":"2020","unstructured":"McGeoch C, Farr\u00e9 P (2020) The d\u2011wave advantage system: an overview. D\u2011Wave Systems Inc, Burnaby, BC, Canada, Tech. Rep"},{"key":"468_CR7","volume-title":"Quantum computation and quantum information","author":"MA Nielsen","year":"2010","unstructured":"Nielsen MA, Chuang IL (2010) Quantum computation and quantum information. Cambridge University Press"},{"key":"468_CR8","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1145\/237814.237866","volume-title":"Proceedings of the twenty-eighth annual ACM symposium on theory of computing","author":"LK Grover","year":"1996","unstructured":"Grover LK (1996) A\u00a0fast quantum mechanical algorithm for database search. In: Proceedings of the twenty-eighth annual ACM symposium on theory of computing, pp 212\u2013219"},{"issue":"2","key":"468_CR9","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1103\/PhysRevLett.79.325","volume":"79","author":"LK Grover","year":"1997","unstructured":"Grover LK (1997) Quantum mechanics helps in searching for a\u00a0needle in a\u00a0haystack. Phys Rev Lett 79(2):325","journal-title":"Phys Rev Lett"},{"key":"468_CR10","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1109\/SFCS.1994.365700","volume-title":"Proceedings 35th annual symposium on foundations of computer science","author":"PW Shor","year":"1994","unstructured":"Shor PW (1994) Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings 35th annual symposium on foundations of computer science. Ieee, pp 124\u2013134"},{"issue":"5516","key":"468_CR11","doi-asserted-by":"publisher","first-page":"472","DOI":"10.1126\/science.1057726","volume":"292","author":"E Farhi","year":"2001","unstructured":"Farhi E, Goldstone J, Gutmann S, Lapan J, Lundgren A, Preda D (2001) A\u00a0quantum adiabatic evolution algorithm applied to random instances of an np-complete problem. Science 292(5516):472\u2013475","journal-title":"Science"},{"issue":"5\u20136","key":"468_CR12","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/0009-2614(94)00117-0","volume":"219","author":"AB Finnila","year":"1994","unstructured":"Finnila AB, Gomez MA, Sebenik C, Stenson C, Doll JD (1994) Quantum annealing: a\u00a0new method for minimizing multidimensional functions. Chem Phys Lett 219(5\u20136):343\u2013348","journal-title":"Chem Phys Lett"},{"issue":"5","key":"468_CR13","doi-asserted-by":"publisher","first-page":"5355","DOI":"10.1103\/PhysRevE.58.5355","volume":"58","author":"T Kadowaki","year":"1998","unstructured":"Kadowaki T, Nishimori H (1998) Quantum annealing in the transverse ising model. Phys Rev\u00a0E 58(5):5355","journal-title":"Phys Rev E"},{"issue":"16","key":"468_CR14","doi-asserted-by":"publisher","first-page":"11828","DOI":"10.1103\/PhysRevB.39.11828","volume":"39","author":"P Ray","year":"1989","unstructured":"Ray P, Chakrabarti BK, Chakrabarti A (1989) Sherrington-kirkpatrick model in a\u00a0transverse field: absence of replica symmetry breaking due to quantum fluctuations. Phys Rev\u00a0B 39(16):11828","journal-title":"Phys Rev B"},{"issue":"5564","key":"468_CR15","doi-asserted-by":"publisher","first-page":"2427","DOI":"10.1126\/science.1068774","volume":"295","author":"GE Santoro","year":"2002","unstructured":"Santoro GE, Marton\u00e1k R, Tosatti E, Car R (2002) Theory of quantum annealing of an ising spin glass. Science 295(5564):2427\u20132430","journal-title":"Science"},{"key":"468_CR16","first-page":"97","volume-title":"Stochastic Processes, Physics and Geometry: Proceedings of the Ascona-Locarno Conference","author":"B Apolloni","year":"1990","unstructured":"Apolloni B, Cesa-Bianchi N, De Falco D (1990) A\u00a0numerical implementation of \u201cquantum annealing\u201d. In: Stochastic Processes, Physics and Geometry: Proceedings of the Ascona-Locarno Conference, pp 97\u2013111"},{"issue":"6","key":"468_CR17","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1143\/JPSJ.5.435","volume":"5","author":"T Kato","year":"1950","unstructured":"Kato T (1950) On the adiabatic theorem of quantum mechanics. J\u00a0Phys Soc Japan 5(6):435\u2013439","journal-title":"J Phys Soc Japan"},{"key":"468_CR18","doi-asserted-by":"publisher","unstructured":"Jansen S, Ruskai M-B, Seiler R (2007) Bounds for the adiabatic approximation with applications to quantum computation. J\u00a0Math Phys 48(10). https:\/\/doi.org\/10.1063\/1.2798382","DOI":"10.1063\/1.2798382"},{"issue":"3\u20134","key":"468_CR19","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/BF01343193","volume":"51","author":"M Born","year":"1928","unstructured":"Born M, Fock V (1928) Beweis des adiabatensatzes. Z\u00a0Phys 51(3\u20134):165\u2013180","journal-title":"Z Phys"},{"key":"468_CR20","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1007\/s10878-014-9734-0","volume":"28","author":"G Kochenberger","year":"2014","unstructured":"Kochenberger G, Hao J-K, Glover F, Lewis M, L\u00fc Z, Wang H, Wang Y (2014) The unconstrained binary quadratic programming problem: a\u00a0survey. J\u00a0Comb Optim 28:58\u201381","journal-title":"J Comb Optim"},{"issue":"1","key":"468_CR21","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/s10479-022-04634-2","volume":"314","author":"F Glover","year":"2022","unstructured":"Glover F, Kochenberger G, Du Hennig R (2022) Quantum bridge analytics i: a\u00a0tutorial on formulating and using qubo models. Ann Oper Res 314(1):141\u2013183","journal-title":"Ann Oper Res"},{"key":"468_CR22","volume-title":"Exactly solved model in statistica","author":"RJ Baxter","year":"1989","unstructured":"Baxter RJ (1989) Exactly solved model in statistica vol 109"},{"key":"468_CR23","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1109\/ISTCS.1995.377033","volume-title":"Proceedings third Israel symposium on the theory of computing and systems","author":"U Feige","year":"1995","unstructured":"Feige U, Goemans M (1995) Approximating the value of two power proof systems, with applications to max 2sat and max dicut. In: Proceedings third Israel symposium on the theory of computing and systems. IEEE, pp 182\u2013189"},{"key":"468_CR24","doi-asserted-by":"publisher","first-page":"5","DOI":"10.3389\/fphy.2014.00005","volume":"2","author":"A Lucas","year":"2014","unstructured":"Lucas A (2014) Ising formulations of many np problems. Front Phys 2:5","journal-title":"Front Phys"},{"issue":"1","key":"468_CR25","doi-asserted-by":"publisher","first-page":"4213","DOI":"10.1038\/ncomms5213","volume":"5","author":"A Peruzzo","year":"2014","unstructured":"Peruzzo A, McClean J, Shadbolt P, Yung M-H, Zhou X-Q, Love PJ, Aspuru-Guzik A, O\u2019brien JL (2014) A\u00a0variational eigenvalue solver on a\u00a0photonic quantum processor. Nat Commun 5(1):4213","journal-title":"Nat Commun"},{"issue":"1","key":"468_CR26","doi-asserted-by":"publisher","first-page":"014008","DOI":"10.1088\/2058-9565\/aad3e4","volume":"4","author":"J Romero","year":"2018","unstructured":"Romero J, Babbush R, McClean JR, Hempel C, Love PJ, Aspuru-Guzik A (2018) Strategies for quantum computing molecular energies using the unitary coupled cluster ansatz. Quantum Sci Technol 4(1):14008","journal-title":"Quantum Sci Technol"},{"key":"468_CR27","volume-title":"A\u00a0quantum approximate optimization algorithm","author":"E Farhi","year":"2014","unstructured":"Farhi E, Goldstone J, Gutmann S (2014) A\u00a0quantum approximate optimization algorithm (arXiv preprint arXiv:1411.4028)"},{"key":"468_CR28","volume-title":"The quantum approximate optimization algorithm at high depth for maxcut on large-girth regular graphs and the sherrington-kirkpatrick model","author":"J Basso","year":"2021","unstructured":"Basso J, Farhi E, Marwaha K, Villalonga B, Zhou L (2021) The quantum approximate optimization algorithm at high depth for maxcut on large-girth regular graphs and the sherrington-kirkpatrick model (arXiv preprint arXiv:2110.14206)"},{"issue":"2","key":"468_CR29","doi-asserted-by":"publisher","first-page":"022304","DOI":"10.1103\/PhysRevA.97.022304","volume":"97","author":"Z Wang","year":"2018","unstructured":"Wang Z, Hadfield S, Jiang Z, Rieffel EG (2018) Quantum approximate optimization algorithm for maxcut: a\u00a0fermionic view. Phys Rev\u00a0A 97(2):22304","journal-title":"Phys Rev A"},{"key":"468_CR30","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1007\/978-3-031-32041-5_13","volume-title":"Quantum annealing vs. QAOA: 127 qubit higher-order Ising problems on\u00a0NISQ computers","author":"E Pelofske","year":"2023","unstructured":"Pelofske E, B\u00e4rtschi A, Eidenbenz S (2023) Quantum annealing vs. QAOA: 127 qubit higher-order Ising problems on\u00a0NISQ computers. Springer, pp 240\u2013258 https:\/\/doi.org\/10.1007\/978-3-031-32041-5_13 (https:\/\/doi.org\/10.1007\/978-3-031-32041-5_13)"},{"key":"468_CR31","volume-title":"Database management systems","author":"R Ramakrishnan","year":"2003","unstructured":"Ramakrishnan R, Gehrke J, Gehrke J (2003) Database management systems vol 3. McGraw-Hill, New York"},{"key":"468_CR32","volume-title":"Database system concepts","author":"A Silberschatz","year":"2011","unstructured":"Silberschatz A, Korth HF, Sudarshan S (2011) Database system concepts"},{"key":"468_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, Kemper A, Neumann T (2018) Query optimization through the looking glass, and what we found running the join order benchmark. Vldb\u00a0J 27:643\u2013668","journal-title":"Vldb J"},{"key":"468_CR34","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1145\/582095.582099","volume-title":"Proceedings of the 1979 ACM SIGMOD international conference on management of data","author":"PG Selinger","year":"1979","unstructured":"Selinger PG, Astrahan MM, Chamberlin DD, Lorie RA, Price TG (1979) Access path selection in a\u00a0relational database management system. In: Proceedings of the 1979 ACM SIGMOD international conference on management of data, pp 23\u201334"},{"key":"468_CR35","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/s007780050040","volume":"6","author":"M Steinbrunn","year":"1997","unstructured":"Steinbrunn M, Moerkotte G, Kemper A (1997) Heuristic and randomized optimization for the join ordering problem. Vldb\u00a0J 6:191\u2013208","journal-title":"Vldb J"},{"key":"468_CR36","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/978-3-540-92137-0_21","volume-title":"Advances in Computation and Intelligence: Third International Symposium, ISICA 2008","author":"N Li","year":"2008","unstructured":"Li N, Liu Y, Dong Y, Gu J (2008) Application of ant colony optimization algorithm to multi-join query optimization. In: Advances in Computation and Intelligence: Third International Symposium, ISICA 2008. Springer, Wuhan, China, pp 189\u2013197 (December 19\u201321, 2008 Proceedings 3)"},{"key":"468_CR37","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1109\/ICMTMA.2015.109","volume-title":"2015 seventh international conference on measuring technology and mechatronics automation","author":"X Mingyao","year":"2015","unstructured":"Mingyao X, Xiongfei L (2015) Embedded database query optimization algorithm based on particle swarm optimization. In: 2015 seventh international conference on measuring technology and mechatronics automation. IEEE, pp 429\u2013432"},{"key":"468_CR38","first-page":"1","volume-title":"Proceedings of the first international workshop on exploiting artificial intelligence techniques for data management","author":"R Marcus","year":"2018","unstructured":"Marcus R, Papaemmanouil O (2018) Deep reinforcement learning for join order enumeration. In: Proceedings of the first international workshop on exploiting artificial intelligence techniques for data management, pp 1\u20134"},{"issue":"1","key":"468_CR39","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3588946","volume":"1","author":"M Sch\u00f6nberger","year":"2023","unstructured":"Sch\u00f6nberger M, Scherzinger S, Mauerer W (2023) Ready to leap (by co-design)? join order optimisation on quantum hardware. Proc Acm Manag Data 1(1):1\u201327","journal-title":"Proc Acm Manag Data"},{"key":"468_CR40","first-page":"1","volume-title":"Proceedings of the international workshop on big data in emergent distributed environments","author":"T Winker","year":"2023","unstructured":"Winker T, \u00c7alikyilmaz U, Gruenwald L, Groppe S (2023) Quantum machine learning for join order optimization using variational quantum circuits. In: Proceedings of the international workshop on big data in emergent distributed environments, pp 1\u20137"},{"key":"468_CR41","volume-title":"Quantum optimisation of general join trees","author":"M Sch\u00f6nberger","year":"2022","unstructured":"Sch\u00f6nberger M, Trummer I, Mauerer W (2022) Quantum optimisation of general join trees"},{"key":"468_CR42","unstructured":"(2023) Row estimation examples. https:\/\/www.postgresql.org\/docs\/current\/row-estimation-examples.html. Accessed 14.03.2024"}],"container-title":["Datenbank-Spektrum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13222-024-00468-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s13222-024-00468-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13222-024-00468-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,27]],"date-time":"2024-03-27T10:27:55Z","timestamp":1711535275000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s13222-024-00468-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3]]}},"alternative-id":["468"],"URL":"https:\/\/doi.org\/10.1007\/s13222-024-00468-3","relation":{},"ISSN":["1618-2162","1610-1995"],"issn-type":[{"value":"1618-2162","type":"print"},{"value":"1610-1995","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3]]},"assertion":[{"value":"22 October 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 February 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 March 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}