The Case for Cardinality Lower Bounds
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910042099286016 |
|---|---|
| author | Stoian, Mihail Bang, Tiemo Zhao, Hangdong Camacho-Rodríguez, Jesús Tian, Yuanyuan Kipf, Andreas |
| author_facet | Stoian, Mihail Bang, Tiemo Zhao, Hangdong Camacho-Rodríguez, Jesús Tian, Yuanyuan Kipf, Andreas |
| contents | Despite decades of research, cardinality estimation remains the optimizer's Achilles heel, with industrial-strength systems exhibiting a systemic tendency toward underestimation. At cloud scale, this is a severe production vulnerability: in Microsoft's Fabric Data Warehouse (DW), a mere 0.05% of extreme underestimates account for 95% of all CPU under-allocation, causing preventable slowdowns for thousands of queries daily. Yet recent theoretical work on provable upper bounds only corrects overestimation, leaving the more harmful problem of underestimation unaddressed. We argue that closing this gap is an urgent priority for the database community.
As a vital step toward this goal, we introduce xBound, the first theoretical framework for computing provable join size lower bounds. By clipping the optimizer's estimates from below, xBound offers strict mathematical safety nets demanded by production systems - using only a handful of lightweight base table statistics. We demonstrate xBound's practical impact on Fabric DW: on the StackOverflow-CEB benchmark, it corrects 23.6% of Fabric DW's underestimates, yielding end-to-end query speedups of up to 20.1x, demonstrating that even a first step toward provable lower bounds can deliver meaningful production gains and motivating the community to further pursue this critical, open direction. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_13117 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Case for Cardinality Lower Bounds Stoian, Mihail Bang, Tiemo Zhao, Hangdong Camacho-Rodríguez, Jesús Tian, Yuanyuan Kipf, Andreas Databases Information Theory Despite decades of research, cardinality estimation remains the optimizer's Achilles heel, with industrial-strength systems exhibiting a systemic tendency toward underestimation. At cloud scale, this is a severe production vulnerability: in Microsoft's Fabric Data Warehouse (DW), a mere 0.05% of extreme underestimates account for 95% of all CPU under-allocation, causing preventable slowdowns for thousands of queries daily. Yet recent theoretical work on provable upper bounds only corrects overestimation, leaving the more harmful problem of underestimation unaddressed. We argue that closing this gap is an urgent priority for the database community. As a vital step toward this goal, we introduce xBound, the first theoretical framework for computing provable join size lower bounds. By clipping the optimizer's estimates from below, xBound offers strict mathematical safety nets demanded by production systems - using only a handful of lightweight base table statistics. We demonstrate xBound's practical impact on Fabric DW: on the StackOverflow-CEB benchmark, it corrects 23.6% of Fabric DW's underestimates, yielding end-to-end query speedups of up to 20.1x, demonstrating that even a first step toward provable lower bounds can deliver meaningful production gains and motivating the community to further pursue this critical, open direction. |
| title | The Case for Cardinality Lower Bounds |
| topic | Databases Information Theory |
| url | https://arxiv.org/abs/2601.13117 |