PostgreSQL: 조인 알고리즘과 유형

※ PostgreSQL: Join Algorithms and Types.

 

안녕하세요. 듀스트림입니다.

오늘은 PostgreSQL의 조인 알고리즘을 프로그래밍 관점에서 정리해 보겠습니다.

PostgreSQL로 명시했지만, 알고리즘은 대부분의 DBMS에서 유사합니다.

---

1. 조인 알고리즘

PostgreSQL은 세 가지 조인 알고리즘을 사용합니다.

각 알고리즘은 데이터의 크기, 정렬 여부, 조인 조건 등에 따라 성능과 메모리 사용에 차이가 있습니다.

 

1.1. Nested Loop Join (중첩 반복 조인)

• 동작 방식: 한 테이블의 각 행을 기준으로 다른 테이블의 모든 행을 순회하면서 조인 조건에 맞는 행을 찾습니다.
  • 드라이빙 테이블(Driving Table):
    • 외부 for문에서 순회하는 테이블로, 가능한 한 행 수가 적거나 필터링된 결과가 작은 테이블을 선택하여 전체 반복 횟수를 줄입니다.
  • 드리븐 테이블(Driven Table):
    • 외부 테이블의 각 행에 대해 내부 for문으로 탐색되는 테이블입니다.
• 드라이빙 테이블에 많은 행이 있으면 내부 루프가 여러 번 실행되어 성능이 크게 저하되므로, 조인 순서를 잘 선택하는 것이 중요합니다.
  
  
• 파이썬 예제

def nested_loop_join(driving_table, driven_table, key):
    """
    driving_table (외부 루프, 주도 테이블)과 driven_table (내부 루프, 대상 테이블)을 
    key를 기준으로 inner join 수행
    """
    result = []
    for row1 in driving_table:           # 드라이빙 테이블 (외부 for문)
        for row2 in driven_table:        # 드리븐 테이블 (내부 for문)
            if row1[key] == row2[key]:   # ON절의 조건
                merged_row = row1.copy()
                merged_row.update(row2)
                result.append(merged_row)
    return result

---

1.2. Hash Join (해시 조인)

• 동작 방식: 해시 조인은 주로 동등 조인(equi-join) 조건에서 사용되며, 다음과 같은 두 단계로 나누어 처리됩니다.
  
  • 빌드(Build) 단계:
    
    • 작은 테이블(또는 조인 조건의 선택도가 높은 테이블)의 각 행을 대상으로, 조인 키 값을 기준으로 해시 테이블(파이썬의 딕셔너리)을 생성합니다.
    • 이 해시 테이블은 조인 키를 빠르게 검색할 수 있도록 미리 구성되어, 이후 조인 작업의 탐색 비용을 크게 줄입니다.
  • 프로브(Probe) 단계:
    
    • 큰 테이블의 각 행에 대해, 조인 키 값을 해시 테이블에서 검색(프로빙)합니다.
    • 해시 테이블에 해당 키가 존재하면, 매칭되는 행을 결합하여 결과를 생성합니다.
• 이 두 단계의 분리를 통해 해시 조인은 전체 데이터 스캔 비용을 낮추고, O(n + m) 정도의 시간 복잡도로 동작할 수 있습니다.
• 단, 빌드 단계에서 해시 테이블을 메모리에 구성하기 때문에 메모리 사용량이 중요한 고려 대상이 됩니다.
  
  
• 파이썬 예제

def hash_join(table1, table2, key):
    """
    table1과 table2에서 key를 기준으로 inner join 수행 (해시 조인 방식)
    
    빌드 단계: table2(보통 행의 수가 적은 테이블)를 해시 테이블로 구성.
    프로브 단계: table1의 각 행에 대해 해시 테이블에서 매칭되는 행을 조회.
    """
    result = []
    # 빌드 단계: table2를 해시 테이블로 구성
    hash_table = {}
    for row in table2:
        k = row[key]
        hash_table.setdefault(k, []).append(row)
    
    # 프로브 단계: table1의 각 행에 대해 해시 테이블을 조회
    for row1 in table1:
        k = row1[key]
        if k in hash_table:
            for row2 in hash_table[k]:
                merged_row = row1.copy()
                merged_row.update(row2)
                result.append(merged_row)
    return result

 

• 안티 해시 조인(anti hash join)
  • 한쪽 테이블의 행들 중에서 다른 테이블에 매칭되는 행이 없는 경우만을 반환하는 join 방식입니다.
  • SQL에서 anti join 또는 left anti join이라고 부르며, NOT EXISTS나 NOT IN을 사용할 때와 유사한 개념입니다.
• 파이썬 예제 (Anti Join)

def anti_hash_join(table1, table2, key):
    """
    table1의 행 중 table2에 key 값이 존재하지 않는 행만 반환 (Anti Join)
    """
    result = []
    # table2를 해시 테이블로 구성
    hash_table = { row[key] for row in table2 }
    
    # table1의 각 행에 대해 해시 테이블에 없는 경우를 반환
    for row1 in table1:
        if row1[key] not in hash_table:
            result.append(row1)
    return result

---

1.3. Merge Join (병합 조인)

• 두 테이블이 조인 키 기준으로 정렬된 상태일 때, 두 테이블을 동시에 순회하며 조인합니다.
  1. 각 테이블에 대해 포인터(인덱스)를 초기화합니다.
  2. 포인터가 가리키는 키 값을 비교하여, 같으면 매칭된 모든 조합을 생성하고 포인터를 적절히 이동시킵니다.
  3. 정렬되지 않은 경우에는 정렬 비용이 추가됩니다.
• 정렬된 데이터를 한 번만 순회하기 때문에 효율적이며, 특히 대용량 데이터에서 유리합니다.
  
  
• 파이썬 예제

def merge_join(sorted_table1, sorted_table2, key):
    """
    정렬된 sorted_table1과 sorted_table2에서 key를 기준으로 inner join 수행 (병합 조인 방식)
    """
    result = []
    i, j = 0, 0
    while i < len(sorted_table1) and j < len(sorted_table2):
        val1 = sorted_table1[i][key]
        val2 = sorted_table2[j][key]
        if val1 == val2:
            # 동일한 키를 가진 모든 조합 생성
            temp_j = j
            while temp_j < len(sorted_table2) and sorted_table2[temp_j][key] == val2:
                merged_row = sorted_table1[i].copy()
                merged_row.update(sorted_table2[temp_j])
                result.append(merged_row)
                temp_j += 1
            i += 1
        elif val1 < val2:
            i += 1
        else:
            j += 1
    return result

---

2. 논리적 조인 유형

2.1. Inner Join (내부 조인)

• 두 테이블에서 조인 조건에 일치하는 행만 결합합니다.
• Nested Loop, Hash, Merge 등 여러 알고리즘으로 구현될 수 있습니다.
• 앞서 제공한 Nested Loop, Hash, Merge Join 예제들은 모두 inner join을 수행합니다.

---

2.2. Outer Join (외부 조인)

• 종류
  • Left Outer Join: 왼쪽 테이블의 모든 행을 반환하고, 오른쪽에 매칭되는 값이 없으면 오른쪽 컬럼은 NULL로 채워집니다.
  • Right Outer Join: 오른쪽 테이블의 모든 행을 반환하고, 왼쪽에 매칭되지 않으면 왼쪽 컬럼은 NULL 처리됩니다.
  • Full Outer Join: 양쪽 테이블의 모든 행을 반환하며, 한쪽에만 존재하는 경우 다른 쪽은 NULL이 됩니다.
• 파이썬 예제 (Left Outer Join)

def left_outer_join(table1, table2, key):
    """
    table1(왼쪽 테이블)과 table2(오른쪽 테이블)에서 key를 기준으로 left outer join 수행
    """
    result = []
    for row1 in table1:
        matched = False
        for row2 in table2:
            if row1[key] == row2[key]:
                merged_row = row1.copy()
                merged_row.update(row2)
                result.append(merged_row)
                matched = True
        if not matched:
            # 매칭되지 않으면 오른쪽 테이블의 컬럼은 None 처리
            merged_row = row1.copy()
            if table2:
                for k in table2[0].keys():
                    merged_row[k] = None # None = SQL에서 NULL
            result.append(merged_row)
    return result

---

2.3. Self Join (자기 자신 조인)

• 동일한 테이블 내에서 두 번 참조하여, 서로 다른 별칭(alias)을 부여한 후 조건에 따라 조인합니다.
• 예를 들어, 직원 테이블에서 상사와 부하의 관계를 찾을 때 사용할 수 있습니다.
  
  
• 파이썬 예제

def self_join(table, key1, key2):
    """
    동일 테이블 내에서 key1과 key2가 일치하는 경우를 찾는 self join 예제
    (예: employee 테이블에서 'id'와 'manager_id'가 일치하는 경우)
    """
    result = []
    for row1 in table:      # 테이블의 한 행 (부하)
        for row2 in table:  # 같은 테이블의 다른 행 (상사)
            if row1[key1] == row2[key2]:
                merged_row = row1.copy()
                # self join 시에는 alias 구분을 위해 key에 접두사를 붙일 수 있음
                merged_row = { **{'emp_' + k: v for k, v in row1.items()},
                               **{'mgr_' + k: v for k, v in row2.items()} }
                result.append(merged_row)
    return result

---

2.4. Cross Join (교차 조인)

• 두 테이블의 모든 행의 조합(Cartesian Product)을 반환합니다.

def cross_join(table1, table2):
    """
    table1과 table2의 모든 행 조합을 반환 (교차 조인)
    """
    result = []
    for row1 in table1:
        for row2 in table2:
            merged_row = row1.copy()
            merged_row.update(row2)
            result.append(merged_row)
    return result

---

2.5. Semi Join (세미 조인)

• 왼쪽 테이블의 행 중, 오른쪽 테이블과 매칭되는 행이 존재하는 경우만 선택하지만 오른쪽 테이블의 컬럼은 포함하지 않습니다.
• 일반적으로 EXISTS 또는 IN 서브쿼리의 결과와 유사한 역할을 합니다.
  
  
• 파이썬 예제

def semi_join(table1, table2, key):
    """
    table1에서 table2와 key가 매칭되는 행만 반환 (오직 table1의 컬럼만 포함)
    """
    result = []
    # table2의 key 값을 집합으로 구성
    key_set = { row[key] for row in table2 }
    for row1 in table1:
        if row1[key] in key_set:
            result.append(row1)
    return result

---

2.6. Anti Join (안티 조인)

• 왼쪽 테이블의 행 중, 오른쪽 테이블과 매칭되지 않는 행을 반환합니다.
• 예를 들어, 존재하지 않는 값을 찾거나 NOT EXISTS 서브쿼리와 유사한 역할을 합니다.

---

정리하자면,

• Inner Join, Self Join, Cross Join은 단순한 행 결합에 집중합니다.
• Outer Join은 매칭되지 않는 행까지 포함하여 누락 없이 데이터를 반환합니다.
• Semi Join과 Anti Join은 서브쿼리나 존재 여부 확인에 활용되어 불필요한 중복 결합을 피합니다.
• 안티 해시 조인은 해시 조인의 변형으로, 매칭되지 않는 데이터를 효율적으로 찾기 위한 기법입니다.

쿼리 플래너는 통계 정보를 바탕으로 조인 순서를 결정하며, 가장 효율적인 알고리즘(Nested Loop, Hash, Merge)과 조인 순서를 선택합니다.

 

또, 보통 우리가 SQL을 작성할 때 습관적으로 조인을 위한 ON절에서 대상 테이블을 먼저 적는데 사실 SQL에서 이 순서는 의미가 없습니다.

ON절에 작성된 순서 단지 논리적인 조건을 나타낼 뿐이며, 실제 실행 계획에서 어떤 테이블을 드라이빙 테이블로 할지는 쿼리 플래너가 내부 통계와 비용 모델을 기반으로 결정합니다. (물론, Hint(pg_hint_plan)로 강제할 수 있습니다.)

---

흐름도도 그려서 넣을까 했었는데.. 파이썬 예제로도 충분히 설명이 될 거 같아서 굳이 그리지는 않았습니다. (귀찮아서 아님)

 

오늘은 여기까지~