join은 관계형 DB를 사용하게 되면 거진 필수적으로 다루게 되며, 매우 자주 쓰인다.
이번에는 이렇게 join할 때 사용되는 여러가지 join 알고리즘에 대해 살펴보고 언제 어떤 알고리즘을 사용하는게 좋을지 정리해보려한다.
크로스 결합
크로스 결합은 테이블과 테이블을 곱했을 때 나오는 모든 경우의 수를 결과로 나올 때 사용하는 알고리즘이다.
이렇게 모든 결과가 나오는 크로스 결합의 테이블과 테이블의 곱을 카테시안 곱(Cartesian Product)이라고 한다.
들으면서 느꼈겠지만 거의 쓰지 않을 뿐더러 성능이 좋지 않다.
아래와 같은 쿼리문을 수행할 때 크로스 결합이 수행된다.
select * from a,b
Nested Loops
join 시 중첩 반복문을 사용하는 알고리즘이다.
SQL에서 결합은 한 번에 두개의 테이블만 결합하므로 본질적으로 이중 반복과 정확히 일치한다.
아래와 같은 쿼리문을 수행할 때 보통 발생한다. (아래에서 설명하겠지만 전부는 아니다.)
select * from a inner join b on a.id = b.a_id
이중 반복문을 생각해보자. 위와 같은 쿼리문을 이중 반복문으로 결합 결과를 내려면 어떻게 해야할까?
다음과 같이 나올 것이다.
for a_item in a_list:
for b_item in b_list:
if a_item.id = b_item.a_id:
result.add(~)이것이 정확히 Nested Loop 알고리즘이다.
이중 반복문에서 어떤 테이블이 바깥에 위치하고(위 반복문 예시에서는 a) 안에 위치하고(위 반복문 예시에서는 b)는 결과에는 전혀 영향을 끼치지 않지만 생각해보면 차이가 존재한다.
잘 생각해보면 밖의 테이블의 각 row들은 단 한번씩만 접근하게 되나 안의 테이블의 row는 밖의 테이블의 row 수만큼 접근하게 된다.
지금까지의 알고리즘 내용을 정리해보면
- 결합 대상 테이블에서 레코드를 하나씩 반복해가며 스캔, 이를 구동 테이블(반복문에서 밖에 위치)이라고 부름, 다른 테이블은 내부 테이블이라고부른다. (이중 루프에서 안쪽 반복에서 접근한다는 의미)
- 구동 테이블의 레코드 하나마다 내부 테이블의 레코드를 하나씩 스캔해서 결합 조건에 맞으면 결과에 더한다.
- 이러한 작동을 구동 테이블의 모든 레코드에 반복
여기까지 읽고 제대로 이해가 됐다면 ‘카르테시안 곱과 뭐가 다른거지?’ 라는 생각이 들것이다. 이중 반복문이면 결국 테이블 * 테이블과 정확히 성능이 같은 것 아닌가? 라는 생각이 들 수 있다.
결론만 말하면 사실 같다.
Mysql에서도 카르테시안 곱이 나올 sql을 수행해도 Nested Loop Join이 나온다.
둘의 차이는 결합 조건을 볼때 그 조건 col이 내부 테이블 index가 있나 없나의 차이에서 결과가 극명하게 갈린다.
여담이지만 위 실행계획에서 Using join buffer는 위와 같이 두 테이블의 결합 조건에 적절하게 사용할 인덱스가 없다면 내부 테이블에서 읽은 레코드를 임시 공간에 보관해두고 필요할 때 재사용할 수 있게 해준다.
읽은 레코드를 임시로 보관해두는 메모리 공간을 "조인 버퍼"라고 하며, 조인 버퍼가 사용되는 실행 계획의 Extra 칼럼에는 "Using join buffer"라는 메시지가 표시된다.
간단하게 말하면 카르테시안 곱은 너무 성능상 좋지 않으니 내부 테이블을 메모리에 들고와서 성능을 보완하는 것이다. (당연히 이러한 메모리는 제한이 있고 너무 과다하게 사용되면 swap이 일어나 성능이 떨어진다.)
그렇다면 어떤 테이블을 구동 테이블로?
어떤 테이블을 구동 테이블로 잡는게 좋을까?
위에서 내부 테이블은 구동테이블의 row 수만큼 접근되니 내부 테이블이 더 작은게 좋나? 라고 생각할 수도 있다.
그러나 결론만 말하자면 구동 테이블이 작은게 좋다.
반대로 말하면 내부 테이블이 큰게 좋다.
(Sql계의 격언이다.)
구동 테이블이 작으면 좋은 이유
사실 구동 테이블이 작아도 결국 접근하는 레코드 수는 R(a) * R(b)로 같다.
그래서 구동 테이블이 작게 라는 격언에는 다음과 같은 암묵적인 전제가 포함된다.
내부 테이블의 결합 키 필드에 인덱스가 존재한다.
내부 테이블의 결합 키 필드에 인덱스가 존재한다면 해당 인덱스를 통해 DBMS는 내부 테이블을 완전히 순환하지 않아도 된다.
즉, 두개의 테이블 모두 Table Full Scan이 일어나지 않아도 된다. (위에서 봤겠지만 두 테이블 모두에 적절한 인덱스가 없다면 성능을 위해 join buffer라는 메모리에 내부 테이블의 결과를 가져와놓고 재사용한다.)
내부 테이블에 인덱스가 있게되면 내부 테이블을 반복해서 돌 필요 없이 인덱스를 통해 해당 값이 있는지 확인하면 그만이다.
즉, 양쪽 테이블의 결합키에 인덱스가 있을 때 더 작은 테이블을 구동 테이블로 선택하여 더 작은 테이블에 대해서만 Table Full Scan이 일어날 수 있게 할 수 있다.
아래와 같은 경우 더 작은 B Table을 구동 테이블을 택하면 성능 상 더 좋다. (당연히 아래보다 더 큰 차이가 날 때 유의미하다.)
내부 테이블의 결합 키 인덱스가 사용되지 않으면 구동 테이블이 작아봤자 아무런 장점이 없다.
내부 테이블은 구동 테이블의 레코드 수만큼 N번 돌기 때문에 내부 테이블을 올릴 수 있을 만큼 충분한 양의 버퍼 캐시가 있다면 내부 테이블이 큰 경우가 더 유리할 수도 있지만 인덱스를 사용할 수 있는 경우와 비교하면 효과가 크지 않다. 위 Mysql에서 버퍼를 사용한 경우에는 더 큰 테이블을 옵티마이저가 선택한 것을 볼 수 있다.
만약 인덱스가 내부 테이블에 대해 유일하지 않다면 반복은 여전히 생긴다. (Index Range Scan)
Nested Loop Join의 단점
결합 키로 내부 테이블을 접근할 때 히트되는 레코드가 너무 많은 경우 (인덱스가 내부 테이블에 대해 유일하지 않은 경우 index range scan이 일어나 히트되는 레코드가 많을 수 있다.) 성능이 좋지 않을 수 있다.
Mysql 기준
보통 Mysql에서는 FK로 설정하면 자동으로 Index가 생성된다.
그러면 결국 보통의 경우에는 두 테이블 다 결합키가 인덱스인데 어떤 테이블이 구동 테이블이 되는 것이 좋을까? 위에 말을 잘 이해했다면 당연히 구동 테이블이 더 작은 경우라고 할 수 있다!
보통의 1대 다 경우라면 외래키는 다 쪽에 있고 다쪽의 레코드가 절대적으로 많은 경우가 대다수이므로 1이 구동 테이블이 될 것이라 예상할 것이다.
이렇게 되면 1 테이블의 pk로 더 큰 내부 테이블(다)로 네스티드 루프 조인을 돌게 되면 IndexRangeScan이 발생해서 성능이 안좋을 확률이 크다.
이는 Hash Join을 통해 해결하거나 더 큰 1의 테이블을 구동 테이블로 잡아서 Index Unique Scan이 일어나게해 성능 상의 이점을 취할 수 있다.
실제 Mysql에서도 더 큰 테이블이고 다쪽인 Point를 구동 테이블로 잡아 FullScan이 일어난 것을 볼 수 있다.
Hash Join
해시 결합은 일단 작은 테이블을 스캔하고, 결합 키에 해시함수를 적용해서 해시값으로 변환한다.
이렇게 변환된 해시 값은 매칭되는 워킹 메모리에 새로운 해시 테이블을 만들어 그곳에 저장한다.
작은 것을 선택하는 이유는 메모리에 저장되어 자리를 조금 차지해야하기 때문이다.
이어서 다른 테이블(큰 테이블)을 스캔하고, 결합 키가 해시 테이블에 존재하는지를 확인하는 방법으로 결합을 수행한다.
Hash Join이 사용되는 경우는 어느 한쪽 테이블이 극단적으로 작거나 크지 않은 경우이다.
극단적으로 작으면 Nested Loop가 성능 상 훨씬 좋다.
특징
- 결합 테이블로부터 해시 테이블을 만들어서 활용하므로, Nested Loops에 비해 메모리를 크게 소모한다.
- 메모리가 부족하면 저장소를 사용하므로 지연이 말생한다
- 소비하는 메모리 양이 높아 스왑이 일어나 지연이 발생할 리스크가 있다.
- 사용자의 요청이 잦은 OLTP 서비스(사용자 요구에 바로 응답해야하는 처리)에는 사용하지 않는 것이 좋고, 배치 같은 시스템에 사용하는 것이 좋다.
- 출력되는 해시 값은 입력 값의 순서를 알지 못하므로 등치 결합에만 사용할 수 있다. (on 조건 시 =만 가능)
- 양쪽 테이블을 모두 읽어야 하므로 테이블 풀 스캔이 일어난다.
유용한 경우
- Nested Loops에서 적절한 구동 테이블(작은 테이블)이 존재하지 않는 경우
- 작은 테이블이 있지만 히트되는 레코드 수가 너무 많은 경우
- Nested Loops의 내부 테이블에 인덱스가 존재하지 않는 경우
- 한마디로 Nested Loops가 효율적으로 작동하지 않는 경우 유용함
Sort Merge
결합 대상 테이블들을 각각 결합 키로 정렬하고, 이 둘을 모두 워킹 메모리에 저장한다.
정렬된 각 결합 키들을 순차적으로 비교해 일치하는 결합 키를 찾으면 결과로 반환한다. 정렬된 상태이기에 Nested Loop join보다 성능이 좋을 수 있다.
특징
- 대상 테이블들을 모두 정렬해야 하므로 Nested Loops Join보다 많은 메모리를 소모한다.
- Hash와 비교할 때 규모에 따라 다르지만 Hash는 한쪽 테이블에 대해서만 해시 테이블을 만들므로 Hash보다 많은 메모리를 사용하기도 한다. → Swap 발생으로 인한 지연 가능
- Hash와 다르게 동치 결합 뿐만 아니라 부등호를 사용한 결합에도 사용할 수 있다. (부정 조건은 불가능, 부정 조건은 Nested Loop join만 가능하다)
- 결합 키가 정렬되어 있는 상태라면(인덱스) 정렬을 생략하기도 한다. 다만 SQL에서 테이블에 있는 레코드의 물리적인 위치를 알고 있을 때 가능해서 이러한 생략은 구현 의존적이다.
- 테이블을 정렬하므로 한쪽 테이블을 모두 스캔한 시점에 결합을 완료할 수 있다.
결합 자체에 걸리는 시간은 레코드 수가 많더라도 아래와 같이 선형으로 진행되어 나쁘지 않다.
그러나 테이블 정렬에 많은 시간과 리소스를 요구할 가능성이 있어 정렬을 생략할 수 있을 때만 사용하는 것이 좋다.
그 이외의 경우에는 Nested Loops나 Hash 고려하는 것이 좋다.
의도하지 않은 Cross join
삼각 결합 패턴
Table B - Table A - Table C의 삼각 결합 형태로 join하는 것을 삼각 결합 패턴이라고 하는데 이와 같은 경우에 의도하지 않은 Cross join이 발생할 수 있다.
이때, B와 C의 크기가 작다면 옵티마이저가 A에 두번 결합하기보다는 먼저 작은 테이블들을 결합(결합 조건이 없으니 CrossJoin)하고 그 결과와 A를 결합하여 1회로 횟수를 줄이는 것을 택할 수 있다.
→ 이러한 경우는 특이한 경우는 아다. 거래 명세 등의 큰 트랜잭션 테이블과 고객 또는 달력 등의 작은 마스터 테이블을 결합할 때 자주 나타난다.
(다대다를 일대 대 - 다대일로 푸는 패턴) 그래서 작은 테이블 들끼리의 코로스 결합이 일어나는 것을 두려워할 필요는 없다.
문제는 큰 테이블끼리 결합할 때 크로스 결합이 선택되는 경우다.
이는 단순히 테이블의 크기가 클 때 뿐만 아니라, 검색 조건으로 히트되는 레코드 수가 변할 때도 발생한다.
- 레코드 수를 꽤 압축할 수 있는 입력이 들어오면 옵티 마이저가 크로스 결합으로 충분하겠다고 판단한 후 이를 저장
- 이후 레코드 수를 제대로 압축할 수 없는 입력이 들어왔을 때도 저장된 정보를 바탕으로 같은 실행 계획을 선택해버리는 일이 생길 수 있다.
의도하지 않은 크로스 결합을 회피하는 방법
B와 C 사이에 불필요한 결합 조건 설정 → 이 결합 조건이 결과에 아무런 영향도 주지 않는 경우에만 사용할 수 있다.
가령 아래와 같이 사용 가능하다.
select * from member
inner join point on member.member_id = point.member_id
inner join order on member.member_id = order.member_id and order.member_id = point.member_id
상황에 따른 최적의 결합 알고리즘
- Nested Loops
- 장점 : 작은 구동 테이블 + 내부 테이블의 인덱스 조건 하에 굉장히 빠르고, memory 또는 디스크 소비가 적어 OLTP에 적합
- 단점 : 대규모 테이블들의 결합에는 부적합, 인덱스가 없거나 선택률이 높으면 느림
- Hash
- 장점 : 대규모 테이블들을 결합할 때 적합
- 단점 : 메모리 소비량이 큰 OLTP에는 부적합→ swap으로 인한 지연 가능, 등가 결합만 가능
- Sort Merge
- 장점 : 대규모 테이블들을 결합할 때 적합
- 단점 : 데이터가 미리 정렬되어있지 않다면 비효율적, 메모리 소비량이 큰 OLTP에는 부적합→ swap으로 인한 지연 가능, 등가 결합만 가능
소규모 - 소규모 : 뭘써도 성능 차이가 크지 않음
소규모 - 대규모 : 소규모 테이블을 구동 테이블로 하는 Nested Loops를 사용 인덱스가 필요하고 구동 테이블의 선택에 대한 생각이 필요, Hash 사용 검토
대규모 - 대규모 : 일단 해쉬 사용하고, 정렬된 상태라면 Sort Merge 고려
정리
결합은 알고리즘이 복잡하여 실행 계획 변동이 일어나기 쉽고, 이를 예측하기는 어렵다. 이를 방지하려면 결국 결합을 최대한 사용하지 않는 것이 중요하다!
필자의 개인적인 생각에는 DB에는 항상 데이터가 쌓일 수 있고 불확실성이 너무 크기 때문에 join을 사용하여 해결한 경우 그리고 join을 사용하지 않는 경우에 대한 성능테스트를 시도 후 지속적인 모니터링을 통한 관찰을 통한 성능 관리가 필요하다고 생각한다.
참고 : 실행계획을 맹신하면 안되는 이유와 옵티마이저와 통계 정보
이번에 실행계획을 많이 봤는데 이를 맹신하면 안되는 이유에 대해 알아본다.
옵티마이저는 통계 정보가 저장된 카탈로그에서부터 정보를 받아와 쿼리 플랜을 작성한다.
그런데 옵티마이저가 실제로 최적의 쿼리 플랜을 선택하지 못하는 경우가 꽤 많다.
카탈로그는 항시 데이터가 들어오거나 update될 때마다 정보가 바뀌는 것이 아니어서 카탈로그 정보와 현재 DB 정보의 불일치가 대표적인 원인이다.
카탈로그에 포함되어있는 통계 정보
- 각 테이블의 레코드 수
- 각 테이블의 필드 수와 필드의 크기
- 필드의 카디널리티 (값의 개수)
- 필드 값의 히스토그램(어떤 값이 얼마나 분포되어 있는가)
- 필드 내부에 있는 NULL 수
- 인덱스 정보
테이블에 데이터 삽입/갱신/제거가 수행될 때 카탈로그 정보가 갱신되지 않는다면, 옵티마이저는 오래된 정보를 바탕으로 실행 계획을 세우게 된다. 과거 정보만 갖고 있으니 잘못된 계획을 세우게된다.
최적의 실행 계획이 작성되게 하는 방법
따라서 테이블의 데이터가 많이 바뀌면 카탈로그의 통계 정보도 함께 수정해야한다.