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

什么是臨界點?

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

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

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

    需要注意的是覆蓋索引中不存在RID/Key，而是對應(yīng)的列值，所以不會出現(xiàn)這個問題。

臨界點什么時候出現(xiàn)?

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

      一個表總行數(shù)為1,000,000，每頁存放2條行數(shù)，共500,000頁。則25%=125,000,33%=166,000。臨界點會出現(xiàn)在125,000頁和166,000頁間。轉(zhuǎn)換成行表示就是125000/(2*500000)=12.5%，166000/(2*500000)=16.6%。也就是說當(dāng)返回行數(shù)小于62400(500000*12.55)時，很可能會使用Lookup。當(dāng)返回行數(shù)大于83000時，很可能會使用Scan。這個表的行太寬了，一個頁只能存放2行數(shù)據(jù)，從百分比看起來沒有什么太大感覺。

一個表總行數(shù)為1,000,000，每頁存放100條行數(shù)，共10,000頁。則25%=2500，33%=3300。轉(zhuǎn)換成行2500/1000000=0.25%,3300/1000000=0.33%。它的臨界點上限不超過0.5%。也就是說你查詢表中不到0.5%的行數(shù)時，會全表掃描。

一個表總行數(shù)為1,000,000，每頁存放20條行數(shù)，共50,000頁。則25%=125,00,33%=166,00。轉(zhuǎn)換成行表示就是125000/(2*500000)=1.25%，166000/(2*500000)=1.66%。

   不難發(fā)現(xiàn)，臨界點判斷，對于大表的查詢性能是有很大幫助的。而對于小表而言，幾乎都會是Scan，但是數(shù)據(jù)庫有緩存機(jī)制，小表會完整緩存，掃描影響也不大。

我們能做些什么？

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

 2.建立一個覆蓋索引消除Lookup操作。

示例分析

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

通過下的查詢可以知道表有121317行，共1237個數(shù)據(jù)頁，每頁大約存放98行數(shù)據(jù)。由此我們可以預(yù)估一下臨界點在(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

然后再統(tǒng)計一下不同的ProductID在表中行數(shù)，好針對性的測試不同ProductID:

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

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

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

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

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

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

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

總結(jié)

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

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

參考 

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