背景

有如下的數據查詢場景。

SELECT  a,b,c,d,e,f
FROM xxx.BBBB
WHERE dt = '${zdt.addDay(0).format('yyyy-MM-dd')}' 
AND predict_type  
not IN 
( SELECT distinct a FROM xxx.AAAAAWHERE dt = '${zdt.addDay(0).format('yyyy-MM-dd')}' 
)

分析

通過查看SQL語句的執行計劃基本就可以判斷性能瓶頸所在。

1. | == Physical Plan ==

2. BroadcastNestedLoopJoin BuildRight,

Spark?SQL的優化器最終將SQL優化為了一個BroadcastNestedLoopJoin。

實際上就是在對JOIN兩側的數據做笛卡爾積運算。時間復雜度為O()，過濾前的結果集行數達到了萬億級別。

優化方法

嘗試將NOT IN子查詢改寫成了LEFT JOIN形式

SELECT  a.*
FROM
(SELECT  a,b,c,d,e,fFROM xxx.BBBBWHERE dt = '${zdt.addDay(0).format('yyyy-MM-dd')}'
) a
LEFT JOIN
(SELECT  cFROM xxx.AAAAWHERE dt = '${zdt.addDay(0).format('yyyy-MM-dd')}' 
) b
ON a.c = b.c 
WHERE b.c is null

執行計劃如下:

1. Filter is null(#391L)

2. +- SortMergeJoin

可以看到，JOIN方式變成了SortMergeJoin。

SortMergeJoin的原理是對JOIN兩側的數據排序后在做歸并。

不妨假設：

排序的時間復雜度為O(nlogn)。
則SortMergeJoin整體的時間復雜度為O(n + nlogn)，依然是百萬級數據量的過濾計算。

在數據庫查詢優化中，"Broadcast Nested Loop Join" 和 "Sort Merge Join" 是兩種不同的關聯操作算法。

Broadcast Nested Loop Join:
在這種連接算法中，一張表被廣播到其他所有的節點上，然后與每個節點上的本地數據進行嵌套循環連接。這通常適用于一個小表和一個大表的連接，其中小表的數據可以很容易地廣播到所有節點上。

優勢:
1. 適用于小表連接：?當一個表很小而另一個表很大時，廣播小表可以減少網絡傳輸和數據傳輸開銷。
2. 簡單性：?實現相對簡單，不需要進行大規模數據排序。
3. 內存友好：?不需要大量的內存，因為每次只處理小表的一行。

Sort Merge Join:
這是一種更加通用的連接算法，它不涉及表的廣播，而是將連接的列進行排序，然后按照排序結果進行逐對比較，從而執行連接操作。

優勢:
1. 適用于大表連接：當兩個表的大小都比較大時，Sort Merge Join 可以更好地處理連接操作，因為不需要將整個表廣播到各個節點。
2. 高效的順序訪問：由于涉及數據的排序，Sort Merge Join 可以更好地利用磁盤預讀，提高磁盤數據訪問效率。
3. 穩定性：對于不同數據分布的情況，Sort Merge Join 的性能通常比 Broadcast Nested Loop Join 更穩定。

所以，Broadcast Nested Loop Join 適用于小表和大表之間的連接，而 Sort Merge Join 則更適合連接兩個較大的表。但請注意，具體的性能取決于數據分布、硬件配置和數據庫管理系統的優化能力。在實際情況中，優化器可能會根據統計信息和其他因素來選擇最適合的連接算法。