Nested loop join, Hash join

Nested loop join, Hash join

Join

Join 이란?

Join은 두 개 이상의 테이블을 결합하여 하나의 테이블로 만드는 데이터베이스 연산이다.

우리는 서로 다른 테이블의 데이터를 결합함으로써 더 유용한 정보를 얻을 수 있게 된다.

Join 을 언제 사용하나?

Join을 사용하는 경우는 많지만, 대략적으로 큰 가지를 뻗어보면 다음과 같다.

• 데이터 통합: 여러 테이블에 분산된 데이터를 결합하여 종합적인 정보를 얻고자 할 때.

• 데이터 분석: 서로 관련된 데이터를 결합하여 분석할 때.

• 리포트 생성: 다양한 테이블의 데이터를 결합하여 새로운 데이터 셋을 생성할 때.

• 데이터 일관성 유지: 데이터베이스의 정규화된 구조를 유지하면서도 필요한 데이터를 한 번에 조회할 때.

Join 의 종류

Join 의 종류중, 아래 개념에 대해서는 기본적으로 숙지할 필요가 있겠다.

이미지는 다른 블로그에 많으니 생략.

• Inner Join: 두 테이블에서 일치하는 데이터만 결합. 일치하지 않는 데이터는 제외.

• Outer Join: 두 테이블에서 일치하는 데이터뿐만 아니라 일치하지 않는 데이터도 포함. Outer Join은 다시 Left Outer Join, Right Outer Join, Full Outer Join으로 나뉜다.

  • Left Outer Join: 왼쪽 테이블의 모든 데이터와 오른쪽 테이블에서 일치하는 데이터.

  • Right Outer Join: 오른쪽 테이블의 모든 데이터와 왼쪽 테이블에서 일치하는 데이터.

  • Full Outer Join: 두 테이블에서 일치하는 데이터와 일치하지 않는 모든 데이터.

• Cross Join: 두 테이블의 모든 가능한 조합을 생성.

• Self Join: 같은 테이블을 자기 자신과 조인하는 방식.

Nested Loop Join

Nested Loop Join 이란?

Nested Loop Join은 두 테이블의 모든 가능한 쌍을 비교하여 조인하는 방식이다.

하나의 테이블을 외부 루프로, 다른 테이블을 내부 루프로 설정하고, 외부 루프의 각 행에 대해 내부 루프의 모든 행을 비교한다.

아래는 두 테이블을 Nested Loop Join 으로 Join 하는 방식이다.

SELECT A.*, B.*
FROM TableA A, TableB B
WHERE A.key = B.key;

이 쿼리는 TableA와 TableB의 모든 행을 비교하여 key 값이 일치하는 행을 조인한다.

만약 TableA와 TableB의 행이 각각 1000개씩이라면, 이 쿼리는 최대 100만 번의 비교를 수행하게 된다.

언뜻봐도 비효율적이다.

• 특징:

  • 간단하고 구현이 용이.

  • 작은 데이터셋에 적합.

  • 데이터의 양이 많아질수록 성능이 급격히 저하.

• 유의사항:

  • 큰 테이블 간의 조인에서는 비효율적.

  • 인덱스를 활용하면 성능이 개선될 수 있다.

  • 일반적으로 소규모 데이터셋이나 인덱스가 잘 설계된 상황에서 사용.

Hash Join

Hash Join 이란?

Hash Join은 두 테이블의 데이터를 해시 테이블을 사용하여 조인하는 방식.

하나의 테이블을 해시 테이블로 변환하고, 다른 테이블의 각 행을 해시 테이블과 비교하여 조인한다.

SELECT A.*, B.*
FROM TableA A
JOIN TableB B ON A.key = B.key;

• 특징:

  • 대규모 데이터셋에 적합.

  • 메모리를 효율적으로 사용하여 성능이 우수.

  • 빌드 단계와 프로브 단계로 나누어진다.

• 유의사항:

  • 메모리 사용량이 크므로 메모리 관리가 중요하다.

  • 해시 충돌이 발생할 수 있으므로 해시 함수의 선택이 중요하다.

  • 모든 데이터가 메모리에 적재될 수 없을 때는 성능이 저하될 수 있다.

함정

다음은 복잡한 조건을 가진 쿼리 예시이다.

이 쿼리는 Nested Loop Join으로 인해 성능이 저하될 수 있다.

SELECT p.product_id, p.name, c.category_name
FROM products p
INNER JOIN order_items oi ON p.product_id = oi.product_id
INNER JOIN orders o ON o.order_id = oi.order_id
WHERE p.price > ? 
  AND p.stock > ? 
  AND o.order_date > ?
  AND oi.quantity > ?
  AND oi.discount IS NULL
GROUP BY p.product_id, c.category_name;

이 쿼리의 실행 계획을 보면 크게 3가지 문제가 있다.

1. Nested Loop 조인:

   • Nested Loop 조인은 각 행에 대해 반복적으로 다른 테이블을 스캔.

   • 이 경우, order_items와 orders 간의 조인이 매우 많은 반복을 발생시켜 성능이 저하.

   • 특히, orders 테이블에서 order_date 조건을 만족하는 행을 찾기 위해 많은 반복 작업이 필요.

2. 데이터 양:

   • products 테이블에서 조건을 만족하는 행이 다수일 경우, 각 행에 대해 order_items와 조인한 후, 결과적으로 수많은 orders 테이블 접근이 발생할 수 있음.

   • 예를 들어, products 테이블에서 200개의 행이 필터링된다고 가정하면, 각 행에 대해 order_items와 조인하면 결과적으로 수십만 번의 orders 테이블 접근이 발생할 수 있다.

3. Index Only Scan:

   • orders 테이블에 대한 Index Only Scan이 반복되면서 많은 I/O 작업이 발생할 수 있다.

   • 위 쿼리는 Nested Loop Join을 통해 많은 데이터 행을 반복적으로 스캔.

   • 가장 해결이 필요한 부분은 수십만 번의 orders 테이블 접근.

최적화 방안

Nested Loop Join을 피하고, Hash Join을 사용하도록 쿼리를 최적화해보자. 또한, WITH 절을 이용하여 서브쿼리를 최적화해보자.

1. Hash Join을 사용하도록 쿼리 작성:

Hash Join을 유도하기 위해, 데이터의 중간 결과를 WITH 절을 사용하여 먼저 계산해보자.

WITH filtered_products AS (
  SELECT product_id, name
  FROM products
  WHERE price > ? AND stock > ?
),
filtered_orders AS (
  SELECT order_id
  FROM orders
  WHERE order_date > ?
)
SELECT p.product_id, p.name, c.category_name
FROM filtered_products p
INNER JOIN order_items oi ON p.product_id = oi.product_id
INNER JOIN filtered_orders o ON o.order_id = oi.order_id
WHERE oi.quantity > ?
  AND oi.discount IS NULL
GROUP BY p.product_id, c.category_name;

이렇게 하면, products와 orders 테이블에서 먼저 조건에 맞는 데이터를 필터링하고, 그 결과를 조인할 수 있다.

이로써, 중간 결과를 먼저 생성하여 조인의 효율성을 높일 수 있다.

최적화 결과 분석

• WITH 절 사용: 중간 결과를 생성하여 조인의 범위를 줄여보자. 이렇게 하면 각 테이블에서 먼저 조건에 맞는 데이터를 필터링한 후 조인하기 때문에 전체 데이터셋을 반복적으로 스캔하는 것을 방지할 수 있다.

• Hash Join 유도: 중간 결과를 사용하면, DBMS는 더 큰 조인 결과를 효율적으로 처리하기 위해 Hash Join을 선택할 가능성이 높아진다.

• 성능 향상: 데이터의 중간 결과를 미리 생성함으로써, 전체 쿼리의 성능이 크게 향상될 수 있다. 특히, 대규모 데이터셋에서 효과적이다.

위의 최적화된 쿼리를 통해 성능 저하를 방지하고, 보다 효율적으로 데이터를 조인할 수 있다.

이는 특히 대규모 데이터셋에서 중요한 최적화 기법이다.