{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,27]],"date-time":"2026-01-27T14:13:00Z","timestamp":1769523180686,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":25,"publisher":"ACM","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,22]]},"DOI":"10.1145\/3736393.3736695","type":"proceedings-article","created":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T12:39:22Z","timestamp":1750682362000},"page":"20-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Hybrid Quantum-Classical Optimization for Bushy Join Trees"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5265-9312","authenticated-orcid":false,"given":"Hanwen","family":"Liu","sequence":"first","affiliation":[{"name":"University of Southern California, Los Angeles, California, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-9988-4637","authenticated-orcid":false,"given":"Abhishek","family":"Kumar","sequence":"additional","affiliation":[{"name":"University of Southern California, Los Angeles, California, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4784-9100","authenticated-orcid":false,"given":"Federico","family":"Spedalieri","sequence":"additional","affiliation":[{"name":"University of Southern California, Los Angeles, California, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-2102-5241","authenticated-orcid":false,"given":"Ibrahim","family":"Sabek","sequence":"additional","affiliation":[{"name":"University of Southern California, Los Angeles, California, USA"}]}],"member":"320","published-online":{"date-parts":[[2025,6,23]]},"reference":[{"key":"e_1_3_3_1_2_2","doi-asserted-by":"crossref","unstructured":"MHS Amin. 2005. Flux qubit in charge-phase regime. Physical Review B\u2014Condensed Matter and Materials Physics 71 2 (2005) 024504.","DOI":"10.1103\/PhysRevB.71.024504"},{"key":"e_1_3_3_1_3_2","doi-asserted-by":"crossref","unstructured":"Maliheh Aramon Gili Rosenberg et\u00a0al. 2019. Physics-inspired optimization for quadratic unconstrained problems using a digital annealer. Frontiers in Physics 7 (2019) 48.","DOI":"10.3389\/fphy.2019.00048"},{"key":"e_1_3_3_1_4_2","first-page":"54","volume-title":"International Conference on Database Theory","author":"Cluet Sophie","year":"1995","unstructured":"Sophie Cluet and Guido Moerkotte. 1995. On the complexity of generating optimal left-deep processing trees with cross products. In International Conference on Database Theory. Springer, 54\u201367."},{"key":"e_1_3_3_1_5_2","unstructured":"D-Wave Leap\u2019s Hybrid Solvers. 2024. https:\/\/docs.dwavesys.com\/docs\/latest\/doc_leap_hybrid.html."},{"key":"e_1_3_3_1_6_2","doi-asserted-by":"crossref","unstructured":"Toshihide Ibaraki and Tiko Kameda. 1984. On the optimal nesting order for computing N-relational joins. ACM Trans. Database Syst. 9 3 (Sept. 1984) 482\u2013502. https:\/\/doi.org\/10.1145\/1270.1498","DOI":"10.1145\/1270.1498"},{"key":"e_1_3_3_1_7_2","doi-asserted-by":"crossref","unstructured":"M.\u00a0W. Johnson M.\u00a0H.\u00a0S. Amin et\u00a0al. 2011. Quantum annealing with manufactured spins. Nature 473 7346 (2011) 194\u2013198. https:\/\/doi.org\/10.1038\/nature10012","DOI":"10.1038\/nature10012"},{"key":"e_1_3_3_1_8_2","doi-asserted-by":"crossref","unstructured":"Tadashi Kadowaki and Hidetoshi Nishimori. 1998. Quantum annealing in the transverse Ising model. Phys. Rev. E 58 (Nov 1998) 5355\u20135363. Issue 5. https:\/\/doi.org\/10.1103\/PhysRevE.58.5355","DOI":"10.1103\/PhysRevE.58.5355"},{"key":"e_1_3_3_1_9_2","doi-asserted-by":"crossref","unstructured":"Viktor Leis Andrey Gubichev et\u00a0al. 2015. How Good Are Query Optimizers Really? Proc. VLDB Endow. 9 3 (2015) 204\u2013215. https:\/\/doi.org\/10.14778\/2850583.2850594","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_3_3_1_10_2","series-title":"(QDML \u201925)","volume-title":"Proc. 1st Workshop Quantum Data and Machine Learning","author":"Liu Hanwen","year":"2025","unstructured":"Hanwen Liu, Pranshi Saxena, Federico Spedalieri, and Ibrahim Sabek. 2025. Optimizing Join Orders via Constrained Quadratic Models (Abstract). In Proc. 1st Workshop Quantum Data and Machine Learning (HongKong, China) (QDML \u201925)."},{"key":"e_1_3_3_1_11_2","doi-asserted-by":"crossref","unstructured":"Andrew Lucas. 2014. Ising formulations of many NP problems. Frontiers in Physics 2 (2014). https:\/\/doi.org\/10.3389\/fphy.2014.00005","DOI":"10.3389\/fphy.2014.00005"},{"key":"e_1_3_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.5555\/1182635.1164207"},{"key":"e_1_3_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376672"},{"key":"e_1_3_3_1_14_2","volume-title":"MySQL 8.4 Reference Manual (8.4 ed.)","author":"Team MySQL Documentation","year":"2025","unstructured":"MySQL Documentation Team. 2025. MySQL 8.4 Reference Manual (8.4 ed.). https:\/\/dev.mysql.com\/doc\/en\/"},{"key":"e_1_3_3_1_15_2","series-title":"(BiDEDE \u201923)","volume-title":"Proceedings of the International Workshop on Big Data in Emergent Distributed Environments","author":"Nayak Nitin","year":"2023","unstructured":"Nitin Nayak, Jan Rehfeld, et\u00a0al. 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(BiDEDE \u201923). Article 7. https:\/\/doi.org\/10.1145\/3579142.3594298"},{"key":"e_1_3_3_1_16_2","doi-asserted-by":"crossref","unstructured":"Nitin Nayak Tobias Winker et\u00a0al. 2024. Quantum Join Ordering by Splitting the Search Space of QUBO Problems. Datenbank-Spektrum 24 1 (2024) 21\u201332.","DOI":"10.1007\/s13222-024-00468-3"},{"key":"e_1_3_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183733"},{"key":"e_1_3_3_1_18_2","volume-title":"Oracle Database Reference, 19c (19c ed.)","author":"Corporation Oracle","year":"2025","unstructured":"Oracle Corporation. 2025. Oracle Database Reference, 19c (19c ed.). https:\/\/docs.oracle.com\/en\/database\/oracle\/oracle-database\/19\/refrn\/index.html"},{"key":"e_1_3_3_1_19_2","unstructured":"Eneko Osaba and Pablo Miranda-Rodriguez. 2024. D-Wave\u2019s Nonlinear-Program Hybrid Solver: Description and Performance Analysis. arxiv:https:\/\/arXiv.org\/abs\/2410.07980\u00a0[cs.ET]"},{"key":"e_1_3_3_1_20_2","unstructured":"OSSC-DB. [n. d.]. pg_hint_plan. https:\/\/github.com\/ossc-db\/pg_hint_plan."},{"key":"e_1_3_3_1_21_2","unstructured":"PostgreSQL Global Development Group. [n. d.]. https:\/\/www.postgresql.org\/."},{"key":"e_1_3_3_1_22_2","series-title":"(Q-Data \u201924)","first-page":"38","volume-title":"Proc. 1st Workshop Quantum Comput. Quantum-Inspired Technol. Data-Intensive Syst. Appl.","author":"Saxena Pranshi","year":"2024","unstructured":"Pranshi Saxena, Ibrahim Sabek, and Federico Spedalieri. 2024. Constrained Quadratic Model for Optimizing Join Orders. In Proc. 1st Workshop Quantum Comput. Quantum-Inspired Technol. Data-Intensive Syst. Appl. (Santiago, AA, Chile) (Q-Data \u201924). 38\u201344. https:\/\/doi.org\/10.1145\/3665225.3665447"},{"key":"e_1_3_3_1_23_2","doi-asserted-by":"crossref","unstructured":"Manuel Sch\u00f6nberger Stefanie Scherzinger et\u00a0al. 2023. Ready to Leap (by Co-Design)? Join Order Optimisation on Quantum Hardware. Proc. ACM Manag. Data 1 1 Article 92 (may 2023) 27\u00a0pages. https:\/\/doi.org\/10.1145\/3588946","DOI":"10.1145\/3588946"},{"key":"e_1_3_3_1_24_2","doi-asserted-by":"crossref","unstructured":"Manuel Sch\u00f6nberger Immanuel Trummer and Wolfgang Mauerer. 2023. Quantum-inspired digital annealing for join ordering. Proceedings of the VLDB Endowment 17 3 (2023) 511\u2013524.","DOI":"10.14778\/3632093.3632112"},{"key":"e_1_3_3_1_25_2","volume-title":"VLDB Workshops","author":"Sch\u00f6nberger Manuel","year":"2023","unstructured":"Manuel Sch\u00f6nberger, Immanuel Trummer, and Wolfgang Mauerer. 2023. Quantum Optimisation of General Join Trees.. In VLDB Workshops."},{"key":"e_1_3_3_1_26_2","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1145\/582095.582099","volume-title":"Proc. ACM SIGMOD Int. Conf. Manage. Data (SIGMOD \u201979)","author":"Selinger P.\u00a0Griffiths","year":"1979","unstructured":"P.\u00a0Griffiths Selinger, M.\u00a0M. Astrahan, et\u00a0al. 1979. Access path selection in a relational database management system. In Proc. ACM SIGMOD Int. Conf. Manage. Data (SIGMOD \u201979). 23\u201334. https:\/\/doi.org\/10.1145\/582095.582099"}],"event":{"name":"SIGMOD\/PODS '25: Workshop on Quantum Computing and Quantum-Inspired Technology for Data-Intensive Systems and Applications","location":"Berlin Germany","acronym":"Q-Data '25"},"container-title":["Proceedings of the 2nd Workshop on Quantum Computing and Quantum-Inspired Technology for Data-Intensive Systems and Applications"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3736393.3736695","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T12:39:57Z","timestamp":1750682397000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3736393.3736695"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,22]]},"references-count":25,"alternative-id":["10.1145\/3736393.3736695","10.1145\/3736393"],"URL":"https:\/\/doi.org\/10.1145\/3736393.3736695","relation":{},"subject":[],"published":{"date-parts":[[2025,6,22]]},"assertion":[{"value":"2025-06-23","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}