Please enable JavaScript.
Coggle requires JavaScript to display documents.
OPTIMIZACIÓN DE CONSULTAS (14.2. ESTIMACIÓN DE LAS ESTADÍSTICAS DE LOS…
OPTIMIZACIÓN DE CONSULTAS
Proceso de selección del plan de evaluación de las consultas más eficiente de entre las muchas estrategias generalmente disponibles para el procesamiento de una consulta dada, especialmente si la consulta es compleja.
14.1. VISIÓN GENERAL
Existen varios planes de evaluacion de consultas, unos mejores a otros.
Para escoger entre los diferentes planes de evaluación de consultas el optimizador tiene que estimar el coste de cada plan de evaluación.
Para hallar el plan de evaluación de consultas menos costoso el optimizador necesita generar planes alternativos que produzcan el mismo resultado que la expresión dada y escoger el menos costoso.
La generación de planes de evaluación de consultas implica dos etapas: la generación de expresiones que sean equivalentes lógicamente a la expresión dada.
La anotación de las expresiones resultantes en maneras alternativas de generar planes de evaluación de consultas alternativos.
El cálculo del coste exacto de evaluación de un plan no suele resultar posible sin evaluar realmente el plan. En lugar de eso, los optimizadores hacen uso de la información estadística sobre las relaciones, como los tamaños de las relaciones y las profundidades de los índices, para realizar una buena estimación del coste de cada plan.
Dada una consulta, suele haber gran variedad de métodos para calcular la respuesta. Es responsabilidad del sistema transformar la consulta tal y como la introdujo el usuario en una consulta equivalente que pueda calcularse de manera más eficiente. El proceso de búsqueda de una buena estrategia para el procesamiento de la consulta se denomina optimización de consultas.
14.2. ESTIMACIÓN DE LAS ESTADÍSTICAS DE LOS RESULTADOS
DE LAS EXPRESIONES
El coste de cada operación depende del tamaño y de
otras estadísticas de sus valores de entrada.
Se relacionan algunas estadísticas de las relaciones de bases de datos que se almacenan en los catálogos de los sistemas de bases de datos y luego se muestra el modo de utilizar las estadísticas para estimar estadísticas de los resultados de varias operaciones relacionales.
Información del catálogo
nr, el número de tuplas de la relación r.
br, el número de bloques que contienen tuplas de la relación r.
tr, el tamaño de cada tupla de la relación r en bytes.
fr, el factor de bloqueo de la relación r, es decir, el número de tuplas de la relación r que caben en un bloque.
V (A, r), el número de valores distintos que aparecen en la relación r para el atributo A
Los catálogos de los SGDD almacenan la siguiente información estadística sobre las relaciones de las bases de datos:
Estimación del tamaño de la selección
Depende del predicado de la selección.
En primer lugar se considerará un solo predicado de igualdad, luego un solo predicado de comparación y, finalmente, combinaciones de predicados
• Selecciones complejas:
Conjunción
Disyunción
Negación
Estimación del tamaño de las reuniones
• Si R ∩ S = ∅
es decir, las relaciones no tienen ningún atributo en común entonces r s es igual que r ∩ s, y se puede utilizar la técnica de estimación para los productos cartesianos.
• Si R ∩ S es una clave de R,
Entonces se sabe que cada tupla de s se combinará como máximo con una tupla de r.
• El caso más difícil es que R ∩ S no sea una clave de R ni de S. En este caso se supone, como se hizo para las selecciones, que todos los valores aparecen con igual probabilidad.
Estimación del tamaño de otras
operaciones
•Proyección: El tamaño estimado (número de registros de las tuplas) de una proyección de la forma ∏A (r) es V (A, r), ya que la proyección elimina los duplicados.
•Agregación: El tamaño de A G F (r) es simplemente V (A, r), ya que hay una tupla de A G F (r) por cada valor distinto de A.
•Operaciones de conjuntos: Si las dos entradas de una operación de conjuntos son selecciones de la misma relación se puede reescribir la operación de conjuntos como disyunciones, conjunciones o negaciones.
•Reunión externa: El tamaño estimado de r s es el tamaño de r s más el tamaño de r; el de r s es simétrico, mientras que el de r s es el tamaño de r s más los tamaños de r y de s
Estimación del número de valores
distintos
Para las selecciones el número de valores distintos de un atributo (o de un conjunto de atributos) A en el resultado de una selección, V (A, σθ (r)), puede estimarse de las maneras siguientes:
Si la condición de selección θ obliga a que A adopte un valor especificado (por ejemplo, A = 3), V (A, σθ (r)) = 1.
Si θ obliga a que A adopte un valor de entre un conjunto especificado de valores (por ejemplo, (A = 1 2 A = 3 2 A = 4)), entonces V (A, σθ (r)) se define como el número de valores especificados.
Si la condición de selección θ es de la forma A op v, donde op es un operador de comparación, V (A, σθ (r)) se estima que es V (A, r) * s, donde s es la selectividad de la selección.
En todos los demás casos de selecciones se da por supuesto que la distribución de los valores de A es independiente de la distribución de los valores para los que se especifican las condiciones de selección y se utiliza una estimación aproximada de min (V (A, r), nσθ (r) ).
Para las reuniones el número de valores distintos de un atributo (o de un conjunto de atributos) A en el resultado de una reunión, V (A, r s), puede estimarse de las maneras siguientes:
Si todos los atributos de A proceden de r, V (A, r s) se estima como min (V (A, r), n r s ), y de manera parecida si todos los atributos de A proceden de> s, V (A, r s) se estima que es min (V (A, s), n r s ).
Si A contiene atributos A1 de r y A2 de s, entonces V (A, r s) se estima como min (V (A1, r)
V (A2 – A1, s), V (A1 – A2, r)
V (A2, s), n r s )
14.3. TRANSFORMACIÓN DE EXPRESIONES RELACIONALES
Cada expresión del álgebra relacional representa una secuencia concreta de operaciones. El primer paso para la selección de una estrategia de procesamiento de consultas es la búsqueda de una expresión del álgebra relacional que sea equivalente a la expresión dada y que se estime menos costosa de ejecutar
Reglas de equivalencia
Las operaciones de selección conjuntivas pueden dividirse en una secuencia de selecciones individuales. Esta transformación se denomina cascada de σ
Las operaciones de selección son conmutativas
Sólo son necesarias las últimas operaciones de una secuencia de operaciones de proyección, las demás pueden omitirse. Esta transformación también puede denominarse cascada de Π.
Las selecciones pueden combinarse con los productos cartesianos y con las reuniones zeta.
Las operaciones de reunión zeta son conmutativas.
Las operaciones de reunión natural son asociativas.
La operación de selección se distribuye por la operación de reunión zeta bajo algunas condiciones.
La operación proyección se distribuye por la operación de reunión zeta bajo algunas condiciones
Las operaciones de conjuntos unión e intersección son conmutativas.
La unión y la intersección de conjuntos son asociativas.
La operación de selección se distribuye por las operaciones de unión, intersección y diferencia de conjuntos.
La operación de proyección se distribuye por la operación unión.
Ordenación de las reuniones
Una buena ordenación de las operaciones de reunión es
importante para reducir el tamaño de los resultados temporales.
Enumeración de expresiones equivalentes
Las técnicas de representación de expresiones que permiten que las dos expresiones apunten a las subexpresiones compartidas pueden reducir de manera significativa los requisitos de espacio, y muchos optimizadores de consultas las utilizan.
14.4. ELECCIÓN DE LOS PLANES DE EVALUACIÓN
Los planes de evaluación alternativa para cada expresión pueden generarse mediante reglas parecidas y se puede escoger el plan más económico para todas las expresiones. Se dispone de varias técnicas de optimización para reducir el número de expresiones alternativas y los planes que hace falta generar.
Interacción de las técnicas de evaluación
además de considerar las expresiones alternativas de cada consulta, también hay que considerar los algoritmos alternativos para cada operación de cada expresión. Se pueden utilizar reglas muy parecidas a las reglas de equivalencia para definir los algoritmos que pueden utilizarse para cada operación, y si su resultado puede encauzarse o se debe materializar. Se pueden utilizar estas reglas para generar todos los planes de evaluación de consultas para una expresión dada.
Optimización basada en el coste
Generan una gama de planes de evaluación a partir de la consulta dada empleando las reglas de equivalencia y escogen el de coste mínimo. Para las consultas complejas el número de planes de consulta diferentes que son equivalentes a un plan dado puede ser grande.
Optimización heurística
muchos sistemas utilizan la heurística para reducir el
número de elecciones que hay que hacer de una manera
basada en los costes. Algunos sistemas incluso deciden
utilizar sólo la heurística y no utilizan en absoluto
la optimización basada en el coste.
Ejemplos
Llevar a cabo las operaciones de selección tan pronto como sea posible.
Llevar a cabo las proyecciones tan pronto como sea posible
Pasos
Hay que descomponer las selecciones conjuntivas en una secuencia de operaciones de selección sencillas.
Hay que desplazar las operaciones de selección hacia la parte inferior del árbol de consultas para conseguir su ejecución lo antes posible.
Hay que determinar las operaciones de selección y de reunión que producirán las relaciones de menor tamaño, es decir, que producirán las relaciones con el menor número de tuplas.
Hay que sustituir por operaciones de reunión las operaciones producto cartesiano seguidas de condiciones de selección.
Hay que dividir las listas de atributos de proyección y desplazarlas hacia la parte inferior del árbol todo lo que sea posible, creando proyecciones nuevas donde sea necesario.
Hay que identificar los subárboles cuyas operaciones pueden encauzarse y ejecutarlos utilizando el encauzamiento.
Estructura de los optimizadores de consultas
**
Los enfoques de la optimización de consultas que integran la selección heurística y la generación de planes de acceso alternativos se han adoptado en varios sistemas.
Los optimizadores de consultas más prácticos combinan elementos de ambos enfoques.
Optimización de las subconsultas
anidadas**
SQL trata conceptualmente a las subconsultas anidadas de la cláusula where como funciones que toman parámetros y devuelven un solo valor o un conjunto de valores (quizás, un conjunto vacío). Los parámetros son las variables de la consulta del nivel externo que se utilizan en la subconsulta anidada (estas variables se denominan variables de correlación).
Los optimizadores de SQL intentan transformar las subconsultas anidadas en reuniones, siempre que resulta posible. Los algoritmos de reunión eficientes evitan las costosas operaciones aleatorias de E/S. Cuando la transformación no resulta posible el optimizador conserva las subconsultas como expresiones independientes, las optimiza por separado y luego las evalúa mediante la evaluación correlacionada.
14.5. VISTAS MATERIALIZADAS**
Las vistas materializadas pueden utilizarse para acelerar el procesamiento de las consultas.
La conservación incremental de las vistas es necesaria para actualizar de forma eficiente las vistas materializadas cuando se modifican las relaciones subyacentes.
El diferencial de cada operación puede calcularse mediante expresiones algebraicas que impliquen a los diferenciales de las entradas de la operación.
Entre otros aspectos relacionados con las vistas materializadas están el modo de optimizar las consultas haciendo uso de las vistas materializadas disponibles y el modo de seleccionar las vistas que hay que materializar.
Es una vista cuyo contenido se calcula y se almacena.
Mantenimiento de las vistas
Las vistas tienen que mantenerse actualizadas, he aqui algunos metodos:
Las vistas pueden mantenerse mediante código escrito a mano.
otra forma es la definición de desencadenadores para la inserción, la eliminación y la actualización de cada relación de la definición de la vista.
Una opción mejor es modificar sólo las partes afectadas de la vista materializada, lo que se conoce como mantenimiento incremental de la vista.
Mantenimiento incremental
de las vistas
Se consideran las operaciones individuales:
Las operaciones selección y proyección
La operación reunión
Las operaciones selección y proyección
Las operaciones de agregación
Otras operaciones
Tratamiento de expresiones
Para tratar una expresión entera se pueden obtener expresiones para el cálculo del cambio incremental en el resultado de cada subexpresión, comenzando por las de menor tamaño.
Optimización de consultas y vistas materializadas
La optimización de consultas puede llevarse a cabo tratando las vistas materializadas igual que a las relaciones normales. No obstante, las vistas materializadas ofrecen más oportunidades para la optimización:
Reescritura de las consultas para el empleo de vistas materializadas.
Sustitución del empleo de una vista materializada por la definición de la vista.