QCardEst/QCardCorr: Quantum Cardinality Estimation and Correction
This addresses query optimization bottlenecks in DBMS for database administrators and developers, representing an incremental hybrid quantum-classical method.
The authors tackled cardinality estimation for query optimization in database management systems by developing a quantum machine learning approach called QCardEst, which encodes SQL queries into quantum states and processes them with variational quantum circuits, achieving improvements over PostgreSQL optimizer of 6.37× for JOB-light and 8.66× for STATS datasets.
Cardinality estimation is an important part of query optimization in DBMS. We develop a Quantum Cardinality Estimation (QCardEst) approach using Quantum Machine Learning with a Hybrid Quantum-Classical Network. We define a compact encoding for turning SQL queries into a quantum state, which requires only qubits equal to the number of tables in the query. This allows the processing of a complete query with a single variational quantum circuit (VQC) on current hardware. In addition, we compare multiple classical post-processing layers to turn the probability vector output of VQC into a cardinality value. We introduce Quantum Cardinality Correction QCardCorr, which improves classical cardinality estimators by multiplying the output with a factor generated by a VQC to improve the cardinality estimation. With QCardCorr, we have an improvement over the standard PostgreSQL optimizer of 6.37 times for JOB-light and 8.66 times for STATS. For JOB-light we even outperform MSCN by a factor of 3.47.