Seminars
View all Seminars | Download ICal for this eventQuantum-powered Index Advisors for Relational Databases
Series: Ph.D. Colloquium
Speaker: Manish Kesarwani, Ph.D (Engg) ERP student, Dept. of CSA, IISc.,
Date/Time: Aug 14 10:00:00
Location: CSA Auditorium, (Room No. 104, Ground Floor)
Faculty Advisor: Prof. Jayant R. Haritsa
Abstract:
Given an SQL query workload and a storage budget, an Index Advisor (IA) recommends column indexes that reduce workload execution cost. This is a fundamental but computationally hard problem in physical database design because the number of possible index configurations grows exponentially with the number of candidate indexes. A conventional IA therefore decomposes the task into the following pipeline stages: (i) identifying candidate indexes, (ii) estimating their storage requirements, (iii) sampling feasible index configurations, (iv) obtaining optimizer-estimated costs for these configurations, (v) deriving per-index benefits from those costs, and (vi) selecting a final configuration. To make these stages tractable, a suite of heuristics is applied. For instance, the last stage, configuration selection, is typically reduced to a 0-1 knapsack problem and solved greedily, assuming that index benefits are additive and thereby overlooking interactions among indexes. Although these simplifications make the problem tractable, they can discard high-quality ??hidden gems? and produce substantially suboptimal recommendations.
This thesis investigates whether the raw computational power promised by quantum platforms can be harnessed to uncover better index configurations. Our findings offer an encouraging answer: through careful algorithmic design, hybrid quantum-classical systems can improve recommendation quality while remaining compatible with contemporary database engines.
We first present QIA, a Quantum Index Advisor that retains the first five stages of the classical pipeline but moves final configuration selection to a quantum platform. QIA offers two complementary formulations. OQIA models selection as a Quadratic Unconstrained Binary Optimization problem and solves it using the Quantum Approximate Optimization Algorithm. SQIA instead uses Grover search to explore the restricted configuration space produced by the classical pipeline and identify a high-quality configuration with high probability. Its key technical contribution is a quantum oracle that computes over data encoded in the relative phases of a superposition state. Experimental evaluations show that QIA identifies substantially better index configurations than conventional commercial index advisors.
Despite these gains, QIA operates only after the preceding classical stages have already restricted and approximated the search space. This raises a broader question: could extending quantum computation to the upstream stages reveal even better index configurations?
To address this question, we present AQuIA, an Agent-supported Quantum Index Advisor that moves configuration enumeration and costing, in addition to configuration selection, into the quantum framework. At its core, AQuIA orchestrates a three-way collaboration among LLM-based agents, the database engine, and quantum hardware. The agents work with the database engine to identify a quantum-hardware-bounded set of relevant atomic configurations, which provide a compact basis for workload costing. The optimizer supplies their costs, while AQuIAs quantum oracle dynamically selects the applicable atomic configuration for each query across all index configurations represented in superposition and derives the aggregate workload cost, thereby preserving index interactions. It thereby avoids configuration sampling, the conversion of configuration costs into per-index benefits, and the subsequent 0-1 knapsack formulation. We evaluate both QIA and AQuIA on the 156-qubit IBM Heron quantum processor across a suite of TPC-H, TPC-DS, and JOB workloads on two leading commercial database engines, IBM DB2 and Microsoft SQL Server. Across these experiments, AQuIA identifies better index configurations than QIA and the classical baselines, while often recommending simpler indexes.
Finally, we prototype the QIA framework in QUARK, an interactive tool that connects to a live database, constructs and executes the two QIA formulations on simulators or real hardware, and compares their recommendations with classical baselines. To make the computation interpretable, QUARK decomposes each circuit into DBMS-relevant stages and explains measured intermediate states using familiar concepts such as configuration encoding, cost aggregation, and constraint enforcement. Together, QIA, AQuIA, and QUARK demonstrate the promise of quantum platforms for improving index recommendations, from novel quantum formulations to their practical integration with contemporary database systems.