Optimización de Preguntas

Optimización de preguntas

Optimización: pregunta plan costo ópt.costo = CPU + I/O + COMUNICACIONES

Necesario para responder eficientementePosible con lenguajes no procedurales (ej.

SQL) leng. no procedural: se dice qué se quiere

obtener y no cómo obtenerlo (algoritmo, uso de índices...)

sistemas con lenguajes procedurales: ej. IMS (jerárquico) o CODASYL (en red)

Ejemplo motivador

La optimización es posible y necesariaLas distintas estrategias requieren

costes muy distintoDebe ser un proceso automático

depende del momento concreto en la vida de la BD

es complicado saber qué estrategia es mejor

Nunca se esta seguro (estimaciones)

Etapas en la optimización

Convertir la pregunta en una representación interna (álgebra relacional, árbol sintáctico)

Transformar la pregunta en una forma canónica (reglas sintácticas y semánticas)

Escoger los procedimientos de bajo nivel candidatos (para cada operador) ¿índices? ¿clustering? ¿rango y núm. valores?

Generar los planes y escoger el más barato usar heurísticos para reducir búsqueda

Optimización sintáctica

Entrada: expresión álgebra relacionalSalida: expr. álgebra relacional

equivalente operaciones de idempotencia, propagar ctes. operación selección se baja en el árbol operación proyección se baja en el árbol agrupar selecciones y proyecciones Idea: reducir tamaño de las relaciones a

combinar con la operación join

Optimización semántica

Transformar la pregunta en otra que devuelve las misma tuplas

Utilizar conocimiento semántico de la BD restr. integridad, dependencias funcionales,

claves extranjeras, reglas semánticas En general, la opt. sem. es un proceso caro,

por lo que los SGBD comerciales no la aplican. Se suele basar en técnicas de Int. Artificial.

Optimización física: Selección

Algoritmos Búsqueda lineal Búsqueda binaria Empleo de índices (de distintos tipos)

Selectividad de una condición % de la relación que satisface la condición Ejecutar primero las selecciones de mayor

selectividad

Optimización física: Join

Algoritmos Ciclo anidado (Nested Loops) o fuerza

bruta Sort-Join (Sort Merge) Join con índice en una de las relaciones Join con índice para cada relación Hash-Join

Optimización física: otras op.

Proyecciones: fácil de implementar (hay que recorrer todas las tuplas)

Producto cartesiano: muy costosa Evitarla

Unión, Intersección, Diferencia Primero se ordenan las dos relaciones

Generar los planes y escoger el más barato

Planes para responder a la pregunta, y su costoCada plan se construye combinando el conjunto

de procedimientos candidatos posibles. Calcular el costo es complicado hay que estimar

tamaños de resultados intermedios (estadísticas de la BD, en el catálogo). Calcular el orden óptimo de ejecución de joins

• N! posibilidades de ejecutar un join entre N relaciones

Evitar resultados intermedios (subir selecciones)

Usar heurísticos para reducir la búsqueda

Optimización del costo:CPU + I/O + COM

BD centralizadas generalmente se tiene en cuenta sólo costo I/O

BD distribuidas en Redes Area Amplia (WAN) generalmente, sólo costo COM.

BD distribuidas en Redes de Area Local (LAN) generalmente, costos I/O y COM.

BD en servidores paralelos influyen los tres: CPU, I/O y COM.

Optimización en Oracle

Optimización basada en reglas o basada en costes (seleccionado por el usuario)

EXPLAIN PLAN: ver como se ejecutará una sentencia SQL

No hay optimización semántica hasta Oracle 8, incluido

Se puede influir en el uso o no de índices (no recomendado)

Conclusiones

Los SGBD realizan optimización de preguntas• son inútiles algunas reformulaciones de preguntas

Algunas optimizaciones (todavía) no son realizadas por los SGBD (ej. optimización semántica)

• hay que reformular algunas preguntas

El proceso de optimización de preguntas es complejo y cada SGBD lo hace distinto.

• hay que consultar el manual del SGBD concreto.

Es necesario conocer cómo se procesan las preguntas para realizar el DISEÑO FÍSICO.

• cuándo es útil usar índices o hash o no utilizarlos.• saber que el join es costoso --> reducir número de joins.