Technical Perspective: Join Size Bounds using ℓ p -Norms on Degree Sequences
Hung Q. Ngo · ACM SIGMOD Record · 2025
Cardinality estimation is one of the most, if not the most, important components of the query optimization pipeline: these estimates are the main parameters in the cost-estimators of query plans, parallel query processing, and in computing budgets for in-memory query processing. After more than half a century of theory and implementation of relational database systems, whose global market size is on the order of 100 billions USD, commercial database systems still routinely misestimate cardinalities by a factor of 1000 or more. Two major reasons for the misestimation are: (1) relational RDBMSs employ estimators that make distributional assumptions about the data (such as uniformity) which may not hold in real workloads or in standard benchmarks, and (2) traditional estimators treat selection predicates independently, leading to error accumulation on large queries. Hence, estimation errors grow exponentially as the number of joins increases.