軟工數(shù)據(jù)庫課程part利用計(jì)算機(jī)系統(tǒng)提供并行處理能力通過

第十章第十章第十章并行數(shù)據(jù)庫系統(tǒng)10.1.1））引入并行的目的：保證即使在數(shù)據(jù)庫的規(guī)模和事務(wù)的數(shù)量都大大增長時(shí)，數(shù)據(jù)庫系統(tǒng)仍能以可接受的速度運(yùn)行。age>20(s)|><|∏dno,dean(響應(yīng)時(shí)間(responsetime)：對于單個(gè)任務(wù)從提對于處理大事務(wù)的系統(tǒng)，通過并行地執(zhí)行每個(gè)事務(wù)中的子任務(wù)可以縮短響應(yīng)時(shí)間，同時(shí)提高吞吐量。線性的擴(kuò)展比：如果線性的擴(kuò)展比：如果TL=TS，則稱并行系統(tǒng)ML亞線性的擴(kuò)展比：如果TL>TS，則稱系統(tǒng)實(shí)現(xiàn)TS加速比通過增加并行度來在更短的時(shí)間里運(yùn)行一個(gè)給定的任務(wù)。由于并行性而獲得的加速比定義為TS/TL目標(biāo)--使處理任務(wù)所需的時(shí)間與所分配的處的資源的N倍，獲得的加速比也是N時(shí)，稱并行系統(tǒng)實(shí)現(xiàn)了線性的加速比。統(tǒng)的資源的N倍，而獲得的加速比小于N，則稱系統(tǒng)實(shí)現(xiàn)了亞線性的加速比。擴(kuò)展比通過提供 的資源以在相同的時(shí)間里處理更大的任務(wù)。是由于并行性而獲得的擴(kuò)展比定義為TS目標(biāo)--使能夠處理的任務(wù)的規(guī)模與所分配的 無共享：各處理器既不共享公共的主共享內(nèi)存SM（又稱做全共享的體系結(jié)構(gòu)SE） PM主器中的數(shù)據(jù)可以被任何一個(gè)處理器。一個(gè)處理器可以通過往主器中寫的辦法來向其他缺點(diǎn)：規(guī)模過32個(gè)或64或互連網(wǎng)絡(luò)是由所有的處理器共享的，它會(huì)變成瓶頸。共享磁盤 器。 無共享器，以及一個(gè)或多個(gè)磁盤。一個(gè)結(jié)點(diǎn)上的處理器可以通過高速互連網(wǎng)絡(luò)與另一個(gè)結(jié)點(diǎn)上的另一個(gè)處理器通信。一個(gè)結(jié)點(diǎn)作為該結(jié)點(diǎn)所擁有的磁盤上的數(shù)據(jù)的服務(wù)器。P 層次的PMPMPM（Stonebraker1986年提出，得到普遍接受。對關(guān)系進(jìn)行劃分，放置到多個(gè)磁盤上，從而可以并行地，以縮減從磁盤上對關(guān)系進(jìn)行檢I/O輪轉(zhuǎn)法(Round-范圍分布(Range10.2.110.2.1劃分策略輪轉(zhuǎn)法：一種均勻地在各個(gè)磁盤上分配元組的標(biāo)號為Dimodn的磁盤上。元組在多個(gè)磁盤上平均分布，每個(gè)磁盤上具有大致相同數(shù)目的元組。10.2.1劃分策略散列分布：基于劃分屬性將元組散列分布到各個(gè)磁定一個(gè)值域?yàn)閧0,1,…n-1}的散列函數(shù)。將關(guān)hash(t[A])=0hash(t[A])=1hash(t[A])= hash(t[A])=n-10.2.110.2.1劃分策略T[A]<VV<=T[A]<VV<=T[A]<V10.2.1劃分策略范圍分布：往每一個(gè)磁盤上分配連續(xù)的屬性值范[V0,V1,…,Vn-10.2.210.2.2I/OSELECT*FROM 例SELECT*FROMbranchWHEREbranch-city=SELECT*FROMWHEREbalanceBETWEEN10000AND10.2.2I/O并行屬性值偏斜：關(guān)系的諸元組在劃分屬性上取值不均衡所導(dǎo)致的劃分中的負(fù)載不平衡。劃分偏斜：在不存在屬性值偏斜的情況下，出現(xiàn)的劃分中的負(fù)載不平衡。 10.3對于共享磁盤或無共享的體系結(jié)構(gòu)：各處理器必須以一種協(xié)同的方式來執(zhí)行和日志等任務(wù)，需要它們互相之間傳送消息。10.310.3查詢間并行 10.3查詢間并行一個(gè)事務(wù)對一個(gè)頁面進(jìn)行任何讀寫之前，先根據(jù)需要用共享或排他方式該頁面。當(dāng)事務(wù)獲得了對頁面的共享鎖或排他鎖，它立刻從共享磁盤中讀到該頁面的版本。頁面刷新到共享磁盤中，然后再釋放。上述協(xié)議保證，當(dāng)一個(gè)事務(wù)對于某頁面設(shè)置了共享鎖或排他鎖時(shí)，它得到該頁面的正確版本。10.410.4例Пcustomer-name(Пaccount-|><|σbalance>1000|><|10.4查詢內(nèi)并行操作內(nèi)并行：通過并行地執(zhí)行每一個(gè)操作，如排序、選擇、投影、連接等，來加快一個(gè)查詢的處理速度。操作間并行：通過并行地執(zhí)行一個(gè)查詢表達(dá)式中的多個(gè)不同的操作，來加快一個(gè)查詢的處理速度。假設(shè)關(guān)系初始地分布在磁盤D0，D1，…，Dn-處理器P0，P1，…，Pm（m<n）進(jìn)行排序。假設(shè)關(guān)系初始地分布在磁盤D0，D1，Dn-1（不是按…12每個(gè)處理器在本地對送給它的關(guān)系的分片進(jìn)行排序。最后串接各個(gè)處理器的排序結(jié)果。數(shù)據(jù)并行：在不同的數(shù)據(jù)排序。（數(shù)據(jù)并行）分向量，用范圍分布的辦法分布到處理器P0…,10.5.1并行排序..... 10.5.2并行連接10.5.2并行連接 rs10.5.2基本思想：將檢測一個(gè)個(gè)元組對是否滿足連接條件的操作分散到多個(gè)處理器上進(jìn)行，最后從各個(gè)處理器收集結(jié)果，產(chǎn)生最終連接結(jié)果?；趧澐值倪B接（適用于等值連接和自然連接 連接（適用于一般的連接條件并行連接基于劃分的連接（）rr1s1并行連接 ——特殊情況：非對稱的分片- 10.5.210.5.2并行連接s s s s10.5.2并行連接 連接——一般情況（兩個(gè)關(guān)系都分片（保證至少有m*n個(gè)處理器，標(biāo)記為P0,0,P0,1,…,P0,m-P1,0…Pn-1,m-1 到處理器Pi,0,Pi,1,…,Pi,m-1 到處理器P0,i,P1,i,…,Pn-1,i10.5.2并行連接10.5.2并行連接 …并行連接并行連接并行連接 10.5.2并行連接 h1分布r元 rHs sh1分布sai=v（r）：如果關(guān)系r是基于屬性ai進(jìn)行劃分l≤aii可以通過將關(guān)系基于分組屬性進(jìn)行劃分（范圍分布或散列分布），然后在每個(gè)處理器中并行地計(jì)算 Tpart+Tasm+max(T0,T1,…,Tn-10.6.110.6.110.6.1流水線并行 r1|><|r2|><|r3|><|處理器P1計(jì)算temp1←r1|><|r2當(dāng)P1計(jì)算出r1|><|r2中的元組時(shí)，就將這些元組提供r1|><|r2中的一些元組。P2就可以利用它得到的元組開始計(jì)算r3|><|temp1。10.6.110.6.1流水線并行 r1|><|r2|><|r3|><|r4|><|流水線并行的重要性主要在于避免中間結(jié)果寫到磁盤，而不在于提高并行度： 10.6.210.6.2例r1|><|r2|><|r3|><|10.710.710.7并行查詢優(yōu)化串行系統(tǒng)中找具有最小工作量的查詢執(zhí)行計(jì)劃，這樣的執(zhí)行計(jì)劃必然具有最快的響應(yīng)時(shí)間。并行系統(tǒng)中找具有最快響應(yīng)時(shí)間的查詢執(zhí)行計(jì)劃。因?yàn)榫哂凶钚」ぷ髁康牟樵儓?zhí)行計(jì)劃可能具有很強(qiáng)的固有順序性，難以并行化。通過網(wǎng)絡(luò)連接在一起的（地理上分布