PostgreSQL 18 preview - index skip scan 优化

PostgreSQL 18 preview - index skip scan 优化

在说PostgreSQL 18 的 index skip scan优化手段之前, 先翻一下之前的吐槽文章, 大致回顾一下缺少skip scan在某些场景下有多挫.

• 《SQLite3 的index skip scan优化器功能》
• 《DB吐槽大会,第62期 - PG 不支持index skip scan》
• 《PostgreSQL 时序数据库插件 timescaledb 2.2.1 通过custom plan provider接口实现index skip scan, 加速distinct, last_value, first_value等大表稀疏值快速搜索, 最快上万倍性能提升》
• 《递归+排序字段加权 skip scan 解决 窗口查询多列分组去重的性能问题》
• 《PostgreSQL Oracle 兼容性之 - INDEX SKIP SCAN (递归查询变态优化) 非驱动列索引扫描优化》
• 《distinct xx和count(distinct xx)的变态递归优化方法 - 索引收敛(skip scan)扫描》

不过PG 18要翻身了, 陆续开始引入skip scan的基础框架和优化器的支持..

• 《PostgreSQL 18 preview - 索引启发式扫描 优化 in , = any(array) 多值匹配性能》

简单来说就是缺少驱动列条件时, 如何优化?

例如 INDEX ON t1 (a, b, c), 查询 WHERE b = 5 AND c = 10 时，因为缺少对第一个索引列 a 的 = 条件，传统的索引扫描（Index Scan）效率不高。需要遍历整个索引的叶子结点.

skip scan的核心是先找到最小的a, 然后匹配其b,c. 结束后马上找下一个a, 而不是通过叶子结点的链表全面扫描. skip scan适合驱动列缺失并且驱动列的唯一值较少的情况.

https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit;h=92fe23d93aa3bbbc40fca669cabc4a4d7975e327

Add nbtree skip scan optimization.  
author Peter Geoghegan <[email protected]>   
Fri, 4 Apr 2025 16:27:04 +0000 (12:27 -0400)  
committer Peter Geoghegan <[email protected]>   
Fri, 4 Apr 2025 16:27:04 +0000 (12:27 -0400)  
commit 92fe23d93aa3bbbc40fca669cabc4a4d7975e327  
tree e79d024c849f0a0b89378ff8c16b6d6b2d0cc777 tree  
parent 3ba2cdaa45416196fadc7163998cda7b4e07e7d7 commit | diff  
Add nbtree skip scan optimization.  
Teach nbtree multi-column index scans to opportunistically skip over  
irrelevant sections of the index given a query with no "=" conditions on  
one or more prefix index columns.  When nbtree is passed input scan keys  
derived from a predicate "WHERE b = 5", new nbtree preprocessing steps  
output "WHERE a = ANY(<every possible 'a' value>) AND b = 5" scan keys.  
That is, preprocessing generates a "skip array" (and an output scan key)  
for the omitted prefix column "a", which makes it safe to mark the scan  
key on "b" as required to continue the scan.  The scan is therefore able  
to repeatedly reposition itself by applying both the "a" and "b" keys.  
A skip array has "elements" that are generated procedurally and on  
demand, but otherwise works just like a regular ScalarArrayOp array.  
Preprocessing can freely add a skip array before or after any input  
ScalarArrayOp arrays.  Index scans with a skip array decide when and  
where to reposition the scan using the same approach as any other scan  
with array keys.  This design builds on the design for array advancement  
and primitive scan scheduling added to Postgres 17 by commit 5bf748b8.  
Testing has shown that skip scans of an index with a low cardinality  
skipped prefix column can be multiple orders of magnitude faster than an  
equivalent full index scan (or sequential scan).  In general, the  
cardinality of the scan's skipped column(s) limits the number of leaf  
pages that can be skipped over.  

The core B-Tree operator classes on most discrete types generate their  
array elements with the help of their own custom skip support routine.  
This infrastructure gives nbtree a way to generate the next required  
array element by incrementing (or decrementing) the current array value.  
It can reduce the number of index descents in cases where the next  
possible indexable value frequently turns out to be the next value  
stored in the index.  Opclasses that lack a skip support routine fall  
back on having nbtree "increment" (or "decrement") a skip array's  
current element by setting the NEXT (or PRIOR) scan key flag, without  
directly changing the scan key's sk_argument.  These sentinel values  
behave just like any other value from an array -- though they can never  
locate equal index tuples (they can only locate the next group of index  
tuples containing the next set of non-sentinel values that the scan's  
arrays need to advance to).  
A skip array's range is constrained by "contradictory" inequality keys.  
For example, a skip array on "x" will only generate the values 1 and 2  
given a qual such as "WHERE x BETWEEN 1 AND 2 AND y = 66".  Such a skip  
array qual usually has near-identical performance characteristics to a  
comparable SAOP qual "WHERE x = ANY('{1, 2}') AND y = 66".  However,  
improved performance isn't guaranteed.  Much depends on physical index  
characteristics.  
B-Tree preprocessing is optimistic about skipping working out: it  
applies static, generic rules when determining where to generate skip  
arrays, which assumes that the runtime overhead of maintaining skip  
arrays will pay for itself -- or lead to only a modest performance loss.  
As things stand, these assumptions are much too optimistic: skip array  
maintenance will lead to unacceptable regressions with unsympathetic  
queries (queries whose scan can't skip over many irrelevant leaf pages).  
An upcoming commit will address the problems in this area by enhancing  
_bt_readpage's approach to saving cycles on scan key evaluation, making  
it work in a way that directly considers the needs of = array keys  
(particularly = skip array keys).  
Author: Peter Geoghegan <[email protected]>  
Reviewed-By: Masahiro Ikeda <[email protected]>  
Reviewed-By: Heikki Linnakangas <[email protected]>  
Reviewed-By: Matthias van de Meent <[email protected]>  
Reviewed-By: Tomas Vondra <[email protected]>  
Reviewed-By: Aleksander Alekseev <[email protected]>  
Reviewed-By: Alena Rybakina <[email protected]>  
Discussion: https://postgr.es/m/CAH2-Wzmn1YsLzOGgjAQZdn1STSG_y8qP__vggTaPAYXJP+G4bw@mail.gmail.com  

https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit;h=21a152b37f36c9563d1b0b058fe1436baf578b4c

Improve nbtree skip scan primitive scan scheduling.  
author Peter Geoghegan <[email protected]>   
Fri, 4 Apr 2025 17:58:05 +0000 (13:58 -0400)  
committer Peter Geoghegan <[email protected]>   
Fri, 4 Apr 2025 17:58:05 +0000 (13:58 -0400)  
commit 21a152b37f36c9563d1b0b058fe1436baf578b4c  
tree 667c7fb8614d019fbbf53b9e39f7d03990e9d0f2 tree  
parent cf2655a9029aff63dd567dbbdcdee15ec969905d commit | diff  
Improve nbtree skip scan primitive scan scheduling.  
Don't allow nbtree scans with skip arrays to end any primitive scan on  
its first leaf page without giving some consideration to how many times  
the scan's arrays advanced while changing at least one skip array  
(though continue not caring about the number of array advancements that  
only affected SAOP arrays, even during skip scans with SAOP arrays).  
Now when a scan performs more than 3 such array advancements in the  
course of reading a single leaf page, it is taken as a signal that the  
next page is unlikely to be skippable.  We'll therefore continue the  
ongoing primitive index scan, at least until we can perform a recheck  
against the next page's finaltup.  
Testing has shown that this new heuristic occasionally makes all the  
difference with skip scans that were expected to rely on the "passed  
first page" heuristic added by commit 9a2e2a28.  Without it, there is a  
remaining risk that certain kinds of skip scans will never quite manage  
to clear the initial hurdle of performing a primitive scan that lasts  
beyond its first leaf page (or that such a skip scan will only clear  
that initial hurdle when it has already wasted noticeably-many cycles  
due to inefficient primitive scan scheduling).  
Follow-up to commits 92fe23d9 and 9a2e2a28.  
Author: Peter Geoghegan <[email protected]>  
Reviewed-By: Matthias van de Meent <[email protected]>  
Discussion: https://postgr.es/m/CAH2-Wz=RVdG3zWytFWBsyW7fWH7zveFvTHed5JKEsuTT0RCO_A@mail.gmail.com  

https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit;h=b3f1a13f22f9e28842ee5fbd08b7ec805e27aaac

Avoid extra index searches through preprocessing.  
author Peter Geoghegan <[email protected]>   
Fri, 4 Apr 2025 18:14:08 +0000 (14:14 -0400)  
committer Peter Geoghegan <[email protected]>   
Fri, 4 Apr 2025 18:14:08 +0000 (14:14 -0400)  
commit b3f1a13f22f9e28842ee5fbd08b7ec805e27aaac  
tree a8a352ad3cca638e9c35f94da34a72fd6a8b8f31 tree  
parent 21a152b37f36c9563d1b0b058fe1436baf578b4c commit | diff  
Avoid extra index searches through preprocessing.  
Transform low_compare and high_compare nbtree skip array inequalities  
(with opclasses that offer skip support) in such a way as to allow  
_bt_first to consistently apply later keys when it descends the tree.  
This can lower the number of index searches for multi-column scans that  
use a ">" key on one of the index's prefix columns (or use a "<" key,  
when scanning backwards) when it precedes some later lower-order key.  

For example, an index qual "WHERE a > 5 AND b = 2" will now be converted  
to "WHERE a >= 6 AND b = 2" by a new preprocessing step that takes place  
after low_compare and high_compare have been finalized.  That way, the  
initial call to _bt_first can use "WHERE a >= 6 AND b = 2" to find an  
initial position, rather than just using "WHERE a > 5" -- "b = 2" can be  
applied during every _bt_first call.  There's a decent chance that this  
will allow such a scan to avoid the extra search that might otherwise be  
needed to determine the lowest "a" value still satisfying "WHERE a > 5".  
The transformation process can only lower the total number of index  
pages read when the use of a more restrictive set of initial positioning  
keys in _bt_first actually allows the scan to land on some later leaf  
page directly, relative to the unoptimized case (or on an earlier leaf  
page directly, when scanning backwards).  But the savings can really add  
up in cases where an affected skip array comes after some other array.  
For example, a scan indexqual "WHERE x IN (1, 2, 3) AND y > 5 AND z = 2"
can save as many as 3 _bt_first calls by applying the new transformation  
to its "y" array (up to 1 extra search can be avoided per "x" element).  
Follow-up to commit 92fe23d9, which added nbtree skip scan.  
Author: Peter Geoghegan <[email protected]>  
Reviewed-By: Matthias van de Meent <[email protected]>  
Discussion: https://postgr.es/m/CAH2-Wz=FJ78K3WsF3iWNxWnUCY9f=Jdg3QPxaXE=uYUbmuRz5Q@mail.gmail.com  

AI 解读

这三个相关的 PostgreSQL Patch，它们共同构成了一个重要的 B-Tree 索引优化：**跳跃扫描 (Skip Scan)**。

核心目标： 提升多列 B-Tree 索引在缺少前缀列 = 条件查询时的性能。

Patch 1: (Commit 92fe23d9) "Add nbtree skip scan optimization." - 引入 nbtree 跳跃扫描优化

• 解决了什么问题？

• 假设你有一个多列索引，例如 INDEX ON t1 (a, b, c)。
• 当你查询 WHERE b = 5 AND c = 10 时，因为缺少对第一个索引列 a 的 = 条件，传统的索引扫描（Index Scan）效率不高。它可能需要扫描所有 a 值对应的 (b=5, c=10) 的索引条目，即使很多 a 的分支下根本不存在 b=5 的情况。这可能导致扫描大量无关的索引页。

• 如何解决 (核心机制)？

• 当遇到像 WHERE b = 5 这样的查询（缺少前缀列 a 的 = 条件）时，优化器会在内部“改造”查询条件。它会生成一个针对列 a 的“跳跃数组”。
• 这个跳跃数组的作用类似于 a = ANY(<所有可能的 a 值>)。它不是真的存储所有 a 值，而是一个“按需生成”值的机制。
• 这样，内部处理的扫描条件就变成了类似 WHERE a = <当前跳跃数组的值> AND b = 5。
• 引入“跳跃扫描” (Skip Scan)： 这个 Patch 允许 B-Tree 索引扫描在这种情况下“跳过”不相关的索引部分。
• “跳跃数组” (Skip Array)：
• 扫描过程：
• 利用现有框架： 这个设计复用了 Postgres 17 中为数组操作（ScalarArrayOp）和原子扫描调度（primitive scan scheduling）添加的基础设施（Commit 5bf748b8）。跳跃数组的工作方式和普通的 IN (...) 或 = ANY(...) 的数组类似。
• 性能提升： 对于被跳过的前缀列（如 a）基数（不同值的数量）较低的情况，性能提升可能达到几个数量级。基数越低，能跳过的索引页越多。

1. 找到第一个满足 a = <a 的第一个可能值> AND b = 5 的索引项。
2. 处理完这个 a 值下所有 b = 5 的项后，利用跳跃数组机制直接定位到下一个可能的 a 值（比如 a = <a 的下一个可能值>），并再次结合 b = 5 条件进行查找。
3. 这个过程允许扫描跳过那些中间 a 值下所有 b != 5 的索引条目和叶子页。

• 操作符类支持 (Opclass Support): 对于大多数离散数据类型（如整数、文本等），B-Tree 的核心操作符类提供了自定义的“跳跃支持例程” (skip support routine)。这使得 nbtree 可以通过递增/递减当前值来高效地生成跳跃数组的下一个元素，有时能避免额外的索引树下降 (index descent)。
• 无支持时的回退： 如果操作符类没有提供跳跃支持，nbtree 会使用特殊的标记 (NEXT/PRIOR scan key flag) 来表示需要移动到下一个/上一个不同的值组，虽然效率稍低，但功能依然可用。
• 不等式约束： 如果查询中包含对跳跃列的不等式条件（如 WHERE a BETWEEN 1 AND 2 AND b = 66），跳跃数组生成的范围会受到限制（只会生成 1 和 2）。这种情况下性能接近于 WHERE a = ANY('{1, 2}') AND b = 66。
• 乐观策略与未来改进： 当前的预处理逻辑比较“乐观”，总是假设跳跃扫描能带来好处。但这可能导致在某些不适合跳跃的查询（无法跳过很多页）中，维护跳跃数组的开销反而导致性能下降（Regression）。作者提到，后续会有 Commit 改进 _bt_readpage 中的扫描键评估逻辑，以更智能地处理数组键（特别是跳跃数组键），减少这种开销。 (这是对未来工作的预告)

Patch 2: (Commit 3ab681bc) "Improve nbtree skip scan primitive scan scheduling." - 改进 nbtree 跳跃扫描的原子扫描调度

• 解决了什么问题？

• “原子扫描”（Primitive Scan）是索引扫描内部执行的更小粒度的扫描单元。之前的调度逻辑（特别是 Commit 9a2e2a28 引入的“通过第一页”启发式规则）对于跳跃扫描可能不够优化。
• 问题在于，一个跳跃扫描可能在同一个索引叶子页内，因为前缀列（跳跃列）的值变化而多次推进其跳跃数组。旧的调度逻辑可能只看到扫描还在第一页，就过早地结束了当前的原子扫描，导致启动和停止原子扫描的开销过大，效率低下。

• 如何解决 (新启发式规则)？

• 增加新规则： 如果一个带有跳跃数组的扫描，在处理单个叶子页的过程中，其跳跃数组（只关心跳跃数组，不关心普通的 SAOP 数组）被推进（advance）了超过 3 次，那么就认为下一页不太可能被跳过（因为当前页内值的密度就很高了）。
• 行为改变： 在这种情况下，即使还在原子扫描的第一个叶子页，扫描也会继续进行到下一页，而不是立即结束当前的原子扫描。这有助于避免因跳跃数组在密集区域内频繁小步前进导致的调度效率低下。
• 效果： 这个新规则在某些场景下可以显著改善跳跃扫描的性能，帮助扫描“越过”初始难以跳跃的阶段，减少不必要的调度开销。

• 上下文： 这是对前一个跳跃扫描补丁 (92fe23d9) 和另一个调度补丁 (9a2e2a28) 的跟进修复和改进。

Patch 3: (Commit f08a3c2b) "Avoid extra index searches through preprocessing." - 通过预处理避免额外的索引搜索

• 解决了什么问题？

• 考虑一个查询 WHERE a > 5 AND b = 2，索引是 (a, b)。
• 在引入跳跃扫描后，a > 5 会被处理（可能涉及跳跃数组或范围限制）。但在初始定位（_bt_first 函数调用）时，可能只使用了 a > 5 这个条件来找到第一个 a 值大于 5 的位置。然后可能需要进行额外的查找或检查来应用 b = 2 这个条件，尤其是在找到第一个 a 值后需要找到该 a 值下 b=2 的具体位置。这可能导致额外的索引树下降（index search）。

• 如何解决 (预处理转换)？

• 对于 a > 5 （正向扫描），将其转换为 a >= 6 (假设 a 是整数类型，能计算出紧邻 5 的下一个值是 6)。
• 对于 a < 5 （反向扫描），类似地转换为 a <= 4。
• 新的预处理步骤： 对于支持跳跃的操作符类（能计算出下一个离散值），在预处理阶段增加一个转换步骤。
• 转换逻辑：
• 效果： 转换后的条件 WHERE a >= 6 AND b = 2 可以让初始的 _bt_first 调用同时使用这两个条件进行更精确的定位。这增加了直接在 B-Tree 下降过程中就利用 b = 2 条件的可能性，从而可能直接降落到满足所有条件的第一个索引条目所在的叶子页，避免了原本可能需要的额外搜索。
• 显著场景： 当跳跃/范围条件（如 y > 5）前面还有其他数组条件时（如 WHERE x IN (1, 2, 3) AND y > 5 AND z = 2），这个优化效果更明显。因为对于 x 的每个值（1, 2, 3），原本都可能需要一次额外的搜索来处理 y > 5，现在通过转换为 y >= 6，每次都能更精确地定位，最多可能节省 3 次 _bt_first 调用（对应 x 的每个值节省一次）。

• 上下文： 这是对引入跳跃扫描的补丁 (92fe23d9) 的进一步优化。

总结:

这三个 Patch 协同工作：

1. Patch 1 (92fe23d9): 奠定了基础，引入了 B-Tree 跳跃扫描的核心机制（跳跃数组），用于优化缺少前缀列 = 条件的多列索引查询，能大幅提升特定查询的性能，但也指出了初期实现的性能隐患。
2. Patch 2 (3ab681bc): 针对 Patch 1 引入的跳跃扫描，改进了其内部的原子扫描调度逻辑，通过新的启发式规则避免了在数据密集区域进行跳跃扫描时可能出现的调度效率低下的问题。
3. Patch 3 (f08a3c2b): 进一步优化了跳跃扫描（尤其是涉及前缀列不等式条件时）的初始定位过程，通过预处理转换条件，使得初始索引查找能利用更多信息，减少不必要的索引搜索次数。

总的来说，这一系列补丁显著增强了 PostgreSQL 处理多列索引的能力，使得在更多查询场景下，即使查询条件不完全匹配索引前缀，也能高效地利用索引，避免全索引扫描或低效的部分扫描。