Constrained Quadratic Model for Optimizing Join Orders
Open Access
- 9 June 2024
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 38-44
Abstract
We present a quantum-based approach for the optimization of join orders in database applications. Our approach relies on a hybrid framework, where classical heuristics are combined with a quantum processor to accelerate the search over the set of solutions to a constrained problem. By taking advantage of a previously introduced formulation of the join order optimization as a Quadratic Unconstrained Binary Optimization (QUBO) problem, we implement it using the Constrained Quadratic Model (CQM), a hybrid classical-quantum solver that interfaces classical heuristics with D-Wave’s quantum annealer. We show that even a generic implementation of this classical-quantum hybrid framework produces competitive results for the join order problem, suggesting that better-tailored hybrid solvers could produce a computational advantage.Keywords
This publication has 28 references indexed in Scilit:
- Noisy intermediate-scale quantum algorithmsReviews of Modern Physics, 2022
- Query optimization through the looking glass, and what we found running the Join Order BenchmarkThe VLDB Journal, 2017
- Solving the Join Ordering Problem via Mixed Integer Linear Programming2017
- Quantum annealing with manufactured spinsNature, 2011
- Polynomial heuristics for query optimization2010
- Query simplification2009
- Dynamic programming strikes back2008
- A genetic algorithm for database query optimization2002
- Quantum annealing in the transverse Ising modelPhysical Review E, 1998
- Rapid bushy join-order optimization with Cartesian products1996