BoundEst: Estimating Join Cardinalities with Tight Upper Bounds

Cardinality estimation is a critical component of query optimization. Despite extensive research, achieving efficient and accurate estimation for join queries remains challenging. Estimating tight upper bounds for join cardinalities can help the query optimizer generate better and more robust query plans. However, existing methods fail to account for the high skewness of real data and produce loose upper bounds. In this paper, we propose a new framework BoundEst, which designs an upper bound formula that accounts for the presence of outliers in the data distribution and introduces the DBSCAN clustering algorithm to identify these outliers. Moreover, we incorporate the learning-based model to learn the correlation between attributes. Given queries, BoundEst efficiently estimates tight upper bounds for join cardinalities by applying separate calculation methods to outliers and other values. We evaluate our approach on real-world datasets, and the results show that BoundEst generates effective estimates for query optimizer.