技術コミュニケーション室 OSSグループの髙﨑です。

当グループでは、マストドンというオープンソースの分散型マイクロブログについて、 弊社が運営するインスタンス「friends.nico」の運営、独自機能の開発、運用、ならびにそれらで得た知見を上流のプレーンなマストドンへcontributeするという業務を主に行っています。

本記事では、tableに適切なindexを張ることによってとあるスロークエリの速度改善を行った事例について、実際に上流へ行ったPullRequestをベースにお話させていただきます。

内容としては反面教師とするべき失敗例を伴った、非常に基礎的なPostgreSQLの実行計画の読み方ならびにクエリに合わせたindexの張り方です。

また、表題の2万倍速というのは改善前の最悪の場合比であり嘘ではないものの、通常問い合わせされる範囲の条件ではだいたい3〜30倍速であるということを予め申し上げておきます。

要するに

• マストドンのテーブルのindexが
  • 肥大化してスロークエリが出始めた
  • より適切なものに張り直した
  • それにあたって実行計画を正しく理解しながら読んだ
• 実行計画とは
  • 入力されたクエリを処理するためにどのような内部処理をどの手順で行えば良いかを示す木構造
  • PostgreSQLのEXPLAINで示される実行計画の基礎的な読み方を示した
• 複数カラムに対してindexを張る際には
  • WHERE句の条件として用いられているカラムの中で
    • 選択性が高いものから順番に、ただし選択性だけではなくWHERE句でどのように指定されうるかも考える
    • 選択性が低い場合はindexのサイズも考慮して含めないという選択も考える
  • ORDER BY句の条件に指定されたカラムは
    • 選択性が高く、かつ複数指定や広い範囲の指定がされにくいカラムの後に書く

背景・前提知識

マストドンはマイクロブログサービスを分散型で実現するオープンソースソフトウェアです。

マイクロブログサービスとは短文投稿サービスとも訳される、数百字程度までの比較的短い文章を投稿し公開することができるサービスであり、最も代表的なものとしてtwitterが挙げられます。

マストドンはそのようなマイクロブログサービスを、httpsのREST APIによるpush/pullで連携することにより、管理主体が異なる複数のサーバ間であってもtwitterのようなフォロー/フォロワー関係、およびメッセージの送受信を実現するソフトウェアです。

サーバサイドの内部構成はRuby on Rails、Sidekiq、Node.js、それらのバックエンドとしてRedisとPostgreSQLを使用しています。

今回問題になったクエリ

さて、今回問題になったクエリは下記の通りです。

SELECT  "notifications"."id", "notifications"."updated_at", "notifications"."activity_type", "notifications"."activity_id" 
FROM "notifications" WHERE "notifications"."account_id" = $1 
AND "notifications"."activity_type" IN ('Mention', 'Status', 'Follow', 'Favourite')
ORDER BY "notifications"."id" DESC LIMIT $2;

マストドンにおけるnotificationsテーブルは被フォロー、返信など各ユーザに対しての通知が格納されているテーブルで、 friends.nicoではこのnotificationsテーブルが非常に巨大になる利用傾向となっています。

これによりDBに負荷がかかる、あるいはユーザがページを開いてからReactで非同期取得しているため通知内容が表示されるまでの時間が長い、といった問題点がありました。

これについては以前にもindexを追加するPullRequest(#4750)を送ってmargeされているのですが、 今回はレコード数の増加に伴いその時のindexを使用してもスロークエリとなってしまったためindexをより適切なものに張り直しました。 その内容がこちらのPullRequest(#6108)です。

複数カラムのindexを張る

複数カラムに対するindexを張る際は、かなり乱暴に一言で言ってしまえば「WHERE句に指定される条件を書き、続いてORDER BY句に指定される条件を書く」というのが基本であるものの、これは非常にお恥ずかしい話ですが#4750の時点で既に守れていませんでした。

「WHERE句に指定される条件を書き、続いてORDER BY句に指定される条件を書く」に素直に従えば張るべきindexは(account_id, activity_type,id DESC)との順番になるわけですが、#4750では私の知識不足から(id DESC, account_id, activity_type)という順番で張ってしまっていました。

とはいえ#4750以前はそもそもこのクエリに使用できるindexが存在せず、主キーを用いた逐次スキャンで探していたという有様だったため、それと比べればこれでも遥かに高速でした。 よく見るとこの時も改善前比1.25万〜10万倍速という恐ろしい数字が出ています。

PostgreSQLのプランナ(実行計画作成部)はクエリの条件部に書いてあるカラムがindexの部分集合であれば順番が違っていても使用を検討してくれ、またそれで十分に効率的であると考えられれば使用してくれるからでした。

より適切なindexに張り直す

しかしながら前述しましたとおり、notificationsテーブルのレコード数の増加によって当該のクエリは再びスロークエリログに記録されるようになり、indexの張り直しを検討する必要が出てきました。

実行計画を読む

そこでまず行ったのが実行計画をもっと正しく理解しながら読み込むことでした。

実行計画とは、入力されたクエリを処理するためにどのような内部処理をどの手順で行えば良いかを示す、内部処理を根、節、葉とする木構造です。

PostgreSQLを含むRDBMSは入力されたクエリに対して複数の実行計画を生成し、その中で最も高速に実行できそうなものを選んで実際に実行します。

PostgreSQLでは、EXPLAIN文を用いるとその後に続けて記述したクエリを実行するために推定した最も高速に実行できそうと考えられる実行計画を表示してくれます。 また、ANALYZEオプションを付けることにより、その実行計画を実際に実行した結果かかった時間などを一緒に表示してくれます。

ANALYZEオプションは実際に文を実行するため、INSERT、UPDATE、DELETEなどの内容を操作する文である場合、その結果がDBに反映されてしまいますので、必ずトランザクション内で実行し、COMMITせずにROLLBACKしてください。　参照:PostgreSQL日本語訳マニュアル EXPLAIN

下記は、本番環境のDBスナップショットから作成した検証用DBにおいて、新しいindexを張る前の実行計画です。

mastodon-production=> explain analyze SELECT  "notifications"."id", "notifications"."updated_at", "notifications"."activity_type", "notifications"."activity_id" FROM "notifications" WHERE "notifications"."account_id" = $1 AND "notifications"."activity_type" IN ('Mention', 'Status', 'Follow', 'Favourite') ORDER BY "notifications"."id" DESC LIMIT 20;
                                                                                          QUERY PLAN                                                        
                                  
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.56..4347.50 rows=20 width=33) (actual time=56.979..1990.931 rows=20 loops=1)
   ->  Index Scan using index_notifications_on_id_and_account_id_and_activity_type on notifications  (cost=0.56..494247.53 rows=2274 width=33) (actual time=56.975..1990.906 rows=20 loops=1)
         Index Cond: (account_id = $1)
         Filter: ((activity_type)::text = ANY ('{Mention,Status,Follow,Favourite}'::text[]))
 Planning time: 0.145 ms
 Execution time: 1990.972 ms
(6 rows)

水平線の後の行からPlanning timeの前の行までが実行計画を表したもので、最も上の行に書いてある処理（実行計画の根）の実行が終わると結果が全て揃ってそのクエリの実行が完了すること、またそのためにはそれよりも下に書かれている（すなわち木構造の節や葉である）内部処理を行う必要があることを表しています。

上記例ではLimit処理が実行計画の根、Index Scan処理が唯一の葉となっています。ツリーの深さは通常、インデントによって表現されます。

まず実行計画の根であるLimit処理を例にしますと、

(cost=0.56..4347.50 rows=20 width=33)はプランナがテーブルの統計情報に基づいて推定した数値です。

(actual time=56.979..1990.931 rows=20 loops=1)が実際に実行してみた際の数値です。

という内容になっています。 そしてこのLimitの元データを揃えるためにその下のIndex Scan using index_notifications_on_id_and_account_id_and_activity_type on notificationsが必要とされており、

実行計画の木構造はクエリの内容により3段以上に深くなったり、上記例に登場していない種類の内部処理が行われることもありますが、もっと詳しい読み方についてはPostgreSQL日本語訳マニュアル EXPLAINの利用を参照してください。

データの傾向を考える

本記事の前のほうでは複数カラムに対するindexを張る際の基本的考え方について、「WHERE句とORDER BY句に指定された条件を順番に書く」と書きましたが、 「WHERE句の条件として用いられているカラムの中で対象レコードの範囲を最も狭められるもの（選択性が高いもの）から順番に、そしてORDER BY句の条件に指定されたカラムは他カラムの選択性を考慮してフィルタさせるかソートさせるかを考え適切な位置に差し込む」というのがより正しい表現となります。

それに従って、今回問題のクエリをもう一度見てみましょう。

SELECT "notifications"."id", "notifications"."updated_at", "notifications"."activity_type", "notifications"."activity_id" FROM "notifications" WHERE "notifications"."account_id" = $1 AND "notifications"."activity_type" IN ('Mention', 'Status', 'Follow', 'Favourite') ORDER BY "notifications"."id" DESC LIMIT $2;

WHERE句の条件として指定されているのはaccount_idとactivity_typeですが、その中で対象レコードの範囲をより狭められるのはどちらかといえばaccount_idです。

notificationsテーブルは前述しましたとおり各ユーザに対しての各種通知が格納されているテーブルですから、59,699人(2018/01/10時点)のユーザがいるfriends.nicoではこれを用いて絞り込むだけで単純計算で6万分の1程度にまで範囲が絞りこまれ、取得して調べる必要のあるレコードが劇的に少なくなります。

また、account_idカラムに指定される条件はその内容が通知対象ユーザのIDであることからも想像できる通り必ず単一の値であって、 BETWEENなどを用いた範囲検索やIN演算子を用いた複数指定は行われないため、その点からしてもindexの最初に書くカラムとして適しています。

逆にactivity_typeについては今回は結局indexの対象にしませんでした。 なぜならactivity_typeに入り得る値はマストドンのコードより'Mention', 'Status', 'Follow', 'Favourite', 'FollowRequest'の5種類ですが、 文字列をindex対象に含めるコストに見合うほどの範囲の狭まり方をするようには思えなかったからです。

そして「ORDER BY句の条件に指定されたカラムは他カラムの選択性を考慮してフィルタさせるかソートさせるかを考え適切な位置に差し込む」ということで、 今回選択性の低いactivity_typeはindexに含めずフィルタさせることにしましたので、単純にaccount_idの後に付けるということになります。

以上の事から作成するべきindexは(account_id, id DESC)の順番であり、 CREATE INDEX CONCURRENTLY new_index ON notifications (account_id, id DESC)という文に行き着き、 これをRailsの書き方で書いたものが#6108のPullRequestというわけです。

indexを貼った後の実行計画は下記の通りです。

                                                                        QUERY PLAN                                                                        
----------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.56..80.72 rows=20 width=33) (actual time=0.030..0.073 rows=20 loops=1)
   ->  Index Scan using new_index on notifications  (cost=0.56..9114.20 rows=2274 width=33) (actual time=0.028..0.062 rows=20 loops=1)
         Index Cond: (account_id = $1)
         Filter: ((activity_type)::text = ANY ('{Mention,Status,Follow,Favourite}'::text[]))
 Planning time: 0.153 ms
 Execution time: 0.099 ms
(6 rows)

使用するindexが変わった以外の差異はありませんが、プランナが算出した推定コストも、実所要時間も劇的に短くなっていることがわかります。

ここまでお読みになった普段MySQLをお使いの方であれば「取得するべきカラムが限定されているのになぜIndex Only Scanを使わないのか」と疑問に思われるかと思いますが、 これはPostgreSQLとMySQLの設計方針および実装の違いからくる判断の結果であり、それについては次回の記事でお話することにします。