[DB] 조인 동작 원리

오형상·2025년 6월 14일
CS데이터베이스
0

데이터베이스

목록 보기
6/7
post-thumbnail

중첩 루프 조인 (Nested Loop Join)

개념

프로그래밍의 중첩 반복문처럼 한 테이블의 각 행마다 다른 테이블을 반복 검색하여 조건이 일치하는지 확인합니다.

동작 원리

  1. 선행테이블(Outer Table)에서 조인 조건을 만족하는 한 행을 읽는다.
    (이때 조건을 만족하지 않는 행은 필터링되어 조인 대상에서 제외된다)

  2. 해당 행의 조인 키 값을 가지고 후행테이블(Inner Table)에서 인덱스 또는 탐색 방법으로 조인 키 존재 여부를 확인한다.

  3. 조인 키가 존재하면, 후행테이블의 해당 행을 읽고 추가 조건이 모두 만족되는지 검증한다.

  4. 모든 조인 조건이 만족되면, 조인된 결과 행을 추출 버퍼(임시 결과 저장 공간)에 저장한다.

  • 1~4 과정을 선행 테이블의 모든 행에 대해 반복 수행

반복문의 외부에 있는 테이블을 선행 테이블 또는 외부 테이블 (Outer Table)이라고 하고, 반복문의 내부에 있는 테이블을 후행 테이블 또는 내부 테이블(Inner Table)이라고 합니다.

특징

  • 인덱스가 있는 후행 테이블에 적합
  • 선행 테이블을 풀스캔하므로 선행 테이블의 크기가 작을수록 유리
  • 랜덤 I/O 발생 → 대량 데이터에는 부적합
  • 후행테이블에 대해서는 반드시 인덱스가 존재해야 중첩 루프 조인이 가능하다.

정렬 병합 조인 (Sort Merge Join)

개념

양쪽 테이블을 조인 키로 정렬한 후, 정렬된 상태에서 병합하여 조인을 수행합니다.

동작 원리

  1. 선행테이블에서 조인 조건 및 필터 조건을 만족하는 모든 행을 찾는다.

  2. 조건에 맞는 선행테이블의 모든 행을 조인 키 기준으로 정렬한다.

  3. 후행테이블에서도 조인 조건 및 필터 조건을 만족하는 모든 행을 찾는다.

  4. 조건에 맞는 후행테이블의 모든 행을 조인 키 기준으로 정렬한다.

  5. 정렬된 결과를 이용하여 조인을 수행하며 조인에 성공하면 추출버퍼에 넣음

특징

  • 인덱스 없어도 가능
  • 대부분 해시 조인보다 느린 성능이지만, 아래와 같은 상황에서는 정렬 병합 조인이 유용하다.
    - First 테이블에 Sort 연산을 대체할 인덱스가 있을 때
    - 조인할 First 집합이 이미 정렬되어 있을 때
    - 조인 조건식이 등차(=) 조건이 아닐때
  • 두 테이블의 사이즈가 비슷한 경우에 유리하다.

해시 조인 (Hash Join)

개념

한 테이블을 해시 테이블로 구성하고, 다른 테이블을 해시 기반 탐색으로 조인하는 방식입니다.

동작 원리

  1. 선행 테이블에서 주어진 조건을 만족하는 행을 찾음

  2. 선행 테이블의 조인 키를 기준으로 해시함수를 적용하여 해시 테이블을 생성 -> 조인 컬럼과 SELECT 절에서 필요로 하는 컬럼도 함께 저장

  • 1 ~ 2번 작업을 선행 테이블의 조건을 만족하는 모든 행에 대해 반복 수행

  1. 후행 테이블에서 주어진 조건을 만족하는 행을 찾음

  2. 후행 테이블의 조인 키를 기준으로 해시 함수를 적용하여 해당 버킷을 찾음 -> 조인 키를 이용해서 실제 조인될 데이터를 찾음

  3. 조인에 성공하면 추출버퍼에 넣음

  • 3 ~ 5번 작업을 후행 테이블의 조건을 만족하는 모든 행에 대해 반복 수행

특징

  • 조인 컬럼에 인덱스 불필요
  • 등가(=) 조건에서만 사용 가능
  • In-Memory 해시 조인이 가장 성능이 좋으며, 메모리가 부족한 경우에는 Partitioned Hash Join 방식으로 수행된다.
  • 메모리 사용이 큰 대용량 테이블 조인시 메모리 외에 임시영역(PGA 메모리)까지 사용하여 저장할 수 있어 유리함

Reference

profile
오형상
이전 포스트

[DB] join

다음 포스트

[DB] 인덱스

0개의 댓글