ACM/IEEE International Conference on Model Driven Engineering Languages and Systems (MODELS)

Toward a Platform-Independent Model for QUBO-Based Join-Order Optimization in Multi-Tier IoT Systems

Eduardo Gutiérrez, Sebastián Villarroya

Published Oct 4, 2026• 0 citations

Abstract

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.

DOI: 10.1145/3837062.3839080

Related papers

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

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

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

Valter Uotila

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.

arXiv:2502.00362Frontiers in Computer ScienceOct 7, 20254 citations

Quantum-Classical Hybrid Algorithms for Complex Query Planning: A Scalable Computational Framework for High-Dimensional Decision Optimization in Heterogeneous Data Ecosystems

Parameswara Reddy Nangi, Chaithanya Kumar Reddy Nala Obannagari

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.

International Journal of AI BigData Computational and Management StudiesJan 1, 20260 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

QFusion: A Demonstration of Boundary-Aware Fusion Planning and Execution for Large-Scale QUBO Optimization

Hanwen Liu, Ibrahim Sabek

Large-scale database optimization problems can be encoded as Quadratic Unconstrained Binary Optimization (QUBO) instances for execution on quantum hardware. As the problem size grows, these QUBOs quickly exceed the capacity of current devices and must be decomposed into multiple subproblems. However, decomposition does not eliminate global dependencies: subproblems remain coupled through boundary interfaces, and overall solution quality depends critically on how partial solutions are fused. In this demonstration, we present QFusion , the first boundary-aware fusion planning and execution framework for large-scale QUBO solving that runs on an actual quantum annealer. We propose a DBMS-inspired, cost-based fusion tree that explicitly selects the fusion order and merge strategy. QFusion supports three database optimization tasks: join order optimization, multiple query optimization, and index selection. Conference attendees can interactively control the complete workflow through three designed scenarios: inspecting the construction of QUBOs with their database semantics, adjusting the decomposition granularity to observe the resulting boundary interfaces, and configuring fusion planning to examine the execution results on an actual quantum annealer. Overall, the demonstration highlights that scalable QUBO solving is not only a matter of solving local subproblems, but also a systems problem that requires boundary-aware fusion planning. The video corresponding to this demonstration is available at this link.

Proceedings of the VLDB EndowmentAug 1, 20261 citation