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.
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 la sentencia 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:
- Se computan todas las formas de acceder a cada relación de la consulta; éstas formas pueden ser:
- Búsqueda secuencial.
- 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.
- 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.
- 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:
- Un orden particular puede evitar operaciones de ordenamiento posteriores.
- Determinado orden puede acelerar un JOIN subsecuente porque agrupa los datos en determinada forma.
Tuplas
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.
Relación
Formalmente, una relación R es un conjunto de n-tuplas.
Las propiedades fundamentales de una relación son:
- No hay tuplas repetidas.
- Las tuplas no están ordenadas.
- Los atributos no están ordenados.
Cuando vamos a realizar este proceso debemos tener en cuenta aspectos tales como:
- Evaluación de que la consulta es algebraicamente más correcta
- Evaluación de la carga sobre los recursos del sistema
Ejemplo
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.
SELECT DISTINCT S.NOMBRE
FROM S, SP
WHERE S.S=SP.S
AND SP.P="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.
Procedimientos
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.
¿Dónde incide la optimización?
- El coste de comunicación de acceso a almacenamiento secundario.
- El coste de almacenamiento.
- El coste de computación.
- El optimizador interviene también en las actualizaciones y borrados.
El proceso de optimización
Representación interna de consultas
- Características:
- Ser relacionalmente completo.
- Suministrar un punto de partida sólido para las siguientes fases.
- Proporcionar un grado de libertad suficiente para realizar las posibles optimizaciones.
- Sistemas de representación:
- Álgebra relacional
- Cálculo relacional
- El árbol sintáctico abstracto o árbol de consulta.
Conversión a forma canónica
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.
Elección de procedimientos de bajo nivel
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.
- Un optimizador debe tener algunos procedimientos disponibles para una operación de JOIN tales como:
- Un procedimiento para el caso en que la condición sea a través de una clave candidata.
- Un procedimiento para el caso en que el campo de restricción (en alfa unión) esté indexado.
- Un procedimiento para el caso en que el campo de restricción no esté indexado pero sí agrupados los datos físicamente.
Generación y elección de planes de consulta
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.
