MySQL :: InnoDB 全文検索 : N-gram Parser

(この記事は InnoDB Full-Text : N-gram Parser を Yoshiaki Yamasaki が翻訳したものです)

デフォルトのInnoDB全文検索パーサー(構文解析プログラム)は、空白がトークン(語句)もしくは単語の区切りとなっているラテン語ベースの言語に対して理想的です。しかし、個々の単語の区切り文字が存在せず、それぞれの単語は複数の文字で構成できる中国語・日本語・韓国語(CJK)のような言語には向いていません。そこで、私たちは異なった方法で単語/トークンを識別する方法を必要とします。
私は今MySQL 5.7.6で、CJKで使用できるn-gramパーサーを提供するために、新しいプラガブル全文検索パーサーをサポートすることをとても嬉しく思っています！

N-gramとは？

全文検索において、n-gramとは与えられた文字列中のn文字の連続した文字列です。例えば、n-gramで”abcd”という文字列をトークナイズすると以下のようになります。

N=1 : 'a', 'b', 'c', 'd';
N=2 : 'ab', 'bc', 'cd';
N=3 : 'abc', 'bcd';
N=4 : 'abcd';

N=1 : 'a', 'b', 'c', 'd';

N=2 : 'ab', 'bc', 'cd';

N=3 : 'abc', 'bcd';

N=4 : 'abcd';

どのようにしてN-gramパーサーをInnoDBで使うか？

新しいn-gramパーサーはデフォルトで有効になっているため、関連するDDL文にWITH PARSER句を追加するだけで使用できます。例えば、以下のDDL文はMySQL 5.7.6以降で有効です。

mysql> CREATE TABLE articles
(
        FTS_DOC_ID BIGINT UNSIGNED AUTO_INCREMENT NOT NULL PRIMARY KEY,
        title VARCHAR(100),
        FULLTEXT INDEX ngram_idx(title) WITH PARSER ngram
) Engine=InnoDB CHARACTER SET utf8mb4;
Query OK, 0 rows affected (1.26 sec)
 
mysql> # ALTER TABLE articles ADD FULLTEXT INDEX ngram_idx(title) WITH PARSER ngram;
mysql> # CREATE FULLTEXT INDEX ngram_idx ON articles(title) WITH PARSER ngram;

mysql> CREATE TABLE articles

(

FTS_DOC_ID BIGINT UNSIGNED AUTO_INCREMENT NOT NULL PRIMARY KEY,

title VARCHAR(100),

FULLTEXT INDEX ngram_idx(title) WITH PARSER ngram

) Engine=InnoDB CHARACTER SET utf8mb4;

Query OK, 0 rows affected (1.26 sec)

mysql> # ALTER TABLE articles ADD FULLTEXT INDEX ngram_idx(title) WITH PARSER ngram;

mysql> # CREATE FULLTEXT INDEX ngram_idx ON articles(title) WITH PARSER ngram;

MySQL 5.7.6では、ngram_token_size (トークンはn文字からなる単語とほぼ同等) という新しいサーバー変数も導入されています。デフォルト値は2(bigram)で、1～10まで変更可能です。次の疑問として、「どのトークンサイズを選択すればいいか？」、という疑問が湧いてきます。2またはbigramはCJKの一般的な使用方法において推奨されていますが、この単純なルールに基づいて任意の有効な値を選択できます。
　ルール：あなたが検索時に期待する最大のトークンに合わせてトークンサイズを設定する。
もし、単一の文字を検索したい場合は、ngram_token_sizeを1に設定する必要があります。ngram_token_sizeが小さい方がインデックスを小さくでき、そのインデックスを使った全文検索がより高速になります。しかしながら欠点は、あなたが検索できるトークンのサイズを制限していることです。例えば、英語の「Happy Birthday」は伝統的な中国語では「生日高興」と翻訳されます。(「Happy」=「高興」、「Birthday」=「生日」)この例のように、それぞれの単語/トークンは2文字から構成されるため、このトークンを検索するためにはngram_token_sizeを2以上に設定する必要があります。

N-gramトークン化の詳細

n-gramパーサーはデフォルトの全文検索パーサーと以下の点が異なります。

トークンサイズ： innodb_ft_min_token_size とinnodb_ft_max_token_size は無視されます。代わりにトークンを制御するためにngram_token_sizeを指定します。
ストップワードの処理： stopwordsの処理も少し異なります。通常、トークン化された単語自体(完全一致)がストップワードテーブルにあるならば、その単語には全文検索インデックスは作成されません。しかしながら、n-gramパーサーの場合は、トークン化された単語がストップワードを含んでいないか確認し、含んでいればインデックスを作成しません。このように動作が異なる理由は、私たちのCJKは非常に多くの頻繁に使われる無意味な文字、単語、句読点を持っているからです。ストップワードに一致する文字が含まれているかを確認する方式を使うと、より役に立たないトークンを除去できます。
空白：空白は常にストップワードです(ハードコードされています)。例を挙げると、’my sql’は’my’、’y ’、’ s’、’sq’、’ql’にトークナイズされ、’y ’と’ s’はインデックス化されません。

私達はINFORMATION_SCHEMA.INNODB_FT_INDEX_CACHE テーブルとINFORMATION_SCHEMA.INNODB_FT_TABLEテーブルを参照することで、特定の全文検索インデックス内にどのようなトークンがインデックス化されているか正確に確認できます。これはデバッグの為に非常に便利なツールです。例えば、単語が期待通りに全文検索結果に表示されない場合、その単語は何らかの理由(ストップワード、トークンサイズ、など)でインデックス化されていないことを、これらのテーブルを参照することで確認できます。簡単な例を紹介します。

mysql> INSERT INTO articles (title) VALUES ('my sql');
Query OK, 1 row affected (0.03 sec)
 
mysql> SET GLOBAL innodb_ft_aux_table="test/articles";
Query OK, 0 rows affected (0.00 sec)
 
mysql> SELECT * FROM INFORMATION_SCHEMA.INNODB_FT_INDEX_CACHE;
+------+--------------+-------------+-----------+--------+----------+
| WORD | FIRST_DOC_ID | LAST_DOC_ID | DOC_COUNT | DOC_ID | POSITION |
+------+--------------+-------------+-----------+--------+----------+
| my   |            1 |           1 |         1 |      1 |        0 |
| ql   |            1 |           1 |         1 |      1 |        4 |
| sq   |            1 |           1 |         1 |      1 |        3 |
+------+--------------+-------------+-----------+--------+----------+
3 rows in set (0.00 sec)

mysql> INSERT INTO articles (title) VALUES ('my sql');

Query OK, 1 row affected (0.03 sec)

mysql> SET GLOBAL innodb_ft_aux_table="test/articles";

Query OK, 0 rows affected (0.00 sec)

mysql> SELECT * FROM INFORMATION_SCHEMA.INNODB_FT_INDEX_CACHE;

+------+--------------+-------------+-----------+--------+----------+

+------+--------------+-------------+-----------+--------+----------+

| my | 1 | 1 | 1 | 1 | 0 |

| ql | 1 | 1 | 1 | 1 | 4 |

| sq | 1 | 1 | 1 | 1 | 3 |

+------+--------------+-------------+-----------+--------+----------+

3 rows in set (0.00 sec)

N-gramの検索処理の詳細

テキスト検索

NATURAL LANGUAGE MODEでは、検索されるテキストはn-gramの和集合に変換されます。例えば、’sql’は’sq ql’に変換されます(デフォルトのトークンサイズである2、もしくはbigramの場合)。

mysql> INSERT INTO articles (title) VALUES ('my sql'), ('mysql'), ('sq'), ('sl'), ('ql');
Query OK, 5 rows affected (0.03 sec)
Records: 5  Duplicates: 0  Warnings: 0
 
mysql> SELECT * FROM articles WHERE MATCH (title) AGAINST ('sql' IN NATURAL LANGUAGE MODE);
+------------+--------+
| FTS_DOC_ID | title  |
+------------+--------+
|          1 | my sql |
|          2 | my sql |
|          3 | mysql  |
|          4 | sq     |
|          6 | ql     |
+------------+--------+
5 rows in set (0.01 sec)

mysql> INSERT INTO articles (title) VALUES ('my sql'), ('mysql'), ('sq'), ('sl'), ('ql');

Query OK, 5 rows affected (0.03 sec)

Records: 5 Duplicates: 0 Warnings: 0

mysql> SELECT * FROM articles WHERE MATCH (title) AGAINST ('sql' IN NATURAL LANGUAGE MODE);

+------------+--------+

| FTS_DOC_ID | title |

+------------+--------+

| 1 | my sql |

| 2 | my sql |

| 3 | mysql |

| 4 | sq |

| 6 | ql |

+------------+--------+

5 rows in set (0.01 sec)

BOOLEAN MODEでは、検索されるテキストはn-gramフレーズ検索に変換されます。例えば、’sql’は'”sq ql”‘に変換されます。
翻訳者注釈追記：”sq ql”は、’sq’と’ql’がこの順番で両方とも一致する必要があるため、’sq’や’ql’は検索結果に出てこない。

mysql> SELECT * FROM articles WHERE MATCH(title) AGAINST('sql' IN BOOLEAN MODE);
+------------+--------+
| FTS_DOC_ID | title  |
+------------+--------+
|          1 | my sql |
|          2 | my sql |
|          3 | mysql  |
+------------+--------+
3 rows in set (0.00 sec)

mysql> SELECT * FROM articles WHERE MATCH(title) AGAINST('sql' IN BOOLEAN MODE);

+------------+--------+

| FTS_DOC_ID | title |

+------------+--------+

| 1 | my sql |

| 2 | my sql |

| 3 | mysql |

+------------+--------+

3 rows in set (0.00 sec)

ワイルドカードを使った検索

プレフィックス(接頭辞)がngram_token_sizeより小さい場合、検索結果はその接頭辞で始まるn-gramのトークンを含む全ての行を返します。

mysql> SELECT * FROM articles WHERE MATCH (title) AGAINST ('s*' IN BOOLEAN MODE);
+------------+--------+
| FTS_DOC_ID | title  |
+------------+--------+
|          1 | my sql |
|          2 | my sql |
|          3 | mysql  |
|          4 | sq     |
|          5 | sl     |
+------------+--------+
5 rows in set (0.00 sec)

mysql> SELECT * FROM articles WHERE MATCH (title) AGAINST ('s*' IN BOOLEAN MODE);

+------------+--------+

| FTS_DOC_ID | title |

+------------+--------+

| 1 | my sql |

| 2 | my sql |

| 3 | mysql |

| 4 | sq |

| 5 | sl |

+------------+--------+

5 rows in set (0.00 sec)

プレフィックスの長さがngram_token_sizeと同じか大きい場合、ワイルドカードを使った検索はフレーズ検索に変換され、ワイルドカードは無視されます。例えば、’sq*’は'”sq”‘に変換され、’sql*’は'”sq ql”‘に変換されます。

mysql> SELECT * FROM articles WHERE MATCH (title) AGAINST ('sq*' IN BOOLEAN MODE);
+------------+--------+
| FTS_DOC_ID | title  |
+------------+--------+
|          1 | my sql |
|          2 | my sql |
|          3 | mysql  |
|          4 | sq     |
+------------+--------+
4 rows in set (0.00 sec)
 
mysql> SELECT * FROM articles WHERE MATCH (title) AGAINST ('sql*' IN BOOLEAN MODE);
+------------+--------+
| FTS_DOC_ID | title  |
+------------+--------+
|          1 | my sql |
|          2 | my sql |
|          3 | mysql  |
+------------+--------+
3 rows in set (0.00 sec)

mysql> SELECT * FROM articles WHERE MATCH (title) AGAINST ('sq*' IN BOOLEAN MODE);

+------------+--------+

| FTS_DOC_ID | title |

+------------+--------+

| 1 | my sql |

| 2 | my sql |

| 3 | mysql |

| 4 | sq |

+------------+--------+

4 rows in set (0.00 sec)

mysql> SELECT * FROM articles WHERE MATCH (title) AGAINST ('sql*' IN BOOLEAN MODE);

+------------+--------+

| FTS_DOC_ID | title |

+------------+--------+

| 1 | my sql |

| 2 | my sql |

| 3 | mysql |

+------------+--------+

3 rows in set (0.00 sec)

フレーズ検索

フレーズ検索は、n-gramトークンのフレーズ検索に変換されます。例えば、”sql”は”sq ql”に変換されます。

mysql> SELECT * FROM articles WHERE MATCH (title) AGAINST('"sql"' IN BOOLEAN MODE);
+------------+--------+
| FTS_DOC_ID | title  |
+------------+--------+
|          1 | my sql |
|          2 | my sql |
|          3 | mysql  |
+------------+--------+
3 rows in set (0.00 sec)
 
mysql> SELECT * FROM articles WHERE MATCH (title) AGAINST ('"my sql"' IN BOOLEAN MODE);
+------------+--------+
| FTS_DOC_ID | title  |
+------------+--------+
|          1 | my sql |
|          2 | my sql |
+------------+--------+
2 rows in set (0.00 sec)
 
mysql> SELECT * FROM articles WHERE MATCH (title) AGAINST ('"mysql"' IN BOOLEAN MODE);
+------------+-------+
| FTS_DOC_ID | title |
+------------+-------+
|          3 | mysql |
+------------+-------+
1 row in set (0.00 sec)

mysql> SELECT * FROM articles WHERE MATCH (title) AGAINST('"sql"' IN BOOLEAN MODE);

+------------+--------+

| FTS_DOC_ID | title |

+------------+--------+

| 1 | my sql |

| 2 | my sql |

| 3 | mysql |

+------------+--------+

3 rows in set (0.00 sec)

mysql> SELECT * FROM articles WHERE MATCH (title) AGAINST ('"my sql"' IN BOOLEAN MODE);

+------------+--------+

| FTS_DOC_ID | title |

+------------+--------+

| 1 | my sql |

| 2 | my sql |

+------------+--------+

2 rows in set (0.00 sec)

mysql> SELECT * FROM articles WHERE MATCH (title) AGAINST ('"mysql"' IN BOOLEAN MODE);

+------------+-------+

| FTS_DOC_ID | title |

+------------+-------+

| 3 | mysql |

+------------+-------+

1 row in set (0.00 sec)

InnoDBの全文検索全般に関して詳細を知りたい場合は、ユーザーマニュアルのInnoDB Full-Text Index セクションや、ジミーの素晴らしい記事(Dr. Dobb’s article) を参照して下さい。N-gramパーサーに関する詳細は、ユーザーマニュアルのN-gram parserセクションを参照して下さい。

私達はこの新しい機能が役立つことを願っています！私たちはMySQL 5.7を通して全文検索がCJK対応したことをとても嬉しく思っていますし、この改善はMySQL 5.7の改善点の中でも大きなものです。ご質問があれば、このブログにコメントして頂くか、サポートにお問合せ下さい。もし、バグを見つけた場合は、このブログにコメントして頂くか、バグレポートに投稿して頂くか、サポートにお問合せ下さい。

いつもMySQLをご利用いただき、ありがとうございます！