Use the Index, Luke! 笔记2 性能、Join操作

这是读 use-the-index-luke 的第二篇笔记，是 Testing and Scalability 和 The Join Operation 两章的内容。

存储大小和请求量对性能的影响

在开发环境工作很好的 SQL 到了生产环境可能执行的很慢，主要会受两个方面的影响：

数据量：同样一个查询，在几百条开发数据里面跑和几亿的数据里面跑，效果是不一样的；
请求量：开发环境只有几个连接查询，在生产环境中可能同时有几百个并发查询，速度也会显著下降。

分析 Execution Plan 的结果会比简单的 Benchmark 更有自信（要格外注意 Predicate Information 中的 filter，filter 随时可能爆炸）。完全的压测也是有必要的，但是通常成本很高。

有人认为生产环境的机器配置更高，机器更多，可以解决查询慢的问题。但是大部分的慢查询都不能通过增加硬件来解决。21世纪以来 CPU 的性能没有很大提升，CPU 厂商都开始用多核技术来提高 CPU 的性能。如果仅仅是一个任务，那么开发用的笔记本和服务器效果是差不多的。生产环境就像高速公路，可以允许更多的车在上面跑，而它本身并不会让车跑的更快。相反的，生产环境的设施更加复杂，服务器之间的交互更多，加上防火墙等设施，在生产环境运行更有可能更慢。NoSQL 宣称解决一切问题，但是本质上它是用最终一致性换取了水平扩展写的能力。如果一个查询在关系型数据库很慢，那么即使迁移到 NoSQL 也会很慢。加快查询最靠谱的方法是利用好 B-Tree 索引。

另一个导致查询慢的原因是硬盘磁头 Seek 的次数太多了，虽然一次 Seek 只需要几毫秒，一次索引查询（B-Tree）最多也只会 Seek 4次，但是如果 join 表太多的话，就会 Seek 几百次。

所以再次强调，最靠谱的验证方式还是看执行计划。否则很容被开发环境小量数据的效果“欺骗”。

Join 操作

先来两个笑话吧（No hard feelings）。

笑话1：

SQL 走进了一家酒吧，看到有两张桌子（Table），他问：我能加入（Join）你们吗？

笑话2：

为什么前端程序员总是独自吃饭？

因为他们不懂 Join Tables.

回到正题，join 可以将分散在多个表中的数据重新组合起来。因为 join 需要聚合分散的数据，所以 join 操作对磁盘的 seek 非常敏感。正确的索引可以加快 join 操作，如何索引取决于使用哪种 join 算法。常用的一共有 3 种。但是这些算法的一个共同点是：一次只能 join 两个 Table。如果有多个 Table，那么先 join 起来前两个 Table，然后作为中间表，再去和后面的 join。所以下文在讨论的时候，都是讨论两张表之间的 join。

虽然 join 的顺序对最后的结果没有什么影响，但是对查询性能是有影响的。优化器需要从所有的可能中选一个最优的查询计划出来。在这种情况下，光优化查询的参数是不够的，因为优化器做选择本身就会花一些时间（n! 复杂度，n是查询条件）。当然，如果使用 bind parameters 就没有这个问题啦（参考我的第一篇笔记），所以参数越多，使用 bind parameters 就越有必要。

接下来介绍 3 种最常用的 join 算法：

Nested Loops – 用循环来 join 两张表；
Hash Join – 将一张表构建出来 Hash 表，然后对表2中的每一行记录，找到 hash 表中对应的行；
Sort Merge – 将两张表排好序，然后用 Merge Sort 算法进行 join；

Nested Loops

这是实现起来最简单的一种方法：Join 表1 和表2，只要遍历表1中每一行，去表2 Select 就行了。

如果你使用 ORM 的话，可能遇到过一个经典的问题：N+1 select ——错误做法：从两张表查询 N 行记录，先在表1中查出来所有的行，然后用一个循环 Select 表2中的行。因为一共会执行 N + 1次 Select（第一次查询出所有记录，然后遍历N次），所以叫做 N+ 1 Select 问题。这样做可能在上线之后引起性能问题，因为执行了大量的 Select。

通过上面这个问题，可以比较好的理解 Nested Loops. 可以看出，join 的条件有没有索引，对 join 的性能影响很大。因为相当于执行的是 select。

通过 Nested loops 来进行 join 虽然和 ORM 这种 N+1 Select 的原理是相同的，但是用 SQL join 会更加高效。这是因为 join 是直接在数据库服务里面做的，而 N + 1 Select 要客户端和服务器来来回回对每一条 Select 进行请求和响应。

性能一般反应在两个方面：Response Time 和 Throughput，在网络上反应为延迟和带宽。对于数据库来说，延迟更加关键，带宽并不是很重要。

所以最好打开执行的 SQL 日志（一般的 ORM 都有这种选项），来看一下类似的操作是否是通过 SQL 来 join 的。

如果 join 条件有索引，并且数据集不大的话，Nested Loops 的性能是不错的。如果数据量大的话，优化器就会选择其他的 join 方式。

Hash Join

Hash Join 的原理是对一个表执行 Full table scan，将这个表 load 进 hash 表中，以 join 的条件作为这个 hash 表的 key；然后选出第二张表中，符合 where 查询条件的行，在 hash 表中找到对应的第一张表的数据。

将一张表加载到内存中，来避免了 join 的过程中多次 select。因为 join 的条件会被作为 hash 表的 key，本身就是 O(1) 的速度了，所以对 join 的条件建立索引，在 hash Join 中并不会起作用。

优化 Hash Join 速度的方法主要有两个：

加速遍历第二章表的速度，即对 where 条件建索引；
尽量减少 join 的内容的数量，这样降低 load 进内存的大小；水平角度，我们可以用 where 语句过滤出尽量少的行；垂直角度，我们只 select 需要的 column，而不是 select *；

Sort Merge

Sort Merge 的原理很简单，将两张表排好序，然后用 sort merge 的算法将两张表 join 起来。

Sort Merge 所需要的索引和 Hash join 一样，尽可能加速查询，对 where 语句索引。join 的条件是没有必要索引的。

Sort Merge 对 join 的顺序完全不感冒，A join B 和 B join A 的结果是完全一样的，性能也是一样；

因为 Sort Merge 要将两边的表都排好序，所以代价很高，相比之下，Hash Join 只需要处理一边的表。所以 Hash Join 实际上更常用一些。但是有一种情况，就是如果输入的数据已经是排好序的，那么 Sort Merge 是非常快的。

一	二	三	四	五	六	日
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30