Learned containment rates between query pairs, combined with a queries pool of known cardinalities, substantially improve cardinality estimates on multi-join queries.
Simple set cardinality estimation through random sampling
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We present a simple algorithm that estimates the cardinality $n$ of a set $V$ when allowed to sample elements of $V$ uniformly and independently at random. Our algorithm with probability $(1-\delta)$ returns a $(1\pm\epsilon)-$approximation of $n$ drawing $O\big(\sqrt{n} \cdot \epsilon^{-1}\sqrt{\log(\delta^{-1})}\big)$ samples (for $\epsilon^{-1}\sqrt{\log(\delta^{-1})} = O(\sqrt{n})$).
fields
cs.DB 1years
2019 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Improved Cardinality Estimation by Learning Queries Containment Rates
Learned containment rates between query pairs, combined with a queries pool of known cardinalities, substantially improve cardinality estimates on multi-join queries.