Software Systems Atlas

中文

English

中文

English

主题

2.2 查询等价、逻辑改写与 SQL 语义边界 ​

优化器的任务不是“把语句变短”，而是在等价 logical plans 中寻找成本更低的 physical plan。等价的前提是：对允许的所有输入，两边结果在目标语义下相同。

Selection pushdown ​

原式：

text
σ Items.value_cents >= 50000 (Items ⋈ Items.type_id=Types.type_id Types)

predicate 只引用 Items，可下推：

text
(σ value_cents >= 50000 (Items))
⋈ Items.type_id=Types.type_id
Types

下推可能在 join 前减少 rows。但若 predicate 引用了两侧 attributes，就不能完整推到任何单侧；若是 outer join，还必须检查对 NULL-extended rows 的影响。

SQL 示例：

sql
SELECT i.name, t.code
FROM vault_items AS i
JOIN item_types AS t
  ON t.item_type_id = i.item_type_id
WHERE i.value_cents >= 50000;

数据库通常自行执行这类改写，应用开发者不必把它改写成 subquery 才能“强迫先过滤”。是否下推要看优化器和表达式属性。

Projection pushdown ​

join 后最终只需要 i.name 与 t.code，可以尽早丢弃无关 attributes，但必须保留 join key 和 predicate 使用的 columns：

text
π name, code
  (
    (π name, type_id Items)
    ⋈ type_id
    (π type_id, code Types)
  )

忘记保留 type_id 会让 join 无法计算。physical engine 也可能为了 index-only scan、tuple identity 或 late materialization 保留不同内部信息。

Inner join 的重排 ​

在 classical inner equijoin 条件下，join 具有 commutativity 和 associativity：

text
R ⋈ S = S ⋈ R
(R ⋈ S) ⋈ T = R ⋈ (S ⋈ T)

这让 optimizer 可以选择先 join 小表、高选择性结果，或利用现有排序/index。但 SQL 实际还涉及 duplicate、type coercion、collation 和 expression error；优化器只会采用目标系统认为合法的变换。

physical join order 与 SQL 文本顺序不同是正常现象。不要用书写顺序推测执行顺序，要看 plan。

Outer join 不能随意重排 ​

sql
SELECT a.name, q.quest_id
FROM adventurers AS a
LEFT JOIN quests AS q
  ON q.adventurer_id = a.adventurer_id
WHERE q.status = 'active';

WHERE predicate 会删除没有匹配 q 的 NULL-extended rows。若目标是保留没有 active quest 的 adventurer，应写：

sql
SELECT a.name, q.quest_id
FROM adventurers AS a
LEFT JOIN quests AS q
  ON q.adventurer_id = a.adventurer_id
 AND q.status = 'active';

这两个查询不等价。outer join 的 predicate pushdown、join reorder 和消除都需要 null-rejection 等额外证明。

Duplicate 会破坏某些 set 推理 ​

classical relation 没有 duplicate，而 SQL 默认保留。比如：

sql
SELECT adventurer_id
FROM quests;

一个人有三项 quest 就出现三次；加 DISTINCT 才变成 set-like result。UNION 与 UNION ALL、COUNT(*) 与 COUNT(DISTINCT ...) 也因此不同。

duplicate elimination 需要 hash/sort 等工作，不能为了“看起来干净”到处加 DISTINCT。若 join 意外放大结果，DISTINCT 可能掩盖错误 cardinality，而不是修复模型。

NULL 与 equivalence ​

SQL 三值逻辑下：

text
NOT (x = 1)

在 x IS NULL 时是 UNKNOWN，不等同于“x 是任意不为 1 的普通值”。NOT IN 与 nullable subquery 尤其危险：

sql
SELECT i.item_id
FROM vault_items AS i
WHERE i.item_id NOT IN (
    SELECT nullable_item_id
    FROM imports
);

若 subquery 包含 NULL，比较链可能使所有候选结果都不是 TRUE。表达 anti-join 时优先明确使用 NOT EXISTS，并在 schema 层尽量限制本不应 nullable 的 key。

Aggregation 不能穿过 join 而不看 cardinality ​

假设 quest 有多项 item：

sql
SELECT SUM(q.reward_cents)
FROM quests AS q
JOIN quest_items AS qi
  ON qi.quest_id = q.quest_id;

每个 reward 会按 item 数重复。若要总 quest reward，应先在 quest grain aggregation，或根本不 join quest_items。查询优化首先要明确 output grain，不是先猜 index。

sql
SELECT SUM(q.reward_cents)
FROM quests AS q
WHERE EXISTS (
    SELECT 1
    FROM quest_items AS qi
    WHERE qi.quest_id = q.quest_id
);

这个查询只统计至少含一项 item 的 quest，每项 quest 最多贡献一次。

Correlated subquery 与 decorrelation ​

sql
SELECT a.adventurer_id, a.name
FROM adventurers AS a
WHERE EXISTS (
    SELECT 1
    FROM quests AS q
    WHERE q.adventurer_id = a.adventurer_id
      AND q.status = 'active'
);

逻辑上 inner query 依赖当前 outer tuple。optimizer 可能把它 decorrelate 成 semijoin；也可能保留 parameterized lookup。不能仅凭“有 subquery”断言每行都会完整扫描一次。

EXPLAIN/EXPLAIN ANALYZE 与真实 cardinality 才能说明目标数据库采用了什么 plan。

Relational calculus 视角 ​

关系代数描述“用 operators 如何构造结果”，relational calculus 描述“结果 tuple 满足什么条件”。例如 active quest 的 adventurer：

text
{ a | Adventurers(a)
      ∧ ∃q (Quests(q)
            ∧ q.adventurer_id = a.adventurer_id
            ∧ q.status = 'active') }

calculus 是 declarative 视角的重要理论基础。安全/range-restricted expression 保证结果只从有限 database values 构成，避免产生无限 domain 上的结果。

从 logical 到 physical ​

同一个 logical join 可以对应：

  • nested-loop join；
  • index nested-loop join；
  • hash join；
  • merge join。

选择取决于 cardinality estimate、row width、memory、ordering、available indexes 和并行能力。估算偏差会导致错误 join order、hash table spill 或大量随机 lookup。

优化时记录：

text
logical requirement
actual row counts per operator
estimated row counts
scan/index access
join algorithm and order
sort/hash spill
buffer/cache and I/O
execution time across representative parameters

只看总时间无法区分计划不佳与 cache 冷热；只看 estimated cost 也不是实际运行证明。

安全改写清单 ​

在声称两个 SQL 等价之前，检查：

  • result 是 set 还是 bag；
  • NULL 是否存在，predicate 是否 null-rejecting；
  • inner、left、right、full join 类型；
  • key/foreign-key/uniqueness constraint 是否真的成立；
  • expression 是否 deterministic，是否可能抛错；
  • collation、type coercion、timezone 与 overflow；
  • aggregation grain 是否改变；
  • ORDER BY/LIMIT 是否参与语义；
  • concurrent data changes 与 isolation snapshot 是否一致。

练习 ​

  1. 把“active quest 中所有 weapon 名称”的 SQL 写成 algebra tree。
  2. 先将只引用 item_types.code 的 predicate 下推，再列出 projection 必须保留的 join columns。
  3. 构造一位没有 quest 的 adventurer，证明 WHERE 与 ON 中的 status predicate 结果不同。
  4. 构造 nullable subquery，观察 NOT IN 与 NOT EXISTS。
  5. 比较 JOIN + DISTINCT 与 EXISTS，解释语义和计划差异。

本章小结 ​

关系代数为查询改写提供了规则，但 SQL 的 duplicate、NULL、outer join 与实现类型系统会给规则增加前提。专业优化的顺序是先证明语义，再分析 cardinality，最后选择和验证 physical plan。

Built with VitePress | Software Systems Atlas

Copyright 2026 Steven Yang