This abstract summarizes the core ideas presented in [2]. The join order (JO) optimization problem is an NP-hard combinatorial challenge in query optimization. It aims to find the most efficient sequence for joining multiple relations. Dynamic programming (DP) provides optimal solutions for small queries but becomes impractical for larger ones due to its exponential complexity. Heuristic methods balance between quality and efficiency. The JO problem has recently been explored with Quantum Computing, which relies on the Quadratic Unconstrained Binary Optimization (QUBO) [4].
This abstract summarizes the core ideas presented in [2]. The join order (JO) optimization problem is an NP-hard combinatorial challenge in query optimization. It aims to find the most efficient sequence for joining multiple relations. Dynamic programming (DP) provides optimal solutions for small queries but becomes impractical for larger ones due to its exponential complexity. Heuristic methods balance between quality and efficiency. The JO problem has recently been explored with Quantum Computing, which relies on the Quadratic Unconstrained Binary Optimization (QUBO) [4].
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.
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.
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 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.
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.
Large Internet-of-Things (IoT) installations increasingly place relational databases at gateways, edge servers, application servers, and cloud nodes. Queries that correlate many tables create a difficult join-order problem: exact classical enumeration becomes impractical as the number of relations grows, while production optimizers must rely on bounded dynamic programming and heuristics. Recent work has encoded join ordering as Quadratic Unconstrained Binary Optimization (QUBO) and has evaluated digital annealers, quantum annealers, and hybrid quantum–classical optimizers. However, existing prototypes bind the database engine, encoding, solver interface, and deployment topology together. This work in progress proposes a platform-independent model that separates five concerns: IoT deployment, database and query structure, QUBO encoding, solver capabilities, and execution traceability. The proposal is grounded in our functional SQLite prototype, previously reported at JISBD 2026, which conditionally delegates join ordering to a private PC library compatible with Fujitsu Digital Annealer code. The intended model supports multiple database engines, QUBO formulations, algorithms, hardware classes, and locations across the IoT–edge–cloud continuum, while preserving validation and native-planner fallback. We define a preliminary conceptual metamodel, transformation chain, consistency rules, and evaluation plan; implementation and empirical validation remain future work.