• sql
  • join
  • query-optimization
  • book

SQL 레벨업 Ch.6 — 결합

Nested Loops, Hash, Sort Merge 세 가지 결합 알고리즘의 동작 방식과 각각이 유리한 상황을 정리했다.

Manx4분 읽기
시리즈 · BackEnd 서적4 / 17
  1. SQL 레벨업 Ch.1 — DBMS 아키텍처
  2. SQL 레벨업 Ch.3 — SQL의 조건 분기
  3. SQL 레벨업 Ch.4~5 — 집약과 자르기, 반복문
  4. SQL 레벨업 Ch.6 — 결합
  5. SQL 레벨업 Ch.7 — 서브쿼리
  6. SQL 레벨업 Ch.8 — SQL의 순서
  7. SQL 레벨업 Ch.9 — 갱신과 데이터 모델
  8. SQL 레벨업 Ch.10 — 인덱스 사용
  9. 오브젝트 Ch.1 — 객체, 설계
  10. 오브젝트 Ch.2 — 객체지향 프로그래밍
  11. 오브젝트 Ch.3~4 — 역할, 책임, 협력 / 설계 품질과 트레이드오프
  12. 오브젝트 Ch.5 — 책임 할당하기
  13. 오브젝트 Ch.6 — 메시지와 인터페이스
  14. 오브젝트 Ch.8 — 의존성 관리하기
  15. 오브젝트 Ch.9 — 유연한 설계
  16. 오브젝트 Ch.10, 12 — 상속과 코드 재사용, 다형성
  17. 오브젝트 Ch.13 — 서브클래싱과 서브타이핑

CROSS JOIN, INNER JOIN, OUTER JOIN 같은 결합의 종류는 생략하고, 결합 알고리즘과 성능만 정리한다.

결합 알고리즘과 성능

옵티마이저가 선택할 수 있는 결합 알고리즘은 Nested Loops, Hash, Sort Merge 세 가지이고, 선택 기준은 데이터의 크기와 결합 키의 분산이다. 사용 빈도도 이 순서대로 높다.

DBMS에 따라 지원하지 않는 알고리즘도 있다. 책에서는 MySQL이 Nested Loops와 그 파생 버전만 지원한다고 설명하는데, MySQL 8.0.18부터는 해시 조인이 추가되었다. 이처럼 버전에 따라 달라지므로 사용하는 DBMS의 동향을 확인해야 한다.

Nested Loops

  • 이중 for문과 같은 방식이다.
  • 접근하는 레코드 수는 Table_A * Table_B이고, 실행 시간은 이에 비례한다.
  • 한 단계에서 처리하는 레코드 수가 적어 Hash, Sort Merge에 비해 메모리 소비가 적다.

내부 테이블의 결합 키에 인덱스가 있으면 내부 테이블을 전부 순회하지 않아도 된다. 구동 테이블의 레코드 하나에 내부 테이블의 레코드 하나가 대응하는 이상적인 경우, 접근하는 레코드 수는 Table_A * 2가 된다. 내부 테이블이 클수록 인덱스로 반복을 생략하는 효과가 커진다.

‘작은 구동 테이블의 Nested Loops + 내부 테이블 결합 키의 인덱스’ 조합은 SQL 튜닝의 기본 중의 기본이다.

한계와 대처

결합 키가 내부 테이블에서 유일하지 않아 히트되는 레코드가 너무 많으면 기대만큼의 응답 시간이 나오지 않는다. 대처 방법은 두 가지다.

  • 큰 테이블을 구동 테이블로 선택한다. 역설적이지만, 이렇게 하면 내부 테이블 접근이 기본 키로 수행되어 항상 레코드 하나에만 접근하는 것이 보장된다. 큰 내부 테이블을 반복해서 뒤지는 대신 작은 테이블에 접근하게 되므로 성능 저하를 막을 수 있다고 이해했다.
  • Hash를 사용한다.

결국 SQL의 성능은 처리하는 데이터양에 달려 있다.

Hash

  1. 작은 테이블을 스캔한다.
  2. 결합 키에 해시 함수를 적용해 해시 테이블을 만든다.
  3. 다른 테이블(큰 테이블)을 스캔하면서 결합 키의 해시값이 해시 테이블에 있는지 확인한다.

작은 테이블로 해시 테이블을 만드는 이유는 해시 테이블이 워킹 메모리에 저장되기 때문이다.

특징

  • 해시 테이블을 만들기 때문에 Nested Loops보다 메모리를 많이 쓴다.
  • 메모리가 부족하면 저장소를 사용해 지연이 발생한다.
  • 해시값은 입력값의 순서를 보존하지 않으므로 등치 결합에만 쓸 수 있다.
  • 양쪽 테이블을 모두 읽어야 해서 풀 스캔이 되는 경우가 많다. 테이블이 매우 크다면 풀 스캔 시간도 고려해야 한다.

유용한 경우

Hash는 Nested Loops가 효율적으로 동작하지 않을 때의 차선책이다.

  • 구동 테이블로 쓸 만큼 충분히 작은 테이블이 없는 경우
  • 작은 구동 테이블은 있지만 내부 테이블에서 히트되는 레코드가 너무 많은 경우
  • 내부 테이블에 인덱스가 없는 경우

다수의 트랜잭션이 동시에 실행되는 OLTP 처리에 Hash를 쓰면 메모리가 부족해져 저장소를 사용하게 되고 지연이 발생한다. 동시 처리가 적은 야간 배치 같은 시스템에 한해 유용하다.

Sort Merge

결합 대상 테이블을 각각 결합 키로 정렬한 뒤, 일치하는 결합 키를 찾아 결합한다.

  • 양쪽 테이블을 모두 정렬해야 하므로 메모리를 많이 쓴다. 한쪽 테이블로만 해시 테이블을 만드는 Hash보다 더 많이 쓰기도 한다.
  • 등치 결합뿐 아니라 부등호를 사용한 결합에도 쓸 수 있다. 단, 부정 조건(<>) 결합에는 쓸 수 없다.
  • 정렬에 많은 시간과 리소스가 들 수 있다.

테이블 정렬을 생략할 수 있는 경우에는 고려할 만하지만, 그 외에는 Nested Loops와 Hash를 우선 검토한다.

실행 계획 제어

  • Oracle: 힌트 구(USE_NL, USE_HASH, USE_MERGE)를 사용하고, LEADING으로 구동 테이블도 지정할 수 있다.
  • MSSQL: 힌트 구(LOOP, HASH, MERGE)
  • PostgreSQL: pg_hint_plan으로 힌트 구처럼 제어할 수 있다.

사용자가 실행 계획을 고정하면 데이터가 변했을 때 비효율적일 수 있다. 그렇다고 옵티마이저의 선택이 언제나 옳은 것도 아니다. 그래서 결합 자체를 줄이는 방법도 함께 알아 두어야 한다.

  • 비정규화
  • 결합을 다른 수단으로 대체(상관 서브쿼리, 윈도우 함수 등)