PostgreSQL 18 preview - 索引启发式扫描 优化 in , = any(array) 多值匹配性能
digoal约 6 分钟PostgreSQL 18 preview - 索引启发式扫描 优化 in , = any(array) 多值匹配性能
当数据库在处理 WHERE column = ANY(array) , WHERE column in (...) 这类多个条件匹配的查询时, 如果使用索引扫描, 原始扫描逻辑如下:
页1 → 结束 → 重启扫描 → 页2 → 结束 → 重启扫描 → 页3...
以上扫描逻辑在某些情况下会浪费CPU和IO, 例如条件在同一个或密集在一些有序block内时. 例如 in (1,2,3,4,...) 显然会在相邻索引叶子页面里. PostgreSQL 18 引入了一个扫描优化, 启发式扫描:
新逻辑：页1 → 页2（直接步进） → 页3（直接步进）...
如果原始扫描（primitive scan）已经从初始叶子页向右或向左移动到相邻页（说明匹配条目可能密集分布），则不会立即结束扫描。不需要每次都重新从btree的root开始扫描, 而是在叶子节点直接步进.
https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit;h=9a2e2a285a149490a69a7bd92dd618bb7ca975b3
Improve nbtree array primitive scan scheduling.
author Peter Geoghegan <[email protected]>
Sat, 22 Mar 2025 17:02:18 +0000 (13:02 -0400)
committer Peter Geoghegan <[email protected]>
Sat, 22 Mar 2025 17:02:18 +0000 (13:02 -0400)
commit 9a2e2a285a149490a69a7bd92dd618bb7ca975b3
tree f4871e5e813c243c710dc63e67023b8216899ed8 tree
parent e215166c9c810950cff101cc098e66c8758538fa commit | diff
Improve nbtree array primitive scan scheduling. Add a new scheduling heuristic: don't end the ongoing primitive index
scan immediately (at the point where _bt_advance_array_keys notices that
the next set of matching tuples must be on a later page) if the primscan
already managed to step right/left from its first leaf page. Schedule a
recheck against the next sibling leaf page's finaltup instead.
The new heuristic tends to avoid scenarios where the top-level scan
repeatedly starts and ends primitive index scans that each read only one
leaf page from a group of neighboring leaf pages. Affected top-level
scans will now tend to step forward (or backward) through the index
instead, without wasting cycles on descending the index anew.
The recheck mechanism isn't exactly new. But up until now it has only
been used to deal with edge cases involving high key finaltups with one
or more truncated -inf attributes that _bt_advance_array_keys deemed
"provisionally satisfied" (satisfied for the purposes of allowing the
scan to step onto the next page, subject to recheck once on that page).
The mechanism was added by commit 5bf748b8, which invented the general
concept of primitive scan scheduling. It was later enhanced by commit
79fa7b3b, which taught it about cases involving -inf attributes that
satisfy inequality scan keys required in the opposite-to-scan direction
only (arguably, they should have been covered by the earliest version).
Now the recheck mechanism can be applied based on scan-level heuristics,
which have nothing to do with truncated high keys. Now rechecks might
be performed by _bt_readpage when scanning in _either_ scan direction.
The theory behind the new heuristic is that any primitive scan that
makes it past its first leaf page is one that is already likely to have
arrays whose key values match index tuples that are closely clustered
together in the index. The rules that determine whether we ever get
past the first page are still conservative (that'
ll still only happen
when pstate.finaltup strongly suggests that it's the right thing to do).
Surviving past the first leaf page is a strong signal in itself.
Preparation for an upcoming patch that will add skip scan optimizations
to nbtree. That'll work by adding skip arrays, which behave similarly
to SAOP arrays, but generate their elements procedurally and on-demand. Note that this commit isn't specifically concerned with skip arrays; the
scheduling logic doesn't (and won't) condition anything on whether the
scan uses skip arrays, SAOP arrays, or some combination of the two
(which seems like a good general principle for _bt_advance_array_keys).
While the problems that this commit ameliorates are more likely with
skip arrays (at least in practice), SAOP arrays (or those with very
dense, contiguous array elements) are also affected.
Author: Peter Geoghegan <[email protected]>
Reviewed-By: Matthias van de Meent <[email protected]>
Discussion: https://postgr.es/m/CAH2-Wzkz0wPe6+02kr+hC+JJNKfGtjGTzpG3CFVTQmKwWNrXNw@mail.gmail.com
AI 解读
解读：nbtree 数组原始扫描调度优化补丁
补丁目标
优化 PostgreSQL 中 B 树索引（nbtree）在处理包含数组的查询时的扫描效率，减少因频繁重启扫描导致的性能损耗。
问题背景
• 场景：当使用 WHERE column = ANY(array) 这类数组条件查询时，优化器会生成多个扫描键（scan keys），每个键对应数组中的一个元素。
• 原始逻辑：若扫描发现下一个匹配的元组在后续页面，会立即结束当前扫描，重新开始新的扫描（从根节点逐层下探到叶子页）。
• 缺陷：若数组元素对应的索引条目集中在相邻的叶子页中，频繁重启扫描会导致重复的索引遍历，浪费 CPU 和 I/O 资源。
核心改进
新启发式规则
• 触发条件：如果原始扫描（primitive scan）已经从初始叶子页向右或向左移动到相邻页（说明匹配条目可能密集分布），则不会立即结束扫描。
• 行为变更：安排在下个兄弟叶子页的finaltup（页末元组）处重新检查，直接步进到相邻页继续扫描，避免重新遍历索引树。Recheck 机制的扩展
• 原用途：仅处理高键（high key）被截断的特殊情况（如-inf属性匹配）。
• 新用途：基于扫描级别的启发式决策，即使没有高键问题，也会触发重新检查相邻页。
技术原理
• finaltup 的作用：
每个叶子页的最后一个元组（finaltup）用于判断后续页是否可能存在匹配数据。若当前页的 finaltup 符合条件，则继续扫描下一个页。
• 示例流程：
原始逻辑：页1 → 结束 → 重启扫描 → 页2 → 结束 → 重启扫描 → 页3...
新逻辑：页1 → 页2（直接步进） → 页3（直接步进）...
性能优化效果
• 减少索引遍历：避免重复从根节点下探到叶子页，减少 CPU 和磁盘 I/O。
• 适用场景：
• 密集分布的数组元素：如查询 WHERE id IN (1, 2, 3)，且这些 ID 对应的索引条目集中在相邻页。
• 未来 Skip Scan 优化：为后续动态生成扫描键（如范围扫描）提供基础，进一步提升复杂查询效率。
实现细节
• 代码改动：
• 修改 _bt_advance_array_keys 逻辑，增加对“是否已移动过页面”的判断。
• 扩展 _bt_readpage 中的 recheck 逻辑，支持双向（向前/向后）扫描。
• 保守规则：
仅当 pstate.finaltup 强烈建议继续扫描时（如相邻页可能有匹配数据），才触发新逻辑。
对用户的影响
• 性能提升：包含数组的查询（尤其是元素密集的情况）执行速度更快。
• 透明优化：无需修改查询或配置，由优化器自动应用。
• 兼容性：与现有 SAOP（Scalar Array Op）数组和未来的 Skip Scan 优化兼容。
技术背景
• 相关提交：
• 初始 recheck 机制（commit 5bf748b8）用于处理高键截断问题。
• 扩展 recheck（commit 79fa7b3b）支持 -inf 属性的特殊匹配。
• 未来计划：
支持 Skip Scan，动态生成扫描键（类似数组但更灵活），进一步优化范围查询。
总结
此补丁通过优化扫描调度逻辑，显著减少了数组查询时的索引遍历开销，为后续高级优化（如 Skip Scan）奠定了基础。核心思想是“利用邻近页的连续性，避免无意义的索引树重遍历”。