Otimização de Semi-Junções: Aplicação do Nested Loop Join e Estratégias de Execução Eficientes
Resumo
Este artigo explora o uso do algoritmo Nested Loop Join para a execução de semi-junções. São apresentadas três variações do algoritmo: uma abordagem ingênua e duas versões otimizadas. Os experimentos realizados analisaram o impacto dessas otimizações em duas consultas representativas. Além disso, foram examinados os planos de execução gerados, destacando como a identificação da semântica de uma semi-junção pode permitir otimizações significativas, desmistificando a ideia de que subconsultas são mais custosas do que junções regulares.Referências
Cagliero, L., De Russis, L., Farinetti, L., and Montanaro, T. (2018). Improving the effectiveness of sql learning practice: A data-driven approach. In 2018 IEEE 42nd Annual Computer Software and Applications Conference (COMPSAC), volume 01, pages 980–989.
Elhemali, M., Galindo-Legaria, C. A., Grabs, T., and Joshi, M. M. (2007). Execution strategies for sql subqueries. In Proceedings of the 2007 ACM SIGMOD international conference on Management of data, pages 993–1004.
Kossmann, J., Papenbrock, T., and Naumann, F. (2022). Data dependencies for query optimization: a survey. The VLDB Journal, 31(1):1–22.
Krogh, J. W. and Krogh, J. W. (2020). The query optimizer. MySQL 8 Query Performance Tuning: A Systematic Method for Improving Execution Speeds, pages 417–485.
Lawrence, R. (2014). Integration and virtualization of relational sql and nosql systems including mysql and mongodb. In 2014 International Conference on Computational Science and Computational Intelligence, volume 1, pages 285–290. IEEE.
Lee, K., König, A. C., Narasayya, V., Ding, B., Chaudhuri, S., Ellwein, B., Eksarevskiy, A., Kohli, M., Wyant, J., Prakash, P., et al. (2016). Operator and query progress estimation in microsoft sql server live query statistics. In Proceedings of the 2016 International Conference on Management of Data, pages 1753–1764.
Mehta, S., Kaur, P., Lodhi, P., and Mishra, O. (2018). Empirical evidence of heuristic and cost based query optimizations in relational databases. In 2018 Eleventh International Conference on Contemporary Computing (IC3), pages 1–3.
Miedema, D., Fletcher, G., and Aivaloglou, E. (2022). Expert perspectives on student errors in sql. ACM Trans. Comput. Educ., 23(1).
Płodzień, J. and Subieta, K. (2001). Query optimization through removing dead sub-queries. In East European Conference on Advances in Databases and Information Systems, pages 27–40. Springer.
Poulsen, S., Butler, L., Alawini, A., and Herman, G. L. (2020). Insights from student solutions to sql homework problems. In Proceedings of the 2020 ACM Conference on Innovation and Technology in Computer Science Education, ITiCSE ’20, page 404–410, New York, NY, USA. Association for Computing Machinery.
Shankar, S., Nehme, R., Aguilar-Saborit, J., Chung, A., Elhemali, M., Halverson, A., Robinson, E., Subramanian, M. S., DeWitt, D., and Galindo-Legaria, C. (2012). Query optimization in microsoft sql server pdw. In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data, pages 767–776.
Elhemali, M., Galindo-Legaria, C. A., Grabs, T., and Joshi, M. M. (2007). Execution strategies for sql subqueries. In Proceedings of the 2007 ACM SIGMOD international conference on Management of data, pages 993–1004.
Kossmann, J., Papenbrock, T., and Naumann, F. (2022). Data dependencies for query optimization: a survey. The VLDB Journal, 31(1):1–22.
Krogh, J. W. and Krogh, J. W. (2020). The query optimizer. MySQL 8 Query Performance Tuning: A Systematic Method for Improving Execution Speeds, pages 417–485.
Lawrence, R. (2014). Integration and virtualization of relational sql and nosql systems including mysql and mongodb. In 2014 International Conference on Computational Science and Computational Intelligence, volume 1, pages 285–290. IEEE.
Lee, K., König, A. C., Narasayya, V., Ding, B., Chaudhuri, S., Ellwein, B., Eksarevskiy, A., Kohli, M., Wyant, J., Prakash, P., et al. (2016). Operator and query progress estimation in microsoft sql server live query statistics. In Proceedings of the 2016 International Conference on Management of Data, pages 1753–1764.
Mehta, S., Kaur, P., Lodhi, P., and Mishra, O. (2018). Empirical evidence of heuristic and cost based query optimizations in relational databases. In 2018 Eleventh International Conference on Contemporary Computing (IC3), pages 1–3.
Miedema, D., Fletcher, G., and Aivaloglou, E. (2022). Expert perspectives on student errors in sql. ACM Trans. Comput. Educ., 23(1).
Płodzień, J. and Subieta, K. (2001). Query optimization through removing dead sub-queries. In East European Conference on Advances in Databases and Information Systems, pages 27–40. Springer.
Poulsen, S., Butler, L., Alawini, A., and Herman, G. L. (2020). Insights from student solutions to sql homework problems. In Proceedings of the 2020 ACM Conference on Innovation and Technology in Computer Science Education, ITiCSE ’20, page 404–410, New York, NY, USA. Association for Computing Machinery.
Shankar, S., Nehme, R., Aguilar-Saborit, J., Chung, A., Elhemali, M., Halverson, A., Robinson, E., Subramanian, M. S., DeWitt, D., and Galindo-Legaria, C. (2012). Query optimization in microsoft sql server pdw. In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data, pages 767–776.
Publicado
23/04/2025
Como Citar
SOUZA, Matheus D.; MERGEN, Sérgio L. S..
Otimização de Semi-Junções: Aplicação do Nested Loop Join e Estratégias de Execução Eficientes. In: ESCOLA REGIONAL DE BANCO DE DADOS (ERBD), 20. , 2025, Florianópolis/SC.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2025
.
p. 100-109.
ISSN 2595-413X.
DOI: https://doi.org/10.5753/erbd.2025.6725.
