SH2の日記

実験エントリです。

予習してみる

「転置インデックス」というキーワードで検索して、しばらく勉強してみます。

• 転置インデックス - Wikipedia
• mixi Engineers’ Blog » 転置インデックスを実装しよう
• ASCII.jp：悟空、秘剣「転置インデックス」を手に入れる ｜Googleはなぜ的確に探せるのか？
• [を] 転置インデックスによる検索システムを作ってみよう！
• 転置インデックスで学ぶ検索エンジンの中身アプリ - 睡眠不足？！

うーんなるほど。分かったような分からないような。

作ってみる

とりあえず、Twitter4Jを使ってこんなデータを用意しました。ちなみに人選は漢(オトコ)のコンピュータ道: MySQLerのTwitterアカウントまとめ。を参考にさせていただきました。

5707049458,2009-11-14 20:28:34,sakaik,@hbstudy  あ。そうですか〜。教えていただき
5707129844,2009-11-14 20:35:11,kazuho,InnoDB 1.0.5でバッファプールのGenerational
5707141572,2009-11-14 20:36:09,kazuho,RT @higepon: RT @yukichi: 「フリーランス」
5707146470,2009-11-14 20:36:34,_Fake,@_yuyu どうしてこうなった
5707159628,2009-11-14 20:37:41,hirose31,恵比寿でスーツコスなう
5707167760,2009-11-14 20:38:22,kazuho,old領域はデフォルトで37%。ロードしたデータ
5707190203,2009-11-14 20:40:17,stanaka,色々カスタマイズ可能な項目が増えるのは基
5707246432,2009-11-14 20:45:00,sh2nd,いきたかった #hbstudy
5707324541,2009-11-14 20:51:27,kazuho,mtstat は Monty Taylor's stat の略なのかな
5707385902,2009-11-14 20:56:23,_Fake,ブレーカー落ちた…

次に、タイムラインを格納するためのテーブルを作ります。

mysql> DESC timeline;
+-------------+--------------+------+-----+---------+-------+
| Field       | Type         | Null | Key | Default | Extra |
+-------------+--------------+------+-----+---------+-------+
| id          | bigint(20)   | NO   | PRI | NULL    |       |
| created_at  | datetime     | YES  |     | NULL    |       |
| screen_name | varchar(15)  | YES  |     | NULL    |       |
| text        | varchar(140) | YES  |     | NULL    |       |
+-------------+--------------+------+-----+---------+-------+
4 rows in set (0.00 sec)

もう一つテーブルを作ります。こういうのを転置インデックスと言うんだそうです。

mysql> DESC timeline_i;
+--------+------------+------+-----+---------+-------+
| Field  | Type       | Null | Key | Default | Extra |
+--------+------------+------+-----+---------+-------+
| bigram | varchar(2) | NO   | PRI |         |       |
| id     | bigint(20) | NO   | PRI | 0       |       |
+--------+------------+------+-----+---------+-------+

timelineテーブルにトリガを仕掛けます。

DROP TRIGGER IF EXISTS timeline_create_bigram;
DELIMITER //
CREATE TRIGGER timeline_create_bigram
AFTER INSERT ON timeline FOR EACH ROW
BEGIN
 DECLARE text_length INT;
 DECLARE text_index INT;
 
 SET text_length = CHAR_LENGTH(NEW.text);
 SET text_index = 1;
 
 WHILE text_index < text_length DO
  INSERT IGNORE INTO timeline_i (bigram, id)
         VALUES (SUBSTRING(NEW.text, text_index, 2), NEW.id);
  SET text_index = text_index + 1;
 END WHILE;
END;
//
DELIMITER ;

データロードを行います。

mysql> LOAD DATA LOCAL INFILE 'timeline.dat' INTO TABLE timeline;
Query OK, 35732 rows affected (1 min 34.76 sec)
Records: 35732  Deleted: 0  Skipped: 0  Warnings: 0

だいぶ遅いですけど、うまくロードできたみたいです。データロード後のテーブルは以下のようになります。

mysql> SELECT id, created_at, screen_name, LEFT(text, 20)
    -> FROM timeline ORDER BY id LIMIT 10 OFFSET 32000;
+------------+---------------------+-------------+---------------------------------------+
| id         | created_at          | screen_name | LEFT(text, 20)                        |
+------------+---------------------+-------------+---------------------------------------+
| 5706909826 | 2009-11-14 20:16:42 | sakaik      | 参加できなかったんだけど、ustないのん |
| 5706917932 | 2009-11-14 20:17:26 | kazuho      | オチを先に言うの禁止www #hbstu        |
| 5706918515 | 2009-11-14 20:17:30 | _Fake       | @_yuyu もうだまされないぞ！           |
| 5706994272 | 2009-11-14 20:23:52 | _Fake       | @_yuyu 日本語でお願いします！         |
| 5707049458 | 2009-11-14 20:28:34 | sakaik      | @hbstudy  あ。そうですか〜。教        |
| 5707129844 | 2009-11-14 20:35:11 | kazuho      | InnoDB 1.0.5でバッファプール          |
| 5707141572 | 2009-11-14 20:36:09 | kazuho      | RT @higepon: RT @yuk                  |
| 5707146470 | 2009-11-14 20:36:34 | _Fake       | @_yuyu どうしてこうなった             |
| 5707159628 | 2009-11-14 20:37:41 | hirose31    | 恵比寿でスーツコスなう                |
| 5707167760 | 2009-11-14 20:38:22 | kazuho      | old領域はデフォルトで37%。ロードし    |
+------------+---------------------+-------------+---------------------------------------+
10 rows in set (0.04 sec)

mysql> SELECT bigram, id FROM timeline_i
    -> ORDER BY bigram, id LIMIT 20 OFFSET 1280000;
+--------+------------+
| bigram | id         |
+--------+------------+
| 行性   | 2627699213 |
| 行情   | 4696663607 |
| 行手   | 6165165693 |
| 行振   | 1968230572 |
| 行支   | 5609167583 |
| 行支   | 5751891393 |
| 行政   | 4309254243 |
| 行政   | 5793749538 |
| 行数   |  814006785 |
| 行数   |  895299155 |
| 行数   | 3836569341 |
| 行数   | 3931668910 |
| 行数   | 4496147540 |
| 行方   |  773875969 |
| 行方   | 3121814754 |
| 行方   | 3976865730 |
| 行日   | 6055373012 |
| 行時   |  802293533 |
| 行時   | 3275845988 |
| 行時   | 3275991644 |
+--------+------------+
20 rows in set (0.75 sec)

検索してみる

普通にLIKE検索してみると、こんな感じです。

mysql> SELECT id, created_at, screen_name, text FROM timeline
    -> WHERE text LIKE '%味噌ラーメン%'\G
*************************** 1. row ***************************
         id: 5007144696
 created_at: 2009-10-20 10:46:49
screen_name: hirose31
       text: @sugizou 昼はねぎ味噌ラーメンにしまっす！
1 row in set (0.07 sec)

転置インデックスを組み合わせると、こうなります。

mysql> SELECT t.id, t.created_at, t.screen_name, t.text
    -> FROM timeline t INNER JOIN timeline_i i ON t.id = i.id
    -> WHERE i.bigram = '味噌'
    -> AND t.text LIKE '%味噌ラーメン%'\G
*************************** 1. row ***************************
         id: 5007144696
 created_at: 2009-10-20 10:46:49
screen_name: hirose31
       text: @sugizou 昼はねぎ味噌ラーメンにしまっす！
1 row in set (0.00 sec)

おー、速くなっているみたいですね！

測定してみる

適当に作ったわりには効果があるようなので、きちんと測定してみました。

• 試験プログラム：Javaで自作
• 同時接続数：1
• 試験方法：ネットワーク越しにクエリを連続実行し、レスポンスタイムの中央値を取得
• CPU：Pentium4 2.8GHz HTなし
• RAM：DDR-266 SDRAM 1GB
• HDD：IDE 3.5inch 7,200rpm 80GB
• OS：CentOS 5.4 32bit
• RDBMS：MySQL Community Server 5.1.41＋InnoDB Plugin 1.0.5

今まではVMwareの環境を使っていたのですが、ベンチマークをするのに仮想化はないだろうということで古いPCを引っ張り出してきました。しばらくこれを使っていこうと思います。

いろいろな検索語で試してみたところ、以下のような結果になりました。

このように、今回試した検索語においてはすべて転置インデックスを使った方が速いという結果が出ました。「http://」の場合は全体の12%もヒットしてしまうのですが、それでもLIKE検索でフルスキャンを行うよりは速いようです。グラフにすると傾向が見えてきます。

もう少し工夫すれば、使いどころが出てくるかもしれませんね。