基本概念

• Nested loop join：
  Outer table中的每一行與inner table中的相應(yīng)記錄join，類似一個(gè)嵌套的循環(huán)。
• Sort merge join：
  將兩個(gè)表排序，然后再進(jìn)行join。
• Hash join：
  將兩個(gè)表中較小的一個(gè)在內(nèi)存中構(gòu)造一個(gè)Hash 表（對(duì)JoinKey），掃描另一個(gè)表，同樣對(duì)JoinKey進(jìn)行Hash后探測(cè)是否可以join，找出與之匹配的行。
  一張小表被hash在內(nèi)存中。因?yàn)閿?shù)據(jù)量小，所以這張小表的大多數(shù)數(shù)據(jù)已經(jīng)駐入在內(nèi)存中，剩下的少量數(shù)據(jù)被放置在臨時(shí)表空間中；
  每讀取大表的一條記錄，就和小表中內(nèi)存中的數(shù)據(jù)進(jìn)行比較，如果符合，則立即輸出數(shù)據(jù)（也就是說沒有讀取臨時(shí)表空間中的小表的數(shù)據(jù)）。而如果大表的數(shù)據(jù)與小表中臨時(shí)表空間的數(shù)據(jù)相符合，則不直接輸出，而是也被存儲(chǔ)臨時(shí)表空間中。
  當(dāng)大表的所有數(shù)據(jù)都讀取完畢，將臨時(shí)表空間中的數(shù)據(jù)以其輸出。如果小表的數(shù)據(jù)量足夠?。ㄐ∮趆ashareasize），那所有數(shù)據(jù)就都在內(nèi)存中了，可以避免對(duì)臨時(shí)表空間的讀寫。
  如果是并行環(huán)境下，前面中的第2步就變成如下了：每讀取一條大表的記錄，和內(nèi)存中小表的數(shù)據(jù)比較，如果符合先做join，而不直接輸出，直到整張大表數(shù)據(jù)讀取完畢。如果內(nèi)存足夠，Join好的數(shù)據(jù)就保存在內(nèi)存中。否則，就保存在臨時(shí)表空間中。

適用范圍

• Nested loop join：
  　　適用于outer table(有的地方叫Mastertable)的記錄集比較少（<10000）而且innertable（有的地方叫Detailtable）索引選擇性較好的情況下（inner table要有index）。
  　　inner table被outer table驅(qū)動(dòng)，outertable返回的每一行都要在innertable中檢索到與之匹配的行。當(dāng)然也可以用ORDERED提示來改變CBO默認(rèn)的驅(qū)動(dòng)表，使用USE_NL(table_name1table_name2)可是強(qiáng)制CBO執(zhí)行嵌套循環(huán)連接。
  　　cost = outer access cost + (inner access cost *outercardinality)
• Sort merge join：
  　　用在數(shù)據(jù)沒有索引但是已經(jīng)排序的情況下。
  　　通常情況下hash join的效果都比Sortmergejoin要好，然而如果行源已經(jīng)被排過序，在執(zhí)行排序合并連接時(shí)不需要再排序了，這時(shí)Sort mergejoin的性能會(huì)優(yōu)于hashjoin?？梢允褂肬SE_MERGE(table_name1 table_name2)來強(qiáng)制使用Sortmergejoin。
  　　cost = (outer access cost * # of hash partitions) + inneraccesscost
• Hash join：
  　　適用于兩個(gè)表的數(shù)據(jù)量差別很大。但需要注意的是：如果HASH表太大，無法一次構(gòu)造在內(nèi)存中，則分成若干個(gè)partition，寫入磁盤的temporarysegment，則會(huì)多一個(gè)I/O的代價(jià)，會(huì)降低效率，此時(shí)需要有較大的temporarysegment從而盡量提高I/O的性能。
  　　可以用USE_HASH(table_name1table_name2)提示來強(qiáng)制使用散列連接。如果使用散列連HASH_AREA_SIZE初始化參數(shù)必須足夠的大，如果是9i，Oracle建議使用SQL工作區(qū)自動(dòng)管理，設(shè)置WORKAREA_SIZE_POLICY為AUTO，然后調(diào)整PGA_AGGREGATE_TARGET即可。
  　　也可以使用HASH_JOIN_ENABLED=FALSE（默認(rèn)為TRUE）強(qiáng)制不使用hash join。
  　　cost = (outer access cost * # of hash partitions) + inneraccesscost

效率比較

Hashjoin的主要資源消耗在于CPU（在內(nèi)存中創(chuàng)建臨時(shí)的hash表，并進(jìn)行hash計(jì)算），而mergejoin的資源消耗主要在于磁盤I/O（掃描表或索引）。在并行系統(tǒng)中，hashjoin對(duì)CPU的消耗更加明顯。所以在CPU緊張時(shí)，最好限制使用hashjoin。
在絕大多數(shù)情況下，hash join效率比其他join方式效率更高：
在Sort-Merge Join(SMJ)，兩張表的數(shù)據(jù)都需要先做排序，然后做merge。因此效率相對(duì)最差；
Nested-Loop Join(NL)效率比SMJ更高。特別是當(dāng)驅(qū)動(dòng)表的數(shù)據(jù)量很大（集的勢(shì)高）時(shí)。這樣可以并行掃描內(nèi)表。
Hash join效率最高，因?yàn)橹灰獙?duì)兩張表掃描一次。

MySQL中Join算法實(shí)現(xiàn)原理分析
通往性能優(yōu)化的JOIN方法說明
SQL中的JOIN的簡(jiǎn)潔解釋

1，排序 - - 合并連接（Sort Merge Join， SMJ）

內(nèi)部連接過程：
1）首先生成row source1需要的數(shù)據(jù)，然后對(duì)這些數(shù)據(jù)按照連接操作關(guān)聯(lián)列（如A.col3）進(jìn)行排序。
2）隨后生成row source2需要的數(shù)據(jù)，然后對(duì)這些數(shù)據(jù)按照與sort source1對(duì)應(yīng)的連接操作關(guān)聯(lián)列（如B.col4）進(jìn)行排序。
3）最后兩邊已排序的行被放在一起執(zhí)行合并操作，即將2個(gè)row source按照連接條件連接起來
下面是連接步驟的圖形表示：
MERGE
/
SORT SORT
| |
Row Source 1 Row Source 2
如果row source已經(jīng)在連接關(guān)聯(lián)列上被排序，則該連接操作就不需要再進(jìn)行sort操作，這樣可以大大提高這種連接操作的連接速度，因?yàn)榕判蚴莻€(gè)極其費(fèi)資源的操作，特別是對(duì)于較大的表。預(yù)先排序的row source包括已經(jīng)被索引的列（如a.col3或b.col4上有索引）或row source已經(jīng)在前面的步驟中被排序了。盡管合并兩個(gè)row source的過程是串行的，但是可以并行訪問這兩個(gè)row source（如并行讀入數(shù)據(jù)，并行排序）。
SMJ連接的例子：
SQL> explain plan for
select /*+ ordered */ e.deptno， d.deptno
from emp e， dept d
where e.deptno = d.deptno
order by e.deptno， d.deptno；
Query Plan

SELECT STATEMENT [CHOOSE] Cost=17
MERGE JOIN
SORT JOIN
TABLE ACCESS FULL EMP [ANALYZED]
SORT JOIN
TABLE ACCESS FULL DEPT [ANALYZED]
排序是一個(gè)費(fèi)時(shí)、費(fèi)資源的操作，特別對(duì)于大表?；谶@個(gè)原因，SMJ經(jīng)常不是一個(gè)特別有效的連接方法，但是如果2個(gè)row source都已經(jīng)預(yù)先排序，則這種連接方法的效率也是蠻高的。

2，嵌套循環(huán)（Nested Loops， NL）

這個(gè)連接方法有驅(qū)動(dòng)表（外部表）的概念。其實(shí)，該連接過程就是一個(gè)2層嵌套循環(huán)，所以外層循環(huán)的次數(shù)越少越好，這也就是我們?yōu)槭裁磳⑿”砘蚍祷剌^小 row source的表作為驅(qū)動(dòng)表（用于外層循環(huán)）的理論依據(jù)。但是這個(gè)理論只是一般指導(dǎo)原則，因?yàn)樽裱@個(gè)理論并不能總保證使語句產(chǎn)生的I/O次數(shù)最少。有時(shí)不遵守這個(gè)理論依據(jù)，反而會(huì)獲得更好的效率。如果使用這種方法，決定使用哪個(gè)表作為驅(qū)動(dòng)表很重要。有時(shí)如果驅(qū)動(dòng)表選擇不正確，將會(huì)導(dǎo)致語句的性能很差、很差。
內(nèi)部連接過程：
Row source1的Row 1 —— Probe ->Row source 2
Row source1的Row 2 —— Probe ->Row source 2
Row source1的Row 3 —— Probe ->Row source 2
……。
Row source1的Row n —— Probe ->Row source 2
從內(nèi)部連接過程來看，需要用row source1中的每一行，去匹配row source2中的所有行，所以此時(shí)保持row source1盡可能的小與高效的訪問row source2（一般通過索引實(shí)現(xiàn)）是影響這個(gè)連接效率的關(guān)鍵問題。這只是理論指導(dǎo)原則，目的是使整個(gè)連接操作產(chǎn)生最少的物理I/O次數(shù)，而且如果遵守這個(gè)原則，一般也會(huì)使總的物理I/O數(shù)最少。但是如果不遵從這個(gè)指導(dǎo)原則，反而能用更少的物理I/O實(shí)現(xiàn)連接操作，那盡管違反指導(dǎo)原則吧！因?yàn)樽钌俚奈锢?I/O次數(shù)才是我們應(yīng)該遵從的真正的指導(dǎo)原則，在后面的具體案例分析中就給出這樣的例子。
在上面的連接過程中，我們稱Row source1為驅(qū)動(dòng)表或外部表。Row Source2被稱為被探查表或內(nèi)部表。
在NESTED LOOPS連接中，Oracle讀取row source1中的每一行，然后在row sourc2中檢查是否有匹配的行，所有被匹配的行都被放到結(jié)果集中，然后處理row source1中的下一行。這個(gè)過程一直繼續(xù)，直到row source1中的所有行都被處理。這是從連接操作中可以得到第一個(gè)匹配行的最快的方法之一，這種類型的連接可以用在需要快速響應(yīng)的語句中，以響應(yīng)速度為主要目標(biāo)。
如果driving row source（外部表）比較小，并且在inner row source（內(nèi)部表）上有唯一索引，或有高選擇性非唯一索引時(shí)，使用這種方法可以得到較好的效率。NESTED LOOPS有其它連接方法沒有的的一個(gè)優(yōu)點(diǎn)是：可以先返回已經(jīng)連接的行，而不必等待所有的連接操作處理完才返回?cái)?shù)據(jù)，這可以實(shí)現(xiàn)快速的響應(yīng)時(shí)間。
如果不使用并行操作，最好的驅(qū)動(dòng)表是那些應(yīng)用了where 限制條件后，可以返回較少行數(shù)據(jù)的的表，所以大表也可能稱為驅(qū)動(dòng)表，關(guān)鍵看限制條件。對(duì)于并行查詢，我們經(jīng)常選擇大表作為驅(qū)動(dòng)表，因?yàn)榇蟊砜梢猿浞掷貌⑿泄δ?。?dāng)然，有時(shí)對(duì)查詢使用并行操作并不一定會(huì)比查詢不使用并行操作效率高，因?yàn)樽詈罂赡苊總€(gè)表只有很少的行符合限制條件，而且還要看你的硬件配置是否可以支持并行（如是否有多個(gè)CPU，多個(gè)硬盤控制器），所以要具體問題具體對(duì)待。
NL連接的例子：
　　SQL> explain plan for
　　select a.dname，b.sql
　　from dept a，emp b
　　where a.deptno = b.deptno；
　　Query Plan
　　-------------------------
　　SELECT STATEMENT [CHOOSE] Cost=5
　　NESTED LOOPS
　　TABLE ACCESS FULL DEPT [ANALYZED]
　　TABLE ACCESS FULL EMP [ANALYZED]

3，哈希連接（Hash Join， HJ）

這種連接是在oracle 7.3以后引入的，從理論上來說比NL與SMJ更高效，而且只用在CBO優(yōu)化器中。
較小的row source被用來構(gòu)建hash table與bitmap，第2個(gè)row source被用來被hansed，并與第一個(gè)row source生成的hash table進(jìn)行匹配，以便進(jìn)行進(jìn)一步的連接。Bitmap被用來作為一種比較快的查找方法，來檢查在hash table中是否有匹配的行。特別的，當(dāng)hash table比較大而不能全部容納在內(nèi)存中時(shí)，這種查找方法更為有用。這種連接方法也有NL連接中所謂的驅(qū)動(dòng)表的概念，被構(gòu)建為hash table與bitmap的表為驅(qū)動(dòng)表，當(dāng)被構(gòu)建的hash table與bitmap能被容納在內(nèi)存中時(shí)，這種連接方式的效率極高。
HASH連接的例子：
　　SQL> explain plan for
　　select /*+ use_hash（emp） */ empno
　　from emp， dept
　　where emp.deptno = dept.deptno；
　　Query Plan
　　----------------------------
　　SELECT STATEMENT[CHOOSE] Cost=3
　　HASH JOIN
　　TABLE ACCESS FULL DEPT
　　TABLE ACCESS FULL EMP
要使哈希連接有效，需要設(shè)置HASH_JOIN_ENABLED=TRUE，缺省情況下該參數(shù)為TRUE，另外，不要忘了還要設(shè)置 hash_area_size參數(shù)，以使哈希連接高效運(yùn)行，因?yàn)楣＿B接會(huì)在該參數(shù)指定大小的內(nèi)存中運(yùn)行，過小的參數(shù)會(huì)使哈希連接的性能比其他連接方式還要低。

最后，總結(jié)一下，在哪種情況下用哪種連接方法比較好：

• 排序 - - 合并連接（Sort Merge Join， SMJ）：
  a）對(duì)于非等值連接，這種連接方式的效率是比較高的。
  b）如果在關(guān)聯(lián)的列上都有索引，效果更好。
  c）對(duì)于將2個(gè)較大的row source做連接，該連接方法比NL連接要好一些。
  d）但是如果sort merge返回的row source過大，則又會(huì)導(dǎo)致使用過多的rowid在表中查詢數(shù)據(jù)時(shí)，數(shù)據(jù)庫性能下降，因?yàn)檫^多的I/O.
• 嵌套循環(huán)（Nested Loops， NL）：
  a）如果driving row source（外部表）比較小，并且在inner row source（內(nèi)部表）上有唯一索引，或有高選擇性非唯一索引時(shí)，使用這種方法可以得到較好的效率。
  b） NESTED LOOPS有其它連接方法沒有的的一個(gè)優(yōu)點(diǎn)是：可以先返回已經(jīng)連接的行，而不必等待所有的連接操作處理完才返回?cái)?shù)據(jù)，這可以實(shí)現(xiàn)快速的響應(yīng)時(shí)間。
• 哈希連接（Hash Join， HJ）：
  a）這種方法是在oracle7后來引入的，使用了比較先進(jìn)的連接理論，一般來說，其效率應(yīng)該好于其它2種連接，但是這種連接只能用在CBO優(yōu)化器中，而且需要設(shè)置合適的hash_area_size參數(shù)，才能取得較好的性能。
  b）在2個(gè)較大的row source之間連接時(shí)會(huì)取得相對(duì)較好的效率，在一個(gè)row source較小時(shí)則能取得更好的效率。
  c）只能用于等值連接中