  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.
