# 从谓词、连接与排序推导索引

LLMS 索引： [llms.txt](/llms.txt)

---

索引设计的输入不是表结构，而是查询合同。面对一条 SQL，先把它改写成下面这张工作单：

```text
query family:
  predicates = column/expression + operator + representative value
  joins      = outer/inner side + join key + expected cardinality
  order      = exact key/direction/NULLS + LIMIT
  output     = returned columns and width
  workload   = parameter distribution + frequency + concurrency + SLO
  writes     = INSERT/UPDATE/DELETE columns and rate
```

然后才提出：

```text
access method (key columns [direction]) [INCLUDE payload]
[WHERE stable predicate]
```

这样做会自然排除“这个字段经常查，所以单独给它建索引”一类脱离操作符、组合方式和代价的建议。

## 9.2.1 等值、范围与多列顺序 {#item-9-2-1}

### B-tree 的有效搜索区间

对多列 B-tree `(a, b, c)`，传统且跨 PostgreSQL 14–18 都成立的基本推导是：

1. 从最左侧开始的等值条件不断缩小连续索引区间；
2. 第一个没有等值、但有不等式的列确定该区间的起止边界；
3. 更右侧条件仍可在索引内检查，却不一定进一步减少需要扫描的索引项；
4. 排序能否直接复用，还取决于等值前缀、列顺序、方向和 `NULLS` 规则。

例如：

```sql
WHERE tenant_id = $1
  AND state = 'open'
  AND created_at >= $2
  AND created_at <  $3
ORDER BY created_at DESC
LIMIT 50
```

一个自然候选是：

```sql
CREATE INDEX ticket_tenant_state_time_idx
ON ticket (tenant_id, state, created_at DESC);
```

两个 equality key 固定前缀，`created_at` 同时承担 range 与 ordering。若把 `created_at` 放到 `state` 前面，进入时间范围后，右侧的 `state` 通常只是过滤条件；它仍可能减少 heap visit，却不能像等值前缀那样缩短该时间范围本身。

这不是要求把所有等值列机械放在所有范围列之前。真正的问题是：

- 哪些条件总是一起出现，哪些只是某个 query family 才有；
- 哪个条件在 planning time 可见；
- 是否要支持某个 `ORDER BY ... LIMIT`；
- 同一个索引还要服务哪些前缀查询；
- 写入是否频繁改变这些列；
- 一个较短、可复用索引是否已足够。

### “最具选择性的列放最前”不是算法

设 `tenant_id=$1` 选出全表 1%，`state='open'` 选出 10%。对总是同时出现的两个等值条件，`(tenant_id, state)` 与 `(state, tenant_id)` 最终都能把搜索收敛到相同组合；不能只凭全局选择率宣布第一种必然更快。顺序更应考虑：

- 单独按 `tenant_id` 与单独按 `state` 的真实 workload；
- 后续 range/order 列如何衔接；
- distinct 数、数据倾斜和参数分布；
- 是否能省掉另一个索引；
- index tuple、prefix compression/dedup 与 write cost 的实测结果。

“选择率最高在前”最多是一条需要上下文的启发式，不是 PostgreSQL 多列索引的正确性规则。

### 从订单查询推导，而不是从订单表推导

本章订单 query family 是：

```sql
SELECT order_no, amount_minor, placed_at
FROM shop_private.ch09_order_probe
WHERE customer_id = 42
  AND order_status = 'placed'
ORDER BY placed_at DESC
LIMIT 20;
```

fixture 有 200000 行，`placed` 占 5%，目标客户恰有 10 行已下单记录。候选不是把所有 WHERE 列都当普通 key，而是：

```sql
CREATE INDEX CONCURRENTLY ch09_order_placed_cover_idx
ON shop_private.ch09_order_probe
    (customer_id, placed_at DESC)
INCLUDE (order_no, amount_minor)
WHERE order_status = 'placed';
```

推导逐项对应：

| 查询合同 | 索引设计 |
|---|---|
| `order_status` 是稳定 literal，且只关心少数 placed rows | partial predicate，不再把它重复存成 key |
| `customer_id = 42` | 第一个 search key |
| `ORDER BY placed_at DESC LIMIT 20` | 第二个 key，直接输出 Top-N 顺序 |
| 返回窄的 `order_no, amount_minor` | 候选 payload，是否保留还要验证 VM 与大小 |

这只是“有资格”的设计；9.3 会证明 generic parameter 可能无法使用这个 partial predicate，9.4–9.5 还要证明它值得让写入长期维护。

### PostgreSQL 18 的 B-tree skip scan：能力，不是默认设计借口

本章库存表已有主键：

```sql
PRIMARY KEY (warehouse_id, sku_id)
```

但查询是：

```sql
WHERE sku_id = 4242
```

在 PostgreSQL 14–17，不能把“后导列也在联合主键里”当成高效定位的通用保证；通常要么扫描大量索引项，要么选择其他路径。因此反向 query family 的自然候选是：

```sql
CREATE INDEX ch09_inventory_sku_cover_idx
ON shop_private.ch09_inventory_probe (sku_id, warehouse_id)
INCLUDE (available, reserved, updated_at);
```

PostgreSQL 18 引入 B-tree skip scan。若前导列 distinct 很少、后导列条件足够有用，planner 可以为若干可能的前导值重复发起 index search，跳过不可能匹配的大段索引。本章 30 个 warehouse、300000 行的 fixture 上，before plan 确实对 warehouse-first 主键使用了 skip scan；这是一条真实的 PG18 路径。

边界必须同时保留：

- skip scan 是 PostgreSQL 18 新能力，不能倒写成 14–17 的前提；
- 它由 cost model 选择，不保证每次出现；
- 前导 distinct 很大时，重复搜索可能不划算；
- 即使 before 已能 skip scan，专用 `(sku_id, warehouse_id)` 仍可能更直接、更小或更容易覆盖；
- 最终保留哪一个由读收益、索引大小和写成本决定，不由节点名决定。

因此章节验收不把“before 必须出现 Skip Scan”设为跨版本 golden，只要求 after 候选能正确支持 declared SKU lookup。

## 9.2.2 连接键、排序、分组与 Top-N {#item-9-2-2}

### 连接索引建在被反复探测的一侧

“JOIN 列要建索引”同样太粗。以下 nested loop 中，外侧每产生一个 `customer`，内侧就按 `order.customer_id` 探测：

```sql
SELECT c.customer_id, o.order_no
FROM customer AS c
JOIN orders AS o
  ON o.customer_id = c.customer_id
WHERE c.region = $1;
```

若外侧很小而内侧很大，`orders(customer_id)` 可能让每次探测便宜。若两侧都要读很大比例，planner 可能选择 hash join 或 merge join；此时新索引未必有价值。评审至少记录：

```text
outer rows × inner probes
join cardinality estimate vs actual
inner predicate/order/output
available uniqueness
hash/sort memory and spill
```

主键或 `UNIQUE` 约束会创建唯一索引，PostgreSQL **不会自动为外键的引用列创建索引**。外键索引的理由不是“约束要求”，而是两类真实动作：

- 从父表删除/更新 key 时，快速检查子表引用；
- 应用从子表按 parent key 查询或连接。

例如 `order_item(order_id)` 常常值得索引，但应由 delete/update parent 的风险和查询频率验证。不要重复创建一个已经由复合索引左前缀覆盖的 `order_id` 单列索引。

### 排序是一种可被索引提供的属性

B-tree 能按 key order 输出，planner 可在三种路径间权衡：

```text
index path already ordered
bitmap/seq path + explicit Sort
partially ordered path + Incremental Sort
```

对返回大部分表的查询，顺序 index scan 仍可能产生大量随机 heap access，`Seq Scan + Sort` 反而更便宜。对 Top-N，索引价值通常更高，因为它可能在找到前 N 行后停止：

```sql
SELECT order_no, placed_at
FROM orders
WHERE customer_id = $1
ORDER BY placed_at DESC
LIMIT 20;
```

候选 `(customer_id, placed_at DESC)` 能在固定 customer 前缀内直接取前 20 行。若没有 `ORDER BY`，`LIMIT 20` 只是任意 20 行，不能把偶然的索引输出顺序当业务语义。

方向需要按整组 key 判断：

```sql
CREATE INDEX mixed_order_idx
ON metric (tenant_id ASC, recorded_at DESC);
```

单列 B-tree 可正反扫描；多列索引整体反向会同时翻转各列，因此 `(tenant_id ASC, recorded_at ASC)` 的反向扫描不能提供 `tenant_id ASC, recorded_at DESC`。`NULLS FIRST/LAST` 也属于 order contract。只有查询要求的 order 与一种扫描方向吻合，才可省掉 Sort。

### 分组、去重与窗口不能只看关键字

有序输入可能帮助 `GroupAggregate`、`DISTINCT`、merge join、窗口函数或 incremental sort，但不保证 planner 一定利用索引：

```sql
SELECT tenant_id, count(*)
FROM event
WHERE occurred_at >= $1
GROUP BY tenant_id;
```

如果时间范围覆盖很多行，按 `(occurred_at, tenant_id)` 扫描再聚合未必比 Seq Scan + HashAggregate 好；若查询需要按 tenant 分组且只读少量 tenant，另一个 key order 才可能合适。为 `GROUP BY` 新建索引前，要比较：

- 过滤后实际行数；
- 现有输入是否已排序；
- hash aggregate 的内存与 spill；
- sort/incremental sort 的内存、磁盘与并行；
- 最终是否还有 order/limit；
- 这个 query 的频率是否能抵消写成本。

同样，窗口函数的 `PARTITION BY/ORDER BY` 是完整序列需求，不是见到某列就建单列索引。

## 9.2.3 选择率、相关性与访问路径 {#item-9-2-3}

### 选择率属于“谓词 + 值”，不只属于列

`state='failed'` 可能命中 0.01%，`state='success'` 可能命中 99%。同一 prepared query 的 hot/cold 参数可能对应完全不同的最佳路径。先看统计对 planner 描述了什么：

```sql
SELECT
    attname,
    null_frac,
    n_distinct,
    most_common_vals,
    most_common_freqs,
    histogram_bounds,
    correlation
FROM pg_stats
WHERE schemaname = 'shop_private'
  AND tablename = 'ch09_order_probe';
```

MCV 捕获常见值，histogram 描述其余分布，`n_distinct` 描述 distinct 规模；多列相关则需要第 7 章的 extended statistics 或更合适的数据模型。统计是抽样模型，不是精确计数，数据漂移后必须 `ANALYZE`，但也不能把无限提高 statistics target 当第一反应。

判断一个索引路径时，应同时看：

```text
estimated rows vs actual rows
rows removed by filter
loops
heap blocks touched and cache hits/reads
sort/spill
result rows and correctness
parameter bucket
```

若 cardinality 根本错了，节点选择往往只是后果。

### 物理相关性改变 heap 访问代价

`pg_stats.correlation` 近似描述列逻辑顺序与 heap 物理顺序的相关程度。高度相关的 range scan 往往按邻近 heap page 读取；随机分布的相同行数可能触碰更多 page。相关性不是永久属性：

- append 时间列通常天然相关；
- UPDATE、乱序导入和长期 churn 会改变布局；
- `CLUSTER` 可重写表，但不会自动持续维持物理顺序；
- BRIN 依赖 block range summary，相关性漂移会扩大 recheck；
- partitioning 能缩小关系范围，却不等同于每个分区内部有序。

所以不能把另一个环境的 `random_page_cost` 或 correlation 照搬为本环境真相。

### Index、Bitmap 与 Seq Scan 各有合理区间

可以用一个粗略模型理解三类路径：

| 路径 | 倾向的 workload | 主要风险 |
|---|---|---|
| plain Index Scan | 少量、高选择率；或必须保序/Top-N | 随机 heap page 多，低选择率时昂贵 |
| Bitmap Index + Heap Scan | 中等命中量；需合并多个 index | bitmap 可能 lossy，需要 recheck；丢失 index order |
| Seq Scan | 大比例、表小、顺序读便宜 | 扫描全部 page，不适合严格 point latency |

PostgreSQL 能用 `BitmapAnd`/`BitmapOr` 组合多个索引。这有时让两个短索引胜过一个专用复合索引，也可能因丢失 ordering 而需要 Sort。不能据此为每列各建一个索引：组合仍有 bitmap 建立、heap recheck、排序和所有单列索引的写成本。

`EXPLAIN` 的 cost 是在当前统计、参数、settings 与硬件成本假设下比较候选，不是毫秒。`enable_seqscan=off` 之类 GUC 可以做“是否存在某路径”的诊断，不得作为让 planner 听话的长期修复。正确闭环是：

1. 用代表参数捕获 before plan 与结果；
2. 提出能从 operator/order 证明的 candidate；
3. 在相同数据与统计下捕获 after；
4. 比较 read、write、size 与生命周期；
5. 即使 after 仍选 Seq Scan，也判断其是否符合真实成本；
6. 只有收益覆盖长期代价才保留。

本章实验正是这个闭环，而不是“让四条查询都出现 Index Scan”的演示。

## 延伸阅读

- [PostgreSQL 18：Multicolumn Indexes](https://www.postgresql.org/docs/18/indexes-multicolumn.html)
- [PostgreSQL 18：Indexes and `ORDER BY`](https://www.postgresql.org/docs/18/indexes-ordering.html)
- [PostgreSQL 18：Combining Multiple Indexes](https://www.postgresql.org/docs/18/indexes-bitmap-scans.html)
- [PostgreSQL 18：Planner Statistics](https://www.postgresql.org/docs/18/planner-stats.html)
- [PostgreSQL 18 Release Notes：B-tree skip scan](https://www.postgresql.org/docs/release/18.0/)

---

[上一节：索引方法与操作符类](../01/) · [返回本章目录](../) · [下一节：表达式、部分与覆盖索引](../03/) ·
[查看全书目录](/toc/) · [查看索引中心](/indexes/)