一、搜尋
1. 未建立索引的表格
- SQLite 中的所有表格都有 0 到多列資料，而每一列皆包含一個唯一的整數鍵（ROWID 或 INTEGER PRIMARY KEY）與內容。而每一列資料皆按照 ROWID 由小到大的順序進行儲存。
- 接下來，我們會以如下結構的 table 來說明：
CREATE TABLE FruitsForSale(
Fruit TEXT,
State TEXT,
Price REAL
);
圖1: 表格「FruitsForSale」的邏輯結構 - 請注意在此例中的「ROWID」欄位值是不連續的，但卻是有順序性的（由小而大）。ROWID 通常從 1 開始，每增加一列資料，ROWID 就會加 1。但如果某些列被刪除，就可能會有空隙發生。
- 假設你想要查詢桃子的價格，可執行如下 SQL：
SELECT price FROM FruitsForSale WHERE fruit='Peach'; - SQLite 會讀取此 table 中的每一列，並檢查 「fruit」欄位值是否為「Peach」？此過 程稱為「全表掃瞄」（full table scan），如圖 2所示。若資料量很多時，全表掃瞄的效 能就會變得很差，所以我們應盡可能避免。
圖2: 全表掃瞄（Full Table Scan）
- 一個避免「全表掃瞄」的方法是使用「ROWID」（或者 INTGER PRIMARY KEY）。例如要查詢桃子的價格，可以查詢 rowid 為 「4」的資料列：
SELECT price FROM FruitsForSale WHERE rowid=4; - 因為資料是依據 ROWID 的順序儲存於 table 中的，所以 SQLite 可以在 ROWID 欄位上使用 binary search 以找到正確的資料列。如果 table 包含了 N 筆資料列，那麼找到正確資料列的時間複雜度是 O(logN)，而非「全表掃瞄」的 O(N)。如果表內包含了 1,000 萬筆資料列，用此方法會比全表掃瞄快上 100 萬倍（N/logN =10000000/LOG(10000000, 10) = 1428571.429 ）。
圖3: 使用 ROWID 查詢
- 使用 ROWID 查詢的問題是你根本不關心「物件 4」的價格，你想知道的是「桃子」的價格，所以使用 ROWID 查詢並無濟於事。
- 如下，我們可以在「fruit」欄位上加上索引「idx1」：
CREATE INDEX idx1 ON FruitsForSale(fruit); - 如圖 4 所示，所謂的「索引」是另一張類似原來 FruitsForSale 的 表格，只是每一列的最前面是「內容」（即「fruit」欄位），後面再跟著「ROWID」欄位，並依據「內容」的順序儲存。
圖 4: fruit 欄位上的索引 - 由於 ROWID 是唯一的（unique），所以即使 fruit 欄位有可能重複， 但複合鍵「fruit+ ROWID」仍然會是唯一的。
- 就「查詢桃子價格」這個問題，我們可以利用索引設計另一個查詢計畫：
SELECT price FROM FruitsForSale WHERE fruit='Peach'; - 這個查詢會先以 binary search 在 idx1 索引上尋找「fruit='Peach'」對應的 ROWIDs ，再用這些 ROWIDs 去尋找 FruitsForSale 表格上對應的資料列，最後再取出這些資料列的 price 欄位，過程如圖 5 所示：
圖 5: 利用索引查詢桃子（Peach）的價格 - 在此例中，雖然 SQLite 必須做兩次 binary search 才能找到桃子的價格，但在一張資料列很多的 table 裡這個方法仍會比「全表掃瞄」快很多。
- 上例「fruit='Peach'」的查詢只有將結果限縮到一列資料而已。但是同樣的技巧也可用來限縮結果到多列資料。假設我們這次想查詢「Orange」的價格：
SELECT price FROM FruitsForSale WHERE fruit='Orange'; - 就本例而言，SQLite 仍只會做一次 binary search 以尋找符合「fruit='Orange'」的第一筆索引。從索引中取得對應的 ROWID 後，再使用 binary search 去原來的 table 裡尋找 ROWID 所對應的資料列、並輸出價格。但此時，DB 引擎的工作還不會結束，它會繼續前往索引中的下一列，並重複尋找「fruit='Orange'」資料列的程序。整個過程如圖 6 所示：
圖 6: 利用索引查詢柳橙（Orange）的價格 - 由於下一列通常與當前列在同一 DB 分頁上，所以繼續前往索引的下一列會比再做一次 binary search 的成本低（事實上，低到幾乎可以忽略不計）。所以這個查詢的總成本是 3 次 binary search
- 假設輸出的資料總筆數是 K，而 table 內的資料總筆數是 N，那麼一般的狀況下，執行此類查詢的成本約是 (K+1)* logN（此處的「1」代表在索引執行的1次 binary search，「K」則代表在原表格執行的 binary search）。
5. 當 WHERE 子句裡面有多個 AND 條件
- 假設你不是想查詢所有柳橙的價格，而只想查詢加州（CA, California）生產的柳橙價格，您可能會執行的查詢如下：
SELECT price FROM FruitsForSale WHERE fruit='Orange' AND state='CA'; - 如圖 7 所示，有一個方法是先找出「fruit='Orange'」的資料列，然後再將那些產地不在「加州」的資料剔除掉。因為這個方法會多做一次的 binary search，所以比較沒有效率（找到佛羅里達州（FL, Florida）出產的柳橙，然後再剔除掉）。
圖 7: 利用索引查詢加州柳橙的價格 - 假設我們也建立 state 欄位的索引：
CREATE INDEX idx2 ON FruitsForSale(state);
圖 8: state 欄位上的索引 - state 索引的作用和 fruit 索引一樣，都是一張新表格，其中有兩個欄位：state 和 ROWID，並依照 state 排序。差別只在於 idx1 的第一欄是「fruit」，而 idx2 的第一欄是「state」。
- 在我們的範例資料中，雖然 state 欄位中資料重複的現象比 fruit 欄位更多，但仍可透過「ROWID」來區分。
- 藉由 state 欄位上的 idx2 索引，SQLite 可以用另外一個方法來查詢加州柳橙的價格 — 首先找出所有在加州生產的水果，然後再把那些不是柳橙的資料列剔除：
圖 9: 利用索引查詢加州柳橙的價格 - 由 idx1 改為使用 idx2 ，會讓 SQLite 去檢驗不同的資料列，但最終都會得到相同的答案（請記得：索引並不會改變答案，只會幫助 SQLite 更快地找到答案），而且執行的工作量一樣多。所以，就本例而言， idx2 在效能上並無助益。
- 在這個例子中，不管是使用 idx1 或 idx2，最後兩個查詢所花費的時間一樣多。所以 SQLite 會選用哪一個索引呢？如果先前有執行過「ANALYZE」指令，SQLite 會依據 ANALYZE 所蒐集到的索引相關統計資訊來決定要使用哪一個索引。若 SQLite 發現使用 idx1 可將搜尋動作限縮在一筆資料列，而 idx2 會限縮到兩筆，則 SQLite 會選擇使用「idx1」（不過，本例的「fruit='Orange'」是例外）。如果兩者相等呢？SQLite 會選擇「idx1」。但如果尚未執行過「ANALYZE」指令呢？則 SQLite 會隨機選擇其中一個索引。
- 對於「WHERE 子句裡有多個 AND 條件」這類查詢（如 WHERE fruit='Orange' AND state='CA'），若希望獲得最大效能，則必須使用「多欄位索引」（而且索引中須包含所有 「AND 」條件的欄位，如：fruit 和 state）。
- 舉例來說，我們可建立如下的多欄位索引：
CREATE INDEX idx3 ON FruitsForSale(fruit, state); - 「多欄位索引」與「單一欄位」的索引一樣，都是在 ROWID 欄位前面增加內容欄位，唯一的差別只在於欄位數量比較多。 最左邊的欄位是用來排序索引之中的資料列。而第二個欄位 則用來做索引的細分（亦即當第一個欄位相同時，可再結合 此欄位進行比較）。如果還有第三或更多欄位，也是依此類 推。因為 ROWID 一定會是唯一的，所以即使內容欄位都一樣 ，索引中的每一列也都會是唯一的。
圖10: 由兩個欄位組成的索引 - 現在有了「idx3」這個多欄位索引，SQLite 執行兩次 binary search 就可以找到加州柳橙的價格了：
SELECT price FROM FruitsForSale WHERE fruit='Orange' AND state='CA';
圖11: 使用兩個欄位組成的索引進行查詢 - 因為 idx3 包含了 WHERE 子句中的兩個條件欄位，所以 SQLite 只要做一次 binary search 就可以找到加州柳橙的 ROWID，然後再到原 table 中找出對應資料列裡的價格即可。完全沒有死角，也沒有不必要的 binary search，所以這是一個比較有效率的查詢。
- 另外，值得注意的是：因為 idx3 也涵蓋了 idx1 的所有資訊，所以其實我們也可以不需要 idx1 了。而「查詢桃子價格」的問題其實也透過 idx3 來就可以解決，SQLite 會自動忽略 idx3 中的「state」欄位：
SELECT price FROM FruitsForSale WHERE fruit='Peach';
圖12: 使用兩欄索引來進行單欄查詢 - 因此，以上這個例子說明了一個很重要的經驗法則：絕對不要在 DB 裡建立兩個前置欄位相同的索引！請將欄位比較少的索引移除，因為 SQLite 仍然可以透過比較長的索引進行有效查詢。
7. 涵蓋式索引（Covering indecies）
- 「兩欄位索引」可提高「查詢加州柳橙價格」問題的處理效率。但如果把「price」欄位也建到索引裡面，透過這個「三欄索引」， SQLite 的查詢效率會更好：
CREATE INDEX idx4 ON FruitsForSale(fruit, state, price);
圖13: 涵蓋式索引（Covering Index） - 這個新的索引包含了對「FruitsForSale」進行 查詢時要用到的所有欄位 — 搜尋條件與輸出欄位 。所以我們稱這類索引為「涵蓋式索引」 （Covering Index）。因為所需要的資訊全都包含 在這個索引當中了，所以 SQLite 不需要再到原表 格裡查詢價格：
SELECT price FROM FruitsForSale WHERE fruit='Orange' AND state='CA';
圖14: 使用涵蓋式索引的查詢 - 因此，藉由在每列索引後方再加上一個用於輸出結果的欄位，就可以避免對原表格的參照，也減少了一半的 binary search 次數。
- 這是一個常數因子（constant-factor）的性能改善（大約增加一倍的速度）。另一方面，這也是一種優化。在剛開始為 table 建立索引時，兩倍與一百萬倍的性能提升很難看出來。而且就大部分的查詢來說，1 毫秒與 2 毫秒之間的差異也很難被發現。
- 「涵蓋式索引」也是「多欄位索引」的一種。
8. 當 WHERE 子句裡面有多個 OR 條件
- 由於多欄位索引只會在「WHERE 子句裡有多個 AND 條件」的狀況下發揮作用，所以 idx3 和 idx4 也只有在搜尋「柳橙 AND 所有在加州生產的水果」的物件時有用。但是如果我們想查詢「柳橙 OR 所有在加州生產的水果」的物件時，這兩個索引就沒有用了：
SELECT price FROM FruitsForSale WHERE fruit='Orange' OR state='CA'; - 當「WHERE 子句裡有多個 OR 條件」時，SQLite 會分別檢驗每個 OR 條件，並試著使用索引去找出每個條件裡頭相關的 ROWIDs，然後再用這些 ROWIDs 的 UNION 操作去找出最終結果。下圖說明了這個過程：
圖15: 使用 OR 限制式的查詢 - 如上圖所示，SQLite 會先找出所有的 ROWID，然後用 UNION 操作將這些 ROWID 合併起來，最後再到原始表格中去搜尋這些 ROWID。而事實上，在 rowid 的搜尋之間還穿插著 ROWID 的計算。事實上，SQLite 每次會使用一個索引（idx1 和 idx3）來尋找 ROWID，找到以後就會記下來，並自動避開之前已經找到的 ROWID。這是程式實作細節，所以上圖並不完全準確，在此只是提供給讀者瞭解大致的流程。而這樣的技巧稱為「OR-by-UNION」。
- 若要讓「OR-by-UNION」技巧發揮作用，一定要透過索引來解析 WHERE 裡頭的 OR 子句。如果所有 OR 字句裡面的欄位都沒有建立索引，那麼 SQLite 就會使用「全表掃瞄」來搜尋。而且也只會在一個步驟內就把所有結果都從原始表格中找出來，而不會再混合使用 UNION 操作與 binary search。
- 有人可能會想到：既然 SQLite 可以透過多個索引與 UNION 操作來提升這類查詢的效能，那應該也能用多個索引與 INTERSECT 操作來提升「WHERE 子句裡有多個 AND 條件」查詢的效能吧！？有許多資料庫引擎確實也都是這麼做的。但是跟只使用單一索引相比，這個方法所提升的效能很小，所以 SQLite 目前並未實作此技術。或許將來SQLite 的新版會支援此項「AND-by-INTERSECT」技術。
- SQLite 除了可以利用索引來加快查詢速度之外，也可用索引來處理查詢中的「ORDER BY」子句。換句話說，索引可以用在「排序」與「搜尋」的加速。
- 當沒有合適的索引可用時，SQLite 在處理一個含有「ORDER BY」子句的查詢，必須把排序視為另一個單獨的步驟。考慮以下狀況：
SELECT * FROM FruitsForSale ORDER BY fruit; - SQLite 會先蒐集所有的查詢結果，然後再透過「排序元件」（sorter）來執行輸出：
圖16: 不使用索引來排序 - 若輸出的結果列數是 K，則排序的時間複雜度是 O(KlogK)。如果 K 很小，那排序的時間就不是影響效能主要關鍵。但若是像上面這個查詢，那 SQLite 用在排序的時間的時間會遠大於「全表掃瞄」。再者，由於整個輸出都是先累積在一塊暫存空間（視編譯與執行時期的設定而定，有可能是主記憶體或磁碟），所以這意味著 SQLite 要完成這個查詢，還必須要先有一塊很大的暫存空間才行。
- 因為排序的成本很高，所以 SQLite 會盡力地將 ORDER BY 子句轉換為 no-ops（不進行任何操作，組合語言的一種指令）。若未指定輸出結果要依據特定順序顯示，SQLite 就不會進行任何排序工作。舉例來說，如果您要求依照 ROWID 順序輸出， SQLite 就不會進行任何排序工作：
SELECT * FROM FruitsForSale ORDER BY rowid;
圖17: 依據 rowid 來排序 - 您也可以像下面這樣指定反向的排序方式：
SELECT * FROM FruitsForSale ORDER BY rowid DESC;
SQLite 仍將忽略排序步驟。但為了讓輸出結果依據正確順序顯示，SQLite 將會從表格尾端一直掃瞄到表格開頭，而不是像圖 17 那樣，從開頭掃到結尾。
- 依據 ROWID 來排序查詢輸出結果並沒什麼用處，通常我們會希望依據某個欄位來排列輸出的結果。
- 如果在「ORDER BY」子句中的欄位有索引可用，SQLite 就會利用該索引進行排序。假設我們希望所有的項目都能依據「fruit」欄位來排序：
SELECT * FROM FruitsForSale ORDER BY fruit;
圖18: 利用索引來排序 - 那麼 SQLite 就會依據 fruit 的順序從「idx1」索引的開頭掃瞄到尾端以找出每一項目的 ROWID。然後再針對每筆 ROWID 執行 binary search，並輸出該列資料。
- 與「不利用索引來排序」相比，這個方式的時間複雜度同樣也是 O(NlogN)，所以並沒有比較節省時間！
- SQLite 使用「以成本為基礎」（cost-based ）的 query planner。所以當同一查詢有多種解決方式時，SQLite 會先試著估計每一個查詢計畫的總時間，再從中選出 cost 最小的查詢計畫。
- 成本的計算主要來自於估計花費時間（estimated time），所以就這個例子來說，SQLite 可能會依據表格大小、WHERE 子句中的限制條件或諸如此類的因素來選擇。但是，一般狀況下，SQLite 會選用「利用索引來排序」（indexed sort）的方式。因為在開始排序之前， SQLite 不需要先將整個結果集都儲存在暫存空間，所以只需使用很少的暫存空間。
- 查詢時若能利用「涵蓋式索引」（covering index），便可避免多個 ROWID 的查詢與以及大幅減少查詢成本。
圖19: 利用涵蓋式索引來排序 - 藉由「涵蓋式索引」，SQLite 只需要從索引的一端走到另一端並輸出結果就可以了，而不需配置一大塊緩衝區以保留結果集。
三、同時進行搜尋與排序
1. 使用多欄索引- 前面我們分別就「搜尋」與「排序」兩個主題進行了討論，但實務上，同一時間執行搜尋與排序會是比較常見的狀況。很幸運地，SQLite 有可能使用一個索引就能辦到。
- 假設我們希望找出所有柳橙的價格、並依照產地的州別（state）排序，可以使用如下查詢：
SELECT price FROM FruitForSale WHERE fruit='Orange' ORDER BY state; - 此查詢中包含了 WHERE 子句與 ORDER 子句，使用兩欄索引 idx3 就可達成同時搜尋與排序的需求。
圖20: 利用多欄索引進行搜尋和排序 - SQLite 會先在索引上從頭到尾做一次 binary search 以找出符合「fruit='Orange'」的索引列（因為「fruit」是索引最左邊的欄位，而且其中資料也是依據這個欄位做排列的，所以相同的「fruit」列會被排在一起），接著再用這些 ROWID 到原始表格中做 binary search ，以找出價格。
- 您應該注意到了在上圖裡並沒有出現「排序元件」（sorter），這是因為「ORDER BY」子句已經變成 no-op 了。因為這個查詢是要求輸出結果必須依據「state」欄位來排序，而「state」欄位剛好是索引中「fruit」後面的欄位。這個索引本來就是先依據「state」排序、再依據「fruit」欄位排序過的，所以 SQLite 只需單純地由上而下進行掃瞄就好了。
2. 使用覆蓋式索引
- 「覆蓋式索引」也可用於同時搜尋與排序。考慮以下查詢：
SELECT * FROM FruitForSale WHERE fruit='Orange' ORDER BY state;
圖21: 利用覆蓋式索引進行搜尋和排序 - 同樣地，SQLite 會先在覆蓋式索引上由上而下進行一次 binary search 以找出滿足 WHERE 子句要求的索引列。而由於這個索引本來就是先依據「state」排序、再依據「fruit」欄位排序過的，所以其結果就可以直接拿來使用（輸出）。因此這個查詢是相當有效率的。
- SQLite 也將類似技巧應用在「降冪 ORDER BY」（descending ORDER BY）上：
SELECT * FROM fruitforsale WHERE fruit='Orange' ORDER BY state DESC; - 除了掃瞄的方向從「由上而下」改成「由下而上」，SQLite 按照同樣的基本邏輯，將輸出結果依據「state」欄位降冪排序後輸出。
沒有留言:
張貼留言