24. PostgreSQL のコスト計算について - PostgreSQL のソースコードを読む

PostgreSQL の Bitmap Scan コスト計算で、怪しいところを見つけたので報告の前に下調べ。

基礎編

コスト計算は教科書通り行われる。Database Management system の 8, 14 章を一通り読めば理解できると思う。

コストは Explain で見られる
start-up コストとは？
- output scan の前にかかるコスト。
- bitmap を作る、ソートする、オンメモりハッシュ作るなど。
total コストとは？
- 全ての行が取り出されると仮定した場合のコスト
コストには、クライアントに行を返す部分は含まれない
伝統的には全てのコストは、ページのフェッチ I/O コスト（seq_page_cost）を 1 として他のパラメータを相対で決める
コストパラメータ。教科書通り。
- seq_page_cost: ディスクから 1 ページフェッチするのにかかるコスト。
- random_page_cost: シーケンシャルではない場合のページフェッチコスト
- cpu_tuple_cost: 1行を CPU であれこれするコスト。例えば取り出したタプルが filer にマッチするか調べるとか。
- cpu_index_tuple_cost: 索引の1回処理
必ず事前に VACUUM ANALYZE を
- 行数の見積もりなどの情報
2回続けて同じクエリを発行するとキャッシュに載る。キャッシュに載ったあとのコストを見た方が良い。

コードの話

backend/optimizer/costsize.c にコスト計算の関数がまとまっている。

SEQ Scan を強制的にオフにするためのコードが面白かった。

Cost disable_cost = 100000000.0;

if (!enable_seqscan)
   startup_cost += disable_cost;

cost_bitmap_heap_scan

お。 where 句が 1つのときに、Index Scan と Bitmap Scan のどちらがコストが高いのかに関して決定的なコード見つけた。

/*
 * Charge a small amount per retrieved tuple to reflect the costs of
 * manipulating the bitmap.  This is mostly to make sure that a bitmap
 * scan doesn't look to be the same cost as an indexscan to retrieve a
 * single tuple.
 */
*cost += 0.1 * cpu_operator_cost * ((IndexPath *) path)->rows;

Index Scan の方が若干コストが高いという事になる。

この辺りも面白い。

/*
 * For small numbers of pages we should charge random_page_cost apiece,
 * while if nearly all the table's pages are being read, it's more
 * appropriate to charge seq_page_cost apiece.	The effect is nonlinear,
 * too. For lack of a better idea, interpolate like this to determine the
 * cost per page.
 */
if (pages_fetched >= 2.0)
cost_per_page = random_page_cost -
(random_page_cost - seq_page_cost) * sqrt(pages_fetched / T);

ここがかなり怪しい。あとで読み返そう。

/*
 * For a single scan, the number of heap pages that need to be fetched
 * is the same as the Mackert and Lohman formula for the case T <= b
 * (ie, no re-reads needed).
 */
pages_fetched = (2.0 * T * tuples_fetched) / (2.0 * T + tuples_fetched);

sort 関連

sort のコスト計算ではオンメモリでソートできるかが大きな鍵となる。

想定される tuple の量が work_mem より小さい場合は、オンメモリソート
上記以外は external ソートとなる（Disk上の merge ソートになる）

Bitmap Heap Scan のメモ

lossy モードは、tid ではなくて、このページを visit しなさいという情報しか残らない。
lossy モードへの移行は、index を読みながら動的に行われる。
具体的には index scan して tid をつっこんでいき、maxentries を超えたら、bitmap 全体を動的に再構築している。

if (tbm->nentries > tbm->maxentries)
tbm_lossify(tbm);

というわけで、
nodeBitmapIndexscan.c で maxentries = work_mem * 1024L となっているので

tbm = tbm_create(work_mem * 1024L);

見積もり tuple 数 > work_mem * 1024L
が成り立つ場合にコストペナルティを課すべき。

リンク

PostgreSQL のソースコードを読む