• search hit 11 of 645
Back to Result List

Quantum-Inspired Digital Annealing for Join Ordering

  • Finding the optimal join order (JO) is one of the most important problems in query optimisation, and has been extensively considered in research and practise. As it involves huge search spaces, approximation approaches and heuristics are commonly used, which explore a reduced solution space at the cost of solution quality. To explore even large JO search spaces, we may consider special-purpose software, such as mixed-integer linear programming (MILP) solvers, which have successfully solved JO problems. However, even mature solvers cannot overcome the limitations of conventional hardware prompted by the end of Moore’s law. We consider quantum-inspired digital annealing hardware, which takes inspiration from quantum processing units (QPUs). Unlike QPUs, which likely remain limited in size and reliability in the near and mid-term future, the digital annealer (DA) can solve large instances of mathematically encoded optimisation problems today. We derive a novel, native encoding for the JO problem tailored to this class of machines that substantially improves over known MILP and quantum-based encodings, and reduces encoding size over the state-of-the-art. By augmenting the computation with a novel readout method, we derive valid join orders for each solution obtained by the (probabilistically operating) DA. Most importantly and despite an extremely large solution space, our approach scales to practically relevant dimensions of around 50 relations and improves result quality over conventionally employed approaches, adding a novel alternative to solving the long-standing JO problem.

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics
Metadaten
Author:Manuel Schönberger, Immanuel Trummer, Wolfgang MauererORCiDGND
Parent Title (English):Proceedings of the VLDB Endowment
Document Type:Preprint
Language:English
Year of first Publication:2023
Release Date:2023/12/01
Pagenumber:14
Institutes:Fakultät Informatik und Mathematik
Fakultät Informatik und Mathematik / Labor für Digitalisierung (LFD)
research focus:Digitalisierung
Licence (German):Creative Commons - CC BY-NC-ND - Namensnennung - Nicht kommerziell - Keine Bearbeitungen 4.0 International