大數(shù)據(jù)中數(shù)據(jù)庫(kù)是如何工作的（二）

　　數(shù)據(jù)庫(kù)是可以輕松訪(fǎng)問(wèn)和修改的信息的集合，但是一堆簡(jiǎn)單的文件也可以做到這一點(diǎn)。實(shí)際上，最簡(jiǎn)單的數(shù)據(jù)庫(kù)(如SQLite)僅是一堆文件，你知道大數(shù)據(jù)中數(shù)據(jù)庫(kù)是如何工作的嗎?
 

　　SQLite是一堆精心設(shè)計(jì)的文件，因?yàn)樗试S你執(zhí)行以下操作：使用確保數(shù)據(jù)安全和連貫的交易，即使你正在處理數(shù)百萬(wàn)個(gè)數(shù)據(jù)，也可以快速處理數(shù)據(jù)，數(shù)據(jù)庫(kù)可以如下圖所示：
 

　　將數(shù)據(jù)庫(kù)分為相互交互的多個(gè)組件。
 

　　核心組件：
 

　　進(jìn)程管理器：許多數(shù)據(jù)庫(kù)都有一個(gè)需要管理的進(jìn)程/線(xiàn)程池。而且，為了獲得納秒級(jí)的性能，某些現(xiàn)代數(shù)據(jù)庫(kù)使用其自己的線(xiàn)程而不是操作系統(tǒng)線(xiàn)程。
 

　　網(wǎng)絡(luò)管理員：網(wǎng)絡(luò)I / O是一個(gè)大問(wèn)題，尤其是對(duì)于分布式數(shù)據(jù)庫(kù)。這就是為什么某些數(shù)據(jù)庫(kù)擁有自己的管理器的原因。
 

　　文件系統(tǒng)管理器：磁盤(pán)I / O是數(shù)據(jù)庫(kù)的第一個(gè)瓶頸。重要的是擁有一個(gè)能夠完美處理操作系統(tǒng)文件系統(tǒng)甚至替換它的管理器。
 

　　內(nèi)存管理器：為避免磁盤(pán)I / O損失，需要大量的內(nèi)存。但是，如果你處理大量?jī)?nèi)存，則需要高效的內(nèi)存管理器。尤其是當(dāng)你有多個(gè)查詢(xún)同時(shí)使用內(nèi)存時(shí)。
 

　　安全管理器：用于管理用戶(hù)的身份驗(yàn)證和授權(quán)
 

　　客戶(hù)經(jīng)理：用于管理客戶(hù)連接
 

　　…
 

　　工具：
 

　　備份管理器：用于保存和還原數(shù)據(jù)庫(kù)。
 

　　Recovery Manager：用于在崩潰后以一致的狀態(tài)重新啟動(dòng)數(shù)據(jù)庫(kù)
 

　　監(jiān)視管理器：用于記錄數(shù)據(jù)庫(kù)的活動(dòng)并提供監(jiān)視數(shù)據(jù)庫(kù)的工具
 

　　管理管理器：用于存儲(chǔ)元數(shù)據(jù)(如表的名稱(chēng)和結(jié)構(gòu))，并提供工具來(lái)管理數(shù)據(jù)庫(kù)，模式，表空間.....
 

　　查詢(xún)管理器：
 

　　查詢(xún)解析器：檢查查詢(xún)是否有效
 

　　查詢(xún)重寫(xiě)器：預(yù)優(yōu)化查詢(xún)
 

　　查詢(xún)優(yōu)化器：優(yōu)化查詢(xún)
 

　　查詢(xún)執(zhí)行器：編譯并執(zhí)行查詢(xún)
 

　　數(shù)據(jù)管理器：
 

　　交易經(jīng)理：處理交易
 

　　高速緩存管理器：在使用數(shù)據(jù)之前先將其放入內(nèi)存中，然后在將其寫(xiě)入磁盤(pán)之前先將其放入內(nèi)存中
 

　　數(shù)據(jù)訪(fǎng)問(wèn)管理器：訪(fǎng)問(wèn)磁盤(pán)上的數(shù)據(jù)
 

　　對(duì)于本文的其余部分，我將重點(diǎn)介紹數(shù)據(jù)庫(kù)如何通過(guò)以下過(guò)程來(lái)管理SQL查詢(xún)：
 

　　客戶(hù)經(jīng)理
 

　　查詢(xún)管理器
 

　　數(shù)據(jù)管理器(在這一部分中，我還將包括恢復(fù)管理器)
 

　　客戶(hù)經(jīng)理
 

　　客戶(hù)經(jīng)理是處理與客戶(hù)通信的部分?？蛻?hù)端可以是(Web)服務(wù)器或最終用戶(hù)/最終應(yīng)用程序?？蛻?hù)端管理器提供了通過(guò)一組著名的API訪(fǎng)問(wèn)數(shù)據(jù)庫(kù)的不同方法：JDBC，ODBC，OLE-DB…
 

　　它還可以提供專(zhuān)有的數(shù)據(jù)庫(kù)訪(fǎng)問(wèn)API。
 

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

　　管理員首先檢查你的身份驗(yàn)證(你的登錄名和密碼)，然后檢查你是否具有使用該數(shù)據(jù)庫(kù)的授權(quán)。這些訪(fǎng)問(wèn)權(quán)限由你的DBA設(shè)置。
 

　　然后，它檢查是否有一個(gè)進(jìn)程(或線(xiàn)程)可用于管理你的查詢(xún)。
 

　　它還會(huì)檢查數(shù)據(jù)庫(kù)是否不處于高負(fù)荷狀態(tài)。
 

　　它可以等待片刻以獲取所需的資源。如果此等待達(dá)到超時(shí)，它將關(guān)閉連接并給出可讀的錯(cuò)誤消息。
 

　　然后它將你的查詢(xún)發(fā)送到查詢(xún)管理器并處理你的查詢(xún)
 

　　由于查詢(xún)處理不是“全有或全無(wú)”的事情，因此，一旦它從查詢(xún)管理器獲取數(shù)據(jù)，它將部分結(jié)果存儲(chǔ) 在緩沖區(qū)中并開(kāi)始將其發(fā)送給你。
 

　　出現(xiàn)問(wèn)題時(shí)，它將停止連接，為你提供易于閱讀的解釋并釋放資源。
 

　　查詢(xún)管理器
 

　　這是數(shù)據(jù)庫(kù)功能所在的地方。在這一部分中，將寫(xiě)得不好的查詢(xún)轉(zhuǎn)換為快速的可執(zhí)行代碼。然后執(zhí)行代碼，并將結(jié)果返回給客戶(hù)管理器。這是一個(gè)多步驟操作：首先解析查詢(xún)以查看其是否有效，然后將其重寫(xiě)以刪除無(wú)用的操作并添加一些預(yù)優(yōu)化，然后對(duì)其進(jìn)行優(yōu)化以提高性能，并將其轉(zhuǎn)變?yōu)閳?zhí)行和數(shù)據(jù)訪(fǎng)問(wèn)計(jì)劃，然后編制計(jì)劃，最后執(zhí)行。
 

　　PostgreSQL的如何優(yōu)化一個(gè)很好的演示查詢(xún)這里。這是最易訪(fǎng)問(wèn)的文檔，因?yàn)樗?ldquo;讓我們看看PostgreSQL使用的算法”更多地是關(guān)于“讓我們看看PostgreSQL在這些情況下給出的查詢(xún)計(jì)劃”。
 

　　有關(guān)優(yōu)化的官方SQLite文檔。它很容易閱讀，因?yàn)镾QLite使用簡(jiǎn)單的規(guī)則。而且，這是唯一真正說(shuō)明其工作原理的官方文檔。
 

　　查詢(xún)解析器
 

　　每個(gè)SQL語(yǔ)句都發(fā)送到解析器，在該處檢查語(yǔ)法是否正確。如果你在查詢(xún)中輸入錯(cuò)誤，則解析器將拒絕該查詢(xún)。例如，如果你寫(xiě)的是“ SLECT…”而不是“ SELECT…”，那么故事到此結(jié)束。
 

　　但這更深了，它還檢查是否以正確的順序使用了關(guān)鍵字。例如，SELECT之前的WHERE將被拒絕。然后，分析查詢(xún)中的表和字段。解析器使用數(shù)據(jù)庫(kù)的元數(shù)據(jù)來(lái)檢查：如果這些表存在;如果表的字段存在;如果可以對(duì)字段類(lèi)型進(jìn)行操作(例如，你不能將整數(shù)與字符串進(jìn)行比較，則不能對(duì)整數(shù)使用substring()函數(shù))。然后，它檢查你是否具有讀取(或?qū)懭?查詢(xún)中的表的權(quán)限。同樣，這些對(duì)表的訪(fǎng)問(wèn)權(quán)限由你的DBA設(shè)置。
 

　　在此解析期間，SQL查詢(xún)將轉(zhuǎn)換為內(nèi)部表示形式(通常為樹(shù))，如果一切正常，則將內(nèi)部表示形式發(fā)送到查詢(xún)重寫(xiě)器。
 

　　查詢(xún)重寫(xiě)器
 

　　在此步驟中，我們具有查詢(xún)的內(nèi)部表示。重寫(xiě)器的目的是：預(yù)優(yōu)化查詢(xún)，避免不必要的操作，幫助優(yōu)化器找到最佳解決方案
 

　　重寫(xiě)器在查詢(xún)中執(zhí)行已知規(guī)則的列表。如果查詢(xún)符合規(guī)則的模式，則將應(yīng)用規(guī)則并重寫(xiě)查詢(xún)。以下是(可選)規(guī)則的詳盡列表：
 

　　視圖合并：如果你在查詢(xún)中使用視圖，則將使用該視圖的SQL代碼轉(zhuǎn)換該視圖。
 

　　子查詢(xún)展平：很難優(yōu)化子查詢(xún)，因此重寫(xiě)器將嘗試使用子查詢(xún)修改查詢(xún)以刪除子查詢(xún)。
 

　　刪除不必要的運(yùn)算符：例如，如果使用DISTINCT卻有一個(gè)UNIQUE約束來(lái)防止數(shù)據(jù)不唯一，則DISTINCT關(guān)鍵字將被刪除。
 

　　冗余聯(lián)接消除：如果由于一個(gè)聯(lián)接條件被隱藏在視圖中而使你擁有兩次相同的聯(lián)接條件，或者由于傳遞性而存在無(wú)用的聯(lián)接，則將其刪除。
 

　　恒定算術(shù)評(píng)估：如果編寫(xiě)需要演算的內(nèi)容，則在重寫(xiě)過(guò)程中將對(duì)其進(jìn)行一次計(jì)算。例如，將WHERE AGE> 10 + 2轉(zhuǎn)換為WHERE AGE> 12，然后將TODATE(“ some date”)轉(zhuǎn)換為datetime格式的日期
 

　　(高級(jí))分區(qū)修剪：如果你使用的是分區(qū)表，重寫(xiě)器將能夠找到要使用的分區(qū)。
 

　　(高級(jí))實(shí)例化視圖重寫(xiě)：如果你具有與查詢(xún)中的謂詞子集匹配的實(shí)例化視圖，則重寫(xiě)器將檢查該視圖是否為最新視圖，并將查詢(xún)修改為使用實(shí)例化視圖而不是原始表。
 

　　(高級(jí))自定義規(guī)則：如果你具有用于修改查詢(xún)的自定義規(guī)則(例如Oracle策略)，則重寫(xiě)器將執(zhí)行這些規(guī)則
 

　　(高級(jí))Olap轉(zhuǎn)換：分析/窗口函數(shù)，星型連接，匯總……也都進(jìn)行了轉(zhuǎn)換(但是我不確定是由重寫(xiě)器還是優(yōu)化器完成的，因?yàn)檫@兩個(gè)過(guò)程都非常接近，它必須取決于數(shù)據(jù)庫(kù))。然后，這個(gè)重寫(xiě)的查詢(xún)將發(fā)送到查詢(xún)優(yōu)化器。
 

　　統(tǒng)計(jì)數(shù)據(jù)：在我們看到數(shù)據(jù)庫(kù)如何優(yōu)化查詢(xún)之前，我們需要先談?wù)劷y(tǒng)計(jì)信息，因?yàn)闆](méi)有統(tǒng)計(jì)信息，數(shù)據(jù)庫(kù)是愚蠢的。如果你不告訴數(shù)據(jù)庫(kù)分析自己的數(shù)據(jù)，它將不會(huì)這樣做，并且會(huì)做出(非常)錯(cuò)誤的假設(shè)。
 

　　數(shù)據(jù)庫(kù)和操作系統(tǒng)如何存儲(chǔ)數(shù)據(jù)?他們利用所謂的最小單位一個(gè) 頁(yè)面或塊(4或8千字節(jié)默認(rèn)情況下)。這意味著，如果你只需要1 KB，則將花費(fèi)你一頁(yè)。如果頁(yè)面占用8 KB，那么你將浪費(fèi)7 KB。
 

　　當(dāng)你要求數(shù)據(jù)庫(kù)收集統(tǒng)計(jì)信息時(shí)，它計(jì)算的值如下：表中的行數(shù)/頁(yè)數(shù);對(duì)于表中的每一列：不同的數(shù)據(jù)值，數(shù)據(jù)值的長(zhǎng)度(最小值，最大值，平均值)，數(shù)據(jù)范圍信息(最小值，最大值，平均值)，有關(guān)表索引的信息。
 

　　這些統(tǒng)計(jì)信息將幫助優(yōu)化器估計(jì)查詢(xún)的 磁盤(pán)I / O，CPU和內(nèi)存使用率。
 

　　每列的統(tǒng)計(jì)信息非常重要。例如，如果需要在2列上聯(lián)接表PERSON：LAST_NAME，F(xiàn)IRST_NAME。根據(jù)統(tǒng)計(jì)信息，數(shù)據(jù)庫(kù)知道FIRST_NAME上只有1000個(gè)不同的值，而LAST_NAME上只有1000萬(wàn)個(gè)不同的值。因此，數(shù)據(jù)庫(kù)將聯(lián)接LAST_NAME，F(xiàn)IRST_NAME而不是FIRST_NAME，LAST_NAME上的數(shù)據(jù)，因?yàn)樗a(chǎn)生的方式比較少，因?yàn)長(zhǎng)AST_NAME不太可能相同，因此大多數(shù)情況下，比較數(shù)據(jù)庫(kù)的第2個(gè)(或3個(gè))首字符LAST_NAME就足夠了。
 

　　但是這些是基本統(tǒng)計(jì)數(shù)據(jù)。你可以要求數(shù)據(jù)庫(kù)計(jì)算稱(chēng)為直方圖的高級(jí)統(tǒng)計(jì)信息。直方圖是統(tǒng)計(jì)信息，用于通知列中值的分布。
 

　　這些額外的統(tǒng)計(jì)信息將幫助數(shù)據(jù)庫(kù)找到更好的查詢(xún)計(jì)劃。特別是對(duì)于相等謂詞(例如：WHERE AGE = 18)或范圍謂詞(例如：WHERE AGE> 10和AGE <40)，因?yàn)閿?shù)據(jù)庫(kù)會(huì)對(duì)這些謂詞所涉及的行數(shù)有更好的了解(請(qǐng)注意：這個(gè)概念就是選擇性)。
 

　　統(tǒng)計(jì)信息存儲(chǔ)在數(shù)據(jù)庫(kù)的元數(shù)據(jù)中。該統(tǒng)計(jì)數(shù)據(jù)必須是最新的。沒(méi)有什么比數(shù)據(jù)庫(kù)認(rèn)為表只有500行而表有1 000 000行更糟糕的了。統(tǒng)計(jì)信息的唯一缺點(diǎn)是計(jì)算它們需要時(shí)間。這就是為什么在大多數(shù)數(shù)據(jù)庫(kù)中默認(rèn)情況下不會(huì)自動(dòng)計(jì)算它們的原因。數(shù)以百萬(wàn)計(jì)的數(shù)據(jù)很難對(duì)其進(jìn)行計(jì)算。在這種情況下，你可以選擇僅計(jì)算基本統(tǒng)計(jì)信息或計(jì)算數(shù)據(jù)庫(kù)樣本的統(tǒng)計(jì)信息。
 

　　查詢(xún)優(yōu)化器

　　所有現(xiàn)代數(shù)據(jù)庫(kù)都使用基于成本的優(yōu)化(CBO)來(lái)優(yōu)化查詢(xún)。這樣做的目的是為每次操作增加成本，并通過(guò)使用最便宜的操作鏈來(lái)獲取結(jié)果，從而找到降低查詢(xún)成本的最佳方法。
 

　　為了理解成本優(yōu)化器的工作原理，最好有一個(gè)示例來(lái)“感覺(jué)”該任務(wù)背后的復(fù)雜性。即使是簡(jiǎn)單的聯(lián)接查詢(xún)也是要優(yōu)化的噩夢(mèng)。
 

　　對(duì)于這些連接，專(zhuān)注于自己的時(shí)間復(fù)雜度，但一個(gè)數(shù)據(jù)庫(kù)優(yōu)化計(jì)算的CPU成本，磁盤(pán)I / O成本和存儲(chǔ)空間需求。時(shí)間復(fù)雜度和CPU成本之間的區(qū)別在于，時(shí)間成本非常近似。對(duì)于CPU成本，應(yīng)該將每個(gè)操作都算作加法，“ if語(yǔ)句”，乘法，迭代…等等。此外：每個(gè)高級(jí)代碼操作都有特定數(shù)量的低級(jí)CPU操作。
 

　　無(wú)論你使用的是Intel Core i7，Intel Pentium 4，AMD Opteron…，CPU操作的成本(在CPU周期方面)都不相同。換句話(huà)說(shuō)，它取決于CPU體系結(jié)構(gòu)。使用時(shí)間復(fù)雜度更容易，并且有了它，我們?nèi)匀豢梢缘玫紺BO的概念，瓶頸通常是磁盤(pán)I / O而不是CPU使用率。
 

　　指標(biāo)
 

　　看到B + Trees時(shí)談到索引，這些索引就已經(jīng)排序了。還有其他類(lèi)型的索引，例如位圖索引。在CPU，磁盤(pán)I / O和內(nèi)存方面，它們提供的成本與B + Tree索引所提供的成本不一樣。此外，如果可以提高執(zhí)行計(jì)劃的成本，許多現(xiàn)代數(shù)據(jù)庫(kù)可以?xún)H為當(dāng)前查詢(xún)動(dòng)態(tài)創(chuàng)建臨時(shí)索引。
 

　　存取路徑：在應(yīng)用聯(lián)接運(yùn)算符之前，你首先需要獲取數(shù)據(jù)。這是獲取數(shù)據(jù)的方法。
 

　　全面掃描：如果你曾經(jīng)閱讀過(guò)執(zhí)行計(jì)劃，那么你肯定已經(jīng)看到“完全掃描”(或僅掃描)一詞。完全掃描只是數(shù)據(jù)庫(kù)完全讀取一個(gè)表或一個(gè)索引。就磁盤(pán)I / O而言，表完全掃描顯然比索引完全掃描更昂貴。
 

　　范圍掃描：還有其他類(lèi)型的掃描，例如索引范圍掃描。例如，當(dāng)你使用“ WHERE AGE> 20 AND AGE <40”這樣的謂詞時(shí)，將使用它。你需要在AGE字段上有一個(gè)索引才能使用此索引范圍掃描。
 

　　范圍查詢(xún)的時(shí)間成本類(lèi)似于log(N)+ M，其中N是此索引中的數(shù)據(jù)數(shù)，而M是對(duì)該范圍內(nèi)的行數(shù)的估計(jì)。由于統(tǒng)計(jì)信息，N和M值都已知(注意：M是謂詞AGE> 20 AND AGE <40的選擇性)。而且，對(duì)于范圍掃描，你不需要讀取完整索引，因此就磁盤(pán)I / O而言，它比完整掃描便宜。
 

　　獨(dú)特掃描：如果你只需要索引中的一個(gè)值，則可以使用唯一掃描。
 

　　按行ID訪(fǎng)問(wèn)：在大多數(shù)情況下，如果數(shù)據(jù)庫(kù)使用索引，則它將不得不查找與索引關(guān)聯(lián)的行。為此，它將使用按行ID進(jìn)行的訪(fǎng)問(wèn)。
 

　　如果你有一個(gè)列年齡的人的索引，那么優(yōu)化器將使用該索引查找所有28歲的人，然后它會(huì)詢(xún)問(wèn)表中的關(guān)聯(lián)行，因?yàn)樗饕齼H包含有關(guān)年齡的信息，并且你想知道姓氏和名字。
 

　　SELECT TYPE_PERSON.CATEGORY from PERSON ,TYPE_PERSON
 

　　WHERE PERSON.AGE = TYPE_PERSON.AGE
 

　　PERSON上的索引將用于與TYPE_PERSON聯(lián)接，但是行ID將無(wú)法訪(fǎng)問(wèn)表PERSON，因?yàn)槟銢](méi)有在該表上詢(xún)問(wèn)信息。
 

　　盡管它對(duì)于某些訪(fǎng)問(wèn)非常有效，但此操作的真正問(wèn)題是磁盤(pán)I / O。如果你需要通過(guò)行ID進(jìn)行太多訪(fǎng)問(wèn)，則數(shù)據(jù)庫(kù)可能會(huì)選擇完全掃描。
 

　　3個(gè)常見(jiàn)的聯(lián)接運(yùn)算符：合并聯(lián)接，哈希聯(lián)接和嵌套循環(huán)聯(lián)接。
 

　　當(dāng)你連接兩個(gè)關(guān)系時(shí)，連接算法對(duì)兩個(gè)關(guān)系的管理方式不同。在本文的其余部分，假定：外部關(guān)系是左數(shù)據(jù)集，內(nèi)部關(guān)系是正確的數(shù)據(jù)集。A JOIN B是A和B之間的聯(lián)接，其中A是外部關(guān)系，B是內(nèi)部關(guān)系。在大多數(shù)情況下，A JOIN B的成本與B JOIN A的成本不同。在這一部分中，假設(shè)外部關(guān)系具有N個(gè)元素 ，內(nèi)部關(guān)系具有M個(gè)元素。真正的優(yōu)化程序可以通過(guò)統(tǒng)計(jì)信息了解N和M的值，N和M是關(guān)系的基數(shù)。
 

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

　　對(duì)于外部關(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
 

　　由于是兩次迭代，因此時(shí)間復(fù)雜度為O(N * M)。就磁盤(pán)I / O而言，對(duì)于外部關(guān)系中的N行中的每行，內(nèi)部循環(huán)都需要從內(nèi)部關(guān)系中讀取M行。該算法需要從磁盤(pán)讀取N + N * M行。但是，如果內(nèi)部關(guān)系足夠小，則可以將該關(guān)系存儲(chǔ)在內(nèi)存中，并且只需進(jìn)行M + N次讀取即可。通過(guò)這種修改，內(nèi)部關(guān)系必須是最小的，因?yàn)樗懈嗟臋C(jī)會(huì)適合內(nèi)存。
 

　　就時(shí)間復(fù)雜度而言，沒(méi)有什么區(qū)別，就磁盤(pán)I / O而言，最好只讀取一次兩個(gè)關(guān)系。當(dāng)然，內(nèi)部關(guān)系可以用索引代替，這對(duì)于磁盤(pán)I / O會(huì)更好。由于此算法非常簡(jiǎn)單，因此如果內(nèi)部關(guān)系太大而無(wú)法容納在內(nèi)存中，則這是另一個(gè)對(duì)磁盤(pán)I / O更友好的版本，不是逐行閱讀兩個(gè)關(guān)系。
 

　　一堆又一堆地讀取它們，并在內(nèi)存中保留2束行(來(lái)自每個(gè)關(guān)系)，比較兩個(gè)束中的行，并保持匹配的行，然后從磁盤(pán)加載新的束并進(jìn)行比較，以此類(lèi)推，直到?jīng)]有束要加載為止。
 

　　// 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
 

　　使用此版本，時(shí)間復(fù)雜度保持不變，但是磁盤(pán)訪(fǎng)問(wèn)數(shù)量減少了：在以前的版本中，該算法需要N + N * M次訪(fǎng)問(wèn)(每個(gè)訪(fǎng)問(wèn)獲得一行)，在此新版本中，磁盤(pán)訪(fǎng)問(wèn)數(shù)變?yōu)閚umber_of_bunches_for(外部)+ number_of_ bundlees_for(外部)* number_of_ bundlees_for(內(nèi)部)。如果增加束的大小，則會(huì)減少磁盤(pán)訪(fǎng)問(wèn)次數(shù)。
 

　　哈希聯(lián)接
 

　　在許多情況下，哈希聯(lián)接比嵌套循環(huán)聯(lián)接更復(fù)雜，但成本更高。

　　哈希聯(lián)接的想法是：
 

　　1)從內(nèi)部關(guān)系中獲取所有元素
 

　　2)建立一個(gè)內(nèi)存中的哈希表
 

　　3)一對(duì)一地獲得外部關(guān)系的所有元素
 

　　4)計(jì)算每個(gè)元素的哈希值(使用哈希表的哈希函數(shù))以找到內(nèi)部關(guān)系的關(guān)聯(lián)存儲(chǔ)區(qū)
 

　　5)查找存儲(chǔ)桶中的元素與外部表的元素之間是否存在匹配項(xiàng)
 

　　在時(shí)間復(fù)雜度方面，我需要做一些假設(shè)來(lái)簡(jiǎn)化問(wèn)題：
 

　　內(nèi)部關(guān)系分為X個(gè)值區(qū)，散列函數(shù)為這兩種關(guān)系幾乎均勻地分布散列值。換句話(huà)說(shuō)，鏟斗尺寸相同。外部關(guān)系的元素與存儲(chǔ)桶中的所有元素之間的匹配會(huì)花費(fèi)存儲(chǔ)桶中的元素?cái)?shù)。時(shí)間復(fù)雜度為(M / X)* N + cost_to_create_hash_table(M)+ cost_of_hash_function * N，如果哈希函數(shù)創(chuàng)建了足夠多的小型存儲(chǔ)桶，則時(shí)間復(fù)雜度為O(M + N)
 

　　哈希聯(lián)接的另一個(gè)版本對(duì)內(nèi)存更友好，但對(duì)磁盤(pán)I / O的友好性更低：
 

　　1)計(jì)算內(nèi)部和外部關(guān)系的哈希表
 

　　2)然后將它們放在磁盤(pán)上
 

　　3)然后按桶比較2個(gè)關(guān)系桶(其中一個(gè)加載在內(nèi)存中，另一個(gè)逐行讀取)，合并加入，合并聯(lián)接是唯一產(chǎn)生排序結(jié)果的聯(lián)接。
 

　　合并聯(lián)接可以分為兩個(gè)步驟：(可選)對(duì)聯(lián)接操作進(jìn)行排序：兩個(gè)輸入都對(duì)聯(lián)接鍵進(jìn)行了排序;合并聯(lián)接操作：將排序的輸入合并在一起。
 

　　合并加入
 

　　這部分與我們看到的合并排序的合并操作非常相似。但是這一次，我們沒(méi)有從兩個(gè)關(guān)系中選擇每個(gè)元素，而是僅從兩個(gè)關(guān)系中選擇了相等的元素。
 

　　1)比較2個(gè)關(guān)系中的兩個(gè)當(dāng)前元素(第一次時(shí)current = first)
 

　　2)如果它們相等，則將兩個(gè)元素都放入結(jié)果中，然后轉(zhuǎn)到兩個(gè)關(guān)系的下一個(gè)元素
 

　　3)如果不是，則轉(zhuǎn)到具有最低元素的關(guān)系的下一個(gè)元素(因?yàn)橄乱粋€(gè)元素可能匹配)
 

　　4)并重復(fù)1,2,3，直到到達(dá)其中一個(gè)關(guān)系的最后一個(gè)元素。
 

　　之所以可行，是因?yàn)閮蓚€(gè)關(guān)系都已排序，因此你無(wú)需在這些關(guān)系中“返回”。
 

　　此算法是簡(jiǎn)化版本，因?yàn)樗鼰o(wú)法處理相同數(shù)據(jù)在兩個(gè)數(shù)組中多次出現(xiàn)(換句話(huà)說(shuō)，多個(gè)匹配項(xiàng))的情況。對(duì)于這種情況，實(shí)際版本“更復(fù)雜”。這就是為什么我選擇了簡(jiǎn)化版本。
 

　　如果兩個(gè)關(guān)系都已排序，則時(shí)間復(fù)雜度為O(N + M);如果兩個(gè)關(guān)系都需要排序，那么時(shí)間復(fù)雜度就是兩個(gè)關(guān)系的排序成本：O(N * Log(N)+ M * Log(M))
 

　　在可用內(nèi)存量：沒(méi)有足夠的內(nèi)存，你可以說(shuō)再見(jiàn)了強(qiáng)大的散列連接(至少滿(mǎn)內(nèi)存哈希聯(lián)接)。
 

　　2個(gè)數(shù)據(jù)集的大小。例如，如果一個(gè)很小的表，則嵌套循環(huán)聯(lián)接將比哈希聯(lián)接要快，因?yàn)楣Ｂ?lián)接具有昂貴的哈希創(chuàng)建。如果你有2個(gè)非常大的表，則嵌套循環(huán)聯(lián)接將占用大量CPU。該存在的指標(biāo)。使用2個(gè)B + Tree索引，明智的選擇似乎是合并聯(lián)接
 

　　如果需要對(duì)結(jié)果進(jìn)行排序：即使你正在使用未排序的數(shù)據(jù)集，你也可能希望使用代價(jià)高昂的合并聯(lián)接(帶有排序)，因?yàn)樽詈髮?duì)結(jié)果進(jìn)行排序并且可以鏈接另一個(gè)合并聯(lián)接的結(jié)果(或者可能是因?yàn)椴樵?xún)通過(guò)ORDER BY / GROUP BY / DISTINCT操作隱式/顯式地要求排序結(jié)果)
 

　　如果關(guān)系已經(jīng)排序：在這種情況下，合并聯(lián)接是最佳候選者
 

　　該類(lèi)型的連接，你正在做的：這是一個(gè)等值連接(即：tableA.col1 = tableB.col2)?它是一個(gè)內(nèi)部聯(lián)接，一個(gè)外連接，一個(gè)笛卡爾積或自連接?某些聯(lián)接在某些情況下不起作用。
 

　　該數(shù)據(jù)的分布。如果在數(shù)據(jù)連接條件是傾斜的(例如你在自己的姓氏加入的人，但很多人都有相同的)，使用散列連接將是一場(chǎng)災(zāi)難，因?yàn)楣：瘮?shù)將產(chǎn)生不良分布式桶。
 

　　如果我們需要聯(lián)接5個(gè)表才能完整地看到一個(gè)人，一個(gè)人可以有：多個(gè)移動(dòng)，多個(gè)郵件，多個(gè)地址，多個(gè)BANK_ACCOUNTS，換句話(huà)說(shuō)，我們需要以下查詢(xún)的快速答案：
 

　　SELECT * from PERSON, MOBILES, MAILS,ADRESSES, BANK_ACCOUNTS
 

　　WHERE
 

　　PERSON.PERSON_ID = MOBILES.PERSON_ID
 

　　AND PERSON.PERSON_ID = MAILS.PERSON_ID
 

　　AND PERSON.PERSON_ID = ADRESSES.PERSON_ID
 

　　AND PERSON.PERSON_ID = BANK_ACCOUNTS.PERSON_ID
 

　　作為查詢(xún)優(yōu)化器，必須找到處理數(shù)據(jù)的最佳方法。但是有兩個(gè)問(wèn)題：應(yīng)該為每種聯(lián)接使用哪種聯(lián)接?有3種可能的聯(lián)接(哈希聯(lián)接，合并聯(lián)接，嵌套聯(lián)接)，可以使用0,1或2個(gè)索引(更不用說(shuō)有不同類(lèi)型的索引了)。
 

　　應(yīng)該選擇什么順序來(lái)計(jì)算聯(lián)接?下圖顯示了4個(gè)表上僅3個(gè)聯(lián)接的不同可能計(jì)劃
 

　　所以以下是可能性：
 

　　1)使用蠻力方法
 

　　使用數(shù)據(jù)庫(kù)統(tǒng)計(jì)信息，計(jì)算出每種可能的計(jì)劃的成本，并保持最佳計(jì)劃。但是有很多可能性。對(duì)于給定的聯(lián)接順序，每個(gè)聯(lián)接都有3種可能性：HashJoin，MergeJoin，NestedJoin。因此，對(duì)于給定的連接順序，存在3 4種可能性。連接排序是二叉樹(shù)上的一個(gè)置換問(wèn)題，有(2 * 4)!/(4 + 1)!!可能的訂單。對(duì)于這個(gè)非常簡(jiǎn)化的問(wèn)題，最終得到3 4 *(2 * 4)!/(4 + 1)!可能性。
 

　　用非極客術(shù)語(yǔ)來(lái)說(shuō)，這意味著27 216個(gè)可能的計(jì)劃。如果現(xiàn)在添加使合并聯(lián)接采用0,1或2個(gè)B + Tree索引的可能性，則可能的計(jì)劃數(shù)變?yōu)?10000。
 

　　由于不是超人，所以無(wú)法計(jì)算每個(gè)計(jì)劃的成本。相反，可以任意選擇所有可能計(jì)劃的子集，計(jì)算其成本，然后為你提供此子集的最佳計(jì)劃。運(yùn)用精明的規(guī)則來(lái)減少可能的計(jì)劃數(shù)量。
 

　　有兩種類(lèi)型的規(guī)則：
 

　　可以使用“邏輯”規(guī)則來(lái)消除無(wú)用的可能性，但是它們不會(huì)過(guò)濾很多可能的計(jì)劃。例如：“嵌套循環(huán)連接的內(nèi)部關(guān)系必須是最小的數(shù)據(jù)集”
 

　　接受沒(méi)有找到最佳解決方案，而是采用更具侵略性的規(guī)則來(lái)減少大量可能性的想法。例如：“如果關(guān)系很小，請(qǐng)使用嵌套循環(huán)聯(lián)接，切勿使用合并聯(lián)接或哈希聯(lián)接”
 

　　在這個(gè)簡(jiǎn)單的示例中，最終有很多可能性。但是實(shí)際查詢(xún)可以具有其他關(guān)系運(yùn)算符，例如OUTER JOIN，CROSS JOIN，GROUP BY，ORDER BY，PROJECTION，UNION，INTERSECT，DISTINCT……這意味著更多的可能性。
 

　　強(qiáng)大的大數(shù)據(jù)中數(shù)據(jù)庫(kù)是如何工作的?他可以承載我們無(wú)法想象的數(shù)據(jù)，并且為我們所用，因此，很多朋友對(duì)大數(shù)據(jù)抱有強(qiáng)烈的探究意味，甚至躍躍欲試，但是大數(shù)據(jù)專(zhuān)業(yè)并不是那么簡(jiǎn)單的，AAA教育的大數(shù)據(jù)分析專(zhuān)業(yè)課程包括數(shù)據(jù)分析、Python、機(jī)器學(xué)習(xí)和人工智能，能夠進(jìn)行系統(tǒng)全面地學(xué)習(xí)才能更好更快的理解和掌握，自我探索的道路并不是平坦的。這是大數(shù)據(jù)中數(shù)據(jù)庫(kù)是如何工作的第二部分，顯然并未完結(jié)，感興趣的朋友一起接著往下看吧。