查詢有多種實(shí)現(xiàn)方法,例如查“王平”所選修的課程編號及成績,系統(tǒng)可用多種等價的關(guān)系代數(shù)表達(dá)式完成這一操作,如
T1=?CNO , GRADE(σ-S . SNO=S_C . SNO ù S . SNAME=”王平”(SXS_C))
T2=?CNO , GRADE(σ- SNAME=”王平”(S>< S_C))
T3=?CNO , GRADE((σ- SNAME=”王平”(S))>< S_C)
在這些操作中,它們的結(jié)果是一樣的,但執(zhí)行過程相差很大,且系統(tǒng)的開銷也大相徑庭。
對于T1而言,當(dāng)計(jì)算SXS_C時,需要把S和S-C的全部元組連接起來。假設(shè)每個存儲塊能保存10元組,S的物理文件在存貯器中需B1個存貯存塊,S_C的物理文件需B2塊。內(nèi)存中提供的運(yùn)算緩沖區(qū)多能裝n塊,而B1、B2均大于n。因而對乘積較好的執(zhí)行辦法是:將S文件分成若干個n-1塊,首先將第一個n-l塊裝入內(nèi)存,并逐次裝入S_C文件的一個塊,使之與S已裝入的n-l塊進(jìn)行乘積運(yùn)算;當(dāng)S_C文件的每塊都裝入一遍后,再往內(nèi)存裝入S文件的下一個n-l塊,并同樣從第一塊開始逐次地裝入S_C的每一塊,重復(fù)執(zhí)行上述連接運(yùn)算,這樣直到計(jì)算完乘積的全部元組為止,其讀塊數(shù)目為: B1+ [B1/(n-1)]* B2
設(shè)B1=B2=1500,n=80,則所需的讀塊的總數(shù)目為1500+[1500/79]*1500=30000。假設(shè)一秒鐘能讀20塊時,大約需要25分鐘時間。同樣假設(shè)每個存儲塊能保存聯(lián)接后的10 個元組和一秒鐘能寫入20塊,則聯(lián)接后一共有1500*1500=2250000塊,將聯(lián)接后的中間結(jié)果寫入存儲器需要1875分鐘,然后再將中間結(jié)果讀出來進(jìn)行選擇和投影,也需1875分鐘。與讀塊和寫塊相比,聯(lián)接、選擇、投影等運(yùn)算時間均可忽略不計(jì)。完成T1表達(dá)式的運(yùn)算的時間大約需要3775分鐘,即62小時。
對T3而言,先對S文件作SNAME=”王平”的選擇操作,讀塊數(shù)目為B1;然后把結(jié)果與S_C作連接、投影運(yùn)算,讀塊數(shù)目為B2,所以總的讀塊數(shù)目為B1+B2=3000,由于滿足條件的元組很少(大約50個元組),不用保存中間結(jié)果文件,因而完成T3表達(dá)式共需約2.5分鐘(一秒鐘仍讀20塊),僅等于前者的一千五百分之一。當(dāng)文件的存貯塊數(shù)更多且存在關(guān)于SNAME的倒排索引時,兩者的時間差別將更為顯著。
對于一個運(yùn)算表達(dá)式,能否找出一個與之等價且操作時間更少的表達(dá)式呢?這正是查詢優(yōu)化所要研究的問題。
T1=?CNO , GRADE(σ-S . SNO=S_C . SNO ù S . SNAME=”王平”(SXS_C))
T2=?CNO , GRADE(σ- SNAME=”王平”(S>< S_C))
T3=?CNO , GRADE((σ- SNAME=”王平”(S))>< S_C)
在這些操作中,它們的結(jié)果是一樣的,但執(zhí)行過程相差很大,且系統(tǒng)的開銷也大相徑庭。
對于T1而言,當(dāng)計(jì)算SXS_C時,需要把S和S-C的全部元組連接起來。假設(shè)每個存儲塊能保存10元組,S的物理文件在存貯器中需B1個存貯存塊,S_C的物理文件需B2塊。內(nèi)存中提供的運(yùn)算緩沖區(qū)多能裝n塊,而B1、B2均大于n。因而對乘積較好的執(zhí)行辦法是:將S文件分成若干個n-1塊,首先將第一個n-l塊裝入內(nèi)存,并逐次裝入S_C文件的一個塊,使之與S已裝入的n-l塊進(jìn)行乘積運(yùn)算;當(dāng)S_C文件的每塊都裝入一遍后,再往內(nèi)存裝入S文件的下一個n-l塊,并同樣從第一塊開始逐次地裝入S_C的每一塊,重復(fù)執(zhí)行上述連接運(yùn)算,這樣直到計(jì)算完乘積的全部元組為止,其讀塊數(shù)目為: B1+ [B1/(n-1)]* B2
設(shè)B1=B2=1500,n=80,則所需的讀塊的總數(shù)目為1500+[1500/79]*1500=30000。假設(shè)一秒鐘能讀20塊時,大約需要25分鐘時間。同樣假設(shè)每個存儲塊能保存聯(lián)接后的10 個元組和一秒鐘能寫入20塊,則聯(lián)接后一共有1500*1500=2250000塊,將聯(lián)接后的中間結(jié)果寫入存儲器需要1875分鐘,然后再將中間結(jié)果讀出來進(jìn)行選擇和投影,也需1875分鐘。與讀塊和寫塊相比,聯(lián)接、選擇、投影等運(yùn)算時間均可忽略不計(jì)。完成T1表達(dá)式的運(yùn)算的時間大約需要3775分鐘,即62小時。
對T3而言,先對S文件作SNAME=”王平”的選擇操作,讀塊數(shù)目為B1;然后把結(jié)果與S_C作連接、投影運(yùn)算,讀塊數(shù)目為B2,所以總的讀塊數(shù)目為B1+B2=3000,由于滿足條件的元組很少(大約50個元組),不用保存中間結(jié)果文件,因而完成T3表達(dá)式共需約2.5分鐘(一秒鐘仍讀20塊),僅等于前者的一千五百分之一。當(dāng)文件的存貯塊數(shù)更多且存在關(guān)于SNAME的倒排索引時,兩者的時間差別將更為顯著。
對于一個運(yùn)算表達(dá)式,能否找出一個與之等價且操作時間更少的表達(dá)式呢?這正是查詢優(yōu)化所要研究的問題。