NLJ：
根據(jù)連接鍵，把小表的每一行，和大筆的每一行做對比。 一般情況下會對大表連接鍵上建index。
成本計算：讀小表的行+（小表的每一行×讀取大表的行）
SMJ:
讀取小表和大表讀的行，根據(jù)連接鍵排序，然后根據(jù)排序后的數(shù)據(jù)集（小表的和大表的）合進(jìn)行連接。
理想狀態(tài)：2個表的排序操作都能在內(nèi)存進(jìn)行
常規(guī)情況：2階段進(jìn)行：
1.sort run階段：數(shù)據(jù)讀取到內(nèi)存，排序，寫出到臨時表空間。直到所有的row sourse完成排序。
2.merge階段：之前每次寫到臨時表空間的數(shù)據(jù)（即sort run）被重新讀入到內(nèi)存，進(jìn)行merge。
成本計算：讀取小表的行+寫小表的run sort到temp表空間+
讀取大表的行+寫大表的run sort到temp表空間+
cpu對小表和大表的排序消耗
join連接中的并行機(jī)制：
能在NLJ和SMJ中使用。并發(fā)查詢的執(zhí)行計劃是一個樹形結(jié)構(gòu)（DFO），每個樹上的DFO節(jié)點是一個sql操作過程，并且能把該操作過程能指派到一個query slave進(jìn)程中。
Hash Join：
用在條件為等號的環(huán)境下，hash連接的效率要比SMJ和NLJ要高（如果索引的blevel比較高），且hash join不要求一定要有索引。
hash join的基本算法是在內(nèi)存中建立hash table，小表叫做build input，理想狀態(tài)下，build input在內(nèi)存中；大表叫做probe input。
在實際的情況下，build input不一定能完全放在內(nèi)存中，此時，和probe input一樣，build input的溢出部分，會在磁盤上用hash函數(shù)分割成小的不連續(xù)的分區(qū)。
hash連接分2個階段進(jìn)行：
1.partitioning階段：即在內(nèi)存中存放build input，若放不下，則和probe input一樣，在磁盤上利用hash函數(shù)將input分割成小的不連續(xù)的分區(qū)。
1.join階段：在相同的鍵值上，將build input和probe input的分區(qū)進(jìn)行一一配對，并且join。
以上的hash連接的算法也叫g(shù)race join。
hash算法的限制：該算法是假設(shè)hash之后連接值傾斜度（skew）不高，使得每個partition上保持大約相同數(shù)量的rows。但是事實上不可能保證每個partition有大約相同數(shù)量的rows。
hybrid hash join是在oracle 7.3之后應(yīng)用的比較高效的hash算法，它是在grace join的基礎(chǔ)上，盡量在內(nèi)存在搭建build input。
但是由于不可能在每個partition中保證相同的rows，后來有出來一些技術(shù)如bit-vector filtering、role reversal和histograms。我們將在后面的章節(jié)講到這些技術(shù)。
分區(qū)的數(shù)量，我們叫做fan-out。fan-out太多會導(dǎo)致partition較多，從而影響IO，但是如果fan-out太少又會造成數(shù)量較少的大partition，這些大partition無法放在hash內(nèi)存中。因此選擇一個合適的fan-out和partition 大小，是hash join調(diào)優(yōu)的關(guān)鍵。
當(dāng)partitioning之后，build input或者probe input如果在內(nèi)存中無法放下，hash table的溢出部分將會做nested-loops hash join。
hash table是由部分（在內(nèi)存內(nèi)的）build input partition和所有的probe input連接構(gòu)成。剩余的不在內(nèi)存中的build input將通過迭代的方式繼續(xù)獲取，直到所有的build input被迭代完。
hash join 規(guī)則：
假設(shè)有2個表：
S = { 1, 1, 1, 3, 3, 4, 4, 4, 4, 5, 8, 8, 8, 8, 10 }
B = { 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 8, 9, 9, 9, 10, 10, 11}
首先會根據(jù)hash_area_size確定小表是否能做build table。如果build input不能完全的在內(nèi)存中，那么build input就被會分區(qū)，分區(qū)的數(shù)量我們稱為fan-out，
fan-out是由hash_area_size和cluster size決定的，cluster size是指分區(qū)中還沒被寫出到臨時表空間的連續(xù)塊的數(shù)量。
cluster size=db_block_size * hash_multiblock_io_count，hash_multiblock_io_count在oracle9i中是隱含參數(shù)
hash算法會把S和B表的連接列分成不連接的桶（bucket），桶也叫做分區(qū)（partition），hash算法是盡量的減少數(shù)據(jù)的傾斜度，使得數(shù)據(jù)盡量均勻的分布。
以上面的S表和B表為例，如果我們簡單的假設(shè)hash算法是取余，則：
S的分區(qū)為:{0,1,3,4,5,8}
B的分區(qū)為:{0,1,2,3,8,9}
經(jīng)過這樣的分區(qū)之后，只需要相應(yīng)的分區(qū)之間做join即可（也就是所謂的partition pairs），如果有一個分區(qū)為NULL的話，則相應(yīng)的分區(qū)join即可忽略。即他們可以在0,1,3,8上做連接。
相應(yīng)的如果我們用SMJ或者NLJ，在連接上的消耗要高很多。
當(dāng)build input被讀入hash area內(nèi)存準(zhǔn)備進(jìn)行分區(qū)的時候，build input表中的唯一列值被作為連接鍵構(gòu)建起來，即所謂的位圖向量（bitmap vector）。
按照上面的例子，bitmap vector為：{1,3,4,8,10}。
bitmap vector用來決定在partitioning 階段和大表（probe input）進(jìn)行連接的時候，哪些行是需要的，哪些是不需要的，不需要的將被丟棄，這就是我們上面說的bit-vector filtering技術(shù)。
當(dāng)對B表進(jìn)行分區(qū)時，將每一個連接鍵上的值與位圖向量相比較，如果不在其中，則將其記錄丟棄。在我們這個例子中，B表中以下數(shù)據(jù)將被丟棄
這個例子中，B表中以下數(shù)據(jù)將被丟棄{0,0,2,2,2,2,2,2,9,9,9,9,9}。
當(dāng)?shù)谝粋€S分區(qū)和B分區(qū)做完連接后，需要將第i個S分區(qū)和B分區(qū)讀入內(nèi)存中做連接，此時會根據(jù)分區(qū)的大小，自動的選擇哪個做build input，哪個做probe input。這就是動態(tài)角色轉(zhuǎn)換技術(shù)，即我們前面所說的role reversal。
總體說來，hash算法為如下步驟（以下考慮的是hash area size不夠大，需要寫出到磁盤的情況）：
1.決定fanout的數(shù)量，即分區(qū)的數(shù)量。分區(qū)數(shù)量×cluster大小<=內(nèi)存中能用的hasharea比例×hashareasize大小
2.讀取S表，根據(jù)內(nèi)部的hash算法（我們暫時稱作hash_fun_1），將連接列上的值map到分區(qū)。在此步驟，還利用另一個hash函數(shù)（我們稱作hash_fun_2）產(chǎn)生另一個hash值，和連接鍵一起存放。該值將在后續(xù)的構(gòu)建hashtable中用到。
3.為S表的獨立的連接鍵形成的bitmap向量
4.根據(jù)partition的大小排序，使得盡量多（也就是盡量小的partition進(jìn)入內(nèi)存。這也就是之前要根據(jù)partition大小排序的原因）的分區(qū)放入內(nèi)存來構(gòu)建hashtable。如果內(nèi)存不夠放下所有的parittion，則輸出到tempsegment上）。
5.利用之前的hash值，構(gòu)建S表的hashtable。
6.讀取B表，根據(jù)位圖向量過濾，如果通過hash算法后B的值與位圖向量比較不在其中，則丟棄該行。
7.將過濾后B表的行，利用內(nèi)部的hash_fun_1和連接鍵，形成partition。
8.如果B表的行能在內(nèi)存中形成分區(qū)，就利用內(nèi)部的hash_fun_2執(zhí)行連接，并且形成合適的hash桶。
9.如果不能在內(nèi)存中形成分區(qū)，則將S的分區(qū)、連接鍵、B表的剩余行寫出到磁盤。
10.從磁盤中讀取未處理的S表和B表的分區(qū)。利用內(nèi)部hash_fun_2值，構(gòu)建hashtable，在構(gòu)建時將使用動態(tài)角色轉(zhuǎn)換技術(shù)。在第一次循環(huán)中，優(yōu)化器將先使用小表做buildinput，大表做probeinput，角色轉(zhuǎn)換技術(shù)僅在第一次循環(huán)后使用。
11.如果probeinput或者buildinput中（已經(jīng)經(jīng)過角色轉(zhuǎn)換了）較小的那個還是不能放入到內(nèi)存中，則將讀取較小的那個buildinput到內(nèi)存chunk中，并且循環(huán)的和probeinput做hash 連接。這我們叫做nestedhashloopsjoin。
hash join的成本計算：
1.最簡單的情況，hash area足夠大能放下S表分區(qū)后的所有的build input：
cost（HJ）=read（S）+build hash table in memory（cpu）+read（B）+perform in memory join（cpu）
如果忽略cpu的成本，cost（HJ）無限接近于 read（s）+read（b）
2.當(dāng)hash area（后面用M表示）不夠大，不能容納build input，S，它將會寫出到磁盤。當(dāng)然了，表B也會寫出到磁盤：
total cost 無限接近于 cost（HJ循環(huán)1）+cost（HJ循環(huán)2）
其中cost（HJ循環(huán)1） 無限接近于 read（S）+read（B）+write（（S-M）+（B-B*M/S））
即上述2至9步。
由于HJ循環(huán)2使用了nested hash loops join，hash join的算法處理Si和Bi分區(qū)。當(dāng)每個build input的chunk被讀取時，probe input將被多次讀。
因此cost（HJ循環(huán)2） 無限接近于 read（（S-M）+n×（B-B*M/S））
即上述10至11步。
n為進(jìn)行nested hash loops join的次數(shù)，n一般在10以上，也就是需要構(gòu)建的partition大于10倍的hash area。
http://www./study-note/study-hash-join/
