Estimación de selectividad de joins de desigualdad en bases de datos
Autores: Repas, Diogo; Luo, Zhicheng; Schoemans, Maxime; Sakr, Mahmoud
Idioma: Inglés
Editor: MDPI
Año: 2023
Acceso abierto
Artículo científico
2023
Estimación de selectividad de joins de desigualdad en bases de datos
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Habilidad
Optimizador de consultas SQL
Estimación de selectividad
Joins de desigualdad
Algoritmo
PostgreSQL
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 22
Citaciones: Sin citaciones
La estimación de la selectividad se refiere a la capacidad del optimizador de consultas SQL para estimar el tamaño de los resultados de un predicado en la consulta. Es el cálculo principal en base al cual el optimizador puede seleccionar el plan menos costoso para ejecutar. Aunque el problema ha sido conocido desde mediados de la década de 1970, nos sorprendió que no haya soluciones en la literatura para la estimación de la selectividad de joins desiguales. Al probar cuatro sistemas de bases de datos comunes: Oracle, SQL-Server, PostgreSQL y MySQL, encontramos que los sistemas de código abierto PostgreSQL y MySQL carecen de esta estimación. Oracle y SQL-Server hacen estimaciones bastante precisas, aunque sus algoritmos son secretos. Este documento propone un algoritmo para la estimación de la selectividad de joins desiguales. El algoritmo propuesto se implementó en PostgreSQL y se envió como un parche para ser incluido en las próximas versiones. Comparamos esta implementación con los mencionados SGBD para tres distribuciones de datos diferentes (uniforme, normal y Zipfian) y demostramos que nuestro algoritmo proporciona estimaciones extremadamente precisas (por debajo del 0,1% de error promedio), superando a los otros sistemas en un orden de magnitud.
Descripción
La estimación de la selectividad se refiere a la capacidad del optimizador de consultas SQL para estimar el tamaño de los resultados de un predicado en la consulta. Es el cálculo principal en base al cual el optimizador puede seleccionar el plan menos costoso para ejecutar. Aunque el problema ha sido conocido desde mediados de la década de 1970, nos sorprendió que no haya soluciones en la literatura para la estimación de la selectividad de joins desiguales. Al probar cuatro sistemas de bases de datos comunes: Oracle, SQL-Server, PostgreSQL y MySQL, encontramos que los sistemas de código abierto PostgreSQL y MySQL carecen de esta estimación. Oracle y SQL-Server hacen estimaciones bastante precisas, aunque sus algoritmos son secretos. Este documento propone un algoritmo para la estimación de la selectividad de joins desiguales. El algoritmo propuesto se implementó en PostgreSQL y se envió como un parche para ser incluido en las próximas versiones. Comparamos esta implementación con los mencionados SGBD para tres distribuciones de datos diferentes (uniforme, normal y Zipfian) y demostramos que nuestro algoritmo proporciona estimaciones extremadamente precisas (por debajo del 0,1% de error promedio), superando a los otros sistemas en un orden de magnitud.