[DB] SQL - JOIN

이 글은 데이터베이스 스터디 중 학습한 내용을 정리한 것입니다.

 

 

---

 

 

JOIN 수행 원리

 조인이란 두 개 이상의 테이블을 하나의 집합으로 만드는 연산이다. JOIN 절 뿐만 아니라, SQL문에서 FROM절에 두 개 이상의 테이블이 나열된 경우에도 조인이 수행된다. 다만, 여러개의 테이블에 대해 JOIN이 수행되더라도, JOIN은 실제 동작할 때 두개의 테이블을 대상으로 수행된다. 여러개의 테이블을 다룰때는 연쇄적으로 JOIN이 수행되는 것이다. 조인 기법은 여러가지가 존재하는 데, 대표적으로 NL JOIN, Hash JOIN, Sort Merge JOIN이 있다.

 

1. NL JOIN(Nested Loop JOIN)

 NL JOIN은 프로그래밍에서 사용하는 FOR 반복문을 중첩으로 사용한 것과 유사하다. 반복문의 외부에 있는 테이블을 선행 테이블 또는 외부 테이블 (또는 드라이빙 테이블)이라고 하고, 반복문 내부에 있는 테이블을 후행 테이블 또는 내부 테이블(또는 드리븐 테이블)이라고 한다.

 

 먼저 선행 테이블에서 조건을 만족하는 행을 추출하여 후행 테이블을 읽으면서 조인을 수행한다. 이 작업은 선행 테이블의 조건을 만족하는 모든 행의 수만큼 반복한다. 즉, 선행 테이블에서 추출된 행만큼 곱해진 연산이 수행되는 것이다. 따라서, JOIN이 수행될 테이블 중에서, 추출되는 행의 개수가 가장 적은 테이블을 조인 순서상 선행 테이블로 지정하는 것이, 전체 연산을 줄이는데 효과적인다.

 

 NL JOIN은 랜덤 방식으로 데이터를 액세스하기 때문에 처리 범위가 좁은 것이 유리하다.

NL JOIN의 작업 방법은 다음과 같다.

1. 선행 테이블에서 주어진 조건을 만족하는 행을 찾음
2. 선행 테이블의 조인 키 값을 가지고 후행 테이블에서 조인 수행
3. 선행 테이블의 조건을 만족하는 모든 행에 대해 1~2번 작업을 반복

 

 구체적인 과정을 설명하자면 위와 같다. 선행테이블에는 인덱스가 없고, 후행테이블에는 인덱스가 있음을 가정한 예시이다.

1. 선행 테이블의 조건을 만족하는 첫 번째 행 찾음
2. 선행 테이블의 조인키를 가지고 후행 테이블에 조인 키가 존재하는지 찾으러 감
3. 후행 테이블의 인덱스에 위 조인키가 존재하는지 확인(조인 값이 후행 테이블에 존재하지 않으면 선행 테이블 데이터는 더이상 조인 작업을 할 필요가 없기 떄문에 필터링됨)
4. 후행 테이블의 인덱스에서 도출된 레코드 식별자를 이용해 후행 테이블을 엑세스 → 후행 테이블의 조건까지 만족하면 해당 행을 추출버퍼에 넣음
5. ~ 11 : 1~4의 작업을 반복함

만약, 선행테이블에 인덱스가 있다면, 인덱스를 활용하는 부분이 프로세스의 맨 처음에 추가될 것이다.

 

 

2. Sort Merge Join

 Sort Merge Join은 조인 칼럼을 기준으로 데이터를 정렬하여 조인을 수행한다. 넓은 범위의 데이터를 처리할 떄 이점이 있다. 다만, 정렬할 데이터가 많아 메모리에서 모든 정렬 작업을 수행하기 어려울 때는 DISC를 임시로 사용하기 때문에 성능이 떨어질 수 있다. 일반적으로 Hash JOIN이 더 성능상 이점이 있지만, Sort Merge Join은 비동등 조인(조인되는 컬럼이 정확히 일치하지는 않는 조인)이 가능하다는 장점이 있다.

동작 방법은 아래와 같다.

1. 선행 테이블에서 주어진 조건을 만족하는 행을 찾음
2. 조인 키를 기준으로 정렬 작업 수행 → 1~2의 작업을 선행 테이블의 모든 행에 대해 수행
3. 후행 테이블에서 주어진 조건을 만족한느 행을 찾음
4. 조인 키를 기준으로 정렬 작업 수행 → 3~4의 작업을 후행 테이블의 모든 행에 대해 수행
5. 정렬된 결과를 이용하여 조인을 수행하고, 조인 성공 시 추출버퍼에 넣음

Sort Merge Join 방식에서는 조인 컬럼의 인덱스를 사용하지 않기 때문에, 인덱스가 없는 경우에도 사용가능한 기법이다.

 

 

3. Hash JOIN

 조인을 수행할 테이블의 조인 컬럼을 기준으로 해시 함수를 수행하고, 서로 동일한 해시 값을 갖는 것들 사이에서 실제 값이 같은지를 비교하면서 조인을 수행한다. NL JOIN의 랜덤 엑세스 문제점과 Sort Merge JOIN의 정렬 작업 부담 문제점을 해결하기 위한 대안으로 등장하였다.

Hash JOIN의 동작 방법은 아래와 같다.

1. 선행 테이블에서 주어진 조건을 만족하는 행을 찾음
2. 해당 조인 키를 기준으로 해시 함수를 적용하여 해시 테이블 생성 → 1~2번 작업을 선행 테이브르이 조건을 만족하는 모든 행에 대해 수행
3. 후행 테이블에서 주어진 조건을 만족하는 행을 찾음
4. 해당 조인 키를 기준으로 해시 함수를 적용 → 해시 테이블에서 해당하는 버킷을 찾고, 실제 데이터가 일치하는지 확인
5. 조인에 성공하면 추출버퍼에 넣음

 선행 테이블에서 생성된 데이터는 처음 해시 테이블을 생성하기 때문에 Build Input이라고 하며, 후행 테이블에서 생성된 데이터는 해시 테이블에 해기 값이 존재하는지 검사하기 때문에 Prove Input이라고 한다. 선행 테이블로 결과 값이 적은 테이블을 사용하여 성능의 향상을 기대할 수 있다.

 

 

 

SQL - JOIN 종류

INNER JOIN

 두 테이블에서 모두 동일한 조인 컬럼의 값이 존재할 때 데이터를 출력하는 조인 기법이다. 교집합의 형태를 띈다. 이 때문에, NULL 에 해당하지 않는 튜플들이 출력된다.

mysql> SELECT city.* , country.Name
    -> FROM city
    -> JOIN country
    -> ON city.CountryCode = country.Code
    -> LIMIT 15;
+-----+------------------+-------------+------------------+------------+----------------------+
| ID  | Name             | CountryCode | District         | Population | Name                 |
+-----+------------------+-------------+------------------+------------+----------------------+
| 129 | Oranjestad       | ABW         | ?                |      29034 | Aruba                |
|   1 | Kabul            | AFG         | Kabol            |    1780000 | Afghanistan          |
|   2 | Qandahar         | AFG         | Qandahar         |     237500 | Afghanistan          |
|   3 | Herat            | AFG         | Herat            |     186800 | Afghanistan          |
|   4 | Mazar-e-Sharif   | AFG         | Balkh            |     127800 | Afghanistan          |
|  56 | Luanda           | AGO         | Luanda           |    2022000 | Angola               |
|  57 | Huambo           | AGO         | Huambo           |     163100 | Angola               |
|  58 | Lobito           | AGO         | Benguela         |     130000 | Angola               |
|  59 | Benguela         | AGO         | Benguela         |     128300 | Angola               |
|  60 | Namibe           | AGO         | Namibe           |     118200 | Angola               |
|  61 | South Hill       | AIA         | ?                |        961 | Anguilla             |
|  62 | The Valley       | AIA         | ?                |        595 | Anguilla             |
|  34 | Tirana           | ALB         | Tirana           |     270000 | Albania              |
|  55 | Andorra la Vella | AND         | Andorra la Vella |      21189 | Andorra              |
|  33 | Willemstad       | ANT         | Cura?ao          |       2345 | Netherlands Antilles |
+-----+------------------+-------------+------------------+------------+----------------------+

 

 

OUTER JOIN

 두 테이블에 대해 조인 컬럼의 값을 기준으로 데이터를 매칭하지만, 매칭되지 않는 튜플의 경우 NULL 값으로 출력한다. Outer Join은 LEFT, RIGHT, FULL 로 나눠지는데, MySQL에서는 FULL OUTER JOIN을 지원하지 않기 때문에, LEFT OUTER JOIN과 RIGHT OUTER JOIN을 Union 하는 형태롤 구현할 수 있다.

 

LEFT OUTER JOIN & RIGHT OUTER JOIN

 예시를 위해 간단한 데이터 셋을 가정한다.

mysql> select * from student;
+----+-------+
| id | class |
+----+-------+
|  1 |     1 |
|  2 |     1 |
|  3 |     2 |
+----+-------+

mysql> select * from class;
+----+
| id |
+----+
|  1 |
|  3 |
+----+

 

 학생 테이블(student)과, 학급 테이블(class)이 존재한다. 학생 테이블의 class 필드는 학습 테이블의 id 필드와 연결 지어져 있다. 다만, 참조 무결성 제약조건을 설정해두지 않았기 때문에, 학생 테이블에는 존재하지 않는 학급에 속한 학생이 있다.

이러한 조건에서 LEFT OUTER JOIN 과 RIGHT OUTER JOIN의 결과는 아래와 같다.

 

 -- LEFT OUTER JOIN
mysql> select * from student left join class on student.class = class.id;
+----+-------+------+
| id | class | id   |
+----+-------+------+
|  1 |     1 |    1 |
|  2 |     1 |    1 |
|  3 |     2 | NULL |
+----+-------+------+

-- RIGHT OUTER JOIN
mysql> select * from student right join class on student.class = class.id;
+------+-------+----+
| id   | class | id |
+------+-------+----+
|    2 |     1 |  1 |
|    1 |     1 |  1 |
| NULL |  NULL |  3 |
+------+-------+----+

 

 위 결과 처럼, LEFT OUTER JOIN은 우측 테이블에서 조인 컬럼의 값으로 매칭되지 않는 튜플이 있을 때 NULL 값으로 비워두며, RIGHT OUTER JOIN은 좌특 테이블에서 매핑되는 튜플이 없을 때 NULL 값으로 비워둔다.

 위 두 JOIN문을 결합하여 FULL OUTER JOIN을 구현할 수 있다. 결과는 아래와 같다.

 

mysql> select * from student left join class on student.class = class.id
    -> union
    -> select * from student right join class on student.class = class.id;
+------+-------+------+
| id   | class | id   |
+------+-------+------+
|    1 |     1 |    1 |
|    2 |     1 |    1 |
|    3 |     2 | NULL |
| NULL |  NULL |    3 |
+------+-------+------+
4 rows in set (0.01 sec)

 

 

INNER JOIN vs OUTER JOIN

 두 조인 기법은 출력하는 결과물과 목적에 있어서 명확한 차이가 존재한다. INNER JOIN은 조인 컬럼의 값이 일치하는 튜플만을 원할 떄 사용하지만, OUTER JOIN은 조인 컬럼의 값이 존재하지 않는 경우도 고려하고자 하는 목적이다.

 

 성능에서도 명확한 차이가 있다. INNER JOIN은 전체 튜플을 탐색하지 않고 필터링 된 튜플에 대해 JOIN을 수행하는 반면, OUTER JOIN은 전체 튜플에 대해 JOIN을 수행하기 때문에, INNER JOIN과 비교했을 떄 더 느리다. ( ← 매우 단순화 해서 표현한 것입니다.)

 

 아래 결과는 explain 명령어를 사용하여, JOIN 기법을 제외하고 동일한 쿼리에 대해, INNER JOIN일때와 LEFT JOIN일 떄의 실행계획을 비교한 것이다. 가장 우측의 filtered 필드를 보면, INNER JOIN의 경우 33.33% 에 해당하는 튜플이 필터링 되어 JOIN이 수행되지만, LEFT JOIN의 경우 필터링 되지 않고 전체 튜플이 JOIN에 수행됨을 알 수 있다.

mysql> explain select * from student join class on student.class = class.id;
+----+-------------+---------+------------+------+---------------+------+---------+------+------+----------+--------------------------------------------+
| id | select_type | table   | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra                                      |
+----+-------------+---------+------------+------+---------------+------+---------+------+------+----------+--------------------------------------------+
|  1 | SIMPLE      | class   | NULL       | ALL  | NULL          | NULL | NULL    | NULL |    2 |   100.00 | NULL                                       |
|  1 | SIMPLE      | student | NULL       | ALL  | NULL          | NULL | NULL    | NULL |    3 |    33.33 | Using where; Using join buffer (hash join) |
+----+-------------+---------+------------+------+---------------+------+---------+------+------+----------+--------------------------------------------+
2 rows in set, 1 warning (0.00 sec)

mysql> explain select * from student left join class on student.class = class.id;
+----+-------------+---------+------------+------+---------------+------+---------+------+------+----------+--------------------------------------------+
| id | select_type | table   | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra                                      |
+----+-------------+---------+------------+------+---------------+------+---------+------+------+----------+--------------------------------------------+
|  1 | SIMPLE      | student | NULL       | ALL  | NULL          | NULL | NULL    | NULL |    3 |   100.00 | NULL                                       |
|  1 | SIMPLE      | class   | NULL       | ALL  | NULL          | NULL | NULL    | NULL |    2 |   100.00 | Using where; Using join buffer (hash join) |
+----+-------------+---------+------------+------+---------------+------+---------+------+------+----------+--------------------------------------------+

 

CROSS JOIN

 CROSS JOIN은 카타시안 곱이라고 표현하기도 한다. 두 테이블의 모든 튜플들에 대해 다대다의 형태로 매핑시켜 데이터를 추출하는 형태를 말한다. CROSS JOIN에서는 조인 컬럼이 존재하지 않으며, 중복을 고려하지 않는다. 예를 들어, 어느 테이블의 튜플이 4개이고, 다른 테이블의 튜플이 3개일 때, CROSS JOIN은 12개의 로우들을 반환할 것이다.