6장 - 결합

생성일

2023/09/28 07:39

태그

결합의 종류

결합 알고리즘 성능

결합이 느린 경우

결합의 종류

SQL에는 크로스 결합, 내부 결합, 외부 결합, 자기 결합, 등가/비등가 결합, 자연 결합과 같이 결합 연산이 굉장히 많다.

기능적 관점으로 보았을 때는 크로스 결합, 내부 결합, 외부 결합으로 분류된다. 이 세 가지는 서로 배타적인 분류로, 내부 결합이면서 외부 결합인 조합은 있을 수 없다.

등가/비등가 결합은 결합 조건으로 등호(=)를 사용하는지 이외의 부등호(>, >=, … 등)를 사용하는지 차이를 의미한다.

자연 결합은 등가 결합 조건을 간단하게 작성하는 방법이다.

SELECT * FROM Employees E INNER JOIN Departments D ON E.id = D.id;
SQL
복사

이런 SQL 구문을 자연 결합을 사용하면 아래와 같이 작성할 수 있다.

SELECT * FROM Employees NATURAL JOIN Departments;
SQL
복사

사실 자연 결합으로 인해 줄어드는 코드의 양이 그다지 줄어들지 않고, 필드 이름이 다르거나 자료형이 다르면 사용할 수 없는 등의 이유로 인해 거의 사용 되지 않는다.

크로스 결합

SELECT * FROM Employees CROSS JOIN Departments;
SQL
복사

위와 같은 두 테이블에 크로스 결합을 적용하면 아래와 같이 결과가 나온다.

이처럼 크로스 결합을 수행하게되면 (A 테이블의 조회 개수 * B 테이블의 조회 개수)만큼 출력된다. 크로스 결합은 수학에서 데카르트 곱이라고 불리는 연산으로, 2개 테이블의 레코드에서 가능한 모든 조합을 구하는 연산이다.

실무에서는 이와 같은 결과가 필요한 일이 없기도하고 크로스 연산 자체가 비용이 매우 많이 드는 연산이기 때문에 사용되지 않는다.

SELECT * FROM Employees, Departments;
SQL
복사

이 SQL 구문도 위와 동일한 결과를 출력한다. WEHRE 절을 통해 결합 조건을 지정해 주지 않으니, DBMS에서 두 테이블에서 가능한 모든 조합을 만들어 출력한다.

이러한 실수를 막으려면 표준 SQL에 맞게 결합 구문을 사용하는 것이 좋다. INNER JOIN과 같은 표준 SQL 구문에서는 결합 조건이 없으면 오류가 발생하여, 이러한 실수를 방지할 수 있다는 장점도 있다.

내부 결합

위의 테이블에서 사원의 부서 이름을 알기 위해서는 양쪽 테이블에 모두 존재하는 부서 ID 필드를 결합 키로 사용하여 결합된 정보를 가져와야 한다.

SELECT E.emp_id, E.emp_name, E.depth_id, D.dept_name FROM Employees E 
		INNER JOIN Departments D ON E.depth_id = D.dept_id;
SQL
복사

크로스 결합의 결과와 비교해본다면 내부 결합의 결과는 크로스 결합의 부분 집합임을 알 수 있고, 이 때문에 내부 결합이라 불린다.

이와 같은 내부 결합은 상관 서브쿼리로도 작성할 수 있다.

SELECT E.emp_id, E.emp_name, 
				(SELECT D.dept_name FROM Departments D
					WHERE E.dept_id = D.dept_id) AS dept_name
		FROM Employees E;
SQL
복사

하지만 기본적으로 상관 서브쿼리보다 결합을 사용하는 것이 좋다. 상관 서브쿼리를 스칼라 서브쿼리로 사용하면 레코드 수만큼 상관 서브쿼리가 실행돼 비용이 높아지기 때문이다.

외부 결합

외부 결합은 내부 결합과 배타적인 연산으로, 내부가 데카르트 곱의 부분 집합을 의미한다면 외부는 데카르트 곱의 부분 집합이 아니라는 것을 의미한다. 다만, 경우에 따라서 데카르트 곱의 부분 집합이 되기도 한다.

외부 결합에는 왼쪽 외부 결합, 오른쪽 외부 결합, 완전 외부 결합이 있다. 왼쪽 외부 결합과 오른쪽 외부 결합은 실질적으로 같은 기능을 가지며, 마스터가 되는 테이블을 왼쪽에 두면 왼쪽 외부 결합이고 오른족에 두는 것이 오른쪽 외부 결합니다.

// 왼쪽 외부 결합
SELECT E.emp_id, E.emp_name, E.dept_id, D.dept_name FROM Departments D 
		LEFT OUTER JOIN Employees E ON D.dept_id = E.dept_id;

// 오른쪽 외부 결합
SELECT E.emp_id, E.emp_name, E.dept_id, D.dept_name FROM Employees E 
		RIGHT OUTER JOIN Departments D ON E.dept_id = D.dept_id;
SQL
복사

위의 두 SQL은 동일한 결과를 출력한다.

마지막 결과를 보면 알 수 있듯이, 마스터 테이블 쪽에만 존재하는 키가 있다면 해당 레코드를 제거하지 않고 보존한다.

외부 결합과 내부 결합 차이

위의 결과에서 마지막 레코드를 보면, 크로스 결합의 결과에 없던 레코드가 출력되었다. 이 레코드가 외부 결합의 외부의 의미에 해당한다. 외부 결합은 마스터 테이블의 정보를 보존하여 NULL을 생성하지만, 크로스 결합이나 내부 결합은 NULL을 생성하지 않는다.

자기 결합

자기 결합은 문자 그대로 자기 자신 테이블과 결합하는 연산이다. 자기 결합은 생성되는 결과를 기준으로 분류하는 것이 아니라, 연산 대상으로 무엇을 하는가에 따른 분류이다. 분류가 다르기 때문에 자기 결합 + 내부 결합이나 자기 결합 + 크로스 결합과 같은 조합이 발생할 수 있다.

이와 같은 테이블이 있을 때, 자기 결합 + 크로스 결합을 구하면 다음과 같다.

SELECT D1.digit + (D2.digit * 10) AS seq
		FROM Digits D1 CROSS JOIN Digits D2;
SQL
복사

크로스 결합의 레코드 수는 결합되는 테이블들의 레코드 수의 곱이므로, 자기 결합으로 크로스 결합을 하면 N * N 만큼의 레코드가 출력된다.

자기 결합을 수행하는 경우는 일반적으로 동일한 테이블에 서로 다른 별칭을 붙여 마치 다른 테이블인 것처럼 조작한다. 물리 레벨에서 보면 같은 테이블과 결합하는 것이지만, 논리 레벨에서 보면 데이터가 같은 서로 다른 두 테이블을 결합한다고 볼 수 있다.

결합 알고리즘 성능

SQL 결합 연산을 수행할 때 내부적으로 옵티마이저가 선택할 수 있는 알고리즘은 크게 Nested Loops, Hash, Sort Merge 세 가지가 있다. 옵티마이저는 데이터의 크기나 결합 키의 분산에 따라 어떤 알고리즘을 선택할지 결정한다.

세 알고리즘은 대부분 DBMS가 지원하지만, MySQL처럼 Nested Loops와 그 파생 버전만 지원하고 Hash나 Sort Merge를 사용하지 않는 DBMS도 있다. 하지만 Nested Loops는 모든 DBMS에서 지원한다.

Nested Loops

Nested Loops는 이름 그대로 중첩 반복을 사용하는 알고리즘으로, SQL은 한 번에 두 개의 테이블만 결합하므로 본질적으로 이중 반복을 의미한다.

Nested Loops의 세부 동작은 다음과 같다.

결합 대상 테이블(Table_A)에서 레코드를 하나씩 반복해가며 스캔한다. 이 테이블을 구동 테이블(driving table) 혹은 외부 테이블(outer table)이라 부른다. 또 다른 테이블(Table_B)은 내부 테이블(inner table)이라 부른다.

구동 테이블의 레코드 하나마다 내부 테이블의 레코드를 스캔해서 결합 조건에 맞는지 확인한다.

위의 2번 과정을 구동 테이블의 모든 레코드에 반복한다.

이런 Nested Loops는 Table_A와 Table_B를 결합할 때 접근하는 레코드 수는 각 테이블의 레코드 수 R(A)와 R(B)의 곱 R(A) X R(B)가 된다. 따라서 Nested Loops의 실행 시간은 레코드 수에 비례한다.

한 번에 처리하는 레코드 수가 Hash나 Sort Merge에 비해 적기 때문에, 알고리즘에 따른 메모리 사용량 또한 더 적다.

이런 Nested Loops는 매우 단순해보이지만, 결합 성능에서 가장 중요하다. 어떤 테이블을 구동 테이블로 사용하느냐에 따라 큰 의미를 가진다. 정확히 말하면 구동 테이블이 작을수록 성능이 좋아진다.

실제 접근하는 레코드 수는 R(A) X R(B)와 R(B) X R(A)로 동일하지만, 내부 테이블의 결합 키 필드에 인덱스가 존재한다면 내부 테이블을 완전히 순회하지 않아도 되기 때문이다.

내부 테이블에 인덱스가 사용되는 경우를 이전의 예시를 통해 쿼리로 확인해보면 다음과 같다.

SELECT E.emp_id, E.emp_name, E.dept_id, D.dept_name FROM Employees E
		INNER JOIN Departments D ON E.dept_id = D.dept_id;
SQL
복사

PostgreSQL 실행 계획

Oracle 실행 계획

하지만 내부 테이블에 인덱스가 사용되지 않으면 테이블 풀 스캔이 2번 발생한다

PostgreSQL 실행 계획

Oracle 실행 계획

결합 키가 내부 테이블에 대해 유일한 경우 이처럼 INDEX UNIQUE SCAN이 발생하고, 이로 인해 굉장히 효율적으로 레코드에 접근할 수 있다. 반면 결합 키가 내부 테이블에 대해 유일하지 않다면 여러 개의 레코드가 히트되고, 히트된 레코드들에 대해 반복을 적용해야 한다. 이런 경우에는 INDEX RANGE SCAN이 되고, 그럼에도 테이블 풀 스캔보다 효율적이다.

Nested Loops에서 인덱스를 통한 시간 단축의 요지는 더 큰 테이블에 인덱스를 적용하여 반복 생략 효과를 올려 내부 테이블로 설정하는 것이다.

Nested Loops 단점

더 작은 구동 테이블 + 내부 테이블 결합 키에 인덱스로 성능이 충분할 수 있지만, 기대만큼 성능이 나오지 않을수도 있다. 보통 이런 경우는 결합 키로 내부 테이블에 접근할 때 히트되는 레코드가 너무 많아서 반복을 생략한다 해도 절대적으로 많은 양의 반복이 발생하여 지연이 일어나는 것이다.

결국 SQL의 성능은 처리하는 데이터양에 의존한다. 이런 문제에 대처하는 방법은 두 가지가 있다.

•

구동 테이블로 큰 테이블을 선택하기

내부 테이블에 대한 접근이 기본 ID로 수행되므로, 항상 하나의 레코드에 접근하는 것이 보장된다. 이런 경우는 거대 테이블 접근 비용이 현실적인 범위라면 굉장히 효과적이다.

•

Nested Loops 대신 Hash 선택하기

Hash

해시는 일정 수준의 유일성과 균일성을 가진 값을 출력하는 해시 함수를 통해 얻은 해시값으로 데이터를 찾는 방식이다.

SQL에서 해시 결합은 작은 테이블을 스캔 후, 결합 키에 해시 함수를 적용해 해시값을 얻는다. 그 후 큰 테이블을 스캔하고 결합 키가 해시값에 존재하는지를 확인한다.

Nested Loops에 비해 비교하는 레코드 수가 줄기 때문에 성능적으로는 더 빠르지만, 해시 테이블 자체가 워킹 메모리에 저장되기 때문에 해시 테이블이 너무 크면 TEMP 탈락이 발생해 지연이 생긴다. 작은 테이블에서 해시 테이블을 만드는 이유도 같은 이유에서 해시 테이블을 조금이라도 작은 것으로 만들기 위함이다.

PostgreSQL 실행 계획

Oracle 실행 계획

해시 결합은 반드시 양쪽 테이블의 레코드를 전부 읽어야하기 때문에, 위처럼 테이블 풀 스캔이 두번 발생하는 경우가 많다.

해시 결합은 위에서 언급했듯이, 해시 테이블을 만들어 사용하기 때문에 Nested Loops보다 메모리를 많이 사용한다. 메모리가 부족하면 저장소를 사용하기 때문에 성능이 크게 떨어질 수 있다. 또한 해시는 입력값의 순서를 알지 못하기 때문에, 등치 결합(=)에만 사용할 수 있다.

해시 결합은 주로 Nested Loops가 효율적이지 않을 때 차선책으로 사용된다. Nested Loops에서 두 테이블의 레코드 수가 비슷하여 구동 테이블을 선택하기 애매한 상황과, 구동 테이블은 있지만 내부 테이블에 인덱스가 없거나 내부 테이블에서 히트되는 레코드가 너무 많은 경우에 사용된다.

해시 결합은 메모리를 사용하기 때문에, 동시 실행성이 높은 OLTP 처리(사용자 요구에 즉시 응답해야 하는 처리, 대부분의 웹 어플리케이션이 해당된다)를 수행할 때 해시 결합이 사용되는 경우 메모리가 부족해져 지연이 발생할 리스크가 있다. 때문에 해시의 기본 전략은 동시 처리가 적은 야간 배치나 BI/DWH와 같은 시스템에 한해 사용하는 것이다.

Sort Merge

Nested Loops가 비효율적인 경우 해시 결합말고도 Sort Merge를 사용하기도 한다. Merge Join이라고도 불리는 Sort Merge는, 결합 테이블들을 각각 결합 키 기준으로 정렬 후 일치하는 결합 키를 찾는 방식이다.

Sort Merge는 구동 테이블과 내부 테이블 모두 정렬해야하기 때문에, Nested Loops 보다 많은 메모리를 사용하고 일반적으로 해시 결합보다도 많은 메모리를 사용한다. 그로 인해 해시 결합과 마찬가지로 TEMP 탈락이 발생해 I/O 비용이 늘어 지연이 발생할 리스크가 있다.

등치 결합만 비교할 수 있는 해시 결합과는 다르게 부등호(<, <=, >, >=)에도 사용할 수 있다. 하지만 부정 조건(<>) 결합에서는 사용할 수 없다.

원리적으로는 테이블이 결합 키 기준으로 정렬되어 있다면, 정렬을 생략할 수 있다. 다만 SQL에서 테이블에 있는 레코드의 물리적인 위치를 알고 있을 때만 가능하여, 이러한 생략은 구현 의존적이다.

Sort Merge는 테이블 정렬에 많은 메모리와 시간을 사용할 가능성이 있기 때문에, 테이블 정렬을 생략할 수 있는 경우에만 사용을 고려해보고 그 외의 경우에는 Nested Loops와 Hash를 우선적으로 고려하자.

의도하지 않은 크로스 결합

실무에서는 크로스 결합을 거의 사용할 일이 없다. 하지만 삼각 결합이라 불리는 패턴으로 의도치 않게 크로스 결합이 발생할 수 있다.

SELECT A.col_a, B.col_b, C.col_c FROM Table_A A
		INNER JOIN Table_b B ON A.col_a = B.col_b
		INNER JOIN Table_C C ON A.col_a = C.col_c;
SQL
복사

위 SQL 구문은 결합 조건이 Table_A Table_B와 Table_A Table_C에 있는 3개의 테이블을 결합한다.

이런 상황에서는 다양한 실행 계획이 나올 수 있다.

이 중 어떤 테이블을 구동 테이블을 선택하느냐에 따라 Nested Loops로 결합을 할 수도 있고, 크로스 결합으로 결합을 할수도 있다.

Table_A를 구동 테이블로 선택하면 Nested Loops 결합을 사용한다.

하지만 Table_B를 구동 테이블로 Table_C와 결합하고 그 결과를 Table_A에 결합하고자 한다면 아래와 같이 크로스 결합이 발생한다.

MERGE JOIN CARTESIAN이 Oracle에서 크로스 결합을 수행할 때 실행 계획이다. 이와 같이 크로스 결합이 선택되는 이유는 옵티마이저에서 아래처럼 Table_A보다 나머지 두 테이블이 충분히 작아서 크로스 결합이 적합하다고 판단하면 발생한다.

이런 의도하지 않은 크로스 결합으로 회피하는 방법은 결합 조건이 없는 Table_B와 Table_C에 불필요한 결합 조건을 추가해주는 것이다.

SELECT A.col_a, B.col_b, C.col_c FROM Table_A A
		INNER JOIN Table_b B ON A.col_a = B.col_b
		INNER JOIN Table_C C ON A.col_a = C.col_c 
												AND B.col_b = C.col_c;
SQL
복사

결합이 느린 경우

최적의 결합 알고리즘

결합의 세 알고리즘에 대해 장점과 단점을 정리하면 아래와 같다.

옵티마이저는 이런 장단점을 고려해 실행 계획을 세우지만, 여러 이유에 의해 최적의 결합 알고리즘을 선택하지 못할 수 있다. 레코드 수 관점에서 최적의 결합 알고리즘은 다음과 같다.

•

소규모 - 소규모

결합 대상 테이블들이 전부 작은 경우에는 어느 알고리즘을 선택하든 성능 차이가 별로 없다.

•

소규모 - 대규모

소규모 테이블을 구동 테이블로 하는 Nested Loops를 사용한다. 대규모 테이블의 결합 키에 인덱스를 만들어주는 것으로 성능을 올릴 수 있고, 내부 테이블에 히트되는 레코드가 많다면 내부 테이블을 바꾸거나 Hash를 고려해야 한다.

•

대규모 - 대규모

기본적으로 Hash를 사용하지만, 결합 키가 정렬되어 있는 상태라면 Sort Merge를 사용한다.

실행 계획 제어

RDB는 원칙적으로 실행 계획을 통계 정보를 바탕으로 옵티마이저가 자동으로 세우지만, DBMS에 따라 실행 계획을 사용자가 선택하여 바꿀 수 있다. Oracle은 사용자가 힌트 구문을 통해 원하는 알고리즘과 구동 테이블 선택 모두 가능하지만, DB2는 사용자가 실행 계획에 대해서 아무것도 선택할 수 없다.

사용자가 실행 계획을 제어하면, 데이터양과 카디널리티가 데이터베이스 운용에 따라 지속적으로 바뀌기 때문에 적절했던 실행 계획이 어느 순간 적절하지 못하게 될 수 있다. 옵티마이저가 동적으로 실행 계획을 선택하는 목적이 위와 같은 이유이고, 때문에 실행 계획을 직접 선택하는 것은 DBMS의 진화에 역행하는 발상이다.

사용자가 실행 계획을 제어하기 위해서는 이러한 리스크를 충분히 검토하고, 미래의 시스템 상황도 예측하여 적절한 실행 계획을 선택해야한다. 또한 데이터의 특성을 바탕으로 시간에 따라 데이터 변화를 유사적으로 모방하여 성능 테스트를 실시해야 한다.

옵티마이저가 실행 계획을 잘못 선택하는 경우

옵티마이저에게 맡기더라도 최적의 실행 계획이 선택되지 않는 경우가 있다. 대표적으로 장기적인 운용 중 데이터 양의 증가로 인해 통계 정보가 변했을 때, 일정한 역치를 넘으면 옵티마이저가 실행 계획을 변화시키며 예측하지 못하는 돌발적인 슬로다운 발생한다.

이런 실행 계획 변동이 가장 자주 발생하는 연산이 여러 개의 알고리즘을 선택할 수 있는 결합 연산이다. 따라서 SQL의 성능 변동 위험을 줄이려면 되도록 결합을 피해야 한다.