六月 7, 2024
摘要：在本教程中，您将了解 PostgreSQL 位图扫描的成本估算。
目录
PostgreSQL 位图扫描
虽然索引扫描在相关性高的情况下很有效，但当相关性下降到扫描模式偏随机性（缺少顺序性），并且页面获取次数增加的程度时，它就有些低效了。这里的一种解决方案是事先收集所有元组的 TID，按页面号对它们进行排序，然后使用它们来扫描表。这就是位图扫描的工作原理，它也是第二种基本的索引扫描方法。它可用于任何具有 BITMAP SCAN 属性的访问方法（access method）。
让我们开始设置一个小的测试用例：
CREATE TABLE foo (typ int, bar int, id1 int);
CREATE INDEX ON foo(typ);
CREATE INDEX ON foo(bar);
CREATE INDEX ON foo(id1);
INSERT INTO foo (typ, bar, id1)
SELECT
CAST(cos(2 * pi() * random()) * sqrt(-2 * ln(random())) * 100 AS integer),
n % 97, n % 101
FROM generate_series(1, 1000000) n;
VACUUM ANALYZE foo;
请考虑下面的计划：
EXPLAIN SELECT * FROM foo WHERE typ = 28;
QUERY PLAN
-------------------------------------------------------------------------------
Bitmap Heap Scan on foo (cost=110.39..3792.67 rows=3867 width=12)
Recheck Cond: (typ = 28)
-> Bitmap Index Scan on foo_typ_idx (cost=0.00..109.43 rows=3867 width=0)
Index Cond: (typ = 28)
(4 rows)
位图扫描操作由两种节点表示：“Bitmap Index Scan” 和 “Bitmap Heap Scan”。位图索引扫描会调用访问方法，该方法会生成所有元组 TID 的位图。
位图由多个块组成，每个块对应于表中的单个页面。由于每个元组的头部大小很大，一个页面上的元组数是有限制的（每个标准页最多 256 个元组）。由于每个页面对应于一个位图块，因此创建的块会足够大，以容纳最多数目的元组（每个标准页 32 个字节）。
位图堆扫描节点会逐个块地扫描位图块，访问相应的页面，并获取位图中标记的所有元组。因此，页面按升序获取，每个页面仅获取一次。
实际的扫描顺序不是连续的，因为页面可能不是在磁盘上一个接一个地找到的。操作系统的预读在这里是没有帮助的，因此位图堆扫描会异步读取 effective_io_concurrency 数目的页面，来实现自己的预读能力（它是唯一这样做的节点）。此功能很大程度上取决于您的系统是否支持posix_fadvise函数。如果系统支持，您可以根据硬件能力设置该参数（在表空间层面）。
位图精度
当查询从大量页面获取元组时，这些页面的位图可能会占用大量本地内存。允许的位图大小受 work_mem 参数的限制。如果位图达到允许的最大大小，则其某些块开始放大映射范围：每个放大块的位与页面而不是元组匹配，然后该块覆盖一系列页面，而不仅仅是一个页面。这样可以让位图大小易于管理，但会牺牲一些准确性。您可以使用EXPLAIN ANALYZE命令来检查位图精度：
EXPLAIN (analyze, costs off, timing off)
SELECT * FROM foo WHERE typ > 60;
QUERY PLAN
---------------------------------------------------------------------
Bitmap Heap Scan on foo (actual rows=273085 loops=1)
Recheck Cond: (typ > 60)
Heap Blocks: exact=3473
-> Bitmap Index Scan on foo_typ_idx (actual rows=273085 loops=1)
Index Cond: (typ > 60)
Planning time: 0.226 ms
Execution time: 42.928 ms
(7 rows)
在本例中，位图足够小，可以在不放大映射范围的情况下容纳所有元组数据。这就是我们所说的精确位图。如果我们降低 work_mem 参数值，一些位图块将被放大。这将使位图变成有损位图：
SET work_mem = '128kB';
EXPLAIN (analyze, costs off, timing off)
SELECT * FROM foo WHERE typ > 60;
QUERY PLAN
---------------------------------------------------------------------
Bitmap Heap Scan on foo (actual rows=273085 loops=1)
Recheck Cond: (typ > 60)
Rows Removed by Index Recheck: 545651
Heap Blocks: exact=862 lossy=2611
-> Bitmap Index Scan on foo_typ_idx (actual rows=273085 loops=1)
Index Cond: (typ > 60)
Planning time: 0.253 ms
Execution time: 76.703 ms
(8 rows)
使用放大的位图块获取表页时，规划器必须根据查询条件重新检查其元组。无论检查是否实际发生，在计划中都会有 “Recheck Cond” 行来表示此步骤。过滤掉的行数会显示在 “Rows Removed by Index Recheck” 行。
在大型数据集上，即使每个块都放大了位图，也可能仍会超过 work_mem 大小。如果是这种情况，则会直接忽略 work_mem 的限制，但是不会进行额外的放大或缓冲。
位图操作
一个查询在其筛选条件中可能会包含多个字段。每个字段可能都有单独的索引。位图扫描允许我们同时利用多个索引。每个索引都可获得一个为其构建的行版本位图，然后将这些位图放在一起进行 AND（交集）和 OR（并集）操作。例如：
EXPLAIN (costs off)
SELECT * FROM foo WHERE bar = 2 AND id1 = 4;
QUERY PLAN
----------------------------------------------
Bitmap Heap Scan on foo
Recheck Cond: ((id1 = 4) AND (bar = 2))
-> BitmapAnd
-> Bitmap Index Scan on foo_id1_idx
Index Cond: (id1 = 4)
-> Bitmap Index Scan on foo_bar_idx
Index Cond: (bar = 2)
(7 rows)
在此示例中，BitmapAnd 节点对两个位图进行了 AND（交集）操作。
当精确位图进行 AND 和 OR 操作时，它们会保持精确（除非生成的位图超出了 work_mem 限制）。原始位图中任何放大的块在生成的位图中会保持放大。
成本估算
请考虑下面的位图扫描示例：
EXPLAIN SELECT * FROM foo WHERE bar = 2;
QUERY PLAN
--------------------------------------------------------------------------------
Bitmap Heap Scan on foo (cost=115.47..5722.32 rows=10200 width=12)
Recheck Cond: (bar = 2)
-> Bitmap Index Scan on foo_bar_idx (cost=0.00..112.92 rows=10200 width=0)
Index Cond: (bar = 2)
(4 rows)
规划器在这里估算出的选择率大约为：
SELECT round(10200::numeric/reltuples::numeric, 4)
FROM pg_class WHERE relname = 'foo';
round
−−−−−−−−
0.0102
(1 row)
位图索引扫描的总成本的计算方式，与普通索引扫描的成本计算相同，但表扫描部分的成本计算不同：
SELECT round(
current_setting('random_page_cost')::real * pages +
current_setting('cpu_index_tuple_cost')::real * tuples +
current_setting('cpu_operator_cost')::real * tuples
)
FROM (
SELECT relpages * 0.0102 AS pages, reltuples * 0.0102 AS tuples
FROM pg_class WHERE relname = 'foo_bar_idx'
) c;
round
−−−−−−−
112
(1 row)
当位图进行 AND 和 OR 操作时，它们的索引扫描成本会相加，再加上逻辑操作的（微小）成本。
位图堆扫描在 I/O 部分的成本计算，与索引扫描在相关性理想的情况下的成本计算有很大不同。位图扫描按升序获取表页，无需重复扫描，但匹配的元组不再整齐地相邻放置，因此不会快速轻松地进行顺序扫描。因此，可能要获取的页面数会增加。
下面的公式说明了这一点：
估算的单个页面的获取成本，在 seq_page_cost 到 random_page_cost 之间，具体取决于要获取的页面总数的比例。
WITH t AS (
SELECT relpages,
least(
(2 * relpages * reltuples * 0.0102) /
(2 * relpages + reltuples * 0.0102), relpages
) AS pages_fetched,
round(reltuples * 0.0102) AS tuples_fetched,
current_setting('random_page_cost')::real AS rnd_cost,
current_setting('seq_page_cost')::real AS seq_cost
FROM pg_class WHERE relname = 'foo'
)
SELECT pages_fetched,
rnd_cost - (rnd_cost - seq_cost) *
sqrt(pages_fetched / relpages) AS cost_per_page,
tuples_fetched
FROM t;
pages_fetched | cost_per_page | tuples_fetched
-------------------+--------------------+----------------
5248.543689320389 | 1.0440121655071204 | 10200
(1 row)
和通常一样，每个扫描的元组都会有一个处理成本，要添加到总的 I/O 成本中。对于一个精确位图，获取的元组数等于表行数乘以选择率。而对于有损位图，还需要重新检查有损页面上的所有元组：
这就是为什么（在 PostgreSQL 11 及更高版本中）估计值考虑了有损页面可能的占比（根据总行数和 work_mem 限制计算得出）。
估计值还包括了查询条件重新检查的总成本（即使对于精确位图也是如此）。位图堆扫描启动成本的计算方式，与位图索引扫描总成本的计算略有不同：需要考虑位图操作成本。在此示例中，位图是精确的，估计值的计算方式如下：
WITH t AS (
SELECT 1.0440121655071204 AS cost_per_page,
5248.543689320389 AS pages_fetched,
10200 AS tuples_fetched
),
costs(startup_cost, run_cost) AS (
SELECT
( SELECT round(
112 /* child node cost */ +
0.1 * current_setting('cpu_operator_cost')::real *
reltuples * 0.0102
)
FROM pg_class WHERE relname = 'foo_bar_idx'
),
( SELECT round(
cost_per_page * pages_fetched +
current_setting('cpu_tuple_cost')::real * tuples_fetched +
current_setting('cpu_operator_cost')::real * tuples_fetched
)
FROM t
)
)
SELECT startup_cost, run_cost, startup_cost + run_cost AS total_cost
FROM costs;
startup_cost | run_cost | total_cost
--------------+----------+------------
115 | 5607 | 5722
(1 row)