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

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

　　SQLite是一堆精心設計的文件，因為它允許你執(zhí)行以下操作：使用確保數(shù)據(jù)安全和連貫的交易，即使你正在處理數(shù)百萬個數(shù)據(jù)，也可以快速處理數(shù)據(jù)，數(shù)據(jù)庫可以如下圖所示：
 

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

　　核心組件：
 

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

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

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

　　內(nèi)存管理器：為避免磁盤I / O損失，需要大量的內(nèi)存。但是，如果你處理大量內(nèi)存，則需要高效的內(nèi)存管理器。尤其是當你有多個查詢同時使用內(nèi)存時。
 

　　安全管理器：用于管理用戶的身份驗證和授權
 

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

　　…
 

　　工具：
 

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

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

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

　　管理管理器：用于存儲元數(shù)據(jù)(如表的名稱和結構)，并提供工具來管理數(shù)據(jù)庫，模式，表空間.....
 

　　查詢管理器：
 

　　查詢解析器：檢查查詢是否有效
 

　　查詢重寫器：預優(yōu)化查詢
 

　　查詢優(yōu)化器：優(yōu)化查詢
 

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

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

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

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

　　數(shù)據(jù)訪問管理器：訪問磁盤上的數(shù)據(jù)
 

　　對于本文的其余部分，我將重點介紹數(shù)據(jù)庫如何通過以下過程來管理SQL查詢：
 

　　客戶經(jīng)理
 

　　查詢管理器
 

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

　　客戶經(jīng)理
 

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

　　它還可以提供專有的數(shù)據(jù)庫訪問API。
 

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

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

　　然后，它檢查是否有一個進程(或線程)可用于管理你的查詢。
 

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

　　它可以等待片刻以獲取所需的資源。如果此等待達到超時，它將關閉連接并給出可讀的錯誤消息。
 

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

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

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

　　查詢管理器
 

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

　　PostgreSQL的如何優(yōu)化一個很好的演示查詢這里。這是最易訪問的文檔，因為它比“讓我們看看PostgreSQL使用的算法”更多地是關于“讓我們看看PostgreSQL在這些情況下給出的查詢計劃”。
 

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

　　查詢解析器
 

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

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

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

　　查詢重寫器
 

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

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

　　視圖合并：如果你在查詢中使用視圖，則將使用該視圖的SQL代碼轉換該視圖。
 

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

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

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

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

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

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

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

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

　　統(tǒng)計數(shù)據(jù)：在我們看到數(shù)據(jù)庫如何優(yōu)化查詢之前，我們需要先談談統(tǒng)計信息，因為沒有統(tǒng)計信息，數(shù)據(jù)庫是愚蠢的。如果你不告訴數(shù)據(jù)庫分析自己的數(shù)據(jù)，它將不會這樣做，并且會做出(非常)錯誤的假設。
 

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

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

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

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

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

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

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

　　查詢優(yōu)化器

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

　　為了理解成本優(yōu)化器的工作原理，最好有一個示例來“感覺”該任務背后的復雜性。即使是簡單的聯(lián)接查詢也是要優(yōu)化的噩夢。
 

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

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

　　指標
 

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

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

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

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

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

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

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

　　如果你有一個列年齡的人的索引，那么優(yōu)化器將使用該索引查找所有28歲的人，然后它會詢問表中的關聯(lián)行，因為索引僅包含有關年齡的信息，并且你想知道姓氏和名字。
 

　　SELECT TYPE_PERSON.CATEGORY from PERSON ,TYPE_PERSON
 

　　WHERE PERSON.AGE = TYPE_PERSON.AGE
 

　　PERSON上的索引將用于與TYPE_PERSON聯(lián)接，但是行ID將無法訪問表PERSON，因為你沒有在該表上詢問信息。
 

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

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

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

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

　　對于外部關系中的每一行，你查看內(nèi)部關系中的所有行以查看是否存在匹配的行。
 

　　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
 

　　由于是兩次迭代，因此時間復雜度為O(N * M)。就磁盤I / O而言，對于外部關系中的N行中的每行，內(nèi)部循環(huán)都需要從內(nèi)部關系中讀取M行。該算法需要從磁盤讀取N + N * M行。但是，如果內(nèi)部關系足夠小，則可以將該關系存儲在內(nèi)存中，并且只需進行M + N次讀取即可。通過這種修改，內(nèi)部關系必須是最小的，因為它有更多的機會適合內(nèi)存。
 

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

　　一堆又一堆地讀取它們，并在內(nèi)存中保留2束行(來自每個關系)，比較兩個束中的行，并保持匹配的行，然后從磁盤加載新的束并進行比較，以此類推，直到?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ù)量減少了：在以前的版本中，該算法需要N + N * M次訪問(每個訪問獲得一行)，在此新版本中，磁盤訪問數(shù)變?yōu)閚umber_of_bunches_for(外部)+ number_of_ bundlees_for(外部)* number_of_ bundlees_for(內(nèi)部)。如果增加束的大小，則會減少磁盤訪問次數(shù)。
 

　　哈希聯(lián)接
 

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

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

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

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

　　3)一對一地獲得外部關系的所有元素
 

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

　　5)查找存儲桶中的元素與外部表的元素之間是否存在匹配項
 

　　在時間復雜度方面，我需要做一些假設來簡化問題：
 

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

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

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

　　2)然后將它們放在磁盤上
 

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

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

　　合并加入
 

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

　　1)比較2個關系中的兩個當前元素(第一次時current = first)
 

　　2)如果它們相等，則將兩個元素都放入結果中，然后轉到兩個關系的下一個元素
 

　　3)如果不是，則轉到具有最低元素的關系的下一個元素(因為下一個元素可能匹配)
 

　　4)并重復1,2,3，直到到達其中一個關系的最后一個元素。
 

　　之所以可行，是因為兩個關系都已排序，因此你無需在這些關系中“返回”。
 

　　此算法是簡化版本，因為它無法處理相同數(shù)據(jù)在兩個數(shù)組中多次出現(xiàn)(換句話說，多個匹配項)的情況。對于這種情況，實際版本“更復雜”。這就是為什么我選擇了簡化版本。
 

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

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

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

　　如果需要對結果進行排序：即使你正在使用未排序的數(shù)據(jù)集，你也可能希望使用代價高昂的合并聯(lián)接(帶有排序)，因為最后將對結果進行排序并且可以鏈接另一個合并聯(lián)接的結果(或者可能是因為查詢通過ORDER BY / GROUP BY / DISTINCT操作隱式/顯式地要求排序結果)
 

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

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

　　該數(shù)據(jù)的分布。如果在數(shù)據(jù)連接條件是傾斜的(例如你在自己的姓氏加入的人，但很多人都有相同的)，使用散列連接將是一場災難，因為哈希函數(shù)將產(chǎn)生不良分布式桶。
 

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

　　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
 

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

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

　　所以以下是可能性：
 

　　1)使用蠻力方法
 

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

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

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

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

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

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

　　在這個簡單的示例中，最終有很多可能性。但是實際查詢可以具有其他關系運算符，例如OUTER JOIN，CROSS JOIN，GROUP BY，ORDER BY，PROJECTION，UNION，INTERSECT，DISTINCT……這意味著更多的可能性。
 

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