PostgreSQLのプランナがテーブル行数見積りをどうしているか

More than 1 year has passed since last update.

マニアックな話。

PostgreSQLがクエリプランを作成するときに、テーブルに含まれている行数を見積もる方法

density := (reltuples) / (relpages)
(見積り行数) := round(density * (curpages))
  • reltuples: ANALYZEで取得した統計情報のテーブルの行数
  • relpages: ANALYZEで取得したテーブルのページ数
  • curpages: ディスク上のファイルを調べて取得したテーブルのページ数

reltuplesとrelpagesはANALYZEを実行したタイミングで更新される統計情報の値なので、データの挿入や更新、削除によって必ずしも最新の状態を反映していない数値になっている。
かといって、全データを舐めて行数を数えるのは演算コストが大きく時間がかかりすぎる (SELECT count(*) FROM ...; を実行するのと等価)。
ただし、テーブルに何ページ含まれているか(curpages)を数えるのはディスク上のファイルサイズを調べればわかるので、比較的短時間でできる。

そこで、1ページあたりに含まれている行数の密度は多少更新されても変化しないだろう、という前提のもとで、直近のANALYZEによって判明している reltuples と relpages から行密度を計算して、行密度に curpages を掛けることで行数を見積もる、というアプローチがとられている。

実際に↑の計算をしているのは、src/backend/optimizer/util/plancat.cestimate_rel_size関数(定義へのリンク)。

curpages を取得する関数は表面上は RelationGetNumberOfBlocks関数だが、内部での関数呼び出しの階層は深く、結局正味の仕事をしているのはmdnblocks関数である。
コールスタックはこんな感じ。

  • RelationGetNumberOfBlocks マクロ展開→ RelationGetNumberOfBlocksInFork
  • smgrnblocks
  • smgrクラスのnblocksメソッドにディスパッチ
  • 実際にはsmgrクラスの実装はmdの1つしかないので mdnblocks が呼ばれる

このネタを調べた経緯

PostgreSQLの pg_stat_user_tables にある n_live_tup の値(有効な行数)が一体全体何の値を指し示しているのか気になって調べていた。

その最中に pgsql-general のこのスレッドが出てきて、話の中でTom Laneが

The planner doesn't use n_live_tup; the only thing that that's used for
is decisions about when to autovacuum/autoanalyze.

と答えていて、さらに続くメールでは

I'm just curious: where does the planner take the (approximate) row-count from?

It uses the tuple density estimated by the last vacuum or analyze (viz,
reltuples/relpages) and multiplies that by the current relation size.
There are various reasons for not using n_live_tup, some historical and
some still pretty relevant.

とも書いていたので、実際に計算してる場所が気になったので調べてみた。
n_live_tupを使わない "various reasons" も気になるが、とりあえず放置。