Robust Plan Selection using Cardinality Distribution Models

Efficient query optimization requires an accurate estimation of cardinalities. Various techniques to improve cardinality estimation all share a common limitation: by classic definition, cardinality estimates are single-point values that drive the generation and selection of candidate execution plans. Relying on a wrong estimate can significantly impact the efficiency of query execution and therefore overall database performance. Rarely has the uncertainty of estimators been assessed or incorporated into the plan selection. Rather than solely relying on a single value estimate, we seek to quantify the risk associated with using each estimate, aiming to avoid those suspected to be wrong, unreliable or generally not trustworthy. To this end, we reformulate the cardinality estimation problem, introduce a novel class of learned cardinality estimators fit for this refined formulation, and explore their application in a robust plan selection strategy by implementing a simple query optimizer.