Optimización de Consultas Basada en Costos
La optimización de consultas basada en costos busca en el espacio de planes de ejecución equivalentes para una consulta y selecciona aquel con el costo estimado más bajo, utilizando estadísticas sobre los datos y un modelo de costo de ejecución.
Definition
La optimización de consultas basada en costos es el proceso de estimar, a partir de estadísticas de datos y un modelo de costos, el costo de ejecución de planes equivalentes alternativos para una consulta y seleccionar el plan de menor costo estimado, típicamente con el orden de unión elegido por programación dinámica.
Scope
Este tema cubre cómo un optimizador elige un plan: el espacio de búsqueda de planes generado por equivalencias de álgebra relacional y operadores físicos alternativos, el modelo de costos que califica los planes (principalmente en E/S y CPU), la estimación de cardinalidad y selectividad a partir de estadísticas e histogramas, y el enfoque de programación dinámica para la enumeración de órdenes de unión introducido por System R. Excluye la implementación de los operadores en sí mismos y la reescritura lógica basada en reglas más allá de lo que alimenta la generación de planes.
Core questions
- ¿Cómo se genera y poda el espacio de planes de ejecución equivalentes?
- ¿Cómo estima el optimizador la cardinalidad y selectividad de las operaciones?
- ¿Cómo enumera la programación dinámica los órdenes de unión de manera eficiente?
- ¿Qué considera el modelo de costos y cómo se combinan los costos de E/S y CPU?
- ¿Por qué los errores de estimación de cardinalidad provocan malas elecciones de plan?
Key concepts
- espacio de búsqueda de planes
- modelo de costos (E/S y CPU)
- estimación de selectividad y cardinalidad
- histogramas y estadísticas
- enumeración de órdenes de unión
- programación dinámica
- órdenes interesantes
- optimización basada en transformaciones
Key theories
- Optimización por programación dinámica de System R
- El optimizador de Selinger enumera los órdenes de unión de abajo hacia arriba con programación dinámica, manteniendo el plan más barato para cada subconjunto de relaciones (y cada orden de clasificación interesante), lo que hace que la búsqueda en el gran espacio de órdenes de unión sea manejable.
- Estimación de cardinalidad y selectividad
- El optimizador estima el número de tuplas que produce cada operación utilizando estadísticas de tabla, histogramas y fórmulas de selectividad; estas estimaciones impulsan el modelo de costos y son la principal fuente de error de optimización.
- Modelos de costos y estrategias de búsqueda
- Los planes se califican mediante un modelo de costos que combina los efectos de E/S, CPU y memoria; más allá de la programación dinámica de System R, los optimizadores basados en transformaciones exploran planes mediante reglas de reescritura para extender la optimización a operadores más ricos y entornos distribuidos.
Clinical relevance
El optimizador es el componente que permite a los usuarios escribir SQL declarativo sin especificar cómo ejecutarlo; la calidad de sus estimaciones de costos y su búsqueda rige directamente si las consultas en grandes bases de datos son rápidas, por lo que la optimización basada en costos se encuentra entre las partes más estudiadas y comercialmente importantes de los sistemas de bases de datos.
History
El optimizador System R de 1979, desarrollado por Selinger y sus colegas, introdujo la optimización basada en costos con ordenación de uniones por programación dinámica y estimación de costos basada en selectividad, definiendo el campo. Optimizadores posteriores basados en transformaciones, como Volcano y Cascades, generalizaron la búsqueda, y el trabajo en curso sobre la estimación de cardinalidad, incluidos los modelos aprendidos, aborda la debilidad central del marco.
Debates
- Estimación de cardinalidad versus ejecución adaptativa
- Dado que la optimización basada en costos es tan buena como sus estimaciones de tamaño, que a menudo son incorrectas para datos correlacionados, los investigadores debaten si invertir en mejores estadísticas y estimadores aprendidos por máquina o si confiar más en la re-optimización adaptativa en tiempo de ejecución que corrige planes deficientes durante la ejecución.
Key figures
- Patricia Selinger
- Goetz Graefe
- Surajit Chaudhuri
Related topics
Seminal works
- selinger1979
- graefe1993
Frequently asked questions
- ¿Por qué un optimizador a veces elige un plan deficiente?
- Los optimizadores basados en costos se basan en estimaciones de cuántas filas producirá cada operación. Cuando los datos están sesgados o las columnas están correlacionadas, estas estimaciones pueden ser muy inexactas, y el error se acumula a través de las uniones. Una estimación incorrecta puede llevar al optimizador a elegir un orden de unión o una ruta de acceso deficiente, aunque el plan pareciera económico en teoría.
- ¿Por qué usar programación dinámica para la ordenación de uniones?
- El número de posibles órdenes de unión crece combinatoriamente con el número de tablas, por lo que la búsqueda exhaustiva es inviable. La programación dinámica construye planes óptimos para conjuntos de relaciones más grandes a partir de planes óptimos para subconjuntos más pequeños, reduciendo drásticamente el trabajo y aun así encontrando un buen (a menudo óptimo) orden de unión para tamaños de consulta típicos.