métodos para realizar la operación de reunión (join) francisco moreno
TRANSCRIPT
![Page 1: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/1.jpg)
Métodos para realizar la operación de reunión (join)
Francisco Moreno
![Page 2: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/2.jpg)
La operación join
Centro de interés: • Operación join (reunión):
- Métodos (algoritmos) para su ejecución - Evaluación de costo de cada método
![Page 3: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/3.jpg)
La operación join
Relaciones r(A,…) y s(B,…)
Join: r ⋈A=B s
Sean:• Fr = Número de páginas de r
• Fs = Número de páginas de s
• tr = Número de tuplas de r
• ts = Número de tuplas de s
![Page 4: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/4.jpg)
La operación join
Para el ejemplo, se manejarán estos valores:• Fr = 1000
• Fs = 100
• tr = 10000
• ts = 1000
![Page 5: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/5.jpg)
Algoritmos para join
1. Simple Nested Loops (Ciclos Anidados Simple)
FOR EACH t r DO
FOR EACH t’ s DO
IF t.A = t’.B THEN output <t, t’>
![Page 6: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/6.jpg)
Nested Loops
• s se debe recorrer (leer) por cada tupla de r, lo cual resulta en:
tr * Fs (páginas)
• r se recorre una sola vez
Costo Total: Fr + tr * Fs (páginas)
Ej:
Costo = 1000 + 10000 * 100 = 1001000
Fr trFs
![Page 7: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/7.jpg)
Nested Loops
• El orden de las relaciones en los ciclos importa:
Intercambiando r y s:
Costo = 100 + 1000 * 1000 = 1000100
Fs ts Fr
![Page 8: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/8.jpg)
Nested Loops
• Aunque en este ejemplo la diferencia es despreciable, en otros casos la diferencia es significativa
• De todas formas este método no se suele usar ya que se mejora así:
![Page 9: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/9.jpg)
Nested Loops
2. Block Nested Loops (Ciclos Anidados con Bloques)
FOR EACH page pr of r DO
FOR EACH page ps of s DO
output pr ⋈A=B ps
![Page 10: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/10.jpg)
Nested Loops
• En vez de leer s por cada tupla de r, se lee s por cada página de r
• Esto reduce el costo a:
Fr + Fr * Fs (páginas)
Ej: 1000 + 1000 * 100 = 101000
Intercambiando:
100 + 1000 * 100 = 100100
Fr FrFs
Fs FrFs
La diferencia sigue siendo despreciable
![Page 11: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/11.jpg)
Nested Loops
Supóngase que se tiene una memoria de M
páginas• M - 2 páginas se usarán para la relación
del ciclo externo (r)• 1 página se usará para la relación del ciclo
interno (s) • 1 página se usará para generar la salida
![Page 12: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/12.jpg)
Nested Loops
r
s
r ⋈ s1 M-2
⋈
…
Input buffer for r
2
Input buffer for s Output buffer
![Page 13: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/13.jpg)
Nested Loops
• Por lo tanto, la relación s se recorre una vez por cada grupo de (M - 2) páginas de r, es decir, se recorre: Fr / (M - 2) veces.
• Por lo tanto, el costo es:
Fr + Fs * Fr / (M - 2)
Nótese que si Fr (M - 2) entonces el costo
es: Fr + Fs
![Page 14: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/14.jpg)
Nested Loops
• Ej: si M = 102 entonces
Costo = 1000 + 100 * 1000 / (102 - 2) = 2000
• Intercambiando r y s:
Costo = 100 + 1000 * 100 / (102 - 2) = 1100
Aquí la diferencia es casi del 50%, así el orden de
las relaciones importa…
Fr FrFs M - 2
Fs FsFr M - 2
![Page 15: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/15.jpg)
Nested Loops
• Es más “económico” colocar la relación más pequeña en el ciclo externo (s en este caso), es decir, si Fr > Fs, entonces:
Fr + Fs * Fr / (M - 2) > Fs + Fr * Fs / (M - 2)
![Page 16: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/16.jpg)
Nested Loops
3. Index Nested Loops (Ciclos Anidados con Índice)
• Supóngase que s (relación interna) tiene un índice sobre el atributo de join B
• En vez de recorrer toda s en el ciclo interno se puede usar el índice para encontrar las matching tuplas así:
![Page 17: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/17.jpg)
Algoritmo
FOR EACH t r DO {
- Usar el índice sobre B para encontrar
todas las tuplas t’ s tales que t.A = t’.B
- output <t, t’> para cada una de las t’
}
![Page 18: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/18.jpg)
Nested Loops
Para estimar el costo se debe considerar:
• El tipo de índice (B+, hash, etc.)
y• Si el índice es clustered (agrupado) o
unclustered
![Page 19: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/19.jpg)
Índice clustered
Archivo de datos
Entradas del índice
Mecanismo para localizar las entradas del índice
Registros de datos
Archivo del índice
![Page 20: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/20.jpg)
Índice unclustered
Archivo de datos
Entradas del índice
Mecanismo para localizar las entradas del índice
Registros de datos
Archivo del índice
![Page 21: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/21.jpg)
• Si el índice es de tipo B+, el costo promedio para llegar al nodo hoja de la tupla buscada está entre 2 a 4 páginas
• Si el índice es de tipo hash, el costo promedio es 1.2 páginas
Nested Loops
![Page 22: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/22.jpg)
• Si el índice es unclustered el número de lecturas (páginas) requerido para recuperar todas las matching tuplas de s es en el peor de los casos Fs (implicaría leer toda s)
• Por lo tanto, los índices unclustered no son recomendables para este método a menos que B sea una clave candidata en s (en este caso habría una sola matching tupla y se requeriría una sola lectura (página) para recuperarla)
Nested Loops
![Page 23: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/23.jpg)
• Si el índice es clustered, todas las matching tuplas de t estarán en la misma página o en las páginas adyacentes, en promedio, 1 o 2 lecturas (páginas)
• Por lo tanto, en este caso el costo es:
Nested Loops
![Page 24: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/24.jpg)
Nested Loops
Fr + ( + 1) * tr
• Donde es el costo promedio de localizar con el índice el nodo hoja del arbol B+ (o el bucket correspondiente si el índice es hash)
• El 1 adicional corresponde a la lectura de la página de las matching tuplas
![Page 25: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/25.jpg)
• Si el índice es unclustered entonces el costo es:
Fr + ( + ) * tr
• Donde es el número de páginas que hay que leer para recuperar las matching tuplas de t
Nested Loops
![Page 26: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/26.jpg)
Nested Loops
• Ej: Supóngase = 2, un índice B+ clustered sobre el atributo B de s, r externa y s interna, entonces:
1000 + (2 + 1) * 10000 = 31000
• Intercambiando r y s y suponiendo un índice B+ clustered sobre el atributo A de r:
100 + (2 + 1) * 1000 = 3100
Fr tr
Fs ts
![Page 27: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/27.jpg)
Nested Loops
• En este ejemplo, este método “pierde” con el Block Nested, pero si la relación interna es de gran tamaño, el Index Nested no aumenta demasiado mientras que el Block Nested si…veamos:
• Si Fs = 10000, ts = 100000 entonces:
![Page 28: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/28.jpg)
Nested Loops
• El Block Nested (r externa, s interna y M = 102):
1000 + 10000 * 1000/(102-2) = 101000
• El Index Nested (r externa, s interna, índice clustered sobre B en s, = 2):
1000 + (2 + 1) * 10000 = 31000
Fr FrFs M - 2
Fr tr
![Page 29: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/29.jpg)
Nested Loops
• Nótese que para una relación s muy grande, crece…pero poco
• El Index Nested suele trabajar “bien” con relaciones de gran tamaño, con la relación interna: a) más grande que la externa y b) con índice clustered sobre el atributo de join
![Page 30: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/30.jpg)
Sort Merge Join
4. Sort Merge Join (Reunión con Ordenamiento y Mezcla)
Se hace en dos etapas:
i. Se ordenan las relaciones por los atributos de join
ii. Luego se hace un proceso de mezcla tal y como lo muestra el algoritmo:
![Page 31: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/31.jpg)
Sort Merge JoinProceso de Mezcla
Las relaciones ya vienen ordenadas por los atributos de join
Input: relación r ordenada por el atributo A
relation s ordenada por el atributo B
Output: r ⋈A=B s
Result := {} //Se inicializa el resultado
tr := getFirst(r) //Primera tupla de r
ts := getFirst(s) //Primera tupla de s
while !eof(r) AND !eof(s) do {
while !eof(r) AND tr.A < ts.B do
tr := getNext(r) //Obtener la próxima tupla de r while !eof(s) AND tr.A > ts.B do ts := getNext(s) //Obtener la próxima tupla de s if tr.A = ts.B = c then { //Para alguna constante c Result := (A=c(r) x B=c(s)) U Result; tr := próxima tupla t r tal que t.A > c }}Return Result
![Page 32: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/32.jpg)
Sort Merge Join
• Costo total:
Costo del ordenamiento de cada relación +
Costo de la mezcla
El costo de la mezcla es: Fr + Fs
Ahora se debe obtener el costo de ordenar
una relación:
![Page 33: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/33.jpg)
Sort Merge Join
Costo de ordenar una relación:Ordenar una relación en una BD consta a su vez de dos fases:- Partial sorting (ordenamiento parcial)- Mezcla (K-way merge)*
* No confundir con la mezcla del Sort Merge, son dos procesos distintos…
![Page 34: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/34.jpg)
Sort Merge Join
- Costo del ordenamiento parcial:• Supóngase una memoria de M páginas y
una relación de F páginas (F es usualmente más grande que M, es decir, F>>M)
• Se leen, ordenan y escriben todas las páginas de la relación, tal y como lo muestra el siguiente algoritmo:
![Page 35: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/35.jpg)
Sort Merge Join
Algoritmo ordenamiento parcial:
DO{
1. Leer M páginas desde disco a la memoria principal
2. Ordenarlas en memoria con uno de los métodos conocidos (suponer que existe memoria adicional suficiente para llevar a cabo este proceso, aparte de la memoria para las M páginas)
3. Escribir el resultado ordenado en un nuevo archivo
}UNTIL(Fin de archivo)
![Page 36: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/36.jpg)
Sort Merge Join
• Por lo tanto, el costo del ordenamiento parcial es:
F(lectura) + F(escritura) = 2F (páginas)• N = Número de “runs” generadas:
N = F/M
Ej: Si M = 4 y F = 10 entonces 10/4 = 3
• Nótese que el tamaño de cada run es M páginas*
* Excepto una de ellas cuando la división no es exacta…
![Page 37: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/37.jpg)
Sort Merge Join
13 3 2 6 1 10 15 7 20 11 8 4 18 5 9 0 12 21 19 14
1 2 3 6 7 10 13 15 0 4 5 8 9 11 18 20 12 14 19 21
Run 1 Run 2 Run 3
Cada run está ordenada
![Page 38: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/38.jpg)
Sort Merge Join
- Costo del K-way merge
Supongamos que hay N = 16 runs
ordenadas cada una de 4 páginas.
Sea M = 5
Como se requiere una página para generar
la salida, se puede usar un 4-way merge
como máximo. Gráficamente:
![Page 39: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/39.jpg)
Paso 1:
Se lee y escribe cada run cuyo tamaño es M (M-1 M) (se va leyendo de a una página de cada run y se realiza el K-way merge): Total 2NM páginas
Paso 2:
Se lee y escribe cada run cuyo tamaño es 4M (se va leyendo de a una página de cada run y se realiza el K-way merge): Total 2NM páginas
Número de Pasos: LogM-1(N)
Sort Merge JoinUna run de 4 páginas
K-way merge
![Page 40: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/40.jpg)
Sort Merge Join
• En cada paso se acceden 2NM páginas• Por lo tanto, el total de páginas accedidas es:
(2NM) * LogM-1(N)
• Pero NM = F (número de páginas de la relación) y N = F/M, remplazando la fórmula queda:
Total de páginas que se accesa (lee y escribe) en cada paso
Número total de pasos
![Page 41: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/41.jpg)
Sort Merge Join
(2F) * LogM-1(F/M) =
(2F) * (LogM-1(F) - LogM-1M) =
(2F) * (LogM-1(F) - 1) Costo del K-way merge
Por lo tanto, el costo total del ordenamiento es:
Costo ordenamiento parcial + Costo del K-way merge:
2F + (2F) * (LogM-1(F) - 1)
1
![Page 42: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/42.jpg)
Sort Merge Join
• Simplificando:
2F + 2F * LogM-1(F) – 2F
Costo del ordenamiento de una relación:
2F * LogM-1(F)
Redondeando el logaritmo:
2F * LogM-1(F) Costo del ordenamiento
![Page 43: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/43.jpg)
Sort Merge Join
Por lo tanto, el costo total del Sort Merge
Join será:
Costo del ordenamiento de cada relación +
Costo de la etapa merge del Sort Merge:
2Fr * LogM-1(Fr) + 2Fs * LogM-1(Fs) + Fr + Fs
Costo de ordenar r
Costo de ordenar s
Costo de la mezcla del Sort Merge
![Page 44: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/44.jpg)
Sort Merge Join
• Se han propuesto mejoras al algoritmo Sort Merge donde se fusionan las mezclas de ambos procesos (merge del Sort Merge y merge del K-way) y se logra evitar el acceso (Fr + Fs)
• Así, el costo del Sort Merge se puede reducir a:
2Fr * LogM-1(Fr) + 2Fs * LogM-1(Fs)
![Page 45: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/45.jpg)
Sort Merge Join
• Ej: Sea Fr = 1000, Fs = 100 y M = 102
2(1000) * Log101(1000) + 2(100) * Log101(100)
2000 * 2 + 200 * 1 = 4201 (páginas)
Fr FrM-1 Fs FsM-1
![Page 46: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/46.jpg)
Sort Merge Join
• En este caso el costo dio mayor que el del Block Nested, pero a medida que r y s crecen, el Sort Merge tiene un mejor comportamiento que el Block Nested…
![Page 47: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/47.jpg)
Hash Join
5. Hash Join (Reunión con Dispersión)El hash join se hace en dos etapas:a. Se hace un proceso de hashing en r sobre el
atributo de join (A)Se hace un proceso de hashing en s sobre el atributo de join (B)Esto tiene el efecto de que las tuplas de r y s que posiblemente harán parte del join quedarán en el mismo bucket (cubeta)
b. Se hace el join de r y s en cada cubeta para producir así el resultado final (join total).
![Page 48: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/48.jpg)
Hash Join
r
s
r1 ⋈ s1
rn ⋈ sn
Stage 1
Hash Table Buckets
⋈A=B
⋈A=B
Hash Function
Input buffer for r
Input buffer for s
r1
s1
rn
sn
r1
s1
rn
sn
Stage 2
![Page 49: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/49.jpg)
Hash Join
Costo:
Si cada cubeta cabe en memoria el costo es:
3(Fr + Fs)
Ya que:- r y s se deben leer para generar las cubetas:
Fr + Fs
- Las cubetas resultantes se deben escribir:
Fr + Fs
- Cada cubeta se debe leer para hacer el join: Fr + Fs
![Page 50: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/50.jpg)
Hash Join
• Para el ejemplo: Fr = 1000, Fs = 100
Costo: 3 (1000 + 100) = 3300
Y aunque el costo es mayor que el del Block
Nested, también tiene un comportamiento
asintótico mejor que este…
![Page 51: Métodos para realizar la operación de reunión (join) Francisco Moreno](https://reader035.vdocumento.com/reader035/viewer/2022081419/551cee47550346497a8b5257/html5/thumbnails/51.jpg)
Hash Join
• Desventajas:- Si una cubeta es muy grande y no cabe
en memoria, implicaría accesos adicionales
- Si se elige (o el sistema la provee) una función de hashing inadecuada
- Nótese que solo sirve para joins basados en condición de igualdad