加入收藏 | 设为首页 | 会员中心 | 我要投稿 聊城站长网 (https://www.0635zz.com/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 站长学院 > MySql教程 > 正文

MySQL和PostgreSQL在多表连接算法上的差别有哪些

发布时间:2022-01-10 16:15:42 所属栏目:MySql教程 来源:互联网
导读:这篇文章主要介绍MySQL和PostgreSQL在多表连接算法上的差异有哪些,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完! 我们知道mysql没有hash join,也没有merge join,所以在连接的时候只有一种算法nest loop join,nl join使用驱动
      这篇文章主要介绍MySQL和PostgreSQL在多表连接算法上的差异有哪些,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完!
 
       我们知道mysql没有hash join,也没有merge join,所以在连接的时候只有一种算法nest loop join,nl join使用驱动表的结果集作为外表到内表中查找每一条记录,如果有索引,就会走索引扫描,没有索引就会全表扫。
 
      nl join并不能适用所有场景,例如两个表都是很大的表的等值连接,这种场景是hash join所擅长的,而且是生产环境中最常见的场景。mysql在这个时候就显得力不从心,所以在使用mysql时我们可能会制定如下规范:禁止使用大表连接。这也是mysql永远的痛。不过据说8.0版本已经将hash join作为一个需求纳入了,我们拭目以待吧。
 
      相比起来,postgresql的优化器十分的强劲。支持了hash join、nest loop、sort merge join,扫描算法支持seq scan、index scan、index only scan,同时还支持堆内元组技术(HOT)。在postgresql11版本中还加入了并行扫描,亲测在两张大表(一张1.6亿一张256万数据,均无索引)做join结果集300多万,pg开启并行大概20s以内就跑出结果,强于其他数据库。
 
       贪心算法的前提是确定源点,算法思想也和名字很像,只找当前步骤的最优解,是一种深度优先的解法,算法复杂度是O(n²)找到后继续深入下一层,直至达到终点。比如上图从A到G,使用贪心算法的路径是A->B->D->G算法,代价是1+2+6=9,很明显这并不是最优解,最优解我们肉眼可以看出来是A->C->F->G,代价是2+3+1=6。所以我们看贪心算法并不是全局最优的,但是优点是算法复杂度低,mysql可能也是基于这种考虑而使用贪心算法,不想将时间都浪费在计算代价上了,因为如果关联的表特别多,那么代价的计算是指数级增长,所以贪心算法虽然不是最优解,但是在连接表的数量很大的情况下具有一定优势。
 
再来看看pg使用的动态规划,动态规划解决的是无源最短路径问题,我们想象一下其实多表连接本身就是一个无源最短路径问题,只是mysql在进行连接的时候随机选了一个作为起点而已。
 
对于第一行,依次计算ab,ac,ad,ae的距离是否有第三个节点进行替换,对于ab计算发现,ab<ac+cb&&ab<ad+db&&ab<ae+eb,所以ab不用更新,同理ac也不用更新,对于ad,计算得到ab+bd=6,ac+cd=∞,ae+ed=∞,于是更新ad=6,同理计算更新ae=8;然后依次计算下面几行。全部遍历完,经历了三层循环,算法复杂度是O(n³)。pg使用该算法能够得到最优执行计划,但是在表的个数很多时计算代价所付出的代价也很大。

(编辑:聊城站长网)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!