조인 기법 종류

흔히 Left Join, Inner Join 등 이런 조인은 많이 들어보셨을거다. 하지만, 오늘 다룰 건 데이터베이스 엔진이 실제로 조인을 처리하는 방법 즉, 조인 실행 방식을 다룰 것이다. 단순 Left Join이나 Inner Join처럼 SQL 구문이 아니라, 데이터베이스가 내부적으로 조인을 구현하는 방법인 셈이다.

조인 기법을 알아보기 전에 데이터베이스가 어떻게 쿼리를 처리하는지 알아보자.

1. SQL parser가 request된 쿼리에 대해 문법 확인한다.
2. 쿼리 분할해서 parser tree로 만든다.
3. SQL 옵티마이저가 쿼리를 최적화 결정하여 실행 계획 생성한다.
4. 실행 계획대로 핸들러 API로 스토리지 엔진에 요청한다.
5. 스토리지 엔진이 실행 계획에 따라 요청 사항 수행한다.

여기서 실행 계획을 생성할 때, 옵티마이저(optimizer)는 쿼리를 분석하여 가장 효율적인 실행 방법을 선택한다. 옵티마이저는 다양한 접근 방식을 평가하고 비용 기반 분석을 통해 쿼리를 처리하는 데 드는 리소스를 최소화하는 경로를 선택한다. 이 과정에서 조인 순서, 조인 방식, 인덱스 사용 여부 등을 결정하게 된다.

조인을 처리하기 위한 실행 계획에서는 여러 가지 알고리즘이 사용되며, 이 중 대표적인 3가지 방법이 있다.

• Nested Loop Join
• Hash Join
• Sort Merge Join

옵티마이저가 이 중 어떤 조인 방식을 선택할지는 아래와 같은 요인에 따라 달라진다.

테이블 크기는 어떤가?

• 작은 테이블 간의 조인은 Nested Loop Join이 적합한 경우가 많다. 비교 연산 비용이 적기 때문이다.
• 큰 테이블의 경우 Hash Join이나 Sort Merge Join이 상대적으로 더 나은 성능을 보일 수 있다.

조인 키에 인덱스 유무는?

• 조인 조건의 컬럼에 인덱스가 존재한다면, 데이터 검색 속도가 빨라져 Nested Loop Join의 성능이 크게 향상된다.
• 반면, 인덱스가 없다면 Hash Join이나 Sort Merge Join이 더 적합할 수 있다.

데이터 정렬 여부는?

• 조인에 사용되는 데이터가 이미 정렬되어 있는 경우, 추가적인 정렬 작업이 필요 없으므로 Sort Merge Join이 매우 효율적이다.
• 반대로 데이터가 정렬되지 않았다면, 정렬 작업이 추가로 발생하여 성능에 영향을 줄 수 있다.

메모리 가용성은?

• 충분한 메모리 리소스가 제공되는 환경에서는 Hash Join이 유리하다. 해시 테이블을 메모리에 생성하여 조인 작업을 수행하기 때문이다.
• 그러나 메모리가 부족하면 디스크 I/O가 증가하여 성능 저하가 발생할 수 있다.

쿼리 복잡도와 통계 정보는 어떻게 되는가?

• 옵티마이저는 테이블의 통계 정보(e.g. 행 수, 데이터 분포, 평균/최대 값 등)를 바탕으로 각 조인 방식의 비용(cost)을 계산한다.
• 쿼리가 복잡하거나 데이터 분포가 비대칭적인 경우, 옵티마이저는 비용이 가장 낮은 방식(e.g. Nested Loop Join, Hash Join, Sort Merge Join)을 선택한다.

옵티마이저는 이러한 요인들을 기반으로 최적의 실행 계획을 생성하여 쿼리 성능을 극대화하려고 노력한다. 실제로는 다양한 요인이 얽혀 있어 항상 고정된 결과를 보장하진 않으니, 필요에 따라 힌트나 쿼리 튜닝을 적용하는 것도 고려해야 한다.

이제 각 조인 기법을 알아가보자.

Nested Loop Join

두 테이블을 반복적으로 탐색하여 조인 조건을 만족하는 레코드를 찾는 방법
주로 작은 데이터 세트나 인덱스가 존재하는 경우에 효율적이다.

조인하려는 두 개의 테이블 중 더 작은 테이블을 선행 테이블(outer table)이라 하고 더 큰 테이블을 후행 테이블 (inner table)이라고 한다. 선행 테이블에서 결합 조건에 일치하는 레코드를 후행 테이블에 반복적으로 탐색하며, 조인하는 방식이다. 이 때 선행 테이블(outer table)이 작고, 후행 테이블(inner table)이 커야 효과적이다.

작동 과정

1. 외부 테이블에서 첫 번째 레코드를 선택합니다.
2. 내부 테이블의 모든 레코드를 하나씩 확인하며 조인 조건을 만족하는지 비교합니다.
3. 조건을 만족하는 레코드가 있으면 결과 집합에 추가합니다.
4. 외부 테이블의 다음 레코드로 이동하여 과정을 반복합니다.
5. 외부 테이블의 모든 레코드가 처리되면 종료합니다.

예시 쿼리

SELECT * 
FROM Employees e
JOIN Departments d
ON e.department_id = d.department_id;

• 외부 테이블(Outer Table): Employees
• 내부 테이블(Inner Table): Departments

Employees의 각 레코드에 대해 Departments의 모든 레코드를 순차적으로 비교하여 department_id가 일치하는 레코드를 찾는다.

특징

1. 인덱스는 선택이 아닌 필수!

Nested Loop Join에서 성능을 보장하려면 조인 열에 인덱스가 반드시 존재해야 한다.

작동 원리

Nested Loop Join은 외부 테이블의 각 레코드에 대해 내부 테이블에서 조인 조건을 만족하는 레코드를 탐색한다. 이 과정에서 내부 테이블에 적절한 인덱스가 없다면, 매번 Full Table Scan을 수행하게 된다. 이는 큰 테이블일수록 탐색 비용이 기하급수적으로 증가하는 원인이 된다.

랜덤 액세스 문제

Nested Loop Join은 랜덤 액세스(Random Access)를 기반으로 작동하기 때문에, 내부 테이블을 탐색할 때 디스크 I/O 비용이 발생한다. 랜덤 액세스의 범위를 줄이기 위해 인덱스 구성 전략이 중요하며, 인덱스가 없다면 Sort Merge Join이나 Hash Join과 같은 다른 방식이 더 적합하다.

2. 작은 데이터 규모에 적합하다.

외부 테이블의 크기가 크거나, 내부 테이블의 데이터가 방대하다면 랜덤 액세스 비용이 크게 증가한다. 테이블 크기가 작고, 조인 대상 레코드 수가 적다면 Nested Loop Join은 빠르고 효율적으로 작동한다. 그러나 대량 데이터를 처리할 경우, 처리 시간과 I/O 비용이 급격히 증가할 수 있다.

3. OLTP 시스템에 적합하다.

OLTP는 실시간으로 소량의 데이터를 빠르게 처리한다. 일반적으로 데이터량이 크지 않으며, 다수의 단순 쿼리가 실행된다. 반대로, 대량 데이터를 분석하고 처리하는 OLAP에서는 Hash Join이나 Sort Merge Join과 같은 방식이 더 적합하다.

하지만, 실제 서비스를 개발하다 보면 OLTP 환경에서도 데이터량이 점차 증가하거나, 복잡한 쿼리가 필요해지는 상황이 발생할 수 있다. 이러한 경우 Nested Loop Join이 초기에는 적합했더라도, 데이터의 크기와 쿼리 복잡도가 증가하면서 성능 문제가 나타날 가능성이 있다고 생각한다.

4. 외부 테이블과 내부 테이블 선택 중요하다.

Nested Loop Join의 성능은 외부 테이블과 내부 테이블의 선택에 크게 의존한다.

외부 테이블

• 크기가 작은 테이블을 외부 테이블로 설정하는 것이 효율적이다.
• 외부 테이블이 클수록 반복 횟수가 증가하여 성능이 저하된다.

내부 테이블

• 조인 키에 인덱스가 구성된 테이블을 내부 테이블로 선택해야 성능을 극대화할 수 있다.

위 특징을 바탕으로 장/단점을 간단하게 정리해보자.

장점

• 구현이 쉬워 대부분의 데이터베이스 엔진에서 기본적으로 제공된다.
• 테이블 크기가 작거나 조인 대상이 적은 경우 효율적이다.
• 내부 테이블에 적절한 인덱스가 있으면, 탐색 범위를 줄여 성능을 크게 향상시킬 수 있다.

단점

• 대량 데이터 처리에는 비효율적이다.
• 랜덤 액세스 방식으로 인해 디스크 I/O가 빈번하게 발생한다.
• 내부 테이블에 적절한 인덱스가 없으면 Full Table Scan을 반복적으로 수행하게 되어 성능이 크게 저하된다.

Nested Loop Join를 최적화한다면?

이미 위에서 몇번 반복한 내용이 많지만 그래도 한번 정리해보자.

1. 인덱스를 사용하자.

내부 테이블에 조인 키를 기준으로 인덱스가 존재한다면, 내부 테이블을 전수조사하지 않고 인덱스를 통해 원하는 데이터를 빠르게 검색할 수 있다. 이를 Index Nested Loop Join이라고 부르며, 일반적인 Nested Loop Join에 비해 훨씬 빠른 성능을 보여준다!

2. 작은 테이블을 외부 테이블로 설정하자.

3. 캐싱을 활용하자.
내부 테이블을 메모리에 캐싱하여 디스크 I/O를 줄이면 성능이 개선될 수 있다. 이건 아마도 DBMS 단에서 알아서 버퍼에 적재될 것 같다.

Sort Merge Join

두 테이블을 조인 키를 기준으로 정렬한 뒤, 정렬된 데이터를 병합(Merge)하여 조인하는 방식

주로 대량의 정렬된 데이터 또는 조인 키가 정렬된 인덱스를 가진 경우에 적합하다.

Sort Merge Join은 두 테이블을 조인하기 전에 조인 키를 기준으로 각각 정렬(Sort)하고, 정렬된 데이터를 병합(Merge)하여 조인 조건을 만족하는 레코드를 찾는 방식이다. 정렬된 데이터를 다루기 때문에 효율적이고 대량 데이터를 처리하는 데 자주 사용된다.

작동 과정

Sort Merge Join은 Sort 단계와 Merge 단계로 나뉜다!

1. Sort 단계

조인 대상 테이블 각각을 조인 키를 기준으로 정렬한다.

• 조인 키에 정렬된 인덱스가 없는 경우, 정렬 작업을 수행해야 하며 이 과정에서 많은 I/O와 CPU 리소스가 사용된다.
• 만약 조인 키에 이미 정렬된 인덱스가 존재하면, 정렬 없이 바로 Merge 단계로 넘어간다.

2. Merge 단계

정렬된 두 테이블의 데이터를 하나씩 읽으면서 조인 키를 비교하여 병합한다.

• 조인 키가 동일한 레코드를 결과 집합에 추가한다.
• 조인 키가 일치하지 않으면, 정렬 순서에 따라 다음 레코드를 읽으며 병합 작업을 이어간다.

3. 결과 생성

예시 쿼리

SELECT *
FROM Orders o
JOIN Customers c
ON o.customer_id = c.customer_id;

Sort 단계

Orders와 Customers 테이블을 각각 customer_id를 기준으로 정렬한다.

Merge 단계

정렬된 두 테이블의 데이터를 순차적으로 비교하여 customer_id가 동일한 레코드를 병합(Merge)한다.

특징

1. 정렬 작업이 필요하다.

Sort Merge Join은 조인을 수행하기 전에 테이블을 조인 키 기준으로 정렬해야 한다.

• 조인 키에 정렬된 인덱스가 없는 경우, 정렬 작업으로 인해 높은 CPU와 I/O 비용이 발생한다.
• 정렬된 인덱스가 존재하면 정렬 작업을 생략할 수 있어 성능이 크게 향상된다.
• 정렬 작업은 테이블 크기가 클수록 더 많은 리소스를 소모하므로, 가능한 정렬 작업을 줄이는 것이 중요하다.

2. 대량 데이터 처리에 적합하다.

Sort Merge Join은 정렬된 데이터를 병합하기 때문에 데이터 크기가 커도 상대적으로 높은 성능을 보여준다.

• 대량 데이터를 효율적으로 처리하고 M:N 관계의 조인에서도 안정적인 성능을 보장한다.
• 정렬 작업을 제외하면 병합(Merge) 작업은 순차적으로 진행되므로 랜덤 액세스가 필요 없으며, I/O 비용이 낮다.
• 테이블 크기가 큰 경우에도 한 번의 정렬로 효율적인 조인이 가능하다.

3. 정렬된 인덱스가 있으면 성능이 크게 향상된다.

조인 키에 정렬된 인덱스가 있으면, 정렬 작업 없이 병합 작업만 수행하므로 큰 성능 향상을 기대할 수 있다. 테이블에 이미 조인 키 기반의 클러스터드 인덱스 또는 정렬된 데이터가 존재할 경우, Sort Merge Join이 가장 효율적인 방식이 된다. 하지만? 클러스터 인덱스가 아닌 넌클러스터 인덱스를 사용할 경우 Lookup 비용이 발생할 수 있어 이를 고려해야 한다.

4. OLAP 시스템에 적합하다.

OLAP 환경에서는 정렬된 데이터를 다루는 경우가 많아, 추가적인 정렬 비용 없이 빠르게 조인을 수행할 수 있다.거기에 데이터를 스캔 방식으로 처리하므로, 대량 데이터 처리에서도 안정적인 성능을 보여준다.

5. Nested Loop Join과 Hash Join의 단점을 보완한다.

Nested Loop Join의 단점 보완

Merge Join은 Nested Loop Join의 랜덤 액세스 방식의 비효율을 줄이기 위해 고안된 방식이다. Inner Table을 반복적으로 탐색하는 Nested Loop Join과 달리, Sort Merge Join은 두 테이블을 한 번씩 읽고 정렬 후 비교하므로 랜덤 액세스 비용이 없다.

Hash Join의 단점 보완

Hash Join은 정렬된 결과를 요구하는 경우 적합하지 않으며, 메모리 제약이 있을 경우 성능이 저하된다. 반면, Sort Merge Join은 정렬된 데이터를 요구하는 상황이나 메모리 제약 상황에서도 효율적이다.

6. 정렬 작업은 비용이 많이 들 수 있다.

조인 키에 정렬된 인덱스가 없는 경우, 테이블을 정렬하는 작업에 많은 리소스가 소모될 수 있다.

• 정렬 작업 중 메모리가 부족하면 디스크를 사용하게 되어 디스크 I/O 비용이 크게 증가한다.
• 특히 대용량 테이블의 경우, 정렬 작업이 성능 병목으로 작용할 수 있다.
• 이러한 문제를 피하기 위해 조인 키에 인덱스 생성을 고려해야 하며, 인덱스가 없으면 추가적인 튜닝이 필요하다.

7. 스캔 방식을 사용한다.

Sort Merge Join은 Nested Loop Join의 랜덤 액세스 방식과 달리 순차적인 스캔 방식을 사용한다.

• 두 테이블을 정렬한 뒤 순차적으로 스캔하므로 랜덤 액세스가 필요 없다.
• 각 테이블을 한 번만 읽기 때문에, 테이블 크기가 큰 경우에도 효율적으로 작동한다.
• 인덱스를 사용하지 않으며, 정렬된 데이터 스캔을 통해 조인을 수행한다.

8. 동등 조건(=)이 필요하다.

조인 조건에는 동등 조건(=)이 반드시 포함되어야 한다.

• '=' 조건은 두 테이블의 조인 키 값이 정확히 일치하는 행을 쉽게 찾도록 도와준다.
• 비동등 조건(<, >, !=)이 사용되면 정렬된 순서를 활용하기 어려워 성능이 저하된다.
• 언제나 예외는 있는 법..! FULL OUTER JOIN의 경우 '=' 조건 없이도 사용할 수 있다.
  • FULL OUTER JOIN은 조인 키 조건을 적용하지 않고도 남아있는 데이터까지 반환하기 때문이다.

9. 중복 데이터 처리가 필요하다.

중복 값이 많은 경우, Sort Merge Join에서 중복 데이터를 제거하는 과정에서 많은 비용이 발생할 수 있다.

• 중복 데이터를 처리하기 위해 메모리에서 임시 테이블을 생성하게 되며, 이로 인해 리소스 사용량이 증가할 수 있다.
• 중복 데이터를 줄이기 위해 UNIQUE INDEX를 생성하거나, GROUP BY를 사용하는 것이 좋다.
• 중복 데이터는 M:N 관계에서 특히 성능에 영향을 미치므로 이를 사전에 처리하는 것이 중요하다.

위 특징을 장/단점으로 정리해보자!

장점

• 정렬된 데이터를 병합하기 때문에 대량 데이터 처리에 효율적이다.
• Nested Loop Join과 Hash Join의 단점을 보완하며, 정렬된 결과를 요구하는 상황에서 특히 적합하다.
• 조인 키에 정렬된 인덱스가 존재하면, 정렬 작업을 생략하여 매우 높은 성능을 제공한다.
• OLAP 시스템처럼 대규모 데이터를 다루는 환경에서 안정적이고 높은 성능을 보인다.
• 순차적인 스캔 방식으로 I/O 비용을 줄이고, 대규모 데이터를 효율적으로 처리한다.
• 조인 후 정렬된 결과를 바로 제공할 수 있다.

단점

• 조인 키에 정렬된 인덱스가 없으면 정렬 작업으로 인해 높은 CPU와 I/O 비용이 발생한다.
• 대용량 테이블의 경우, 정렬 작업이 병목으로 작용할 수 있다.
• 중복 데이터가 많은 경우, 이를 처리하는 데 추가 비용이 발생할 수 있다.
• 비동등 조건(<, >, !=)을 사용할 경우 정렬된 순서를 활용하기 어려워 성능이 저하된다.
• FULL OUTER JOIN을 제외한 경우, 동등 조건(=)이 반드시 필요하다.

Sort Merge Join를 최적화한다면?

1. 조인 키에 정렬된 인덱스를 사용하자.

조인 키에 정렬된 인덱스가 있으면, 정렬 작업 없이 바로 병합 작업으로 넘어갈 수 있다. 이는 CPU와 I/O 비용을 크게 줄이며, Sort Merge Join의 성능을 극대화할 수 있다.

2. 정렬 작업을 최소화하자.

테이블 크기가 크거나 조인 키에 인덱스가 없는 경우, 정렬 작업이 병목이 될 수 있다. 데이터를 조인 전에 미리 정렬하거나, 데이터를 샤딩 및 파티셔닝하여 정렬 작업의 범위를 줄이는 것이 중요하다.

3. 중복 데이터를 사전에 처리하자.

중복 값이 많은 경우 임시 테이블 생성 비용이 증가하므로, 중복 데이터를 줄이기 위해 UNIQUE INDEX를 생성하거나, GROUP BY를 사용하는 것을 고려하자.

4. 스캔 방식을 활용하자.

NL 조인의 랜덤 액세스 방식과 달리, 정렬된 데이터를 순차적으로 읽는 스캔 방식은 I/O 비용을 줄이고 효율적인 처리가 가능하다.

5. 동등 조건을 사용하자.

조인 키에 동등 조건(=)을 사용하는 것이 Sort Merge Join의 성능을 높이는 데 중요하다. 비동등 조건은 성능 저하를 초래할 수 있으므로, 필요 시 다른 조인 방식과 병행 사용을 고려하자.

6. 병렬 처리를 활용하자.

병렬 처리를 활성화하여 정렬 및 병합 작업을 여러 프로세스에서 나누어 처리하면 대량 데이터를 더 빠르게 처리할 수 있다.

이 방식이 효율적이지만 조건이 맞아야 최적의 성능을 발휘하는 게 좋겠쥬?

Hash Join

해시 테이블을 사용하여 두 테이블 간의 조인 조건을 효율적으로 처리하는 방식

주로 대량의 데이터 세트나 인덱스가 없는 경우에 효율적이다.

Hash Join은 조인을 수행하기 위해 두 테이블 중 하나를 메모리에 로드하고, 해당 테이블의 데이터를 해시 테이블(Hash Table)로 변환한다. 이후 다른 테이블의 데이터를 하나씩 탐색하며 해시 테이블과 매칭하여 조인 조건을 만족하는 레코드를 찾는다. 이 방식은 테이블 크기가 크거나, 조인 키에 인덱스가 없는 경우 특히 효과적이다.

작동 과정

Hash Join은 Build 단계와 Probe 단계로 나뉜다.

1. Build 단계

두 테이블 중 상대적으로 작은 테이블을 메모리에 로드한다. (이를 Build Input이라고 부른다.)

Build Input의 데이터를 조인 키를 기준으로 해시 테이블(Hash Table)로 변환한다.

• 각 레코드는 조인 키를 기반으로 해시 함수(Hash Function)를 통해 특정 버킷(Bucket)에 저장된다.
• 해시 테이블은 빠르게 검색할 수 있도록 최적화된 구조를 갖는다.
• 이 과정은 메모리를 많이 사용하므로, Build Input 테이블 크기가 메모리에 넉넉해야한다.

2. Probe 단계

상대적으로 큰 테이블을 Probe Input이라고 부르며, 이 테이블의 각 레코드를 순차적으로 탐색한다.

Probe Input의 레코드에서 조인 키를 추출하고, 동일한 해시 함수를 사용해 해시 테이블에서 매칭되는 레코드를 찾는다.

• 매칭된 레코드가 있으면 결과 집합에 추가한다.
• 매칭되지 않으면 해당 레코드는 무시된다.

3. 결과 생성

예시 쿼리

SELECT *
FROM Orders o
JOIN Customers c
ON o.customer_id = c.customer_id;

Build 단계

Customers 테이블을 메모리에 로드하고 customer_id를 기준으로 해시 테이블 생성한다.

Probe 단계

Orders 테이블의 각 레코드를 읽으면서 customer_id를 기준으로 해시 테이블에서 매칭한다.

특징

1. 메모리 활용이 필수적이다.

Hash Join은 해시 테이블을 메모리에 생성하기 때문에 충분한 메모리 리소스가 필요하다.

• 작은 테이블(주로 Build 단계의 테이블)을 메모리에 올려 해시 테이블을 생성한다.
• 해시 테이블은 Hash Bucket(해시 버킷)으로 구성되며, 각 조인 키는 해시 함수(Hash Function)를 사용해 적절한 버킷에 매핑된다.

만약 메모리가 부족하면, 데이터를 여러 파티션으로 나누어 디스크 기반으로 처리하는 Partitioned Hash Join이 수행되며, 이는 디스크 I/O 비용을 증가시켜 성능이 저하될 수 있다.

2. 대량 데이터 처리에 적합하다.

Hash Join은 데이터가 정렬되지 않아도 효율적으로 작동하며, 특히 대량 데이터를 처리하는 데 적합하다.

• Sort Merge Join처럼 정렬 작업이 필요 없고, Nested Loop Join처럼 반복적인 탐색 작업을 최소화 할 수 있다.
• 해시 함수와 해시 테이블을 사용해 데이터를 빠르게 매칭할 수 있기 때문에, 테이블 크기가 큰 경우에도 상대적으로 높은 성능을 보여준다.
• M:N 관계의 조인에서도 성능이 뛰어나며, 조인 대상 테이블에 인덱스가 없거나 테이블 크기가 매우 클 때 특히 유리하다.

3. 조인 키에 인덱스가 없어도 효율적이다.

해시 함수(Hash Function)를 사용해 조인 키를 해시 테이블에 저장하고, Probe 단계에서 입력 데이터를 비교하기 때문에, 내부 테이블에 인덱스가 없는 경우에도 Full Table Scan을 최소화할 수 있다. Nested Loop Join과 달리, 조인 키에 인덱스가 없어도 해시 테이블을 활용하여 빠르게 매칭 작업을 수행한다.

4. OLAP 시스템에 적합하다.

OLAP 시스템에서는 정렬되지 않은 대량 데이터를 처리하거나 분석하는 경우가 많다. 해시 테이블을 사용하면 정렬 작업 없이 빠르게 데이터를 매칭할 수 있으며, 데이터의 크기가 커도 상대적으로 성능 저하가 적다. 또한, 해시 테이블은 병렬 처리를 지원하기 때문에, 여러 프로세스를 활용하여 대규모 데이터를 효과적으로 조인할 수 있다.

5. Merge Join과 Nested Loop Join의 단점을 보완한다.

Merge Join은 테이블 크기가 크거나 정렬 작업이 필요한 경우 성능이 저하될 수 있지만, Hash Join은 정렬 없이 빠르게 작동한다. Nested Loop Join은 테이블 크기가 크거나, 조인 키에 인덱스가 없을 경우 성능이 크게 저하되는데, Hash Join은 인덱스가 없어도 효율적으로 데이터를 매칭할 수 있다. 특히, 테이블 간 관계가 M:N으로 복잡하거나, 조인 결과 정렬이 필요 없는 경우 Hash Join은 더 나은 성능을 보여준다.

6. 해시 충돌로 인해 성능 저하가 발생할 수 있다.

Hash Join의 성능은 해시 함수의 품질에 크게 의존할 수 밖에 없다.

동일한 해시 값을 가진 여러 레코드가 동일한 해시 버킷(Hash Bucket)에 저장되며, 이를 해시 충돌이라고 하는데 충돌이 발생하면 동일한 버킷 내에서 추가적인 탐색 작업(체인 처리)이 필요하므로 성능이 저하될 수 있다. 데이터베이스 엔진은 충돌을 최소화하기 위해 최적화된 해시 함수를 사용하지만, 데이터 분포가 불균형하거나 편중되어 있는 경우 충돌이 많아질 수 있다.

7. 생성된 해시 테이블은 일회용이다.

조인 작업이 끝나면 해시 테이블은 메모리에서 삭제되므로, 동일한 데이터에 대해 반복적으로 조인 작업을 수행해야 한다면 추가적인 작업이 필요하다. 메모리와 디스크 I/O 리소스를 많이 사용하는 환경에서 성능 최적화를 위해 고려해야 할 사항이다.

위 특징을 바탕으로 장/단점을 간단하게 정리해보자.

장점

• 데이터 정렬이 필요하지 않아 Sort Merge Join보다 효율적이다.
• 대량 데이터 처리에 최적화되어 있으며, M:N 관계의 조인에서도 성능이 뛰어나다.
• 조인 키에 인덱스가 없어도 해시 테이블을 활용해 빠르게 조인 작업을 수행할 수 있다.
• OLAP 시스템과 같은 대규모 데이터 분석 환경에서 높은 성능을 제공한다.
• Nested Loop Join처럼 반복 탐색을 최소화하여 상대적으로 빠른 성능을 보여준다.
• 병렬 처리를 지원해 대규모 데이터를 효과적으로 처리할 수 있다.

단점

• 해시 테이블을 메모리에 생성하므로 메모리 의존성이 높으며, 메모리가 부족할 경우 성능 저하가 발생한다.
• 동일한 해시 값을 가진 레코드가 많을 경우 해시 충돌이 발생해 성능이 저하될 수 있다.
• Partitioned Hash Join이 수행될 경우 디스크 I/O 비용이 증가하여 처리 속도가 느려질 수 있다.
• 생성된 해시 테이블은 일회용으로, 동일한 데이터를 반복적으로 사용할 경우 추가적인 리소스가 필요하다.
• 데이터 분포가 불균형할 경우 일부 해시 버킷에 데이터가 몰리면서 성능 저하가 발생할 수 있다.

Hash Join를 최적화한다면?

1. 작은 테이블을 Build Input으로 설정하자.

해시 테이블은 Build 단계에서 생성되며 메모리에 적재되기 때문에, 상대적으로 작은 테이블을 Build Input으로 설정하는 것이 중요하다. 이렇게 하면 메모리 사용량을 줄이고, 디스크 I/O를 최소화할 수 있다.

2. 충분한 메모리를 확보하자.

Hash Join은 메모리 의존적인 알고리즘이다. 메모리가 부족하면 Partitioned Hash Join이 수행되며, 이는 디스크 I/O 비용을 증가시켜 성능 저하가 발생할 수 있다. 따라서, 충분한 메모리 리소스를 확보하거나 서버의 메모리 구성을 최적화하자.

3. 해시 함수의 품질을 개선하자.

해시 충돌이 발생하면 동일한 해시 버킷 내에서 추가적인 탐색 작업이 필요하다. 데이터베이스 엔진이 사용하는 해시 함수가 데이터 특성에 적합한지 확인하고, 데이터 분포를 분석하여 충돌 가능성을 줄이는 최적화된 해시 함수를 사용하는 것이 중요하다.

4. 데이터 분포를 고르게 유지하자.

조인 키의 데이터 분포가 불균형하면 특정 해시 버킷에 데이터가 몰리면서 성능 저하가 발생할 수 있다. 데이터 정규화 또는 조인 키 설계 개선을 통해 데이터 분포를 균일하게 만드는 것이 중요하다.

5. 조인 대상 데이터를 사전에 필터링하자.

조인 전에 WHERE 조건이나 ON 조건을 활용해 불필요한 데이터를 제거하면, 해시 테이블의 크기를 줄이고 처리 속도를 높일 수 있다.

6. 병렬 처리를 활용하자.

Hash Join은 병렬 처리가 가능한 알고리즘이다. 여러 프로세스를 활용해 해시 테이블 생성과 탐색 작업을 분산 처리하면, 대량 데이터를 조인하는 데 있어 큰 성능 향상을 기대할 수 있다.

7. 파티셔닝 전략을 활용하자.

테이블 크기가 너무 커서 메모리에 적재하기 어려운 경우, 데이터를 파티셔닝하여 처리 범위를 나눌 수 있다. Partitioned Hash Join을 활용하면 메모리 사용량을 줄일 수 있지만, 디스크 I/O 비용이 증가할 수 있으므로 적절히 사용해야 한다.

8. 캐싱을 활용하자.

같은 데이터를 반복적으로 사용하는 경우, 조인 결과를 캐싱하여 불필요한 해시 테이블 생성 및 탐색 작업을 줄일 수 있다. 캐싱된 결과를 재활용하면 리소스 소모를 최소화할 수 있다.

9. 디스크 I/O를 최소화하자.

조인 전 데이터를 정렬하거나 테이블의 블록 읽기 순서를 최적화하면, 디스크 I/O를 줄이고 성능을 향상시킬 수 있다. 이를 위해 테이블 설계와 파일 시스템 튜닝을 고려하자.

간단 요약

GPT에게 정리한 내용을 요약해달라고 부탁해봤다.

각 조인 방식의 상세 종류도 정리하고 싶었지만, 데이터베이스마다 지원하는 기법이 달라 따로 정리하지 않았다. 다음엔 각 조인 기법을 최적화하는 글로 찾아오겠다. 빠잉.

출처

https://ryean.tistory.com/73
https://kimsj.dev/blog/mysql-nestedloopjoin-hashjoin/
RealMySQL 서적
내 머리