はじめに
PostgreSQL の実行計画において、Bitmap Index Scan の後に実行される Bitmap Heap Scan で "Recheck cond" と出力されます。Index Scan をしているにも関わらず、なぜ Heap Scan でインデックスの検索条件を再チェックする必要があるのか解説します。
事前に以下の資料を一読頂くことをお勧めします。
Explain説明資料（第20回しくみ勉強会）.pdf
特に「Bitmap Scanについて」「work_mem と lossy storage」をご確認ください。
本エントリの内容を適用できるPostgreSQLのバージョン範囲を特定できていませんが、9.4系や10系で適用できることを確認しています。実際にはもっと幅広く適用できると思われます。
解説編
本件に関し、海外のQAサイトで丁寧な解説がありました。
postgresql - "Recheck Cond:" line in query plans with a bitmap index scan - Database Administrators Stack Exchange
解説編ではこの回答をベースにポイントをまとめます。
exact と lossy モード
Bitmap Index Scan の結果（検索条件に合致するインデックスが指し示す行の情報）をビットマップに格納する際、exact と lossy モードの2種類が用いられます。exact モードが優先されます。
exact モードは行の位置を示すTIDをビットマップに格納します。このため、ビットマップから該当行のデータへ直接アクセスすることができます。
lossy モードは該当行が格納されているページ番号をビットマップに格納します。このため、ビットマップから該当行が含まれているページへアクセスすることはできますが、そのページに含まれているどの行が条件に合致するかを改めて検証する必要があります。これが、Bitmap Heap Scan のRecheck処理 "Recheck Cond" ということです。
exact モードから lossy モードへの移行
ビットマップが work_mem に収まりきらなくなると、exact モードから lossy モードへ移行します。exact モードが行単位の情報を保持するのに対し、lossy モードはページ単位の情報を保持します。lossy モードは情報の粒度が荒い分、ビットマップによるメモリ領域の消費を抑えることができますが、Recheck処理が必要になるというトレードオフが発生します。
exact モードから lossy モードへの移行はページ単位で行われます。ビットマップのサイズが十分に小さくなれば、移行処理はストップします。つまり、ビットマップ内でexact モードと lossy モードの情報が共存することになります。
実行計画での確認方法
Bitmap Heap Scan がどのモードで実行されたかは EXPLAIN ANALYZE でわかります。
Bitmap Index Scan の結果を受けて Bitmap Heap Scan が行われますが、Bitmap Heap Scan の詳細に Heap Blocks （読み込んだブロック数）が表示されます。ブロックに exact モードでアクセスすれば exact、lossy モードでアクセスすれば lossy と区別して表示されます。
なお、ページとブロックの用語の使い分けは以下の通りです。
一応、ストレージ上のリレーションのデータ切片が「ブロック」で、メモリ上のデータ切片が「ページ」「バッファ」と呼び分けるが、8 KiB は同一のデータ構造を持っているのでブロックとページ(バッファ)は論理的に同一である。
PostgreSQL のテーブルとブロックのデータ構造
Heap Blocks の表示で exact と lossy が同時に表示されることがあります。これは exact モードと lossy モードの情報が共存していることを指し示しています。
lossy モードへの移行が行われなくても、実行計画には "Recheck Cond" が出力されます。これは lossy モードへの移行が実行時に動的に行われ、実行計画の段階でRecheck処理が行われるか否かを知ることができないためです。
挙動確認編
work_mem が不足すると exact モードから lossy モードへの移行が起こることを PostgreSQL 10.3 で検証しました。
CREATE TABLE recheck_test(key serial PRIMARY KEY, value integer); INSERT INTO recheck_test(value) SELECT generate_series(1, 1000000)%10; CREATE INDEX value_idx ON recheck_test(value); VACUUM ANALYZE; SET enable_indexonlyscan TO off; SET work_mem = 4096; -- 4096kB EXPLAIN ANALYZE SELECT count(*) FROM recheck_test WHERE value=1;
QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------
Aggregate (cost=7788.08..7788.09 rows=1 width=8) (actual time=28.944..28.944 rows=1 loops=1)
-> Bitmap Heap Scan on recheck_test (cost=1868.58..7538.99 rows=99633 width=0) (actual time=5.409..21.428 rows=100000 loops=1)
Recheck Cond: (value = 1)
Heap Blocks: exact=4425
-> Bitmap Index Scan on value_idx (cost=0.00..1843.67 rows=99633 width=0) (actual time=4.939..4.939 rows=100000 loops=1)
Index Cond: (value = 1)
Planning time: 0.149 ms
Execution time: 28.979 ms
(8 rows)work_mem が十分にあれば exact モードのみとなります。
"Recheck Cond"が出力されていますが、Recheck処理を行いません。
SET work_mem = 64; -- 64kB EXPLAIN ANALYZE SELECT count(*) FROM recheck_test WHERE value=1;
QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------
Aggregate (cost=7788.08..7788.09 rows=1 width=8) (actual time=96.134..96.134 rows=1 loops=1)
-> Bitmap Heap Scan on recheck_test (cost=1868.58..7538.99 rows=99633 width=0) (actual time=5.812..88.340 rows=100000 loops=1)
Recheck Cond: (value = 1)
Rows Removed by Index Recheck: 733871
Heap Blocks: exact=817 lossy=3608
-> Bitmap Index Scan on value_idx (cost=0.00..1843.67 rows=99633 width=0) (actual time=5.724..5.724 rows=100000 loops=1)
Index Cond: (value = 1)
Planning time: 0.077 ms
Execution time: 96.168 ms
(9 rows)work_mem が足りないため、ビットマップの一部が lossy モードとなりました。Recheck処理が行われ、その結果削除された行数が "Rows Removed by Index Recheck" として出力されています。
work_mem が十分にある場合と比較すると、Bitmap Heap Scan で読み込んだブロック数は同じですが、処理時間は延びています。これはRecheck処理によるものと思われます。
実装確認編
ビットマップの構造を PostgreSQL 10.3 のコードで確認しました。
https://www.postgresql.org/ftp/source/v10.3/
src/backend/nodes/tidbitmap.c
PostgreSQLはテーブルとインデックスをページの集まりとして格納しています。このページの集まりがファイルとして格納されます。
物理構造の詳細は「内部構造から学ぶPostgreSQL 設計・運用計画の鉄則」の「6.1 各種ファイルのレイアウトとアクセス」を参照ください。
Bitmap Index Scan ではデータの格納にビットマップを利用します。このビットマップは PagetableEntry 構造体内に bitmapword として定義されています。ソースコードのコメントにもある通り、PagetableEntry 構造体は BlockNumber （ページ番号）をキーとしたハッシュテーブルに格納されます。
typedef struct PagetableEntry { BlockNumber blockno; /* page number (hashtable key) */ char status; /* hash entry status */ bool ischunk; /* T = lossy storage, F = exact */ bool recheck; /* should the tuples be rechecked? */ bitmapword words[Max(WORDS_PER_PAGE, WORDS_PER_CHUNK)]; } PagetableEntry;
exact モードは行の位置を示すTIDをビットマップに格納します。TIDを BlockNumber と OffsetNumber に分け、同じ BlockNumber を持つ PagetableEntry 構造体の ビットマップ bitmapword に OffsetNumber の指し示すビット位置を書き込みます。
lossy モードは PagetableEntry 構造体に BlockNumber のみを格納しますが、exact モードと同じデータ構造を利用するため、以下の要領で格納します。
pageno = 該当行の存在するBlockNumber
bitno = pageno % PAGES_PER_CHUNK;
chunk_pageno = pageno - bitno;
chunk_pageno と同じ BlockNumber を持つ PagetableEntry 構造体の ビットマップ bitmapword に bitno の指し示すビット位置を書き込みます。
こうすることで同じハッシュテーブル内に exact モードと lossy モードのデータを混在させることが可能となっています。コメントから説明を引用します。
We actually store both exact pages and lossy chunks in the same hash table, using identical data structures. (This is because the memory management for hashtables doesn't easily/efficiently allow space to be transferred easily from one hashtable to another.)
簡略化した例を示します。以下の表記及び定義とします。
{BlockNumber, OffsetNumber}
PAGES_PER_CHUNK = 5
{0, 1}, {6, 0}を格納します。
| blockno | ischunk | words[0] | words[1] | words[2] | words[3] | words[4] |
|---|---|---|---|---|---|---|
| 0 | F | 0 | 1 | 0 | 0 | 0 |
| 6 | F | 1 | 0 | 0 | 0 | 0 |
{3, 4}を追加する際に lossy モードへ移行が発生したとします。
bitno = pageno % PAGES_PER_CHUNK = 3 % 5 = 3
chunk_pageno = pageno - bitno = 3 - 3 = 0
| blockno | ischunk | words[0] | words[1] | words[2] | words[3] | words[4] |
|---|---|---|---|---|---|---|
| 0 | T | 1 | 0 | 0 | 1 | 0 |
| 6 | F | 1 | 0 | 0 | 0 | 0 |
blockno=0のwords[0]が0→1に、words[1]が1→0になっています。これは lossy モードに移行することで、ビットマップの情報が行からページへと転換したためです。これは転換前に格納されていた{0, 1}のBlockNumberに対応しています。OffsetNumberの情報は失われました。
bitno = pageno % PAGES_PER_CHUNK = 0 % 5 = 0
chunk_pageno = pageno - bitno = 0 - 0 = 0
おわりに
Bitmap Heap Scan でRecheck処理が行われるか否かは実行するまで分かりません。このため、EXPLAIN ではなく EXPLAIN ANALYZE で確認する必要があります。
Recheck処理が行われると、その分パフォーマンスが落ちます。これを避けるためには適切な work_mem の値を設定します。
