2 Ejercicios Corregidos Operadores Relacionales

Pregunta 1          

Con base en los algoritmos vistos en clase, encuentre las fórmulas de costo así como las condiciones límite en la memoria (asumiendo que M no incluye 2 o 3 buffers para E/S).

SMJ

• M> |R|+|S| : Leer R, ordenar R en la memoria según el atributo de unión, lo mismo para S en la memoria, fusionar páginas ordenadas en la memoria. Por lo tanto tenemos |R|+|S| discos de entrada y salida para leer las 2 relaciones. (Nota: la redacción del resultado nunca está incluida en los costes de los operadores).
• |R|+|S| > M > sqr(|R|+|S|): Las dos relaciones no se mantienen en la memoria. El algoritmo entonces es el siguiente. Lea R en la memoria en paquetes de M páginas y ordene el paquete en la memoria según el atributo de unión. Este paquete se escribe en disco (llamado cubo en inglés). El proceso se repite |R|/M veces hasta que todo R se haya consumido y ordenado. 

Obtenemos |R|/M paquetes de tuplas ordenadas de R. El número de entradas y salidas es, por tanto, aquí 2|R|, para leer R y escribir los paquetes ordenados de R. El mismo proceso se aplica a S, correspondiente a 2|S| entradas salidas. Luego obtenemos |R|/M+|S|/M paquetes de tamaño M. Luego debemos unir las tuplas. Para ello realizamos la fase de fusión. Necesitamos al menos una página de memoria por paquete. Luego se recupera en la memoria la primera página de cada paquete. En el resultado se producen tuplas de unión. 

Cuando sabemos que una página de un paquete contiene tuplas que ya no se pueden unir, la reemplazamos con la siguiente página del paquete del que proviene. Así, se lee cada página de cada paquete, generando |R|+|S| entradas salidas. La cantidad de depósitos no puede exceder M si queremos poder fusionarnos. La memoria necesaria para realizar este procesamiento es de al menos una página por paquete. Entonces es necesario que M > |R|/M+|S|/M de ahí el resultado de la tabla.

GHJ:

• M> |R|+|S| : Leer R en la memoria, aplicar hash a R, leer y aplicar hash a S en la memoria, unir los paquetes hash correspondientes en la memoria. Por lo tanto tenemos |R|+|S| salidas de entrada.
• M> sqr(|R|): La relación R no se mantiene en la memoria. El algoritmo entonces es el siguiente. Leer R en la memoria en paquetes de M y fabricar N paquetes de tuplas de R con hash en el atributo de unión (N es el número de valores hash producidos por la función hash), hasta haber consumido todo R.

La cantidad de depósitos de R no puede exceder M para tener al menos una página de memoria para cada entrada en la tabla hash. Por tanto, el número de entradas y salidas es 2|R|. El mismo proceso se aplica a S, generando 2|S| entradas salidas. Para unir las tuplas, debemos leer un paquete hash completo de R en la memoria y pasar página por página el paquete hash correspondiente de S. Para conservarlo en la memoria, el paquete hash de R debe ser menor que M. Tenemos más M paquetes y, en promedio, |R|/M páginas por paquete. La memoria necesaria para realizar este procesamiento es, por tanto, |R|/M < M, de ahí el resultado de la tabla.

Pregunta 2          

Proponer una estrategia de ejecución para SMJ y GHJ cuando la memoria es menor que sqr(|R|+|S|) (SMJ) o sqr(|R|) (GHJ)

SMJ: podemos hacer varios niveles de corridas. Luego aumentamos el tamaño de los paquetes y reducimos su número. Esto se puede hacer fusionando varios paquetes de R (hacemos paquetes ordenados más grandes con las tuplas de los paquetes iniciales) y de S mediante clasificación. Luego obtenemos 3|R|+3|S| E/S (1 nivel de ejecución), 5R|+5|S| (2 niveles de carreras), 7|R|+7|S| (3 niveles de carreras).

GHJ: Hacemos un hash más fino (otra función de hash) los paquetes R cuyo tamaño es mayor que el de la memoria. (Pb: ¿deberíamos repetir también S?)

Pregunta 3          

Suponiendo que leer n páginas consecutivas del disco lleva 10 ms + n*0,2 ms, compare Block Nested Loop Join (BNLJ), GHJ y SMJ. Para el SMJ y el GHJ, nos situamos en el caso de que tengamos una memoria menor que |R|+|S| y que |R| respectivamente.

BNLJ: lee un bloque de R y luego pasa todo S página por página. Haz esto R/M veces. Obtenemos por tanto: |R|/M (10 + M x 0,2ms) + |R|/M (10ms + |S| x 0,2ms)

SMJ: Obtenemos 2 x |R|/M (10ms + M x 0,2ms) + 2 x |S|/M (10ms + M x 0,2ms) + (|R|+|S|) (10ms + 0,2ms ) = lectura/escritura secuencial por bloques de R y S + lectura aleatoria de páginas de R y S

GHJ: Obtenemos 2 x (|R|+|S|) (10ms + 0.2ms) + |R|/M (10ms + M x 0.2ms) + |R|/M (10ms + |S| * M / |R| x 0.2ms) = lectura/escritura aleatoria de páginas de R y S + lectura secuencial de bloques de R y S

Ref: “Buscando la verdad sobre las uniones ad hoc”

Pregunta 4

Basado en el algoritmo Hybrid Hash Join visto en clase, proponga una estrategia de ejecución de hash adaptativa que le permita aprovechar la máxima memoria disponible pero sin saber a priori el tamaño de R (Para simplificar, asumiremos que M > sqr(|R|) y M<|R|). Evalúe el costo de E/S para M = R/2, M = R/3.

Podemos decidir comenzar a aplicar hash a R en la memoria como si todo fuera a ir bien (M > |R|), luego, tan pronto como nos quedemos sin memoria, colocamos ciertos paquetes hash en el disco (comenzando desde el final). Estos valores hash ahora se encontrarán en el mismo paquete. Luego leemos S y lo unimos con los paquetes de R que se encuentran en la memoria. Las tuplas de S que se unen a un paquete de R en el disco se escriben en el disco como un paquete hash. Finalmente volvemos a leer los paquetes R y S en el disco para producir los resultados que faltan.

Con M=|R|/2, escribimos la mitad de |R|. Al final, la mitad de los paquetes hash quedan en la memoria, y en los discos el resto de paquetes que contienen la mitad de las tuplas de R (|R|/2 entradas salidas). Pasamos S contra la tabla hash página por página (|S| entradas y salidas del disco). Producimos los resultados correspondientes a las tuplas de S uniéndolas a los paquetes de R en memoria y escribimos las tuplas de S en el disco (en forma de paquetes hash). correspondiente a paquetes R en el disco.

Esto genera |S|/2 entradas y salidas. Finalmente, releemos los paquetes de R y S en los discos, lo que genera entradas y salidas |R|/2+|S|/2. En total, hay, por tanto, 2 (|R|+|S|) entradas y salidas.

Con M=|R|/3, obtenemos |R| + 2/3 |R| + |S| + 2/3|S| + 2/3 |R| + 2/3|S| = 7/3 (|R|+|S|) entradas salidas.