とあるクエリを2万倍速にした話 -データベースの気持ちになる- 後編
技術コミュニケーション室 OSSグループの髙﨑です。
本記事は、とあるクエリを2万倍速にした話 -データベースの気持ちになる- 前編の続きです。
前回の記事でお話しした内容がPullRequestを作ったときの過程だったわけですが、 そのような結果に至った経緯、Index Only Scanを使わなかったPostgreSQL特有の事情について、 PostgreSQLのアーキテクチャなども交えもう少し詳しくお話させていただきます。
要するに
- 実行計画のコストとはレコードやindexの読み込み、フィルタ処理などからその実行にどの程度の時間が必要となるかの推定値
- indexを張る際にはそのindexがどのように辿られるかを意識する必要がある
- 範囲検索される可能性があるカラムはindexの先頭にはあまり適さない
- PostgreSQLにおけるIndex Only Scanは新しい/更新頻度の高いデータに対しては効きにくい
- 対象レコードの含まれるブロックに未VACUUMな古いレコードがあった場合対象レコード本体を確認しに行くため
- PostgreSQLの実行計画のFilterサブ処理は暗黙のうちにレコード本体の全体を取得する
- indexに載っていないカラムでも絞り込みができる反面、常にレコード本体の取得が行われることに注意する必要がある
データベースの気持ちになる
まず実行計画のコストとは何なのか
PostgreSQLのプランナが推定および算出するコストとは、DBにおけるデータの読み込み単位であるページ(OSにおける仮想記憶の層で使われる用語のページとは異なります)をシーケンシャルリード、すなわちHDDで磁気ヘッダのシークなしに1個読み込む動作を1とした、その実行計画の実行にどの程度の時間が必要かを見積もった数値です。
ほかにもindexを辿る時のCPUコスト、indexを1行チェックする時に処理コストなど様々な種類がありますが、詳しくはPostgreSQL日本語訳マニュアル プランナコスト定数をご参照ください。
マストドンのユースケースにおいてパラレルワーカーが動作することは滅多にありませんので、実行計画のコストで支配的になるのはページの読み出しコストとなります。
すなわち、おおざっぱに表現するとディスクから読み込むレコードまたはindexの量を減らせば減らすほど実行計画のコストが下がり、また実際に高速となると考えることができます。これについては普段MySQLをお使いの方も「EXPLAINのRowを減らす」という形で似た考え方をされていると思います。
#4750のindexはなぜ良くなかったのか
なぜ良くなかったのか、と書くと前回の記事でお話ししました通り「選択性の低い列から順番にindexを張ってしまっていたから」となるわけですが、逆にその様な張り方をしてしまったにも関わらずなぜ高速化したのでしょうか。
これは実行計画のコストについての項でもお話ししましたとおり、クエリの実行において支配的なのはディスクからデータを取得する待ち時間であることからわかります。
下記が#4750に書いてある改善前の実行計画ですが、
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=0.43..5155.13 rows=15 width=29) (actual time=910.979..3401.273 rows=15 loops=1)
-> Index Scan Backward using notifications_pkey on notifications (cost=0.43..486603.34 rows=1416 width=29) (actual time=910.974..3401.245 rows=15 loops=1)
Filter: ((account_id = *****) AND ((activity_type)::text = ANY ('{Mention,Status,Follow,Favourite}'::text[])))
Rows Removed by Filter: 7990584
Planning time: 0.140 ms
Execution time: 3401.305 ms
(6 rows)
これを見るとnotifications_pkeyをIndex Scan Backward、つまりidを逆順に遡りながらレコード全体を取得し、account_idおよびactivity_typeが異なるものをFilterで合計799万件強捨てるという動作をしていました。
そして#6108の改善前(#4750の改善後)を再掲しますが、
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)
この時のindex_notifications_on_id_and_account_id_and_activity_typeは(id DESC, account_id, activity_type)の順番で張ってあったため、実行時にはindex上のidを辿りながら、account_idによる絞り込みをindex上で行い、その後でactivity_typeによる絞り込みを行っていたと考えられます。
すなわち、#4750改善前のような799万件強を捨てるという明らかな無駄はなくなったものの、依然としてindexを逐次走査する必要がある状態だったと考えられます。
それに対して#6108ではaccount_idによって対象範囲が絞り込まれた後、idの降順にまず15件取得しながらactivity_typeが条件に合わなかった場合にのみ捨てて追加取得するという動作となるため辿るべきindexの量が劇的に少なくなりました。
もっとデータベースの気持ちになる
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;
なぜIndex Only Scanを採用しなかったのか
前回の記事で「普段MySQLをお使いの方であれば『取得するべきカラムが限定されているのになぜIndex Only Scanを使わないのか』と疑問に思われるかと思います」と書きました。
実はこれについては下記の通り試していて、確かにIndex Only Scanとの記述は出ていたものの、速度の向上はありませんでした。
mastodon-production=> CREATE INDEX CONCURRENTLY index_20171225_notify_3 on notifications (account_id, id desc, activity_type, updated_at, activity_id);
CREATE INDEX
mastodon-production=> explain analyze SELECT "notifications"."id", "notifications"."updated_at", "notifications"."activity_type", "notifications"."activity_id" FROM "notifications" WHERE "notifications"."account_id" = 3 AND "notifications"."activity_type" IN ('Mention', 'Status', 'Follow', 'Favourite') ORDER BY "notifications"."id" DESC LIMIT 15;
QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------------------------
--
Limit (cost=0.56..24.56 rows=15 width=33) (actual time=0.033..0.058 rows=15 loops=1)
-> Index Only Scan using index_20171225_notify_3 on notifications (cost=0.56..185436.28 rows=115910 width=33) (actual time=0.032..0.054 rows=15 loops=1
)
Index Cond: (account_id = 3)
Filter: ((activity_type)::text = ANY ('{Mention,Status,Follow,Favourite}'::text[]))
Heap Fetches: 15
Planning time: 0.261 ms
Execution time: 0.088 ms
(7 rows)
これについてはPostgreSQLが追記型アーキテクチャを採用しているという点が関係しています。
PostgreSQLはDELETEやUPDATEを行う際、MySQLのように古いレコードを直接削除や上書きをするのではなく、 UPDATEの場合には空き領域に新しいレコードを書き込み、古いレコードに削除マークを付けるという動作を行います。
それによって万一の電源断などに対する堅牢性を増している一方で、削除マークが付けられた古いレコードを 空き領域へとリサイクルするVACUUMと呼ばれる作業をある程度の間隔で行う必要があります。
私の経験によった話ですが、VACUUMの実行間隔は手動で実行しなければならなかった時代の環境では概ねオフピーク時間帯である早朝ごろに日次で行うものでしたし、 のべ更新削除行数を基準に自動で行ってくれるAUTO VACUUMが実装されているバージョンであるfriends.nicoのPostgreSQLもnotificationsテーブルにおけるAUTO VACUUMの発動は日次より長い間隔となっています。
そして、PostgreSQLではIndex Only Scanを行う上でVisibility Mapと呼ばれる仕組みでIndex上に書いてある値を本当に返してよいのか、 それともページ上のレコード本体を確認するべきかを管理しており、それは対象レコードが含まれるテーブルのブロックに削除マークが付けられたレコードが存在するかどうかが条件となっています。
UPDATEやDELETEと共にindexも書き換えられているはずなのでそのまま返してしまってもよいのではないかと思ってしまいがちですが、 PostgreSQLにおけるIndex Only Scanは比較的新しい機能(といっても2012年9月)であり、それまではIndex Scanによって レコード本体を逐一取得する方法で行っていたためそれとの一貫性を取り安全側に倒した結果としてそうなっているようです。
さて、話を戻しますと対象レコードが含まれるテーブルのブロックに削除マークが付けられたレコードが存在しない状態というのはすなわち、 そのブロックにおいてVACUUMが完了している状態を意味しますが、VACUUMは先ほど書きました通りリアルタイムに行う処理ではありませんので、 今回のクエリのようにidの降順で新しいものを取得する場合にVACUUMが行われている可能性は低いと考えられます。
上記のEXPLAINの結果ではHeap Fetches: 15と書いてある部分がページ上のレコード本体を確認した件数を表しており、
結局15件全てにおいてレコード本体を確認したことがわかります。
であれば、無理にカラムを全てindexに含めてIndex Only Scanを狙うより、(account_id, id DESC)のみに絞ってindexの必要領域を削減したほうが良いだろう、という判断でした。
なぜactivity_typeをindexに含めなかったのか
activity_typeをindexに含めようとした場合、(account_id, activity_type, id DESC)と(account_id, id DESC, activity_type)の二つの場合が考えられますので、それぞれの場合について考えてみます。
(account_id, activity_type, id DESC)
前回の記事の結論である(account_id, id DESC)の間にactivity_typeを素直に挟んだパターンです。
この順番のindexも念のため作ってみてはいたのですが、実行計画に選択されることはありませんでした。
問題のクエリはaccount_idごとの新しい順で取得したいにも関わらず、activity_typeが挟まっていることによりidが降順で一括取得できなくなってしまっており、top-N sort、すなわち複数のソート済み集合から新しい順に取得しまとめるという処理が必要であったため、その分のコストが嵩んだからであると考えられます。
(account_id, id DESC, activity_type)
同様にidの後にactivity_typeを付けたパターンも試していたのですが、こちらも実所要時間に大きな差はありませんでした。
より正確に表現すると、使用するindexとしては選択してもらえたものの、index上のactivity_typeが参照されている様子はありませんでした。
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=0.56..60.81 rows=15 width=33) (actual time=0.032..0.061 rows=15 loops=1)
-> Index Scan using index_20171225_notify_2 on notifications (cost=0.56..9134.20 rows=2274 width=33) (actual time=0.030..0.054 rows=15 loops=1)
Index Cond: (account_id = x)
Filter: ((activity_type)::text = ANY ('{Mention,Status,Follow,Favourite}'::text[]))
Planning time: 0.262 ms
Execution time: 0.086 ms
(6 rows)
試した時には「account_idとidで取得するレコードの一覧を作成し、activity_typeを用いて絞り込んだ後にレコード本体を取得」という動作を期待していたのですが、 PostgreSQLでは複数個の値が指定されたIN演算子は基本的にFilterサブ処理に変換され、 Index ScanのFilterサブ処理をする際には暗黙のうちにレコード本体の全体を取得するようでした。
実際にactivity_typeの条件の個数を変化させてEXPLAINしたところ、一つに絞るまでIndex CondがAND条件となることはありませんでした。
マストドンのユースケースからするとactivity_typeが1種類のみで指定されることはまずなく、 activity_typeを含めるだけでindexのデータサイズが1.5倍強になってしまうため、 迷った結果、indexにはactivity_typeを含めないことにしました。
activity_typeに入り得る5種類の値('Mention', 'Status', 'Follow', 'Favourite', 'FollowRequest')のうち、
FollowRequestだけは単独で指定される可能性がそれなりにありますが、
FollowRequestはそもそも検索条件として指定される頻度が少なく、そこにindexを張る必要性は今のところ感じていません。
どうしても必要そうであれば、CREATE INDEX CONCURRENTLY partitive_index ON notifications (account_id, id DESC) WHERE activity_type = 'FollowRequest'として部分indexを張ることになるでしょう。
