View
107
Download
5
Category
Preview:
Citation preview
1
J4 Hash-Join R und S werden mittels der gleichen Hashfunktion h
– angewendet auf R.A und S.B – auf (dieselben) Hash-Buckets abgebildet
Hash-Buckets sind i.Allg. auf Hintergrundspeicher (abhängig von der Größe der Relationen)
Zu verbindende Tupel befinden sich dann im selben Bucket
Wird (nach praktischen Tests) nur vom Merge-Join „geschlagen“, wenn die Relationen schon vorsortiert sind
Implementierung der Verbindung: Strategien
2
Implementierung der Verbindung: Strategien
A r1 5 r2 7 r3 8 r4 5
R SB 5 s1
7 s2
10 s3
5 s4
r1 5
s15
r4 5
s45
10 s3
r2 7
s27
r3 8
h(A) h(B )
Bucket 3Bucket 2Bucket 1
3
„Normaler“ blockierender Hash-Join mit Überlauf: Partitionieren
Send
R
Send
S
receive
P1
P2
P3
Partitionh(R.A)
P1
P2
P3
Partitionh(S.A)
receive
4
„Normaler“ blockierender Hash-Join mit Überlauf: Build/Probe
Send
R
Send
S
P1
P2
P3
Partitionh(R.A)
P1
P2
P3
build
Hashtabelle
probe
Lade Blöcke von P1
5
6
7
8
9
Mengendurchschnitt (~Join) mit einem Hash/Partitionierungs-Algorithmus
R23
445
769013174288
S44179746
272
133
R S
• Nested Loop: O(N2)
• Sortieren: O(N log N)
• Partitionieren und Hashing
10
Mengendurchschnitt mit einem Hash/Partitionierungs-Algorithmus
R23
445
769013174288
S44179746
272
133
R SR3
90427613882
445
17
Mod
3
11
Mengendurchschnitt mit einem Hash/Partitionierungs-Algorithmus
R23
445
769013174288
S44179746
272
133
R SR3
90427613882
445
17
S6
273
974
1344172
Mod
3
Mod
3
12
Mengendurchschnitt mit einem Hash/Partitionierungs-Algorithmus
R23
445
769013174288
S44179746
272
133
R SR3
90427613882
445
17
S6
273
974
1344172
Mod
3
Mod
3
13
Mengendurchschnitt mit einem Hash/Partitionierungs-Algorithmus
R SR3
90427613882
445
17
S6
273
974
1344172
6273
Mod 5
Build-Phase
Hashtabelle
14
Mengendurchschnitt mit einem Hash/Partitionierungs-Algorithmus
R S = {3, }R3
90427613882
445
17
S6
273
974
1344172
6273
Mod 5
Probe-Phase
15
Mengendurchschnitt mit einem Hash/Partitionierungs-Algorithmus
R S = {3, }R3
90427613882
445
17
S6
273
974
1344172
97134
Mod 5
Build-Phase2. Partition
16
Mengendurchschnitt mit einem Hash/Partitionierungs-Algorithmus
R S = {3, }R3
90427613882
445
17
S6
273
974
1344172
97134
Mod 5
Probe-Phase2. Partition
17
Mengendurchschnitt mit einem Hash/Partitionierungs-Algorithmus
R S = {3, 13 }R3
90427613882
445
17
S6
273
974
1344172
97134
Mod 5
Probe-Phase2. Partition
18
Mengendurchschnitt mit einem Hash/Partitionierungs-Algorithmus
R23
445
769013174288
S44179746
272
133
R3
90427613882
445
17
S6
273
974
1344172
Mod
3
Mod
3
R S = {3, 13, 2, 44, 17 }
19
Vergleich: Sort/Merge-Join versus Hash-Join
R run run S
merge m
erge
R partition partition S
Radix-Join: Erhöhung der Cache-Lokalität durch Partitionierung
Wiederholte Partitionierung
Technische Universität München
Range partitioning of private input
919
7
19
3211
17
2234
318
2026
21
17
23
31
2026
chun
k of
wor
ker
W1
chun
k of
wor
ker
W2
histogram of worker W1
7 = 00111 <16≥16
17 = 10001
histogram of worker W2
<16≥16
43
34
prefix sum of
worker W100
prefix sum of
worker W243
W1
W2
W1
W2
1
19
19=10011
22
5
2=00010
2
Technische Universität München
Range partitioning of private input
919
73
211
17
2234
318
2026
chun
k of
wor
ker
W1
chun
k of
wor
ker
W2
histogram of worker W1
7 = 00111 <16
17 = 10001
histogram of worker W2
<16
43
34
prefix sum of
worker W100
prefix sum of
worker W243
73
9
1
4
17
31
2
8
21
23
2026
W1
W2
W1
W2
1
19
19=10011
23
≥16
≥165
2=00010
Technische Universität München
Real C hacker at work …
Technische Universität München
Paralleler Hash-Join ohne Partitionierung
25
Recommended