#title Loop Join
[[TableOfContents]]

==== 테스트를 위한 준비 ====
연결 액세스 분석을 위해서는 테이블간의 관계를 먼저 알아야 한다. 개념 ERD가 있으면 더욱 좋다. 여기에서는 MSSQL Server 다이어그램을 사용하겠다. 다음은 MSSQL Server의 예제 데이터베이스인 Pubs 데이터베이스의 Employees 테이블과 Jobs 테이블을 가지고 설명한다. 두 테이블의 기본적인 정보는 다음과 같다. 

attachment:loop_join01.jpg

{{{
use pubs
exec sp_helpindex 'employee'
exec sp_helpindex 'jobs'
go
}}}
attachment:loop_join02.jpg

INDEX_KEYS 컬럼을 보면 어떤 컬럼에 인덱스가 생성되어 있는지 볼 수 있다. 여기서는 EMPLOYEE테이블과 JOBS테이블을 조인할 것인데 연결고리(FOREIGN KEY)가 되는 컬럼(여기서는 EMPLOYEE.JOB_ID 컬럼)에 인덱스가 잡혀있지 않은 것을 볼 수 있다. 그렇다면 다음과 같은 쿼리를 MSSQL SERVER 2000은 어떻게 실행계획을 세울 것인가? (물론 여기에서는 자동으로 통계정보를 업데이트하고 있다는 가정하에서 말하는 것이다.)

==== Loop Join의 기본 ====

{{{
set statistics io on --입출력의 양을 알아보기 위한 설정

--1
use pubs
select  e.emp_id, e.fname + e.lname as name, j.job_id, j.job_desc
from employee e inner join jobs j
on e.job_id = j.job_id
go

--테이블 'jobs'. 검색 수 0, 논리적 읽기 수 86
--테이블 'employee'. 검색 수 1, 논리적 읽기 수 2
}}}
attachment:loop_join03.jpg

실행계획을 보면 EMPLOYEE 테이블부터 읽혀진 것이 보인다. 실행계획은 오른쪽 우선, 위쪽 우선으로 먼저 실행된다. 트리를 생각하면 된다. 실행계획과 입/출력 양을 통해 위 쿼리를 분석해 보도록 하자. 결론부터 이야기하자면 이 쿼리는 NESTED LOOP JOIN조인이며, 내부조인(INNER JOIN)이다. 그리고 EMPLOYEE테이블이 먼저 읽혀졌다. 즉, 다음과 같은 순서로 테이블이 읽혀진 것이다. 

attachment:loop_join04.jpg

아래의 결과 집합에서 JOB_ID의 순서를 보면 13, 14, 6, 12 ... 의 순서임을 알 수 있다. EMPLOYEE 테이블을 먼저 풀스캔하는 과정에서 JOBS테이블의 클러스터드 인덱스(JOB_ID)와 비교하여 같은 것을 결과집합으로 뽑아냈다. 입/출력 양을 보면 스캔수가 43인 것을 볼 수 있다. 이것은 EMPLOYEE 테이블의 43개의 행에 대해서 JOBS 테이블의 JOB_ID를 비교하여 그런 수치가 나온 것이다. 먼저 풀스캔(클러스터드 인덱스 스캔은 풀스캔과 같다. 클러스터드 인덱스의 구조상..)을 한 원인은 EMPLOYEE.JOB_ID에 인덱스가 잡혀있지 않기 때문이다. 

attachment:loop_join05.jpg

만약 JOBS테이블을 먼저 읽는다고 한다면 어떤 실행계획이 잡혀질까? 다음과 같이 강제로 JOBS 테이블을 먼저 읽도록 쿼리해보자. 

{{{
--2
use pubs
select  e.emp_id, e.fname + e.lname as name, j.job_id, j.job_desc
from jobs j inner join employee e --순서를 바꾸고
on e.job_id = j.job_id
option (force order, loop join) --옵션으로 from절에 나열된 순서로 조인하도록 했다.
go
--테이블 'employee'. 검색 수 1, 논리적 읽기 수 29
--테이블 'jobs'. 검색 수 1, 논리적 읽기 수 2
}}}
attachment:loop_join06.jpg

결과의 순서도 틀려졌다. 
attachment:loop_join07.jpg

총 논리적 읽기 수(i/o)도 첫 번째 쿼리는 2+86이고, 두 번째 쿼리는 2+29로 차이가 난다. 별도의 처리 비용[* 정렬 비용]을 들이지 않고 정렬을 했다. 만약 정렬까지 필요했다면 Order By job_id를 했을 때와 이 쿼리와 비용차를 비교해서 비용이 적을 쿼리를 사용할 수도 있다. 

두 쿼리를 동시에 수행시켜 비용의 비교를 해보자. 
{{{
use pubs

--1
select  e.emp_id, e.fname + e.lname as name, j.job_id, j.job_desc
from employee e inner join jobs j
on e.job_id = j.job_id
go

--2
select  e.emp_id, e.fname + e.lname as name, j.job_id, j.job_desc
from jobs j inner join employee e --순서를 바꾸고
on e.job_id = j.job_id
option (force order, loop join) --옵션으로 from절에 나열된 순서로 조인하도록 했다.
go
}}}

attachment:loop_join08.jpg

==== 옵티마이저는 왜 employee 테이블부터 읽었을까? ====
비용을 비교해 본 결과 쿼리1:쿼리2 = 57:43으로 비용차이가 남에도 불구하고 옵티마이저는 왜 비용이 더 많이 발생하는 방식(employee 테이블부터 읽는 방식)으로 실행계획을 세웠을까? 만약 employee 테이블의 Row수가 1백만 건이라도 두 번째 쿼리가 비용이 더 적게 발생할까? employee 테이블의 1백만 건 짜리 복사본으로 테스트 해보자. 
{{{
--drop table #employee
select top 1000000 a.* into #employee
from employee a, employee b, employee c, employee d
}}}

테스트를 해보니 아예 Loop Join이 되지 않고, Hash Join으로 풀려 버린다. 일단 여기서는 Loop Join을 알아보기 위한 곳이므로 Join Hint를 주어 Loop Join으로 바꿔 보겠다. 

{{{
select  e.emp_id, e.fname + e.lname as name, j.job_id, j.job_desc
from #employee e inner loop join jobs j 
on e.job_id = j.job_id
--테이블 'jobs'. 검색 수 0, 논리적 읽기 수 2000000
--테이블 '#employee___000000000006'. 검색 수 1, 논리적 읽기 수 6455
}}}

분석을 해보자. 이 쿼리는 #employee 테이블을 풀스캔했다. 6455 페이지 만큼이 풀스캔의 양이다. 다음으로 jobs 테이블을 읽었다. jobs 테이블은 Row수가 얼마되지 않아 한 페이지에 다 넣을 수 있다. 하지만 Clustered Index가 생성되어 있어서 2페이지를 읽어야 한다. Clustered Index Seek를 해도 어쨌든 최소 2페이지를 읽어야 한다. #employee 테이블이 1백만 건이므로 1백만 번 Loop를 돌아가면서 jobs 테이블을 뒤졌다는 것이다. 그래서 jobs테이블의 I/O의 양이 2000000라는 숫자가 나온 것이다. 

{{{
select  e.emp_id, e.fname + e.lname as name, j.job_id, j.job_desc
from jobs j inner join #employee e --순서를 바꾸고
on e.job_id = j.job_id
option (force order, loop join, maxdop 1)
--테이블 'Worktable'. 검색 수 1, 논리적 읽기 수 3009266
--테이블 '#employee___000000000006'. 검색 수 1, 논리적 읽기 수 6455
--테이블 'jobs'. 검색 수 1, 논리적 읽기 수 2
}}}

이 쿼리도 위와 같이 분석을 해보자. jobs 테이블은 2 페이지를 읽었고, #employee 테이블에는 인덱스가 없으므로 6455 페이지를 jobs 테이블의 Row수 만큼 읽어서 뒤져야 한다. 그러므로 계산으로 해보면 14(jobs)건 * 6455 = 90370 페이지라는 결과가 나온다. 즉, jobs 테이블 1회 풀스캔, #employee 테이블 14회 풀스캔이다. 하지만 데이터베이스 시스템의 데이터는 여러 사람에게 공유되는 것이 기본이므로 한 테이블을 연속해서 풀스캔하는 것은 잠금(정확히 공유잠금)이 생기므로 약간의 블록킹을 유발하게 된다. 또한 중간에 다른 트랜잭션이 치고 들어와 Lock이라도 걸면 조회 성능은 급격히 나빠진다. 그래서 SQL Server는 임시테이블에 데이터를 삽입하여 14번의 풀스캔을 하는 Join 연산을 임시테이블에서 수행하게 하여 동시성을 높인다. set statistics io on의 결과에서 'Worktable'이 임시테이블(아래의 그래픽 실행계획에서 TableSpool)을 말한다. 

attachment:loop_join09.jpg

계산해 본 I/O양보다 3009266으로 훨신 많은 I/O양이 나왔다. 대략 이렇게 생각하면 된다. 임시 테이블에 입력할 때 발생한 I/O와 임시 테이블에는 인덱스가 생성되어 Seek하는데 3페이지 I/O가 되었다고 생각하면 된다. 실제 TableSpool에 마우스를 가져다 대면 14(jobs)*1000000(#employee) 만큼이 실제 행수가 된다. 실제로는 힌트를 빼면 옵티마이저가 이런 어처구니 없는 실행계획을 세우지 않으니 걱정하지 않아도 된다. 
==== employee.job_id에 Non-Clustered Index를 생성하면? ====
#employee.job_id에 Non-Clustered Index를 생성하면 실행계획이 어떻게 변할까? Loop Join 힌트를 빼고 실행을 해보자. 

{{{
create index idx_job_id
on #employee(job_id)
go

--1
select  e.emp_id, e.fname + e.lname as name, j.job_id, j.job_desc
from #employee e inner join jobs j
on e.job_id = j.job_id
go

--Table '#employee'. Scan count 1, logical reads 6455
--Table 'jobs'. Scan count 1, logical reads 2
}}}
attachment:loop_join10.jpg

결과는 [Hash Join]이다. 논리적 읽기 수도 두 테이블의 풀스캔 만큼이다. 어떤 사람은 새롭게 생성된 인덱스를 이용할꺼라는 예상을 했을 것인데 풀스캔을 하여 실망을 할 수도 있다. Loop Join을 했으면 Index Seek 연산자를 볼 수도 있었겠지만[* 실제로 해보라. Index Seek가 보이는가?] SQL Server는 Loop Join이 아닌 [Hash Join]을 선택하여 실행계획을 최적화시켰다. 그렇다고 실망하지 않아도 된다. 우리가 사용했던 #employee 테이블의 emp_id는 선택도가 좋지 않기 때문에 생성해준 인덱스는 거의 쓸모가 없다. 최초에 '#employee.job_id에 인덱스를 생성하면 실행계획이 어떻게 변할까?'라는 필자의 질문 자체가 븅신 같은 것이었다. 

==== employee.job_id에 Clustered Index를 생성하면? ====
employee.job_id에 Clustered Index를 생성하면 상황은 확 바뀐다. Clustered Index의 특성상 두 연결고리가 Clustered Index라면 [Merge Join]의 가능성이 높은데, jobs 테이블 워낙 작아 [Hash Join]의 가능도 매우 높다. 물론 Loop Join도 [Merge Join]만큼이나 가능성이 높다. 2000버전의 경우는 이렇게 양쪽 연결고리가 정렬된 상태라면 [Merge Join]으로 실행계획이 풀렸다. 하지만 2000이후 버전은 Loop Join으로 실행계획이 풀릴 가능성이 높다. 
{{{
select  e.emp_id, e.fname + e.lname as name, j.job_id, j.job_desc
from #employee e inner join jobs j
on e.job_id = j.job_id
go
}}}
attachment:loop_join11.jpg

==== 양쪽 연결고리[* 예제에서 job_id가 연결고리다]에 인덱스가 없다면? ====
양쪽 연결고리에 인덱스가 없다면 Loop Join은 생각치 말아야 한다. 간혹 Loop Join으로 실행계획이 풀릴 수 있겠으나 Index Spool 또는 Table Spool이 동반될 것이다. 연결고리가 아닌 연결되는 2개 이상의 테이블에서 액세스 양을 줄여 줄 수 있는 다른 조건이 존재한다면 Loop Join이 될 수도 있다. 양쪽 연결고리에 인덱스가 없는 경우 대부분 [Merge Join] 이나 [Hash Join]으로 풀린다. 가능성은 [Hash Join]이 더 많다. 

==== Network Join ====
분산된 서버 환경에서 물리적으로 분리된 서버의 각 테이블과 조인하는 경우가 심심치 않게 있다. 이런 경우를 'Network Join'이라고 정의[* 이런 용어가 있는지는 잘 모르겠다.]하자. 다음의 소스를 보자. 

{{{
SELECT
,	A.Col1
,	A.Col2
,	(SELECT TOP 1 Col3 FROM Remote.TestDB.dbo.TableB WHERE A.Key = B.Key) Col3
FROM dbo.TabeA A
WHERE A.Col4 BETWEEN 1 AND 1000
--결과는 1000건
}}}
attachment:nt_join.jpg

결과가 1000건이라면 Localhost와 Remote Server간에 네트워크 패킷을 1000회 주고 받으면서 Loop Join을 수행하게 된다. 매우 안 좋은 경우이다. 상황에 따라서는 이렇게 네트워크를 통해 패킷을 주고 받으면서 Join하는 것보다 원격 서버의 연결되는 테이블을 풀스캔해서 가져와 임시테이블에 담은 후, 임시 테이블과 Join하는 것이 더 빠른 경우도 있다. 가능하다면 Network Join이 발생한다면 항상 실행계획을 살펴보아야 한다. 가능하면 원격의 소스를 먼저 읽는 방법을 취하는 것이 바람직하다. 
==== Loop Join 정리 ==== 
Join 방식이 여러 가지가 있지만 여기에서는 Loop Join을 한다는 가정하에 정리한 것이다. 또한 병렬 처리 실행계획이면 또 틀려지므로 여기에서는 직렬처리(CPU 1개만 사용) 실행계획일 경우만으로 한정한다. 여러분은 아래의 경우에 따라서 어떤 액세스 경로[* 어떤 테이블을 먼저 읽을 것이지]가 유리할 것인지 의사결정을 할 수 있어야 한다. 

 * 두 Join Key 중 한쪽에 인덱스가 없는 경우
 * 두 Join Key 중 양쪽에 인덱스가 있는 경우
  * 양쪽 연결 고리가 모두 Clustered Index 인 경우
  * 한쪽 연결 고리만 Clustered Index 인 경우
  * 양쪽 연결 고리가 모두 Non-Clustered Index 인 경우
 * 두 Join Key 중 양쪽에 인덱스가 없는 경우

==== Advanced Loop Join ====
oracle에서 버전별도 자동 지원된다. 다음과 같이 테이블이 있다.
attachment:LoopJoin/01.png

이 테이블들은 물리적으로 다음과 같이 여러개의 블록에 분포되어 있다. 

attachment:LoopJoin/02.png

다음과 같이 동작한다. 여기서 물리I/O는 랜덤액세스를 말한다. 이는 마치 sql server에서 사원 테이블의 '부서ID'에 클러스터드 인덱스를 생성했을 때와 같이 I/O가 줄어든다. 이는 [클러스터링 팩터]에 따라서 성능이 다름을 의미한다.

attachment:LoopJoin/03.png

==== 참고자료 ====
 * attachment:LoopJoin/Join_Algorithm.pdf