[4기 대구 박병권] 데이터베이스 해시 인덱스 사용법 #2

안녕하세요!

대구멤버십 21-2기 박병권입니다.

 

저번 시간에 이어 해시 인덱스의 이야기를 조금 더 하려고 합니다.

 

해시 인덱스는 Memory 스토리지 엔진에서만 가능합니다. 만약 다른 스토리지 엔진을 사용하게 된다면 스스로 InnoDB와 비슷한 방식으로 해시 인덱스를 흉내 내면 됩니다. 이렇게 한다면 키가 아주 길어도 인덱스 크기는 매우 작은 것 같은 해시 인덱스의 특성을 누릴 수 있습니다.

방법은 표준 B-트리 인덱스의 꼭대기에 가상의 해시를 생성하는 것입니다. 이것은 진짜 해시 인덱스와 완전히 똑같진 않지 않지만 B-TREE에서 키 자체가 아닌 키의 해시값을 이용해 조회를 합니다.

 

예를 들어 설명하면 URL을 조회를 한다고 가정하면, URL은 B-TREE 인덱스를 커지게 하는데 이는 URL이 아주 길기 때문입니다. 보통 이런식으로 쿼리를 날리게 됩니다.

 

mysql> SELECT id FROM url WHERE url="http://www.mysql.com";

 

하지만 url 칼럼의 인덱스를 제거하고 인덱스된 url_crc칼럼을 테이블에 추가하면 이렇게 쿼리를 사용할 수 있습니다.

 

mysql> SELECT id FROM url WHERE url="http://www.mysql.com"

AND url_crc=CRC32("http://www.mysql.com");

이 쿼리는 잘 작동하는데 MySQL 쿼리 옵티마이저가 url_crc 칼럼에 작고 선택도가 매우 높은 인덱스가 있다는 걸 알고 해당 값을 가진 엔트리를 인덱스 조회하기 때문입니다. 예닐곱 개의 행이 똑같은 url_crc값을 갖더라도 정수 비교가 빠르므로 해당 url_crc 값을 가진 행들을 찾아내고 검사하여 전체 URL값이 정확이 일치하는 행을 찾기는 아주 쉽습니다. 다른 방법으로는 전체를 문자열로 인덱스하는 방법이 있는데 이 방법은 훨씬 더 느립니다.

 

이 방법의 약점은 해시 값을 지속적으로 유지해야 한다는 점입니다. 스스로 해도 가능하지만 트리거를 이용한다면 큰 문제는 없습니다.

 

CREATE TABLE hashtest(

id int unsigned NOT NULL auto_increment,

url varchar(255) NOT NULL,

url_crc int unsigned NOT NULL DEFAULT 0,

PRIMARY KEY(id)

);

 

위 와 같이 테이블을 생성합니다.

위 테이블을 단순 url를 저장하는 테이블입니다. 해시값을 저장하기 위해 url_crc를 unsigned int 타입으로 칼럼을 하나 더 생성하였습니다.

 

이제 값을 입력합니다.

삽입

mysql> INSERT INTO hashtest (`url`, `url_crc`) VALUES ('http://blog.secmem.org', CRC32('http://blog.secmem.org'));

 

조회

mysql> SELECT id FROM hashtest WHERE url_crc=CRC32("http://blog.secmem.org");

 

수정

mysql> UPDATE hashtest SET url='http://blog.secmem.org'

WHERE url_crc=CRC32("http://blog.secmem.org");

 

위와 같이 url 칼럼에는 url을 넣고 url_crc 칼럼에는 MySQL의 CRC32함수로 해시 값을 넣습니다.

 

- 주의사항

이 접근법을 사용할 경우 SHA1() 또는 MD5() 해시 함수를 사용하면 안됩니다. 이 함수는 아주 긴 문자열을 반환하게 되는데 이로 인해 공간 낭비가 심하고 비교 속도 또한 느려지기 때문입니다. 두 함수는 충돌이 거의 발생하지 않는 장점입니다.

 

CRC32를 해시 함수로 사용 하였을 때 충돌이 일어났다면 조건절에 아래와 같이 확인하는 조건이 필요합니다.

mysql> SELECT id FROM url WHERE url_crc=CRC32("http://blog.secmem.org")

AND url="http://blog.secmem.org");

 

이 때 두 번째 url을 확인하는 절차로 인해 효율성은 떨어지게 됩니다.

 

---

참고문헌 

1. MySQL 성능 최적화 / 위키북스 / 배론 슈와츠 지음

---