前置知识

相关文章

仓库 · 242 字 · 1 分钟阅读

JOIN:通过值、而非指针来表达关系

用共享的值而不是物理引用来表达关系,是关系模型真正的突破。五十年后,四种连接类型、三种连接算法,和一个根本问题,仍在驱动世界上大多数的数据。

目录
  1. TL;DR
  2. JOIN 之前:指针导航
  3. 关系式的替代方案
  4. 四种连接类型
    1. INNER JOIN
    2. LEFT OUTER JOIN
    3. RIGHT OUTER JOIN
    4. FULL OUTER JOIN
    5. 那个没人点名的第五种:CROSS JOIN
  5. 三种连接算法
    1. 嵌套循环连接(Nested Loop Join)
    2. 哈希连接(Hash Join)
    3. 排序归并连接(Sort-Merge Join)
  6. 为什么连接顺序重要
  7. 那为什么不直接用图数据库?
  8. 反规范化:当连接变成痛苦
  9. JOIN 真正证明了什么

#TL;DR

在前关系时代的数据库里,记录之间的关系是物理指针——你要通过数据库作者当初决定存进去的某个字面意义上的内存地址,从客户记录导航到订单记录。在 Codd 的关系模型里,关系是逻辑的:两张表里共享的一个值(客户的 ID 同时出现在 customers 表和 orders 表里),而 JOIN 运算在需要时把两张表的行组合起来。听起来像个小改动,实际上却是一个”你能演进”和”你不能演进”的数据库之间的差别。连接有四种类型(INNER、LEFT、RIGHT、FULL OUTER),用三种主要算法执行(嵌套循环、哈希、排序归并),而且是现实数据库负载中大多数性能问题的来源。

#JOIN 之前:指针导航

在 CODASYL 网状数据库和 IMS 层次数据库里,关系是显式的。一个客户记录有一个物理指针指向它的第一条订单记录,每条订单记录又有一个指向下一条的指针。要找一位客户的所有订单,你写的代码大致这样:

customer = find_customer(id=101)
order = customer.first_order
while order is not None:
    process(order)
    order = order.next_order

如果你只想问”把客户 101 的订单给我”,这样是高效的。也是你能廉价问出来的唯一问题。要从一个订单回到客户,你需要一个反向指针——而这个反向指针必须在数据插入时就已经建好。要查”所有寄到伦敦地址的订单”,你必须遍历每位客户的订单链表再过滤。

每一种新的查询模式都要求新指针。每个新指针都要求模式变更、数据迁移和应用代码改写。预料到的查询飞快,没预料到的就不可能。

#关系式的替代方案

Codd 1970 年的论文提出了相反的做法:完全不要指针。客户记录有一个 ID,订单记录有一个 customer_id 列。关系就是这两列含有匹配的值这一事实。数据本身不知道这件事——这是数据的一个逻辑性质,数据库可以在查询时去发现并利用。

Customers                          Orders
┌────┬──────────────┬──────────┐  ┌────┬─────────┬──────┐
│ id │ name         │ city     │  │ id │ cust_id │  amt │
├────┼──────────────┼──────────┤  ├────┼─────────┼──────┤
│101 │ Ada Lovelace │ London   │  │  1 │     101 │  250 │
│102 │ Alan Turing  │ London   │  │  2 │     102 │   80 │
│103 │ Grace Hopper │ New York │  │  3 │     101 │  430 │
└────┴──────────────┴──────────┘  └────┴─────────┴──────┘

隐式关系:orders.cust_id 与 customers.id 匹配

orders 表里没有任何指针说”这条订单属于这个物理客户记录”。cust_id 这一列只是说”这条订单的客户就是 ID 为 101 的那位客户”。在 orders.cust_id = customers.id 上连接这两张表,就得到合并后的视图。

回报是灵活性。同一批数据可以按不同方向为不同查询做连接:

  • “查出 Ada 的所有订单”——从 customers 连到 orders。
  • “查出下了 3 号订单的客户”——从 orders 连到 customers。
  • “查出下单金额超过 $400 的所有客户”——连接再过滤。
  • “按城市求平均订单金额”——连接再聚合。

数据库在设计时不需要考虑其中任何一条查询。关系内嵌在数据里,查询语言去把它们发现出来。

#四种连接类型

SQL 暴露四种主要的连接类型,区别在于没有匹配的行会怎么样。

#INNER JOIN

默认的那种。只有两边都有匹配的行才出现在结果里。

SELECT c.name, o.amount
FROM customers c
INNER JOIN orders o ON o.cust_id = c.id;

如果一位客户没有订单,他不会出现。如果一条订单没有匹配的客户(这意味着参照完整性被破坏),它也不会出现。

#LEFT OUTER JOIN

左表所有行,加上右表的匹配。没有匹配的左行在右侧得到 NULL。

SELECT c.name, o.amount
FROM customers c
LEFT JOIN orders o ON o.cust_id = c.id;

Grace Hopper 没有订单,她仍然出现在结果里,amount 列为 NULL。当问题是”列出所有客户,如果他们有订单,就一并展示”时,用这种连接。

#RIGHT OUTER JOIN

LEFT 的镜像。右表所有行,没有匹配的右行在左侧得到 NULL。实际里很少用——你总可以把 RIGHT JOIN 写成 LEFT JOIN 再把两张表对调,大多数查询作者更喜欢从左往右读。

#FULL OUTER JOIN

两张表的所有行。没匹配的那一侧得到 NULL。适合找应该在两张表里都有却没有的数据——比如对账报告。

#那个没人点名的第五种:CROSS JOIN

CROSS JOIN 是笛卡尔积——左表的每一行和右表的每一行配对,没有匹配条件。如果你有 1,000 个客户和 10,000 条订单,一次 cross join 返回 1000 万行。多数时候是 bug。偶尔故意——比如生成所有可能的取值组合用于测试。

-- 危险:很少是你想要的
SELECT c.name, o.amount
FROM customers c
CROSS JOIN orders o;

在 SQL 里漏掉 ON 子句常常就产出一次意外的 cross join,这也是为什么现代 SQL 方言有时会拒绝执行没有显式连接条件的 JOIN。

#三种连接算法

在 SQL 里写 JOIN 是声明式的——说的是连什么,不是怎么连。查询优化器会根据表的大小、可用索引、内存和统计信息来选择物理算法。主要有三种。

#嵌套循环连接(Nested Loop Join)

for each row r in outer_table:
    for each row s in inner_table:
        if match(r, s):
            emit(r, s)

复杂度:大小为 N 和 M 的两张表,是 O(N × M)。对大表很朴素也很慢——但如果内层表的连接列上有索引,就可以把内层循环换成一次索引查找,代价降到 O(N × log M)。

嵌套循环适合:

  • 一张表非常小(就几行)。
  • 内层表的连接列上有好的索引。
  • 内存紧——嵌套循环不需要缓冲。

#哈希连接(Hash Join)

build: hash_table = {}
       for each row r in smaller_table:
           hash_table[r.join_key].append(r)

probe: for each row s in larger_table:
           for r in hash_table.get(s.join_key, []):
               emit(r, s)

复杂度:O(N + M),大约 O(N) 内存。对大表比嵌套循环快得多,但需要足够的内存装下较小表的哈希。变种:grace hash join 先把两张表分区写入磁盘,然后按分区逐对做哈希连接——在内存装不下的时候仍然合理。

哈希连接适合:

  • 两张表都很大。
  • 连接列上都没有合适的索引。
  • 较小的那张表装得下内存。

#排序归并连接(Sort-Merge Join)

按连接键对两张表排序
并行走两路有序流,发射匹配

复杂度:O(N log N + M log M),因为要排序;但如果数据本来就是有序的(比如从连接键的 B 树索引读出来),就降到 O(N + M)。

排序归并连接适合:

  • 两张表已经按连接键排序。
  • 数据太大,哈希连接的内存撑不住。
  • 输出本来也要排序。

现代数据库还有一些变种:非等值归并连接、广播连接(用在分布式系统,其中一边小到可以复制到每个节点)、布隆过滤器辅助连接等等。上面三种是核心。

#为什么连接顺序重要

一条四表连接的查询可以按许多不同顺序执行:

SELECT *
FROM customers c
JOIN orders o    ON o.cust_id = c.id
JOIN order_items i ON i.order_id = o.id
JOIN products p  ON p.id = i.product_id;

把这些连接排序,有 4! / 2 = 12 种做法(假设是左深树)。每个顺序产出相同的结果,但性能可能天差地别:

  • 先连 orders 和 order_items(都是大表)——得到一个很大的中间结果。
  • 先把 customers 过滤到伦敦,再连 orders——中间结果小得多。
  • 如果 products 小而选择度高,就把它尽早加入——中间结果非常小。

从中做选择是查询优化器的工作,它有自己的文章。选择依赖于表大小、可用索引和来自统计信息的基数估计。选错了,查询就会从毫秒变成小时。

现实数据库里大部分”这查询慢”的问题,骨子里都是连接顺序问题。EXPLAIN ANALYZE 常常揭示优化器选了坏顺序,是因为统计信息陈旧了,或者查询结构把估算器搞糊涂了。

#那为什么不直接用图数据库?

一个合理的反问:如果我们要的是关系,为什么不直接把关系存起来?图数据库(Neo4j、JanusGraph、AWS Neptune)把节点和边作为一等公民存储,并建好索引以便快速遍历。

答案是:多数工作负载其实不是图工作负载。 它们确实有关系,但这些关系深度有限、形状可预测。典型的 OLTP 查询连接 2-5 张表。典型的分析查询在几个维度上聚合。这正是:

  • 关系模型”表 + 连接”的抽象契合数据的结构。
  • 外键列上的索引让连接很便宜。
  • 查询优化器能找到好的计划。

图数据库真正闪光的是深度递归查询:“找出和这个人分不过六度、又在同一行业工作的所有人”。这是 SQL 很难优雅表达的真正图遍历(虽然现代 SQL 有递归 CTE)。

对于典型的企业工作负载——客户、订单、商品、品类、交易——关系模型加连接才是对的抽象。它已经被竞争性地优化了五十年。图数据库有它的生态位,但比它们自己的市场宣传要小。

#反规范化:当连接变成痛苦

到了足够大的规模,连接会成为瓶颈。把十亿行的交易表、十亿行的用户表、一百万行的商品表连接到一起的查询,不管优化器多好,数据量本身就会让它慢。

务实的应对是反规范化——存冗余数据以便在查询时避免连接。不写:

SELECT t.amount, u.country
FROM transactions t
JOIN users u ON u.id = t.user_id;

你可以把 country 预存进交易表本身:

SELECT amount, country
FROM transactions;  -- 不用连接

更快,但有代价。用户国家一变,现在就得传播到每一行交易。存储更大了,数据模型也不那么干净了——你复制了信息。

数据仓库(Snowflake、BigQuery、Redshift)经常激进地反规范化,因为分析查询从避免连接中获益,读写比又很高,更新成本是可以接受的。OLTP 数据库极少反规范化,因为它们写密集的负载会被持续不断地更新冗余副本拖垮。

这是一个持续的权衡,不是一个已解决的问题。关系模型把规范化设计作为起点;反规范化是从起点出发的一次经过深思和测量的偏离。

#JOIN 真正证明了什么

关系模型那篇把 JOIN 叫做关系模型的”关键洞见”。这个提法准确但过于临床。JOIN 在实践中真正证明的是:

  • 数据比它最初的用例活得久。 一个围绕外键设计的模式,可以被问出最初设计者没预料到的组合查询。层次和网状模式做不到。
  • 逻辑关系胜过物理关系。 指针是一个特定的内存地址。外键是一个共享的值,它在迁移、复制、分区、灾难恢复之间都稳定。
  • 数据库引擎可以进步。 连接可以朴素地实现(嵌套循环),也可以高级地实现(哈希、排序归并),而改进实现不需要改任何应用代码。五十年的数据库工程就是在同一张 SQL 表面后面不断加入更聪明的连接算法。

前关系数据库并不慢,而是不灵活。让关系模型灵活的,正是 JOIN:任何关系,按需发现,算法由优化器在运行时选。数据不需要知道自己将如何被查询。这正是让关系模型比此前任何东西都更耐用的那个性质。