Estudo Experimental da Estimativa de Cardinalidade para Autojunções
Resumo
A estimativa de cardinalidade é um dos principais fatores que contribuem para a geração de planos de consulta subótimos. A literatura recente tem se concentrado na estimativa para consultas do tipo seleção-projeção-junção, enquanto a estimativa de cardinalidade para consultas com autojunção permanece uma área ainda pouco explorada. Consultas com autojunção são amplamente utilizadas em tarefas de limpeza de dados, como a validação de restrições de negação. Nesse contexto, investigamos empiricamente as principais técnicas de estimativa de cardinalidade para consultas com autojunção sob diferentes distribuições de dados. Nossos resultados mostram que estruturas de dados probabilísticas compactas (sketches) produzem estimativas consistentemente melhores do que modelos de custo tradicionais baseados em suposições.
Palavras-chave:
otimização de consultas, plano de execução, estimativa de seletividade, junção, banco de dados em memória
Referências
Alon, N., Gibbons, P. B., Matias, Y., and Szegedy, M. (1999). Tracking join and self-join sizes in limited storage. In Proceedings of the Eighteenth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS ’99, page 10–20, New York, NY, USA. Association for Computing Machinery.
Cormode, G., Garofalakis, M., Haas, P. J., and Jermaine, C. (2012). Synopses for massive data: Samples, histograms, wavelets, sketches. Found. Trends Databases, 4(1–3):1–294.
Cormode, G. and Muthukrishnan, S. (2005). An improved data stream summary: the count-min sketch and its applications. Journal of Algorithms, 55(1):58–75.
Flajolet, P., Fusy, É., Gandouet, O., and Meunier, F. (2007). Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm. Discrete mathematics & theoretical computer science, (Proceedings).
Freitag, M. and Neumann, T. (2019). Every row counts: Combining sketches and sampling for accurate group-by result estimates. ratio, 1:1–39.
Ioannidis, Y. (2003). The history of histograms (abridged). In Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29, VLDB ’03, page 19–30. VLDB Endowment.
Lee, K., Dutt, A., Narasayya, V., and Chaudhuri, S. (2023). Analyzing the impact of cardinality estimation on execution plans in microsoft sql server. Proc. VLDB Endow., 16(11):2871–2883.
Leis, V., Gubichev, A., Mirchev, A., Boncz, P., Kemper, A., and Neumann, T. (2015). How good are query optimizers, really? Proc. VLDB Endow., 9(3):204–215.
Leis, V., Radke, B., Gubichev, A., Mirchev, A., Boncz, P., Kemper, A., and Neumann, T. (2018). Query optimization through the looking glass, and what we found running the join order benchmark. The VLDB Journal, 27(5):643–668.
Liu, Z., Deep, S., Fariha, A., Psallidas, F., Tiwari, A., and Floratou, A. (2024). Rapidash: Efficient detection of constraint violations. Proc. VLDB Endow., 17(8):2009–2021.
Moerkotte, G. (2024). Cardinality estimation for having-clauses. Proc. VLDB Endow., 18(1):28–41.
Moerkotte, G. (2025). Building query compilers. University of Mannheim. [link].
Moerkotte, G., Neumann, T., and Steidl, G. (2009). Preventing bad plans by bounding the impact of cardinality estimation errors. Proc. VLDB Endow., 2(1):982–993.
Pena, E. H. M., de Almeida, E. C., and Naumann, F. (2021). Fast detection of denial constraint violations. Proc. VLDB Endow., 15(4):859–871.
Selinger, P. G., Astrahan, M. M., Chamberlin, D. D., Lorie, R. A., and Price, T. G. (1979). Access path selection in a relational database management system. In Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data, SIGMOD ’79, page 23–34, New York, NY, USA. Association for Computing Machinery.
Silberschatz, A., Korth, H. F., and Sudarshan, S. (2020). Database System Concepts, Seventh Edition. McGraw-Hill Book Company.
Wang, F., Chen, Q., Li, Y., Yang, T., Tu, Y., Yu, L., and Cui, B. (2023). Joinsketch: A sketch algorithm for accurate and unbiased inner-product estimation. Proc. ACM Manag. Data, 1(1).
Cormode, G., Garofalakis, M., Haas, P. J., and Jermaine, C. (2012). Synopses for massive data: Samples, histograms, wavelets, sketches. Found. Trends Databases, 4(1–3):1–294.
Cormode, G. and Muthukrishnan, S. (2005). An improved data stream summary: the count-min sketch and its applications. Journal of Algorithms, 55(1):58–75.
Flajolet, P., Fusy, É., Gandouet, O., and Meunier, F. (2007). Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm. Discrete mathematics & theoretical computer science, (Proceedings).
Freitag, M. and Neumann, T. (2019). Every row counts: Combining sketches and sampling for accurate group-by result estimates. ratio, 1:1–39.
Ioannidis, Y. (2003). The history of histograms (abridged). In Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29, VLDB ’03, page 19–30. VLDB Endowment.
Lee, K., Dutt, A., Narasayya, V., and Chaudhuri, S. (2023). Analyzing the impact of cardinality estimation on execution plans in microsoft sql server. Proc. VLDB Endow., 16(11):2871–2883.
Leis, V., Gubichev, A., Mirchev, A., Boncz, P., Kemper, A., and Neumann, T. (2015). How good are query optimizers, really? Proc. VLDB Endow., 9(3):204–215.
Leis, V., Radke, B., Gubichev, A., Mirchev, A., Boncz, P., Kemper, A., and Neumann, T. (2018). Query optimization through the looking glass, and what we found running the join order benchmark. The VLDB Journal, 27(5):643–668.
Liu, Z., Deep, S., Fariha, A., Psallidas, F., Tiwari, A., and Floratou, A. (2024). Rapidash: Efficient detection of constraint violations. Proc. VLDB Endow., 17(8):2009–2021.
Moerkotte, G. (2024). Cardinality estimation for having-clauses. Proc. VLDB Endow., 18(1):28–41.
Moerkotte, G. (2025). Building query compilers. University of Mannheim. [link].
Moerkotte, G., Neumann, T., and Steidl, G. (2009). Preventing bad plans by bounding the impact of cardinality estimation errors. Proc. VLDB Endow., 2(1):982–993.
Pena, E. H. M., de Almeida, E. C., and Naumann, F. (2021). Fast detection of denial constraint violations. Proc. VLDB Endow., 15(4):859–871.
Selinger, P. G., Astrahan, M. M., Chamberlin, D. D., Lorie, R. A., and Price, T. G. (1979). Access path selection in a relational database management system. In Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data, SIGMOD ’79, page 23–34, New York, NY, USA. Association for Computing Machinery.
Silberschatz, A., Korth, H. F., and Sudarshan, S. (2020). Database System Concepts, Seventh Edition. McGraw-Hill Book Company.
Wang, F., Chen, Q., Li, Y., Yang, T., Tu, Y., Yu, L., and Cui, B. (2023). Joinsketch: A sketch algorithm for accurate and unbiased inner-product estimation. Proc. ACM Manag. Data, 1(1).
Publicado
08/09/2026
Como Citar
T. ENOKIDA, Alexandre; PENA, Eduardo H. M..
Estudo Experimental da Estimativa de Cardinalidade para Autojunções. In: SIMPÓSIO BRASILEIRO DE BANCO DE DADOS (SBBD), 41. , 2026, São Carlos/SP.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2026
.
p. 250-260.
ISSN 2763-8979.
DOI: https://doi.org/10.5753/sbbd.2026.249204.
