基於共享Cache多核處理器的資料庫哈希連接方法

2023-09-12 14:06:55

專利名稱：基於共享Cache多核處理器的資料庫哈希連接方法
技術領域：
本發明主要涉及資料庫查詢執行技術，具體涉及資料庫哈希連接的多線程執行優化方法。
背景技術：
隨著處理器電晶體數量的不斷增加，處理器頻率己達到現有條件下的極限，且能耗越來 越大，所以處理器的發展趨勢正從高主頻的單核處理器轉向片上多核處理器，從依靠指令級 的並行轉向線程級並行。目前2核和4核的處理器正成為市場的主流，而且內核數量仍在不 斷增加，極大地提高了單處理器的並行計算性能，相比較多核處理器普及之前，並行計算正 成為主要的程序運行模式，並日益受到重視。與傳統的SMP(Symmetrical Multi- Processing) 系統相比，多核處理器不但從硬體成本上更易被採納，而且由於晶片內的通信速度大大高於 晶片間，多核處理器並行效率要高於SMP系統。對資料庫而言，共享Cache可以減少數據重 復，提高Cache利用率。但也正由於多核處理器一般共享二級Cache,造成了多線程之間比 較容易發生共享Cache訪問衝突，造成性能下降。與此同時，在多緩存體系結構中，隨著內 存價格不斷下降和內存容量的不斷增大，大容量內存資料庫伺服器正成為主流配置，磁碟1/0 延遲逐漸得到緩解，而內存訪問速度相對於Cache和寄存器差距明顯，並且仍在不斷擴大， Cache訪問性能成為影響資料庫性能的重要因素，處理器等待Cache從上一級存儲器取數據 造成的延遲正成為資料庫系統的主要瓶頸。
目前的資料庫伺服器一般都已採用多核處理器和大容量內存，甚至一些高端伺服器配置 了多個多核處理器，並行計算能力得到極大提高。雖然資料庫採用的一個客戶端對應一個線 程的體系結構，使得多個客戶端提高的查詢請求，在伺服器端執行時能夠利用多核處理器的 並行計算優勢，但目前查詢內部的執行多採用單線程，使得單個查詢的執行不能充分利用處 理器技術進步帶來的性能提升。而且多核處理器普遍採用共享二級Cache的體系結構，在某 些類型的資料庫査詢執行時，給傳統的多線程執行方式帶來了潛在的性能瓶頸，特別是在大 內存容量資料庫伺服器中，這個問題更加突出。資料庫中哈希連接時最常見的連接運算之一， 對資料庫系統的性能起著至關重要的作用。針對哈希連接的性能優化主要有兩種途徑，利用 線程級並行優化哈希連接或改善哈希連接執行時的Cache訪問性能來提高性能。上述兩種優 化方法在共享二級Cache多核處理器中會存在以下缺點
41) 多線程哈希連接執行時，由於哈希表需要被重複訪問，在共享二級Cache的多核處 理器中，發生Cache訪問衝突的概率較高。嚴重的Cache訪問衝突會極大地降低多線程的優 化效果。2) 通過優化Cache訪問性能優化哈希連接在多核處理器中不能充分發揮其並行線程執 行的優勢，極大地浪費了處理器的計算資源，導致性能相比較多線程哈希連接有巨大的差距。最近幾年哈希連接的多線程優化研究主要有，微軟研究中心的Zhou JinRen等人提出在 SMT (Simultaneous Multithreading)處理器中，將元組分為奇偶兩類在兩個線程之間劃分，實 現並行執行資料庫操作。還提出利用主線程和Helper線程模式優化Data Cache,從而達到優 化哈希連接性能的目的；美國威斯康星大學的Philip等人提出利用流水線式多線程模式優化 哈希連接，但其未研究如何避免線程間的共享Cache訪問衝突帶來的問題。所以目前尚未有 基於共享二級Cache CMP優化哈希連接的研究工作，特別是減少多線程之間的共享二級 Cache訪問衝突的研究。 發明內容本發明要解決的技術問題是針對目前資料庫哈希連接在配置了共享二級Cache多核處 理器的大內存容量資料庫伺服器中，處理器並行計算資源利用率低下的問題，本發明提供了 一種基於數據劃分的多線程哈希連接處理方法。該方法充分利用處理器的並行計算資源的同 時，根據共享二級Cache的數據訪問特點，優化多線程執行時的Cache訪問性能。本發明解決其技術問題所採用的技術方案是分為連接表劃分和聚集連接兩個步驟；連接表劃分階段首先由臨時表生成模塊讀取表中的頁面生成臨時表，再由臨時表劃分模 塊將臨時表劃分成若干個小的聚集得到聚集表，連接表劃分中的兩種優化模塊在運行時 設定連接表劃分中各種線程運行的參數，以減少共享Cache訪問衝突；聚集連接階段由 多個聚集連接線程同時執行聚集連接操作，連接線程工作集分配模塊在運行時設定聚集 連接線程的各種參數。所述的連接表劃分階段包含三個模塊臨時表生成模塊，臨時表劃分模塊和線程優化 模塊；線程優化模塊則包括頁面讀取優化模塊和臨時表劃分優化模塊；臨時表由Hash Cell 組成，Hash Cell的結構為〈Wa^Ffl/we,《e;;^/Me,77D、其中/fo^Fa/we為連接列哈希值， 兀e;;Ffl/we為連接列的值，T/Z)為元組ID;臨時表劃分時，處理//ar/^"/we的￡>位二進位數據， 每次數據劃分處理A位i/w/zf^/we值，通過屍次劃分將表分成formula see original document page 5個聚集。所述的臨時表生成模塊，包含兩類線程頁面預取線程和頁面讀取線程；在頁面讀取線 程執行前，根據表的頁面號範圍，從頁面緩存模塊獲取連接執行前己在頁面緩存中的頁面集合和未在頁面緩存中的頁面集合；頁面預取線程首先從磁碟讀取連接執行前未在頁面緩存中 的頁面，由頁面讀取線程處理，然後頁面讀取線程再處理連接執行前已在頁面緩存中的頁面 集合；頁面讀取優化模塊則用於協調頁面預取線程和頁面讀取線程的執行，並設置線程執行所述的臨時表劃分模塊，在運行時根據參與劃分的臨時表數據量的大小確定合適的臨時 表劃分策略；在臨時表劃分時，臨時表劃分優化模塊根據每次數據劃分後產生的聚集情況確 定臨時表劃分線程的啟動時機；具體如下根據臨時表劃分參數D的闕值AfecD，結合處理 器核心數W決定具體的數據劃分策略(1) ZKMccZ)時，可令Z)屍1，即每次數據劃分處理1位Z/a^ra/we，從而避免使用交換 表，減少Cache訪問衝突；(2) D2AfaxD時，為了減少數據劃分次數較多造成的數據劃分代價，令A-"/P,即一 個數據劃分處理/)//位HashValue，減少數據劃分次數。所述的頁面讀取優化模塊，用於設置最佳的頁面讀取線程啟動時機，當頁面預取線程預 取的頁面數據量與處理這些頁面所需的臨時表數據量之和接近於二級Cache容量時，即可啟 動頁面讀取線程處理被預取的頁面。所述的臨時表劃分優化模塊，在運行時根據聚集的平均大小決定臨時表劃分線程的啟動 時機；具體方法如下(I ) ZKMoxZ)時，令#.=|^《.為第_/次臨時表劃分後生成的聚集數，7TS/ze-i:.tuple515(^//^^為臨時表大小；根據每次臨時表劃分後生成的聚集數在確定具體 的臨時表劃分線程啟動策略。(II) D2i^oxD時，在臨時表劃分前，判斷(:*(2，+%^是否大於C;如果大於C則在第一次臨時表劃分完成後啟動Min(歷,A/)個臨時表劃分線程，否則在每次臨時表劃分完成後，判斷2產7T能^e是否成立，i表示啟動的臨時表劃分線程個數，下同，2S/《iV，如果成立 A 一則可啟動Max(O個臨時表劃分線程。而在_/=|_屍/2」時，如果仍不存在滿足條件的/，則可立即啟動W個臨時表劃分線程。所述的聚集連接階段，首先連接線程工作集分配模塊基於聚集大小分類的原則為聚集線 程劃分好工作集；聚集連接執行時根據聚集分類的大小，啟動合適的聚集連接線程個數，從 大到小處理每個聚集分類中的聚集對，並通過減少哈希桶所需的內存量，優化了聚集連接執行的內存訪問。所述的連接線程工作集分配模塊，用於遍歷臨時表劃分生成的兩個聚集集合，根據每對 聚集的大小a^to"P"/W/ze,結合聚集連接線程個數J77Vw附和二級Cache容量C將聚集劃分 至對應的聚集分類『oWfc&r中，保證聚集連接線程處理某個聚集分類中的聚集對時，處理的 數據小於或等於二級Cache容量，減少Cache訪問衝突。所述聚集連接執行，除了『onfcS"e/
，對於fforA5"[/]中的聚集對，根據2乂^W是否滿足 分為兩種情況(a) 2j'SW滿足，將聚集連接線程分為_/組，每組由1 +聚集連接線程組成，執行一個聚集對的連接運算；(b)如果2/>〃，啟動_/個連接線程，每個聚集連接線程均勻分配聚集對即可；所述聚集連接執行時，首先處理『orfcS^[l]中的聚集對，接著處理『orfcS" [2]，以此類 推；最後啟動W個聚集連接線程處理『orfcSe [O]。本發明與現有技術相比所具有的優點與傳統的多線程哈希連接算法相比，本發明能夠 極大地減少線程訪問共享二級Cache時的Cache訪問衝突，並且使得處理器各個核心的負載 均衡，從而充分利用多核處理器的計算資源。由於本發明基於多線程執行哈希連接，並充分考慮了共享二級Cache對多線程執行的影 響，以及處理器負載均衡，因而使得本發明提出的多線程執行框架在執行時能夠極大地減少 因Cache訪問衝突造成的處理器等待數據從內存取到Cache的時間，而且處理器核心間的負 載在多數情況下是均衡的，所以本發明能夠充分地利用多核處理器的並行計算資源，從而取 得最大的性能提升。


圖1為多線程Hash連接執行框架；圖2為並發內存訪問；圖3為哈希連接內存訪問優化示意圖；具體實施方式
下面結合附圖及具體實施方式
詳細介紹本發明。本發明的基於共享Cache多核處理器的多線程資料庫哈希連接方法，包括連接表劃分和 聚集連接兩個步驟。第一步連接表劃分。對參與連接的兩個表(L和R)，按照連接列的哈希值進行數據 劃分。如圖1所示，圖的左半部分為連接表劃分階段框架圖。連接表劃分執行時，首先由臨時表生成模塊生成臨時表，然後由臨時表劃分模塊對臨時表進行數據劃分。具體步驟如下-A、 獲取表中所有頁面的頁面號集合，然後遍歷該頁面號集合，通過資料庫頁面緩存模 塊的哈希表映射函數計算頁面映射至哈希表中的具體位置，判斷該頁面當前是否在頁面緩存 中。遍歷完該頁面號集合後，即可獲得兩個頁面號集合未在頁面緩存中的頁面集合(屍ageM^/n^/"和己在頁面緩存中的頁面集合(屍age/"萬w/)。B、 臨時表生成時，處理上述A獲得的兩個頁面集合PflgeA^/^5w/和戶age/w^w/。首先 處理屍ageiVor/jiBw/中的頁面，通過頁面預取線程從磁碟將頁面讀入頁面緩存中，並將已讀取 的頁面號放入一個全局隊列，供頁面讀取線程並行處理，其中通過頁面讀取優化模塊決定最 佳的頁面讀取線程啟動時機。頁面預取線程處理Pfl^Ww/"Sw/時，根據頁面號是否連續，分 為兩種執行模式組讀取和單頁面讀取。組讀取為讀取頁面號連續的頁面，因此可以利用數 據庫支持的頁面組讀取功能， 一次I/0操作讀取多個頁面。當PageiVo /"萬M/中頁面處理完畢， 頁面讀取線程處理戶age/"^w/，完成臨時表生成運算。C、 臨時表劃分時，處理上述B生成的臨時表，根據鍵值的哈希值，將臨時表中的鍵值 劃分至對應的聚集中。臨時表劃分需要多次劃分用於處理二進位的哈希值，每次處理A位， 通過P次劃分將臨時表劃分成W-f^Wp個聚集，其中通過臨時表劃分優化模塊決定在第幾次聚集劃分完成後啟動臨時表劃分線程，以最大限度的減少臨時表劃分線程間的Cache訪問衝突。由於完成劃分後的每個聚集非常小，適合於通過簡單的哈希連接算法執行連接操作，也便於連接時能全部讀入二級Cache。上述步驟B中，頁面讀取優化模塊在頁面預取線程組讀取或單頁面讀取的頁面達到一定數量時再啟動頁面讀取線程，以避免頁面讀取線程的頻繁啟動代價。同時為了減少因頁面讀取線程訪問臨時表將預取的數據頁面替換出二級Cache造成的Cache訪問衝突，需要設置頁面讀取線程最佳啟動時機Atoc戶ageJVww。 的設置方法如下，令預取的數據頁面達到Atoc屍ageATw加時啟動頁面讀取線程，可得對應的頁面讀取線程需要訪問的臨時表數據量為MxcPageM/w*Mtuple* Ce/to'ze，其中M.tuple表示頁面中元組個數，CellSize表示臨時表數據項的大小。因此該次頁面處理線程啟動所需要訪問的全部數據量7btoto&=JWaxPageiVww* ^W,tuple* C"e//w.^+ A/ax/ age* A/.size，令7bto/j/2e《C ，可得Afox屍agejVw附-_^_。M.size+M.tuple * Ce〃5fee上述步驟C中，臨時表劃分優化模塊在每次聚集劃分完成後根據當前的聚集的平均大小， 然後結合啟動的臨時表劃分線程個數判斷此時啟動多線程劃分，臨時表劃分線程之間是否會 產生比較嚴重的Cache訪問衝突，如果Cache訪問衝突較少，則可立即啟動多線程劃分，否8則繼續進行單線程臨時表劃分處理。根據不同的數據劃分策略，採用不同的臨時表劃分方法， 具體如下(1) 、 ZKil/ox"時，具體的數據劃分方法為每次臨時表劃分只處理一個比特的哈希值。 比如有臨時表，其"=3、屍=3，即需要3次臨時表劃分，每次處理1比特的哈希值。第一次 臨時表劃分時，從臨時表7^7np7b6/e的起始位置遍歷其中的HashCeU，如果第Z)位為0，則 繼續遍歷re琴raWe，直到其值為1。然後從rempraWe尾部開始遍歷，如果第D位為1，則 繼續遍歷re琴7bWe直到其值為0，然後交換這兩個Hash Cell，然後從頂部開始繼續開始遍 歷，重複上述運算。當第一次臨時表劃分完成後，對於生成的各個子聚集，按照上述步驟處 理i^y/^a/w的第i)-l位數據。當處理完Z)位數據後，即完成了臨時表劃分階段。臨時表劃分優化模塊則根據每次臨時表劃分後生成的聚集數，將臨時表劃分線程的啟動時機分為三種情況，令/Z.-J^A為第/次臨時表劃分後生成的聚集數，rra'ze-丄.tuple忙e/扱ze' =i '為臨時表大小。(a) /^《W且7T&'ze^C，表明數據量很少，第一次臨時表劃分完成後，即可完成連 接表劃分進入聚集連接階段；(b) //^7VT且7Ts/z^c時，在每次臨時表劃分完成後，判斷i!ZZ^Ef^e是否滿足，/7 //乂表示啟動的線程個數，下同，2《K/^.。如果存在/滿足該條件，啟動Max(O個臨時表劃分線程(Max(/)表示滿足條件的/中最大的/，下同)，此時不會出現較嚴重的Cache訪問衝突， 如果不存在/滿足該條件，則進入情況(C);(c) 此時H,W,在每次臨時表劃分完成後，判斷i!ZZ^i《e是否滿足，其中2&、W,A 一如果存在滿足該條件的/且Max(/)<M此時啟動Max(/)個臨時表劃分線程。(2) 、 r^^foxZ)時，每次臨時表劃分可以處理多個比特哈希值。比如有臨時表，其 P=3,戶=2，即需要2次臨時表劃分，第一次處理2比特哈希值，第二次處理l比特哈希值， 同時需要交換表實現臨時表劃分時的數據交換。臨時表劃分優化模塊在臨時表劃分前，判斷<:*(2^^)是否大於C。如果大於C則在第一次臨時表劃分完成後啟動Min(7/,，^)個臨時表 劃分線程，否則在每次臨時表劃分完成後，判斷2!'*7TS!'ze^廣是否成立(2S! 《AQ，如果成立則可啟動Max(/)個臨時表劃分線程，而在戶L屍/2」時，如果仍不存在滿足條件的! ，則可立即啟動iV個臨時表劃分線程。上述處理過程中，iWoxZ)的取值由實驗證實最佳的取值為7。啟動聚集線程的時機產log,，)沐7T版，如果J'接近屍則失去了啟動多線程的意義。因此需要在臨時表劃分據開始前，先由產log2^^7T5fee(其中!'取值為2^'《AO計算出(z',力值，再以(/,/)為參數，根 臨時表劃分的加速比公式S(A，戶,j)- 計算出加速比s (其中A為臨時表劃分線程數，y為在屍次聚集劃分中，聚集劃分線程的啟動時機)，選擇最大s對應的(/，力，如果此J值大於Ma，"則無需/*7T<Sfeg,廣滿足(實驗測試表明Max7-Z)/2)，在/T^A^時即可啟動^ 丄 廣個聚集劃分。在第y次臨時表劃分完成後啟動，這時有/Z」個聚集，啟動W個臨時表劃分線程， 將巧個聚集均勻分配給iV個臨時表劃分線程。第二步聚集連接。如圖l的右半部分所示，處理臨時表劃分生成的兩個聚集表L和R。 對於第一步生成的兩個聚集表，對滿足連接條件的聚集之間執行多線程哈希連接操作。首先 由連接線程工作機分配模塊遍歷臨時表劃分生成的兩個聚集表，根據每對聚集的大小 C/w^e/^a 'nStee，結合聚集連接線程個數J7jVw附和二級Cache容量C將聚集劃分至對應的聚 集分類中，保證聚集連接線程處理某個聚集分類中的聚集對時，處理的數據小於或等於二級 Cache容量，減少Cache訪問衝突。具體如下如果^〈a^to"屍^您K^ (1S^^JTM^-1)，則可將該聚集對歸於Wo^S^[幻；尺+1 《如果0<C/*~W/^丄，則將該聚集對歸於『onfcSW [J7W,];如果C7w5terPa/r&ie>C，則將該聚集對歸於『o;^Sw
。比如令L[j]表示一個聚集，L[j].hashvalue表示該聚集對應的hashvalue值，如圖1的 L
.hashvalue-000。聚集連接線程執行前，由連接線程工作集分配模塊遍歷L和R，獲取滿 足連接條件的聚集對，如圖1中所示，滿足連接條件的聚集對為(L[O],R[O])， (L[l]，R[l])， (L[2諷4)，(L[3]， R[5])， (L[6]，R[6])，在獲得聚集對的同時，根據這些聚集對各自的 C7w;j^^a/rS&e放入對應的WorkSet中。根據上述聚集分類的結果『ont5^即可執行聚集連接，將聚集對分配給各個聚集連接線程執行。獲得『07"^^後根據啟動聚集連接線程前，『oz"WW的數組下標/與iV的關係2_/SAT是否滿足分為兩種情況分別進行處理(I )如果2j、AA滿足，將連接線程分為y組，每組由1+ D個聚集連接線程組成， 執行一個聚集對的連接運算，每組線程之間平均分配該聚集對中Probe表的元組。同時指定某個線程在Probe操作執行前構建Hash表，將Hash桶加入PKsli表中，組內其它線程需等待 Hash表構建完成。(II)如果2_/>^，啟動/個連接線程，每個連接線程均勻分配聚集對即可；，然後根據 WorkSet的下標啟動合適個數的聚集連接線程處理該WorkSet中的聚集對。比如對於 WorkSet[2]中的聚集對，處理器核心個數為4，將聚集連接線程分為2組，每組由2個連接線 程組成，每組中的聚集連接線程同時只處理一個聚集對的哈希連接運算，即該線程組中的兩 個聚集連接線程平分Probe表中的數據，同時訪問哈希表。 聚集連接階段的Hash連接內存訪問優化方法如下在連接表劃分階段，生成臨時表的同時構建數據量較大的表的Hash表數組Md，同時記 錄映射到每個//[/]的元組個數ifW.BucketNum，避免Hash桶插入Hash表時浪費內存空間。 聚集連接階段生成Hash桶時，如果有數據映射到i/W，則一次性從已分配好的內存中獲取能 容納Z/[i].BucketNum個Hash桶的內存塊。該存儲結構減少了 Hash表所需內存量，從而降低 了 Cache訪問衝突的可能性，因為Hash桶以數組存儲，無須指針即可遍歷//[/]中所有Hash 桶。圖1中的各種線程以背景線程方式實現，在適當的時機被啟動，賦予工作集，完成任務 後進入"睡眠"狀態。在資料庫服務啟動時，生成並初始化圖1中的各種線程，並進入"睡眠" 狀態。連接表劃分和聚集連接處理過程啟動的線程，在完成任務後同樣也作為背景線程進入" 睡眠"狀態。如圖2所示，為本發明所採用的並發內存訪問結構圖。用於臨時表生成時，頁面讀取線 程並行的向臨時表中寫入Hash Cell。它將臨時表分成若干個小的6wifer c/n/^,每個頁面讀取 線程都以6w#er cft"^:為單位讀/寫內存，線程訪問時無需並發訪問控制，只需要對該並發內存 的管理數據進行互斥訪問即可。比如標識該緩存中已經被寫入數據的6wj^rc/m/^個數，空閒 6w炎r c/ wwA:個數等。如圖3所示，為本發明的Hash連接內存訪問優化。通過在臨時表劃分時，構建哈希表數 據H[i]，同時記錄映射到每個H[i]的元組個數H[i]. Bucket- Num。聚集連接階段生成哈希桶 時，如果有數據映射到Z/W,則一次性從已分配好的內存中獲取能容納/^'].BucketNum個哈 希桶的內存塊。比如圖2中，對R
構建哈希表時，根據R[O]. Hashvalue對應的H[R[O]. Hashvalue]. BucketNum即可獲得映射到該哈希表數組中的哈希桶的個數，然後即可分配 H[R[O]. Hashvalue]. BucketNum個哈希桶，避免了指針存儲空間。本發明說明書中未作詳細描述的內容屬於本領域專業技術人員公知的現有技術。 以上所述僅是本發明的優選實施方式，應當指出，對於本技術領域的普通技術在不脫離本發明原理的前提下，還可以做出若干改進和潤飾，這些改進和潤飾也應視為本發 明的保護範圍。
權利要求
1、基於共享Cache多核處理器的資料庫哈希連接方法，其特徵在於分為連接表劃分和聚集連接兩個步驟；連接表劃分階段首先由臨時表生成模塊讀取表中的頁面生成臨時表，再由臨時表劃分模塊將臨時表劃分成若干個小的聚集得到聚集表，連接表劃分中的兩種優化模塊在運行時設定連接表劃分中各種線程運行的參數，以減少共享Cache訪問衝突；聚集連接階段由多個聚集連接線程同時執行聚集連接操作，連接線程工作集分配模塊在運行時設定聚集連接線程的各種參數。
2、 如權利要求1所述的基於共享Cache多核處理器的資料庫哈希連接方法，其特徵在 於所述的連接表劃分階段包含三個模塊臨時表生成模塊，臨時表劃分模塊和線程優 化模塊；線程優化模塊包括頁面讀取優化模塊和臨時表劃分優化模塊；臨時表由Hash Cell 組成，Hash Cell的結構為〈/^;y/^a/we,A:e少Fa/we,77D、其中//os/zFa/we為連接列哈希值， 《WFa/we為連接列的值，J7D為元組ID;臨時表劃分時，處理//aWra/we的￡>位二進位 數據，每次數據劃分處理A位HaA^/we值，通過P次劃分將表分成/Z-p]f/^個聚集。
3、 如權利要求2所述的臨時表生成模塊，其特徵在於包含兩類線程，頁面預取線 程和頁面讀取線程；在頁面讀取線程執行前，根據表的頁面號範圍，從頁面緩存模塊獲 取連接執行前己在頁面緩存中的頁面集合和未在頁面緩存中的頁面集合；頁面預取線程 首先從磁碟讀取連接執行前未在頁面緩存中的頁面，由頁面讀取線程處理，然後頁面讀 取線程再處理連接執行前已在頁面緩存中的頁面集合；線程優化模塊中的頁面讀取優化 模塊用於協調頁面預取線程和頁面讀取線程的執行，並設置線程執行參數。
4、 如權利要求3所述的臨時表生成模塊，其特徵在於所述的頁面讀取線程的啟動 時機為，當頁面預取線程預取的頁面數據量與處理這些頁面所需的臨時表數據量之和接 近於二級Cache容量時，即可啟動頁面讀取線程處理被預取的頁面。
5、 如權利要求2所述的臨時表劃分模塊，其特徵在於在運行時根據參與劃分的臨 時表數據量的大小確定合適的臨時表劃分策略；在臨時表劃分時，臨時表劃分優化模塊 根據每次數據劃分後產生的聚集情況確定臨時表劃分線程的啟動時機。
6、 如權利要求5所述的臨時表劃分策略，其特徵在於根據臨時表劃分參數"的闕 值MoxD，結合處理器核心數iV決定具體的數據劃分策略，具體方法如下-(1) ZKMaxD時，可令A-1，即每次數據劃分處理1位/ffl^^/we，從而避免使用 交換表，減少Cache訪問衝突；(2) Z)2MoxZ)時，為了減少數據劃分次數較多造成的數據劃分代價，令A-"//5,即一個數據劃分處理A位HashValue，減少數據劃分次數。
7、 如權利要求5所述的臨時表劃分優化模塊，其特徵在於，在運行時根據聚集的平 均大小決定臨時表劃分線程的啟動時機；具體方法如下(I ) ZKMax"時，令//.=[^;/,為第_/次臨時表劃分後生成的聚集數，7TS/"=iL.tUple*CW/S/M為臨時表大小；根據每次臨時表劃分後生成的聚集數在確定具體 的臨時表劃分線程啟動策略；(n) Z)》Jl/axZ)時，在臨時表劃分前，判斷d^+〉^)是否大於C;如果大於C則在第一次臨時表劃分完成後啟動Min(仏,7V)個臨時表劃分線程，否則在每次臨時表劃分完成後，判斷2"7T5fe^c是否成立，/表示啟動的臨時表劃分線程個數，下同，2S/《W， A —如果成立則可啟動Max(/)個臨時表劃分線程；而在_/=[屍/2」時，如果仍不存在滿足條件的/，則可立即啟動iV個臨時表劃分線程。
8、 如權利要求l所述的基於共享Cache多核處理器的資料庫哈希連接方法，其特徵在 於所述的聚集連接階段首先連接線程工作集分配模塊基於聚集大小分類的原則為聚 集線程劃分好工作集；聚集連接執行時根據聚集分類的大小，啟動合適的聚集連接線程 個數，從大到小處理每個聚集分類中的聚集對，並通過減少哈希桶所需的內存量，優化 了聚集連接執行的內存訪問。
9、 如權利要求8所述的連接線程工作集分配模塊，其特徵在於遍歷臨時表劃分生 成的兩個聚集集合，根據每對聚集的大小a"W^Pa/Wfee，結合聚集連接線程個數J7W"M 和二級Cache容量C將聚集劃分至對應的聚集分類中，保證聚集連接線程處理某個聚集 分類中的聚集對時，處理的數據小於或等於二級Cache容量，減少Cache訪問衝突。
10、 如權利要求8所述的聚集連接執行，其特徵在於，除了『orfcSe/
，對於『oASer[/'] 中的聚集對，根據2j'《W是否滿足分為兩種情況(a)如果2j'《iV滿足，將聚集連接線程分為y'組，每組由1+木聚集連接線程組成，執行一個聚集對的連接運算；(b)如果2戶見啟動y個連接線程，每個聚集連接線程均勻分配聚集對即可； 聚集連接執行時，首先處理『o"S"[l]中的聚集對，接著處理,ASW[2]，以此類推； 最後啟動iV個聚集連接線程處理『oASe/
。
全文摘要
本發明公開了一種基於共享Cache多核處理器的資料庫哈希連接方法，該方法分為連接表劃分和聚集連接兩個階段；連接表劃分首先通過臨時表生成模塊生成臨時表，然後臨時表劃分線程對臨時表執行臨時表劃分，劃分前根據臨時表的大小確定合適的數據劃分策略，並在臨時表劃分過程中決定臨時表劃分線程的合適啟動時機以減少Cache訪問衝突；聚集連接時，採用基於聚集大小分類的聚集連接執行方法，並優化了哈希連接時的內存訪問。本發明確保哈希連接充分利用多核處理器的計算資源，哈希連接執行的加速比接近於處理器核心個數，從而大大的縮短了哈希連接執行時間。
文檔編號G06F12/08GK101593202SQ20091007692
公開日2009年12月2日 申請日期2009年1月14日 優先權日2009年1月14日
發明者馮登國, 盧戰偉, 周成虎, 敏 張, 張明波, 震 徐, 寧 景, 軍 李, 偉 熊, 程昌秀, 炯 謝, 鄧亞丹, 犖 陳, 馳 陳, 陳宏盛, 陳榮國 申請人:中國人民解放軍國防科學技術大學;中國科學院地理科學與資源研究所;中國科學院軟體研究所