조인 기본 원리

 

 

🪡 Nested Loop Join

 

💡기본 메커니즘

중첩 루프의 기본적인 구조는 다른 프로그래밍 언어와 다르지 않다. 자바의 for 문을 생각한다면 다음과 같다.

for(int i = 0; i < n ; i++){
	for(int j = 0; j < i; j++){
    }
}

 

이와 같은 중첩 for문을 생각하고, NL Join을 생각하면 이것도 같은 구조로 돌아간다는 것을 알 수 있다.

이것을 쿼리로 본다면 아래와 같다.

/* PL/SQL */
begin 
	for outer in (select deptno, empno, rpad(ename, 10) ename from emp) loop -- outer 루프 
		for inner in (select dname from dept where deptno = outer.deptno) loop -- inner 루프 
		dbms_output.put_line(outer.empno||' : '||outer.ename||' : '||inner.dname); 
    	end loop; 
	end loop; 
end;


/* 쿼리 */
select /*+ ordered use_nl(d) */ e.empno, e.ename, d.dname 
from emp e, dept d 
where d.deptno = e.deptno 

select /*+ leading(e) use_nl(d) */ e.empno, e.ename, d.dname 
from dept d, emp e 
where d.deptno = e.deptno

 

 

🐤 NL Join 수행 과정 분석

select /*+ ordered use_nl(e) */ e.empno, e.ename, d.dname, e.job, e.sal 
from dept d, emp e 
where 	e.deptno = d.deptno …………… ① 
		and d.loc = 'SEOUL' …………… ② 
        and d.gb = '2' …………… ③ 
        and e.sal >= 1500 …………… ④ 
order by sal desc

 

Index

* pk_dept : dept.deptno * dept_loc_idx : dept.loc * pk_emp : emp.empno * emp_deptno_idx : emp.deptno * emp_sal_idx : emp.sal

 

다음과 같은 문장을 수행하고, 인덱스가 지정되어 있다고 할 때 실행 계획은 어떻게 될까.

 

1. (2)에 해당하는 dept.log = 'SEOUL' 에 만족하는 레코드를 찾기 위해 dept_loc_idx 인덱스를 범위 스캔한다.

2. 1에서 가져온 rowid를 이용하여 dept 테이블에 엑세스하고, (3)에 해당하는 d.gb = '2' 조건에 만족하는 레코드를 찾는다.

3. dept 테이블에서 읽은 deptno 값을 가지고 (1)에 만족하는 값을 찾기 위해 emp_depton_idx를 범위 스캔한다.

4. emp_deptno_idx 인덱스에서 가져온 rowid를 기반으로 emp테이블에 엑세스하여 (4)에 해당하는 sal >= 1500 조건을 만족하는 레코드를 찾는다.

5. 값을 만족하는 레코드들을 sal 칼럼 기준 내림차순 정렬한다.

 

이것을 보다보면 중첩 루프와 같은 것을 볼 수 있다. 만약, 조건에 부합하는 것을 찾으면 하위 테이블로 내려가 같은 값을 찾고, 없다면 다시 위로 올라가 행위를 반복한다. 여기에서, 조인을 튜닝할 때 루프를 설계할 때와 마찬가지로 부하조건이 발생하지 않도록 필터링되는 비율을 확인하고, 각 단계의 수행 횟수를 분석하여 과도한 Random 엑세스가 발생하는 것을 방지하거나, 인덱스를 사용하는 방법을 사용해야 한다.

 

🐣NL Join의 특징

1) Random 엑세스 위주의 조인 방식

- 인덱스 구성이 완벽하더라도 대량의 데이터를 조인할 때 비효율적이다.

2) 조인을 한 레코드씩 순차적으로 진행

- Random 엑세스를 하지만, 조인 자체는 순차적으로 진행하기 때문에 대용량 집합이더라도 극적인 응답 속도가 가능. 그렇기 때문에 선행 엑세스 테이블의 처리 범위에 의해서 전체 일량이 결정됨.

3) 인덱스 구성 전략 필요

- 1번과 2번의 특징대문에 인덱스 구성과 컬럼 구성에 의한 영향을 많이 받음.

4) 소량의 데이터를 처리하거나 부분범위처리가 가능한 온라인 트랜잭션 환경에 적합

 

 

 

🧶 Sort Merge Join

 

NL Join에서는 조인 칼럼을 선두로 가진 인덱스가 없을 경우 Outer 테이블에서 읽히는 건마다 Inner 테이블 전체를 스캔하기 때문에 인덱스의 유무가 굉장히 중요하다. 선두 인덱스가 없을 경우 옵티마이저는 Sort Merge Join이나 Hash Join을 고려하는데, Sort Merge Join은 두 테이블을 각각 정렬한 다음 두 집합을 머지하면서 조인을 수행한다. 실행 순서는 아래와 같다.

 

1) 소트 단계 : 양쪽 집합을 조인 칼럼 기준으로 정렬

2) 머지 단계 : 정렬된 양쪽 집합을 서로 머지

 

* 만약 조인 칼럼에 인덱스가 있으면 1의 단계를 거치지 않고 바로 조인도 가능하다. 

 

🐣 기본 메커니즘

Sort Merge Join은 기본적으로 조인할 테이블들을 먼저 정렬을 하고, 그 다음 맞는 것을 찾아서 그 부분까지 가져온다. 아주 쉽게 [1, 2, 3, 4] 의 a 테이블과 [ 1, 1, 3, 4, 2, 2, 5 ] 의 b 테이블이 있다고 가정했을 때 진행 상황은 다음과 같다.

1) a 테이블을 [1, 2, 3, 4] 로 정렬한다.

2) b 테이블을 [1, 1, 2, 2, 3, 4, 5] 로 정렬한다.

3) a 테이블의 1과 같은 b 테이블의 1, 1을 찾고, 위치를 기억한다.

4) 위치를 첫번째 인덱스로 하여 다음 순서부터 탐색한다.

 

🐤 Sort Merge Join의 특징

1. Join 전에 양쪽 집합을 정렬한다.

- NL Join은 정렬 없이 Outer 집합을 한 건식 차례대로 조인하지만, Sort Merge Join은 양쪽 집합을 조인 칼럼 기준 정렬한 후 조인을 시작한다. 이와 같은 방식은 Random 엑세스 방식의 비효율을 개선할 수 있지만, 초 대용량의 테이블일 경우 정렬 자체가 큰 비용이 들기 때문에 성능 개선이 미미할 수 잇다. 그러나, 일반 인덱스 또는 클러스터형 인덱스와 같이 미리 정렬되어있는 오브젝트를 이용한다면 정렬작업 없이 바로 조인 수행이 가능하기 때문에 좋은 대안이 될 수 있다.

2. 부분적으로, 부분 범위 처리가 가능하다.

- Sort Merge Join은 양쪽 집합을 정렬해야 하기 대분에 부분범위처리가 불가능할 것처럼 보이지만 부분적으로는 가능하다. for문을 돌다가 특정 조건에서 break를 거는 것과 같이, 사용자가 일부 로우만 Fetch 하다가 멈춘다면 Outer 집합은 끝까지 읽지 않은 상태로 끝날 수 있다.

3. 테이블별 검색 조건에 의해 전체 일량이 좌우된다.

- NL Join은 Outer 집합의 모든 건마다 Inner 집합을 탐색하기 때문에 조인 대상이 되는 건수에 의해 전체 일량이 좌우되지만, Sort Merge Join은 두 집합을 각각 정렬한 후에 조인하기 때문에 각 집합의 크기, 즉 테이블별 검색 조건에 의해 전체 일량이 좌우된다.

4. 스캔 위주의 조인 방식

- Inner 테이블을 반복 엑세스하지 않기 대문에 머지 과정에서 Random 엑세스가 발생하지 않지만, 테이블 검색 조건에 해당하는 대상 집합을 찾을 때 인덱스를 이용한 Random 엑세스 방식으로 처리될 수 있다. 이때 발생하는 엑세스량이 많다면 Sort Merge Join의 이점이 사라질 수 있다.

 

 

 

🏹 Hash Join

 

💡기본 메커니즘

Hash Join은 둘 중 작은 집합을 읽어 해시 영역에 테이블을 생성하고, 반대쪽 큰 집합을 읽은 뒤 해시 테이블을 탐색하면서 조인하는 방식이다.

출력값을 미리 알 수는 없지만 같은 입력값에 대하여 같은 출력값을 보장하며, 다른 입력값에 대해 출력값이 같을 수 있는데 이것을 '해시 충돌' 이라고 한다. 해시 충돌이 발생하면 입력값이 다른 엔트리가 한 해시 버킷에 담길 수 있다.

 

1) 해시 테이블 생성

- 두 집합 중 작다고 판단되는 집합을 읽어 해시 함수를 사용, 테이블을 만든다. 

2) Probe Input 스캔

- 선택되지 않은 나머지 집합(큰 집합) 을 스캔한다.

3) 해시 테이블 탐색

- 2에서 읽은 데이터로 테이블을 탐색한다. 여기에서는, 함수에서 리턴받은 버킷 주소로 찾아가 체인을 스캔하는 방식을 사용한다.

 

Hash Join은 Random 엑세스 부하가 없으며 정렬하는 부담 또한 없다. 그러나, 해시 테이블을 생성하는 비용이 들기 때문에 작은 집합(Build Input)이 작을 때 효과적이다. 도한, 해시 키 값으로 사용되는 컬럼에 중복 값이 거의 없어야 효과적이다.

 

🐤 Build Input이 가용 메모리 공간을 초과한다면?

Hash Join은 Hash Build를 위해 가용한 메모리 공간에 충분히 담길 정도로 작아야 효과적인데, 만약 그것이 불가능할 때 DBMS는 'Grace Hash Join' 이라고 알려진 조인 알고리즘을 사용하게 된다.

1) 파티션 단계

- 조인되는 양쪽 집합 모두 조인 칼럼에 해시 함수를 적용하고, 반환된 값에 따라서 동적 파티셔닝을 수행한다. 독립적 수행을 위하여 여러 개의 서브집합으로 분할한다고 생각하면 된다. 그러나 파티션 단계에서 양쪽 집합을 모두 읽어서 디스크의 Temp 공간에 저장하기 때문에 성능이 크게 떨어진다.

2) 조인 단계

- 파티션 관계가 완료되면 각 파티션의 pair에 대하여 하나식 조인을 수행한다. 이대, 각각 저장되어있기 때문에 Build Input과 Probe Input은 독립적으로 결정된다. 그렇기 때문에 파티션이 진행되기 전에 어느 쪽이 작은 테이블이었는지에 상관 없이 각 파티션 pair 별로 작은 파티션을 Build Input으로 선택하여 해시 테이블을 생성하고, 후에 반대쪽 파티션 로우를 읽으면서 탐색하는 분할 정복 방식을 사용한다.

 

🐣 Build Input 해시 키 값에 중복이 많을 때?

해시 알고리즘의 성능은 해시 충돌을 얼마나 최소화할 수 있는 지에 따라 달려있는데, 이를 방지하기 위해서는 그만큼 많은 버킷을 할당해야 한다. 키 칼럼에 중복 값이 많다면 하나의 버킷에 많은 엔트리가 달리게 되고, 그렇게 된다면 해시 버킷을 빠르게 찾는다고 하더라도 스캔하는 과정에서 많은 시간을 허비하기 때문에 탐색 속도가 저하된다.

 

✨Hash Join 사용 기준

- 한쪽 테이블이 가용 메모리에 담길 정도로 충분히 작아야 함

- Build Input 해시 키 칼럼에 중복이 거의 없어야 함

이 두 조건이 제일 중요한 조건이며, 최적의 성능을 보장받을 수 있다. 또한, 아래와 같은 상황에서 사용하는 것이 제일 효과적이다.

- 조인 칼럼에 적당한 인덱스가 없어 NL Join이 비효율적일 때

- 조인 칼럼에 인덱스가 존재해도 NL Join 드라이빙 집합에서 Inner 쪽 집합으로의 조인 엑세스량이 많을 때

- Sort Merge Join 하기에 두 테이블이 너무 커 정렬 부하가 심할 때

- 수행빈도가 낮고 조인할 때

 

* Hash Join은 다른 조인보다 훨씬 속도가 빠르지만, 수행시간이 짧으면서도 수행 빈도가 매우 높은 쿼리를 사용하게 된다면 수행이 끝나고 바로 소멸하는 Hash 구조 상 계속해서 CPU와 메모리 사용률을 증가시키게 되며 자원 확보를 위한 경합을 발생시킨다.

 

 

 

🛞 Scalar Subquery

 

쿼리에 내장되어있는 또다른 쿼리 블록을 서브쿼리라고 통칭하는데, 그 중에서 함수처럼 한 레코드당 정확히 하나의 값만을 리턴하는 서브쿼리를 'Scalar Subquery' 라고 한다. 몇 가지의 예외사항을 뺀다면 칼럼이 올 수 있는 대부분의 위치에서 사용이 가능하다.

 

Scalar Subquery에는 내부적으로 캐싱 기법이 작용되며, 이를 이용한 튜닝이 자주 행해진다.

 

이를 사용할 때 한 레코드당 하나의 값만 읽는다는 특징때문에 사용할 때 반복 또는 테이블 전체 스캔 등의 비효율적인 쿼리를 쓰게 되는데, 구하고자 하는 값들을 모두 결합한 뒤 바깥쪽 엑세스 쿼리에서 substr 함수로 분리하는 형태로 사용할 수 있다.

 

/* Befor */
select d.deptno, d.dname, avg_sal, min_sal, max_sal 
from dept d right outer join (select deptno, avg(sal) avg_sal, min(sal) min_sal, max(sal) max_sal 
								from emp group by deptno) e 
			on e.deptno = d.deptno 
where d.loc = 'CHICAGO'


/* after */
select deptno, dname , to_number(substr(sal, 1, 7)) avg_sal , to_number(substr(sal, 8, 7)) min_sal , to_number(substr(sal, 15)) max_sal 
from ( select d.deptno, d.dname ,(select lpad(avg(sal), 7) || lpad(min(sal), 7) || max(sal) 
									from emp 
       								where deptno = d.deptno) sal 
        from dept d 
        where d.loc = 'CHICAGO' )