透析MySQL 8.0 hash join中的笛卡尔积缺陷
在发现了MySQL 8.0 hash join的一个比较惨的现象之后，在本周一晚上发布了关于这个现象的文章，MySQL8.0 Hash JOIN 严重缺陷，周二，对这个现象背后的原因进行了研究，对问题有了初步的定位。因为作者是运维工作师，运维才是主业，研究mysql源码只是为了解决主业过程中遇到的问题，因为时间跟精力的原因，没有马上对这个问题的认知做更多分享。现在是周末，将更进一步的认知写出来，分享给大家，希望大家对这个现象背后的原因有更深入地了解，以助于我们更好地用好/运维好mysql.
之前文章中举的列子，过于简单，而TPCH测试中的案例又稍微麻烦些，得做些准备。现在再重新举个相对比较好的例子，以便更利于模拟以及观察现象。还是之前的3个表，但这次数据准备得多点：
create table t1 ( t1_id varchar(20),t1_name varchar(20) ,t1_addr varchar(20));
create table t2 ( t2_id varchar(20),t2_name varchar(20) ,t2_addr varchar(20));
create table t3 ( t3_id varchar(20),t3_name varchar(20) ,t3_addr varchar(20));
T1表：T1表总数1000行。
insert into t1 values('a0','name0','addr0');
insert into t1 values('a1','name1','addr1');
insert into t1 values('a2','name2','addr2');
insert into t1 values('a3','name3','addr3');
insert into t1 values('a4','name4','addr4');
.....................................................................
....................................................................
insert into t1 values('a997','name997','addr997');
insert into t1 values('a998','name998','addr998');
insert into t1 values('a999','name999','addr999');
T2表： T2表总数50000行。
insert into t2 values('a0','name0','addr0');
insert into t2 values('a1','name1','addr1');
insert into t2 values('a2','name2','addr2');
insert into t2 values('a3','name3','addr3');
........................................................................
................................................................................
insert into t2 values('a49998','name49998','addr49998');
insert into t2 values('a49999','name49999','addr49999');
T3表：T3表的总数是5100行。
insert into t3 values('a0','name0','addr0');
insert into t3 values('a1','name1','addr1');
insert into t3 values('a2','name2','addr2');
..................................................................
..........................................................
insert into t3 values('a5097','name5097','addr5097');
insert into t3 values('a5098','name5098','addr5098');
insert into t3 values('a5099','name5099','addr5099');
为了勾起大家的好奇心，以便可以认真地看下去，这里抛出一个疑问，T1表造1000行，T2表造50000行，T3表为啥造5100，而不是5000 ，5100跟5000有区别吗？继续读下去， 5000跟5100这两个数字的差别，含有这个文章的本质内容，本文要讲得就是这个。
然后执行下面这个SQL, 执行时间1.30秒， 这个数据库是debug模式安装的，且跑在自己的虚拟机上， 所以比较慢，正常情况，这点数据量做正常的hash jion ，要不了1.3秒。
mysql> select count(*) from t1,t2,t3 where t1_id=t2_id and t2_addr=t3_addr;
+----------+
| count(*) |
+----------+
| 1000 |
+----------+
1 row in set (1.30 sec)
我们看看执行计划：
表的关联顺序是T1->T2->T3，这是一个非常正常的关联顺序，也是我们想要的关联顺序，特别提一下，在上一篇文章中，原文“目前简单地猜测（纯属肤浅猜测，还没有做源码级研究），mysql做hash jion 的时候， 只看表的数量，小表在前，大表在后，因为T2表的数量多，所以放在后，而让没有直接等于关系的T1表跟T3表去做笛卡尔积关联.”,当时确实是肤浅猜测，这个案例的关联顺序是T1->T2->T3,T2大并没有放在后，之前的猜测被推翻，现纠正，肤浅地低估了优化器的复杂程度。不过，这个规则在优化器中确实是存在，后面会讲到。
但是，现在作者比较讨厌这个正常的关联顺序，希望它有问题，该怎么办?
给某个表加数据来干扰执行计划？ 确实可以这么做，但现在想做一个更另类的操作------删除数据。 按照常理，表越小，执行越快。但如果表小了，反而变慢了，那就不正常了，肯定是某个环节出了问题。
现在来制造问题， 不是加数据，而是删除数据，T3表当前有5100行，我们来删除100行记录， 让它变成5000行，我们来观察情况是否有变：
mysql> delete from t3 order by t3_id desc limit 100;
Query OK, 100 rows affected (0.44 sec)
mysql> select count(*) from t3;
+----------+
| count(*) |
+----------+
| 5000 |
+----------+
1 row in set (0.37 sec)
然后执行之前的SQL,观察是否发生些什么？
mysql> select count(*) from t1,t2,t3 where t1_id=t2_id and t2_addr=t3_addr;
+----------+
| count(*) |
+----------+
| 900 |
+----------+
1 row in set (30.87 sec)
这个SQL的执行时间从1.3秒变成了30秒，因为我们删除了100行的数据，SQL的执行速度反而下降了，那一定是执行计划变了，变成了什么样子呢？
这次， 是T1->T3->T2, 藐视又回到按照表的大小顺序进行关联了（玄乎？）。 但T1跟T3之间，在这个SQL中，T1跟T3本身没有直接的关联关系，所以造成了笛卡尔积关联，关联后将产生1000 * 5000 条记录，这是SQL执行时间从1.3秒变成30秒的直接原因。
T3表的数据从5100变成5000，导致SQL的执行计划发生了变化。 对数据进一步变化是否会对执行计划产生影响有兴趣的朋友，可以自己测试一下。例如将T3表的数据量从5000继续往下降，或者从5100继续往上涨 ， 看看是否会导致执行计划的改变。
以上是实验现象， 现在来透过现象去了解背后的原因，作者将目前了解的原理跟大家描述一下（补充说明：是基于现有版本的hash jion，不涉嵌套关联等其他规则）。
1. 首先优化器在编排表的关联顺序之前，先把要关联的表进行排序，有依赖关系的话需要优先确定表的依赖关系，如外连接中的依赖关系，嵌套关联中ref访问等，依赖关系影响排序位置。如果没有依赖关系，按照表的数量进行排序，因为T1,T2,T3表之间的关联，不是外连接，也没有索引，所以按照大小排定顺序，顺序是t1->t3->t2. 我们把这个顺序命名为tab_ref_order
2. 然后优化器才进行表关联顺序的编排，规则如下：
首先取出T1表，确定T1表的访问方式， 没有索引，只能全表扫描，扫描成本计算方式如下：
IO成本+取数据的成本。 因为表很小，IO成本比较小，主要是取数成本。在通过explain format=tree命令 的输出中，显示T1的cost为101.25. 由表的行数1000*0.100000000....1（我们把它当成0.1后,也就是100） 计算得出取数成本100（cpu成本）， 再加上IO成本1， 总共101.
接下来，T1表选择先计算跟T3表关联的成本（因为在前面提到的tab_ref_order顺序中，顺序为T1->T3->T2），因为表T1 跟T3之间没有关联关系，所以做笛卡尔积关联，T3跟T1关联后的结果是5000*1000，也就是500万，取数成本为50万，再加上表T1,表T3的IO成本，总成本就是执行计划图中显示的500105.88。（因为IO成本占比实在太小，后面直接忽略这部分）。
然后，再跟T2表进行关联，关联成本计算完毕之后，次得出这三个表之间关联的全路径T1->T3->T2的关联成本，方法同前，因为表T1跟T3表笛卡尔积关联，关联后记录数为500万，表T2的总数为50000, 所以取数成本就是500百万*5万*0.1系数=250亿。我们再来看上面出现过的T1->T3->T2执行计划图,完整路径的总代价为251亿（有差别是因为浮点计算，还有系数按照0.1计算，而不是0.1........1）。
在次全路径计算完成之后，再回退到上一层（执行计划生成用得是递归算法，到顶之后回退），于是选择T2表跟T1表进行关联，这一步计算完成之后，可能就决定了T1表到底跟T2表关联，还是跟T3表进行关联。（为什么说可能，因为可能会进行全路径成本的比较，也可能不需要，这就是优化器“偷懒”的操作，规则是局部成本优。如果T1->T2的关联成本优于T1->T3,则继续计算全路径T1->T2->T3三表关联的成本，如果T1->T2的关联成比T1->T3高，直接抛弃，不再扩展这条线路上的路径）。
下面我们来计算T1->T2的关联成本，T1表1000，T2表50000，笛卡尔积之后是5000万，但是T1跟T2之间有等于条件，所以会产生过滤，过滤效果怎么计算？ 因为表T2的T2_id没有索引，怎么去估算这个T1_id=T2_id条件的过滤效果? 所以问题就出现在这里， MySQL对无法估算过滤效果的过滤条件，给一个统一的默认值，这个默认值就是0.1f. 所以MYSQL优化器认为T1跟T2关联后会产生比500万条还多一点点的记录（浮点计算的原因），认为比T1表跟T3表做笛卡尔积关联后的数量多（T1跟T3表关联后是500万，看到这里，可能会明白这个案例T3表的数据量是精准设计的），所以优化器选择了将T1表与T3表进行笛卡尔积的关联。因此，如果T3的数量再大一些，表T1跟表T3关联后的笛卡尔积的数量将超过500万， 那优化器将选择T1表跟T2表进行关联。 但实际上， T1表跟T2表关联后的记录才1000条， 因为优化器没有办法知道关联后到底会有多少条记录，所以给了一个默认值0.1系数，按照十分一的比例进行过滤。
上面只是理论分析了T1表跟T2表关联的成本，我们来看一下T1跟T2表的确认的实际成本，这次需要通过关键字straight_join强制指定关联顺序，不然优化器会选择T1跟T3表做笛卡尔积关联。
explain format=tree select count(*) from t1 straight_join t2 straight_join t3 where t1_id=t2_id and t2_addr=t3_addr;
表的关联顺序为T1->T2->T3, T1跟T2表关联后的成本为:
cost=5023259.16, rows=5023100
而按照T1->T3->T2关联顺序进行关联， 则如下（这个图片在前面出现过，现重新再拿来对比）
表T1->T3关联后的成本为：
cost=500105.88, rows=5000000
进行比较，cost比较：500105.88<5023259.16, 行数比较5000000<5023100 , 所以优化器选择了T1->T3表进行笛卡尔积关联，但这两个不同路径（或者方案）的执行成本已经非常接近，所以当T3表再增大一点点，在本次测试案例中，是将其数量从5000，变成5100之后， 优化器将选择T1表将跟T2表进行关联，这样就出现了表的数量增加了，执行速度反而变快了的“奇怪现象”。
到这里，大家应该比较清楚地了解hash join 过程中，有可能产生笛卡尔积关联的原因了。 简单地总结一下：就是两个表做hash join的时候，在没有其他信息可以帮助做出关联条件的过滤效果的估计的时候，采用默认值0.1f,也就是10%的过滤，这个值在演示案例中，被严重低估（T1表跟T2表关联后的结果只有1000条，但优化器按照笛卡尔积的数量乘以0.1去估算，也就是500万，所以选择宁愿让T1跟T3表做笛卡尔积关联，这是一个误判）。至于为什么这个值为10%，作者大胆猜测，可能mysql的优化器开发人员认为------如果两个表关联，过滤比例超过笛卡尔积的10%，则认为有比较好的过滤效果，正确的用法应该是在关联字段上建上索引，建完索引之后，按照目前的hash join策略，是不会再用hash join关联，也就避免了这个问题。
原文链接：https://mp.weixin.qq.com/s/j_onacVPgBQty9Yn0GdngQ
相关文章