안티 조인(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
);
- 세미 조인과 주요 차이점:
- 세미 조인: 일치하는 데이터 선택 - 안티 조인: 일치하지 않는 데이터 선택
- 성능 팁:
- - 인덱스 활용
- - 서브쿼리 최적화
- - 데이터 양에 따른 적절한 조인 방식 선택
안티조인 알고리즘을 파이썬으로 구현
- 안티조인 알고리즘
- 오른쪽의 키 집합을 만들 때 NULL 값이 포함된 키 튜플은 매칭 대상으로 간주하지 않습니다(즉, 오른쪽에 NULL 키가 있어도 그 행은 키 집합에 추가되지 않음).
- 왼쪽 행의 키에 NULL이 포함된 경우:
- - SQL의 NOT EXISTS 관점에서는 일반적으로 NULL 자체가 존재 여부 판정에 영향을 주지 않으므로, 왼쪽 키가 NULL이라 하더라도 오른쪽에 해당 비-NULL 키가 없으면 안티 조인 결과에 포함됩니다.
- 그러나 NOT IN의 경우 NULL 비교로 인해 결과가 달라질 수 있으므로, 아래 구현된 내용은 NOT EXISTS 해석을 따릅니다(왼쪽에 NULL 있어도 오른쪽에 매칭이 없으면 결과에 포함).
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
- 사용 예시:
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을 명확히 제외하는 버전
- 두 버전 공통 인터페이스:
- - 함수명: 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이 포함된 키는 매칭 대상으로 사용하지 않습니다.
- 코드 (두 버전 모두 포함):
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
- 간단한 사용 예:
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) 또는 블록 처리 방식 고려가 필요합니다.