読者です 読者をやめる 読者になる 読者になる

文系プログラマによるTIPSブログ

文系プログラマ脳の私が開発現場で学んだ事やプログラミングのTIPSをまとめています。

何故MySQLは中間・後方一致検索でインデックスが効かないのか

mysql solr

しょうもないトピックです。
MySQLは何故中間一致検索、又は後方一致検索するとフルスキャンしてしまうか解りますか?
簡単です。

中間部分の索引を保持しても効率よくbtreeを辿れないからです。

例えば現実世界の辞書を想像して下さい。
おまわりさんーーーー10p
こわいおにいさんーー12p
めがいってるひとーー20p

これは普通ですね。ではこれならどうですか?
・まわ・・・・・ーー10p
・・いお・・・・ーー12p
・・・・てる・・ーー13p

は?(威圧)と思いますよね。
この中間部分の索引(インデックス)をメモリ空間に格納する時、
一体どこに格納すれば高速に検索できるか解りますか?
解りませんね。技術的には中間部分の索引も保存できるでしょうが、上手く格納できない、
つまり高速にbtreeを辿れないのです。高速に辿れないなら検索も低速、
つまりフルスキャンするのと同等なわけです。だからlike '%hoge%' は必ずフルスキャンなのです。

これは後方一致にも言える事です。
・・・りさんーーーー10p
・・・おにいさんーー12p
・・・ってるひとーー20p

は?(威圧)と思いますよね。中間一致と全く同じ理屈です。
ただ、これは全く逆方向のbtreeがあれば、前方一致でインデックスが有効になるのと
同じ理屈でインデックスが効きそうですが、まだその機能はありません。

RDBだけでなく、全文検索エンジンであるsolrについても少し触れてみます。

solrの後方一致検索

実はsolrで高速に後方一致検索する事は可能です。
WildcardQueryを使えば可能ですが、MySQLと同じく索引が使えないので検索は非常に遅いです。
ReverseStringFilter (Lucene 3.5.0 API)
luceneにReverseStringFilterというフィルタがあり、文字列を反転させる事ができるのです。
これを利用して、通常のフィールドと別にもう一個フィールドを用意し、
そのフィールドにはReverseStringFilterを適用したデータを入れてしまうのです。
その反転フィールドに対して前方一致検索かければ、後方一致検索になるという仕組みです。

フィールドA -> おまわりさん
フィールドB -> んさりわまお

フィールドBに対して「んさ*」と検索すれば実質後方一致検索ですね。
ユーザには「さん」という文字列を入力させ、システム側で「んさ」に反転して前方一致検索します。

solrの中間一致検索

solrの中間一致検索ですが、RDBと全く同じ形にはできません。
NGramTokenizerFactoryと形態素解析を組み合わせて、中間部分を頑張ってヒットさせる、
という形で中間一致検索もどきを実現する事になります。
エキスパートのためのMySQL[運用+管理]トラブルシューティングガイド

エキスパートのためのMySQL[運用+管理]トラブルシューティングガイド


Apache Solr 4 Cookbook

Apache Solr 4 Cookbook