해시 조인
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
해시 조인은 데이터베이스에서 두 개 이상의 테이블을 조인하는 데 사용되는 알고리즘으로, 내부 조인, 안티 조인, 세미 조인 등 다양한 유형이 있다. 클래식 해시 조인은 작은 관계를 기반으로 해시 테이블을 생성하고, 큰 관계를 스캔하여 일치하는 로우를 찾는 방식으로 작동한다. 그레이스 해시 조인은 해시 함수를 사용하여 관계를 여러 파티션으로 분할하고 재귀적으로 처리하며, 하이브리드 해시 조인은 그레이스 해시 조인과 고전적인 해시 조인을 결합하여 메모리 사용을 최적화한다. 해시 안티-조인과 해시 세미-조인은 특정 조건에 따라 데이터를 선택하는 데 사용되며, 왼쪽과 오른쪽으로 구분된다.
더 읽어볼만한 페이지
- 데이터베이스 알고리즘 - ARIES
ARIES는 로깅, DPT, TT 등의 자료 구조와 로그 레코드를 활용하여 데이터베이스 무결성을 보장하고, 장애 발생 시 로그 분석, 재실행, 실행 취소 단계를 통해 데이터베이스를 복구하는 기술이다. - 데이터베이스 알고리즘 - 로그 선행 기입
로그 선행 기입(WAL)은 데이터베이스 시스템에서 데이터 일관성, 충돌 안전성 및 안정성을 보장하는 기술로, 데이터 변경 사항을 디스크에 기록하기 전에 로그 파일에 먼저 기록하여 시스템 장애 시 데이터 손실을 최소화한다. - 해싱 - 해시 충돌
해시 충돌은 해시 함수에서 서로 다른 입력값이 동일한 해시값을 생성하는 현상으로, 데이터 수와 해시 값 범위에 따라 발생 가능성이 높아지며 데이터 무결성 및 보안 상의 문제점을 야기하여 해결 방법이 연구되고 있다. - 해싱 - HMAC
HMAC(Keyed-Hash Message Authentication Code)는 공유된 비밀 키와 암호화 해시 함수를 사용하여 메시지의 무결성을 검증하는 메시지 인증 코드로서, IPsec, SSH, TLS, JSON 웹 토큰 등 다양한 보안 프로토콜에서 활용된다.
| 해시 조인 |
|---|
2. 클래식 해시 조인(Classic hash join)
클래식 해시 조인은 내부 조인을 위한 가장 기본적인 해시 조인 알고리즘이다. 이 알고리즘은 먼저 작은 관계(테이블)를 기반으로 해시 테이블을 생성한다. 해시 테이블의 항목은 조인 속성과 해당 행 전체로 구성된다. 해시 함수를 통해 조인 속성에 빠르게 접근할 수 있어, 일반적인 검색보다 훨씬 빠르게 원하는 행을 찾을 수 있다. 해시 테이블이 생성되면, 더 큰 관계를 스캔하면서 해시 테이블에서 관련 있는 행을 찾는다.
이 과정에서 첫 번째 단계를 "빌드" 단계, 두 번째 단계를 "탐색" 단계라고 부른다. 해시 테이블을 만드는 데 사용되는 작은 관계를 "빌드" 입력, 다른 관계를 "탐색" 입력이라고 한다. 이는 합병 조인과 유사하다.
2. 1. 작동 방식
클래식 해시 조인은 두 관계에 대한 내부 조인을 위해 사용되는 알고리즘이며, 다음과 같이 작동한다.- 먼저, 작은 관계(테이블)를 기반으로 해시 테이블을 준비한다. 해시 테이블의 각 항목은 조인 속성과 해당 행 전체로 구성된다. 해시 함수를 통해 조인 속성에 빠르게 접근할 수 있으므로, 일반적인 검색보다 훨씬 빠르게 원하는 행을 찾을 수 있다.
- 해시 테이블이 준비되면, 더 큰 관계를 스캔하면서 해시 테이블에서 관련 있는 행을 찾는다.
이 과정에서 첫 번째 단계를 "빌드" 단계, 두 번째 단계를 "탐색" 단계라고 부른다. 해시 테이블을 만드는 데 사용되는 작은 관계를 "빌드" 입력, 다른 관계를 "탐색" 입력이라고 한다. 이는 합병 조인과 유사하다.
하지만, 작은 관계가 메모리보다 큰 경우(자주 발생하지는 않지만)에는 추가적인 과정이 필요하다.
1. 빌드 입력의 각 튜플(행)에 대해:
1. 튜플을 메모리 내 해시 테이블에 추가한다.
2. 해시 테이블 크기가 메모리 한계에 도달하면:
1. 탐색 입력을 스캔하여 일치하는 조인 튜플을 결과에 추가한다.
2. 해시 테이블을 초기화한다.
2. 탐색 입력에 대해 최종 스캔을 수행하여 남은 조인 튜플을 결과에 추가한다.
이 과정은 블록 중첩 루프 조인 알고리즘과 유사하며, 탐색 입력을 여러 번 스캔해야 할 수도 있다.
2. 2. 메모리 제한 처리
작은 테이블이 메모리에 들어가지 않을 경우, 블록 중첩 루프 조인과 유사한 방식으로 처리한다. 이 방법은 다음과 같이 진행된다.:1. 빌드 입력 의 각 튜플 에 대해
::1-1. 을 메모리 내의 해시 테이블에 추가한다.
::1-2. 만약 해시 테이블의 사이즈가 메모리의 크기 한계와 같다면
:::1-2-1. 탐색 인풋 를 스캔하고, 매칭된 조인 튜플들을 아웃풋 관계에 추가한다.
:::1-2-2. 해시 테이블을 리셋한다
:2. 탐색 인풋 에 대해 최종 스캔을 진행하고 남은 나머지 조인 튜플들을 아웃풋 관계에 추가한다.
이 과정은 블록 중첩 루프 조인 알고리즘과 거의 흡사하다. 하지만 이 알고리즘은 를 필요 이상으로 여러 번 스캔해야 할 수도 있다.
3. 그레이스 해시 조인(Grace hash join)
'''그레이스 해시 조인'''(en)은 GRACE 데이터베이스 머신에 처음 구현된 알고리즘이다. 해시 함수를 이용하여 관계 와 양쪽을 여러 파티션으로 분할하고, 이러한 파티션들을 디스크에 기록하여 관계 전체를 다시 스캔하는 과정을 회피한다. 그런 다음 파티션 쌍을 메모리에 로드하고, 작은 관계에 대한 해시 테이블을 생성한 후, 현재 해시 테이블과 일치하는 다른 관계를 탐색한다. 파티션은 조인 키를 해싱하여 형성되므로, 조인 출력 튜플은 반드시 동일한 파티션에 속해야 한다.
3. 1. 작동 방식
해시 조인은 다음 두 단계로 작동한다.1. 파티션 단계: 해시 함수를 사용하여 두 관계(테이블) 과 를 여러 파티션으로 분할하고 디스크에 기록한다.
2. 조인 단계: 파티션 쌍을 메모리에 로드하고, 작은 관계에 대한 해시 테이블을 생성한 다음, 큰 관계를 탐색하여 현재 해시 테이블과 일치하는 레코드를 찾는다.
파티션은 조인 키를 기반으로 생성되므로, 조인 결과는 반드시 같은 파티션에 속하게 된다.
만약 하나 이상의 파티션이 메모리에 맞지 않는 경우, 알고리즘은 재귀적으로 적용된다. 즉, 더 큰 파티션을 하위 파티션으로 다시 해싱하기 위해 다른 해시 함수를 선택하고 이전과 동일한 방식으로 처리한다. 이 과정은 비용이 많이 들기 때문에, 알고리즘은 초기 파티션 단계에서 가능한 한 많은 파티션을 생성하여 이러한 상황을 최소화하려고 한다.
3. 2. 재귀적 처리
"그레이스 해시 조인"에서 하나 이상의 파티션이 사용 가능한 메모리에 여전히 맞지 않는 경우가 발생할 수 있는데, 이 경우 알고리즘은 재귀적으로 적용된다. 추가적인 해시 함수를 선택하여 큰 파티션을 하위 파티션으로 해싱한 다음, 이전과 동일하게 처리한다. 이는 비용이 많이 들기 때문에, 알고리즘은 초기 파티션 단계에서 가능한 한 많은 파티션을 형성하여 이러한 상황이 발생할 가능성을 줄이려고 시도한다.4. 하이브리드 해시 조인(Hybrid hash join)
하이브리드 해시 조인[1][2]은 클래식 해시 조인과 그레이스 해시 조인의 장점을 결합한 알고리즘이다. 그레이스 해시 조인처럼 분할에 최소한의 메모리를 사용하고, 나머지 메모리는 분할 단계에서 고전적인 해시 조인을 초기화하는 데 사용한다.
메모리 사용을 개선하여 파티션 0은 디스크에서 읽거나 쓰지 않으므로, 일반적으로 그레이스 해시 조인보다 디스크 I/O 횟수가 적다. 관계가 메모리에 거의 완전히 맞으면 고전적인 해시 조인과 유사하게 동작하고, 그렇지 않으면 그레이스 해시 조인을 모방한다.
4. 1. 작동 방식
하이브리드 해시 조인 알고리즘[2]은 그레이스 해시 조인을 개선하여 메모리 사용 효율을 높인 알고리즘이다. 파티셔닝 단계에서 하이브리드 해시 조인은 추가 메모리를 다음과 같이 두 가지 방식으로 활용한다.# 각 파티션들의 현재 결과에 대한 버퍼용 페이지를 저장한다.
# "파티션 0"이라고 불리는 모든 파티션들에 대한 정보를 메모리에 저장한다.
파티션 0은 디스크에서 읽거나 쓰지 않으므로, 하이브리드 해시 조인은 일반적으로 그레이스 해시 조인보다 디스크 I/O 횟수가 적다.[2] 이 알고리즘은 메모리 상태에 민감한데, 파티션 0을 위한 해시 테이블과 나머지 파티션 조각들의 결과를 저장하기 위한 공간이라는 두 가지 경쟁적인 메모리 사용 요구가 있기 때문이다. 너무 큰 크기의 해시 테이블을 선택하면 알고리즘이 재귀될 수 있는데, 이는 파티션 0이 아닌 파티션 조각 중 하나가 메모리에 들어가기에 너무 커질 수 있기 때문이다.[2]
하이브리드 해시 조인 알고리즘[1]은 고전적인 해시 조인과 그레이스 해시 조인을 결합한 방식이다. 그레이스 해시 조인처럼 분할에 최소한의 메모리를 사용하고, 나머지 메모리는 분할 단계에서 고전적인 해시 조인을 초기화하는 데 사용한다. 분할 단계에서 하이브리드 해시 조인은 사용 가능한 메모리를 다음 두 가지 목적으로 사용한다.[1]
# 두 관계를 분할한다.
# "분할 0"이라고 알려진 관계의 전체 분할을 메모리에 보관한다.
분할 0은 디스크에 기록되지 않으므로, 하이브리드 해시 조인은 일반적으로 그레이스 해시 조인보다 더 적은 I/O 작업을 수행한다. 관계가 메모리에 거의 완전히 맞는 경우, 하이브리드 해시 조인은 더 유리한 고전적인 해시 조인과 유사하게 동작한다. 그렇지 않으면 하이브리드 해시 조인은 그레이스 해시 조인을 모방한다.[1]
이 알고리즘은 메모리에 민감하다는 점에 유의해야 한다. 메모리에 대한 두 가지 상반된 요구 사항(분할 0에 대한 해시 테이블과 나머지 분할에 대한 출력 버퍼)이 있기 때문이다. 분할 0에 대해 너무 큰 해시 테이블을 선택하면 0이 아닌 분할 중 하나가 메모리에 맞지 않아 알고리즘이 재귀될 수 있다.[1]
4. 2. 메모리 민감성
하이브리드 해시 조인 알고리즘은 메모리 상태에 민감하다.[2] 파티션 0에 대한 해시 테이블과 나머지 파티션 조각들의 결과를 저장하기 위한 용도로 메모리를 사용하는데, 이 두 가지 요구 사항이 서로 상충하기 때문이다. 너무 큰 크기의 해시 테이블을 선택하면 파티션 0이 아닌 파티션 조각 중 하나가 메모리에 들어갈 수 없을 정도로 커져 알고리즘이 재귀될 수 있다.[2]5. 해시 안티-조인(Hash anti-join)
해시 안티-조인은 한 테이블에는 존재하지만 다른 테이블에는 존재하지 않는 레코드를 찾는 데 사용되는 조인 방식이다. 해시 조인은 다른 테이블에서 관련 값을 찾을 수 없을 때 한 테이블에서 값을 선택하는 반 결합 조건에도 사용할 수 있다. 테이블 크기에 따라 다른 알고리즘이 적용될 수 있다.[1]
5. 1. 해시 LEFT 안티-조인(Hash left anti-join)
해시 조인은 안티-조인의 술어부에 대해서도 유용하게 사용된다. 술어부는 한 테이블에서 다른 출력값과 관계가 없는 값들을 찾아내는 용도로 사용하는 값이다. 테이블 크기에 따라 다른 알고리즘이 적용될 수 있다.- "NOT IN" 쪽에 해당하는 작은 테이블로 해시 테이블을 준비한다.
- 다른 테이블을 스캔하면서, 조인 특성의 해시 값이 해시 테이블에 없는 로우(레코드)들을 선택한다.
이것은 "NOT IN"의 테이블이 조인하려는 테이블보다 더 작을 때 좀 더 유용하다.
5. 2. 해시 RIGHT 안티-조인(Hash right anti-join)
먼저, 조인할 테이블을 바탕으로 해시 테이블을 만든다. 그 다음, 'NOT IN'에 해당하는 테이블을 훑어보면서 해시 테이블에서 같은 레코드를 지운다. 이 과정을 마치면 해시 테이블에 남아 있는 레코드들이 결과값이 된다.이 방법은 'NOT IN' 테이블이 조인 대상 테이블보다 더 클 때 효율이 좋다.
6. 해시 세미-조인(Hash semi-join)
해시 세미-조인은 다른 테이블에서 발견된 레코드를 반환하는 데 사용된다. 일반 조인과 달리, 'IN' 테이블에 일치하는 항목이 여러 개 있더라도 선행 테이블에서 일치하는 각 레코드를 한 번만 반환한다. 안티 조인과 마찬가지로 세미 조인도 왼쪽과 오른쪽으로 나눌 수 있다.[1]
6. 1. 해시 LEFT 세미-조인(Hash left semi-join)
해시 LEFT 세미-조인은 'IN' 쪽에 해당하는 작은 테이블로 해시 테이블을 생성하고, 다른 테이블을 스캔하면서 해시 테이블에 존재하는 레코드를 반환하는 방식이다. 이 방식은 조인 대상 테이블보다 'IN' 쪽에 해당하는 테이블이 더 작을 때 효율적이다.[1]해시 세미-조인은 다음과 같이 동작한다.[1]
- 조인의 'IN' 쪽에 해당하는 테이블로 해시 테이블을 만든다.
- 다른 쪽 테이블을 스캔하면서 해시 테이블에서 일치하는 레코드를 찾는다.
- 해시 테이블에서 일치하는 레코드를 찾으면 즉시 반환한다. 이때 해시 테이블 자체의 레코드는 무시한다.
6. 2. 해시 RIGHT 세미-조인(Hash right semi-join)
먼저 조인할 쪽에 해당하는 테이블로 해시 테이블을 만든다.[1] 그런 다음, "IN" 테이블을 훑어보면서 해시 테이블에서 일치하는 행을 찾아 반환하고, 찾은 행은 해시 테이블에서 제거한다.[1]이 방법을 사용하면, 해시 테이블(조인할 쪽 테이블로 만든)의 각 행은 한 번만 반환되고 제거되므로, 결과적으로 한 번만 반환된다.[1] 이 방법은 "IN" 테이블이 조인할 쪽 테이블보다 클 때 더 효과적이다.[1]
참조
[1]
논문
Implementation techniques for main memory database systems
1984-06
[2]
저널
Implementation techniques for main memory database systems
1984-06
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com