mysqlで疑似的にtrieを実現する方法

mysqlで疑似的にtrieを実現する方法のメモ。

ウェブサービスで、処理対象とする URL が何らかの除外したい URL に前方一致でマッチするかを判定したい場合、
除外URLの数が多い場合、効率よく判定を行う必要があります。

例えば、test.com/abcdef/ghi が mysql に登録されたURLにマッチするかを調べる場合、
以下のような select 文で前方一致の検索を行うことができます。

select * from {table名} where 'test.com/abcdef/ghi' like concat({URLのカラム名}, '%');

しかし、上記の select 文では、mysql に登録されている各レコードの URL カラムに対して
前方一致で文字列マッチの判定が行われ、レコード数分の検索が行われることになります。
そのため、レコード数に応じて処理速度が低下します。


以下は、mysql で trie 相当の機能を実現する方法案です。
ある URL が、除外したい URL にマッチするかどうかの判定を行う例で考えます。

まず、除外URL に URL に使用されない文字を追加して固定文字列長の URL を生成します。
例えば、除外URL の文字列長が15文字で、除外 URL が test.com/abc の場合、
URLに使用されない文字として '@' を追加して以下のような文字列を生成し、DBに登録します。

test.com/abc@@@

判定対象の URL (= 'test.com/abcdefg') が除外対象の URL かを判定するために、
以下の検索式でテーブルを検索します。

select * from {テーブル名} where {URLのカラム名} regexp '^t[e@][s@][t@][\.@][c@][o@][m@][/@][a@][b@][c@][d@][e@][@f][@g]';

正規表現の ^ で URL の文字列の先頭にマッチさせ、次の t は URL の先頭文字列です。
前方一致でのマッチを行うため、一文字目は判定対象の URL の先頭文字の t が
必ず入っていることを想定しています。

次の [e@] は "test.com の e または 使用されない文字 @" にマッチする場合で、
前方一致の URL として te または t@ が登録されている場合にマッチします。
t@ にマッチするのは前方一致の URL が t のみの場合で、DBに登録された値が "t"+"@"x15 の場合に相当します。
[s@] 以降も同様です。


以下、検証です。

URLのテーブルとして、以下を定義して適当にテスト用のURLを登録します。

create table url_trie_test (
       url   varchar(512) not null,
       index(url)
);

そして、以下の explain を実行します。

explain select * from url_trie_test where url regexp '^t[e@][s@][t@][\.@][c@][o@][m@][/@][a@][b@][c@][d@][e@][f@][g@][h@][i@][j@][/@][k@][l@][m@]'\G

すると、explain の結果は以下のようになり、インデックスが使われた検索になっているようです。

  select_type: SIMPLE
        table: url_trie_test
         type: index
possible_keys: NULL
          key: url
      key_len: 514
          ref: NULL
         rows: 2691
        Extra: Using where; Using index

前方一致の url として約2700件が登録されている状態で、上記の select 文を実行すると、以下のようになりました。

mysql> select * from url_trie_test where url regexp '^t[e@][s@][t@][\.@][c@][o@][m@][/@][a@][b@][c@][d@][e@][f@][g@][h@][i@][j@][/@][k@][l@][m@]'\G
*************************** 1. row ***************************
url: test.com/abc@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
1 row in set (0.08 sec)

mysqlのインデックスを使って、疑似的に trie の検索ができているようです。