# 索引扫描
LLMS 索引： [llms.txt](/zh18/llms.txt)
---
## 20.1. 常规索引扫描 {#internal-ru-section-20-1}
存在两种使用索引提供的行版本标识符的基本方式。第一种是*索引扫描*。大多数索引方法（但并非全部）都具有 INDEX SCAN 属性，并支持这种方式。（参见 [409](/zh18/19-index-access-methods/#internal-ru-page-410)）
索引扫描在查询计划中由 Index Scan 节点表示 [^internal-ru-415-1]:
```text {label="psql"}
=> EXPLAIN SELECT * FROM bookings
WHERE book_ref = '9AC0C6' AND total_amount = 48500.00;
QUERY PLAN
---------------------------------------------
Index Scan using bookings_pkey on bookings
(cost=0.43..8.45 rows=1 width=21)
Index Cond: (book_ref = '9AC0C6'::bpchar)
Filter: (total_amount = 48500.00)
(4 rows)
```
在索引扫描过程中，访问方法逐个返回行版本标识符[^internal-ru-415-2]。索引机制获取下一个标识符，访问其所指向的表页，获取行版本，并在该版本满足可见性规则时返回所需字段集。此过程持续进行，直到访问方法不再有符合查询条件的标识符为止。
Index Cond 中仅列出可通过索引检查的条件。需要在表上重新验证的额外条件则单独显示在 Filter 行中。
因此，对索引和表的访问并未分为两个独立的计划节点，而是在同一个 Index Scan 节点中执行。尽管存在专门的 Tid Scan 节点[^internal-ru-416-1]，它根据已知的标识符从表中读取行版本：
```text {label="psql"}
=> EXPLAIN SELECT * FROM bookings WHERE ctid = '(0,1)'::tid;
QUERY PLAN
---------------------------------------------------------
Tid Scan on bookings (cost=0.00..4.01 rows=1 width=21)
TID Cond: (ctid = '(0,1)'::tid)
(2 rows)
```
### 成本估算 {#internal-ru-subsection-star-268}
索引扫描的评估由索引访问评估和表页读取评估组成。
显然，评估中的索引部分完全取决于具体的访问方法。对于 B-树，主要开销在于读取索引页和处理这些页中的行。具体读取多少页和行，可以通过已知的数据总量和条件的选择性来确定。索引页访问具有随机性（逻辑上相邻的页在物理上可能以不可预测的方式分布）。评估还包含从根节点下降到叶节点的 CPU 资源消耗以及计算所需表达式的开销 [^internal-ru-416-2]。（参见 [335](/zh18/16-query-execution-stages/#internal-ru-page-336)）
表部分的评估考虑了访问页的成本和处理所有读取的行版本所需的 CPU 时间。重要的是，输入/输出评估不仅取决于索引访问的选择性，还取决于行版本在磁盘上的物理位置与访问方法输出其标识符的顺序之间的*相关性*。
### 良好场景：高相关性 {#internal-ru-subsection-star-270}
如果磁盘上行版本的物理顺序与索引中标识符的逻辑顺序完全相关，那么在逐个读取行版本时，Index Scan 节点将*顺序*地从一页跳到另一页，并且每一页仅被访问*一次*。
{#internal-ru-fig-20-1 num="20.1" caption="理想情况：高相关性" .book-original-figure width=658 height=267}
相关性信息作为统计信息的一部分收集：（参见 [361](/zh18/17-statistics/#internal-ru-page-362)）
```text {label="psql"}
=> SELECT attname, correlation
FROM pg_stats WHERE tablename = 'bookings'
ORDER BY abs(correlation) DESC;
attname | correlation
--------------+--------------
book_ref | 1
total_amount | 0.0026738467
book_date | 8.02188e-05
(3 rows)
```
接近于 1 的值（如 `book_ref` 列）表示高度有序，而接近于 0 的值则表示分布混乱。
> [!NOTE]
> 本例中 `book_ref` 列的高相关性显然源于数据按该列值升序加载到表中且未被修改。对这个列的索引执行 `CLUSTER` 命令也会产生类似效果。
> 但即使存在完全相关性，也不能保证任何查询都会按 `book_ref` 升序返回数据。首先，任何行的修改都会导致该行当前版本被移动到末尾
> [!NOTE]
> 表中。其次，使用其他列的索引访问方法生成的计划将按不同顺序输出数据。甚至顺序扫描也可能不从表的开头开始。因此，如果需要特定顺序，必须在 `ORDER BY` 子句中明确指定。
以下是大量行的索引扫描示例：（参见 [198](/zh18/09-buffer-cache/#internal-ru-page-199)）
```text {label="psql" hl_lines="5"}
=> EXPLAIN SELECT * FROM bookings WHERE book_ref < '100000';
QUERY PLAN
---------------------------------------------
Index Scan using bookings_pkey on bookings
(cost=0.43..4640.91 rows=132999 width=21)
Index Cond: (book_ref < '100000'::bpchar)
(3 rows)
```
根据规划器的评估，条件的选择性为：
```text {label="psql"}
=> SELECT round(132999::numeric/reltuples::numeric, 4)
FROM pg_class WHERE relname = 'bookings';
round
--------
0.0630
(1 row)
```
这接近于基于一般推理得出的 \(\frac{1}{16}\) 估计值，已知 `book_ref` 的值范围为 `000000` 到 `FFFFFF`。（参见 [357](/zh18/17-statistics/#internal-ru-page-358)）
B-树的索引部分输入/输出评估考虑了读取所需页数的成本。B-树支持的任何条件对应的索引行都是有序的，并位于逻辑上相连的叶页中，因此读取的索引页数量评估为索引大小乘以选择性。但这些页在物理上并不有序，因此读取是*随机*的。
CPU 资源用于处理所有读取的索引行（每行处理成本评估为 *cpu\_index\_tuple\_cost* 参数值）以及为每行计算条件（本例中条件包含一个操作符；其计算成本评估为 *cpu\_operator\_cost* 参数值）。（默认值：`0.005`）（默认值：`0.0025`）
表输入/输出被视为*顺序*读取所需页数。在理想相关性下，表行版本在物理上彼此相邻，因此页数评估为表大小乘以选择性。
输入/输出成本还包含处理所有读取的行版本的成本；每行版本的处理成本评估为 *cpu\_tuple\_cost* 参数值。（默认值：`0.01`）
```text {label="psql"}
=> WITH costs(idx_cost, tbl_cost) AS (
SELECT
(
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.0630 AS pages, reltuples * 0.0630 AS tuples
FROM pg_class WHERE relname = 'bookings_pkey'
) c
),
(
SELECT round(
current_setting('seq_page_cost')::real * pages +
current_setting('cpu_tuple_cost')::real * tuples
)
FROM (
SELECT relpages * 0.0630 AS pages, reltuples * 0.0630 AS tuples
FROM pg_class WHERE relname = 'bookings'
) c
)
)
SELECT idx_cost, tbl_cost, idx_cost + tbl_cost AS total
FROM costs;
idx_cost | tbl_cost | total
----------+----------+-------
2457 | 2180 | 4637
(1 row)
```
该公式展示了成本计算的逻辑，结果与规划器的评估相符，但并非精确值。获得精确值需要考虑我们不深入讨论的细节。
### 不良场景：低相关性 {#internal-ru-subsection-star-272}
当相关性较低时，表访问情况发生变化。创建一个与索引几乎无相关性的 `book_date` 列的索引，并查看选择大致相同比例行的查询。索引访问变得如此昂贵，以至于规划器仅在禁止所有其他替代方案时才会选择它：
```text {label="psql" hl_lines="9"}
=> CREATE INDEX ON bookings(book_date);
=> SET enable_seqscan = off;
=> SET enable_bitmapscan = off;
=> EXPLAIN SELECT * FROM bookings
WHERE book_date < '2016-08-23 12:00:00+03';
QUERY PLAN
---------------------------------------------------------------------
Index Scan using bookings_book_date_idx on bookings
(cost=0.43..57121.48 rows=132403 width=21)
Index Cond: (book_date < '2016-08-23 12:00:00+03'::timestamp w...
(3 rows)
```
原因在于，相关性越低，访问方法返回的下一个行版本标识符指向的页与当前页越可能不同。因此，Index Scan 节点不再顺序读取，而是“跳跃”式地从一页跳到另一页，而在最坏情况下，访问页数可能达到所选行版本数。
{#internal-ru-fig-20-2 num="20.2" caption="糟糕情况：低相关性" .book-original-figure width=658 height=178}
但简单地将上述公式中的 *seq\_page\_cost* 替换为 *random\_page\_cost*，并将 `relpages` 替换为 `reltuples` 是不正确的。我们从计划中看到的成本比这样估算出的成本低一个数量级：
```text {label="psql" hl_lines="16"}
=> WITH costs(idx_cost, tbl_cost) AS (
SELECT
(
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.0630 AS pages, reltuples * 0.0630 AS tuples
FROM pg_class WHERE relname = 'bookings_pkey'
) c
),
(
SELECT round(
current_setting('random_page_cost')::real * tuples +
current_setting('cpu_tuple_cost')::real * tuples
)
FROM (
SELECT relpages * 0.0630 AS pages, reltuples * 0.0630 AS tuples
FROM pg_class WHERE relname = 'bookings'
) c
)
)
SELECT idx_cost, tbl_cost, idx_cost + tbl_cost AS total
FROM costs;
idx_cost | tbl_cost | total
----------+----------+--------
2457 | 533330 | 535787
(1 row)
```
原因在于模型额外考虑了缓存效应。频繁访问的页会保留在缓冲区缓存（以及操作系统缓存）中，因此缓存越大，找到所需页的可能性越高，从而避免磁盘操作。为规划目的，缓存大小由 *effective\_cache\_size* 参数值决定。该值越小，评估中需要读取的页数越高。（默认值：`4GB`）
图表显示了在选择性为 \(\frac12\) 且每页容纳十行的情况下，读取页数的评估值随表大小变化的关系 [^internal-ru-421-1]。
{#internal-ru-fig-20-3 num="20.3" caption="糟糕情况：低相关性" .book-original-figure width=710 height=539}
图表中的虚线表示访问次数等于页数的一半（理想相关性下的最佳理论情况）和行数的一半（零相关性且无缓存时的最坏情况）。
假设 *effective\_cache\_size* 参数值应对应于可用于缓存的总内存（包括 PostgreSQL 缓冲区缓存和操作系统缓存）。但由于该参数仅用于评估，不导致实际内存分配，因此可根据需要调整，无需考虑真实数值。
将参数设为最小值后，计划评估结果接近于未考虑缓存效应时计算出的最坏情况评估值：
```text {label="psql" hl_lines="7"}
=> SET effective_cache_size = '8kB';
=> EXPLAIN SELECT * FROM bookings
WHERE book_date < '2016-08-23 12:00:00+03';
QUERY PLAN
---------------------------------------------------------------------
Index Scan using bookings_book_date_idx on bookings
(cost=0.43..532745.48 rows=132403 width=21)
Index Cond: (book_date < '2016-08-23 12:00:00+03'::timestamp w...
(3 rows)
```
```text {label="psql"}
=> RESET effective_cache_size;
=> RESET enable_seqscan;
=> RESET enable_bitmapscan;
```
表输入/输出成本针对上述两种情况——良好和糟糕——进行计算，然后根据实际相关性取中间值[^internal-ru-423-1]。
因此，当需要读取表中部分行时，索引扫描是高效的。如果表中行版本的排列与访问方法输出标识符的顺序相关，则这部分开销可能非常显著。但如果相关性较弱，随着选择性降低，索引访问的吸引力会迅速下降。
## 20.2. 仅索引扫描 {#internal-ru-section-20-2}
包含执行查询所需的所有表数据的索引称为该查询的*覆盖索引*（covering）。如果存在覆盖索引，可以避免对表的额外访问，直接从访问方法获取数据而非行版本标识符。这种索引扫描的变体称为*仅索引扫描*[^internal-ru-423-2]。它可被支持 RETURNABLE 属性的方法使用。（参见 [411](/zh18/19-index-access-methods/#internal-ru-page-412)）
该操作在查询计划中由 Index Only Scan 节点表示 [^internal-ru-424-1]:
```text {label="psql" hl_lines="1 5"}
=> EXPLAIN SELECT book_ref FROM bookings WHERE book_ref < '100000';
QUERY PLAN
-------------------------------------------------
Index Only Scan using bookings_pkey on bookings
(cost=0.43..4640.91 rows=132999 width=7)
Index Cond: (book_ref < '100000'::bpchar)
(3 rows)
```
名称可能让人误以为 Index Only Scan 节点从不访问表，但事实并非如此。PostgreSQL 中的索引不包含判断行可见性的信息，因此访问方法会返回所有符合条件的版本数据，无论其对当前事务是否可见。可见性随后由索引机制检查。（参见 [89](/zh18/03-pages-and-tuples/#internal-ru-page-90)）
但如果每次都要查看表来确定可见性，这种扫描方法与普通索引扫描并无区别。问题通过 PostgreSQL 支持的表*可见性映射*解决，其中清理过程标记那些仅包含对所有事务可见的行版本的页，无论其快照如何。如果索引方法返回的行版本标识符属于此类页，则无需检查其可见性。（参见 [32](/zh18/01-introduction/#internal-ru-page-33)）
仅索引扫描的评估受可见性映射中标记的表页比例影响。该信息包含在收集的统计信息中：
```text {label="psql"}
=> SELECT relpages, relallvisible
FROM pg_class WHERE relname = 'bookings';
relpages | relallvisible
----------+---------------
13488 | 13446
(1 row)
```
仅索引扫描的评估与普通索引扫描不同，其与表访问相关的输入/输出成本按未包含在可见性映射中的页的比例计算。（行版本处理的 CPU 成本保持不变。）
由于本例中所有页上的所有行版本对所有事务都可见，因此成本评估中实际上完全排除了表输入/输出成本：
```text {label="psql"}
=> WITH costs(idx_cost, tbl_cost) AS (
SELECT
(
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.0630 AS pages,
reltuples * 0.0630 AS tuples
FROM pg_class WHERE relname = 'bookings_pkey'
) c
) AS idx_cost,
(
SELECT round(
(1 - frac_visible) * -- доля страниц вне карты видимости
current_setting('seq_page_cost')::real * pages +
current_setting('cpu_tuple_cost')::real * tuples
)
FROM (
SELECT relpages * 0.0630 AS pages,
reltuples * 0.0630 AS tuples,
relallvisible::real/relpages::real AS frac_visible
FROM pg_class WHERE relname = 'bookings'
) c
) AS tbl_cost
)
SELECT idx_cost, tbl_cost, idx_cost + tbl_cost AS total
FROM costs;
idx_cost | tbl_cost | total
----------+----------+-------
2457 | 1333 | 3790
(1 row)
```
存在尚未越过数据库视界且未被清理处理的更改，会增加计划成本（从而降低优化器对计划的偏好）。要了解实际的强制表访问次数，可以使用 `EXPLAIN ANALYZE` 命令。（参见 [106](/zh18/04-snapshots/#internal-ru-page-107)）
在新创建的表中，重新检查所有行版本的可见性：
```text {label="psql" hl_lines="10 12"}
=> CREATE TEMP TABLE bookings_tmp WITH (autovacuum_enabled = off)
AS SELECT * FROM bookings ORDER BY book_ref;
=> ALTER TABLE bookings_tmp ADD PRIMARY KEY(book_ref);
=> ANALYZE bookings_tmp;
=> EXPLAIN (analyze, timing off, summary off, buffers off)
SELECT book_ref FROM bookings_tmp WHERE book_ref < '100000';
QUERY PLAN
---------------------------------------------------------------------
Index Only Scan using bookings_tmp_pkey on bookings_tmp
(cost=0.43..4641.91 rows=132999 width=7) (actual rows=132109.0...
Index Cond: (book_ref < '100000'::bpchar)
Heap Fetches: 132109
Index Searches: 1
(5 rows)
```
清理创建了可见性映射，因此无需再检查：
```text {label="psql" hl_lines="7 9"}
=> VACUUM bookings_tmp;
=> EXPLAIN (analyze, timing off, summary off, buffers off)
SELECT book_ref FROM bookings_tmp WHERE book_ref < '100000';
QUERY PLAN
---------------------------------------------------------------------
Index Only Scan using bookings_tmp_pkey on bookings_tmp
(cost=0.43..3794.91 rows=132999 width=7) (actual rows=132109.0...
Index Cond: (book_ref < '100000'::bpchar)
Heap Fetches: 0
Index Searches: 1
(5 rows)
```
### 包含 INCLUDE 子句的索引 {#internal-ru-subsection-star-274}
存在一种情况，即无法扩展索引以包含查询所需的所有列：
- 对于唯一索引，添加列不会保证原始列的唯一性；
- 新增列的数据类型可能不支持索引访问方法的运算符类。
在这种情况下，可以将列添加到索引中，但不将其作为索引键的一部分。当然，无法通过这些附加列进行搜索，但对于包含这些列的查询，索引仍可作为覆盖索引使用。
示例展示了如何将用于支持主键的自动创建索引替换为包含额外列的另一个索引：
```text {label="psql"}
=> CREATE UNIQUE INDEX ON bookings(book_ref) INCLUDE (book_date);
=> BEGIN;
=> ALTER TABLE bookings DROP CONSTRAINT bookings_pkey CASCADE;
NOTICE: drop cascades to constraint tickets_book_ref_fkey on table
tickets
ALTER TABLE
=> ALTER TABLE bookings ADD CONSTRAINT bookings_pkey PRIMARY KEY
USING INDEX bookings_book_ref_book_date_idx; -- новый индекс
NOTICE: ALTER TABLE / ADD CONSTRAINT USING INDEX will rename index
"bookings_book_ref_book_date_idx" to "bookings_pkey"
ALTER TABLE
=> ALTER TABLE tickets
ADD FOREIGN KEY (book_ref) REFERENCES bookings(book_ref);
=> COMMIT;
=> EXPLAIN SELECT book_ref, book_date
FROM bookings WHERE book_ref < '100000';
QUERY PLAN
---------------------------------------------------------------------
Index Only Scan using bookings_pkey on bookings (cost=0.43..438...
Index Cond: (book_ref < '100000'::bpchar)
(2 rows)
```
> [!NOTE]
> 人们常常将此类 INCLUDE 索引称为“覆盖索引”，这是错误的。索引是否为覆盖索引，取决于其列集是否覆盖了特定查询所需的所有列。无论这些列是作为键列还是通过 `INCLUDE` 子句添加的，都不影响判断。此外，同一个索引对一个查询可能是覆盖的，而对另一个查询则不是。
## 20.3. 位图扫描 {#internal-ru-section-20-3}
在索引扫描中，相关性降低会增加对页面的访问次数，并将读取方式从顺序读取变为随机读取。这一限制可以通过在访问表之前获取所有行版本标识符并按页面号升序排列来克服[^internal-ru-428-1]。这就是第二种基本标识符处理方式——“位图扫描”的工作原理。支持 BITMAP SCAN 特性的访问方法可以使用该方式。（参见 [409](/zh18/19-index-access-methods/#internal-ru-page-410)）
与普通索引扫描不同，该操作在查询计划中表现为两个节点：
```text {label="psql"}
=> CREATE INDEX ON bookings(total_amount);
=> EXPLAIN
SELECT * FROM bookings WHERE total_amount = 48500.00;
QUERY PLAN
---------------------------------------------------------------------
Bitmap Heap Scan on bookings (cost=54.63..7045.60 rows=2865 wid...
Recheck Cond: (total_amount = 48500.00)
-> Bitmap Index Scan on bookings_total_amount_idx
(cost=0.00..53.92 rows=2865 width=0)
Index Cond: (total_amount = 48500.00)
(5 rows)
```
节点 Bitmap Index Scan [^internal-ru-428-2] 向访问方法请求所有行版本标识符的“位图”。 [^internal-ru-428-3]
位图由若干片段组成，每个片段对应一个表页。所有片段大小相同，足以覆盖页中所有行版本，无论其数量多少。由于头部开销较大，页中最多容纳 256 个行版本，仅需 32 字节即可表示[^internal-ru-428-4]。
节点 Bitmap Heap Scan [^internal-ru-429-1] 随后逐个片段扫描位图，读取对应片段的表页，并在该页上检查位图中标记的所有行版本。因此，页面按编号升序读取，且每页仅读取一次。
由于在构建位图阶段已知所需页面列表，扫描操作可利用异步 I/O。并非所有操作都是多块读取，因为所需页面并不总是一一相邻，但无论如何，异步预读显著提升了该访问方法的效率。（参见 [183](/zh18/09-buffer-cache/#internal-ru-page-184)）
### 位图准确性 {#internal-ru-subsection-star-276}
被行版本覆盖的页面越多，位图所占空间越大。位图在服务进程的本地内存中构建，受参数 *work\_mem* 限制。若构建过程中内存使用达到上限，部分位图片段将被“粗化”，使得每个片段比特对应整页，且片段覆盖范围从单页扩展为一个区间[^internal-ru-429-2]。这可减小位图大小，但牺牲了精度。（默认值：`4MB`）
命令 `EXPLAIN ANALYZE` 可显示所构建位图的精度。本例中内存足够构建精确（exact）位图：
```text {label="psql" hl_lines="7"}
=> EXPLAIN (analyze, costs off, timing off, summary off, buffers off)
SELECT * FROM bookings WHERE total_amount > 150000.00;
QUERY PLAN
---------------------------------------------------------------------
Bitmap Heap Scan on bookings (actual rows=242691.00 loops=1)
Recheck Cond: (total_amount > 150000.00)
Heap Blocks: exact=13447
-> Bitmap Index Scan on bookings_total_amount_idx (actual rows...
Index Cond: (total_amount > 150000.00)
Index Searches: 1
(6 rows)
```
若减小 *work\_mem* 值，部分位图片段将存储为低精度（lossy）：
```text {label="psql" hl_lines="9"}
=> SET work_mem = '512kB';
=> EXPLAIN (analyze, costs off, timing off, summary off, buffers off)
SELECT * FROM bookings WHERE total_amount > 150000.00;
QUERY PLAN
---------------------------------------------------------------------
Bitmap Heap Scan on bookings (actual rows=242691.00 loops=1)
Recheck Cond: (total_amount > 150000.00)
Rows Removed by Index Recheck: 1145721
Heap Blocks: exact=5178 lossy=8269
-> Bitmap Index Scan on bookings_total_amount_idx (actual rows...
Index Cond: (total_amount > 150000.00)
Index Searches: 1
(7 rows)
=> RESET work_mem;
```
当读取对应粗化片段的表页时，必须对页中每个行版本重新检查筛选条件。无论实际是否执行，计划中始终显示 Recheck Cond —— 重新检查条件。通过重新检查过滤掉的行版本数量单独显示（Rows Removed by Index Recheck）。
> [!NOTE]
> 当选择集非常大时，即使位图完全由粗化片段组成，也可能无法放入 *work\_mem* 所限内存中。此时不再受该限制约束，位图将占用所需全部空间。不会额外降低精度或将部分片段写入磁盘。
### 位图操作 {#internal-ru-subsection-star-278}
若查询条件作用于表的多个字段，且为这些字段创建了不同索引，则位图扫描可同时使用多个索引[^internal-ru-430-1]。为每个索引构建行版本位图，随后根据条件逻辑合并：若表达式由 `AND` 连接，则进行按位逻辑与；若由 `OR` 连接，则进行按位逻辑或。
例如：
```text {label="psql"}
=> EXPLAIN (costs off)
SELECT *
FROM bookings
WHERE book_date < '2016-08-28'
AND total_amount > 250000;
QUERY PLAN
---------------------------------------------------------------------
Bitmap Heap Scan on bookings
Recheck Cond: ((total_amount > '250000'::numeric) AND (book_da...
-> BitmapAnd
-> Bitmap Index Scan on bookings_total_amount_idx
Index Cond: (total_amount > '250000'::numeric)
-> Bitmap Index Scan on bookings_book_date_idx
Index Cond: (book_date < '2016-08-28 00:00:00+03'::tim...
(7 rows)
```
此处节点 BitmapAnd 通过按位“与”操作合并两个位图。
在合并两个位图为一个时[^internal-ru-431-1]，若新位图在内存中 *work\_mem* 足够，则精确片段保持精确；但只要任一片段为粗化，则结果片段也将为低精度。
### 成本估算 {#internal-ru-subsection-star-280}
以一个使用位图扫描的查询为例：
```text {label="psql" hl_lines="5 8"}
=> EXPLAIN
SELECT * FROM bookings WHERE total_amount = 28000.00;
QUERY PLAN
---------------------------------------------------------------------
Bitmap Heap Scan on bookings (cost=599.48..14485.96 rows=31878 ...
Recheck Cond: (total_amount = 28000.00)
-> Bitmap Index Scan on bookings_total_amount_idx
(cost=0.00..591.51 rows=31878 width=0)
Index Cond: (total_amount = 28000.00)
(5 rows)
```
此处规划器估算的条件选择性约为
```text {label="psql"}
=> SELECT round(31878::numeric/reltuples::numeric, 4)
FROM pg_class WHERE relname = 'bookings';
round
--------
0.0151
(1 row)
```
节点 Bitmap Index Scan 的总成本估算方式与普通索引访问相同，不考虑对表的访问：
```text {label="psql"}
=> 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.0151 AS pages, reltuples * 0.0151 AS tuples
FROM pg_class WHERE relname = 'bookings_total_amount_idx'
) c;
round
-------
589
(1 row)
```
节点 Bitmap Heap Scan 的 I/O 成本估算与理想相关性下的普通索引扫描不同。位图允许按页面号升序读取表页且无重复访问，但满足条件的行版本不再彼此相邻。因此，可能需要读取远多于严格顺序紧凑范围的页面。
{#internal-ru-fig-20-4 num="20.4" caption="成本估算" .book-original-figure width=658 height=158}
读取页面数量估算公式为 [^internal-ru-433-1]
$$
\min\left(\frac{2\,\mathtt{relpages}\cdot\mathtt{reltuples}\cdot sel}{2\,\mathtt{relpages}+\mathtt{reltuples}\cdot sel},\mathtt{relpages}\right),
$$
单页读取成本介于 *seq\_page\_cost* 与 *random\_page\_cost* 之间，具体取决于读取页面数与表中总页面数的比例：
```text {label="psql"}
=> WITH t AS (
SELECT relpages,
least(
(2 * relpages * reltuples * 0.0151) /
(2 * relpages + reltuples * 0.0151),
relpages
) AS pages_fetched,
round(reltuples * 0.0151) 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 = 'bookings'
)
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
---------------+---------------+----------------
13488 | 1 | 31878
(1 row)
```
通常，I/O 成本估算会加上节点处理每个读取行版本的开销。在精确位图情况下，行数估算为表中总行数乘以条件选择性。但当部分位图片段为非精确时，必须检查对应页中所有行版本。因此估算中需考虑位图中非精确片段的预期比例（可通过已知选择集总行数和 *work\_mem* 限制计算得出）[^internal-ru-433-2]。
估算中还包含条件重新检查的完整成本（与位图精度无关）。
{#internal-ru-fig-20-5 num="20.5" caption="成本估算" .book-original-figure width=664 height=192}
在本例中，位图完全精确，估算大致如下 [^internal-ru-434-1]：
```text {label="psql"}
=> WITH t AS (
SELECT 1 AS cost_per_page,
13488 AS pages_fetched,
31878 AS tuples_fetched
),
costs(startup_cost, run_cost) AS (
SELECT
(
SELECT round(
589 /* оценка нижележащего узла */ +
0.1 * current_setting('cpu_operator_cost')::real *
reltuples * 0.0151
)
FROM pg_class
WHERE relname = 'bookings_total_amount_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
--------------+----------+------------
597 | 13886 | 14483
(1 row)
```
此处节点 Bitmap Heap Scan 的初始成本估算基于节点 Bitmap Index Scan 的总成本估算，并加上位图处理成本：
```text
QUERY PLAN
-----------------------------------------------------
Bitmap Heap Scan on bookings
(cost=599.48..14485.96 rows=31878 width=21)
Recheck Cond: (total_amount = 28000.00)
-> Bitmap Index Scan on bookings_total_amount_idx
(cost=0.00..591.51 rows=31878 width=0)
Index Cond: (total_amount = 28000.00)
(6 rows)
```
若查询计划合并多个位图，各索引访问成本之和将增加（少量）合并本身的成本[^internal-ru-435-1]。
## 20.4. 并行索引扫描 {#internal-ru-section-20-4}
所有索引扫描方式——普通扫描、仅索引扫描、位图扫描——均有并行计划版本。（参见 [379](/zh18/18-table-access-methods/#internal-ru-page-380)）
并行执行成本估算方式与串行类似，但（如同并行顺序扫描）CPU 资源在所有并行进程间分配，从而降低总成本。I/O 成本不分配，因为页面读取在进程间同步且为顺序进行。
接下来我仅展示并行计划示例，不再分析成本估算。
并行索引扫描 Parallel Index Scan：
```text {label="psql" hl_lines="9"}
=> EXPLAIN SELECT sum(total_amount)
FROM bookings WHERE book_ref < '400000';
QUERY PLAN
---------------------------------------------------------------------
Finalize Aggregate (cost=19202.81..19202.82 rows=1 width=32)
-> Gather (cost=19202.59..19202.80 rows=2 width=32)
Workers Planned: 2
-> Partial Aggregate (cost=18202.59..18202.60 rows=1 widt...
-> Parallel Index Scan using bookings_pkey on bookings
(cost=0.43..17652.82 rows=219907 width=6)
Index Cond: (book_ref < '400000'::bpchar)
(7 rows)
```
在 B-树的并行扫描中，服务器的共享内存中存储当前索引页号。由启动扫描的进程初始化该值：它从树根下降至叶页并记录该页。工作进程按需请求下一页，更新保存的页号。获取页后，进程处理其中所有匹配行，并从表中读取对应行版本。当读取完所有满足查询条件的值范围时，扫描结束。（参见 [524](/zh18/25-b-tree/#internal-ru-page-525)）
并行仅索引扫描 Parallel Index Only Scan：
```text {label="psql" hl_lines="9"}
=> EXPLAIN SELECT sum(total_amount)
FROM bookings WHERE total_amount < 50000.00;
QUERY PLAN
---------------------------------------------------------------------
Finalize Aggregate (cost=23538.60..23538.61 rows=1 width=32)
-> Gather (cost=23538.38..23538.59 rows=2 width=32)
Workers Planned: 2
-> Partial Aggregate (cost=22538.38..22538.39 rows=1 widt...
-> Parallel Index Only Scan using bookings_total_amoun...
(cost=0.43..21555.27 rows=393244 width=6)
Index Cond: (total_amount < 50000.00)
(7 rows)
```
并行仅索引扫描仅在可见性映射允许时，不访问表页。
最后是并行位图扫描：
```text {label="psql" hl_lines="9 12"}
=> EXPLAIN SELECT sum(total_amount)
FROM bookings WHERE book_date < '2016-10-01';
QUERY PLAN
---------------------------------------------------------------------
Finalize Aggregate (cost=21533.21..21533.22 rows=1 width=32)
-> Gather (cost=21532.99..21533.20 rows=2 width=32)
Workers Planned: 2
-> Partial Aggregate (cost=20532.99..20533.00 rows=1 widt...
-> Parallel Bitmap Heap Scan on bookings
(cost=4891.17..20174.01 rows=143588 width=6)
Recheck Cond: (book_date < '2016-10-01 00:00:00+03...
-> Bitmap Index Scan on bookings_book_date_idx
(cost=0.00..4805.01 rows=344611 width=0)
Index Cond: (book_date < '2016-10-01 00:00:00+...
(10 rows)
```
在位图扫描中，位图构建始终由一个主进程顺序完成，因此节点 Bitmap Index Scan 不添加 "Parallel" 一词。位图构建完成后，表扫描在节点 Parallel Bitmap Heap Scan 中并行执行。工作进程按需请求下一页并处理。
## 20.5. 各种访问方法的比较 {#internal-ru-section-20-5}
下一页展示了不同访问方法成本随条件选择性变化的曲线图。该图具有定性特征；具体数值显然取决于表结构和服务器参数。
顺序扫描与选择性无关，当选择行比例达到一定阈值后，通常优于其他方法。
索引扫描成本高度依赖于行版本物理位置与索引访问方法输出标识符顺序之间的相关性。在理想相关性下，即使选择比例较高，索引扫描仍能高效运行。
{#internal-ru-fig-20-6 num="20.6" caption="访问方法比较" .book-original-figure width=710 height=436}
所选行数。但在弱相关性（这在现实中更常见）的情况下，成本很高，并且很快就会超过顺序扫描的成本。尽管如此，在索引（通常是唯一索引）用于检索单行的非常重要的情况下，索引扫描无疑是最佳选择。
如果适用，仅索引扫描可以带来极佳的效果，甚至在选择所有行时也能优于顺序扫描。然而，其性能高度依赖于可见性映射，在最坏情况下，仅索引扫描会退化为普通索引扫描。
位图扫描的成本取决于可用内存的大小，但其受相关性影响的程度远低于索引扫描。在弱相关性情况下，位图扫描具有显著优势。
每种访问方法在某些情况下可能优于其他方法，而在其他情况下则可能表现较差。查询规划器会针对每种具体情况，对所有方法的效率进行深入评估。当然，这些评估结果与实际情况的接近程度，强烈依赖于统计信息的时效性。
[^internal-ru-415-1]: [backend/executor/nodeIndexscan.c]().
[^internal-ru-415-2]: [backend/access/index/indexam.c](), 函数 index\_getnext\_tid.
[^internal-ru-416-1]: [backend/executor/nodeTidscan.c]().
[^internal-ru-416-2]: [backend/utils/adt/selfuncs.c](), 函数 btcostestimate; [postgrespro.ru/docs/postgresql/18/index-cost-estimation]().
[^internal-ru-421-1]: [backend/optimizer/path/costsize.c](), 函数 index\_pages\_fetched.
[^internal-ru-423-1]: [backend/optimizer/path/costsize.c](), 函数 cost\_index.
[^internal-ru-423-2]: [postgrespro.ru/docs/postgresql/18/indexes-index-only-scans]().
[^internal-ru-424-1]: [backend/executor/nodeIndexonlyscan.c]().
[^internal-ru-428-1]: [backend/access/index/indexam.c](), 函数 index\_getbitmap.
[^internal-ru-428-2]: [backend/executor/nodeBitmapIndexscan.c]().
[^internal-ru-428-3]: [backend/access/index/indexam.c](), 函数 index\_getbitmap.
[^internal-ru-428-4]: [backend/nodes/tidbitmap.c]().
[^internal-ru-429-1]: [backend/executor/nodeBitmapHeapscan.c]().
[^internal-ru-429-2]: [backend/nodes/tidbitmap.c](), 函数 tbm\_lossify.
[^internal-ru-430-1]: [postgrespro.ru/docs/postgresql/18/indexes-ordering]().
[^internal-ru-431-1]: [backend/nodes/tidbitmap.c](), 函数 tbm\_union 和 tbm\_intersect.
[^internal-ru-433-1]: [backend/optimizer/path/costsize.c](), 函数 compute\_bitmap\_pages.
[^internal-ru-433-2]: [backend/optimizer/path/costsize.c](), 函数 compute\_bitmap\_pages.
[^internal-ru-434-1]: [backend/optimizer/path/costsize.c](), 函数 cost\_bitmap\_heap\_scan.
[^internal-ru-435-1]: [backend/optimizer/path/costsize.c](), 函数 cost\_bitmap\_and\_node 和 cost\_bitmap\_or\_node.