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