PostgreSQL 与关系代数 (Equi-Join , Semi-Join , Anti-Join , Division)

PostgreSQL , 关系代数 , EquiJoin , SemiJoin , AntiJoin , Division

关系数据库中很多操作来自关系代数中的一些概念。例如常见的JOIN操作，下面是关系代数中的一些概念。

<a href="https://en.wikipedia.org/wiki/Relational_algebra">https://en.wikipedia.org/wiki/Relational_algebra</a>

JOIN本身也分好多种比如EquiJoin , SemiJoin , AntiJoin , Division。

这种JOIN最为常见。例如：

实际上关系代数中为θ-join，包括(&lt;, ≤, =, &gt;, ≥)，当使用=时，对应的就是equijoin.

只要操作符（JOIN条件）返回TRUE，就输出对应的JOIN记录。（也可以理解为笛卡尔乘积中，仅返回JOIN条件为TRUE的那些）

返回在Employee中的记录，同时这条记录与Dept中的所有记录一对多操作时，有一个返回TRUE的操作即可。

例如

<a href="https://github.com/digoal/blog/blob/master/201802/20180205_01_pic_001.jpg" target="_blank"></a>

由于semiJoin的操作在EXISTS中只要有一条符合TRUE即可，所以很大概率下并不需要扫描全量Dept。

semiJOIN支持hash, merge, nestloop几种JOIN方法。

Employee很小，并且Dept有索引时，NESTLOOP就会比较快。

Employee很大时，使用hash就很快。

PostgreSQL 11在hash操作上有了极大的性能提升：

<a href="https://github.com/digoal/blog/blob/master/201802/20180201_01.md">《PostgreSQL 11 preview - parallel hash (含hash JOIN , hash agg等) 性能极大提升》</a>

<a href="https://github.com/digoal/blog/blob/master/201802/20180201_02.md">《PostgreSQL dblink异步调用实现 并行hash分片JOIN - 含数据交、并、差 提速案例》</a>

AntiJoin与SemiJoin表达的意思有点相反，要求Employee中的每一条记录，与Dept中所有记录进行操作后，Dept中没有任何一条能满足。返回在Employee中的这样的记录。

<a href="https://github.com/digoal/blog/blob/master/201802/20180205_01_pic_002.jpg" target="_blank"></a>

AntiJoin要求Employee中每一条记录与Dept所有记录进行操作，并且所有操作都不满足条件，这条算作有效记录，返回该Employee的记录。

对于JOIN操作符为=号的，不管是semijoin还是antijoin，都可以用HASH join，达到非常好的加速效果。

JOIN中的除法运算，没有对应的SQL，需要写多条SQL或者使用CTE语法写一条SQL来实现。

<a href="https://github.com/digoal/blog/blob/master/201802/20180205_01_pic_003.jpg" target="_blank"></a>

<a href="https://github.com/digoal/blog/blob/master/201802/20180205_01_pic_004.jpg" target="_blank"></a>

1、补齐

tmp1:

2、使用AntiJoin计算余数

tmp2:

3、去重，并使用except求差，得到最终结果

outerjoin不再赘述。

PostgreSQL 11

64线程机器，使用HASH并行。

测试数据：

PostgreSQL的JOIN算法可圈可点，在版本11后，引入了parallel hash join，支持equijoin, semijoin, antijoin等各种关系计算。

性能杠杠的。

<a href="https://www.postgresql.org/message-id/flat/CAEepm=[e-mail]#CAEepm=[e-mail]">https://www.postgresql.org/message-id/flat/CAEepm=[e-mail]#CAEepm=[e-mail]</a>

<a href="http://blog.itpub.net/15480802/viewspace-703260/">http://blog.itpub.net/15480802/viewspace-703260/</a>