SQL (24) - Nested Loop JOIN

SQL에서는 JOIN을 하는 경우 수행하는 3가지 연산이 존재하는데, 크게 다음과 같습니다.

• Nested Loop(NL) 조인
• Merge(병합) 조인
• Hash(해쉬) 조인

따로 지정하지 않는 이상, DB가 판단하기에 가장 적합한 JOIN 연산을 지정하여 JOIN하지만,

이번 포스트에서는 그중에서도 Nested Loop, 중첩 루프 조인에 대해 알아보겠습니다.

 

1) 3가지 JOIN 연산의 수행

우선, 간단하게 3가지 JOIN이 사용되는 경우를 알아보겠습니다.

-- Merge Join
SELECT *
FROM players AS P
	INNER JOIN salaries AS s
	ON p.playerID = s.playerID;

-- Nested Loop
SELECT TOP 5 *
FROM players AS P
	INNER JOIN salaries AS s
	ON p.playerID = s.playerID;
    
-- Hash Match
SELECT *
FROM salaries AS s
	INNER JOIN teams AS t
	ON s.teamID = t.teamID;

 

위 쿼리별로 ctrl + L을 눌러서 동작 과정을 살펴보면, 다음의 3개의 결과를 얻을 수 있습니다.

첫 번째 쿼리

 

두 번째 쿼리

 

세 번째 쿼리

 

2) 중첩 루프 JOIN 알아보기

위의 예제 쿼리에서 Hash JOIN으로 동작하는 쿼리를 강제적으로 NL JOIN으로 사용해보겠습니다.

SELECT *
FROM players AS P
	INNER JOIN salaries AS s
	ON p.playerID = s.playerID
	OPTION(LOOP JOIN);

 

위 쿼리의 동작 방식을 확인해보겠습니다.

 

위와 같이 중첩 루프 JOIN으로 잘 변화한 것을 확인할 수 있습니다.

그렇다면 이제 중첩 루프 JOIN의 동작원리를 알아보겠습니다.

 

2 - 1) 중첩 루프 JOIN의 원리

중첩 로프 JOIN은 이중 for문을 기반으로 동작합니다.

하지만 이 경우 데이터를 처리하는데 O(N^2)의 시간을 사용하게 됩니다.

 

따라서 일반적인 이중 for문이 특별한 형식의 이중 for문을 사용하게 됩니다.

우선, 첫번째로 해쉬값으로 동작하는 자료구조를 사용하여 순회하는데 소모하는 시간을 줄입니다.

그리고 두번째로 순회하는 데이터의 수를 제한하여 순회하는 횟수를 줄입니다.

 

C#으로 중첩 루프 JOIN을 표현하면 다음과 같습니다.

foreach (Player p in players)
{
	Salary s = null;
	if (Dsalaries.TryGetValue(p.playerId, out s))
	{
		result.Add(p.playerId);
		if (result.Count >= 5)
			break;
	}
}

 

Dictionary인 Player를 순회하면서, playerId의 Key로 저장된 Salary의 Value를 찾습니다.

찾은 결과값을 리스트 result에 넣고 result의 값이 5라면 순회를 종료합니다.

 

위와 같이 해쉬를 사용하고 또, 순회하는 양을 줄여

순회 시간을 O(N)으로 줄일 수 있습니다.

 

2 - 2) 예제 쿼리 분석

기존의 쿼리의 동작 순서를 다시 확인해보겠습니다.

 

위와 같이 Index Seek로 동작하는 부분이 해쉬를 통해 Leaf Page에서 페이지를 찾는 부분입니다.

이후 다시 돌아가 Key Lookup을 수행하는 부분은 Non-Clustered INDEX에서

Key값을 사용해 Clustered INDEX에서 데이터를 찾는 부분을 의미합니다.

 

2 - 3) 루프에서의 Outer와 Inner를 바꾸는 경우

이번에는 예제의 쿼리에서 순회하는 테이블간의 위치를 강제적으로 바꿔보겠습니다.

SELECT *
FROM players AS P
	INNER JOIN salaries AS s
	ON p.playerID = s.playerID
	OPTION(FORCE ORDER, LOOP JOIN);

 

위와 같이 쿼리를 구성한 후 동작 과정을 살펴보면 다음과 같습니다.

 

위의 경우에는 Index Scan만이 동작하여 일일이 테이블을 순회하는 

다시 말해, 이중 for문을 수행하는 과정이 됩니다.

 

3) Nested Loop JOIN 최종 정리

먼저 OUTER 테이블의 행에 접근하고, INNER 테이블의 랜덤한 행에 접근하는 방식으로 동작합니다.
그리고 INNER 테이블에 인덱스가 없는 경우, 동작이 매우 느립니다.(정렬되어 있지 않으므로)
NL JOIN을 사용하는 가장 좋은 경우는, 범위가 정해진 데이터를 처리하는 경우입니다.