エグゼキュータ。ビットマップヒープスキャン（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はよくわかっていない。今は大きなデータのときに採用される方法というくらいの認識で。
