タグ: 全文検索 を抽出しています。
Total: 5

FULLTEXTインデックス(MyISAM)から転置インデックス(InnoDB)へ

ブログ | 2010/11/28 23:04
全文検索を実装するときに、転置インデックス的なやり方(そんな名前がついてるとか知らなかったけれど)は検討したのだけれど、どんでもないレコード数になるから、扱いづらくて遅いんじゃないかと思ってました。

で、実験中。

table
CREATE TABLE IF NOT EXISTS `inno_node_index` (
 `ngram` varchar(3) NOT NULL,
 `nid` int(11) NOT NULL,
 PRIMARY KEY (`ngram`,`nid`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
nidは、65万件くらい。
1nidに対して、ngram化した文字が1000あったとして、レコード数は6億レコードとかになる。

insertは、10万nidで15分くらいだったから、許容範囲だろうか。

検索クエリー
SELECT SQL_NO_CACHE nid FROM `inno_node_index`
WHERE ngram IN ('差出箱','出箱7','箱7号')
GROUP BY nid
HAVING COUNT(nid) = 3;

FULLTEXTの場合は、こんな感じだったもの。
SELECT SQL_NO_CACHE nid FROM `new_node_search`
WHERE match(ngram) against ('+差出箱 +出箱7 +箱7号'  in boolean mode);

さあ、どんな結果がでるのだろう。
ただいま、データinsert中。

MyISAMで更新の多いFULLTEXTインデックスは、すぐにオーバーヘッドが発生するし、修復もハイコストだし、なんとかしたいというのが動機。InnoDB化がきっかけ。
▼追記 2010/11/29 01:10
6億レコードもなかった。70,295,304レコード。(InnoDBはレコード数をカウントするのが遅いことを知る)

では、検索スピード比較(3文字ngram)
数日前のポストマップのインデックスからです。
「差出箱7号」
InnoDB転置: (2,622 合計, クエリの実行時間 1.0055 秒)
FULLTEXT: (2,624 合計, クエリの実行時間 0.0731 秒)

「差出箱5号」
InnoDB転置: (87 合計, クエリの実行時間 1.0579 秒)
FULLTEXT: (87 合計, クエリの実行時間 0.0633 秒)

「kuwa」
InnoDB転置: (1,369 合計, クエリの実行時間 0.0236 秒)
FULLTEXT: (1,369 合計, クエリの実行時間 0.1547 秒)

「たぬき」
InnoDB転置: (37 合計, クエリの実行時間 0.0007 秒)
FULLTEXT: (37 合計, クエリの実行時間 0.0222 秒)

「愛」
InnoDB転置: (43,252 合計, クエリの実行時間 0.0014 秒)
FULLTEXT: (43,257 合計, クエリの実行時間 0.0558 秒)

「東京都港区赤坂」
InnoDB転置: (4 合計, クエリの実行時間 0.0962 秒)
FULLTEXT: (4 合計, クエリの実行時間 0.0048 秒)

「万博」
InnoDB転置: (83 合計, クエリの実行時間 0.0029 秒)
FULLTEXT: (83 合計, クエリの実行時間 0.0514 秒)

「白木屋」
InnoDB転置: (29 合計, クエリの実行時間 0.0187 秒)
FULLTEXT: (29 合計, クエリの実行時間 0.0267 秒)

「傾いている」
InnoDB転置: (37 合計, クエリの実行時間 0.1045 秒)
FULLTEXT: (37 合計, クエリの実行時間 0.1354 秒)

「そんなことじゃないかと思っていました。」
InnoDB転置: (1 合計, クエリの実行時間 0.5424 秒)
FULLTEXT: (1 合計, クエリの実行時間 0.1139 秒)
スピードに関しては、十分という気がする。3文字までなら転置の方が速くて、それ以上はFULLTEXTという結果かな。

データ容量に関しては、
InnoDB転置: 3.8G
FULLTEXT: 1.6G
倍くらいなら、気にならない。
▼追記 2010/12/6 01:54
tableのindexだけれど、
PRIMARY KEY (`nid`,`ngram`)
こうしておかないと、nidで検索したときにインデックスが使用されない。順番大事。
http://dev.mysql.com/doc/refman/5.1/ja/multiple-...

検索を更新するときに、nidで検索して削除しなければならないから。
▼追記 2010/12/6 13:19
これはとんでもない勘違いだ。検索でindexが使用できなくなるじゃないか。
CREATE TABLE IF NOT EXISTS `inno_node_index` (
 `ngram` varchar(3) NOT NULL,
 `nid` int(11) NOT NULL,
 PRIMARY KEY (`ngram`,`nid`),
 KEY `nid` (`nid`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
nidに追加でindexをつけるしかなさそうだ。

MySQL,fulltextインデックス,Ngram化のまとめ。

ブログ | 2009/9/30 00:46
少し説明的に。
MySQLには、fulltextという全文検索用のインデックスがあります。
ただ、日本語は単語単位で区切られていないので、なんらかの方法で区切る必要があります。区切り方には、形態解析で区切る方法と、意味なんて考えずに1文字とか2文字とかで区切っていくNgramという方式があります。

(あ、その前に、検索対象が数万件くらいなら、「REGEXP」で検索するのがいいと思います。速いし、おそらく厳密だし。)

で、今までは形態解析の方でやってました(mecabなるものを利用)。
ただ、このインデックス化は、「アイスクリーム」を検索したい時に、インデックスに「アイスクリーム」しかないと、「アイス」という検索ではヒットしないというところが難点でした。

初期導入時は、、なんとなく意味で区切った方がインデックス文字列が少なくていいし、優れているのではないかというのが選択動機だったと思います。

さて、Ngram化。

1) まずインデックス文字列の作り方。PHPです。
function ngramIndex($str,$wlen){
 $str = preg_replace('/[\r\n  ]/u','',$str);
 $len = mb_strlen($str);
 $n = array();
 for($i=0; $i < $len; $i++){
   for($a=1; $a <= $wlen; $a++){
     $n[] = mb_substr($str,$i,$a);
   }
 }
 $n = array_unique($n);
 return $n;
}

$str がNgram化したい文字列。
$wlen は、何文字までインデックス化するか(僕は、5にしてみた)

で、配列が返ってくるので、
$str = ngramIndex($str,5);
$str = mysql_real_escape_string(implode(' ',$str));
こんな感じで、$strをMySQLにインサートします。

2) 検索文字列の作り方。PHPです。
function ngram($str){
 $len = mb_strlen($str);
 if($len > 5){
   $n[] = mb_substr($str,0,5);
   if($len > 10){
     for($i=5; $i <= $len-5; $i++){
       if($i%5 == 0){
         $n[] = mb_substr($str,$i,5);
       }
     }
   }
   $n[] = mb_substr($str,-5,5);
   $n = array_unique($n);
 }else{
   $n[] = $str;
 }
 return $n;
}
こんなことにしました。

「マルボロ」-> 「マルボロ」
「クリーニング」-> 「クリーニン, リーニング」
「トールラテで腹下ルのです」-> 「トールラテ, で腹下ルの,下ルのです」

このように配列が返ってくるので、これを展開して、
SELECT ~~~~ WHERE MATCH (ngram) AGAINST ('+クリーニン +リーニング' IN BOOLEAN MODE) ~~~
こんなクエリーにセット。

実際は、複数単語で、AND、OR、除外やらという検索をさせるから、そのあたりはグルグリ関数を書きました。

さて、結果はいかに。今、ポストマップのインデックスを再作成中。
現在、482,436件くらいのデータのようです。
http://postmap.org/list

Rottelも後日、変更していきます。
▼追記 2009/9/30 10:36
5文字までやってたら、longtext型の4294967295byteを超えてエラーで止まった。とりあえず4文字にして、insertする文字数をちゃんと容量内にするように書いて継続。

インデックス作りはもう少し研究が必要だ。
▼追記 2009/9/30 11:44
あー、インデックスづくりで、遅延だ、遅延だ。
▼追記 2009/9/30 15:15
インデックスづくりは休み休みやろう。

...
コメントの検索って、あれ使ってるのかな。
▼追記 2009/10/1 03:29
インデックス作りをなめてた。
朝までに終わるかな・・・。

ポストが終わったら、電話やって、Rottelに行こう。
▼追記 2009/10/2 00:29
なんか、検索スピードが納得いかない。
ヒット件数が少ないと速いみたいだけれど。

インデックスが大きすぎるのが原因のような気がするので、3文字に減らしてみる。
▼追記 2009/10/2 03:05
インデックス更新を回して寝る。
いろんなサイトでDBが遅延してしまいますが、すみません。(投稿したものがすぐに出てくなかったりすると思います)

朝までに終わらない気もする。
▼追記 2009/10/2 19:08
200件インデックス作成したら、30秒スリープしてDBの同期を待つ。これでいい感じ。FULLTEXTインデックスの更新はなかなか遅いらしく、テストするのも何かと大変だ。

文字列のNgram化

ブログ | 2009/9/29 02:43
function ngram($str){
 $str = preg_replace('/[\r\n  ]/u','',$str); //...(1)
 $len = mb_strlen($str);
 $n = array();
 for($i=0; $i < $len-1; $i++){
   $n[] = mb_substr($str,$i,2);  //....(2)
 }
 $n = array_unique($n);   //...(3)
 return $n;
}
こんな感じかな。

(1) 改行とスペースの削除
(2) 2文字ずつ配列に
(3) 重複をまとめる

で、配列で返す。
▼追記 2009/9/29 04:15
2文字のインデックスだけだと、「駅」みたいな1文字が検索できないんだな。
$n[] = mb_substr($str,$i,1);
も追加しとくか。
▼追記 2009/9/29 22:58
1文字2文字だけだと、長いフレーズが遅いと思う。
ということで、1〜5文字でインデックス化したる。

phpからmecabのわかち書き

ブログ | 2009/1/10 20:04
file_put_contents($tmpfile,$str);
return shell_exec('/opt/local/bin/mecab -O wakati '.$tmpfile);
こんな感じで、ファイルを作ってみたのだけれど、
http://kudelab.com/archives/15
のソースでは、ファイル必要なし。

-O wakati を足してみよう。

$descriptorspec = array(
 0 => array("pipe", "r"),
 1 => array("pipe", "w")
);
$process = proc_open("/opt/local/bin/mecab -O wakati", $descriptorspec, $pipes);

if(is_resource($process)){
 fwrite($pipes[0], $str);
 fclose($pipes[0]);
 $result = stream_get_contents($pipes[1]);
 fclose($pipes[1]);
 proc_close($process);
 return($result);
}

「神奈川県」をどうやって検索しよう。
「神奈川県」は「神奈川 県」と分かれるから、「神奈川」ではヒットしても「神奈川県」でヒットしない。検索文字列もわかちして「+神奈川 +県」で一応ヒットするけれど、「神奈川と千葉県は東京湾を挟んでいる」がヒットしてしまってよいのだろうか。

あとで考えよう。

my.cnfに
ft_min_word_len=1
は忘れずに。

mysqlで日本語全文検索の効果 (Nega Diary)

ブックマーク | 2008/12/24 02:42 | feed
http://www.ironhearts.com/diary/archives/000868....
phpで文字列を16進数にするには
bin2hex(str);
▼追記 2008/12/25 11:37
研究結果。
REGEXPの方が速かった・・・
前 | 1 | 次

Rottel内コンテンツ

ユーザー一覧

Rottelとは?
利用規約
開発飲料
利用者の声
ヘルプ
close