エグゼキュータ。LimitとSort
8.3からORDER BYとLIMITの組み合わせが改良されたということで、どう処理されるのか見てみた。参考にしたのは以下のページ。
マイコミジャーナルの記事ではoffsetをつけた場合には最適化が適用されないとあったが、PostgreSQL 8.3.5で試す限り、offsetをつけても最適化されているように見える（実行計画と実際の処理をdebugで確かめた）。
クエリ（explain analyze verboseつき）
1000000万件あるデータから10件を取り出す。
explain analyze verbose select * from accounts order by abalance limit 10
プランツリーと実行計画
{LIMIT
:startup_cost 47485.60
:total_cost 47485.63
:plan_rows 10
:plan_width 97
:targetlist (
{TARGETENTRY
:expr
{VAR
:varno 65001
:varattno 1
:vartype 23
:vartypmod -1
:varlevelsup 0
:varnoold 1
:varoattno 1
}
:resno 1
:resname aid
:ressortgroupref 0
:resorigtbl 16453
:resorigcol 1
:resjunk false
}
{TARGETENTRY
:expr
{VAR
:varno 65001
:varattno 2
:vartype 23
:vartypmod -1
:varlevelsup 0
:varnoold 1
:varoattno 2
}
:resno 2
:resname bid
:ressortgroupref 0
:resorigtbl 16453
:resorigcol 2
:resjunk false
}
{TARGETENTRY
:expr
{VAR
:varno 65001
:varattno 3
:vartype 23
:vartypmod -1
:varlevelsup 0
:varnoold 1
:varoattno 3
}
:resno 3
:resname abalance
:ressortgroupref 1
:resorigtbl 16453
:resorigcol 3
:resjunk false
}
{TARGETENTRY
:expr
{VAR
:varno 65001
:varattno 4
:vartype 1042
:vartypmod 88
:varlevelsup 0
:varnoold 1
:varoattno 4
}
:resno 4
:resname filler
:ressortgroupref 0
:resorigtbl 16453
:resorigcol 4
:resjunk false
}
)
:qual <>
:lefttree
{SORT
:startup_cost 47485.60
:total_cost 49985.76
:plan_rows 1000062
:plan_width 97
:targetlist (
{TARGETENTRY
:expr
{VAR
:varno 65001
:varattno 1
:vartype 23
:vartypmod -1
:varlevelsup 0
:varnoold 1
:varoattno 1
}
:resno 1
:resname aid
:ressortgroupref 0
:resorigtbl 16453
:resorigcol 1
:resjunk false
}
{TARGETENTRY
:expr
{VAR
:varno 65001
:varattno 2
:vartype 23
:vartypmod -1
:varlevelsup 0
:varnoold 1
:varoattno 2
}
:resno 2
:resname bid
:ressortgroupref 0
:resorigtbl 16453
:resorigcol 2
:resjunk false
}
{TARGETENTRY
:expr
{VAR
:varno 65001
:varattno 3
:vartype 23
:vartypmod -1
:varlevelsup 0
:varnoold 1
:varoattno 3
}
:resno 3
:resname abalance
:ressortgroupref 1
:resorigtbl 16453
:resorigcol 3
:resjunk false
}
{TARGETENTRY
:expr
{VAR
:varno 65001
:varattno 4
:vartype 1042
:vartypmod 88
:varlevelsup 0
:varnoold 1
:varoattno 4
}
:resno 4
:resname filler
:ressortgroupref 0
:resorigtbl 16453
:resorigcol 4
:resjunk false
}
)
:qual <>
:lefttree
{SEQSCAN
:startup_cost 0.00
:total_cost 25874.62
:plan_rows 1000062
:plan_width 97
:targetlist (
{TARGETENTRY
:expr
{VAR
:varno 1
:varattno 1
:vartype 23
:vartypmod -1
:varlevelsup 0
:varnoold 1
:varoattno 1
}
:resno 1
:resname aid
:ressortgroupref 0
:resorigtbl 16453
:resorigcol 1
:resjunk false
}
{TARGETENTRY
:expr
{VAR
:varno 1
:varattno 2
:vartype 23
:vartypmod -1
:varlevelsup 0
:varnoold 1
:varoattno 2
}
:resno 2
:resname bid
:ressortgroupref 0
:resorigtbl 16453
:resorigcol 2
:resjunk false
}
{TARGETENTRY
:expr
{VAR
:varno 1
:varattno 3
:vartype 23
:vartypmod -1
:varlevelsup 0
:varnoold 1
:varoattno 3
}
:resno 3
:resname abalance
:ressortgroupref 1
:resorigtbl 16453
:resorigcol 3
:resjunk false
}
{TARGETENTRY
:expr
{VAR
:varno 1
:varattno 4
:vartype 1042
:vartypmod 88
:varlevelsup 0
:varnoold 1
:varoattno 4
}
:resno 4
:resname filler
:ressortgroupref 0
:resorigtbl 16453
:resorigcol 4
:resjunk false
}
)
:qual <>
:lefttree <>
:righttree <>
:initPlan <>
:extParam (b)
:allParam (b)
:scanrelid 1
}
:righttree <>
:initPlan <>
:extParam (b)
:allParam (b)
:numCols 1
:sortColIdx 3
:sortOperators 97
:nullsFirst false
}
:righttree <>
:initPlan <>
:extParam (b)
:allParam (b)
:limitOffset <>
:limitCount
{CONST
:consttype 20
:consttypmod -1
:constlen 8
:constbyval false
:constisnull false
:constvalue 8 [ 10 0 0 0 0 0 0 0 ]
}
}
Limit (cost=47485.60..47485.63 rows=10 width=97) (actual time=3300.073..3300.073 rows=10 loops=1)
-> Sort (cost=47485.60..49985.76 rows=1000062 width=97) (actual time=3300.073..3300.073 rows=10 loops=1)
Sort Key: abalance
Sort Method: top-N heapsort Memory: 18kB
-> Seq Scan on accounts (cost=0.00..25874.62 rows=1000062 width=97) (actual time=0.000..1360.033 rows=1000000 loops=1)
Total runtime: 3300.073 msLimitの処理はExecLimit()、Sortの処理はExecSort()で行われる。
- ExecLimit()
- offset指定なしは 0 を指定したのと同じ。
- 結果のタプルを下位ノードから受け取るが、offsetを満たすまではループして捨てる。
- 一度offsetを超えたら、limitになるまでは1件ごとに上位へタプルを返す。
- 結果がなくなるかlimitになったらNULLを返して処理終わり。
- ExecSort()
- 最初のアクセスでは、下位のノードから受け取ったタプルをひたすらtuplesort_puttupleslot()をつかってputする。今回の例だと1000000回。そしてtuplesort_performsort()でソートする。
- ソートされた結果をTupleTableSlotに詰めて返す。
- 2度目以降のアクセスではソート済みのデータを単に返すだけ。
- puttuple_common()
- tuplesort_puttupleslot()から呼び出される。
- 最初は（TSS_INITIALの状態）タプルをメモリにためていく。
- limitの2倍に達するか、メモリが足りなくなったらmake_bounded_heap()を呼び出し、limit分だけしか保持しないようにする。TSS_BOUNDEDの状態に移行する。
- TSS_BOUNDEDの状態になったら、limit分の件数だけを保持する。この例の場合、より小さい値がきたら、今までのなかでもっとも大きいデータを破棄（しているっぽい）。
まとめ
limit分の件数だけを保持し、それだけをソートするというのが8.3から最適化の内容らしい。8.2以前では、limitに関係なく全データをソートしていたのだろう。今回の例だとソート対象が10件か1000000件かだから違いは大きい。
tuplesort.cは今のところ軽くみただけ。いずれちゃんと読む。
エグゼキュータ。ビットマップヒープスキャン（Bitmap Heap Scan）
たまに実行計画で見かけるBitmap Heap Scan や Bitmap Index Scan が気になり調べてみた。ここの解説がわかりやすい。
【PostgreSQLウォッチ】第17回 新しい実行プラン・タイプによるPostgreSQL 8.1の性能向上
Indexの種類としてビットマップインデックスというものがB-Treeインデックスに並ぶものとしてあるというわけではなく、実行時にビットマップを使うよということ。ビットマップヒープスキャンが行われそうなクエリを投げて実行される処理を確認する。
ドキュメントで触れているのはここかな。
11.5. 複数のインデックスの組み合わせ
他のRDBMSでインデックスマージと呼んでいるものと同じなのかもしれない。
クエリ（explain analyze verboseつき）
aidにはインデックスが張られている。aidに対してはorで検索。bidにはインデックスは張られていないが、bid = 1 としたのはインデックス以外の条件が含められた場合を確認するため。
explain analyze verbose select aid from accounts where bid = 1 and ( aid = 100 or aid = 500 or aid = 1000 )
結果
プランツリーと実行計画。
{BITMAPHEAPSCAN
:startup_cost 13.04
:total_cost 24.97
:plan_rows 1
:plan_width 4
:targetlist (
{TARGETENTRY
:expr
{VAR
:varno 1
:varattno 1
:vartype 23
:vartypmod -1
:varlevelsup 0
:varnoold 1
:varoattno 1
}
:resno 1
:resname aid
:ressortgroupref 0
:resorigtbl 16453
:resorigcol 1
:resjunk false
}
)
:qual (
{OPEXPR
:opno 96
:opfuncid 65
:opresulttype 16
:opretset false
:args (
{VAR
:varno 1
:varattno 2
:vartype 23
:vartypmod -1
:varlevelsup 0
:varnoold 1
:varoattno 2
}
{CONST
:consttype 23
:consttypmod -1
:constlen 4
:constbyval true
:constisnull false
:constvalue 4 [ 1 0 0 0 ]
}
)
}
)
:lefttree
{BITMAPOR
:startup_cost 13.04
:total_cost 13.04
:plan_rows 3
:plan_width 0
:targetlist <>
:qual <>
:lefttree <>
:righttree <>
:initPlan <>
:extParam (b)
:allParam (b)
:bitmapplans (
{BITMAPINDEXSCAN
:startup_cost 0.00
:total_cost 4.35
:plan_rows 1
:plan_width 0
:targetlist <>
:qual <>
:lefttree <>
:righttree <>
:initPlan <>
:extParam (b)
:allParam (b)
:scanrelid 1
:indexid 16464
:indexqual (
{OPEXPR
:opno 96
:opfuncid 65
:opresulttype 16
:opretset false
:args (
{VAR
:varno 1
:varattno 1
:vartype 23
:vartypmod -1
:varlevelsup 0
:varnoold 1
:varoattno 1
}
{CONST
:consttype 23
:consttypmod -1
:constlen 4
:constbyval true
:constisnull false
:constvalue 4 [ 100 0 0 0 ]
}
)
}
)
:indexqualorig (
{OPEXPR
:opno 96
:opfuncid 65
:opresulttype 16
:opretset false
:args (
{VAR
:varno 1
:varattno 1
:vartype 23
:vartypmod -1
:varlevelsup 0
:varnoold 1
:varoattno 1
}
{CONST
:consttype 23
:consttypmod -1
:constlen 4
:constbyval true
:constisnull false
:constvalue 4 [ 100 0 0 0 ]
}
)
}
)
:indexstrategy (i 3)
:indexsubtype (o 23)
}
{BITMAPINDEXSCAN
:startup_cost 0.00
:total_cost 4.35
:plan_rows 1
:plan_width 0
:targetlist <>
:qual <>
:lefttree <>
:righttree <>
:initPlan <>
:extParam (b)
:allParam (b)
:scanrelid 1
:indexid 16464
:indexqual (
{OPEXPR
:opno 96
:opfuncid 65
:opresulttype 16
:opretset false
:args (
{VAR
:varno 1
:varattno 1
:vartype 23
:vartypmod -1
:varlevelsup 0
:varnoold 1
:varoattno 1
}
{CONST
:consttype 23
:consttypmod -1
:constlen 4
:constbyval true
:constisnull false
:constvalue 4 [ -12 1 0 0 ]
}
)
}
)
:indexqualorig (
{OPEXPR
:opno 96
:opfuncid 65
:opresulttype 16
:opretset false
:args (
{VAR
:varno 1
:varattno 1
:vartype 23
:vartypmod -1
:varlevelsup 0
:varnoold 1
:varoattno 1
}
{CONST
:consttype 23
:consttypmod -1
:constlen 4
:constbyval true
:constisnull false
:constvalue 4 [ -12 1 0 0 ]
}
)
}
)
:indexstrategy (i 3)
:indexsubtype (o 23)
}
{BITMAPINDEXSCAN
:startup_cost 0.00
:total_cost 4.35
:plan_rows 1
:plan_width 0
:targetlist <>
:qual <>
:lefttree <>
:righttree <>
:initPlan <>
:extParam (b)
:allParam (b)
:scanrelid 1
:indexid 16464
:indexqual (
{OPEXPR
:opno 96
:opfuncid 65
:opresulttype 16
:opretset false
:args (
{VAR
:varno 1
:varattno 1
:vartype 23
:vartypmod -1
:varlevelsup 0
:varnoold 1
:varoattno 1
}
{CONST
:consttype 23
:consttypmod -1
:constlen 4
:constbyval true
:constisnull false
:constvalue 4 [ -24 3 0 0 ]
}
)
}
)
:indexqualorig (
{OPEXPR
:opno 96
:opfuncid 65
:opresulttype 16
:opretset false
:args (
{VAR
:varno 1
:varattno 1
:vartype 23
:vartypmod -1
:varlevelsup 0
:varnoold 1
:varoattno 1
}
{CONST
:consttype 23
:consttypmod -1
:constlen 4
:constbyval true
:constisnull false
:constvalue 4 [ -24 3 0 0 ]
}
)
}
)
:indexstrategy (i 3)
:indexsubtype (o 23)
}
)
}
:righttree <>
:initPlan <>
:extParam (b)
:allParam (b)
:scanrelid 1
:bitmapqualorig (
{BOOLEXPR
:boolop or
:args (
{OPEXPR
:opno 96
:opfuncid 65
:opresulttype 16
:opretset false
:args (
{VAR
:varno 1
:varattno 1
:vartype 23
:vartypmod -1
:varlevelsup 0
:varnoold 1
:varoattno 1
}
{CONST
:consttype 23
:consttypmod -1
:constlen 4
:constbyval true
:constisnull false
:constvalue 4 [ 100 0 0 0 ]
}
)
}
{OPEXPR
:opno 96
:opfuncid 65
:opresulttype 16
:opretset false
:args (
{VAR
:varno 1
:varattno 1
:vartype 23
:vartypmod -1
:varlevelsup 0
:varnoold 1
:varoattno 1
}
{CONST
:consttype 23
:consttypmod -1
:constlen 4
:constbyval true
:constisnull false
:constvalue 4 [ -12 1 0 0 ]
}
)
}
{OPEXPR
:opno 96
:opfuncid 65
:opresulttype 16
:opretset false
:args (
{VAR
:varno 1
:varattno 1
:vartype 23
:vartypmod -1
:varlevelsup 0
:varnoold 1
:varoattno 1
}
{CONST
:consttype 23
:consttypmod -1
:constlen 4
:constbyval true
:constisnull false
:constvalue 4 [ -24 3 0 0 ]
}
)
}
)
}
)
}
Bitmap Heap Scan on accounts (cost=13.04..24.97 rows=1 width=4) (actual time=0.000..0.000 rows=3 loops=1)
Recheck Cond: ((aid = 100) OR (aid = 500) OR (aid = 1000))
Filter: (bid = 1)
-> BitmapOr (cost=13.04..13.04 rows=3 width=0) (actual time=0.000..0.000 rows=0 loops=1)
-> Bitmap Index Scan on accounts_pkey1 (cost=0.00..4.35 rows=1 width=0) (actual time=0.000..0.000 rows=1 loops=1)
Index Cond: (aid = 100)
-> Bitmap Index Scan on accounts_pkey1 (cost=0.00..4.35 rows=1 width=0) (actual time=0.000..0.000 rows=1 loops=1)
Index Cond: (aid = 500)
-> Bitmap Index Scan on accounts_pkey1 (cost=0.00..4.35 rows=1 width=0) (actual time=0.000..0.000 rows=1 loops=1)
Index Cond: (aid = 1000)"
Total runtime: 0.000 ms
実行計画とプランツリーについて気づいたこと
- 実行計画がどのように出力されるかはExplainOnePlan()あたりを見るとわかる
- Recheck Cond は bitmapqualorig に対応
- Filter は qual に対応
- Index Cond は indexqualorig に対応
- explain verboseだとPlannedStmtのノードが出力されない（デバッグ出力と異なりPlannedStmtのメンバのplanTreeが出力対象になっている）。だからどのリレーションにアクセスしようとしているのかわからない。
- righttreeは空。
実行時の処理
とりあえずbtで呼び出しシーケンス（抜粋）。
(gdb) bt #0 _bt_next (scan=0x84d5f48, dir=ForwardScanDirection) at nbtsearch.c:923 #1 0x080aee63 in btgetmulti (fcinfo=0xbfe18c20) at nbtree.c:326 #2 0x0831e0c5 in FunctionCall4 (flinfo=0x84f5a70, arg1=139288392, arg2=3219230352, arg3=1024, arg4=3219230348) at fmgr.c:1331 #3 0x080a8d85 in index_getmulti (scan=0x84d5f48, tids=0xbfe18e90, max_tids=1024, returned_tids=0xbfe18e8c) at indexam.c:708 #4 0x0819ed5e in MultiExecBitmapIndexScan (node=0x84d5e40) at nodeBitmapIndexscan.c:94 #5 0x0818f67e in MultiExecProcNode (node=0x84d5e40) at execProcnode.c:460 #6 0x0819e180 in MultiExecBitmapOr (node=0x84d5da0) at nodeBitmapOr.c:151 #7 0x0818f69e in MultiExecProcNode (node=0x84d5da0) at execProcnode.c:468 #8 0x0819e49e in BitmapHeapNext (node=0x84d4420) at nodeBitmapHeapscan.c:114 #9 0x08197b6b in ExecScan (node=0x84d4420, accessMtd=0x819e35c <BitmapHeapNext>) at execScan.c:103 #10 0x0819e97f in ExecBitmapHeapScan (node=0x84d4420) at nodeBitmapHeapscan.c:335 #11 0x0818f45d in ExecProcNode (node=0x84d4420) at execProcnode.c:344 #12 0x0818d14a in ExecutePlan (estate=0x84d4290, planstate=0x84d4420, operation=CMD_SELECT, numberTuples=0, direction=ForwardScanDirection, dest=0x8503a08) at execMain.c:1335
上位の関数から見ていく。
- ExecBitmapHeapScan()
- 実行計画のBitmap Heap Scanに対応。
- ExecScan()
- 関数ポインタを受け取って、個別処理はそっちに委譲する汎用処理。
- 実行計画のFilterに相当するところを実行。
- BitmapHeapNext()
- ExecScan()に渡される関数ポインタの実体。
- TIDBitmap型のデータから示されるブロックのタプルにアクセスし、TupleTableSlotに詰めて返す。
- 実行計画のRecheck Condに対応する処理はlossyのときにのみ行われる。
- MultiExecBitmapOr()
- 実行計画のBitmapOrに対応。
- 下位の結果をビットマップに束ねて（unionして）返す。要するに複数タプルの情報を返す。
- 今回のように下位のノードがBitmapIndexScanStateときはunionの処理は省かれている。重複が発生しないことがわかっているからだと思う。
- MultiExecBitmapIndexScan()
- 実行計画のBitmap Index Scanに対応。
- index_getmulti()を呼び出し、インデックスアクセスで一度に複数の結果を取得しようとしている。B-Treeの場合はbtgetmulti()が呼ばれることになる。
- _bt_next()などは他のインデックスアクセスからも呼ばれる処理。
- btgetmulti()
- 最初の実行かどうかで_bt_first()と_bt_next()を呼び出し分けている。
- 複数のTID（structとしてはItemPointer）を返す。このTIDはこの例だとaccountsテーブルのある特定のブロックとそのオフセット番号のこと。
まとめ
実行計画が実行される順番で見ていくとこうなる。
- 3つのBitmap Index Scanがあるが、この処理ごとにインデックスアクセスし複数のTIDを取得する（今回のようにインデックスがユニークの場合は1度のBitmap Index Scanで1件しかヒットしないが）。
- BitmapOrでTIDをまとめる。この時点でアクセスしているのTIDだけ。まだタプルの実体にアクセスしていない。
- Bitmap Heap Scanで実際にリレーション（テーブル）のブロックにアクセスしタプルを取り出す。
- lossyならRecheck Condのチェック。
- Filterの処理。
lossyはよくわかっていない。今は大きなデータのときに採用される方法というくらいの認識で。
