陳 鑫

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

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

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

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

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

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

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

（3）Tjdisk：表示算法第j步中的磁盤(pán)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)順序磁盤(pán)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=得到。

第一步：建表階段。

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

第二步：探詢階段。

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

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）通過(guò)網(wǎng)絡(luò)互聯(lián)，網(wǎng)絡(luò)啟動(dòng)時(shí)間為0.05 ms。測(cè)試參數(shù)取值如表1所示。

表1 測(cè)試參數(shù)

通過(guò)對(duì)模擬測(cè)試結(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í)間取決于磁盤(pán)I/O時(shí)間和網(wǎng)絡(luò)傳輸時(shí)間,基于合格標(biāo)記的隱式連接并行執(zhí)行算法的響應(yīng)時(shí)間取決于磁盤(pán)I/O時(shí)間CPU時(shí)間；

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

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

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

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

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

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

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

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

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

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