フォローしているユーザのツイートを検索する SQL について実験

とりあえず検証してみた内容を書いとく．どうすればいいんだろうなぁ．

問題

フォロー関係とツイートを DB に保存しているものとする．以下のような簡単なテーブル定義とする．(追記 gist を更新してしまったのでインデックス付いているが最初の段階では6 行目はなかった）

この状態である人がフォローしている人のツイートを取得したい場合を考える．つまり， user_id が 1 の人が user_id が 2, 3 の人をフォローしているとするとタイムラインとしては user_id が 2 の人がツイートした内容と user_id が 3 の人がツイートした内容が表示されるようにしたい．ここでは簡単のために user_id が 1 の人のツイートをタイムラインに表示しない．

このようなクエリを実行する際にツイート数が多い場合実行時間が大きくなるためこれの改善が出来ないかについて考えてみる．

事前実験

環境

Ubuntu 12.04 LTS
MySQL 5.5.35

実施内容

データとして以下のようなものを用意した．

項目合計	値
ユーザ	1000
ツイート	1000000
フォロー数	177500

フォロー数内訳．誰をフォローしているかはランダム．

user_id	フォロー数
0 - 99	0
100 - 199	10
200 - 299	20
300 - 399	25
400 - 499	50
500 - 599	100
600 - 699	120
700 - 799	250
800 - 899	500
900 - 999	700

例えばある人がフォローしている人のツイートを取得したい場合を考える．すると以下のような SQL になる．

SELECT t.id, t.user_id, t.tweet FROM tweet t
  WHERE t.user_id IN (SELECT follow_to FROM follow WHERE follow_from = ?) LIMIT 20;

このクエリの EXPLAIN の確認および実行時間を各フォロー数についてそれぞれ実行してみる．

実施結果

mysql> EXPLAIN SELECT t.id, t.user_id, t.tweet FROM tweet t WHERE t.user_id IN (SELECT follow_to FROM follow WHERE follow_from = 1) LIMIT 20;
+----+--------------------+--------+------+--------------------+--------------------+---------+------------+----------+-------------+
| id | select_type        | table  | type | possible_keys      | key                | key_len | ref        | rows     | Extra       |
+----+--------------------+--------+------+--------------------+--------------------+---------+------------+----------+-------------+
|  1 | PRIMARY            | t      | ALL  | NULL               | NULL               | NULL    | NULL       | 10000329 | Using where |
|  2 | DEPENDENT SUBQUERY | follow | ref  | follow_from_to_idx | follow_from_to_idx | 8       | const,func |        1 | Using index |
+----+--------------------+--------+------+--------------------+--------------------+---------+------------+----------+-------------+
2 rows in set (0.03 sec)

ためしにユーザ ID = 1 のものの結果を取得してみる．

mysql> SELECT t.id, t.user_id, t.tweet FROM tweet t WHERE t.user_id IN (SELECT follow_to FROM follow WHERE follow_from = 1) LIMIT 20;
Empty set (18.69 sec)

簡単に実行してみると以下のような時間になる．（もちろんクエリキャッシュはなし）

ユーザ ID	クエリ実行時間
1	18.69 sec
101	2.00 sec
201	0.36 sec
301	1.46 sec
401	0.16 sec
501	0.12 sec
601	0.24 sec
701	0.03 sec
801	0.05 sec
901	0.03 sec

なぜかフォロー数が 0 の場合にとても遅いという結果になった．これだと遅すぎるため改善が必要．

改善に向けて（１）

「実践ハイパフォーマンス MySQL 」

第３章スキーマの最適化とインデックスの 3.3.4 カバリングインデックスを参考に下記のように書き換えてみる．

SELECT t.id, t.user_id, t.tweet FROM tweet t JOIN
  (
    SELECT t2.id FROM tweet t2 
      JOIN follow f ON f.follow_to = t2.user_id AND f.follow_from = ?
  ) AS t1
  ON t1.id = t.id LIMIT 20;

結果が同じことは出力結果を比較して確認している．

for id in $(seq 0 9); do
        FROM=`expr $id \* 100 + 1`
        diff -q \
                <(mysql -uadmin follow_test -phogehoge -e "select t.id, t.user_id, t.tweet from tweet t where t.user_id in (select follow_to from follow where follow_from = $FROM)") \
                <(mysql -uadmin follow_test -phogehoge -e "SELECT t.id, t.user_id, t.tweet FROM tweet t JOIN ( SELECT t2.id FROM tweet t2, follow f WHERE f.follow_to = t2.user_id AND f.follow_from = $FROM) AS t1 ON t1.id = t.id")
done

実施結果

EXPLAIN は下記のようになる．フォロー数が多くなるほど rows が大きくなっている．

mysql> EXPLAIN SELECT t.id, t.user_id, t.tweet FROM tweet t JOIN (SELECT t2.id FROM tweet t2 JOIN follow f ON f.follow_to = t2.user_id AND f.follow_from = 1) AS t1 ON t1.id = t.id LIMIT 20;
+----+-------------+-------+------+--------------------+--------------------+---------+-------------------------+--------+-----------------------------------------------------+
| id | select_type | table | type | possible_keys      | key                | key_len | ref                     | rows   | Extra                                               |
+----+-------------+-------+------+--------------------+--------------------+---------+-------------------------+--------+-----------------------------------------------------+
|  1 | PRIMARY     | NULL  | NULL | NULL               | NULL               | NULL    | NULL                    |   NULL | Impossible WHERE noticed after reading const tables |
|  2 | DERIVED     | f     | ref  | follow_from_to_idx | follow_from_to_idx | 4       |                         |      1 | Using index                                         |
|  2 | DERIVED     | t2    | ref  | user_id_idx        | user_id_idx        | 4       | follow_test.f.follow_to | 555573 | Using index                                         |
+----+-------------+-------+------+--------------------+--------------------+---------+-------------------------+--------+-----------------------------------------------------+
3 rows in set (0.02 sec)

mysql> EXPLAIN SELECT t.id, t.user_id, t.tweet FROM tweet t JOIN (SELECT t2.id FROM tweet t2 JOIN follow f ON f.follow_to = t2.user_id AND f.follow_from = 101) AS t1 ON t1.id = t.id LIMIT 20;
+----+-------------+------------+--------+--------------------+--------------------+---------+-------------------------+--------+-------------+
| id | select_type | table      | type   | possible_keys      | key                | key_len | ref                     | rows   | Extra       |
+----+-------------+------------+--------+--------------------+--------------------+---------+-------------------------+--------+-------------+
|  1 | PRIMARY     | <derived2> | ALL    | NULL               | NULL               | NULL    | NULL                    | 100000 |             |
|  1 | PRIMARY     | t          | eq_ref | PRIMARY            | PRIMARY            | 4       | t1.id                   |      1 |             |
|  2 | DERIVED     | f          | ref    | follow_from_to_idx | follow_from_to_idx | 4       |                         |     10 | Using index |
|  2 | DERIVED     | t2         | ref    | user_id_idx        | user_id_idx        | 4       | follow_test.f.follow_to | 555573 | Using index |
+----+-------------+------------+--------+--------------------+--------------------+---------+-------------------------+--------+-------------+
4 rows in set (0.07 sec)

mysql> EXPLAIN SELECT t.id, t.user_id, t.tweet FROM tweet t JOIN (SELECT t2.id FROM tweet t2 JOIN follow f ON f.follow_to = t2.user_id AND f.follow_from = 901) AS t1 ON t1.id = t.id LIMIT 20;
+----+-------------+------------+--------+--------------------+--------------------+---------+------------------------+----------+-------------+
| id | select_type | table      | type   | possible_keys      | key                | key_len | ref                    | rows     | Extra       |
+----+-------------+------------+--------+--------------------+--------------------+---------+------------------------+----------+-------------+
|  1 | PRIMARY     | <derived2> | ALL    | NULL               | NULL               | NULL    | NULL                   |  7000000 |             |
|  1 | PRIMARY     | t          | eq_ref | PRIMARY            | PRIMARY            | 4       | t1.id                  |        1 |             |
|  2 | DERIVED     | t2         | index  | user_id_idx        | user_id_idx        | 4       | NULL                   | 10000329 | Using index |
|  2 | DERIVED     | f          | ref    | follow_from_to_idx | follow_from_to_idx | 8       | follow_test.t2.user_id |        1 | Using index |
+----+-------------+------------+--------+--------------------+--------------------+---------+------------------------+----------+-------------+
4 rows in set (18.39 sec)

簡単に実行してみると以下のような時間になる．今度はフォロー数が多い場合に遅い．

ユーザ ID	クエリ実行時間
1	0.03 sec
101	0.11 sec
201	0.12 sec
301	0.12 sec
401	0.23 sec
501	0.37 sec
601	17.00 sec
701	22.36 sec
801	17.13 sec
901	17.57 sec

改善に向けて（１）まとめ

最初に WHERE IN によってフォロー中のユーザのツイートを取得する SQL として以下のようなクエリを書いてみた（SQL1 とする）

SELECT t.id, t.user_id, t.tweet FROM tweet t
  WHERE t.user_id IN (SELECT follow_to FROM follow WHERE follow_from = ?) LIMIT 20;

次に改善案 SQL として以下のようなクエリを書いてみた（SQL2 とする）

SQL2

SELECT t.id, t.user_id, t.tweet FROM tweet t JOIN
  (
    SELECT t2.id FROM tweet t2 
      JOIN follow f ON f.follow_to = t2.user_id AND f.follow_from = ?
  ) AS t1
  ON t1.id = t.id LIMIT 20;

二つの実行時間の結果を比べてみると以下のようになる．

ユーザ ID	フォロー数	SQL1	SQL2
1	0	18.69 sec	0.03 sec
101	10	2.00 sec	0.11 sec
201	20	0.36 sec	0.12 sec
301	25	1.46 sec	0.12 sec
401	50	0.16 sec	0.23 sec
501	100	0.12 sec	0.37 sec
601	120	0.24 sec	17.00 sec
701	250	0.03 sec	22.36 sec
801	500	0.05 sec	17.13 sec
901	700	0.03 sec	17.57 sec

SQL1 はフォロー数が小さい時に実行時間が大きくなり SQL2 はフォロー数が大きい場合に実行時間が大きくなる．うーん．

改善に向けて（２）

gist9952931 の定義からさらに追加して下記コマンドを実行してユニーク制約をつけてみる．

ALTER TABLE follow ADD UNIQUE  `follow_from_to_UNIQUE_idx` (`follow_from`,`follow_to`);

ユーザ ID	フォロー数	SQL1	SQL2
1	0	32.01 sec	0.02 sec
101	10	3.02 sec	0.06 sec
201	20	0.64 sec	0.11 sec
301	25	1.54 sec	0.15 sec
401	50	0.21 sec	0.19 sec
501	100	0.16 sec	0.36 sec
601	120	0.28 sec	2.45 sec
701	250	0.03 sec	2.63 sec
801	500	0.06 sec	3.11 sec
901	700	0.03 sec	3.61 sec

フォロー関係にユニーク制約をつけると SQL2 でフォロー数が多い場合に大きく改善が見えた．

付録：データ準備

user_id は連番が付いているものとする．今回生成したデータは以下のようになる．

項目合計	値
ユーザ	1000
ツイート	1000000
フォロー数	177500

フォロー数内訳．誰をフォローしているかはランダム．

user_id	フォロー数
0 - 99	0
100 - 199	10
200 - 299	20
300 - 399	25
400 - 499	50
500 - 599	100
600 - 699	120
700 - 799	250
800 - 899	500
900 - 999	700

初期化コード

gist9952931

SQL 生成コード

gist9952888

gist9952894

実行コマンド

$ mysqladmin -uadmin create follow_test -p
$ mysql -uadmin follow_test -p < init.sql
$ go run follow.go | mysql -uadmin follow_test -p
$ go run tweet.go  | mysql -uadmin follow_test -p