Content #

如果问我：“善是什么？”那么我的回答是，善就是善，这个问题即使追根究底也是这样。或者如果问我：“怎样给善下定义?芽”那么我的回答是，它不可能下定义，这就是我对此所能说的一切。这些回答也许令人失望，但它们却是至关重要的。

穆尔把“善”和“黄”作类比，因为“黄”也是不可定义的。绞尽脑汁，也没有办法说明“黄”给我们一种什么感觉，如果查字典，“黄”的解释是“金子的颜色”，只能从表象上作说明，没有对黄的本质作出任何交代。也许有人会争辩说，“黄”可以定义为某一频率的电磁波反射到人视觉神经所产生的感觉。但这仍未把“黄”给人的感觉说清楚。因为人类在发现电磁波以前很久就已经有了“黄”的概念，并且有了“黄”这个字。从这个意义上说，“黄”仍然是不可定义的。“黄”和“善”都不能定义的原因是，它们都是最简单的、不可再分解的。它们不像“马”，马可以分解为尾、蹄、心、肝等，因此马可以通过这些更基本的要素来定义。而“善”则不可能。穆尔研究伦理学强调对伦理概念和善恶判断作出逻辑分析，目的在于寻求对什么是善作出回答，同时要求此种回答所依据的概念和判断是一致或无矛盾的，这种研究称为逻辑实证研究。

而传统的伦理学强调伦理规范的研究，即人们的行为应遵循什么规则，研究道德的社会功能。通过伦理规范的研究，指出人应该如何处理与周围的人和事的关系，揭示出引导人们正确处理这些关系的方法。总之规范性的研究，是带有目的性的，而不仅是客观地对它分析。实证研究和规范研究是互相补充的。

From #

Links #

Content #

GHJ 算法与 SHJ 的不同之处在于，GHJ 正视了哈希表大于内存这个问题，将哈希表分块缓存在磁盘上。GHJ 中的 Grace 并不是指某项技术，而是首个采用该算法的数据库的名字。

GHJ 算法的执行过程，也是分为两个阶段。

第一阶段，Inner 表的记录会根据哈希值分成若干个块（Bucket）写入磁盘，而且每个 Bucket 必须小于内存容量。Outer 表也按照同样的方法被分为若干 Bucket 写入磁盘，但它的大小并不受到内存容量限制。

第二阶段和 SHJ 类似，先将 Inner 表的 Bucket 加载到内存，再读取 Outer 表对应 Bucket 的记录进行匹配，所有 Inner 表和 Outer 表的 Bucket 都读取完毕后，就得到了最终的结果集。

Viewpoints #

From #

20 | 关联查询：如何提升多表Join能力？

Links #

Content #

Simple Hash Join，也称为经典哈希连接（Classic Hash Join），它的执行过程包括建立阶段（Build Phase）和探测阶段（Probe Phase）。

1. 建立阶段

在 Build 阶段，在基表之上，算法使用既定的哈希函数构建哈希表，如上图的步骤 1 所示。哈希表中的 Key 是 id 字段应用（Apply）哈希函数之后的哈希值，而哈希表的 Value 同时包含了原始的 Join Key（id 字段）和 Payload。

1. 探测阶段

算法依次遍历驱动表的每一条数据记录。首先使用同样的哈希函数，以动态的方式计算 Join Key 的哈希值。然后，算法再用哈希值去查询刚刚在 Build 阶段创建好的哈希表。如果查询失败，则说明该条记录与基表中的数据不存在关联关系；相反，如果查询成功，则继续对比两边的 Join Key。如果 Join Key 一致，就把两边的记录进行拼接并输出，从而完成数据关联。

Simple Hash Join 做了非常理想化的假设，也就是 Inner 表形成的哈希表小到能够放入内存中。可实际上，即使对于单体数据库来说，这个哈希表也是有可能超过内存容量的。

Viewpoints #

From #

20 | 关联查询：如何提升多表Join能力？

Links #

Content #

排序归并算法就是 Sort-Merge Join（SMJ），也被称为 Merge Join。SMJ 可以分为排序和归并两个阶段：

1. 第一阶段是排序，就是对 Outer 表和 Inner 表进行排序，排序的依据就是每条记录在连接键上的数值。
2. 第二阶段就是归并，因为两张表已经按照同样的顺序排列，所以 Outer 表和 Inner 表各一次循环遍历就能完成比对工作了。

SMJ 就是先要把两个数据集合变成两个数据序列，也就是有序的数据单元，然后再做循环比对。这样算下来，它的计算成本是两次排序再加两次循环。你可能会觉得奇怪，这成本是不是比 NLJ 还要高呀？

是的。所以选择 SMJ 是有前提的，而这个前提就是表的记录本身就是有序的，否则就不划算了。

索引是天然有序的，如果表的连接键刚好是索引列，那么 SMJ 就是三种嵌套循环算法中成本最低的，它的时间复杂度只有 O(m+n)。

Viewpoints #

From #

20 | 关联查询：如何提升多表Join能力？

Links #

Content #

所有的嵌套循环算法都由内外两个循环构成，分别从两张表中顺序取数据。其中，外层循环表称为外表（Outer 表），内层循环表则称为内表（Inner 表）。因为这个算法的过程是由遍历 Outer 表开始，所以 Outer 表也称为驱动表。在最终得到的结果集中，记录的排列顺序与 Outer 表的记录顺序是一致的。

根据在处理环节上的不同，嵌套循环算法又可以细分为三种：

1. Simple Nested Loop Join
2. Block Nested-Loop Join
3. Index Lookup Join

Viewpoints #

From #

20 | 关联查询：如何提升多表Join能力？

Links #

Content #

SNLJ 和 BNJ 都是直接在数据行上扫描，并没有使用索引。所以，这两种算法的磁盘 I/O 开销还是比较大的。

Index Lookup Join（ILJ）就是在 BNJ 的基础上使用了索引，算法执行过程是这样的：

1. 遍历 Outer 表，取一个批次的记录 ri；
2. 通过连接键（Join Key）和 ri 可以确定对 Inner 表索引的扫描范围，再通过索引得到对应的若干条数据记录，记为 sj；
3. 将 ri 的每一条记录与 sj 的每一条记录做 Join 操作并输出结果；
4. 重复前三步，直到遍历完 Outer 表中的所有数据，就得到了最后结果集。

ILJ 的主要优化点就是对 Inner 表进行索引扫描。

那么，为什么不让 Outer 表也做索引扫描呢？

Outer 表当然也可以走索引。但是，BNJ 在 Inner 表上要做多次全表扫描成本最高，所以 Inner 表上使用索引的效果最显著，也就成为了算法的重点。而对 Outer 表来说，因为扫描结果集要放入内存中暂存，这意味着它的记录数是比较有限的，索引带来的效果也就没有 Inner 表那么显著，所以在定义中没有强调这部分。

Viewpoints #

From #

20 | 关联查询：如何提升多表Join能力？

Links #

Content #

BNJ 是对 Simple Nested Loop Join 的一种优化，改进点就是减少 Inner 表的全表扫描次数。 BNJ的变化主要在于步骤 1，读取 Outer 表时不再只取一条记录，而是读取一个批次的 x 条记录，加载到内存中。这样执行一次 Inner 表的全表扫描就可以比较 x 条记录。

在 MySQL 中，这个 x 对应一个叫做 Join Buffer 的设置项，它直接影响了 BNJ 的执行效率。

与 SNLJ 相比，BNJ 虽然在时间复杂度都是 O(m*n)（m 和 n 分别是 Outer 表和 Inner 表的记录行数），但磁盘 I/O 的开销却明显降低了，所以效果优于 SNLJ。

Viewpoints #

From #

20 | 关联查询：如何提升多表Join能力？

Links #

Content #

SNLJ 是最简单粗暴的算法，所以也称为 Simple Nested-Loop Join。有些资料中会用 NLJ 指代 SNLJ。

SNLJ 的执行过程是这样的：

1. 遍历 Outer 表，取一条记录 r1；
2. 遍历 Inner 表，对于 Inner 表中的每条记录，与 r1 做 join 操作并输出结果；
3. 重复步骤 1 和 2，直至遍历完 Outer 表中的所有数据，就得到了最后的结果集。

SNLJ 算法虽然简单，但也很笨拙，存在非常明显的性能问题。原因在于，每次为了匹配 Outer 表的一条记录，都要对 Inner 表做一次全表扫描操作。而全表扫描的磁盘 I/O 开销很大，所以 SNLJ 的成本很高。

Viewpoints #

From #

20 | 关联查询：如何提升多表Join能力？

Links #

Content #

网络断了之后，主从库会采用增量复制的方式继续同步。

只要有从库存在，就会有repl_backlog_buffer。主库的所有写命令除了传播给从库之外，都会在这个repl_backlog_buffer中记录一份，缓存起来。当从库断连后，从库重新发送psync $master_runid $offset，主库才能通过$offset在 repl_backlog_buffer中找到从库断开的位置，只发送$offset之后的增量数据给从库即可。

repl_backlog_buffer 是一个环形缓冲区，主库会记录自己写到的位置，从库则会记录自己已经读到的位置。

刚开始的时候，主库和从库的写读位置在一起，这算是它们的起始位置。随着主库不断接收新的写操作，它在缓冲区中的写位置会逐步偏离起始位置，我们通常用偏移量来衡量这个偏移距离的大小，对主库来说，对应的偏移量就是 master_repl_offset。主库接收的新写操作越多，这个值就会越大。

同样，从库在复制完写操作命令后，它在缓冲区中的读位置也开始逐步偏移刚才的起始位置，此时，从库已复制的偏移量 slave_repl_offset 也在不断增加。正常情况下，这两个偏移量基本相等。

主从库的连接恢复之后，从库首先会给主库发送 psync 命令，并把自己当前的 slave_repl_offset 发给主库，主库会判断自己的 master_repl_offset 和 slave_repl_offset 之间的差距。

在网络断连阶段，主库可能会收到新的写操作命令，所以，一般来说， master_repl_offset 会大于 slave_repl_offset。此时，主库只用把 master_repl_offset 和 slave_repl_offset 之间的命令操作同步给从库就行。

就像刚刚示意图的中间部分，主库和从库之间相差了 put d e 和 put d f 两个操作，在增量复制时，主库只需要把它们同步给从库，就行了

Viewpoints #

From #

06 | 数据同步：主从库如何实现数据一致？

Links #

Content #

replication buffer 是主从库在进行全量复制时，主库上用于和从库连接的客户端的 buffer，而 repl_backlog_buffer 是为了支持从库增量复制，主库上用于持续保存写操作的一块专用 buffer。

Redis 主从库在进行复制时，当主库要把全量复制期间的写操作命令发给从库时，主库会先创建一个客户端，用来连接从库，然后通过这个客户端，把写操作命令发给从库。在内存中，主库上的客户端就会对应一个 buffer，这个 buffer 就被称为 replication buffer。Redis 通过 client_buffer 配置项来控制这个 buffer 的大小。主库会给每个从库建立一个客户端，所以 replication buffer 不是共享的，而是每个从库都有一个对应的客户端。

repl_backlog_buffer 是一块专用 buffer，在 Redis 服务器启动后，开始一直接收写操作命令，这是所有从库共享的。主库和从库会各自记录自己的复制进度，所以，不同的从库在进行恢复时，会把自己的复制进度（slave_repl_offset）发给主库，主库就可以和它独立同步。

Viewpoints #

From #

10 | 第1～9讲课后思考题答案及常见问题答疑

Links #