2 Ejercicios Corregidos Operadores Relacionales

Esta página presenta casos de uso para operadores relacionales mediante ejercicios corregidos.

operadores relacionales

Recordatorio del curso

Queremos unir dos relaciones R y S (sin clasificar). R es menor que S

|R| = Número de páginas en el disco de R, ||R|| = Número de tuplas de R, M = Número de páginas de memoria disponibles (asumimos que se asignan 3 páginas de memoria para E/S

Algoritmo de unión de clasificación y fusión (SMJ)

Condición en la memoria

costo de E/S

METRO > |R|+|S|

Costo = |R|+|S|

|R|+|S| > M > cuadrado(|R|+|S|)

Costo = 3|R|+3|S|

Algoritmo de unión hash de gracia (GHJ)

Condición en la memoria

costo de E/S

METRO > |R|

Costo = |R|+|S|

M > cuadrado(|R|)

Costo = 3|R|+3|S|

Ejercicio 1

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).

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)

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.

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.

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.

operadores relacionales

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).

operadores relacionales

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.

Ejercicio 2

Estamos ahora en un caso extremo en el que la memoria disponible es de sólo unos pocos bytes; por otro lado, los datos se almacenan en una memoria electrónica, por lo que el coste de lectura es similar al de la lectura desde la memoria.

Pregunta 5

Encontrar algoritmos y expresarlos con el formalismo del modelo iterador para realizar las siguientes operaciones: Selección, proyección, unión.

Especifique la memoria mínima requerida.

Pregunta 6

¿Podemos realizar cálculos de clasificación o agregados? Si es así, ¿cómo?

Pregunta 7

Ahora tienes unos pocos KB de RAM. ¿Cómo optimizar las uniones?

Pregunta 8

¿Y clasificar o calcular agregados?

Estamos ahora en un caso extremo en el que la memoria disponible es de sólo unos pocos bytes; por otro lado, los datos se almacenan en una memoria electrónica, por lo que el coste de lectura es similar al de la lectura desde la memoria.

Pregunta 5

Encontrar algoritmos y expresarlos con el formalismo del modelo iterador para realizar las siguientes operaciones: Selección, proyección, unión.

Especifique la memoria mínima requerida.

Los operadores de selección y proyección trabajan tupla a tupla, por lo que no consumen RAM. La unión se puede realizar mediante un bucle anidado, no hay consumo de memoria (o 1 puntero por relación).

Pregunta 6

¿Podemos realizar cálculos de clasificación o agregados? Si es así, ¿cómo?

Por ejemplo, podemos escanear completamente la entrada del operador para encontrar la tupla que comparte la clave de clasificación más pequeña, luego rehacer un escaneo completo de la entrada para entregar todas las tuplas que comparten esta clave, y así sucesivamente hasta haber producido todas las tuplas. Por tanto, podemos ordenar tuplas de esta manera.

Para calcular agregados, procedemos de la misma manera calculando el agregado de las tuplas que comparten la clave.

Pregunta 7

Ahora tienes unos pocos KB de RAM. ¿Cómo optimizar las uniones?

Hacemos un bloque de bucle anidado...

Pregunta 8

¿Y clasificar o calcular agregados?

Cada vez que pasamos datos, almacenamos en búfer varios valores de clasificación o agregados. Cada pasada permite así procesar varias claves de clasificación o de agregación.

Compartir, repartir