[MySQL] Hash 인덱스

해시(Hash) 인덱스

---

해시 인덱스는 B-Tree만큼 범용적이지 않지만 고유의 특성과 용도를 지닌 인덱스 가운데 하나입니다. 해시 인덱스는 동등 비교 검색에는 최적화돼 있지만 범위를 검색한다거나 정렬된 결과를 가져오는 목적으로는 사용할 수 없습니다. 일반적인 DBMS에서 해시 인덱스는 메모리 기반의 테이블에 주로 구현돼 있으며 디스크 기반의 대용량 테이블용으로는 거의 사용되지 않는다는 특징이 있습니다. 해시 인덱스 알고리즘은 테이블의 인덱스뿐 아니라 InnoDB의 버퍼 풀에서 빠른 레코드 검색을 위한 어댑티브 해시 인덱스(Adaptive Hash Index)로 사용되기도 하고, 오라클과 같은 DBMS에서는 조인에 사용되기도 합니다. 해시 인덱스는 주로 메모리 기반의 테이블에서 주로 사용되지만 기본적인 특성은 반드시 알아두는 것이 좋습니다.

구조 및 특성

해시 인덱스의 큰 장점은 실제 키값과는 관계없이 인덱스 크기가 작고 검색이 빠르다는 것입니다. 위의 그림에서 보는 것처럼 해시 인덱스는 트리 형태의 구조가 아니므로 검색하고자 하는 값을 주면 해시 함수를 거쳐서 찾고자 하는 키값이 포함된 버켓을 알아낼 수 있습니다. 그리고 그 버켓 하나만 읽어서 비교해보면 실제 레코드가 저장된 위치를 바로 알 수 있습니다. 그래서 트리 내에서 여러 노드를 읽어야 하지만 레코드의 주소를 알아 낼 수 있는 B-Tree보다 상당히 빨리 결과를 가져올 수 있습니다.

B-Tree 인덱스나 해시 인덱스 모두 각 키값과 레코드 주소값 등의 정보를 저장해 두는 공간이 필요합니다. 일반적으로 이 저장 공간은 작업의 기본 단위가 되며 고정된 크기로 할당됩니다. B-Tree에서는 이처럼 고정된 크기의 저장 공간을 노드라고 하며, 해시 인덱스에서는 이를 버켓이라고 합니다. 버켓은 크게 중요한 개념은 아니므로 키 값이 저장된 단위 크기의 메모리 공간으로 이해하면 됩니다.

또한 해시 인덱스는 원래의 키값을 저장하는 것이 아니라 해시 함수의 결과(일반적으로는 단순 숫자값)만을 저장하므로 키 컬럼의 값이 아무리 길어도 실제 해시 인덱스에 저장되는 값은 4~8바이트 수준으로 상당히 줄어듭니다. 그래서 해시 인덱스는 B-Tree 인덱스보다는 상당히 크기가 작은 편입니다.

해시 인덱스에서 가장 중요한 것은 해시 함수로, 입력된 키값이 어디에 저장될지를 결정하는 함수입니다. 해시 함수의 결과 값의 범위가 넓으면 그만큼 버켓이 많이 필요해져서 공간의 낭비가 커지고, 값의 범위가 너무 작으면 충돌되는 경우가 너무 많이 발생해 해시 인덱스의 장점이 사라집니다. 여기서 충돌이라 함은 입력 값은 다르지만 해시 함수의 결과 값이 같은 경우를 의미합니다.

해시 함수 F(value) = CRC32(value) % 10

F('Banette') = 7
F('Aamer') = 9
F('Jaana') = 9
...

CRC16이라는 함수의 결과 값을 10으로 나눈 결과 나머지 값을 취하는 것으로 해시 함수를 정의했다고 해봅시다. 위의 예제에서 "Jaana"와 "Aamer"는 입력 값은 다르지만 결과 값은 똑같이 9라는 것을 알 수 있습니다. 이렇게 입력 값은 다르지만 해시 값이 같은 경우를 "충돌"이라고 표현합니다. 해시 함수 결과 값의 범위가 좁으면 필요한 버켓의 개수가 적어지지만 충돌이 많이 발생합니다. 반대로 해시 함수 결과 값의 범위가 넓으면 버켓의 개수가 많이 필요하지만 충돌이 줄어듭니다. 검색을 위한 해시 인덱스에서는 충돌이 많이 발생하면 할수록 검색의 효율이 떨어집니다.

위의 예제에서 "Banette"를 검색하는 경우는 해시 값이 7인 것을 검색하므로 1건만 일치하지만, "Aamer"를 검색하는 경우에는 해시 값이 9인 것을 검색하므로 2건이 일치합니다. 하지만 후자는 실제로 값이 "Aamer"가 아닌 경우("Jaana")가 포함돼 있어서 필터링 과정이 필요하며 자연히 검색 성능은 느려집니다.

해시 알고리즘은 여러 가지 목적으로 사용될 수 있지만 DBMS에서는 대표적으로 검색을 위한 인덱스와 테이블의 파티셔닝 용도로 사용됩니다. 검색을 위해 해시 알고리즘이 사용되는 경우에는 해시 함수의 결과 값이 범위가 넓어야 충돌이 줄어들고 그만큼 검색 성능이 높아집니다. 하지만 테이블 파티셔닝 용도로 사용되는 경우에는 해시 함수가 필요한 파티션의 개수만큼만 만들어내도록 설계해야 하므로 해시 함수의 결과 값의 범위를 좁게 사용합니다. MySQL의 해시 파티션은 이러한 해시 알고리즘을 이용해 테이블을 파티셔닝하는 기능입니다. 

MEMORY 스토리지 엔진이나 NDB 클러스터와 같이 해시 인덱스를 지원하는 스토리지 엔진에서는 이미 해시 함수를 내장하고 있는 모든 처리를 자동으로 해주기 때문에 실제 사용자가 해시 함수를 생성하거나 개발해야 하는 것은 아닙니다. 하지만 가끔 해시 인덱스를 지원하지 않는  InnoDB 스토리지 엔진에서 해시 인덱스처럼 작동하도록 테이블을 만들어야 할 때도 있습니다. 인위적인 해시 함수를 이용해 B-Tree 인덱스를 해시 인덱스처럼 작동하도록 구현하는 것이 가능하기도 합니다.

해시 인덱스의 가용성 및 효율성

해시 인덱스는 빠른 검색을 제공하지만 키값 자체가 변환되어 저장되기 때문에 범위를 검색하거나 원본값 기준으로 정렬할 수 없습니다. 해시 인덱스는 이렇게 원본 키값이 변환되어 저장되기 때문에 B-Tree와는 달리 어떤 방식으로도 해시 인덱스를 사용하지 못하는 경우도 발생합니다.

작업 범위 제한 조건으로 해시 인덱스를 사용하는 쿼리

다음 패턴의 쿼리는 동등 비교 조건으로 값을 검색하고 있으므로 해시 인덱스의 빠른 장점을 그대로 이용할 수 있습니다. IN 연산자도 결국 여러 개의 동등 비교로 풀어서 처리할 수 있기 때문에 같은 효과를 얻을 수 있습니다.

SELECT ... FROM tb_hash WHERE column = '검색어';
SELECT ... FROM tb_hash WHERE column <=> '검색어';
SELECT ... FROM tb_hash WHERE column IN ('검색어1', '검색어2');
SELECT ... FROM tb_hash WHERE column IS NULL;
SELECT ... FROM tb_hash WHERE column IS NOT NULL;

"<=>"는 "NULL-Safe Equal" 연산자라고 하는데, 비교 양쪽의 값이 NULL이 있을 때를 제외하고는 "=" 연산자와 똑같습니다.

해시 인덱스를 전혀 사용하지 못하는 쿼리

아래와 같은 형태의 크다 또는 작다 기반의 검색은 어떠한 방법으로도 해시 인덱스를 사용할 수 없습니다. 즉 작업 범위 결정 조건뿐 아니라 체크 조건의 용도로도 전혀 사용할 수 없습니다. 대체로 범위 비교나 부정형 비교는 해시 인덱스를 사용할 수 없습니다.

SELECT ... FROM tb_hash WHERE column >= '검색어';
SELECT ... FROM tb_hash WHERE column BETWEEN 100 AND 120;
SELECT ... FROM tb_hash WHERE column LIKE '검색어%';
SELECT ... FROM tb_hash WHERE column <> '검색어';

해시 인덱스에서 하나 더 꼭 기억해야 할 주의사항이 있습니다. 다중 컬럼으로 생성된 해시 인덱스에서도 모든 컬럼이 동등 조건으로 비교되는 경우에만 인덱스를 사용할 수 있다는 점입니다. 아래와 같이 member_id 컬럼과 session_id 컬럼을 결합한 해시 인덱스를 가진 tb_session이 있을 때, 이 테이블에 member_id만 동등 조건으로 비교되는 경우에는 ix_memberid_sessionid 인덱스를 사용할 수 없습니다. 많이 실수하는 부분이므로 기억해두는 것이 좋습니다.

CREATE TABLE tb_session (
    session_id BIGINT NOT NULL,
    member_id CHAR(20) NOT NULL,
    ...
    INDEX ix_memberid_sessionid (member_id, session_id)
) ENGINE=MEMORY;

SELECT * FROM tb_session WHERE member_id='user_nickname';

MEMORY 스토리지 엔진에서는 특별히 인덱스의 알고리즘을 명시하지 않으면 기본적으로 해시 인덱스가 적용됩니다. 인덱스에 대한 자세한 내용은 "SHOW INDEX FROM tb_session" 명령으로 확인할 수 있습니다.

출처: https://12bme.tistory.com/141?category=682920 [길은 가면, 뒤에 있다.]