DB Join algorithm

Introduction to Join Evaluation

• Join 명령어는 데이터베이스에서 두 테이블을 연결하여 구체화 시키거나 (중간 단계 테이블로 저장) 즉석에서 사용 (이번에는 후자의 경우만 고려한다) 할 수 있게 만들어준다.
• 가장 많이 사용되는 명령어 중 하나로 최적화가 잘 돼있다.
• 조인 알고리즘의 목표는 이러한 연결을 더 효율적으로 잘 하는 것이다.

Simple Nested Loops Join

For each tuple r in R do
     For each tuple s in S do
        If r and s satisfy the join condition
           Then output the tuple <r,s>

Block Nested Loops Join

• 기존의 SNLJ에서 |R| < |S| 라고 가정한다면, S는 R의 모든 튜플에 대하여 한 번씩 스캔이 될 것이다. 만약 조건을 만족하는 R 튜플이 많다면, 그리고 S에 조인을 위한 인덱스가 없다면 이 비용은 배우 비쌀 것이다.

• BNLJ는 R 튜플의 "묶음" 당 한 번의 S 스캔을 실행함으로 효율을 높인다.

• 예를 들면 BNLJ의 방식 중 하나는 R 튜플의 모든 페이지를 메모리로 읽고 hash table 으로 로드한다. 그리고 S를 스캔할 때 hash table을 이용하여 현재 로드된 R의 페이지의 어떤 튜플이라도 매치하는 S의 튜플을 찾는다. 이렇게 하여 S의 스캔 횟수를 줄일 수 있다.
• DB에서 성능에 중요한 부분은 디스크 I/O가 일어나는 횟수인데 이가 줄어든다.

• 또 다른 변형은 R의 페이지를 가능한 많이 메모리에 로드하여 모두 hash table화 하는 것이다. 그리고 반복적으로 S를 스캔한다. 이렇게 하면 S의 스캔 횟수를 더 줄일 수 있다. 
• 사실 이러한 알고리즘은 따로 분류되어 hash join 알고리즘이라 불린다.

Index Nested Loops Join

• 기존의 접근 방법은 R x S 을 항상 실행하고 존재하는 인덱스를 사용하지 않는 문제가 있다.
• 만약 한 릴레이션 (S라고 하자)의 join 열에 인덱스가 있다면 이 릴레이션을 inner로 만들고 이 인덱스를 사용하지 않을 이유가 없다.
• outer 릴레이션 R을 스캔 한다 (한 번에 한 페이지씩).
• R의 각 튜플 r에 대해 인덱스를 이용하여 S에서 일치하는 튜플을 찾아낸다.
• eqi-join 인 경우에 사용한다. 다른 경우에도 사용할 수는 있지만 매우 효율이 좋지 않음.
• Nested Loop Join과 같은 방식으로 읽어오고 비교한다.
• Cost of Indexed-Nested Loop
• worst cast (r 테이블의 한 개 블록만 메모리에 수용)
• C = bi + nr * c
• c는 r의 튜플과 조인조건을 만족하는 s의 튜플을 찾는 비용이며, 접근한 인덱스의 노드 블록의 수가 비용이 됨.
• 만약 r과 s 두 개 릴레이션 모두에 조인 애트리뷰트에 대한 인덱스가 사용 가능하다면?
• 큰 릴레이션을 inner로(인덱스를 사용하는 쪽으로) 보낸다.
• 비용 c의 높이는 인덱스 트리의 높이에 비례해서 급격하게 줄어든다.
• 트리에서 찾는 비용은 O(lg n) 이니까..

Sort-Merge Join

• R x S의 생성을 피하는 또 다른 방법으로 SMJ가 있다.

• 인덱스가 없을 때 SNLJ 보다 좋은 성능을 내기 위해 사용.

• 동등 조인 조건에 대해서만 수행이 가능하다.
• 동등 조인이란: Equi 조인이라고도 하며, 공통 컬럼의 동등 비교만을 한다.
• 즉 <, > 등의 부등호는 사용하지 않고 ON a.col1 = b.col2 처럼 동등한 경우만을 고려한다.

• SMJ는 두 단계로 나뉜다.
• 정렬 단계
• external sort 알고리즘을 사용하여 R과 S를 조인 속성을 기준으로 정렬한다.
• 병합 단계
• 두 릴레이션을 병합하며 R과 S에 속해있는 튜플을 찾아낸다.
• 병합 단계는 SNLJ과 비슷하지만 차이는 정렬되어 있다는 것이고, 동등 조인 조건에서만 가능하므로 동등 조건이 아니면 병합을 시도하지 않는 것이다.

Hash Join

• 비용이 가장 많이 들어가는 조인 방법이지만 대용량 데이터 조인 시 Sorted 나 Nested Loop 보다 좋은 성능을 나타낸다.

• 조인에 참여한 두 집합 중 작은 집합 (Build input) 의 해쉬 테이블을 메모리상에 만들고  큰 집합 (Probe Input) 은 조인을 위해 해쉬 테이블을 검색한다.

• 따라서 조인 과정에서 발생하는 부하가 없으나, hash table 생성 비용이 크다. 따라서 Build Input이 작을 때라야 효과적이다.

• 이용 가능한 hash area의 크기에 따라 성능에 영향을 받는다.

• 이용 가능한 메모리가 작은 집합을 유지할 정도로 충분히 크지 않다면 두 집합을 좀 더 작은 단위로 나누게 되는데, 이를 파티션이라고 한다.