數(shù)據(jù)庫(kù)原理DatabasePrincipl

《數(shù)據(jù)庫(kù)原理DatabasePrincipl》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)庫(kù)原理DatabasePrincipl（74頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、An Introduction to Database System 數(shù)據(jù)庫(kù)原理Database Principle仲愷農(nóng)業(yè)技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院 An Introduction to Database System 第 九 章 關(guān) 系 查 詢 處 理 和 查 詢 優(yōu) 化9.1 概 述9.2 代 數(shù) 優(yōu) 化9.3 物 理 優(yōu) 化9.4 MSSQL優(yōu) 化 之 執(zhí) 行 計(jì) 劃 9.5 小 結(jié) An Introduction to Database System 9.1 概 述n 本 章 目 的 ： n RDBMS的 查 詢 處 理 步 驟 n 查 詢 優(yōu) 化 的 概 念 n 基 本 方 法

2、和 技 術(shù) n 查 詢 優(yōu) 化 分 類 ： n 代 數(shù) 優(yōu) 化n 物 理 優(yōu) 化 An Introduction to Database System 9.1 概 述 （ 續(xù) ）n 9.1.1 查 詢 處 理 步 驟n 9.1.2 實(shí) 現(xiàn) 查 詢 操 作 的 算 法 示 例 An Introduction to Database System 9.1.1 查 詢 處 理 步 驟n RDBMS查 詢 處 理 階 段 ： 1. 查 詢 分 析2. 查 詢 檢 查3. 查 詢 優(yōu) 化 4. 查 詢 執(zhí) 行 An Introduction to Database System 查 詢 處 理 步 驟

3、（ 續(xù) ） 查 詢 處 理 步 驟 An Introduction to Database System 1. 查 詢 分 析n 對(duì) 查 詢 語(yǔ) 句 進(jìn) 行 掃 描 、 詞 法 分 析 和 語(yǔ) 法分 析 n 從 查 詢 語(yǔ) 句 中 識(shí) 別 出 語(yǔ) 言 符 號(hào) n 進(jìn) 行 語(yǔ) 法 檢 查 和 語(yǔ) 法 分 析 An Introduction to Database System 2. 查 詢 檢 查 n 根 據(jù) 數(shù) 據(jù) 字 典 對(duì) 合 法 的 查 詢 語(yǔ) 句 進(jìn) 行 語(yǔ) 義 檢 查 n 根 據(jù) 數(shù) 據(jù) 字 典 中 的 用 戶 權(quán) 限 和 完 整 性 約 束 定 義 對(duì) 用 戶 的 存取 權(quán) 限 進(jìn)

4、 行 檢 查 n 檢 查 通 過(guò) 后 把 SQL查 詢 語(yǔ) 句 轉(zhuǎn) 換 成 等 價(jià) 的 關(guān) 系 代 數(shù) 表 達(dá) 式 n RDBMS一 般 都 用 查 詢 樹 (語(yǔ) 法 分 析 樹 )來(lái) 表 示 擴(kuò) 展 的 關(guān) 系 代數(shù) 表 達(dá) 式 n 把 數(shù) 據(jù) 庫(kù) 對(duì) 象 的 外 部 名 稱 轉(zhuǎn) 換 為 內(nèi) 部 表 示 An Introduction to Database System 3. 查 詢 優(yōu) 化n 查 詢 優(yōu) 化 ： 選 擇 一 個(gè) 高 效 執(zhí) 行 的 查 詢 處 理 策 略 n 查 詢 優(yōu) 化 分 類 ：n 代 數(shù) 優(yōu) 化 ： 指 關(guān) 系 代 數(shù) 表 達(dá) 式 的 優(yōu) 化 ， 改 變 操 作

5、的 次 序 和 組 合n 物 理 優(yōu) 化 ： 指 存 取 路 徑 和 底 層 操 作 算 法 的 選 擇n 查 詢 優(yōu) 化 方 法 選 擇 的 依 據(jù) ： n 基 于 規(guī) 則 (rule based)n 基 于 代 價(jià) (cost based)n 基 于 語(yǔ) 義 (semantic based) An Introduction to Database System 4. 查 詢 執(zhí) 行 n 依 據(jù) 優(yōu) 化 器 得 到 的 執(zhí) 行 策 略 生 成 查 詢 計(jì)劃n 代 碼 生 成 器 (code generator)生 成 執(zhí) 行 查詢 計(jì) 劃 的 代 碼 An Introduction to D

6、atabase System 9.1 關(guān) 系 數(shù) 據(jù) 庫(kù) 系 統(tǒng) 的 查 詢 處 理n 9.1.1 查 詢 處 理 步 驟n 9.1.2 實(shí) 現(xiàn) 查 詢 操 作 的 算 法 示 例 An Introduction to Database System 9.1.2 實(shí) 現(xiàn) 查 詢 操 作 的 算 法 示 例 n 一 、 選 擇 操 作 的 實(shí) 現(xiàn) n 二 、 連 接 操 作 的 實(shí) 現(xiàn) An Introduction to Database System 一 、 選 擇 操 作 的 實(shí) 現(xiàn) n 例 1 Select * from student where ；考 慮 的 幾 種 情 況 ： C1

7、： 無(wú) 條 件 ； C2： Sno 200215121； C3： Sage20； C4： Sdept CS AND Sage20； An Introduction to Database System 選 擇 操 作 的 實(shí) 現(xiàn) （ 續(xù) ）n 選 擇 操 作 典 型 實(shí) 現(xiàn) 方 法 ：n 1. 簡(jiǎn) 單 的 全 表 掃 描 方 法 對(duì) 查 詢 的 基 本 表 順 序 掃 描 ， 逐 一 檢 查 每 個(gè) 元 組 是 否 滿 足 選擇 條 件 ， 把 滿 足 條 件 的 元 組 作 為 結(jié) 果 輸 出 適 合 小 表 ， 不 適 合 大 表 n 2. 索 引 (或 散 列 )掃 描 方 法 適 合

8、選 擇 條 件 中 的 屬 性 上 有 索 引 (例 如 B+樹 索 引 或 Hash索引 ) 通 過(guò) 索 引 先 找 到 滿 足 條 件 的 元 組 主 碼 或 元 組 指 針 ， 再 通 過(guò)元 組 指 針 直 接 在 查 詢 的 基 本 表 中 找 到 元 組 An Introduction to Database System 選 擇 操 作 的 實(shí) 現(xiàn) （ 續(xù) ）n 例 1-C2 以 C2為 例 ， Sno 200215121， 并 且 Sno上 有 索 引(或 Sno是 散 列 碼 )n 使 用 索 引 (或 散 列 )得 到 Sno為 200215121 元 組 的 指 針n 通

9、過(guò) 元 組 指 針 在 student表 中 檢 索 到 該 學(xué) 生n 例 1-C3 以 C3為 例 ， Sage20， 并 且 Sage 上 有 B+樹 索 引 n 使 用 B+樹 索 引 找 到 Sage 20的 索 引 項(xiàng) ， 以 此 為 入 口 點(diǎn) 在 B+樹的 順 序 集 上 得 到 Sage20的 所 有 元 組 指 針n 通 過(guò) 這 些 元 組 指 針 到 student表 中 檢 索 到 所 有 年 齡 大 于 20的 學(xué)生 。 An Introduction to Database System 選 擇 操 作 的 實(shí) 現(xiàn) （ 續(xù) ）n 例 1-C4 以 C4為 例 ， Sd

10、ept CS AND Sage20， 如 果Sdept和 Sage上 都 有 索 引 ：n 算 法 一 ： 分 別 用 上 面 兩 種 方 法 分 別 找 到 Sdept CS的 一 組 元組 指 針 和 Sage20的 另 一 組 元 組 指 針 求 這 2組 指 針 的 交 集 到 student表 中 檢 索 得 到 計(jì) 算 機(jī) 系 年 齡 大 于 20的 學(xué) 生n 算 法 二 ： 找 到 Sdept CS的 一 組 元 組 指 針 ， 通 過(guò) 這 些 元 組 指 針 到 student表 中 檢 索 對(duì) 得 到 的 元 組 檢 查 另 一 些 選 擇 條 件 (如 Sage20)是 否

11、 滿 足 把 滿 足 條 件 的 元 組 作 為 結(jié) 果 輸 出 。 An Introduction to Database System 二 、 連 接 操 作 的 實(shí) 現(xiàn) n 連 接 操 作 是 查 詢 處 理 中 最 耗 時(shí) 的 操 作 之 一 n 本 節(jié) 只 討 論 等 值 連 接 (或 自 然 連 接 )最 常 用 的 實(shí) 現(xiàn) 算 法 n 例 2 SELECT * FROM Student， SC WHERE Student.Sno=SC.Sno； An Introduction to Database System 連 接 操 作 的 實(shí) 現(xiàn) （ 續(xù) ）n 1. 嵌 套 循 環(huán) 方

12、 法 (nested loop) n 2. 排 序 -合 并 方 法 (sort-merge join 或 merge join)n 3. 索 引 連 接 (index join)方 法 n 4. Hash Join方 法 An Introduction to Database System 連 接 操 作 的 實(shí) 現(xiàn) （ 續(xù) ）1. 嵌 套 循 環(huán) 方 法 (nested loop)n 對(duì) 外 層 循 環(huán) (Student)的 每 一 個(gè) 元 組 (s)， 檢索 內(nèi) 層 循 環(huán) (SC)中 的 每 一 個(gè) 元 組 (sc)n 檢 查 這 兩 個(gè) 元 組 在 連 接 屬 性 (sno)上 是

13、否 相等 n 如 果 滿 足 連 接 條 件 ， 則 串 接 后 作 為 結(jié) 果 輸出 ， 直 到 外 層 循 環(huán) 表 中 的 元 組 處 理 完 為 止 An Introduction to Database System 連 接 操 作 的 實(shí) 現(xiàn) （ 續(xù) ）2. 排 序 -合 并 方 法 (sort-merge join 或 merge join) n 適 合 連 接 的 諸 表 已 經(jīng) 排 好 序 的 情 況 n 排 序 合 并 連 接 方 法 的 步 驟 ： 如 果 連 接 的 表 沒 有 排 好 序 ， 先 對(duì) Student表 和 SC表 按連 接 屬 性 Sno排 序 取 St

14、udent表 中 第 一 個(gè) Sno， 依 次 掃 描 SC表 中 具 有 相同 Sno的 元 組 An Introduction to Database System 連 接 操 作 的 實(shí) 現(xiàn) （ 續(xù) ）200215121200215122200215123200215124. 200215121 1 92200215121 2 85200215121 3 88200215122 2 90200215122 3 80. 排 序 -合 并 連 接 方 法 示 意 圖 An Introduction to Database System 連 接 操 作 的 實(shí) 現(xiàn) （ 續(xù) ）n 排 序 合 并

15、 連 接 方 法 的 步 驟 （ 續(xù) ） ： 當(dāng) 掃 描 到 Sno不 相 同 的 第 一 個(gè) SC元 組 時(shí) ， 返 回Student表 掃 描 它 的 下 一 個(gè) 元 組 ， 再 掃 描 SC表 中具 有 相 同 Sno的 元 組 ， 把 它 們 連 接 起 來(lái) 重 復(fù) 上 述 步 驟 直 到 Student 表 掃 描 完 An Introduction to Database System 連 接 操 作 的 實(shí) 現(xiàn) （ 續(xù) ）n Student表 和 SC表 都 只 要 掃 描 一 遍n 如 果 2個(gè) 表 原 來(lái) 無(wú) 序 ， 執(zhí) 行 時(shí) 間 要 加 上 對(duì) 兩 個(gè)表 的 排 序 時(shí)

16、間n 對(duì) 于 2個(gè) 大 表 ， 先 排 序 后 使 用 sort-merge join方法 執(zhí) 行 連 接 ， 總 的 時(shí) 間 一 般 仍 會(huì) 大 大 減 少 An Introduction to Database System 連 接 操 作 的 實(shí) 現(xiàn) （ 續(xù) ）3. 索 引 連 接 (index join)方 法n 步 驟 ： 在 SC表 上 建 立 屬 性 Sno的 索 引 ， 如 果 原 來(lái) 沒 有 該 索引 對(duì) Student中 每 一 個(gè) 元 組 ， 由 Sno值 通 過(guò) SC的 索 引查 找 相 應(yīng) 的 SC元 組 把 這 些 SC元 組 和 Student元 組 連 接 起

17、來(lái) 循 環(huán) 執(zhí) 行 ， 直 到 Student表 中 的 元 組 處 理 完 為 止 An Introduction to Database System 連 接 操 作 的 實(shí) 現(xiàn) （ 續(xù) ）4. Hash Join方 法 n 把 連 接 屬 性 作 為 hash碼 ， 用 同 一 個(gè) hash函 數(shù) 把 R和 S中 的 元 組 散 列 到 同 一 個(gè)hash文 件 中n 步 驟 ：n 劃 分 階 段 (partitioning phase)：n 對(duì) 包 含 較 少 元 組 的 表 (比 如 R)進(jìn) 行 一 遍 處 理 n 把 它 的 元 組 按 hash函 數(shù) 分 散 到 hash表 的

18、桶 中n 試 探 階 段 (probing phase)： 也 稱 為 連 接 階 段 (join phase) n 對(duì) 另 一 個(gè) 表 (S)進(jìn) 行 一 遍 處 理n 把 S的 元 組 散 列 到 適 當(dāng) 的 hash桶 中n 把 元 組 與 桶 中 所 有 來(lái) 自 R并 與 之 相 匹 配 的 元 組 連 接 起 來(lái) An Introduction to Database System 連 接 操 作 的 實(shí) 現(xiàn) （ 續(xù) ）n 上 面 hash join算 法 前 提 ： 假 設(shè) 兩 個(gè) 表 中較 小 的 表 在 第 一 階 段 后 可 以 完 全 放 入 內(nèi)存 的 hash桶 中 n 以

19、 上 的 算 法 思 想 可 以 推 廣 到 更 加 一 般 的多 個(gè) 表 的 連 接 算 法 上 An Introduction to Database System 優(yōu)化的一般步驟 1 把 查 詢 轉(zhuǎn) 換 成 某 種 內(nèi) 部 表 示2 代 數(shù) 優(yōu) 化 ： 把 語(yǔ) 法 樹 轉(zhuǎn) 換 成 標(biāo) 準(zhǔn) （ 優(yōu) 化 ）形 式3 物 理 優(yōu) 化 ： 選 擇 低 層 的 存 取 路 徑4 生 成 執(zhí) 行 計(jì) 劃 ， 選 擇 代 價(jià) 最 小 的 An Introduction to Database System 第 九 章 關(guān) 系 查 詢 處 理 和 查 詢 優(yōu) 化9.1 概 述9.2 代 數(shù) 優(yōu) 化9.3

20、 物 理 優(yōu) 化9.4 MSSQL優(yōu) 化 之 執(zhí) 行 計(jì) 劃 9.5 小 結(jié) An Introduction to Database System 9.2 代 數(shù) 優(yōu) 化n 9.2.1 關(guān) 系 代 數(shù) 表 達(dá) 式 等 價(jià) 變 換 規(guī) 則 n 9.2.2 查 詢 樹 的 啟 發(fā) 式 優(yōu) 化 An Introduction to Database System 9.2.1 關(guān) 系 代 數(shù) 表 達(dá) 式 等 價(jià) 變 換 規(guī) 則 n 代 數(shù) 優(yōu) 化 策 略 ： 通 過(guò) 對(duì) 關(guān) 系 代 數(shù) 表 達(dá) 式的 等 價(jià) 變 換 來(lái) 提 高 查 詢 效 率 n 關(guān) 系 代 數(shù) 表 達(dá) 式 的 等 價(jià) ： 指 用 相

21、 同 的 關(guān)系 代 替 兩 個(gè) 表 達(dá) 式 中 相 應(yīng) 的 關(guān) 系 所 得 到的 結(jié) 果 是 相 同 的n 兩 個(gè) 關(guān) 系 表 達(dá) 式 E1和 E2是 等 價(jià) 的 ， 可 記 為E1E2 An Introduction to Database System 9.2.1 關(guān) 系 代 數(shù) 表 達(dá) 式 等 價(jià) 變 換 規(guī) 則 （ 續(xù) ）1)2)3)4)5) An Introduction to Database System 常用的等價(jià)變換規(guī)則：1. 連 接 、 笛 卡 爾 積 交 換 律 設(shè) E1和 E2是 關(guān) 系 代 數(shù) 表 達(dá) 式 ， F是 連 接 運(yùn) 算 的 條 件 ， 則 有 E1 E2E

22、2 E1 E1 E2E2 E1 E1 E2E2 E12. 連 接 、 笛 卡 爾 積 的 結(jié) 合 律 設(shè) E 1， E2， E3是 關(guān) 系 代 數(shù) 表 達(dá) 式 ， F1和 F2是 連 接 運(yùn) 算 的 條 件 ， 則 有 (E1 E2) E3E1 (E2 E3) (E1 E2) E3E1 (E2 E3) (E1 E2) E3E1 (E2 E3) An Introduction to Database System 關(guān) 系 代 數(shù) 表 達(dá) 式 等 價(jià) 變 換 規(guī) 則 （ 續(xù) ）3. 投 影 的 串 接 定 律 ( (E) (E)這 里 ， E是 關(guān) 系 代 數(shù) 表 達(dá) 式 ， Ai(i=1， 2，

23、 ， n)，Bj(j=1， 2， ， m)是 屬 性 名 且 A1， A2， ， An構(gòu) 成B1， B2， ， Bm的 子 集 。4. 選 擇 的 串 接 定 律 ( (E) (E)這 里 ， E是 關(guān) 系 代 數(shù) 表 達(dá) 式 ， F 1、 F2是 選 擇 條 件 。 選 擇 的 串 接 律 說(shuō) 明 選 擇 條 件 可 以 合 并 。 這 樣 一 次 就 可檢 查 全 部 條 件 。nAAA , 21 mBBB , 21 nAAA , 211F 2F 21 FF An Introduction to Database System 關(guān) 系 代 數(shù) 表 達(dá) 式 等 價(jià) 變 換 規(guī) 則 （ 續(xù) ）

24、5. 選 擇 與 投 影 操 作 的 交 換 律 F( (E) (F(E)選 擇 條 件 F只 涉 及 屬 性 A1， ， An。若 F中 有 不 屬 于 A1， ， An的 屬 性 B1， ，Bm則 有 更 一 般 的 規(guī) 則 ： ( F(E) (F( (E)nAAA , 21 nAAA , 21nAAA , 21 nAAA , 21mn BBBAAA , 2121 An Introduction to Database System 關(guān) 系 代 數(shù) 表 達(dá) 式 等 價(jià) 變 換 規(guī) 則 （ 續(xù) ）6. 選 擇 與 笛 卡 爾 積 的 交 換 律如 果 F中 涉 及 的 屬 性 都 是 E1中

25、 的 屬 性 ， 則 (E1 E2) (E1) E2如 果 F=F1 F2， 并 且 F1只 涉 及 E1中 的 屬 性 ， F2只 涉 及 E2中 的 屬 性 ， 則 由 上 面 的 等 價(jià) 變 換 規(guī) 則 1， 4， 6可 推 出 ： (E1 E2) (E1) (E2)若 F1只 涉 及 E1中 的 屬 性 ， F2涉 及 E1和 E2兩 者 的 屬 性 ， 則仍 有 (E 1 E2) ( (E1) E2)它 使 部 分 選 擇 在 笛 卡 爾 積 前 先 做 。 1F 2F2F 1FF FFF An Introduction to Database System 關(guān) 系 代 數(shù) 表 達(dá)

26、式 等 價(jià) 變 換 規(guī) 則 （ 續(xù) ）7. 選 擇 與 并 的 分 配 律設(shè) E=E1 E2， E1， E2有 相 同 的 屬 性 名 ， 則 F(E1 E2)F(E1) F(E2)8. 選 擇 與 差 運(yùn) 算 的 分 配 律若 E1與 E2有 相 同 的 屬 性 名 ， 則 F(E1-E2)F(E1)-F(E2)9. 選 擇 對(duì) 自 然 連 接 的 分 配 律 F(E1 E2)F(E1) F(E2) F只 涉 及 E1與 E2的 公 共 屬 性 An Introduction to Database System 關(guān) 系 代 數(shù) 表 達(dá) 式 等 價(jià) 變 換 規(guī) 則 （ 續(xù) ）10. 投 影

27、與 笛 卡 爾 積 的 分 配 律設(shè) E1和 E2是 兩 個(gè) 關(guān) 系 表 達(dá) 式 ， A1， ， An是 E1的 屬 性 ，B1， ， Bm是 E2的 屬 性 ， 則 (E1 E2) (E1) (E2)11. 投 影 與 并 的 分 配 律設(shè) E 1和 E2有 相 同 的 屬 性 名 ， 則 (E1 E2) (E1) (E2)mn BBBAAA , 2121 nAAA , 21 mBBB , 21 nAAA , 21 nAAA , 21 nAAA , 21 An Introduction to Database System 9.2 代 數(shù) 優(yōu) 化n 9.2.1 關(guān) 系 代 數(shù) 表 達(dá) 式 等

28、 價(jià) 變 換 規(guī) 則 n 9.2.2 查 詢 樹 的 啟 發(fā) 式 優(yōu) 化 An Introduction to Database System 典型的啟發(fā)式規(guī)則：n 選 擇 運(yùn) 算 應(yīng) 盡 可 能 先 做 n 目 的 ： 減 小 中 間 關(guān) 系n 在 執(zhí) 行 連 接 操 作 前 對(duì) 關(guān) 系 適 當(dāng) 進(jìn) 行 預(yù) 處 理n 按 連 接 屬 性 排 序n 在 連 接 屬 性 上 建 立 索 引 n 投 影 運(yùn) 算 和 選 擇 運(yùn) 算 同 時(shí) 做n 目 的 ： 避 免 重 復(fù) 掃 描 關(guān) 系 n 將 投 影 運(yùn) 算 與 其 前 面 或 后 面 的 雙 目 運(yùn) 算 結(jié) 合n 目 的 ： 減 少 掃 描

29、關(guān) 系 的 遍 數(shù) An Introduction to Database System 查詢優(yōu)化的一般準(zhǔn)則 （續(xù)）n 某 些 選 擇 運(yùn) 算 在 其 前 面 執(zhí) 行 的 笛 卡 爾 積 = 連 接 運(yùn) 算 例 ： Student.Sno=SC.Sno (Student SC) Student SCn 提 取 公 共 子 表 達(dá) 式 當(dāng) 查 詢 的 是 視 圖 時(shí) ， 定 義 視 圖 的 表 達(dá) 式 就 是 公 共 子 表 達(dá) 式 的 情 況 如 果 這 種 重 復(fù) 出 現(xiàn) 的 子 表 達(dá) 式 的 結(jié) 果 不 是 很 大 的 關(guān) 系 并 且 從 外 存 中讀 入 這 個(gè) 關(guān) 系 比 計(jì) 算 該

30、 子 表 達(dá) 式 的 時(shí) 間 少 得 多 ， 則 先 計(jì) 算 一 次 公 共子 表 達(dá) 式 并 把 結(jié) 果 寫 入 中 間 文 件 是 合 算 的 An Introduction to Database System 查 詢 樹 的 啟 發(fā) 式 優(yōu) 化 （ 續(xù) ）n 遵 循 這 些 啟 發(fā) 式 規(guī) 則 ， 應(yīng) 用 9.2.1的 等 價(jià) 變 換 公 式 來(lái) 優(yōu)化 關(guān) 系 表 達(dá) 式 的 算 法 。算 法 ： 關(guān) 系 表 達(dá) 式 的 優(yōu) 化輸 入 ： 一 個(gè) 關(guān) 系 表 達(dá) 式 的 查 詢 樹輸 出 ： 優(yōu) 化 的 查 詢 樹方 法 ：(1) 利 用 等 價(jià) 變 換 規(guī) 則 4把 形 如 F1 F

31、2 Fn(E)變 換 為 F1(F2(Fn(E)。(2) 對(duì) 每 一 個(gè) 選 擇 ， 利 用 等 價(jià) 變 換 規(guī) 則 4 9盡 可 能 把 它移 到 樹 的 葉 端 。 An Introduction to Database System 查 詢 樹 的 啟 發(fā) 式 優(yōu) 化 （ 續(xù) ）(3) 對(duì) 每 一 個(gè) 投 影 利 用 等 價(jià) 變 換 規(guī) 則 3， 5， 10， 11中的 一 般 形 式 盡 可 能 把 它 移 向 樹 的 葉 端 。n 注 意 ： 等 價(jià) 變 換 規(guī) 則 3使 一 些 投 影 消 失 規(guī) 則 5把 一 個(gè) 投 影 分 裂 為 兩 個(gè) ， 其 中 一 個(gè) 有 可 能被 移

32、向 樹 的 葉 端 (4) 利 用 等 價(jià) 變 換 規(guī) 則 3 5把 選 擇 和 投 影 的 串 接 合 并 成單 個(gè) 選 擇 、 單 個(gè) 投 影 或 一 個(gè) 選 擇 后 跟 一 個(gè) 投 影 。 使 多個(gè) 選 擇 或 投 影 能 同 時(shí) 執(zhí) 行 ， 或 在 一 次 掃 描 中 全 部 完 成 An Introduction to Database System 查 詢 樹 的 啟 發(fā) 式 優(yōu) 化 （ 續(xù) ） (5) 把 上 述 得 到 的 語(yǔ) 法 樹 的 內(nèi) 節(jié) 點(diǎn) 分 組 。 每 一 雙 目 運(yùn)算 ( ， ， ， -)和 它 所 有 的 直 接 祖 先 為 一 組 (這 些 直接 祖 先 是

33、 (， 運(yùn) 算 )。n 如 果 其 后 代 直 到 葉 子 全 是 單 目 運(yùn) 算 ， 則 也 將 它 們 并入 該 組 n 但 當(dāng) 雙 目 運(yùn) 算 是 笛 卡 爾 積 ( )， 而 且 后 面 不 是 與 它組 成 等 值 連 接 的 選 擇 時(shí) ， 則 不 能 把 選 擇 與 這 個(gè) 雙 目運(yùn) 算 組 成 同 一 組 ， 把 這 些 單 目 運(yùn) 算 單 獨(dú) 分 為 一 組 An Introduction to Database System 優(yōu)化的一般步驟 (續(xù))例 2： 求 選 修 了 課 程 2的 學(xué) 生 姓 名SELECT Student.SnameFROM Student, SCW

34、HERE Student.Sno=SC.SnoAND SC.Cno=2; An Introduction to Database System (1) 把SQL語(yǔ)句轉(zhuǎn)換成查詢樹結(jié) 果project(Sname) select(SC.Cno=2) join(Student.Sno=SC.Sno) Student SC查 詢 樹 An Introduction to Database System 為了使用關(guān)系代數(shù)表達(dá)式的優(yōu)化法，假設(shè)內(nèi)部表示是關(guān)系代數(shù)語(yǔ)法樹，則上面的查詢樹如下圖所示。Sname SC.Cno=2 Student.Sno=SC.S Student SC關(guān) 系 代 數(shù) 語(yǔ) 法 樹 A

35、n Introduction to Database System (2) 對(duì)查詢樹進(jìn)行優(yōu)化利 用 優(yōu) 化 算 法 把 語(yǔ) 法 樹 轉(zhuǎn) 換 成 標(biāo) 準(zhǔn) （ 優(yōu) 化 ） 形 式 Sname Student.Sno=SC.Sno SC.Cno=2 Student SC優(yōu) 化 后 的 查 詢 樹 An Introduction to Database System n 例 3： An Introduction to Database System n 優(yōu) 化 后 的 查 詢 樹 An Introduction to Database System An Introduction to Databas

36、e System 優(yōu)化 An Introduction to Database System 第 九 章 關(guān) 系 查 詢 處 理 和 查 詢 優(yōu) 化9.1 概 述9.2 代 數(shù) 優(yōu) 化9.3 物 理 優(yōu) 化9.4 MSSQL優(yōu) 化 之 執(zhí) 行 計(jì) 劃 9.5 小 結(jié) An Introduction to Database System 9.3 物 理 優(yōu) 化n 代 數(shù) 優(yōu) 化 改 變 查 詢 語(yǔ) 句 中 操 作 的 次 序 和 組 合 ，不 涉 及 底 層 的 存 取 路 徑n 對(duì) 于 一 個(gè) 查 詢 語(yǔ) 句 有 許 多 存 取 方 案 ， 它 們 的 執(zhí)行 效 率 不 同 ， 僅 僅 進(jìn) 行

37、 代 數(shù) 優(yōu) 化 是 不 夠 的 n 代 數(shù) 優(yōu) 化 比 較 粗 糙 ,而 存 儲(chǔ) 路 徑 優(yōu) 化 效 果 明 顯n 物 理 優(yōu) 化 就 是 要 選 擇 高 效 合 理 的 操 作 算 法 或 存取 路 徑 ， 求 得 優(yōu) 化 的 查 詢 計(jì) 劃 An Introduction to Database System 存 取 路 徑 選 擇 優(yōu) 化n 一 、 選 擇 操 作n 二 、 連 接 操 作 An Introduction to Database System 存 取 路 徑 選 擇 優(yōu) 化n 一 、 選 擇 操 作 An Introduction to Database System

38、存 取 路 徑 選 擇 優(yōu) 化 (續(xù) ) An Introduction to Database System 存 取 路 徑 選 擇 優(yōu) 化 (續(xù) )n 二 、 連 接 操 作n 1. 如 果 2個(gè) 表 都 已 經(jīng) 按 照 連 接 屬 性 排 序n 選 用 排 序 -合 并 方 法2. 如 果 一 個(gè) 表 在 連 接 屬 性 上 有 索 引n 選 用 索 引 連 接 方 法3. 如 果 上 面 2個(gè) 規(guī) 則 都 不 適 用 ， 其 中 一 個(gè) 表 較 小n 選 用 Hash join方 法 An Introduction to Database System 第 九 章 關(guān) 系 查 詢 處

39、理 和 查 詢 優(yōu) 化9.1 概 述9.2 代 數(shù) 優(yōu) 化9.3 物 理 優(yōu) 化9.4 MSSQL優(yōu) 化 之 執(zhí) 行 計(jì) 劃 9.5 小 結(jié) An Introduction to Database System 9.4 MSSQL優(yōu) 化 之 執(zhí) 行 計(jì) 劃n 談 到 優(yōu) 化 就 必 然 要 涉 及 索 引 ， 就 像 要 講鎖 必 然 要 說(shuō) 事 務(wù) 一 樣n 探 索 MSSQL的 執(zhí) 行 計(jì) 劃 ， 來(lái) 讓 大 家 知 道如 何 查 看 MSSQL的 優(yōu) 化 機(jī) 制 ， 以 此 來(lái) 優(yōu)化 SQL查 詢 An Introduction to Database System 9.4 MSSQL優(yōu)

40、 化 之 執(zhí) 行 計(jì) 劃 （ 續(xù) ）例 4 MSSQL優(yōu) 化1. 新 建 測(cè) 試 表 T_UserInfo 2. 插 入 100條 數(shù) 據(jù) 演 示 An Introduction to Database System 9.4 MSSQL優(yōu) 化 之 執(zhí) 行 計(jì) 劃 （ 續(xù) ）3. 查 詢 SELECT * FROM T_UserInfo WHERE USERID=ABCDE6EF 4. Ctrl+L查 看 執(zhí) 行 計(jì) 劃 這 就 是 MSSQL的 執(zhí) 行計(jì) 劃 ：表 掃 描 ： 掃 描 表 中 的 行 An Introduction to Database System 9.4 MSSQL優(yōu) 化

41、 之 執(zhí) 行 計(jì) 劃 （ 續(xù) ）5. 查 看 該 語(yǔ) 句 對(duì) IO的 讀 寫 執(zhí) 行 :SET STATISTICS IO ON 此 時(shí) 再 執(zhí) 行 該 SQL:SELECT * FROM T_UserInfo WHERE USERID=ABCDE6EF 四 個(gè) 值 分 別 為 ： 執(zhí) 行 的 掃 描 次 數(shù) ; 從 數(shù) 據(jù) 緩 存 讀 取 的 頁(yè) 數(shù) ; 從 磁 盤 讀 取 的 頁(yè) 數(shù) ; 為 進(jìn) 行 查 詢 而 放 入 緩 存 的 頁(yè) 數(shù) ; An Introduction to Database System 9.4 MSSQL優(yōu) 化 之 執(zhí) 行 計(jì) 劃 （ 續(xù) ）注 意 ： 如 果 對(duì)

42、 于 一 個(gè) SQL查 詢 有 多 種 寫 法 ，那 么 這 四 個(gè) 值 中 的 邏 輯 讀 (logical reads)決 定 了 哪 個(gè) 是 最 優(yōu) 化 的 。 An Introduction to Database System 9.4 MSSQL優(yōu) 化 之 執(zhí) 行 計(jì) 劃 （ 續(xù) ）6. 接 下 來(lái) 我 們 為 其 建 一 個(gè) 聚 集 索 引 CREATE CLUSTERED INDEX INDEX_Userid ON T_UserInfo (Userid)7. 查 詢 SELECT * FROM T_UserInfo WHERE USERID=ABCDE6EF8. Ctrl+L查

43、看 執(zhí) 行 計(jì) 劃 An Introduction to Database System 9.4 MSSQL優(yōu) 化 之 執(zhí) 行 計(jì) 劃 （ 續(xù) ）9. 注 意 : 此 時(shí) 邏 輯 讀 由 原 來(lái) 的 1變 成 2， 說(shuō) 明 我 們 又 加了 一 個(gè) 索 引 頁(yè) ， 現(xiàn) 在 我 們 查 詢 時(shí) ， 邏 輯 讀 就 是 要 讀兩 頁(yè) (1索 引 頁(yè) +1數(shù) 據(jù) 頁(yè) )， 此 時(shí) 的 效 率 還 不 如 不 建索 引 。 An Introduction to Database System 9.4 MSSQL優(yōu) 化 之 執(zhí) 行 計(jì) 劃 （ 續(xù) ）10. 測(cè) 試 數(shù) 據(jù) 改 變 成 1000條 11.

44、 再 執(zhí) 行 SET STATISTICS IO ON,再 執(zhí) 行 SELECT * FROM T_UserInfo WHERE USERID=ABCDE6EF在 不 加 聚 集 索 引 的 情 況 下 ：表 T_UserInfo。 掃 描 計(jì) 數(shù) 1， 邏 輯 讀 10 次 ， 物 理 讀 0 次 ， 預(yù) 讀 0 次 。在 加 聚 集 索 引 的 情 況 下 ： CREATE CLUSTERED INDEX INDEX_Userid ON T_UserInfo (Userid)表 T_UserInfo。 掃 描 計(jì) 數(shù) 1， 邏 輯 讀 2 次 ， 物 理 讀 0 次 ， 預(yù) 讀 0 次 。

45、(其 實(shí) 也 就 是 說(shuō) 此 時(shí) 是 讀 了 一 個(gè) 索 引 頁(yè) ， 一 個(gè) 數(shù) 據(jù) 頁(yè) )在 加 索 引 的 情 況 下 ： CREATE INDEX INDEX_Userid ON T_UserInfo (Userid)表 T_UserInfo。 掃 描 計(jì) 數(shù) 1， 邏 輯 讀 3 次 ， 物 理 讀 0 次 ， 預(yù) 讀 0 次據(jù) 此 ， 在 數(shù) 據(jù) 量 稍 大 時(shí) ， 索 引 的 查 詢 優(yōu) 勢(shì) 就 顯 示 出 來(lái) 了 。 An Introduction to Database System 9.4 MSSQL優(yōu) 化 之 執(zhí) 行 計(jì) 劃 （ 續(xù) ）先 小 結(jié) 下 ： 當(dāng) 你 構(gòu) 建 S

46、QL語(yǔ) 句 時(shí) ， 按 Ctrl+L就 可 以 看 到 語(yǔ)句 是 如 何 執(zhí) 行 ， 是 用 索 引 掃 描 還 是 表 掃 描 ？ 通 過(guò) SET STATISTICS IO ON 來(lái) 查 看 邏 輯 讀 ，完 成 同 一 功 能 的 不 同 SQL語(yǔ) 句 ， 邏 輯 讀 越 小 查 詢 速 度 越 快 (當(dāng) 然 不 要 找 那 個(gè) 只 有 幾 百條 記 錄 的 例 子 )。 An Introduction to Database System 9.4 MSSQL優(yōu) 化 之 執(zhí) 行 計(jì) 劃 （ 續(xù) ）n -相 關(guān) SQL語(yǔ) 句 解 釋n -n -建 聚 集 索 引n CREATE CLUST

47、ERED INDEX INDEX_Userid ON T_UserInfo (Userid)n -建 非 聚 集 索 引n CREATE NONCLUSTERED INDEX INDEX_Userid ON T_UserInfo (Userid) n -刪 除 索 引n DROP INDEX T_UserInfo.INDEX_Userid An Introduction to Database System 9.4 MSSQL優(yōu) 化 之 執(zhí) 行 計(jì) 劃 （ 續(xù) ）n -顯 示 有 關(guān) 由 Transact-SQL 語(yǔ) 句 生 成 的 磁 盤 活 動(dòng) 量 的 信 息n SET STATISTIC

48、S IO ONn -關(guān) 閉 有 關(guān) 由 Transact-SQL 語(yǔ) 句 生 成 的 磁 盤 活 動(dòng) 量 的 信 息n SET STATISTICS IO OFFn -顯 示 返 回 有 關(guān) 語(yǔ) 句 執(zhí) 行 情 況 的 詳 細(xì) 信 息 ， 并 估 計(jì) 語(yǔ) 句 對(duì) 資 源 的需 求 n SET SHOWPLAN_ALL ON n -關(guān) 閉 返 回 有 關(guān) 語(yǔ) 句 執(zhí) 行 情 況 的 詳 細(xì) 信 息 ， 并 估 計(jì) 語(yǔ) 句 對(duì) 資 源 的需 求 n SET SHOWPLAN_ALL OFFn -n 請(qǐng) 記 住 ： SET STATISTICS IO 和 SET SHOWPLAN_ALL 是 互斥

49、的 。 An Introduction to Database System 9.4 MSSQL優(yōu) 化 之 執(zhí) 行 計(jì) 劃 （ 續(xù) ） ? SELECT * FROM T_UserInfo WHERE USERID LIKE ABCDE8% An Introduction to Database System 第 九 章 關(guān) 系 查 詢 處 理 和 查 詢 優(yōu) 化9.1 概 述9.2 代 數(shù) 優(yōu) 化9.3 物 理 優(yōu) 化9.4 MSSQL優(yōu) 化 之 執(zhí) 行 計(jì) 劃 9.5 小 結(jié) An Introduction to Database System 9.5 小 結(jié)n 查 詢 處 理 是 RDB

50、MS的 核 心 ， 查 詢 優(yōu) 化 技術(shù) 是 查 詢 處 理 的 關(guān) 鍵 技 術(shù) n 本 章 講 解 的 優(yōu) 化 方 法 n 啟 發(fā) 式 代 數(shù) 優(yōu) 化n 基 于 規(guī) 則 的 存 取 路 徑 優(yōu) 化n 基 于 代 價(jià) 的 優(yōu) 化n 本 章 的 目 的 ： 希 望 讀 者 掌 握 查 詢 優(yōu) 化 方法 的 概 念 和 技 術(shù) An Introduction to Database System 小 結(jié) （ 續(xù) ）n 比 較 復(fù) 雜 的 查 詢 ， 尤 其 是 涉 及 連 接 和 嵌 套 的 查 詢n 不 要 把 優(yōu) 化 的 任 務(wù) 全 部 放 在 RDBMS上n 應(yīng) 該 找 出 RDBMS的 優(yōu) 化 規(guī) 律 ， 以 寫 出 適 合 RDBMS自動(dòng) 優(yōu) 化 的 SQL語(yǔ) 句 n 對(duì) 于 RDBMS不 能 優(yōu) 化 的 查 詢 需 要 重 寫 查 詢 語(yǔ) 句 ， 進(jìn) 行手 工 調(diào) 整 以 優(yōu) 化 性 能 An Introduction to Database System n 作 業(yè) ： 275 2