Join_Algorithm.md

Join Algorithm

Join Algorithm (결합 알고리즘)

• SELECT 쿼리에 결합(JOIN)과 관련된 구문이 있을 경우, 결합 테이블의 조회를 위해 Join 알고리즘 중 한 가지를 사용함
• 자주 사용되는 Join 알고리즘
  • Nested Loops
  • Hash
  • Sort Merge

Nested Loops

• 중첩 반복문의 동작 과정과 유사하게 결합 테이블을 참조
• 즉, 두 테이블의 레코드 수가 각각 N개, M개라면 이론적으로는 N*M 번의 레코드 조회가 발생

장점

• ⭐ 외부 테이블이 내부 테이블보다 작고, 내부 테이블의 결합 키에 인덱스가 존재하는 경우 해당 알고리즘이 가장 효율적으로 동작
• 비동기 결합에도 사용 가능

단점

• 내부적으로 두 테이블 중 작은 테이블을 외부 테이블로 선정하는데, 외부/내부 테이블이 모두 크기가 큰 경우에는 비효율적
• 내부 테이블에 인덱스가 없는 경우 비효율적

Hash

• 외부 테이블의 결합 키를 해시 함수를 통과시켜 해시값으로 만들고, 이를 Working Memory 내 해시 테이블에 저장하고, 이 해시 테이블과 내부 테이블의 결합 키 간 매칭 여부를 확인해 결합
• Nested Loops가 비효율적이라고 판단되는 경우 대부분 Hash를 사용

장점

• 대규모 테이블 간 결합에 적합

단점

• 메모리를 소비한다.
  • 이는 곧 TEMP 탈락이 발생할 가능성이 존재한다는 뜻
• 해시를 이용하므로 순서 보장이 되지 않아 등가 결합에서만 사용 가능

Sort Merge

• 두 테이블을 결합 키 기준으로 정렬한 정렬 테이블을 Working Memory에 생성하고, 이를 기준으로 탐색

장점

• 대규모 테이블 간 결합에 적합
• 비동기 결합 가능

단점

• 데이터를 정렬해야 하는 오버헤드
• 두 테이블의 크기만큼 Working Memory를 사용하므로, 메모리 사용량이 큼
  • TEMP 탈락이 발생할 가능성 존재