in 分布式数据库 数据库 ~ read.

数据库之Join

select * from t1, t2 where t1.c1 = t2.c2
select * from t1 left join t2 on t1.c1 = t2.c2
select * from t1 right join t2 on t1.c1 = t2.c2
select * from t1 where t1.c1 [NOT]IN (select c2 from t2)

基本概念

Join表示表的关联操作,它相当于将两张表进行笛卡尔积运算,根据关联条件进行过滤,得到满足条件的数据结果。
Join语法通常为依据等值条件做连接操作,另一种是子查询方式,子查询是指嵌套在 SQL 内部的查询块,子查询的结果作为输入,填入到外层查询中,从而用于计算外层查询的结果。

连接类型

  • Join
    2个数据源的键值一一比较,返回相匹配的记录结果;
    • InnerJoin
      内连接,可写为INNER JOINJOIN,左表记录与右表中存在匹配记录时,返回结果行。
  • OuterJoin
    2个数据源键值一一比较,返回相互匹配的;但如果在另外一个表中没有找到匹配的也返回记录。
    • LeftJoin
      左连接,可写为LEFT JOINLEFT OUTER JOIN,左表中返回所有的行,即使右表中没有匹配记录,如果没有匹配记录,返回结果为NULL。
    • RightJoin
      右连接,可写为RIGHT JOINRIGHT OUTER JOIN,右表中返回所有的行,即使左表中没有匹配的记录,如果没有匹配记录,返回结果为NULL。
    • FullJoin
      全连接,可写为FULL JOINFULL OUTER JOIN,结合LeftJoin和RightJoin的功能结果。

join

  • SemiJoin
    半连接,对于外部查询的每个键值,当在内部查询中找到第一匹配的键值,就立即返回,不再继续查找其它匹配的键值,且右表一条记录也不会返回。常用于子查询Exists,In中;

    EXIST运算符用于判断查询子句是否有记录,如果有一条或多条记录存在返回True,否则返回False。

  • AntiJoin
    找到满足条件的不返回,不满足条件的返回。常用于!=,not in,not exists类的查询条件;其逻辑与Join相反。
  • 隐式连接
    不指定Join关键字的情况下执行连接操作;

常识性概念

  1. Probe表:通常表示Join中的左表
  2. Build表:通常表示Join中的右表
  3. Join计算的核心:将Probe表和Build表中每一行数据进行对比,如果符合关联条件,则将两行数据关联,得到一行结果

实现方式

通过Join计算的核心,可以知道需要进行大量的数据扫描操作,所以不同的Join算法为了适应不同的场景,提供最高效的解决方式。

  • HashJoin
    散列连接,适用于大数据集连接时的场景,会选择两个表中比较小的表,利用连接键在内存中建立Hash表,然后逐行扫描另一个大表的数据并探测Hash表,找到与Hash表中的数据匹配的行。
    • NormalJoin
      普通的HashJoin算法,常用于两个大表之间的关联。
    • InvisibleJoin
      常用于大表与多个码表之间的关联。
      存在的隐含问题:数据倾斜很严重,内存放不下Hash表,Hash表键值冲突;
      优势场景:两个特别大的表的连接,一个特别大的表与一个小表的连接;
  • NestedLoopJoin
    嵌套循环连接,采用内外表嵌套扫描逐行比较的方式,即在一个嵌套循环中,内表被外表驱动,外表返回的每一行数据都要在内表中检索是否有与之匹配的行。
    由于嵌套循环扫描的影响,复杂度为O(N*M),对于大数据量的表不适合用这种方式,一般会通过在内表上建立索引来提升性能;
    优势场景:适用于被连接数据子集较小的场景。
  • MergeJoin
    排序合并连接,首先会按照两个表的关联字段对两表进行排序,排好序后,分别从两个表中取出一行进行匹配,如果匹配则得到一行结果;如果不匹配则将较小的那行数据丢掉继续匹配下一行,直到将两表的数据取完。
    它的大部分性能开销都是消耗在排序上,成为同等条件下差于HashJoin的一个原因;
    但是,如果源数据已经过排序,那么在经过MergeJoin就不需要重新排序,这时性能会高于HashJoin;
    当表特别小或者特别巨大的时候,使用全表扫描的方式可能会比使用索引进行范围扫描更快,所以性能可能会高于NestedLoopJoin;
对于结果集很大的情况,MergeJoin需要进行排序,效率不会很高,而NestedLoopJoin基于嵌套循环的查询方式,更加不适合大数据集的连接,HashJoin的出现就是为了处理这种复杂的查询而产生,特别是对于一个大表和一个小表的情况,只要将小表经过Hash放入内存,扫描一遍大表也就得到结果(基本上只需要两表各扫描一遍)。

总体来说:HashJoin只适用于等值连接,对于>, <, <=, >=这样的查询连接还是需要NestedLoopJoin这种通用的连接算法来处理。如果连接key本来就是有序的或者需要排序,那么可能用MergeJoin的代价会比HashJoin更小,此时MergeJoin会更有优势。