轉(zhuǎn)自https://blog.csdn.net/zhangcanyan/article/details/51439021

客戶端管理器

客戶端管理器是處理客戶端通信的悼凑》Ｎ荩客戶端可以是一個（網(wǎng)站）服務(wù)器或者一個最終用戶或最終應(yīng)用【舷剩客戶端管理器通過一系列知名的API（JDBC, ODBC, OLE-DB …）提供不同的方式來訪問數(shù)據(jù)庫宁脊。

客戶端管理器也提供專有的數(shù)據(jù)庫訪問API。

當(dāng)你連接到數(shù)據(jù)庫時：

管理器首先檢查你的驗(yàn)證信息（用戶名和密碼）贤姆，然后檢查你是否有訪問數(shù)據(jù)庫的授權(quán)榆苞。這些權(quán)限由DBA分配。

然后庐氮，管理器檢查是否有空閑進(jìn)程（或線程）來處理你對查詢语稠。

管理器還會檢查數(shù)據(jù)庫是否負(fù)載很重宋彼。

管理器可能會等待一會兒來獲取需要的資源弄砍。如果等待時間達(dá)到超時時間，它會關(guān)閉連接并給出一個可讀的錯誤信息输涕。

然后管理器會把你的查詢送給查詢管理器來處理音婶。

因?yàn)椴樵兲幚磉M(jìn)程不是『不全則無』的，一旦它從查詢管理器得到數(shù)據(jù)莱坎，它會把部分結(jié)果保存到一個緩沖區(qū)并且開始給你發(fā)送衣式。

如果遇到問題，管理器關(guān)閉連接檐什，向你發(fā)送可讀的解釋信息碴卧，然后釋放資源。

客戶端管理器

查詢管理器

這部分是數(shù)據(jù)庫的威力所在乃正，在這部分里住册，一個寫得糟糕的查詢可以轉(zhuǎn)換成一個快速執(zhí)行的代碼，代碼執(zhí)行的結(jié)果被送到客戶端管理器瓮具。這個多步驟操作過程如下：

查詢首先被解析并判斷是否合法

然后被重寫荧飞，去除了無用的操作并且加入預(yù)優(yōu)化部分

接著被優(yōu)化以便提升性能凡人，并被轉(zhuǎn)換為可執(zhí)行代碼和數(shù)據(jù)訪問計劃。

然后計劃被編譯

最后叹阔，被執(zhí)行

這里我不會過多探討最后兩步挠轴，因?yàn)樗鼈儾惶匾?/p>

看完這部分后，如果你需要更深入的知識耳幢，我建議你閱讀：

關(guān)于成本優(yōu)化的初步研究論文(1979)：關(guān)系型數(shù)據(jù)庫系統(tǒng)存取路徑選擇岸晦。這個篇文章只有12頁，而且具備計算機(jī)一般水平就能理解帅掘。

非常好委煤、非常深入的 DB2 9.X 如何優(yōu)化查詢的介紹

非常好的PostgreSQL如何優(yōu)化查詢的介紹。這是一篇最通俗易懂的文檔修档，因?yàn)樗v的是『我們來看看在這種情況下碧绞，PostgreSQL給出了什么樣的查詢計劃』，而不是『我們來看看PostgreSQL用的什么算法』吱窝。

官方SQLite優(yōu)化文檔讥邻。『易于』閱讀院峡，因?yàn)镾QLite用的是簡單規(guī)則兴使。再者，這是唯一真正解釋SQLite如何工作的官方文檔照激。

非常好的SQL Server 2005 如何優(yōu)化查詢的介紹

Oracle 12c 優(yōu)化白皮書

2篇查詢優(yōu)化的教程发魄，第一篇 第二篇。教程來自《數(shù)據(jù)庫系統(tǒng)概念》的作者俩垃，很好的讀物励幼，集中討論磁盤I/O，但是要求具有很好的計算機(jī)科學(xué)水平口柳。

另一個原理教程苹粟，這篇教程我覺得更易懂，不過它僅關(guān)注聯(lián)接運(yùn)算符（join operators）和磁盤I/O跃闹。

查詢解析器

每一條SQL語句都要送到解析器來檢查語法嵌削，如果你的查詢有錯，解析器將拒絕該查詢望艺。比如苛秕，如果你寫成”SLECT …” 而不是 “SELECT …”，那就沒有下文了找默。

但這還不算完艇劫，解析器還會檢查關(guān)鍵字是否使用正確的順序，比如 WHERE 寫在 SELECT 之前會被拒絕啡莉。

然后港准，解析器要分析查詢中的表和字段旨剥，使用數(shù)據(jù)庫元數(shù)據(jù)來檢查：

表是否存在

表的字段是否存在

對某類型字段的 運(yùn)算 是否 可能（比如，你不能將整數(shù)和字符串進(jìn)行比較浅缸，你不能對一個整數(shù)使用 substring() 函數(shù)）

接著轨帜，解析器檢查在查詢中你是否有權(quán)限來讀取（或?qū)懭耄┍眈媒贰Ｔ購?qiáng)調(diào)一次：這些權(quán)限由DBA分配蚌父。

在解析過程中，SQL 查詢被轉(zhuǎn)換為內(nèi)部表示（通常是一個樹）毛萌。

如果一切正常苟弛，內(nèi)部表示被送到查詢重寫器。

查詢重寫器

在這一步阁将，我們已經(jīng)有了查詢的內(nèi)部表示膏秫，重寫器的目標(biāo)是：

預(yù)優(yōu)化查詢

避免不必要的運(yùn)算

幫助優(yōu)化器找到合理的最佳解決方案

重寫器按照一系列已知的規(guī)則對查詢執(zhí)行檢測。如果查詢匹配一種模式的規(guī)則做盅，查詢就會按照這條規(guī)則來重寫缤削。下面是（可選）規(guī)則的非詳盡的列表：

視圖合并：如果你在查詢中使用視圖，視圖就會轉(zhuǎn)換為它的 SQL 代碼吹榴。

子查詢扁平化：子查詢是很難優(yōu)化的亭敢，因此重寫器會嘗試移除子查詢

例如：

SELECT PERSON.*

FROM PERSON

WHERE PERSON.person_key IN

(SELECT MAILS.person_key

FROM MAILS

WHERE MAILS.mail LIKE 'christophe%');

會轉(zhuǎn)換為：

SELECT PERSON.*

FROM PERSON, MAILS

WHERE PERSON.person_key = MAILS.person_key

and MAILS.mail LIKE 'christophe%';

- 去除不必要的運(yùn)算符：比如，如果你用了 DISTINCT图筹，而其實(shí)你有 UNIQUE 約束（這本身就防止了數(shù)據(jù)出現(xiàn)重復(fù)）帅刀，那么 DISTINCT 關(guān)鍵字就被去掉了。

-?排除冗余的聯(lián)接：如果相同的 JOIN 條件出現(xiàn)兩次远剩，比如隱藏在視圖中的 JOIN 條件扣溺，或者由于傳遞性產(chǎn)生的無用 JOIN，都會被消除民宿。

-?常數(shù)計算賦值：如果你的查詢需要計算娇妓，那么在重寫過程中計算會執(zhí)行一次像鸡。比如 WHERE AGE > 10+2 會轉(zhuǎn)換為 WHERE AGE > 12 活鹰， TODATE(“日期字符串”) 會轉(zhuǎn)換為 datetime 格式的日期值。

-?（高級）分區(qū)裁剪（Partition Pruning）：如果你用了分區(qū)表只估，重寫器能夠找到需要使用的分區(qū)志群。

-?（高級）物化視圖重寫（Materialized view rewrite）：如果你有個物化視圖匹配查詢謂詞的一個子集，重寫器將檢查視圖是否最新并修改查詢蛔钙，令查詢使用物化視圖而不是原始表锌云。

-?（高級）自定義規(guī)則：如果你有自定義規(guī)則來修改查詢（就像 Oracle policy），重寫器就會執(zhí)行這些規(guī)則吁脱。

-?（高級）OLAP轉(zhuǎn)換：分析/加窗 函數(shù)桑涎，星形聯(lián)接彬向，ROLLUP 函數(shù)……都會發(fā)生轉(zhuǎn)換（但我不確定這是由重寫器還是優(yōu)化器來完成，因?yàn)閮蓚€進(jìn)程聯(lián)系很緊攻冷，必須看是什么數(shù)據(jù)庫）娃胆。 【譯者注： 物化視圖 。謂詞等曼，predicate里烦，條件表達(dá)式的求值返回真或假的過程】

重寫后的查詢接著送到優(yōu)化器，這時候好玩的就開始了禁谦。

統(tǒng)計

研究數(shù)據(jù)庫如何優(yōu)化查詢之前我們需要談?wù)劷y(tǒng)計胁黑，因?yàn)闆]有統(tǒng)計的數(shù)據(jù)庫是愚蠢的。除非你明確指示州泊，數(shù)據(jù)庫是不會分析自己的數(shù)據(jù)的丧蘸。沒有分析會導(dǎo)致數(shù)據(jù)庫做出（非常）糟糕的假設(shè)。

但是遥皂，數(shù)據(jù)庫需要什么類型的信息呢触趴？

我必須（簡要地）談?wù)剶?shù)據(jù)庫和操作系統(tǒng)如何保存數(shù)據(jù)。兩者使用的最小單位叫做頁或塊（默認(rèn) 4 或 8 KB）渴肉。這就是說如果你僅需要 1KB冗懦，也會占用一個頁。要是頁的大小為 8KB仇祭，你就浪費(fèi)了 7KB披蕉。

回來繼續(xù)講統(tǒng)計！ 當(dāng)你要求數(shù)據(jù)庫收集統(tǒng)計信息乌奇，數(shù)據(jù)庫會計算下列值：

表中行和頁的數(shù)量

表中每個列中的：

唯一值

數(shù)據(jù)長度（最小没讲，最大，平均）

數(shù)據(jù)范圍（最小礁苗，最大爬凑，平均）

表的索引信息

這些統(tǒng)計信息會幫助優(yōu)化器估計查詢所需的磁盤 I/O、CPU试伙、和內(nèi)存使用

對每個列的統(tǒng)計非常重要嘁信。

比如，如果一個表 PERSON 需要聯(lián)接 2 個列： LAST_NAME, FIRST_NAME疏叨。

根據(jù)統(tǒng)計信息潘靖，數(shù)據(jù)庫知道FIRST_NAME只有 1,000 個不同的值，LAST_NAME 有 1,000,000 個不同的值蚤蔓。

因此卦溢，數(shù)據(jù)庫就會按照 LAST_NAME, FIRST_NAME 聯(lián)接。

因?yàn)?LAST_NAME 不大可能重復(fù)，多數(shù)情況下比較 LAST_NAME 的頭 2 单寂、 3 個字符就夠了贬芥，這將大大減少比較的次數(shù)。

不過宣决，這些只是基本的統(tǒng)計誓军。你可以讓數(shù)據(jù)庫做一種高級統(tǒng)計，叫直方圖疲扎。直方圖是列值分布情況的統(tǒng)計信息昵时。例如：

出現(xiàn)最頻繁的值

分位數(shù) 【譯者注：http://baike.baidu.com/view/1323572.htm】

…

這些額外的統(tǒng)計會幫助數(shù)據(jù)庫找到更佳的查詢計劃，尤其是對于等式謂詞（例如： WHERE AGE = 18 ）或范圍謂詞（例如： WHERE AGE > 10 and AGE < 40）椒丧，因?yàn)閿?shù)據(jù)庫可以更好的了解這些謂詞相關(guān)的數(shù)字類型數(shù)據(jù)行（注：這個概念的技術(shù)名稱叫選擇率）壹甥。

統(tǒng)計信息保存在數(shù)據(jù)庫元數(shù)據(jù)內(nèi)，例如（非分區(qū)）表的統(tǒng)計信息位置：

Oracle： USER / ALL / DBA_TABLES 和 USER / ALL / DBA_TAB_COLUMNS

DB2： SYSCAT.TABLES 和 SYSCAT.COLUMNS

統(tǒng)計信息必須及時更新壶熏。如果一個表有 1,000,000 行而數(shù)據(jù)庫認(rèn)為它只有 500 行句柠，沒有比這更糟糕的了。統(tǒng)計唯一的不利之處是需要時間來計算棒假，這就是為什么數(shù)據(jù)庫大多默認(rèn)情況下不會自動計算統(tǒng)計信息溯职。數(shù)據(jù)達(dá)到百萬級時統(tǒng)計會變得困難，這時候帽哑，你可以選擇僅做基本統(tǒng)計或者在一個數(shù)據(jù)庫樣本上執(zhí)行統(tǒng)計谜酒。

舉個例子，我參與的一個項目需要處理每表上億條數(shù)據(jù)的庫妻枕，我選擇只統(tǒng)計10%僻族，結(jié)果造成了巨大的時間消耗。本例證明這是個糟糕的決定屡谐，因?yàn)橛袝r候 Oracle 10G 從特定表的特定列中選出的 10% 跟全部 100% 有很大不同（對于擁有一億行數(shù)據(jù)的表述么，這種情況極少發(fā)生）。這次錯誤的統(tǒng)計導(dǎo)致了一個本應(yīng) 30 秒完成的查詢最后執(zhí)行了 8 個小時愕掏，查找這個現(xiàn)象根源的過程簡直是個噩夢度秘。這個例子顯示了統(tǒng)計的重要性。

注：當(dāng)然了饵撑，每個數(shù)據(jù)庫還有其特定的更高級的統(tǒng)計剑梳。如果你想了解更多信息，讀讀數(shù)據(jù)庫的文檔肄梨。話雖然這么說阻荒，我已經(jīng)盡力理解統(tǒng)計是如何使用的了挠锥，而且我找到的最好的官方文檔來自PostgreSQL众羡。

查詢優(yōu)化器

所有的現(xiàn)代數(shù)據(jù)庫都在用基于成本的優(yōu)化（即CBO）來優(yōu)化查詢。道理是針對每個運(yùn)算設(shè)置一個成本蓖租，通過應(yīng)用成本最低廉的一系列運(yùn)算粱侣，來找到最佳的降低查詢成本的方法羊壹。

為了理解成本優(yōu)化器的原理，我覺得最好用個例子來『感受』一下這個任務(wù)背后的復(fù)雜性齐婴。這里我將給出聯(lián)接 2 個表的 3 個方法油猫，我們很快就能看到即便一個簡單的聯(lián)接查詢對于優(yōu)化器來說都是個噩夢。之后柠偶，我們會了解真正的優(yōu)化器是怎么做的情妖。

對于這些聯(lián)接操作，我會專注于它們的時間復(fù)雜度诱担，但是毡证，數(shù)據(jù)庫優(yōu)化器計算的是它們的 CPU 成本、磁盤 I/O 成本蔫仙、和內(nèi)存需求料睛。時間復(fù)雜度和 CPU 成本的區(qū)別是，時間成本是個近似值（給我這樣的懶家伙準(zhǔn)備的）摇邦。而 CPU 成本恤煞，我這里包括了所有的運(yùn)算，比如：加法施籍、條件判斷居扒、乘法、迭代……還有呢：

每一個高級代碼運(yùn)算都要特定數(shù)量的低級 CPU 運(yùn)算丑慎。

對于 Intel Core i7苔货、Intel Pentium 4、AMD Opteron…等立哑，（就 CPU 周期而言）CPU 的運(yùn)算成本是不同的夜惭，也就是說它取決于 CPU 的架構(gòu)。

使用時間復(fù)雜度就容易多了（至少對我來說）铛绰，用它我也能了解到 CBO 的概念诈茧。由于磁盤 I/O 是個重要的概念，我偶爾也會提到它捂掰。請牢記敢会，大多數(shù)時候瓶頸在于磁盤 I/O 而不是 CPU 使用。

索引

在研究 B+樹的時候我們談到了索引这嚣，要記住一點(diǎn)鸥昏，索引都是已經(jīng)排了序的。

僅供參考：還有其他類型的索引姐帚，比如位圖索引吏垮，在 CPU、磁盤I/O、和內(nèi)存方面與B+樹索引的成本并不相同膳汪。

另外唯蝶，很多現(xiàn)代數(shù)據(jù)庫為了改善執(zhí)行計劃的成本，可以僅為當(dāng)前查詢動態(tài)地生成臨時索引遗嗽。

存取路徑

在應(yīng)用聯(lián)接運(yùn)算符（join operators）之前粘我，你首先需要獲得數(shù)據(jù)。以下就是獲得數(shù)據(jù)的方法痹换。

注：由于所有存取路徑的真正問題是磁盤 I/O征字，我不會過多探討時間復(fù)雜度。

【譯者注：四種類型的Oracle索引掃描介紹 】

全掃描

如果你讀過執(zhí)行計劃娇豫，一定看到過『全掃描』（或只是『掃描』）一詞柔纵。簡單的說全掃描就是數(shù)據(jù)庫完整的讀一個表或索引。就磁盤 I/O 而言锤躁，很明顯全表掃描的成本比索引全掃描要高昂搁料。

范圍掃描

其他類型的掃描有索引范圍掃描，比如當(dāng)你使用謂詞 ” WHERE AGE > 20 AND AGE < 40 ” 的時候它就會發(fā)生系羞。

當(dāng)然郭计，你需要在 AGE 字段上有索引才能用到索引范圍掃描。

在第一部分我們已經(jīng)知道椒振，范圍查詢的時間成本大約是 log(N)+M昭伸，這里 N 是索引的數(shù)據(jù)量，M 是范圍內(nèi)估測的行數(shù)澎迎。多虧有了統(tǒng)計我們才能知道 N 和 M 的值（注： M 是謂詞 “ AGE > 20 AND AGE < 40 ” 的選擇率）庐杨。另外范圍掃描時，你不需要讀取整個索引夹供，因此在磁盤 I/O 方面沒有全掃描那么昂貴灵份。

唯一掃描

如果你只需要從索引中取一個值你可以用唯一掃描。

根據(jù) ROW ID 存取

多數(shù)情況下哮洽，如果數(shù)據(jù)庫使用索引填渠，它就必須查找與索引相關(guān)的行，這樣就會用到根據(jù) ROW ID 存取的方式鸟辅。

例如氛什，假如你運(yùn)行：

SELECT LASTNAME, FIRSTNAME from PERSON WHERE AGE = 28

如果 person 表的 age 列有索引，優(yōu)化器會使用索引找到所有年齡為 28 的人匪凉，然后它會去表中讀取相關(guān)的行枪眉，這是因?yàn)樗饕兄挥?age 的信息而你要的是姓和名。

但是再层，假如你換個做法：

SELECT TYPE_PERSON.CATEGORY from PERSON ,TYPE_PERSON

WHERE PERSON.AGE = TYPE_PERSON.AGE

PERSON 表的索引會用來聯(lián)接 TYPE_PERSON 表贸铜，但是 PERSON 表不會根據(jù)行ID 存取堡纬，因?yàn)槟悴]有要求這個表內(nèi)的信息。

雖然這個方法在少量存取時表現(xiàn)很好萨脑，這個運(yùn)算的真正問題其實(shí)是磁盤 I/O隐轩。假如需要大量的根據(jù)行ID存取饺饭，數(shù)據(jù)庫也許會選擇全掃描渤早。

其它路徑

我沒有列舉所有的存取路徑，如果你感興趣可以讀一讀 Oracle文檔瘫俊。其它數(shù)據(jù)庫里也許叫法不同但背后的概念是一樣的鹊杖。

聯(lián)接運(yùn)算符

那么，我們知道如何獲取數(shù)據(jù)了扛芽，那現(xiàn)在就把它們聯(lián)接起來骂蓖！

我要展現(xiàn)的是3個個常用聯(lián)接運(yùn)算符：合并聯(lián)接（Merge join），哈希聯(lián)接（Hash Join）和嵌套循環(huán)聯(lián)接（Nested Loop Join）川尖。但是在此之前登下，我需要引入新詞匯了：內(nèi)關(guān)系和外關(guān)系（ inner relation and outer relation） 【譯者注： “內(nèi)關(guān)系和外關(guān)系” 這個說法來源不明，跟查詢的“內(nèi)聯(lián)接（INNER JOIN） 叮喳、外聯(lián)接（OUTER JOIN） ” 不是一個概念 被芳。只查到百度百科詞條：關(guān)系數(shù)據(jù)庫 里提到“每個表格（有時被稱為一個關(guān)系）……” 。 其他參考鏈接 “Merge Join” “Hash Join” “Nested Loop Join” 】 馍悟。 一個關(guān)系可以是：

一個表

一個索引

上一個運(yùn)算的中間結(jié)果（比如上一個聯(lián)接運(yùn)算的結(jié)果）

當(dāng)你聯(lián)接兩個關(guān)系時畔濒，聯(lián)接算法對兩個關(guān)系的處理是不同的。在本文剩余部分锣咒，我將假定：

外關(guān)系是左側(cè)數(shù)據(jù)集

內(nèi)關(guān)系是右側(cè)數(shù)據(jù)集

比如侵状， A JOIN B 是 A 和 B 的聯(lián)接，這里 A 是外關(guān)系毅整，B 是內(nèi)關(guān)系趣兄。

多數(shù)情況下， A JOIN B 的成本跟 B JOIN A 的成本是不同的悼嫉。

在這一部分诽俯，我還將假定外關(guān)系有 N 個元素，內(nèi)關(guān)系有 M 個元素承粤。要記住暴区，真實(shí)的優(yōu)化器通過統(tǒng)計知道 N 和 M 的值。

注：N 和 M 是關(guān)系的基數(shù)辛臊∠闪唬【譯者注： 基數(shù) 】

嵌套循環(huán)聯(lián)接

嵌套循環(huán)聯(lián)接是最簡單的。

道理如下：

針對外關(guān)系的每一行

查看內(nèi)關(guān)系里的所有行來尋找匹配的行

下面是偽代碼：

nested_loop_join(array outer, array inner)

? for each row a in outer

? ? for each row b in inner

? ? ? if (match_join_condition(a,b))

? ? ? ? write_result_in_output(a,b)

? ? ? end if

? ? end for

? end for

由于這是個雙迭代彻舰，時間復(fù)雜度是 O(N*M)伐割。

在磁盤 I/O 方面候味， 針對 N 行外關(guān)系的每一行，內(nèi)部循環(huán)需要從內(nèi)關(guān)系讀取 M 行隔心。這個算法需要從磁盤讀取 N+ N*M 行白群。但是，如果內(nèi)關(guān)系足夠小硬霍，你可以把它讀入內(nèi)存帜慢，那么就只剩下 M + N 次讀取。這樣修改之后唯卖，內(nèi)關(guān)系必須是最小的粱玲，因?yàn)樗懈髾C(jī)會裝入內(nèi)存。

在CPU成本方面沒有什么區(qū)別拜轨，但是在磁盤 I/O 方面抽减，最好最好的，是每個關(guān)系只讀取一次橄碾。

當(dāng)然卵沉，內(nèi)關(guān)系可以由索引代替，對磁盤 I/O 更有利法牲。

由于這個算法非常簡單史汗，下面這個版本在內(nèi)關(guān)系太大無法裝入內(nèi)存時，對磁盤 I/O 更加有利皆串。道理如下：

為了避免逐行讀取兩個關(guān)系淹办，

你可以成簇讀取，把（兩個關(guān)系里讀到的）兩簇數(shù)據(jù)行保存在內(nèi)存里恶复，

比較兩簇數(shù)據(jù)怜森，保留匹配的，

然后從磁盤加載新的數(shù)據(jù)簇來繼續(xù)比較

直到加載了所有數(shù)據(jù)谤牡。

可能的算法如下：

// improved version to reduce the disk I/O.

nested_loop_join_v2(file outer, file inner)

? for each bunch ba in outer

? // ba is now in memory

? ? for each bunch bb in inner

? ? ? ? // bb is now in memory

? ? ? ? for each row a in ba

? ? ? ? ? for each row b in bb

? ? ? ? ? ? if (match_join_condition(a,b))

? ? ? ? ? ? ? write_result_in_output(a,b)

? ? ? ? ? ? end if

? ? ? ? ? end for

? ? ? end for

? ? end for

? end for

使用這個版本副硅，時間復(fù)雜度沒有變化，但是磁盤訪問降低了：

用前一個版本翅萤，算法需要 N + N*M 次訪問（每次訪問讀取一行）恐疲。

用新版本，磁盤訪問變?yōu)?外關(guān)系的數(shù)據(jù)簇數(shù)量 + 外關(guān)系的數(shù)據(jù)簇數(shù)量 * 內(nèi)關(guān)系的數(shù)據(jù)簇數(shù)量套么。

增加數(shù)據(jù)簇的尺寸培己，可以降低磁盤訪問。

哈希聯(lián)接

哈希聯(lián)接更復(fù)雜胚泌，不過在很多場合比嵌套循環(huán)聯(lián)接成本低省咨。

哈希聯(lián)接的道理是：

1) 讀取內(nèi)關(guān)系的所有元素

2) 在內(nèi)存里建一個哈希表

3) 逐條讀取外關(guān)系的所有元素

4) （用哈希表的哈希函數(shù)）計算每個元素的哈希值，來查找內(nèi)關(guān)系里相關(guān)的哈希桶內(nèi)

5) 是否與外關(guān)系的元素匹配玷室。

在時間復(fù)雜度方面我需要做些假設(shè)來簡化問題：

內(nèi)關(guān)系被劃分成 X 個哈希桶

哈希函數(shù)幾乎均勻地分布每個關(guān)系內(nèi)數(shù)據(jù)的哈希值零蓉，就是說哈希桶大小一致笤受。

外關(guān)系的元素與哈希桶內(nèi)的所有元素的匹配，成本是哈希桶內(nèi)元素的數(shù)量敌蜂。

時間復(fù)雜度是 (M/X) * (N/X) + 創(chuàng)建哈希表的成本(M) + 哈希函數(shù)的成本 * N 箩兽。

如果哈希函數(shù)創(chuàng)建了足夠小規(guī)模的哈希桶，那么復(fù)雜度就是 O(M+N)章喉。

還有個哈希聯(lián)接的版本汗贫，對內(nèi)存有利但是對磁盤 I/O 不夠有利。 這回是這樣的：

1) 計算內(nèi)關(guān)系和外關(guān)系雙方的哈希表

2) 保存哈希表到磁盤

3) 然后逐個哈希桶比較（其中一個讀入內(nèi)存囊陡，另一個逐行讀确技ā）掀亥。

---------------------

作者：火山石

來源：CSDN

原文：https://blog.csdn.net/zhangcanyan/article/details/51439021

版權(quán)聲明：本文為博主原創(chuàng)文章撞反，轉(zhuǎn)載請附上博文鏈接！