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>