大數據中數據庫是如何工作的（二）

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

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

　　將數據庫分為相互交互的多個組件。
 

　　核心組件：
 

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

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

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

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

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

　　客戶經理：用于管理客戶連接
 

　　…
 

　　工具：
 

　　備份管理器：用于保存和還原數據庫。
 

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

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

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

　　查詢管理器：
 

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

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

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

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

　　數據管理器：
 

　　交易經理：處理交易
 

　　高速緩存管理器：在使用數據之前先將其放入內存中，然后在將其寫入磁盤之前先將其放入內存中
 

　　數據訪問管理器：訪問磁盤上的數據
 

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

　　客戶經理
 

　　查詢管理器
 

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

　　客戶經理
 

　　客戶經理是處理與客戶通信的部分。客戶端可以是(Web)服務器或最終用戶/最終應用程序?？蛻舳斯芾砥魈峁┝送ㄟ^一組著名的API訪問數據庫的不同方法：JDBC，ODBC，OLE-DB…
 

　　它還可以提供專有的數據庫訪問API。
 

　　當你連接到數據庫時：
 

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

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

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

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

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

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

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

　　查詢管理器
 

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

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

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

　　查詢解析器
 

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

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

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

　　查詢重寫器
 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　查詢優(yōu)化器

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

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

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

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

　　指標
 

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

　　存取路徑：在應用聯接運算符之前，你首先需要獲取數據。這是獲取數據的方法。
 

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

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

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

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

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

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

　　SELECT TYPE_PERSON.CATEGORY from PERSON ,TYPE_PERSON
 

　　WHERE PERSON.AGE = TYPE_PERSON.AGE
 

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

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

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

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

　　嵌套循環(huá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
 

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

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

　　一堆又一堆地讀取它們，并在內存中保留2束行(來自每個關系)，比較兩個束中的行，并保持匹配的行，然后從磁盤加載新的束并進行比較，以此類推，直到沒有束要加載為止。
 

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

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

　　哈希聯接
 

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

　　哈希聯接的想法是：
 

　　1)從內部關系中獲取所有元素
 

　　2)建立一個內存中的哈希表
 

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

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

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

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

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

　　哈希聯接的另一個版本對內存更友好，但對磁盤I / O的友好性更低：
 

　　1)計算內部和外部關系的哈希表
 

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

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

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

　　合并加入
 

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

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

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

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

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

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

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

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

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

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

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

　　如果關系已經排序：在這種情況下，合并聯接是最佳候選者
 

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

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

　　如果我們需要聯接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)化器，必須找到處理數據的最佳方法。但是有兩個問題：應該為每種聯接使用哪種聯接?有3種可能的聯接(哈希聯接，合并聯接，嵌套聯接)，可以使用0,1或2個索引(更不用說有不同類型的索引了)。
 

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

　　所以以下是可能性：
 

　　1)使用蠻力方法
 

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

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

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

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

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

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

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

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