Divergent Index Tuning via Quantum Optimisation
- Bachelor-/Masterarbeit -
Beschreibung:
Given a database of tables with attributes (columns) and tuples (records), an index is a structure that allows for faster retrieval of data when searching over an attribute or set of attributes. Indexes require additional memory to store, and the challenge of choosing the best set of indexes to reduce query processing time within a given storage budget is called the Index Selection Problem. This problem is NP-hard, so an exhaustive search is not feasible over all possible index configurations. Existing approaches use heuristic algorithms or machine learning techniques to approximate a good solution.
Instead of using a single centralised database, data may stored in a cluster of
replicated databases, each of which may have their own set of indexes. This replication allows for queries to be processed in parallel, and allows each replica to specialise in processing different types of query by creating different indexes. The process of choosing indexes for the databases in the cluster is called Divergent Design Index Tuning.
Because the index selection problem is computationally difficult, it has been proposed to use quantum computing to accelerate index tuning [1]. One approach is to model index selection as a combinatorial optimisation problem and use the quantum adiabatic theorem to obtain a solution [2]. Another is to use the Quantum Approximate Optimisation Algorithm (QAOA) to find a solution [3]. Both of these techniques formulate index tuning as a Quadratic Unconstrained Binary Optimisation (QUBO) expression and apply a quantum algorithm to find a near-optimal solution.
Existing approaches are for a centralised database. A QUBO is to be developed for divergent design index tuning and quantum optimisation algorithms are to be applied to efficiently find solutions for index tuning on distributed databases.
[1] L. Gruenwald, T. Winker, U. Çalıkyılmaz, J. Groppe, and S. Groppe, “Index tuning with machine learning on quantum computers for large-scale database applications,” in Joint Workshops at 49th International Conference on Very Large Data Bases (VLDBW’23) — International Workshop on Quantum Data Science and Management (QDSM’23), 2023. [Online]. Available: https://ceur-ws.org/Vol-3462/QDSM5.pdf
[2] I. Trummer and D. Venturelli, “Leveraging quantum computing for database index selection,” in Proc. Q-Data ’24. New York, NY, USA: Association for Computing Machinery, 2024, p. 14–26. [Online]. Available: https://doi.org/10.1145/3665225.3665445
[3]: M. Kesarwani and J. R. Haritsa, “Index advisors on quantum platforms,” Proc. VLDB Endow., vol. 17, no. 11, p. 3615–3628, Jul. 2024. [Online]. Available: https://doi.org/10.14778/3681954.3682025
Anforderungen/Kenntnisse:
Quantm Computing
Betreuung:
Prof. Dr. rer. nat. habil. Sven Groppe
Institut für Informationssysteme
Ratzeburger Allee 160 ( Gebäude 64 - 2. OG)
23562 Lübeck
Telefon: 0451 / 3101 5706
mit Unterstüzung von Prof. Le Gruenwald und Sam Bird (University of Oklahoma)
