數(shù)據(jù)庫并行查詢方案研究

陳 鑫

（長治學(xué)院 計(jì)算機(jī)系，山西 長治 046011）

對于數(shù)據(jù)庫來說，查詢處理的效率是系統(tǒng)性能的主要指標(biāo)之一，并行數(shù)據(jù)庫系統(tǒng)試圖利用并行性來提高查詢處理效率，但是“并行不等于高效”。具體而言，主要是在并行性的開發(fā)過程中可能產(chǎn)生出新的“無意義”的工作，這些無效工作將會(huì)抵消并行性帶來的效果，因此并行性的充分開發(fā)不一定導(dǎo)致高效的產(chǎn)生。而查詢優(yōu)化是提高查詢處理效率的有效手段，所以把并行性和查詢優(yōu)化相結(jié)合是提高查詢處理效率的有效途徑，即在并行處理的基礎(chǔ)上，進(jìn)一步利用有效合理的查詢優(yōu)化策略，盡量避免無效事務(wù)，從而最大的提高查詢處理效率。

并行查詢其優(yōu)勢就是可以通過多個(gè)線程來處理查詢作業(yè)，從而提高查詢的的效率。SQL Server數(shù)據(jù)庫為具有多個(gè)CPU的數(shù)據(jù)庫服務(wù)器提供并行查詢功能，以優(yōu)化查詢作業(yè)的性能。也就是說，只要數(shù)據(jù)庫服務(wù)器有多個(gè)CPU，則數(shù)據(jù)庫系統(tǒng)就可以使用多個(gè)操作系統(tǒng)進(jìn)程并執(zhí)行查詢操作，來加速完成查詢作業(yè)。

1 并行執(zhí)行算法的設(shè)計(jì)

為方便算法的設(shè)計(jì)，給出以下標(biāo)記說明：

（1）T：表示數(shù)據(jù)操作并行執(zhí)行算法的響應(yīng)時(shí)間；

（2）Tjcpu：表示算法第j步中的cpu時(shí)間；

（3）Tjdisk：表示算法第j步中的磁盤I/O時(shí)間；

（4）Tjnet：表示算法第j步中的網(wǎng)絡(luò)傳輸時(shí)間；

其中Tjcpu是由構(gòu)造一個(gè)關(guān)聯(lián)模式花費(fèi)的cpu時(shí)間+啟動(dòng)互聯(lián)網(wǎng)接收和發(fā)送數(shù)據(jù)的cpu時(shí)間+啟動(dòng)順序磁盤I/O用的cpu時(shí)間；

因?yàn)樗惴ㄔO(shè)計(jì)考慮了重疊，Tj可取Tjcpu、Tjdisk、Tjnet三者中的最大值作為第j步中并行執(zhí)行算法的響應(yīng)時(shí)間：

而算法的響應(yīng)時(shí)間：

2 傳統(tǒng)的連接并行執(zhí)行算法設(shè)計(jì)

傳統(tǒng)的隱式和顯式連接并行執(zhí)行算法由建表階段、探詢階段兩部分組成，它的響應(yīng)時(shí)間T由T=得到。

第一步：建表階段。

從磁盤讀出對C類進(jìn)行選擇操作和投影操作的結(jié)果，因?yàn)槠骄總€(gè)C類對象與α 個(gè)D類對象相關(guān)聯(lián)，即平均每個(gè)C類對象的連接性質(zhì)由α 個(gè)二元組（Oid，Oid）構(gòu)成，且共需要為α*{C}*sel/N個(gè)部分對象建立表格，取每個(gè)部分對象建表的cpu開銷為（thash+tinset）。

第二步：探詢階段。

從磁盤讀出對D類進(jìn)行選擇操作和投影操作的結(jié)果，根據(jù)已建的表格，匹配符合連接條件的C類和D類的部分對象，對于隱式連接，這種對象匹配的cpu時(shí)間為（thash+F*tcomp)最后將結(jié)果存入磁盤。

3 合格標(biāo)記的連接并行執(zhí)行算法設(shè)計(jì)

基于合格標(biāo)記的隱式和顯式連接并行執(zhí)行算法由建表階段、探詢建表階段和探詢階段三部分組成，它的響應(yīng)時(shí)間是

4 實(shí)驗(yàn)結(jié)果及分析

模擬的工作環(huán)境是：多臺(tái)SGI Challenge服務(wù)器（MIPS R4400芯片，128MIPS）通過網(wǎng)絡(luò)互聯(lián)，網(wǎng)絡(luò)啟動(dòng)時(shí)間為0.05 ms。測試參數(shù)取值如表1所示。

表1 測試參數(shù)

通過對模擬測試結(jié)果圖中ratio隨相關(guān)數(shù)據(jù)的變化進(jìn)行觀察，分析其結(jié)果，可以得出以下的一些結(jié)論：

（1）基于合格標(biāo)記的連接并行執(zhí)行算法優(yōu)于傳統(tǒng)的連接并行執(zhí)行算法；

（2）基于傳統(tǒng)的隱式連接并行執(zhí)行算法的響應(yīng)時(shí)間取決于磁盤I/O時(shí)間和網(wǎng)絡(luò)傳輸時(shí)間,基于合格標(biāo)記的隱式連接并行執(zhí)行算法的響應(yīng)時(shí)間取決于磁盤I/O時(shí)間CPU時(shí)間；

（3）基于傳統(tǒng)的顯式連接并行執(zhí)行算法的響應(yīng)時(shí)間取決于磁盤I/O的時(shí)間，而基于合格標(biāo)記的顯式連接并行執(zhí)行算法的響應(yīng)時(shí)間取決于CPU時(shí)間；

（4）隱式連接的并行執(zhí)行算法中結(jié)點(diǎn)數(shù)目的變化對ratio不產(chǎn)生顯著影響，而顯式連接的并行執(zhí)行算法的ratio隨著結(jié)點(diǎn)數(shù)目的增加而減少，原因是隨著結(jié)點(diǎn)數(shù)N的增加，傳統(tǒng)的顯式連接操作并行執(zhí)行算法的磁盤I/O量顯著減少，而基于合格標(biāo)記的顯式連接并行執(zhí)行算法的cpu開銷沒有明顯減少。

（5）通過改變類N、Sel、Sbig等重要參數(shù)的取值，觀察兩種算法的響應(yīng)時(shí)間比值ratio可以看出，在相同的參數(shù)值下，顯式連接的并行執(zhí)行算法的ratio要高于隱式連接的并行執(zhí)行算法，說明相比之下，在不知道兩個(gè)類之間是否存在關(guān)系的情況下，即顯式連接的并行執(zhí)行算法能達(dá)到更高的優(yōu)化效果。

（6）隱式連接的并行執(zhí)行算法中ratio的值隨著關(guān)聯(lián)系數(shù)α 的增加而減少，原因是隨著α 的增加，傳統(tǒng)的隱式連接操作并行執(zhí)行算法的磁盤I/O量和網(wǎng)絡(luò)傳輸量增加不明顯，基于合格標(biāo)記的隱式連接并行執(zhí)行算法的磁盤I/O量和cpu開銷增長顯著，而顯式連接的并行執(zhí)行算法的ratio與關(guān)聯(lián)系數(shù)α 的值無關(guān)，原因是顯式連接的兩個(gè)類之間不存在關(guān)聯(lián)。

眾所周知，查詢優(yōu)化是提高查詢處理效率的有效手段，而并行性與查詢優(yōu)化相結(jié)合是提高查詢處理效率的重要方法，即在并行查詢處理的基礎(chǔ)上，進(jìn)一步利用合理有效的查詢策略，進(jìn)一步提高查詢處理的效率。

在傳統(tǒng)的連接操作并行執(zhí)行算法的基礎(chǔ)上，研究了基于合格標(biāo)記的連接操作并行執(zhí)行算法，而且對顯式連接和隱式連接兩種連接操作從理論上以及模擬實(shí)驗(yàn)兩方面進(jìn)行了分析和評價(jià)，得出這種基于合格標(biāo)記的優(yōu)化策略確實(shí)可以提高并行執(zhí)行的效率。而且可以看出隱式連接適合兩個(gè)有關(guān)聯(lián)類之間的連接并行執(zhí)行操作，顯式連接適合不相關(guān)的兩個(gè)類之間進(jìn)行連接并行執(zhí)行操作。

［1］王珊,肖艷芹.內(nèi)存數(shù)據(jù)庫關(guān)鍵技術(shù)研究［J］.計(jì)算機(jī)應(yīng)用,2007,（2）：232-235.

［2］朱鳳華,陳昌生,孫永強(qiáng),賴樹華.并行查詢優(yōu)化策略［J］.計(jì)算機(jī)工程,2000,（9）：127-131.

［3］劉煥婷,張凌燕.分布式數(shù)據(jù)庫系統(tǒng)查詢策略研究［J］.計(jì)算機(jī)應(yīng)用研究,2002,（8）：153-155.

［4］王勇智,胡虛懷,唐志平.提髙并行數(shù)據(jù)庫性能的幾點(diǎn)思考［J］.計(jì)算機(jī)現(xiàn)代化,2005,（6）：184-187.