Notas Optimizacion (Bases de Datos)

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia

Notación[editar]

= memoria asignada para páginas.
Siendo R una relación:

  • : # bloques que ocupa R
  • : factor de bloqueo = Cuantas de tuplas por bloque de R
  • : longuitud de una tupla de R
  • : # total de tuplas de la relación R
  • : Imagen del atributo de A en R: Denota la # de valores distintos de ese atributo en la relacion.
  • : altura del arbol de busqueda
  • : Cantidad de entradas por bloque del índice I (factor de bloqueo del índice)
  • : Cantidad de bloques que ocupa el índice i para nodos hoja (el índice debe ser árbol B+). Si no se tiene el dato y se desea calcularlo, se utilizará el criterio de peor caso (cada nodo hoja estará completo en su mínimo, es decir, d/2, donde d es el orden del árbol)
  • : Cantidad máxima de bloques que ocupa un bucket del índice i (el índice debe ser basado en hashing)
  • : cantidad de buckets del índice I (el índice debe ser basado en hashing)

Organizacion Archivos/Indices[editar]

Producto Cartesiano: con

  • (), (sino)

Junta por igualdad: R.A = S.A

  • (B+ clustered), (B+ unclustered)

Notacion:

  • B' = # bloques q/ debo verificar pues cumplen con la condición
  • BH = # bloques q/ debo verificar pues cumplen con la condición
  • T' = # tuplas q/ debo verificar pues cumplen con la condición
  • BB = # bloques por bucket

Costo de tipos de acceso.jpg

Evaluación de operaciones relacionales[editar]

COSTOS
Proyeccion Seleccion Nat.Join
Cant.Tuplas

TR

  • [A=a]: TR/IR,A
  • [A=a AND B=b]: TR/[IR,A*IR,B]
  • [A>a]: dist(a, Amax) / dist(Amin, Amax), [dist n/ap]: 1/2
  • [a1<A<a2]: dist(a1,a2) / dist(Amin,Amax), [dist n/ap]: 1/2
  • [A IN {a1…an} ]: n/IR,A
  • [A=a OR B=b]: (TR/IR,A)+(TR/IR,B)+(TR/(IR,A*IR,B))
  • [caso general]: sel(p) * TR

Long.Tuplas
  • long atr conocida: ∑{Ai in l} (LAi)
  • sino: LR * #atrs R / #atrs l

LR

LR+LS-"long.campos comunes"

Costo Input
  • L.ARCH:
  • L.IB+:
  • L.IHASH:
  • L.ARCH:
  • B.ARCH ORD: (res queda ordenado)
  • IB+C: (res queda ordenado)
  • IB+U: (res queda ordenado)
  • IHASH:
  • BNLJ: .
  • INLJ: "Buscar p/ tupla Index Entries en S" + "Buscar valores apuntados por Index Entries"
    • IB+C:
    • IB+U:
    • IHASH:
  • SMJ: Ordenar = Merge =
Costo Output BQ BQ BQ

Pipeline vs Materializacion:
Pipeline segun combinación de operaciones.jpg

Plan de Ejecución[editar]

Pasos:

  1. Consulta SQL
  2. Árbol Canónico
  3. Árboles Optimizados
  4. Métodos de resolución de junta
  5. Caminos de acceso (Filescan, Index, etc...)
  6. Materializar / Pipeline

Propiedades Algebraicas para la Optimización de Consultas[editar]

Propiedades para Optimizaciones Algebraicas.jpg

Heuristicas de Optimización de Consultas[editar]

A continuación enumeramos algunas heurísticas aplicables:

  • a) Considerar sólo árboles sesgados a izquierda: Al analizar los posibles árboles candidatos, reducir el espacio de búsqueda considerando sólo árboles sesgados a izquierda, es decir, árboles donde los sucesores derechos de cualquier nodo sean hojas.
  • b) Descomponer las selecciones conjuntivas en una secuencia de selecciones simples formadas por cada uno de los términos de la selección original.
  • c) Llevar las selecciones lo más cercano posible a las hojas del árbol, de manera de lograr la ejecución temprana reduciendo así el número de tuplas que se propagan hacia niveles superiores.
  • d) Reemplazar los productos cartesianos seguidos de selecciones por joins. Evitar en la medida de lo posible los productos cartesianos. Si se tiene un producto cartesiano seguido de una selección con un predicado p sobre atributos que determinan un join sobre ese predicado p, se descarta el árbol con las dos operaciones por separado. De esta manera se evita propagar resultados intermedios muy voluminosos.
  • e) Descomponer las listas de atributos de las proyecciones y llevarlas lo más cercano posible a las hojas del árbol, creando nuevas proyecciones cuando sea posible de manera de no propagar.

Pasos para la optimización de una consulta[editar]

  1. Construir el árbol canónico
  2. Construir árboles equivalentes alternativos, utilizando alguna heurística para que no se sobredimensione innecesariamente el espacio de búsqueda del mejor plan
  3. Para cada árbol construido, hacer tantos planes de ejecución como surjan de las diferentes combinaciones «interesantes» de reemplazar los operadores lógicos por operadores físicos o algoritmos, indicando en qué casos los resultados intermedios son pipelinizados y si algún resultado queda en un orden interesante
  4. Para cada plan concreto de ejecución, evaluar sus costos totales
  5. Elegir el plan que haya resultado con menor costo