Inner Join Internally

Inner Join이란

Inner Join은 두 개의 테이블에서 공통된 값을 가진 행만을 반환하는 SQL 연산이다. Inner join은 연산 효율화를 위한 데이터 필터링을 위해 사용하거나, 연관된 테이블을 하나의 통합 데이터 세트로 만들때 많이 사용된다.

 

Inner Join의 구현 방식은 크게 3가지가 있다.

Nested Loop Join

Nested Loop Join은 이름 그대로 loop를 두번 사용해서 Join하는 알고리즘이다.

• Outer loop: 첫번째 테이블의 모든 row를 한번씩 탐색한다.
• Inner loop: 첫번째 테이블의 하나의 row에 대해서 두번째 테이블에서 주어진 조건이 맞는 row를 탐색한다.

구현이 매우 간단하기 때문에 대부분의 RDBMS에서 기본적으로 구현을 했다. 하지만 첫번째 테이블안의 데이터 수를 N, 두번째 테이블안의 데이터 수를 M이라고 할때 NM 만큼 시간이 소요된다. 

이런 Nested loop를 구현할때는 Outer loop가 Inner loop 보다 더 적게 반복하는 것이 좋다. 따라서 Inner join할때 첫번째 테이블이 두번째 테이블에 비해 데이터 수가 적게 설정한다.

Merge Join

Merge Join은 두 테이블의 데이터를 인덱스 혹은 내부적인 기준으로 데이터를 정렬 후, 한번 데이터를 sweeping하는 방식이다.

당연히 이미 정렬된 데이터에 대해 효율적으로 동작하고, Equi / Theta 여부와 상관없이 적용 가능하다. Nested Loop Join과 비교했을 때 NLogN + MLogM으로 데이터가 많아질 수록 더 효율적이다.

Hash Join

Hash Join은 첫번째 테이블에 대해 Hash Table을 만들고, 두번째 테이블을 한번 탐색하면서 Hash Table에 일치하는 값이 있는지 찾는다. Hash Table은 메모리에 저장되고, 만약 메모리에 저장할 수 없는 경우 디스크에 저장된다.

첫번째 테이블에 대해 Hash Table을 만드므로, 상대적으로 첫번째 테이블이 두번째 테이블보다 데이터 수가 적게 설정한다.

 

Hash Join은 Hash Table을 활용하기 때문에 Theta Join을 할 수 없다. 따라서 이 경우는 Merge join이나 Nested loop join을 사용해야 한다. 또한 해시 함수 계산에 대한 오버헤드가 있을수 있다. 하지만 Join에 필요한 연산수가 (N + M)으로 가장 적고, 병렬 처리가 가능하기 때문에, 대규모 데이터를 조인할 때 더 효율적이다.