杰弗里·乌尔曼的数据库理论：驱动快速、可扩展查询的原理

为什么 Ullman 对现代数据工作至关重要

几乎所有写 SQL、构建仪表盘或调优慢查询的人都或多或少受益于杰弗里·乌尔曼的工作——即便他们从未听过他的名字。Ullman 是位计算机科学家和教育家，他的研究与教材帮助定义了数据库如何描述数据、如何推理查询，以及如何高效执行查询。

日常工具背后的低调影响

当数据库引擎把你的 SQL 转成能快速执行的东西时，它依赖的思想必须既精确又可适应。Ullman 帮助形式化了查询的含义（这样系统就能安全地改写它们），并把数据库思维与编译器思维连接起来（因此查询可以被解析、优化并翻译为可执行步骤）。

这种影响很低调，因为它不会以按钮出现在你的 BI 工具里，也不会是云控制台上的可见功能。它表现为：

• 在你添加索引或重写 JOIN 后查询变快
• 优化器会随着数据增长选择不同的计划
• 系统在不改变查询结果的前提下完成扩展

你将从本文学到什么（不搞繁琐数学证明）

本文以 Ullman 的核心思想为导览，讲述在实际工作中最重要的数据库内部机制：关系代数如何支撑 SQL、查询改写如何保持含义、基于代价的优化器为何做出那些选择，以及连接算法如何决定作业是几秒完成还是几小时卡住。

我们还会借用一些类似编译器的概念——解析、改写与规划——因为数据库引擎比很多人想象的更像复杂的编译器。

一个快速承诺：讨论保持准确，但避免大量数学证明。目标是给你能在下次遇到性能、扩展或令人困惑的查询行为时直接应用的思维模型。

Ullman 奠定的数据库基础知识

如果你曾写过 SQL 并期望它“只意味着一件事”，那么你依赖的是杰弗里·乌尔曼帮助普及和形式化的那些思想：一个清晰的数据模型，加上一套精确描述查询所求的方式。

用通俗语言理解关系模型

关系模型把数据视为表（关系）。每张表有行（元组）和列（属性）。这现在看起来很显而易见，但重要的是它带来的规范：

• 键用于标识行。主键是每条记录的“名牌”。
• 关系通过外键连接表，这样事实可以存放在一个地方并在别处引用。

这种表述让我们可以在不靠主观判断的前提下推理正确性与性能。当你知道一张表代表什么以及如何标识行时，就能预测连接该做什么、重复项意味着什么，以及为什么某些过滤会改变结果。

关系代数：查询的计算器

Ullman 的教学常用关系代数作为一种查询计算器：一小套操作（select、project、join、union、difference），可以组合来表达你想要的结果。

它对日常 SQL 的意义：数据库会把 SQL 翻译成代数形式，然后改写成等价的另一种形式。两条看起来不同的查询在代数上可能是相同的——这就是优化器能重新排序连接、下推过滤或删除冗余工作的方式，同时保持语义不变。

代数 vs. 演算（高层次）

• 关系代数更偏“怎么做”：计算结果的一系列操作。
• 关系演算更偏“要什么”：描述你想要的结果。

SQL 在很大程度上是“要什么”，但引擎通常用代数式的“怎么做”来优化。

基础优先于记忆方言

SQL 方言不同（Postgres vs. Snowflake vs. MySQL），但基本原理不会变。理解键、关系与代数等价可以帮助你判断查询是逻辑错误、只是慢，还是哪些改动能在不同平台间保持含义。

关系代数：SQL 底下的隐藏语言

关系代数是 SQL 的“数学底层”：一小套运算符用来描述你想要的结果。杰弗里·乌尔曼的工作让这种运算符视角变得清晰且易于教学——它仍然是大多数优化器的思维模型。

核心运算符（及其含义）

一个数据库查询可以表示为几种构建块的流水线：

• Select (σ)：过滤行（SQL 中的 WHERE）
• Project (π)：保留特定列（SQL 中的 SELECT col1, col2）
• Join (⋈)：基于条件组合表（JOIN ... ON ...）
• Union (∪)：合并形状相同的结果（UNION）
• Difference (−)：A 中但不在 B 中的行（许多 SQL 方言中的 EXCEPT）

由于集合很小，推理正确性变得更容易：如果两个代数表达式是等价的，那么在任何有效的数据库状态下它们返回相同的表。

SQL 如何映射到代数（概念上）

看一个熟悉的查询：

SELECT c.name
FROM customers c
JOIN orders o ON o.customer_id = c.id
WHERE o.total > 100;

概念上，这可以表示为：

1. 先对 customers 和 orders 做 join：customers ⋈ orders

2. 对 orders 做过滤 o.total > 100：σ(o.total > 100)(...)

3. 投影你想要的列：π(c.name)(...)

这不是每个引擎内部使用的精确符号，但思路是：SQL 被转成一个运算符树。

等价性：通向优化的大门

许多不同的树可以表示相同的结果。例如，过滤器通常可以早些应用（在大连接前应用 σ），投影通常可以尽早丢弃未使用的列（尽早应用 π）。

这些等价规则使数据库在不改变含义的前提下改写查询以获得更低成本成为可能。一旦把查询看成代数，"优化" 就不再是魔术，而是基于规则的重塑。

从 SQL 到查询计划：保持含义的改写

当你写 SQL 时，数据库并不会“按你写的方式”执行它。它会把语句翻译成一个查询计划：描述要做的工作的结构化表示。

一个好的心理模型是一个运算符树。叶子节点读取表或索引；内部节点转换并组合行。常见运算包括 scan、filter（选择）、project（投影）、join、group/aggregate 和 sort。

逻辑计划 vs. 物理计划（要做什么 vs. 怎么做）

数据库通常把规划分成两层：

• 逻辑计划：用抽象运算（过滤、连接、聚合）表达要计算的结果——是“做什么”。
• 物理计划：选择如何在真实存储与硬件上执行（索引扫描 vs 全表扫描、哈希连接 vs 嵌套循环连接、并行或单线程）。

Ullman 的影响体现在对保持含义的变换的强调：可以在不改变答案的前提下重排逻辑计划多种方式，然后选择高效的物理策略。

减少工作量的规则式改写

在选择最终执行方式之前，优化器会应用代数式的“清理”规则。这些改写不会改变结果；它们旨在减少不必要的工作。

常见例子：

• 下推选择（Selection pushdown）：尽早应用过滤，这样后续步骤处理的行更少。
• 投影裁剪（Projection pruning）：只保留需要的列，减少 I/O 与内存占用。
• 连接重排（Join reordering）：优先连接更小/更具选择性的子结果（在安全的前提下），而不是按 SQL 的书写顺序进行。

一个简单的改写示例

假设你要查询一个国家的订单：

SELECT o.order_id, o.total
FROM users u
JOIN orders o ON o.user_id = u.id
WHERE u.country = 'CA';

一种天真的做法可能会把所有用户与所有订单先连接，然后再过滤出加拿大的用户。保持含义的改写会把过滤下推，从而使连接涉及的行更少：

• 先把 users 过滤为 country = 'CA'
• 然后把这些用户与 orders 做连接
• 最后投影 order_id 和 total

在计划术语中，优化器尝试把：

Join(Users, Orders) → Filter(country='CA') → Project(order_id,total)

变成更接近：

Filter(country='CA') on Users → Join(with Orders) → Project(order_id,total)

答案相同，但工作量更小。

这些改写之所以容易被忽视，是因为你从未手动输入它们——但它们是同一条 SQL 在一个数据库上快、在另一个上慢的主要原因。

用不晦涩的语言理解基于代价的优化

当你运行 SQL 时，数据库会考虑多种能返回相同结果的方式，然后选择它预计代价最低的一种。这个决策过程就是基于代价的优化——也是 Ullman 风格理论在日常性能中最直接的体现之一。

什么是“代价模型”

代价模型是优化器用来比较不同计划的评分系统。大多数引擎用几个核心资源来估计代价：

• 处理的行数（工作量通常与数据流量成正比）
• I/O（从磁盘或 SSD 读取页面，以及缓存命中）
• CPU（过滤、哈希、排序、聚合的消耗）
• 内存（操作是否能驻留内存或需溢写到磁盘）

模型不需要完美；需要的是在大多数情况下能方向性地选出较好的计划。

基数估计，通俗解释

在对计划评分前，优化器会在每一步问自己：**这一步会产出多少行？**这就是基数估计。

如果你过滤 WHERE country = 'CA'，引擎会估计表中有多少比例符合条件。如果你把客户与订单连接，它会估计有多少对匹配这些键。这些行数的猜测决定了是选择索引扫描还是全表扫描、哈希连接还是嵌套循环、排序会是小规模还是巨大规模。

统计的重要性（以及统计缺失会带来什么问题）

优化器的猜测依赖于统计信息：计数、值分布、空值率，有时还有列之间的相关性。

当统计过时或缺失时，引擎可能把行数估计错几个数量级。一条在纸面上看起来便宜的计划可能在实际中代价巨大——典型症状包括数据增长后突发的慢查询、计划的“随机”变化或连接意外地溢写到磁盘。

无法避免的取舍：准确性 vs 规划时间

更好的估计通常需要更多工作：更细致的统计、采样或探索更多候选计划。但规划本身也有时间成本，特别是对复杂查询而言。

因此，优化器要在两者间平衡：

• 规划速度要足够快（满足交互式工作负载）
• 规划要足够聪明（避免灾难性的选择）

理解这一权衡能帮助你读懂 EXPLAIN 输出：优化器不是试图搞花样，而是在有限信息下追求“可预测的正确”。

连接算法与查询性能的核心

Ullman 的工作推广了一个简单但强大的观点：SQL 并不是被“执行”，而是被翻译成执行计划。连接处尤为明显：两条返回相同行的查询，根据引擎选择的连接算法和连接顺序，其运行时可以天壤之别。

嵌套循环、哈希连接、合并连接——各自适用场景

嵌套循环连接简单直接：对左侧每一行，在右侧找匹配行。当左侧小且右侧有可用索引时可以很快。

哈希连接从一个输入（通常较小的一侧）构建哈希表，再用另一个输入进行探测。它在大型、未排序的等值连接上表现出色，但需要内存；一旦溢写到磁盘，优势会被抹去。

合并连接在两个输入按排序顺序遍历时工作良好。当双方已经按连接键排序（或者索引可以按键顺序返回行）时，合并连接通常很合适。

为什么连接顺序能主导性能

当涉及三表或更多表时，可能的连接顺序数量呈指数增长。先连接两张大表可能产生巨大的中间结果，使后续所有操作变慢。更好的顺序通常从最具选择性的过滤开始，向外扩展，保持中间结果尽可能小。

索引如何改变可行方案的菜单

索引不仅加速查找——它们还使得某些连接策略可行。连接键上的索引可以把昂贵的嵌套循环变成每行快速寻址的模式。反之，缺失或不可用的索引可能迫使引擎选择哈希连接或为了合并连接进行大量排序。

实用检查清单：糟糕连接计划的症状

• 随着数据略微增长，运行时间急剧上升（连接顺序放大了中间结果）。
• 计划显示巨大的“估计行数 vs 实际行数”差异（基数估计错误导致选择错误的连接策略）。
• 出现大量排序或哈希溢写到磁盘（内存压力或缺少支持索引）。
• 一个被大量过滤的小表反而被晚连接（过滤没有被尽早应用）。
• 连接谓词不是兼容类型上的简单等值（阻碍高效的哈希/合并行为）。

数据库引擎中的编译器思想

数据库不仅仅是“运行 SQL”。它们在很多方面是在编译 SQL。Ullman 的影响既跨越数据库理论又跨越编译器思维，这种联系解释了为什么查询引擎像编程语言工具链一样：在做任何真正工作之前先翻译、改写与优化。

解析与语法树：SQL 是如何被读取的

当你发送查询时，第一步看起来就像编译器的前端。引擎会把关键字和标识符分词、检查语法并构建一个解析树（通常简化为抽象语法树）。这是捕获基本错误的地方：缺逗号、列名二义性、分组规则无效等。

一个有用的心理模型：SQL 是一种编程语言，它的“程序”恰好是用来描述数据关系，而不是循环或条件分支。

从解析树到逻辑运算符

编译器会把语法转换为中间表示（IR）。数据库也类似：它把 SQL 语法翻译为逻辑运算符，比如：

• Selection（过滤行）
• Projection（选择列）
• Join（组合表）
• Aggregation（GROUP BY）

这个逻辑形式更接近关系代数而不是 SQL 文本，从而更容易推理语义与等价性。

为什么优化器像编译器优化

编译器优化在保持程序结果不变的前提下让执行更便宜。数据库优化器做同样的事情，使用类似的规则系统：

• 提前下推过滤（尽早减少工作量）
• 重排连接顺序（结果相同但代价不同）
• 消除冗余计算

这就是数据库版的“死代码消除”：技术不同，但哲学相同——保持语义，降低代价。

调试：像看汇编一样读计划

如果查询慢了，不要只盯着 SQL 文本。把查询计划当作编译器输出去看。计划告诉你引擎实际选择了什么：连接顺序、索引使用以及时间消耗的具体环节。

实用结论：学会读 EXPLAIN 输出，把它当作性能的“汇编清单”。这会把调优从猜测变成基于证据的调试。想把这变成习惯？参见 /blog/practical-query-optimization-habits。

会影响真实性能的模式设计理论

良好的查询性能通常始于写 SQL 之前。Ullman 的模式设计理论（尤其是范式化）是关于如何构造数据，使数据库在增长时保持正确、可预测且高效。

范式化的目标（它存在的理由）

范式化旨在：

• 减少异常（例如在五处更新客户地址却漏掉一处）
• 通过把每个事实放在唯一位置来提高一致性
• 使约束可表达（键、外键），让引擎而不是应用代码来强制规则

这些正确性收益会转化为性能收益：更少的重复字段、更小的索引和更少昂贵的更新操作。

用通俗语言理解范式

你不需要记住证明才能使用这些思想：

• 1NF：在原子列中存储值（不要用逗号分隔的列表）。这使过滤和索引更简单。
• 2NF：在复合键表中，每个非键列应依赖于整个键而不是键的一部分，避免属性重复。
• 3NF：非键列应该只依赖于键，而不是其他非键列，防止隐藏的重复。
• BCNF：比 3NF 更严格，当“几乎唯一”的列引发微妙的重复时非常有用。

何时反范式化是合理的

当你：

• 构建以分析为主的表（宽事实表、报表）
• 连接成为瓶颈且可以接受受控冗余
• 优化读取速度并有明确的刷新规则（例如夜间重建）

关键是有意识地反范式化，并有保持重复同步的流程。

模式选择如何影响优化器与扩展

模式设计决定了优化器能做什么。清晰的键与外键使更好的连接策略、更安全的改写和更准确的基数估计成为可能。相反，过度冗余会膨胀索引并放慢写入，多值列阻碍高效谓词。随着数据量增长，这些早期建模决策往往比微调单条查询更加重要。

理论在系统扩展时如何显现

当系统“扩展”时，问题通常不仅仅是加更大的机器。更常见的难点是：必须在保持查询含义不变的前提下，让引擎选择完全不同的物理策略来保持运行时间可控。Ullman 强调形式等价性的思想正是让这些策略变化在不改变结果的情况下成为可能的基础。

扩展往往是物理布局 + 计划选择

在小规模时，许多计划都“能工作”。到了规模化时，扫描一张表、使用索引或使用预计算结果之间的差别可能意味着秒级与小时级的差距。理论方面重要的是：优化器需要一套安全的改写规则（比如把过滤下推、重排连接），这些规则不会改变答案，即便它们极大地改变了实际执行的工作。

分区会改变运行的查询，即便 SQL 没变

按日期、客户、地区等做分区，会把一个逻辑表变成许多物理片段。这影响规划：

• 哪些分区可以被跳过（分区裁剪）
• 连接是否可以在分区内完成或需要跨节点洗牌
• 是否可以在本地先做聚合再合并结果

SQL 文本不变，但最佳计划取决于行所在的位置。

物化视图：把代数子表达式预先计算

物化视图本质上是“保存的子表达式”。如果引擎能证明你的查询与某个已存结果相匹配（或能改写成匹配），它就能把昂贵的工作（重复的连接与聚合）替换为一次快速查找。这正是关系代数思想的实际应用：识别等价并重用结果。

缓存有用，但不能修形状不对的工作

缓存能加速重复读取，但不能拯救必须扫描过多数据、洗牌巨大中间结果或计算巨大连接的查询。遇到扩展问题时，常见的修复是：减少涉及的数据量（布局/分区）、减少重复计算（物化视图），或改变计划——而不是简单地“加缓存”。

受 Ullman 启发的实用调优习惯

Ullman 的影响体现为一种简单心态：把慢查询看作数据库的一条意图声明，数据库可以对它做改写，然后验证它实际上做了什么。你不需要成为理论家就能受益——只需要一个可重复的流程。

1) 读 EXPLAIN 计划：先看什么

从通常主导运行时间的部分入手：

• 访问方式：引擎是在扫描整张表，还是按你预期做了索引查找？
• 估计行数 vs 实际行数（如果数据库显示两者）：大差距通常解释“神秘”慢查询。
• 连接顺序：哪个表驱动连接？它是否从最具选择性的过滤开始？
• 昂贵操作：排序、哈希构建、大规模嵌套循环——这些通常暴露了耗时的根源。

如果只能做一件事，定位行数首次暴增的操作节点。那通常就是根因。

2) 击败优化器的常见反模式

这些写法既容易出现又代价惊人：

• 对有索引列应用函数：WHERE LOWER(email) = ... 可能阻止索引使用（如果支持，可用函数索引或保持标准化列）。
• 缺失谓词：忘记加时间范围或租户过滤，会把针对性的查询变成宽扫描。
• 意外的笛卡尔积：缺少连接条件会使行数成倍增长，产生巨大中间结果。

3) 用代数思维形成假设

关系代数鼓励两个实际动作：

• 尽早下推过滤：在连接前尽可能应用 WHERE 来缩小输入。
• 尽早减少列：在连接前只保留需要的列，降低内存与 I/O。

一个好的假设可以是：“这个连接很贵，因为我们连接了太多行；如果先把 orders 过滤到最近 30 天，连接输入会大幅下降。”

4) 索引、重写还是模式变更？

用一个简单决策规则：

• 添加索引：当查询正确、有选择性且被频繁执行时。
• 重写查询：当 EXPLAIN 显示可避免的工作（不必要的连接、晚过滤、不可被索引利用的谓词）。
• 改变模式：当工作负载稳定且你反复在同一瓶颈上挣扎时（例如预计算聚合、反范式化的查找字段或按时间/租户分区）。

目标不是“写聪明的 SQL”，而是让中间结果可预测且更小——正是 Ullman 的等价性思想最容易帮助识别的改进。

在真实产品中应用这些思想

这些概念不仅对数据库管理员有用。如果你在交付应用，你在无形中做出数据库与查询规划决策：模式形状、键的选择、查询模式与数据访问层都会影响优化器能做什么。

例如，如果你使用一种快速原型工作流（比如从聊天界面生成 React + Go + PostgreSQL 应用的 Koder.ai），Ullman 风格的思维模型是一个实用的安全网：你可以审查生成的模式是否有干净的键与关系，检查应用依赖的查询，并在上线前用 EXPLAIN 验证性能。你能更快地在“查询意图 → 计划 → 修复”之间迭代，就能从加速开发中获得更多价值。

在工作中如何进一步学习与应用

你不需要把“理论”当做一个单独的爱好来研究。受益 Ullman 基础知识的最快方法是学到足以自信阅读查询计划的程度——然后在自己的数据库上练习。

适合入门的资源

搜索这些书籍与讲座主题（无任何关联，仅为常见起点）：

• “A First Course in Database Systems” (Ullman & Widom) — 亲和的数据库基础与实用框架。
• “Principles of Database and Knowledge-Base Systems” (Ullman) — 想深入可读这本更偏理论的书。
• “Compilers: Principles, Techniques, and Tools” (Aho, Lam, Sethi, Ullman) — 理解“为什么优化器像编译器”这一联系。
• 讲座/搜索主题：关系代数、查询改写、连接排序、基于代价的优化、索引与选择性、解析与查询语言。

轻量学习路径

从小处做起并把每一步与可观测的事物挂钩：

1. 关系代数：学会选择、投影、连接与等价规则。
2. 计划：学会阅读计划节点（扫描类型、过滤、连接、排序、聚合）。
3. 连接：理解嵌套循环、哈希连接与合并连接及其适用场景。
4. 代价模型：学会驱动决策的少数输入（行数、选择性、I/O vs CPU）。

能快速产生成果的小练习

选 2–3 条真实查询并反复迭代：

• 重写：把 IN 改为 EXISTS、提前下推谓词、删除不必要列，比较结果。
• 比较计划：记录“前/后”计划并注意变化（连接顺序、连接类型、扫描类型）。
• 改变索引：一次添加/移除一个索引，观察估计与实际行数的变化。

向团队传达发现的方法

用清晰、基于计划的语言：

• “计划从顺序扫描切到索引扫描，因为过滤变得更具选择性。”
• “估计行数偏差 100×，导致优化器选错了连接顺序。”
• “这个重写是等价的（结果相同），但启用了谓词下推，从而减少了进入连接的行数。”

这就是 Ullman 基础的实际回报：你获得了一套共享的词汇来解释性能，而不是靠猜测。