안티 조인(Anti Join)
목적
- 첫 번째 테이블의 데이터 중 두 번째 테이블과 일치하지 않는 데이터만 반환
특징
- NOT EXISTS 또는 NOT IN 연산자 사용
- 조인 조건에 만족하지 않는 행만 선택
- 예시 쿼리:
SELECT e.employee_id, e.name
FROM employees e
WHERE NOT EXISTS (
SELECT 1
FROM departments d
WHERE e.department_id = d.department_id
);
- 세미 조인과 주요 차이점:
- 세미 조인: 일치하는 데이터 선택 - 안티 조인: 일치하지 않는 데이터 선택
- 성능 팁:
- - 인덱스 활용
- - 서브쿼리 최적화
- - 데이터 양에 따른 적절한 조인 방식 선택
안티조인 알고리즘을 파이썬으로 구현
요청하신 Oracle 스타일의 안티 조인(Anti Join) 알고리즘을 Python으로 구현해 드리겠습니다. 설명과 함께 다음 구현은 앞서 제공한 세미 조인과 동일한 인터페이스를 유지하되, Oracle/SQL의 NOT EXISTS/NOT IN 의미를 가능한 한 근접하게 모사하도록 NULL 처리 정책을 명확히 반영합니다.
정책(기본값) - 오른쪽의 키 집합을 만들 때 NULL 값이 포함된 키 튜플은 매칭 대상으로 간주하지 않습니다(즉, 오른쪽에 NULL 키가 있어도 그 행은 키 집합에 추가되지 않음). - 왼쪽 행의 키에 NULL이 포함된 경우:
- SQL의 NOT EXISTS 관점에서는 일반적으로 NULL 자체가 존재 여부 판정에 영향을 주지 않으므로, 왼쪽 키가 NULL이라 하더라도 오른쪽에 해당 비-NULL 키가 없으면 안티 조인 결과에 포함됩니다. - 그러나 NOT IN의 경우 NULL 비교로 인해 결과가 달라질 수 있으므로, 본 구현은 NOT EXISTS 해석을 따릅니다(왼쪽에 NULL 있어도 오른쪽에 매칭이 없으면 결과에 포함).
원하시면 NULL 처리 정책을 변경한 버전도 제공 가능합니다.
코드: ```python from typing import List, Dict, Tuple, Callable, Any, Iterable
Row = Dict[str, Any]
def make_key_from_row(row: Row, keys: Iterable[str]) -> Tuple:
"""주어진 키 목록으로부터 튜플 키를 생성합니다.""" return tuple(row.get(k) for k in keys)
def anti_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, treat_null_in_right_as_non_matching: bool = True
) -> List[Row]:
""" 해시 기반 안티 조인 구현 (NOT EXISTS 해석 기반).
매개변수:
- left_rows: 왼쪽 테이블 행 리스트 (결과로 반환될 테이블)
- right_rows: 오른쪽 테이블 행 리스트 (매칭 존재 여부 확인용)
- join_keys: 왼쪽-오른쪽 키 쌍 리스트, 예: [("dept_id", "dept_id")]
- right_key_func: (선택) 오른쪽 행 -> 키 튜플 생성 함수. 지정되면 join_keys 무시 가능.
- left_key_func: (선택) 왼쪽 행 -> 키 튜플 생성 함수. 지정되면 join_keys 무시 가능.
- treat_null_in_right_as_non_matching: True이면 오른쪽 키에 None이 포함된 행은 키 집합에 추가하지 않음.
False이면 None을 포함한 키도 집합에 추가(권장하지 않음, SQL의 NULL 비교와 차이 발생).
반환값:
- 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)
if treat_null_in_right_as_non_matching and any(v is None for v in key):
# 오른쪽에 NULL이 포함된 키는 매칭 키로 사용하지 않음 (NOT EXISTS 해석)
continue
right_key_set.add(key)
# 2) 왼쪽 테이블을 순회하며 오른쪽에 매칭이 없는 행만 결과에 추가
result = []
for l in left_rows:
lkey = left_key_func(l)
# NOT EXISTS 해석:
# - 왼쪽 키에 NULL이 있어도, 오른쪽에 동일한 (비-NULL) 키가 없다면 안티 조인 결과에 포함되어야 함.
# 따라서 왼쪽 키에 None이 있어도 단순히 건너뛰지 않는다.
# - 다만 오른쪽에 None을 포함하는 키를 매칭 대상으로 삼지 않았으므로, None 관련 비교는 위험이 없다.
if lkey not in right_key_set:
result.append(l)
return result
```
사용 예시: ```python 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"},
]
anti = anti_join_hash(left, right, [("dept_id", "dept_id")])
- anti 결과: emp_id 3 (dept_id None) 및 emp_id 4 (dept_id 30) 포함
print(anti) ```
주의사항 및 확장 제안: - NOT IN vs NOT EXISTS: NOT IN은 오른쪽에 NULL이 있으면 결과가 달라질 수 있습니다(대부분의 경우 NULL 때문에 비교 결과가 UNKNOWN이 되어 제외됨). 본 구현은 NOT EXISTS 해석을 따릅니다. NOT IN 동작을 그대로 모사하려면 오른쪽에 NULL이 존재하면 모든 결과를 빈 결과로 만드는 특별 처리 필요. - 다중 컬럼 조인: join_keys에 여러 쌍을 넣으면 복합 키로 동작합니다. - 성능: 해시 기반이므로 오른쪽 집합 전체를 메모리에 올립니다. 큰 데이터셋에서는 메모리/외부 정렬/블록 처리 고려가 필요합니다. - 인덱스 흉내: 오른쪽을 키->rows 맵으로 만들면, 매칭 행의 존재 여부뿐 아니라 첫 매칭 행의 상세 정보가 필요할 때 확장 가능합니다.
- NOT IN과 동일한 NULL 동작을 재현하는 버전, 또는 LEFT NULL을 명확히 제외하는 버전으로 코드를 바꿔드리겠습니다. 어느 방식으로 동작하기를 원하시는지 알려주시면 즉시 수정해 드리겠습니다.
요청하신 두 가지 옵션에 맞게 안티 조인 구현을 수정한 코드를 제공해드리겠습니다. 각 버전은 NULL 처리 방식이 다르므로 목적에 맞는 것을 선택해 사용하시면 됩니다.
두 버전 공통 인터페이스: - 함수명: anti_join_hash(...) - 인자:
- left_rows, right_rows: 리스트(dict) 형식의 테이블 행
- join_keys: 왼쪽-오른쪽 키 쌍 리스트 예: [("dept_id","dept_id")]
- right_key_func, left_key_func: (선택) 사용자 정의 키 생성 함수
- 반환값: 오른쪽에 매칭되는 행이 없는 왼쪽 행 리스트
버전 A — NOT IN과 동일한 NULL 동작 재현 - 동작 요약:
- SQL의 NOT IN은 오른쪽에 NULL이 하나라도 있으면 비교 결과가 UNKNOWN으로 되어 "아무것도 반환하지 않는" 효과가 납니다. - 이 버전은 오른쪽 키 집합에 NULL 포함 키가 하나라도 존재하면, SQL의 NOT IN 동작을 모사하여 빈 결과([])를 반환합니다. - 오른쪽에 NULL이 없으면 일반적인 해시 기반 안티 조인으로 동작합니다.
버전 B — LEFT NULL을 명확히 제외 - 동작 요약:
- 왼쪽 행의 키에 NULL이 하나라도 포함된 경우 그 행은 결과에서 제외합니다 (세미 조인과 동일한 NULL 정책으로 제외). - 오른쪽 NULL 처리 여부는 옵션으로 제어(기본: treat_null_in_right_as_non_matching=True)하며, 기본적으로 오른쪽에 NULL이 포함된 키는 매칭 대상으로 사용하지 않습니다.
코드 (두 버전 모두 포함): ```python from typing import List, Dict, Tuple, Callable, Any, Iterable
Row = Dict[str, Any]
def make_key_from_row(row: Row, keys: Iterable[str]) -> Tuple:
"""주어진 키 목록으로부터 튜플 키를 생성합니다.""" return tuple(row.get(k) for k in keys)
def anti_join_hash_not_in_semantics(
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]:
"""
NOT IN과 동일한 NULL 동작을 모사한 안티 조인.
- 오른쪽에 NULL을 포함한 키가 하나라도 존재하면 SQL의 NOT IN과 동일하게 빈 결과를 반환합니다.
- 그렇지 않으면 오른쪽의 (비-NULL) 키 집합에 없는 왼쪽 행들을 반환합니다.
"""
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)
# 오른쪽 키 집합 생성 및 오른쪽에 NULL 포함 여부 검사
right_key_set = set()
right_has_null_key = False
for r in right_rows:
key = right_key_func(r)
if any(v is None for v in key):
right_has_null_key = True
else:
right_key_set.add(key)
# NOT IN semantics: 오른쪽에 NULL이 하나라도 있으면 결과는 빈 집합
if right_has_null_key:
return []
# 오른쪽에 NULL이 없으면 단순한 안티 조인
result = []
for l in left_rows:
lkey = left_key_func(l)
# LEFT NULL은 비교 시 None이 포함된 키는 일반적으로 right_key_set에 포함되지 않으므로
# 해당 키가 없으면 결과에 포함됩니다. (NOT IN의 경우 오른쪽에 NULL이 없으므로 여기서는 안전)
if lkey not in right_key_set:
result.append(l)
return result
def anti_join_hash_exclude_left_nulls(
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, treat_null_in_right_as_non_matching: bool = True
) -> List[Row]:
"""
왼쪽 NULL을 명확히 제외하는 안티 조인 (세미 조인과 동일한 NULL 정책).
- 왼쪽 키에 None이 포함된 행은 결과에서 제외합니다.
- 오른쪽의 None 포함 키는 treat_null_in_right_as_non_matching=True일 때 매칭 대상으로 사용하지 않습니다.
"""
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)
# 오른쪽 키 집합 생성
right_key_set = set()
for r in right_rows:
key = right_key_func(r)
if treat_null_in_right_as_non_matching and any(v is None for v in key):
continue
right_key_set.add(key)
# 왼쪽을 순회하며 왼쪽 NULL은 제외
result = []
for l in left_rows:
lkey = left_key_func(l)
if any(v is None for v in lkey):
# 왼쪽 키에 NULL이 있으면 세미 조인과 동일하게 결과에서 제외
continue
if lkey not in right_key_set:
result.append(l)
return result
```
간단한 사용 예: ```python left = [
{"emp_id": 1, "dept_id": 10},
{"emp_id": 2, "dept_id": 20},
{"emp_id": 3, "dept_id": None},
{"emp_id": 4, "dept_id": 30},
]
right_with_null = [
{"dept_id": 10},
{"dept_id": None},
]
right_no_null = [
{"dept_id": 10},
{"dept_id": 20},
]
- NOT IN semantics: 오른쪽에 NULL이 있으면 빈 결과
print(anti_join_hash_not_in_semantics(left, right_with_null, [("dept_id","dept_id")])) # => []
- NOT IN semantics: 오른쪽에 NULL 없을 때 정상 동작
print(anti_join_hash_not_in_semantics(left, right_no_null, [("dept_id","dept_id")]))
- => [{'emp_id': 3, 'dept_id': None}, {'emp_id': 4, 'dept_id': 30}]
- 왼쪽 NULL 제외 버전
print(anti_join_hash_exclude_left_nulls(left, right_no_null, [("dept_id","dept_id")]))
- => [{'emp_id': 4, 'dept_id': 30}] (emp_id 3은 left NULL이라 제외)
```
참고 및 권장 사항: - NOT IN을 정확히 재현하려면 오른쪽에 NULL이 하나라도 있는 경우 결과가 빈 집합이 되는 정책을 적용해야 합니다. 이는 SQL 표준에서 NULL 비교가 UNKNOWN으로 처리되는 특성 때문입니다. - 실제 데이터베이스는 NULL 처리나 인덱스, 실행계획에 따라 미세한 차이가 있을 수 있으므로, 복잡한 케이스(복합 키, NULL 혼합 등)는 테스트로 확인하시길 권장드립니다. - 대용량 데이터의 경우 해시 기반 접근은 메모리 사용량이 커질 수 있으므로 외부 정렬(merge-based) 또는 블록 처리 방식 고려가 필요합니다.
원하시면 위 코드 중 하나를 기반으로 성능 최적화(예: 오른쪽을 키->행 맵으로 만들어 첫 매칭을 빠르게 검사), 복합 키 예제, 또는 Pandas DataFrame 버전으로 변환해 드리겠습니다. 어느 쪽을 더 원하시는지 알려주십시오.