先日の正規化ネタの件でid:teramakoさんがdel.icio.usでの例を紹介して下さったので移行してみた。

今までの構造

今までこのブログで記事とタグの関係がどうなっていたかというと、教科書どおりに正規化していた。ただ、タグそのものにIDをふって [items] - [item_tag] - [tags] という構造ではなくて、[items] - [tags]という形になっていた。以下のような感じ:

items

id	title	body	date
1	地球空冷化	<p>最近、私の ...	2001-08-04 00:01:00
2	台風一過	<p>幸運なことに ...	2001-08-22 00:01:00

tags

item_id	tag
1	生活
1	自分のこと
2	2ch
2	コロッケ
2	台風

この構造の問題点は、たとえば「Opera」と「ノウハウ」を含んで「演劇」を含まない記事を出したい! というのが面倒なこと。そのかわり正規化されているからとってもリレーショナル。ある時期に頻出するタグを求めるみたいなことがTF-IDFの応用ですぐできる。HarmanとSparck Jonesによる正規化を組み合わせると、ある期間に頻出するタグiは、log2(タグiのある期間内での登場数+1) / log2(ある期間内に登場したタグの種類数) * (log2(全記事数 / タグiがつけられた記事数) + 1)で求められる。ちゃんと正規化されていればこの計算をSQLで行うのは簡単だが、1セルにすべて閉じ込めてしまうととたんに面倒になる。ただ、そんな頻度の少ない処理が面倒になることよりもいつも行う処理が1つのテーブルを参照するだけですむことのほうが重要だ。記事のCRUDが1テーブルでできるようになれば、記事の更新をphpMyAdminから行うことだってできる。

移行作業

ということで、"MySQLicious" solution を目指す。以下のような感じ:

items

id	title	body	date	tags
1	地球空冷化	<p>最近、私の ...	2001-08-04 00:01:00	生活 自分のこと
2	台風一過	<p>幸運なことに ...	2001-08-22 00:01:00	2ch コロッケ 台風

これをSQLだけでやるにはどうすればいいか。カラムの更新なんだからUPDATEだろjkと思い、下のようなクエリを発行したら#1242 - Subquery returns more than 1 rowと怒られた:

UPDATE items SET tags = concat(tags, ' ', (SELECT tag FROM tags WHERE items.id = tags.id));

これが数値だったら、group byしてsum()したのをupdateすれば終わってたのになー。そんなこといってもしょうがないのでもう少し考えてみたところ、on duplicate keyを使う案をひらめいた:

INSERT INTO items(id, tags) SELECT old_items.id, tag FROM old_items LEFT JOIN tags USING (id) ON duplicate KEY UPDATE tags = concat(tags, ' ', tag);

いやーon duplicate keyって便利ですねー。

ただ、これ逆のことをやろうと思ったらSQLだけじゃできないだろうなあ。

4.1以降ならgroup_concat()関数が使える。この関数の存在に今日気づいたので追記。

副作用

先に触れた、「ある期間中に特に現れるタグ」の計算が面倒になった。今まではこんな感じで計算していた (一部テヌキのためにテキトーな数字で決め打ちしているところがある):

SELECT tag, log(count(tag) + 1) / log(5) * (log(2240/count) + 1) score FROM tags LEFT JOIN df USING(tag) LEFT JOIN items USING(id) WHERE date between ? and ? and count > 1 GROUP BY tag ORDER BY score desc, count(tag) desc LIMIT 10;

変更後はこうなった:

SELECT tag, log(sum(CASE WHEN length(tags) = length(replace(tags, tag, '')) THEN 0 ELSE 1 END) + 1 ) / log(5) * (log(3350/count) + 1) score FROM df LEFT JOIN items ON tags like concat('%', tag ,'%') WHERE date between ? and ? and count > 1 GROUP BY tag ORDER BY score desc LIMIT 10;

ということで、はじめてCASE式を使ってみた。CASE式は面白いので、ぜひSELECT句で分岐させていきたいですね。

副作用だといえるものは、多分これくらいだと思う。LIKE検索で検索が遅くなるのは、このサイトくらいの記事保持数やアクセス数だったらそこまで問題にはならないだろうし、それより内部処理が簡単になる利点を求めたい。

いま後輩が悩んでいるネタ。たとえば、以下のようなデータをデータベースにどう格納するかを考える。

夜行バスと割引

名前	行き先	片道運賃	割引
セレナーデ号	広島駅	8400	早売14、ネット割2%、往復割引
出雲・松江ドリーム名古屋号	出雲市駅	9000	早売21、ネット割2%、往復割引
オリーブ松山号	JR松山支店	10000	往復割引

手元に資料があるもので適当に問題を置き換えたので例が悪いが、とにかくこういうデータをどういうスキーマで格納するかを考える。教科書どおりに沿って考えると、このデータは正規化されていないので、正規形に変える必要があるだろう。

夜行バス

ID	名前	行き先	片道運賃
1	セレナーデ号	広島駅	8400
2	出雲・松江ドリーム名古屋号	出雲市駅	9000
3	オリーブ松山号	JR松山支店	10000

割引

ID	割引
1	早売14
1	ネット割2%
1	往復割引
2	早売21
2	ネット割2%
2	往復割引
3	往復割引

このままデータベースに突っ込めば、「ネット割2%」が適用されるバスの情報が欲しければ以下のSQL文で参照できるはず:

SELECT 名前 FROM 夜行バス LEFT JOIN 割引 USING(id) WHERE 割引='ネット割2%';

問題はここからで、このスキームに従うと、「早売14とネット割2%の両方が指定されている夜行バス」の一覧が欲しいときに割引テーブルを自己結合するか、早売14が指定されているバスの集合とネット割2%が指定されているバスの集合を求めて積集合を取るかしないといけなくなる。指定が3つ4つと増えていくと計算量がみるみる増えていくので、あまり現実的な話ではない。

MySQLにはSET型というものがあるので、これからもずっとMySQLで運用する気なら、割引カラムをSET型で宣言すればよい。

CREATE TABLE 夜行バス (
  id INT NOT NULL PRIMARY KEY AUTO_INCREMENT,
  名前 VARCHAR(20) NOT NULL,
  行き先 VARCHAR(15) NOT NULL,
  片道運賃 SMALL INT UNSIGNED NOT NULL
  割引 SET('早売14','早売21','ネット割2%','往復割引')
);

「早売14とネット割2%の両方が指定されている夜行バス」は以下のSQL文で求められるはず:

SELECT 名前 FROM 夜行バス WHERE FIND_IN_SET('早売14',割引) AND FIND_IN_SET('ネット割2%',割引);

ただ、どうせMySQLでいくなら、割引カラムにFulltextインデックスをつけてmatch() against() したほうが楽だったりして。

問題はほかにもあって、なんか元データはエクセルに以下のような感じで収まっているのだという:

名前	行き先	片道運賃	早売14	早売21	ネット割2%	往復割引
セレナーデ号	広島駅	8400	○		○	○
出雲・松江ドリーム名古屋号	出雲市駅	9000		○	○	○
オリーブ松山号	JR松山支店	10000				○

確かにそれは面倒だ。強まった人なら1発でいい感じに整形できるのだろうけど、私だったら正規表現の使えるエディタにコピペして

s/○$/往復割引/g
s/○(\t[^\t]*)$/ネット割2%\1/g
s/○(\t[^\t]*)(\t[^\t]*)$/早売21\1\2/g
s/○(\t[^\t]*)(\t[^\t]*)(\t[^\t]*)$/早売14\1\2\3/g

と置換するかなあ。置換すべき項目がもっと多いならもう少しエレガントな方法を考えるけど、10個くらいだったら上のようなやり方でやっちゃったほうが早そう。

set型か。覚えておこう。あとどうでもいいが、早「売」14。→http://www.kousokubus.net/PC/BPGD/BPGD221_01.htm というか、実在のデータじゃないのね。

これはやってしまいましたね。修正しました。ご指摘ありがとうございました。あとデータはJR東海バスの『JRハイウェイバス時刻表2008.3.1→6.30』の26ページから引用しました。

変更点は主にBug Fixとなります。詳しくはChangelogを御覧下さい。　なお、今回のリリースから配布形式をパッチ単体ではなく、MySQLのソースコードにパッチ組み込んだ形に変更しました

これはうれしい。

以前書いたMySQLにSennaを当てたときのメモが地味に注目を集めているらしく、ときたまSBMにブクマされたりしている。あのときは、お手本がDebianでパスの指定がCentOSと違っていたり、何か自分の環境で用を全うするのに必要な知識が分散していたりして無駄に時間がかかったので、一応CentOSユーザな私がやったことを一括に並べておいて、後から同じことをするのに都合の良いようにするためにあれを書いた。今はTritonnがあり、Tritonnのドキュメントをそのままなぞれば (--prefixとかはちゃんと変える)、それで用が済んでしまう。

ちなみに、今回私がMySQLをmakeしたときのconfigureオプションはこんな感じ:

./configure \
 --prefix=/usr \
 --with-charset=utf8 \
 --with-extra-charsets=complex \
 --localstatedir=/var/lib/mysql \
 --libexecdir=/var/lib/mysql/bin \
 --enable-thread-safe-client \
 --enable-local-infile \
 --enable-assembler \
 --with-pic \
 --with-fast-mutexes \
 --disable-shared \
 --with-zlib-dir=bundled \
 --with-big-tables \
 --with-yassl \
 --with-readline \
 --with-archive-storage-engine \
 --with-blackhole-storage-engine \
 --with-example-storage-engine \
 --with-federated-storage-engine \
 --with-mysql-idflags=-all-static \
 --with-client-idflags=-all-static \
 --with-mysql-idflags=-all-static \
 --with-mysql-user=mysql \
 --with-innodb \
 --with-extra-charsets=complex \
 --with-senna \
 --with-mecab \
 --with-unix-socket-path=/var/lib/mysql/mysql.sock

前指定したのと、Tritonnのところに書いてあったのを重ねただけなので、これで良いのかはよく分からん。

それで全文検索システムをより簡単に提供できるようになった。検索用インデックスはMeCab付属のIPA辞書で事足りる。目下の問題は表示用インデックスだ。連続する名詞はひとつにまとめるとか、ちゃんと「接頭詞」とか「接尾」とかを理解するようにすれば、「緑資源開発機構」や「参院選」のような辞書にない語彙も表示できる。しかし、作品名とか略語とかはやっぱり辞書にないとうまく取り出せない。サフィックスアレイを使うって? やっぱり? 勉強しなくちゃ。

「Tritonn(MySQL+Senna)+Mecab+Apahce+PHPをCentOS5にインストールする」も参考になる。

いままでMySQL5.0.33+Senna0.8.2だった環境をMySQL5.0.37+Senna1.0.4+MeCab0.95+Tritonn1.0.2に変えた。

従来の環境では、MeCabの辞書で全文検索インデックスを作るよりN-gramの方が早いし良いかと思っていたが、Sennaがついにバージョン1になったり、やっぱり多少速度がアレになってもより正確な方が良いよねということになったりしたので、バージョンアップをすることにした。

いろいろ試行錯誤があったものも、最終的にはMySQL5.0.33を make uninstall して、5.0.37を make installしたのち、古い全文検索インデックスをいったん削除してから貼りなおした。そしてsnippet関数を使おうとしたら

ERROR:
cannot add conditions

よく考えると、5.0.37に変えた後、とくにSnippet UDFをインストールしていないのにsnippetできる方がおかしいので、senna1.0.4についていたSnippet UDFをインストールしようとしたら、

Libraries have been installed in:
   /usr/lib

If you ever happen to want to link against installed libraries
in a given directory, LIBDIR, you must either use libtool, and
specify the full pathname of the library, or use the `-LLIBDIR'
flag during linking and do at least one of the following:
   - add LIBDIR to the `LD_LIBRARY_PATH' environment variable
     during execution
   - add LIBDIR to the `LD_RUN_PATH' environment variable
     during linking
   - use the `-Wl,--rpath -Wl,LIBDIR' linker flag
   - have your system administrator add LIBDIR to `/etc/ld.so.conf'

See any operating system documentation about shared libraries for
more information, such as the ld(1) and ld.so(8) manual pages.

make load すると

ERROR 1125 (HY000) at line 1: Function 'snippet' already exists

こりゃ、ご指示通りマニュアルを読む必要があるのかー。

ぐぐってみると日本語のリソースが1個しか引っかからないのが悲しい。くだんの人は、libの中のファイルが古かったのが原因だったそうな。同じように確認してみたら、私の場合はファイルが古いわけではなかった。1台まっさらなのを用意するほうが早いかなー。

古いsnippetをmake uninstall→新しいsnippetをmake install→MySQLにログインしてdrop function→make loadで解決した。そういわれれば、確かに関数がすでに存在しているなら削除してあげればいいだけの話だった。

複数テーブルにまたがるJOINは避ける

非正規化ロジックで対応

1. まっとうなクエリスキーマをデザインすること。テーブルの結合を怖がることはない、大抵非正規化よりも速い

結局どっちなんだ?

すでにテーブルにある主キーやユニークキーと同じ値をふくむ行を挿入しようとするときに、こちらの想定する振る舞いをさせる方法のまとめ。まぁ、リファレンスマニュアルの INSERT 構文のところを見れば話は終わりなのだけれども。

ID (主キー)	値
1	100
2	800
3	400

間違って主キーと同じ値を含む行を挿入しようとしたらエラーを出して教えてほしいとき

INSERT INTO test VALUES(1,100); とすると、ERROR 1062 (23000): Duplicate entry '1' for key 1 というエラーが出る。

間違って主キーと同じ値を含む行を挿入しようとしても無視して処理を続行してほしいとき

INSERT IGNORE INTO test VALUES(1,100); とすると、Query OK, 0 rows affected (0.00 sec) と表示される。テーブルは変更されていない。

主キーと同じ値を含む行がないなら新しく挿入し、あるならその行を更新してほしいとき

REPLACE INTO test VALUES(1,500); とすると、Query OK, 2 rows affected (0.00 sec) と表示される。削除してから挿入するので影響された行は2になる。テーブルは;

ID (主キー)	値
1	500
2	800
3	400

REPLACE INTO test VALUES(4,200); とすると、Query OK, 1 row affected (0.00 sec) と表示される。主キーが4である行はないので、そのまま挿入されて、影響された行は1になる。テーブルは;

ID (主キー)	値
1	500
2	800
3	400
4	200

主キーと同じ値を含む行がないなら新しく挿入し、あるならその行を元のデータを使って更新してほしいとき

INSERT INTO test VALUES(1,100) ON DUPLICATE KEY UPDATE value = value + 100; とすると、Query OK, 2 rows affected (0.00 sec) と表示される。削除してから挿入するので影響された行は2になる。テーブルは;

ID (主キー)	値
1	600
2	800
3	400
4	200

最後の構文は無駄な IF 文を除去するのに最適なのでぜひおさえておきたい。

本文を形態素分解し、必要な品詞をtfテーブルとdfテーブルに入れる。分析対象となる文書群すべてについてこの処理を行い、各形態素のTF-IDF値を求めて文書をベクトル化する。他の文書ベクトルと内積を比較し、小さい順に「似ている記事」を求めたい (クラスタリングとかは別途)。

HarmanによるTF値の正規化とSparok JonesによるDF値の正規化をする場合のTF-IDF値の計算式は以下のようになる (参考文献):

tfidf(i,j) = log2(freq(i,j) + 1) / log2(NoT) * (log2(N / Dfreq(i)) + 1)

HarmanによるTFの正規化

tf(i,j) = log2(freq(i,j) + 1) / log2(NoT)

tf(i,j)

文書jにおける単語iのTF値

freq(i,j)

文書jにおける単語iの登場回数

NoT

文書j中のタームの種類数(num of terms)

Sparck JonesによるDFの正規化

idf(i) = log2(N / Dfreq(i)) + 1

idf(i)

単語iのDF値

N

文書集合中の文書総数

Dfreq(i)

単語iが登場する文書数

MySQL での表現

TF値の分子

SELECT log2(times + 1) FROM tf WHERE item='j' AND tag='i';

TF値の分母

SELECT log2(count(tag)) FROM tf WHERE item='j' GROUP BY item;

IDF値のlogの分子

SELECT count(id) FROM article;

IDF値のlogの分母

SELECT times FROM df WHERE tag = 'i';

全部くっつけると:

SELECT item, tag, log2(tf.times + 1) / log2(total) * (log2(n / df.times) + 1) AS tfidf
  FROM tf
    LEFT JOIN df USING(tag)
    LEFT JOIN (SELECT item, count(tag) total FROM tf GROUP BY item) AS a USING(item)
    CROSS JOIN (SELECT count(id) AS n FROM items) AS b
  WHERE item="j";

実際はユーザ変数を使った方がSQLが短くなっていいと思う。

SELECT @total := count(tag) FROM tf WHERE item = "j";
SELECT @n := count(id) FROM items;
SELECT item, tag, log2(tf.times + 1) / log2(@total) * (log2(@n / df.times) + 1) AS tfidf
  FROM tf LEFT JOIN df USING(tag)
  WHERE item="j";

これで記事の各形態素のTFIDF値が求められたので、tfidfテーブルに保管しておく。

内積を求めて近い記事を出す

とりあえず各記事の上位100単語くらいを使うことにする。

INSERT INTO tfidf
  SELECT item, tag, log2(tf.times + 1) / log2(@total) * (log2(@n / df.times) + 1) AS tfidf
    FROM tf LEFT JOIN df USING(tag)
    WHERE item="j"
    ORDER BY tfidf DESC
    LIMIT 100;

ある文書wがn次元のベクトルで表せる (w = {w₁ w₂ ... w_n})とき、文書wとxの内積は

Σ(wi * vi) / √(Σ(wi2) * Σ(vi2))

MySQLで書くと

CREATE TEMPORARY TABLE inp
  SELECT self.tag, self.tfidf self, target.tfidf target
    FROM tfidf self
      LEFT JOIN (SELECT tag,tfidf FROM tfidf WHERE item='v') target USING(tag)
    WHERE self.item = 'w';
SELECT sum(self * target) / sqrt(sum(pow(self,2))*sum(pow(target,2))) inp FROM inp

実際にやってみる

実際にニュー速各板のスレでやってみた。だいたい同じニュースの続きのスレだと0.6以上の高い値に、似たようなネタの異なるニュースの場合は0.3～0.4くらいになった。以下はそれらの例。カッコ内が内積

高い値 …… 同じニュースの次スレ、前スレ

【経済】 「格差是正のため、正社員の待遇を非正規社員水準に合わせる」…経済財政諮問会議・八代氏★５

• 【経済】 「格差是正のため、正社員の待遇を非正規社員水準に合わせる」…経済財政諮問会議・八代氏★４ (0.76865722990833)
• 【経済】 「格差是正のため、正社員の待遇を非正規社員水準に合わせる」…経済財政諮問会議・八代氏★３ (0.72848890331971)
• 【経済】「格差是正のため正社員待遇を非正規社員水準へ」…経済財政諮問会議メンバー・八代尚宏氏★２ (0.61619675121174)
• 【経済】「格差是正のため正社員待遇を非正規社員水準へ」…経済財政諮問会議メンバー・八代尚宏氏 (0.63664490692797)

【芸能】森本レオが石原真理子の処女を奪ったことを認める「それでもやっぱりマリコがんばれ」

• 【芸能】石原真理子「17歳で森本レオに処女奪われた」…週刊誌に暴露、「宣伝か」の声も★２ (0.82246383998552)
• 【芸能】石原真理子「17歳で森本レオに処女奪われた」…週刊誌に暴露、「宣伝か」の声も[12/18] (0.79417204039799)

◆自治議論★64◆

• 愛の説教部屋166(地獄キャンペーン実施中)（　ﾟдﾟ) (0.67651278868912)
• ◆自治議論★63◆ (0.81182145799799)
• ◆自治議論★62◆ (0.79929338782244)

中くらいの値 …… 似たようなネタだが異なるニュースのスレ

【MLB】多田野、アスレチックスと再契約 春季キャンプでメジャー復帰目指す★３

• 【社会】 ＮＨＫ職員（男）、電車で大学生（１８０cm・１２０kgの男子）に痴漢→逮捕…東京★３ (0.4629403483907)
• 【社会】 ＮＨＫ職員（男）、電車で大学生（男子）に痴漢→逮捕…東京★２ (0.41509734340642)

【大阪】コリアNGOセンター事務局長「公立校で民族教育は不要との意見が出かねない…外国籍の子供に愛国心強調しないで」［12/18］

• 【論説】 「"日教組が、教育荒廃の元凶"というのは言いがかりだ」…東京新聞★２ (0.35593573724151)
• 【日韓】 ［特派員コラム］韓国は日本を追い越すことができる?潜在力も意欲も韓国が上[12/18] (0.3069814685099)
• 【論説】 「愛国心、"格差"はぐらかす為か？ 学生らは愛国心強要に"日本社会の悪化"を感じている」…毎日新聞★３ (0.39403589906126)

【フィギュアスケート】高橋・安藤・浅田・村主ら日本勢に謎の症状･･･体調不良者が続出★３

• 【北海道】カキ「風評被害」に悲鳴、取扱額４０％減　ノロウイルス食中毒、今季の感染例ゼロなのに★２ (0.41831300355656)

今回やってみて、同じニュースのスレッドは★１だろうが★８だろうが同じようなことを延々と話しているのではないかと感じた。何スレも立つような息の長いニュースについて、スレッドごとの単語の登場の仕方とか共起の仕方を見ていくと、ニュー速民のニュースへの態度を表せたりするかも。面白いのはフィギュアスケート選手の体調不良の記事とカキの風評被害の記事が関連付けられたこと。フィギュアスケートの記事中に「カキ」への言及がなくても、ニュー速民による噂話の可視化によって、実は関係あるかもしれない2つの記事が結びついた。なんか集合知かも～。

このとき使ったのと似たような手法を候補者ブログクローラでも使っています。

いろいろな本からメモってきたメモのメモ。出典を書いておくのを忘れた。思い出し次第補完するかも。

• deleteのコストは高いので、無効化を示すフィールドを作ってupdateすべき
• slow query logに要注意
• 多くのエントリでほとんどのフィールドが同じ値を持つ場合はインデックスの効果が小さい
  • →複合インデックスの効果が大きい
• 複合インデックスは指定の順番が大切。AとBという指定の場合、A単独でもインデックスの効果がある。逆は真でない。
• インデックスが使われる場面は
  • フィールド値を定数と比較するとき (where name = 'hogehoge')
  • フィールド値でJOINするとき (where a.name = b.name)
  • フィールド値の範囲を求めるとき (<,>,between)
  • LIKE句が文字列から始まるとき (where name like 'hoge%')
  • min(),max()
  • 文字列のプレフィクスを基にしたorder by,groupy by
  • WHERE句の全てのフィールドがインデックスの一部の場合はDBをまったく参照せずに結果が返ってくる
• インデックスが使われない場面は
  • LIKE句がワイルドカードから始まるとき (where name like '%hoge')
  • DB全体を読んだほうが早いとMySQLが判断したとき
  • ほかでインデックスを使ったとき
• 遅いクエリをexplain selectで解剖
  • using filesort と using temporary が現れないように
  • using index や where used が現れるとうれしい。where used で type:ALLの場合は適切なインデックスをつけるように
• left join や straight join と using の組み合わせは where より早い
  • left join on と natural join + where だと後者のほうが早いのでそうしていたけれども、usingを一回試してみよう
  • usingは二つのカラム名が同じでないと使えないみたい → usingとonは同じみたい
• where in はかなり早い
• インデックスが適用されないので having はなるべく使わないように
• なるべくシンプルなSQL文を心がける
• update,insert,deleteの最適化
  • multi-row insertをなるべく使うようにする
    • JDBC経由だとどうすればいいんだろう
• select high_priority や update low_priority を使ってみる
• replace のほうが delete → insert より早い
• load data infile, load_file()
• limit句を使って転送量の削減
• joinに使うフィールドは完全に同じ形式にする
  • varchar(64)のフィールドとvarchar(32)のフィールドをJOINさせないように。できればchar()のほうがよりよい
• select ... procedire analyse() で最大必要フィールド長を分析
• 不必要に長いchar,varcharを避ける
• enumの利点
  • エントリごとに1バイトのみ必要
  • 高速化
  • 想定外のデータが入らない
• NULLが入らないフィールドには NOT NULL をつけておく
• varcharよりもなるべくcharを使う。varcharは別テーブルに追いやって全フィールドの固定長化を図る
• key_buffer_size_indexをRAMの4分の1くらいにあげよう
• table_cacheをなるべく多く
• スワップはダメゼッタイ
• NFSを避ける
• 多くのハードディスクに分散させる
• ハードウェアの優先順位は RAM > HDD > CPU > ネットワーク
  • スレーブには鬼のようにメモリを積んでおきたい
• 選択性の高いインデックスだと効果がある
  • PRIMARY KEYは選択性最強。膨大な量のデータがあっても1秒程度で
  • 性別などは選択性の低いインデックス。あまり効果がない。WHEREでつなげるなら後回しに
  • WHERE句でよく一緒に使われる列をインデックスに指定する
  • WHERE句に単独で使われることもある列は、インデックスの最初の列に指定する
  • 選択性の優れている列から順に指定する
  • 選択する列も結合インデックスに含めるとさらに高速化が期待できる → DBにまったくアクセスせずに結果を返せる
    • 参照が早くなる反面更新が遅くなるので注意
• NULLはインデックスに含まれない。NULLの検索をしたいならデフォルト値の設定を検討すべき
• !=,<>の使用に注意。in,orなどの置き換えを考える
• WHERE句の条件に関数を使うとインデックスが使用されない。意味的に等価なSQL文への置き換えを考える
• order by 句にインデックスが指定されている場合、インデックス内ですでにデータがソートされているので高速(not nullの場合)
• distinctを使うと遅くなる。本当に必要なときだけ使う
• unionも重複行を削除する処理を行うので処理が遅くなる。union allを使うように
• group by句を使う場合集計するカラムだけでなく(sum()などの集計関数を使って)集計されるカラムにもインデックスをつけておくと早い

138000秒(38時間+)経ってもまだ終わらない。

なんか電車の中からsunameri経由でkurageにログインしてMySQLの調子を観測するのがたるいのでなにかソリューションを考え中、ていうかsunameriにPHPMyAdminとか入れればいいのか。んー

で、このあいだのニュース板クローラに続き実況板クローラも、updateがぜんぜん終わらなくてkillしてもCommandがkilledのまま終わらなくてrepair table したらそれが30000秒経っても終わらないという状態になってしまったので、ていうか実況板クローラで遊ぶよりも卒論とかにリソースを多く注入すべきだと思ったので12月が終わるまで休止させるかも。そんなこと言いつつ適当なタイミングで思ったより早く復活するかもしれないので未来のことはぜんぜんわからないし、そりゃ鬼だってバカウケするよなぁと思った。あとJavaScriptは意外と面白い。

大学祭。ミナミにいたらひーろんが来たので、彼と相合い傘（はーと←ぉぇ）佐世保バーガーがおいしかった。午後から行列になったそうだし、午前の早いうちに味わっておいてよかった。

戻ってきてからcronプロセスの監視。なんかエラーがでてたとこがあったのでパーサを少し書き直した。バージョンの古いのと新しいのがごちゃごちゃしていて、直したと思ったのがそれが実運用に入っていなかったりする。あとですっきりさせないといけない。jarファイルにまとめるとか。

そのあとはMySQLのレプリケーションに手を出す。なんか、レプリケーションまで行くとWindowsにmsiインストーラを使ってクリックだけしてMySQLをインストールしていた頃に比べると隔世の感が出てきた気がする。レベルうｐみたいな

お手本を参考に作業を進める。17時から始めて19時頃にはいったんうまくいった。マスタでinsertしたデータがスレーブでselectできたときにはある種のカタルシス、エクスタシーを覚えた。xtc。

が、ある操作をすると存在するはずのファイルがないと言われる。マスタからスレーブにデータを移すときに一部のデータを移動し損ねたかと思った私は、ふたたびマスタのファイルを圧縮しスレーブに移動させた。そしたらなんということでしょう、スレーブとマスタが協調しなくなってしまったのです。

後から思えば、ファイルは存在しなかったのではない。root権限になっていてmysqlユーザからは見えなかっただけなのだ。そこでchown -R mysql.mysqlできるだけの機転や経験があれば私は2時間を現状回復に費やさずにすんだのに。

ともあれ、終バスの15分前にはなんとか現状回復に成功。爆発1秒前に時限爆弾を止められた映画の主人公の気持ちを疑似体験できた。きょうが土曜日で終電に接続するバスの時間が13分遅くなっていたのも幸い。めずらしくうまくいった。

MySQL 4.1 リファレンスマニュアル の 「日付と時刻関数」には、このクエリでは、過去 30 日以内の日付の date_col 値を持つすべてのレコードが選択されますとして SELECT something FROM tbl_name WHERE TO_DAYS(NOW()) - TO_DAYS(date_col) <= 30; という SQL 文が紹介されているけれども、これって INDEX が使われないわけで。

30日前の日付が他で分かるなら、それを BETWEEN で指定してあげれば、type が range なインデックスが使われる。だから、たとえば SELECT something FROM tbl_name WHERE date_col BETWEEN DATE_FORMAT(DATE_ADD(NOW(), INTERVAL -30 DAY),'%Y-%m-%d 00:00:00') AND DATE_FORMAT(NOW(),'%Y-%m-%d 23:59:59') とすればインデックスを使いつつ過去30日以内レコードを選択できるかなと思った。まぁ、データの量によっては無理してインデックスを使う必要もないわけなのだけれども。

Sennaのsnippet udfを使うSQLは:

SELECT snippet(文書, snippetの長さの最大バイト数, snippetの最大個数, 文書の文字コード, htmlエンコーディングの有無, snippetの開始タグ, snippetの終了タグ, 単語1, 単語1の前につけられるタグ, 単語1の後につけられるタグ, 単語2, 単語2の前につけられるタグ, 単語2の後につけられるタグ, ...);

となっている。単語の数に応じて引数の数が変化するので、PreparedStatementを使えない。

簡単のためにフレーズ検索は考えないことにする。検索窓とかからスペース区切りの検索フレーズを受け取ったら、snippet関数の第8引数以降を何とかして生成したい。

against()の中はPreparedStatementを使えるので、prepareするSQL文は以下のようになるかなー (AND検索する場合):

SELECT title, snippet(body,256,2,'utf8',1,'','',あとで追加する部分) AS snip FROM items WHERE MATCH(title,body) AGAINST(? in boolean mode) order by MATCH(title,body) AGAINST(? in boolean mode);

で、空白区切りのクエリを受け取ったら:

$queries = explode(' ',$q);
$snip = "";
$against = "";
foreach($queries as $idx => $each){
    $snip .= ','.mysql_real_escape_string($each).",'<span class=\"query q$idx\">','</span>'";
    $against .= '+'.$each;
}
$sql = "SELECT title, snippet(body,256,2,'utf8',1,'',''$snip) AS snip FROM items WHERE MATCH(title,body) AGAINST(? in boolean mode) order by MATCH(title,body) AGAINST(? in boolean mode)";
$stmt = $conn->prepare($sql);
$stmt->bind_param("ss", $against, $against);

って感じ? 定石はどんななんだろ。

日本語で全文検索をするために MySQL に Senna を組み込むメモ。少し前は個人ニュースサイトめぐり→日記書きに数時間を要していた私が次に目をつけたのがRSSめぐり→はてブ登録なのだがそれでも依然として数時間かかる。そんなあなた (私) に朗報です。私の代わりにブックマークしてくれるエージェントを作ればいいのです。そしてそのエージェントが今日よく使われていた単語やタグとか出してくれて、1次ソースAについてBさんとCさんとDさんがそれぞれの立場でこんなことを書いているとかいうのが俯瞰できて、さらにあとから検索とかができればいいのです。いまホッテントリを見なくてもいいのです。あとで検索できればいいのです。Googleが拾ってくる量は莫大過ぎるし個人で把握できる範囲にも限度がある。ユーザの皆さんが勝手に重み付けしてくれるならそれを使ったらいい。先週の週刊東洋経済を読んで悟った。いやなんか変だ。むにむに

まずは MeCab のインストール。配布元に詳しいドキュメントあり。Senna のインストール方法には、mecab を configure するときに --prefix=/usr をつけていないぽかったのでつけずにやったら起動できなかった。悔い改めてやり直した。

$ cd mecab-0.93
$ ./configure --enable-utf8-only --enable-mutex --prefix=/usr
$ make
$ make check
$ sudo make install

続けて辞書をインストールして実行してみる。

$ cd mecab-ipadic-2.7.0-20060707
$ ./configure --with-charset=utf8 --prefix=/usr
$ make
$ sudo make install
$ mecab

テストしてみましょう。

諏訪を新宿並みに有名にしたかった
諏訪    名詞,固有名詞,人名,姓,*,*,諏訪,スワ,スワ
を      助詞,格助詞,一般,*,*,*,を,ヲ,ヲ
新宿    名詞,固有名詞,地域,一般,*,*,新宿,シンジュク,シンジュク
並み    名詞,接尾,一般,*,*,*,並み,ナミ,ナミ
に      助詞,格助詞,一般,*,*,*,に,ニ,ニ
有名    名詞,形容動詞語幹,*,*,*,*,有名,ユウメイ,ユーメイ
に      助詞,格助詞,一般,*,*,*,に,ニ,ニ
し      動詞,自立,*,*,サ変・スル,連用形,する,シ,シ
たかっ  助動詞,*,*,*,特殊・タイ,連用タ接続,たい,タカッ,タカッ
た      助動詞,*,*,*,特殊・タ,基本形,た,タ,タ
EOS

成功。続けて Senna を入れる。参考書は前出のSenna のインストール方法。

$ cd senna
$ ./configure --prefix=/usr
$ make
$ sudo make install
$ sudo mkdir /var/senna
$ sudo emacs /var/senna/senna.conf

で、senna.conf に、

DEFAULT_ENCODING utf8

続けて MySQL 。MySQLのconfigureオプションや、Sennaのインストールなどを参考にした。

$ cd mysql-5,0,24
$ patch -p1 < ../senna/bindings/mysql/mysql-5.0.24.senna.diff
$ patch -p1 < ../senna/bindings/mysql/mysql-5.0.24.senna.2ind.diff
$ libtoolize -c -f
$ aclocal-1.9
$ autoheader
$ automake-1.9 -c -a -i
$ autoconf
$ touch sql/sql_yacc.yy
$ CFLAGS="-O3 -mtune=pentium4" \
> CXX=gcc \
> CXXFLAGS="-O3 -mtune=pentium4 -felide-constructors -fno-exceptions -fno-rtti" \
> ./configure --prefix=/usr \
> --with-charset=utf8 \
> --with-extra-charsets=complex \
> --with-senna \
> --with-big-tables \
> --with-readline \
> --enable-thread-safe-client \
> --enable-local-infile \
> --enable-assembler \
> --with-client-idflags=-all-static \
> --with-mysql-idflags=-all-static \
> --with-mysql-user=mysql \
> --localstatedir=/var/lib/mysql \
> --with-unix-socket-path=/var/lib/mysql/mysql.sock
$ make
$ sudo make install
$ sudo ./scripts/mysql_install_db

エラーが出たので

$ su -
# ./scripts/mysql_install_db
# chown -R mysql.mysql /var/lib/mysql
# chmod 755 /var/lib/mysql
# cp support-files/my-medium.cnf /etc/my.cnf
# cp /usr/local/src/mysql-5.0.24/support-files/mysql.server /etc/rc.d/init.d/mysqld
# chmod 755 /etc/rc.d/init.d/mysqld
# chkconfig --add mysqld
# chkconfig --level 345 mysqld on
# service mysqld start

そして

$ mysqladmin -u root password oniichandoite,soitsukorosenai
$ mysql -uroot -p
mysql> create database sennatest;
mysql> grant all on sennatest.* to gonbei@localhost identified by '[tamurayukari]ttedarenanoyo,sakurananoyo,a.ta.shi!';
$ quit;
$ mysql -ugonbei -p
mysql> use sennatest;
mysql> create table articles(
    -> id int unsigned not null auto_increment primary key,
    -> body text,
    -> fulltext(body)
    -> );
Query OK, 0 rows affected (0.06 sec)

mysql> insert into articles values
    -> (null,"郵貯民営化は重要な問題だと思う "),
    -> (null,"スローライフを志向するiPodの強み - CNET Japan"),
    -> (null,"HTML, CSS, Photoshopを同時に学べるサンプル付きデザイン記事：Goodpic"),
    -> (null,"jazzanovaの日記 - 現在顧問弁護士に相談中であり、対応についても検討中"),
    -> (null,"mixi非公式ニュースサイト - mixiの問題人物Kusakabe氏、強制退会に？"),
    -> (null,"むだづかいにっき♂：ネット上で議論を仕掛ける事について"),
    -> (null,"はてな perl ハッカーの方々にお聞きします。近頃ますます良い感じなperlですが、どのような開発環境で開発していますでしょうか。"),
    -> (null,"シナトラ千代子 - 投げ銭が飛び交うなかでダイアリーに立てこもる、という意味。"),
    -> (null,"Going My Way: Skypeの会話をPodcast用に録音する場合の設定方法"),
    -> (null,"Kusakabeさんがmixiの一部？を賑わしている。彼にmixi強制退会が言い渡されたのだ。"),
    -> (null,"Ringo's Weblog: googleと競合しない方法2 "),
    -> (null,"Moleskin Diary - 投げ銭よりたれ銭"),
    -> (null,"第38回　海外メディアが伝えた小泉・郵政解散劇の評判 - nikkeibp.jp - 立花隆の「メディア ソシオ-ポリティクス」"),
    -> (null,"ほその日記 - フォームが変更された事を知る"),
    -> (null,"総選挙はてなと公職選挙法:北海道に住む国家公務員日記 "),
    -> (null,"はてな、政党を株式に見立てて総選挙結果を予測 - CNET Japan");
Query OK, 16 rows affected (1.48 sec)
Records: 16 Duplicates: 0 Warnings: 0

mysql> select * from articles where match (body) against ('はてな');
+----+----------------------------------------------------------------------------------------------------------------------------+
| id | body                                                                                                                       |
+----+----------------------------------------------------------------------------------------------------------------------------+
|  7 | はてな perl ハッカーの方々にお聞きします。近頃ますます良い感じなperlですが、どのような開発環境で開発していますでしょうか。 |
| 15 | 総選挙はてなと公職選挙法:北海道に住む国家公務員日記                                                                        |
| 16 | はてな、政党を株式に見立てて総選挙結果を予測 - CNET Japan                                                                  |
+----+----------------------------------------------------------------------------------------------------------------------------+
3 rows in set (0.00 sec)

すばらしい。じゃあ次は PHP からアクセスしてみよう。PHP は apt-getで入れた。

Warning: mysql_connect(): Can't connect to local MySQL server through socket '/var/lib/mysql/mysql.sock' (13) in /var/www/html/test.php on line 4

うまくいかない。ちゃんと/var/lib/mysql には mysql.sock があるんだけどなー。

mysql_connect("localhost",$user,$pass); を mysql_connect("localhost.localdomain",$user,$pass); に変えたらうまくいった。しかし where match() against() を含んでいる SQL 文を投げると mysql_fetch_object()が false を返す。普通に select * from articles; とすると日本語の部分が全部 "?" になる。MySQL も Apache も UTF-8 を使う設定になっているはずなのになぜだー。

ぐぐったらはてなQに似たような悩みの人がいた。これを参考に、my.cnf の client セクションに default-character-set=utf8 を、 mysqld セクションに init-connect=SET NAMES utf8 を追加。mysqld を restart。直った。素敵。今回は以上。

この記事のメモはTritonnが始まる前に書かれた古いものです。Tritonnを使った場合のインストール方法についてはSennaとかのアレの続き Tritonn編をどうぞ。