The “DEDALUS” project aims to redefine Join Order Optimization (JOO) as a hybrid quantum-classical optimization problem and demonstrate that quantum-inspired methods can produce competitive or superior execution plans on real database workloads.

JOO (Join Order Optimization) is inherently a combinatorial problem. The number of possible bushy join trees grows exponentially with the number of relations, while cost-based optimizers rely on imperfect cardinality estimates. The result is a search space that is both large and error-prone.

The project addresses this by transforming multi-way join enumeration into a structured Quadratic Unconstrained Binary Optimization (QUBO) problem and solving it using classical/quantum solvers. It encodes candidate join subsets as binary decision variables and constructs a QUBO objective whose energy landscape reflects database-aware cost semantics.

Statistics Extraction

• Extracts catalog statistics from PostgreSQL
• Synthesizes a multi-factor cost model incorporating cardinality, predicate cost, skew, and estimation uncertainty

Search Space Pruning

A central design principle of DEDALUS is the search space pruning. Structurally invalid or disconnected subsets are eliminated before binary encoding.
This:

• Reduces the number of logical variables (qubits)
• Lowers coupling density
• Improves embedding feasibility on annealers
• Reduces circuit width for gate-based algorithms

Solver Execution

DEDALUS integrates multiple solver backends within a unified pipeline, including: 

• Classical simulated annealing (SA)
• Exact enumeration (for small instances)
• Gate-based algorithms such as QAOA
• Variational approaches such as VQE
• D-Wave’s quantum annealers suchs as, real QPUs and Hybrid Solving Systems 

The framework is solver-agnostic, enabling controlled comparison between classical, simulated and real quantum execution.

Cost Estimation

The system integrates a Cost Estimator, a machine learning-based decision support system that recommends whether to execute join order optimization queries using classical, simulated or quantum solver.

Provides real-time recommendations before query execution, helping users:

• Avoid expensive quantum hardware misuse
• Identify queries where quantum solvers provide genuine benefit
• Learn query patterns over time
• Make informed decisions about solver selection

An End-to-End Executable Pipeline