Nested Loop Join
这一章节主要讲解 join 的算法,我想记录一些重点的地方。有趣的是 关于 Nested Loop join 对驱动表为什么小表会更好这个问题,搜遍简中的 blog 都是一些错误的描述而且排名还贼高。而且大家都是互相拷贝。。互相抄内容,错来错去都差不多。
我们基于上面的数据集来探讨这个问题。并且我们暂时假设,我们不会使用到任何索引。
首先需要申明一个重要的点,那些有问题的描述多数在讨论外表有多少行,内部表有多少行。然后为了减少连接次数,所以我们应该在外部用小表作为驱动表去驱动内部的表可以减少连接次数。
这个说法,也不能说不对,但是他肯定不完全对。怎么来定义一个小表,我们不只用行数。因为我们真正在读取数据的时候我们读的是 数据页 行是数据的延伸是 tuple。所以归根到底如果我们要 follow 上面的说法
我们应该说我们应该在外部尽量少的扫描数据页,这样可以减少连接消耗。而不是数据行。
同时我们还需要意识到一点,减少连接消耗的本质。。其实就是减少数据页的扫描。
如果我们拿 R 表做外表 S 表做内部表我们需要扫描的数据总数大概是
M + (m * N)
如果我们拿 S 表做外部表 R 表做内部表我们需要扫描的总数大概是
N + (M * n)
如下图
这样可以看出来,即使我们使用最笨的办法,但是我们将小表放在外面,依然是可以节省不少 io 的。
我们外部 for 循环遍历 500page 然后拿着每一条 40000 * 每一条扫一次 page,R 表有 1000 个 page。数据就是这么来的。
那么有没有更好的办法呢
标签:join,小表,memo,扫描,Join,数据,我们,hash From: https://www.cnblogs.com/piperck/p/16940286.html