La optimización de consultas es una característica de muchos sistemas de administración de bases de datos relacionales y otras bases de datos como NoSQL y bases de datos de gráficos . El optimizador de consultas intenta determinar la forma más eficiente de ejecutar una consulta determinada 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 la 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 bases de datos permiten guiar el optimizador de consultas con sugerencias .
Una consulta es una solicitud de información de una base de datos. Puede ser tan simple como "buscar la dirección de una persona con número de Seguro Social 123-45-6789", o más complejo como "buscar 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 forma 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 normalmente requiere un tiempo de procesamiento diferente. Los tiempos de procesamiento de la misma consulta pueden variar mucho, 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 determinada en un tiempo mínimo. 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 ser demasiado costoso y, a menudo, prácticamente imposible. Por lo tanto, la optimización de consultas normalmente intenta aproximarse al óptimo comparando varias alternativas de sentido común para proporcionar en un tiempo razonable un plan "suficientemente bueno" que normalmente no se desvía mucho del mejor resultado posible.
Existe un equilibrio entre la cantidad de tiempo dedicado a determinar el mejor plan de consulta y la calidad de la elección; Es posible que el optimizador no elija la mejor respuesta por sí solo. Las diferentes calidades de los sistemas de gestión de bases de datos tienen diferentes formas de equilibrar ambas. Los optimizadores de consultas basados en costos evalúan la huella de recursos de varios planes de consulta y la utilizan como base para la selección del plan. [5] Estos asignan un "coste" 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 evaluar la consulta, en términos de la cantidad de operaciones de E/S requeridas, la longitud de la ruta de la CPU , la cantidad de espacio de búfer en disco, el tiempo del servicio de almacenamiento en disco y el 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 de archivos) y varias técnicas de unión de tablas relacionales (por ejemplo, unión de fusión, unión de hash , unión de producto). El espacio de búsqueda puede llegar a ser bastante grande dependiendo de la complejidad de la consulta SQL . Hay dos tipos de optimización. Estos consisten en optimización lógica, que genera una secuencia de álgebra relacional para resolver la consulta, y optimización física, que se utiliza para determinar la forma de realizar cada operación.
La mayoría de los optimizadores de consultas representan los planes de consulta como un árbol de "nodos del plan". Un nodo de plan encapsula una única operación necesaria 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: son nodos cuya salida se envía como entrada al 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 clasificación tendrá 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 realizando un escaneo de índice o un escaneo secuencial.
El rendimiento de un plan de consulta está determinado en gran medida por el orden en 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 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 primero A y C. 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 solo selecciones y uniones. En particular, las consultas SQL a menudo anidan varias capas de bloques SPJ (Select-Project-Join), mediante operadores agrupar por , existe y no existe. En algunos casos, estas consultas SQL anidadas se pueden combinar en una consulta de selección de unión a proyecto, 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 provocar un enorme aumento en el tiempo de optimización de las consultas. Por eso, algunos sistemas de gestión de bases de datos utilizan un enfoque alternativo basado en reglas que utiliza un modelo de gráfico de consulta. [6]
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 los costos de los planes de consulta utilizando un modelo matemático de costos de ejecución de consultas que depende en gran medida de 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 los 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 la consulta suelen estar 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 de las razones por las que un administrador de base de datos debe actualizar periódicamente las estadísticas de la base de datos, especialmente después de cargas/descargas importantes de datos.select count(*) from R where R.make='Honda' and R.model='Accord'model='Accord'make='Honda'
La optimización de consultas clásica supone que los planes de consulta se comparan según una única métrica de costo, generalmente el tiempo de ejecución, y que el costo de cada plan de consulta se puede calcular sin incertidumbre. Ambas suposiciones a veces se violan en la práctica [7] y en la literatura de investigación se han estudiado múltiples extensiones de la optimización de consultas clásicas que superan esas limitaciones. Esas variantes de problemas extendidos difieren en cómo modelan el costo de los planes de consulta única y en términos de su objetivo de optimización.
La optimización de consultas clásica asocia cada plan de consulta con un valor de costo escalar. La optimización de consultas paramétricas [8] supone que el costo del plan de consultas depende de parámetros cuyos valores se desconocen 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 de consultas paramétricas asocia cada plan de consulta con una función de costos que se asigna desde un espacio de parámetros multidimensional a un espacio de costos unidimensional.
El objetivo de la optimización suele ser 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 verdaderos valores de los parámetros. La ventaja de la optimización de consultas paramétricas es que la optimización (que en general es una operación muy costosa) se evita en tiempo de ejecución.
A menudo existen otras métricas de costos además del tiempo de ejecución que son relevantes para comparar planes de consultas. En un escenario de computación en la nube , por ejemplo, se deben comparar los planes de consulta no sólo en términos de cuánto tiempo tardan en ejecutarse, 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 [9] modela el costo de un plan de consulta como un vector de costos donde cada componente del vector representa el costo de acuerdo con una métrica de costo 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, el número de componentes del vector de costos) es uno.
Diferentes métricas de costos 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 consultas que minimice todas las métricas de costos, sino que debe ser encontrar un plan de consultas que logre el mejor compromiso entre diferentes métricas de costos. Cuál sea 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 proporcionada como entrada al optimizador (por ejemplo, los usuarios pueden definir ponderaciones entre diferentes métricas de costos para expresar la importancia relativa o definir límites estrictos de costos en ciertas métricas). o para generar una aproximación del conjunto de planes de consulta óptimos de Pareto (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 la compensación de costos preferida de ese conjunto de planes.
La optimización de consultas paramétricas multiobjetivo [7] 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 desde un espacio de parámetros multidimensional hasta un espacio de costos multidimensional. El objetivo de la optimización es generar el conjunto de planes de consulta que puedan 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 mostrar qué operaciones tienen el mayor costo de procesamiento. Microsoft SMS, ApexSQLPlan, Hana y Tableau son algunos ejemplos. Solucionar estos problemas encontrados en estos planes puede reducir decenas de por ciento el tiempo de ejecución y, en algunos casos, puede reducir las búsquedas bidimensionales a lineales.
Una de las listas de verificación de optimización principales y más simples es utilizar operaciones para las que la mayoría de los RDMS están diseñados para ejecutarse de manera eficiente. Véase Sargable .