세미 조인

세미 조인(Semi Join, ⋉)은 두 릴레이션 R, S 를 조인했을 때 짝이 있는 R 의 튜플만 골라, R 의 속성만으로 결과를 돌려주는 관계 연산으로, R ⋉ S = π_{R의 속성}(R ⋈ S) 와 같다.

개요

일반 조인은 두 릴레이션의 속성을 이어 붙인 넓은 튜플을 만든다. 세미 조인은 "S 에 짝이 있는가"만 확인하고 S 의 속성은 결과에 넣지 않는다. 그래서 결과의 차수(속성 수)는 R 과 같고, 결과 튜플 수는 R 의 튜플 수를 넘지 않는다. S 에 짝이 여러 개 있어도 R 의 튜플은 한 번만 나온다. 아파치 스파크 SQL 문서는 세미 조인을 "오른쪽과 짝이 맞는 왼쪽 릴레이션의 값을 돌려주는" 조인으로, 반대로 짝이 없는 왼쪽 값을 돌려주는 것을 안티 조인(anti join, ▷)으로 정의한다.

분산 질의 처리에서의 쓰임

세미 조인은 원래 분산 데이터베이스에서 네트워크로 보내는 데이터 양을 줄이려고 주목받았다. 번스타인(Bernstein)과 추(Chiu)는 세미 조인을 되풀이해 관계형 질의를 푸는 방법을 정리했다. 사이트 1 의 R 과 사이트 2 의 S 를 조인할 때

1. 사이트 2 가 S 의 조인 속성만 추출(π)해 사이트 1 로 보낸다
2. 사이트 1 이 R ⋉ (받은 조인 속성)을 계산해, 실제로 짝이 있는 R 튜플만 남긴다
3. 줄어든 R 을 사이트 2 로 보내 S 와 최종 조인한다

R 전체를 보내는 대신 짝이 있는 튜플만 보내므로, 조인 선택도가 낮을 때 전송량이 크게 준다. 반대로 거의 모든 튜플이 짝이 있으면 조인 속성을 한 번 더 보내는 비용만 늘어난다.

SQL 로 나타내기

SQL 표준에는 SEMI JOIN 키워드가 없고 EXISTS 나 IN 부속 질의로 쓴다(스파크 SQL 은 LEFT SEMI JOIN 을 지원한다).

SELECT * FROM R WHERE EXISTS (SELECT 1 FROM S WHERE S.k = R.k);  -- R ⋉ S
SELECT * FROM R WHERE NOT EXISTS (SELECT 1 FROM S WHERE S.k = R.k);  -- 안티 조인

옵티마이저가 EXISTS 부속 질의를 세미 조인으로 바꾸어 처리하기도 한다 → 데이터베이스 서브 쿼리

다른 조인과 구별하기

연산	결과 속성	짝 없는 R 튜플	S 에 짝이 여러 개일 때
자연 조인 R ⋈ S	R 과 S 속성 모두	빠진다	짝 수만큼 행이 생긴다
세미 조인 R ⋉ S	R 속성만	빠진다	R 튜플 한 번
왼쪽 외부 조인 R ⟕ S	R 과 S 속성 모두	남고 S 속성은 NULL	짝 수만큼 행이 생긴다

세미 조인 결과에는 S 쪽 속성 열이 없으므로, 결과 릴레이션에 S 의 속성이 들어 있거나 NULL 로 채운 행이 있다면 세미 조인이 아니다.

같이 보기

• 데이터베이스 조인
• 외부 조인
• 관계 대수
• 데이터베이스 서브 쿼리