세미조인

세미 조인(Semi Join)

목적

첫 번째 테이블의 데이터 중 두 번째 테이블과 일치하는 데이터만 반환

특징

조인 조건에 만족하는 첫 번째 테이블의 행만 선택
실제 두 번째 테이블의 컬럼은 결과에 포함되지 않음

주요 구현 방법

EXISTS 연산자 사용
IN 연산자 사용
예시 쿼리:

SELECT e.employee_id, e.name
FROM employees e
WHERE EXISTS (
    SELECT 1 
    FROM departments d 
    WHERE e.department_id = d.department_id
);

세미조인 알고리즘을 파이썬으로 구현

세미 조인은 "왼쪽(주 테이블)의 행 중에서 오른쪽(참조 테이블)에 일치하는 행이 존재하는지 여부만 검사"하여,
일치하는 왼쪽 행만 결과로 반환합니다.
오른쪽 테이블의 컬럼 값은 결과에 포함되지 않습니다.

프로그램 로직 설명

관계형 테이블을 Python의 리스트(딕셔너리 항목 리스트)로 표현하고,
조인 조건을 함수로 넘겨서 세미 조인을 수행하는 예시
또한 성능 관점에서 해시 기반(semi-join using hash set) 알고리즘과 중복 일치 처리(첫 발견 시 멈춤)를 반영

사용법 요약

left_rows, right_rows: 각 행은 컬럼명을 키로 하는 dict.
join_keys: 왼쪽과 오른쪽에서 비교할 키 이름의 튜플 리스트. 예: [("dept_id", "dept_id")]
key_func: (선택) 복잡한 조건이 필요하면 행 -> 키 변환 함수로 대체 가능.
semi_join_hash(left_rows, right_rows, join_keys) 호출로 결과 얻음.

- 코드:

from typing import List, Dict, Tuple, Callable, Any, Iterable

Row = Dict[str, Any]

def make_key_from_row(row: Row, keys: Iterable[str]) -> Tuple:
    """주어진 키 목록으로부터 튜플 키를 생성합니다. None 허용."""
    return tuple(row.get(k) for k in keys)

def semi_join_hash(
    left_rows: List[Row],
    right_rows: List[Row],
    join_keys: List[Tuple[str, str]],
    right_key_func: Callable[[Row], Tuple] = None,
    left_key_func: Callable[[Row], Tuple] = None
) -> List[Row]:
    """
    해시 기반 세미 조인 구현.

    매개변수:
    - left_rows: 왼쪽 테이블 행 리스트 (결과로 반환될 테이블)
    - right_rows: 오른쪽 테이블 행 리스트 (매칭 존재 여부 확인용)
    - join_keys: 왼쪽-오른쪽 키 쌍 리스트, 예: [("dept_id", "dept_id"), ("emp_no","emp_no")]
    - right_key_func: (선택) 오른쪽 행 -> 키 튜플 생성 함수. 지정되면 join_keys 무시 가능.
    - left_key_func: (선택) 왼쪽 행 -> 키 튜플 생성 함수. 지정되면 join_keys 무시 가능.

    반환값:
    - left_rows 중 오른쪽에 매칭되는 행만 포함하는 리스트
    """
    if right_key_func is None:
        right_key_names = [rk for _, rk in join_keys]
        def right_key_func(r): return make_key_from_row(r, right_key_names)

    if left_key_func is None:
        left_key_names = [lk for lk, _ in join_keys]
        def left_key_func(l): return make_key_from_row(l, left_key_names)

    # 1) 오른쪽 테이블의 키 집합 생성 (해시)
    right_key_set = set()
    for r in right_rows:
        key = right_key_func(r)
        # Oracle 세미조인 관점: NULL 포함 키 처리 시 NULL이 포함된 키는 매칭으로 간주하지 않는다.
        # Python에서는 None을 포함한 튜플도 set에 들어가므로, NULL 기준을 따르고 싶다면 아래처럼 필터링 가능.
        if any(v is None for v in key):
            # NULL 키는 매칭 불가(옵션). 필요 시 주석 처리하여 NULL도 허용 가능.
            continue
        right_key_set.add(key)

    # 2) 왼쪽 테이블을 순회하며 오른쪽 키 존재 여부만 검사
    result = []
    for l in left_rows:
        lkey = left_key_func(l)
        if any(v is None for v in lkey):
            # 왼쪽 키에 NULL이 있으면 일반적으로 매칭 불가. 필요 시 로직 변경 가능.
            continue
        if lkey in right_key_set:
            result.append(l)

    return result

사용 예시


left = [
    {"emp_id": 1, "name": "Kim", "dept_id": 10},
    {"emp_id": 2, "name": "Lee", "dept_id": 20},
    {"emp_id": 3, "name": "Park", "dept_id": None},
    {"emp_id": 4, "name": "Choi", "dept_id": 30},
]

right = [
    {"dept_id": 10, "dept_name": "HR"},
    {"dept_id": 20, "dept_name": "Sales"},
    {"dept_id": None, "dept_name": "Unknown"},
]

joined = semi_join_hash(left, right, [("dept_id", "dept_id")])
# joined 결과: emp_id 1, 2만 포함 (dept_id None은 무시)
print(joined)

주의사항 및 확장 아이디어:

- NULL 처리: SQL과 Python의 NULL(None) 동작 차이를 유의해야 합니다. 위 구현은 키에 None이 포함되면 매칭되지 않도록 처리했습니다. 필요하면 None 허용 방식으로 변경하실 수 있습니다.

- 다중 컬럼 조인: join_keys에 여러 쌍을 넣으면 다중 컬럼 조인이 됩니다.

- 대량 데이터: 메모리 제약이 있다면 해시 대신 블록 기반 또는 외부 정렬(merge) 접근을 구현해야 합니다.

- Anti Join: 동일한 원리로 right_key_set에 없는 left 행을 반환하도록 바꾸면 안티 조인이 됩니다.

- EXISTS의 짧은 회로(semi-join short-circuit) 동작을 흉내내려면 right 테이블에 대해 인덱스 또는 키 집합을 먼저 만든 후 왼쪽을 순회하는 현재 방법이 적절합니다.