數(shù)據(jù)庫管理系統(tǒng)基本技術(shù)課件

1、數(shù)據(jù)庫管理系統(tǒng)基本技術(shù)主要內(nèi)容數(shù)據(jù)庫存儲技術(shù)數(shù)據(jù)庫查詢技術(shù)3參考書Raghu Ramakrishnan, Johannes Gehrke, DataBase Management Systems(Second Edition), McGraw-HillHector Garcia-Molina, Jeffrey D. Ullman, Jennifer Widom, DataBase systems the complete book, Prentice HallAbraham Silberschatz, Henry F. Korth,etc. Database System Concepts,M

2、c Graw Hill4數(shù)據(jù)庫存儲結(jié)構(gòu)5數(shù)據(jù)庫存儲結(jié)構(gòu)物理存儲介質(zhì)RAID磁盤系統(tǒng)DBMS對磁盤空間的管理DBMS從磁盤讀取數(shù)據(jù)的方法文件中管理頁(page)的方法頁中記錄的處理形式單條記錄的存儲方式6物理存儲介質(zhì)磁盤空間管理文件管理緩沖區(qū)管理控制磁盤上可用的空間以記錄的文件的形式提供給高層的DBMS進(jìn)行訪問，向磁盤空間管理器申請或釋放空間將記錄從磁盤讀到Buff Pool7存儲介質(zhì)層次高速緩存內(nèi)存快閃存磁盤存儲器光存儲器磁帶存儲器第二級存儲器（secondary storage）第三級存儲器（tertiary storage）Primary storage8存儲結(jié)構(gòu)分級存儲的原因價格因素主存

3、是磁盤的100倍尋址的問題32位機的主存大小小于232數(shù)據(jù)需要永久保存磁帶的特點價格便宜，存儲量大順序讀取9磁盤基本概念硬件上的最小單位是sector,是硬件的不可變屬性Block是數(shù)據(jù)存儲的最小單元，由若干sector構(gòu)成硬盤上的同心圓構(gòu)成track相同半徑的同心圓構(gòu)成Cylinder存放數(shù)據(jù)的盤片為Platter每個面有一個讀頭，通過磁盤臂進(jìn)行移動磁盤轉(zhuǎn)動，讀頭不動10磁盤11磁盤硬盤的容量記錄盤面數(shù)每記錄盤面的磁道數(shù)每磁道的盤塊數(shù)每個盤塊的字節(jié)數(shù)數(shù)據(jù)的定位信息柱面號磁頭號盤塊號，系統(tǒng)對盤塊進(jìn)行統(tǒng)一編號磁盤的性能指標(biāo)磁盤容量：10180，000M存取時間Seek timeRotationa

4、l delayTransfer time傳輸速度：15MB/秒可靠性：38萬小時12磁盤讀寫的并行性一般的系統(tǒng)不支持讀頭間讀取數(shù)據(jù)的并行性少數(shù)支持有限度的并行，如兩個并行，主要原因在于讀頭無法并行移動磁盤控制器負(fù)責(zé)實現(xiàn)對磁盤的基本操作，如移動讀頭，定位傳輸數(shù)據(jù)等Checksum用于檢測數(shù)據(jù)是否正確地讀寫，讀寫時各算一遍記錄的存取方式不跨塊方式跨塊方式13磁盤結(jié)構(gòu)對性能的影響DBMS在操作時數(shù)據(jù)在內(nèi)存中磁盤和內(nèi)存間數(shù)據(jù)交換的單位是Block,一次傳輸為一次I/O操作為了提高速度，最好將同時讀寫的數(shù)據(jù)放在接近的地方，如同一block、track、clinderCreate tables space

5、overhead. transfer.14第三級存儲器光盤CDDVDWORM磁帶膠片15RAID磁盤系統(tǒng)磁盤是數(shù)據(jù)庫管理系統(tǒng)性能的瓶頸微處理器速度的提高為每年50%磁盤訪問的速度的提高為每年10%數(shù)據(jù)傳輸?shù)乃俣鹊奶岣邽槊磕?0%磁盤陣列（Disk Array）通過數(shù)據(jù)條帶（Data Striping）分布將多個磁盤變成一個整體若干磁盤組織在一起，通過并行提高速度通過冗余提高數(shù)據(jù)的可靠性Redundant array of independent disk=RAID16數(shù)據(jù)條帶磁盤間的并行性提高了磁盤組數(shù)據(jù)讀取的性能數(shù)據(jù)條帶數(shù)據(jù)被分成等長的分區(qū)，分布在多個盤上，每個分區(qū)的大小為一個條帶單元(st

6、riping unit)17磁盤空間管理DBMS結(jié)構(gòu)的最底層以頁為單位組織數(shù)據(jù)，主要操作包括讀、寫、申請和釋放經(jīng)常訪問的數(shù)據(jù)可放在連續(xù)的空間中隔離上層模塊和底層的軟、硬件平臺18磁盤空間管理管理空閑塊的方法記錄哪些塊正在使用，每一頁的位置通過一個空閑塊鏈表或空閑塊位圖來記錄空閑的塊實現(xiàn)方法利用操作系統(tǒng)文件系統(tǒng)管理磁盤空間自己實現(xiàn)對磁盤的訪問選擇的因素跨平臺的要求有的功能操作系統(tǒng)不提供19緩沖區(qū)管理器負(fù)責(zé)將磁盤上的數(shù)據(jù)讀入內(nèi)存并寫回磁盤的軟件層管理器管理的內(nèi)存空間稱為Buffer PoolBuffer Pool中的每個頁稱為Frame(每個Frame包含若干slot)如Buffer Pool有1

7、0個頁，表中有100個頁，如何進(jìn)行掃描工作決定內(nèi)存中那些頁應(yīng)該被替換的策略稱為Replacement Policy20工作流程DB高層代碼的頁請求Buffer PoolFree FrameDirty FrameDB高層代碼的頁請求Buffer PoolFree FrameDirty Frame如果所需的頁不在BufferPool中且Buffer Pool已滿則用Replace Policy進(jìn)行調(diào)度正在訪問的frame已訪問完且未被修改的數(shù)據(jù)21數(shù)據(jù)結(jié)構(gòu)和流程每個frame包括：pin_count,dirtypin_count:正在訪問該frame的事務(wù)的個數(shù)Dirty:已經(jīng)被修改過的Frame

8、請求處理的流程查看Buffer pool是否包含此頁，如沒有，則找一個pin_cout為的frame，pin_cout+如dirty為true,則將其寫入磁盤將相應(yīng)的頁讀入此frame將frame的地址返回22幾點補充Dirty代表此frame的數(shù)據(jù)已被修改，在Dirty frame被替換之前需要同步到磁盤上申請新的frame時如沒有可替換的frame，則等待如何處理多個事務(wù)同時訪問一個frame中的數(shù)據(jù)？23緩沖區(qū)的替換策略最早使用策略(Lest recently used,LRU)當(dāng)pin_count=0時該frame成為可選擇，但并不是馬上被替換，因為在此之前有可能再次被訪問最早變成可選

9、擇的頁被首先替換Clock策略將所有的frame排成一個圈，下一個被替換的頁是圈上的下一個可選擇的頁使用referenced標(biāo)志避免剛被訪問過的frame被再次訪問，其想法是referenced在第一遍訪問時變成true，第二遍才替換24緩沖區(qū)的替換策略實際系統(tǒng)中的Buffer PoolDB2：clock,允許有多個Buffer PoolSybase ：LRU,允許有多個Buffer PoolInformax,Oracle: LRU,單個Buffer PoolSql Server: clock,單個Buffer Pool25Buffer Pool的預(yù)取Buffer Pool與virtual m

10、emory區(qū)別在于Buffer Pool能夠發(fā)現(xiàn)頁訪問模式頁訪問模式產(chǎn)生的原因在于，頁的訪問方式由上層的查詢代數(shù)和操作決定頁的預(yù)取DB2中的Prefetchingdirty frame的強制寫盤26文件與索引每個頁中包含若干條記錄，每個文件中包含若干個頁每個記錄有一個唯一的標(biāo)識符:rid，它包括頁號和在頁中的位置不同的數(shù)據(jù)庫管理系統(tǒng)的rid的定義略有不同27堆文件數(shù)據(jù)在文件中以記錄為單位無序地存儲，是最簡單的文件形式提供的功能包括：創(chuàng)建、刪除文件，插入刪除記錄需要討論的問題記錄頁中的空閑區(qū)間記錄有空閑區(qū)間的頁如何維護(hù)文件空閑區(qū)域的位置頁的鏈表頁字典28頁的鏈表每個文件記錄其第一個頁該頁連接兩條

11、鏈表缺點對非定長記錄則全在空鏈表中頭表數(shù)據(jù)頁數(shù)據(jù)頁數(shù)據(jù)頁.含空閑區(qū)間的頁數(shù)據(jù)頁數(shù)據(jù)頁數(shù)據(jù)頁.不含空閑區(qū)間的頁29頁字典用一個字典記錄每個頁的信息，包括空閑的空間大小字典的長度相對數(shù)據(jù)部分較小分配空間前將字典讀入.數(shù)據(jù)頁1數(shù)據(jù)頁2數(shù)據(jù)頁n字典頭頁30順序文件根據(jù)查找鍵的值的順序存儲記錄的文件每個記錄有一個指針，按鍵值大小創(chuàng)建鏈表通過自由空間管理，管理空閑空間HeF-257800LiuA-102600ZhouC-34375031順序文件插入操作尋找插入位置申請空閑空間維護(hù)鏈表HeF-257800LiuA-102600ZhouC-343750MaB-547500刪除操作32聚集文件一個文件中存儲多個

12、關(guān)系中的元組根據(jù)鍵屬性進(jìn)行數(shù)據(jù)組織S1 Wang 20 MS2 Liu 21 FS3 Chen 22 MS1 C1 80S1 C2 70S3 C1 90S3 C2 85S3 C3 95SSCS1Wang20S1S1C1C28070S2Liu21S3Chen22S3S3S3C1C2C3908595MFM33代價模型代價用與于估算不同的查詢操作的代價基本的符號B:數(shù)據(jù)庫中數(shù)據(jù)頁的數(shù)量R:每頁中記錄的個數(shù)D:讀寫一頁的時間C:處理一條記錄的時間（對相應(yīng)的屬性進(jìn)行比較）H:對一條記錄執(zhí)行執(zhí)行Hash函數(shù)的時間34代價計算的單位磁盤讀寫操作和計算的代價差巨大D=15毫秒，C,H=100納秒上述差距將越來

13、越大本書采用磁盤頁的讀寫作為代價標(biāo)準(zhǔn)在本書只是討論影響操作的主要因素本書沒有討論塊的讀寫問題，由于一塊上有若干頁，而且是硬件操作的基本單位。但頁是DBMS系統(tǒng)的讀寫單位，所以選用了頁35三種文件組織方式的比較三種文件組織方式隨機排序文件，堆文件對一系列屬性進(jìn)行排序的文件對一系列屬性執(zhí)行Hash操作的文件Search Key:用于排序和Hash的列36基本操作Scan讀取文件中所有的記錄Search with equality selection讀取文件中滿足某一相等條件的記錄Search with range selection讀取文件中滿足區(qū)間條件的記錄Insert將特定記錄插入文件Dele

14、te將特定記錄從文件中刪除37堆文件Scan代價為B(D+RC)Search with equality selection如事先知道只有一個結(jié)果，則為0.5B(D+RC),否則同ScanSearch with range selection代價為B(D+RC)Insert2D+C(數(shù)據(jù)加在關(guān)系的最后面)DeleteD+C(數(shù)據(jù)已經(jīng)在內(nèi)存中，可用rid中的page id訪問)38排過序的文件Scan代價為B(D+RC)Search with equality selection代價為Dlog2B+Clog2R(沒有重復(fù)的情況，且對查詢屬性排序)Search with range selecti

15、on同上InsertB(D+RC)(數(shù)據(jù)是連續(xù)存放的情況)DeleteB(D+RC)(數(shù)據(jù)是連續(xù)存放的情況)39Hashed的文件文件被分解為筐(Bucket)通過一個Hash函數(shù)找到相應(yīng)的筐需要考慮溢出的情況Hash函數(shù)Bucket1Bucket2Bucket3Bucket4Bucket540Hashed的文件Scan代價為1.25B(D+RC)(由于在文件中保存了一定的空閑)Search with equality selection代價為H+D+0.5RC(只有一個結(jié)果)Search with range selection代價為1.25B(D+RC)Insert代價為2DDelete代

16、價為C+D41頁的格式頁由一系列的記錄構(gòu)成每個記錄為一個slot記錄的id為(page id, slot number)42記錄格式記錄格式定長記錄變長記錄系統(tǒng)catalog中記錄了相關(guān)的信息43定長記錄每條記錄的長度是固定的，即沒有變長字段，一個頁存放記錄的數(shù)量和位置也是確定的刪除方法44定長記錄slot1slot2slotn.nPackedslot1slot2slotn.mUnpacked1 0 1. 0 1空閑空間m m-1 . 2 1每次刪除了記錄就將該頁最后一條記錄移到被刪除的位置，所有的空閑空間均在頁的下部，但rid會不斷調(diào)整記錄數(shù)記錄數(shù)每次刪除了記錄不做移動，所有的空閑空間的信息

17、記錄在頁的尾部45定長記錄數(shù)據(jù)連續(xù)存放每個字段有固定的位置各種數(shù)據(jù)的方法基本相同F(xiàn)1 F2 F3 F4 . L1 L2 L3 L4Fi=field iLi=Length of field iBase address(B)Address=B+L1+L2+L346變長記錄記錄中包含變長字段，所以記錄的長度是可變的無法分配定長的slot為了避免大量的零碎空間，每次刪除后需要對頁上的空間進(jìn)行調(diào)整。但是要保證rid不變解決方法：用slot字典存放記錄的起始位置和記錄的長度，用記錄在slot字典中的位置代替slot的實際起始位置47變長記錄數(shù)據(jù)頁inSlot字典 頁中slot數(shù)量記錄（i，1）記錄（i，n

18、）記錄（i，2）48變長記錄兩種存放方法數(shù)據(jù)連續(xù)存放用分割符分開：需要掃描無用信息在記錄的前端用指針指向響應(yīng)的位置F1 $ F2 $ F3 $ F4 . Fi=field iF1 F2 F3 F4 49變長記錄對一個列的修改需要移動其它列的位置一條記錄修改后可能造成記錄的長度超過目前該頁所能提供的空間，需要存入其它的頁，為了保證rid不變需要記錄該記錄的目前位置如長度超過一個頁的大小，則要分頁實際系統(tǒng)中Oracle不限制記錄長度DB2等限制長度，但提供大對象數(shù)據(jù)類型50文件組織和索引文件組織是當(dāng)文件存儲在磁盤上時在文件中組織記錄的方法不同的方法有不同的作用索引是查詢操作的性能的工具51文件組織

19、形式的選擇在實際系統(tǒng)可能并不是完全排序，也不是完全的連續(xù)存放52索引簡介索引是加速查詢操作的輔助文件結(jié)構(gòu)對要訪問的屬性值進(jìn)行重新組織，每個索引項包含（屬性值，rid）包括樹型索引和Hash索引一個索引可認(rèn)為是一個data entry的集合，通過它可快速地找到相應(yīng)的記錄所在的位置需要考慮的兩個問題為了方便查詢?nèi)绾谓M織data entrydata entry的構(gòu)成53索引的例子Smith,44,3000Jones,40,6003Tracy,44,5004Ashby,25,3000Basu,33,4003Bristow,29,2007Cass,50,5004Daniels,22,6003ageh1H

20、(age)=00H(age)=01H(age)=10300030005004salh2H(sal)=00H(sal)=1150044003200760036003File hashed on ageFile of pairs hashed on sal54索引中各種不同的data entry三種類型k*:包含了整個記錄search key為k的記錄search key為k的記錄集合用k*就沒有必要再存儲相應(yīng)的記錄，所以可作為一種特殊的文件組織形式兩種方式廣泛地應(yīng)用于各種索引結(jié)構(gòu)，特別是一個表上不只有一 個索引的情況55索引的特性Clustered versus UnClustered Inde

21、xesDense versus Sparse IndexesPrimary versus Secondary IndexesComposite Search key 的索引56Clustered versus UnClustered Indexes如果文件中記錄的次序同索引中data entry的次序是相同的，則這個索引是Clustered(簇聚的)第一種data entry是Clustered只有當(dāng)記錄的順序用索引對應(yīng)的屬性排序時，第二、三種data entry對應(yīng)的索引才是clustered57Clustered versus UnClustered Indexes一個表只有一個Clust

22、ered索引多個unclustered索引鑒于高昂的維護(hù)代價，即使是一個 Clustered索引也經(jīng)常是不嚴(yán)格排序的用溢出鏈表的形式定期重新排序update操作與Clustered對Range查詢Clustered的作用比較大58Clustered Indexes.Index entryData entryData RecordsIndex fileData file59UnClustered Indexes.Index entryData entryData RecordsIndex fileData file60Dense versus Sparse Indexes如果表在該屬性上出現(xiàn)的所

23、有值在索引文件中均至少有一個data entry與之相對應(yīng)則為dens索引。Sparse索引中每個頁有一個data entry第一種 data entry只能用于dense索引第二種 data entry能用于兩種索引第三種 data entry通常用于dense索引Sparse索引只能是Clustered的索引61例子Smith,44,3000Jones,40,6003Tracy,44,5004Ashby,25,3000Basu,33,4003Bristow,30,2007Cass,50,5004Daniels,22,60032225303340444450AshbyCassSmithSpa

24、rse indexon nameDATADense indexon age62Primary and Secondary Indexes如果索引建在包含Primary Key的屬性上則為Primary Index，其它的為Secondary Index另一種解釋為第一種data entry對應(yīng)的索引為Primary Index,另兩種為Secondary index如果兩個data entry在索引屬性上對應(yīng)的值是相同的，則該索引為duplicates index,否則為unique index63Composite Search key 的索引包含多個屬性的索引是Composite Sear

25、ch key 的索引Bob 12 10Cal 11 80Joe 12 20Sue 13 75Name age sal11121213Index 10207580Index 11,8012,1012,2013,75Index 10,1220,1275,1380,11Index 64索引的定義在SQL-92中并沒有關(guān)于索引的語句，在SQL中也沒有涉及索引所有的商用DBMS均提供了與索引相關(guān)的語句CREATE INDEX IndAgeRating on Student WITH STRUCTURE=BTREE KEY=(age,gpa)65結(jié)構(gòu)索引索引提供高效查詢操作方法和動態(tài)維護(hù)方法B+TREE是

26、一種動態(tài)的索引結(jié)構(gòu)，適用于各種情況基于Hash的索引結(jié)構(gòu)66B+樹一種動態(tài)的索引結(jié)構(gòu)靜態(tài)方法的缺點在于當(dāng)插入刪除過多時造成溢出鏈過長，影響效率。也不利于序列連續(xù)存放M階B+樹的特點每個結(jié)點至多有m棵子樹，至少有m/2棵子樹根結(jié)點或為葉結(jié)點，或至少有兩棵子樹在insert,delete操作中樹保持平衡搜索時只需要訪問樹的高度次所有葉結(jié)點在同一層次，data entry層用雙向鏈表連接，便于訪問67B+樹的結(jié)構(gòu).Index entryData entryIndex file68B+樹索引結(jié)點的結(jié)構(gòu)B+樹結(jié)點的格式每個結(jié)點由n個數(shù)值和n+1個指針構(gòu)成pi指向的子樹上的結(jié)點的值k,有ki=k=ki+1

27、通常用第二種或第三種data entryData Entry 本身可以看成為是記錄的文件，如果data entry包含整個記錄，則文件就是數(shù)據(jù)本身，否則是一個單獨的文件。69搜索Func tree_search(nodepointer, search key value K) returns nodepointerIf *nodepointer is a leaf, return nodepointer;else,if KKm then return tree_search(Pm,K)else,find i such that Ki=KKi+1;return tree_search(Pi,K)

28、;Endfunc70B_樹的例子13 1724 302* 3*5* 7*19* 20*22*29* 24* 27*14* 16*33* 34*38* 39*d=271Insert首先從根結(jié)點出發(fā)向下，找到插入數(shù)據(jù)所在的位置。將數(shù)據(jù)插入到相應(yīng)的位置。當(dāng)結(jié)點滿的時候，進(jìn)行分解操作。逐層向上分解直到不需要分解的時候。當(dāng)結(jié)點滿時另一種方案是：當(dāng)該結(jié)點的兄弟結(jié)點不滿時，也可以進(jìn)行重新分配，以減少分解的數(shù)量。72InsertProc Insert(nodepointer,entry,newchildentry)If *nodepointer is a non-leaf node,say N find I

29、such that Ki=entrys key value Ki+1 insert(Pi,entry,newchildentry) if newchildentry is null, return; else, if N has space put*newchildentry on it, set newchildentry to null, return; else split N; first d key values and d+1 nodepointers stay, last d key values and d+1 nodepointers move to new node N2,

30、 newchildentry=&()73insertif N is the root create new node with make the trees root-node pointer point to the new nodes return; If *nodepointer is a leaf node, say L if L has space put entry on it,set newchildentry to null, and return; elsesplit L: first d entries stay, rest move to brand new node L

31、2; newchildentry=&(); set sibling pointers in L and L2 Return ;Endproc74例子5 132* 3*19* 20*22*29* 24* 27*14* 16*33* 34*24 30175* 7*8*增加8以后38* 39*75重新調(diào)整的例子8 1724 302* 3*5* 7*19* 20*22*29* 24* 27*8* 14* 16*33* 34*增加8以后38* 39*76刪除首先從根結(jié)點出發(fā)向下，找到刪除數(shù)據(jù)所在的位置。將數(shù)據(jù)相應(yīng)的位置刪除。當(dāng)結(jié)點過空的時候，進(jìn)行合并操作。逐層向上合并直到不需要合并的時候。當(dāng)該結(jié)點的兄弟

32、結(jié)點不空時，可以考慮重新分配，以減少合并的數(shù)量。該調(diào)整不僅作用在頁結(jié)點上，也可作用在非頁結(jié)點上77刪除Proc delete(parentpointer,nodepointer,entry,oldchildentry)If *nodepointer is a non-leaf node,say N find i such that Ki=entrys key value 1while there are runs to be merge from previous pass is choose next two runs(from previous pass)read each run int

33、o an input buffer;Merge the runs and write to the output bufferforce output buffer to disk one page at a timeendproc計算量分析若輸入文件大小為2k,k為一個整數(shù)Pass 0，產(chǎn)生2k個run，每個1頁Pass 1，產(chǎn)生2k-1個run，每個2頁Pass 2，產(chǎn)生2k-2個run，每個4頁總共需要log2N +1次pass,N為文件的頁數(shù)，對每一頁做一次讀，一次寫總共的開銷為：2N*(log2N +1)例子3,46,2 2 9,48,75,63,13,42,6 2 4,97,85,

34、61,32,3 4,6 2 4,7 8,91,3 5,6 2,3 4,4 6,7 8,91,2 3,5 6 1,2 2,3 3,4 4,5 6, 6 7,8 9 外部Merge排序若內(nèi)存中有B個pages。如何利用2路Merge排序的思想，進(jìn)行排序操作？在pass 0一次性讀入B個頁的數(shù)據(jù)進(jìn)行排序。在pass 1,2,一次性讀入B個頁的數(shù)據(jù)進(jìn)行排序。利用B-1個Buffer頁作為輸入，將最后一個Buffer頁作為輸出的緩沖區(qū)，進(jìn)行B-1路的Merge排序。算法Proc exsort(file)Read B page into memory, sort them, write out a run

35、While the number of runs at end of previous pass 1while there are runs to be merged from previous passchoose next B-1 runs(from previous pass)read each run into an input buffer; page at at timeMerge the runs and write to the output bufferforce output buffer to disk one page at a timeendproc圖示DiskDis

36、kInput 1Input 2Input B-1output 1Pass i0計算量分析第一次產(chǎn)生N1= N/B個runs對數(shù)據(jù)掃描的遍數(shù)，變?yōu)閘ogB-1N1+1最終的I/O次數(shù)為2N* logB-1N1+1性能實例NB=3B=5B=9B=17B=129B=257102743211103105432210413754221051796533106201075331072312864310826149744109301510854如何減少run的個數(shù)在Pass 0的過程中，可使用一些技巧，使得最初的run的長度平均為2B基本想法有一個頁的輸入緩沖區(qū)、一個頁的輸出緩沖區(qū)和一個當(dāng)前排序緩沖區(qū)首先將

37、數(shù)據(jù)調(diào)入當(dāng)前排序緩沖區(qū)（B-2頁）進(jìn)行排序不斷將大于輸出緩沖區(qū)中數(shù)據(jù)的最小的記錄從當(dāng)前排序緩沖區(qū)讀出送入輸出緩沖區(qū)，并不斷從輸入緩沖區(qū)中補充數(shù)據(jù)。直到當(dāng)前緩沖區(qū)中沒有可選的數(shù)據(jù)為止，則當(dāng)前run結(jié)束例子12 4 2 8 10 3 5 當(dāng)前緩沖區(qū)輸出緩沖區(qū)輸入緩沖區(qū)減少I/O代價的優(yōu)化性能的評價是一I/O的次數(shù)為標(biāo)準(zhǔn)的如果一次對連續(xù)的數(shù)據(jù)進(jìn)行讀寫將提高性能如何提高CPU的使用率塊I/O以緩沖區(qū)Block（若干個page）為單位進(jìn)行讀寫將提高單個Page讀寫的速度(減少了磁頭移動的次數(shù))每次只能進(jìn)行F=(B-b)/b個run的合并，其中B為緩沖區(qū)中頁的數(shù)量，b為一個塊中頁的個數(shù)，總的掃描遍數(shù)為lo

38、gFN2+1,其中N2= N/2B應(yīng)用實例NB=103B=5*103B=104B=5*10410211111031111104221110532221063222107433210853321095433雙緩沖區(qū)排序的時間包括I/O的時間和CPU計算的時間在前面的方法中CPU計算的時間同I/O的時間不是并行的對每個run多加一個緩沖區(qū)，一個緩沖區(qū)在進(jìn)行I/O操作的同時，對另一個緩沖區(qū)的數(shù)據(jù)進(jìn)行計算圖示DiskDiskInput 1 Input 2 Input B-1 output 1 Input 1Input 2Input B-1output 1使用B+樹進(jìn)行排序聚集的索引由于磁盤上的數(shù)據(jù)是已

39、經(jīng)排序的，而且上層有一個索引結(jié)構(gòu)，所以查詢和排序操作性能均很高。非聚集的索引Data entry中的數(shù)據(jù)是排序的，但數(shù)據(jù)在磁盤上的存儲次序是雜亂無章的。計算量是(f+p)*N,N是數(shù)據(jù)頁的數(shù)量，p是每頁平均包含的記錄數(shù)，f是data entry中每條記錄的長度同記錄的長度的比關(guān)系操作的執(zhí)行查詢過程簡介Selection 操作General Selection操作Project 操作Join 操作Set操作聚集操作緩沖區(qū)的影響查詢過程介紹影響查詢操作算法性能的因素數(shù)據(jù)庫表的大小、索引、排序情況、緩沖區(qū)的大小和置換策略各個操作實現(xiàn)時常用的基本技術(shù)Iteration:對數(shù)據(jù)庫的表和data entr

40、y中的數(shù)據(jù)逐個進(jìn)行檢測Indexing:如果選擇和連接操作中有限制條件，可通過索引找到滿足條件的元組Partitioning:將一個表分成若干部分，從而降低操作的執(zhí)行代價，常用排序和散列進(jìn)行分區(qū)訪問路徑(Access Paths)各種從關(guān)系表中訪問記錄的方法稱為訪問路徑訪問路徑的方式文件掃描(File Scan)索引加上選擇匹配條件，如attr op value索引要建在attr上op包括,訪問路徑的選擇率(selectivity)是總共訪問的頁數(shù)(包括索引訪問部分)，查詢優(yōu)化的目的是選擇高選擇率的訪問路徑(即訪問的頁數(shù)少的) 例子和相關(guān)參數(shù)Sailors(sid:integer,sname:

41、string,rating:integer,age:real)Reserves(sid:integer, bid:integer, day:date,rname:string)每個reserve記錄長為40個字節(jié)，一頁100條記錄，共1000頁每個sailors記錄長為50個字節(jié)，一頁80條記錄，共500頁只考慮I/O的頁數(shù)忽略結(jié)果的大小，因為同一個操作的不同實現(xiàn)方法都一樣選擇操作討論目標(biāo)：Select * from Reserves R where R.name=Joe對應(yīng)的查詢代數(shù)操作為：name=Joe(R)沒有索引，數(shù)據(jù)不排序需要掃描整個表代價是1000次I/O操作選擇率差，代價比較大

42、選擇操作沒有索引，數(shù)據(jù)排序采用折半查找的方法代價是O(log21000)，約為10次I/O操作選擇率高，代價比較小如約束是attr5，則首先找到5所在的位置，然后從5開始遍歷一般情況下數(shù)據(jù)的排序往往是和索引相關(guān)的。選擇操作使用B+樹索引查詢方法首先找到約束數(shù)據(jù)所在的位置從相應(yīng)的data entry開始向后逐個檢測直到找到所有滿足條件的data entry根據(jù)data entry找到相應(yīng)的元組代價分析一般找到起始的葉節(jié)點只需要2-3次讀寫主要代價在于滿足條件的記錄數(shù)和索引的是否是簇聚的選擇操作使用B+樹索引如果索引是簇聚的，檢測滿足條件的元組的代價一般為一次 I/O如果索引不是簇聚的，檢測滿足條

43、件的元組的代價為滿足條件的元組的個數(shù)次 I/O，如果事先對涉及的pageid進(jìn)行排序，則將減少I/O次數(shù)避免對同一頁進(jìn)行重復(fù)讀假設(shè)查詢條件改為rname“c%”，則結(jié)果數(shù)為表的大小的10%如果索引是簇聚的，則代價約為100次I/O操作如果索引是不是簇聚的，則代價最壞為10000次I/O操作，pageid 排序后最壞約為1000次I/O操作選擇率高，代價比較小選擇操作Hash索引，相等選擇執(zhí)行過程首先找到相應(yīng)的桶，在桶中的數(shù)據(jù)進(jìn)行檢測從數(shù)據(jù)文件中找到相應(yīng)的元組如果Hash不是簇聚的，有10個緩沖區(qū)，100個查詢結(jié)果查找相應(yīng)的rid的代價是1-2次I/O操作查找結(jié)果元組的代價是1-100次I/O操

44、作，如果對page id進(jìn)行排序，則可避免由于緩沖區(qū)小而帶來的重復(fù)調(diào)入的問題General Selection操作一般的查詢條件是一個邏輯表達(dá)式，通過邏輯連接符和連接的項(term)的表達(dá)式，項的形式為attr1 op attr2或attr1 op valueCNF(Conjunctive normal form)由符連接的conjunct一個conjunct是由連接的項的表達(dá)式(day (day8/9/94 bid=5 sid=3) (rname=Joe bid=5 sid=3) 如果conjunct包含則稱為disjunctive，或包含disjunctionGeneral Selecti

45、on操作幾個例子（若查詢條件為rname=Joe bid=5 sid=3 ）如果有一個Hash索引建立在上，則可直接進(jìn)行檢索，但該索引無法完成查詢條件rname=Joe bid=5如果有一個B+樹索引建立在上，則可直接進(jìn)行檢索，該索引還可直接完成查詢條件rname=Joe bid=5，但不適于查詢bid=5 sid=3 General Selection操作幾個例子（若查詢條件為rname=Joe bid=5 sid=3 ）如果有一個索引(Hash或樹)建立在上，則可直接進(jìn)行檢索，然后對查詢結(jié)果進(jìn)一步檢測rname的值如果有一個索引(Hash或樹)建立在上，還有一個索引建立在rname上，則可

46、提供兩種選擇，每種都可以但都必須做進(jìn)一步的檢測，選擇的標(biāo)準(zhǔn)是選擇率。General Selection操作一個索引滿足一個CNF選擇條件的條件如果一個選擇條件不包含disjunction，如果一個項為attribute=value，則建在attribute上的索引是滿足的如果一個選擇條件不包含disjunction，如果若干項為attributei=value，則以這些attributei為前綴的索引是滿足的滿足索引的conjuncts稱為primary conjuncts不包含disjunction的選擇操作的執(zhí)行可以進(jìn)行文件掃描，或先對選擇率最高的primary conjuncts通過索引

47、進(jìn)行查詢，然后利用非primary conjuncts對結(jié)果進(jìn)行篩選如果有多個索引同時滿足選擇條件首先用每個索引進(jìn)行篩選，找出相應(yīng)的候選記錄集合將這些集合進(jìn)行合并，可采用先排序再合并的方法用其它的conjuncts進(jìn)行篩選例如查詢條件為day8/9/94 bid=5 sid=3,索引分別建在day和sid上，則先執(zhí)行兩個選擇，再進(jìn)行合并，最后用bid進(jìn)行篩選不包含disjunction的選擇操作的執(zhí)行實際系統(tǒng)中的rid集合的交操作Oracle 8位圖的and操作用Hash Join的方法，將兩次查詢的結(jié)果進(jìn)行聯(lián)接Sql Server用索引聯(lián)接的方法DB2用Bloom filter的方法Syba

48、se用位圖的方法Informix也提供了相應(yīng)的方法包含disjunction的選擇操作的執(zhí)行如果有一個項需要對整個文件進(jìn)行掃描，則需要對整個文件進(jìn)行掃描若對rname和sid建了索引，查詢條件是day8/9/94 rname=Joe，由于day8/9/14需要掃描整個表，則要整個查詢也需要若查詢是(day8/9/94 rname=Joe) sid=3，則先對sid進(jìn)行檢索，然后進(jìn)行前半部分的篩選若每一項上均滿足索引，則先在索引上進(jìn)行檢索，再將結(jié)果進(jìn)行合并若對rename和day建了索引，查詢條件是day30 5sal,用帶in的嵌套查詢，先用索引將所有可能的候選找出用位圖的方法直接用disju

49、nction進(jìn)行篩選Sybase用位圖和union的方法投影操作Select distinct R.sid,R.bidFrom Reserves Rsid,bid Reservesattr1,attr2 (R)主要功能去掉不需要的屬性刪除重復(fù)元組排序或Hashing的方法基于排序的投影方法基本思路掃描關(guān)系R，生成只包含需要屬性的數(shù)據(jù)集對數(shù)據(jù)集進(jìn)行排序掃描排好序的結(jié)果，通過前后比較去除重復(fù)元組代價分析第一步代價為M+T,M是原始表的大小，產(chǎn)生的中間結(jié)果的大小為T，T=O(M),第二步的代價為O(Tlog2T),第三步代價為O(T)對表reserves(1000頁數(shù)據(jù)，每條記錄長為40)，若bid

50、和sid的長度和為10，則T為250頁，所以代價總和為: 1000+250+2*2*250+250=2500基于排序的投影方法兩種改進(jìn)將第一步同排序操作的pass 0結(jié)合在一起每次做merge的時候去除重復(fù)元組代價分析假設(shè)有20頁緩沖區(qū)Pass 0的代價是1000+250，產(chǎn)生7個run, pass1的代價是250，總共為1500基于Hasing的投影方法主要思路分區(qū)階段重復(fù)數(shù)據(jù)刪除分區(qū)階段將數(shù)據(jù)逐條讀如內(nèi)存，用一塊數(shù)據(jù)作為輸入緩沖區(qū)，另B-1塊作為輸出緩沖區(qū)用Hash函數(shù)進(jìn)行映射，將數(shù)據(jù)集分成B-1塊，圖示DiskDiskOuput 1Ouput 2Ouput B-1input 1B塊內(nèi)存緩

51、沖區(qū)H基于Hasing的投影方法重復(fù)數(shù)據(jù)刪除階段將每個分區(qū)的數(shù)據(jù)逐條讀入內(nèi)存，利用Hash函數(shù)H2在內(nèi)存中進(jìn)行分區(qū)，并刪除重復(fù)數(shù)據(jù)將內(nèi)存中的數(shù)據(jù)寫入硬盤中，將內(nèi)存緩沖區(qū)進(jìn)行清理，準(zhǔn)備下一分區(qū)的處理代價分析如果內(nèi)存足夠大，即第二階段全部在內(nèi)存中處理。第一階段的代價為M+T第二階段的代價為T總的代價為M+2T,對前面的例子，代價為1000+2*250 =1500兩種方法的比較基于排序的方法總體性能比較好產(chǎn)生的結(jié)果是排好序的特別適于內(nèi)存比較小和數(shù)據(jù)分布不均勻的情況一般排序和重復(fù)元組刪除兩部分是分開的基于Hashing的方法當(dāng)BT1/2的時候兩者性能相差不大投影操作利用索引進(jìn)行投影操作如果相應(yīng)的數(shù)據(jù)項

52、對應(yīng)索引結(jié)構(gòu)，則可直接在索引結(jié)構(gòu)上進(jìn)行操作，不需要訪問文件中的數(shù)據(jù)由于在索引中數(shù)據(jù)是排序的，所以很容易去除冗余數(shù)據(jù)實際系統(tǒng)中的投影操作Oracle 、DB2、Sybase ASE用排序的方法Informix用基于Hashing的方法 Sql Server、Sybase Asiq兩種方法都提供方法Join 操作Select *From Reserves R, Sailors SWhere R.sid=S.sidRSJoin操作相當(dāng)于一個叉乘操作加上一個選擇和投影操作，所以Join操作的結(jié)果一般比叉乘操作的結(jié)果小Join 操作Join操作的多種實現(xiàn)方法需要掃描整個表的方法嵌套循環(huán)join塊嵌套循環(huán)

53、join不需要掃描整個表的方法Sort-merge join方法Hash join方法分析實例（R join S）R中有M個頁，每頁有PR個元組S中有N個頁，每頁有PS個元組Join 操作實際系統(tǒng)中的Join操作Oracle 8支持基于頁的嵌套循環(huán)、Sort-merge、和Hash JoinSql Server支持基于頁的嵌套循環(huán)、索引嵌套循環(huán)、Sort-merge、Hash Join和Hash teamDB2支持基于塊的嵌套循環(huán)、Sort-merge、和Hash Join Sybase支持基于頁的嵌套循環(huán)、索引嵌套循環(huán)、Sort-merge、Hash Join和Join索引Informix支

54、持基于頁的嵌套循環(huán)、索引嵌套循環(huán)和Hash Join簡單嵌套循環(huán)循環(huán)JoinForeach tuple rR do Foreach tuple sS do if ri=sj then add to resultR為outer關(guān)系，S為inner關(guān)系代價分析：M+PR*M*N對前面的例子，有M=1000, PR=100，N=500,所以最后的代價為1000+5*107兩個優(yōu)化從M中每次讀一頁進(jìn)行Join,而不是一個，則代價公式為：M+M*Nouter關(guān)系選擇較小的表塊嵌套循環(huán)Join查詢Foreach Block of B-2 pages of R do Foreach Page of S do

55、 for all matching in-memory tuples r R-block and s S add to result基本思想將關(guān)系R分成長度為B-2的塊，每次調(diào)用一塊到緩沖區(qū)，遍歷S，讀入數(shù)據(jù)，并同緩沖區(qū)中的數(shù)據(jù)進(jìn)行Join這種方法可有效地減少對S的遍歷次數(shù)，如R可整個裝入緩沖區(qū)，則只需代價：M+N塊嵌套循環(huán)Join查詢?nèi)绾螌彌_區(qū)中的數(shù)據(jù)做join將R中讀入緩沖區(qū)的數(shù)據(jù)存入Hash表，對每條讀入的S中的數(shù)據(jù)通過Hash變換后找到相應(yīng)的R中的數(shù)據(jù)，從而加快了速度代價分析：M+M/(B-2) *N對前面的例子，有M=1000,N=500,緩沖區(qū)大小為100頁，最后的代價為1000

56、+10*500=6000頁對前面的例子，若緩沖區(qū)大小為90頁，最后的代價為1000+12*500=7000頁對前面的例子，若緩沖區(qū)大小為100頁，sailer為outer關(guān)系，最后的代價為500+5*1000 =5500頁圖示DiskDiskouput bufferInput bufferB塊內(nèi)存緩沖區(qū)HB-2塊Ri的Hash表Hash函數(shù)塊嵌套循環(huán)Join查詢塊訪問的影響可以增加inner關(guān)系的緩沖區(qū)的大小，這樣可以減少尋找page的時間可以考慮double Buffering 的方法索引嵌套循環(huán) JoinForeach tuple rR do Foreach tuple sS where

57、ri=sj add to result基本思想是在Inner關(guān)系的訪問上用索引，用極少的代價找到滿足條件的元組代價分析如果索引是B+樹，則找到相應(yīng)的也節(jié)點只需要2-4次讀寫，如果索引是Hash表，則找到相應(yīng)的也節(jié)點只需要1-2次讀寫如果索引是簇聚的，讀取滿足條件的元組的代價很少，否則為滿足條件的元組的個數(shù)索引嵌套循環(huán) Join對前面的例子，有M=1000, PR=100，N=500， Ps=80若在Sailer上有Hash的索引，訪問所需的頁需要1.2次讀寫，因為sid是鍵，每次只有一個結(jié)果，代價為1000+100000*1.2若在Reserves上有Hash的索引，訪問所需的頁需要1.2次讀

58、寫，假設(shè)每個sailer對應(yīng)的reserves均在一個頁中，代價為500+40000*1.2若在Reserves上有Hash索引，按平均每個sailer對應(yīng)的reserves應(yīng)為2.5個，所需的讀寫代價根據(jù)簇聚的情況不同為1-2.5,代價為500+40000*1 500+40000*2.5Sort-Merge Join基本想法首先將兩個關(guān)系進(jìn)行排序，并根據(jù)排序的結(jié)果進(jìn)行分區(qū)，每個分區(qū)在join的屬性上是相同的。用兩個指針對兩個關(guān)系分別從前向后掃描，找到相同的分區(qū)，對聯(lián)接屬性值相同的分區(qū)進(jìn)行Join操作，輸出結(jié)果算法proc smjoin(R,S,Ri=Sj)If R not sorted on

59、 attribute I,sort it;If S not sorted on attribute j,sort it;Tr=first tuple in R;Ts=first tuple in S;Gs=first tuple in S;While Treof and Gseof dowhile Tri Gsj doGs=next tuple in S after Gs;算法 Ts=Gs; While Tri= Gsj do Ts=Gs while Tsi= Gsj do addto result Ts= next tuple in S after Ts; Tr=next tuple in

60、R after Tr; Gs=Ts例子sidsnameratingage22dustin745.028Yuppy935.031Lubber855.536Lubber636.044Guppy535.058Rusty1035.0sidbiddayrname2810312/04/96Guppy2810311/03/96Yuppy3110110/10/96Dustin3110210/12/96Lubber3110110/11/96Lubber5810311/12/96DustinSailorsReservesSort-Merge Join代價分析R排序的時間是O(MlogM), S排序的時間是O(Nl