Optimizacion

Procesamiento y Optimización
de Consultas
[EN 18]
[Ramakrishnan - Gehrke 12]

CSI-INCO

Fundamentos de Bases de Datos

1

¿Cómo se resuelven las consultas?
DATOS DE RESPUESTA
SELECT *
FROM
empleados

Representación
interna de la

A partir de la
representación
interna calcula
un plan de
acceso para
resolver esa
consulta

Genera el código
necesario para el
acceso a losdatos
de acuerdo al
plan generado
por el
optimizador

Ejecuta el código
que recibe desde
el generador.

consulta

datos
Plan de
acceso

CSI-INCO

código

Fundamentos de Bases de Datos

2

Estrategias usuales de los
optimizadores
●

Proceso detallado de Optimización.

●

Optimización Heurística
–

●

Basada en equivalencia de las expresión del álgebra yciertas
estrategias básicas para limitar el tamaño de los resultados

Optimización por Costos
–

Basada en estimaciones y datos del catálogo que permiten
selecciónar un mejor plan de acceso.

CSI-INCO

Fundamentos de Bases de Datos

3

Proceso de Optimización
Q
S FW …
Árbol sintáctico

π
σ

π
X

Plan físico a
ejecutar, (el de
menor costo)

π
X

σS σS

4

1

RPlanes físicos

R

Planes lógicos
con tamaños

X
RS
Árbol canónico

2
CSI-INCO

3
Fundamentos de Bases de Datos

4

Ejemplo de Optimización (1)
Resolvamos esta consulta sobre las tablas:

●

–

empleados(nombre,edad,salario,depto)

–

select e.nombre, d.piso
from departamentos d,
empleados e
where e.depto = d.nroD
and e.salario > 30000departamentos(nroD,nombreD,piso,gerente)

Πnombre,piso(σSalario > 30000(empleados * departamentos))
Πnombre,piso

1

Se escribe la
consulta en
álgebra relacional

σ (e.depto=d.nroD)∧(e.salario > 30000)

1.1

Se genera el
árbol canónico
1.2

CSI-INCO

X
departamentos

empleados

Fundamentos de Bases de Datos

5

Ejemplo de Optimización (2)
●

A partir del árbol canónico se generan planeslógicos.

●

Generador de
planes lógicos

Se usan heurísticas y se agregan datos de tamaño.

2

Πnombre,piso
10

σ (e.depto=d.nroD)∧(e.salario > 30000)
10

σ (salario > 30000)

X
departamentos

100

100000

empleados

Parámetro

Valor

Tamaño de EMPLEADOS (tuplas)

100.000

Tamaño de DEPARTAMENTOS (tuplas)

100

Selectividad de σ(salario>3000)

1/10.000CSI-INCO

Fundamentos de Bases de Datos

6

Ejemplo de Optimización (3)
Para cada plan lógico

●

●

Se consideran diferentes implementaciones

3
Parámetro

Valor

Tamaño de EMPLEADOS (tuplas)

100.000

Tamaño de DEPARTAMENTOS (tuplas)

100

Selectividad de σ(salario>3000)

1/10.000

Cantidad de bloques para EMPLEADOS

2000

Cantidad de bloques para DEPTOS.

10Índices sobre EMPLEADOS

B+ en salario

Índices sobre DEPARTAMENTOS

10

10

Hash en nroD

1000
10

100

10

σ (salario > 30000)
10

100.000

10

100

Operación

implementaciones

σ

Busqueda
Binaria

Usar Indice

|X|

100000

Busqueda
lineal
Loop anidado

Loop único

SortMerge

100

100.000

CSI-INCO

Fundamentos de Bases de Datos

7Ejemplo de Optimización (4)
●

Calculo los costos (cant. de accesos a disco)
Operador

Implementación

Costo

σc(R)

4

Busqueda Lineal

bR

Busqueda Binaria Log2 bR + Sc
Uso de Indice
Loop Anidado

R|> 30000)
σ (salario > 30000)

X
departamentos

empleados

1

3

10
1000

σ (salario > 30000)

2,4
10

100

X
CSI-INCO

σ (salario > 30000)
100000Fundamentos de Bases de Datos

14

Proceso de Optimización
Q
S FW …
Árbol sintáctico

π
σ

π
X

Plan físico a
ejecutar, (el de
menor costo)

π
X

σS σS

4

1

R

Planes físicos

R

Planes lógicos
con tamaños

X
RS
Árbol canónico

2
CSI-INCO

3
Fundamentos de Bases de Datos

15

Optimización por Costos
●

Plan Físico
–

–

Como se pueden...