해시 결합

해시 조인은 조인 알고리즘의 일례이며 관계형 데이터베이스 관리 시스템의 구현에 사용됩니다.해시 결합 알고리즘의 모든 변형에는 결합된 관계 중 하나 또는 양쪽의 튜플에서 해시 테이블을 작성한 후 동일한 해시 코드를 가진 튜플만 equijoin에서 비교할 필요가 있도록 이들 테이블을 프로빙하는 작업이 포함됩니다.

결합의 프로브측이 매우 작은 경우를 제외하고 해시 결합은 일반적으로 중첩된 루프 결합보다 효율적입니다.이들은 equijoin 술어(하나 이상의 열에 있는 등가 연산자 '='의 결합을 사용하여 한 표의 레코드와 다른 표의 레코드를 비교하는 술어)를 필요로 한다.

클래식 해시 결합

2개의 관계의 내부 조인에 대한 고전적인 해시 조인 알고리즘은 다음과 같이 진행됩니다.

• 먼저 로컬 술어를 적용한 후 가장 작은 관계 중 하나의 내용을 사용하여 해시 테이블을 작성합니다.이 관계를 조인 빌드 측이라고 합니다.해시 테이블엔트리는 (콤포지트) join 애트리뷰트 값에서 해당 행의 나머지 애트리뷰트(필요한 애트리뷰트)에 대한 매핑입니다.
• 해시 테이블이 작성되면 다른 관계(프로브 측)를 스캔합니다.프로브 관계의 각 행에 대해 해시 테이블을 참조하여 빌드 관계에서 관련 행을 찾습니다.

첫 번째 단계는 보통 "구축" 단계라고 불리며, 두 번째 단계는 "프로브" 단계라고 불립니다.마찬가지로 해시 테이블이 구축되는 조인 관계는 "빌드" 입력이라고 불리는 반면 다른 입력은 "프로브" 입력이라고 불립니다.

이 알고리즘은 간단하지만 메모리에는 보다 작은 조인 관계가 필요합니다.이 알고리즘은 경우에 따라서는 그렇지 않습니다.이 상황에 대처하기 위한 간단한 방법은 다음과 같습니다.

1. 빌드 $입력$의 각 $튜플$에 대해 R$${\$displaystyle$$$R$$$}$
   1. 메모리 내 해시 테이블에 r$\displaystyle$r을 $추가$합니다.
   2. 해시 테이블의 크기가 메모리 내 최대 크기와 동일한 경우:
      1. 프로브 $입력{\displaystyle }$ S$(\displaystyle$ S$)$를 스캔하고 일치하는 조인 튜플을 출력 관계에 추가합니다.
      2. 해시 테이블을 리셋하고 빌드 $입력{\displaystyle }$ R$(\displaystyle$ R$)$ 스캔을 계속합니다.
2. 프로브 $S$를 최종 스캔하고(\$displaystyle$ S) 결과 조인 튜플을 출력 관계에 추가합니다.

이는 기본적으로 블록네스트 루프 가입 알고리즘과 동일합니다.이 알고리즘은 최종적으로 S$(\displaystyle$ S$)$를 필요 이상으로 $스캔합니다{\displaystyle }$.

그레이스 해시 결합

GRACE 데이터베이스 머신을 처음 구현한 후 그레이스 해시 조인이라고 하는 접근방식을 사용합니다.

이 알고리즘은 해시함수를 통해 R$(\displaystyle$ R$)$과 S$(\displaystyle$ S$)$를 $모두{\displaystyle }$ 먼저 분할하고 이러한 파티션을 디스크에 기록함으로써 전체$$S(\$displaystyle$ S$)$ 관계를$$ $다시{\displaystyle }$ 스캔하는 것을 방지합니다.그런 다음 알고리즘은 파티션 쌍을 메모리에 로드하고 더 작은 파티션 관계에 대한 해시 테이블을 작성하고 현재 해시 테이블과 일치하는 다른 관계를 검색합니다.파티션은 조인 키의 해시에 의해 형성되었기 때문에 조인 출력 튜플이 같은 파티션에 속해야 합니다.

하나 이상의 파티션이 여전히 사용 가능한 메모리에 맞지 않을 수 있습니다.이 경우 알고리즘이 재귀적으로 적용됩니다.대형 파티션을 하위 파티션으로 해시하기 위해 추가 직교 해시 함수가 선택되고 이전과 같이 처리됩니다.이 방법은 비용이 많이 들기 때문에 알고리즘은 초기 분할 단계에서 가능한 한 작은 파티션을 형성함으로써 발생할 가능성을 줄이려고 합니다.

하이브리드 해시 결합

하이브리드 해시 결합^[1] 알고리즘은 그레이스 해시 결합을 개량하여 더 많은 가용 메모리를 활용합니다.파티셔닝 단계에서 하이브리드 해시 조인에서는 다음 두 가지 용도로 사용 가능한 메모리가 사용됩니다.

1. $각{\displaystyle }$ k$\displaystyle$k 파티션의$$ 현재 출력 버퍼 페이지를 유지하려면
2. 파티션 전체를 메모리 내에 유지하려면 "파티션 0"이라고 합니다.

파티션 0은 디스크에 쓰거나 디스크에서 읽지 않기 때문에 하이브리드 해시 결합은 일반적으로 그레이스 해시 결합보다 적은 I/O 작업을 수행합니다.메모리에는 2개의 경쟁하는 요구가 있기 때문에(파티션0의 해시 테이블과 나머지 파티션의 출력 버퍼) 이 알고리즘은 메모리에 의존합니다.0이 아닌 파티션 중 하나가 너무 커서 메모리에 맞지 않기 때문에 해시 테이블을 너무 크게 선택하면 알고리즘이 반복될 수 있습니다.

해시 안티조인

해시 조인(Anti-join) 술어(다른 테이블에서 관련 값을 찾을 수 없는 경우 한 테이블에서 값을 선택하는 술어)에 대해서도 평가할 수 있습니다.테이블의 크기에 따라 다른 알고리즘을 적용할 수 있습니다.

해시 좌측 안티 조인

• 조인 NOT IN 측에 해시 테이블을 준비합니다.
• 다른 테이블을 스캔하여 Join 속성이 해시 테이블의 빈 엔트리에 해시되는 행을 선택합니다.

이것은 NOT IN 테이블이 FROM 테이블보다 작을 때 더 효율적입니다.

해시 우측 안티 조인

• 조인 FROM 측에 해시 테이블을 준비합니다.
• NOT IN 테이블을 스캔하여 각 해시 히트 시 해시 테이블에서 대응하는 레코드를 삭제합니다.
• 해시 테이블에 남아 있는 모든 항목을 반환합니다.

이것은 NOT IN 테이블이 FROM 테이블보다 클 때 더 효율적입니다.

해시 세미 조인

해시 세미 조인은 다른 테이블에 있는 레코드를 반환하는 데 사용됩니다.플레인 조인과는 달리 선두 테이블에서 일치하는 레코드는 1회만 반환되며 IN 테이블에 일치하는 레코드가 몇 개 있는지와는 무관합니다.

안티 조인(Anti-Join)과 마찬가지로 세미 조인(Semi-Join)도 좌우로 사용할 수 있습니다.

해시 좌측 세미 조인

• 조인 IN측의 해시 테이블을 준비합니다.
• 다른 테이블을 스캔하여 해시 히트를 생성하는 행을 반환합니다.

레코드는 히트곡을 낸 직후에 반환됩니다.해시 테이블의 실제 레코드는 무시됩니다.

이것은 IN 테이블이 FROM 테이블보다 작을 때 더 효율적입니다.

해시 우측 세미 조인

• 조인 FROM 측에 해시 테이블을 준비합니다.
• IN 테이블을 스캔하여 해시 테이블에서 대응하는 레코드를 반환하고 삭제합니다.

이 알고리즘에서는 해시 테이블(즉 FROM 테이블)의 각 레코드는 반환된 후 삭제되므로 1회만 반환할 수 있습니다.

이것은 IN 테이블이 FROM 테이블보다 클 때 더 효율적입니다.

「 」를 참조해 주세요.

• 대칭 해시 결합
• 중첩 루프 결합
• 정렬-병합

레퍼런스

외부 링크

• Hansjörg Zeller; Jim Gray (1990). "An Adaptive Hash Join Algorithm for Multiuser Environments" (PDF). Proceedings of the 16th VLDB conference. Brisbane: 186–197. Archived from the original (PDF) on 2012-03-11. Retrieved 2008-09-21.