QDBO: A real-time quantum-augmented database system optimizer

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 offline reduction to produce embeddable QUBO instances via multiple mapping strategies that trade off mapping efficiency and quality. It then applies an online iterative relaxation correction procedure that uses sample 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 {\oursystem} for join order optimization. Evaluations on the Join Order Benchmark (JOB) and the Cardinality Estimation Benchmark (CEB) show that {\oursystem} improves \(59\) out of \(113\) JOB queries, and achieves up to \(44.79\times\) execution-time speedup and \(7.13\times\) end-to-end speedup on CEB workload. Evaluations on synthetic queries with up to \(50\) relations show that {\oursystem} achieves less than half the end-to-end latency while maintaining similar solution quality compared with black-box quantum solvers. These results demonstrate that using {\qdbo} to solve large-scale database optimization problems in real-time settings is promising.