조인(Join) 알고리즘 - 중첩 루프 조인(Nested Loop Join)

조인(Join) 알고리즘 - 중첩 루프 조인(Nested Loop Join)

---

조인이란 데이터베이스에서 하나의 테이블이 아닌 두 개 이상의 테이블을 묶어서 하나의 결과물을 만드는 것입니다.

이번 포스팅에서는 이러한 조인의 원리. 즉, 조인 알고리즘 중 중첩 루프 조인에 대해서 알아보겠습니다.

 

 

중첩 루프 조인 (Nested Loop Join)

중첩 for문과 같은 원리로 조건에 맞는 조인을 하는 방법의 조인입니다.

 

for(i: Int in 1..10){
	for(j: Int in 1..10){
		...
	}
}

 

해당 방법에서는 두 개의 테이블을 Driving Table, Driven Table로 나눕니다.

 

for(i: Int in 1..10){ //  <- Driving Table
	조건에 해당하는 데이터를 찾음
	for(j: Int in 1..10){ //  <- Driven Table
		Driving Table에서 찾은 데이터와 같은 데이터를 찾음
	}
}

 

과정을 구체적으로 설명해 보겠습니다.

 

1. Driving Table은 조건에서 조건에 맞는 데이터를 찾습니다.
2. 해당 데이터의 인덱스를 가진 항목이 Driven Table에 존재하는지 확인합니다.
   • Driven Table에서 인덱스가 없다면 Driving Table에서 찾은 데이터마다 Driven Table에서 풀스캔 방식으로 찾아봐야 하기 때문에 중첩 루프 조인은 Driven Table에 인덱스가 있을 때 사용하는 방법입니다.
   • 예를들어 Driving Table에서 조건의 맞는 항목의 인덱스가 5라고 할 때, Driven Table에서 인덱스 5를 가진 항목이 있는지 찾아보는 것입니다.
3. 인덱스에 해당 데이터가 존재한다면 인덱스에 존재하는 주소를 통해 실제 테이블의 데이터에 접근한 후 해당 값을 추출합니다.
4. 이 과정을 전부 마치고 나온 값들이 조인의 결괏값입니다.

 

위와 같은 과정을 통해 중첩 루프 조인은 Driven Table에서 인덱스가 있을 때 사용하는 방법이란 것을 알 수 있습니다.

 

 

또한 대용량의 테이블에서는 적합하지 않습니다.

 

그 이유는 인덱스를 통한 랜덤액세스에서의 시간이 오래 걸리기 때문인데요. 여기서 의문이 생길 수 있습니다.

 

"검색에서 풀스캔보다 인덱스를 통한 랜덤액세스가 빠르다고 했는데 랜덤액세스가 느리다고??" 

 

여기서 느리다는 것은 검색 속도를 의미하는 것이 아니라 인덱스 사용으로 인한 여러 번의 인풋, 아웃풋(I/O)으로 인해 속도가 느리다는 뜻입니다.

위와 같이 인덱스에서 Driven Table에 접근, 그 후 다시 인덱스에 가서 Driven Table에 접근, 그 후도 마찬가지로 계속 동일하게 진행되어 왔다 갔다 하는 시간 때문에 오래 걸리는 것입니다.

 

 

 

※ 잘못된 정보, 혹은 다른 의견이 있다면 댓글로 말해주세요. 감사합니다.