데이터베이스 조인 알고리즘과 쿼리 최적화

이번 포스팅은 데이터베이스의 조인 알고리즘과 쿼리를 최적화하는 방법에 대해서 공부해보고 정리해보겠습니다. 

 

데이터베이스를 깊이있게 공부하면 공부할수록 왜 큰 기업들이 DBA라는 직군을 따로 뽑는지 알 수 있게 되는 대목이었습니다. 정말 데이터베이스 하나만으로도 공부해야될게 엄청나게 많네요. 

 

그럼 시작해보겠습니다!

 

데이터베이스 조인 알고리즘

우리가 RDBMS에서 쿼리를 작성하면 우리가 원하는 데이터를 가져오기위해 조인 연산을 진행하게됩니다. 이 조인연산을 최적화하기위해 데이터베이스 내부에선 옵티마이저라는 엔진이 돌아갑니다. 

 

옵티마이저는 데이터베이스의 상태를 파악하고 어떤 조인 알고리즘을 사용하면 좋을지 어떤 인덱스를 사용하면 좋을지 자체적으로 판단하여 조인연산을 최적화합니다. 

 

보통 실행계획을 실행해보면 옵티마이저가 어떤 알고리즘을 사용했는지 알 수 있습니다. 

 

 

이 쿼리에선 Nested Loop Join을 사용했네요. 

 

이렇게 옵티마이저는 그때그때 최적화를 하는데 어떻게 옵티마이저를 잘 구워삶아먹을지에 대해서 한번 알아보겠습니다. 

 

먼저 그 전에 조인 알고리즘이 어떤 것이 있는지 주요 알고리즘 세개를 공부했습니다. 

 

Nested Loop Join

조인 연산을 바깥에서 안으로 루프를 돌면서 실행하는 조인 연산입니다. 밖에서 안으로 진행하며 기준이되는 테이블을 가장 밖으로 두고 안으로 진행합니다. 

 

위의 예시로 들면 EMP 테이블을 기준으로 DEPT 테이블을 조인연산을 진행한 것에대한 예시입니다. 

 

옵티마이저가 Nested Loop Join를 사용하기로 결정했다면 옵타마이저는 상대적으로 크기가 작은 테이블을 드라이빙 테이블 (기준이 되는 테이블) 으로 설정합니다. 이유는 기준이 되는 테이블은 풀스캔을 해야하는데 크기가 작을수록 효율이 좋기 때문입니다. 

 

보통 Nested Loop Join는 부분부분 조금씩 데이터를 보여줘야하는 상황 (포털이나 이커머스) 에 효율적인 조인 알고리즘이며 대부분 Nested Loop Join을 사용하게 됩니다. 

 

왜냐하면 보통 웹 애플리케이션들이 부분부분 조금씩 데이터를 보여주고 특정한 상황에서 추가적으로 데이터를 가져오니까요. 

 

Nested Loop Join은 조인하는 테이블의 크기가 상대적으로 차이가 많이 나는 경우에 효율적입니다. 

 

Hash Join

Hash Join은 데이터를 초기에 풀스캔해서 해시테이블을 만들고 이 해시값을 이용해서 데이터셋을 만드는 알고리즘이 추가됩니다. 때문에 테이블을 풀스캔하고 해시 테이블을 만드는 초기비용이 존재합니다. 

 

Hash Join은 해싱 알고리즘을 사용하기 때문에 성능상 굉장히 유리합니다. 특히 등호 ( = ) 연산을 사용할 때 특히 성능상 좋습니다. 

 

Hash Join은 테이블의 크기가 서로 비슷하거나 테이블의 크기가 서로 큰 상황에서 유리한 모습을 보여줍니다. 

 

또한, 대량의 데이터를 통계하거나 복잡한 쿼리에서 성능상 유리합니다. 

 

Sort Merge Join

Sort Merge Join은 잘 사용하지 않는 알고리즘으로 테이블을 서로 정렬하고 나서 데이터셋을 만든다는 특징이 있습니다. 하지만 이때 정렬하는 초기비용이 상당히 크기 때문에 잘 안쓰인다고 하네요. 

 

 

옵티마이저의 조인 알고리즘 선택 조건

옵티마이저는 테이블의 통계 쿼리를 이용해서 테이블의 크기, 인덱스의 유무, 데이터의 타입등을 보고 그것에 알맞는 조인 알고리즘을 사용합니다. 

 

이 과정에서 옵티마이저는 개발자가 의도하지 않은 조인 알고리즘을 사용할 수 있고, 인덱스를 설정했음에도 의도하지않게 인덱스를 사용하지 않을 수도 있습니다. 

 

이를 해결하기위해 옵티마이저 힌트라는 것을 사용할 수도 있습니다. 힌트는 개발자가 직접 쿼리문에 어떤 조인 알고리즘을 사용해라, 어떤 인덱스를 사용해라와 같은 명령을 강제로 주입하는 방법입니다. 

 

하지만 이 방법은 옵티마이저의 유연성을 제한하고, 힌트를 유지하기위한 리소스가 들어가며, 만약 인덱스의 변경으로 잘못된 알고리즘 혹은 잘못된 인덱스를 사용할 수도 있으므로 굉장히 주의해서 사용해야합니다. 

 

이런 경우 옵티마이저가 왜 의도하지 않은 알고리즘과 인덱스를 사용했는지 파악하고 이를 해결하는 것이 더 건설적인 방향입니다. 

 

 

데이터베이스와 인덱스

보통 데이터베이스도 하나의 서버 위에서 동작하고 이 서버에서 CPU는 데이터를 가져오기위해 디스크에 접근하고 I/O 연산이 일어납니다. 

 

디스크가 데이터에 접근하는 방법은 크게 두 가지가 있는데 Sequential Access와 Random Access가 바로 그것입니다. 

 

Sequential Access는 문자 그대로 순서대로 접근하는 방법이고 Random Access는 필요한 부분만 콕 찝어서 접근하는 방법입니다. 당연히 Random Access가 Sequential Access보다 월등히 빠르기 때문에 Rnadom Access를 지향해야하는데 보통 인덱스가 그 트리거 역할을 합니다. 

 

하지만 인덱스를 잘못 설정하면 설정안하느니만 못하게 되는데요. 어떤 경우 인덱스를 설정하는 것이 좋을까요?

 

인덱스 선택도

알고리즘 중 Nested Loop Join과 Hash Join이 많이 사용되는데 Nested Loop Join에서 드라이빙 테이블은 어쩔 수 없이 풀스캔을 진행하지만 뒤의 내부 루프는 인덱스를 사용하면 성능을 높일 수 있습니다. 

 

인덱스의 선택도는 카디널리티를 기반으로 계산됩니다. 카디널리티란 인덱스에서 얼마나 같은 값이 중복되는지에 대한 개수를 의미합니다. 

 

예를 들어서 "부서"라는 컬럼으로 조인을 하는 경우 회사에 부서가 많지 않아 "고용"테이블 입장에서 중복되는 값이 많을 것입니다. 이런 경우 카디널리티가 작다고 표현합니다. 만약 "급여" 컬럼으로 조인하는 경우 급여는 중복되는 값이 적으니 이런 경우 카디널리티가 크다고 표현합니다. 

 

즉, 이렇듯 인덱스 선택도는 카디널리티를 기반으로 카디널리티가 작은 경우 선택도가 높아지는 결과를 초래하고 높은 경우 낮아지는 결과를 초래합니다. 반비례 관계라는 것이죠. 

 

인덱스의 선택도 공식은 다음과 같습니다. 

 

특정 데이터 건수 / 전체 데이터 건수

 

즉, 만약 부서가 10개이고 사원 수가 100명이라면 10 / 100 으로 0.1이 됩니다. 보통 인덱스의 선택도가 10퍼센트에서 15퍼센트 (0.1 ~ 0.15)가 되면 인덱스를 설정하는 것이 효율적이라고 합니다. 

 

왜 인덱스를 설정하면 성능이 좋아질까?

인덱스는 설정을 하게 되면 컬럼이 내부적으로 정렬이 됩니다. 이렇게 정렬된 값들은 자료구조에 저장하게 되는데 보통 RDBMS에서 B- 트리 구조로 저장합니다. 

 

B- 트리는 각 노드에 여러개의 값이 들어갈 수 있어 일반적인 이진 트리에 비해 검색 성능이 더 좋습니다. 

 

특히 MySQL의 InnoDB스토리지 엔진은 이보다 더 최적화된 B+ 트리 구조를 저장합니다. B+ 트리는 모든 값이 트리의 종단 노드 (Leaf Node)에 위치하고 있고 마지막 데이터가 그 다음 데이터와 논리적으로 연결되어있어 B- 트리보다 더 높은 검색 성능을 보여줍니다. 

 

하지만 B+ 트리의 경우 모든 데이터들이 리프노드에 몰려있어 데이터의 삽입이나 삭제연산을 수행할 때 B- 트리보다 더 제한적인 성능을 가질 수밖에 없습니다. 즉, B+ 트리는 읽기 연산에 최적화된 자료구조라고할 수 있습니다. 

 

 

마치며

데이터베이스를 공부하면 공부할수록 참 어려운 것 같네요... 좀 깊은 내용을 보려고 하면 이해하는데 참 오랜 시간이 걸리게 되는 것 같네요. 

 

공부할수록 제가 더 작아지는 기분이네요... 공부해서 새로운 지식을 하나 얻었는데 그리 좋은 기분은 아니었습니다. 

 

아무튼 오늘도 긴 글 읽어주셔서 감사합니다. 즐거운 하루 되세요!