TY - JOUR A1 - Schönberger, Manuel A1 - Scherzinger, Stefanie A1 - Mauerer, Wolfgang T1 - Ready to Leap (by Co-Design)? Join Order Optimisation on Quantum Hardware JF - Proceedings of the ACM on Management of Data, PACMMOD N2 - The prospect of achieving computational speedups by exploiting quantum phenomena makes the use of quantum processing units (QPUs) attractive for many algorithmic database problems. Query optimisation, which concerns problems that typically need to explore large search spaces, seems like an ideal match for the known quantum algorithms. We present the first quantum implementation of join ordering, which is one of the most investigated and fundamental query optimisation problems, based on a reformulation to quadratic binary unconstrained optimisation problems. We empirically characterise our method on two state-of-the-art approaches (gate-based quantum computing and quantum annealing), and identify speed-ups compared to the best know classical join ordering approaches for input sizes that can be processed with current quantum annealers. However, we also confirm that limits of early-stage technology are quickly reached. Current QPUs are classified as noisy, intermediate scale quantum computers (NISQ), and are restricted by a variety of limitations that reduce their capabilities as compared to ideal future quantum computers, which prevents us from scaling up problem dimensions and reaching practical utility. To overcome these challenges, our formulation accounts for specific QPU properties and limitations, and allows us to trade between achievable solution quality and possible problem size. In contrast to all prior work on quantum computing for query optimisation and database-related challenges, we go beyond currently available QPUs, and explicitly target the scalability limitations: Using insights gained from numerical simulations and our experimental analysis, we identify key criteria for co-designing QPUs to improve their usefulness for join ordering, and show how even relatively minor physical architectural improvements can result in substantial enhancements. Finally, we outline a path towards practical utility of custom-designed QPUs. KW - Hardware KW - Quantum cmputation KW - Informations systems KW - Join algorithms Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:898-opus4-56634 N1 - Corresponding author: Manuel Schönberger VL - 1 IS - 1 SP - 1 EP - 27 PB - ACM CY - New York, NY, ER - TY - CHAP A1 - Schönberger, Manuel A1 - Trummer, Immanuel A1 - Mauerer, Wolfgang T1 - Quantum Optimisation of General Join Trees T2 - Joint Workshops at 49th International Conference on Very Large Data Bases (VLDBW’23) — International Workshop on Quantum Data Science and Management (QDSM’23), August 28 - September 1, 2023, Vancouver, Canada (CEUR Workshop Proceedings) N2 - Recent advances in the manufacture of quantum computers attract much attention over a wide range of fields, as early-stage quantum processing units (QPU) have become accessible. While contemporary quantum machines are very limited in size and capabilities, mature QPUs are speculated to eventually excel at optimisation problems. This makes them an attractive technology for database problems, many of which are based on complex optimisation problems with large solution spaces. Yet, the use of quantum approaches on database problems remains largely unexplored. In this paper, we address the long-standing join ordering problem, one of the most extensively researched database problems. Rather than running arbitrary code, QPUs require specific mathematical problem encodings. An encoding for the join ordering problem was recently proposed, allowing first small-scale queries to be optimised on quantum hardware. However, it is based on a faithful transformation of a mixed integer linear programming (MILP) formulation for JO, and inherits all limitations of the MILP method. Most strikingly, the existing encoding only considers a solution space with left-deep join trees, which tend to yield larger costs than general, bushy join trees. We propose a novel QUBO encoding for the join ordering problem. Rather than transforming existing formulations, we construct a native encoding tailored to quantum systems, which allows us to process general bushy join trees. This makes the full potential of QPUs available for solving join order optimisation problems. Y1 - 2023 UR - https://ceur-ws.org/Vol-3462/QDSM2.pdf SP - 1 EP - 12 PB - RWTH Aachen, Sun SITE Central Europe CY - Aachen ER - TY - JOUR A1 - Schönberger, Manuel T1 - Applicability of Quantum Computing on Database Query Optimization JF - SIGMOD '22: proceedings of the 2022 International Conference on Management of Data : June 12-17, 2022, Philadelphia, PA, USA N2 - We evaluate the applicability of quantum computing on two fundamental query optimization problems, join order optimization and multi query optimization (MQO). We analyze the problem dimensions that can be solved on current gate-based quantum systems and quantum annealers, the two currently commercially available architectures. First, we evaluate the use of gate-based systems on MQO, previously solved with quantum annealing. We show that, contrary to classical computing, a different architecture requires involved adaptations. We moreover propose a multi-step reformulation for join ordering problems to make them solvable on current quantum systems. Finally, we systematically evaluate our contributions for gate-based quantum systems and quantum annealers. Doing so, we identify the scope of current limitations, as well as the future potential of quantum computing technologies for database systems. Y1 - 2022 U6 - https://doi.org/10.1145/3514221.3520257 SP - 2512 EP - 2514 PB - ACM CY - New York, NY ER - TY - GEN A1 - Schönberger, Manuel A1 - Scherzinger, Stefanie A1 - Mauerer, Wolfgang T1 - Quantum Computing for DB - Applicability on Multi Query Optimization and Join Order Optimization T2 - Frühjahrstreffen Fachgruppe Datenbanken in Potsdam, 2022 Y1 - UR - https://www.lfdr.de/Publications/2022/FGDB_Poster_Schoenberger.pdf ER - TY - CHAP A1 - Schönberger, Manuel A1 - Franz, Maja A1 - Scherzinger, Stefanie A1 - Mauerer, Wolfgang T1 - Peel | Pile? Cross-Framework Portability of Quantum Software T2 - 2022 IEEE 19th International Conference on Software Architecture Companion (ICSA-C), 12-15 March 2022, Honolulu, HI, USA N2 - In recent years, various vendors have made quantum software frameworks available. Yet with vendor-specific frameworks, code portability seems at risk, especially in a field where hardware and software libraries have not yet reached a consolidated state, and even foundational aspects of the technologies are still in flux. Accordingly, the development of vendor-independent quantum programming languages and frameworks is often suggested. This follows the established architectural pattern of introducing additional levels of abstraction into software stacks, thereby piling on layers of abstraction. Yet software architecture also provides seemingly less abstract alternatives, namely to focus on hardware-specific formulations of problems that peel off unnecessary layers. In this article, we quantitatively and experimentally explore these strategic alternatives, and compare popular quantum frameworks from the software implementation perspective. We find that for several specific, yet generalisable problems, the mathematical formulation of the problem to be solved is not just sufficiently abstract and serves as precise description, but is likewise concrete enough to allow for deriving framework-specific implementations with little effort. Additionally, we argue, based on analysing dozens of existing quantum codes, that porting between frameworks is actually low-effort, since the quantum- and framework-specific portions are very manageable in terms of size, commonly in the order of mere hundreds of lines of code. Given the current state-of-the-art in quantum programming practice, this leads us to argue in favour of peeling off unnecessary abstraction levels. KW - Computer Science KW - Quantum Physics KW - Software Engineering Y1 - 2022 U6 - https://doi.org/10.1109/ICSA-C54293.2022.00039 N1 - Preprint unter: https://arxiv.org/abs/2203.06289 PB - IEEE ER - TY - INPR A1 - Schönberger, Manuel A1 - Trummer, Immanuel A1 - Mauerer, Wolfgang T1 - Quantum-Inspired Digital Annealing for Join Ordering T2 - Proceedings of the VLDB Endowment N2 - 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. Y1 - 2023 ER - TY - INPR A1 - Schmidl, Sebastian A1 - Deng, Yangshen A1 - Ma, Pingchuan A1 - Schönberger, Manuel A1 - Mauerer, Wolfgang T1 - Reproducibility Report for ACM SIGMOD 2023 Paper: Ready to Leap (by Co-Design)? Join Order Optimisation N2 - The paper “Ready to Leap (by Co-Design)? Join Order Optimisation on Quantum Hardware” proposes the first approach to solve the problem of join order optimization on quantum hardware. The authors characterize the applicability and limitations of current state-of-the-art quantum hardware, i. e. gate-based quantum computing and quantum annealing, for join ordering and recommend key improvements to the physical hardware to reach practical utility. Based on the provided database queries and QPU system processing data, we have been able to reproduce the original paper’s key insights and quantum problem characteristics reported in its experimental section. The authors provided a self-contained and fully automated reproduction package, including data (database queries, statistics, and collected QPU processing data), experiment scripts, and plotting routines that allowed the identical reconstruction of the three main figures in the paper. Y1 - 2024 UR - https://www.lfdr.de/Publications/2024/SIGMOD_ARI_2023___Paper_37.pdf ER - TY - GEN A1 - Schönberger, Manuel A1 - Scherzinger, Stefanie A1 - Mauerer, Wolfgang T1 - Applicability of Quantum Computing on Database Query Optimization T2 - Frühjahrstreffen Fachgruppe Datenbanken in Potsdam (Poster Presentation) Y1 - 2022 ER - TY - THES A1 - Schönberger, Manuel T1 - Eine zweigleisige Strategie hin zu ausgereiftem Quanten-Datenmanagement T1 - A Twofold Strategy Towards Mature Quantum Data Management N2 - By relying on stagnant general-purpose devices limited by the end of Moore's law, conventional data management (DM) methods are challenged by ever-increasing computational loads. As a promising alternative, we may rely on quantum processing units (QPU) as special-purpose accelerators, which may overcome the limitations of conventional systems by exploiting quantum phenomena. However, given their early-stage, prototypical nature, contemporary QPUs remain limited in size and reliability, which renders them unfit for practical scenarios. In this thesis, we therefore propose a twofold strategy to aid the shift towards mature quantum data management. As a first fundamental pillar, our strategy rests on QPU-DM co-design: Inspired by the conventional hardware-software co-design paradigm, our method yields recommendations for the tailored design of QPU architecture, to craft quantum systems conforming to the specific requirements of DM tasks. Based on an empirical assessment involving contemporary quantum systems, and simulating enhanced QPU architectures, our method identifies the most effective among a variety of architectural enhancements, and allows us to derive recommendations on the design of QPUs tailored to DM tasks. However, to decide whether QPU-DM co-design efforts are truly worth pursuing, we require insights into the true potential of quantum systems for DM up-front. As a second fundamental pillar, our strategy hence assesses the algorithmic aptness of our methods on quantum-inspired special-purpose hardware (HW): While classical in nature, such systems mimic the workings of pure QPUs, and thus provide a lower bound on the capabilities of future QPUs. Thereby, our strategy yields insights into the true potential of future QPUs, which are expected to achieve still higher performance upon obtaining a sufficient level of maturity. We demonstrate the aptness of our twofold strategy on fundamental DM and query optimisation tasks by (1) deriving QPU design recommendations for the join ordering (JO) problem by applying our QPU-DM co-design method, (2) demonstrating the scalability aptness of quantum-inspired HW for extremely large JO solution spaces that prove challenging for conventional approaches, (3) deriving methods to solve the most extensive class of JO problems on quantum(-inspired) systems, and (4) conducting a still more extensive assessment of quantum-inspired HW for multiple query optimisation. Thereby, we aid the shift from currently imperfect QPUs towards systems fit for mature quantum data management. N2 - Anforderungen zur Verarbeitung stetig ansteigender Datenmengen stellen eine wachsende Herausforderung im Bereich des Datenmanagement (DM) dar, dessen etablierte Methoden auf traditionellen Allzweck-Systemen beruhen, deren Entwicklung durch das Ende des Mooreschen Gesetzes stagniert. Eine vielversprechende Alternative bieten Quantum Processing Units (QPU), welche das Potential aufweisen, die Limitationen traditioneller Systeme durch das Ausnutzen von Phänomenen der Quantenmechanik zu überwinden. Aufgrund ihres frühen Entwicklungsstadiums und ihrer prototypischen Natur sind gegenwärtige QPUs jedoch trotz dieses Potentials in ihrer Kapazität und Zuverlässigkeit begrenzt, und folglich ungeeignet für praktische Anwendungen. In dieser Arbeit schlagen wir daher eine zweigleisige Strategie für die Entwicklung hin zu ausgereiftem Quanten-Datenmanagement vor. Als erste fundamentale Säule beruht unsere Strategie auf Techniken des QPU-DM Co-Design: Inspiriert durch das konventionelle Hardware-Software Co-Design Paradigma können wir anhand unserer Methode Empfehlungen für das maßgeschneiderte Design von QPU Architekturen ermitteln, um Quanten-Systeme zu entwerfen, welche an spezifische Anforderungen fundamentaler DM Aufgaben angepasst sind. Basierend auf empirischen Analysen gegenwärtiger Quanten-Systeme und der Simulation strukturell erweiterter QPU Architekturen identifiziert unsere Methode unter Betrachtung einer Vielzahl möglicher Alternativen die effektivsten Erweiterungen für das Design von maßgeschneiderten QPUs. Zur Entscheidung über die Anwendung ressourcen-intensiver QPU-DM Co-Design Methoden benötigen wir vorab jedoch Erkenntnisse über das tatsächliche Potential von Quanten-Systemen für DM. Als zweite fundamentale Säule sieht unsere Strategie daher eine algorithmische Analyse von Quanten-Methoden mittels quanten-inspirierten Systemen vor: Derartige Systeme imitieren die Funktionsweise tatsächlicher QPUs, und geben daher trotz ihrer klassischen Natur Aufschluss über die Mindest-Leistungsfähigkeit und das Potential tatsächlicher, ausgereifter QPUs, welche zur Ausnutzung von Quantenphänomenen befähigt sind. Wir demonstrieren die Tauglichkeit unserer zweigleisigen Strategie für fundamentale DM Probleme durch (1) das Ermitteln von Design-Empfehlungen für das Join Ordering (JO) Problem durch Anwendung unserer QPU-DM Co-Design Methode, (2) das Demonstrieren der Skalierbarkeit quanten-inspirierter Methoden für extrem große JO Lösungsräume, (3) das Konzipieren von Methoden zum Lösen der umfangreichsten Klasse von JO Problemen auf quanten(-inspirierten) Systemen, und (4) das Durchführen einer noch umfangreicheren Analyse quanten-inspirierter Methoden für Multiple Query Optimisation. Dadurch unterstützen wir die Transformation von aktuellen QPU-Prototypen hin zu Quanten-Systemen, die für ausgereiftes Quanten-Datenmanagement geeignet sind. Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:898-opus4-84774 ER - TY - CHAP A1 - Schönberger, Manuel A1 - Trummer, Immanuel A1 - Mauerer, Wolfgang T1 - Large-Scale Multiple Query Optimisation with Incremental Quantum(-Inspired) Annealing T2 - Proceedings of the ACM on Management of Data N2 - Multiple-query optimization (MQO) seeks to reduce redundant work across query batches. While MQO offers opportunities for dramatic performance improvements, the problem is NP-hard, limiting the sizes of problems that can be solved on generic hardware. We propose to leverage specialized hardware solvers for optimization, such as Fujitsu's Digital Annealer (DA), to scale up MQO to problem sizes formerly out of reach. We present a novel incremental processing approach that combines classical computation with DA acceleration. By efficiently partitioning MQO problems into sets of partial problems, and by applying a dynamic search steering strategy that reapplies initially discarded information to incrementally process individual problems, our method overcomes capacity limitations, and scales to extremely large MQO instances (up to νm1000 queries). A thorough and comprehensive empirical evaluation finds our method substantially outperforms existing approaches. Our generalisable framework lays the ground for other database use-cases on quantum-inspired hardware, and bridges towards future quantum accelerators. Y1 - 2025 U6 - https://doi.org/10.1145/3749171 VL - 3 IS - 4 PB - ACM ER -