文章目錄

• 一：查詢處理步驟
• • （1）查詢分析
  • （2）查詢檢查
  • （3）查詢優化
  • （4）查詢執行
• 二：實現查詢操作的算法示例
• • （1）選擇操作的實現
  • • ①：全表掃描
    • ②：索引（或散列）掃描
  • （2）連接操作的實現
  • • ①：嵌套循環方法（nested loop）
    • ②：排序-合并方法（sort-merge join）
    • ③：索引連接（index join）
    • ④：哈希連接（hash join）

查詢處理是關系數據庫管理系統執行查詢語句的過程，其任務是把用戶提交給關系數據庫管理系統的查詢語句轉換為高效的查詢執行計劃

一：查詢處理步驟

關系數據庫管理系統查詢處理可以分為4個階段：

• 查詢分析
• 查詢檢查
• 查詢優化
• 查詢執行

（1）查詢分析

任務：對查詢語句進行掃描，分析詞法、語法是否符合SQL語法規則

• 如果沒有語法錯誤轉入下一步
• 如果有語法錯誤則在報告中顯示錯誤

（2）查詢檢查

任務：

• 對合法的查詢語句進行語義檢查，即根據數據字典中有關的模式定義檢查語句中的數據庫對象，如關系名、屬性名是否存在和有效
• 如果是對視圖的操作，則要用視圖消解方法把對視圖的操作轉換成對基本表的操作
• 還要對權限、完整性約束進行檢查，如果違反則拒絕查詢
• 檢查通過后，把SQL查詢語句轉化為內部表示，也即等價的關系代數表達式
• 在此過程中，要把數據庫對象的外部名稱換為內部表示
• RDBMS一般用查詢樹（又稱為語法分析樹）來表示擴展的關系代數表達式

（3）查詢優化

任務：每個查詢都會有許多可供選擇的執行策略和操作算法，查詢優化就是選擇一個高效執行的查詢處理策略。按照優化的層次一般可以將查詢優化分為

• 代數優化：是指關系代數表達式的優化，也即按照一定規則，通過對關系代數表達式進行等價變換，改變代數表達式中操作的次序和組合，使查詢更高效
• 物理優化：是指存取路徑和底層操作算法的選擇。選擇依據可以是基于規則的(rule based)、基于代價的(cost based)、基于語義的(semantic based)

（4）查詢執行

依據優化器得到的執行策略生成查詢執行計劃，由 代碼生成器(code generator) 生成執行這個查詢計劃的代碼，然后加以執行，回送查詢結果。

二：實現查詢操作的算法示例

（1）選擇操作的實現

以簡單的單表選擇為例，如下

SELECT* FROM STUDENT WHERE<條件表達式>

<條件表達式>可以有以下幾種情況

• $case1$：無條件
• $case2$：Sno=‘201215121’
• $case3$：Sage > 20
• $case4$：Sdept=‘CS’ AND Sage > 20

選擇操作只涉及一個關系，典型的實現方法有

①：全表掃描

思想：假設可以使用的內存塊為$M$塊

• 按照物理次序讀Student的$M$塊到內存
• 檢查內存的每個元組$t$，如果$t$滿足選擇條件，則輸出$t$
• 如果Student還有其他塊未被處理，重復即可

優缺點：

• 優點：只需要用很少的內存（最少為1塊）就可以運行，且控制簡單。適用于規模較小的表
• 缺點：對于規模大的表進行順序掃描，當選擇率低時會使效率很低

②：索引（或散列）掃描

思想：如果選擇條件中的屬性上有索引（例如$B$+樹索引或$hash$索引），可以用索引掃描。通過索引先找到滿足條件的元組指針，再通過元組指針在查詢的基本表中找到元組。 一般來說，當選擇率低于10%時建立索引才有意義

• 以$case$ 2為例：Sno=‘201215121’，并且Sno上有索引，則可以使用索引得到Sno為’201215121’元組的指針，然后通過元組指針在Student表中檢索到該學生
• 以$case$ 3為例：Sage>20， 并且Sage上有B+樹索引，則可以使用B+樹索引找到Sage=20的索引項，以此為入口點在B+樹的順序集上得到Sage>20的所有元組指針，然后通過這些元組指針到Student表中檢索到所有年齡大于20的學生
• 以$case$ 4為例： Sdept=‘CS’ AND Sage>20, 如果Sdept和Sage 上都有索引，一種算法是，分別用上面兩種方法找到Sdept='CS’的一組元組指針和Sage>20的另一組元組指針，求這兩組指針的交集，再到Student表中檢索，就得到計算機系年齡大于20歲的學生；另一種算法是，找到Sdept='CS’的一組元組指針，通過這些元組指針到Student表中檢索，并對得到的元組檢查另一些選擇條件(如Sage>20) 是否滿足，把滿足條件的元組作為結果輸出

（2）連接操作的實現

連接操作是查詢處理中最常用也是最耗時的操作之一 。不失一般性，這里通過例子簡單介紹 等值連接(或自然連接) 最常用的幾種算法思想

SELECT * FROM Student,SC WHERE Student.Sno=SC.Sno;

①：嵌套循環方法（nested loop）

思想：對外層循環(Student表)的每一個元組，檢索內層循環(SC表)中的每一個元組，并檢查這兩個元組在連接屬性(Sno) 上是否相等。如果滿足連接條件，則串接后作為結果輸出，直到外層循環表中的元組處理完為止

②：排序-合并方法（sort-merge join）

思想：

如果參與連接的表沒有排好序，首先對Student表和SC表按連接屬性Sno排序

取Student表中第一個 Sno,依次掃描SC表中具有相同Sno的元組，把它們連接起來

當掃描到Sno不相同的第 一個SC元組時，返回Student 表掃描它的下一 個元組，再掃描SC表中具有相同Sno的元組，把它們連接起來

重復上述步驟直至Student掃描完畢

③：索引連接（index join）

思想：

• 在SC表上已經建立了屬性Sno的索引
• 對Student中每一個元組，由Sno值通過SC的索引查找相應的SC元組
• 把這些SC元組和Student元組連接起來

循環執行第二步和第三步，直至Student中的元組處理完畢

④：哈希連接（hash join）

思想：它把連接屬性作為hash碼，用同一個hash函數把Student表和SC表中的元組散列到hash表中

• 劃分階段（創建階段）：即創建hash表。對包含較少元組的表( 如Student表)進行一遍處理，把它的元組按hash函數(hash碼是連接屬性)分散到hash表的桶中
• 試探階段（連接階段）：對另一個表(SC表)進行一遍處理，把SC表的元組也按同一個hash函數(hash 碼是連接屬性)進行散列，找到適當的hash桶，并把SC元組與桶中來自Student 表并與之相匹配的元組連接起來。

新人創作打卡挑戰賽發博客就能抽獎！定制產品紅包拿不停！

總結

以上是生活随笔為你收集整理的（数据库系统概论|王珊）第九章关系查询处理和关系优化-第一节：查询处理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。