데이터베이스 3가지 JOIN 구조의 알고리즘 (Nested Loop, Sort/Merge, Hash)

Postgres에서 쿼리 실행 계획(Explain Query Plan)을 실행했을 때 Nested Loop 에 대해 알게 되었지만, 제대로 정리해본적은 없었기에 SQL의 3가지 JOIN 알고리즘을 정리해보려 한다. 

JOIN 알고리즘의 종류  

• Nested Loop 
• Sort/Merge 
• Hash

RDBMS 에 따른 알고리즘 지원 현황 

• Oracle : 3가지 모두 지원 
• MySQL : Nested Loop 만 지원 
• Postgres : 3가지 모두 지원 

External Table 과 Internal Table

SELECT * 
FROM 
	table1 t1 
INNER JOIN 
	table2 t2 on t1.id = t2.id;

External Table (Drive Table)

JOIN할 때 기준이 되는 테이블이며, 위 SQL에서는 table1 이다. 

Internal Table

External Table 에 연결하는 테이블이며, 위 SQL에서는 table2 이다. 

 

이렇게 이해해도 되는지 모르겠지만... 이중 for문으로 생각해보니 기준이 되는 테이블이 왜 External(외부) 인지 이해가 되었다. 

for(){
  // External Table 을 도는 바깥쪽 루프이며 바깥에 있다. 
  for(){
    // External Table 테이블에 대한 Internal 루프이며 안쪽에 있다. 
  }
}

특징

Nested Loop Join

• External Table 의 모든 행에 대해 Internal Table 에서 조인 키 컬럼 값이 일치하는 것을 찾아 조인
• 위와 관련하여 External Table의 레코드가 적은 쪽이 루프 수를 줄일 수 있기 때문에 빠른 처리 가능 
• Internal Table 의 조인 키 컬럼에 인덱스가 있는 경우, 인덱스를 사용하여 검색할 수 있으므로 빠른 처리 가능

Sort Merge Join

• External Table 과 Internal Table 을 조인 키의 컬럼으로 정렬
• 정렬한 후 위에서부터 Join 키 값이 일치하는 것을 Join (각각의 값을 증가시키면서 비교)
• 인덱스가 없는 Nested Loop Join 보다 빠름 
• 정렬하는 작업은 리소스 측면에서 무겁기 때문에, 인덱스가 있으면 빠르게 처리 가능 
• Hash Join과 달리 비 등가 조인(Non equi-join)에서도 사용할 수 있습니다.

Hash Join

내용이 조금 길어서 특징과 순서를 나누었다. 

• Join 키 컬럼에 인덱스가 없어도 빠른 Join 가능
• 조회 건수가 증가해도 Join 의 부하가 증가하기 크게 증가하지 않는다. (Hash Table 을 사용하기 때문에  이를 저장할 메모리가 필요)
• 해시 함수로 처리하여 등가 조인(Equi-join '=')에서만 사용 가능

 

• 옵티마이저가 Join 하는 테이블 수를 비교하여 작은 테이블을 모두 스캔
• 위에서 선택한 테이블의 조인 키 컬럼의 값을 해시 함수에 적용하여 해시 테이블 생성 
• External Table 의 Join 키 컬럼을 동일한 해시 함수로 변환한 후 만든 해시 테이블 조회 
• 해시가 동일한 컬럼을 합침 

회고

비즈니스가 우릴 기다려 준다면, 보안이 허락해 준다면 운영서버의 데이터를 포크해서 처음부터 좋은 쿼리를 작성할 수 있겠지만 데이터의 흐름은 언젠가 바뀌기 마련이며 이런 부분을 고민하며 쿼리를 작성하는건 현실적으로 어려워 보인다.

그럼에도 모니터링에서 툭 튀는 슬로우 쿼리를 개선하는데에는 도움이 될 것 같고, TB 단위의 데이터를 가지고 있는 2개의 테이블에서 한번 해보고 싶어졌다. 

 

검색하고자 하는 테이블의 특징이나 데이터 량에 따라 적절한 인덱스를 타게 될지 쿼리 실행 계획을 돌려보곤 한다. 

3가지 유형의 Join 을 알아봤으니, 불필요한 Join 은 없었는지, 서브 쿼리를 사용해 테이블의 크기를 줄인 후 Join 이 가능한지, 내가 원하는 Join 알고리즘이 잘 사용되었는지 등도 확인하는 습관을 가지면 좋겠다 싶다.