[發(fā)明專利]用于對并行數(shù)據(jù)庫管理系統(tǒng)的外連接的系統(tǒng)和方法

有效

• 申請?zhí)枺?/td>: 201080065880.0
• 申請日: 2010-03-30
• 公開（公告）號: CN102844754A
• 公開（公告）日: 2012-12-26
• 發(fā)明（設(shè)計）人: A.K.阿爾-奧馬里;Q.陳
• 申請（專利權(quán)）人: 惠普發(fā)展公司;有限責(zé)任合伙企業(yè)
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06F17/00
• 代理公司: 中國專利代理(香港)有限公司 72001
• 代理人: 馬紅梅;盧江

背景技術(shù)

在大規(guī)模并行處理（Massively?Parallel?Processing，MPP）系統(tǒng)中，商業(yè)智能（Business?Intelligence，BI）和企業(yè)數(shù)據(jù)倉庫（Enterprise?Data?Warehouse，EDW）應(yīng)用處理大量的數(shù)據(jù)。該數(shù)據(jù)（關(guān)系表集）駐留在非常大的數(shù)據(jù)庫系統(tǒng)中，該非常大的數(shù)據(jù)庫系統(tǒng)依靠大數(shù)目的中央處理單元（CPU）來高效地執(zhí)行數(shù)據(jù)庫操作。MPP系統(tǒng)試圖在可用的處理器之間均一地分配數(shù)據(jù)，并且然后并行地施行預(yù)期操作，而不是串行地施行該操作。

基本且最常見的數(shù)據(jù)庫操作之一是兩個關(guān)系表之間的連接。連接操作器基于各表中的列之間的匹配準(zhǔn)則組合來自兩個表的記錄。例如，通過匹配兩個表上的列product_id，可以把表LINEITEM連接到表PRODUCT，以得到具有它們的產(chǎn)品信息的所有行項集。在查詢執(zhí)行樹中，連接操作常常是計算開銷最高的操作，并且其性能指示了該查詢的整體性能。

為了并行地高效施行連接操作，該系統(tǒng)基于連接列（上面的示例中的product_id）的值對來自兩個表的數(shù)據(jù)流進行分區(qū)。也就是說，保證具有來自任一表、或者孩子的連接列的或連接的相同值的所有記錄都被發(fā)送到同一中央處理單元（CPU）。因而，所有連接匹配都可以被在每個CPU中本地地且獨立于其他CPU地找到。

當(dāng)記錄被均勻地分配時，此按值分區(qū)模式效果好。使用良好的哈希函數(shù)確保了不同的值被均勻地（或偽隨機地）分配給所有處理器。然而，良好的哈希函數(shù)不保證記錄被均一地分配，因為不是所有的不同的值在該數(shù)據(jù)集中都具有相同的出現(xiàn)頻率。當(dāng)一個值具有比每個CPU的平均記錄數(shù)高的出現(xiàn)頻率時，該問題變得明顯。這被稱為數(shù)據(jù)傾斜（skew）或傾斜。在傾斜的情況下，通過頻率值選擇的CPU將處理與平均值相比顯著更高數(shù)目的記錄，這可能顯著劣化查詢響應(yīng)時間。

附圖說明

在以下詳細描述中且參考附圖來描述特定的示例性實施例，其中：

圖1A是依據(jù)本發(fā)明的示例性實施例的被適配為執(zhí)行傾斜外連接的系統(tǒng)的框圖；

圖1B是依據(jù)本發(fā)明的示例性實施例的被適配為執(zhí)行傾斜外連接的并行數(shù)據(jù)庫管理系統(tǒng)的框圖；

圖2是表示依據(jù)本發(fā)明的示例性實施例的操作器的邏輯視圖的框圖；

圖3A是表示依據(jù)本發(fā)明的示例性實施例的用于SQL?STATEMENT?1的混合交換操作器的邏輯視圖的框圖；

圖3B是表示依據(jù)本發(fā)明的示例性實施例的用于SQL?STATEMENT?2的混合交換操作器的邏輯視圖的框圖；

圖3C是表示依據(jù)本發(fā)明的示例性實施例的查詢計劃134的擴展邏輯視圖的框圖；

圖3D是表示依據(jù)本發(fā)明的示例性實施例的用于SQL?STATEMENT?2的查詢計劃的框圖；

圖4是依據(jù)本發(fā)明的示例性實施例的用于執(zhí)行查詢的計算機可執(zhí)行方法的處理流程圖；

圖5是示出依據(jù)本發(fā)明的示例性實施例的存儲被適配成執(zhí)行查詢的代碼的有形機器可讀介質(zhì)的框圖。

具體實施方式

圖1A是依據(jù)本發(fā)明的示例性實施例的被適配為執(zhí)行查詢的系統(tǒng)的框圖。該系統(tǒng)通常由附圖標(biāo)記100指代。本領(lǐng)域普通技術(shù)人員將意識到：圖1中所示出的功能框和設(shè)備可以包括硬件元素、軟件元素或者硬件元素和軟件元素這二者的組合，所述硬件元素包括電路，所述軟件元素包括存儲在有形機器可讀介質(zhì)上的計算機代碼。

另外，系統(tǒng)100的功能框和設(shè)備是可以在本發(fā)明的示例性實施例中實施的功能框和設(shè)備的僅一個示例。基于針對特定電子設(shè)備的設(shè)計考慮，本領(lǐng)域普通技術(shù)人員將能夠容易地定義特定的功能框。

該系統(tǒng)100可以包括通過網(wǎng)絡(luò)130通信的數(shù)據(jù)庫服務(wù)器102和一個或多個客戶端計算機104。如圖1A中所圖示的，數(shù)據(jù)庫服務(wù)器102可以包括并行地進行動作的多個處理器112。處理器112可以通過總線113連接到顯示器114、鍵盤116、一個或多個輸入設(shè)備118和諸如打印機120之類的輸出設(shè)備。輸入設(shè)備118可以包括諸如鼠標(biāo)或觸摸屏之類的設(shè)備。

在本發(fā)明的示例性實施例中，在大規(guī)模并行處理系統(tǒng)（MPP）中，該系統(tǒng)100可以包括多個數(shù)據(jù)庫服務(wù)器102。在這樣的示例性實施例中，該系統(tǒng)100可以包括無共享架構(gòu)。

數(shù)據(jù)庫服務(wù)器102還可以通過總線113連接到網(wǎng)絡(luò)接口卡（NIC）126。NIC?126可以把數(shù)據(jù)庫服務(wù)器102連接到網(wǎng)絡(luò)130。網(wǎng)絡(luò)130可以是局域網(wǎng)（LAN）、廣域網(wǎng)（WAN）、或者另一網(wǎng)絡(luò)配置，諸如因特網(wǎng)。網(wǎng)絡(luò)130可以包括路由器、交換機、調(diào)制解調(diào)器、或者被用于互聯(lián)的任何其他種類的接口設(shè)備。