Database systems encompass several performance-critical optimization tasks, such as join ordering and index tuning. As data volumes grow and workloads become more complex, these problems have become exponentially harder to solve efficiently. Quantum computing, especially quantum annealing, is a promising paradigm that can efficiently explore very large search spaces through quantum tunneling. It can escape local optima by tunneling through energy barriers rather than climbing over them. Earlier works mainly focused on providing an abstract representation (e.g., Quadratic Unconstrained Binary Optimization (QUBO)) for the database optimization problems (e.g., join order) and overlooked the real integration within database systems due to the high overhead of quantum computing services (e.g., a minimum 5s runtime for D-Wave's CQM-Solver). Recently, quantum annealing providers have offered more low-latency solutions, e.g., NL-Solver, which paves the road to actually realizing quantum solutions within DBMSs. However, this raises new systems research challenges in balancing efficiency and solution quality. In this talk, we show that this balance is possible to achieve. As a proof of concept, we present Q2O, the first real Quantum-augmented Query Optimizer. We show the end-to-end workflow: we encode the join order problem as a nonlinear model, a format solvable by the NL-Solver, using actual database statistics; the solution is translated into a plan hint that guides PostgreSQL's optimizer to produce a complete plan. Q2O is capable of handling actual queries in real time.
Database systems encompass several performance-critical optimization tasks, such as join ordering and index tuning. As data volumes grow and workloads become more complex, these problems have become exponentially harder to solve efficiently. Quantum computing, especially quantum annealing, is a promising paradigm that can efficiently explore very large search spaces through quantum tunneling. It can escape local optima by tunneling through energy barriers rather than climbing over them. Earlier works mainly focused on providing an abstract representation (e.g., Quadratic Unconstrained Binary Optimization (QUBO)) for the database optimization problems (e.g., join order) and overlooked the real integration within database systems due to the high overhead of quantum computing services (e.g., a minimum 5s runtime for D-Wave's CQM-Solver). Recently, quantum annealing providers have offered more low-latency solutions, e.g., NL-Solver, which paves the road to actually realizing quantum solutions within DBMSs. However, this raises new systems research challenges in balancing efficiency and solution quality. In this talk, we show that this balance is possible to achieve. As a proof of concept, we present Q2O, the first real Quantum-augmented Query Optimizer. We show the end-to-end workflow: we encode the join order problem as a nonlinear model, a format solvable by the NL-Solver, using actual database statistics; the solution is translated into a plan hint that guides PostgreSQL's optimizer to produce a complete plan. Q2O is capable of handling actual queries in real time.
Quantum annealers offer a promising sampling-based computing paradigm for large-scale combinatorial optimization. However, directly using them to solve database optimization problems in real-time scenarios remains challenging due to strict hardware constraints and the opacity of commercial hybrid solvers. To address these challenges, we present QDBO , a white-box quantum-augmented database optimizer that directly leverages low-level quantum sampling on a quantum annealer. It first performs an initial reduction to produce embeddable QUBO instances via multiple mapping strategies that trade off efficiency and quality. It then applies an online iterative relaxation correction procedure that uses sampling feedback to correct the reduced QUBO across iterations, enabling controllable quality improvements under varying time budgets. We integrate QDBO with the PostgreSQL query optimizer to construct Q 2 O-QDBO for join order optimization. Evaluations on the Join Order Benchmark (JOB) and the Cardinality Estimation Benchmark (CEB) show that Q 2 O-QDBO improves 62 out of 113 JOB queries, and achieves up to 49.36× execution-time speedup and 36.88× end-to-end speedup on the CEB workload. Evaluations on synthetic queries with up to 50 relations show that Q 2 O-QDBO achieves significantly less end-to-end latency while maintaining similar solution quality compared with black-box quantum solvers. To demonstrate generality, we further integrate QDBO with PostgreSQL for index selection on TPC-H, where QDBO achieves up to 2.64× workload speedup over the empty-index baseline and outperforms classical and black-box solver baselines. These results demonstrate that using QDBO to solve large-scale database optimization problems in real-time settings is promising.
Quantum computing has shown promise for solving complex optimization problems in databases, such as join ordering and index selection. Prior work often submits formulated problems directly to black-box quantum or quantum-inspired solvers with the expectation of directly obtaining a good final solution. Due to the black-box nature of these solvers, users cannot perform fine-grained control over the solving procedure to balance the accuracy and efficiency, which in turn limits flexibility in real-time settings where most database problems arise. Moreover, it leads to limited potential for handling large-scale database optimization problems. In this paper, we propose a vision for the first real-time quantum-augmented database system, enabling transparent solutions for database optimization problems. We develop two complementary scalability strategies to address large-scale challenges, overcomplexity, and oversizing that exceed hardware limits. We integrate our approach with a database query optimizer as a preliminary prototype, evaluating on real-world workload, achieving up to 14x improvement over the classical query optimizer. We also achieve both better efficiency and solution quality than a black-box quantum solver.
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.
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.
The rapidly increasing number of heterogeneous data ecosystems, such as structured databases, semi-structured data lakes, real-time streams, distributed knowledge graphs, has further complicated the issue of query planning and optimization in modern information systems extensively. The optimization of queries is essentially an NP-hard combinatorial problem especially when based on multi-join queries, distributed execution plan, dynamic cost model, and uncertainty in the data access patterns. Even decades of concept and engineering advances, classical database optimizers are rapidly becoming unable to offer a globally optimal execution plan when faced with high-dimensional data, high data volatility, with a very tight latency constraint. Good news Recent breakthroughs in quantum computing propose promising computational paradigms that can be used to solve combinatorial optimization problems via quantum parallelism, superposition, and entanglement. Nevertheless, even the near-term quantum hardware is limited in the number of available qubits, noise, and decoherence, making it impractical to achieve fully quantum database systems in any perceived future. This is also the reason why quantum-classical hybrid algorithms are being developed: designed to add quantum optimization subroutines to classical database architectures is guaranteed without breaking their compatibility with existing execution engines. The following paper presents a framework of scalable quantum-classical hybrid computing of complex query planning in heterogeneous data ecosystems. The framework breaks down query optimization into classical and quantum-amenable optimization, which allows NP-hard subproblems, such as join ordering, operator placement, and cost minimization, to be transformed into quantum optimization models such as Quadratic Unconstrained Binary Optimization (QUBO) and Ising Hamiltonians. Classical elements handle query parsing, semantic analysis, constraint verification, and orchestration, whereas quantum processors are called selectively to solve combinatorial decision-making tasks. The suggested architecture will consist of a layered execution, hybrid execution, cost-model encoding approach, and adaptive fallback mechanisms to make them robust to quantum hardware variability. This has been experimentally tested with simulated quantum annealing and variational quantum algorithms that exhibit a quantifiable improvement in the quality and scalability of optimization and heuristics based on entirely classical algorithms, especially in high-dimensional query plans. The findings confirm the practicability of quantum query optimization and put down a feasible route to implement quantum algorithms in the serving machine of the next-generation data management systems.
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.