Improved Join Order Optimization for Database Queries using Hybrid Quantum-Classical Approaches for QUBO Problems
For database query optimization, this hybrid method reduces quantum resource requirements and improves performance, but the results are incremental and limited by current hardware constraints.
This work introduces a hybrid quantum-classical approach combining Eliminating Cartesian Products (ECP) and splitting the QUBO search space (SQSS) to reduce QUBO problem size for join order optimization. Evaluated on real-world SQL queries, the method achieves consistent optimal join orders and improved query optimization across various selectivity conditions, while highlighting current quantum hardware limitations.
Efficient query optimization is crucial for relational database systems, especially for optimizing join orders in complex queries. This work introduces a hybrid approach that integrates Eliminating Cartesian Products (ECP) with splitting the QUBO search space (SQSS) to reduce the size of the QUBO problem, minimizing binary variables and constraints. This improves the performance of the quantum algorithm while lowering hardware requirements. We evaluate our method using real-world SQL queries from the ErgastF1 dataset on quantum and classical algorithms, including Quantum Annealing (QA), Simulated Annealing (SA), QAOA, and VQE, implemented on D-Wave's Quantum Annealer and universal gate-based simulators. Additionally, we analyze the impact of selectivity and SQSS on QUBO weight distribution and algorithmic performance, highlighting optimization efficiency for QA and SA. Experimental results show consistent optimal join orders and enhanced query optimization for various selectivity conditions, and they also highlight the limitations of current quantum hardware for complex queries. This study further confirms the potential of hybrid quantum-classical methods for scalable quantum-enhanced database optimization.