La optimización de consultas es una característica de muchos sistemas de gestión de bases de datos relacionales y otras bases de datos como NoSQL y bases de datos gráficas . El optimizador de consultas intenta determinar la forma más eficiente de ejecutar una consulta dada considerando los posibles planes de consulta . [1]
Generalmente, los usuarios no pueden acceder directamente al optimizador de consultas: una vez que las consultas se envían al servidor de base de datos y el analizador las analiza, se pasan al optimizador de consultas donde se produce la optimización. [2] [3] Sin embargo, algunos motores de base de datos permiten guiar al optimizador de consultas con sugerencias .
Una consulta es una solicitud de información a una base de datos. Puede ser tan simple como "encontrar la dirección de una persona con el número de Seguro Social 123-45-6789", o más compleja como "encontrar el salario promedio de todos los hombres casados empleados en California entre 30 y 39 años que ganan menos que sus cónyuges". El resultado de una consulta se genera procesando las filas de una base de datos de manera que se obtenga la información solicitada. Dado que las estructuras de las bases de datos son complejas, en la mayoría de los casos, y especialmente para consultas no muy simples, los datos necesarios para una consulta se pueden recopilar de una base de datos accediendo a ella de diferentes maneras, a través de diferentes estructuras de datos y en diferentes órdenes. [4] Cada forma diferente requiere típicamente un tiempo de procesamiento diferente. Los tiempos de procesamiento de la misma consulta pueden tener una gran variación, desde una fracción de segundo hasta horas, según el método elegido. El propósito de la optimización de consultas, que es un proceso automatizado, es encontrar la manera de procesar una consulta dada en el mínimo tiempo. La gran variación posible en el tiempo justifica la optimización de las consultas, aunque encontrar el plan de consulta óptimo exacto, entre todas las posibilidades, suele ser muy complejo, requiere mucho tiempo, puede resultar demasiado costoso y, a menudo, prácticamente imposible. Por ello, la optimización de consultas suele intentar aproximarse al óptimo comparando varias alternativas de sentido común para proporcionar en un tiempo razonable un plan "suficientemente bueno" que, por lo general, no se desvíe mucho del mejor resultado posible.
Existe un equilibrio entre la cantidad de tiempo empleado en determinar el mejor plan de consulta y la calidad de la elección; el optimizador puede no elegir la mejor respuesta por sí solo. Diferentes calidades de sistemas de gestión de bases de datos tienen diferentes formas de equilibrar estos dos. Los optimizadores de consultas basados en costos evalúan la huella de recursos de varios planes de consulta y utilizan esto como base para la selección del plan. [5] [6] Estos asignan un "costo" estimado a cada plan de consulta posible y eligen el plan con el menor costo. Los costos se utilizan para estimar el costo de tiempo de ejecución de la evaluación de la consulta, en términos de la cantidad de operaciones de E/S requeridas, longitud de ruta de CPU , cantidad de espacio de búfer de disco, tiempo de servicio de almacenamiento en disco y uso de interconexión entre unidades de paralelismo y otros factores determinados a partir del diccionario de datos . El conjunto de planes de consulta examinados se forma examinando las posibles rutas de acceso (por ejemplo, acceso al índice primario, acceso al índice secundario, escaneo completo del archivo) y varias técnicas de unión de tablas relacionales (por ejemplo, unión de fusión , unión hash , unión de producto). El espacio de búsqueda puede llegar a ser bastante grande dependiendo de la complejidad de la consulta SQL . Existen dos tipos de optimización: la optimización lógica, que genera una secuencia de álgebra relacional para resolver la consulta, y la optimización física, que se utiliza para determinar los medios para llevar a cabo cada operación.
La mayoría de los optimizadores de consultas representan los planes de consulta como un árbol de "nodos de plan". Un nodo de plan encapsula una única operación que se requiere para ejecutar la consulta. Los nodos están dispuestos como un árbol, en el que los resultados intermedios fluyen desde la parte inferior del árbol hasta la parte superior. Cada nodo tiene cero o más nodos secundarios, es decir, aquellos nodos cuya salida se introduce como entrada en el nodo principal. Por ejemplo, un nodo de unión tendrá dos nodos secundarios, que representan los dos operandos de unión, mientras que un nodo de ordenación tendría un único nodo secundario (la entrada que se va a ordenar). Las hojas del árbol son nodos que producen resultados al escanear el disco, por ejemplo, al realizar un escaneo de índice o un escaneo secuencial.
El rendimiento de un plan de consulta se determina en gran medida por el orden en el que se unen las tablas. Por ejemplo, al unir 3 tablas A, B, C de tamaño 10 filas, 10.000 filas y 1.000.000 de filas, respectivamente, un plan de consulta que une B y C primero puede tardar varios órdenes de magnitud más en ejecutarse que uno que une A y C primero. La mayoría de los optimizadores de consultas determinan el orden de unión mediante un algoritmo de programación dinámica iniciado por el proyecto de base de datos System R de IBM [ cita requerida ] . Este algoritmo funciona en dos etapas:
El orden de clasificación puede evitar una operación de clasificación redundante más adelante durante el procesamiento de la consulta. En segundo lugar, un orden de clasificación particular puede acelerar una unión posterior porque agrupa los datos de una manera particular.
Una consulta SQL a un DBMS relacional moderno hace más que simplemente seleccionar y unir. En particular, las consultas SQL a menudo anidan varias capas de bloques SPJ (Select-Project-Join), mediante operadores group by , exist y not exist. En algunos casos, estas consultas SQL anidadas se pueden aplanar en una consulta select-project-join, pero no siempre. Los planes de consulta para consultas SQL anidadas también se pueden elegir utilizando el mismo algoritmo de programación dinámica que se utiliza para ordenar las uniones, pero esto puede llevar a una enorme escalada en el tiempo de optimización de la consulta. Por lo tanto, algunos sistemas de gestión de bases de datos utilizan un enfoque alternativo basado en reglas que utiliza un modelo de gráfico de consultas. [7]
Uno de los problemas más difíciles en la optimización de consultas es estimar con precisión los costos de los planes de consulta alternativos. Los optimizadores calculan el costo de los planes de consulta utilizando un modelo matemático de costos de ejecución de consultas que se basa en gran medida en estimaciones de la cardinalidad , o número de tuplas, que fluyen a través de cada borde en un plan de consulta. La estimación de la cardinalidad, a su vez, depende de las estimaciones del factor de selección de predicados en la consulta. Tradicionalmente, los sistemas de bases de datos estiman las selectividades a través de estadísticas bastante detalladas sobre la distribución de valores en cada columna, como histogramas . Esta técnica funciona bien para la estimación de selectividades de predicados individuales. Sin embargo, muchas consultas tienen conjunciones de predicados como . Los predicados de consulta a menudo están altamente correlacionados (por ejemplo, implica ), y es muy difícil estimar la selectividad de la conjunción en general. Las estimaciones de cardinalidad deficientes y la correlación no detectada son una de las principales razones por las que los optimizadores de consultas eligen planes de consulta deficientes. Esta es una razón por la que un administrador de base de datos debe actualizar regularmente las estadísticas de la base de datos, especialmente después de cargas/descargas de datos importantes.select count(*) from R where R.make='Honda' and R.model='Accord'model='Accord'make='Honda'
La optimización clásica de consultas supone que los planes de consulta se comparan según una única métrica de costes, normalmente el tiempo de ejecución, y que el coste de cada plan de consulta se puede calcular sin incertidumbre. En la práctica, ambas suposiciones a veces se violan [8] y en la bibliografía se han estudiado múltiples extensiones de la optimización clásica de consultas que superan esas limitaciones. Esas variantes extendidas del problema difieren en cómo modelan el coste de los planes de consulta individuales y en términos de su objetivo de optimización.
La optimización clásica de consultas asocia cada plan de consulta con un valor de costo escalar. La optimización paramétrica de consultas [9] supone que el costo del plan de consulta depende de parámetros cuyos valores son desconocidos en el momento de la optimización. Dichos parámetros pueden, por ejemplo, representar la selectividad de los predicados de consulta que no están completamente especificados en el momento de la optimización, pero que se proporcionarán en el momento de la ejecución. Por lo tanto, la optimización paramétrica de consultas asocia cada plan de consulta con una función de costo que se asigna de un espacio de parámetros multidimensional a un espacio de costo unidimensional.
El objetivo de la optimización es generalmente generar todos los planes de consulta que podrían ser óptimos para cualquiera de las posibles combinaciones de valores de parámetros. Esto produce un conjunto de planes de consulta relevantes. En tiempo de ejecución, se selecciona el mejor plan de ese conjunto una vez que se conocen los valores verdaderos de los parámetros. La ventaja de la optimización de consultas paramétricas es que se evita la optimización (que en general es una operación muy costosa) en tiempo de ejecución.
Además del tiempo de ejecución, a menudo existen otras métricas de costos que son relevantes para comparar los planes de consulta. En un escenario de computación en la nube , por ejemplo, se deben comparar los planes de consulta no solo en términos de cuánto tiempo lleva ejecutarlos, sino también en términos de cuánto dinero cuesta su ejecución. O en el contexto de la optimización aproximada de consultas, es posible ejecutar planes de consulta en muestras seleccionadas aleatoriamente de los datos de entrada para obtener resultados aproximados con una sobrecarga de ejecución reducida. En tales casos, los planes de consulta alternativos deben compararse en términos de su tiempo de ejecución, pero también en términos de la precisión o confiabilidad de los datos que generan.
La optimización de consultas multiobjetivo [10] modela el costo de un plan de consultas como un vector de costos donde cada componente del vector representa el costo de acuerdo con una métrica de costos diferente. La optimización de consultas clásica puede considerarse como un caso especial de optimización de consultas multiobjetivo donde la dimensión del espacio de costos (es decir, la cantidad de componentes del vector de costos) es uno.
Diferentes métricas de costo pueden entrar en conflicto entre sí (por ejemplo, puede haber un plan con un tiempo de ejecución mínimo y un plan diferente con tarifas de ejecución monetarias mínimas en un escenario de computación en la nube). Por lo tanto, el objetivo de la optimización no puede ser encontrar un plan de consulta que minimice todas las métricas de costo, sino que debe ser encontrar un plan de consulta que logre el mejor compromiso entre diferentes métricas de costo. Cuál es el mejor compromiso depende de las preferencias del usuario (por ejemplo, algunos usuarios pueden preferir un plan más económico mientras que otros prefieren un plan más rápido en un escenario de nube). Por lo tanto, el objetivo de la optimización es encontrar el mejor plan de consulta basado en alguna especificación de las preferencias del usuario proporcionadas como entrada al optimizador (por ejemplo, los usuarios pueden definir pesos entre diferentes métricas de costo para expresar la importancia relativa o definir límites de costo duros en ciertas métricas) o generar una aproximación del conjunto de planes de consulta Pareto-óptimos (es decir, planes tales que ningún otro plan tiene mejor costo según todas las métricas) de modo que el usuario pueda seleccionar el compromiso de costo preferido de ese conjunto de planes.
La optimización de consultas paramétricas multiobjetivo [8] generaliza la optimización de consultas paramétricas y multiobjetivo. Los planes se comparan según múltiples métricas de costos y los costos del plan pueden depender de parámetros cuyos valores se desconocen en el momento de la optimización. Por lo tanto, el costo de un plan de consulta se modela como una función de un espacio de parámetros multidimensional a un espacio de costos multidimensional. El objetivo de la optimización es generar el conjunto de planes de consulta que pueden ser óptimos para cada combinación posible de valores de parámetros y preferencias del usuario.
Varias herramientas muestran planes de ejecución de consultas para indicar qué operaciones tienen el mayor costo de procesamiento. Microsoft SMS, ApexSQLPlan, Hana y Tableau son algunos ejemplos. La solución de los problemas detectados en estos planes puede reducir el tiempo de ejecución en un diez por ciento y, en algunos casos, puede reducir las búsquedas bidimensionales a lineales.
Una de las principales y más sencillas listas de verificación de optimización es utilizar operaciones que la mayoría de los RDMS están diseñados para ejecutar de manera eficiente. Consulte Sargable .