摘要

  • 1979 年的 System R 优化器比较的是“被搜索到的候选方案中的最低估算成本”。成本由预计页面读取与存储接口调用加权组成，既不是事先测得的耗时，也不证明它在所有可能的物理方案中全局最优。
  • 选择率影响基数，基数又改变访问路径、连接顺序与物理算子的价格。所谓“有趣顺序”说明，眼前较贵的路径如果保留了后续需要的排序，可能让整条计划更便宜。
  • Selinger 组织并领导了 Morton Astrahan、Donald Chamberlin、Raymond Lorie、Thomas Price 等人共同完成的架构。它最耐用的部分不是无误预测，而是把假设、选择与执行结果分开，使误差能够被检验和修正。

一条查询，两条都正确的路

设想一个订单分析查询：连接订单、客户与地区，筛选最近一个季度，按市场汇总，再取金额最高的十项。关系语义规定了哪些记录应该出现、怎样聚合。只要实现正确，用索引还是全表扫描、先连接客户还是先连接地区，都不应改变最后的答案。

物理代价却可能完全不同。一条路径利用窄索引先缩小数据，并且天然保留分组所需顺序；另一条路径先扫描大表，产生庞大的中间结果，最后再排序。两者在语义上等价，在生产环境中却可能相差几个数量级。

问题在于：当优化器必须选择时，这次运行尚未发生。缓存里究竟有哪些页面，并发任务会不会抢走内存，某个参数会命中多少行，中间结果是否溢写磁盘——这些现实尚未全部出现。优化器能使用的只是目录统计、选择率假设、算子公式、硬件权重，以及它有时间搜索到的候选集合。

因此，“最便宜”首先是模型内部的比较结论。真正运行以后，实际行数、I/O、CPU、内存与耗时才会出现。把前者说成后者，便把一份预测伪装成了事实。

声明式 SQL 转移了控制权

SQL 的关键承诺是非过程化。用户说明想要什么，不必写出页面怎样读、索引怎样走、连接怎样排。这样做让同一条查询能够随数据规模、索引与硬件变化而重新规划，也把极重要的物理决定交给了数据库。

1979 年论文《Access Path Selection in a Relational Database Management System》把过程分成四个阶段：解析、优化、代码生成与执行。优化阶段产生访问规范，代码生成把它变成可以运行的程序，最后才执行。顺序本身就是边界：优化器在运行证据到来之前承诺一条物理路线。

访问规范不只是查询语义的另一种写法。它记录先访问哪张表、使用段扫描还是索引、连接以什么顺序发生、哪些结果顺序值得保存。语义正确性回答“结果是不是对的”；物理计划回答“机器怎样取得这个结果”。一条计划可以正确但很慢，两条计划可以同样正确却消耗完全不同。

这也解释了为什么一次成功的运行不能证明计划普遍最优。缓存状态改变、参数改变、数据分布改变、并发改变，同一个物理方法的表现就可能改变。正确性相对稳定，经济性则依赖环境。

目录统计是现实的压缩图

System R 不会为了决定怎样读表而先读遍整张表。它使用系统目录中的统计值。论文列出 NCARD（关系中的元组数）、TCARD（占用页面数）、P（页面占用相关量）、ICARD（索引不同键值数）与 NINDX（索引页面数）等指标。

这些数字把庞大的数据压缩成一个可用于计划的描述。它们也必然舍弃细节。统计通过 UPDATE STATISTICS 初始化和周期更新；论文明确解释，不能在每次数据修改后都同步维护，因为目录更新与锁会带来不可接受的成本。

“统计会旧”并非后来系统才遇到的偶然缺陷，而是观察成本的一部分。若维护一份随时完美的现实副本，取得信息本身可能比计划查询更昂贵；若采样过少或更新太慢，排序候选方案时又会依据错误图景。优化器一直在为观察的精度与价格作交换。

今天谈统计维护时，容易把问题简化为“有没有定期分析”。真正的问题还包括采样比例、直方图粒度、相关性信息、分区差异，以及采集时刻与查询时刻之间发生了什么。优化器从未面对完整的未来数据，它面对的是经制度选择后留下的摘要。

选择率是判断，基数是它扩散后的结果

System R 为谓词分配选择率因子，即预计有多大比例的元组满足条件。带索引的等值条件可以利用不同键值数量；缺少信息时则使用经验默认值。论文给出的例子包括：无索引等值条件取十分之一，单边范围取三分之一，闭合范围取四分之一。作者随即强调，这些数值没有更深意义，只用于大致排序。

这句话非常重要。默认值不是数据库世界的自然常数，而是在证据不足时仍然必须作出选择的工程假设。

多个 AND 条件可以把选择率相乘。这很方便，却隐含独立性：仿佛城市与邮编、产品线与价格、账户类型与余额彼此无关。现实数据常常高度相关。一项条件单独看并不稀有，与另一项共同出现时却可能极少；也可能相反。把相关条件按独立事件相乘，小误差会被迅速放大。

基数指一个关系、连接或中间算子输出多少行。System R 的 QCARD 推算把基础关系基数与适用的选择率结合起来。后续成本公式再以这个行数预测为输入。若低估连接的外层行数，嵌套循环会显得便宜；真正执行时，每一行都触发重复工作，代价骤增。若高估一个过滤器，优化器可能放弃实际只需触碰很少记录的索引路径。

选择率与基数不能混用。前者是比例性的判断，后者是输入规模与该判断共同产生的数量。早期节点的一次误判还会改变后面的连接顺序、算子、内存预算与排序方式，因此影响不是局部相加，而会沿计划传播。

2015 年 Leis 等人对现实优化器的评估指出，与成本公式的小幅不准相比，基数估计错误通常更能破坏计划质量；他们在 2025 年的回顾中仍把基数误差、稳健性与自适应列为未完成问题。这不是对 1979 年架构的否定，恰恰说明它暴露出的决策链今天仍在运转。

成本是排序货币，不是秒表

System R 发表的成本表达式十分简洁：

COST = PAGE FETCHES + W × (RSI CALLS)

页面读取代表 I/O，Research Storage Interface 调用近似 CPU 工作，W 是两者的相对权重。把处理器成本写进模型，是相对于只看磁盘读取的重要进步。但相加后的数字仍然只是计划阶段使用的统一货币。

它能说明在这套权重下，候选 A 比候选 B 便宜，却不能自动换算成真实毫秒数。需要的页面是否已经在缓冲区，读取是否连续，系统是否拥塞，中间结果会不会溢写，处理器与存储的相对速度怎样，客户端最终读取多少输出——这些因素要么被简化，要么在计划时不可知。

因此可以严谨地说“模型给 A 更低成本”，也可以把“A 可能更快”当作待验证假设；直接说“A 已经被证明最快”，则跨越了证据边界。至于“最优”，还必须追问：针对哪个目标函数？在什么候选集合内？

PostgreSQL 当前文档仍清楚保留这一区分。计划成本是与平台相关的约定单位，并非毫秒。普通 EXPLAIN 不执行语句，只显示估算；EXPLAIN ANALYZE 真正运行，并报告实际行数与时间。前者是预测记录，后者才把现实带回决策系统。

访问路径、物理算子与连接顺序不是一件事

“选计划”常被说成一个动作，实际上包含若干相互作用的决定。访问路径决定怎样触达基础关系，例如段扫描或可用索引。物理算子决定连接、排序或聚合怎样完成。连接顺序决定哪些关系先组合，也决定中间结果的大小与物理属性。

一个索引既可能减少读取，也可能提供有用顺序。一个高选择性的早期连接能够缩小所有后续输入。适合小外表的连接方法，在基数被低估时会变成灾难。一次为当前步骤付出的排序，又可能省掉后面的排序。

关系等价规则允许优化器在不改变含义的前提下重排表达式，但空值、重复、聚合等语义仍需被正确保持。若答案错了，是正确性问题；若答案对却迟到，是估算、计划或执行问题。把两者混在一起，既无法解释故障，也无法决定修复对象。

“有趣顺序”为什么值得多留一个候选

论文中最有生命力的概念之一是“有趣顺序”。假设索引路径在眼前比扫描昂贵，但它输出的数据已经按连接键、分组键或最终 ORDER BY 排列。这个顺序可能免掉后续排序，或者使下一次连接更便宜。若只保存局部最低成本方案，整个查询反而会更贵。

System R 因而为同一关系子集保留多个代表：最便宜的无序方案，以及每个相关有趣顺序下最便宜的方案。输出行集合相同、并携带相同有用顺序的局部计划，才可以放进同一个比较类别。

这不是成本优化的例外，而是成本能跨阶段成立的条件。中间结果的物理属性具有期权价值：现在多付一点，未来可能少做很多。两条计划在逻辑输出上等价，并不意味着它们能以相同代价被下游替换。

有趣顺序也揭示“最低成本”不是逐节点贪心。优化器要比较总后果，就必须让一些当前较贵但保留未来选择的路径继续存活。

连接顺序让“搜索”本身也有成本

关系一多，连接顺序数量会组合爆炸。直接枚举所有排列接近阶乘增长。若为了节省执行时间而让优化阶段耗尽时间与内存，优化器就失去了意义。

System R 采用动态规划。它先为关系子集建立局部计划，按子集与有趣顺序保存最佳代表，再复用这些结果扩展更大连接。另一个启发式规则尽量推迟笛卡尔积，因为没有连接条件的早期组合通常制造巨大中间结果。

论文把搜索规模约束在关系子集与有趣顺序的组合范围，并报告 IBM 370/158 上八表连接可在数秒内完成优化。这是非常出色的工程成果，也说明搜索空间经过了明确定义。哪些连接树、算子和属性能成为候选，哪些局部方案被剪掉，都由实现决定。

剪枝不等于随意猜测。它是在可承受的表示中求解一个确定问题。但动态规划也不能证明自己覆盖了设计者可能想象的一切物理方案。它找到的是既定枚举器、成本模型与剪枝规则之内的赢家。

规划时间与执行时间因此必须同时计算，又不能混为一谈。扩大搜索也许找到更好方案，却延迟每次编译；缩小搜索很快，却可能错过更稳健的路径。预编译语句还带来通用计划与参数敏感计划的取舍：复用通用计划节省规划时间，但当理想路径强烈依赖参数时，执行成本会转移到尾部。

作者没有掩饰误差

1979 年论文的结论坦率地说，预测成本作为绝对值往往并不准确；与此同时，模型在多数测试中选中了真实表现最好的访问路径，并且仍需进一步验证。这两点并不矛盾。一个没有校准到真实秒数的分数，仍可能正确排序大部分候选。

1986 年 Mackert 与 Lohman 对 R* 优化器的验证把估算资源与实际消耗并列。很多 I/O 模型有效，但 CPU 细节需要补充，缓冲区假设会改变结果，嵌套循环又同时受到连接基数、外层基数与可用页面影响。估算与现实之间的差距由此成为可以测量的工程对象。

这项验证的制度意义很大。成本模型不会因为有公式就免于审查。若误差集中在一类连接或一组参数上，团队可以改进统计、公式、算子假设或反馈机制。预测的价值来自可证伪，而不是数学外观。

IBM 后来提出即时统计，也是同一思路：当独立采集的统计缺失或过时，优化器可以在规划时针对关键疑问购买更好的观察。目标不是消灭所有不确定性，而是在信息价值超过采集成本的地方更新证据。

Selinger 的贡献属于一支团队

Patricia G. Selinger 于 1975 年加入 IBM Research。IBM 历史资料记录她领导 System R 优化器工作，后来参与领导分布式数据库 R* 与更广泛的数据库技术组织；她在 1994 年成为 IBM Fellow，1999 年当选美国国家工程院院士，2018 年从 IBM 退休。

但 1979 年成果不能写成孤胆发明。论文由 P. Griffiths Selinger 领衔，并与 Morton M. Astrahan 共同署名；其他作者还有 Donald D. Chamberlin、Raymond A. Lorie，以及 Thomas G. Price。Chamberlin 在计算机历史博物馆口述史中回忆，Selinger 组织了优化工作与这篇突破性论文，同时明确指出 Lorie、Price、Astrahan 都有重要贡献。IBM 对关系数据库的回顾还把它放在 Edgar Codd 的关系模型、Chamberlin 与 Raymond Boyce 的 SQL、Lorie 的编译器以及整个 System R 计划中理解。

领导力在这里不是独自完成每一项发明，而是把问题组织成可实现的合同：统计提供输入，选择率与基数传递判断，成本函数给候选统一标尺，有趣顺序保存未来价值，动态规划限制搜索。团队让声明式语言不只优雅，而且能够经济地运行。

把这项工作称作“人工智能”反而会抹去具体机制。论文讨论的是显式统计、规则、公式与动态规划。它的历史意义不需要借用后来的流行标签。

真正耐用的是一条诚实边界

成本优化最重要的成果，并不是找到永远正确的唯一道路，而是把“查询含义”与“物理方法”分开，让不同路线可以在一个明确控制层中比较。统计可以更新，基数估计可以学习相关性，权重可以适应硬件，枚举器可以接受新算子，执行反馈可以触发重规划；用户仍然保留原来的声明式查询。

这种可变性只有在边界清楚时才安全。被选中的计划是一项获得授权的预测：它赢得了当前实现的比较，因此被允许执行；它并未提前获得现实的背书。执行后出现的实际行数、I/O、CPU、内存与时间，必须作为另一份记录保存。

成熟的优化系统不要求预测永不出错。它要求知道预测依据什么、错在何处、何时应该买来新证据，以及怎样在不改变查询含义的情况下修正路线。Selinger 与团队留下的正是这种能够承认不确定性、又不因不确定而停止决策的架构。

来源