조인(결합) 알고리즘과 성능

옵티마이저가 선택 가능한 결합 알고리즘

1. Nested Loops

2. Hash

3. Sort Merge 

 

가장 빈번한 알고리즘은 Nested Loops -> Hash -> Sort Merge 이다. 

대부분이 이 세개를 지원하지만 그렇지 않거나 파생된 알고리즘을 제공하는 곳이 있으니 자신이 주로 사용하는 DBMS 최신 동향에 주의를 기울이도록하자. 

 

1. Nested Loops

중첩 반복을 사용하는 알고리즘 -> 결합은 한 번에 두 개의 테이블만 결합하므로 본질적으로 이중 반복과 같은 의미 

R = 구동테이블, S = 내부 테이블

. 테이블 R을 구동 테이블 = 외부 테이블이라고 부르고 B를 내부 테이블이라고 부른다.

1. 결합 대상 테이블 R에서 레코드를 하나씩 반복해가며 스캔

2. 구동 테이블의 레코드 하나마다 내부 테이블의 레코드를 하나씩 스캔해서 결합 조건에 맞으면 리턴

3. 1~2를 구동 테이블의 모든 레코드에 반복

 

특징

- 실행시간은 레코드 수에 비례한다.

- 한 번의 단계에서 처리하는 레코드의 수가 적으므로 hash 또는 sort merge에 비해 메모리 소비가 적다. 

- 모든 dbms에서 지원

 

구동 테이블이 작을수록 성능이 좋아짐. 전제 조건 = 내부 테이블의 결합 키 필드에 인덱스가 존재할 때 

그때 내부 테이블의 특정 레코드들을 건너뛸 수 있기 때문에 결국 구동테이블의 수가 중요해지는 것이다.

 

SELECT E.emp_id, E.emp_name, E.dept_id, D.dept_name 
FROM Emplotees E INNER JOIN Departments D
ON E.dept_id = D.dept_id

이때 내부 테이블의 결합 키 인덱스가 사용된다면 내부 테이블의 반복을 생략할 수 있으므로 빨라진다.

-> 내부 테이블의 반복을 얼마나 생략할 수 있을지가 포인트 

 

2. Hash

 

3. Sort Merge