The optimization of queries speeds up query processing in databases. One of the most time-consuming tasks in query processing is the join operation, where the order of the joins plays a crucial role in determining the number of tuples to be processed for intermediate results, and hence, the overall processing costs. In this paper, we use a variational quantum circuit (VQC) to create a hybrid classical-quantum machine learning algorithm to predict efficient join orders by learning from past join orders. We develop an encoding of the join order problem using a low number of qubits. We show that VQCs with filtering of cross joins outperform the classical dynamic programming optimizer of PostgreSQL with a 2.7% faster execution time.
The optimization of queries speeds up query processing in databases. One of the most time-consuming tasks in query processing is the join operation, where the order of the joins plays a crucial role in determining the number of tuples to be processed for intermediate results, and hence, the overall processing costs. In this paper, we use a variational quantum circuit (VQC) to create a hybrid classical-quantum machine learning algorithm to predict efficient join orders by learning from past join orders. We develop an encoding of the join order problem using a low number of qubits. We show that VQCs with filtering of cross joins outperform the classical dynamic programming optimizer of PostgreSQL with a 2.7% faster execution time.
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.
Optimal join order sequence significantly impacts query execution performance.Because the search space grows exponentially with the number of relations involved in the queries, DP-based approaches can compute optimal plans only for queries with a small number of relations.Many heuristic methods trade off solution quality for computational efficiency.Quantum computing excels at solving combinatorial optimization problems such as join order optimization.However, existing quantum-related methods either focus solely on left-deep join trees-thus narrowing the problem scope-or support bushy join trees but are constrained by quantum hardware and cannot scale to large queries.Importantly, neither branch has been integrated into an actual database system.In this paper, we present a hybrid quantum-classical optimization approach for bushy join trees, integrated within a real database system (PostgreSQL).This approach expands the search space for join order sequences and overcomes previous limitations.Evaluation on the Join Order Benchmark shows that our method can reduce query execution time by up to 92.7% and achieve a 1.42x improvement in end-to-end latency.
Join order optimization is among the most crucial query optimization problems, and its central position is also evident in the new research field where quantum computing is applied to database optimization and data management. In this field, join order optimization is the most studied database problem, typically tackled with a quadratic unconstrained binary optimization model, which is solved using various meta-heuristics, such as quantum and digital annealing, the quantum approximate optimization algorithm, or the variational quantum eigensolver. In this study, we continue developing quantum computing techniques for left-deep join order optimization by presenting three novel quantum optimization algorithms. These algorithms are based on a higher-order unconstrained binary optimization model, which is a generalization of the quadratic model and has not previously been applied to database problems. Theoretically, these optimization problems naturally map to universal quantum computers and quantum annealers. Compared to previous studies, two of our algorithms are the first quantum algorithms to model the join order cost function precisely. We prove theoretical bounds by showing that these two methods encode the same plans as the dynamic programming algorithm with respect to the query graph, which provides the optimal result up to cross products. The third algorithm achieves plans at least as good as those of the greedy algorithm with respect to the query graph. These results establish a meaningful theoretical connection between classical and quantum algorithms for selecting left-deep join orders. To demonstrate the practical usability of our algorithms, we have conducted an extensive experimental evaluation on thousands of clique, cycle, star, tree, and chain query graphs using both quantum and classical solvers.
With the advancement of quantum computing in the Noisy Intermediate-Scale Quantum (NISQ) era, hybrid quantum-classical algorithms have emerged as promising approaches for addressing certain machine learning tasks. This study investigates the Variational Quantum Classifier (VQC), a hybrid model that integrates parameterized quantum circuits with classical optimization routines, implemented via IBM’s Qiskit framework. We provide a detailed account of the VQC architecture, including feature encoding, ansatz construction, and optimization methodology. To assess its performance, we conduct a comparative analysis between VQC and classical Support Vector Classifiers (SVC) across synthetic and real-world datasets, including Iris and a binary-filtered version of MNIST. Experimental results reveal that classical models consistently achieve higher accuracy and faster training times. However, the VQC demonstrates functional viability, particularly under noise-free conditions and reduced-dimensionality settings. These findings underscore the current limitations of quantum models while highlighting the potential of VQC as a proof-of-concept for quantum-enhanced learning as quantum hardware matures.
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.
The join order (JO) optimization problem is a key challenge in query optimization. Classical approaches can compute the optimal solution for smaller queries. For larger queries, some heuristic methods trade off plan quality to reduce the exponential search space. Recently, quantum-based methods have been proposed to leverage quantum mechanisms to accelerate exploration; however, encoding problem-specific constraints as penalty terms introduces extra overhead. Moreover, quantum-inspired methods on classical hardware do not harness the true advantages of quantum computation. Furthermore, these methods remain at the simulation stage. In this demonstration, we present the first Quantum-augmented Query Optimizer ( Q 2 O ) that integrates a hybrid quantum-classical approach to solve the JO problem in a real database setup. This demonstration allows conference attendees to interact directly with Q 2 O by executing queries and viewing detailed execution results (Scenario 1). Users can easily compare plan quality between Q 2 O and PostgreSQL (Scenario 2). Additionally, they can experiment with quantum parameters to observe their impact (Scenario 3). Experimental results show that the query plan generated by our approach achieves up to a 13x speedup in query execution. The video corresponding to this demonstration is available at this link.