Reception with light refreshments in the lobby at 3:30 PM, followed by lecture

“Cardinality Estimation: Achilles’ Heel of Query Optimizers”

Cardinality estimation is the problem of estimating the size of the output of a query, without actually evaluating the query.  It has many applications, ranging from query optimization, to resource allocation, index recommendation, distributed query processing, and memory reservation. The estimator has access to some limited statistics on the database, such as table cardinalities, number of distinct values in various columns, sometimes histograms, and needs to estimate the output size of complex queries, often involving many joins and filter predicates.  Cardinality estimation is a critical piece of query optimization, where it is often the main culprit when the optimizer chooses a poor plan.  In this talk I will briefly survey existing cardinality estimation methods, discussing their pros and cons, then I will introduce a new approach to the problem, which is based on computing an upper bound instead of an estimate.  The upper bound is given by a mathematical formula, which uses the available database statistics in surprising ways.  At a deeper level, the new estimate is based on information-theoretic inequalities, which have recently found several surprising applications in query processing.