透析MySQL 8.0 hash join中的笛卡尔积缺陷

2022-01-12 00:00:00 执行 成本 笛卡尔 关联 顺序

 

       在发现了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


相关文章