PostgreSQL Internals之路 Part-IV 第20章 索引扫描

20.1 常规索引扫描

索引提供有两种访问 TIDS 的基本方法。第一个是执行索引扫描。大多数索引访问方法（但不是全部）都具有 INDEX SCAN 属性来支持此操作。

索引扫描在查询计划里是通过 Index Scan 节点来表示的：

=> EXPLAIN SELECT * FROM bookings
WHERE book_ref = '9AC0C6' AND total_amount = 48500.00;

                                  QUERY PLAN
-------------------------------------------------------------------------------
 Index Scan using bookings_pkey on bookings  (cost=0.42..8.44 rows=1 width=21)
   Index Cond: (book_ref = '9AC0C6'::bpchar)
   Filter: (total_amount = 48500.00)
(3 rows)

在索引扫描期间，访问方法逐个返回 TID。在接收到 TID 后，索引引擎访问它所引用的堆页面，获取相应的元组，如果满足可见性规则，则返回该元组所请求的字段集合。这个过程一直持续，直到访问方法用完与查询匹配的所有 TID 为止。

索引条件行只包括那些可以使用索引检查的筛选条件。必须针对堆重新检查的其他条件在 Filter 行中会单独被列出。

如本例所示，索引和堆访问操作都由一个公共 index Scan 节点处理，而不是由两个不同的节点处理。但是也有一个分隔的 Tid 扫描节点，它从堆中获取元组，如果它们的 ID 是事先已知的：

=> 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)

20.1.1 成本估计

索引扫描的成本估计包括索引访问操作和堆页面读取的估计成本。

显然，估计中与索引相关的部分完全取决于特定的访问方法。对于 B-tree，成本主要是由获取索引页和处理它们的条目引起的。要读取的页数和行数可以由数据总量和应用的筛选器的选择性决定。索引页是随机访问的（逻辑结构中彼此相连的页在物理上分散在磁盘上）。从根节点到叶节点并计算所有所需表达式所花费的资源进一步增加了估计。

估计中与堆相关的部分包括堆页面访问的成本和处理所有获取的元组所需的时间。需要注意的是，I/O 估计既取决于索引扫描选择性，也取决于磁盘上元组的物理顺序与访问方法返回元组的顺序之间的相关性。

20.1.2 好的场景：高关联度

如果磁盘上元组的物理顺序与索引中 TID 的逻辑顺序完全相关，则每个页面将只被访问一次：index Scan 节点将依次从一个页面转到另一个页面，逐个读取元组。

PostgreSQL 对相关性进行统计:

=> SELECT attname, correlation
FROM pg_stats WHERE tablename = 'bookings'
ORDER BY abs(correlation) DESC;
   attname    | correlation
--------------+-------------
 book_ref     |           1
 book_date    | 0.016161675
 total_amount | 0.008723774
(3 rows)

如果对应的绝对值接近于 1，则相关性很高（例如 book_ref 的情况）；接近于零的值是混沌数据分布的标志。

在本例中，book_ref 列中的高相关性当然是由于数据已根据该列按升序加载到表中，并且还没有更新。如果对该列上创建的索引执行命令，将看到相同的图。

然而，完美的相关性并不能保证所有查询都以升序返回 book_ref 值的结果。首先，任何行更新都会将结果元组移动到表的末尾。其次，依赖于基于其他列的索引扫描的计划以不同的顺序返回结果。即使是顺序扫描也可能不会从表的开头开始。因此，如果需要特定的顺序，应该在子句中显式地定义它。

下面是一个处理大量行的索引扫描示例：

EXPLAIN SELECT * FROM bookings WHERE book_ref < '100000';
                                     QUERY PLAN
-------------------------------------------------------------------------------------
 Index Scan using bookings_pkey on bookings  (cost=0.42..595.61 rows=16925 width=21)
   Index Cond: (book_ref < '100000'::bpchar)
(2 rows)

条件的选择性估计如下：

=> SELECT round(16925::numeric/reltuples::numeric, 4)
FROM pg_class WHERE relname = 'bookings';
 round
--------
 0.0644
(1 row)

这个值接近 p 到 1 16，我们知道 book_ref 的取值范围是到，就可以猜到。

对于-tree， / cost 估算中与索引相关的部分包括读取所有所需页面的成本。满足-tree 支持的任何条件的索引条目存储在绑定到有序列表的页面中，因此要读取的索引页面的数量是用索引大小乘以选择性来估计的。但是由于这些页面不是按物理顺序排列的，因此读取以随机的方式进行。

C 资源用于处理所有读取的索引条目（处理单个条目的成本估计为 0.005 cpu_index_tuple_cost 值）和计算每个条目的条件(在本例中，条件包含单个操作符；它的成本估计为 0.0025 （cpu_operator_cost 值）。

表访问被认为是对所需页数的顺序读取。在完全相关的情况下，堆元组将在磁盘上彼此紧跟着，因此页面的数量估计为表的大小乘以选择率。元组处理所产生的费用进一步扩展了 I/O 成本；并按每个元组 cpu_tuple_cost(默认 0.01)来预估成本。

=> 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
----------+----------+-------
      306 |      271 |   577
(1 row)

这些计算说明了成本估计背后的逻辑，因此结果与计划器提供的估计保持一致，即使它是近似值。获得确切的值需要考虑其他细节，我们在这里不打算讨论这些细节。

20.1.3 坏场景：低关联度

如果相关性低，一切都会改变。让我们在 book_date 列上创建一个索引，它与这个索引的相关性几乎为零，然后看看这个查询，它选择的行数与上一个示例中几乎相同。事实证明，索引访问的成本非常高，以至于计划器只有在明确禁止所有其他选择的情况下才会选择索引访问：

=> 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..56957.48 rows=132403 width=21)
Index Cond: (book_date < '2016−08−23 12:00:00+03'::timestamp w...
(3 rows)

问题是，低相关性增加了访问方法返回的下一个元组位于不同页面中的可能性。因此，Index Scan 节点必须在页面之间跳转，而不是顺序读取它们；在最坏的情况下，页面访问的次数可能达到获取元组的数量。

然而，我们不能简单地用 random_page_cost 代替 seq_page_cost，用 reltuples 代替 rel-pages。我们在计划中看到的成本远低于我们通过这种方式估计的价值：

=> 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
----------+----------+--------
      691 |   149919 | 150610
(1 row)

原因是该模型考虑了缓存。经常使用的页面保存在缓冲缓存中（以及缓存中），因此缓存大小越大，在其中找到所需页面的机会就越大，从而避免了额外的磁盘访问操作。出于规划目的，缓存大小由 4GB 的 effecve_cache_size 参数定义。它的值越小，预计读取的页面就越多。

下图显示了要读取的页面数的估计值与表大小之间的依赖关系（对于选择性为 1/2 和包含 10 行的页面）虚线表示最佳场景中的访问计数（如果相关性完美，则为页面计数的一半）和最差场景中的访问计数（如果相关性为零且没有缓存，则为行计数的一半）。

假设 effecve_cache_size 值表示可以用于缓存的内存总量（包括 PostgreSQL 缓冲区缓存和 OS 缓存）。但是由于该参数仅用于估计目的，并不影响内存分配本身，因此在更改此设置时不必将实际数字考虑进去。

如果将 effecve_cache_size 减小到最小，计划估计将接近上面所示的无缓存情况的低端值：

=> 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)
=> RESET effective_cache_size;
=> RESET enable_seqscan;
=> RESET enable_bitmapscan;

规划器计算最坏情况和最佳情况的表的 I/O 成本，然后根据实际相关性取一个中间值。

因此，如果只需要读取一小部分行，索引扫描可能是一个不错的选择。如果堆元组与访问方法返回它们的顺序相关，那么这个分数可能相当大。但是，如果相关性较低，索引扫描对低选择性查询的吸引力就会降低。

20.2 仅索引扫描

如果索引包含查询所需的所有堆数据，则它被称为此特定查询的覆盖索引。如果这样的索引可用，则可以避免额外的表访问：访问方法可以直接返回实际数据，而不是 TIDs。这种类型的索引扫描称为仅索引扫描^[1]。它可以被那些支持 Returnable 属性的访问方法使用。

在该计划中，该操作由 Index Only Scan3 节点表示：

=> EXPLAIN SELECT book_ref FROM bookings WHERE book_ref < '100000';
		QUERY PLAN
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
Index Only Scan using bookings_pkey on bookings
	(cost=0.43..3791.91 rows=132999 width=7)
Index Cond: (book_ref < '100000'::bpchar)
(3 rows)

这个名称暗示这个节点永远不需要访问堆，但事实并非如此。在 PostgreSQL 中，索引不包含关于元组可见性的信息，因此访问方法返回所有满足过滤条件的堆元组的数据，即使当前事务无法看到它们。然后由索引引擎检查它们的可见性。

但是，如果此方法必须访问表以检查每个元组的可见性，则与常规索引扫描没有任何不同。相反，它使用为表提供的可见性映射，其中 VACUUM 进程标记仅包含所有可见元组的页面（即所有事务都可以访问的元组，无论使用的快照如何）。如果索引访问方法返回的内容属于这样的页面，则不需要检查其可见性。

仅索引扫描的成本估计取决于堆中所有可见页面的比例。PostgreSQL 收集这样的统计数据：

=> SELECT relpages, relallvisible
FROM pg_class WHERE relname = 'bookings';
relpages  | relallvisible
−−−−−−−−−−+−−−−−−−−−−−−−−−
13447     | 13446
(1 row)

仅索引扫描的成本估算与常规索引扫描的成本估算不同：其与表访问相关的 I/O 成本与未出现在可见性映射中的页面比例成比例。（元组处理的成本估计是相同的。）

因为在这个特殊的例子中，所有的页面都只包含所有可见的元组，堆 I/O 成本实际上被排除在成本估计之外：

=> 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) * -- fraction of non-all-visible pages
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 |1330 |3787
(1 row)

任何未清除的更改，如果没有消失在数据库范围水平线之后，则会增加计划的估计成本（因此，使该计划对优化器的吸引力降低）。命令 EXPLAIN ANALYZE 可以显示实际的堆访问计数。

在一个新创建的表中，PostgreSQL 必须检查所有元组的可见性：

=> 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)
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..4638.91 rows=132999 width=7) (actual rows=132109 l...
Index Cond: (book_ref < '100000'::bpchar)
Heap Fetches: 132109
(4 rows)

但是，一旦表被清空，这样的检查就变得多余了，只要所有页面都是可见的，就不会执行这样的检查。

=> VACUUM bookings_tmp;
=> EXPLAIN (analyze, timing off, summary 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..3787.91 rows=132999 width=7) (actual rows=132109 l...
Index Cond: (book_ref < '100000'::bpchar)
Heap Fetches: 0
(4 rows)

20.2.1 带 Include 子句的索引

并不总是可以用查询所需的所有列扩展索引：

• 对于惟一索引，添加新列将损害原始键列的惟一性。

• 索引访问方法可能没有为要添加的列的数据类型提供操作符类。

在这种情况下，您仍然可以将列包含到索引中，而不必将它们作为索引键的一部分。当然，不可能基于包含的列执行索引扫描，但是如果查询引用了这些列，则索引将作为覆盖索引。

下面的示例展示了如何用包含列的另一个索引替换自动创建的主键索引：

=> 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; -- a new index
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..437...
Index Cond: (book_ref < '100000'::bpchar)
(2 rows)

这种指数通常被称为覆盖指数，但并不完全正确。如果索引的列集覆盖了特定查询所需的所有列，则认为索引覆盖了。无论它是否涉及 INCLUDE 子句添加的任何列，还是只使用键列，都无关紧要。此外，同一个索引可以覆盖一个查询而不覆盖另一个查询。

20.3 位图扫描

索引扫描的效率是有限的：随着相关性的降低，对堆页面的访问次数增加，并且扫描变得随机而不是顺序。为了克服这个限制，PostgreSQL 可以在访问表之前获取所有的 TIDs，并根据它们的页码^[2]按升序排序这正是位图扫描的工作原理，这是另一种常见的处理 TIDs 的方法。它可以被那些支持 BITMAP SCAN(位图扫描）属性的访问方法使用。

与常规索引扫描不同，此操作在查询计划中由两个节点表示：

=> 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..7040.42 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)

位图索引 Scan 节点从访问方法获取所有 TIDs 的位图。

位图由单独的段组成，每个段对应一个堆页面。所有这些段都有相同的大小，这对于所有页面元组来说都足够了，不管它们有多少个。这个数字是有限的，因为元组头文件相当大；一个标准大小的页面最多可以容纳 256 个元组，它与 32 个字节相适应。

然后位图堆扫描逐个段遍历位图，读取相应的页面，并检查所有标记为全可见的元组。因此，根据页数按升序读取页面，并且每个页面只读取一次。

也就是说，这个过程与顺序扫描不同，因为访问的页面很少遵循彼此。操作系统执行的常规预取在这种情况下没有帮助，因此位图堆扫描节点通过异步读取 effective_io_concurrency 页面来实现它自己的预取——而且它是唯一执行此操作的节点。此机制依赖于某些操作系统实现的 posix_fadvise 函数。如果您的系统支持此函数，那么根据硬件功能在表空间级别配置 effecve_io_concurrency 参数是有意义的。

异步预取也用于其他一些内部进程：

• 堆中的行被删除晨的索引页
• 在分析时的堆页面

预取的深度由:　 maintenance_io_concurrency 来定义。

20.4.1 位图精度

包含满足查询筛选条件的元组的页面越多，位图就越大。它构建在后端本地内存中，其大小受到 4MB work_mem 参数的限制。一旦达到允许的最大大小，一些位图段就会成为有损的：有损段的每个位对应于整个页面，而段本身包含一系列页面^[3]。因此，在精度作为代价的前提下，位图的大小变得更小。

EXPLAIN ANALYZE 命令展示了创建出来的位置的精度：

=> EXPLAIN (analyze, costs off, timing off, summary off)
SELECT * FROM bookings WHERE total_amount > 150000.00;
QUERY PLAN
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
Bitmap Heap Scan on bookings (actual rows=242691 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)
(5 rows)

这里我们对目标位置拥有足够的内存：

如果我们减少 WORK_MEM 的值，某些位图段将变成有损位图：

=> SET work_mem = '512kB';
=> EXPLAIN (analyze, costs off, timing off, summary off)
SELECT * FROM bookings WHERE total_amount > 150000.00;
QUERY PLAN
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
Bitmap Heap Scan on bookings (actual rows=242691 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)
(6 rows)
=> RESET work_mem;

当读取与有损位图段对应的堆页面时，PostgreSQL 必须重新检查页面中每个元组的过滤条件。要重新检查的条件总是在计划中显示为“ReCheck Cond”，即使没有执行此重新检查。在重新检查期间过滤掉的元组数量将单独显示（显示为 Index recheck 删除的行）。

如果结果集的大小太大，则位图可能不适合 work_mem 内存块，即使它的所有段都是有损的。然后忽略这个限制，并且位图占用尽可能多的空间。PostgreSQL 既不会进一步降低位图精度，也不会将其任何段刷新到磁盘。