[DB] 조인의 원리

💡 옵티마이저는 사용자가 질의한 SQL문에 대해 최적의 실행 방법(실행 계획)을 결정하는 역할을 수행합니다. 동일한 SQL 문에 대해 처리하는 방법에 따라 실행 시간은 다를 수 있기 때문에 옵티마이저는 그 중에서 가장 효율적인 방법을 찾아줍니다. 이때, 옵티마이저가 결정하는 실행 계획 중 하나가 조인 원리 입니다.

 

중첩 루프 조인(Nested Loop Join)

프로그래밍에서의 중첩 for 문과 같은 원리로, 조건에 맞는 조인을 하는 방법입니다.

• 한 레코드씩 순차적으로 처리합니다.
• 반복문의 외부에 있는 테이블을 선행 테이블/외부 테이블/드라이빙 테이블 이라 합니다.
• 반복문 내부에 있는 테이블을 후행 테이블/내부 테이블/드리븐 테이블 이라고 합니다.
• 후행 테이블에는 조인을 위한 인덱스 생성이 필요합니다.

동작 방식

1. 선행 테이블에서 주어진 조건을 만족하는 행을 찾습니다. (WHERE)
   -> 맞는 조건이 아니면 필터링 됩니다.
2. 선행 테이블의 조인 키 값을 가지고 후행 테이블에서 조인을 수행합니다.
3. 후행 테이블의 인덱스에 선행 테이블의 조인 키가 존재하는 지 확인합니다.
   -> 조인 키가 존재하지 않으면 선행 테이블 데이터는 필터링 됩니다.
4. 인덱스에서 추출한 레코드 식별자를 이용하여 후행 테이블을 액세스 합니다.
   -> 인덱스 스캔을 통해 테이블 액세스를 수행합니다.
5. 조인 수행 후 해당 행을 추출 버퍼에 넣습니다.
6. 앞의 작업을 반복 수행합니다.

** 추출 버퍼: SQL문의 실행 결과를 보관하는 버퍼로서, 일정 크기를 설정하여 추출 버퍼에 결과가 모두 차거나 더 이상 결과가 없어서 추출 버퍼를 채울 것이 없으면 결과를 사용자에게 반환 합니다.

 

장점

• 조인이 성공하면 조인 결과를 바로 사용자에게 보여줄 수 있습니다.
• 메모리 사용량은 가장 적습니다.
• 인덱스에 의한 랜덤 액세스에 기반하고 있기 때문에 좁은 범위에 유리한 성능을 보여줍니다.
• 소량의 데이터를 주로 처리하거나 부분 범위 처리가 가능한 온라인 트랜잭션 환경에 적합한 조인 방식입니다.

단점

• 대량의 데이터 처리 시 랜덤 액세스에 대한 비용이 많이 증가해서 적합하지 않습니다.
• Join Index가 없거나 검색 조건이 조인 범위를 줄이지 못할 경우 비효율적입니다.

성능 개선 방법

1. 적절한 드라이빙 테이블의 선정
   • 먼저 읽은 테이블의 행의 수만큼 join이 수행되기 때문에, 일반적으로 행의 수가 적은 테이블을 선행 테이블로 선택합니다.
     • 선행 테이블은 옵티마이저의 최적의 실행 계획에 따라 결정됩니다.
     • 단, Outer Join은 Outer가 되는 테이블을 먼저 읽어야 하기 때문에 옵티마이저가 조인 순서를 결정하지 않습니다.
   • 힌트를 사용하여 조인 순서를 결정할 수 있습니다.

   /*+ORDERED*/ -- FROM절에 기술한 테이블 순서대로 제어
   /*+LEADING (table명)*/ -- 힌트 내에 제시된 테이블이 드라이빙으로 처리됨
   

   • 뷰를 사용하여 조인 순서를 결정할 수 있습니다.
     • 뷰를 통해서 데이터를 먼저 읽어낼 수 있고, 뷰로 데이터를 읽은 결과로 다음 테이블로 연결을 시도하면 조인 순서를 제어할 수 있습니다.
2. Driven Table의 조인 컬럼에 인덱스 존재 유무
   • Driven Table에 인덱스가 존재하지 않는다면 Driving Table에서 도출된 결과와 맞는 지를 FULL TABLE SCAN으로 일일이 비교해야 합니다.
   • 효율적인 인덱스를 선정하지 못하면 비효율적으로 수행될 수 있습니다.

블록 중첩 루프 조인(Block Nested Loop)

조인할 테이블을 작은 블록으로 나눠서 블록 하나씩 조인하는 방법입니다.

• 기존의 중첩 루프 조인을 개선한 방식입니다.
• 조건에 맞는 선행 테이블을 페이징 해서 조인 버퍼에 저장한 후에 후행 테이블을 스캔하면서 조인 버퍼를 탐색하는 방식입니다.
• 후행 테이블의 스캔 횟수를 줄일 수 있습니다.+) ex - Driving 테이블 결과 집합: 1000행BNL 조인을 사용하면 100개 행 집합을 비교한다면 Driving 테이블 결과를 조인 버퍼에 설정하고 저장한 다음 Driven 테이블의 각 데이터 행을 사용하여 100개 행의 결과 집합과 비교하므로 한번에 100개의 데이터 행과 비교할 수 있어 1000/100 = 10회로 루프 순환
• Driven 테이블은 NL 조인 알고리즘을 사용하면 1000번 스캔
• +) Driving 테이블의 결과를 조인 버퍼에 저장하고 메모리 루프의 각 데이터 행을 전체 버퍼의 레코드와 비교하여 내부 루프의 스캔 횟수를 줄일 수 있습니다.
• NL Join보다는 빠르지만 Sort Merge Join이나 Hash Join에 비해 느리기 때문에 근본적인 해결책은 아닙니다.

정렬 병합 조인(Sort Merge Join)

각각의 테이블을 조인할 필드 기준으로 정렬하고, 정렬이 끝난 이후에 조인 작업을 수행하는 방법입니다.

• Full Table Scan 방식으로 데이터를 읽는 기법입니다.

동작 방식

1. 선행 테이블에서 주어진 조건을 만족하는 행을 찾습니다.
2. 해당 행들에 대해서 선행 테이블의 조인 키를 기준으로 데이터를 정렬합니다.
   1. 이미 앞 단계에서 정렬 작업이 수행되었다면 정렬 작업은 발생하지 않을 수 있습니다.
3. 후행 테이블에서 주어진 조건을 만족하는 행을 찾습니다.
4. 해당 행들에 대해서 후행 테이블의 조인 키를 기준으로 데이터를 정렬합니다.
5. JOIN을 수행합니다.
6. 성공하면 추출 버퍼에 넣습니다

사용하는 경우

• 조인할 때 쓸 인덱스가 전혀 없는 경우
• 대용량의 자료를 조인할 때 유리한 경우
• 조인 조건으로 범위 연산자가 사용되는 경우
• 인덱스 사용에 따른 랜덤 액세스의 오버 헤드가 많은 경우

장점

• 동등 조인, 비 동등 조인에서 모두 가능합니다.

단점

• 정렬할 데이터가 많아 메모리에서 모든 정렬 작업을 수행하기 어려운 경우에는 임시 영역(디스크)를 사용하기 때문에 성능이 떨어질 수 있습니다.

성능 개선 방법

1. ACCESS 하는 속도 향상
   • FULL TABLE SCAN, INDEX RANGE SCAN 등 테이블을 ACCESS하는 방법을 다양한 방법을 통해 최적화 하여 속도를 향상 시킵니다.
2. 정렬 속도의 향상
   • 조인 조건 칼럼이 이미 정렬되어 있다면 정렬 작업 시간을 단축 시켜 속도를 향상시킬 수 있습니다.
3. 정렬 속도를 맞춤
   • 두 테이블의 정렬 속도를 맞추면, 한쪽이 대기할 필요 없이 조인을 시작할 수 있습니다.
4. SORT_AREA_SIZE 최적화
   • SORT_AREA_SIZE(정렬 공간 크기)를 적절한 크기로 설정하면 Temporary Table Space(메모리가 부족하면 사용)를 사용할 필요가 없으므로 속도 향상에 도움이 됩니다.

해시 조인

해시 테이블을 기반으로 조인하는 방법입니다. 조인될 두 테이블 중 한 테이블을 해시 테이블로 선정해서 조인 키값을 해시 알고리즘으로 비교하여 매치되는 결과값을 얻는 방식입니다.

동작 방식

1. 빌드 단계
   1. 입력 테이블 중 하나를 기반으로 메모리 내 해시 테이블을 빌드하는 단계입니다.
   2. 두 테이블 중 바이트가 더 작은 테이블(Build Input)을 기반으로 Hash Area에 해시 테이블을 빌드합니다.
   3. 조인에 사용하는 필드가 해시 테이블의 키로 사용됩니다.
   ** 해시 테이블은 DBMS의 워킹 메모리에 저장되므로 작은 것이 효율적입니다.
2. 프로브 단계
   1. 다른 큰 집합(Probe Input)을 읽어 해시 테이블을 탐색하면서 JOIN 합니다.
   2. 해시 함수에서 리턴 받은 버킷 주소로 찾아가 해시 체인을 스캔하면서 데이터를 찾습니다.

사용하는 경우

• JOIN 칼럼에 적당한 인덱스가 없는 경우
• JOIN Access량이 많은 경우
• 두 테이블이 너무 커 Sort Merge Join을 할 때 Sort 부하가 심할 경우
• 수행 빈도가 낮고, 쿼리 수행 시간이 오래 걸리는 대용량 테이블을 JOIN 하는 경우

장점

• 각 테이블은 한 번씩만 읽게 되어 중첩해서 두 개의 테이블을 읽는 중첩 루프 조인보다 성능이 더 좋습니다.
• 두 개의 테이블을 조인한다고 했을 때, 하나의 테이블이 메모리에 온전히 들어간다면 보통 중첩 루프 조인보다 더 효율적입니다.
• 사용 가능한 메모리 양은 시스템 변수 join_buffer_size에 의해 제어되며 런타임시에 조정할 수 있습니다.

단점

• 초기에 해시 테이블을 생성해야 해서, 중첩 루프 조인에 비해 소비하는 메모리 양이 많습니다.
• 해시함수를 사용하기 때문에 동등 조인에서만 사용할 수 있습니다.

성능 개선 방법

1. HASH TABLE을 만드는 과정 효율화
   • HASH TABLE로 만들 Build Input이 Hash Area가 담길 정도로 충분히 작아야 하고, Build Input의 해시 키 칼럼에 중복 값이 거의 없으면 효율적인 동작을 기대할 수 있습니다.
2. CPU 성능 향상
   • HASH BUCKET이 조인 집합에 구성되어 해시 함수 결과를 저장하는데, 이때 기본적으로 HASH_AREA_SIZE에 지정된 크기만큼의 메모리를 할당합니다. 이러한 처리에는 많은 메모리와 CPU 자원을 소모하므로 CPU 성능을 향상시키면 해시 조인 성능을 향상시킬 수 있습니다.
3. 충분한 PGA 메모리 확보
   • Hash Area를 할당할 만큼 충분한 PGA 메모리를 확보해야 합니다.
   • Hash Area는 PGA 메모리에 할당되는데 Build Input이 HASH_AREA_SIZE를 초기화 하게 되면, 가장 큰 순서대로 HASH BUCKET이 Temporary Table Space로 내려가서 구성됩니다. 디스크로 내려간 Hash Bucket에 변경이 일어날 때마다 디스크 I/O가 발생하면 성능이 저하됩니다.

** MS-SQL, Oracle: NL 조인, 해시 조인, 머지 조인 지원

** MySQL: NL Join만을 지원했다가, BN 조인이 중간에 도입 → MySQL 8.0.18부터 해시조인 지원하고, BN 조인은 더 이상 사용되지 않음