《數(shù)據(jù)庫系統(tǒng)實(shí)現(xiàn)（第2版）》內(nèi)容深入且全面，技術(shù)實(shí)用且先進(jìn)似芝，敘述深入淺出，是一本難得的高層次的教材板甘，適合作為高等院校計(jì)算機(jī)專業(yè)研究生的教材或本科生的教學(xué)參考書党瓮，也適合作為從事相關(guān)研究或開發(fā)工作的專業(yè)技術(shù)人員的高級(jí)參考資料。
　　Hector Garcia-Molina盐类，斯坦福大學(xué)計(jì)算機(jī)科學(xué)與電子工程系的Leona rd BoSack和SandraLerner教授寞奸。他在數(shù)據(jù)庫系統(tǒng)、分布式系統(tǒng)和數(shù)字圖書館領(lǐng)域中發(fā)表了大量論文傲醉，研究興趣包括分布式計(jì)算系統(tǒng)蝇闭、數(shù)據(jù)庫系統(tǒng)和數(shù)字圖書館。他是ACM會(huì)士硬毕、美國藝術(shù)與科學(xué)院會(huì)士和美國國家工程院成員呻引。他在1999年獲得了ACM SIGMOD創(chuàng)新獎(jiǎng)。
　　Jeffrey D．Ullman吐咳，斯坦福大學(xué)計(jì)算機(jī)科學(xué)與電子工程系StanfordW．Asche rman教授逻悠，數(shù)據(jù)庫技術(shù)專家。他獨(dú)立或與人合作出版了15．v．k著作韭脊，發(fā)表了170多篇技術(shù)論文戳护，研究興趣包括數(shù)據(jù)庫理論、數(shù)據(jù)庫集成腰涧、數(shù)據(jù)挖掘和利用信息基礎(chǔ)設(shè)施進(jìn)行教育葵姥。他是美國國家工程院成員，曾獲得Knuth獎(jiǎng)蔫饰、SIGMOD貢獻(xiàn)獎(jiǎng)琅豆、Karlstrom杰出教育家獎(jiǎng)DEdgar F．Codd發(fā)明獎(jiǎng)。
　　Jennifer Widom篓吁，美國康奈爾大學(xué)計(jì)算機(jī)科學(xué)博士茫因，現(xiàn)為斯坦福大學(xué)計(jì)算機(jī)科學(xué)與電子工程系教授，研究興趣包括半結(jié)構(gòu)化數(shù)據(jù)的數(shù)據(jù)庫系統(tǒng)問委員會(huì)的成員杖剪。她在2007年獲得了ACM SIGMOD Edgar F．Codd發(fā)明獎(jiǎng)冻押。

0 關(guān)鍵字含義

關(guān)系：實(shí)際上是一張二維表，表的每一行是一個(gè)元素盛嘿，每一列是一項(xiàng)屬性洛巢。
元組：指的是一個(gè)關(guān)系上屬性集的笛卡爾積的一個(gè)元素。大部分情況一下次兆，我們可以理解為表的一行數(shù)據(jù)狼渊。

0 關(guān)系代數(shù)基本概念

五種基本操作：

并（Union）：設(shè)關(guān)系R和關(guān)系S具有相同的屬性n，且相應(yīng)的屬性取自同一個(gè)域，則關(guān)系R和關(guān)系S的并由屬于R或?qū)儆赟的元組組成狈邑，其結(jié)果仍為n元的關(guān)系

差（Difference）：設(shè)關(guān)系R和關(guān)系S具有相同的屬性n城须，且相應(yīng)的屬性取自同一個(gè)域，則關(guān)系R和關(guān)系S的差由屬于關(guān)系R而不屬于關(guān)系S的元組組成米苹，其結(jié)果仍為n元的關(guān)系

笛卡爾積（Cartesian Product）：設(shè)關(guān)系R和關(guān)系S的屬性分別為r和s糕伐。定義R和S的笛卡爾積是一個(gè)(r+s)元的元組集合，每個(gè)元組的前r個(gè)分量來自R的一個(gè)元組蘸嘶，后s個(gè)分量來自S的一個(gè)元組

投影（Projection）：對(duì)關(guān)系進(jìn)行垂直分割良瞧，消去某些列，并重新安排列的順序训唱，再刪去重復(fù)元組

選擇（Selection）：根據(jù)某些條件對(duì)關(guān)系做水平分割褥蚯，即選擇符合條件的元組

四種組合操作：

交（Intersection）：設(shè)關(guān)系R和關(guān)系S具有相同的屬性n，且相應(yīng)的屬性取自同一個(gè)域况增，則關(guān)系R和關(guān)系S的交由既屬于關(guān)系R又屬于關(guān)系S的元組組成赞庶，其結(jié)果仍為n元的關(guān)系。關(guān)系的交可以由關(guān)系的差來表示澳骤。

聯(lián)接（Join）：連接操作是笛卡爾積和選擇操作的組合歧强。

自然聯(lián)接（Natural Join）：是一種特殊的等值聯(lián)接，它要求兩個(gè)關(guān)系中進(jìn)行比較的分量必須是相同的屬性組为肮，并且要在結(jié)果中把重復(fù)的屬性去掉摊册。

除（Division）：設(shè)兩個(gè)關(guān)系R和S的屬性分別為r和s(設(shè)r>s>0)，那么R除S是一個(gè)(r-s)元的元組的集合颊艳。它是滿足下列條件的最大關(guān)系：其中每個(gè)元組t與S中的每個(gè)元組u組成的新元組<t,u>必在關(guān)系R中茅特。除運(yùn)算是笛卡爾積的逆運(yùn)算。

1 DBMS系統(tǒng)概述

數(shù)據(jù)模型三要素

1. 數(shù)據(jù)結(jié)構(gòu)：描述系統(tǒng)的靜態(tài)特性

• 數(shù)據(jù)本身
• 數(shù)據(jù)之間的聯(lián)系

2. 數(shù)據(jù)操作：描述系統(tǒng)的動(dòng)態(tài)特性棋枕，對(duì)數(shù)據(jù)庫中對(duì)象的實(shí)例允許執(zhí)行的操作的集合温治，包括操作及操作規(guī)則
3. 完整性約束：完整性規(guī)則的集合，規(guī)定數(shù)據(jù)庫狀態(tài)及狀態(tài)變化所滿足的條件戒悠，保證數(shù)據(jù)庫的正確、有效舟山、相容

DBMS的主要功能

1. 持久存儲(chǔ)：支持對(duì)非常大量的數(shù)據(jù)進(jìn)行存儲(chǔ)绸狐，這些數(shù)據(jù)獨(dú)立于使用數(shù)據(jù)的任何處理程序而存在
2. 訪問接口：使得用戶可以通過強(qiáng)有力的查詢語言訪問數(shù)據(jù)和使用靈活的操作方式修改數(shù)據(jù)
3. 事務(wù)管理：支持對(duì)數(shù)據(jù)的并發(fā)存取，多個(gè)不同的事務(wù)同時(shí)對(duì)數(shù)據(jù)進(jìn)行存取并避免同時(shí)的訪問可能造成的不良后果

DBMS的運(yùn)行過程

image

1. 用戶向DBMS發(fā)出調(diào)用數(shù)據(jù)庫數(shù)據(jù)的命令
2. DBMS對(duì)命令進(jìn)行語法檢查累盗、語義檢查寒矿、存取權(quán)限檢查，決定是否要執(zhí)行該命令
3. DBMS執(zhí)行查詢優(yōu)化若债，把命令轉(zhuǎn)化為一串串記錄的存取操作序列
4. 執(zhí)行存取操作序列（反復(fù)執(zhí)行以下各步直到結(jié)束）
5. DBMS在緩沖區(qū)中查找記錄符相，找到轉(zhuǎn)10，沒找到轉(zhuǎn)6
6. DBMS查看存儲(chǔ)模式，決定從哪個(gè)文件存取哪個(gè)物理記錄
7. 根據(jù)6的結(jié)果啊终，向操作系統(tǒng)發(fā)出讀取記錄的命令
8. 操作系統(tǒng)執(zhí)行讀取數(shù)據(jù)的命令
9. 操作系統(tǒng)將數(shù)據(jù)從數(shù)據(jù)庫存儲(chǔ)區(qū)送到系統(tǒng)緩沖區(qū)
10. DBMS根據(jù)用戶命令和數(shù)據(jù)字典的內(nèi)容導(dǎo)出用戶所要讀取的數(shù)據(jù)格式
11. DBMS將數(shù)據(jù)記錄從系統(tǒng)緩沖區(qū)傳送到用戶工作區(qū)
12. DBMS將執(zhí)行狀態(tài)信息返回給用戶

2 輔助存儲(chǔ)管理

概述

1. 輔助存儲(chǔ)負(fù)責(zé)管理的數(shù)據(jù)：包括目標(biāo)數(shù)據(jù)镜豹、元數(shù)據(jù)、索引和日志等蓝牲，這些數(shù)據(jù)保存在磁盤上趟脂。
2. DBMS中改變了的數(shù)據(jù)必須寫在非易失的磁盤上，才能認(rèn)為改變的數(shù)據(jù)已成為數(shù)據(jù)庫的一部分例衍。

磁盤結(jié)構(gòu)

磁盤結(jié)構(gòu)

image

1. 圓盤-盤面-磁道-扇區(qū) 2. 磁頭不于盤面接觸昔期，而是貼近地懸浮在盤面上，否則會(huì)發(fā)生頭損毀佛玄，破壞盤片 3. 磁盤控制器的功能 + 定位磁頭到一個(gè)特定的半徑位置 + 選擇一個(gè)準(zhǔn)備讀寫的盤面硼一，從位于該盤面的磁頭下的磁道上選擇一個(gè)扇區(qū)。并識(shí)別何時(shí)該扇區(qū)正開始移動(dòng)到磁頭下面梦抢。 + 將從該扇區(qū)讀取的二進(jìn)制位傳送到主存儲(chǔ)般贼，或?qū)闹鞔嬉獙懭氲亩M(jìn)制位傳送到該扇區(qū)。 + 為所寫扇區(qū)附加校驗(yàn)和惑申，并在讀取扇區(qū)時(shí)檢查它具伍。 + 進(jìn)行壞扇區(qū)的重映射

磁盤容量

1. 磁盤容量=盤面×磁道×扇區(qū)×字節(jié)×8位
2. 一個(gè)磁道多少塊=磁道容量/扇區(qū)容量

磁盤訪問時(shí)間

1. 尋道時(shí)間：將磁頭組合定位在磁盤塊所在磁道的磁面上所需要的時(shí)間
2. 旋轉(zhuǎn)延遲（旋轉(zhuǎn)等待時(shí)間）：尋道結(jié)束后，讀寫頭到等待被存取的扇區(qū)所需要的時(shí)間
3. 傳輸時(shí)間：磁盤控制器讀取或?qū)憯?shù)據(jù)時(shí)圈驼，數(shù)據(jù)所在扇區(qū)和扇區(qū)間的空隙經(jīng)過磁頭

磁盤的延遲=尋道時(shí)間+旋轉(zhuǎn)延遲+傳輸時(shí)間

磁盤塊存取的優(yōu)化方法

1. 才主存中對(duì)塊進(jìn)行緩沖以減少塊的讀寫次數(shù)
2. 按柱面組織數(shù)據(jù)
3. 使用多個(gè)磁盤
4. 磁盤鏡像人芽、

假定一個(gè)磁盤的MTTF是100,000小時(shí)，修復(fù)時(shí)間是10小時(shí)绩脆，則鏡像磁盤系統(tǒng)的MTTF是100 , 00 0 2 100,000^2100,0002/（210）=5001 0 6 10^6106小時(shí)萤厅，約為57000年

5. 磁盤臂調(diào)度——電梯算法
6. 利用非易失性RAM作為寫緩沖
7. 預(yù)讀和雙緩沖
8. 日志磁盤

RAID：廉價(jià)磁盤冗余陣列

作用

1. 概述：利用大量廉價(jià)磁盤進(jìn)行磁盤組織的技術(shù)
2. 價(jià)格上：大量廉價(jià)的磁盤比少量昂貴的大磁盤合算
3. 性能上： 使用大量的磁盤可以提高數(shù)據(jù)的并行存取
4. 可靠性上： 冗余數(shù)據(jù)可以放在多個(gè)磁盤上，因而一個(gè)磁盤的故障不會(huì)導(dǎo)致數(shù)據(jù)丟失
5. 通過冗余提高可靠性
6. 通過并行提高性能
7. 通過在多個(gè)磁盤上對(duì)數(shù)據(jù)進(jìn)行拆分來提高傳輸率

分類與優(yōu)缺點(diǎn)

RAIDO

1. 將多個(gè)磁盤并列起來成為一個(gè)大磁盤
2. 優(yōu)點(diǎn)：

• 速度最快
• 塊級(jí)拆分且沒有任何冗余

3. 缺點(diǎn)：如果一個(gè)磁盤損壞所有的數(shù)據(jù)都會(huì)丟失
4. 應(yīng)用：用于高性能訪問并且數(shù)據(jù)丟失不十分重要的應(yīng)用場合

RAID1

1. 帶塊級(jí)拆分的磁盤鏡像
2. 優(yōu)點(diǎn)：

• 讀性能好（是RAID0性能的兩倍）
• 寫性能是由寫性能最差的磁盤決定（但是對(duì)比以后的RAID來說寫的速度還是較快的）
• 可靠性很高

3. 缺點(diǎn)：物理磁盤空間是邏輯磁盤空間的兩倍
4. 應(yīng)用：用于類似于數(shù)據(jù)庫系統(tǒng)中日志文件存儲(chǔ)的應(yīng)用場合

RAID2

1. 按比特級(jí)拆分靴迫，具有內(nèi)存風(fēng)格的糾錯(cuò)碼（ECC）
2. 未被廣泛應(yīng)用惕味，目前沒有商業(yè)化產(chǎn)品
3. 糾錯(cuò)碼：內(nèi)存中每個(gè)字節(jié)都有一個(gè)奇偶校驗(yàn)位與之相連，它記錄這個(gè)字節(jié)中為1的比特位的總數(shù)是偶數(shù)（=0）還是奇數(shù)（=1）玉锌，如果字節(jié)中有一位被破壞名挥，則字節(jié)的ECC與存儲(chǔ)的ECC就不會(huì)相匹配；通過ECC可以檢測到所有的1位錯(cuò)誤主守；通過更多的附加位禀倔，當(dāng)數(shù)據(jù)遭到破壞時(shí)，還可以重建數(shù)據(jù)

RAID3

1. 能夠檢測出一個(gè)扇區(qū)是否被正確的讀出
2. 優(yōu)點(diǎn)

• 效果與RAID2一樣参淫，但是只有一個(gè)磁盤的額外開銷

3. 缺點(diǎn)：

• 恢復(fù)時(shí)間長
• 每個(gè)磁盤參與每個(gè)IO請(qǐng)求救湖，每秒RAID3支持的IO數(shù)較少

RAID4

1. 特點(diǎn)：塊級(jí)拆分，在一個(gè)獨(dú)立的磁盤上為其他N個(gè)磁盤上對(duì)應(yīng)的塊保留一個(gè)奇偶校驗(yàn)位
2. 優(yōu)點(diǎn)：

• 讀取一個(gè)塊只需要訪問一個(gè)磁盤涎才，RAID3需要訪問所有的盤
• 所有的磁盤都可以并行地讀鞋既，讀取大量數(shù)據(jù)的操作有很高的傳輸率

3. 缺點(diǎn)：

• 每個(gè)存取操作的傳輸率低，可以并行地執(zhí)行多個(gè)讀操作，因此產(chǎn)生較高的總的IO率

假定有4個(gè)數(shù)據(jù)盤和一個(gè)冗余盤
讀數(shù)據(jù)：RAID3需要5次磁盤讀操作邑闺；RAID4與從任何一個(gè)cip
寫數(shù)據(jù)：RAID3需要3次磁盤讀和兩次磁盤寫操作RAID4寫數(shù)據(jù)需要兩次磁盤讀和兩次磁盤寫操作

RAID5（塊交叉的分布奇偶校驗(yàn)）

1. 將數(shù)據(jù)和奇偶效驗(yàn)位第一分不到所有的N+1磁盤上跌前，對(duì)每個(gè)塊一個(gè)磁盤存儲(chǔ)奇偶校驗(yàn)位其余磁盤存儲(chǔ)數(shù)據(jù)
2. 奇偶校驗(yàn)塊不能和這個(gè)塊對(duì)應(yīng)的數(shù)據(jù)存儲(chǔ)在同一個(gè)磁盤上
3. 優(yōu)點(diǎn)：

• 包含了RAID4
• 在相同的成本上，RAID5提供了更好的讀寫性能

image

RAID6

1. 類似RAID5检吆，存儲(chǔ)了額外的冗余信息
2. 不使用奇偶校驗(yàn)位的方法舒萎，使用Reed-Solomon碼，對(duì)每4位數(shù)據(jù)存儲(chǔ)兩位冗余信息
3. 優(yōu)點(diǎn)：

• 可以容忍兩個(gè)磁盤發(fā)生故障（高可靠性）

image

RAID分別使用的技術(shù)

1. RAID 0級(jí)：塊級(jí)拆分蹭沛，無冗余
2. RAID 1級(jí)：帶塊級(jí)拆分的磁盤鏡像
3. RAID 2級(jí)：內(nèi)存風(fēng)格的糾錯(cuò)碼組織結(jié)構(gòu)
4. RAID 3級(jí)：位交叉的奇偶校驗(yàn)組織結(jié)構(gòu)
5. RAID 4級(jí)：塊交叉的奇偶校驗(yàn)組織結(jié)構(gòu)
6. RAID 5級(jí)：塊交叉的分布奇偶校驗(yàn)位的組織結(jié)構(gòu)
7. RAID 6級(jí)：P+Q冗余方案

選擇RAID級(jí)別應(yīng)該考慮的因素

1. 所需的額外磁盤存儲(chǔ)帶來的開銷
2. 在IO操作數(shù)量方面的性能需求
3. 磁盤故障時(shí)的性能
4. 數(shù)據(jù)重建過程中的性能

緩沖區(qū)

1. 概述：主存中用于存儲(chǔ)磁盤塊的拷貝的部分臂寝，由固定數(shù)目的緩沖塊構(gòu)成
2. 目的：減少磁盤與主存之間傳輸?shù)目斓臄?shù)目
3. 緩沖區(qū)管理器：負(fù)責(zé)緩沖區(qū)空間分配的子系統(tǒng)

緩沖區(qū)管理工作流程

image

1. 請(qǐng)求處理的流程

• 查看buffer pool是否包含此頁，沒有的則：
  • 找到一個(gè)pin_count（正在訪問該ｆｒａｍｅ的事務(wù)的個(gè)數(shù)）為０的frame,pin_count＋＋
  • 如果dirty為true,寫入磁盤
  • 將相應(yīng)的頁讀入此frame
• 將frame的地址返回

存儲(chǔ)組織

1. 頁的格式：

• 頁是由一系列的記錄構(gòu)成的摊灭，每個(gè)記錄為一個(gè)slot
• 記錄的id為=（page id咆贬， slot number）
• 映射表：邏輯地址、物理地址

2. 定長記錄

• 每條記錄的長度是固定的帚呼，沒有變長字段掏缎，一個(gè)頁存放的數(shù)量和位置也是確定的

3. 變長記錄

• 記錄中包含變長字段，記錄的長度是可變的煤杀，無法分配定長的slot
• 用slot字典存放記錄的起始位置和記錄的長度眷蜈，用記錄在slot字典中的位置代替slot的實(shí)際起始位置

文件中記錄的組織

堆文件組織

1. 概述：一條記錄可以存放在文件中的任何地方，只要有空間存放這條記錄沈自，記錄是無序的酌儒，通常一個(gè)關(guān)系是一個(gè)單獨(dú)的文件

順序文件組織

1. 記錄根據(jù)搜索碼的值順序存儲(chǔ)
2. 大量插刪改后需要重組：當(dāng)進(jìn)行大量的插刪改后，搜索碼順序和物理順序之間的一致性最終將完全喪失枯途，在這種情況下忌怎，順序處理將變得效率十分低下，此時(shí)文件應(yīng)該被重組酪夷，使得他在物理上順序存放榴啸，這種重組的代價(jià)是很高，而且必須在系統(tǒng)負(fù)載很低的時(shí)候執(zhí)行晚岭。需要重組的頻率依賴于新記錄插入的頻率

散列文件組織

1. 在每條記錄的某些屬性上計(jì)算一個(gè)散列函數(shù)鸥印，散列函數(shù)的結(jié)果確定了記錄應(yīng)該放到文件的哪個(gè)快中

聚簇文件組織

1. 幾個(gè)不同關(guān)系的記錄存儲(chǔ)在同一文件中（通常用一個(gè)文件存儲(chǔ)一個(gè)關(guān)系的記錄），甚至用不同關(guān)系中的相關(guān)記錄存儲(chǔ)在相同的塊中坦报，于是一個(gè)IO操作可以從多個(gè)關(guān)系中取到相關(guān)記錄

4 查詢執(zhí)行

SQL是關(guān)系模型操作的高層次抽象库说，所以SQL可以轉(zhuǎn)化為一系列關(guān)系代數(shù)操作。執(zhí)行關(guān)系代數(shù)操作的基本方法有掃描燎竖、散列、排序要销、索引等构回，這些方法對(duì)內(nèi)存容量所做的假設(shè)也有所不同，一些算法假設(shè)內(nèi)存可以容納參與關(guān)系代數(shù)操作的數(shù)據(jù)對(duì)象，另外一些算法假設(shè)操作對(duì)象太大纤掸，內(nèi)存無法容納脐供。這些算法在代價(jià)和結(jié)構(gòu)上有明顯的差別。

4.0 查詢編譯預(yù)覽

查詢編譯可以分為三大步驟：

a) 分析借跪，建立查詢的分析樹政己。
b) 查詢重寫，分析樹被轉(zhuǎn)化為初始查詢計(jì)劃掏愁，這種查詢計(jì)劃通常是查詢的代數(shù)表達(dá)式歇由。然后初始查詢計(jì)劃被轉(zhuǎn)化為一個(gè)預(yù)期所需執(zhí)行時(shí)間較小的等價(jià)查詢計(jì)劃，也被成為邏輯查詢計(jì)劃果港。
c) 物理計(jì)劃生成沦泌，通常是通過給b中產(chǎn)出的邏輯查詢計(jì)劃的每一個(gè)操作符選擇實(shí)現(xiàn)算法并選擇這些操作符的執(zhí)行順序，邏輯計(jì)劃被轉(zhuǎn)化為物理查詢計(jì)劃辛掠。物理查詢計(jì)劃也是用表達(dá)式樹來表示谢谦，同時(shí)還包含很多細(xì)節(jié)，如被查詢的關(guān)系是怎樣被訪問的萝衩，以及一個(gè)關(guān)系何時(shí)或是否應(yīng)該被排序回挽。

b和c部分通常被稱作查詢優(yōu)化器，它們是查詢編譯的難點(diǎn)猩谊。為了選擇最好的查詢計(jì)劃千劈，我們需要判斷：

1. 查詢的哪一個(gè)代數(shù)等價(jià)形式會(huì)為查詢帶來最有效的算法。
2. 對(duì)選中形式的每一個(gè)操作预柒，應(yīng)當(dāng)使用什么算法實(shí)現(xiàn)队塘。
3. 數(shù)據(jù)如何從一個(gè)操作傳到另一個(gè)操作。

這些選擇都依賴關(guān)于數(shù)據(jù)庫的元數(shù)據(jù)宜鸯。

4.1 物理查詢計(jì)劃操作符介紹

物理查詢計(jì)劃由操作符構(gòu)成憔古，每一個(gè)操作符實(shí)現(xiàn)物理查詢計(jì)劃中的一步。物理操作符常常是一個(gè)關(guān)系代數(shù)操作的特定實(shí)現(xiàn)淋袖，除此之外鸿市，也有一些無關(guān)任務(wù)，例如掃描表即碗，將關(guān)系代數(shù)要操作的某個(gè)關(guān)系的每個(gè)元組調(diào)入內(nèi)存焰情。

4.1.1 掃描表

讀取一個(gè)關(guān)系R的整個(gè)內(nèi)容，這個(gè)操作符的一個(gè)變體包含一個(gè)簡單的謂詞(僅讀出關(guān)系R中滿足這個(gè)謂詞的元組)剥懒。

定位關(guān)系R中元組的基本方法

1. 表-掃描内舟，關(guān)系R大部分情況是存放在硬盤中，關(guān)系R中的元組排列存放在硬盤塊中初橘。系統(tǒng)知道包含關(guān)系R元組的塊是哪些验游，并且可以一個(gè)接一個(gè)地讀取這些塊充岛。
2. 索引-掃描，如果關(guān)系R的任意屬性上有索引耕蝉，那么我們可以通過索引來得到R的所有元組崔梗，即使元組存放的塊不是連續(xù)的。

4.1.2 掃描表時(shí)的排序

在讀取一個(gè)關(guān)系的元組時(shí)垒在，很多情況需要將關(guān)系排序蒜魄。SQL中有 ORDER BY 語句會(huì)要求對(duì)關(guān)系排序，另外還有數(shù)據(jù)庫關(guān)系代數(shù)操作的具體算法上也需要對(duì)關(guān)系進(jìn)行排序(后面會(huì)講到)场躯。

排序-掃描的具體實(shí)現(xiàn)有多種方法谈为，例如想產(chǎn)生關(guān)系R上按屬性a排序的關(guān)系，假設(shè)a上有B-數(shù)索引或者R是按a排序的索引屬性存儲(chǔ)的推盛，那么用索引掃描即可峦阁。假設(shè)關(guān)系R很小，則可以用表掃描耘成，然后在內(nèi)存中排序榔昔。假設(shè)關(guān)系R很大，那么后邊會(huì)講到用多路歸并方法排序瘪菌。

4.1.3 物理操作符計(jì)算模型

一個(gè)查詢通常包括好幾個(gè)關(guān)系代數(shù)操作撒会，相應(yīng)的物理查詢計(jì)劃由幾個(gè)物理計(jì)劃操作符組成。挑選最優(yōu)的物理計(jì)劃操作符需要預(yù)估每個(gè)操作符的代價(jià)师妙。磁盤IO的數(shù)目是數(shù)據(jù)庫衡量物理計(jì)劃操作符代價(jià)的標(biāo)準(zhǔn)诵肛，這里有兩個(gè)假設(shè)，第一操作符的對(duì)象位于硬盤默穴、但結(jié)果在內(nèi)存中怔檩，第二一個(gè)查詢的中間操作結(jié)果也應(yīng)該在內(nèi)存中。

4.1.4 衡量代價(jià)的參數(shù)

我們?cè)O(shè)定蓄诽，內(nèi)存的一個(gè)緩沖區(qū)大小和硬盤塊大小一致薛训，我們用M表示緩沖區(qū)的數(shù)目。

當(dāng)描述一個(gè)關(guān)系R的大小時(shí)仑氛，絕大部分情況下乙埃，我們想知道的是關(guān)系R的所有元組所需要的硬盤塊的數(shù)目。我們用B(R)B(R)表示聚集的關(guān)系R所占用的硬盤塊數(shù)锯岖，簡記為BB介袜。

我們用T(R)T(R)表示關(guān)系R的元組總數(shù)，簡記為TT出吹，一個(gè)硬盤塊能容納的元組數(shù)表示為T/BT/B遇伞。

我們用V(R,a)V(R,a)表示關(guān)系R中a屬性的不同值數(shù)目，以此可推捶牢，V(R,a1,a2…an)=T(R)V(R,a1,a2…an)=T(R)鸠珠。

4.1.5 掃描操作符的IO代價(jià)

假設(shè)關(guān)系R是聚集的加派，那么表掃描操作符的代價(jià)近似為B，如果關(guān)系R能夠全部裝進(jìn)內(nèi)存跳芳，那排序掃描的代價(jià)也是B。

如果關(guān)系R不是聚集的竹勉，即元組分散在不同的硬盤塊中飞盆，那么表掃描的代價(jià)就是T，如果關(guān)系R能夠全部裝進(jìn)內(nèi)存次乓，那排序掃描的代價(jià)也是T吓歇。

4.1.6 實(shí)現(xiàn)物理操作符的迭代器

許多物理操作符可以實(shí)現(xiàn)為迭代器。迭代器有三個(gè)方法票腰，這三個(gè)方法允許使用者一次獲得一個(gè)元組城看。

1. Open()，這個(gè)方法啟動(dòng)獲取元組的過程杏慰，但并不獲取元組测柠，它用于初始化。
2. GetNext()缘滥，這個(gè)方法返回結(jié)果中的下一個(gè)元組轰胁，并對(duì)數(shù)據(jù)結(jié)構(gòu)做必要的調(diào)整以得到后續(xù)元組。調(diào)用對(duì)象通常循環(huán)調(diào)用該方法獲取元組直到返回空朝扼。
3. Close()赃阀，當(dāng)使用者獲取到所有元組，則需要調(diào)用該方法關(guān)閉數(shù)據(jù)連接擎颖。

使用迭代器的好處：同一時(shí)刻活躍的操作有很多榛斯，元組按照需要在操作符之間傳遞，這樣就減少了存儲(chǔ)要求搂捧。

表掃描的迭代器實(shí)現(xiàn)驮俗，在open方法中獲取第一個(gè)塊的第一個(gè)元組，在next方法中判斷加載下一個(gè)塊和元組异旧。

排序掃描的迭代器實(shí)現(xiàn)意述，在open方法中讀取整個(gè)關(guān)系R，然后排序吮蛹，在next方法中順序讀取荤崇。

并操作的迭代器實(shí)現(xiàn)，在open方法中先調(diào)用第一個(gè)關(guān)系的迭代器潮针，在next方法中判斷第一個(gè)關(guān)系是否結(jié)束术荤，如果結(jié)束就打開第二個(gè)關(guān)系的迭代器。

4.2 一趟算法

如何執(zhí)行邏輯查詢計(jì)劃中的每個(gè)單獨(dú)步驟(例如連接或選擇)每篷？邏輯查詢計(jì)劃轉(zhuǎn)為物理查詢計(jì)劃的一個(gè)部分就是選擇算法瓣戚。大體上分為三類：

1. 基于排序的方法
2. 基于散列的方法
3. 基于索引的方法

按照算法難度和代價(jià)分為三個(gè)等級(jí)：

1. 一趟算法端圈，僅從硬盤讀取一次數(shù)據(jù)，大部分應(yīng)用于操作對(duì)象能完全放入內(nèi)存子库。
2. 兩趟算法舱权，數(shù)據(jù)量太大，不能一次全部讀入內(nèi)存仑嗅，但又不是特別大(后面會(huì)討論什么是特別大)宴倍。算法特點(diǎn)是首先從硬盤讀取一遍數(shù)據(jù)，按照某種方式處理完后再寫入硬盤仓技，之后在第二趟中讀取數(shù)據(jù)進(jìn)一步處理鸵贬。
3. 多趟算法，對(duì)處理的數(shù)據(jù)量大小沒有限制脖捻，是對(duì)兩趟算法的遞歸推廣阔逼。

操作符的分類：

1. 一次單個(gè)元組，一元操作地沮。這類操作（選擇σσ和投影ππ）不需要一次在內(nèi)存中裝入整個(gè)關(guān)系嗜浮，這樣可以一次讀一個(gè)。
2. 整個(gè)關(guān)系摩疑，一元操作周伦。這些單操作對(duì)象需要一次從內(nèi)存中看到全部元組。一趟算法局限于最大M個(gè)緩沖區(qū)的關(guān)系讀取未荒，一般是分組操作符γγ和去重操作符δδ专挪。
3. 整個(gè)關(guān)系，二元操作片排。交∩∩寨腔、并∪∪、差??率寡，連接和積的集合形式和包形式迫卢。要求這類操作的一個(gè)關(guān)系操作對(duì)象大小限制在M以內(nèi)。

4.2.1 一次單個(gè)元組的一趟算法

非常簡單冶共，如果關(guān)系R是聚集的乾蛤，那么IO代價(jià)是B。如果是非聚集的捅僵，代價(jià)是T家卖。

有一個(gè)例外，帶有在索引上屬性和常量比較的選擇掃描庙楚，效率會(huì)顯著提高上荡，

在open方法中非阻塞

4.2.2 整個(gè)關(guān)系的一元操作的一趟算法

消除重復(fù)

一次讀取一個(gè)塊，但對(duì)于每個(gè)元組要進(jìn)行判斷：

1. 是第一個(gè)出現(xiàn)的元組馒闷，復(fù)制到緩沖區(qū)并輸出酪捡。
2. 以前見過叁征，不用輸出。

要求：B(δ(R))<=MB(δ(R))<=M

在open方法中非阻塞

分組

在內(nèi)存中為分組創(chuàng)建一個(gè)項(xiàng)逛薇，在項(xiàng)中存有分組的屬性值和聚集的一個(gè)或者多個(gè)累計(jì)值捺疼。

• 對(duì)于MIN或MAX，只需要存一個(gè)最小值或最大值永罚。
• 對(duì)于COUNT帅涂，項(xiàng)內(nèi)每見到一個(gè)元組加一。
• 對(duì)于SUM尤蛮，如果項(xiàng)內(nèi)見到的被sum值不為NULL，則累加被sum值斯议。
• AVG情況復(fù)雜产捞，需要保持兩個(gè)累計(jì)值，個(gè)數(shù)和和哼御。

這里需要注意坯临，在open方法中，所有元組掃描完成后才能結(jié)束恋昼。

在open方法中阻塞

4.2.3 二元操作的一趟算法

交看靠、并、差液肌、積和連接操作挟炬。為了操作集合操作和包操作，這里用B和S分別表示包和集合嗦哆。為了簡化連接的討論谤祖，僅考慮自然連接，θθ連接可以被認(rèn)為是積或自然連接后額外增加的條件老速。

包并

包的并可以通過一種非常簡單的一趟算法計(jì)算出來粥喜。R∪BSR∪BS，先復(fù)制關(guān)系R的元組到內(nèi)存橘券，再復(fù)制關(guān)系S的每一個(gè)元組到內(nèi)存额湘。IO代價(jià)為B(R)+B(S)B(R)+B(S)，M=1M=1就夠用旁舰。

在open方法中非阻塞

其他操作則需要將R和S中較小數(shù)量的關(guān)系讀到內(nèi)存并建立合適的數(shù)據(jù)結(jié)構(gòu)锋华。其內(nèi)存要求是min(B(R),B(S))<=Mmin(B(R),B(S))<=M，以下我們假設(shè)S關(guān)系數(shù)據(jù)量最小箭窜。

集合并

將S讀入內(nèi)存供置，生成查找結(jié)構(gòu)，Key為整個(gè)元組。然后一個(gè)一個(gè)地讀取R的元組t僻族，假如元組t在S中，就跳過烤黍，否則就輸出续担。最后輸出S的元組擅耽。

在open方法中非阻塞

集合交

將S讀入內(nèi)存，生成查找結(jié)構(gòu)物遇，Key為整個(gè)元組乖仇。然后一個(gè)一個(gè)地讀取R的元組t，假如元組t在S中询兴，就輸出乃沙，否則就跳過。

在open方法中非阻塞

集合差

R?SSR?SS：將S讀入內(nèi)存诗舰，生成查找結(jié)構(gòu)警儒，Key為整個(gè)元組。然后一個(gè)一個(gè)地讀取R的元組t眶根，假如元組t在S中蜀铲，就跳過，否則輸出属百。

S?SRS?SR：將S讀入內(nèi)存记劝，生成查找結(jié)構(gòu)，Key為整個(gè)元組族扰。然后一個(gè)一個(gè)地讀取R的元組t厌丑，假如元組t在S中，那么刪除內(nèi)存中的元組t渔呵。處理完R的所有元組后蹄衷，輸出內(nèi)存中剩余的元組。

在open方法中阻塞

包交

存儲(chǔ)S的元組和元組出現(xiàn)的次數(shù)計(jì)數(shù)厘肮，注意愧口，相同元組只存一份，計(jì)數(shù)加一类茂。然后一個(gè)一個(gè)地讀取R的元組t耍属，假如元組t在S中，且計(jì)數(shù)不為0巩检，則輸出t并將計(jì)數(shù)減一厚骗。

在open方法中非阻塞

包差

S?BRS?BR：存儲(chǔ)S的元組和元組出現(xiàn)的次數(shù)計(jì)數(shù)，注意兢哭，相同元組只存一份领舰，計(jì)數(shù)加一。然后一個(gè)一個(gè)地讀取R的元組t，假如元組t在S中冲秽，且計(jì)數(shù)不為0舍咖，則將計(jì)數(shù)減一。最后輸出內(nèi)存中剩余元組锉桑，輸出次數(shù)為計(jì)數(shù)值排霉。

R?BSR?BS：存儲(chǔ)S的元組和元組出現(xiàn)的次數(shù)計(jì)數(shù)，注意民轴，相同元組只存一份攻柠，計(jì)數(shù)加一。然后一個(gè)一個(gè)地讀取R的元組t后裸，假如元組t在S中瑰钮，且計(jì)數(shù)不為0，則將計(jì)數(shù)減一微驶，如果元組t不在S中或在S中且計(jì)數(shù)為0浪谴，則輸出。

在open方法中阻塞

積

將S讀入內(nèi)存祈搜，不需要特殊結(jié)構(gòu)。然后一個(gè)一個(gè)地讀取R的元組t士八，與S的每一個(gè)元組連接并輸出容燕。

在open方法中非阻塞

自然連接

R(X,Y)R(X,Y)和S(Y,Z)S(Y,Z)自然連接，YY表示RR和SS的所有公共屬性婚度。

1. 讀取S的所有元組蘸秘，并生成以Y為查找關(guān)鍵字的內(nèi)存結(jié)構(gòu)。
2. 然后一個(gè)一個(gè)地讀取R的元組t蝗茁，判斷t是否可以與S的元組連接醋虏，如果可以就連接輸出。

在open方法中非阻塞

4.3 嵌套循環(huán)連接

在討論更復(fù)雜的方法之前哮翘，先來看看嵌套循環(huán)連接操作算法颈嚼。這些算法某種意義上來說需要一趟半。因?yàn)閮蓚€(gè)操作對(duì)象中的一個(gè)對(duì)象元組只用讀取一次饭寺，而另一個(gè)操作對(duì)象的元組需要重復(fù)讀取阻课。

嵌套循環(huán)連接可以用于任何大小的關(guān)系。

在一趟算法的積和自然連接中艰匙，要求一個(gè)關(guān)系可以完全讀入內(nèi)存限煞。而實(shí)際上，我們每個(gè)關(guān)系只讀入一個(gè)元組员凝，或者一塊署驻。

如果按塊讀取，那么塊少的關(guān)系應(yīng)該在循環(huán)外側(cè)。例如B(R)=1000B(R)=1000旺上，B(S)=500B(S)=500瓶蚂，M=100M=100，先循環(huán)關(guān)系R抚官、再循環(huán)關(guān)系S所需讀取塊數(shù)為：10次外循環(huán)乘100+10次外循環(huán)乘5次內(nèi)循環(huán)乘100=6000扬跋，先循環(huán)關(guān)系S、再循環(huán)關(guān)系R所需讀取塊數(shù)為：5次外循環(huán)乘100+5次外循環(huán)乘10次內(nèi)循環(huán)乘100=5500凌节。

4.4 基于排序的兩趟算法

4.4.1 兩階段多路歸并排序

假設(shè)我們有M個(gè)內(nèi)存緩沖區(qū)進(jìn)行排序钦听，可以通過兩趟的算法對(duì)非常大的關(guān)系進(jìn)行排序，這種算法叫做兩階段多路歸并排序(Two-Phase, Multiway Merge-Sort, TPMMS)倍奢。

• 階段1：不斷地將關(guān)系R中的元組放入M個(gè)緩沖區(qū)朴上，利用內(nèi)存排序算法對(duì)他們排序，并且將排序后的子表存入硬盤卒煞。
• 階段2：將排序好的子表進(jìn)行歸并痪宰。在這個(gè)階段中，最多能對(duì)M-1個(gè)有序子表進(jìn)行歸并畔裕，這就限制了R的大小衣撬。

歸并流程如下：

1. 加載每個(gè)子表的第一塊做緩沖塊。
2. 找到所有塊中最小的元素移到輸出緩沖區(qū)(只有一塊)扮饶。
3. 如果輸出塊已滿具练，則將它寫入硬盤新位置，并歸零輸出塊甜无。
4. 如果被取出的最小元素所在塊元素已耗盡扛点，則取對(duì)應(yīng)子表的下一塊，如果子表中沒有塊岂丘，則保持該緩沖區(qū)為空陵究。
5. 調(diào)至第二步，直到所有緩沖區(qū)為空奥帘。

根據(jù)階段1和階段2可知铜邮，最多有M-1個(gè)子表，每個(gè)子表最多有M個(gè)塊寨蹋，所以關(guān)系R最多有(M?1)?M(M?1)?M個(gè)塊牲距，近似表示為M2M2。在整個(gè)過程中钥庇，需要讀關(guān)系2兩次牍鞠，寫關(guān)系1次。共計(jì)IO次數(shù)為3B评姨。

例子：假設(shè)塊大小為16KB难述，內(nèi)存為1GB萤晴，那么M=1GB/16KB=16K，B最大為16K?16K=22816K?16K=228胁后，總大小為4TB店读。

4.4.2 利用排序去重

在階段2的歸并流程2中，找到所有塊中的最小元素并移到輸出緩沖區(qū)攀芯，在這個(gè)操作上屯断，先檢查輸出緩沖區(qū)是否有相同元組，如果有就忽略侣诺。

4.4.3 利用排序進(jìn)行分組和聚集

在階段1中殖演，取分組屬性作為排序關(guān)鍵字。在階段2的歸并流程2中年鸳，先判斷是否有分組屬性值相同的元組趴久，有就做聚集操作，沒有就直接輸出搔确。

4.4.4 基于排序的并算法

包并(4.2.3)算法與操作對(duì)象無關(guān)彼棍，但集合并算法與操作對(duì)象大小有關(guān)系。

在階段1中膳算，對(duì)關(guān)系R和S分別創(chuàng)建排序子表座硕。在階段2歸并流程1中，為關(guān)系R和S的每個(gè)子表都使用緩沖區(qū)涕蜂。在流程2中华匾，在把元組t輸入輸出緩沖區(qū)后，刪除輸入緩沖區(qū)中和元組t相同的元組宇葱。

4.4.5 基于排序的交和差算法

算法和4.4.4節(jié)類似

• 對(duì)于集合交：如果元組t在R和S中都出現(xiàn)瘦真，就輸出t刊头。
• 對(duì)于包交：輸出的t的次數(shù)是在R和S中出現(xiàn)的最小次數(shù)黍瞧。
• 對(duì)于集合差：關(guān)系R集合減S，當(dāng)且僅當(dāng)t出現(xiàn)在R中原杂，但不在S中印颤，就輸出t。
• 對(duì)于包差：關(guān)系R包減S穿肄，輸出t的次數(shù)是t在R中出現(xiàn)的次數(shù)減去在S中出現(xiàn)的次數(shù)年局。

4.4.6 基于排序的一個(gè)簡單連接算法

R(X,Y)和S(Y,Z)自然連接，Y表示R和S的所有公共屬性咸产。

1. 用Y作為排序關(guān)鍵字矢否，使用TPMMS對(duì)R進(jìn)行排序。

2. 對(duì)S也做排序脑溢。

3. 對(duì)歸并好的R和S僵朗，使用兩個(gè)緩沖區(qū)。一個(gè)給R的當(dāng)前塊，一個(gè)給S的當(dāng)前塊验庙。重復(fù)以下步驟：

4. 在當(dāng)前R和S的塊找到Y(jié)的最小值y顶吮。

5. 如果y在另一個(gè)關(guān)系中沒有出現(xiàn)，那么就刪除有關(guān)鍵字y的元組粪薛。

6. 否則悴了，找到兩個(gè)關(guān)系中具有相關(guān)關(guān)鍵字y的所有元組。

7. 輸出通過連接R和S中具有共同y值的元組連接违寿。

8. 如果一個(gè)關(guān)系在內(nèi)存中已沒有要考慮的元組湃交，就加載下一個(gè)元組。

• 磁盤IO代價(jià)：5(B(R)+B(S))5(B(R)+B(S))
• B(R)<=M∪B(S)<=MB(R)<=M∪B(S)<=M
• 所有用于連接的一個(gè)值的對(duì)應(yīng)所有元組必須能裝入緩沖區(qū)

4.4.8 一種更有效的基于排序的連接

如果擁有公共值的元組太多陨界，4.4.6算法就不可行巡揍。那么可以在排序的第二階段和連接做合并。

1. 用Y做關(guān)鍵字菌瘪，對(duì)R和S生成排序子表
2. 將每個(gè)子表的第一塊調(diào)入緩沖區(qū)腮敌。
3. 重復(fù)地在所有子表的最新元組中第一個(gè)查找最小值y。識(shí)別兩個(gè)關(guān)系中具有y值的所有元組俏扩。輸出這些元組的連接糜工。如果有一個(gè)子表的緩沖區(qū)處理完畢，則重新將磁盤上的塊裝入其中录淡。

4.5 基于散列的兩趟算法

思想如下捌木，如果數(shù)據(jù)量太大不能存儲(chǔ)內(nèi)存，就使用一個(gè)合適的散列關(guān)鍵字散列一個(gè)或多個(gè)操作對(duì)象的所有元組嫉戚。使用該算法刨裆，能使我們把所有需要一起考慮的元組分配到相同的桶。

消除重復(fù)彬檀、分組和聚集帆啃、交并差、連接

4.6 基于索引的算法

非聚簇的關(guān)系不可能有一個(gè)聚簇的索引窍帝，但聚簇的關(guān)系可以有非聚簇的索引努潘。

基于索引的選擇。在沒有索引的情況下磁盤IO為B或T坤学。如果選擇的屬性在索引上疯坤，那么磁盤IO為B(R)/V(R,a)B(R)/V(R,a)。

使用索引的連接深浮。磁盤IO最差情況為為T(R)T(S)/V(S,Y)T(R)T(S)/V(S,Y)压怠、最好情況為T(R)B(S)/V(S,Y)T(R)B(S)/V(S,Y)

4.7 緩沖區(qū)管理

緩沖區(qū)管理策略

最近最少使用(LRU)

清空最長時(shí)間沒有讀寫的塊，這種方法要求保持一張緩沖區(qū)塊的被訪問最后一次時(shí)間的表飞苇。

先進(jìn)先出(FIFO)

占用時(shí)間最長的塊先被清空菌瘫。B-數(shù)的根更容易被寫回硬盤洋闽。

時(shí)鐘算法(第二次機(jī)會(huì))

該算法是LRU的最普遍的一個(gè)近似實(shí)現(xiàn)。實(shí)現(xiàn)方法是將緩沖區(qū)塊看成一個(gè)環(huán)突梦，每個(gè)塊有一個(gè)標(biāo)記(0或1诫舅，初始值為0)，指針指向其中一個(gè)塊宫患。如果想讀寫某一個(gè)塊刊懈，就把這個(gè)塊的標(biāo)志置為1。如果想找到一個(gè)可用的塊娃闲，就順時(shí)針旋轉(zhuǎn)虚汛，找到第一個(gè)0，然后將其設(shè)置成1皇帮，在找的過程中掃過的塊如果標(biāo)志位1就將其標(biāo)志設(shè)置成0卷哩。

4.8 使用超過兩趟的算法

略

5 查詢編譯器

5.1 語法分析和預(yù)處理

5.1.1 語法分析和語法分析樹

語法分析器接收類似SQL的文本，并轉(zhuǎn)換為語法分析樹属拾。樹的節(jié)點(diǎn)由以下兩者構(gòu)成：

1. 原子：詞法成分将谊，例如關(guān)鍵字(select)，關(guān)系或?qū)傩缘拿Q渐白，常數(shù)尊浓，括號(hào)，運(yùn)算符纯衍，以及其他模式
2. 語法類：在一個(gè)查詢中的成分構(gòu)成栋齿。例如<Query>表示select-from-where形式的查詢，<Condition>表示屬于條件的表達(dá)式襟诸。

如果一個(gè)節(jié)點(diǎn)是原子瓦堵，那么該節(jié)點(diǎn)沒有子節(jié)點(diǎn)。如果一個(gè)節(jié)點(diǎn)是語法類歌亲，則其子節(jié)點(diǎn)通過該語言的語法規(guī)則進(jìn)行描述菇用。

5.1.2 SQL的簡單子集語法

<Query> ::= SELECT <SelList> FROM <FromList> WHERE <Condition>

<SelList> ::= <Attrbute> , <SelList> 

<SelList> ::= <Attrbute>

<FromList> ::== <Relation> , <FromList>

<FromList> ::== <Relation>

<Condition> ::== <Condition> AND <Condition>

<Condition> ::== <Attrbute> IN ( <Query> )

<Condition> ::== <Attrbute> = <Attrbute>

<Condition> ::== <Attrbute> like <Pattern>


<Attrbute> 為任意表示當(dāng)前數(shù)據(jù)庫模式的屬性的字符串

<Relation> 為當(dāng)前模式中作為關(guān)系而言的字符串

<Pattern> 為任何用引號(hào)括起來的字符串

5.1.3 預(yù)處理器

虛視圖替換，語義檢查应结。

1. 檢查關(guān)系的使用（模式）刨疼。
2. 檢查和解析屬性的使用（關(guān)系與屬性）泉唁。
3. 檢查類型（篩選條件類型）鹅龄。

5.2 用于改進(jìn)查詢計(jì)劃的代數(shù)定律

5.2.1 交換律和結(jié)合律

積，連接亭畜，并扮休，交都滿足交換律和結(jié)合律。

交換律

• R×S=S×RR×S=S×R

• R?S=S?RR?S=S?R

• R∪S=S∪RR∪S=S∪R

• R∩S=S∩RR∩S=S∩R

• (R×S)×T=R×(S×T)(R×S)×T=R×(S×T)

• (R?S)?T=R?(S?T)(R?S)?T=R?(S?T)

• (R∪S)∪T=R∪(S∪T)(R∪S)∪T=R∪(S∪T)

• (R∩S)∩T=R∩(S∩T)(R∩S)∩T=R∩(S∩T)

5.2.2 涉及選擇的定律

由于選擇可以明顯減少關(guān)系的大小拴鸵，因此進(jìn)行有效查詢處理的最重要規(guī)則之一就是只要不改變表達(dá)式的結(jié)果玷坠，就把選擇在語法樹上盡可能的下移蜗搔。

• σC1ANDC2(R)=σC1(σC2(R))σC1ANDC2(R)=σC1(σC2(R))
• σC1(σC2(R))=σC2(σC1(R))σC1(σC2(R))=σC2(σC1(R))
• σC1ORC2(R)=σC1(R)∪σC2(R)σC1ORC2(R)=σC1(R)∪σC2(R)

涉及σσ的另一類定律允許我們對(duì)二元運(yùn)算符進(jìn)行下推選擇：積、并八堡、交樟凄、差、連接兄渺。有三中類型定律缝龄，這取決于下推選擇到每個(gè)參數(shù)是可選的還是必須的。

1. 對(duì)于并挂谍，選擇必須下推到兩個(gè)參數(shù)中叔壤。
2. 對(duì)于差，選擇必須下推到第一個(gè)參數(shù)口叙，下推到第二個(gè)參數(shù)是可選的炼绘。
3. 對(duì)于其他運(yùn)算符，只要求選擇下推到第一個(gè)參數(shù)妄田。對(duì)于連接和積俺亮，將選擇下推到兩個(gè)參數(shù)是沒有意義的，因?yàn)閰?shù)可能有也可能沒有所要求的屬性疟呐。即使可以下推到兩者铅辞，該做法也不一定能改進(jìn)計(jì)劃。

因此對(duì)于并的定律是：

• σC(R∪S)=σC(R)∪σC(S)σC(R∪S)=σC(R)∪σC(S)

對(duì)于差的定律：

• σC(R?S)=σC(R)?SσC(R?S)=σC(R)?S
• σC(R?S)=σC(R)?σC(S)σC(R?S)=σC(R)?σC(S)

下面這些定律允許將選擇下推到一個(gè)或者兩個(gè)參數(shù)萨醒，對(duì)于選擇σCσC斟珊，我們只能將其下推到包含C所涉及的全部屬性的關(guān)系中。假設(shè)關(guān)系R中有C提及的所有屬性富纸，有以下定律：

• σC(R×S)=σC(R)×SσC(R×S)=σC(R)×S
• σC(R?S)=σC(R)?SσC(R?S)=σC(R)?S
• σC(R?DS)=σC(R)?DSσC(R?DS)=σC(R)?DS
• σC(R∩S)=σC(R)∩SσC(R∩S)=σC(R)∩S

如果C只涉及S的屬性囤踩，則有：

• σC(R×S)=R×σC(S)σC(R×S)=R×σC(S)

對(duì)于其他3個(gè)運(yùn)算符??、?D?D和 ∩∩ 類似晓褪。如果關(guān)系R和S都包含C的屬性堵漱，那么有諸如以下的定律：

• σC(R?S)=σC(R)?σC(S)σC(R?S)=σC(R)?σC(S)

一些平凡的定律

1. 任何對(duì)空關(guān)系的選擇為空。
2. 如果C總是為真的條件涣仿，則σC(R)=RσC(R)=R勤庐。
3. 如果R為空，R∪S=SR∪S=S好港。

5.2.3 下推選擇

5.2.2節(jié)的規(guī)則是查詢優(yōu)化器的有力工具愉镰，在包含虛視圖時(shí)，需要先將選擇盡可能往樹的上部移钧汹，然后再把選擇下推到所有可能分支丈探。

5.2.4 涉及投影的定律

下推投影是有用的，但是一般而言不如下推選擇那么有用拔莱，因?yàn)橥队安桓淖冊(cè)M數(shù)碗降，只改變?cè)M長度隘竭。

投影定律原理：

• 可以在表達(dá)式樹的任意位置引入投影，只要他所消除的屬性是其上的運(yùn)算符從來不會(huì)用到的讼渊，也不在整個(gè)表達(dá)式的結(jié)果之中动看。

5.2.5 有關(guān)連接和積的定律

• R?CS=σC(R×S)R?CS=σC(R×S)
• R?S=πL(σC(R×S))R?S=πL(σC(R×S))

5.2.6 有關(guān)消除重復(fù)的定律

• δ(R×S)=δ(R)×δ(S)δ(R×S)=δ(R)×δ(S)
• δ(R?S)=δ(R)?δ(S)δ(R?S)=δ(R)?δ(S)
• δ(R?CS)=δ(R)?Cδ(S)δ(R?CS)=δ(R)?Cδ(S)
• δ(σC(R))=σC(δ(R))δ(σC(R))=σC(δ(R))
• δ(R∩BS)=δ(R)∩BS=R∩Bδ(S)=δ(R)∩Bδ(S)δ(R∩BS)=δ(R)∩BS=R∩Bδ(S)=δ(R)∩Bδ(S)

5.2.7 涉及分組和聚集的定律

• δ(γL(R))=γL(R)δ(γL(R))=γL(R)
• γL(R)=γ(πM(R))γL(R)=γ(πM(R)) ,其中，M包含L中提到的所有屬性爪幻。
• γL(R)=γL(δ(R))γL(R)=γL(δ(R))弧圆，當(dāng)且僅當(dāng)γLγL不受重復(fù)行影響（例如Min、Max等）

5.3 從語法分析樹到邏輯查詢計(jì)劃

在5.1節(jié)笔咽，我們構(gòu)造好了語法分析樹搔预，接下來需要把語法樹轉(zhuǎn)化為邏輯查詢計(jì)劃。

第一步叶组，按適當(dāng)?shù)娜航M用一個(gè)或者多個(gè)關(guān)系代數(shù)運(yùn)算符替代語法樹上的節(jié)點(diǎn)和結(jié)構(gòu)拯田。第二步，利用第一步中產(chǎn)生的關(guān)系代數(shù)表達(dá)式甩十，將其轉(zhuǎn)換成我們所期待的可被轉(zhuǎn)成最有效的物理查詢計(jì)劃的一個(gè)表達(dá)式船庇。

5.3.1 轉(zhuǎn)換成關(guān)系代數(shù)

select-from-where結(jié)構(gòu)的關(guān)系代數(shù)的非正式陳述為：

如果我們有一個(gè)包含<Condition>的沒有子查詢的<Query>，則可以用一個(gè)關(guān)系代數(shù)表達(dá)式替換整個(gè)成分——選擇列表侣监、from列表以及條件鸭轮，其中代數(shù)表達(dá)式自底向上由下面這些內(nèi)容組成：

• <FromList>中提及的全部關(guān)系的積是以下運(yùn)算符的參數(shù)。
• 選擇σCσC橄霉，其中C就是要被替換成分中<Condition>表達(dá)式窃爷，同時(shí)又是下面運(yùn)算符的參數(shù)。
• 投影πLπL姓蜂，其中L是<SelList>中的屬性列表按厘。

5.3.2 從條件中去除子查詢

對(duì)于<Condition>中包含子查詢的語法樹，我們將引入運(yùn)算符的中間形式钱慢，他介于語法分析樹的語法類與作用到關(guān)系上的關(guān)系代數(shù)運(yùn)算符之間逮京。該運(yùn)算符通常被成為兩參數(shù)選擇。我們將不帶參數(shù)的標(biāo)簽為σσ的節(jié)點(diǎn)表示經(jīng)轉(zhuǎn)換后的語法樹中的兩參數(shù)選擇束莫。該節(jié)點(diǎn)之下有一個(gè)左子節(jié)點(diǎn)懒棉，它表示要對(duì)其做選擇運(yùn)算的關(guān)系R，以及一個(gè)右子節(jié)點(diǎn)览绿，它表示作用到關(guān)系R的每個(gè)原則上的條件表達(dá)式策严。兩個(gè)參數(shù)均可表示為語法樹、表達(dá)式樹或兩者的混合挟裂。

選擇條件的限制
為什么要去除子查詢享钞？選擇σσ的條件實(shí)際上是針對(duì)每一個(gè)元組的篩選揍诽，即每拿出一個(gè)元組诀蓉，都要執(zhí)行一遍選擇條件栗竖，判斷滿不滿足。如果有子查詢渠啤，則每拿出一個(gè)元組狐肢，就要執(zhí)行一遍子查詢，明顯不現(xiàn)實(shí)沥曹。即使子查詢與元組無關(guān)份名，那也對(duì)代價(jià)計(jì)算的影響很大。

規(guī)則的非正式描述妓美，假設(shè)我們有一個(gè)兩參數(shù)選擇僵腺，其中第一個(gè)參數(shù)代表的關(guān)系R，第二個(gè)參數(shù)形如t in S的<Condition>壶栋，其中S是一個(gè)非相關(guān)子查詢辰如，t是R的元組。我們按照以下方式變換：

1. 用S的表達(dá)式樹替換<Condition>贵试，如果S有重復(fù)琉兜，則在S的表達(dá)式的根部增加δδ運(yùn)算。
2. 用單參數(shù)選擇σCσC替換兩參數(shù)選擇毙玻，其中C是元組t和關(guān)系S中相應(yīng)屬性取等值條件豌蟋。
3. 給選擇σCσC一個(gè)參數(shù)，他是R和S的積桑滩。

5.3.3 邏輯查詢計(jì)劃的改進(jìn)

當(dāng)我們把我們的查詢語句轉(zhuǎn)換為關(guān)系代數(shù)時(shí)梧疲，我們獲得了一個(gè)可能的邏輯查詢計(jì)劃。下一步是在5.2節(jié)列出的代數(shù)定律上重寫計(jì)劃运准。

一下是優(yōu)化器最常用到的：

• 選擇盡可能深地推入表達(dá)式樹往声。如果一個(gè)選擇條件是多個(gè)條件的AND，我們可以把該條件分解并分別將每個(gè)條件下推戳吝。
• 投影下推浩销。
• 消除重復(fù)有時(shí)可以消去，或者移到樹中更方便的未知听哭。
• 某些選擇可以與下面的積相結(jié)合從而轉(zhuǎn)為等值連接慢洋。

5.4 運(yùn)算代價(jià)的估計(jì)

邏輯查詢計(jì)劃會(huì)對(duì)應(yīng)多個(gè)物理查詢計(jì)劃，如何評(píng)價(jià)每個(gè)物理查詢計(jì)劃陆盘、或者估計(jì)實(shí)現(xiàn)的代價(jià)普筹。通過以下選擇進(jìn)行代價(jià)枚舉：

1. 滿足結(jié)合律和分配律的運(yùn)算。
2. 在邏輯計(jì)劃中每個(gè)運(yùn)算符的算法隘马。
3. 其他運(yùn)算符太防。
4. 參數(shù)從一個(gè)運(yùn)算符傳送到下一個(gè)運(yùn)算符的方式。

為了做出每項(xiàng)選擇酸员，我們需要知道各個(gè)物理計(jì)劃的代價(jià)是多少蜒车，在沒有執(zhí)行計(jì)劃的前提下讳嘱，我們不能準(zhǔn)確地知道其代價(jià)。執(zhí)行一個(gè)查詢計(jì)劃要比選一個(gè)計(jì)劃所做的工作多酿愧，我們也不想同時(shí)執(zhí)行多個(gè)查詢計(jì)劃沥潭。因此，我們必須能夠預(yù)估某個(gè)計(jì)劃的代價(jià)嬉挡。

5.4.3 選擇運(yùn)算大小的估計(jì)

令S=σA=c(R)S=σA=c(R)钝鸽，有以下估計(jì)：

T(S)=T(R)/V(R,A)T(S)=T(R)/V(R,A)

如果S=σa>=10(R)S=σa>=10(R)，有以下估計(jì)：

T(S)=T(R)/3T(S)=T(R)/3

S=σa!=10(R)S=σa!=10(R)我們認(rèn)為取的是全量數(shù)據(jù)T(S)T(S)庞钢。

AND條件拔恰，建議是不同選擇概率的乘積。

OR條件基括，大小難以估計(jì)仁连，例如S=σC1orC2(R)S=σC1orC2(R)。當(dāng)C1和C2相互獨(dú)立阱穗，n為元組總數(shù)饭冬，m1表示滿足C1的元組數(shù)，m2表示滿足C2的元組數(shù)揪阶，有：

T(S)=n(1?(1?m1/n)(1?m2/n))T(S)=n(1?(1?m1/n)(1?m2/n))

5.4.4 連接運(yùn)算大小的估計(jì)

三種情況：

1. 沒有相交的Y值昌抠，T(R?S)=0T(R?S)=0
2. Y是S的主鍵，且是R的的外鍵鲁僚，T(R?S)=T(R)T(R?S)=T(R)
3. S和R的所有元組都有相同的Y值炊苫，T(R?S)=T(R)T(S)T(R?S)=T(R)T(S)

通常情況的估計(jì)：

T(R?S)=T(R)T(S)/max(V(R,Y),V(S,Y))T(R?S)=T(R)T(S)/max(V(R,Y),V(S,Y))

5.4.7 其他運(yùn)算大小的估計(jì)

并

較大者加較小者的一半

交

較小者的一半

差

T(R)?T(S)/2T(R)?T(S)/2

消除重復(fù)

min(T(R)/2,×V(R,ai))min(T(R)/2,×V(R,ai))

分組和聚集

T(R)/2T(R)/2

5.7 物理查詢計(jì)劃選擇的完成

經(jīng)過分析查詢，轉(zhuǎn)化為初始的邏輯查詢計(jì)劃和優(yōu)化冰沙∏劝基于代價(jià)估計(jì)選擇物理查詢計(jì)劃。將邏輯計(jì)劃轉(zhuǎn)化為完整地物理計(jì)劃還需要以下這些內(nèi)容：

1. 執(zhí)行計(jì)劃的算法的選擇拓挥。
2. 中間結(jié)果何時(shí)被物化（存儲(chǔ)在硬盤中）写烤。
3. 物理查詢計(jì)劃的運(yùn)算符注釋（包含存儲(chǔ)關(guān)系的訪問方法細(xì)節(jié)和相關(guān)代數(shù)運(yùn)算的執(zhí)行算法的細(xì)節(jié)）迅腔。

部分轉(zhuǎn)自：http://blog.gavinzh.com/2019/06/29/database-system-implementation-lean/