Join 알고리즘 특징/최적화

06 Jan 2023

시리즈 목차

3가지 조인 비교

3가지 조인 알고리즘이 어떤 상황에 선택되는지(유리한지) 알아보자. 일단은 시간복잡도부터 따져보면. Nested Loop은 O(N*M), Hash와 Sort-Merge는 O(N+M)이다.

조인 알고리즘은 WHERE문으로 필터링된 데이터의 갯수에 따라 첫번째로 갈린다. WHERE문으로 필터링이 많이돼서 Join할 데이터가 적다면 Nested Loop 조인을 이용한다. WHERE문으로 필터링된 뒤에도 데이터가 많이 남아있다면 Hash 조인과 Merge 조인을 이용한다.

Nested loop

Nested Loop Join은 보통 WHERE문으로 필터링된 데이터가 적을 때 이용된다. 이유는 단순하다. Nested Loop은 특별한 초기 프로세스가 없기 때문이다. Hash 조인은 Hash 테이블을 만들어야하고, Merge 조인은 조인하는 테이블들을 Join 키를 기준으로 정렬해야한다. Nested Loop은 아무것도 없다. 그냥 하나하나 비교하는게 끝이다. 시간복잡도가 다른 알고리즘보다 높음에도 불구하고(O(N*M)) 다른 알고리즘과 다르게 초기 작업이 없기때문에 가볍게 진행될수 있다. 다만 데이터가 많아지면 시간복잡도의 성능 저하가 기초작업에 필요한 성능 저하보다 커지게된다. 그렇게 되면 다른 조인 알고리즘을 선택하게 된다.

Hash vs Sort Merge

이제 Hash 조인과 Sort Merge 조인 중 어떤 알고리즘이 선택되는지에 대해 알아보자. 아래 4가지를 핵심으로 데이터베이스 옵티마이저가 어떤게 좋은 쿼리 성능을 낼지 판단하게 된다.

1. 인덱스

양쪽 테이블이 Join하는 필드에 인덱스가 설정돼있다면 Sort Merge Join이 유리하다. 이름부터 정렬이 붙어있는것만봐도 알수 있듯이 양쪽테이블을 정렬하는 것이 Sort Merge Join의 시작이다. 그런데 정렬을 진행할 조인키에 이미 인덱스가 설정되어있다면 이미 정렬이 돼있는 것이기때문에 정렬 과정이 생략된다. 정렬 작업이 제일 큰 리소스를 소모하는 단계였기때문에 Hash Join보다 큰 성능을 낼수 있게 된다. 둘다 O(N+M)의 시간복잡도를 가졌는데 Sort Merge Join은 기초작업(정렬)이 사라진 반면 Hash Join은 여전히 기초 작업(해시 테이블을 만드는 작업)이 필요하다. 그러므로 성능상 우위에 있다.

2. 데이터 분포

테이블끼리 조인될 때 모두 one-to-one으로 하나씩 매칭돼서 조인되는 것이 아니라 ManyToOne, ManyToMany와 같이 몇몇 인기있는 행에만 여러 조인이 생길때가 많다. (학생과 강의 테이블이 있다고 하면 특정 인기 강의를 조인하는 학생 데이터가 훨씬 많다.) 이러한 상황에 해시테이블을 만들게 되면 같은 해시 테이블 키에 여러 데이터가 들어가버린다.(해시테이블의 값은 일반적으로 바구니(bucket) 형태이다. 여러개의 값이 들어갈수 있다는 의미.) 해시테이블에서는 key에 대해 값이 너무 여러개가 돼버리면 해시키로 값을 찾은 뒤에도 그 값들에서 또 Join key 비교를 해야한다. 이렇듯 해시충돌이 많이 발생해버리면 해시 테이블을 만들어 key로 빠르게 value를 찾으려는 의미가 사라져버린다.

3. 양쪽 테이블의 데이터 양

Hash Join은 양쪽 테이블 중 크기가 작은 것을 이용해 해시테이블을 만드는데 크기가 둘 다 크다면 메모리 이용율이 많아져 좋지 않다. 그리고 해시 데이터가 많아질수록 해시충돌할 확률이 커지므로 성능이 저하된다. 양쪽 테이블의 크기가 크다면 메모리 사용율이 적은 Sort Merge Join이 유리하다.

4. 이용가능한 메모리

위에서 계속해서 Hash Join은 메모리에 해시테이블을 만든다고 했다. 그러니 당연하게도 Sort Merge Join보다 메모리 이용이 커지니 메모리가 부족한 환경에서는 불리하다.

5. Join key의 크기, 복잡성

Join에 이용되는 Key가 너무 길거나 복잡하면 비교 작업에 시간이 더 걸릴 수 있다. 정렬 또한 비교작업이기 때문에 Sort Merge Join에는 취약하다. 반면에 Hash는 key의 복잡성에 그리 큰 영향을 받지 않는다. 그리고 해시함수의 결과값은 인풋의 복잡성,길이에 아무 상관없이 고정된 길이로 변환한다. 그러므로 복잡한 Join key를 가지고 비교하는 과정이 덜한 Hash join이 다른 알고리즘에 비해 유리하다.

위 5가지 +a로 데이터베이스 옵티마이저가 무엇이 좋을지 판단해서 쿼리를 실행하게 된다.