數據庫索引的優化及SQL處理過程

NO IMAGE

想要設計出好的索引,首先必須瞭解SQL語句在數據庫服務器中的處理過程,本文介紹數據庫索引設計與優化中幾個對索引優化非常重要的概念。

謂詞

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

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

上面這個WHERE子句有三個簡單謂詞:

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

也可以認為是兩個組合謂詞:

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

優化器及訪問路徑

關係型數據庫的一大優勢就是,用戶無須關係數據的訪問方式。其訪問路徑是由DBMS的一個組件,即優化器來確定的。優化器是SQL處理過程的核心

這裡以mysql為例展示一個簡單的mysql服務器邏輯結構

數據庫索引的優化及SQL處理過程

在圖中我們可以看到優化器的位置。

在SQL語句能夠被真正執行之前,優化器必須首先確定如何訪問數據。比如mysql會解析查詢並創建解析樹,然後對其進行各種優化,包括決定選擇合適的索引,決定表的讀取順序。

謂詞表達式是索引設計的主要入手點。如果一個索引能夠滿足SELECT查詢語句的所有謂詞表達式,那麼優化器就很有可能建立起一個高效的訪問路徑。

索引片及匹配列

當索引時以B+樹的形式組織,如果有謂詞表達式WHERE A > 100 AND A < 110,那麼查詢到的葉子節點的範圍會最終為下圖:

數據庫索引的優化及SQL處理過程

圖的左邊是索引的一個窄片段,我們稱這個片段為索引片。這個片段會被順序掃描,上面索引行的值在100到110之間,相應的錶行將通過同步讀從表(也可能在緩衝池)中讀取。

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

索引過濾及過濾列

並不是所有的索引列都能夠定義索引片的大小。有時候,列可能既存在於WHERE子句中,也存在於索引中,但這個列卻不能參與索引片的定義,舉個例子。
表上有一聯合索引(A,B,C,D),有如下sql語句:

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

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

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

總結:

上述WHERE子句有兩個匹配列,列A和列B,他們定義了掃描的索引片。除此之外還有一個列C作為過濾列。所以只有當一行同時滿足這三個謂詞時才會訪問表中的數據。

如果列B的謂詞表達式是等值謂詞,那麼這三個列都可以作為匹配列。

如果取消列A的謂詞表達式,那麼索引片段就是整個索引的大小,列B和列C都僅僅只能用來過濾。

過濾因子

過濾因子描述的謂詞的選擇性,即表中滿足謂詞條件的記錄行數所佔的比例,它主要依賴於列值的分佈情況。

計算過濾因子的公式為:

結果集數量/錶行的數量

比如我們的一張用戶表裡有SEX這個字段,當加入一個女性用戶,SEX=‘F’的過濾因子就會變大。

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

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

數據庫索引的優化及SQL處理過程

我們在評估一個索引是否合適的時候,最差情況下的過濾因子比平均過濾因子更重要,因為最差情況與最差輸入相關,即在該輸入條件下,基於特定索引的查詢將消耗最長的時間。

組合謂詞的過濾因子

那我們如何來計算三組合謂詞表達式的過濾因子呢?

如果組成謂詞的列之間非相關,那麼組合謂詞的過濾因子可以從單個謂詞的過濾因子推導出來。

非相關的意思是兩個謂詞的值互不影響,例如我們有一張user表,裡面有”province”和”city”兩個字段,那這就是兩個相關的謂詞,因為城市的值必須是他所在的省下的城市。而CITY和BD(生日)就是不相關的謂詞。

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

如果列CITY有2000個不同的值,列BD有2700個不同的值,那麼組合謂詞的過濾因子就是:1/2000*1/2700。那麼列組合[CITY,BD]總共有5400000個不同的值。

數據庫索引的優化及SQL處理過程

而對於有相關性的列,值會比這小很多。

我們在設計索引結構的時候,需要將SQL語句中的組合謂詞看做一個整體來評估過濾因子。

過濾因子對索引設計的影響

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

假設表有聯合索引
(MAKE, MODEL, YEAR)

對於sql語句:

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

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

數據庫索引的優化及SQL處理過程

而對於下面這個sql語句,這個索引就不大好了:

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

由於聯合索引的最左匹配原則,匹配列只有MAKE。過濾因子為1%,索引片比較大。

數據庫索引的優化及SQL處理過程

sql語句:

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

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

練習

思考一下為以下兩個SQL語句設計最佳的索引

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

相關文章

[譯]9行JavaScript代碼計算圓周率一百萬位

從零開始開發IM(即時通訊)服務端(二)

從零開始開發IM(即時通訊)服務端

MySQL索引的原理,B+樹、聚集索引和二級索引的結構分析