查詢優化器核心剖析第二篇：産生候選執行計劃&執行計劃成本估算

本篇的議題如下：

    産生候選執行計劃

    執行計劃成本估算

産生候選執行計劃

    我們知道，查詢優化器的基本的目标就是為我們的查詢語句找出一個比較高效的執行計劃。即使是一個非常簡單的查詢，也會存在很多的不同方式去通路資料，而這些不同的方式都是可以得到相同的結果的，是以，查詢優化器必須要很“明智的”從這些大量的執行計劃中找出了一個“最佳”的出來。

    為了得到最好的計劃，查詢優化器必須在某些條件的限制下，盡可能多的建立和評估大量的候選執行計劃。看到這裡，就有一點需要注意了“查詢優化器是盡可能多的建立候選執行計劃”，而不是為一個查詢産生所有的執行計劃。在SQL Server中，我們把一個查詢産生的候選執行計劃的集合稱之為“搜尋空間(search space)”。很顯然，搜尋空間中的所有的執行計劃都傳回相同的結果。

給一張示意圖，讓大家更好了解一點，如下所示：

<a href="http://www.agilesharp.com/Services/BlogAttachment.ashx?AttachmentID=77" target="_blank"></a>

    注：圖中的Search Space中的曲線代表執行計劃

    從理論上說，為了找到最佳的執行計劃的查詢，基于成本的查詢優化器應該生成搜尋空間中存在的所有可能的執行計劃，并正确估計每個計劃的成本。然而，一些複雜的查詢可能有成千上萬，或者甚至數百萬可能的執行計劃，查詢優化器不可能去産生并評估一個查詢的每一個候選的執行計劃，如果那樣，評估所有計劃的時間會非常的長，并且嚴重影響查詢的整體的執行時間。

    查詢優化器必須優化的時間和執行計劃的品質之間取得平衡。例如，如果查詢優化器花1秒鐘的時間找到了一個比較好的執行計劃，并且這個計劃的執行時間是1分鐘，那麼這個時候，就沒有必要再去花費5分鐘的時間去為這個查詢找更優的執行計劃。是以SQL Server不會做一個詳盡的全部查找，而是盡快找到一個合适的有效的計劃。由于查詢優化器是有時間限制的，那麼就可能選擇的計劃可能是最優方案，也有可能隻是一些接近最優的方案。

    候選的執行計劃是在查詢優化器的内部通過使用轉換規則，啟發式算法産生的。候選的執行計劃在優化過程中一直儲存在稱之為“Memo(中文翻譯可能為“備忘錄”，以後我們就直接使用英文名稱，很多的技術術語翻譯過來之後就變味了)”的記憶體元件中。從這裡我們就可以知道：如果為了複雜的查詢産生所有的候選執行計劃勢必會占用大量的記憶體。

    我們這裡隻是簡單的介紹一下候選執行計劃的産生，後面我們會對每一個步驟進行詳細的分析。

執行計劃成本估算

    查詢優化器需要為産生的候選的執行計劃進行成本的估算，進而選擇一個成本最低的。為了估算一個計劃的成本，查詢優化器會使用一些成本估算的公式來計算一個計劃的成本，這些成本估算公式會考慮很多資源的使用，例如CPU，I/O，記憶體等。成本估算主要是取決于算法中采用的實體操和估算的将要處理的資料記錄的量（估算資料記錄的量也被稱之為“基數估算”）。

    為了便于進行基數估算，SQL Server會使用并且維護統計資料(statistics)，統計資料描述了表中資料的值的分布情況，或者簡單的了解為“中繼資料-描述資料的資料”。一旦采用基數估算得出了嗎，每個操作的成本和對資源的要求，那麼查詢優化器就會将這個成本數值進行累計，進而得出整個就會的成本。我們這裡不會讨論過多與統計資料相關的知識，在後面中會詳細的講述。

    在下一篇文章中，我們會講述計劃的執行與緩存，以及與Hint相關的話題。

本文轉自yanyangtian51CTO部落格，原文連結：http://blog.51cto.com/yanyangtian/812941 ，如需轉載請自行聯系原作者