Optimización de consultas

Dos posibles planes de consulta para la consulta triangular R(A, B) ⋈ S(B, C) ⋈ T(A, C) ; el primero une S y T primero y une el resultado con R , el segundo une R y S primero y une el resultado con T.

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 y 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 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 desarrollado por el proyecto de base de datos System R de IBM . Este algoritmo funciona en dos etapas:

1. En primer lugar, se calculan todas las formas de acceder a cada relación en la consulta. Se puede acceder a cada relación mediante un escaneo secuencial. Si existe un índice en una relación que se puede usar para responder a un predicado en la consulta, también se puede usar un escaneo de índice. Para cada relación, el optimizador registra la forma más económica de escanearla, así como la forma más económica de escanearla que produce registros en un orden específico.
2. El optimizador considera entonces combinar cada par de relaciones para las que existe una condición de unión. Para cada par, el optimizador considerará los algoritmos de unión disponibles implementados por el sistema de gestión de bases de datos (DBMS) . Conservará la forma más económica de unir cada par de relaciones, además de la forma más económica de unir cada par de relaciones que produzca su resultado según un orden de clasificación específico.
3. A continuación, se calculan todos los planes de consulta de tres relaciones, uniendo cada plan de dos relaciones producido por la fase anterior con las relaciones restantes de la consulta.

El orden de clasificación puede evitar una operación de ordenación redundante más adelante al procesar la consulta. En segundo lugar, un orden de clasificación específico puede acelerar una unión posterior, ya que agrupa los datos de una manera particular.

Una consulta SQL en un sistema de gestión de bases de datos relacionales moderno realiza más que simples selecciones y uniones. En particular, las consultas SQL suelen anidar varias capas de bloques SPJ (Seleccionar-Proyectar-Unir) mediante los operadores GROUP BY , EXISTS y NOT EXISTS . En algunos casos, estas consultas SQL anidadas pueden simplificarse a una consulta de selección-proyección-unión, pero no siempre. Los planes de consulta para consultas SQL anidadas también pueden elegirse utilizando el mismo algoritmo de programación dinámica que se usa para la ordenación de uniones, pero esto puede provocar un aumento considerable en el tiempo de optimización de la consulta. Por ello, algunos sistemas de gestión de bases de datos utilizan un enfoque alternativo basado en reglas que emplea un modelo de grafo de consulta. ^{[ 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 que depende en gran medida de las estimaciones de la cardinalidad , o número de tuplas, que fluyen a través de cada arista en un plan de consulta. La estimación de la cardinalidad, a su vez, depende de las estimaciones del factor de selección de los predicados en la consulta. Tradicionalmente, los sistemas de bases de datos estiman las selectividades mediante estadísticas bastante detalladas sobre la distribución de valores en cada columna, como histogramas . Esta técnica funciona bien para estimar las 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 bases de datos debe actualizar regularmente las estadísticas de la base de datos, especialmente después de cargas/descargas importantes de datos.selectcount(*)fromRwhereR.make='Honda'andR.model='Accord'model='Accord'make='Honda'

La optimización clásica de consultas asocia cada plan de consulta con un valor de coste escalar. La optimización paramétrica de consultas ^{[ 9 ]} supone que el coste del plan de consulta depende de parámetros cuyos valores se desconocen en el momento de la optimización. Dichos parámetros pueden representar, por ejemplo, la selectividad de los predicados de consulta que no se especifican completamente 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 coste que mapea un espacio de parámetros multidimensional a un espacio de coste unidimensional.

El objetivo de la optimización suele ser generar todos los planes de consulta que podrían ser óptimos para cualquier combinación posible de valores de parámetros. Esto da como resultado 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 reales de los parámetros. La ventaja de la optimización de consultas paramétricas es que se evita la optimización (que generalmente 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 coste relevantes para comparar planes de consulta. En un entorno de computación en la nube , por ejemplo, conviene comparar los planes de consulta no solo en función del tiempo de ejecución, sino también de su coste. Asimismo, 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 menor sobrecarga de ejecución. En estos casos, es necesario comparar los planes de consulta alternativos no solo en función de su tiempo de ejecución, sino también de la precisión o fiabilidad de los datos que generan.

La optimización de consultas multiobjetivo ^{[ 10 ]} modela el costo de un plan de consulta como un vector de costos, donde cada componente del vector representa el costo según una métrica de costo diferente. La optimización de consultas clásica puede considerarse 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.

Las distintas métricas de coste pueden entrar en conflicto entre sí (por ejemplo, en un escenario de computación en la nube, puede haber un plan con un tiempo de ejecución mínimo y otro con costes de ejecución mínimos). Por lo tanto, el objetivo de la optimización no puede ser encontrar un plan de consulta que minimice todas las métricas de coste, sino encontrar un plan que logre el mejor equilibrio entre ellas. Este equilibrio óptimo depende de las preferencias del usuario (por ejemplo, en un escenario de nube, algunos usuarios pueden preferir un plan más económico, mientras que otros prefieren uno más rápido). El objetivo de la optimización consiste, por lo tanto, en encontrar el mejor plan de consulta en función de las preferencias del usuario, proporcionadas como entrada al optimizador (por ejemplo, los usuarios pueden definir ponderaciones entre diferentes métricas de coste para expresar su importancia relativa o establecer límites de coste estrictos para ciertas métricas), o bien en generar una aproximación del conjunto de planes de consulta óptimos de Pareto (es decir, planes en los que ningún otro plan tiene un coste mejor según todas las métricas), de modo que el usuario pueda seleccionar la opción de coste que prefiera dentro de ese conjunto de planes.

La optimización paramétrica de consultas multiobjetivo ^{[ 8 ]} generaliza la optimización paramétrica y multiobjetivo de consultas. Los planes se comparan según múltiples métricas de costo, y estos costos pueden depender de parámetros cuyos valores se desconocen al 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 resulten óptimos para cada posible combinación de valores de parámetros y preferencias del usuario.

Varias herramientas muestran planes de ejecución de consultas para identificar las operaciones con mayor coste de procesamiento. Microsoft SMS, ApexSQLPlan, Hana y Tableau son algunos ejemplos. Solucionar los problemas detectados en estos planes puede reducir el tiempo de ejecución en decenas de puntos porcentuales y, en algunos casos, convertir búsquedas bidimensionales en lineales.

Una de las listas de verificación de optimización primarias y más simples es usar operaciones que la mayoría de los sistemas de gestión de bases de datos relacionales (RDBMS) están diseñados para ejecutar de manera eficiente. Ver Sargable .