Costos de Operadores

A partir de la información de catálogo, podemos estimar el costo de las distintas operaciones, según la estructura del disco.

Analizaremos los costos en función de cuantos accesos a discos se requiere

Selección

Partimos de una selección básica del tipo ${\sigma }_{\text{cond}}(R)$, en donde $\text{cond}$ es una condición atómica. Analizaremos distintas situaciones para la comparación por igual.

Búsqueda lineal

Si no tenemos índices, entonces debemos recorrer el disco en busca de los registros que cumplen con la condición. Consiste en explorar cada registro, analizando si se verifica la condición.

undefined

\text{cost}(\sigma) = \text{Height}(I(A_i, R)) + 1

undefined

\text{cost}(\sigma) \approx \text{Height}(I(A_i, R)) + \Big\lceil\frac{B(R)}{V(A_i, R)}\Big\rceil

undefined

\text{cost}(\sigma) \approx \text{Height}(I(A_i, R)) + \Big\lceil\frac{n(R)}{V(A_i, R)}\Big\rceil

undefined

cost(\pi) = B(R)

### Sin superclave Si $X$ no es superclave, entonces debemos eliminar duplicados. Llamaremos $\hat\pi_X(R)$ a la proyección de multiconjuntos. Podemos ordenar la tabla en memoria si la tabla entra en memoria, en caso contrario el costo usando un ordenamiento externo será:

\text{cost}(\pi) = \text{cost}(\text{ord}M(R)) = 2B(R) \cdot [\log{M-1}(B(R))] - B(R)

$$Tambi\acute{e}npodemosutilizarunaestructurade\ast hash\ast .Sinoentraenmemoria,elcostousandoun\ast hashing\ast externoser\acute{a}de:$$

\text{cost}(\pi) = B(R) + 2\cdot B(\hat\pi_X(R))

Si la consulta de SQL no incluye `DISTINCT`, entonces el resultado es un multiconjunto y el costo es siempre $B(R)$. ## Unión e Intersección Primero, ordenamos las tablas $R$ y $S$. Si alguno no entra en memoria, utilizamos un *sort* externo. Asumimos que no se devuelven repetidos (comportamiento por defecto de SQL). Se puede modificar sencillamente en caso de querer repetidos. Procesaremos ambas tablas ordenadas haciendo un *merge* que avanza por las filas $r_i$ y $s_i$ ordenadas de cada tabla, el costo es:

\text{cost}(\cup | \cap) = \text{cost}(\text{ord}_M(R)) + \text{cost}(\text{ord}_M(S)) + 2B(R) + 2B(S)

undefined

\text{cost}(R*S) = \min(B(R) + B(R)\cdot B(S), B(S) + B(S) \cdot B(R))

$$Estaestimaci\acute{o}nesunpeorcaso,suponiendoquesolopodemostenerunbloquedecadatablasimult\acute{a}neamenteenmemoria.Sipudi\acute{e}ramoscargarunadelastablascompletaenmemoria,sobrar\acute{a}unbloque,tendr\acute{ı}amoselmejorcaso:$$

\text{cost}(R*S) = B(R) + B(S)

Genéricamente, podemos calcular el costo, siendo $M$ la cantidad de memoria disponible (en bloques). Notemos que debemos guardar un bloque para el desfile, y otro bloque para los resultados.

B(R) + \lceil B(R)/(M-2)\rceil \cdot B(S)

undefined

\text{cost}(R*S) = B(S) + n(S)\cdot(\text{Height}(I(A_i, R)) + 1)

$$Siel\acute{ı}ndiceesdeordenamiento,entonceselcostoser\acute{a}:$$

\text{cost}(R*S) = B(S) + n(S)\cdot(\text{Height}(I(A_i, R)) + \Big\lceil\frac{B(R)}{V(A_i, R)}\Big\rceil

)

$$Siel\acute{ı}ndiceessecundario,entonceselcostoser\acute{a}:$$

\text{cost}(R*S) = B(S) + n(S)\cdot(\text{Height}(I(A_i, R)) + \Big\lceil\frac{n(R)}{V(A_i, R)}\Big\rceil

)

Si existe la consulta simétrica, entonces podremos calcular ambas estimaciones y elegir la más eficiente. > [!note] Nota > > En caso donde las tablas son chicas, no siempre es mas efectivo este método ### Método de sort-merge Este método consiste en ordenar los archivos de cada tabla por el atributo de junta. Si entran en memoria, el ordenamiento puede hacerse con *quicksort* y el costo de acceso a disco es solo $B(R) + B(S)$. Si los archivos no caben en memoria, debe utilizarse un algoritmo de *sort* externo. El costo de ordenar $R$ y volverlo a guardar en disco es de aproximadamente $2B(R) \cdot \lceil\log_{M-1}(B(R))\rceil$ Una vez ordenados, se hace un *merge* de ambos archivos que solo selecciona aquellos pares de tuplas en que coinciden los atributos de junta. El *merge* recorre una única vez cada archivo, con un costo total de $B(R) + B(S)$. El costo total entonces es:

\text{cost}(R*S) = B(R) + B(S) + 2B(R) \cdot \lceil\log_{M-1}(B(R))\rceil + 2B(S) \cdot \lceil\log_{M-1}(B(S))\rceil

undefined

\text{cost}(R*S) = 3 \cdot (B(R) + B(S))

### Pipelining En muchos casos, el resultado de un operador puede ser procesado por el operador siguiente en forma parcial (es decir, sin necesidad de que el operador anterior haya terminado de generar todas las tuplas) Esta estrategia se denomina *pipelining*, y los gestores suelen utilizarla en los planes de ejecución siempre que sea posible. Al calcular el costo de dos operaciones anidadas $O_2(O_1(R))$, debemos considerar que en el caso de utilizar pipelining no será necesario tener todos los bloques de la salida de $O_1$ para comenzar a calcular $O_2$. En particular, no tendremos que materializar toda la salida de $O_1$ por falta de espacio en memoria.