Tritonnとは

TritonnはMySQLから全文検索エンジンSennaを利用可能にするための改造を行うプロジェクトです。

以前はMySQLに当てるパッチを開発するプロジェクトでしたが、現在は1歩進めてMySQLの改造版ソースを開発するプロジェクトとして活動しています。

簡単に言うと以下の2点からTritonnプロジェクトが必要と考えています。

• MySQLには日本語データに対する全文検索を行うための十分な機能が実装されていません。
• MySQLでは全文検索を行うための実装面での十分な高速化が行われていません。

どんな機能が不足しているのか

現在、MySQLには日本語環境で使用するための十分な全文検索機能が実装されていません。

例えば英語の場合、以下のように全文検索をすることができますが、、、

[test] > SET NAMES utf8;
Query OK, 0 rows affected (0.00 sec)

[test] > CREATE TABLE t1 (c1 TEXT, FULLTEXT INDEX idx (c1)) ENGINE = MyISAM DEFAULT CHARSET utf8;
Query OK, 0 rows affected (0.00 sec)

[test] > INSERT INTO t1 VALUES ("I have a pen."), ("May I Help You?"), ("Have a nice day.");
Query OK, 3 rows affected (0.00 sec)
Records: 3  Duplicates: 0  Warnings: 0

[test] > SELECT * FROM t1 WHERE MATCH(c1) AGAINST("nice");
+------------------+
| c1               |
+------------------+
| Have a nice day. |
+------------------+
1 row in set (0.00 sec)

日本語の場合、結果が0件になってしまいます。

[test] > drop table t1;
Query OK, 0 rows affected (0.00 sec)

[test] > CREATE TABLE t1 (c1 TEXT, FULLTEXT INDEX idx (c1)) ENGINE = MyISAM DEFAULT CHARSET utf8;
Query OK, 0 rows affected (0.00 sec)

[test] > INSERT INTO t1 VALUES("私はペンを持っています。"), ("いらっしゃいませ〜"), ("良い一日を。");
Query OK, 3 rows affected (0.00 sec)
Records: 3  Duplicates: 0  Warnings: 0

[test] > SELECT * FROM t1 WHERE MATCH(c1) AGAINST("良い");
Empty set (0.00 sec)

なぜこのようなことが起きるかというと、これはMySQLのFULLTEXTインデックスのキーワード抽出を行うパーサが「半角スペースで区切られているものをキーワードとして認識する」という実装になっているためです。欧米の言語は通常、単語と単語の間は半角スペースで区切られていますので十分機能しますが、日本語の場合はそうではないためキーワードの抽出を行えません。

例えば、「私はペンを持っています。」を例にすると、あらかじめ「私 は ペン を 持って いま す 。」のように半角スペースで区切っておけば(分かち書きと言います）現在のMySQLでも日本語全文検索を行うことができます。しかしMySQLに入力するデータをあらかじめ分かち書きするのは、その分処理が増えるのでできれば避けたいですし、オリジナルのデータと別に分かち書きしたデータを用意しなければならないのは効率が良くありません。

こうした問題があることから、FULLTEXTインデックスを使った全文検索ではなく、LIKE演算子を使った部分一致検索を用いるケースもあります。

[test] > SELECT * FROM t1 WHERE c1 LIKE "%良い%";
+--------------------+
| c1                 |
+--------------------+
| 良い一日を。       |
+--------------------+
1 row in set (0.00 sec)

このようにLIKE演算子への引数の先頭と末尾にワイルドカード'%'を指定することで、文中のどの位置に指定のキーワードが含まれていたとしても、捜し出すことができます。

しかしながら、このLIKE演算子による部分一致検索には、別の問題があります。部分一致検索を行う場合、インデックスを一切使用することができなくなってしまうため、テーブルのフルスキャンが発生します。これはテーブルサイズが非常に小さい時には問題にならないかもしれませんが、テーブルサイズの増大と共に、あっというまに性能問題となって表に出てきます。

従って、MySQLで日本語環境で全文検索を行うためには、何か新しい手段が必要となっていました。Tritonn（MySQL+Senna）はまさにこれら問題を解決するためのものです。

どんな実装上の高速化が必要なのか？

MySQLの全文検索用インデックス(FULLTEXTインデックス)は「転置インデックス」という方式に基づいた実装が行われています。転置インデックスとは、簡単に言うと「任意のキーワードを含むレコードの識別子をあらかじめ記録しておく形式のインデックス」というものです。

例えば"apple"というキーワードがあったとします。この"apple"を含むレコードを検索する時、もし転置インデックスがなければ、テーブルをフルスキャンして、1レコードずつ"apple"が含まれているかどうかをチェックする必要があります。ここで転置インデックスがある場合、転置インデックス内に"apple"が登録されているかどうかをまず走査し、見つかった場合にはそこに既に"apple"を含むレコードの識別子が記録されていますので、テーブルをスキャンすること無しに、該当のレコードを特定できます。

しかしながら、多くのケースではこれだけでは十分ではありません。

上記の例のように「りんご」を検索キーワードとする場合はおそらく単純な転置インデックスにより高速に処理することができますが、例えば「デジタル式腕時計」という検索キーワードで検索する場合を考えてみましょう。

「りんご」と同様に「デジタル式腕時計」というキーで転置インデックスに登録していれば問題ありませんが、「デジタル式腕時計」は以下の4つの単語に分解されて転置インデックスに登録されることが想定されます。

• デジタル
• 式
• 腕
• 時計

なぜなら、このように分解しておかないと「デジタル」で検索されたとき、あるいは「時計」で検索されたときに対応できないからです。

単純な転置インデックスの場合、「デジタル式腕時計」で検索された時、まず「デジタル」を含むレコードを探します。これは転置インデックスを走査することで効率よく見つけることができます。しかしここで見つかったレコードは例えば「デジタルカメラ」を含むレコードがヒットしている可能性もあるわけです。そこで、一度見つけたレコード群の中から、さらに「式」「腕」「時計」を順番通りに含んでいるかどうかをチェックしていくことになります。

この時、最初に転置インデックスを使って見つけたレコード群の数が少なければさほど大きな処理とはなりませんが、多数のレコードがヒットするようなメジャーな単語で検索する場合にはこの部分の処理時間が問題となります。またこれはレコード総数が増えるほど、問題が顕著になっていきますので、大容量データに対する全文検索としては単純な転置インデックスでは弱いということになります。

この問題を回避するため、Sennaでは「完全転置インデックス」という方式でインデックスを実装しています。完全転置インデックスとは、インデックス内に各キーワードを含むレコードの識別子だけでなく、そのレコード内でのそのキーワードの出現位置についても記録する方式のインデックスです。

先ほどの「デジタル式腕時計」の例でいうと、完全転置インデックスの場合は「デジタル」「式」「腕」「時計」それぞれのインデックスにレコード識別子と位置情報が記録されていますので、インデックスを走査するだけで「デジタル式腕時計」を含むレコードを特定することができます。これによりテーブルからのレコード読み込み数を最小化することができ、大容量データでの全文検索に強い構造になっています。

この反面、完全転置インデックスは単純な転置インデックスに比べるとインデックスが保持する情報が増えるため更新のオーバーヘッドの増加とインデックスファイルサイズの増加が起きるデメリットがあります。しかしながら、大容量データに対する全文検索を考慮すると、完全転置インデックスの方が総合的に見てメリットが大きいと見ています。

Tritonnでは、MySQLのFULLTEXTインデックスの処理にMyISAMのビルトインのFULLTEXTではなく、Sennaを使うようにソースコードを改変しています。

またSennaを管理するためのSQLコマンドや変数などを追加するために、MySQLの上位層のソースファイルに対しても改変を行っていますが、本質的な部分においては基本的にはMyISAMに対する改造という内容になっています。

従いまして、MySQLにこのパッチを適用した場合、変わるのは基本的にはMyISAMのFULLTEXTインデックスの振る舞いのみで、後はこれまでと同様となっています。またこの図をご覧頂くとお分かりになるかと思いますが、MySQLへアクセスするアプリケーションから見ると、MySQLの上位層がSennaを隠蔽しているため、アプリケーション側で特にSennaを意識する必要はありません。

従って、これまでとほぼ同じ感覚でMySQLを利用することができます。

元々Sennaを使っている人の多くはMySQL+Sennaを使っている人だと思いましたので、特にTritonn専用のMLは設けていません。何かありましたら、こちら（Senna本家のML）へお越し下さい。

• senna-dev@sourceforge.jp

mysql-senna-arch.gif
download