해시 필터 링 알고리즘 (HF)

해시 필터 (Bloom 필터 라 고도 함) 는 열 이나 열 집중 값 의 분 포 를 나타 내 는 데이터 구조 입 니 다.해시 필 터 는 (긴) 비트 문자열 로 볼 수 있 습 니 다. 그 중 1 비트 지 시 는 특정한 줄 이 있 고 0 비트 지 시 는 이 위치 에 줄 이 없습니다.한 줄 의 값 을 필터 의 각 위치 에 분산 시 키 면 데이터베이스 서버 는 이 값 과 일치 하 는 줄 이 있 는 지 확인 할 수 있 습 니 다 (해시 충돌 이 있 을 수 있 습 니 다).

R<idx> *JH S<seq> JH* T<idx>

여기 서 R 을 S 와 T 에 연결 합 니 다.데이터베이스 서버 는 R 의 모든 줄 을 읽 은 다음 T 에서 임의의 줄 을 읽 습 니 다.해시 필터 가 색인 스 캔 으로 되 돌아 오 는 R 의 줄 로 구 축 된 경우 데이터베이스 서버 는 R 과 연결 할 수 없 는 T 의 줄 을 즉시 거부 할 수 있 습 니 다.이것 은 두 번 째 해시 연결 에 저장 해 야 할 줄 수 를 줄 일 것 이다.
해시 필 터 는 다음 조건 을 동시에 만족 시 키 는 조회 에서 사용 할 수 있 습 니 다.
4. 567917. 조회 에서 의 작업 은 다음 작업 이 줄 로 돌아 가기 전에 전체 입력 을 읽 습 니 다.예 를 들 어 한 열 에 있 는 두 표 의 해시 연결 은 그 중의 한 입력 에서 모든 관련 줄 을 읽 어서 연결 의 산 목록 을 구성 해 야 합 니 다
4. 567917. 방문 계획 의 후속 작업 을 조회 하면 이 작업 결과 의 줄 을 참조 합 니 다.예 를 들 어 첫 번 째 연결 이 열 에 있 는 다른 연결 은 첫 번 째 연결 을 만족 시 키 는 줄 만 사용 합 니 다
이러한 상황 에서 첫 번 째 연결 결과 로 구 축 된 해시 필 터 는 두 번 째 연결 의 성능 을 현저히 향상 시 킬 수 있다.그 실현 방법 은 해시 필터 의 비트 문자열 에서 예비 조회 작업 을 수행 하여 첫 번 째 연결 이 이전에 어떤 줄 을 성공 적 으로 처 리 했 는 지 확인 하 는 것 입 니 다. 만약 에 이런 줄 이 존재 하지 않 는 다 면 두 번 째 연결 로 산 목록 탐 사 를 하 는 것 을 완전히 피 할 수 있 습 니 다. 해시 필터 에 1 자리 가 존재 하지 않 으 면 탐지 가 일치 하 는 항목 을 만 들 수 없 기 때 문 입 니 다.