SQLite 中的大部分表格都包含零或多列具有唯一整數鍵 (即 rowid 或 INTEGER PRIMARY KEY) 的列，後接內容。(例外為 WITHOUT ROWID 表格。) 這些列會依 rowid 增加的順序以邏輯方式儲存。例如，本文使用名為「FruitsForSale」的表格，將各種水果與其生長州別和市場單價關聯起來。架構如下：

CREATE TABLE FruitsForSale(
  Fruit TEXT,
  State TEXT,
  Price REAL
);

如果有一些 (任意的) 資料，則此類表格可能會以圖 1 所示的方式在磁碟上以邏輯方式儲存

圖 1：表格「FruitsForSale」的邏輯配置

在此範例中，rowid 並非連續的，但它們是有序的。SQLite 通常會建立從 1 開始的 rowid，並隨著每個新增列而增加 1。但是，如果刪除列，則順序中可能會出現間隙。而且，如果需要，應用程式可以控制所指定的 rowid，以便不一定要在底部插入列。但是，無論發生什麼情況，rowid 始終都是唯一的，並且嚴格按照遞增順序排列。

假設您想要查詢桃子的價格。查詢如下：

SELECT price FROM fruitsforsale WHERE fruit='Peach';

為了滿足此查詢，SQLite 會從表格中讀取每一列，檢查「fruit」欄是否有「Peach」的值，如果有，則輸出該列的「price」欄。此程序由下方的圖 2 說明。此演算法稱為全表掃描，因為必須讀取和檢查表格的全部內容才能找到感興趣的那一列。對於只有 7 列的表格，全表掃描是可以接受的，但如果表格包含 7 百萬列，則全表掃描可能會讀取數 MB 的內容才能找到一個 8 位元組的數字。因此，通常會嘗試避免全表掃描。

圖 2：全表掃描

1.2. 以 Rowid 查詢

避免全表掃描的一種技術是透過 rowid（或等效的 INTEGER PRIMARY KEY）查詢。若要查詢桃子的價格，可以查詢 rowid 為 4 的項目

SELECT price FROM fruitsforsale WHERE rowid=4;

由於資訊是以 rowid 順序儲存在資料表中，因此 SQLite 可以使用二元搜尋找出正確的列。如果資料表包含 N 個元素，查詢所需的時間與 logN 成正比，而不是像全表掃描那樣與 N 成正比。如果資料表包含 1000 萬個元素，這表示查詢速度約為 N/logN，也就是快了約 100 萬倍。

圖 3：以 Rowid 查詢

1.3. 以索引查詢

以 rowid 查詢資訊的問題在於，您可能不關心「項目 4」的價格，而是想知道桃子的價格。因此，rowid 查詢沒有幫助。

若要提高原始查詢的效率，我們可以在「fruitsforsale」資料表的「fruit」欄位上新增索引，如下所示

CREATE INDEX Idx1 ON fruitsforsale(fruit);

索引是另一個與原始「fruitsforsale」表格相似的表格，但內容（此例中為水果欄）儲存在 rowid 之前，且所有列都依內容順序排列。圖 4 提供 Idx1 索引的邏輯檢視。「水果」欄是主要鍵，用於排序表格的元素，而「rowid」是次要鍵，用於在兩個或多個列具有相同「水果」時打破平手。在範例中，rowid 必須用作「橘子」列的平手打破者。請注意，由於 rowid 在原始表格的所有元素中始終都是唯一的，因此「水果」後接「rowid」的複合鍵在索引的所有元素中都是唯一的。

圖 4：水果欄的索引

這個新索引可用於為原始「桃子的價格」查詢實作更快的演算法。

SELECT price FROM fruitsforsale WHERE fruit='Peach';

查詢會先對 Idx1 索引執行二元搜尋，以尋找水果='桃子'的項目。SQLite 可以對 Idx1 索引執行此二元搜尋，但無法對原始 FruitsForSale 表格執行，因為 Idx1 中的列依「水果」欄排序。在 Idx1 索引中找到水果='桃子'的列後，資料庫引擎可以萃取該列的 rowid。然後，資料庫引擎會對原始 FruitsForSale 表格執行第二次二元搜尋，以尋找包含水果='桃子'的原始列。SQLite 接著可以從 FruitsForSale 表格中的列萃取價格欄的值。此程序由圖 5 說明。

圖 5：桃子價格的索引查詢

SQLite 必須執行兩次二元搜尋才能使用上述方法找到桃子的價格。但對於列數眾多的表格而言，這仍然比執行完整表格掃描快很多。

1.4. 多重結果列

在先前的查詢中，fruit='Peach' 約束將結果縮小到單一列。但即使取得多重列，相同的技術仍然有效。假設我們查詢柳丁的價格，而不是桃子的價格

SELECT price FROM fruitsforsale WHERE fruit='Orange'

圖 6：柳丁價格的索引查詢

在這種情況下，SQLite 仍然執行單一二元搜尋，以找出索引中 fruit='Orange' 的第一個項目。然後，它從索引中萃取 rowid，並使用該 rowid 透過二元搜尋查詢原始表格項目，並從原始表格中輸出價格。但資料庫引擎並未停止，而是進到索引的下一列，為下一個 fruit='Orange' 項目重複此程序。進到索引（或表格）的下一列，比執行二元搜尋便宜許多，因為下一列通常位於與目前列相同的資料庫頁面上。事實上，進到下一列的成本與二元搜尋相比非常便宜，因此我們通常會忽略它。因此，我們估計此查詢的總成本為 3 次二元搜尋。如果輸出的列數為 K，而表格中的列數為 N，則一般而言，執行查詢的成本與 (K+1)*logN 成正比。

1.5. 多重 AND 連接的 WHERE 子句詞彙

接著，假設您想要查詢的不只是任何柳丁的價格，而是特別是加州種植的柳丁。適當的查詢如下

SELECT price FROM fruitsforsale WHERE fruit='Orange' AND state='CA'

圖 7：加州柳丁的索引查詢

對於此查詢，一種方法是使用 WHERE 子句中的 fruit='Orange' 詞彙來找出所有與橘子相關的列，然後透過排除來自加州以外州別的列來過濾這些列。此程序如上方的圖 7所示。在大部分情況下，這是一個完全合理的做法。是的，資料庫引擎確實必須對稍後被排除的佛羅里達橘子列執行額外的二元搜尋，因此其效率不如我們所希望的那麼高，儘管對於許多應用程式而言，其效率已足夠。

假設除了「fruit」上的索引之外，還有一個「state」上的索引。

CREATE INDEX Idx2 ON fruitsforsale(state);

圖 8：州欄位上的索引

「state」索引的作用方式與「fruit」索引相同，它是一個新表格，在 rowid 之前有一個額外的欄位，並以該額外欄位作為主鍵進行排序。唯一的差別在於，在 Idx2 中，第一個欄位是「state」，而不是像 Idx1 那樣是「fruit」。在我們的範例資料集中，「state」欄位有更多重複，因此有更多重複的項目。關聯仍使用 rowid 來解決。

使用「state」上的新 Idx2 索引，SQLite 有另一個選項來查詢加州橘子的價格：它可以查詢包含來自加州的水果的每一列，並過濾出不是橘子的那些列。

圖 9：加州橘子的索引查詢

使用 Idx2 而不是 Idx1 會導致 SQLite 檢查不同的列組，但最終會得到相同的答案（這非常重要 - 請記住索引不應改變答案，而只能協助 SQLite 更快取得答案），而且會執行相同數量的作業。因此，在此情況下，Idx2 索引並未有助於效能。

在我們的範例中，最後兩個查詢花費的時間相同。因此，SQLite 會選擇哪個索引，Idx1 或 Idx2？如果已對資料庫執行 ANALYZE 指令，讓 SQLite 有機會收集可用索引的統計資料，則 SQLite 會知道 Idx1 索引通常會將搜尋範圍縮小至單一項目（我們的範例 fruit='Orange' 是此規則的例外），而 Idx2 索引通常只會將搜尋範圍縮小至兩列。因此，如果其他條件相同，SQLite 會選擇 Idx1，希望將搜尋範圍縮小至最少數量的列。此選擇僅因 ANALYZE 提供的統計資料而可能。如果尚未執行 ANALYZE，則選擇使用哪個索引是任意的。

1.6. 多欄索引

若要從 WHERE 子句中包含多個 AND 連接詞的查詢中取得最佳效能，您確實需要一個多欄索引，其欄位包含每個 AND 詞彙。在此情況下，我們在 FruitsForSale 的「fruit」和「state」欄位上建立新的索引

CREATE INDEX Idx3 ON FruitsForSale(fruit, state);

圖 1：雙欄索引

多欄索引遵循與單欄索引相同的模式；索引欄位會新增在 rowid 之前。唯一的差異在於現在新增多個欄位。最左邊的欄位是主要鍵，用於排序索引中的列。第二個欄位用於打破最左邊欄位的平手。如果有第三個欄位，它會用於打破前兩個欄位的平手。索引中的所有欄位以此類推。由於 rowid 保證唯一，即使兩列的所有內容欄位相同，索引的每一列都會是唯一的。我們的範例資料中不會發生這種情況，但有一個情況（水果='橘子'）第一欄位平手，必須由第二欄位打破。

有了新的多欄 Idx3 索引，SQLite 現在可以使用只有 2 個二元搜尋來找出加州橘子的價格

SELECT price FROM fruitsforsale WHERE fruit='Orange' AND state='CA'

圖 11：使用雙欄索引進行查詢

在 WHERE 子句約束的兩個欄位上建立 Idx3 索引後，SQLite 可以對 Idx3 執行單一二元搜尋，以找出加州橘子的 rowid，然後對原始表格執行單一二元搜尋，以找出該項目的價格。沒有死胡同，也沒有浪費二元搜尋。這是一個更有效率的查詢。

請注意，Idx3 包含與原始 Idx1 相同的所有資訊。因此，如果我們有 Idx3，我們就不再需要 Idx1。只要忽略 Idx3 的「state」欄位，就可以使用 Idx3 來滿足「桃子的價格」查詢

SELECT price FROM fruitsforsale WHERE fruit='Peach'

圖 12：在多欄索引上進行單欄查詢

因此，一個不錯的經驗法則就是，資料庫架構中絕不應該包含兩個索引，其中一個索引是另一個索引的前綴。刪除具有較少欄位的索引。SQLite 仍能使用較長的索引進行有效的查詢。

1.7. 覆蓋索引

透過使用兩欄位索引，讓「加州柳丁價格」查詢變得更有效率。但 SQLite 可以透過包含「價格」欄位的三欄位索引，讓效率更高

CREATE INDEX Idx4 ON FruitsForSale(fruit, state, price);

圖 13：覆蓋索引

這個新索引包含查詢使用的所有 FruitsForSale 表格原始欄位，包括搜尋詞和輸出。我們稱之為「覆蓋索引」。由於覆蓋索引包含所有所需資訊，因此 SQLite 永遠不需要查詢原始表格就能找到價格。

SELECT price FROM fruitsforsale WHERE fruit='Orange' AND state='CA';

圖 14：使用覆蓋索引的查詢

因此，透過在索引尾端新增額外的「輸出」欄位，可以避免參照原始表格，進而將查詢的二元搜尋數量減半。這是一個效能的常數因子改善（速度大約提升一倍）。但另一方面，這也只是一個改良；兩倍的效能提升遠不及表格第一次建立索引時所見的百萬倍提升。而且對於大多數的查詢而言，1 微秒和 2 微秒之間的差異不太可能被察覺。

1.8. WHERE 子句中的 OR 連接詞

多欄索引僅在查詢的 WHERE 子句中的約束條件以 AND 連接時才有效。因此，當搜尋同時為橘子和在加州種植的項目時，Idx3 和 Idx4 會有所幫助，但如果我們想要所有為橘子或在加州種植的項目，這兩個索引都不會那麼有用。

SELECT price FROM FruitsForSale WHERE fruit='Orange' OR state='CA';

當在 WHERE 子句中遇到以 OR 連接的條件時，SQLite 會分別檢查每個 OR 條件，並嘗試使用索引來尋找與每個條件相關聯的 rowid。然後，它會採用結果 rowid 集合的聯集來找出最終結果。下圖說明了這個程序

圖 15：具有 OR 約束條件的查詢

上方的圖表暗示 SQLite 會先計算所有 rowid，然後在開始對原始表格執行 rowid 查詢之前，使用聯集運算將它們組合起來。實際上，rowid 查詢會穿插在 rowid 計算中。SQLite 會一次使用一個索引來尋找 rowid，同時記住它之前看過的 rowid，以避免重複。不過，那只是一個實作細節。儘管圖表並非 100% 準確，但它提供了正在發生的事情的良好概觀。

為了讓上面顯示的 OR-by-UNION 技術有用，必須有一個索引可用來解析 WHERE 子句中的每個 OR 連接條件。如果甚至一個 OR 連接條件沒有索引，則必須執行完整的表格掃描才能找到由一個條件產生的 rowid，如果 SQLite 必須執行完整的表格掃描，它也可以在原始表格上執行，並在單次傳遞中取得所有結果，而無需處理聯集運算和後續的二元搜尋。

可以看出，也可以使用 OR-by-UNION 技術，在 WHERE 子句有 AND 連接的詞彙的查詢中使用多個索引，方法是在聯集的位置使用交集運算子。許多 SQL 資料庫引擎都會這樣做。但相較於只使用單一索引，效能提升很小，因此 SQLite 目前尚未實作此技術。不過，未來的 SQLite 版本可能會增強支援 AND-by-INTERSECT。

2. 排序

SQLite（就像其他所有 SQL 資料庫引擎）也可以使用索引來滿足查詢中的 ORDER BY 子句，除了加速查詢。換句話說，索引可以用於加速排序和搜尋。

當沒有適當的索引時，必須將包含 ORDER BY 子句的查詢當作一個獨立的步驟來排序。考慮這個查詢

SELECT * FROM fruitsforsale ORDER BY fruit;

SQLite 會透過收集查詢的所有輸出，然後將該輸出透過排序器來處理。

圖 16：沒有索引的排序

如果輸出列的數量是 K，則排序所需的時間與 KlogK 成正比。如果 K 很小，排序時間通常不是一個因素，但在如上方的查詢中，其中 K==N，排序所需的時間會遠大於執行完整資料表掃描所需的時間。此外，整個輸出會累積在暫存儲存空間中（根據不同的編譯時間和執行時間設定，可能是主記憶體或磁碟），這表示需要大量的暫存儲存空間才能完成查詢。

2.1. 依照 Rowid 排序

由於排序可能會很耗費資源，因此 SQLite 會努力將 ORDER BY 子句轉換成無操作。如果 SQLite 判斷輸出會自然出現在指定的順序中，則不執行排序。因此，例如，如果您要求以 rowid 順序輸出，則不會執行排序

SELECT * FROM fruitsforsale ORDER BY rowid;

圖 17：依據 Rowid 排序

您也可以像這樣要求反向排序

SELECT * FROM fruitsforsale ORDER BY rowid DESC;

SQLite 仍會省略排序步驟。但為了讓輸出以正確順序顯示，SQLite 會從尾端開始進行資料表掃描，並朝向開頭進行，而不是像圖 17 所示從開頭開始朝向尾端進行。

2.2. 依據索引排序

當然，依據 rowid 排序查詢輸出很少有用。通常會想要依據其他欄位排序輸出。

如果 ORDER BY 欄位有可用的索引，則可以使用該索引進行排序。考慮依據「水果」排序所有品項的要求

SELECT * FROM fruitsforsale ORDER BY fruit;

圖 18：使用索引排序

Idx1 索引從上到下掃描（或如果使用「ORDER BY fruit DESC」則從下到上掃描），以依據水果尋找每個品項的 rowid。然後，對於每個 rowid，執行二元搜尋來查詢並輸出該列。這樣一來，輸出會以要求的順序顯示，而無需收集整個輸出並使用單獨的步驟進行排序。

但這真的可以節省時間嗎？原始無索引排序中的步驟數與 NlogN 成正比，因為這是排序 N 列所需的時間。但當我們在此所示範中使用 Idx1 時，我們必須執行 N 次 rowid 查詢，每次查詢需要 logN 時間，因此 NlogN 的總時間是一樣的！

SQLite 使用基於成本的查詢規劃器。當有兩種或更多種方法可以解決相同的查詢時，SQLite 會嘗試估計使用每個計畫執行查詢所需的時間總量，然後使用估計成本最低的計畫。成本主要是從估計時間計算出來的，因此這個案例可能會根據表格大小和 WHERE 子句約束的可用性等因素而有所不同。但一般來說，索引排序可能會被選中，因為它不需要在排序前將整個結果集累積在暫存儲存區中，因此使用較少的暫存儲存區。

2.3. 使用覆蓋索引排序

如果覆蓋索引可用於查詢，則可以避免多重 rowid 查詢，而且查詢成本會大幅下降。

圖 19：使用覆蓋索引排序

使用覆蓋索引，SQLite 可以從一端走到另一端，並在與 N 成正比的時間內傳送輸出，而無需分配大型緩衝區來儲存結果集。

3. 同時搜尋和排序

前述討論將搜尋和排序視為兩個獨立的主題。但在實際上，通常需要同時搜尋和排序。幸運的是，可以使用單一索引來執行此操作。

3.1. 使用多欄索引搜尋和排序

假設我們想要找出所有種類的柳丁價格，並依據生長州別排序。查詢如下

SELECT price FROM fruitforsale WHERE fruit='Orange' ORDER BY state

查詢包含 WHERE 子句中的搜尋限制和 ORDER BY 子句中的排序順序。搜尋和排序可以使用雙欄索引 Idx3 同時完成。

圖 20：使用多欄索引搜尋和排序

查詢對索引執行二元搜尋，以找出具有 fruit='Orange' 的列子集。（因為 fruit 欄位是索引的最左欄位，且索引的列以排序順序排列，所以所有此類列都會相鄰。）然後，它從上到下掃描相符的索引列，以取得原始資料表的 rowid，並對每個 rowid 對原始資料表執行二元搜尋以找出價格。

您會注意到，在上述圖表中任何地方都沒有「排序」方塊。查詢的 ORDER BY 子句已變成無作用運算。這裡不需要進行任何排序，因為輸出順序是依據 state 欄位，而 state 欄位剛好也是索引中 fruit 欄位之後的第一個欄位。因此，如果我們從上到下掃描具有 fruit 欄位相同值的索引項目，這些索引項目保證會依據 state 欄位排序。

3.2. 使用覆蓋索引進行搜尋和排序

也可以使用覆蓋索引同時進行搜尋和排序。考量下列內容

SELECT * FROM fruitforsale WHERE fruit='Orange' ORDER BY state

圖 21：使用覆蓋索引進行搜尋和排序

與之前一樣，SQLite 對滿足 WHERE 子句的覆蓋索引中的列範圍執行單一二進制搜尋，從上到下進行掃描以取得所需的結果。滿足 WHERE 子句的列保證相鄰，因為 WHERE 子句是索引最左邊列的等式約束。透過從上到下掃描匹配的索引列，輸出保證會依據狀態排序，因為狀態列就在水果列的正右方。因此，產生的查詢非常有效率。

SQLite 可以對遞減 ORDER BY 執行類似的技巧

SELECT * FROM fruitforsale WHERE fruit='Orange' ORDER BY state DESC

遵循相同的基礎演算法，但這次從下到上掃描索引的匹配列，而不是從上到下，這樣狀態就會以遞減順序顯示。

3.3. 使用索引進行部分排序（又稱區塊排序）

有時只能使用索引滿足 ORDER BY 子句的一部分。例如，考慮以下查詢

SELECT * FROM fruitforsale ORDER BY fruit, price

如果使用覆蓋索引進行掃描，「水果」列會自然以正確順序顯示，但當兩個或多個列有相同水果時，價格可能會亂序。發生這種情況時，SQLite 會執行許多小排序，針對每個不同的水果值進行一次排序，而不是一次大型排序。下方的圖 22 說明了這個概念。

圖 22：依索引進行部分排序

在這個範例中，不是對 7 個元素進行單一排序，而是對每個元素進行 5 次排序，並對 fruit=='Orange' 的情況進行 1 次 2 個元素的排序。

執行許多較小的排序而不是單一大型排序的優點如下

多個小型排序整體上使用的 CPU 週期比單一大型排序少。
每個小型排序獨立執行，表示任何時間點都只需要在暫時儲存中保留較少資訊。
ORDER BY 中已因索引而處於正確順序的那些欄位可以從排序鍵中省略，進一步減少儲存需求和 CPU 時間。
當每個小型排序完成時，輸出列可以傳回應用程式，而且遠早於表狀掃描完成的時間點。
如果存在 LIMIT 子句，則有可能避免掃描整個表狀。

由於這些優點，SQLite 始終嘗試使用索引進行部分排序，即使無法按索引進行完整排序。

4. WITHOUT ROWID 表狀

上述的基本原則適用於一般 rowid 表狀和 WITHOUT ROWID 表狀。唯一的差別是，作為表狀鍵並顯示為索引中最右側項目的 rowid 欄位已由 PRIMARY KEY 取代。

此頁面最後修改於 2022-10-26 13:30:36 UTC