1 Administración de Bases de Datos Procesamiento y optimización de consultas Objetivos Comprender las tareas de procesamiento y optimización de consultas

1

Administración de Bases de Datos

Procesamiento y optimización de consultas

Objetivos

Comprender las tareas de procesamiento y optimización de consultas realizadas por un SGBD relacional

Conocer reglas heurísticas y de transformaciones de expresiones del álgebra relacional y cómo aplicarlas para mejorar la eficiencia de una consulta

Conocer diferentes estrategias de implementación de operaciones relacionales, en particular del join y cómo evaluar sus costes

Identificar la información estadística de la BD necesaria para estimar el coste de ejecución de las operaciones del álgebra relacional

2



Contenidos


Etapas del procesamiento de consultas Análisis léxico, sintáctico y validación Optimización

Reglas transformación

Implementación de operaciones relacionales

3



Crítica a los primeros sistemas relacionales: bajo rendimiento en las consultas.

Estudio de algoritmos eficientes para procesar consultas

En un SGBD...

Consultas expresadas en SQL: Qué datos y no cómo recuperarlos

El SGBD selecciona la mejor estrategia de ejecución: el sistema decide las operaciones necesarias y su orden de ejecución

4



Procesamiento de consultas:

actividades involucradas en la recuperación de datos de la BD

Optimización de consultas:

Elección de una estrategia de ejecución eficaz para procesar cada consulta sobre la BD

La optimización automática es obligatoria se se quiere lograr un tiempo de consulta aceptable

5



Objetivos del procesamiento de consultas

Transformar una consulta SQL en una estrategia de ejecución eficaz, expresada en un lenguaje de bajo nivel

Ejecutar dicha estrategia para recuperar los datos requeridos Existen muchas transformaciones equivalentes

Objetivos de la optimización de consultas

Elegir la estrategia de ejecución que minimiza el uso de los recursos

En general, el SGBD no garantiza que la estrategia elegida sea la óptima (pero seguro que es una bastante eficiente)

6



Ventajas de la optimización automática

El usuario no se preocupa de cómo formular la consulta El módulo optimizador trabaja “mejor” que el programador:

Dispone de información estadística en el diccionario de datos Mayor precisión al estimar la eficiencia de cada posible

estrategia Y así (con mayor probabilidad) elegirá la más eficiente Si cambian las estadísticas (tras reorganización del esquema de

la BD), el módulo optimizador elige otra estrategia El módulo optimizador considera más estrategias que un

programador El optimizador contempla toda la experiencia sobre el tema

7


Procesamiento de una consulta

1. Análisis léxico, sintáctico y validación

2. Optimización

3. Generación de código

4. Ejecución

8


Análisis léxico, sintáctico y validación

Análisis léxico Identificar los componentes léxicos en el texto de la

consulta SQL Análisis sintáctico

Revisar la corrección gramatical de la consulta SQL Validación semántica

Verificar la validez de los nombres de las relaciones y atributos

Traducción de la consulta a una representación interna El formalismo usado debe ser:

Rico, para representar toda consulta posible Neutral, sin predisponer a ciertas opciones de optimización

Álgebra relacional

9



Nombres de los empleados que trabajan en el proyecto 2

SELECT nombrep FROM Empleado E, Trabaja_en TWHERE E.nss=T.nsse and T.nump>=2;

nombrep (nump=2 (Empleado TRABAJA_EN))nss=nsse

proyección restricción fusión

10



nombrep (nump=2 (Empleado TRABAJA_EN))nss=nsse

Resultado

Proyectar(E.nombrep)

restringir(T.nump=2)

Reunir(E.nss=T.nsse)

EMPLEADO(E) TRABAJA_EN(T)

árbol de consulta (o árbol sintáctico abstracto) como

representación de una expresión algebraica

11


Optimización

El optimizador de consultas combina diferentes técnicas:

Optimización heurística

Ordenar las operaciones en una estrategia de ejecución

Estimación de costes

Estimar sistemáticamente el coste de cada estrategia

Elegir el plan (estrategia) con el menor costo estimado

12


Optimización heurística

Aplicación de reglas heurísticas para midificar la representación interna de una consulta (álgebra relacional o árbol de consulta) para mejorar su rendimiento

Varias expresiones del álgebra relacional pueden corresponder a la misma consulta

Lenguajes de consulta como SQL ...

Permiten expresar una misma consulta de formas diferentes, ...

... pero el rendimiento no debería depender de cómo sea expresada la consulta

13


Optimización

El analizador sintáctico genera un árbol de consulta inicial

Sin optimización y por tanto ineficiente

El optimizador de consultas transforma el árbol de consulta inicial en un árbol de consulta final equivalente pero más eficiente

Mediante la aplicación de reglas de transformación guiadas por heurísticos

Conversión de la consulta a su forma canónica equivalente

14


Optimización

Obtenida la forma canónica equivalente, el Optimizador decide cómo evaluarla

Estimación sistemática de costes:

Estimación y comparación de los costes de ejecutar una consulta con diferentes estrategias, y elegir la de menor coste estimado

El punto de partida es considerar la consulta como una serie de operaciones interdependientes

Operaciones del álgebra relacional JOIN, PROYECCIÓN, RESTRICCIÓN, UNION, INTERSECCIÓN, ...

15


Optimización

El Optimizador tiene un conjunto de técnicas para implementar cada operación. Por ejemplo, la operación

Búsqueda lineal Búsqueda binaria Empleo de índice primario o clave de dispersión Empleo de índice de agrupamiento Empleo de índice secundario

Cada procedimiento tiene asociada una estimación del coste

COSTE = número de accesos a bloque de disco necesarios Debe estimar el tamaño actual de las tablas

16


Optimización

Información Estadística

(diccionario de datos)

Información sobre la interdependencia entre las operaciones de bajo nivel

Elección de varias técnicas candidatas para cada operación

OPTIMIZADOR

17


Optimización

Información estadística El éxito de la estimación estadística del tamaño y coste de las

operaciones incluidas en una consulta depende de la cantidad y actualidad de la información almacenada en el diccionario de datos

Para cada relación Cardinalidad (número de tuplas) Factor de bloque (número de tuplas que caben en cada bloque) Número de bloques ocupados Método de acceso primario y otras estructuras de acceso (índices,

hash, etc.) Atributos indexados, de dispersión, de ordenamiento (físico o no),

etc. Para cada atributo:

Número de valores distintos almacenados Valores máximo y mínimo

Número de niveles de los índices de múltiples niveles

18


Optimización

El optimizador genera varios planes de ejecución y elige el plan más económico

Plan de ejecución = combinación de técnicas candidatas (una por cada operación de bajo nivel de la consulta)

Función de cose a minimizar

Medida en número de accesos a bloque (transferencias de bloques de memoria a disco)

)icacoste(técn )coste(plan ii

19


Optimización

En general, existen muchos posibles planes de ejecución (demasiados!)

La tarea de elegir el plan más económico tiene un coste prohibitivo

Uso de técnicas heurísticas para mantener el conjunto de planes de consulta generados dentro de unos límites razonables:

se pretende una reducción del espacio de evaluación

20


Reglas generales de transformación

Una secuencia de restricciones sobre una relación A puede transformarse en una sola restricción

c1(c2(A)) = c1 AND c2(A)

En una secuencia de proyecciones contra una relación A pueden ignorarse todas, salvo la última (si cada atributo mencionado en la última, también aparece en las demás)

p2(p1(A)) = p2(A), sii p2 p1

Una restricción de una proyección puede transformarse en una proyección de una restricción

c(p(A)) = p(c(A))

Es mejor hacer restricción antes que proyección pues la restricción reduce el número de filas a considerar

21



Distributividad respecto a una operación:f(A op B) = f(A) op f(b)

Las restricciones son distributivas respecto a la UNIÓN, INTERSECCIÓN y DIFERENCIA

c(R op S) = (c(R)) op (c(S)) donde op ={ , , - }

La proyección es distributiva respecto a la UNIÓN

p(R S) = (p(R)) (p(S))

22



La restricción es distributiva respecto a la reunión (JOIN) si la condición de selección contiene atributos que sólo pertenecen a una relación

O puede escribirse como (c1 AND c2), y en c1 sólo intervienen atributos de R1 y en c2 sólo de R2

Se reduce el número de tuplas a examinar en la siguiente operación

nump=2 (Empleado TRABAJA_EN) =

EMPLEADO nump=2 (TRABAJA_EN)

nss=nsse

nss=nsse

c (R1 R2) = (c1(R1)) (c2(R2)) j j

23



Las proyecciones son distributivas respecto del JOIN si la condición de reunión R sólo intervienen atributos incluidos en la lista de proyección P

sii P = (PR1 UNION PR2) y P incluye todo atributo de reunión que aparece en R

También se reduce el número de tuplas que son examinadas

P (R1 R2) = (PR1 (R1)) (PR2 (R2)) R R

24



Conmutatividadop es conmutativo si A op B = B op A

son conmutativas UNION, INTERSECTION, JOIN no conmutativas DIFERENCIA

Asociatividadop es asociativo si A op (B op C) = (A op B) op C

son asociativas UNION, INTERSECTION, JOIN no asociativas DIFERENCIA

Idempotentesop es idempotente si A op A = A

son idempotentes DIFERENCIA, UNION, INTERSECTION, JOIN

25



Expresiones de cómputo escalar El Optimizador debe conocer reglas de transformación de

expresiones aritméticas, pues aparecen en las consultas Reglas de transformación basadas en propiedades

Conmutativa, Asociativa y distributiva

Expresiones condicionales El optimizador debe saber aplicar reglas generales a

operadores De comparación (<,>, ...) Lógicos (AND, OR, ...)

26



Sean a y b atributos de dos relaciones distintas R(...,a,...) S(...,b,...)

La condición a>b AND b>3 equivale a a>3 AND b>3 AND a>bLa condición a>3 permite realizar una restricción antes del JOIN entre R y S necesario para evaluar a>b

Sean los atributos a,b,c,d,e,fLa condición a>b OR (c=d AND e<f) equivale a(a>b OR c=d) AND (a>b AND e<f)OR distributivo respecto al ANDToda expresión condicional puede transformarse en su Forma Normal Conjuntiva (FNC)

27



Una FNC tiene la forma C1 AND C2 AND ... CN donde Ci no incluye ningún ANDEs TRUE si todo Ci es TRUE, y es FALSE si algún Ci es FALSE

Ventajas de la FNC

Ya que AND es conmutativo, el Optimizador puede evaluar cada Ci en cualquier orden (por ejemplo, en orden creciente de dificultad). En cuanto un Ci es FALSE, el proceso puede acabar!

En un entorno de procesamiento paralelo, es posible evaluar todos los Ci a la vez. Y en cuanto uno diera FALSE, el proceso acabaría

28


Reglas heurísticas

Ejecutar las operaciones de restricción tan pronto como sea posible

Ejecutar primero las restricciones más restrictivas (las que producen menor número de tuplas)

Ejecutar las operaciones de proyección tan pronto como sea posible

29


Implementación del JOIN

Técnicas para realizar una reunión:

Fuerza bruta Búsqueda por índice Búsqueda Hash Mezcla Hash Combinación de las anteriores

El coste asintótico debería calcularse en términos de número de accesos a bloques de disco (no a tuplas)

30


Implementación del JOIN

Técnicas para realizar una reunión:

Fuerza bruta Búsqueda por índice Búsqueda Hash Mezcla Hash Combinación de las anteriores

El coste asintótico debería calcularse en términos de número de accesos a bloques de disco (no a tuplas)

31


Implementación del JOIN por fuerza bruta

Examinar todas las posibles combinaciones de tuplas R y S

for(i=1;i<=m;i++)for(j=1;j<=n;j++)

if (R[i].k = S[j].k) añadir R[i]+S[j] al resultado

O(m*n)

32


Implementación del JOIN por búsqueda por índice

Existe un índice X sobre el atributo S.k

for(i=1;i<=m;i++)// existen t entradas de X con valor de atributo

R[i].kfor(j=1;j<=t;j++)

añadir R[i]+S[j] al resultado

O(m*t*log n) donde suponemos n >> t*log n

33


Implementación del JOIN por búsqueda hashing

Existe un Hash H sobre el atributo S.k

for(i=1;i<=m;i++)// existen t tuplas accesibles desde H(R[i].k)for(j=1;j<=t;j++)

añadir R[i]+S[j] al resultado

O(m*t) donde suponemos n >> t

34


Implementación del JOIN por mezcla

Considera R y S ordenadas según el atributo de reunión Pueden examinarse ambas tablas en una única pasada

comparándolas simultáneamente

O(m+n) Supone las dos tablas ordenadas O(mlogm+nlogn)

35


Implementación del JOIN por Hash

Necesita una única pasada sobre los datos de cada relación

1) Construir una Tabla Hash H sobre S.k

2) Examinar R y aplicar la misma función de Hash sobre R.k

Si una tupla R colisiona en H con tuplas de S, entonces se generan las tuplas reunidas

No es necesario tenerlas ordenadas

O(n+m)

36


Optimización en MySQL

La optimización requiere la comprensión de todo el sistema

Compromiso entre el tiempo que requiere encontrar la mejor optimización y la mejora en eficiencia

http://www.mysql.com/information/benchmarks.html

http://www.mysql.com/information/crash-me.php

SELECT benchmark(loop_count, expression)

37


EXPLAIN

EXPLAIN SELECT select_options

Explica cómo se procesará la operación SELECT, cómo se reunirán (JOIN) las tablas y en qué orden

Con la ayuda de EXPLAIN podemos averiguar cuando debemos añadir nuevos índices a las tablas para hacer los SELECT más eficientes

Deberíamos ejecutar ANALYZE TABLE frecuentemente para obtener estadísticas sobre la cardinalidad de claves que pueden afectar a las elecciones del optimizador

38


EXPLAIN

EXPLAIN SELECT select_options

Explica cómo se procesará la operación SELECT, cómo se reunirán (JOIN) las tablas y en qué orden

Con la ayuda de EXPLAIN podemos averiguar cuando debemos añadir nuevos índices a las tablas para hacer los SELECT más eficientes

STRAIGHT_JOIN para forzar el orden de un SELECT

Deberíamos ejecutar ANALYZE TABLE frecuentemente para obtener estadísticas sobre la cardinalidad de claves que pueden afectar a las elecciones del optimizador

39


EXPLAIN

Las tablas aparecen en el orden en que son procesadas

table type possible_keys key key_len ref rows Extraet ALL PRIMARY NULL NULL NULL 74do ALL PRIMARY NULL NULL NULL 2135et_1 ALL PRIMARY NULL NULL NULL 74tt ALL AssignedPC, NULL NULL NULL 3872

ClientID,ActualPC

74 * 2135 * 74 * 3872 = 45,268,558,720

40


EXPLAIN

Soluciones:

Añadir índices

SHOW INDEX FROM table

Myisamchk –analyse table

ANALIZE TABLE

OPTIMIZE TABLE

41


WHERE

Elimina paréntesis innecesarios

((a AND b) AND c OR (((a AND b) AND (c AND d)))) =>(a AND b AND c) OR (a AND b AND c AND d)

Substitución de constantes

(a<b AND b=c) AND a=5 =>B>5 AND b=c AND a=5

Eliminación de condiciones constantes

(b>=5 AND b=5) OR (B=6 AND 5=5) OR (B=7 AND 5=6) =>

B=5 OR B=6

42


Otras optimizaciones

DISTINCT

LEFT JOIN, RIGHT JOIN

ORDER BY

LIMIT

INSERT

UPDATE

DELETE

43


Optimización de la estructura de la BD

Ocupar el mínimo (en tamaño de datos e índices)

Las lecturas de disco serán más rápidas Los índices ocupan menos sobre campos pequeños

Usar los tipos más eficientes posible (más pequeños) Declarar los campos NOT NULL Usar tamaños fijos de registro (varchar, TEXT, BLOB) Sólo crear los índices necesarios (los UPDATES son más

lentos con más índices)

44


Los índices

Se almacenan aparte de los datos! Optimizan la cláusula WHERE Optimizan las operaciones JOIN Localizan el MIN y MAX del campo indexado Ordena o agrupa una tabla Algunas veces permite ahorrarnos la consulta de los

datos! Comparar valores con LIKE “Name%” Podemos indexar prefijos de campos Pueden indexarse todos los tipos de campo

45


Diferentes configuraciones

Según las distintas cargas esperadas

my-small.cnf

my-medium.cnf

my-large.cnf

my-huge.cnf

46


Replicación

Mejora la robustez y la velocidad

Puede mantener varias copias de la BD. Una actúa de MASTER y la otra de SLAVE.

Todas las actualizaciones (UPDATE, INSERT, DELETE) se realizan sobre el MASTER

Todas las consultas pueden derivarse a múltiples SLAVE

47


Replicación

Mejoramos la robustez porque siempre tenemos una copia actualizada que podemos usar de backup

La velocidad la mejoramos al distribuir nuestra carga de consultas sobre diferentes réplicas del servidor

El MASTER genera un diario binario (binary log)

Los SLAVE consultan el diario para sincronizarse con el servidor

Documents

1 Administración de Bases de Datos Procesamiento y optimización de consultas Objetivos Comprender las tareas de procesamiento y optimización de consultas