Bitmap Index Scan の後の Bitmap Heap Scan でRecheck処理が行われることの解説

はじめに

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 各種ファイルのレイアウトとアクセス」を参照ください。

内部構造から学ぶPostgreSQL 設計・運用計画の鉄則 (Software Design plus)

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 の値を設定します。

SQLの GROUP BY 句には列名だけでなく式も記述することができる

はじめに

「達人に学ぶSQL徹底指南書」（以下、達人SQL）の「1-1 CASE式のススメ」には GROUP BY 句に CASE 式の含まれるSQLが登場します。

達人に学ぶ SQL徹底指南書 (CodeZine BOOKS)

一般的に GROUP BY 句には列名を指定すると説明されており、このSQLは乖離しているように思えます。なぜこれが実現できるのかを説明します。

解説には「プログラマのためのSQL 第4版」（以下、プログラマSQL）も参照します。

プログラマのためのSQL 第4版

検証環境・データ

PostgreSQL 10.3, Oracle Database 12cR2 で検証を行いました。
達人SQLを参考に検証用のテーブルおよびデータを作成します。

pref_name （県名）	population （人口）
徳島	100
香川	200
愛媛	150
高知	200
福岡	300
佐賀	100
長崎	200
東京	400
群馬	50

CREATE TABLE PopTbl
(pref_name CHAR(10) NOT NULL PRIMARY KEY,
 population INTEGER NOT NULL);

INSERT INTO PopTbl VALUES ('徳島', 100);
INSERT INTO PopTbl VALUES ('香川', 200);
INSERT INTO PopTbl VALUES ('愛媛', 150);
INSERT INTO PopTbl VALUES ('高知', 200);
INSERT INTO PopTbl VALUES ('福岡', 300);
INSERT INTO PopTbl VALUES ('佐賀', 100);
INSERT INTO PopTbl VALUES ('長崎', 200);
INSERT INTO PopTbl VALUES ('東京', 400);
INSERT INTO PopTbl VALUES ('群馬', 50);

解説

達人SQLに記載のSQLとその実行結果を提示します。

SELECT CASE pref_name
         WHEN '徳島' THEN '四国'
         WHEN '香川' THEN '四国'
         WHEN '愛媛' THEN '四国'
         WHEN '高知' THEN '四国'
         WHEN '福岡' THEN '九州'
         WHEN '佐賀' THEN '九州'
         WHEN '長崎' THEN '九州'
       ELSE 'その他' END AS district,
       SUM(population)
  FROM PopTbl
 GROUP BY CASE pref_name
         WHEN '徳島' THEN '四国'
         WHEN '香川' THEN '四国'
         WHEN '愛媛' THEN '四国'
         WHEN '高知' THEN '四国'
         WHEN '福岡' THEN '九州'
         WHEN '佐賀' THEN '九州'
         WHEN '長崎' THEN '九州'
       ELSE 'その他' END;

district	sum
四国	650
九州	600
その他	450

このSQLのように GROUP BY 句に CASE 式を含めてもエラーにならない理由を直感的に理解するには、PopTbl テーブルに CASE 式の結果が district 列として追加され、その district 列でグループ化したとイメージするとわかりやすいです。

PopTbl テーブルに district 列を追加したイメージを示します。

pref_name （県名）	population （人口）	district （地区）
徳島	100	四国
香川	200	四国
愛媛	150	四国
高知	200	四国
福岡	300	九州
佐賀	100	九州
長崎	200	九州
東京	400	その他
群馬	50	その他

達人SQL「1-1 CASE式のススメ」のまとめでは、CASE式が 1 + 1 や a / b と同じ式の仲間であるとしたうえで、以下の説明をしています。

式であるがゆえに、CASE 式は実行時には評価されて一つの値に定まりますし（だから集約関数の中に書ける）、式だから、SELECT 句にも GROUP BY 句にも WHERE 句にも ORDER BY 句にも書くことができます。ひらたく言って、CASE 式は列名や定数を書ける場所には常に書くことができます。

また、プログラマSQL「28.4 計算列によるグルーピング」には以下の記述があります。

SQL-99では計算列によるグループ化が可能になった。

つまり、CASE 式が式として扱われ、それを仮想的な計算列（列の値は式の結果）とみなし、計算列を集約キーとしてその値でグループ化したと考えることができます。また、CASE 式（の計算列）は集約キーであるため、SELECT 句に含めることができます。

GROUP BY 句に列名ではなく式を記述できることを以下の例で確認できます。

（例1）

SELECT MOD(population, 100), COUNT(*)
  FROM PopTbl
 GROUP BY MOD(population, 100);

mod	count
0	7
50	2

（例2）

SELECT COUNT(pref_name), SUM(population)
  FROM PopTbl
 GROUP BY 5-0;

count	sum
9	1700

例2のSQLには GROUP BY 句に列名すら表れていませんが、実行可能です。"5"という値でPopTblをグループ化、つまりPopTbl全体をグループとし、そのグループを集約関数で処理しています。

まとめ

多くの記事や本の説明では GROUP BY 句に列名を指定できるとしていますが、実際には式も記述することができます。

CASE式が式の仲間である、との説明は達人SQLのまとめに「細かい話」として記載されています。ですが、本来は章の冒頭にもってきてもよいぐらい重要なポイントといえます。

海外からの旅行者に電車の乗換案内を英語で質問されたときの乗り越え方

はじめに

新幹線や飛行機だけでなく、日常的に通勤や遊びに行くために使う路線でも海外からの旅行者を多く見かけるようになりました。今後もさらに増えていくことでしょう。

そんな状況を背景に、海外からの旅行者に電車の乗換案内を英語で質問されるかもしれません。私は過去数回遭遇しています。

ですが、残念なことに私は英語を中1で挫折しています。speaking & writing スキルは当時のままです。まともに答えられるはずがありません。それでも困っている方を何とか助けたい。では、どうやって案内したか、何ができるのか、ということをまとめます。

聞く・話す・読む・書く、をとにかくやってみる

質問されるときはいつも突然です。たいてい、"Excuse me."から始まります。

パニックになりますが、まずは聞くことに集中してください。英単語が全てわからなくても、駅名は日本語の読みなので聞き取れることが多いです。まずはわかるキーワードを拾ってください。

この後、案内のためのツールなどを紹介しますが、それらを駆使して調べた内容をなんとか伝えようとしてください。文法なんて無茶苦茶でいい、単語の使い方が多少間違っていてもいい、とにかく聞く・話す・読む・書くにチャレンジすること。これが最も大切なことです。

また、スマホで調べ物をする際は一声かけて、できれば何をしているのか実況しながら操作しましょう。旅行者にとって不安な中、無言で調べられても何をしているのかわからず、余計に不安が募ってしまうからです。これはどこかへ案内する時も同じで、無言で引っ張るのではなく、声をかけてから移動しましょう。

英語版乗換案内

乗換案内を検索して、その結果を見せるときは英語版であることが重要です。日本語版の画面だと日本語が分からない、英語版はないのかといわれます。

案内当時は日本語版であってもニュアンスでわかるだろうに、なぜこんなに拒否反応されるのだろうと不思議でした。ですが改めて考えてみると、例えば自分が迷っているさなかにアラビア語の乗換案内を見せられて落ち着いて見られるかというと、はなはだ怪しいです。それと同じ感覚なのかもしれません。

旅行者のスマホで調べてもらえれば一番ですが、動作や回線が重すぎて使えないようなケースであれば、自分のスマホで調べ、旅行者のカメラで画面を撮ってもらうという手もあります（"Please screenshot" で通じました。）。

インストールや設定不要ですぐに使えるサービスとして、以下の2つがありました。

ジョルダンの提供する Japan Transit Planner。
https://world.jorudan.co.jp/mln/en/

ヴァル研究所の提供する Ekispert for WEB。
https://roote.ekispert.net/en/

Japan Transit Planner

私が実際の案内で利用したのは Japan Transit Planner でした。

こちらの良いところはデフォルト表示でメイン言語が英語、サブ言語に日本語が表示されているところです。案内する方もされる方も同じ画面を見ながら容易に理解できます。

また、駅ナンバリング表示があることもメリットとなります。駅ナンバリングとは新宿駅に"JY17"とか、渋谷駅に"TY01"と書かれているマークです。路線であれば英字のみで"JY"（JR山手線）、"TY"（東急東横線）と表記されています。

実際の案内の際には何度もこのマークを説明しました。"green rectangle is yamanotesen"のような感じです。最初は何のこと？という顔をしていた旅行者も、駅の道案内看板を見せた際に理解してくださったようで、その後は一人で乗換通路を歩いていました。

このサイトの場合、路線間の直通運転(Direct)表記もあります。いつの間にか知らない路線に変わっていて焦る、ということがなくなりそうです。ただ、直通運転とはなにかを口頭で説明する必要があります（私の場合、ここで降りないで！同じ電車！と拙い英語で伝えました）。

惜しむべきはプラットフォーム表示が有料機能ということです。困ったその場で使えないというのはかなり辛いです。この機能があれば、反対方向の電車に乗り間違える、というミスもかなり減ると思うのですが…。

Ekispert for WEB

Japan Transit Planner よりシンプルです。その分、駅ナンバリングや直通運転などの説明を省いているのがデメリットとも言えます。

ただ、このサイトの大きな強みがホーム番号（〇番線）が表示されることです。

また、画面がシンプルな分、必要なスクロールが少なくて見やすいというのもあります。画面を撮影する場合に小さなメリットとなります。

翻訳サイト/アプリ

英語が苦手でも翻訳サイト/アプリが力になってくれます。私の場合、インストール済みだったGoogle翻訳アプリを利用しました。
（iOS版）
https://itunes.apple.com/jp/app/google-%E7%BF%BB%E8%A8%B3/id414706506
（Android版）
https://play.google.com/store/apps/details?id=com.google.android.apps.translate&hl=ja

日本語でテキスト入力をしながらリアルタイムで翻訳されるため、旅行者も画面をのぞき込みながら何度もうなずいていました。

Google翻訳アプリは音声（マイク）入力も可能なので、その方がよりスムーズかもしれません。

乗換案内メモ

メモに書くべきと思われる内容は以下の事項です。

【必須項目】

• 出発駅・到着駅・乗換駅
• 路線名（直通ならその旨も）
• 電車の方向（例：池袋行、新宿行 等）

【推奨項目】

• 駅ナンバリング
• ホーム番号
• 日本語表記（そのメモを見た他の日本人がすぐに理解できる）

特に電車の方向は重要です。これがないと、どの電車に乗るべきか判断することは難しいです。可能であれば、メモを渡す際にこれを参考に乗る電車を判断して、と伝えるとよいでしょう。

駅員へ案内する

運が良ければ英語のできる駅員がいるかもしれません。近くの駅に降りて探してみましょう。

自分で乗換案内する

私がまれに行う究極の手段です。最後までは無理でも、途中駅まで一緒に案内します。

なぜ自分で乗換案内するかというと、自分が迷った経験からです。例えば、道が分からず交番で相談すると、何ステップにもわたる複雑な道順を案内されます。結局覚えきれず、不安いっぱいでなんとなく歩いてみる…そんな経験は無いでしょうか。だから、道案内を頼まれたときもガイドすることがあります。それと同じように、乗換案内もガイドします。

さいごに

海外からの旅行者に乗換案内を頼まれた、という話をすると、自分には無理だという方がほとんどです。私だってそうです。本当は断りたい。誰か見かねた英語の得意な方が助け舟を出してくれないだろうか、毎回心の奥底で願っています（でも現れない）。

ただ、想像してみてください。もしあなたが海外で迷子＆一人ぼっちになり、周囲に助けを求めたのに断られたら。その思いが私の原動力です。

繰り返しとなりますが、一番大切なことは聞く・話す・読む・書くことです。コミュニケーションをとろうというその思いが導きます。