[SQL Tune] 三個常見的JOIN簡介

談到SQL tune大概不能不談Join. 開發人員若在SQL語法中用了Join, 對ExecutionPlan中TABLE如何被Join一定要有基本的認識和瞭解, 否則Tune就只是空談而已. 本文就會針對Join的三種方式作一些介紹.

實例演練

我用的DATABASE是 Oracle XE 10G.

-- 以 HR 連線

Connect hr/hr;

-- 建立一個 Driving table

create table Driving_Emp as select * from EMPLOYEES;

-- 建立一個 Driven table
create table Driven_Dept as select * from DEPARTMENTS;

-- 建立 Index

create index e_deptno on Driven_Dept(DEPARTMENT_ID);
-- 收集相關 Statistics
exec dbms_stats.gather_table_stats('HR','Driving_Emp');

exec dbms_stats.gather_table_stats('HR','Driven_Dept');

1.Nested loop

這大概是最常見的Join方式, 以Join兩個TABLE為例, 基本上他的運作方式就像用VB寫兩個迴圈,各自抓取一個TABLE,一個是Driving TABLE(驅動端)一個是Driven TABLE(被驅動端). 前者是外迴圈後者是內迴圈. 如以下程式範例:

寫成SQL會是這樣:

Select Driving.*, Driven.* from Driving, Driven where Driving.col1=Driven.col2;

若寫成PL/SQL 應該會像這樣:

For i in (select * from Driving)

loop
For j in (select * from Driven where col2=i.col1)
loop
Display results;
End loop;

End loop;

這時ORACLE內部會做的是:

a) 找出外迴圈的driving table

b) 找出內迴圈的 driven table 指定給外迴圈

c) 根據每次外迴圈取得的資料, 連接內迴圈去取得相關資料.

使用時機

• 外迴圈最好有一些條件去限制回傳的筆數, 若外迴圈的筆數很多則Nested Loop的Cost可想 而知會相當高.
  
• 內迴圈連接外迴圈的欄位(Col2)最好有合適的INDEX, 否則內迴圈用Full Table Scan對效率可能會有影響.
• 原則上, Hash Join 的效率會較 Nested Loop 來得好.

實例演練
--利用以下指令虛擬出會產生 Nested Loop的資料筆數. 還蠻有趣的, 當筆數資料一調整就可以看到 Execution Plan從 Nested Loop 和 Hash Join之間跳來跳去.
exec dbms_stats.set_table_stats(ownname => 'HR', tabname => 'Driven_Dept', numrows => 40,numblks => 100 , avgrlen => 124);

exec dbms_stats.set_table_stats(ownname => 'HR', tabname => 'Driving_Emp', numrows => 100, numblks => 100, avgrlen => 124);

exec dbms_stats.set_index_stats(ownname => 'HR', indname => 'E_DEPTNO', numrows => 100, numlblks => 10);

-- Run 看看以下SQL
select
e.EMPLOYEE_ID,d.DEPARTMENT_NAME from Driving_Emp e, Driven_Dept d
where e.DEPARTMENT_ID=d.DEPARTMENT_ID;

-- 果然跑出 Nested Loop
Plan
SELECT STATEMENT ALL_ROWSCost: 41 Bytes: 13,320 Cardinality: 360
4 TABLE ACCESS BY INDEX ROWID TABLE HR.DRIVEN_DEPT Cost: 1 Bytes: 120 Cardinality: 4
3 NESTED LOOPS Cost: 41 Bytes: 13,320 Cardinality: 360
1 TABLE ACCESS FULL TABLE HR.DRIVING_EMP Cost: 29 Bytes: 700 Cardinality: 100
2 INDEX RANGE SCAN INDEX HR.E_DEPTNO Cost: 0 Cardinality: 9

2. Hash join

Hash joins 用來串接較大的TABLE, 可以把它想成改良版的Nested Loop, 有人稱它為Blocked Nested Loop, 可參閱 Wiki.

他的作法可分為兩個階段, 如下,

1. 建置 - Build : 建立一個 in-memory 的 hash table, 先將 Driving table 的一部分資料讀進Hash table(若 Memory 足夠則放在Memory, 若不夠則放在 Temporary space)透過 Hash Function 計算 Join Key. Hash的 Memory是屬於 Private memory, 也就是這個SQL所獨享的, 不像其他 Logic I/O 會用到 Latch. 相對於 Nested Loop 整個 Logic I/O 會大幅下降, 這也是 Hash Join 會優於 Nested Loop的原因之ㄧ.
   
2. 偵測 - Probe : 偵測第一階段的hash table的hash value去掃瞄Driven table, 若得到Output則輸出結果.
   

這時要看DBA 設定 Hash Join的相關參數, 若Memory設定沒有大到足以一次驟完成上述步驟, 則ORACLE會分多次完成. 和Nested Loop的差異在於前者是每次的外迴圈都要連接一次內迴圈而後者則是Hash Table讀滿後才連結一次內迴圈. 相較之下對CPU的需求也較高.

使用時機

• Driving table筆數少而Driven table 筆數多時, 此方式會較Nested Loop 來得有效率.
• 若是SQL的結果是要呈現在分頁的REPORT上面, Nested Loop 會好一些. 若是呈現全部的結果則 Hash Join 會強一些.

實例演練

-- 適著調大一下筆數囉
exec dbms_stats.set_table_stats(ownname => 'HR', tabname => 'Driving_Emp', numrows => 100000000, numblks => 100000, avgrlen => 124);

exec dbms_stats.set_index_stats(ownname => 'HR', indname => 'E_DEPTNO', numrows => 100000000, numlblks => 10000);

exec dbms_stats.set_table_stats(ownname => 'HR', tabname => 'Driven_Dept', numrows => 100000000,numblks => 10000 , avgrlen => 124);

-- Run SQL
select e.EMPLOYEE_ID,d.DEPARTMENT_NAME from Driving_Emp e, Driven_Dept d where e.DEPARTMENT_ID=d.DEPARTMENT_ID;

-- 變成 Hash Join啦
Plan
SELECT STATEMENT ALL_ROWSCost: 15,127,941,348 Bytes: 33,636,363,300,000,000 Cardinality: 909,090,900,000,000
3 HASH JOIN Cost: 15,127,941,348 Bytes: 33,636,363,300,000,000 Cardinality: 909,090,900,000,000
1 TABLE ACCESS FULL TABLE HR.DRIVING_EMP Cost: 33,028 Bytes: 700,000,000 Cardinality: 100,000,000
2 TABLE ACCESS FULL TABLE HR.DRIVEN_DEPT Cost: 5,551 Bytes: 3,000,000,000 Cardinality: 100,000,000

3. Sort merge join

Driving/Driven Table的觀唸到 Sort Merge Join 就不復見了. 原則上它的作法就是將兩個TABLE的資料各自排序後做合併的動作.原則上整個動作可以分為兩個部份.

• 排序 (Sort join operation)

從兩個TABLE中將資料各自做排序.

• 合併 (Merge join operation)

將排序完後的結果合併並篩選出結果.

使用時機

大概只有在join大概只有在join條件用到不等於(<, <=, >=, <>)時, 有機會期望用到此方式. 原則上,這是一個吃IO很重的動作.

實例演練

-- 如前所說 Merge Join常出現於'不等於', 那就來個不等於吧.

select *
from Driving_Emp e, Driving_Emp f
where E.EMPLOYEE_ID<>F.EMPLOYEE_ID
and E.HIRE_DATE<=F.hire_date

--是不是變成 Merge Join

Plan
SELECT STATEMENT ALL_ROWSCost: 11,824 Bytes: 71,327,102,832 Cardinality: 495,327,103
6 MERGE JOIN Cost: 11,824 Bytes: 71,327,102,832 Cardinality: 495,327,103
2 SORT JOIN Cost: 1,753 Bytes: 7,200,000 Cardinality: 100,000
1 TABLE ACCESS FULL TABLE HR.DRIVING_EMP Cost: 35 Bytes: 7,200,000 Cardinality: 100,000
5 FILTER
4 SORT JOIN Cost: 1,753 Bytes: 7,200,000 Cardinality: 100,000
3 TABLE ACCESS FULL TABLE HR.DRIVING_EMP Cost: 35 Bytes: 7,200,000 Cardinality: 100,000

相關連結

1.Expert one-on-one Oracle

2.Nested loops, Hash join and Sort Merge joins – difference?(Sachin Arora )

3. Wiki (Merge Join, Hash Join)