CBO 子查询SQL优化里的First match思想

主要是在semi join/anti join里使用，不管是nested loops,还是hash join,sort merge join,只要走semi join/anti join都有

first match思想，这是一种“短路”算法，快速裁剪，类似加个rownum=1(但是得注意，如果你手动加rownum=1,

oracle数据库则子查询不能unnest,pg,mysql可以，所以，CBO自己能处理，就不要“画蛇添足”),

如下所示：

1）nested loops semi/anti join

必须外表驱动才能走nested loops semi/anti,因为走NL 的outer/semi/anti算法，对于外连接，子查询必须外表驱动才可以，当然，

如果子查询能够先转为view,然后view merge消除子查询，则是普通nested loops join,就没有这个限制了,anti join还是有限制的，

因为anti join等价于left join+where inner.key is null,还是个外连接，所以在MySQL里，外连接，anti join只能外表做驱动表。

驱动表经过条件过滤后的每一行，都会去探测内表，因为有first match,只要匹配到内表一条记录即可返回结果，

这种对于驱动表返回行数很少，就算内表很大，也是效率极好的，当然走NL，要求内表必须走高效索引，按照与外表匹配的列+其它内表过滤条件，

综合考虑，建立索引。

nested loops semi join===>外表每行记录用关联键代入到内表，内表匹配到一行就返回外表结果。

三大数据库基本非相关，相关的现在都可以走这种，当然，必须相关子查询能够查询转换的，相关子查询查询重写复杂的有很多限制。

##只能主表驱动，除非查询重写成view,然后走普通nested loops join才能从表驱动。

nested loops anti join===>外表每行记录用关联键代入到内表，内表匹配到一行就丢弃外表结果。（注意，这里是丢弃，不是返回）

anti join如果能够unnest的，走xx anti join算子，也是转成等值查询的，如果像nested loops anti join,内表也是可以走join key索引的,

但是如果不能unnest,比如像pg的not in子查询都不能unnest，从Filter,则会按照<>计算，所以，如果子查询结果有NULL，则整个查询没有结果返回，

而且子查询关联列也走不了索引，这种，MySQL类似oracle 10g，可以内外表关联列加not null约束或is not null搞定,oracle 11g已经有

hash join anti NA算法。

##必须主表驱动，才能走nested loops anti join，因为改普通join也是外连接+where inner.id is null

当然，如果走FILTER，其实也会有first match。

另外oracle的nested loops semi/anti包括Filter,隐式的Filter如标量子查询，UPDATE SET里的相关子查询，都有subquery cache,内部构建hash表，

1024个buckets,如果外表返回的行join key有序且重复值多，可以大幅度减少子查询执行次数来提高效率。

而MySQL只有非相关子查询且没有unnest走Filter的，然后子查询走materialization的才有subquery cache。

pg的子查询没有subquery cache,只有普通nested loops join才有memorize（也是cache),如果像标量子查询要利用到cache提高效率，

可以使用lateral join,也可以改成普通join，但是必须走nested loops才行。

2）hash join semi/anti以及right semi/anti

前面的nested loops semi/anti join是驱动表返回行很少，内表走高效索引效率高，但是当驱动表返回行数很多，或内表没有高效索引情况下呢？

很显然，内表查询走索引，然后回表随机读，这个随机读影响很大，外表返回行数和性能是线性关系，如果外表是大表，返回行很多，

或外表是小表，但是查询的返回行比例比较大，比如超过10%，

内表又没有高效索引，比如内表关联列有隐式类型转换，这时候，HASH JOIN就是很好的选择了，HASH JOIN作为大数据量运算的首选算法，有些要求：

2.1)必须等值JOIN

所以，MySQL那种拉跨的hash join算法，不等值的就是先笛卡尔积无条件hash join,效率极低，临时数据容易让磁盘空间暴增

2.2)hash collision碰撞问题

build hash table的时候，如果hash_func(key)的结果重复，一般是key重复，则每个hash bucket存放的就是链表，如果每个hash bucket分布很不均，

很多bucket里存放很长的链表，最差是全部重复，只有一个hash bucket里有数据，则hash join性能会蜕化，扫描某些hash bucket里链表数目多的，

类似nested loops,当然，比nested loops稍好的是没有随机读，但是，比如蜕化成一个hash bucket里有数据，则原来的hash function运算，以及

写入hash table的成本加起来，可能抵消了nested loops的内表回表随机读，效率可能不如nested loops了。

解决hash碰撞，要从业务上增加多条件，避免hash表的join key有很多重复值，组合join key选择性越好，则hash join效率越高

2.3)本地内存要足够容纳hash table

不能足够容纳hash table，那会不是optimal hash,要走one pass,少数走multi pass,有grace hash join,hybrid hash join算法，

像oracle这种一般使用hybrid hash join算法，最大化使用本地内存做join,具体就很复杂了，首先对hash table分区，还要有bitmap/bloom Filter

的快速检测是否在磁盘里，然后对probe table结果也要分区，写入磁盘临时空间，然后再读入到本地内存做join，如果读入的本地内存还放不下，还要

递归分区，继续写到磁盘再读回...有多次写入磁盘，写回本地内存

比较的过程，所以时间复杂度就大幅度提升了，不在是简单的O(M+N+..),可能是O((M+N）*P），写盘趟数P最差接近3（grace hash join).。。

所以，SQL最好是按需查找，只查找需要的字段，特别在hash join里可能影响很大，因为hash table的大小是sum(columns_size)*hash_table_rows

像oracle每个会话能使用的本地内存是受PGA自动分布的，具体地，HASH JOIN能使用的是1G大小，手动分配最大是2G-1，并行能够使用更多的本地内存。

MySQL受join_buffer_size,pg受work_mem控制。

综上所述，hash join适合OLAP，OLTP不能大量使用，特别 高并发使用，因为，它是CPU敏感操作，

hash join效率和本地内存大小，hash table的大小以及是否hash碰撞有很大关系，特别适合大数据量运算，但是hash表要小点能全部

放到本地内存里的，也即小结果集vs大结果集的join运算，如果都很大，有磁盘IO操作，效率会迅速下降，。

oracle的hash join，支持hash join right outer/semi/anti，还是hash join anti NA,算子更强大，pg也支持hash join right anti/semi,

而MySQL没有hash join right anti/semi,另外要注意一点，oracle hash join驱动表是hash table,按照hash join顺序来的，

是hash join算子的第一个子节点，而pg和mysql的hash join第一个算子是probe table,按照探测顺序来的，hash table在下面，

当然，实际顺序还是先hash table,然后probe table查找hash table,

这个要注意点，所以，oracle的hash join right和pg的hash join right顺序是不一样的，oracle的hash join right是hash表从外表切换到内表，

而pg也是驱动表从外表切换到内表，但是pg的驱动表当成probe table的，按照探测顺序来的，实际上驱动表应该是hash table，

对于MySQL，pg的hash join,驱动表应该是hash join算子第二个节点，有个hash标志的先做。

oracle里right join只有hash join才有，主要是用于外连接和子查询，merge join没有right join，比如not exists的驱动表只能是主表。

3）sort merge semi/anti join

这种先对join key排序，然后做merge，也可以针对大数据量，但是有个排序成本，能够通过索引消除排序较好，

一般对于等值查询，sort merge join不如hash join,但是能够消除排序，则效率较好，否则可能有很多IO操作，sort merge join对IO比较敏感。

对于按照order by join key,如果能索引消除排序的，可能这个算法较好。

它也是可以有first match的，虽然sort merge join没有驱动表概念，但是对于子查询，不能转为普通join的，一般算子第一个表还是主表。

这个oracle比较强大，除了等值的，还支持>,<,>=,<=...而PG只支持=，MySQL不支持，另外注意，oracle最多只能消除第一个表排序，而pg都能消除。

pg支持merge right anti join,但是pg没有merge semi join算子，如果semi join走sort merge join,只能是子查询的view然后可能剔重后转为普通join

oracle没有merge right anti join,只能主表驱动，有merge semi join,merge semi join可以子查询表驱动，不用查询重写成普通join。