Quantum Join Ordering by Splitting the Search Space of QUBO Problems
Open Access
- 18 March 2024
- journal article
- schwerpunktbeitrag
- Published by Springer Nature in Datenbank-Spektrum
- Vol. 24 (1) , 21-32
Abstract
The join order has a huge impact on the execution time of a query, such that finding an optimal join order plays a crucial 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 reasonable number of QUBO problems solved by D‑Wave’s 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.Keywords
Funding Information
- Universität zu Lübeck
This publication has 32 references indexed in Scilit:
- Quantum Annealing vs. QAOA: 127 Qubit Higher-Order Ising Problems on NISQ Computers2023
- Quantum bridge analytics I: a tutorial on formulating and using QUBO modelsAnnals of Operations Research, 2022
- Query optimization through the looking glass, and what we found running the Join Order BenchmarkThe VLDB Journal, 2017
- A variational eigenvalue solver on a photonic quantum processorNature Communications, 2014
- The unconstrained binary quadratic programming problem: a surveyJournal of Combinatorial Optimization, 2014
- Application of Ant Colony Optimization Algorithm to Multi-Join Query Optimization2008
- Bounds for the adiabatic approximation with applications to quantum computationJournal of Mathematical Physics, 2007
- Heuristic and randomized optimization for the join ordering problemThe VLDB Journal, 1997
- Quantum annealing: A new method for minimizing multidimensional functionsChemical Physics Letters, 1994
- Beweis des AdiabatensatzesThe European Physical Journal A, 1928