PostgreSQL: 空間局所性とディスクI/Oを意識してB+treeインデックスを見る

はじめに： 〜Index Only Scan になっているにも関わらず、遅かった〜

こんにちは。最近、スロークエリログが出ていたので EXPLAIN ANALYZE してみたら、ちゃんと Index Only Scan になっているにも関わらず遅いという事象に遭遇しました。

ぱっと見は直感に反する挙動ですが、しっかり調べると、DBMSがデータをディスク上でどう管理しているかという「物理的な挙動」に理由があることがわかりました。

本記事では、この事象を調べる過程で再整理した、インデックス、テーブルデータ、ディスクI/O、そして 「空間局所性」 という概念についてまとめつつ、B+treeインデックスをみていきます。

前提

本記事では以下を想定します。

• DBMSはPostgreSQL
• インデックスはB+tree

また、本記事で登場する図表は全てNano Banana Pro 🍌を用いて作成したものです。

ディスクは「できれば触りたくない」

まず大前提として、DBMSにとってディスク（ストレージ）へのアクセスは、メモリへのアクセスと比較して圧倒的に遅いため、できればやりたくない処理です。

1回あたりのディスクアクセスが数ミリ秒だとしても、数万回、数億回と積み重なれば膨大な時間になります。

HDDの場合は、物理的な動作がボトルネックになります。データを読み取るために、回転する円盤上の目的の位置まで磁気ヘッドを物理的に移動（シーク）させる必要があるためです。「ヘッドの移動」と「回転待ち」というアナログな機械動作が含まれるため、電気的に高速なCPUやメモリと比べると、どうしても遅くなってしまいます。

SSDの場合、HDDのような物理的な可動部品はありません。しかし、それでもメモリ（DRAM）と比較すると、I/Oレイテンシは数桁遅くなります。また、SSDであってもランダムアクセスはシーケンシャルアクセスに比べて、内部的なコマンド処理のオーバーヘッドや、並列性を活かしにくい点などでスループットが落ちる傾向にあります。

つまり、媒体がHDDであれSSDであれ、チューニングの究極の目的は「いかに低速なディスクI/Oを減らし、高速なメモリ上で処理を完結させるか」に尽きます。

PostgreSQLは共有メモリ内の「バッファプール」というメモリ領域を最大限に使います。データアクセスでは必ずこの領域を経由させることで、この速度差を埋めようとしています。そして、このバッファプールの効率を左右するのが、「空間局所性」という概念です。空間局所性とは、「アクセスされたデータの近くにあるデータも、近い将来アクセスされる可能性が高い」という性質を指します。この性質を活かすことで、一度ディスクから読み込んだページに含まれる複数のデータを、その後のアクセスでメモリから高速に取得できるようになります。

B+treeインデックス と テーブル(ヒープ)の構造的な違い

以下はインデックスとテーブル(ヒープ)の関係を表した図です。

B+treeインデックス

B+treeインデックスは大きくわけて、ルートノード、内部ノード、リーフノードの3種類のノードから構成される、平衡木です。すべてのリーフノードが常に同じ深さにあり、ルートノードからリーフノードへの移動を常にO(logN)で行うことができます。

ノードとページ

ノードとは、ツリーを構成する各要素を指します。各ノードは、ディスクや共有バッファなどで管理される「ページ」に対応します。

PostgreSQLにおいて、データの読み書きはこの「ページ」というブロック単位で行われます。たった1行のデータが欲しくても、I/Oは必ずページ単位です。
内部ノードにもリーフノードにも複数のキーが格納されており、1ページには常に関連性の高い複数のキーが含まれています。つまり、ある1つのインデックスキーに対応したデータを取得すると、同じページに含まれる近しいキーのデータもついでにキャッシュされるため、空間局所性を活かしたキャッシュが強制的に行われることになります。

また、範囲検索（Index Range Scan）などの際には、ノードレベルでの空間局所性を活かした先読みが行われることがあります。隣のノードもついでにデータをとってきて、キャッシュしておくという戦略です。つまり、連続したキーへのアクセス（範囲検索など）は、空間局所性をフルに活かすことに繋がります。

内部ノード

検索キーと子ノードへのポインタを保持し、探索ルートを案内する階層です。1つの内部ノードには複数のキーが入っています。

リーフノード

リーフノードには、インデックスキーと、ヒープ内の実データへのポインタである TID (Tuple ID) のペア(インデックス タプル)が複数格納されています。そして、インデックス タプルはインデックスキーの値を基準にソートされています。また、インデックス タプルを複数保持するリーフノード自体も、双方向リストによって隣合うノードと論理的に連結されています。これにより、リーフノード間を双方向にシーケンシャルに移動することが可能になります。 この特性のおかげで、例えばORDER BYでインデックスを活用するときに、昇順でも降順でも同じインデックスを使い回すことができるようになります。範囲検索をする際も、スムーズに隣のノードにアクセスすることができるようになります。

---

インデックスは、インデックスキーを順番に並べた上で保存するのが特徴です。そのため、常に整列コストを払いつつデータを管理する必要があります。Insert時には、そのキーの適切な挿入先を探し、必要に応じてノードを分割し、必要に応じてツリーの高さをリバランスします。このような管理を伴うため、インデックスを増やせば増やすほど、Insertのパフォーマンスは低下します。これが、インデックスショットガン^[1]がアンチパターンである所以です。 また、当然ですが、インデックス自体のデータもディスク上にあることを忘れてはいけません。ノード単位でのキャッシュを意識すること。つまり、ソートされた順序でデータを要求し、空間局所性を活かしたインデックスへのアクセスをすることがパフォーマンスを考えるならば重要です。

テーブル(ヒープ)

一方で、実データが格納されているテーブル本体は、PostgreSQLでは「ヒープ（Heap）」と呼ばれます。Heapとは「山積み」という意味ですが、構造はその名の通りであり、データは空いてるところに順次置いていく方式です。 データは基本的にINSERTされた順、あるいはDELETEで空いた場所に順次詰め込まれていきます。つまり、IDなどの論理的なキーと、物理的な格納位置には何の関係もありません。論理的には隣り合っているデータでも、ディスク上では全く異なる場所に分散していることは珍しくありません。

そのため、ヒープからデータを取るときに、もし「大量の行」をインデックス経由で1行ずつ取ってこようとすると、前述したようなランダムアクセスのオーバーヘッドにより、非常に効率が悪くなります。逆に、テーブルの先頭から順にまとめてデータを取る（シーケンシャルアクセス）場合は、このオーバーヘッドを避けられます。大量のデータを取得する際に、インデックスを使わずテーブルフルスキャンが採用されるのはこういった背景があります。

Index Scanの3つのステップ

ここからは、インデックスでのスキャンについて詳しく見ていきます。

「インデックスを使った検索（Index Scan）」といっても、内部動作を分解すると3つの全く異なるフェーズで構成されています。これらを区別することで、ボトルネックが見えてきます。

ここでは、その挙動を「Phase 1, 2, 3」に分けて説明します。

Phase 1. 垂直探索

まずはツリーを上から下へ降りる動きです。バッファプール上のページを辿り、必要であればディスクから読み込みます。ルートノードから大小比較をして、目的のデータが存在するリーフノード（シークの開始地点）を特定します。
ツリーの高さはデータ量に対してO(logN)のペースで増えます。そのため、数億件のデータでも深さは3〜5階層程度です。従って垂直探索は一瞬で完了するため、基本的にはここがボトルネックになることはありません。

垂直探索ではアクセス述語(Index Cond) を評価し、スキャンの開始位置をピンポイントで特定します。

Phase 2. 水平走査

該当のページ（リーフノード）に到達したら、次はページ間の横移動です。双方向リストを辿りながら、条件に合致するキーを順次読み込んでいきます。リーフページ内のアイテムを走査し、検索条件を満たすキーを探します。ヒット件数（読み取るリーフページの範囲）に比例してコストが高まります。

ここで特に重要になるのが、フィルタ述語の影響です。スキャンの開始位置は決まっていますが、そこから横方向に走査を進める中で、「これは条件に合わない」「これも違う」とデータを次々と捨てながら進むケースがあります。これがフィルタ述語による絞り込みです。
問題は、「走査してI/Oコストを支払う」にもかかわらず「結果を捨てる」という点です。フィルタで除外されるデータ量が多くなればなるほど、無駄なコストが増大し、パフォーマンスの大きな低下を招きます。

---

アクセス述語とフィルタ述語は、実行計画をみると具体的なイメージが持ちやすいです。
例えばusersテーブルがあり、user_idカラムでインデックスを貼っているとします。その上で、以下のようなSQLを実行したとします。

EXPLAIN ANALYZE
SELECT *
FROM users
WHERE user_id = 12345
  AND is_deleted = FALSE;

すると、以下のような実行計画のノードが得られたとします。Index Condはアクセス述語。Filterはフィルタ述語です。スキャン開始地点(user_id = 12345)を求めたあと、候補となるインデックスエントリらが、is_deleted = falseのフィルタを満たすか満たさないか、インデックスエントリを1つずつみていくイメージです。

Index Scan using users_user_id_idx on users
  Index Cond: (user_id = 12345)
  Filter: (is_deleted = false)

後述の Index Only Scan が正しく効いた場合を除き、Filter 判定が必要なインデックスエントリは、インデックス上の情報だけでは結果を確定できません。
さらに、SELECT の対象にインデックス上に存在しないカラムが含まれている場合も、同様にインデックスだけでは結果を確定できません。
これらのケースの場合、 TID を使ってヒープ（テーブル本体）を参照し、実データを取得する処理、つまり Phase 3 のヒープフェッチが発生します。

Phase 3. ヒープフェッチ

最後に、インデックスで見つけたTIDを使って、ヒープ領域に存在する実データを取りに行きます。そして、ここが最大のボトルネックになりがちです。なぜなら、インデックス上では隣り合っているデータでも、実データ（ヒープ）上ではディスクのあちこちに散らばっている可能性が高いからです。非連続的なアクセスとなるため、空間局所性が弱く、各アクセスでページキャッシュミスが発生しやすくなります。

なぜ「インデックスを使っているのに遅い」のか？

インデックスを使っているのに遅いということは、ディスクへのアクセスが発生している可能性が高いです。上記の探索のうち、「Phase 1」は所要ステップの回数が少ないため、「Phase 2」か「Phase 3」のどちらかで発生しているということになります。本章では、「Phase 2」や「Phase 3」でディスクへのアクセスが発生するパターンについていくつか取り上げます。

Case 1: ヒープへのランダムI/Oの多発によるオーバーヘッド

これはインデックス経由でのデータヒット件数が比較的多い場合に発生します。 「Phase 3. ヒープフェッチ」で言及したように、インデックスが指し示す先のテーブルデータ（ヒープ）へのアクセスは非連続的なものとなります。 このアクセス数が多いと、HDDのヘッド移動はもちろん、SSDであってもI/OレイテンシやIOPS消費が積み重なり、大きなオーバーヘッドとなります。

こうなると、PostgreSQLのオプティマイザも「ランダムアクセスを大量に行うより、最初から全てシーケンシャルに読んだ（Seq Scan）ほうが速い」と判断し、インデックスを使用しないか、あるいは無理に使用して逆に遅くなることがあります。

余談: 「カーディナリティ」よりも「選択率」が本質

トピックの、「ヒープへのランダムI/Oの多発によるオーバーヘッド」に関連して、「カーディナリティ（値の種類）が低いカラムにはインデックスを貼るな」という定説について触れます。

これの本質は「選択率」にあります。 選択率とは、「その条件でデータ全体をどの程度まで絞り込めるか」という割合を指します。選択率 = 条件に合致する行数 / テーブル全体の行数です。絞り込んだ結果のインデックスエントリごとに、TIDを用いたヒープフェッチが発生します。

選択率	インデックスは有効か
低い（0に近い、ヒット行数が少ない）	ヒープフェッチの回数が少ないため、インデックスが非常に有効
高い（1に近い、ヒット行数が多い）	ヒープフェッチが大量発生するため、インデックスは有効ではない。テーブルフルスキャン（Seq Scan）の方が高速

具体例： 削除フラグ（is_deleted）

これを理解するために、削除フラグ（is_deleted）というカーディナリティが極端に低いカラムで考えてみます。

値	データ全体に占める割合
削除済み(true)	1%
未削除(false)	99%

上記のように、データに占める割合に偏りがあるとします。

WHERE is_deleted = true （選択率 0.01）の場合

• 全体の中から1%だけをピンポイントで読み取ればよいため、インデックス経由の検索は非常に高速です。「カーディナリティが低いカラム」であっても、選択率が低ければインデックスは有効に機能します。

WHERE is_deleted = false （選択率 0.99）の場合

• 対象が全体の99%にも及びます。この場合、インデックス経由で検索すると、大量のリーフノードを読み込みつつ、その都度ランダムなヒープフェッチが発生します。これなら、最初からインデックスを無視して順次読み込んだ方が速くなります。

つまり、カーディナリティが高いか低いかが直接の決定要因ではなく、「そのクエリ条件における選択率が十分に低いか（十分に絞り込めるか）」が、インデックス有効活用の分かれ道となります。選択率を下げ、ヒープフェッチの回数を減らせるかを念頭にインデックス設計したいものです。

また、これはI/Oの観点で見ると、「ページ密度」の話でもあります。
選択率が高いということは、「1ページあたりに含まれるヒット行数が多い」ということです。1回のI/Oでたくさんの有効なデータが取れるなら、わざわざインデックスを経由してあちこちのページをランダムアクセスするよりも、シーケンシャルにページを舐めたほうが、I/Oの総コストは安くなるのです。

解決策: Index Only Scan

インデックスエントリ1つ1つでヒープアクセスが発生することを防ぐ方法として、カバリングインデックスの定義が挙げられます。SELECTで必要なカラムを全てインデックスに含めてしまえば（=カバリングインデックス）、実データを見に行く必要がなくなります。これにより、Index Only Scanとなり、ランダムアクセスが発生するPhase 3が省略されるため、劇的に高速化されます。

https://www.postgresql.jp/docs/9.6/indexes-index-only-scans.html

ただし、Index Only Scan を理論上の形で動作させるためには、Visibility Map が適切に更新されている必要があります。
PostgreSQL は 追記型のアーキテクチャ(MVCC)を採用しており、テーブルには「過去のトランザクションからは見えるが、現在のトランザクションからは見えてはいけない」行が混在する可能性があります。そして、インデックスには 「その行が現在のトランザクションから可視であるか」 という情報は保存されていません。このため、インデックスだけでは、その行を本当に返して良いのかを判断できず、可視性確認のためにヒープアクセスが必要になる場合があります。そして、この可視性判定の手間を省くための仕組みが Visibility Map です。

Visibility Map は各ページについて「このページに含まれる全ての行が、全トランザクションから見て可視である」という情報をビットマップの形で管理します。

Visibility Map 状態	動作
All Visible	ヒープ参照なし（純粋な Index Only Scan が成立）
All Visibleではない	可視性確認のためにヒープフェッチが発生

注意事項として、頻繁に更新されるテーブルなどでVACUUMが追いついておらず、Visibility Mapがメンテナンスされていない状態だと、「実行計画上は Index Only Scan なのに、裏では大量のヒープフェッチが発生していて遅い」という現象が起きます。つまり、Index Only Scanの性能は Visibility Mapの健全性に依存します。

https://www.postgresql.jp/docs/9.4/storage-vm.html

解決策: Cluster

Index Only Scanが「ヒープへのアクセスそのものを無くす」アプローチだとすれば、もう一つの解決策である「Cluster（クラスタ化）」は、「ヒープへのアクセスをシーケンシャル化する」アプローチです。

先述したように、通常、PostgreSQLのヒープへのデータ格納順序は、インデックスの順序とは無関係です。そのため、インデックススキャンで「論理的には隣り合っているデータ」を取得しようとしても、物理的にはディスク上のあちこちに散らばったページを見に行くことになります。これがランダムI/Oの正体です。

CLUSTERコマンドを使用すると、指定したインデックスの順序に従って、ヒープ自体を物理的に並べ替えることができます。そのため、インデックスと同様空間局所性に基づくページキャッシュを期待できます。コマンド実行時点のワンショットな並び替えであることと、クラスタ化を行っているテーブルでは、その処理が終わるまで排他ロックがかかることには注意が必要ですが、上手く使えば1つの解決策になると思います。

https://www.postgresql.jp/docs/9.4/sql-cluster.html

Case 2: インデックス自体のキャッシュミス

ヒープへのアクセスだけでなく、インデックスそのものを取得する際にもI/Oの遅延は発生します。

空間局所性を背景としたページキャッシュを活かすには、先述したようにインデックスキーの並び順に沿った形で問い合わせることが重要です。
私が今回遭遇したのは、まさしくこの「インデックスアクセス時の順序」が原因で発生したキャッシュミスでした。

具体的には、Hash Joinなどによって順序がバラバラになった結果セットを外側のループとし、内側のテーブルへインデックスアクセスを行うNested Loop Joinが行われていました。

例えば以下のように、100000件のHash Joinの結果をIndex Only Scanに渡したため、ページキャッシュが効かず、毎回キャッシュミスしてディスクへのアクセスが発生してしまっていました(read=94300)。

Nested Loop  (actual time=45.500..3250.420 rows=100000 loops=1)
  Buffers: shared hit=5200 read=94800
  ->  Hash Join  (actual time=15.000..85.000 rows=100000 loops=1)
        Hash Cond: (orders.customer_id = customers.id)
        Buffers: shared hit=2000 read=500
        ->  Seq Scan on orders  (actual time=0.010..30.000 rows=100000 loops=1)
              Buffers: shared hit=1000 read=250
        ->  Hash  (actual time=10.000..10.000 rows=50000 loops=1)
              Buckets: 65536  Batches: 1  Memory Usage: 3000kB
              Buffers: shared hit=1000 read=250
              ->  Seq Scan on customers  (actual time=0.005..8.000 rows=50000 loops=1)
                    Buffers: shared hit=1000 read=250
  ->  Index Only Scan using idx_items_order_id on order_items  (actual time=0.005..0.028 rows=1 loops=100000)
        Index Cond: (order_id = orders.id)
        Heap Fetches: 0
        Buffers: shared hit=3200 read=94300

なぜ「順序」が重要なのか

インデックスのリーフノード（ページA）には、キー（1, 2, 3...）がソートされた状態で格納されています。
検索キーが昇順（1, 2, 3...）であれば、一度ページAを読み込むだけで、そこに含まれるキーをすべて処理できます。空間局所性を活かしたページキャッシュが効いています。

しかし、問い合わせてくるキーの順序がデタラメ（1, 100, 2, 99...）だった場合どうなるでしょうか。「ページA（キー1） → ページZ（キー100） → ページA（キー2）...」のように、右往左往ページへランダムにアクセスすることになります。こうなると、せっかくキャッシュしたページが再利用される前にバッファプールから追い出されてしまい、同じページに対して何度もディスクI/Oが発生するという非効率な状態に陥ります。

結果として、「Index Only Scanだからヒープへのアクセスはないと思ったのに、インデックス自体の読み込みで大量のI/Oが発生して遅い」という現象が起きていました。

解決策: インデックスアクセスの入力キーをソート（整列）させる

クエリの構造を見直し、問い合わせる前に、問い合わせに使うキーをソートし、それからインデックスにアクセスするような実行計画にするようチューニングすることが解決策として挙げられます。
これにより、空間局所性を背景としたページキャッシュが効くようになるため、パフォーマンスの悪化を防止できます。

おわりに

スロークエリが起きる場合の原因は様々です。統計情報がきちんと更新されているならば、原因は何でしょうか。色々あると思いますが、キャッシュミスによるヒープフェッチや、SortやGroup byの際のtemp落ちなど、「ディスクへのアクセスが伴っている可能性」をまず疑うのは、基本的には間違いないのではと思います。

実行計画を眺めたときに、単にインデックスが使われているかだけでなく、「そのアクセスは物理的にスムーズか？」「空間局所性を活かせているか？」という視点を持つことで、ボトルネックの真因が見えてくることがあります。

EXPLAINの向こう側に、ディスクへのI/Oがひそんでいないかという視点を持つことを、心がけていきたいなと思います。

参考

• Database Design and Implementation: For Data-Centric Applications(2019)
• Use The Index, Luke!
• SQL実践入門 ― 高速でわかりやすいクエリの書き方(2015)
• 内部構造から学ぶPostgreSQL―設計・運用計画の鉄則(2022)

脚注

1. SQLアンチパターンより