Optimización de consultas

Cuando hablamos de optimización de consultas nos referimos a mejorar los tiempos de respuesta en un sistema de gestión de bases de datos relacional, pues la optimización es el proceso de modificar un sistema para mejorar su eficiencia o también el uso de los recursos disponibles.

En bases de datos relacionales el lenguaje de consultas SQL es el más utilizado por el común de los programadores y desarrolladores para obtener información desde la base de datos. La complejidad que pueden alcanzar algunas consultas puede ser tal, que el diseño de una consulta puede tomar un tiempo considerable, obteniendo no siempre una respuesta óptima.

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.

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.

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:

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:

Una tupla de una relación o de una tabla corresponde a una fila de aquella tabla. Las tuplas están comúnmente desordenadas puesto que matemáticamente una relación se define como un conjunto y no como una lista. No existen tuplas duplicadas en una relación o tabla dado el hecho de que una relación es un conjunto y los conjuntos por definición no permiten elementos duplicados.

Un corolario importante en este punto es que la llave primaria siempre existe dada la condición de unicidad de las tuplas, por lo tanto, como mínimo la combinación de todos los atributos de una tabla puede servir para la conformación de la llave primaria, sin embargo usualmente no es necesario incluir todos los atributos, comúnmente algunas combinaciones mínimas son suficientes.

Formalmente, una relación R es un conjunto de n-tuplas.

Las propiedades fundamentales de una relación son:

Cuando vamos a realizar este proceso debemos tener en cuenta aspectos tales como:

A continuación podemos observar un ejemplo de la problemática de optimización. En este simple problema tenemos tablas de “Suppliers” (S) y “Orders” (SP) con 100 administradores y 10 000 pedidos.

Consulta: “Obtener los nombres de los suministradores que nos sirven la pieza P2”. Consideraremos que sólo 50 tuplas de SP corresponden a la pieza P2.

En el anterior ejercicio tenemos un producto cartesiano S x SP 100 x 10.000 = 1.000.000 de tuplas leídas. Probablemente 1.000.000 de tuplas escritas en memoria virtual. Cuando utilizamos la sentencia WHERE pasamos de 1.000.000 de tuplas leídas a 50 tuplas, luego realizamos una proyección sobre S.NOMBRE, dando como resultado un máximo de 50 tuplas.

Seleccionar en SP las tuplas de la pieza P2. Se realizará lectura de 10.000 tuplas dando como resultado: 50 tuplas. Hacer JOIN de la tabla anterior. Con la tabla S se realizara lectura de 100 tuplas, dando como resultado: 50 tuplas con proyección sobre S.NOMBRE, dando como resultado un máximo de 50 tuplas.

En la conversión canónica encontramos que hay optimizaciones previas que tienen un resultado positivo seguro. En este paso debemos encontrar la expresión equivalente de una consulta dada en la que se mejore de alguna manera el rendimiento. Esta expresión equivalente será la forma canónica de dicha consulta.

En la elección de procedimientos de bajo nivel se debe evaluar la consulta previamente transformada, también encontraremos existencia de índices u otras rutas de acceso y la distribución de los valores de los datos almacenados. Luego se realizará un agrupamiento físico de los registros.

Cuando elegimos un plan una de las primeras cosas que debemos tener en cuenta para escogerlo es la estimación de costes. Estos costes dependen de muchos aspectos tales como el número de operaciones de entrada/salida del disco requeridas, la utilización de la CPU. Una consulta suele implicar la generación de resultados intermedios, estos resultados estarán directamente relacionados con el número de entrada/salida.