{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,27]],"date-time":"2026-05-27T13:08:13Z","timestamp":1779887293599,"version":"3.53.1"},"reference-count":65,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2023,11]]},"abstract":"<jats:p>Finding the optimal join order (JO) is one of the most important problems in query optimisation, and has been extensively considered in research and practise. As it involves huge search spaces, approximation approaches and heuristics are commonly used, which explore a reduced solution space at the cost of solution quality. To explore even large JO search spaces, we may consider special-purpose software, such as mixed-integer linear programming (MILP) solvers, which have successfully solved JO problems. However, even mature solvers cannot overcome the limitations of conventional hardware prompted by the end of Moore's law.<\/jats:p>\n          <jats:p>\n            We consider\n            <jats:italic>quantum-inspired<\/jats:italic>\n            digital annealing hardware, which takes inspiration from quantum processing units (QPUs). Unlike QPUs, which likely remain limited in size and reliability in the near and mid-term future, the digital annealer (DA) can solve large instances of mathematically encoded optimisation problems\n            <jats:italic>today.<\/jats:italic>\n            We derive a novel, native encoding for the JO problem tailored to this class of machines that substantially improves over known MILP and quantum-based encodings, and reduces encoding size over the state-of-the-art. By augmenting the computation with a novel readout method, we derive valid join orders for each solution obtained by the (probabilistically operating) DA. Most importantly and despite an extremely large solution space, our approach scales to practically relevant dimensions of around 50 relations and improves result quality over conventionally employed approaches, adding a novel alternative to solving the long-standing JO problem.\n          <\/jats:p>","DOI":"10.14778\/3632093.3632112","type":"journal-article","created":{"date-parts":[[2024,1,20]],"date-time":"2024-01-20T11:26:31Z","timestamp":1705749991000},"page":"511-524","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["Quantum-Inspired Digital Annealing for Join Ordering"],"prefix":"10.14778","volume":"17","author":[{"given":"Manuel","family":"Sch\u00f6nberger","sequence":"first","affiliation":[{"name":"Technical University of Applied Sciences Regensburg, Regensburg, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Immanuel","family":"Trummer","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, NY, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wolfgang","family":"Mauerer","sequence":"additional","affiliation":[{"name":"Technical University of Applied Sciences Regensburg, Siemens AG, Corporate Research, Regensburg\/Munich, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,1,20]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1103\/RevModPhys.90.015002"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2627692.2627697"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.3389\/fphy.2019.00048"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3410566.3410593"},{"key":"e_1_2_1_5_1","first-page":"1","article-title":"Hardware Accelerating the Optimization of Transaction Schedules via Quantum Annealing by Avoiding Blocking","volume":"7","author":"Bittner Tim","year":"2020","unstructured":"Tim Bittner and Sven Groppe. 2020. Hardware Accelerating the Optimization of Transaction Schedules via Quantum Annealing by Avoiding Blocking. Open Journal of Cloud Computing (OJCC) 7, 1 (2020), 1--21.","journal-title":"Open Journal of Cloud Computing (OJCC)"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447916"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/3598581.3598603"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543650"},{"key":"e_1_2_1_9_1","volume-title":"Database Theory --- ICDT '95","author":"Cluet Sophie","unstructured":"Sophie Cluet and Guido Moerkotte. 1995. On the complexity of generating optimal left-deep processing trees with cross products. In Database Theory --- ICDT '95. Springer Berlin Heidelberg, Berlin, Heidelberg, 54--67."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687553.1687572"},{"key":"e_1_2_1_11_1","volume-title":"Murat Ali Bayir, and Ahmet Cosar","author":"Dokeroglu Tansel","year":"2014","unstructured":"Tansel Dokeroglu, Murat Ali Bayir, and Ahmet Cosar. 2014. Integer Linear Programming Solution for the Multiple Query Optimization Problem. In Information Sciences and Systems 2014, Tadeusz Czach\u00f3rski, Erol Gelenbe, and Ricardo Lent (Eds.). Springer International Publishing, Cham, 51--60."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/NOMS54207.2022.9789782"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3465998.3466015"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jfranklin.2022.08.021"},{"key":"e_1_2_1_15_1","volume-title":"Fujitsu Digital Annealer - solving large-scale combinatorial optimization problems instantly. Retrieved","author":"Limited Fujitsu","year":"2023","unstructured":"Fujitsu Limited. 2023. Fujitsu Digital Annealer - solving large-scale combinatorial optimization problems instantly. Retrieved November 9, 2023 from https:\/\/www.fujitsu.com\/emeia\/services\/business-services\/digital-annealer\/what-is-digital-annealer\/"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3472163.3472164"},{"key":"e_1_2_1_17_1","volume-title":"Retrieved","author":"Hipp Richard D","year":"2020","unstructured":"Richard D Hipp. 2020. SQLite. Retrieved November 10, 2023 from https:\/\/www.sqlite.org\/index.html"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.3390\/jrfm14010034"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICEC.1994.349926"},{"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.1016\/j.ymssp.2022.109957"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/93605.98740"},{"key":"e_1_2_1_23_1","volume-title":"CIDR. 1--8. arXiv:1809.00677 Retrieved","author":"Kipf Andreas","year":"2023","unstructured":"Andreas Kipf, Thomas Kipf, Bernhard Radke, Viktor Leis, Peter Boncz, and Alfons Kemper. 2018. Learned cardinalities: estimating correlated joins with deep learning. In CIDR. 1--8. arXiv:1809.00677 Retrieved November 10, 2023 from http:\/\/arxiv.org\/abs\/1809.00677"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","unstructured":"S. Kirkpatrick C. D. Gelatt and M. P. Vecchi. 1983. Optimization by Simulated Annealing. Science 220 4598 (1983) 671--680. arXiv:https:\/\/www.science.org\/doi\/pdf\/10.1126\/science.220.4598.671 10.1126\/science.220.4598.671","DOI":"10.1126\/science.220.4598.671"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/645913.671481"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3387940.3391472"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0480-7"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342644"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3542700.3542702"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90687-B"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASP-DAC47756.2020.9045100"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/SANER53432.2022.00148"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3465998.3466005"},{"key":"e_1_2_1_36_1","volume-title":"Retrieved","author":"Moerkotte Guido","year":"2023","unstructured":"Guido Moerkotte. 2023. Building query compilers. Retrieved November 10, 2023 from https:\/\/pi3.informatik.uni-mannheim.de\/~moer\/querycompiler.pdf"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/1182635.1164207"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376672"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3465998.3466006"},{"key":"e_1_2_1_40_1","volume-title":"Retrieved","author":"Nakayama Hiroshi","year":"2021","unstructured":"Hiroshi Nakayama, Junpei Koyama, Noboru Yoneoka, and Toshiyuki Miyazawa. 2021. Description: Third Generation Digital Annealer Technology. Retrieved November 10, 2023 from https:\/\/www.fujitsu.com\/global\/documents\/about\/research\/techintro\/3rd-g-da_en.pdf"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3579142.3594298"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559889"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183733"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1140\/epjst\/e2015-02349-9"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDEW.2007.4401027"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/QSW59989.2023.00022"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588946"},{"key":"e_1_2_1_49_1","volume-title":"Joint Workshops at 49th International Conference on Very Large Data Bases (VLDBW'23) --- International Workshop on Quantum Data Science and Management (QDSM '23).","author":"Sch\u00f6nberger Manuel","unstructured":"Manuel Sch\u00f6nberger, Immanuel Trummer, and Wolfgang Mauerer. 2023. Quantum Optimisation of General Join Trees. In Joint Workshops at 49th International Conference on Very Large Data Bases (VLDBW'23) --- International Workshop on Quantum Data Science and Management (QDSM '23)."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/582095.582099"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780050040"},{"key":"e_1_2_1_52_1","volume-title":"2022 European Conference on Optical Communication (ECOC). 1--4.","author":"Sugimura Masahiko","year":"2022","unstructured":"Masahiko Sugimura, Mikinori Kobayashi, Hidetoshi Matsumura, Xi Wang, and Paparao Palacharla. 2022. Accelerate Optical Network Modernization through Quantum-inspired Digital Annealing. In 2022 European Conference on Optical Communication (ECOC). 1--4."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/67544.66961"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/971701.50203"},{"key":"e_1_2_1_55_1","volume-title":"Retrieved","author":"Transaction Processing Performance Council","year":"2023","unstructured":"Transaction Processing Performance Council. 2023. TPC Benchmark H. Retrieved November 10, 2023 from https:\/\/www.tpc.org\/"},{"key":"e_1_2_1_56_1","volume-title":"Retrieved","author":"Transaction Processing Performance Council","year":"2023","unstructured":"Transaction Processing Performance Council. 2023. TPC Benchmark DS. Retrieved November 10, 2023 from https:\/\/www.tpc.org\/"},{"key":"e_1_2_1_57_1","volume-title":"Retrieved","author":"Trummer Immanuel","year":"2016","unstructured":"Immanuel Trummer. 2016. Query Optimizer Library. Retrieved November 10, 2023 from https:\/\/github.com\/itrummer\/query-optimizer-lib"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.14778\/2947618.2947621"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.14778\/2947618.2947622"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064039"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/233269.233317"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","unstructured":"Adrian Vogelsgesang Michael Haubenschild Jan Finis Alfons Kemper Viktor Leis Tobias Muehlbauer Thomas Neumann and Manuel Then. 2018. Get real: How benchmarks Fail to Represent the Real World. In DBTest. 10.1145\/3209950.3209952","DOI":"10.1145\/3209950.3209952"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/3555041.3589404"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-21867-5_7"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.5555\/645923.673657"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00116"},{"key":"e_1_2_1_67_1","volume-title":"High Performance Computing","author":"Zbinden Stefanie","unstructured":"Stefanie Zbinden, Andreas Bartschi, Hristo Djidjev, and Stephan Eidenbenz. 2020. Embedding algorithms for quantum annealers with Chimera and Pegasus connection topologies. In High Performance Computing. Springer International Publishing, Cham, 187--206."},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/3465998.3466016"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3632093.3632112","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,20]],"date-time":"2024-01-20T11:27:40Z","timestamp":1705750060000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3632093.3632112"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11]]},"references-count":65,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,11]]}},"alternative-id":["10.14778\/3632093.3632112"],"URL":"https:\/\/doi.org\/10.14778\/3632093.3632112","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,11]]},"assertion":[{"value":"2024-01-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}