Download Administración de Bases de Datos WHERE

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
1
Administración de Bases de Datos
Procesamiento y optimización de consultas
 Contenidos
 Procesamiento y optimización de consultas
 Etapas del procesamiento de consultas
 Análisis léxico, sintáctico y validación
 Optimización
 Reglas transformación
 Implementación de operaciones relacionales
2
Administración de Bases de Datos
Procesamiento y optimización de consultas
 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
3
Administración de Bases de Datos
Procesamiento y optimización de consultas
 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
4
Administración de Bases de Datos
Procesamiento y optimización de consultas
 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)
5
Administración de Bases de Datos
Procesamiento y optimización de consultas
 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
6
Administración de Bases de Datos
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
7
Administración de Bases de Datos
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
8
Administración de Bases de Datos
Análisis léxico, sintáctico y validación
Nombres de los empleados que trabajan en el proyecto 2
SELECT nombrep
FROM Empleado E, Trabaja_en T
WHERE E.nss=T.nsse and T.nump>=2;
pnombrep (snump=2 (Empleado
proyección
restricción
nss=nsse
TRABAJA_EN))
fusión
9
Administración de Bases de Datos
Análisis léxico, sintáctico y validación
pnombrep (snump=2 (Empleado
TRABAJA_EN))
nss=nsse
Resultado
Proyectar(E.nombrep)
árbol de consulta (o árbol
sintáctico abstracto) como
representación de una
expresión algebraica
restringir(T.nump=2)
Reunir(E.nss=T.nsse)
EMPLEADO(E)
TRABAJA_EN(T)
10
Administración de Bases de Datos
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
11
Administración de Bases de Datos
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
12
Administración de Bases de Datos
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
13
Administración de Bases de Datos
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, ...
14
Administración de Bases de Datos
Optimización
 El Optimizador tiene un conjunto de técnicas para implementar
cada operación. Por ejemplo, la operación s
 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
15
Administración de Bases de Datos
Optimización
Información
Estadística
(diccionario de datos)
Información sobre la
interdependencia entre las
operaciones de bajo nivel
OPTIMIZADOR
Elección de varias técnicas
candidatas para cada operación
16
Administración de Bases de Datos
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
17
Administración de Bases de Datos
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
coste(plan )  i coste(técn ica i )
Medida en número de accesos a bloque (transferencias de bloques
de memoria a disco)
18
Administración de Bases de Datos
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
19
Administración de Bases de Datos
Reglas generales de transformación

Una secuencia de restricciones sobre una relación A puede
transformarse en una sola restricción
sc1(sc2(A)) = sc1 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)
pp2(pp1(A)) = pp2(A), sii p2  p1

Una restricción de una proyección puede transformarse en una
proyección de una restricción
sc(pp(A)) = pp(sc(A))
Es mejor hacer restricción antes
que proyección pues la restricción
reduce el número de filas a
considerar
20
Administración de Bases de Datos
Reglas generales de transformación

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
sc(R op S) = (sc(R)) op (sc(S)) donde op ={  ,  , - }

La proyección es distributiva respecto a la UNIÓN
pp(R  S) = (pp(R))  (pp(S))
21
Administración de Bases de Datos
Reglas generales de transformación

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
snump=2 (Empleado
EMPLEADO

TRABAJA_EN) =
snump=2 (TRABAJA_EN)
O puede escribirse como (c1 AND c2), y en c1 sólo intervienen
atributos de R1 y en c2 sólo de R2
sc (R1

nss=nsse
nss=nsse
j
R2) = (sc1(R1))
j
(sc2(R2))
Se reduce el número de tuplas a examinar en la siguiente
operación
22
Administración de Bases de Datos
Reglas generales de transformación

Las proyecciones p 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
pP (R1
R
R2) = (pPR1 (R1))
(pPR2 (R2))
R
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
23
Administración de Bases de Datos
Reglas generales de transformación

Conmutatividad
op es conmutativo si A op B = B op A



Asociatividad
op es asociativo si A op (B op C) = (A op B) op C



son conmutativas UNION, INTERSECTION, JOIN
no conmutativas DIFERENCIA
son asociativas UNION, INTERSECTION, JOIN
no asociativas DIFERENCIA
Idempotentes
op es idempotente si A op A = A

son idempotentes DIFERENCIA, UNION, INTERSECTION, JOIN
24
Administración de Bases de Datos
Reglas generales de transformación

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, ...)
25
Administración de Bases de Datos
Reglas generales de transformación

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>b
La 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,f
La 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 AND
Toda expresión condicional puede transformarse en su Forma
Normal Conjuntiva (FNC)
26
Administración de Bases de Datos
Reglas generales de transformación

Una FNC tiene la forma C1 AND C2 AND ... CN donde Ci no
incluye ningún AND
Es 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
27
Administración de Bases de Datos
Reglas heurísticas

Ejecutar las operaciones de restricción s 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 p tan pronto como sea
posible
28
Administración de Bases de Datos
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)
29
Administración de Bases de Datos
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
Administración de Bases de Datos
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)
31
Administración de Bases de Datos
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].k
for(j=1;j<=t;j++)
añadir R[i]+S[j] al resultado
O(m*t*log n) donde suponemos n >> t*log n
32
Administración de Bases de Datos
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
33
Administración de Bases de Datos
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)
34
Administración de Bases de Datos
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)
35
Administración de Bases de Datos
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)
36
Administración de Bases de Datos
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
37
Administración de Bases de Datos
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
38
Administración de Bases de Datos
EXPLAIN

Las tablas aparecen en el orden en que son procesadas
table
et
do
et_1
tt

type
ALL
ALL
ALL
ALL
possible_keys
PRIMARY
PRIMARY
PRIMARY
AssignedPC,
ClientID,
ActualPC
key key_len
NULL NULL
NULL NULL
NULL NULL
NULL NULL
ref
rows Extra
NULL 74
NULL 2135
NULL 74
NULL 3872
74 * 2135 * 74 * 3872 = 45,268,558,720
39
Administración de Bases de Datos
EXPLAIN

Soluciones:
 Añadir índices
 SHOW INDEX FROM table
 Myisamchk –analyse table
 ANALIZE TABLE
 OPTIMIZE TABLE
40
Administración de Bases de Datos
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
41
Administración de Bases de Datos
Otras optimizaciones

DISTINCT

LEFT JOIN, RIGHT JOIN

ORDER BY

LIMIT

INSERT

UPDATE

DELETE
42
Administración de Bases de Datos
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)
43
Administración de Bases de Datos
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
44
Administración de Bases de Datos
Diferentes configuraciones
 Según las distintas cargas esperadas
 my-small.cnf
 my-medium.cnf
 my-large.cnf
 my-huge.cnf
45
Administración de Bases de Datos
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
46
Administración de Bases de Datos
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
47