PostgreSQL查询为何能高效使用列序为(c3,c2)的复合索引？

问题复现 #

现有测试表DDL定义如下：

CREATE TABLE test
(
    c1 SMALLINT  NOT NULL,
    c2 INTERVAL  NOT NULL,
    c3 TIMESTAMP NOT NULL,
    c4 VARCHAR   NOT NULL,
    PRIMARY KEY (c1, c2, c3)
);

CREATE INDEX test_index ON test (c3, c2);

执行查询语句：

SELECT *
FROM test
WHERE c2 = '1 minute'::INTERVAL
ORDER BY c3
LIMIT 1000

PostgreSQL 13.3版本输出的执行计划如下：

Limit  (cost=0.43..49.92 rows=1000 width=60)
    ->  Index Scan using test_index on test  (cost=0.43..316739.07 rows=6400526 width=60)
            Index Cond: (c2 = '00:01:00'::interval)

已知test_index的列定义顺序为(c3, c2)，按照常规经验，ORDER BY涉及的列需要位于索引定义的末尾才能命中索引消除排序，但上述查询不仅命中了该索引完成c2字段过滤，改写为ORDER BY c3 DESC时也能同样命中索引，需要解释该现象的底层逻辑。

底层原理 #

这个现象和常规索引规则并不冲突，本质是B树索引有序性在等值过滤场景下的正常适配，核心逻辑如下：

• B树多列索引的排序规则严格遵循定义顺序：(c3, c2)结构的索引，所有索引条目先按c3的值做全局升序排列，c3取值相同的条目，再按c2的值排序存储，叶子节点通过双向链表串联。
• 当WHERE子句对索引后缀列做等值匹配时，索引前缀列的全局有序性不会被破坏。可以把这个索引结构类比成现代汉语字典：c3对应字典的拼音首字母排序规则，c2对应每个首字母分组下的声调排序规则。如果要筛选所有声调为第一声的汉字，并且要求结果按拼音首字母排序，只需要顺着字典的页码顺序从头到尾翻阅，每个首字母分组下挑出符合声调要求的字即可，挑出的结果天然就是按拼音首字母有序的，完全不需要额外排序。这个案例里c2固定为'1 minute'::INTERVAL就是那个固定的声调筛选条件，顺着索引扫描得到的匹配条目天然按c3有序，直接满足ORDER BY的排序要求。
• ORDER BY c3 DESC也能命中索引的原因很简单：PostgreSQL的B树索引支持双向扫描，顺着叶子节点的双向链表从前往后扫可以得到c3升序的结果，从后往前扫就可以得到c3降序的结果，不需要额外创建倒序索引就能适配倒序排序需求。
• 注意这个优化有严格的适用边界：如果c2的过滤条件不是等值（比如范围查询c2 > '1 minute'::INTERVAL），匹配到的条目就不再沿c3保持全局有序，这时候就无法用该索引同时完成过滤和c3排序，这也和常规认知里"ORDER BY列需要放在索引定义末尾"的规则完全对齐——该规则的适用前提就是索引前列使用了非等值过滤条件。

执行计划的Index Cond中只展示了c2的过滤条件，是输出的简化处理：扫描过程本身就是沿c3的有序方向遍历，c3的有序性直接用来满足排序需求，不需要作为过滤条件单独列出。搭配LIMIT 1000的限制，扫描时凑够1000条符合c2条件的结果就会立即终止扫描，不需要遍历全量匹配数据，因此执行成本极低。

内容的提问来源于stack exchange，提问作者Vitalii Vitrenko