InnoDBのフレーズ検索はなぜ遅いのか（転置インデックスと完全転置インデックス）

前回の記事で書いたようにInnoDBによる全文検索では、（特にNGram検索で）「フレーズ検索」によるパフォーマが悪化しやすいです。
quotto.hatenablog.com

「フレーズ検索」とは、指定した順番で単語が出てくる文章のみを抽出する方法です。
例えば「メロン」という言葉が含まれる文章があり、文章は2gramで分解されているとします。
「メロン」は3文字ですから、発行すべきSQLはこんな感じです。

select * from fruits where match(desctext) against('"メロ ロン"');

2gramで分解した場合、「メロン」は「メロ」「ロン」という順番で分解されているはずです。
フレーズ検索では、「""」（ダブルクウォート）内にブランク区切りで単語を連ねることで、「その順番で単語が出現する文章」を検索します。

ではなぜ、InnoDBのフレーズ検索が遅いのか？
それはInnoDBのfulltext indexが「転置インデックス」であるためです。
以下、こちらのサイトから得た情報です。
http://lab.bizreach.co.jp/51/

転置インデックスとは、「ある単語が出てくる文章（レコード）を記憶する」インデックスです。
冒頭の例でいくとInnoDBは「メロ」や「ロン」がどのレコードの文章に出現するかを把握しています。
そのためひとつの単語の指定であれば、比較的早く検索できます。

しかし転置インデックスでは「文章の単語の並び順」まではわからないため、「メロの次にロンがくる」というようなフレーズ検索を行った場合、検索時に逐一並び順をチェックする必要があり、パフォーマンスが低下してしまうのです。

そこで完全転置インデックスの登場です。
完全転置インデックスは「その単語が文章のどの位置に出現するか」も記憶しています。
そのためフレーズ検索した場合にも、全てインデックスから引っ張ってこられるためパフォーマンスが向上します。

当然ながら完全転置インデックスはインデックス自体の容量をより多く必要とし、インデックスの作成にも時間を要するためデータ更新時のオーバヘッドは大きくなります。

サードパーティのストレージエンジンであるMroongaでは完全転置インデックスが使われています。

ということで、次回はInnoDBとMroongaのパフォーマンス比較を行ってみたいと思います。