Seminar - Dec 28 (Mon)

Sort vs. Hash Revisited: Fast join Implementation on Modern Multi-core CPUs

by Changkyu Kim  (Intel's Microprocessor and Programming Research)

1) Introduction

DB의 문제를 architecture로 어떻게 풀것인가?의 문제.

DB operation인 Join은 매우 heavy한 operation. table size가 커지면 load가 exponential하게 증가한다

memory capacity가 증가하고 faster I/O의 등장으로 과거에는 I/O bottleneck이 문제였지만 이제는 CPU resource가 중요하게 되었음.

Join operation은 Hash join, Sort-merge join의 두 종류가 있다.

GOAL: Revisit these two join algorithm in the morden CPU and the future CPUs

2) Hash Join

large hash table -> random memory eccess가 증가

random memory access는 cache line unfriendly access or TLB unfriendly access로 memory bound operation이다.

Main Idea: 이를 compute bound problem으로 바꾸기 위해서 cache안에서 Join computing을 할 수 있도록 한다.

Use (4B key, 4B record) tuples in cache, with partial key and another hash function for record.

전체 과정은 Prolog -> Join -> Epilog 의 순으로 진행된다.

Prolog: compaction to (4B partial key, 4B record pointer)

Hash Join operation: table 1을 Key에 따라 Partition, table 2에서 일치하는 key를 찾아서 match, result table에 쓴다.

Epilog: test if false positive, find the real key with the partial key

이러한 방법으로 In-memory hash join을 함으로써 fastest reported performance를 낼 수 있었음.

문제: (4B key, 4B record) tuples이 가능한가

Prolog와 Epilog작업이 얼마나 expensive한가가 관건

3) Sort-merge Join

partition작업 대신에 table 1의 key 전체를 sort한 후에

table 2에서 일치하는 key를 찾아서 merge.

지금까지는 hash join이 sort-merge join보다 더 성능이 좋다고 알려져 있지만

미래에 wider SIMD가 사용되게 되면, sort-merge join이 더 적합할 것으로 보인다.

4) Evaluation

Prolog와 Epilog에 많은 시간이 소요되지만, 이를 포함해도 성능이 좋아짐

(4B key, 4B record) tuples에 대해서는 여전히 논의해야할 문제이다.