MySQL Hash Index

Last Updated on 1월 14, 2021 by 태랑(정현호)



1. MySQL Hash Index



Hash index 는 B-tree 만큼 일반적/범용적으로 사용되지는 않지만 고유의 기능과 특성을 가지고 있는 인덱스 오브젝트 입니다. Hash index 는 동등(equal =) 비교 검색시 사용 및 최적화 되어 있으며 범위나 FullText Search 나 정렬된 결과를 가져오는 목적으로는 사용할 수는 없습니다.

Hash index 는Memory ,NDB Storage Engine 에서 사용 할 수 있으며, Memory Engine 에서 테이블 생성시 Hash Index 가 Default Index 로 생성 됩니다. Hash index 에서 사용되는 알고리즘은 파티션 테이블(HASH) 나 InnoDB 버퍼풀의 Adaptive Hash Index 에도 사용됩니다.

[참고1] 포스팅에서 언급하는 Hash Index 와 Adaptive Hash Index 는 다른 종류 입니다.

[참고2] Memory Engine
Memory Engine 은 메모리에 데이터를 저장하는 엔진이며 MyISAM 과 같이 Transaction을 지원하지 않고, table-level locking 이 사용됩니다 메모리를 사용하기 때문에 처리 속도가 아주 빠르지만 메모리에 데이터를 사용하기 때문에 MySQL의 재시작 등으로 잃어버릴 위험이 있기 때문에 영구적으로 저장하는 데이터가 아닌 빠른 처리가 필요한 임시 테이블로 많이 사용합니다.

Memory Engine의 테이블은 테이블당 64개의 인덱스가 가능하며, 인덱스 당 16컬럼을 포함 가능하며 , 키의 길이는 최대 3072 byte 까지 가능 합니다.




2. Hash Index 의 장점



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

B-Tree Index 에서 고정된 크기의 저장 공간을 노드 라고 하며 Hash index 에서는 버켓이라고 하며 키 값이 저장된 단위 크기의 메모리 공간 입니다.

Hash index 는 원래의 값을 저장하는 것이 아닌 해시 함수의 결과만을 저장하게 됨에 따라 키 컬럼 값은 4~8바이트 정도로 작은 길이로 줄어 들게 되고 B-Tree 인덱스에 비해 상당히 작은 크기 입니다.

Hash index 에서 중요한것은 해시 함수이며 입력된 키값이 어디에 저장이 될지를 결정하게 되는 함수 입니다 입력한 값이 다르지만 해시된 값이 같을 경우 해시 충돌 이라고 표현하고 해시 함수의 결과 값의 범위가 좁으면 필요한 버켓의 개수가 적어지게 되면서 충돌할수 있는 확율이 높게 됩니다. Hash index 에서 충돌이 많이 발생 될 수록 검색 효율이 떨어지게 됩니다.

Memoy 나 NDB Engine에서 지원하는 Hash index 는 스토리지 엔진 영역에서 이미 해시 함수를 내장하고 있으며 처리를 해주기 때문에 별도의 사용자가 해시함수를 사용한다던가 함수나 추가 개발등을 하지 않아도 됩니다.




3. 해시 인덱스의 효율 및 사용성



1. 비교 연산자

해시 인덱스 는 빠른 검색을 지원(제공) 하지만 키값이 해시 화 되어서 저장되기 때문에 범위 검색이나 FullText 나 정렬 등은 할수 없습니다 그래서 B-Tree 인덱스에 비해서 사용하는 조건에서 동등(equal =) 비교 검색을 사용해야 하는 차이를 보이게 됩니다

• 해시 인덱스 사용 가능 비교 연산자
 WHERE  = 'Search' , <=> 'Search' ,
               IN('Search1','Search2') , IS NULL, IS NOT NULL

•해시 인덱스 사용불가 바교 연산자로
 WHERE  >= 'Search', between Search and Search ,
                      LIKE 'Search%', <> 'Search'



2. 다중 컬럼

해시 인덱스 사용시 다중 컬럼의 경우 where 절에 모든 컬럼이 동등 조건으로 비교되는 경우에만 사용이 가능 한것으로 확인 됩니다

Hash Index Characteristics


Only whole keys can be used to search for a row.


2.1 테스트 테이블 생성

mysql> CREATE TABLE tb_test(
ip_host varchar(100),
agent varchar(100),
..
..
Index ix_test_01(ip_host,agent) using HASH
) EGINE=MEMORY;

mysql> select *
from tb_test where ip_host='123.123.123.11';
<--!!


2.2 Plan

테스트 해보면 모든 조건을 비교하지 않을 경우, 즉 선두컬럼 만 조건 또는 후행 컬럼 만 조건이 있을 경우 Full Scan 으로 수행되는 것이 확인 됩니다.


• 인덱스 컬럼에 해당하는 모든 조건 비교
mysql> explain
select * from tb_test
where ip_host='123.123.123.11' and agent='IE7'\G

**************** 1. row ****************
id: 1
select_type: SIMPLE
table: tb_test
partitions: NULL
type: ref
possible_keys: ix_test_01
key: ix_test_01
key_len: 806
ref: const,const
rows: 3
filtered: 100.00
Extra: NULL
1 row in set, 1 warning (0.00 sec)


• 인덱스 컬럼중 후행 컬럼 만 비교
mysql> explain

select * from tb_test where agent='IE7'\G
**************** 1. row ****************
id: 1
select_type: SIMPLE
table: tb_test
partitions: NULL
type: ALL
possible_keys: NULL
key: NULL
key_len: NULL
ref: NULL
rows: 6
filtered: 16.67
Extra: Using where
1 row in set, 1 warning (0.00 sec)


• 인덱스 컬럼중 선행 컬럼 만 비교
mysql> explain
select * from tb_test
where ip_host='123.123.123.11'\G

**************** 1. row ****************
id: 1
select_type: SIMPLE
table: tb_test
partitions: NULL
type: ALL
possible_keys: ix_test_01
key: NULL
key_len: NULL
ref: NULL
rows: 6
filtered: 16.67
Extra: Using where
1 row in set, 1 warning (0.00 sec)



3. InnoDB에서 Hash Index



위에서 Memory,NDB 는 스트로지 엔진의 내장 해시함수에 의해서 사용자의 별도 구현 없이 처리 된다고 언급 하였습니다 InnoDB 스토리지 엔진에서는 기본적으로 기존적으로 지원하지 않지만 
사용을 하려고 할 경우 해시 인덱스 처럼 동작 할수 있도록 데이터 입력을 하여 사용할 수 있습니다.

해시를 할때 사용할 알고리즘을 선택 해야하며 CRC32() 함수는 4바이트로 해시값을 만들어내기 때문에 해시 충돌의 발성 가능성이 높으며 그래서 MD5나 SHA 와 같은 함수를 사용하면 됩니다.

- MD5 16bytes ,  SHA 20bytes



• 테스트 테이블 생성

mysql> CREATE TABLE tb_test(
id int not null auto_increment,
host_ip varchar(100),
agent varchar(100),
url_addr varchar(100),
url_addr_hash CHAR(32),
url_ref varchar(100),
PRIMARY KEY(id),
index ix_test_01(url_addr_hash)
) ENGINE=InnoDB;


• 쿼리 사용시

- Insert 나 Selct 시

아래와 같이 Hash 함수를 이용하여 쿼리를 수행 합니다.
mysql> INSERT INTO tb_test(url_addr,url_addr_hash)
values('htts://hoing.io',MD5('htts://hoing.io'));

mysql> COMMIT;

- 데이터 조회시
mysql> select * from tb_test\G
**************** 1. row ****************
id: 1
host_ip: NULL
agent: NULL
url_addr: htts://hoing.io
url_addr_hash: d5cc2ce10a79bc9a0bd9dd09ed63124c
url_ref: NULL
1 row in set (0.00 sec)

- WHERE 절 비교하여 조회시
mysql> select * from tb_test
where url_addr_hash=md5('htts://hoing.io')\G
**************** 1. row ****************
id: 1
host_ip: NULL
agent: NULL
url_addr: htts://hoing.io
url_addr_hash: d5cc2ce10a79bc9a0bd9dd09ed63124c
url_ref: NULL
1 row in set (0.00 sec)


여기에서 컬럼의 저장 공간을 더 줄이고자 한다면 바이너리 값으로 저장하게 되면 디스크 공간을 MD5의 16bytes만 필요하게 됩니다.




4. conclusion



정리하면 Memoy,NDB Storage 에서는 스토리지 엔진에서의 내장 해시 함수를 이용하여 Hash Index 를 사용할 수 있으며 동등 조건시 B-Tree index 에 비해 더 빠르게 조회할 수 있는 기능 입니다.

또한 InnoDB에서 Hash를 사용하여 저장하면 긴 Text String도 Hash로 적은 공간을 차지 하면서 빠르게 동등조건으로 검색 할 수 있게 됩니다.



Ref book - Real MySQL
Ref link
dev.mysql.com/index-btree-hash
dev.mysql.com/mysql-indexes.html
dev.mysql.com/memory-storage-engine.html
dev.mysql.com/storage-engines.html




연관된 다른 글

 

 

 

 




답글 남기기