Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries
Yuan Ying Qiu, Yilei Wang, Ke Yi, Feifei Li, Bin Wu, Chaoqun Zhan · 2021
SPJ (select-project-join) queries form the backbone of many SQL queries used in practice. Accurate cardinality estimation of these queries is thus an important problem, with applications in query optimization, approximate query processing, and data analytics. However, this problem has not been rigorously addressed in the literature, despite the fact that cardinality estimation techniques of the three relational operators, selection, projection, and join, have each been extensively studied (but not when used in combination) in the past 30+ years. The major technical difficulty is that (distinct) projection seems to be difficult to combine with the other two operators when it comes to cardinality estimation.