LpBound in Action: Cardinality Estimation with One-Sided Guarantees

Résumé fourni par la source

We demonstrate LpBound, a cardinality estimator that computes guaranteed upper bounds on the output size of a given query. Among the wealth of traditional, learned, and pessimistic estimators, LpBound's uniqueness lies in its use of two key ingredients: (1) data statistics based on ℓ$_{p}$-norms of degree sequences of the join columns, and (2) a linear program formulation of the cardinality estimation problem, whose constraints are the Shannon inequalities and new information inequalities derived from data statistics. LpBound comes with a visual interface accessible in the browser. The users can interact with the interface by choosing a query from the JOB, STATS, and Subgraph Matching benchmarks and the range of ℓ$_{p}$-norms available to LpBound. Within a few milliseconds, LpBound computes an upper bound on the query output size. This bound is explained by a closed-form formula using the available ℓ$_{p}$-norms. The users can also inspect the estimation errors of LpBound and a variety of other estimators.

Ce résumé expose les affirmations des auteurs. BNTIC ne l’interprète pas comme une validation indépendante des résultats.