서론
RDBMS에서는두 개이 상의 테이블을 결합하여 하나의 결과의 집합을 만들때 조인 알고리즘을 사용하게된다. 이러한 조인 알고리즘은 대부분의 주요 관계형 데이터베이스(RDBMS)에서 사용되는 일반적인 알고리즘이다.
왜 알아야하는가?
RDBMS는 옵티마이저라는 핵심 엔진이 있다. 옵티마이저는 SQL문을 수행할 최적의 처리 경로를 생성해주는 엔진이다.
이에 따라 옵티마이저는 SQL문에 대한 실행 계획을 세운 뒤 시스템 통계 정보를 활용하여 각 실행 계획의 예상 비용을 산정한 후 각 실행계획을 비교해서 최고의 효율을 가지는 쿼리를 수행한다! 이 실행 계획에서는 옵티마이저가 사용할 조인 알고리즘을 보여준다. 하지만, 주의할 점이 있다. 옵티마이저의 성능은 점차 향상되고 있지만 결코 만능은 아니다. 따라서, 우리는 RDBMS의 동작 원리와 옵티마이저가 제공하는 실행 계획을 이해하고 있어야 한다. 이렇게 함으로써, SQL 쿼리의 성능 문제를 분석하고 해결하는 데 필요한 지식을 얻을 수 있다. 특히, 대용량 데이터베이스 환경에서는 효율적인 조인 전략이 전체 시스템 성능에 큰 영향을 미칠 수 있다.
NL Join(Nested Loops Join) 수행 원리
1. 선행 테이블에서 조건을 만족하는 첫 번째 행을 찾음 → 이때 선행 테이블에 주어진 조건을 만족하지 않는 경우 해당 데이터는 필터링 된다.
2. 선행 테이블의 조인 키를 가지고 후행 테이블에 조인 키가 존재하는지 찾으러 감 → 조인 시도
3. 후행 테이블의 인덱스에 선행 테이블의 조인 키가 존재하는지 확인 → 선행 테이블의 조인 값이 후행 테이블에 존재하지 않으면 선행 테이블 데이터는 필터링 됨 (더 이상 조인 작업을 진행할 필요 없음)
4. 인덱스에서 추출한 레코드 식별자를 이용하여 후행 테이블을 액세스 → 후행 테이블에 주어진 조건까지 모두 만족하면 해당 행을 추출버퍼에 넣음.
5 ~ 11. 앞의 작업을 반복 수행.
- NL 조인(Join)은 프로그래밍 언어에서 사용하는 중첩된 반복문과 유사한 방식으로 조인을 수행한다.
- NL Join의 가장 큰 특징은 랜덤 액세스(Random Access) 방식으로 데이터 읽는다는 것이다. 그리고 랜덤 액세스의 예로는 인덱스 스캔(Index Scan)이 있다. 즉, 인덱스 스캔(Index Scan)은 NL Join 방식으로 조인을 수행한다. 추가적으로 대량의 데이터를 랜덤 액세스로 접근하게 되면 많은 I/O가 발생하여 성능상 좋지 않기 때문에 무조건 랜덤 액세스가 좋은 게 아님을 인지
- NL Join 기법은 조인이 성공하면 바로 조인 결과를 사용자에게 보여 줌. 따라서 결과를 가능한 한 빨리 화면에 보여줘야 하는 온라인 프로그램에 적당한 조인 기법이다.
- NL Join 이외의 Sort Merge Join과 Hash Join은 조인 칼럼의 인덱스(Index)가 없어도 사용 가능하며, 메모리에 적재할 수 있는 크기보다 더 커지면 임시 영역(디스크)을 사용한다는 특징이 있다.
Sort Merge Join 수행 원리
1. 선행 테이블에서 주어진 조건을 만족하는 행을 찾는다.
2. 해당 행들에 대해서, 선행 테이블의 조인 키(칼럼)를 기준으로 데이터를 정렬.
3. 후행 테이블에서 주어진 조건을 만족하는 행을 찾는다.
4. 해당 행들에 대해서, 후행 테이블의 조인 키(칼럼)를 기준으로 데이터를 정렬.
5. JOIN을 수행.
6. 조인에 성공하면 추출버퍼에 넣는다.
- Sort Merge Join은 NL Join에서의 랜덤 액세스로는 부담이 되던 넓은 범위의 데이터를 처리할 때 이용되던 조인 기법으로, 주로 Full Table Scan 방식으로 데이터를 읽는 기법이다. 정리하자면, Sort Merge Join은 조인 칼럼의 인덱스가 존재하지 않을 경우에도 사용할 수 있는 특징이 있다.
- 이처럼 Sort Merge Join은 조인 칼럼을 기준으로 데이터를 정렬한 후 조인을 수행한다는 특징이 있지만, 조인 작업을 위해 항상 정렬 작업이 발생하는 것은 아니다. 예를 들어, 조인할 테이블 중에서 이미 앞 단계의 작업을 수행하는 도중에 정렬 작업이 미리 수행되었다면 조인을 위한 정렬 작업은 발생하지 않을 수 있다.
- 정렬할 데이터가 많아 메모리에서 모든 정렬 작업을 수행하기 어려운 경우에는 임시 영역(디스크)을 사용하기 때문에 성능이 떨어질 수 있다. 그래서 일반적으로 대량의 조인 작업에서 정렬 작업을 필요로 하는 Sort Merge Join 보다는 CPU 작업 위주로 처리하는 Hash Join이 성능상 유리하다.
- Sort Merge Join은 Hash Join과는 달리 동등 조인(Equi Join) 뿐만 아니라 Non-Equi Join에 대해서도 조인 작업이 가능하다.
Hash Join 수행 원리
1. 선행 테이블에서 주어진 조건을 만족하는 행을 찾는다.
2. 해당 행들에 대해서, 선행 테이블의 조인 키(칼럼)를 기준으로 Hash 함수를 적용하여 해쉬 테이블을 생성.
3. 후행 테이블에서 주어진 조건을 만족하는 행을 찾는다.
4. 해당 행들에 대해서, 후행 테이블에 Hash 함수를 적용하여 선행 테이블의 해쉬 테이블에서 맞는 버킷을 찾음.
5. JOIN을 수행 & 조인에 성공하면 추출버퍼에 넣는다.
6. 후행 테이블의 조건을 만족하는 모든 행에 대해서 3~5번 반복.
- 해쉬 조인(Hash Join)을 수행할 테이블의 조인 칼럼을 기준으로 Hash 함수를 적용하여 서로 동일한 Hash 값을 갖는 것들 사이에서 실제 값이 같은지를 비교하면서 조인을 수행하는 방식이다.
- 해쉬 함수를 적용한 실제 값은 어떤 값으로 해슁(Hashing)될 지 예측할 수 없다. 하지만 해쉬 함수가 적용될 때 동일한 값은 항상 같은 값으로 해슁됨이 보장된다. 하지만 해쉬 함수를 적용할 때 보다 큰 값이 항상 큰 값으로 해슁되고 작은 값이 항상 작은 값으로 해슁된다는 보장은 없다. 그렇기 때문에 Hash Join은 동등 조인(Equi join)에서만 사용할 수 있다는 특징이 있다.
- CPU 작업 위주로 데이터 처리하는 Hash Join은 NL Join의 랜덤 액세스 문제점과 Sort Merge Join의 문제점인 정렬 작업의 부담을 해결 위한 대안으로 등장하였다.
- Hash Join은 조인 작업을 수행하기 위해 ‘해쉬 테이블’을 메모리에 생성한다. → Hash Table의 크기가 메모리에 적재할 수 있는 크기보다 더 커지면 임시 영역(디스크)에 해쉬 테이블을 저장함. 그렇기 때문에 Hash Join을 할 때는 결과 행의 수가 적은 테이블을 선행 테이블로 사용하는 것이 좋다. 선행 테이블의 결과를 완전히 메모리에 저장할 수 있다면 임시 영역에 저장하는 작업이 발생하지 않기도 하고 CPU연산을 조금 덜 수행할 수 있기 때문
- Hash Join에서는 선행 테이블을 이용하여 먼저 해쉬 테이블을 생성한다고 해서 선행 테이블을 Build Input이라고도 하며, 후행 테이블은 만들어진 해쉬 테이블에 대해 해쉬 값의 존재여부를 검사한다고 해서 Prove Input이라고도 한다.
'개발 > RDBMS' 카테고리의 다른 글
| Transaction이란? (0) | 2024.04.19 |
|---|
