조인의 원리

조인의 원리인 중첩 루프 조인, 정렬 병합 조인, 해시 조인에 대해 알아보자.

중첩 루프 조인

중첩 루프 조인(Nested Loop Join)은 가장 기본적인 조인 알고리즘으로, 두 테이블의 모든 행을 비교하여 일치하는 행을 찾는 방식이다. 즉, 외부 테이블의 각 행에 대해 내부 테이블의 모든 행을 순회하며 조인을 수행한다. 중첩 루프 조인은 구현이 간단하고, 인덱스가 없는 경우에도 사용할 수 있다는 장점이 있지만, 성능이 좋지 않다는 단점이 있다. 중첩 루프 조인의 시간 복잡도는 O(N * M)으로, N과 M은 각각 두 테이블의 행 수이다.

중첩 루프 조인의 예시:

javascript

const result = [];

for (const rowA of tableA) {
	for (const rowB of tableB) {
		if (rowA.key === rowB.key) {
			result.push({ ...rowA, ...rowB });
		}
	}
}

보다 발전된 형태로, 중첩 루프 조인에서 조인할 테이블을 작은 블록으로 나누어 처리하는 블록 중첩 루프 조인(Block Nested Loop Join)이 있다.

정렬 병합 조인

정렬 병합 조인(Sort-Merge Join)은 두 테이블이 조인 키를 기준으로 정렬되어 있을 때 효율적으로 동작하는 조인 알고리즘이다.

정렬 병합 조인은 다음과 같은 단계로 수행된다.

두 테이블을 조인 키를 기준으로 정렬한 후, 각 테이블의 첫 번째 행부터 시작하여 조인을 수행한다.
조인 키가 일치하면 결과에 추가하고, 그렇지 않으면 작은 값을 가진 테이블의 다음 행으로 이동한다.
이 과정을 두 테이블의 끝까지 반복한다.

정렬 병합 조인은 정렬된 데이터에 대해 매우 효율적이며, 대용량 데이터 처리에 적합하다. 정렬 병합 조인의 정렬 시간 복잡도는 O(N log N + M log M)이며 병합 단계의 시간 복잡도는 O(N + M)으로 총 시간 복잡도는 O(N log N + M log M)이다.

정렬 병합 조인의 예시:

javascript

const result = [];
let i = 0;
let j = 0;

tableA.sort((a, b) => a.key - b.key); // O(N log N)
tableB.sort((a, b) => a.key - b.key); // O(M log M)

// O(N + M) -> 투 포인터 알고리즘
while (i < tableA.length && j < tableB.length) {
	if (tableA[i].key === tableB[j].key) {
		result.push({ ...tableA[i], ...tableB[j] });
		i++;
		j++;
	} else if (tableA[i].key < tableB[j].key) {
		i++;
	} else {
		j++;
	}
}

해시 조인

해시 조인(Hash Join)은 두 테이블 중 하나를 해시 테이블로 변환하여 조인을 수행하는 알고리즘이다.

해시 조인은 다음과 같은 단계로 수행된다.

1. 빌드 단계

작은 테이블(보통 메모리에 적재할 수 있는 크기)을 선택하여, 조인 키를 기준으로 해시 테이블을 생성한다. 조인에 사용되는 키는 해시 테이블의 키로 사용된다.

2. 프로브 단계

큰 테이블의 각 행에 대해, 조인 키를 사용하여 해시 테이블에서 일치하는 행을 찾는다. 일치하는 행이 있으면 결과에 추가한다.

해시 조인은 대용량 데이터에 대해 효율적으로 동작하며, 특히 조인 키에 대한 인덱스가 없는 경우에 유용하다. 해시 조인의 시간 복잡도는 O(N + M)이다.

Principle of JOIN