数据库中的表连接算法

May 10, 2016


单表扫描算法

常用的单表扫描算法

  • 全表扫描表数据
  • 局部扫描表数据

两表连接算法

基本的两表连接算法

循环

简单的二重循环。

for row1 in t1:
    for row2 in t2:
        if row1, row2 satisfies join conditions:
            join row1, row2

这里是以元组为单位的连接。 但是元组是从一个内存页面获取过来的,而内存页面是通过以为单位申请的多个。

然后改进一下就成了以块为单位读入,这样一次读取多个页面。

还有基于索引做改进,因为索引中的元祖相同值都放在一起,可以有效减少 IO。 然后查找索引还能加速,O(logn)?

排序归并连接算法

这个没怎么看懂,好像归并排序一样,从最小的开始并起来。那么为什么要选有序的呢?

Hash 连接算法

用连接列作为 Hash 关键字,对内表建立 Hash 表,然后对外表 Hash,一映射就能连接了。 这样乍一看效率是非常高的,如果能保证桶的分布均匀的话,不过太消耗内存。O(n)? 然而 MySQL 中只有第一种算法。