我的Join查询是如何得出结果的?

2020-08-08

Join Algorithms

在需要连接多表数据时,我们通常会使用到JOIN操作。

Nested Loop Join

Basic Nested Loop Join

假设现在有两个关系对集合,RS,我们需要将它连接起来,连接通过一定的条件来指定,这个条件我们称为Join Predicate,即连接谓词:

JP(r, s) := r.x == s.x

这个连接谓词表明RS依靠字段x相等作为条件进行连接,当满足条件时,JP(r, s)返回为True,否则为False

下面用伪代码表述Nested Loop Join的处理过程:

# R
# S
# JP(r, s) := r.x == s.x

def nested_loop_join(R, S, JP(r, s)):
    for r in R:
        for s in S:
            if JP(r, s):
                outupt((r, s))

可以看出Nested Loop Join的处理过程即是两个关系对集合RS的求Cross Product过程,因此若R中有n个关系对,S中有m个关系对,他们的处理复杂度即为O(m * n)

Nested Loop Join的优势在于它不仅可以在等值连接(EquiJoin)中使用,还可以处理其他非等值连接:

  • 在NLJ中无需关注判定式JP(r, s)的实现
  • 对于非等值连接,只判定式内部实现对应Join Predicate即可,外层循环无感知。如:JP(r, s) := r.x <= s.x

Indexed Nested Loop Join

现在输入的情况稍作改变,我们不仅有RS和连接谓词JP(r, s),还知道在其中一个关系集合,无论是R还是S,的连接谓词的列x上有对应的索引:

IndexOnRX := catelog.get(indexes, R.x)

IndexOnRX现在可以视为一个Rx列的索引查询方法,它可以接收查询值,并且返回一个集合,代表集合中的元素存在于R中。

下面用伪代码表述Indexed Nested Loop Join的处理过程:

# S
# JP(r, s)
# IndexOnRX

def indexed_nested_loop_join(IndexOnRX, S, JP(r, s)):
    for s in S:
        query_result_set = IndexOnRX(s.x)
        if query_result_set != None:
            output({s} * query_result_set)

与NLJ不同,INLJ通过遍历其中1个关系对集合S,使用对应的索引查询得到另一个查询集合R的子集,如果有符合的case,将{s} * query_result_set结果追加到最后输出的集合中。因此在INLJ中,因为只遍历了其中一个关系对集合,查询复杂度可以视为O(n)

Hash Join

现在我们同样有两个关系对集合RS,一个连接谓词JP(r, s) := r.x == s.x
下面用伪代码来表述Simple Hash Join的处理过程:

# R
# S
# JP(r, s) := r.x == s.x

def simple_hash_join(R, S, JP(r, s)):
    indexOnRX := build_ht(R.x)
    for s in S:
        query_result_set = IndexOnRS(s.x)
        if query_result_set != None:
            output({s} * query_result_set)

可以看出在循环和判定上,SHJ和INLJ非常相似,最大的区别在于SHJ使用了一个临时生成的Hash内存表作为IndexOnRS依据。由于使用Hash Table,因此SHJ相比之前的NLJ而言缺少了非等值查询的支持。同时在查询复杂度上,SHJ先遍历其中一个关系对集合生成HT,再遍历另一个关系对进行判定,因此为O(m + n)

Sort-Merge Join

现在我们有两张表CustomerCity,我们需要通过Join操作获取每个customer所在的city。

namestreetcityIDcityIDcity
n1s100A
n2s201B
n3s303C
n4s415D
n5s517E
n6s659F
n7s75
n8s87
n9s99
n10s109
n11s119

我们按照以下原则进行Merge Join

  • 使用两个指针,分别指向两表的cityID字段
  • 当指针对应的值相等时,output一行结果
  • 指针需要移动至下一行时,优先移动当前指向值较小的指针,若值相等时优先移动指向Customer表的指针

输出结果为:

namestreetcityIDcity
n1s10A
n2s20A
n3s30A
n4s41B
n5s51B
n6s65D
n7s75D
n8s87E
n9s99F
n10s109F
n11s119F

注意到这种Merge操作的前提是两表的连接谓词所在字段必须是排序的,因此这种连接算法称为Sort-Merge Join

根据以上条件写出伪代码:

# R
# S
# JP(r, s)

def sort_merge_join(R, S, JP(r, s)):
    sort(R on R.x)
    sort(S on S.x)
    pointer_r = R[0]
    pointer_s = S[0]

    while pointer_r != R.end and pointer_s != S.end:
        if pointer_r.x == pointer_s.x:
            output((pointer_r, pointer_s))

        if pointer_r.x <= pointer_s.x:
            pointer_r++
        else:
            pointer_s++

    # handle rest row here

要注意如果将Customer表与City表位置互换,并且保持优先移动左表(City)表指针,我们输出的结果将会是不正确的。

另外,如果两表的排序字段都不是主键或唯一,输出的结果也会有遗漏的case。

因此,Sort-Merge Join算法有必须满足的前提条件:

  • Join字段在其中一个表中必须唯一
  • 保持优先移动ref表(即Join字段非唯一的表)

最后估算查询复杂度,需要先进行排序,为O(nlogn)的复杂度,然后双指针遍历两表为O(m+n)的复杂度。

Conclusion

Join操作使用的基础算法:

  • Nested Loop Join,可以视为两表相乘,嵌套循环逐行检查是否满足Join条件
  • Indexed Nested Loop Join,遍历部分表,并用遍历结果作为索引查询条件,借助索引查询
  • Hash Join,可以视为INLJ的特殊情况,区别在于Hash Join使用现有或临时生成的Hash值作为索引,此时不支持非等值连接
  • Sort-Merge Join,限定条件比较多,先根据Join字段排序,再合并两表,同样不支持非等值连接,否则会退化为NLJ