txqz memo

記事-タグの関係をMySQLicious化

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

今までの構造

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

items
idtitlebodydate
1地球空冷化<p>最近、私の ...2001-08-04 00:01:00
2台風一過<p>幸運なことに ...2001-08-22 00:01:00
tags
item_idtag
1生活
1自分のこと
22ch
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
idtitlebodydatetags
1地球空冷化<p>最近、私の ...2001-08-04 00:01:00生活 自分のこと
2台風一過<p>幸運なことに ...2001-08-22 00:01:002ch コロッケ 台風

これを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) AS 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) AS 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検索で検索が遅くなるのは、このサイトくらいの記事保持数やアクセス数だったらそこまで問題にはならないだろうし、それより内部処理が簡単になる利点を求めたい。