Apuntes de CI-5313 Base de Datos III (USB-VE)/Optimización de consultas

Optimización de Consultas basadas en Costos

$T'=\sigma _{cond}(T)$

Estimación del tamaño de T'

$T'=FS(cond)+|T|$

Asumiendo:

• Los valores de los atributos en las condiciones en cond se distribuyen uniformemente.
• Las condiciones en cond son independientes.

Estimación del tamaño Join's

A $\bowtie$_cond B = | A | * | B | * FS(c)

Proyección (Estimación del tamaño del proyecto)

$CURSAR(CodMat,CarnetmTrimestre,Nota)$

$\pi \ _{carnet,trimestre}(CURSAR)$

¿Cuantas materias puedo cursar un estudiante en un trimestre? Eso lo necesito para predecir el tamaño de la proyección. El manejador no elimina duplicados.

Factores de Reducción de la Proyección sin considerar la eliminación de duplicados (FR).

Tamaño -----> numAtributos(todos)

X --------------> numAtributos

---

Estimar el costo de un plan físico

$n!m_{n-1}$ → olvidando las proyecciones y selecciones. No es posible realizar una exploración exhaustiva del espacio.

Problema: Identifica un plan de ejecución dada una consulta q y el conjunto de operadores físicos.

Queremos identificar un plan de ejecución para q, tal que el costo(q) sea el menor posible.

• Solución "buena": es una solución que se aleja del peor caso que es la solución del árbol canónico.
• Solucion "ingenua": (Algoritmo greedy) \n Construir un plan de ejecución por etapas siguiendo una estrategia "Greedy"

Entrada: $ConjuntoRelaciones\{T_{i}/T_{i}esunatablaenq\}$ ConsultaParcial = la tabla del conjunto de relaciones con las proyecciones y relaciones que aparecen en la consulta y cuyo tamaño de resultado sea el más pequeño.

SELECT attList FROM T1, ... , Tn WHERE cond

Mientras existan tablas en ConjuntoRelaciones asignar a ConsultaParcial la consulta formada por σ_c(ConsultaParcial$\bowtie$ T_i) donde T_i $\in$ ConjuntoRelaciones

$\pi _{A}(\sigma _{c}(ConsultaParcial\bowtie T_{i}))$ es la solución con menor tamaño estimado

Costo de la solución ingenua: $T_{1},...,T_{n}$ O(n)

Puede ser muy malo en función de la salida pero bueno en función del costo.