知识卡片

普通读书笔记卡 · 2281.m.2.c

归并连接利用有序输入

理解等级:中级

两侧按连接键排序后,比较当前键:较小的一侧向前推进,相等时组合两组行。索引若已提供相同顺序,可免额外排序;有序条件不满足时,不能只看到线性归并就忽略前置排序成本。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 5 处

    参考来源

    - 位置:《TiDB源码阅读系列文章》第15章《TiDB 源码阅读系列文章(十五)Sort Merge Join》(来源项目:book-sources;源文件:extracted/TiDB源码阅读系列文章/_epub-src/OEBPS/Text/TiDB 源码阅读系列文章(十五)Sort Merge Join.html;阅读段落 2,6,9,10,11;均为书中版本) - 结论依据:原文对归并连接利用有序输入给出上述机制或边界;本卡把已读说明整理为可独立理解的解释。 - 原始内容:在开始阅读源码之前, 我们来看看什么是 Sort Merge Join (SMJ),定义可以看 wikipedia。简单说来就是将 Join 的两个表,首先根据连接属性进行排序,然后进行一次扫描归并, 进而就可以得出最后的结果。这个算法最大的消耗在于对内外表数据进行排序,而当连接列为索引列 …… 顺序读取外表 A 直到 join-keys 中出现另外的值,把相同 keys 的行放入数组 a1,同样的规则读取内表 B,把相同 keys 的行放入数组 a2。如果外表数据或者内表数据读取结束,退出。 …… cmpResult > 0, 表示 v1 大于 v2,把当前 a2 的数据丢弃,从内表读取下一批数据,读取方法同 1。重复 2。 …… cmpResult < 0, 表示 v1 小于 v2,说明外表的 v1 没有内表的值与之相同,把外表数据输出给 resultGenerator(不同的连接类型会有不同的结果输出,例如外连接会把不匹配的外表数据输出)。 …… cmpResult == 0, 表示 v1 等于 v2。那么遍历 a1 里面的数据,跟 a2 的数据,输出给 resultGenerator 作一次连接。