조인의 원리

조인의 원리를 기반으로 조인 작업이 이뤄진다.
조인의 원리인 중첩 루프 조인, 정렬 병합 조인, 해시 조인에 대해 알아보겠다.

중첩 루프 조인

• 중첩 루프 조인은 중첩 for 문과 같은 원리로 조건에 맞는 것을 조인하는 방법을 말하며, 디스크 접근에 대한 비용이 많이 증가하므로 대용량의 테이블에서는 사용하지 않아야 한다.
• 예를 들어 t1, t2 테이블을 중첩 루프 조인을 통해 조인할 때 t1 테이블에서 먼저 한 행만 읽고 t2 테이블에서 행을 하나씩 읽어 조건에 맞는 레코드를 찾아 조인하는 것을 말한다.
• 디스크 접근 비용을 줄여 성능을 높인 방법으로는 블록 중첩 루프 조인이 있다.
  • 테이블을 작은 블록으로 나눠서 메모리에 올린 후 이 블록을 재사용하면서 조인을 진행시켜 디스크 접근을 줄이는 방법이다.

정렬 병합 조인

• 정렬 병합 정렬이란 각각의 테이블을 조인할 필드 기준으로 정렬하고 정렬이 끝난 이후에 벙합하여 조인하는 방법이다.
• 병합시에는 정렬된 리스트들을 한 번씩만 순회하면서 비교하다 조인을 해준다.
• 즉, 최선의 경우 O(N + M) 시간 복잡도가 걸린다. 최악의 경우는 O(N*M)이 될 수 있다.
• 조인할 때 쓸 적절한 인덱스가 없고 대용량의 테이블들을 조인하고 조인 조건으로 <, > 등 범위 비교 연산자가 있을 때 사용된다.

해시 조인

• 해시조인은 해시 테이블을 기반으로 조인하는 방법이다.
• 하나의 테이블이 메모리에 온전히 들어간다면 보통 중첩 루프 조인보다 더 효율적이다(메모리에 올릴 수 없을 정도로 크다면 디스크를 사용하는 비용이 발생된다).
• MySQL의 해시 조인 단계는 빌드 단계, 프로브 단계로 나뉜다.
  • 빌드 단계
    • 입력 테이블 중 크기가 더 작은 테이블을 기반으로 메모리 내 해시 테이블을 빌드하는 단계
    • 조인에 사용되는 필드가 해시 테이블의 키로 사용된다.
  • 프로브 단계
    • 조인에 사용되는 필드 값을 통해 해시 테이블에 접근한다.
    • 해시 버킷에 조건에 부합하는 레코드가 있으면 조인을 진행한다.