In-memory optimized table에 사용되는 Hash Index

·         Version : SQL Server 2014 later

SQL Server에서 새롭게 추가된 Hash Index(해시 인덱스)는  In-Memory optimized table(인메모리 최적화 테이블)에서 사용된다. 기본적으로 테이블의 행을 빠르게 찾고 읽으려면 인덱스가 필요하다.

해시 인덱스는 버킷의 컬렉션은 배열(Array) 구성된다. 해시 함수는 인덱스 키를 해시 인덱스의 해당 버킷으로 매핑한다. 아래 그림은 세 개의 인덱스가 해시 함수를 사용하여 해시 인덱스에 있는 세 개의 서로 다른 버킷에 매핑되는것을 나타낸다. 아래 그림에서 해시 함수 이름은 f(x)이다.

해시 인덱스에 사용되는 해시 함수의 특징은 아래와 같다.

·         SQL Server에는 모든 해시 인덱스에 사용되는 하나의 해시 함수가 있다.

·         해시 함수는 결정적이다. 동일한 인덱스 키는 항상 해시 인덱스의 동일한 버킷에 매핑된다.

·         여러 인덱스 키는 동일한 해시 버킷에 매핑할 수 있다.

·         해시 함수는 균형을 이룬다. 즉, 해시 버킷에 대한 인덱스 키값의 분포는 일반적으로 포아송 분포를 따른다.

포아송 분포는 균등한 분포가 아니다. 인덱스 키 값은 해시 버킷에 균등하게 분포되지 않는다. 예를 들어 n개의 해시 버킷에 대한 n개의 고유인덱스 키의 포아송 분포는 버킷을 대략적으로 삼등분 한다. 삼등분된 버킷 부분에는 공백, 하나의 인덱스 키, 두 개의 인덱스 키가 각각 포함된다. 소수의 버킷에 세 개이상의 키가 포함된다. 두개의 인덱스 키가 동일한 해시 버킷에 매핑되면 해시 충돌(Collision)이 발생한다.  많은 숫자의 해시 충돌은 읽기 작업의 성능에 영향을 준다.

인메모리 해시 인덱스 구조는 메모리 포인터의 배열로 구성된다. 각 버킷은 이 배열의 오프셋에 매핑된다. 배열의 각 버킷은 해당 해시 버킷의 첫 번째 행을 가리킨다. 버킷의 각 행은 그 다음 행을 가리키기 때문에 다음 그림과 같이 각 해시 버킷에 대한 행 체인이 만들어 진다. 아래 그림은 행이 포함된 세 개의 버킷이 있다.

맨 위에서 두번째 버킷에는 세 개의 빨간색 행이 포함된다. 네 번째 버킷에는 하나의 파란색 행이 포함된다. 맨 아래 버킷에는 두 개의 녹색 행이 포함된다. 이러한 행동은 동일한 행의 서로 다른 버전일 수 있다.

[참고자료]

https://docs.microsoft.com/en-us/sql/database-engine/hash-indexes?view=sql-server-2014

2018-08-29 / Sungwook Kang / http://sqlmvp.kr

SQL Server, MSSQL, Hash Index, 해시 인덱스, 인모메리 최적화 테이블, In-memory optimized table