Researchers at IISc report cutting-edge work that brings the benefits of quantum computing to relational database engines, the workhorses of big data processing in enterprise software applications. This work was presented in August at the 50th Very Large Data Bases (VLDB) conference, a premier international database research forum, held in Guangzhou, China. It was carried out by Jayant R Haritsa, Professor at the Department of Computational and Data Sciences (CDS) and Department of Computer Science and Automation (CSA), and Manish Kesarwani, a PhD student at IISc also working as a scientist with IBM Research. Notably, this was the only research paper from India accepted at VLDB this year.
Their study presents a radical quantum gate-based circuit design for solving the computationally hard problem of database index selection. The new solution promises substantive improvement, approaching optimality, in data retrieval efficiency, as compared to contemporary heuristic approaches, which may result in poor outcomes. A highlight of the investigation is its validation on real quantum hardware, through access to IBM’s quantum hardware, over the cloud.
Index Selection Problem
Relational database systems store data in tabular format with columns representing entity attributes and rows the values of these attributes. Tree-structured indexes, called B-trees, are created by database systems to efficiently access data on the underlying columns – for instance, a census database may create an index on the home state attribute to quickly filter out citizens from a particular state. This is similar to how indexes are used in reference books to quickly find relevant information.
Given a query workload, we need to select the appropriate column indexes for materially reducing the workload’s execution time. In the early days of computing, these indexes were manually selected by database administrators (DBAs). However, contemporary engines feature automated Index Advisors (IA) that identify good configurations while adhering to storage budgets.
IA design has been an active area of research over the past three decades in both academia and industry. However, searching for an optimal index configuration that maximises the time benefit inherently entails exploring a combinatorically large search space. Therefore, IA tools settle for index choices based on greedy heuristics, but this may result in arbitrarily poor outcomes.
Index Selection via Quantum Computing
Quantum computing leverages fundamental principles of quantum mechanics – such as superposition, interference, and entanglement – to dramatically enhance information processing. In classical computing, bits exist as either 0 or 1, but quantum computers use quantum bits or qubits, which can exist in multiple states simultaneously (superposition). This allows quantum computers to exponentially increase their compute space as the number of qubits increase, greatly increasing their computational power. Additionally, interference helps refine results by amplifying correct outcomes, while entanglement enables qubits to share information instantly, speeding up complex calculations.
The IISc study presents two new IA approaches – Optimisation-based Quantum Index Advisor (OQIA) and Search-based Quantum Index Advisor (SQIA) – that judiciously incorporate quantum computing within a classical index selection wrapper.
In OQIA, the index selection problem is modeled as a Quadratic Unconstrained Binary Optimisation problem and solved using the Quantum Approximate Optimisation Algorithm. The obtained solution is approximate but significantly better in quality than the earlier heuristic approaches. On the other hand, in SQIA, the index selection is modeled as a fully enumerative search and solved using the seminal Grover Search algorithm. This approach identifies, with high probability, the optimal index configuration.
A remarkable feature of the IISc solution is that they propose, for the first time, storage of index-related data in the relative phase of qubits, instead of the standard residency in basis states, and performing subsequent computations in phase space. If we imagine a qubit to be a spinning coin that is showing both heads and tails, then the phase is the angle or orientation at which the coin is spinning. This phase-based implementation requires only a linear number of circuit gates in contrast to the exponential number required by the standard approach, thereby ensuring scalability with problem size.
Looking ahead, the IISc research team plans to infuse quantum computing within other functional modules, the ultimate goal being a fully quantum-powered database engine.
