Estudo experimental da estimativa de cardinalidade para autojunções

Abstract

Query optimization is a critical task employed by Database Management Systems (DBMSs) to search for efficient execution plans. Commercial DBMSs employ cost models that rely on estimating the selectivity of predicates and the cardinality of operators, using catalog statistics and data structures such as sketches. However, the assumptions underlying these estimations— such as the inclusion principle in joins or the independence of attributes — often introduce inaccuracies. These inaccuracies leads to the selection of suboptimal plans, severely impacting performance, especially in more complex queries. Recent literature has predominantly focused on estimation for SPJ (Select-Project-Join) and grouping queries, while the effectiveness of estimations for self-join queries remains under-explored. This type of query is widely used in data cleaning tasks, such as denial constraints, but often exhibits unpredictable performance and high memory consumption — frequently due to the adoption of inefficient join algorithms. In this context, the proposal of this work is to experimentally investigate cardinality estimation techniques for self-join queries. To this end, the main contributions the work seeks are: (i) a review of the main cardinality estimation techniques for self-joins; (ii) the implementation of a synthetic data generator, designed for benchmarking estimation techniques applied to self-joins; and (iii) conducting a comprehensive comparative experiment, evaluating the performance of different cardinality estimation strategies for self-join queries. This research is expected to provide results regarding the limitations and effectiveness of current approaches for self-join query cardinality estimation.