JOIN

1068. Product Sales Analysis I

SELECT P.product_name, S.year, S.price
FROM Sales as S
join Product as P using(product_id)

• 두 테이블을 JOIN하여 상품명, 판매 년도, 가격을 확인하는 간단한 쿼리이다.

• 첫 접근에서는 left join을 사용하여 문제를 해결했는데, 수행 시간이 상대적으로 느렸다.

• 더 효율적인 쿼리의 경우 join (inner join)을 사용했는데, 둘의 차이를 확인하기 위해 EXPLAIN 명령을 수행 해 보았다.

• left join

| id | select_type | table | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra                                      |
| -- | ----------- | ----- | ---------- | ---- | ------------- | ---- | ------- | ---- | ---- | -------- | ------------------------------------------ |
| 1  | SIMPLE      | S     | null       | ALL  | null          | null | null    | null | 3    | 100      | null                                       |
| 1  | SIMPLE      | P     | null       | ALL  | null          | null | null    | null | 3    | 100      | Using where; Using join buffer (hash join) |

• inner join

| id | select_type | table | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra                                      |
| -- | ----------- | ----- | ---------- | ---- | ------------- | ---- | ------- | ---- | ---- | -------- | ------------------------------------------ |
| 1  | SIMPLE      | S     | null       | ALL  | null          | null | null    | null | 3    | 100      | null                                       |
| 1  | SIMPLE      | P     | null       | ALL  | null          | null | null    | null | 3    | 33.33    | Using where; Using join buffer (hash join) |

• 가장 눈에 띄는 부분은 "filtered" 컬럼이다. left join의 경우 100%로 Products 테이블의 모든 레코드를 확인해야 하고, inner join의 경우는 33%의 레코드만 확인하면 되기 때문에 두 쿼리의 성능 차이가 생긴다.

• 이번 기회에 JOIN의 종류 및 MySQL에서 작동 방식에 대해서 확인해보자.

JOIN의 종류

Input: 
Sales table:
+---------+------------+------+----------+-------+
| sale_id | product_id | year | quantity | price |
+---------+------------+------+----------+-------+ 
| 1       | 100        | 2008 | 10       | 5000  |
| 2       | 100        | 2009 | 12       | 5000  |
| 7       | 200        | 2011 | 15       | 9000  |
+---------+------------+------+----------+-------+
Product table:
+------------+--------------+
| product_id | product_name |
+------------+--------------+
| 100        | Nokia        |
| 200        | Apple        |
| 300        | Samsung      |
+------------+--------------+

• INNER JOIN : 두 테이블 간에 일치하는 행만 반환합니다. 양쪽 테이블 모두에서 조건을 만족하는 행이 있는 경우에만 결과에 포함됩니다.

SELECT *
FROM Sales as S
INNER JOIN Product as P using(product_id)

| product_id | sale_id | year | quantity | price | product_name |
| ---------- | ------- | ---- | -------- | ----- | ------------ |
| 100        | 2       | 2009 | 12       | 5000  | Nokia        |
| 100        | 1       | 2008 | 10       | 5000  | Nokia        |
| 200        | 7       | 2011 | 15       | 9000  | Apple        |

• LEFT JOIN (LEFT OUTER JOIN) : 왼쪽 테이블의 모든 행과 오른쪽 테이블의 일치하는 행을 반환합니다. 오른쪽 테이블에 일치하는 행이 없으면 NULL 값을 반환합니다.

SELECT *
FROM Sales as S
LEFT JOIN Product as P using(product_id)

| product_id | sale_id | year | quantity | price | product_name |
| ---------- | ------- | ---- | -------- | ----- | ------------ |
| 100        | 1       | 2008 | 10       | 5000  | Nokia        |
| 100        | 2       | 2009 | 12       | 5000  | Nokia        |
| 200        | 7       | 2011 | 15       | 9000  | Apple        |

• RIGHT JOIN (RIGHT OUTER JOIN) : 오른쪽 테이블의 모든 행과 왼쪽 테이블의 일치하는 행을 반환합니다. 왼쪽 테이블에 일치하는 행이 없으면 NULL 값을 반환합니다.

SELECT *
FROM Sales as S
RIGHT JOIN Product as P using(product_id)

| product_id | product_name | sale_id | year | quantity | price |
| ---------- | ------------ | ------- | ---- | -------- | ----- |
| 100        | Nokia        | 2       | 2009 | 12       | 5000  |
| 100        | Nokia        | 1       | 2008 | 10       | 5000  |
| 200        | Apple        | 7       | 2011 | 15       | 9000  |
| 300        | Samsung      | null    | null | null     | null  |

• FULL OUTER JOIN : 양쪽 테이블의 모든 행을 반환하며, 일치하지 않는 행에는 NULL 값을 포함합니다. MySQL FULL OUTER JOIN을 직접 지원하지 않지만, UNION을 사용하여 구현할 수 있습니다.

SELECT product_id, sale_id, year, quantity, price, product_name
FROM Sales
LEFT JOIN Product USING(product_id)
UNION
SELECT product_id, sale_id, year, quantity, price, product_name
FROM Sales
RIGHT JOIN Product USING(product_id);

| product_id | sale_id | year | quantity | price | product_name |
| ---------- | ------- | ---- | -------- | ----- | ------------ |
| 100        | 1       | 2008 | 10       | 5000  | Nokia        |
| 100        | 2       | 2009 | 12       | 5000  | Nokia        |
| 200        | 7       | 2011 | 15       | 9000  | Apple        |
| 300        | null    | null | null     | null  | Samsung      |

• CROSS JOIN : 두 테이블 간의 모든 가능한 조합을 반환합니다. 테이블의 모든 행이 다른 테이블의 모든 행과 결합됩니다.
  • 결과

SELECT *
FROM Sales as S
CROSS JOIN Product as P

| sale_id | product_id | year | quantity | price | product_id | product_name |
| ------- | ---------- | ---- | -------- | ----- | ---------- | ------------ |
| 7       | 200        | 2011 | 15       | 9000  | 100        | Nokia        |
| 2       | 100        | 2009 | 12       | 5000  | 100        | Nokia        |
| 1       | 100        | 2008 | 10       | 5000  | 100        | Nokia        |
| 7       | 200        | 2011 | 15       | 9000  | 200        | Apple        |
| 2       | 100        | 2009 | 12       | 5000  | 200        | Apple        |
| 1       | 100        | 2008 | 10       | 5000  | 200        | Apple        |
| 7       | 200        | 2011 | 15       | 9000  | 300        | Samsung      |
| 2       | 100        | 2009 | 12       | 5000  | 300        | Samsung      |
| 1       | 100        | 2008 | 10       | 5000  | 300        | Samsung      |

• SELF JOIN : 자기 자신과의 JOIN입니다. 같은 테이블 내의 행들을 결합하여 쿼리합니다.

SELECT *
FROM Sales as S, Sales as P
WHERE S.sale_id = P.sale_id

| sale_id | product_id | year | quantity | price | sale_id | product_id | year | quantity | price |
| ------- | ---------- | ---- | -------- | ----- | ------- | ---------- | ---- | -------- | ----- |
| 1       | 100        | 2008 | 10       | 5000  | 1       | 100        | 2008 | 10       | 5000  |
| 2       | 100        | 2009 | 12       | 5000  | 2       | 100        | 2009 | 12       | 5000  |
| 7       | 200        | 2011 | 15       | 9000  | 7       | 200        | 2011 | 15       | 9000  |

JOIN의 시간 복잡도

• table1의 행 : N, table2의 행 : M

• 인덱스가 없을 경우

  • SELF JOIN : O(N^2)
  • INNER, LEFT, RIGHT, CROSS, FULL OUTER : O(N * M)
  • 이론적인 시간 복잡도는 같지만, 필터링이 적용되는 정도에 따라 시간 복잡도의 차이가 있다
    • 일반적으로는 INNER JOIN < LEFT JOIN ≈ RIGHT JOIN < CROSS JOIN
  • 또한, MySQL에서 FULL OUTER JOIN의 경우 아래와 같은 이유로 성능이 떨어진다.
    • JOIN을 두번(LEFT, RIGHT) 한다
    • UNION 연산을 통해 중복된 행을 제거하는데 추가적인 비용이 필요하다
    • JOIN 연산 결과를 메모리에 유지하고 UNION 작업을 수행해야 하므로, 메모리 사용량이 증가한다

• 인덱스가 있을 경우

  • O(NlogM) 또는 O(MlogN)
  • B-트리 구조등을 통해 행을 빠르게 검색할 수 있기 때문에 시간복잡도가 줄어든다

메모리 효율

• 일반적으로 쿼리 실행 후 결과 테이블은 메모리(RAM)에 올려놓는 형식으로 관리됩니다. 이는 쿼리 결과를 빠르게 반환하고 후속 처리를 효율적으로 하기 위함입니다. 다만, 매우 큰 결과 집합의 경우 메모리 사용량을 줄이기 위해 디스크의 임시 파일로 저장될 수 있습니다.

• 따라서, 쿼리 실행 후 결과 테이블의 크기 (공간 복잡도)도 쿼리 성능에 큰 영향을 미친다

• 성능 최적화 방법으로는 아래와 같은 방법이 있다.

  • 필터링: WHERE 절을 사용하여 결과 집합의 크기를 줄입니다.
  • 인덱스 사용: 적절한 인덱스를 사용하여 JOIN 조건을 최적화합니다.
  • 페이징: 결과 집합을 페이지 단위로 나누어 한 번에 작은 양의 데이터만 처리합니다. (LIMIT, OFFSET)
  • 제한: 필요한 데이터만 선택하여 불필요한 열이나 행을 제거합니다. (LIMIT)