Join
Nested-Loop join
외부 릴레이션의 각 레코드에 대해 내부 릴레이션의 모든 블록을 메모리에 적재하여 확인하는 방식
- 비용 계산
| 경우 | Cost Formula | 설명 |
|---|---|---|
| Worst case | n × bs + br |
외부 테이블 레코드 수 × 내부 테이블 블록 수 + 외부 테이블 블록 수 |
| Best case | bs + br |
내부 테이블 블록 수 + 외부 테이블 블록 수 |
하나의 릴레이션이 메모리에 모두 올라갈 정도의 크기라면, 읽기 연산을 한번만 하고 메모리에 적재된 값들로 조인 연산을 할 수 있습니다.
- 색인이 필요 없고, 모든 조인 조건에 사용 가능
- 메모리 과다 사용, 느림
Block Nested-Loop join
Block 단위의 비교
| 경우 | Cost Formula | 설명 |
|---|---|---|
| Worst Case | br × bs + br |
외부 테이블 블록 수 × 내부 테이블 블록 수 + 외부 테이블 블록 수 |
| Best Case | bs + br |
내부 테이블 블록 수 + 외부 테이블 블록 수 |
이로 봤을 때, outer 릴레이션의 크기가 작다면 더 빠른 연산을 한다는 것을 알 수 있습니다.
그런데 대부분의 경우, 블럭보다 메모리의 크기가 더 크므로 메모리에 여러 블럭을 한번에 적재할 수 있습니다.
사용 가능한 메모리의 크기를 M이라 할 때, 블럭 접근 횟수는 B1 + (B1 / M) * B2로 나타낼 수 있습니다.
Indexed Nested-Loop join
Inner relation에 대해 file scan 대신 index lookup
Join column에 대해 인덱스가 있는 경우, 그 인덱스를 활용할 수 있습니다.
예제로 살펴보겠습니다. 인덱스로 B+ 트리를 사용하고 트리의 높이가 4인 경우, Depositor 테이블과 Customer 테이블을 조인하는 비용은 다음과 같습니다.
5000 × 5 + 100 = 25,100
여기서 5는 트리의 높이인 4와 평균 결과 블록을 나타내는 1을 더한 값입니다.
Sort-Merge join
정렬된 순서로 정렬된 두 테이블을 병합하여 조인을 수행
- Phase 1인 build 단계에서 릴레이션 S를 분할해서 가용한 메모리만큼의 크기인 Run들을 생성합니다.
- Phase 2인 probe 단계에서는 각각의 버퍼에서 값을 읽어와 Min Heap과 같은 우선순위 큐에 저장합니다.
- 저장된 우선순위 큐에서 가장 작은 값들을 비교해서 같다면 조인 결과를 저장합니다.
- 조인을 수행하기 전에는 조인할 컬럼을 미리 정렬해야 합니다.
- NL 조인은 이미 생성된 인덱스를 활용하며, 반면에 Sort-Merge 조인은 쿼리가 '실행 중'에 정렬 구조체를 동적으로 생성하여 사용합니다.
- NL 조인과 비교했을 때 INNER 집합을 반복적으로 탐색하지 않습니다.
Hash join
R에 대한 해시 테이블을 생성후, 메모리에 저장하고 저장된 해시 값을 바탕으로 equal 연산을 상대 릴레이션의 join column에 대해 수행
해시 테이블을 만드는데 사용되는 집합을 Build Input이라 하고 탐색하는 데 사용되는 집합을 Probe Input이라고 합니다.
- R에 대한 해시 테이블을 생성 후, 메모리에 저장
- S의 레코드를 스킨해면서, 해시 테이블을 probe
-
sort-merge 조인과는 다르게 equi-join에만 수행이 가능
-
정렬할 필요가 없음
-
R의 해시 테이블이 너무 커서 메모리에 저장될 수 없는 경우?
→ 해시 테이블을 분할해야 하므로 Partitioning algorithm 필요
Simple Hash join algorithm
메모리만을 사용해서 해싱하고 조인을 진행
- 전체중 일부만 해시 테이블에 적재하고 조인
- R의 다음 일부분을 해싱하고 조인 → 릴레이션 R을 여러번 읽어야 함
Grace Hash join algorithm
- Phase 1인 파티셔닝 단계에서 릴레이션 R을 버퍼를 사용해서 해싱한 값을 바탕으로 각각의 여러 subset으로 그룹화해서 분리
- Phase 2인 조인 단계에서 Ri와 Si끼리 조인을 하면 원하는 조인 결과를 저장할 수 있습니다.
- 레코드 각각을 WHERE 조건에 맞추어 해싱을 진행
- 얻은 해싱 값(key)으로 릴레이션간의 같은 key끼리 조인합니다.
Hybrid Hash join algorithm
- Simple Hash Join과 Grace Hash Join요소가 결합되어 조인
- 첫 해싱값들은 파일에 쓰지 말고 남는 메모리를 활용해서 메모리에서 바로 계산
Sort-merge join vs. Hash join
| Sort-merge join | Hash join | |
|---|---|---|
| 비용 | 3(br + bs) (파티셔닝(2 * I/O) + 조인(1 * I/O)) | Sort-merge 조인과 동일 |
| Pros | 조인 결과과 정렬 ORDER BY과 연산시 최적화 가능 |
Sort-merge 조인보다 작은 메모리로 조인 가능 해싱 값으로 그룹화되어 있어서 병렬 처리에 적합 |
Joins in DBMS
Oracle
Oracle에서 다른 조인 방식을 명시적으로 지정하려면 SQL 힌트를 사용할 수 있습니다.
- SQL 힌트 - 쿼리 옵티마이저에게 특정 실행 계획을 사용하도록 지시하는 주석
SELECT /*+ USE_NL(s d) */
sid,
sname,
s.deptno,
dname
FROM STUDENT s,
DEPT d
WHERE s.deptno = d.deptno;Hint의 종류
| Join Type | Hint |
|---|---|
| Nested loop | /*+ USE_NL(s d) */ |
| Merge join | /*+ USE_MERGE(s d) */ |
| Hash join | /*+ USE_HASH(s d) */ |
위의 Hint를 바탕으로 SQL을 실행할 때, 조인 방식을 지정할 수 있습니다.
그리고 SQL Developer를 사용한다면, F10 + enter로 SQL 쿼리 실행 cost를 확인할 수 있습니다.
MySQL
MySQL은 직접적으로 조인 방식을 지정할 수는 없지만 가장 최적화된 방식으로 동작합니다.
EXPLAIN를 사용해서 쿼리 명령어 수행 방식을 상세히 확인할 수 있습니다.
N-Way join시 주의 사항
고려 사항
-
Cartesian product를 하지 않도록 알맞는 Join 순서 정하기
-
선행되는 Join 결과를 저장?
- 선행되는 Join의 결과가 outer relation으로 사용될 경우, 다음 relation과 즉시 join 가능
-
다양한 조합에 대한 cost를 조사하고 최소 cost를 갖는 join permutation 선택
Evaluation of Expressions
Materialization
- 중간 결과들을 임시 릴레이션에 저장해야 함
- Query Execution cost에 디스크 저장 비용을 포함
Pipelining
- 연산자들을 별도의 프로세스나 쓰레드로 구현
- 하부 연산 결과 → 상위 연산자의 입력으로 전달
- 중간 연산결과를 임시 릴레이션에 저장할 필요가 없음
- 병렬 질의 처리에 적합
- 단, Sort-merge의 경우, 두 테이블을 먼저 정렬해야 하고 진행하기 때문에 파이프라이닝이 불가능
SQL 쿼리 비교
아래의 두 쿼리는 같은 결과를 얻을 수 있지만 수행 비용이 차이납니다.
- πcustomer-name(σbalance<2500(ACCOUNT) ⨝ CUSTOMER)
- πcustomer-name(σbalance<2500(ACCOUNT ⨝ CUSTOMER))
1번 SQL 연산의 경우, 먼저 ACCOUNT 릴레이션에서 balance가 2500보다 큰 레코드를 찾은 다음에, 이를 CUSTOMER 릴레이션과 조인 연산을 합니다.
2번의 경우, 조인을 먼저하고 조건에 맞는 레코드를 찾습니다. 그래서 2번보다 1번이 더 적은 비용으로 연산이 가능하다고 말할 수 있습니다.