DB - Query Processing (4)

jaewonnow_·2025년 10월 20일

Database

데이터베이스

목록 보기

6/11

이전까지 Sorting Operation 작업을 통해 SQL 에서 조건에 맞게 섞는 작업을 하였다.

이번엔 뽑은 데이터를 정렬하는 과정 Join Processing 에 대해 알아보자

I/O의 기본 단위는 블록이다컴퓨터 시스템(특히 디스크 I/O)에서 데이터를 읽는 기본 단위는 튜플 하나가 아니라 블록(Block).

튜플은 논리적인 데이터 단위.
블록은 물리적인 전송 단위.

CPU가 내부 릴레이션 $s$ 에서 튜플 하나를 읽으려 할 때, 해당 튜플이 디스크에 있다면 시스템은 튜플 하나만 가져오는 것이 아니라 그 튜플이 포함된 블록 전체를 메모리로 전송해야 한다.

Join

Nested-loop join (중첩 루프 조인)

두 릴레이션( $r$ 과 $s$ )을 조인할 때

한 릴레이션의 모든 튜플에 대해 다른 릴레이션의 모든 튜플을 검사하는 가장 기본적이고 단순한 조인 알고리즘

알고리즘 동작 방식주어진 의사 코드( $r \ \theta \ s$ 계산)를 단계별로 설명하면 다음과 같습니다.

외부 릴레이션 (= Outer Loop)

외부 릴레이션 $r$ 의 각 튜플( $t_r$ )은 한 번씩 선택되어 고정된 기준이 되며, 이 튜플이 바뀔 때마다 내부 루프가 처음부터 다시 실행된다.
내부 릴레이션 (= Inner Loop)

외부 릴레이션(outer loop) $t_r$ 이 고정된 상태에서, $s$ 의 모든 튜플( $t_s$ )과 비교하기 위해 반복적으로 전체가 스캔된다.

조건 검사 및 결과 추가: 두 튜플 쌍 ( $t_r$ , $t_s$ )이 조인 조건 $\theta$ 를 만족하는지 확인합니다.만약 만족하면, 두 튜플을 결합한 ( $t_r \bullet t_s$ ) 새로운 튜플을 결과 릴레이션에 추가된다.

가장 기본적이고 단순한 조인은 성능적으로 좋을 수 가 없는 건 이제 말안해도 알 수 있다.

직접 비용을 계산해보면

1. 최악의 경우 (Worst Case) 비용 분석

최악의 경우는 메인 메모리가 두 릴레이션의 각각 한 블록씩만 담을 수 있을 때의 비용이다. 외부 릴레이션 $r$ 의 한 튜플을 비교할 때마다 내부 릴레이션 $s$ 전체를 디스크에서 반복해서 읽어야 하는 상황.

블록 전송 (Block Transfers) : $\mathbf{n_r} \times \mathbf{b_s} + \mathbf{b_r}$
외부 릴레이션 $r$ 전체를 읽는 비용 $\mathbf{b_r}$ 에, 외부 릴레이션 $r$ 의 각 튜플 수 $n_r$ 만큼 내부 릴레이션 $s$ 전체를 반복해서 읽는 비용 $n_r \times b_s$ 를 더한 값이다.

탐색 (Seeks) : $\mathbf{n_r} + \mathbf{b_r}$
외부 릴레이션 $r$ 의 튜플 수 $n_r$ 만큼 내부 릴레이션 $s$ 의 첫 블록으로 돌아가야 하므로 $\mathbf{n_r}$ 번의 탐색이 발생하고, $r$ 의 블록을 읽기 위한 탐색 횟수 $\mathbf{b_r}$ 이 더해진다.

$r$ 의 첫 번째 블록( $r_1$ )이 로드되어 튜플을 하나씩 처리한다.

$r_1$ 에 있는 모든 튜플( $n_{r1}$ 개)에 대한 비교가 끝난 후, 다음 외부 블록 $r_2$ 를 메모리로 로드해야 합니다. -> 총 br개를 탐색한다

튜플 조인 비용 공식에서 $\mathbf{b_s}$ 를 사용하는 이유이 비용을 계산하는 목표는 "디스크에서 메모리로 데이터를 몇 번 전송했는가?" (즉, 블록 전송 횟수, I/O 횟수)를 측정하는 것.

최적화된 경우 (작은 릴레이션을 내부로) 비용 분석

최적화된 경우는 두 릴레이션 중 작은 릴레이션을 내부 릴레이션 ( $s$ )으로 선택하고, 이 $s$ 가 전부 메모리에 들어갈 때의 비용이다.가정: 릴레이션 $s$ 가 $r$ 보다 작으며, $s$ 의 전체 블록 수 $b_s$ 가 메모리 $M$ 보다 작아서 $s$ 전체가 메모리에 로드될 수 있다고 가정한다.

블록 전송 (Block Transfers): $\mathbf{b_r} + \mathbf{b_s}$
1. $s$ 를 메모리에 한 번 로드하는 비용 $\mathbf{b_s}$ .
2. $r$ 전체를 한 번 스캔하는 비용 $\mathbf{b_r}$ . 내부 릴레이션이 메모리에 있으므로, $r$ 의 튜플마다 $s$ 를 다시 읽을 필요가 없어져 비용이 $n_r \times b_s$ 에서 $b_s$ 로 급감한다.

탐색 (Seeks) : $\mathbf{2}$
1. $s$ 의 첫 블록을 찾기 위한 1회 탐색. 2. $r$ 의 첫 블록을 찾기 위한 1회 탐색. (이후 $r$ 과 $s$ 는 순차적으로 읽힌다고 가정).

Block nested-loop join (블록 중첩 루프 조인)

기존의 튜플 중첩 루프 조인(Tuple Nested-Loop Join)은 외부 릴레이션의 튜플 하나에 대해 내부 릴레이션 전체를 스캔했다. 이와 달리, 블록 중첩 루프 조인은 외부 릴레이션 $r$ 의 블록 하나를 메모리에 올린 후 ( = 내부 릴레이션 $s$ 의 모든 블록과 비교한다.)

예를 들어, 1000개의 튜플( $n_r=1000$ )이 10개의 블록( $b_r=10$ )에 담겨 있다고 가정하면

튜플 조인: 내부 릴레이션 $s$ 를 외부r 의 튜플 수만큼 1000번 반복해서 읽고 (튜플 단위 비교)

블록 조인: 내부 릴레이션 $s$ 를 블록 수만큼 10번만 반복해서 읽는다. (블록 단위 비교)

-> I/O 효율성이 1000번 -> 10번 획기적으로 줄어든다.

최악의 경우 (Worst Case) 비용 분석블록 중첩 루프 조인에서 최악의 경우, 즉 메모리가 외부 릴레이션 $r$ 의 단 한 블록( $B_r$ )만 담을 수 있을 때의 비용이다.

블록 전송 (Block Transfers)
$\mathbf{b_r} \times \mathbf{b_s} + \mathbf{b_r}$ = 외부 릴레이션 $r$ 의 블록 수 $b_r$ 만큼 내부 릴레이션 $s$ 의 전체 블록 개수 $\mathbf{b_s}$ 를 반복해서 읽는 비용( $b_r \times b_s$ )에 $r$ 전체를 읽는 비용 $\mathbf{b_r}$ 을 더한 값이다.

탐색 (Seeks)
$\mathbf{2 \times b_r}$ = 외부 릴레이션 $r$ 의 각 블록 $b_r$ 마다 $r$ 블록을 읽고, 다음 $s$ 의 시작 위치로 이동해야 하므로, $r$ 의 블록 수의 약 두 배만큼 탐색이 발생한다.

핵심 변화 (비용 절감): 이 비용은 기본적인 튜플 중첩 루프 조인의 비용( $n_r \times b_s + b_r$ 블록 전송)에서 외부 릴레이션의 튜플 수 $n_r$ 가 블록 수 $b_r$ 로 대체된 것이다. $n_r$ 은 $b_r$ 보다 수백~수천 배 크기 때문에, 이 변경만으로도 I/O 비용이 대폭 감소된다.

최적의 경우 (Best Case) 비용 분석최적의 경우는 두 릴레이션 중 작은 쪽(여기서는 내부 릴레이션 $s$ 로 가정)이 메모리에 완전히 들어갈 때의 비용이다.

이 경우는 블록 조인뿐만 아니라 모든 중첩 루프 조인에서 달성할 수 있는 가장 낮은 I/O 비용이다.
$r$ 의 튜플/블록마다 $s$ 를 반복해서 읽을 필요가 없어진다.

블록 전송 (Block Transfers) : $\mathbf{b_r} + \mathbf{b_s}$ 내부 릴레이션 $s$ 를 메모리에 한 번 로드하는 비용 $\mathbf{b_s}$ 와 외부 릴레이션 $r$ 을 한 번 스캔하는 비용 $\mathbf{b_r}$ 만 발생한다.

탐색 (Seeks)
$\mathbf{2}$ = $r$ 의 시작 위치로 한 번, $s$ 의 시작 위치로 한 번, 총 2회의 탐색만 발생한다.

Indexed nested-loop join

인덱스 중첩 루프 조인은 내부 릴레이션 전체를 반복적으로 스캔하는 대신, 인덱스를 사용하여 조인 조건에 맞는 튜플을 직접 찾아 접근함으로써 I/O 비용을 크게 절감하는 방법

조인 비용은 외부 릴레이션을 읽는 비용과, 내부 릴레이션의 인덱스를 반복적으로 사용하는 비용의 합으로 추정된다.

$\text{Cost} = \mathbf{b_r} \times (\mathbf{t_T} + \mathbf{t_S}) + \mathbf{n_r} \times \mathbf{c}$
$\mathbf{b_r} \times (\mathbf{t_T} + \mathbf{t_S})$ : 외부 릴레이션 $r$ 의 블록들을 읽는 I/O 비용. ( $b_r$ : $r$ 의 블록 수, $t_T$ : 블록 전송 시간, $t_S$ : 탐색 시간).
$\mathbf{n_r} \times \mathbf{c}$ : $r$ 의 튜플 수 $\mathbf{n_r}$ 만큼 인덱스 조회를 반복하는 총 비용. $\mathbf{c}$ : $r$ 의 튜플 하나에 대해 $s$ 의 인덱스를 탐색하고 조인 조건에 맞는 모든 $s$ 튜플을 디스크에서 가져오는 데 드는 비용.

이는 $r$ 을 한 번 순차적으로 읽는 비용과 거의 같다.

$\mathbf{c}$ 는 $s$ 릴레이션에 대해 조인 조건을 이용한 단일 선택(Single Selection) 연산을 수행하는 비용과 같다.

최적화 전략 (외부 릴레이션 선택)
If indices are available on join attributes of both r and s, use the relation with fewer tuples as the outer relation
최적의 선택 : 만약 $r$ 과 $s$ 모두 조인 속성에 인덱스가 구축되어 있다면, 튜플 수가 더 적은 릴레이션을 외부 릴레이션( $r$ )으로 선택해야 한다.

이유: 총 비용 공식 $\mathbf{n_r} \times \mathbf{c}$ 에서 알 수 있듯이, 내부 릴레이션 $s$ 의 인덱스 조회 및 페치 비용 $\mathbf{c}$ 는 외부 릴레이션의 튜플 수 $\mathbf{n_r}$ 에 곱해진다. 따라서 $n_r$ 이 작을수록 반복 횟수가 줄어들어 전체 조인 비용이 최소화된다.

Merge-join

두 릴레이션(테이블)을 미리 조인 속성(Join Attribute)으로 정렬을 전제로 하고, 두 정렬된 목록을 병합(Merge)하면서 조인 조건을 만족하는 튜플을 찾아내는 효율적인 조인 알고리즘.

동등 조인(Equi-joins)과 자연 조인(Natural joins)에만 사용할 수 있다. (정렬 순서에 기반하기 때문에 부등호 조건에는 적합하지 않음)

알고리즘 단계는 병합, 조인은 크게 두 단계로 나뉜다:

정렬 (Sort)
두 릴레이션( $r$ 과 $s$ )을 모두 조인 속성을 기준으로 정렬. 만약 릴레이션이 이미 조인 속성으로 정렬되어 있거나, 조인 속성에 대한 클러스터링 인덱스가 구축되어 있다면 이 단계는 생략.
병합 (Merge)
정렬된 두 릴레이션을 처음부터 끝까지 한 번씩 순차적으로 스캔하며 병합.

조인 단계는 외부 정렬-병합(External-sort Merge) 알고리즘의 병합 단계와 유사하다. 두 릴레이션에서 현재 포인터가 가리키는 튜플을 비교하며, 작은 값을 가진 포인터는 전진하고, 값이 일치하면 조인 결과를 생성한다.

중복 값 처리: 조인 속성 값이 같은 튜플이 여러 개 있는 중복 값은 특별히 처리하는데 , 같은 값을 가진 모든 쌍을 매칭해야 한다. 예를 들어, $r$ 에 'A'를 가진 튜플이 3개, $s$ 에 'A'를 가진 튜플이 2개 있다면, $3 \times 2 = 6$ 개의 조인 결과가 생성되어야 한다. 이를 위해 포인터를 잠시 되돌리거나, 일치하는 블록을 메모리에 임시 보관하는 등의 작업이 필요하다.

비용 효율성 (I/O Cost) : 병합 조인의 가장 큰 장점은 I/O 효율성이다.

핵심: 정렬된 상태에서는 각 릴레이션의 블록을 단 한 번씩만 읽으면 된다.
가정: 어떤 특정 조인 속성 값에 해당하는 모든 튜플이 메인 메모리에 들어갈 만큼 충분히 작다고 가정한다. (이 가정이 깨지면 I/O가 늘어날 수 있음).

비용 공식

$\text{Cost} = (\mathbf{b_r} + \mathbf{b_s}) \text{ block transfers} + \lceil \mathbf{b_r} / \mathbf{b_b} \rceil + \lceil \mathbf{b_s} / \mathbf{b_b} \rceil \text{ seeks} + \text{Cost of sorting (if unsorted)}$

$\mathbf{b_r} + \mathbf{b_s}$ 블록 전송: 두 릴레이션( $r, s$ )의 모든 블록을 한 번씩만 디스크에서 읽어오는 비용이다. 이는 조인 과정에서 발생하는 최소한의 I/O 비용이다.

$\lceil \mathbf{b_r} / \mathbf{b_b} \rceil + \lceil \mathbf{b_s} / \mathbf{b_b} \rceil$ 탐색: 각 릴레이션을 읽을 때 발생하는 디스크 탐색 비용이다. 버퍼 블록 $\mathbf{b_b}$ 를 할당하여 순차적으로 읽으므로, 전체 블록 수 $\mathbf{b_x}$ 를 버퍼 크기 $\mathbf{b_b}$ 로 나눈 값만큼의 탐색만 발생한다. (순차 접근이므로 탐색 비용이 낮음)

정렬 비용: 만약 릴레이션이 정렬되어 있지 않다면, 조인을 수행하기 전에 외부 정렬을 수행해야 하므로 그 비용(외부 정렬-병합 비용)이 추가된다.

Hash-join

해시 함수(Hash Function)를 사용하여 두 릴레이션(테이블)의 조인 속성 값이 같은 튜플들을 효율적으로 찾아서 조인하는 알고리즘.

해시 조인은 동등 조인(Equi-joins)과 자연 조인(Natural Joins)에만 적용 가능하다. 해시 함수는 동등성(같음) 비교에 최적화되어 있기 때문.

조인 속성에 대해 해시 함수 $h$ 를 적용하여, 같은 해시 값을 가진 튜플들만 서로 비교해 보는 것.

해시 값 비교: 외부 릴레이션( $R$ )의 튜플 $d$ 와 내부 릴레이션( $S$ )의 튜플 $c$ 가 있을 때, 먼저 $h(c)$ 와 $h(d)$ 가 같은지 확인한다.

필터링 효과: 만약 $h(c) \neq h(d)$ 라면, $c$ 와 $d$ 는 조인 속성 값이 반드시 다르다는 것을 의미하므로, 이 두 튜플은 조인 조건을 만족할 리가 없어 즉시 건너뛸 수 있다. (불필요한 비교 제거)

검증 필요: 만약 $h(c) = h(d)$ 라면, 이 두 튜플은 조인 속성 값이 같을 가능성이 높다는 의미이다. 하지만 해시 충돌(Hash Collision, 다른 입력 값이 같은 해시 값을 내는 현상)이 있을 수 있으므로, 반드시 원래 조인 속성 값이 실제로 같은지( $c.\text{ID} = d.\text{ID}$ )를 추가로 테스트해야 한다.