레이블이 Tritonn인 게시물을 표시합니다. 모든 게시물 표시
레이블이 Tritonn인 게시물을 표시합니다. 모든 게시물 표시

2010년 12월 30일 목요일

Tritonn을 이용한 MySQL 서버의 전문 검색 엔진 구현

MySQL전문 검색 엔진 (Fulltext search engine)은 테이블의 레코드 건수나 Fulltext 인덱스 건수에 따라서 성능 저하 현상이 심한 편이다
또한, 전문 인덱스의 인덱싱 방식이 Stopword 기반이기 때문에 LIKE와 비슷한 패턴의 검색(Partial search)이 불가능하며, 검색의 목적에 맞게 전문 인덱스를 여러 개 만들어야 할 경우도 있다.
MySQL 5.1에서 Fulltext engine Parser를 플러그 인으로 만들어서 끼워 넣을 수 있지만, 현재로써는 적당한 오픈 소스 Parser가 없으며, 직접 만든다는 것은 더더욱 어려운 것이 사실이다.

이러한 이유들로 인해서, 일본에서 MySQL 전문 검색의 단점을 보완하고, 아시아권 언어를 위한 Tritonn이라는 
전문 검색 엔진을 오픈 소스로 개발했으며, MySQL builtin 전문 검색 엔진에서는 제공되지 않는 여러 가지 
기능들을 더 제공하고 있다.
가장 큰 장점은 Stopword 뿐만 아니라 구분자와 n-Gram 방식의 전문 분석 및 인덱싱이 가능하다는 것이다.
MySQL Builtin 전문 검색 엔진과 Tritonn 전문 검색 엔진의 기능 비교는 아래 URL을 참조하기 바란다.

n-Gram 방식의 인덱싱이란 Document의 전체 내용을 구분자나 Stopword에 관계 없이 n-문자씩 잘라서 
전문 인덱싱을 구성하는 방식을 이야기하며, 자르는 문자 수에 따라서 2-Gram 또는 4-Gram 등등으로 
구분할 수 있지만, 일반적으로 2-Gram이 일반적이다
이러한 n-Gram 방식의 인덱싱은 구분자나 Stopword 기준으로 검색하지 않아도 검색이 가능하다는 것이 장점이다.
예를 들어서 "Diablo Entertainment"라는 데이터와 "BlizzardDiabloEntertainment"라는 두 개의 데이터가 있다고 
가정할 때, "Diablo"로 검색할 경우, 구분자나 Stopword 방식으로는 첫 번째 데이터만 검색할 수 있다
하지만, n-Gram방식의 인덱싱에서는 둘 다 검색을 할 수 있게 되는 것이다.

현재 Tritonn MySQL 5.0 버전 대에서는 Source-patch 방식으로 적용할 수 있으며,
MySQL 5.1 버전 부터는 Plugin 형태로 적용할 수 있게 되었다. (, MySQL 소스 코드를 다시 빌드하지 않고 
적용할 수 있다.)

Tritonn (MySQL 5.0) URLhttp://qwik.jp/tritonn/ 이며,
Groonga (Tritonn MySQL 5.1 용 플러그인 버전의 이름)의 정보는 http://mroonga.github.com/ 를 참조하면 된다.
Groonga는 현재 개발 버전이며 Release 버전은 아니므로, 오늘 글에서는 MySQL 5.0.87 버전의 Tritonn 패치를 가지고 설치 및 인덱스 생성 사용하는 방법을 살펴보도록 하겠다.

우선 Tritonn이 전문 인덱싱을 위해서 사용하는 Senna라는 라이브러리를 받아서 설치해야 한다.
http://sourceforge.jp/projects/senna/releases/ 사이트를 방문하여 senna-1.1.4.tar.gz(더 최신 버전이 있지만, Tritonn이 이 버전을 타겟으로 개발했기 때문에) 파일을 다운로드 한다.

그리고, http://sourceforge.jp/projects/tritonn/releases/ 사이트에서 Tritonn의 소스 코드가 패치된 MySQL 5.0.87 
소스 파일을(tritonn-1.0.12-mysql-5.0.87.tar.gz)을 다운로드한다.


Senna를 Build하기 위해서는 최소 Redhat Enterprise linux 5.x(CentOS 5.x) 이상이 필요함

Senna 설치
tar zxvf senna-1.1.4.tar.gz
cd senna-1.1.4
./configure --prefix=/usr --without-mecab
make
make install

"ls -al /usr/bin/senna" 명령으로 senna library가 설치되었는지 확인한다.
그리고, MeCab은 일본어를 위한 언어 분석기이기 때문에 오늘 설치 절차에서는 제외하기로 한다.

그 다음으로 Tritonn 코드가 패치된 MySQL 5.0.87을 압축 해제하여 빌드하고 설치한다.
tar zxvf tritonn-1.0.12-mysql-5.0.87.tar.gz
cd tritonn-1.0.12-mysql-5.0.87
./configure \
    '--prefix=/mysql/MySQL-5.0.87'\
    '--localstatedir=/mysql/MySQL-5.0.87/data'\
    '--libexecdir=/mysql/MySQL-5.0.87/bin'\
    '--with-comment=MySQL 5.0.87 tritonn 1.0.12 64bit'\
    '--with-server-suffix=-tritonn_64'\
    '--enable-thread-safe-client'\
    '--enable-local-infile'\
    '--enable-assembler'\
    '--with-pic'\
    '--with-fast-mutexes'\
    '--with-client-ldflags=-static'\
    '--with-mysqld-ldflags=-static'\
    '--with-zlib-dir=bundled'\
    '--with-big-tables'\
    '--with-readline'\
    '--with-innodb'\
    '--with-federated-storage-engine'\
    '--with-extra-charsets=complex'\
    '--enable-shared'\
    '--with-senna'\
    '--without-mecab'\
    'CC=gcc'\
    'CXX=gcc'

make
make install
cd /mysql/MySQL-5.0.87

MySQL Configure 과정은 필요한 다른 것들을 추가하거나 변경해도 무방하지만, '--with-senna' '--without-mecab' 옵션은 반드시 추가해주어야 한다.

이렇게 해서 빌드된 MySQL 프로그램을 /mysql/MySQL-5.0.87 디렉토리에 복사하고 나면
일반적인 MySQL의 설치 과정과 같이 기본 데이터베이스를 생성해주고 MySQL을 기동하면 된다.

cp /mysql/MySQL-5.0.87/share/mysql/mysql.server /etc/init.d/
cd /mysql/MySQL-5.0.87
.bin/mysql_install_db  --defaults-file=./etc/my.cnf
/etc/init.d/mysql.server start

MySQL 이 정상적으로 기동되었다면, MySQL에 로그인해보자.

[root@toto:/mysql/MySQL-5.0.87]$ ./bin/mysql -uroot -p
Enter password:
Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 1
Server version: 5.0.87-tritonn_64 MySQL 5.0.87 tritonn 1.0.12 64bit

정상적으로 버전 레이블이 출력되었다면, 이제 Tritonn을 이용해서 n-Gram 전문 인덱스를 생성 해보자.

CREATE TABLE tritonn_test (
  doc_id INT NOT NULL AUTO_INCREMENT,
  title VARCHAR(1000) NOT NULL,
  document TEXT,
  PRIMARY KEY (doc_id),
  FULLTEXT INDEX fx_document USING NGRAM, NO NORMALIZE (document)
) ENGINE=MyISAM DEFAULT CHARSET utf8;

insert into tritonn_test values (NULL, 'Tritonn full text search engine', '트리튼 전문 검색 엔진');

root@localhost:test>select * from tritonn_test;
+--------+---------------------------------+--------------------------------+
| doc_id | title                           | document                       |
+--------+---------------------------------+--------------------------------+
|      1 | Tritonn full text search engine | 트리튼 전문 검색 엔진          |
+--------+---------------------------------+--------------------------------+

Tritonn 인덱스를 이용하는 테이블이 만들어지면, "SHOW SENNA STATUS;" 라는 명령을 이용하여 각 전문 인덱스들의 특성들을 확인할 수 있다.
(여기서는 크게 중요하지 않으므로, 그냥 무시)
SENNA를 이용한 인덱스가 만들어지면, MySQL의 데이터 디렉토리에는 아래와 같은 파일들이 생성된다.
-rw-rw---- 1 mysql mysql    8612 Dec 30 17:20 category.frm
-rw-rw---- 1 mysql mysql   98304 Dec 30 17:20 category.ibd
-rw-rw---- 1 mysql mysql 8462336 Dec 30 17:23 tritonn_test.001.SEN
-rw-rw---- 1 mysql mysql  430080 Dec 30 17:23 tritonn_test.001.SEN.i
-rw-rw---- 1 mysql mysql  135168 Dec 30 17:23 tritonn_test.001.SEN.i.c
-rw-rw---- 1 mysql mysql 8462336 Dec 30 17:23 tritonn_test.001.SEN.l
-rw-rw---- 1 mysql mysql    8634 Dec 30 17:23 tritonn_test.frm
-rw-rw---- 1 mysql mysql      76 Dec 30 17:23 tritonn_test.MYD
-rw-rw---- 1 mysql mysql    2048 Dec 30 17:23 tritonn_test.MYI

.SEN 파일 MyISAM 테이블과 SENNA의 내부 문서 ID의 매핑 파일로써, 레코드가 증가할수록 파일 크기가 증가함
.SEN.i 파일은 인덱스 버퍼 정도로 생각하면 되고, INDEX 생성시에 사이즈를 지정할 수 있음
.SEN.l 파일은 어휘와 어휘 ID의 매핑을 관리하는 파일로써, 등록된 어휘의 수가 늘어날수록 파일 크기가 증가함
.SEN.i.c 파일은 인덱스를 저장하는 파일

이제 다시 MySQL로 돌아와서
이제 Tritonn을 이용한 전문 검색을 실행 해보자
Tritonn의 전문 검색 사용 방법은 MySQLFulltext와 기본적으로 동일하다.

-- // 공백이나 구분자 또는 Stopword로 구분된 단위가 아니어도 검색이 가능하다.
root@localhost:test>SELECT * FROM tritonn_test WHERE MATCH (document) AGAINST ('리튼' IN BOOLEAN MODE);
+--------+---------------------------------+--------------------------------+
| doc_id | title                           | document                       |
+--------+---------------------------------+--------------------------------+
|      1 | Tritonn full text search engine | 트리튼 전문 검색 엔진          |
+--------+---------------------------------+--------------------------------+

-- // 중간에 공백이 있는 단어라 하더라도 검색이 가능하다.
root@localhost:test>SELECT * FROM tritonn_test WHERE MATCH (document) AGAINST ('색 엔' IN BOOLEAN MODE);
+--------+---------------------------------+--------------------------------+
| doc_id | title                           | document                       |
+--------+---------------------------------+--------------------------------+
|      1 | Tritonn full text search engine | 트리튼 전문 검색 엔진          |
+--------+---------------------------------+--------------------------------+

-- // Tritonn의 전문 검색 엔진 결과와 다른 MyISAM 또는 InnoDB 테이블과 조인이 가능하다.
root@localhost:test>SELECT c.category_name, d.doc_id, d.title, d.document
    -> FROM tritonn_test d, category c
    -> WHERE MATCH (document) AGAINST ('리튼' IN BOOLEAN MODE)
    ->   AND c.doc_id=d.doc_id;
+---------------+--------+---------------------------------+--------------------------------+
| category_name | doc_id | title                           | document                       |
+---------------+--------+---------------------------------+--------------------------------+
| MySQL         |      1 | Tritonn full text search engine | 트리튼 전문 검색 엔진          |
+---------------+--------+---------------------------------+--------------------------------+


이제
두 개의 컬럼을 이용한 전문 검색 인덱스를 생성해서, 인덱스의 전체 컬럼 또는 일부 컬럼만 검색하는 예제를 살펴보자.
CREATE TABLE tritonn_test (
  doc_id INT NOT NULL AUTO_INCREMENT,
  title VARCHAR(1000) NOT NULL,
  document TEXT,
  PRIMARY KEY (doc_id),
  FULLTEXT INDEX fx_title_document USING NGRAM, NO NORMALIZE, SECTIONALIZE (title, document)
) ENGINE=MyISAM DEFAULT CHARSET utf8;

insert into tritonn_test values (NULL, 'Tritonn full text search engine', '트리튼 전문 검색 엔진');

-- // 전문 인덱스가 두개의 컬럼으로 만들어졌기 때문에 MATCH 절에는 항상 2개의 컬럼 모두 명시되어야 한다.
-- // AGAINST 절에 따른 패턴이 적용되지 않으면, 기본적으로 모든 컬럼에 대해서 검색을 실행한다.
root@localhost:test>SELECT * FROM tritonn_test WHERE MATCH (title, document) AGAINST ('리튼' IN BOOLEAN MODE);
+--------+---------------------------------+--------------------------------+
| doc_id | title                           | document                       |
+--------+---------------------------------+--------------------------------+
|      1 | Tritonn full text search engine | 트리튼 전문 검색 엔진          |
+--------+---------------------------------+--------------------------------+

-- // AGAINST 절에 검색어 앞에 "*Wn" 가 명시되면, 인덱스의 n 번째 컬럼에 대해서만 전문 검색을 실행하게 된다.
-- // 아래 예제는 "*W1" 이기 때문에 첫번째 컬럼인 title 컬럼에 대한 검색만 실행한다. 그래서, 결과가 없음.
root@localhost:test>SELECT * FROM tritonn_test WHERE MATCH (title, document) AGAINST ('*W1 리튼' IN BOOLEAN MODE);
Empty set (0.00 sec)

-- // 이번에는 "*W2" 이기 때문에 두 번째 컬럼인 document 컬럼에 대한 검색만 실행한다.
root@localhost:test>SELECT * FROM tritonn_test WHERE MATCH (title, document) AGAINST ('*W2 리튼' IN BOOLEAN MODE);
+--------+---------------------------------+--------------------------------+
| doc_id | title                           | document                       |
+--------+---------------------------------+--------------------------------+
|      1 | Tritonn full text search engine | 트리튼 전문 검색 엔진          |
+--------+---------------------------------+--------------------------------+

Tritonn 전문 검색 엔진에 대해서는 여기까지 간단히 설명을 끝내고,
Tritonn과 비슷한 Sphinx라는 전문 검색 엔진도 있다이 또한 n-Gram 방식의 검색을 지원하고 있다.
Sphinx에 대해서는 다시 한번 더 알아볼 수 있는 기회를 갖도록 하겠다.




참고로, "SHOW CREATE TABLE tritonn_test;"의 결과에서 보이는
512라는 숫자는 INITIAL_N_SEGMENTS (인덱스 버퍼 공간의 기본값) 값이며 512 Default.




2010년 12월 27일 월요일

MySQL Builtin Full Text Search Engine과 Tritonn의 기능 비교


MySQL Builtin Full Text Search Engine Tritonn의 기능 비교


MySQL Builtin
Tritonn
MySQL Version dependency
All Enterprise, Community Version
Specific Community version
UTF-8 Support
Yes
Yes
Support Table Engine Type
MyISAM
MyISAM
Indexing Method
Stop Word
Stop Word and N-Gram
Support online Indexing
Yes (Online Incremental)
Yes (Online Incremental)
Search Mode
Natural and Boolean Mode
Natural and Boolean Mode
Multi Full Text Index
Yes
Yes
Multi Column Full Text Index
Yes
Yes
Support Join with Normal Table
Yes
Yes
Full Text Index Sectionizing
No
Yes
Search Result Custom Weighting
No
Yes
Partial String Search
No
Yes
License
MySQL Dependent
GPL2
(Support only community version)
MySQL Version dependency : 어떤 버전의 MySQL 서버에 적용 가능한지 비교
Multi Full Text Index : 하나의 테이블 내에서 여러 개의 Full Text Search Index 생성이 가능한지 비교
Multi Column Full Text Index : 하나의 Full Text Search Index에 여러 개의 Column 적용 가능한지 비교
Support Join with Normal Table : Full Text Search 결과와 일반 테이블 (Memory, Innodb, MyISAM)과 조인이 가능한지 비교
Full Text Index Sectionizing : 여러 개의 Column을 이용하여 하나의 Full Text Search을 생성했을 때, 개별 Column에 대해서만 검색이 가능한지 비교
Search Result Custom Weighting : 검색 시, 별도의 가중치 (Weighting) 부여가 가능한지 비교
Partial String Search : Stop Word (Space, Tab, …) 를 기준으로 전체 문자열이 아닌, 해당 문자열의 일부분만 검색 가능한지 비교

전문 검색 엔진(Full text search engine)의 검색 방식 및 인덱싱


검색 방식

  • 자연어 검색
    자연어 검색이란, 문자 그대로 검색어를 일반적으로 인간이 사용하는 문장이나 절로(자연스러운 문장의 구문) 가정하여 그대로 Matching해서 검색을 실행하는 방법을 의미한다.  별도의 연산자를 사용할 수 없으며, StopWord 가 적용되며,  50% 이상의 레코드에 존재하는 단어는 일반적인 단어로 간주하여 검색에서 배제한다. 또한, 검색 결과 Match율은 Percentage로 표시된다. MySQL에서는 별도의 옵션을 제공하지 않으면, 자연어 검색을 실행하게 된다.
    (MySQL Built-in 전문 검색엔진을 포함한 대부분의 전문 검색 도구가 지원한다.)
  • Boolean 검색
    자연어와 달리 검색어의 단어 단위로 특별한 예약어 (+-* 등)를 사용하여 검색 방법을 지정할 수 있다. 검색 방식의 이름에서도 알 수 있듯이, 일부 일치(몇 Percentage 일치)와 같은 개념은 존재하지 않으며, Match율은 순수하게 0% 아니면, 100% 일치로 표기된다. 또한 검색 결과도 100% 일치건만 추출된다.
    (MySQL Built-in 전문 검색엔진을 포함한 대부분의 전문 검색 도구가 지원한다.)


인덱싱 방식

  • 구분자 또는 불용어 (Delimiter, StopWord)
    Full Text search에서는 전문 (Text)의 내용의 빠른 검색을 위해서 Index Building이 중요한데, 전문의 내용을 기 정의된 StopWord 목록을 이용하여 Parsing(분리)을 해서 결과 단어들의 목록을 인덱스로 생성해 두고 검색에 이용하는 방법을 말한다.  일반적으로 구분자는 공백이나 쉼표 또는 한국어의 조사 등을 구분자로 많이 사용하게 되며, 특정 시스템별로 아주 자주 사용되는 단어들도 검색의 의미가 없기 때문에 구분자로 등록하는 경우도 많다. (예를 들어 MySQL 홈페이지에서 MySQL 이라는 단어는 검색의 의미가 없기 때문에 구분자로 등록하는 것이 효율적일 수 있다)
    MySQL의 Built-in 전문 검색 엔진 (FullText search)은 이 방식만으로 인덱싱을 할 수 있다.
  • N-Gram
    지정된 구분자로 전 세계 모든 언어에서 단어를 구분해 낸다는 것은 쉽지 않을 것이다. 이러한 부분을 보완하기 위해서 지정된 규칙이 없는 전문도 분석 및 검색을 가능하도록 하는 방법이 N-Gram이라는 방식이다. N-Gram이란, 전문을 무조건적으로 몇 글자씩 잘라서 Indexing을 하는 방법이다. 구분자에 의한 방법보다는 Indexing이 복잡하고, 만들어진 Index의 Size도 상당히 큰 편이다.  
    (Tritonn이나 Sphinx는 다른 인덱싱 방법들도 제공하지만 이 방법이 주로 사용된다.)
  • 형태소 분석
    국가별 언어에 대해서 각 문장 및 단어들의 문법 또는 의미적인 단위(형태소)로 쪼개어서 구분하고, 구문의 실제 의미를 인식할 수 있는 수준까지 분석하는 방법으로 주로 번역 시스템이나 검색 엔진들이 사용하는 방법이다. 이러한 방식은 상당히 복잡하기 때문에 일반적인 DBMS의 전문 검색 엔진에서는 쉽게 사용되진 않는 편이다.
    (Tritonn에서는 MeCab(일본어 형태소 분석기) 과 같은 형태소 분석기 라이브러리를 사용하여 적용할 수도 있다.)


Online / Offline 인덱싱

  • Online 인덱싱
    Full Text Search Engine 방식에 따라서, 대상 테이블에 데이터 레코드가 등록, 변경, 삭제되면서, Full Text Search Index에도 실시간으로 변경 분만 적용되는 형태를 의미한다.
    (MySQL Builtin Engine과 Tritonn Search Engine이 이와 같은 형태로 구현되어 있음)
  • Offline 인덱싱
    대상 테이블에 데이터 레코드가 등록, 변경, 삭제와는 무관하게 Full Text Search Index가 관리되면서, 실시간으로 Full Text Index에 반영되지 않고, 일정 주기로 수동 Batch 형태로 Full Text Index Building 작업을 해 주어야 하는 형태를 의미한다.
    (현재, Sphinx Engine이나 Lucene과 같은 소프트웨어가 이와 같은 형태로 구현되어 있음)