想要設(shè)計(jì)出好的索引，首先必須了解SQL語句在數(shù)據(jù)庫服務(wù)器中的處理過程，本文介紹 數(shù)據(jù)庫索引設(shè)計(jì)與優(yōu)化 中幾個(gè)對(duì)索引優(yōu)化非常重要的概念。

[[274110]]

謂詞

謂詞就是條件表達(dá)式。 SQL語句的where子句由一個(gè)或者多個(gè)謂詞組成。

WHERE SEX = 'M' 
 AND  
 (WHIGHT > 90 
 OR 
 HEIGHT > 190) 

上面這個(gè)WHERE子句有三個(gè)簡(jiǎn)單謂詞：

• SEX = ‘M’
• WRIGHT > 90
• HEIGHT >190

也可以認(rèn)為是兩個(gè)組合謂詞：

• WEIGHT > 90 OR HEIGHT >190
• SEX = ‘M’ AND (WEIGHT > 90 OR HEIGHT >190)

優(yōu)化器及訪問路徑

關(guān)系型數(shù)據(jù)庫的一大優(yōu)勢(shì)就是，用戶無須關(guān)系數(shù)據(jù)的訪問方式。其訪問路徑是由DBMS的一個(gè)組件，即 優(yōu)化器 來確定的。 優(yōu)化器是SQL處理過程的核心 。

這里以mysql為例展示一個(gè)簡(jiǎn)單的mysql服務(wù)器邏輯結(jié)構(gòu)

在圖中我們可以看到優(yōu)化器的位置。

在SQL語句能夠被真正執(zhí)行之前，優(yōu)化器必須首先確定如何訪問數(shù)據(jù)。比如mysql會(huì)解析查詢并創(chuàng)建解析樹，然后對(duì)其進(jìn)行各種優(yōu)化，包括決定選擇合適的索引，決定表的讀取順序。

而 謂詞表達(dá)式 是索引設(shè)計(jì)的主要入手點(diǎn)。如果一個(gè)索引能夠滿足SELECT查詢語句的所有謂詞表達(dá)式，那么優(yōu)化器就很有可能建立起一個(gè)高效的訪問路徑。

索引片及匹配列

如果索引時(shí)以B+樹的形式組織的，如果有謂詞表達(dá)式 WHERE A > 100 AND A < 110 ，那么查詢到的葉子節(jié)點(diǎn)的范圍會(huì)最終為下圖：

圖的左邊是索引的一個(gè)窄片段，我們稱這個(gè)片段為 索引片

• 這個(gè)片段會(huì)被順序掃描，上面索引行的值在100到110之間，相應(yīng)的表行將通過同步讀從表(也可能在緩沖池)中讀取。

所以訪問路徑的成本很大程度上取決于這個(gè)索引片的厚度，也就是謂詞表達(dá)式確定的值域范圍。索引片越厚，需要掃描的索引頁就越多，需要處理的索引記錄也就越多，但最大的開銷還是來自于增加的對(duì)表的同步讀操作，每次表頁讀取的I/O操作可能需要10ms。相應(yīng)的，索引片比較窄，就會(huì)減少對(duì)表的同步讀取。

索引過濾及過濾列

并不是所有的索引列都能夠定義索引片的大小。有時(shí)候，列可能既存在于WHERE子句中，也存在于索引中，但這個(gè)列卻不能參與索引片的定義，舉個(gè)例子。 表上有一聯(lián)合索引(A,B,C,D)，有如下sql語句：

WHERE A = :A 
 AND 
 B > :B 
 AND 
 C = :C 

我們需要確定WHERE子句中的謂詞是否能夠確定索引片大小：

1. 首先我們看在WHERE子句中，該列是否至少有一個(gè) 足夠簡(jiǎn)單 的謂詞與之對(duì)應(yīng)? 如果有，那么這個(gè)列就是匹配列。如果沒有，那么這個(gè)列及其后面的索引列都是非匹配列。
2. 如果該謂詞是一個(gè)范圍謂詞，那么剩余的索引列都是非匹配列。
3. 對(duì)于最后一個(gè)匹配列之后的索引列，如果擁有一個(gè)足夠簡(jiǎn)單的謂詞與其對(duì)應(yīng)，那么該列為過濾列。 根據(jù)這個(gè)方法，我們可以判斷出列A出現(xiàn)在一個(gè)等值謂詞中，這是一個(gè)足夠簡(jiǎn)單的謂詞，因此A是匹配列，列B是一個(gè)范圍謂詞，也是匹配列。而B后面的列C無法定義索引片(無法讓索引片變得更窄)，但它依舊可以參與索引片的過濾過程。 也就是說我們通過列A和列B定義了索引片的大小，而列C不能，但是在訪問表之前，依舊可以通過列C來過濾記錄，能夠減少不必要的表訪問。列C就屬于 過濾列 ，它和列A列B一樣重要。

總結(jié)：

上述WHERE子句有兩個(gè)匹配列，列A和列B，他們定義了掃描的索引片。除此之外還有一個(gè)列C作為過濾列。所以只有當(dāng)一行同時(shí)滿足這三個(gè)謂詞時(shí)才會(huì)訪問表中的數(shù)據(jù)。

如果列B的謂詞表達(dá)式是等值謂詞，那么這三個(gè)列都可以作為匹配列。

如果取消列A的謂詞表達(dá)式，那么索引片段就是整個(gè)索引的大小，列B和列C都僅僅只能用來過濾。

過濾因子

過濾因子描述的謂詞的選擇性，即表中滿足謂詞條件的記錄行數(shù)所占的比例，它主要依賴于列值的分布情況。

計(jì)算過濾因子的公式為：

結(jié)果集數(shù)量/表行的數(shù)量

比如我們的一張用戶表里有SEX這個(gè)字段，當(dāng)加入一個(gè)女性用戶，SEX=‘F’的過濾因子就會(huì)變大。

如果男性在表中占70%，那么SEX='M'的過濾因子就是70%，SEX='F'的過濾因子為30%，SEX列的最差情況下過濾因子為70%，平均過濾因子為50%。

如果男女比例一比一，那么列SEX最差情況下的過濾因子和平均過濾因子都是50%。

我們?cè)谠u(píng)估一個(gè)索引是否合適的時(shí)候，最差情況下的過濾因子比平均過濾因子更重要，因?yàn)樽畈钋闆r與最差輸入相關(guān)，即在該輸入條件下，基于特定索引的查詢將消耗最長(zhǎng)的時(shí)間。

組合謂詞的過濾因子

那我們?nèi)绾蝸碛?jì)算三組合謂詞表達(dá)式的過濾因子呢?

如果組成謂詞的列之間 非相關(guān) ，那么組合謂詞的過濾因子可以從單個(gè)謂詞的過濾因子推導(dǎo)出來。

非相關(guān)的意思是兩個(gè)謂詞的值互不影響，例如我們有一張user表，里面有"province"和"city"兩個(gè)字段，那這就是兩個(gè)相關(guān)的謂詞，因?yàn)槌鞘械闹当仨毷撬诘氖∠碌某鞘小６鳦ITY和BD(生日)就是不相關(guān)的謂詞。

比如組合謂詞 CITY = :CITY AND BD = :BD 的過濾因子等于謂詞 CITY = :CITY 和謂詞 BD = :BD 的過濾因子的乘積。

如果列CITY有2000個(gè)不同的值，列BD有2700個(gè)不同的值，那么組合謂詞的過濾因子就是： 1/2000*1/2700 。那么列組合[CITY,BD]總共有5400000個(gè)不同的值。

而對(duì)于有相關(guān)性的列，值會(huì)比這小很多。

我們?cè)谠O(shè)計(jì)索引結(jié)構(gòu)的時(shí)候，需要將SQL語句中的組合謂詞看做一個(gè)整體來評(píng)估過濾因子。

過濾因子對(duì)索引設(shè)計(jì)的影響

很顯然，需要掃描的索引片的大小對(duì)訪問路徑的性能影響至關(guān)重要。過濾因子越小，篩選出來的索引片的就越小，那就意味著訪問表的次數(shù)越少。

假設(shè)表有聯(lián)合索引 (MAKE, MODEL, YEAR)

對(duì)于sql語句:

SELECT PRICE, COLOR, DEALERNO 
FROM CAR 
WHERE MAKE = :MAKE 
 AND 
 MODEL = :MODEL 
ORDER BY PRICE 

MAKE 和 MODEL都是匹配列。如果組合謂詞的過濾因子是0.1%，那么所需要訪問的索引片大小將為整個(gè)索引的0.1%。

而對(duì)于下面這個(gè)sql語句，這個(gè)索引就不大好了：

SELECT PRICE, COLOR, DEALERNO 
FROM AUTO 
WHERE MAKE = :MAKE 
 AND 
 YEAR = :YEAR 

由于聯(lián)合索引的最左匹配原則，匹配列只有MAKE。過濾因子為1%，索引片比較大。

sql語句：

SELECT LNAME, FNAME, CNO 
FROM CUST 
WHERE SEX='M' 
 AND 
 (WEIGHT > 90 
 OR 
 HEIGHT > 190) 
ORDER BY LNAME, FNAME 

這個(gè)SQL語句查找身材高大有一定要求的男性，此時(shí)匹配謂詞只有一個(gè)SEX，過濾因子正常情況下為50%，如果表有100萬行記錄，那么索引片就有50萬行，這就是相當(dāng)厚的索引片了。

練習(xí)

思考一下為以下兩個(gè)SQL語句設(shè)計(jì)最佳的索引

SELECT LNAME, FNAME, CNO 
FROM CUST 
WHERE SEX = 'M' 
 AND 
 HEIGHT > 190 
ORDER BY LNAME, FNAME 
SELECT LNAME, FNAME, CNO 
FROM CUST 
WHERE SEX = 'M' 
 AND 
 (WHIGHT > 90 
 OR 
 HEIGHT > 190) 
ORDER BY LNAME, FNAME