Null Aware Anti Join 速记

所谓 semi join，指的是 join 的两张表里只输出其中一侧，另一侧用于计算输出条件。通常，我们把输出侧叫“保留侧”，条件侧叫“非保留侧”。

Tips：Anti join 要求我们在非保留侧不要输出任何辅助表达式（如计算分区id表达式），因为这一侧会被丢弃。

semi join 下面有一个子类叫 semi anti join，它指的是计算输出条件的表达式是 NOT IN, <> ALL，这两个表达式是 NULL 敏感的。所谓 NULL 敏感是说 join 条件要写成：

a.c1 = b.c1 OR a.c1 is null OR b.c1 is null

对于这个条件无法使用 hash join 算法来处理，只能使用 nested loop join 来做笛卡尔积。

注：Hash Join, Merge Join 两种算法都不适合用于做笛卡尔积运算。

笛卡尔积太慢了。如果我们能：

• 通过 schema 属性来确信 a.c1 NOT NULL, b.c1 NOT NULL
• 或者 SQL 里存在类似表达式 where a.c1 IS NOT NULL AND b.c1 NOT NULL
  那么 join 条件可以改成 a.c1 = b.c1，此时可以使用 hash join 来高效处理。

但现实中并不总是能满足上述条件。Oracle 开发了 NAAJ 专利算法，可以将任意 semi anti join 合法地改写成 hash join，核心思路是：

1. 对于非 null 值，做正常的 hash join
2. 对于左表、右表的 null 值，做特殊处理
3. 如果右表为空，做特殊处理

通过这种方式，使得 anti semi join 的执行性能得到数量级的提升。

Oracle 论文中给出了一个例子：

• Enhanced SubQuery Optimizations in Oracle》第六节
• http://structureddata.org/2008/05/22/null-aware-anti-join/