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

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

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

まあ、当然ですよね〜


f:id:treeapps:20180418131549p:plain

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と形態素解析を組み合わせて、中間部分を頑張ってヒットさせる、という形で中間一致検索もどきを実現する事になります。