[MySQL] 전문 검색 인덱스

전문 검색(Full Text Search) 인덱스

---

인덱스 알고리즘은 일반적으로 크지 않은 데이터 또는 이미 키워드화돼 있는 작은 값에 대한 인덱싱 알고리즘이었습니다. 대표적으로 MySQL의 B-Tree 인덱스는 실제 컬럼의 값이 1MB라 하더라도 1MB 전체의 값을 인덱스 키로 사용하는 것이 아니라 1,000바이트(MyISAM) 또는 767바이트(InnoDB)까지만 잘라서 인덱스 키로 사용합니다. 또한 B-Tree 인덱스의 특성에서도 알아봤듯이 전체 일치 또는 좌측 일부 일치와 같은 검색만 가능합니다.

문서의 내용 전체를 인덱스화해서 특정 키워드가 포함된 문서를 검색하는 전문(Full Text) 검색에는 InnoDB나 MyISAM 스토리지 엔진에서 제공하는 일반적인 용도의 B-Tree 인덱스를 사용할 수 없습니다. 문서 전체에 대한 분석과 검색을 위한 이러한 인덱싱 알고리즘을 전문 검색(Full Text search) 인덱스라고 하는데, 전문 검색 인덱스는 일반화된 기능의 명칭이지 전문 검색 알고리즘의 이름을 지칭하는 것은 아닙니다. 전문 검색 인덱스에는 문서의 키워드를 인덱싱하는 기법에 따라 크게 구분자(Stopword)와 N-그램으로 나눠서 생각해 볼 수 있습니다. 이 이외의 알고리즘은 그다지 알려지지도 않고 특히나 MySQL에서 사용할 수 있는 것이 없습니다.

인덱스 알고리즘

---

전문 검색에서는 문서 본문의 내용에서 사용자가 검색하게 될 키워드를 분석해 내고, 빠른 검색용으로 사용할 수 있게 이러한 키워드로 인덱스를 구축합니다. 키워드의 분석 및 인덱스 구축에는 여러 가지 방법이 있을 수 있습니다. 여기서는 MySQL 모든 버전에서 기본적으로 제공하는 전문 검색 엔진의 인덱스 방식인 구분자(Stopword)와 MySQL이 아닌 서드파티에서 제공하는 전문 검색 기능에서 주로 제공하는 N-그램 방식에 대해 살펴보겠습니다.

구분자(Stopword) 기법 

전문의 내용을 공백이나 탭(띄어쓰기) 또는 마침표와 같은 문장 기호, 그리고 사용자가 정의한 문자열을 구분자로 등록합니다. 구분자 기법은 이처럼 등록된 구분자를 이용해 키워드를 분석해 내고, 결과 단어를 인덱스로 생성해 두고 검색에 이용하는 방법을 말합니다. 일반적으로 공백이나 쉼표 또는 한국어의 조사 등을 구분자로 많이 사용합니다. MySQL의 내장 전문 검색(FullText search) 엔진은 구분자 방식만으로 인덱싱할 수 있습니다.

구분자 기법은 문서의 본문으로부터 키워드를 추출해 내는 작업이 추가로 필요할 뿐, 내부적으로는 B-Tree 인덱스를 그대로 사용합니다. 전문 검색 인덱스의 많은 부분은 B-Tree의 특성을 따르지만 전문 검색 엔진을 통해 조회되는 레코드는 검색어나 본문 내용으로 정렬되어 조회되지는 않습니다. 전문 검색에서 결과의 정렬을 일치율(Match percent)이 높은 순으로 출력되는 것이 일반적입니다.

구분자 기법으로 전문 검색을 사용할 때는 문장 기호뿐 아니라 특정 단어를 일부러 구분자로 등록할 수도 있습니다. 예를 들어 MySQL 매뉴얼을 페이지 단위로 잘라서 테이블에 저장하고 전문 검색을 구현한다고 해봅시다. 이 경우 테이블의 모든 레코드에는 "MySQL"이라는 단어가 포함돼 있을 것입니다. 이 경우 "MySQL"이라는 단어로 검색하면 테이블의 모든 레코드가 일치하므로 검색의 효과가 없어집니다. 이럴 때는 "MySQL"이라는 단어를 구분자에 등록하고 전문 검색 인덱스에 포함하지 않게 해주는 것이 좋습니다.

많은 인터넷 사이트에서 "Stopword"를 "불용어"로 해석하고 있지만, 이보다는 "구분자"라는 표현이 더 적절한 해석이라고 볼 수 있습니다. 이 기법의 알고리즘에서 "Stopword"는 "검색에 사용할 수 없다"보다는 "검색어를 구분해주는 기준(문장 기호나 특정 문자열)이다"의 의미가 더 강하기 때문입니다.

N-그램(N-Gram) 기법

하지만 각 국가의 언어는 띄어쓰기가 전혀 없다거나 문장 기호가 전혀 다른 경우가 허다합니다. 이런 다양한 언어에 대해 하나의 규칙을 적용해 키워드를 추출해내기란 쉽지 않습니다. 또한 구분자 방식은 추출된 키워드의 일부(키워드의 뒷부분)만 검색하는 것은 불가능하다는 단점도 있습니다. 이러한 부분을 보완하기 위해 지정된 규칙이 없는 전문도 분석 및 검색을 가능하게 하는 방법이 N-그램이라는 방식입니다.

N-그램이란 본문을 무조건적으로 몇 글자씩 잘라서 인덱싱하는 방법입니다. 구분자에 의한 방법보다는 인덱싱 알고리즘이 복잡하고, 만들어진 인덱스의 크기도 상당히 큰 편입니다. 트리톤(Tritonn)이나 스핑크스(Sphinx)에서는 다른 인덱싱 방법도 제공하지만, 이 알고리즘이 주로 사용됩니다. N-그램에서 n은 인덱싱할 키워드의 최소 글자(또는 바이트) 수를 의미하는데, 일반적으로는 2글자 단위로 키워드를 쪼개서 인덱싱하는 2-Gram(또는 Bi-Gram이라고도 한다) 방식이 많이 사용됩니다.

2-Gram 인덱싱 기법은 2글자 단위의 최소 키워드에 대한 키를 관리하는 프론트엔드(Front-end) 인덱스와 2글자 이상의 키워드 묶음(n-SubSequence Window)를 관리하는 백엔드(Back-end) 인덱스 2개로 구성됩니다. 인덱스의 생성 과정은 다음과 같이 2가지 단계로 나눠서 처리됩니다.

첫 번째 단계로, 문서의 본문을 2글자보다 큰 크기로 블록을 구분해서 백엔드 인덱스(3)을 생성

두 번째 단계로, 백엔드 인덱스의 키워드들을 2글자씩 잘라서 프론트엔드 인덱스(6)을 생성

인덱스의 검색 과정은 전문 인덱스의 생성과는 반대로, 입력된 검색어를 2바이트 단위로 동일하게 잘라서 프론트엔드 인덱스를 검색합니다. 그 결과를 대상 후보 군으로 선정하고, 백엔드 인덱스를 통해 최종 검증을 거쳐 일치하는 결과를 가져옵니다.

구분자와 N-그램의 차이

---

실제 사용자가 보는 구분자와 N-그램의 가장 큰 차이는 검색 결과에 있습니다. 아래와 같은 데이터가 포함된 테이블을 예로 살펴보겠습니다.

doc_id	doc_body
1	중고 아이폰 3G 팝니다.
2	아이폰 3Gs 구해 봅니다.
3	애플아이폰 3Gs 싸게 팝니다.

위 테이블의 doc_body 컬럼에 전문 검색 인덱스를 생성하고, 다음 쿼리를 실행하면 결과는 어떻게 달라질가요?

SELECT * FROM tb_test WHERE MATCH(doc_body) AGAINST('아이폰' IN BOOLEAN MODE);

구분자 방식 (MySQL 내장 전문 검색 엔진)

doc_id	doc_body
1	중고 아이폰 3G 팝니다.
2	아이폰 3Gs 구해 봅니다.

N-그램 방식 (트리톤 스토리지 엔진)

doc_id	doc_body
1	중고 아이폰 3G 팝니다.
2	아이폰 3Gs 구해 봅니다.
3	애플아이폰 3Gs 싸게 팝니다.

MySQL 내장 전문 검색 엔진이 사용하는 구분자 방식의 검색에서는 반드시 구분자를 기준으로 삼아 왼쪽 일치 기준으로 비교 검색을 실행하게 됩니다. 그래서 검색어 ("아이폰")앞에 다른 단어("애플")가 연결돼있으면 이ㅏ는 찾아낼 수 없습니다. 하지만 N-그램은 모든 데이터에 대해 무작위로 2바이트씩 인덱스를 생성하므로 검색이 가능한 것입니다. 구분자의 이러한 제약은 쇼핑몰과 같은 웹 서비스에서 상품의 이름을 검색할 때 상당한 제한 사항이 될 수도 있습니다.

다음으로, N-그램 방식의 트리톤 전문 검색 엔진과 구분자 방식의 MySQL  빌트 인(Built-in) 전문 검색 엔진의 성능과 인덱스의 크기도 한번 비교 해보겠습니다. 우선 N-그램 전문 검색 인덱스는 구분자 방식보다 인덱스의 크기가 큽니다.

또한, N-그램 방식의 인덱스는 인덱스를 생성하는 과정이 복잡하므로 전문 인덱스에 키워드를 추가하거나 삭제하는 데 시간도 많이 걸리게 됩니다. 하지만 전문 검색을 수행하는데 걸리는 시간은 2-Gram 알고리즘의 트리톤이 2~3배 이상 빠르며, 클라이언트의 동시 실행 쿼리 수가 많아질수록 그 차이는 더욱 벌어집니다.

전문 검색에서 검색어 길이에 따른 성능 변화를 살펴보면 트리톤과 MySQL 빈트인 전문 검색 엔진 모두 검색어 길이가 길어질수록 많은 성능 저하를 불러일으키게 됩니다. 특히 MySQL 빌트인 전문 검색은 검색어 길이가 커질수록 쿼리의 성능이 더 심하게 느려지는 것을 알 수 있습니다.

전문 검색 인덱스의 가용성

---

전문 검색 인덱스를 사용하려면 반드시 그에 맞는 구문을 사용해야 합니다. 다음과 같이 테이블의 doc_body 컬럼에 전문 검색 인덱스를 생성했다고 가정해 보겠습니다.

CREATE TABLE tb_test (
    doc_id INT,
    doc_body TEXT,
    PRIMARY KEY (doc_id),
    FULLTEXT KEY fx_docbody (doc_body)
) ENGINE=MyISAM;

다음과 같은 검색 쿼리로도 원하는 검색 결과를 얻을 수 있을 것입니다. 하지만 전문 검색 인덱스를 이용해 효율적으로 쿼리가 실행된 것이 아니라 테이블을 처음부터 끝까지 읽는 풀 테이블 스캔으로 쿼리를 처리합니다.

SELECT * FROM tb_test WHERE doc_body LIKE '%애플%';

전문 검색 인덱스를 사용하려면 반드시 MATCH (...) AGAINST (...) 구문으로 검색 쿼리를 작성해야 하며, MATCH 절의 괄호에 포함되는 내용은 반드시 사용할 전문 검색 인덱스에 정의된 컬럼이 모두 명시돼야 합니다. 트리톤이나 스핑크스 같은 서드파티 스토리지 엔진 또한 "MATCH (...) AGAINST (...)"의 기본 구문을 그대로 사용할 수 있습니다. 또한 서드파티 스토리지 엔진들은 추가적인 키워드나 문법을 더 지원하므로 반드시 해당 소프트웨어의 매뉴얼을 참조하는 것이 좋습니다.

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