Mike Heddes: Efficient Cardinality Estimation of Multi-Join Queries using Count Sketches

Cardinality estimates are a primary input to query optimizers to determine an appropriate join order. The seminal AMS sketch can estimate the cardinality of an equi-join between two relations using little space. Since then, two important advancements are the Count sketch, a method which significantly improves upon the sketching time, and secondly, an extension of the AMS sketch to accommodate multi-join queries. However, combining the strengths of these methods to maintain sketches for multi-join queries while ensuring fast update times is a non-trivial task, and has remained an open problem for decades as highlighted in the existing literature. This talk will address this problem by introducing a novel sketching method which has fast updates, even for sketches capable of accurately estimating the cardinality of complex multi-join queries. Experimental results confirm the significant improvement in update time complexity, resulting in orders of magnitude faster estimates, with equal or better estimation accuracy.