arXiv:2502.00362 · Frontiers in Computer Science

Left-deep join order selection with higher-order unconstrained binary optimization on quantum computers

Valter Uotila

Published Oct 7, 2025• 4 citations

Abstract

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.

DOI: 10.3389/fcomp.2025.1649354

Related papers

Quantum Join Ordering by Splitting the Search Space of QUBO Problems

Nitin Nayak, Tobias Winker, Umut Çalıkyılmaz +2 more

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.

Datenbank-SpektrumMar 1, 202410 citations

Constrained Quadratic Model for Optimizing Join Orders

Pranshi Saxena, Ibrahim Sabek, Federico M. Spedalieri

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.

Workshop on Quantum Computing and Quantum-Inspired Technology for Data-Intensive Systems and Applications (Q-Data)Jun 9, 202414 citations

Constructing Optimal Bushy Join Trees by Solving QUBO Problems on Quantum Hardware and Simulators

Nitin Nayak, Jan Rehfeld, Tobias Winker +3 more

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.

International Workshop on Big Data in Emergent Distributed Environments (BiDEDE)Jun 12, 202326 citations

Improved Join Order Optimization for Database Queries using Hybrid Quantum-Classical Approaches for QUBO Problems

Nitin Nayak, Tobias Winker, Umut Çalıkyılmaz +2 more

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.

arXiv:2606.16247Jun 15, 20260 citations

Hybrid Quantum-Classical Optimization for Bushy Join Trees

Hanwen Liu, Abhishek Kumar, Federico M. Spedalieri +1 more

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.

Workshop on Quantum Computing and Quantum-Inspired Technology for Data-Intensive Systems and Applications (Q-Data)Jun 22, 20253 citations

Kvanttilaskennan menetelmät kyselyjen optimointiin relaatiotietokannoissa

Valter Uotila

Quantum computing is an emerging technology that has experienced rapid progress and growing interest in recent years. To realize the potential of quantum computing, it is essential to consider its applicability in various domains. This thesis focuses on a relatively new field, the intersection of quantum computing and query processing in relational databases. During the research conducted for this thesis, the field has undergone substantial growth. The key problem in this field is to identify computationally challenging database optimization or other data management-related problems that can be tackled with quantum computing methods. The methodological core of this thesis centers on three larger themes: quantum machine learning, quantum optimization, and quantum information theory. In each case, the thesis focuses on a specific query-optimization problem that can be addressed by a particular method. The first problem is the challenge of estimating various SQL metrics, such as execution times and cardinalities, for queries before executing them on a relational database. This problem is addressed using a novel quantum natural language processing model that converts SQL queries into parametrized quantum circuits, which serve as the basis for the quantum machine learning model. The second problem, join order selection, is the most-studied query optimization problem at the intersection of quantum computing and databases. While most previous formulations of these problems have been quadratic unconstrained binary optimization problems, this work develops a higher-order binary optimization formulation for join order optimization. The applicability of higher-order binary optimization is also demonstrated by a work that develops an optimization problem to discover practical matrix multiplication algorithms. Finally, the third query processing problem is among the most-studied theoretical database optimization problems. It seeks worst-case size bounds for conjunctive queries with arbitrary functional dependencies. Previous research has developed Shannon-entropy-based linear programming formulations to compute size bounds. Our work proposes replacing Shannon entropy with the quantum Rényi entropy, which yields a similar yet theoretically slightly different formulation. Most importantly, this creates connections between theoretical database research and quantum information theory. Quantum computing has been notoriously challenging to apply to real-world problems. The practical estimates from the quantum machine learning model for the query metrics indicate that the proposed model can learn to estimate query metrics as a classifier for short SQL queries. In particular, the novel encoding mechanism that transforms SQL queries into parameterized quantum circuits is a key contribution of this work. For join order optimization problems, this work develops the first higher-order binary optimization formulations, which achieve comparable accuracy to that of dynamic programming and greedy algorithms, which are foundational methods for the problem in classical computing. Finally, the last article derives the worst-case size bound in terms of Rényi entropy and discusses the differences to those achieved with Shannon entropy. Continued development of quantum computing hardware, software, and algorithms will benefit from research that studies their performance in specific interdisciplinary applications. This thesis introduces relational databases and query processing as a domain that encompasses computationally complex problems at both practical and theoretical levels. It demonstrates how various quantum computational methods can be modified and applied to these problems, showcasing their practical usability while acknowledging their limitations.

Työväentutkimus VuosikirjaFeb 20, 20260 citations