join 알고리즘

JOIN 알고리즘의 종류

- Nested-Loop JOIN (중첩 루프 조인)
- Sort Merge JOIN (병합조인)
- Hash JOIN (해시 조인)

 

로우가 많아 질수록 쿼리의 코스트(Cost)는 높아진다. 

이렇게 모두 비례적으로 성능의 떨어지지만 떨어지는 정도에는 차이가 있다.

Loop가 가장 기본적인 방법이며, 양이 적을 때에는 성능이 좋지만 데이터가 많아질 수록 비용도 급격히 증가한다.

Merge 방식은 데이터가 적을 경우에는 Loop 보다는 못하지만, 양이 많아 질 수록 더 뛰어난 성능을 보인다. (여러 조건들이 있음)

Hash 방식은 데이터가 얼마 없을 경우에는 그 오버헤드(Overhead)로 인하여 성능이 좋지 않지만, 데이터가 많을수록 Loop 보다는 낮고 Merge 보다는 못하게 비용이 증가한다.

 

Nested-Loop JOIN (중첩 루프 조인)

• 중첩 for문과 같은 원리.
• 좁은 범위에 유리한 성능을 보여줌
• 가능한 모든 경우를 조회하여 결과 집합을 찾는 방법
• 순차적으로 처리하며, Random Access 위주 → 선행테이블에서 조건에 맞게 순차적으로 처리하나, 정렬되지 않은 후행테이블에서 데이터를 찾을 때 랜덤접근.
• 후행 테이블(Driven)에는 조인을 위한 인덱스 생성 필요
• 실행속도 = 선행 테이블 사이즈 * 후행 테이블 접근횟수
• 선행 테이블의 조건을 만족하는 행을 추출하여, 후행 테이블을 읽으면서 조인을 수행한다. 이 작업은 선행 테이블의 조건을 만족하는 모든 행의 수만큼 반복 수행한다.
  • 선행 테이블의 행이 적을 수록 for문같은 반복 수행이 적어진다. 따라서 처리 주관 범위가 좁은 테이블을 선행테이블로 선택하는 것이 유리하다. 즉, 1:M에서 1인 테이블이 outer테이블인 것이 유리하다.
  • 랜덤 방식으로 데이터에 access하기 때문에 처리 범위가 좁은 것이 유리하다

성능을 높이기 위한 방법

  가) 후행테이블의 크기가 작을수록

  나) 요소들의 비교가 빠르게 이루어 지도록 인덱스가 미리 설정되어 있어야 한다.

 

* 선행테이블(Driving Table) : 찾는 주체가 되는 테이블

* 후행테이블(Driven Table) : 비교 대상이 되는 테이블

 

방식

1. 선행 테이블에서 주어진 조건을 만족하는 행을 찾음
2. 선행 테이블의 조인 키 값을 가지고 후행 테이블에서조인수행
3. 선행 테이블의 조건을 만족하는 모든 행에 대해 1번 작업 반복 수행

Sort Merge JOIN (병합조인)

한집합과 다른 집합을 합하기 위해서 양쪽 다 정렬이 되어 있어야만 비교 가능하다.

중첩 for문과 유사. 양 테이블을 조인 컬럼을 기준으로 정렬시킨 후 조인한다.

랜덤 엑세스 방식으로 데이터를 읽었던 NLJ와 달리 SMJ는 주로 스캔 방식으로 데이터를 읽는다.

넓은 범위를 처리할 때 이용.

 

방식

1. 선행 테이블에서 주어진 조건을 만족하는 행을 찾음
2. 선행 테이블의 조인 키를 기준으로 정렬 작업을 수행 1 ~ 2번 작업을 선행 테이블의조건을만족하는모든행에대해반복수행
3. 후행 테이블에서 주어진 조건을 만족하는 행을 찾음
4. 후행 테이블의 조인 키를 기준으로 정렬 작업을 수행. 3 ~ 4번 작업을 후행 테이블의 조건을 만족하는 모든 행에 대해 반복 수행
5. 정렬된 결과를 이용하여 조인을 수행하며 조인에 성공하면 추출버퍼에 넣음

장점

• inner table에 적절한 인덱스가 없어서 NLJ를 쓰기 비효율 적일 때
• 범위로 Join 할 때

단점

• 정렬할 데이터가 많아서 메모리에서 모두 수행하기 어려운 경우, 임시영역인 디스크를 사용하므로 성능이 떨어진다.

정렬하기 때문에 Table Random Access가 일어나지 않고, sorting작업이 PGA 영역에서 수행되기 때문에 경합이 발생하지 않아서 성능에 유리하다. 또한 해시조인과 달리 동등 조인과 비동등 조인에 대해서도 조인 작업이 가능하다.

Hash JOIN (해시 조인)

NL join의 랜덤 엑세스 문제와 SMJ의 정렬 부담을 해결하기 위한 대안으로 등장했다.

CPU작업 위주의 해시 조인이 성능상 유리하다.

대용량 조인을 할 때 사용. 이너테이블의 데이터가 너무 많을 때 아우터 테이블을 해시 영역에 저장.

해시 또한 PGA영역에서 이뤄지므로 매우 빠르다.

해시를 사용하는 경우는 해당 조인 키가 전혀 정렬되어 있지 않고, 인덱스도 존재하지 않으면서 비교해야 할 대상은 많은 때이다.

 

특징

• Equal join만 가능
  • 해쉬함수를 이용해 조인을 수행하므로 '='로 수행하는 동등조인만 가능.
• SMJ처럼 Random access부하가 없다
• 해시테이블로 올라갈 테이블의 크기가 충분히 작아야 성능이 좋다. 테이블의 용량이 해시테이블보다 크게 되면 오히려 디스크 영역을 사용하게 돼서 성능에 불리
  • SMJ와 마찬가지로 정렬에 사용하거나 생성된 해시 테이블을 적재할 메모리의 크기가 부족해지면 디스크 영역을 사용한다. 따라서 결과 행의 수가 적은 테이블을 선행테이블로 사용해야 한다.
• OLTP환경에서 사용하면 오히려 CPU사용량이 증가.

방식

1. 선행 테이블에서 주어진 조건을 만족하는 행을 찾음
2. 선행 테이블의 조인 키를 기준으로 해쉬 함수를 적용하여 해쉬 테이블을 생성 → 조인 칼럼과 SELECT 절에서 필요로 하는 칼럼도 함께 저장됨 1 ~ 2번 작업을 선행 테이블의 조건을 만족하는 모든 행에 대해 반복 수행
3. 후행 테이블에서 주어진 조건을 만족하는 행을 찾음
4. 후행 테이블의 조인 키를 기준으로 해쉬 함수를 적용하여 해당 버킷을 찾음
5. 조인 키를 이용해서 실제 조인될 데이터를 찾음
6. 조인에 성공하면 추출버퍼에 넣음 3 ~ 5번 작업을 후행 테이블의 조건을 만족하는 모든 행에 대해서 반복 수행