Re: One Response to “「フレンド・タイムライン処理の原理と実践」を追試してみた”

http://sklave.jp/logs/2008/06/10/re_friend_timeline_on_mysql/

コメントに書いたことと、あとワーストケースのパフォーマンスの問題かなぁ、と思いました。

単純なクエリは、実際には、

SELECT message.* FROM message INNER JOIN (
  SELECT message.id FROM message INNER JOIN follower
  ON message.user_id=follower.follower_id
  WHERE follower.user_id=1
  ORDER BY message.id DESC LIMIT 20
) as t1 USING (id);

のような形になるのでしょうが、このケース () 内の JOIN において、message テーブルを優先するにせよ、follower テーブルを優先するにせよ、遅いパターンが出てきます。

奥のテストデータは、ヘビーユーザとライトユーザを表現するために、ある程度の偏りを持つようにして生成してあるのですが、最もデータ量とフォロワーの多いユーザ (ID=1) についてのタイムライン取得処理は、上のクエリだと、 6.3 タイムライン／秒 という速度に落ち込みます。

単にこの問題に対処するのであれば、MySQL のオプティマイザが follower テーブルを優先しているのを、STRAIGHT_JOIN コマンドを使って message テーブルを優先するように指示してしまえば、とても高速なクエリになります。しかし今度は、フォロワーの少ないユーザーのタイムライン取得処理が (message テーブルの降順でのアクセスでデータを発見するまで時間がかかるようになるため) 重たくなってしまいます。

残念ながら MySQL は、指定されたユーザ ID を基準に、どちらのインデックスを優先するか自動で判断してくれません。というより、それはインデックス単位のカーディナリティではカバーできない種類の最適化になるので、開発者がコードで工夫せざるを得ないたぐいのことになります。

というわけで、スケーラビリティが問題になるようなケースでは、複雑であっても、データサイズに依存せず、極端に重い処理が発生しないアルゴリズムのほうがいいのかな、と思っています。