Cost Model Improvements for Cardinality Estimation

This technical report discusses advancements in cardinality estimation, focusing on improving accuracy and consistency within Presto's optimizer. The document outlines the current limitations of cardinality estimation techniques and proposes specific changes to enhance the optimizer's performance. Key recommendations include eliminating 'unknown' cardinality estimates, augmenting the filter statistics calculator with an Adjustment Factor algorithm, and implementing a Max Entropy algorithm for addressing missing adjustment factors. The report also details the fundamental techniques for cardinality estimation and highlights the issues arising from the independence assumption in selectivity estimates. It presents a high-level design for achieving consistent cardinality estimates and discusses design considerations for implementing these improvements in Presto. The document emphasizes the importance of accurate cardinality estimation in optimizing query execution plans and provides a framework for addressing the challenges associated with selectivity estimation.