[Oracle] 결합알고리즘과 성능

1. Nested Loops

SQL에서 결합 연산을 수행할 때 내부적으로 선택되는 알고리즘을 바탕으로 결합에 대해서 알아보겠습니다. 결합 알고리즘의 가장 기본이되는 Nested Loops는 이름 그대로 중첩 반복을 사용하는 알고리즘입니다. SQL에서 결합은 한 번에 두 개 의 테이블만 결합하므로 본질적으로 이중 반복과 같은 의미입니다. 

● 결합 대상 테이블에서 레코드를 하나씩 반복해가며 스캔합니다. 이 테이블을 구동테이블 또는 외부 테이블이라고 부릅니다. 다른 테이블은 내부 테이블이라고 합니다.

 

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

 

● 이러한 작동을 구동 테이블의 모든 레코드에 반복합니다.

 

● 한 번의 단계에서 처리하는 레코드 수가 적으므로 Hash, 또는 Sort Merge에 비해 메모리 소비가 적습니다.

 

특히 A, B의 어떤 테이블을 구동 테이블로 사용할지가 큰 요인이 됩니다. 내부 테이블의 결합 키 필드에 인덱스가 존재한다면 구동 테이블을 작게해야합니다. 해당 인덱스를 통해 DBMS는 내부 테이블을 완전히 순회하지 않고 반복을 어느 정도 건너뛸 수 있습니다.

 

납입방법 테이블에 인덱스 존재

 

고객테이블에 인덱스 존재

이처럼 내부 테이블의 결합 키 인덱스가 사용된다면 내부 테이블의 반복을 생략할 수 있으므로 Nested Loops가 빨라집니다. 물론 내부테이블의 반복을 완전하게 생략할 수 있는 경우는 결합 키가 내부 테이블에 대해 유일한 경우일 뿐입니다. 오라클의 실행 계획 중 'INDEX UNIQUE SCAN'이 그렇습니다. 

 

반면 결합 키가 내부 테이블에 대해 유일하지 않은 경우는 인덱스로 내부 테이블에 접근하는 경우라도 여러 개의 레코드가 히트될 가능성이 있습니다. 이 경우에는 히트된여러 개의 레코드에 반복을 적용해야 합니다. 이게 Nested Loops에 단점입니다. 히트되는 레코드가 너무 많아 절대적인 양이 많아지면 반복이 많이 일어나게되고 지연이 일어납니다. 

 

-> '작은 구동테이블' + '내부 테이블의 인덱스'라는 조건이 있을 때 사용. 소규모-대규모결합에 적합 

 

2. Hash 

Hash 알고리즘은 시스템 세계에서 굉장히 자주 사용됩니다. 입력에 대해 어느 정도 유일성과 균일성을 가진 값을 출력하는 함수를 해시라고 합니다. 해시 결합은 일단 작은 테이블을 스캔하고, 결합 키에 해시 함수를 적용해서 해시값으로 변환합니다. 이어서 다른 테이블을 스캔하고, 결합 키가 해시값에 존재하는지를 확인하는 방법으로 결합을 수행합니다. 

 

작은 테이블에서 해시 테이블을 만드는 이유는 해시 테이블은 DBMS의 워킹 메모리에 저장되므로 조금이라도 작은 것이 효율적이기 때문입니다. Hash가 사용되는 경우 어떤 한 쪽의 테이블이 극단적으로 작거나 크지 않습니다. 따라서 구동 테이블이라고 부르는 의미가 전혀 없습니다.

 

* 특징

● Nested Loops에서 적절한 구동 테이블(상대적으로 충분히 작은)이 존재하지 않는 경우 유용합니다.

 

● Nested Loops의 단점에서 구동 테이블로 사용할만한 작은 테이블은 있지만, 내부 테이블에서 히트되는 레코드 수가 너무 많은 경우

 

● Nested Loops의 내부 테이블에 인덱스가 존재하지 않는 경우

 

● 한마디로 말하면 Nested Loops가 효율적으로 작동하지 않는 경우의 차선책이 Hash입니다.

 

-> 대규모 테이블들을 결합할 때 적합. 정렬되어 있다면 Merge Sort 그렇지 않으면 Hash가 적합

* 단점

○ 초기에 해시 테이블을 만들어야 하므로, Nested Loops에 비해 소비하는 메모리 양이 많음

 

○ Hash 결합은 반드시 양쪽 테이블의 레코드를 전부 읽어야 하므로, 테이블 풀 스캔이 사용되는 경우가 많습니다. 테이블의 규모가 굉장히 크다면, 이런 풀 스캔에 걸리는 시간도 고려해야 합니다.

 

3. Sort Merge

Nested Loops가 비효율적인 경우, Hash 사용 외에 또 다른 선택지로 Sort Merge라는 알고리즘도 있습니다. Sort Merge는 결합 대상 테이블들을 각각 결합키로 정렬하고, 일치하는 결합키를 찾으면 결합합니다.

 

● 대상 테이블을 모두 정렬해야 하므로 메모리를 많이 소비합니다. Hash는 한쪽 테이블에 대해서만 해시 테이블을 만들므로 Hash보다 많은 메모리를 사용하기도 합니다.

 

● Hash와 다르게 부등호를 사용한 결합에도 사용할 수 있습니다. 단, 부정조건 결합에서는 사용할 수 없습니다.

 

●  테이블이 결합 키로 정렬되어 있다면 정렬을 생략할 수 있습니다. 

 

●  테이블을 정렬하므로 한쪽 테이블을 모두 스캔한 시점에 결합을 완료할 수 있습니다.

 

-> 테이블의 정렬에 많은 시간과 리소스를 요구할 가능성이 있으므로, Nested Loops와 Hash를 우선적으로 고려!

-> 대규모 테이블들을 결합할 때 적합, 비등가 결합에서도 사용 가능