在今天的文章里我想談下基數計算里的一個特定問題：在查詢謂語里相關列的基數計算。首先我們看下在SQL Server 7.0起的操作方法，最后我們詳細看下SQL Server 2014里，在查詢期間，處理相關列基數計算的全新實現方式。

在我們進入問題細節前，我們必須要澄清什么是相關列。當我們看SQL Server使用的查詢優化器時，查詢優化器是基于4個核心假設：

• 獨立性（Independence）
• 一致性（Uniformity）
• 密封度（Containment）
• 夾雜物（Inclusion）

我不想細談每個假設，因為它們在其它的白皮書里解釋得非常清楚。在文章末尾的小結部分你會找到白皮書的鏈接。今天我們要聚焦的是第1個假設——獨立性（Independence）。獨立性意味這在查詢謂語（WHERE子句）里用到的列是獨立的，當各自查詢時，會返回不同的記錄。它們彼此間互不影響。遺憾的是這個假設并不都正確。我們來看一個具體的例子，這里違反了假設。假設下列2個查詢：

1 SELECT * FROM Sales.SalesOrderHeader2 WHERE SalesOrderID > 74000 AND SalesOrderID < 750003 GO4 5 SELECT * FROM Sales.SalesOrderHeader6 WHERE OrderDate >= '20080626' AND OrderDate <= '20080724'7 GO

第1個查詢返回999條記錄，第2個查詢返回1125條記錄。但符合這2個查詢條件的記錄是912條，這就是說這2列之間是有關聯的。但是查詢優化器并沒有意識到這點。

現在我們來看下SQL Server 7.0-2012是如何處理這個相關列的。在具體的執行計劃里，第1個查詢里，查詢優化器估計行數是999.936，第2個查詢里，查詢優化器估計行數是1125。

用那些信息就與基數計算我們的表（這里表總記錄數是31465），我們可以計算出查詢謂語所謂的選擇度（Selectivity）。選擇度是0到1的數字。選擇度越小，從查詢返回的記錄越少（0表示0%的記錄返回，1表示100%的記錄返回）。我們可以通過估計行數除以表存儲的總記錄數來計算查詢謂語的選擇度。因此第1個查詢謂語的選擇度是0.03177931034482758620689655172414（999/31465），第2個查詢謂語的選擇度是0.03575401239472429683775623708883（1125/31465）?，F在我們來看下如果我們使用AND運算符組合2個查詢謂語會發生什么：

1 SELECT * FROM Sales.SalesOrderHeader2 WHERE SalesOrderID > 74000 AND SalesOrderID < 750003 AND OrderDate >= '20080626' AND OrderDate <= '20080724'4 GO

當你查看執行計劃時，查詢優化器在聚集索引查找（聚集的）（Clustered Index Seek (Clustered) ）運算符上的估計行數是35.7517。

實際執行返回是如剛才提到的912行。這個差異太大了。查詢優化器只是把2個查詢謂語的選擇度值相乘得出最后的估計行數。SQL Server假設2個查詢謂語返回不同的行——假設這2列是彼此獨立的：

0.03177931034482758620689655172414 * 0.03575401239472429683775623708883 * 31465 = 35.7517241379310344827586206896586

當然，事實是完全不一樣的，因為在2個查詢謂語間有巨大的關聯。因此你會看到估計行數和行數之間有絕大的差異。在查詢里使用更多的AND組合各個查詢謂語，差異就會更大。當最后估計將至1行時，查詢優化器總會估計至少1行——從不估計0行。

你可能已經聽說了，SQL Server 2014包含了一個新的基數計算。一旦你的數據庫是在120的兼容模式，新的基數計算就會用到。注意，當你從老版本的SQL Server還原或附加數據庫時——這里的兼容性會變成老的！如果你想步改變兼容模式使用新的基數計算，你也可以使用新的2312跟蹤標記?，F在讓我們對查詢啟用2312跟蹤標記來讓剛才的2個查詢謂語使用新的基數計算。

1 SELECT * FROM Sales.SalesOrderHeader2 WHERE SalesOrderID > 74000 AND SalesOrderID < 750003 AND OrderDate >= '20080626' AND OrderDate <= '20080724'4 OPTION (RECOMPILE, QUERYTRACEON  2312)5 GO

當你查看執行計劃時，你會看到基數計算已經變了。

現在新的基數計算估計行數是188898.比剛才的老的基數計算的35.75行大很多。但到查詢實際返回的912行還是有個大的缺口。不過現在新的基數估計用的是什么公式呢？新的基數計算使用所謂的指數退避算法（Exponential Back-off algorithm）。查詢優化器取走這4個查詢謂語，根據它們的選擇度排序。所有的選擇度再次相互相乘，但這里不同的是每個子過程值通過更大的平方根來軟化。我們來看下公式來來理解這個行為：

c0 * (c1 ^ 1/2) * (c2 ^1/4) * (c3 ^ 1/8)

我們來看下具體的例子，通過下列計算就可以獲得最終的基數：

0.03177931034482758620689655172414 * SQRT(0.03575401239472429683775623708883) * 31465 = 189.075212620762

比起188.898的估計行數我們的計算還有小差異，因為在SQL Server提供給執行計劃里的估計行數是999.936行。使用指數退避算法，查詢優化器可以確保做出更好的估計收緊估計行數和實際行數的洞，如果接受的查詢參數之間有關聯的話。

在這篇文章里我們談了關系數據庫里基數計算期間的特定問題：作為查詢謂語使用的關聯列如何使用基數估計。在SQL Server 2014之前，查詢優化器使用不同選擇值相乘，非常平穩的方法。這會導致巨大的低估，如果執行計劃里前一個運算符（例如Sort或Hash運算符）基于這些估計，它會引起麻煩。

SQL Server 2014新的基數計算對此特定問題使用增強的機制：在基數計算期間使用指數退避公式，生成更好的估計。但和運行時的實際行數還是有差異。如果你想了解更多SQL Server 2014新的基數計算，我建議看下Joe Sack寫的白皮書“使用SQL Server 2014參數計算優化你的查詢計劃”。

感謝關注！

-----------------------------------------------------------------------

原文鏈接：https://www.sqlpassion.at/archive/2014/04/22/cardinality-estimation-for-correlated-columns/

Translated by:WoodyTu