Qi

Cogito ergo sum

发表于 分类于

“排序并查集” 不是一个常见的术语，我认为您可能在表述上存在一些误解。通常，”排序” 和 “并查集” 是两种不同的数据结构和算法。

  1. 排序：排序是一种将数据元素按照一定规则重新排列的操作。常见的排序算法包括冒泡排序、选择排序、插入排序、归并排序、快速排序等。这些算法根据元素的比较和交换操作来实现排序。

  2. 并查集：并查集（Disjoint Set Union，简称 DSU）是一种用于处理元素分组问题的数据结构。它主要支持两种操作：合并（Union）和查找（Find）。合并操作将两个不相交的集合合并为一个集合，而查找操作用于确定一个元素属于哪个集合。并查集常用于解决集合的合并、连通性问题等。

以下是一个简单的 Java 实现示例，展示如何实现并查集：

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class UnionFind {
    private int[] parent;
    private int[] rank;

    public UnionFind(int size) {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX == rootY) {
            return;
        }

        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
}

public class UnionFindExample {
    public static void main(String[] args) {
        int n = 6; // 元素个数
        UnionFind uf = new UnionFind(n);

        uf.union(0, 1);
        uf.union(2, 3);
        uf.union(4, 5);

        System.out.println(uf.find(1) == uf.find(0)); // 输出 true，因为已经合并
        System.out.println(uf.find(1) == uf.find(2)); // 输出 false，因为不在同一个集合中
    }
}

在上面的示例中，我们首先创建了一个 UnionFind 类来实现并查集。parent 数组存储每个元素的父节点，rank 数组存储每个集合的秩（树的深度）。在 find 方法中使用路径压缩优化，通过递归将节点的父节点直接指向根节点，以减小树的深度。

union 方法用于合并两个集合，根据秩的大小选择将一个集合的根节点连接到另一个集合的根节点，并更新秩。

这只是一个简单的并查集实现示例。在实际应用中，可能需要更多的优化和扩展，例如按秩合并、路径压缩等。

发表于 分类于

问题解析

自增id用完怎么办？MySQL里有很多自增的id，每个自增id都是定义了初始值，然后不停地往上加步长。

虽然自然数是没有上限的，但是在计算机里，只要定义了表示这个数的字节长度，那它就有上限。

比如，无符号整型(unsigned int)是4个字节，上限就是2 -1。

既然自增id有上限，就有可能被用完。

但是，自增id用完了会怎么样呢？今天这篇文章，我们就来看看MySQL里面的几种自增id，一起分析一下它们的值达到上限以后，会出现什么情况。

表定义自增值id说到自增id，你第一个想到的应该就是表结构定义里的自增字段，也就是我在第39篇文章《自增主键为什么不是连续的？》中和你介绍过的自增主键id。

表定义的自增值达到上限后的逻辑是：再申请下一个id时，得到的值保持不变。

我们可以通过下面这个语句序列验证一下：

32可以看到，第一个insert语句插入数据成功后，这个表的AUTO_INCREMENT没有改变（还是4294967295），就导致了第二个insert语句又拿到相同的自增id值，再试图执行插入语句，报主键冲突错误。

2 -1（4294967295）不是一个特别大的数，对于一个频繁插入删除数据的表来说，是可能会被用完的。

因此在建表的时候你需要考察你的表是否有可能达到这个上限，如果有可能，就应该创建成8个字节的bigint unsigned。

InnoDB系统自增row_id如果你创建的InnoDB表没有指定主键，那么InnoDB会给你创建一个不可见的，长度为6个字节的row_id。

InnoDB维护了一个全局的dict_sys.row_id值，所有无主键的InnoDB表，每插入一行数据，都将当前的dict_sys.row_id值作为要插入数据的row_id，然后把dict_sys.row_id的值加1。

实际上，在代码实现时row_id是一个长度为8字节的无符号长整型(bigint unsigned)。

但是，InnoDB在设计时，给row_id留的只是6个字节的长度，这样写到数据表中时只放了最后6个字节，所以row_id能写到数据表中的值，就有两个特征：

  1. row_id写入表中的值范围，是从0到2 -1；

  2. 当dict_sys.row_id=2 时，如果再有插入数据的行为要来申请row_id，拿到以后再取最后6个字节的话就是0。

也就是说，写入表的row_id是从0开始到2 -1。

达到上限后，下一个值就是0，然后继续循环。

当然，2 -1这个值本身已经很大了，但是如果一个MySQL实例跑得足够久的话，还是可能达到这个上限的。

在InnoDB逻辑里，申请到row_id=N后，就将这行数据写入表中；如果表中已经存create table t(id int unsigned auto_increment primary key) auto_increment=4294967295;insert into t values(null);//成功插入一行 4294967295show create table t;/* CREATE TABLE t̀ ̀( ìd ̀int(10) unsigned NOT NULL AUTO_INCREMENT, PRIMARY KEY (̀ id )̀) ENGINE=InnoDB AUTO_INCREMENT=4294967295;*/insert into t values(null);//Duplicate entry ‘4294967295’ for key ‘PRIMARY’3248484848在row_id=N的行，新写入的行就会覆盖原有的行。

要验证这个结论的话，你可以通过gdb修改系统的自增row_id来实现。

注意，用gdb改变量这个操作是为了便于我们复现问题，只能在测试环境使用。

图1 row_id用完的验证序列图2 row_id用完的效果验证可以看到，在我用gdb将dict_sys.row_id设置为2 之后，再插入的a=2的行会出现在表t的第一行，因为这个值的row_id=0。

之后再插入的a=3的行，由于row_id=1，就覆盖了之前a=1的行，因为a=1这一行的row_id也是1。

从这个角度看，我们还是应该在InnoDB表中主动创建自增主键。

因为，表自增id到达上限后，再插入数据时报主键冲突错误，是更能被接受的。

毕竟覆盖数据，就意味着数据丢失，影响的是数据可靠性；报主键冲突，是插入失败，影响的是可用性。

而一般情况下，可靠性优先于可用性。

Xid48在第15篇文章《答疑文章（一）：日志和索引相关问题》中，我和你介绍redo log和binlog相配合的时候，提到了它们有一个共同的字段叫作Xid。

它在MySQL中是用来对应事务的。

那么，Xid在MySQL内部是怎么生成的呢？MySQL内部维护了一个全局变量global_query_id，每次执行语句的时候将它赋值给Query_id，然后给这个变量加1。

如果当前语句是这个事务执行的第一条语句，那么MySQL还会同时把Query_id赋值给这个事务的Xid。

而global_query_id是一个纯内存变量，重启之后就清零了。

所以你就知道了，在同一个数据库实例中，不同事务的Xid也是有可能相同的。

但是MySQL重启之后会重新生成新的binlog文件，这就保证了，同一个binlog文件里，Xid一定是惟一的。

虽然MySQL重启不会导致同一个binlog里面出现两个相同的Xid，但是如果global_query_id达到上限后，就会继续从0开始计数。

从理论上讲，还是就会出现同一个binlog里面出现相同Xid的场景。

因为global_query_id定义的长度是8个字节，这个自增值的上限是2 -1。

要出现这种情况，必须是下面这样的过程：

  1. 执行一个事务，假设Xid是A；

  2. 接下来执行2 次查询语句，让global_query_id回到A；

  3. 再启动一个事务，这个事务的Xid也是A。

不过，2 这个值太大了，大到你可以认为这个可能性只会存在于理论上。

Innodb trx_idXid和InnoDB的trx_id是两个容易混淆的概念。

Xid是由server层维护的。

InnoDB内部使用Xid，就是为了能够在InnoDB事务和server之间做关联。

但是，InnoDB自己的trx_id，是另外维护的。

其实，你应该非常熟悉这个trx_id。

它就是在我们在第8篇文章《事务到底是隔离的还是不隔离的？》中讲事务可见性时，用到的事务id（transaction id）。

InnoDB内部维护了一个max_trx_id全局变量，每次需要申请一个新的trx_id时，就获得max_trx_id的当前值，然后并将max_trx_id加1。

InnoDB数据可见性的核心思想是：每一行数据都记录了更新它的trx_id，当一个事务读到一行数646464据的时候，判断这个数据是否可见的方法，就是通过事务的一致性视图与这行数据的trx_id做对比。

对于正在执行的事务，你可以从information_schema.innodb_trx表中看到事务的trx_id。

我在上一篇文章的末尾留给你的思考题，就是关于从innodb_trx表里面查到的trx_id的。

现在，我们一起来看一个事务现场：

图3 事务的trx_idsession B里，我从innodb_trx表里查出的这两个字段，第二个字段trx_mysql_thread_id就是线程id。

显示线程id，是为了说明这两次查询看到的事务对应的线程id都是5，也就是session A所在的线程。

可以看到，T2时刻显示的trx_id是一个很大的数；T4时刻显示的trx_id是1289，看上去是一个比较正常的数字。

这是什么原因呢？实际上，在T1时刻，session A还没有涉及到更新，是一个只读事务。

而对于只读事务，InnoDB并不会分配trx_id。

也就是说：

  1. 在T1时刻，trx_id的值其实就是0。

而这个很大的数，只是显示用的。

一会儿我会再和你说说这个数据的生成逻辑。

  1. 直到session A 在T3时刻执行insert语句的时候，InnoDB才真正分配了trx_id。

所以，T4时刻，session B查到的这个trx_id的值就是1289。

需要注意的是，除了显而易见的修改类语句外，如果在select 语句后面加上for update，这个事务也不是只读事务。

在上一篇文章的评论区，有同学提出，实验的时候发现不止加1。

这是因为：

  1. update 和 delete语句除了事务本身，还涉及到标记删除旧数据，也就是要把数据放到purge队列里等待后续物理删除，这个操作也会把max_trx_id+1， 因此在一个事务中至少加2；

  2. InnoDB的后台操作，比如表的索引信息统计这类操作，也是会启动内部事务的，因此你可能看到，trx_id值并不是按照加1递增的。

那么，T2时刻查到的这个很大的数字是怎么来的呢？其实，这个数字是每次查询的时候由系统临时计算出来的。

它的算法是：把当前事务的trx变量的指针地址转成整数，再加上2 。

使用这个算法，就可以保证以下两点：

  1. 因为同一个只读事务在执行期间，它的指针地址是不会变的，所以不论是在 innodb_trx还是在innodb_locks表里，同一个只读事务查出来的trx_id就会是一样的。

  2. 如果有并行的多个只读事务，每个事务的trx变量的指针地址肯定不同。

这样，不同的并发只读事务，查出来的trx_id就是不同的。

那么，为什么还要再加上2 呢？在显示值里面加上2 ，目的是要保证只读事务显示的trx_id值比较大，正常情况下就会区别于读写事务的id。

但是，trx_id跟row_id的逻辑类似，定义长度也是8个字节。

因此，在理论上还是可能出现一个读写事务与一个只读事务显示的trx_id相同的情况。

不过这个概率很低，并且也没有什么实质危害，可以不管它。

另一个问题是，只读事务不分配trx_id，有什么好处呢？一个好处是，这样做可以减小事务视图里面活跃事务数组的大小。

因为当前正在运行的只读事务，是不影响数据的可见性判断的。

所以，在创建事务的一致性视图时，InnoDB就只需要拷贝读写事务的trx_id。

另一个好处是，可以减少trx_id的申请次数。

在InnoDB里，即使你只是执行一个普通的select语句，在执行过程中，也是要对应一个只读事务的。

所以只读事务优化后，普通的查询语句不需要申请trx_id，就大大减少了并发事务申请trx_id的锁冲突。

484848由于只读事务不分配trx_id，一个自然而然的结果就是trx_id的增加速度变慢了。

但是，max_trx_id会持久化存储，重启也不会重置为0，那么从理论上讲，只要一个MySQL服务跑得足够久，就可能出现max_trx_id达到2 -1的上限，然后从0开始的情况。

当达到这个状态后，MySQL就会持续出现一个脏读的bug，我们来复现一下这个bug。

首先我们需要把当前的max_trx_id先修改成2 -1。

注意：这个case里使用的是可重复读隔离级别。

具体的操作流程如下：

图 4 复现脏读由于我们已经把系统的max_trx_id设置成了2 -1，所以在session A启动的事务TA的低水位就是484848482 -1。

在T2时刻，session B执行第一条update语句的事务id就是2 -1，而第二条update语句的事务id就是0了，这条update语句执行后生成的数据版本上的trx_id就是0。

在T3时刻，session A执行select语句的时候，判断可见性发现，c=3这个数据版本的trx_id，小于事务TA的低水位，因此认为这个数据可见。

但，这个是脏读。

由于低水位值会持续增加，而事务id从0开始计数，就导致了系统在这个时刻之后，所有的查询都会出现脏读的。

并且，MySQL重启时max_trx_id也不会清0，也就是说重启MySQL，这个bug仍然存在。

那么，这个bug也是只存在于理论上吗？假设一个MySQL实例的TPS是每秒50万，持续这个压力的话，在17.8年后，就会出现这个情况。

如果TPS更高，这个年限自然也就更短了。

但是，从MySQL的真正开始流行到现在，恐怕都还没有实例跑到过这个上限。

不过，这个bug是只要MySQL实例服务时间够长，就会必然出现的。

当然，这个例子更现实的意义是，可以加深我们对低水位和数据可见性的理解。

你也可以借此机会再回顾下第8篇文章《事务到底是隔离的还是不隔离的？》中的相关内容。

thread_id接下来，我们再看看线程id（thread_id）。

其实，线程id才是MySQL中最常见的一种自增id。

平时我们在查各种现场的时候，show processlist里面的第一列，就是thread_id。

thread_id的逻辑很好理解：系统保存了一个全局变量thread_id_counter，每新建一个连接，就将thread_id_counter赋值给这个新连接的线程变量。

thread_id_counter定义的大小是4个字节，因此达到2 -1后，它就会重置为0，然后继续增加。

但是，你不会在show processlist里看到两个相同的thread_id。

这，是因为MySQL设计了一个唯一数组的逻辑，给新线程分配thread_id的时候，逻辑代码是这样的：

484832do { new_id= thread_id_counter++;} while (!thread_ids.insert_unique(new_id).second);这个代码逻辑简单而且实现优雅，相信你一看就能明白。

小结今天这篇文章，我给你介绍了MySQL不同的自增id达到上限以后的行为。

数据库系统作为一个可能需要7*24小时全年无休的服务，考虑这些边界是非常有必要的。

每种自增id有各自的应用场景，在达到上限后的表现也不同：

  1. 表的自增id达到上限后，再申请时它的值就不会改变，进而导致继续插入数据时报主键冲突的错误。

  2. row_id达到上限后，则会归0再重新递增，如果出现相同的row_id，后写的数据会覆盖之前的数据。

  3. Xid只需要不在同一个binlog文件中出现重复值即可。

虽然理论上会出现重复值，但是概率极小，可以忽略不计。

  1. InnoDB的max_trx_id 递增值每次MySQL重启都会被保存起来，所以我们文章中提到的脏读的例子就是一个必现的bug，好在留给我们的时间还很充裕。

  2. thread_id是我们使用中最常见的，而且也是处理得最好的一个自增id逻辑了。

当然，在MySQL里还有别的自增id，比如table_id、binlog文件序号等，就留给你去验证和探索了。

不同的自增id有不同的上限值，上限值的大小取决于声明的类型长度。

而我们专栏声明的上限id就是45，所以今天这篇文章也是我们的最后一篇技术文章了。

既然没有下一个id了，课后也就没有思考题了。

今天，我们换一个轻松的话题，请你来说说，读完专栏以后有什么感想吧。

这个“感想”，既可以是你读完专栏前后对某一些知识点的理解发生的变化，也可以是你积累的学习专栏文章的好方法，当然也可以是吐槽或者对未来的期望。

欢迎你给我留言，我们在评论区见，也欢迎你把这篇文章分享给更多的朋友一起阅读。

Continue  12跟着学了三个多月，受益匪浅，学到了很多新的知识和其中的原理！2019-02-25 作者回复早2019-02-25克劳德  7本人服务端工程师，在学习这门课之前数据库一直是我的短板，曾听朋友说MySQL或数据库中涉及了很多方面的知识点，每一个拿出来展开讲几乎都能出一本书了，对数据库是越来越忌惮，同时也因为工作上并没有过多接触，水平便一直停留在编写简单SQL层面。

在面试中被问到数据库问题，只能无奈的说这块不太清楚，也曾在网上自学过，但网上的文章知识点比较零散，很多都是给出一些结论性的观点，由于不了解其内部原理，记忆很难深刻。

老实说，当初报这门课的时候就像买技术书籍一样，我相信大家都有这样的体会，以为买到了就等于学到了，所以有一段时间没有点开看过，以至于后面开始学的时候都是在追赶老师和大家的进度，唯一遗憾的地方就是没能跟老师及时留言互动。

这门课虽然是文字授课，但字里行间给我的感觉就是很亲切很舒服，为什么呢，因为老师可以把晦涩的知识变得通俗易懂，有时我在思考，如果让我来讲一个自己擅长的领域是否也能做到这一点，如果要做到的话需要什么样的知识储备呢。

最后真要感谢老师的这门课，让我从心里不再惧怕数据库问题，不管是工作还是面试中信心倍增，现在时不时都敢和我们DBA“切磋切磋“了，哈哈。

精选留言祝好~2019-02-25 作者回复“切磋切磋“留言不会“过时”哈，在对应的章节下面提出相关的问题，我会持续关注评论区2019-02-25三胖  3老师，我才学了四分之一的课程，但是这门课已经更新完了，我是直接跑到最后一节技术篇来留言的！很想知道，后来者比如我在学到后面的课程时遇到问题留言，老师还会看会回复吗？（老师的课程超值！！）2019-02-25 作者回复会看的后台系统是按照留言时间显示的而且我在这事情上有强迫症，一定会让“未处理问题”变成0的只是说如果是其他同学评论区问过的问题，我可能就不会重复回复了2019-02-25某、人  2很遗憾没能坚持到最后,但是也很庆幸能遇到这么好的专栏。

以前了解mysql都是一些零散的知识点,通过学习完专栏,不论是mysql整体架构还是基础的知识点,都有了更深的认识。

以后就把老师的文档当官方文档查,出现问题先来看看专栏。

感触特别深的是,老师对于提到的每一个问题,都会严谨又认真的去回答,尽量帮助每一位同学都能有所收获。

要做到这一点，是特别耗费精力的。

感谢老师的传道授业解惑,希望以后有机会能当面向老师请教问题。

期待老师下一部杰作2019-02-26 作者回复刚过完年都是很忙的， 找时间补上哈，等你的评论区留言^_^2019-02-26夜空中最亮的星（华仔）  2不知道是最后一篇，否则的话就慢些读完了；

我是一名运维，公司也没有DBA，所以MySQL库也归我收拾；

读了老师的专栏，操作起数据库来，心情更好了；

老师的课，让我有了想看完《高性能MySQL》的兴趣；

听了老师的课，开发都来问我数据库的问题了，高兴；

老师你会有返场吗？我猜会 可否透漏下接下来的安排，会有续集吗？进阶吗？不想这一别就是一生。

您的从未谋面的学生。

2019-02-25 作者回复谢谢你“开发都来问我数据库的问题了”，当年我也是这么开始“入坑”，加油2019-02-25极客时间  2通過這個專欄的系統學習，梳理很多知識點、擴展了我對MySQL的認識及以後使用。

感謝老師的諄諄教導！2019-02-25NoDBA  1低版本thread_id超过2^32-1后，在general log显示是负数，高版本貌似没有这个问题，是否高版本的thread_id是8字节呢？2019-02-27 作者回复主要不是定义的问题，而是打印的时候代码问题，按照这个代码输出的：

“%5ld “, (long) thread_id是个bug， 超过2^31就变成负数了，新版本改了好问题2019-02-28kun  1感觉戛然而止哈 没学够，后面还会再回顾，老师辛苦！2019-02-26亮  1老师，sql 的where里 < 10001 和 <= 10000有什么区别吗？2019-02-25 作者回复这要看你关注的是什么你这么问，应该这个字段是整型吧？从查询结果可能是一样的，不过锁的范围不同，你可以看下21篇2019-02-25IceGeek17  1IceGeek17  1感谢老师，课程受益匪浅，课程结束后，如果有问题，是继续在这里的评论区提问，还是会有另外一条答疑通道？另外，在第35篇我提了几个问题，老师还没有回答，我这里再贴一下，老师看一下问题一：

对于BKA算法的流程理解，用文中的例子，先把t1表（小表）中查询需要的字段放入join_buffer,然后把join_buffer里的字段值批量传给t2表，先根据索引a查到id，然后得到一批主键id，再根据主键id排序，然后再根据排完序的id去主键索引查数据（这里用到MRR）理解是否正确？这里对于主键id排序是在哪里做的，是在join_buffer里，还是另外再开辟一块临时内存？如果在join_buffer里，那join_buffer里的每行内容是不是：t2.id + t1查询必须的字段，并且join_buffer里是根据id排序的？问题二：

虽然MySQL官方没有支持hash join，但是之前看到文章说，MariaDB已经支持hash join，能不能后续在答疑文章中简单总结下mariaDB支持的join算法问题三：

在实际项目中，一个比较困惑的问题，看到过这样的类似写法：

select xxx from t1 join t2 on t1.id = t2.id for update （目的是获取几个表上最新的数据，并且加上锁，防止数据被更新）这里有几个问题：

  1. 像这样 join + for update，表上的加锁规则是怎么样的？是不是在需要join的两个表上根据具体的查询执行过程都加上锁？2）像这样 join + for update 的用法是否合理？碰到这样的场景，应该怎么去做？问题四：

看过阿里输出的开发手册里，强调 “最多不超过三表join”，实际项目中，给我感觉很难做到所有业务都不超过三表join，那这里的问题就是，有什么相关的经验方法，可以尽量降低参与join的数据表？比如，在数据表里添加冗余字段，可以降低参与join的数据表数量，还有什么其他好的方法？2019-02-25 作者回复就在我们评论区，提跟文章相关的内容，会继续关注。

问题一、前面的过程理解正确，MRR过程用的是read_rnd_buffer 问题二、其实我们文中最后那个过程，你把他设想成在MySQL内部执行。

。

问题三、这种复杂的语句，你要把我们两部分知识点连起来看。

一个原则：for update的话，执行语句过程中扫到的间隙和记录都要加锁。

当然最好是不这么做，拆成两个语句会好些。

问题四、还是我文中的建议，如果都用NLJ或BKA算法的join其实还好，所以看看explain。

降低join表数量的方法，基本上行就是冗余字段和拆成多个语句这两个方向了2019-02-25Leon  1跟着老师终于学到了最后，每天的地铁时间无比充实，我对mysql的基本原理和工作流程大致有了初步的了解，而不是以前的增删查改，打算以后抽时间再二刷三刷，等全部搞懂后，再去看看高性能mysql这本书，如果时间允许，打算再去自己参照教程实现一个简易的DB，课程虽然结束了，仍然感觉意犹未尽，希望老师拉一个倍洽群，大家一起在里面讨论和学习2019-02-25 作者回复 评论区一直会开放大家到对应的文章去提相关问题 二刷三刷我也一直在哦2019-02-25Dkey  1当前系统并无其他事务存在时，启动一个只读事务时（意味没有事务id），它的低高水位是怎么样的老师。

2019-02-25 作者回复假设当前没有其他事务存在，假设当前的max_trx_id=N,这时候启动一个只读事务，它的高低水位就都是N。

2019-02-25shawn  1受益匪浅，最后几讲还想了解下null值如何建立索引，由于null直接不能比较和排序，MySQL能区分出每一个null值吗2019-02-25 作者回复可以，因为普通索引上都有主键值对吧，所以其实是 (null, id1), (null, id2) ….2019-02-25亢星东  0id是有上限的，这个的id上限是45，这个结局可以，讲的不错，学到很多2019-03-13Bamboo  0今天终于读完了，从对MySQL只停留在CRUD操作的水平，慢慢开始对MySQL底层的机制有了一些认识，在遇到问题时，会首先从底层原理去分析，并结合explain来验证自己的分析，一次很nice的学习之旅。

感谢大神老师这么认真负责，节假日都不休息，哈哈！2019-03-12 作者回复2019-03-13ArtistLu  0相遇恨晚，安慰下自己，种树的最好时机是十年前，其次是现在！！！谢谢老师2019-03-08 作者回复2019-03-09fighting  0已经二刷了，准备三刷四刷2019-03-07 作者回复2019-03-09沙漠里的骆驼  0讲的非常好，是我遇到课程讲授最好的了。

今天刚和池老师说，希望可以有线下的课程，比如完成一个数据库的完整设计，从最上层的sql语法解析器到底层的文件调度系统。

在集中的时间里面比如1个月或者2个月，线下组织大家一起，每个人都完成一个tiny_db的工程。

我想这是最好的成长了。

不知道老师是否也有这方面的想法？不管如何，真的很感谢老师。

如此娓娓道来，所谓的如沐春风便是如此吧。

2019-03-06 作者回复谢谢你。

后面只要还是在评论区继续和大家交流2019-03-07芬  0学习到了很多平时没有关注到的小细节，很赞！当然 师傅领进门 修行靠个人。

剩下的就是自己好好消化应用了，谢谢老师2019-02-28封建的风  0之前很多知识点有点粗浅，尤其在行版本可见性，redo log&bin log关系，加锁的原理章节，深入浅出，受益匪浅。

感谢老师精品专栏，后期再二刷2019-02-27```

发表于 分类于

问题解析

答疑文章（三）：说一说这些好问题
这是我们专栏的最后一篇答疑文章，今天我们来说说一些好问题。

在我看来，能够帮我们扩展一个逻辑的边界的问题，就是好问题。

因为通过解决这样的问题，能够加深我们对这个逻辑的理解，或者帮我们关联到另外一个知识点，进而可以帮助我们建立起自己的知识网络。

在工作中会问好问题，是一个很重要的能力。

经过这段时间的学习，从评论区的问题我可以感觉出来，紧跟课程学习的同学，对SQL语句执行性能的感觉越来越好了，提出的问题也越来越细致和精准了。

接下来，我们就一起看看同学们在评论区提到的这些好问题。

在和你一起分析这些问题的时候，我会指出它们具体是在哪篇文章出现的。

同时，在回答这些问题的过程中，我会假设你已经掌握了这篇文章涉及的知识。

当然，如果你印象模糊了，也可以跳回文章再复习一次。

join的写法在第35篇文章《join语句怎么优化？》中，我在介绍join执行顺序的时候，用的都是straight_join。

@郭健 同学在文后提出了两个问题：

  1. 如果用left join的话，左边的表一定是驱动表吗？2. 如果两个表的join包含多个条件的等值匹配，是都要写到on里面呢，还是只把一个条件写到on里面，其他条件写到where部分？为了同时回答这两个问题，我来构造两个表a和b：

表a和b都有两个字段f1和f2，不同的是表a的字段f1上有索引。

然后，我往两个表中都插入了6条记录，其中在表a和b中同时存在的数据有4行。

@郭健 同学提到的第二个问题，其实就是下面这两种写法的区别：

我把这两条语句分别记为Q1和Q2。

首先，需要说明的是，这两个left join语句的语义逻辑并不相同。

我们先来看一下它们的执行结果。

create table a(f1 int, f2 int, index(f1))engine=innodb;create table b(f1 int, f2 int)engine=innodb;insert into a values(1,1),(2,2),(3,3),(4,4),(5,5),(6,6);insert into b values(3,3),(4,4),(5,5),(6,6),(7,7),(8,8);select * from a left join b on(a.f1=b.f1) and (a.f2=b.f2); /Q1/select * from a left join b on(a.f1=b.f1) where (a.f2=b.f2);/Q2/图1 两个join的查询结果可以看到：

语句Q1返回的数据集是6行，表a中即使没有满足匹配条件的记录，查询结果中也会返回一行，并将表b的各个字段值填成NULL。

语句Q2返回的是4行。

从逻辑上可以这么理解，最后的两行，由于表b中没有匹配的字段，结果集里面b.f2的值是空，不满足where 部分的条件判断，因此不能作为结果集的一部分。

接下来，我们看看实际执行这两条语句时，MySQL是怎么做的。

我们先一起看看语句Q1的explain结果：

图2 Q1的explain结果可以看到，这个结果符合我们的预期：

驱动表是表a，被驱动表是表b；

由于表b的f1字段上没有索引，所以使用的是Block Nexted Loop Join（简称BNL） 算法。

看到BNL算法，你就应该知道这条语句的执行流程其实是这样的：

  1. 把表a的内容读入join_buffer 中。

因为是select * ，所以字段f1和f2都被放入join_buffer了。

  1. 顺序扫描表b，对于每一行数据，判断join条件（也就是a.f1=b.f1 and a.f2=b.f2)是否满足，满足条件的记录, 作为结果集的一行返回。

如果语句中有where子句，需要先判断where部分满足条件后，再返回。

  1. 表b扫描完成后，对于没有被匹配的表a的行（在这个例子中就是(1,1)、(2,2)这两行），把剩余字段补上NULL，再放入结果集中。

对应的流程图如下：

图3 left join -BNL算法可以看到，这条语句确实是以表a为驱动表，而且从执行效果看，也和使用straight_join是一样的。

你可能会想，语句Q2的查询结果里面少了最后两行数据，是不是就是把上面流程中的步骤3去掉呢？我们还是先看一下语句Q2的expain结果吧。

图4 Q2的explain结果这里先和你说一句题外话，专栏马上就结束了，我也和你一起根据explain结果“脑补”了很多次一条语句的执行流程了，所以我希望你已经具备了这个能力。

今天，我们再一起分析一次SQL语句的explain结果。

可以看到，这条语句是以表b为驱动表的。

而如果一条join语句的Extra字段什么都没写的话，就表示使用的是Index Nested-Loop Join（简称NLJ）算法。

因此，语句Q2的执行流程是这样的：顺序扫描表b，每一行用b.f1到表a中去查，匹配到记录后判断a.f2=b.f2是否满足，满足条件的话就作为结果集的一部分返回。

那么，为什么语句Q1和Q2这两个查询的执行流程会差距这么大呢？其实，这是因为优化器基于Q2这个查询的语义做了优化。

为了理解这个问题，我需要再和你交代一个背景知识点：在MySQL里，NULL跟任何值执行等值判断和不等值判断的结果，都是NULL。

这里包括， select NULL = NULL 的结果，也是返回NULL。

因此，语句Q2里面where a.f2=b.f2就表示，查询结果里面不会包含b.f2是NULL的行，这样这个left join的语义就是“找到这两个表里面，f1、f2对应相同的行。

对于表a中存在，而表b中匹配不到的行，就放弃”。

这样，这条语句虽然用的是left join，但是语义跟join是一致的。

因此，优化器就把这条语句的left join改写成了join，然后因为表a的f1上有索引，就把表b作为驱动表，这样就可以用上NLJ 算法。

在执行explain之后，你再执行show warnings，就能看到这个改写的结果，如图5所示。

图5 Q2的改写结果这个例子说明，即使我们在SQL语句中写成left join，执行过程还是有可能不是从左到右连接的。

也就是说，使用left join时，左边的表不一定是驱动表。

这样看来，如果需要left join的语义，就不能把被驱动表的字段放在where条件里面做等值判断或不等值判断，必须都写在on里面。

那如果是join语句呢？这时候，我们再看看这两条语句：

我们再使用一次看explain 和 show warnings的方法，看看优化器是怎么做的。

select * from a join b on(a.f1=b.f1) and (a.f2=b.f2); /Q3/select * from a join b on(a.f1=b.f1) where (a.f2=b.f2);/Q4/图6 join语句改写可以看到，这两条语句都被改写成：

执行计划自然也是一模一样的。

也就是说，在这种情况下，join将判断条件是否全部放在on部分就没有区别了。

Simple Nested Loop Join 的性能问题我们知道，join语句使用不同的算法，对语句的性能影响会很大。

在第34篇文章《到底可不可以使用join？》的评论区中，@书策稠浊 和 @朝夕心 两位同学提了一个很不错的问题。

我们在文中说到，虽然BNL算法和Simple Nested Loop Join 算法都是要判断M*N次（M和N分别是join的两个表的行数），但是Simple Nested Loop Join 算法的每轮判断都要走全表扫描，因此性能上BNL算法执行起来会快很多。

为了便于说明，我还是先为你简单描述一下这两个算法。

BNL算法的执行逻辑是：

  1. 首先，将驱动表的数据全部读入内存join_buffer中，这里join_buffer是无序数组；

  2. 然后，顺序遍历被驱动表的所有行，每一行数据都跟join_buffer中的数据进行匹配，匹配成功则作为结果集的一部分返回。

select * from a join b where (a.f1=b.f1) and (a.f2=b.f2);Simple Nested Loop Join算法的执行逻辑是：顺序取出驱动表中的每一行数据，到被驱动表去做全表扫描匹配，匹配成功则作为结果集的一部分返回。

这两位同学的疑问是，Simple Nested Loop Join算法，其实也是把数据读到内存里，然后按照匹配条件进行判断，为什么性能差距会这么大呢？解释这个问题，需要用到MySQL中索引结构和Buffer Pool的相关知识点：

  1. 在对被驱动表做全表扫描的时候，如果数据没有在Buffer Pool中，就需要等待这部分数据从磁盘读入；

从磁盘读入数据到内存中，会影响正常业务的Buffer Pool命中率，而且这个算法天然会对被驱动表的数据做多次访问，更容易将这些数据页放到Buffer Pool的头部（请参考第35篇文章中的相关内容)；

  1. 即使被驱动表数据都在内存中，每次查找“下一个记录的操作”，都是类似指针操作。

而join_buffer中是数组，遍历的成本更低。

所以说，BNL算法的性能会更好。

distinct 和 group by的性能在第37篇文章《什么时候会使用内部临时表？》中，@老杨同志 提了一个好问题：如果只需要去重，不需要执行聚合函数，distinct 和group by哪种效率高一些呢？我来展开一下他的问题：如果表t的字段a上没有索引，那么下面这两条语句：

的性能是不是相同的?首先需要说明的是，这种group by的写法，并不是SQL标准的写法。

标准的group by语句，是需要在select部分加一个聚合函数，比如：

这条语句的逻辑是：按照字段a分组，计算每组的a出现的次数。

在这个结果里，由于做的是聚合计算，相同的a只出现一次。

select a from t group by a order by null;select distinct a from t;select a,count(*) from t group by a order by null;备注：这里你可以顺便复习一下第37篇文章中关于group by的相关内容。

没有了count(*)以后，也就是不再需要执行“计算总数”的逻辑时，第一条语句的逻辑就变成是：

按照字段a做分组，相同的a的值只返回一行。

而这就是distinct的语义，所以不需要执行聚合函数时，distinct 和group by这两条语句的语义和执行流程是相同的，因此执行性能也相同。

这两条语句的执行流程是下面这样的。

  1. 创建一个临时表，临时表有一个字段a，并且在这个字段a上创建一个唯一索引；

  2. 遍历表t，依次取数据插入临时表中：

如果发现唯一键冲突，就跳过；

否则插入成功；

  1. 遍历完成后，将临时表作为结果集返回给客户端。

备库自增主键问题除了性能问题，大家对细节的追问也很到位。

在第39篇文章《自增主键为什么不是连续的？》评论区，@帽子掉了 同学问到：在binlog_format=statement时，语句A先获取id=1，然后语句B获取id=2；接着语句B提交，写binlog，然后语句A再写binlog。

这时候，如果binlog重放，是不是会发生语句B的id为1，而语句A的id为2的不一致情况呢？首先，这个问题默认了“自增id的生成顺序，和binlog的写入顺序可能是不同的”，这个理解是正确的。

其次，这个问题限定在statement格式下，也是对的。

因为row格式的binlog就没有这个问题了，Write row event里面直接写了每一行的所有字段的值。

而至于为什么不会发生不一致的情况，我们来看一下下面的这个例子。

图7 insert 语句的binlog可以看到，在insert语句之前，还有一句SET INSERT_ID=1。

这条命令的意思是，这个线程里下一次需要用到自增值的时候，不论当前表的自增值是多少，固定用1这个值。

create table t(id int auto_increment primary key);insert into t values(null);这个SET INSERT_ID语句是固定跟在insert语句之前的，比如@帽子掉了同学提到的场景，主库上语句A的id是1，语句B的id是2，但是写入binlog的顺序先B后A，那么binlog就变成：

你看，在备库上语句B用到的INSERT_ID依然是2，跟主库相同。

因此，即使两个INSERT语句在主备库的执行顺序不同，自增主键字段的值也不会不一致。

小结今天这篇答疑文章，我选了4个好问题和你分享，并做了分析。

在我看来，能够提出好问题，首先表示这些同学理解了我们文章的内容，进而又做了深入思考。

有你们在认真的阅读和思考，对我来说是鼓励，也是动力。

说实话，短短的三篇答疑文章无法全部展开同学们在评论区留下的高质量问题，之后有的同学还会二刷，也会有新的同学加入，大家想到新的问题就请给我留言吧，我会继续关注评论区，和你在评论区交流。

老规矩，答疑文章也是要有课后思考题的。

在第8篇文章的评论区， @XD同学提到一个问题：他查看了一下innodb_trx，发现这个事务的trx_id是一个很大的数（281479535353408），而且似乎在同一个session中启动的会话得到的trx_id是保持不变的。

当执行任何加写锁的语句后，trx_id都会变成一个很小的数字（118378）。

你可以通过实验验证一下，然后分析看看，事务id的分配规则是什么，以及MySQL为什么要这么设计呢？你可以把你的结论和分析写在留言区，我会在下一篇文章和你讨论这个问题。

感谢你的收听，也欢迎你把这篇文章分享给更多的朋友一起阅读。

上期问题时间上期的问题是，怎么给分区表t创建自增主键。

由于MySQL要求主键包含所有的分区字段，所以肯定是要创建联合主键的。

这时候就有两种可选：一种是(ftime, id)，另一种是(id, ftime)。

如果从利用率上来看，应该使用(ftime, id)这种模式。

因为用ftime做分区key，说明大多数语句都SET INSERT_ID=2;语句B；

SET INSERT_ID=1;语句A；

是包含ftime的，使用这种模式，可以利用前缀索引的规则，减少一个索引。

这时的建表语句是：

当然，我的建议是你要尽量使用InnoDB引擎。

InnoDB表要求至少有一个索引，以自增字段作为第一个字段，所以需要加一个id的单独索引。

当然把字段反过来，创建成：

CREATE TABLE t̀ ̀( ìd ̀int(11) NOT NULL AUTO_INCREMENT, f̀time ̀datetime NOT NULL, c ̀int(11) DEFAULT NULL, PRIMARY KEY (̀ ftime ,̀ ìd )̀) ENGINE=MyISAM DEFAULT CHARSET=latin1PARTITION BY RANGE (YEAR(ftime))(PARTITION p_2017 VALUES LESS THAN (2017) ENGINE = MyISAM, PARTITION p_2018 VALUES LESS THAN (2018) ENGINE = MyISAM, PARTITION p_2019 VALUES LESS THAN (2019) ENGINE = MyISAM, PARTITION p_others VALUES LESS THAN MAXVALUE ENGINE = MyISAM);CREATE TABLE t̀ ̀( ìd ̀int(11) NOT NULL AUTO_INCREMENT, f̀time ̀datetime NOT NULL, c ̀int(11) DEFAULT NULL, PRIMARY KEY (̀ ftime ,̀ ìd )̀, KEY ìd ̀(̀ id )̀) ENGINE=InnoDB DEFAULT CHARSET=latin1PARTITION BY RANGE (YEAR(ftime))(PARTITION p_2017 VALUES LESS THAN (2017) ENGINE = InnoDB, PARTITION p_2018 VALUES LESS THAN (2018) ENGINE = InnoDB, PARTITION p_2019 VALUES LESS THAN (2019) ENGINE = InnoDB, PARTITION p_others VALUES LESS THAN MAXVALUE ENGINE = InnoDB); PRIMARY KEY (̀ id ,̀ f̀time )̀, KEY ìd ̀(̀ ftime )̀也是可以的。

0%