RDB Join 에 대해

최근에 학교 수업에서 parallel join 에 대해 배웠다. 시험 공부도 할 겸 join 에 대해 전체적으로 정리해 보자.

# 왜 join 이 필요한지?

Relational database 에서는 data repetition 을 줄이기 위해 normalization 을 수행한다.

이는 하나의 큰 테이블을 작은 테이블로 split 해서 저장하는 것을 뜻한다.

 

이들간의 관계는 foreign key 로 저장하고, 원래의 큰 데이터를 reconstruct 하는 데에 join 을 이용한다.

 

# join 의 비용? = # I.O

Disk IO (read / write in-out) 하는 cost 를 join 의 cost 로 잡는다.

메모리 계층에서 disk 에 저장된 tuple 을 cpu 가 access 해야 하고, 이게 가장 비싼 작업이기 때문이다.

 

# join algorithms

테이블 R, S를 join 하는 경우를 생각하고 페이지 사이즈는 각각 M, N 개, #rows 는 각각 m, n 개 라고 하자.

1. Nested loop join

이중 for loop 로 두 테이블을 도는걸 뜻한다.

Cost 는 M + m * N 으로 R의 row 하나를 돌 때 마다 S 테이블 전체를 돌기 때문이다.

 

Block 을 활용해서 cache locality 를 활용하면 M + M / Br (블록수) * N 으로 줄일 수 있다.

 

Cost 에 N * M 있으므로 기본적으로 매우 비싼 알고리즘이다.

 

 

2. Hash join

두 개의 step 으로 구성된다. 1) R 을 hash bucket 에 올린다. 2) S 를 probing 하면서 bucket 에 집어넣는다.

 

여기서 문제가 있는데, hash bucket 도 cpu 가 access 해야 하므로 IO 를 거친다는 점이다.

 

또한 hash 의 단점으로 memory address 가 random 이라 read / write 가 sequential 보다 비싸다.

 

*Sequence locality 를 활용해야 cpu cache 효율이 좋다.

 

이를 해결하기 위한 여러 알고리즘이 있는데.. (는 시험범위니까 공부하자)