Index-Based Join Size Estimation Using Adaptive Sampling
Sergiu Pocol · 2021
Cost-based query optimizers rely on cardinality estimates of intermediate results to avoid suboptimal query execution plans. However, when confronted with ad-hoc queries on big data, said optimizers can produce large estimation errors, resulting in drastic decreases in overall performance. Such errors occur because many estimation algorithms for joins make use of strong independence and uniformity assumptions. Moreover, equi-joins on skewed data with filter predicates tend to cause the aforementioned assumptions to fail [2]. Since the cardinality estimate of a result with many joins depends on estimates of the underlying joins, it has been shown that improving the accuracy of join size estimates in a "bottom-up" order can significantly improve performance [2]. Thus, our research aims at improving the estimation of two-table join sizes.