Constructing Optimal Bushy Join Trees by Solving QUBO Problems on Quantum Hardware and Simulators
Open Access
- 18 June 2023
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1-7
Abstract
The join order is one of the most important factors that impact the speed of query processing. Its optimization is known to be NP-hard, such that it is worth investigating the benefits of utilizing quantum computers for optimizing join orders. Hence in this paper, we propose to model the join order problem as quadratic unconstrained binary optimization (QUBO) problem to be solved with various quantum approaches like QAOA, VQE, simulated annealing and quantum annealing. In this paper, we will show the enhanced performance using our QUBO formulation to find valid and optimal shots for real-world queries joining three, four and five relations on D-Wave quantum annealer. The highlight of this study will demonstrate that we were able to generate valid and optimal join orders for five relations using the D-Wave quantum annealer, with values of about 12% and 0.27% respectively and we were able to find the optimal bushy join trees. Experiments for the gate-based simulations were able to produce optimized join order for three and four relations including bushy trees using QAOA and VQE algorithms.Keywords
Funding Information
- German Federal Ministry of Education and Research (13N16090)
This publication has 25 references indexed in Scilit:
- An introduction to quantum machine learningContemporary Physics, 2014
- The Photoelectric Effect: Reconstructing the Story for the Physics ClassroomScience & Education, 2009
- Application of Ant Colony Optimization Algorithm to Multi-Join Query Optimization2008
- Quantum Computation and Quantum InformationAmerican Journal of Physics, 2002
- Quantum annealing in the transverse Ising modelPhysical Review E, 1998
- Heuristic and randomized optimization for the join ordering problemThe VLDB Journal, 1997
- Modern Quantum Mechanics, Revised EditionAmerican Journal of Physics, 1995
- A modern analysis of the Stern–Gerlach experimentAmerican Journal of Physics, 1992
- Optimization of large join queries1988
- Access path selection in a relational database management system1979