マニアックな話。
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.cのestimate_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" も気になるが、とりあえず放置。