NL(Nested Loop) 조인
Nested Loop Join 의 개념
NL 조인의 영문의 뜻 : 중첩된(Nested) + 반복(Loop) + 연결(Join)
* 프로그래밍 언어에서 For 문장 처럼 반복(Loop) 처리
- 두개의 테이블에서, 하나의 집합(테이블)을 기준으로 순차적으로 상대방 테이블의 row 를 결합하여 원하는 결과를 추출하는 테이블 연결 방식
- 결합하기 위해 기준이 되는 테이블(선행테이블=드라이빙(driving) 테이블=outer테이블) : 드라이빙(driving) 테이블( OUTER 테이블, 즉 바깥쪽 테이블)
- 결합되어지는 테이블(후행=드리븐(driven) 테이블=inner테이블) : 드리븐(driven) 테이블(INNER 테이블, 즉 안쪽 테이블)
- NL 조인에서는 드라이빙 테이블의 각 row 에 대하여 loop 방식으로 조인이 되는데 드라이빙 테이블의 집합을 줄여주는 조건이 (where에서 사용된 컬럼에 인덱스가 있는가?) NL 조인의 성능을 결정함.
- 예시) USE_NL(각각 테이블에 어떤 컬럼에 인덱스를 이용 할것 인가? )
SELECT 고객.* ,주문.* FROM 고객 -- 1) [고객]테이블은 어떤 컬럼에 인덱스가 있으면 좋은가? JOIN 주문 -- 2) [주문]테이블은 어떤 컬럼에 인덱스가 있으면 좋은가? ON 주문.고객번호 = 고객.고객번호 WHERE 고객.고객명='홍길동' AND 주문.주문일자='201909';
- 고객(outer,드라이빙테이블,선행 테이블)은 WHERE절의 '=' 조건(고객명) 인덱스 여부,
- 주문(inner,드리븐테이블,후행 테이블)은 고객번호 컬럼(조인되는컬럼)의 인덱스 여부가 N/L조인의 성능을 결정.
NL조인 시 인덱스 의 중요성
* 인덱스의 중요성
:# outer(선행,driving ) 테이블이 한 row 씩 반복해 가면서 inner(후행,driven ) 테이블로 조인이 이루어짐
- inner(후행) 테이블의 컬럼은 outer(선행) 테이블의 컬럼을 받아서 데이터를 빨리 찾기하기 위해서는 인덱스가 반드시 있어야함.(성능 향상 포인트)
- inner 테이블의 크기가 적다면 테이블 전체를 메모리에 읽어서 반복적으로 검색하는 것이 빠름
- 조인되는 값들의 카디널리티(cardinality) 가 높을 수록, 한 번 스캔되어 조인된 자료가 다음 row 에서 조인에 사용될 확률이 낮아지기 때문에 스캔에 의한 조인 효율은 저하
- 원하는 값이 존재하는 지 빠르게 확인하기 위한 목적과 그 값에 대한 데이터를 빠르게 읽어 내기 위해서 인덱스 오브젝트는 N/L 조인에서 (특히 inner 테이블의 액세스 시) 반드시 필요
인덱스 조건
* NL조인에서 인덱스의 중요성
- 선행(드라이빙,outer) 테이블은 where 절에 사용된 컬럼의 인덱스 여부가 중요
- 후행(드리븐,inner) 테이블은 조인조건 컬럼의 인덱스가 중요
*
- outer 테이블 조회 후 1건씩 순차적(sequential)으로 inner 테이블에 접근
- INDEX 구성
- EMP.IX_EMP_01 ( DEPTNO)
- DEPT.IX_DEPT_01 ( DEPTNO))
SELECT /*+ USE_NL(B) LEADING(A) */ ENAME,JOB,B.DNAME FROM EMP A JOIN DEPT B ON A.DEPTNO = B.DEPTNO ------------------------------------------------------------------------------------------------------------------------------------- | Id | Operation | Name | Starts | E-Rows |E-Bytes| Cost (%CPU)| E-Time | A-Rows | A-Time | Buffers | ------------------------------------------------------------------------------------------------------------------------------------- | 0 | SELECT STATEMENT | | 1 | | | 17 (100)| | 14 |00:00:00.01 | 11 | | 1 | NESTED LOOPS | | 1 | 14 | 672 | 17 (0)| 00:00:01 | 14 |00:00:00.01 | 11 | | 2 | NESTED LOOPS | | 1 | 14 | 672 | 17 (0)| 00:00:01 | 14 |00:00:00.01 | 10 | | 3 | TABLE ACCESS FULL | EMP | 1 | 14 | 364 | 3 (0)| 00:00:01 | 14 |00:00:00.01 | 7 | |* 4 | INDEX RANGE SCAN | IX_DEPT_01 | 14 | 1 | | 0 (0)| | 14 |00:00:00.01 | 3 | | 5 | TABLE ACCESS BY INDEX ROWID| DEPT | 14 | 1 | 22 | 1 (0)| 00:00:01 | 14 |00:00:00.01 | 1 | -------------------------------------------------------------------------------------------------------------------------------------
LEADING 이나 ORDERED 힌트와 같이 사용 추천
- INDEX 구성
- EMP.IX_EMP_01 ( DEPTNO)
- DEPT.IX_DEPT_01 ( DEPTNO))
SELECT /*+ USE_NL(A,B) LEADING(A) */ ENAME,JOB,B.DNAME FROM EMP A JOIN DEPT B ON A.DEPTNO = B.DEPTNO ------------------------------------------------------------------------------------------------------------------------------------- | Id | Operation | Name | Starts | E-Rows |E-Bytes| Cost (%CPU)| E-Time | A-Rows | A-Time | Buffers | ------------------------------------------------------------------------------------------------------------------------------------- | 0 | SELECT STATEMENT | | 1 | | | 17 (100)| | 14 |00:00:00.01 | 11 | | 1 | NESTED LOOPS | | 1 | 14 | 672 | 17 (0)| 00:00:01 | 14 |00:00:00.01 | 11 | | 2 | NESTED LOOPS | | 1 | 14 | 672 | 17 (0)| 00:00:01 | 14 |00:00:00.01 | 10 | | 3 | TABLE ACCESS FULL | EMP | 1 | 14 | 364 | 3 (0)| 00:00:01 | 14 |00:00:00.01 | 7 | |* 4 | INDEX RANGE SCAN | IX_DEPT_01 | 14 | 1 | | 0 (0)| | 14 |00:00:00.01 | 3 | | 5 | TABLE ACCESS BY INDEX ROWID| DEPT | 14 | 1 | 22 | 1 (0)| 00:00:01 | 14 |00:00:00.01 | 1 | -------------------------------------------------------------------------------------------------------------------------------------
USE_NL 괄호 안의 테이블은 NL조인 적용 대상 테이블
SELECT /*+ USE_NL(A,B) LEADING(B) */ ENAME,JOB,B.DNAME FROM EMP A JOIN DEPT B ON A.DEPTNO = B.DEPTNO ------------------------------------------------------------------------------------------------------------------------------------ | Id | Operation | Name | Starts | E-Rows |E-Bytes| Cost (%CPU)| E-Time | A-Rows | A-Time | Buffers | ------------------------------------------------------------------------------------------------------------------------------------ | 0 | SELECT STATEMENT | | 1 | | | 6 (100)| | 14 |00:00:00.01 | 10 | | 1 | NESTED LOOPS | | 1 | 14 | 672 | 6 (0)| 00:00:01 | 14 |00:00:00.01 | 10 | | 2 | NESTED LOOPS | | 1 | 20 | 672 | 6 (0)| 00:00:01 | 14 |00:00:00.01 | 9 | | 3 | TABLE ACCESS FULL | DEPT | 1 | 4 | 88 | 3 (0)| 00:00:01 | 4 |00:00:00.01 | 7 | |* 4 | INDEX RANGE SCAN | IX_EMP_01 | 4 | 5 | | 0 (0)| | 14 |00:00:00.01 | 2 | | 5 | TABLE ACCESS BY INDEX ROWID| EMP | 14 | 4 | 104 | 1 (0)| 00:00:01 | 14 |00:00:00.01 | 1 | ------------------------------------------------------------------------------------------------------------------------------------
NL조인 - 파이썬으로 구현한 예제
- NL 조인은 두 개의 테이블을 조인할 때, 한 테이블(외부 테이블)을 먼저 순차적으로 스캔하고, 스캔한 각 행마다 다른 테이블(내부 테이블)을 반복적으로 탐색하여 조인하는 방식
- 이중 for 루프와 같아서 이름이 '중첩 루프(Nested Loop)' 조인
- 외부 테이블(Outer Table): 바깥쪽 루프를 도는 테이블. 주로 크기가 작거나 인덱스가 있는 테이블이 선택됨.
- 내부 테이블(Inner Table): 안쪽 루프를 도는 테이블. 외부 테이블의 행 수만큼 반복적으로 스캔. 내부 테이블에 조인되는 컬럼에 인덱스가 있으면 성능이 매우 향상됨
- 아래 코드는 employees 테이블과 departments 테이블을 NL 조인하는 상황을 가정
- 이 예제에서는 departments를 외부 테이블로, employees를 내부 테이블로 사용.
# 'departments' 테이블 (외부 테이블) departments = [ {'dept_id': 10, 'dept_name': '인사팀'}, {'dept_id': 20, 'dept_name': '개발팀'}, {'dept_id': 30, 'dept_name': '마케팅팀'}, ] # 'employees' 테이블 (내부 테이블) employees = [ {'emp_id': 1, 'name': '김철수', 'dept_id': 20}, {'emp_id': 2, 'name': '박영희', 'dept_id': 10}, {'emp_id': 3, 'name': '이민호', 'dept_id': 20}, {'emp_id': 4, 'name': '최민수', 'dept_id': 30}, {'emp_id': 5, 'name': '정수미', 'dept_id': 40}, # 조인되지 않는 데이터 ] # 조인된 결과 joined_results = [] # 외부 루프: departments 테이블을 순회 for dept in departments: # 내부 루프: employees 테이블을 순회 for emp in employees: # 조인 조건: 두 테이블의 dept_id가 같은지 비교 if dept['dept_id'] == emp['dept_id']: # 조건이 일치하면 조인 결과를 추가 joined_row = { 'emp_id': emp['emp_id'], 'name': emp['name'], 'dept_name': dept['dept_name'] } joined_results.append(joined_row) # 조인 결과 출력 for result in joined_results: print(result) # 예상 출력: # {'emp_id': 2, 'name': '박영희', 'dept_name': '인사팀'} # {'emp_id': 1, 'name': '김철수', 'dept_name': '개발팀'} # {'emp_id': 3, 'name': '이민호', 'dept_name': '개발팀'} # {'emp_id': 4, 'name': '최민수', 'dept_name': '마케팅팀'}
NL 조인의 특징
- 성능: 외부 테이블의 크기(건수) 와 내부 테이블의 조인되는 컬럼의 인덱스 존재 여부에 따라 성능이 크게 차이남.
- 외부 테이블의 크기: 외부 테이블의 행 수가 적을수록 내부 루프를 도는 횟수가 줄어들어 효율적임.
- 내부 테이블의 인덱스: 내부 테이블의 조인되는 컬럼에 인덱스가 있으면, 내부 루프가 전체 테이블을 스캔하는 대신 인덱스 스캔을 통해 필요한 행만 빠르게 찾으므로 성능이 매우 좋아짐.
- 활용: 주로 외부 테이블이 작고, 내부 테이블의 조인 키에 인덱스가 잘 구성되어 있을 때 효율적입니다.
- 대용량 테이블을 조인할 때는 대부분 비효율적입니다.
해시 조인(Hash Join)
hash의 영문의 뜻 : 잘게 썰다, 다지다의 의미(요리에서 재료를 잘게 썰어서 섞을때 쓰이는말, 예로 맥도날도 '해시브라운(감자를 다져서 튀긴요리)'
* hash함수는 입력된 데이터를 '잘게 다져서' 고유하고 일정한 크기의 식별자로 만들어 냄.
- 해시의 주요특징
- 단방향성 : 해시값을 원래의 값으로 되돌릴수 없다.
- 고유성 : 입력값이 바뀌면 해시값은 완전히 달라진다.
- 고정된길이 : 입력값의 크기와 상관없이 항상 동일한 길이의 출력값을 가진다.
- 해시의 주요특징
- 해시 조인(Hash Join)은 두 개의 테이블을 조인할 때, 더 작은 테이블을 메모리에 올리고 해시 테이블을 만들어 효율적으로 조인하는 방식
- 대용량 테이블을 조인할 때 주로 사용되며, 조인 조건에 인덱스가 없는 경우에도 빠르게 작동
해시 조인의 원리
- 해시 조인은 크게 두 단계로 나뉩니다.
- 빌드 단계 (Build Phase):
- 옵티마이저는 두 테이블 중 더 작은 테이블(빌드 테이블)을 선택
- 이 테이블의 조인 키(컬럼)를 사용하여 PGA 메모리 영역에 해시 테이블을 생성. 각 조인 키 값은 해시 함수를 통하여 해시값으로 변환되어 해시 테이블의 특정 위치에 저장.
- 해시테이블 저장시 변환된 해시값들은 해시버킷의 갯수 만큼 쪼개서 할당되고 "버킷"에 행을 연결리스트(체인) 형태로 저장됨.
- 각 버킷은 "해당 해시 범위에 속하는 행들의 포인터(체인 헤드)" 역활을 하며 , 동일 해시값 이나 충돌이 발생하면 같은 버킷내에서 체인으로 연결됨.(많이 연결될수록 성능 저하,이구간이 성능저하 구간)
- 프로브 단계 (Probe Phase):
- 더 큰 테이블(프로브 테이블)을 순차적으로 읽어옮
- 프로브 테이블의 각 행에서 조인 키를 추출하여, 빌드 단계에서 사용한 동일한 해시 함수로 해시 값을 계산
- 계산된 해시 값을 이용해 빌드 테이블의 해시 테이블에서 일치하는 행을 찾음.(대상 버킷을 찾고 해당 버킷의 체인을 스캔하여 조인키를 비교)
- 일치하는 행을 찾으면, 두 테이블의 행을 결합하여 결과를 반환.
- 만약 빌드 테이블이 PGA 메모리에 다 들어가지 않을 정도로 크다면, 테이블을 여러 개의 파티션으로 나누어 디스크에 임시로 저장한 뒤(성능 저하 구간), 각 파티션별로 빌드와 프로브 단계를 반복하는 '그레이스풀 해시 조인(Graceful Hash Join)'이 수행(성능저하 구간)
- 런타임 파티셔닝을 수행해 부분(배치/파티션) 단위로 템프에 내린 후(DISK I/O발생,성능저하) 다시 합쳐서 1-pass/멀티패스 방식으로 진행함.
파이썬 예제
- 두 개의 CSV 파일 sales.csv와 products.csv가 있다고 가정하고, 이를 파이썬 딕셔너리로 해시 조인을 구현하는 예제.
1. 데이터 준비 (sales.csv, products.csv 파일)
1) 대량 테이블 - 판매(sales.csv 파일)
sale_id,product_id,amount 1,101,100 2,102,150 3,101,200 4,103,50 .... ....
2) 제품 (products.csv)
product_id,product_name 101,Laptop 102,Mouse 103,Keyboard
2. 해시 조인 구현 코드
소량인 products 테이블을 빌드 테이블로, sales 테이블을 프로브 테이블로 사용하여 조인을 수행.
import csv # 1. 빌드 테이블: products.csv를 읽어 메모리 해시 테이블(딕셔너리) 생성 # 'product_id'를 키로, 'product_name'을 값으로 저장 products_hash_table = {} with open('products.csv', 'r') as f: reader = csv.DictReader(f) for row in reader: # 해시 테이블 생성 (딕셔너리) products_hash_table[row['product_id']] = row['product_name'] print("--- 빌드 단계 (해시 테이블) ---") print(products_hash_table) # 출력: {'101': 'Laptop', '102': 'Mouse', '103': 'Keyboard'} print("\n--- 프로브 단계 (조인 결과) ---") # 2. 프로브 테이블: sales.csv를 읽어 해시 테이블에서 찾기 with open('sales.csv', 'r') as f: reader = csv.DictReader(f) for row in reader: # sale_id 3의 'product_id'인 '101'을 해시 테이블에서 찾음 product_id = row['product_id'] if product_id in products_hash_table: # 해시 테이블에서 'product_id'를 키로 검색하여 'product_name'을 가져옴 product_name = products_hash_table[product_id] print(f"Sale ID: {row['sale_id']}, Product Name: {product_name}, Amount: {row['amount']}")
- 예상 출력:
# Sale ID: 1, Product Name: Laptop, Amount: 100 # Sale ID: 2, Product Name: Mouse, Amount: 150 # Sale ID: 3, Product Name: Laptop, Amount: 200 # Sale ID: 4, Product Name: Keyboard, Amount: 50
- products_hash_table이라는 딕셔너리가 바로 해시 테이블 역할을 합니다.
- sales 테이블의 각 행을 읽을 때마다 product_id를 딕셔너리(해시 테이블)에서 빠르게 찾아 product_name을 가져와 조인된 결과를 출력하는 방식
- 이를 통해 전체 products 테이블을 다시 스캔할 필요 없이 O(1)에 가까운 시간 복잡도로 조인 조건을 만족하는 데이터를 찾을 수 있음.
HASH 조인의 성능 향상 원리
Hash 버킷의 역할과 기능
- 해시 버킷은 두 테이블을 효율적으로 조인하기 위한 핵심적인 논리적 저장 공간.
- 이는 조인 키(Join Key)를 기반으로 데이터를 빠르게 찾고 저장하는 데 사용.
역할: 데이터의 논리적 분류 및 저장소
- 해시 버킷은 조인 키 값을 해시 함수에 넣어 얻은 해시 값이 같은 데이터들을 모아두는 공간.
- 이는 거대한 데이터를 조인 키를 기준으로 더 작은 그룹으로 나누어 관리하는 역할을 합니다.
- 이를 통해 빌드 테이블의 모든 데이터를 일일이 탐색하지 않고도, 특정 조인 키에 해당하는 데이터가 어느 버킷에 있는지 바로 알 수 있습니다.
기능: Build 단계와 Probe 단계에서의 활용
- Build 단계:
- Oracle은 먼저 두 테이블 중 더 작은 테이블을 선택하여 빌드 테이블로 지정합니다.
- 빌드 테이블의 각 행을 읽어 조인 키에 해시 함수를 적용하여 해시 값을 계산합니다.
- 계산된 해시 값에 해당하는 버킷에 해당 행의 데이터를 저장합니다. 만약 같은 버킷에 이미 다른 데이터가 있다면, 이를 연결 리스트(Linked List) 형태로 연결하여 **해시 충돌(Hash Collision)**을 처리합니다.
- Probe 단계:
- 이제 더 큰 테이블인 프로브 테이블을 순차적으로 읽습니다.
- 프로브 테이블의 각 행에서 조인 키를 추출하여, 빌드 단계에서 사용한 동일한 해시 함수로 해시 값을 계산합니다.
- 계산된 해시 값을 이용해 빌드 테이블의 해시 버킷 위치를 즉시 찾아갑니다.
- 해당 버킷 안의 연결 리스트를 탐색하여 조인 키가 일치하는 행을 찾습니다.
- 일치하는 행이 발견되면 두 테이블의 데이터를 결합하여 최종 결과를 생성합니다.
- 이러한 해시 버킷의 활용 덕분에, 해시 조인은 테이블의 크기와 상관없이 조인 키가 같은 데이터들을 O(1)에 가까운 시간 복잡도로 찾아낼 수 있어 대용량 데이터 조인에 매우 효과적입니다.
해시 버킷 개수의 결정
- 해시 조인의 최대 해시 버킷 개수는 사전 설정된 고정값이 아니라, 조인하려는 테이블의 크기, 옵티마이저의 예측, 그리고 PGA_AGGREGATE_TARGET 파라미터에 의해 동적으로 결정
- 빌드 테이블(Build Table)의 크기: 옵티마이저가 예측한 더 작은 테이블(빌드 테이블)의 크기에 따라 필요한 해시 버킷의 수가 결정됨
- 할당된 PGA 메모리: PGA_AGGREGATE_TARGET에 의해 세션에 할당된 PGA 메모리 내에서 해시 테이블이 생성됨.
- 메모리 부족 시: 만약 할당된 PGA 메모리만으로 해시 테이블을 모두 생성할 수 없다면, Oracle은 일부 해시 버킷을 디스크의 임시 테이블스페이스(temp tablespace)로 분할하여 저장합니다.
- 이를 '해시 스필(Hash Spill)'이라고 부르며, 이 경우 I/O가 발생하여 성능이 저하됨.
HASH 조인이 느려지는 원인
- 해시 조인 성능이 느려지는 주요 원인 중 하나는 해시 버킷 때문입니다.
- 정확히 말하면, 해시 충돌이 심하게 발생하거나 해시 테이블이 메모리에 맞지 않아 디스크 I/O가 발생하는 경우입니다.
- 해시 버킷 자체는 효율성을 위한 도구지만, 비정상적인 상황에서는 오히려 성능 저하의 원인이 됩니다.
1. 해시 충돌 (Hash Collisions)
- 원리: 해시 함수는 조인 키가 다르더라도 동일한 해시 값을 반환할 수 있습니다. 이것이 해시 충돌입니다.
- 문제점: 해시 충돌이 발생하면, 하나의 버킷에 여러 행이 연결 리스트 형태로 쌓이게 됩니다. 이 버킷을 탐색할 때, 원하는 데이터를 찾기 위해 연결된 모든 데이터를 순차적으로 비교해야 하므로, 탐색 시간이 O(1)에서 O(N)으로 늘어납니다.
- 결과: 조인 키 데이터 분포가 불균형하거나(데이터 편중), 해시 함수가 비효율적이면 해시 충돌이 자주 발생하여 성능이 크게 저하됩니다.
- (결론) 해시조인은 조인키로 사용되는 컬럼이 중복이 많을수록 성능이 좋지 않음
- 파이썬으로 해시 충돌 구현 예제
- 고의로 해시 충돌을 유발하는 데이터를 사용하여 해시 조인의 성능 차이를 보여줍니다.
- products_collision 리스트의 모든 product_id는 해시 함수를 거치면 같은 값을 반환하도록 설계되었습니다.
import time # 일반적인 데이터 (해시 충돌이 거의 없음) products_normal = [ {'product_id': 101, 'product_name': 'Laptop'}, {'product_id': 102, 'product_name': 'Mouse'}, {'product_id': 103, 'product_name': 'Keyboard'}, ] # 의도적으로 해시 충돌을 유발하는 데이터 # 101, 201, 301 모두 100으로 나눈 나머지가 1이 되도록 설계 products_collision = [ {'product_id': 101, 'product_name': 'Laptop'}, {'product_id': 201, 'product_name': 'Mouse'}, {'product_id': 301, 'product_name': 'Keyboard'}, ] # 조인 대상 데이터 (각 product_id에 대한 sales 데이터) sales = [{'sale_id': i, 'product_id': 101, 'amount': 100} for i in range(1000)] + \ [{'sale_id': i+1000, 'product_id': 201, 'amount': 150} for i in range(1000)] + \ [{'sale_id': i+2000, 'product_id': 301, 'amount': 200} for i in range(1000)] # 사용자 정의 해시 함수 (단순화를 위해) def custom_hash(key): return key % 100 def hash_join(build_table, probe_table): # 빌드 단계: 해시 버킷(딕셔너리) 생성 # 파이썬 딕셔너리의 키 충돌을 구현하기 위해, 딕셔너리의 값을 리스트로 저장 hash_buckets = {} for item in build_table: key = item['product_id'] bucket_index = custom_hash(key) if bucket_index not in hash_buckets: hash_buckets[bucket_index] = [] hash_buckets[bucket_index].append(item) # 프로브 단계: 조인 start_time = time.time() joined_results = [] for sale in probe_table: key = sale['product_id'] bucket_index = custom_hash(key) # 해시 버킷에서 일치하는 데이터를 찾기 (충돌 발생 시 순차 탐색) if bucket_index in hash_buckets: for product_info in hash_buckets[bucket_index]: if product_info['product_id'] == key: joined_results.append({**sale, **product_info}) break end_time = time.time() return end_time - start_time # 일반적인 데이터로 조인 normal_time = hash_join(products_normal, sales) # 해시 충돌 데이터로 조인 collision_time = hash_join(products_collision, sales) print(f"일반 데이터 조인 시간: {normal_time:.6f} 초") print(f"해시 충돌 조인 시간: {collision_time:.6f} 초") print(f"성능 저하 비율: {(collision_time / normal_time):.2f}배 느림")
2. 메모리 부족 및 디스크 I/O
- 원리: 해시 조인은 더 작은 테이블(빌드 테이블)을 메모리에 올려 해시 테이블을 만드는 것이 기본 전제입니다.
- 문제점: 빌드 테이블이 너무 커서 **메모리(PGA)**에 다 담을 수 없게 되면, Oracle은 해시 테이블을 여러 파티션으로 나누어 일부를 **임시 테이블스페이스(Temporary Tablespace)**에 저장합니다.
- 결과: 조인을 수행하기 위해 디스크에 기록된 파티션 데이터를 읽고 쓰는 디스크 I/O 작업이 반복적으로 발생합니다. 이는 메모리에서만 작업할 때보다 훨씬 느리므로 성능 저하의 결정적인 원인이 됩니다.
결론
- 해시 조인이 효율적으로 작동하는 것은 해시 버킷이 잘 분산되어 있고, 해시 테이블이 메모리에서 모두 처리될 때입니다. 만약 데이터가 한쪽으로 치우쳐 해시 충돌이 심하거나, 메모리 부족으로 디스크 I/O가 발생하면 해시 조인의 장점이 사라져 성능이 느려지게 됩니다.
HASH 조인의 장/단점
장점
- 대용량 테이블간 "=" 조건의 조인에 적합(정렬 불필요,입력 순서 무관)
- 빠른 접근 가능(버킷을 이용한 빠른 처리)
- 병렬처리에 적합하면 효율성이 좋음
단점
- "=" 조건에만 적합, 범위 조건(between 이나 like) 조인은 사용할수 없음.
- 메모리에 의존적임(빌드테이블이 메모리내에 들어가지 못하면 템프 i/o가 발생)
- 조인키값이 한쪽에 치우치거나(skew),중복도가 높으면 특정 버킷에 연결된 버킷이 길어져 탐색하는 시간이 증가함(CPU사용량 급증, 충돌증가)
- 버킷수가 데이터 대비 부족하면 충돌 발생과 체인 길이가 늘어 탐색 비용이 증가함
MERGE 조인
- 정확한 명칭은 'MERGE JOIN' 또는 'SORT MERGE JOIN')
- SORT(정렬) 후 MERGE(합치다) 의 의미
MERGE 조인이 필요한 경우
- 조인에 사용되는 양쪽 테이블이 이미 정렬되어 있거나, 정렬 비용이 크지 않은 경우
- 대량의 데이터에 대해 효율적인 조인이 필요할 때
MERGE 조인 동작 원리
- 조인에 참여하는 두 테이블의 조인 컬럼을 기준으로 정렬(sorting).
- 두 데이터 집합을 동시에 순차적 으로 탐색하면서 일치하는 조건이 있는 행을 찾아 조인 결과를 만듭니다.
- 두 개의 정렬된 리스트를 한 번에 훑는 것과 비슷하게 동작합니다.
장점
- 대량 데이터 조인에 효율적
- 인덱스가 없는 경우에도 성능이 좋은 편임
단점
- SORT 단계가 필요하므로 메모리 및 디스크 I/O를 소모
- 작은 데이터셋에는 HASH JOIN이 더 빠를 수 있음
MERGE 조인 사용 예시
SELECT /*+ USE_MERGE(a b) */ * FROM table_a a JOIN table_b b ON a.id = b.id;
파이썬으로 MERGE JOIN 구현
- 두 리스트(또는 테이블)가 각각 다음과 같이 주어졌다고 가정
# table_a: (id, value) # table_b: (id, desc) table_a = [ (1, 'apple'), (2, 'banana'), (4, 'melon'), (5, 'peach') ]; table_b = [ (1, 'red'), (2, 'yellow'), (3, 'green'), (4, 'green') ]; join_result = merge_join(table_a, table_b) for row in join_result: print(row) def merge_join(table_a, table_b): # 두 테이블을 id 기준으로 정렬 (이미 정렬되어 있다고 가정) # 만약 정렬이 안 되어 있다면 아래 코드를 참고: # table_a = sorted(table_a, key=lambda x: x[0]) # table_b = sorted(table_b, key=lambda x: x[0]) i, j = 0, 0 result = [] while i < len(table_a) and j < len(table_b): id_a = table_a[i][0] id_b = table_b[j][0] if id_a == id_b: # 조건이 일치할 때 JOIN 결과에 추가 result.append((id_a, table_a[i][1], table_b[j][1])) i += 1 j += 1 elif id_a < id_b: i += 1 else: j += 1 return result
- 실행 결과:
(1, 'apple', 'red') (2, 'banana', 'yellow') (4, 'melon', 'green')
설명
- 양쪽 리스트가 이미 정렬되어 있다는 가정 하에 두 인덱스를 비교해 가면서 일치하는 id를 찾고, 일치하지 않으면 더 작은 쪽 인덱스만 증가시켜 탐색하는 방식.
- Oracle의 MERGE JOIN과 거의 동일한 논리적 방식입니다.