jijijij

Procesamiento y optimización de consultas

Tema 7. Optimización (*)
Procesamiento y optimización de consultas

Proceso de una consulta

Elmasri/Navathe 02

Consulta (SQL)

• Introducción
• Traducción de consultas SQL a álgebra relacional (18.1)
• Optimización sintáctica: Heurística (18.3)
– Árbol de consulta
– Reglas de transformación
– Algoritmo de optimización
• Optimizaciónfísica: Estimación de coste (18.2, 18.4)
– Algoritmos básicos y clasificación externa
– Componentes del coste. Información del catálogo
– Algoritmos y funciones de coste en seleccionar (σ)

Análisis léxico y sintáctico
Validación

Compilador

Forma intermedia

Árbol o grafo
de consulta

Optimizador
Optimizador
Plan de ejecución
Generador de Código
Código
Procesador de BDTiempo de ejecución

Resultado

– Algoritmos y funciones de coste en reunión (|X|, *)
– Orden de ejecución de las reuniones
– Ejemplos de optimización por estimación de coste
– Otros algoritmos: π , ∪, ∩, –, X, agregación, reunión

Modo compilado
o interpretado

Si hay error de ejecución
presenta el mensaje
correspondiente

•

No toma la estrategia óptima:
– Una razonablementeeficiente
– Elegir la óptima puede llevar mucho tiempo

•

externa, combinación de operaciones por segmentación

Consulta en lenguaje alto nivel (SQL): declarativa
– Especifica qué se desea obtener
– No detalla tanto cómo debe obtenerse
– Se puede plantear optimización automática

•Optimización en ORACLE (18.5)
• Optimización semántica (18.6)

(*) Se han fusionado los puntos 18.2 y18.4 para evitar
repetir conceptos.
© A. Jaime 2005

DBD Tema 7

© A. Jaime 2005

1

•

SGBD: cuenta con varios algoritmos para operaciones
relacionales como selección (σ) y reunión ( |X| )
Optimizador considera los algoritmos :
– Disponibles en el SGBD
– Aplicables al diseño físico de los ficheros que
participan en la consulta

•

Cada consulta SQL se divide en bloques deconsulta:
Unidades de traducción al álgebra relacional
bloque de
consulta 1
SELECT APELLIDO, NOMBRE

•

2

Traducción de consultas al álgebra
relacional

Optimización
•

DBD Tema 7

FROM EMPLEADO
WHERE SALARIO > ( SELECT MAX(SALARIO)
FROM EMPLEADO

Traducción
Traducción
al álgebra
al álgebra

WHERE NUMD=5);

πAPELLIDO, NOMBRE(σSALARIO >C(EMPLEADO))
Elegir plan de consultaTraducción
Traducción
al álgebra
al álgebra

Técnicas de optimización:
– Física o estimación de coste:
• Elegir el plan de menor coste estimado
– Sintáctica o reglas heurísticas
• Ordenar las operaciones
• Utiliza un árbol o un grafo de consultas
– Semántica
– Generalmente se combinan las dos primeras técnicas

bloque de
consulta 2

Consulta
anidada.
Se estudian en laasignatura DBD

ℑMAX SALARIO(σNUMD=5(EMPLEADO))
Elegir plan de consulta

Se evalúa sólo una vez.
Se evalúa sólo una vez.
El resultado se trata como
El resultado se trata como
una constante (>C)
una constante (>C)

© A. Jaime 2005

DBD Tema 7

3

© A. Jaime 2005

DBD Tema 7

4

Optimización sintáctica: Heurística

Árbol de consulta

Objetivo: reducir el tamaño de lastablas intermedias

•

•
•

Optimizador:

En forma de
Generada por
árbol o de grafo el analizador
sintáctico
– Reglas heurísticas:
modifican la representación interna de la consulta

SELECTP.NÚMEROP, P.NÚMD, E.APELLIDO,
E.DIRECCIÓN, E.FECHA_NCTO
FROM PROYECTO AS P, DEPARTAMENTO AS D,
EMPLEADO AS E
WHERE P.NÚMD=D.NÚMEROD AND
D.NSS_JEFE=E.NSS AND
P.LOCALIZACIÓN=‘Stafford’

–Después se genera un plan de ejecución:
• Para ejecutar grupos de operaciones
• Según los caminos de acceso que tengan los
ficheros

π

Índices, direccionamiento calculado
•

Representa una expresión del álgebra relacional
Una consulta se puede representar por varios
árboles distintos

P.NÚMEROP, P.NÚMD,
E.APELLIDO, E.DIRECCIÓN,
E.FECHA_NCTO

Regla principal:
– Primero ejecutar...