推薦讀：MYSQL中的where條件，在資料庫中提取與應用淺析

原文： http://hedengcheng.com/?p=577

1        問題描述

一條SQL，在資料庫中是如何執行的呢？相信很多人都會對這個問題比較感興趣。當然，要完整描述一條SQL在資料庫中的生命周期，這是一個非常巨大的問題，涵蓋了SQL的詞法解析、文法解析、權限檢查、查詢優化、SQL執行等一系列的步驟，簡短的篇幅是絕對無能為力的。是以，本文挑選了其中的部分内容，也是我一直都想寫的一個内容，做重點介紹：

給定一條SQL，如何提取其中的where條件？where條件中的每個子條件，在SQL執行的過程中有分别起着什麼樣的作用？

通過本文的介紹，希望讀者能夠更好地了解查詢條件對于SQL語句的影響；撰寫出更為優質的SQL語句；更好地了解一些術語，例如：MySQL 5.6中一個重要的優化——Index Condition Pushdown，究竟push down了什麼？

本文接下來的内容，安排如下：

1. 簡單介紹關系型資料庫中資料的組織形式；
2. 給定一條SQL，如何提取其中的where條件；
3. 最後做一個小的總結；

2        關系型資料庫中的資料組織

關系型資料庫中，資料組織涉及到兩個最基本的結構：表與索引。表中存儲的是完整記錄，一般有兩種組織形式：堆表(所有的記錄無序存儲)，或者是聚簇索引表(所有的記錄，按照記錄主鍵進行排序存儲)。索引中存儲的是完整記錄的一個子集，用于加速記錄的查詢速度，索引的組織形式，一般均為B+樹結構。

有了這些基本知識之後，接下來讓我們建立一張測試表，為表新增幾個索引，然後插入幾條記錄，最後看看表的完整資料組織、存儲結構式怎麼樣的。(注意：下面的執行個體，使用的表的結構為堆表形式，這也是Oracle/DB2/PostgreSQL等資料庫采用的表組織形式，而不是InnoDB引擎所采用的聚簇索引表。其實，表結構采用何種形式并不重要，最重要的是了解下面章節的核心，在任何表結構中均适用)

create table t1 (a int primary key, b int, c int, d int, e varchar(20));

create index idx_t1_bcd on t1(b, c, d);

insert into t1 values (4,3,1,1,’d’);

insert into t1 values (1,1,1,1,’a’);

insert into t1 values (8,8,8,8,’h’):

insert into t1 values (2,2,2,2,’b’);

insert into t1 values (5,2,3,5,’e’);

insert into t1 values (3,3,2,2,’c’);

insert into t1 values (7,4,5,5,’g’);

insert into t1 values (6,6,4,4,’f’);

t1表的存儲結構如下圖所示(隻畫出了idx_t1_bcd索引與t1表結構，沒有包括t1表的主鍵索引)：

簡單分析一下上圖，idx_t1_bcd索引上有[b,c,d]三個字段(注意：若是InnoDB類的聚簇索引表，idx_t1_bcd上還會包括主鍵a字段)，不包括[a,e]字段。idx_t1_bcd索引，首先按照b字段排序，b字段相同，則按照c字段排序，以此類推。記錄在索引中按照[b,c,d]排序，但是在堆表上是亂序的，不按照任何字段排序。

3        SQL的where條件提取

在有了以上的t1表之後，接下來就可以在此表上進行SQL查詢了，擷取自己想要的資料。例如，考慮以下的一條SQL：

select * from t1 where b >= 2 and b < 8 and c > 1 and d != 4 and e != ‘a’;

一條比較簡單的SQL，一目了然就可以發現where條件使用到了[b,c,d,e]四個字段，而t1表的idx_t1_bcd索引，恰好使用了[b,c,d]這三個字段，那麼走idx_t1_bcd索引進行條件過濾，應該是一個不錯的選擇。接下來，讓我們抛棄資料庫的思想，直接思考這條SQL的幾個關鍵性問題：

l         此SQL，覆寫索引idx_t1_bcd上的哪個範圍？

起始範圍：記錄[2,2,2]是第一個需要檢查的索引項。索引起始查找範圍由b >= 2，c > 1決定。

終止範圍：記錄[8,8,8]是第一個不需要檢查的記錄，而之前的記錄均需要判斷。索引的終止查找範圍由b < 8決定；

2        在确定了查詢的起始、終止範圍之後，SQL中還有哪些條件可以使用索引idx_t1_bcd過濾？

根據SQL，固定了索引的查詢範圍[(2,2,2),(8,8,8))之後，此索引範圍中并不是每條記錄都是滿足where查詢條件的。例如：(3,1,1)不滿足c > 1的限制；(6,4,4)不滿足d != 4的限制。而c，d列，均可在索引idx_t1_bcd中過濾掉不滿足條件的索引記錄的。

是以，SQL中還可以使用c > 1 and d != 4條件進行索引記錄的過濾。

3        在确定了索引中最終能夠過濾掉的條件之後，還有哪些條件是索引無法過濾的？

此問題的答案顯而易見，e != ‘a’這個查詢條件，無法在索引idx_t1_bcd上進行過濾，因為索引并未包含e列。e列隻在堆表上存在，為了過濾此查詢條件，必須将已經滿足索引查詢條件的記錄回表，取出表中的e列，然後使用e列的查詢條件e != ‘a’進行最終的過濾。

在了解以上的問題解答的基礎上，做一個抽象，可總結出一套放置于所有SQL語句而皆準的where查詢條件的提取規則：

所有SQL的where條件，均可歸納為3大類：Index Key (First Key & Last Key)，Index Filter，Table Filter。

接下來，讓我們來詳細分析者3大類分别是如何定義，以及如何提取的。

l         Index Key

用于确定SQL查詢在索引中的連續範圍(起始範圍+結束範圍)的查詢條件，被稱之為Index Key。由于一個範圍，至少包含一個起始與一個終止，是以Index Key也被拆分為Index First Key和Index Last Key，分别用于定位索引查找的起始，以及索引查詢的終止條件。

Index First Key

用于确定索引查詢的起始範圍。提取規則：從索引的第一個鍵值開始，檢查其在where條件中是否存在，若存在并且條件是=、>=，則将對應的條件加入Index First Key之中，繼續讀取索引的下一個鍵值，使用同樣的提取規則；若存在并且條件是>，則将對應的條件加入Index First Key中，同時終止Index First Key的提取；若不存在，同樣終止Index First Key的提取。

針對上面的SQL，應用這個提取規則，提取出來的Index First Key為(b >= 2, c > 1)。由于c的條件為 >，提取結束，不包括d。

Index Last Key

Index Last Key的功能與Index First Key正好相反，用于确定索引查詢的終止範圍。提取規則：從索引的第一個鍵值開始，檢查其在where條件中是否存在，若存在并且條件是=、<=，則将對應條件加入到Index Last Key中，繼續提取索引的下一個鍵值，使用同樣的提取規則；若存在并且條件是 < ，則将條件加入到Index Last Key中，同時終止提取；若不存在，同樣終止Index Last Key的提取。

針對上面的SQL，應用這個提取規則，提取出來的Index Last Key為(b < 8)，由于是 < 符号，是以提取b之後結束。

2         Index Filter

在完成Index Key的提取之後，我們根據where條件固定了索引的查詢範圍，但是此範圍中的項，并不都是滿足查詢條件的項。在上面的SQL用例中，(3,1,1)，(6,4,4)均屬于範圍中，但是又均不滿足SQL的查詢條件。

Index Filter的提取規則：同樣從索引列的第一列開始，檢查其在where條件中是否存在：若存在并且where條件僅為 =，則跳過第一列繼續檢查索引下一列，下一索引列采取與索引第一列同樣的提取規則；若where條件為 >=、>、<、<= 其中的幾種，則跳過索引第一列，将其餘where條件中索引相關列全部加入到Index Filter之中；若索引第一列的where條件包含 =、>=、>、<、<= 之外的條件，則将此條件以及其餘where條件中索引相關列全部加入到Index Filter之中；若第一列不包含查詢條件，則将所有索引相關條件均加入到Index Filter之中。

針對上面的用例SQL，索引第一列隻包含 >=、< 兩個條件，是以第一列可跳過，将餘下的c、d兩列加入到Index Filter中。是以獲得的Index Filter為 c > 1 and d != 4 。

3         Table Filter

Table Filter是最簡單，最易懂，也是提取最為友善的。提取規則：所有不屬于索引列的查詢條件，均歸為Table Filter之中。

同樣，針對上面的用例SQL，Table Filter就為 e != ‘a’。

3.1 Index Key/Index Filter/Table Filter小結 

SQL語句中的where條件，使用以上的提取規則，最終都會被提取到Index Key (First Key & Last Key)，Index Filter與Table Filter之中。

Index First Key，隻是用來定位索引的起始範圍，是以隻在索引第一次Search Path(沿着索引B+樹的根節點一直周遊，到索引正确的葉節點位置)時使用，一次判斷即可；

Index Last Key，用來定位索引的終止範圍，是以對于起始範圍之後讀到的每一條索引記錄，均需要判斷是否已經超過了Index Last Key的範圍，若超過，則目前查詢結束；

Index Filter，用于過濾索引查詢範圍中不滿足查詢條件的記錄，是以對于索引範圍中的每一條記錄，均需要與Index Filter進行對比，若不滿足Index Filter則直接丢棄，繼續讀取索引下一條記錄；

Table Filter，則是最後一道where條件的防線，用于過濾通過前面索引的層層考驗的記錄，此時的記錄已經滿足了Index First Key與Index Last Key構成的範圍，并且滿足Index Filter的條件，回表讀取了完整的記錄，判斷完整記錄是否滿足Table Filter中的查詢條件，同樣的，若不滿足，跳過目前記錄，繼續讀取索引的下一條記錄，若滿足，則傳回記錄，此記錄滿足了where的所有條件，可以傳回給前端使用者。

4        結語

在讀完、了解了以上内容之後，詳細大家對于資料庫如何提取where中的查詢條件，如何将where中的查詢條件提取為Index Key，Index Filter，Table Filter有了深刻的認識。以後在撰寫SQL語句時，可以對照表的定義，嘗試自己提取對應的where條件，與最終的SQL執行計劃對比，逐漸強化自己的了解。

同時，我們也可以回答文章開始提出的一個問題：MySQL 5.6中引入的Index Condition Pushdown，究竟是将什麼Push Down到索引層面進行過濾呢？對了，答案是Index Filter。在MySQL 5.6之前，并不區分Index Filter與Table Filter，統統将Index First Key與Index Last Key範圍内的索引記錄，回表讀取完整記錄，然後傳回給MySQL Server層進行過濾。而在MySQL 5.6之後，Index Filter與Table Filter分離，Index Filter下降到InnoDB的索引層面進行過濾，減少了回表與傳回MySQL Server層的記錄互動開銷，提高了SQL的執行效率。