Hype or Heuristic? Quantum Reinforcement Learning for Join Order Optimisation

Abstract

Identifying optimal join orders (JOs) stands out as a key challenge in database research and engineering. Owing to the large search space, established classical methods rely on approximations and heuristics. Recent efforts have successfully explored reinforcement learning (RL) for JO. Likewise, quantum versions of RL have received considerable scientific attention. Yet, it is an open question if they can achieve sustainable, overall practical advantages with improved quantum processors. In this paper, we present a novel approach that uses quantum reinforcement learning (QRL) for JO based on a hybrid variational quantum ansatz. It is able to handle general bushy join trees instead of resorting to simpler left-deep variants as compared to approaches based on quantum(-inspired) optimisation, yet requires multiple orders of magnitudes fewer qubits, which is a scarce resource even for post-NISQ systems. Despite moderate circuit depth, the ansatz exceeds current NISQ capabilities, which requires an evaluation by numerical simulations. While QRL may not significantly outperform classical approaches in solving the JO problem with respect to result quality (albeit we see parity), we find a drastic reduction in required trainable parameters. This benefits practically relevant aspects ranging from shorter training times compared to classical RL, less involved classical optimisation passes, or better use of available training data, and fits data-stream and low-latency processing scenarios. Our comprehensive evaluation and careful discussion delivers a balanced perspective on possible practical quantum advantage, provides insights for future systemic approaches, and allows for quantitatively assessing trade-offs of quantum approaches for one of the most crucial problems of database management systems.

References in corpus (25)

• Quantum Computing in the NISQ era and beyond
• Variational Quantum Algorithms
• Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
• Supervised learning with quantum enhanced feature spaces
• The theory of variational hybrid quantum-classical algorithms
• Quantum Circuit Learning
• Evaluating analytic gradients on quantum hardware
• The effect of data encoding on the expressive power of variational quantum machine learning models
• Power of data in quantum machine learning
• Data re-uploading for a universal quantum classifier
• Quantum advantage in learning from experiments
• A rigorous and robust quantum speed-up in supervised machine learning
• Quantum Natural Gradient
• Neo: A Learned Query Optimizer
• The Expressive Power of Parameterized Quantum Circuits
• Deep Reinforcement Learning for Join Order Enumeration
• Bao: Learning to Steer Query Optimizers
• Is quantum advantage the right goal for quantum machine learning?
• Quantum agents in the Gym: a variational quantum algorithm for deep Q-learning
• Optimizing quantum optimization algorithms via faster quantum gradient computation
• Balsa: Learning a Query Optimizer Without Expert Demonstrations
• On the Quantum versus Classical Learnability of Discrete Distributions
• Uncovering Instabilities in Variational-Quantum Deep Q-Networks
• Impact of quantum noise on the training of quantum Generative Adversarial Networks
• Guided-SPSA: Simultaneous Perturbation Stochastic Approximation assisted by the Parameter Shift Rule