非聚集索引中的臨界點(Tipping Point)

什麼是臨界點?

      註意，我要說的問題是非聚集索引的執行計劃從Seek+Lookup變成Table/Clustered Index Scan的臨界點。SQL Server的訪問數據的IO最小單元是頁。

      我們知道聚集索引的葉級是數據頁，非聚集索引的葉級是指向數據行的指針。所以通過聚集索引獲取數據時，就是直接訪問聚集索引本身，而通過非聚集索引獲取數據時，除了訪問自身，還要通過指針去訪問數據頁。這個過程就是RID/Key Lookup。而此Lookup是一個單頁操作，即每次使用一個RID/Key，然後去訪問對應的一個數據頁，然後獲取頁上的相應的數據行。可能當前數據頁的有多個數據行是符合查詢要求的，但是一次lookup，只能取當前的RID/Key指定的數據行。所以同一個數據頁，可能要被訪問很多次。例如，現在lookup要去找RID為2，3，5，7，9對應的數據行，而這5個數據行都存在數據頁N上，則數據頁N只少要被訪問5次。

    在Seek時，如果要返回N行數據，則Seek操作至少要訪問N次數據頁。當Lookup訪問次數據超過了全表數據頁的總數時，就會出現臨界點。這個時候Scan操作成本要比Lookup低。超過這個臨界點時，查詢優化器一般會選擇Scan替代Seek+Lookup。例如表T有100000行，每頁存放100行，共有1000頁。查詢1000條數據，理論/理想情況下：Scan最少時只需要10次IO，Lookup只少需要1000次IO。

    需要註意的是覆蓋索引中不存在RID/Key，而是對應的列值，所以不會出現這個問題。

臨界點什麼時候出現?

      前面說的理論和原理上的東西，而實際臨界點的出現由很多因素決定。但主要與表的總頁數相關。臨界點大概出現在訪問頁占全表頁數的25%~33%時。為了直觀，通常把頁數再轉換成行數來分析。轉換時需要註意，前面闡明Lookup是單頁操作，所以頁數=行數。

• 一個表總行數為1,000,000，每頁存放2條行數，共500,000頁。則25%=125,000,33%=166,000。臨界點會出現在125,000頁和166,000頁間。轉換成行表示就是125000/(2*500000)=12.5%，166000/(2*500000)=16.6%。也就是說當返回行數小於62400(500000*12.55)時，很可能會使用Lookup。當返回行數大於83000時，很可能會使用Scan。這個表的行太寬了，一個頁只能存放2行數據，從百分比看起來沒有什麼太大感覺。
• 一個表總行數為1,000,000，每頁存放100條行數，共10,000頁。則25%=2500，33%=3300。轉換成行2500/1000000=0.25%,3300/1000000=0.33%。它的臨界點上限不超過0.5%。也就是說你查詢表中不到0.5%的行數時，會全表掃描。
• 一個表總行數為1,000,000，每頁存放20條行數，共50,000頁。則25%=125,00,33%=166,00。轉換成行表示就是125000/(2*500000)=1.25%，166000/(2*500000)=1.66%。

   不難發現，臨界點判斷，對於大表的查詢性能是有很大幫助的。而對於小表而言，幾乎都會是Scan，但是資料庫有緩存機制，小表會完整緩存，掃描影響也不大。

我們能做些什麼？

    很容易想到，既然表有Seek對應的索引，我們使用Hint強制使用Seek，問題不就解決了。這個不一定，本來這個問題的出現就是查詢優化器認為Scan比Lookup的成本要低。如果你強制可能會適得其反。SQL Server的查詢優化器是很強大和智能的，除非你嚴格測試過，證明ForceSeek性能更好一些。

示例分析

    使用AdventureWorks2012的Sales.SalesOrderDetail。在ProductID列有一個非聚集索引IX_SalesOrderDetail_ProductID。

通過下的查詢可以知道表有121317行，共1237個數據頁，每頁大約存放98行數據。由此我們可以預估一下臨界點在(309行，408行)附近。

select page_count,record_count
from sys.dm_db_index_physical_stats(db_id(),object_id(N'Sales.SalesOrderDetail'),1,null,'detailed')
where  index_level=0

然後再統計一下不同的ProductID在表中行數，好針對性的測試不同ProductID:

select ProductID,COUNT(*) as cnt
from Sales.SalesOrderDetail   
group by ProductID
order by cnt

通過上面查詢，我們知道ProductID=882在表中有407行，可以看到它還是使用Lookup的方式。它的IO計數為：

Table 'SalesOrderDetail'. Scan count 1, logical reads 1258

ProductID=751在表中有409行，它就使用了Scan的方式。它的IO計數為：

Table 'SalesOrderDetail'. Scan count 1, logical reads 1246

我們還可以測試其它的返回行數更多的ProductID，如果是掃描的方式則IO都是在1246，如果是Lookup則都會高於1246。證明跟理論還是契合的。

就算500行返回才會超過臨界點，而500行也只占總行數的500/121317=0.41%。也就是說當返回行數超過全表的0.41%時，優化器就認為它的篩選度不夠高了，不用seek+lookup，要掃描了。

總結

1. 當遇到"明明有索引，為什麼會掃描？"，臨界點的問題可能是原因之一。

2. 因為存在臨界點，所以非覆蓋非聚集索引的使用率可能沒有我們想象的高。

參考 

http://www.sqlskills.com/blogs/kimberly/the-tipping-point-query-answers/