Optimizador de consultas

Se ha sugerido que este artículo o sección sea fusionado con Optimización de consultas (discusión). Una vez que hayas realizado la fusión de artículos, pide la fusión de historiales aquí.

El optimizador de consultas es el componente del sistema de gestión de base de datos que intenta determinar la forma más eficiente de ejecutar una consulta SQL, es decir, cual es, de los posibles planes de ejecución para una consulta dada, el más eficiente. Los optimizadores basados en costo asignan un costo (que intenta estimar el costo de la consulta en términos de operaciones de entrada-salida requeridas, requerimientos de CPU y otros factores) a cada uno de esos planes, y elige el que tiene menor costo. El conjunto de planes de ejecución se forma examinando los posibles caminos de acceso (mediante índices o secuenciales), algoritmos de “join” (sort-merge join, hash join, bucles anidados). El optimizador no puede ser accedido directamente por los usuarios, sino que, una vez enviadas las consultas al servidor, pasan primero por el analizador y recién entonces llegan al optimizador.

Implementación

La mayoría de los optimizadores presentan los planes de ejecución como un árbol de nodos del plan. Un nodo del plan encapsula una operación simple en la ejecución de la consulta. Los resultados intermedios fluyen desde las hojas del árbol hacia la raíz. Los hijos de un nodo representan a las operaciones cuyas salidas son la entrada del nodo padre. Por ejemplo, un nodo “join” tendrá dos hijos, que representan a los dos operandos del “join”. Las hojas del árbol representan operaciones que producen resultados mediante búsqueda en el disco, por ejemplo, realizando una búsqueda indexada o una búsqueda secuencial.

Orden de “Join”

La eficiencia de un plan de ejecución es en gran parte determinada por el orden en el cual se opera con las tablas. Por ejemplo, al hacer “join” de una tabla pequeña con otras mucho mayores, tomará más tiempo si primero se operan las tablas grandes y luego la pequeña. La mayoría de los optimizadores determinan el orden de “join” por medio de un algoritmo de programación dinámica impulsado por el proyecto “System R database project” de IBM, que funciona en las siguientes etapas:

1. Se computan todas las formas de acceder a cada relación de la consulta; éstas formas pueden ser:
   1. Búsqueda secuencial.
   2. Búsqueda indexada, si existiere un índice sobre una relación que pudiere ser utilizado para responder a un predicado de la consulta.
      Para cada relación, el optimizador guarda la forma más eficiente de acceder a ella, así como también la forma más eficiente de accederla de manera de obtener los resultados en un orden determinado.
2. Se consideran las combinaciones de cada par de relaciones para las cuales exista una condición de “join”. Para cada par, se consideran los algoritmos de “join” disponibles implementados por el DBMS. Éste preservará la forma más eficiente de hacer “join” de cada par de relaciones.
3. Todos los planes de consultas de tres relaciones son computados, uniendo cada plan de dos relaciones producidos por la etapa previa, con las relaciones que quedan en la consulta.

El algoritmo sigue la pista del orden de los resultados que produce un plan de ejecución. Un plan se considera mejor que otro sólo si produce el resultado en el mismo orden. Esto es así por dos razones:

1. Un orden particular puede evitar operaciones de ordenamiento posteriores.
2. Determinado orden puede acelerar un “join” subsecuente porque agrupa los datos en determinada forma.