이번 포스팅에서는 JOIN, WHERE, ORDER BY와 인덱스와의 관계에 대해 알아보려고 합니다.
😁 JOIN과의 관계
먼저 JOIN의 알고리즘에 대해 알아보겠습니다.
1. Nested Loop Join
Nested Loop Join은 가장 기본적인 JOIN 알고리즘입니다.
Nested Loop Join 방식은 한쪽 테이블의 각 행을 읽고, 다른 테이블을 전체 스캔하며 조건을 비교하는 방식입니다. 예를 들어, A와 B 두 테이블이 있을 경우 A 테이블의 각 행에 대해, B 테이블의 모든 행을 비교하는 방식입니다.
시간 복잡도는 두 테이블의 행을 곱한 O(M X N) 입니다.
또한 비교 대상 테이블의 인덱스 유무에 따라 아래와 같이 동작하게 됩니다.
-
비교 대상 테이블의 인덱스가 없을 경우 JOIN은 Nested Loop 방식을 통해 데이터를 탐색하게 됩니다.
-
비교 대상 테이블의 인덱스가 있을 경우 데이터베이스는 Index Nested Loop 방식을 통해 데이터를 탐색하게 됩니다.
Index Nested Loop 방식은 기준 테이블의 JOIN 비교 값과 일치하는 행들을 비교 대상 테이블 인덱스에서 바로 찾아오는 방식입니다.
즉, 비교 대상 테이블을 전체 스캔하는 것이 아니라 인덱스로 해당 값과 일치하는 행들을 바로 조회하여 합치는 방식입니다.
2. Block Nested Loop Join
Block Nested Loop Join은 Nested Loop Join을 개선시킨 방식입니다.
Nested Loop Join은 기준 테이블의 각 행에 대해서 비교 대상 테이블을 전체 스캔하여 비교하는 반면 Block Nested Loop Join은 비교 대상 테이블을 한 번에 메모리에 로드하여 기준 테이블의 여러 행과 비교하는 방식입니다.
즉, 기준 테이블인 A에 대해서도 각 행마다 읽어오는 게 아니라 여러 행을 블록 단위로 읽어오고 비교 대상 테이블인 B에 대해서 처음 전체 테이터를 한번 읽어온 이후에 메모리에서 비교를 하는 방식입니다.
이를 통해 디스크 I/O를 줄여 성능을 향상시킬 수 있습니다.
3. Hash Join
Hash Join은 해시 구조를 통해 JOIN을 수행하는 방식입니다.
동작 과정은 아래와 같이 Build와 Probe 단계로 나뉩니다.
1. Build 단계
조인할 두 테이블 중 더 작은 테이블(메모리에 적합한 크기)을 선택하여 테이블의 조인키를 기준으로 해시 테이블을 생성합니다.
Hash(1) → {id: 1, name: 'Alice'}
Hash(2) → {id: 2, name: 'Bob'}이 해시 테이블은 조인키를 해시 함수로 변환하여, 특정 버킷에 데이터를 저장하는 구조입니다.
2. Probe 단계
나머지 테이블(큰 테이블)을 읽으며, 조인키를 해시 함수로 변환하여 해시 테이블에서 매칭되는 데이터를 찾습니다. 이 단계에서는 해시 함수 덕분에 데이터를 빠르게 비교할 수 있게 됩니다.
4. Merge Join
Merge Join은 두 테이블이 조인키를 기준으로 정렬된 상태일 때, 정렬된 데이터를 효율적으로 병합하여 조인 결과를 생성하는 방식입니다.
이 방식은 정렬된 값에 따라 포인터를 이동하는 방식인 점에서 Nested Loop Join과 차이점을 지니고 있습니다.
동작 과정은 아래와 같습니다.
1. 정렬(Sort)
조인키를 기준으로 두 테이블을 정렬하며, 이미 정렬된 상태라면 이 단계를 건너뛸 수 있습니다.
2. 병합(Merge)
정렬된 두 테이블을 처음부터 순차적으로 탐색하며, 조인 조건을 만족하는 행을 병합합니다. 두 포인터를 이동하며 조인 조건을 비교하고, 조건이 맞으면 결과에 추가합니다.
포인터 비교 과정은 아래와 같습니다.
1. A 테이블과 B 테이블의 첫 번째 행을 가져옵니다.
2. A의 현재 행과 B의 현재 행의 조인키를 비교합니다.
2-1. A의 값이 B의 값보다 작을 경우, A 테이블의 포인터를 다음 행으로 이동시킵니다.
2-2. A의 값이 B의 값보다 클 경우, B 테이블의 포인터를 다음 행으로 이동시킵니다.
2-3. A의 값과 B의 값이 같을 경우, 매칭된 행을 결과에 추가하고 두 포인터를 모두 이동시킵니다.3. 두 테이블의 모든 행을 비교할 때까지 반복합니다.
두 테이블을 정렬된 상태에서 포인터를 이동하며 비교하지만, 중복된 값이 있을 경우 포인터를 고정하고 반복적으로 조합을 만듭니다.
위의 JOIN 알고리즘에서 Nested Loop Join와 Block Nested Loop Join의 경우 인덱스가 있을 경우 비교 테이블을 풀스캔 하지 않고 인덱스를 통해 값을 비교하기 때문에 성능 면에서 유리하다는 것을 알 수 있습니다. (물론 인덱스가 풀스캔에 비해서 유리한 조건일 때만)
😁 ORDER BY와의 관계
그러면 ORDER BY와 인덱스는 무슨 관계가 있을까요?
인덱스는 내부적으로 정렬된 데이터 구조로 저장되게 됩니다. 일반적으로 데이터베이스는 인덱스를 B-Tree 구조로 저장합니다. 이 정렬된 구조 덕분에, 데이터는 인덱스를 사용할 때 이미 정렬된 상태로 접근할 수 있게 됩니다.
예를 들어, A 컬럼에 인덱스가 설정되어있다면, 데이터는 이미 ASC 순서로 정렬된 상태로 저장되므로 추가적인 정렬 작업이 필요 없습니다. 그렇기 때문에 ORDER BY 설정이 된 컬럼의 인덱스가 존재한다면 정렬된 상태를 바로 조회할 수 있어 성능적으로 이점이 있습니다.
DESC 순서의 정렬인 경우 부가적인 작업이 필요합니다.
😁 WHERE과의 관계
WHERE 조건절에서 인덱스를 설정한 컬럼이 있을 경우 인덱스 범위 스캔 또는 인덱스 유일 스캔을 통해서 필요한 조건의 데이터 위치를 바로 조회할 수 있습니다.
즉, 인덱스를 통해 조건에 맞는 데이터를 풀스캔 없이 바로 찾아오기 때문에 성능적으로 이점이 있습니다.
JOIN, WHERE, ORDER BY를 자주 사용하는 컬럼에 인덱스를 걸면 성능적으로 이점을 볼 수 있습니다!
