分布式查詢處理(數(shù)據(jù)庫)

時間：2022-12-20 06:30:01 | 來源：信息時代

時間：2022-12-20 06:30:01 來源：信息時代

    分布式查詢處理 : 采用全局查詢處理和局部查詢處理來實現(xiàn)分布式數(shù)據(jù)庫查詢的一種技術(shù)。通常,用戶或應用只能看到全局關系組成的全局數(shù)據(jù)庫,且只能在全局關系上完成查詢,并要采用高層數(shù)據(jù)操縱語言來表達全局查詢。之后,由系統(tǒng)將其轉(zhuǎn)換成內(nèi)部表示,并將全局查詢轉(zhuǎn)換為片段查詢。在查詢執(zhí)行過程中,最終涉及的是具體場地上的物理關系的查詢?？梢?分布式查詢處理主要完成將高層的查詢語言(典型的為關系驗算)正確地轉(zhuǎn)換為語義等價的內(nèi)部語言(典型的為關系代數(shù)),并將全局查詢轉(zhuǎn)換為片段查詢。其中,查詢優(yōu)化具有重要作用,因為許多等價的內(nèi)部表示語言的執(zhí)行代價差別很大。因此,為提高查詢效率,在查詢處理過程中需要進行優(yōu)化處理。
查詢優(yōu)化就是確定出一種執(zhí)行代價最小的查詢執(zhí)行策略或?qū)ふ蚁鄬^優(yōu)的操作執(zhí)行步驟,以提高系統(tǒng)執(zhí)行效率。在分布式數(shù)據(jù)庫系統(tǒng)中,影響查詢處理效率的因素主要有: 網(wǎng)絡傳輸代價、局部I/O代價及CPU處理代價等。分布式查詢優(yōu)化的目標就是指局部執(zhí)行代價和網(wǎng)絡傳輸代價的和最小。局部執(zhí)行代價主要指輸入/輸出次數(shù)(I/O代價)及CPU處理代價。網(wǎng)絡傳輸代價主要指傳輸啟動代價和數(shù)據(jù)傳輸代價。通常,查詢優(yōu)化包括全局優(yōu)化和局部優(yōu)化兩部分。這里主要介紹全局查詢優(yōu)化,主要包括全局優(yōu)化和片段優(yōu)化。
1.全局優(yōu)化
全局優(yōu)化是將用戶請求構(gòu)成的查詢樹進行等價變換,得到一種“最好”的操作順序。等價變換的基本思想是先進行中間結(jié)果變小的運算?？梢?全局優(yōu)化就是盡量先進行一元運算,使中間結(jié)果變小,以減少后續(xù)的二元運算代價,從而將一元運算推向查詢樹的底部。變換的通用準則為:
準則1: 盡可能將一元運算移到查詢樹的底部(樹葉部分),使之優(yōu)先執(zhí)行一元運算。
準則2: 利用一元運算的重復律,縮減每一關系,以減少關系尺寸,降低網(wǎng)絡傳輸量和I/O大小。
假設一供應關系數(shù)據(jù)庫中有供應者SUPPLIER{SNO,SNAME,AREA}和供應SUPPLY{SNO,PNO,QTY}兩關系,SNO、SNAME和AREA分別為供應者編號、供應者姓名和供應者所屬地域。PNO和QTY分別為零件號和數(shù)量。
若有查詢要求: “找出地域在 ‘北方’ 且供應100號零件的供應商的信息”,則SQL查詢語句為:
SELECT SNO,
SNAME FROM SUPPLIER,
SUPPLY WHERE AREA="北方"
AND PNO=100
AND SUPPLIER.SNO=SUPPLY.SNO
等價的關系表達式為:
Q₁:∏_SNO,SNAMEσ_{AREA="北方"and PNO=100}(SUPPLIER⋈SUPPLY)。
Q₁的查詢樹如圖1(a)所示。
在查詢樹Q₁的基礎上進行全局優(yōu)化。根據(jù)分配律,將一元運算向下移,得到全局優(yōu)化后的查詢樹Q₂,如圖1(b)所示。在全局關系上的查詢,稱為全局查詢。如圖1中的Q₁和Q₂。

圖1 查詢樹

查詢的處理過程是從全局關系到片段關系,最后再到實際操作的副本關系。為此,需要利用全局關系與其片段關系的等價關系,將全局查詢中的全局關系替換為對片段關系的查詢,變換后的查詢稱為片段查詢。對應于片段查詢的查詢樹,稱為片段查詢樹。
基于全局查詢與片段查詢的等價關系,生成片段查詢樹,具體生成步驟: ①將分片樹的h(水平)結(jié)點轉(zhuǎn)換為查詢樹的∪(并集)結(jié)點;②將分片樹的v(垂直)結(jié)點轉(zhuǎn)換為查詢樹的⋈(連接)結(jié)點; ③用替換后的分片樹代替全局查詢樹中的全局關系,得到片段查詢樹。
假設SUPPLIER和SUPPLY的分片定義為:
S₁＝σ_{AREA="北方"}(SUPPLIER);
S₂＝σ_{AREA="南方"}(SUPPLIER);
SUPPLY₁＝σ_{AREA="北方"}(SUPPLY);
SUPPLY₂＝σ_{AREA="南方"}(SUPPLY)。
則分片樹和轉(zhuǎn)換表示如圖2所示。

圖2 分片樹與轉(zhuǎn)換

在Q₂基礎上,用SUPPLIER分片樹替換后的∪結(jié)點替換查詢樹Q₂的全局關系SUPPLIER,用SUPPLY分片樹替換后的∪結(jié)點替換查詢樹Q₂的全局關系SUPPLY,即得到轉(zhuǎn)換后的片段查詢樹為Q₃(見圖3)。

圖3 Q₃查詢樹

2. 片段優(yōu)化
片段優(yōu)化使全局優(yōu)化樹轉(zhuǎn)換的片段查詢樹進一步優(yōu)化,得到片段優(yōu)化樹。這里需了解兩個基本概念——限定條件和屬性表。限定條件指每個水平片段中數(shù)據(jù)元組所滿足的分片條件,也稱水平分片的取值范圍。屬性表指每個垂直片段中元組所包含的分片屬性,也稱垂直分片的屬性范圍。
例如,存在雇員關系EMP{ENO,ENAME,BIRTH,SALARY,DNO},其分片定義:
E₁＝∏_{ENO,ENAME,BIRTH}(EMP);
E₂＝∏_{ENO,SALARY,DNO}(EMP);
E₂₁＝σ_DNO=201(E₂₎;
E₂₂＝σ_DNO=202(E₂₎;
E₂₃＝σ_{DNO201 AND DNO202}(E₂₎。
則其分片樹如圖4所示。

圖4 EMP分片樹

針對E₂₁定義,其屬性表為ENO,SALARY,DNO,限定條件為DNO=201。
片段查詢優(yōu)化的目的是化簡片段查詢樹,具體思想是依據(jù)水平分片的限定條件,去除空關系,如Q1中AREA="南方"的關系;依據(jù)屬性表,去除無用的中間關系,即無查詢所需屬性的關系。片段查詢優(yōu)化規(guī)則如下:
準則1: 對于一元運算,根據(jù)一元運算的重復律,將葉子結(jié)點之前的選擇運算作用于片段,如果不滿足片段的限定條件,則置為空關系。
準則2: 對于連接運算的樹,若連接條件不滿足,則將其置為空關系。
準則3:在查詢樹中,將連接運算(⋈)下移到并運算(∪)之前執(zhí)行。
準則4: 消去不影響查詢運算的垂直片段。
例如,以片段查詢樹Q₃為基礎,依據(jù)片段查詢優(yōu)化準則進行化簡的步驟:
(1)根據(jù)片段查詢優(yōu)化準則1,將葉子結(jié)點之前的選擇運算作用于片段,得到Q₄(見圖5)。

圖5 Q₄片段查詢樹

(2)若存在如下分片定義:
S₁＝σ_{AREA="北方"}(SUPPLIER);
S₂＝σ_{AREA="南方"}(SUPPLIER);
SUPPLY₁＝σ_{AREA="北方"}(SUPPLY);
SUPPLY₂＝σ_{AREA="南方"}(SUPPLY)。
則Q₄中的虛線部分為空關系。按限定條件化簡,去除空關系,得到Q₅查詢樹(見圖6)。

圖6 Q₅查詢樹

(3)根據(jù)準則3,將連接運算(⋈)下移到并運算(∪)之前,得到Q₆(見圖7)。

圖7 Q₆查詢樹

由于:
S₁＝σ_{AREA="北方"}(SUPPLIER);
S₂＝σ_{AREA="南方"}(SUPPLIER);
SUPPLY₁＝σ_{AREA="北方"}(SUPPLY);
SUPPLY₂＝σ_{AREA="南方"}(SUPPLY)。
因此,Q₆查詢樹中虛線部分滿足準則2,即其連接條件不滿足,則將其置為空關系。將虛線部分從查詢樹中去掉,得到Q₇(見圖8)。Q₇為化簡后的最終的優(yōu)化查詢。

圖8 Q₇優(yōu)化后的查詢樹