読者です 読者をやめる 読者になる 読者になる

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

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

問題

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

gist9952931

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

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

事前実験

環境

実施内容

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

項目合計
ユーザ 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 の場合にとても遅いという結果になった.これだと遅すぎるため改善が必要.

改善に向けて(1)

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

第3章 スキーマの最適化とインデックスの 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

改善に向けて(1)まとめ

最初に 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 はフォロー数が大きい場合に実行時間が大きくなる. うーん.

改善に向けて(2)

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