Download optimizacion
Transcript
Optimización de Preguntas Optimización de preguntas Optimización: pregunta plan costo ópt. costo = CPU + I/O + COMUNICACIONES Necesario para responder eficientemente Posible 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 necesaria Las distintas estrategias requieren costes muy distinto Debe 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 relacional Salida: 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 costo Cada 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.