# Q-error Bounds of Random Uniform Sampling for Cardinality Estimation

arXiv: https://arxiv.org/abs/2108.02715 · HTML: https://mlsanity.com/paper/2108.02715/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Aug 2021.

## Built on by (most cited first, 1 of 1)

- [PerfReasoning: How Well Do LLMs Reason on Hardware Performance?](https://mlsanity.com/paper/2609.04476/) (2026)

## Abstract (arXiv)

Random uniform sampling has been studied in various statistical tasks but few of them have covered the Q-error metric for cardinality estimation (CE). In this paper, we analyze the confidence intervals of random uniform sampling with and without replacement for single-table CE. Results indicate that the upper Q-error bound depends on the sample size and true cardinality. Our bound gives a rule-of-thumb for how large a sample should be kept for single-table CE.