MySQL에서 해시(Hash) 인덱스 구현

MySQL에는 기본적으로 해시 인덱스가 제공되지 않는다.
물론, InnoDB의 Adaptive Hash 인덱스라는 기능이 있지만, 이 기능은 사용자가 조작 가능한 형태가 아니라 InnoDB 엔진에서 자주 접근되는 인덱스 데이터들에 대해서 자동적으로 Hash 인덱스를 생성하는 기능이므로 사용자 테이블에 명시적으로 Hash 인덱스를 적용할 수 는 없다.


Hash 인덱스의 장점은 인덱싱할 필드 값들을 Hash 함수를 통해서 계산된 Hash 값으로 인덱스를 만들기 때문에 검색 대상이 되는 필드 값의 길이에 관계 없이 빠른 검색 기능을 제공할 수 있다.
물론, 단점도 있는데 Hash 인덱스는 이미 한번 가공된 값으로 인데싱을 구현하기 때문에 정확히 일치하는 값만 검색이 가능하다. (즉, 범위 검색이나 부분 일치 검색은 Hash 인덱스를 이용할 수 없다.)


일반적으로, 최근의 많은 웹페이지의 기능들 또는 분석 기능들 중에서는 URL을 가공해야 처리해야 하는 요건이 상당히 많이 발생하는데, URL의 길이는 제한이 없거나 상당히 길다는 것도 B-Tree 인덱스를 사용하기에는 부담스러운 부분이다.


오늘은 간단히 URL 필드 값에 대해서 Hash 인덱스와 비슷한 기능을 MySQL의 B-Tree 인덱스로 구현하는 예제를 살펴보고자 한다.


요건은 간단히 Apache 웹 서버의 Access log를 저장하고 가공하기 위한 테이블을 설계한다고 가정해보자.
우선 아래와 같은 테이블이 필요할 것이다.


CREATE TABLE access_log(
  log_id bigint unsigned not null auto_increment,
  access_dttm datetime not null,
  agent_name varchar(50) not null,
  access_url varchar(2000) not null,
  referrer_url varchar(2000),
  ...
  PRIMARY KEY (log_id),
  INDEX ix_accessdttm (access_dttm)
);


대략 요건을 충족할 수 있는 테이블이 위와 같이 준비하고,
만약, 주로 검색이 발생하는 URL 값이 referrer_url 이라면, referrer_url 컬럼값의 Hash 추출 값을 저장할 컬럼을 하나 더 추가한다.
이때, 추가할 컬럼의 타입은 사용할 해시 함수의 특성과 해시값의 데이터 타입에 따라서 결정해야 한다.
(만약, Referrer의 도메인별 처리가 필요하다면, 테이블의 처음 설계부터 referrer_domain컬럼 추가를 고려하는 것이 좋다.)


CRC32 함수를 사용할 경우
  CRC32 함수는 문자열을 입력으로 받아서, 32Bit unsigned값을 리턴해주는 함수이므로 
  추출값을 저장할 컬럼의 타입을 INT UNSIGNED 로 지정하면 충분하다.
  CRC32는 입력값이 다르다 하더라도 출력되는 값이 동일할 가능성이 상당히 높은 편이다.


MD5 함수를 사용할 경우
  MD5는 Message Digest 함수로써, 긴 문자열이나 데이터를 입력으로 받아서 128 Bit 체크섬을 리턴하는데, 
  MD5() 함수의 결과값은 32 글자의 Hex 문자열을 리턴한다.
  그래서 MD5를 사용할 경우에는 CHAR(32)로 설정하는 것이 일반적인데,
  (MD5 함수의 결과값은 항상 32글자 이므로 VARCHAR(32)보다는 CHAR(32)로 하는 것이 
   더 스토리지 공간을 절약할 수 있다.)
  만약, 데이터의 사이즈를 줄이고자 하는 경우에는 BINARY(16) 으로 타입을 생성하고 리턴값을 
  BINARY로 변환해서 저장하면 된다. 또한 MD5는 비밀번호 암호화 용도로도 주로 사용되는데,
  입력값이 다른 경우, 생성되는 체크섬의 중복 가능성이 상당히 희박하기 때문이다.


기타 해시 함수 사용
  그 해시 함수가 리턴해주는 값의 타입에 맞게 적절히 타입 결정해야 하는데,
  일반적으로 이러한 해시 함수는 MySQL의 SQL로 생성 가능한 것이 작업하기 편하기 때문에 
  CRC32 또는 MD5를 사용하는 것이 일반적이며, 이 함수들이 만족스럽지 못한 경우에는
  UDF를 직접 만들어서 추가해도 무방하다.
  (만약 이 경우를 선택하기로 했다면, FNV (Fowler-Voll-No) 해시 함수를 한번 참조해보는 
   것도 도움이 될듯 하다. - 상당히 빠르며 중복도 작게 발생하는 것으로 많이 알려져 있으며,
   이미 MySQL UDF로 구현된 것도 다운로드 할 수 있을 것이다.)
  
이 글에서는 MD5를 사용하는 것으로 예제를 살펴보겠다.
위에서 준비된 테이블에 Hash값을 저장할 추출 컬럼과 그 컬럼에 인덱스를 추가하자.


CREATE TABLE access_log(
  log_id bigint unsigned not null auto_increment,
  access_dttm datetime not null,
  agent_name varchar(50) not null,
  access_url varchar(2000) not null,
  referrer_url varchar(2000),
  referrer_hash CHAR(32) NOT NULL,
  ...
  PRIMARY KEY (log_id),
  INDEX ix_accessdttm (access_dttm),
  INDEX ix_referrerhash (referrer_hash)
);


이제 간단히 데이터를 저장하는 INSERT 문장과, SELECT 하는 문장을 예제로 살펴보자.


데이터 저장
INSERT INTO access_log (log_id, access_dttm, ..., referrer_url, referrer_hash)
  VALUES (NULL, '2010-11-11 10:22:12', ..., 'http://intomysql.blogspot.com',
          MD5('http://intomysql.blogspot.com'));


데이터 조회 (단순)
SELECT * 
FROM access_log
WHERE referrer_hash=MD5('http://intomysql.blogspot.com');


데이터 조회 (GROUP BY)
SELECT referrer_url, COUNT(*) 
FROM access_log
GROUP BY referrer_hash;


여기에서 한 가지 주의해야 할 사항은,
CRC32 해시 함수의 경우 상당히 중복 가능성이 높다. 그래서 CRC32 함수를 사용하는 경우에는 반드시 실제 데이터의 확인까지 필요하다.


SELECT * 
FROM access_log
WHERE referrer_hash=MD5('http://intomysql.blogspot.com')
  AND referrer_url='http://intomysql.blogspot.com';
  
CRC32가 MD5 보다는 빠르고 저장 공간도 적게 차지하지만, 이러한 부분들을 용인할 수 있다면,
MD5 함수를 해시 함수로 사용할 것을 권장한다. 
물론 MD5 함수도 중복의 가능성은 있지만, 거의 무시할 수 있을 정도이며, 만약 이 부분이 걱정된다면 위 예제처럼 실질값 비교를 추가해주어도 성능상 손실은 거의 없을 것으로 보인다.






그리고, 추가로
만약 MD5 해시 값을 저장하는 컬럼을 CHAR(32)가 아닌 BINARY(16)으로 선택한 경우에는 아래와 같이 INSERT, SELECT하면 된다.
데이터 저장
INSERT INTO access_log (log_id, access_dttm, ..., referrer_url, referrer_hash)
  VALUES (NULL, '2010-11-11 10:22:12', ..., 'http://intomysql.blogspot.com', 
  UNHEX(MD5('http://intomysql.blogspot.com')));


데이터 조회 (단순)
SELECT log_id, access_dttm, HEX(referrer_hash) as referrer_hash
FROM access_log
WHERE referrer_hash=UNHEX(MD5('http://intomysql.blogspot.com'));