SQLite查詢優化

文章目錄

- 1. 引言
- 2. WHERE子句分析
- - 2.1. 索引項使用示例
- 3. BETWEEN優化
- 4. OR優化
- - 4.1. 將OR連接的約束轉換為IN運算符
  - 4.2. 分別評估OR約束并取結果的并集
- 5. LIKE優化
- 6. 跳躍掃描優化
- 7. 連接
- - 7.1. 手動控制連接順序
  - - 7.1.1. 使用 SQLITE_STAT 表手動控制查詢計劃

1. 引言

給定一個SQL語句，可能有數十種、數百種，甚至數千種方法來實現該語句，這取決于語句本身的復雜性和底層數據庫模式的復雜性。查詢計劃的任務是選擇最小化磁盤I/O和CPU開銷的算法。

2. WHERE子句分析

在分析之前，進行以下轉換，將所有的連接約束轉移到WHERE子句中：

所有的NATURAL連接被轉換為帶有USING子句的連接。
所有的USING子句（包括上一步創建的）被轉換為等效的ON子句。
所有的ON子句（包括上一步創建的）作為新的連接詞（AND連接的項）添加到WHERE子句中。

SQLite不區分出現在WHERE子句中的連接約束和內連接的ON子句中的約束，因為這種區別不會影響結果。然而，外連接的ON子句約束和WHERE子句約束是有區別的。因此，當SQLite將一個外連接的ON子句約束移動到WHERE子句時，它會在抽象語法樹（AST）中添加特殊的標簽，以指示約束來自外連接，并且來自哪個外連接。在純SQL文本中無法添加這些標簽。因此，SQL輸入必須在外連接上使用ON子句。但在內部AST中，所有的約束都是WHERE子句的一部分，因為將所有的內容放在一個地方可以簡化處理。

在所有的約束都轉移到WHERE子句之后，WHERE子句被分解為連接詞（以下稱為"項"）。換句話說，WHERE子句被分解為由AND運算符分隔的片段。如果WHERE子句由OR運算符（析取式）分隔的約束組成，則整個子句被視為一個"項"，對其應用OR子句優化。

分析WHERE子句的所有項，看看它們是否可以使用索引來滿足。要被索引使用，項通常必須是以下形式之一：

  column = expressioncolumn IS expressioncolumn > expressioncolumn >= expressioncolumn < expressioncolumn <= expressionexpression = columnexpression IS columnexpression > columnexpression >= columnexpression < columnexpression <= columncolumn IN (expression-list)column IN (subquery)column IS NULLcolumn LIKE patterncolumn GLOB pattern

如果使用像這樣的語句創建索引：

CREATE INDEX idx_ex1 ON ex1(a,b,c,d,e,...,y,z);

那么如果索引的初始列（a、b等列）出現在WHERE子句項中，那么可能會使用該索引。索引的初始列必須使用=或IN或IS操作符。使用的最右邊的列可以使用不等式。對于使用的索引的最右邊的列，可以有多達兩個不等式，這些不等式必須將列的允許值夾在兩個極端之間。

并非索引的每一列都必須出現在WHERE子句項中，才能使用該索引。然而，使用的索引列之間不能有間隙。因此，對于上面的示例索引，如果沒有WHERE子句項約束列c，那么約束列a和b的項可以使用索引，但不能使用約束列d到z的項。同樣，索引列通常不會被使用（用于索引目的），如果它們在僅受不等式約束的列的右邊。（請參閱下面的跳過掃描優化以獲取例外。）

在表達式上的索引的情況下，無論上述文本中何時使用“列”這個詞，都可以替換為“索引表達式”（意思是出現在CREATE INDEX語句中的表達式的副本），一切都會按照相同的方式運行。

2.1. 索引項使用示例

對于上面的索引和類似這樣的WHERE子句：

... WHERE a=5 AND b IN (1,2,3) AND c IS NULL AND d='hello'

索引的前四列a、b、c和d將是可用的，因為這四列形成了索引的前綴，并且都被等式約束。

對于上面的索引和類似這樣的WHERE子句：

... WHERE a=5 AND b IN (1,2,3) AND c>12 AND d='hello'

只有索引的a、b和c列將是可用的。d列將不可用，因為它出現在c的右邊，而c只受不等式約束。

對于上面的索引和類似這樣的WHERE子句：

... WHERE a=5 AND b IN (1,2,3) AND d='hello'

只有索引的a和b列將是可用的。d列將不可用，因為列c沒有受到約束，索引可用的列集合中不能有空隙。

對于上面的索引和類似這樣的WHERE子句：

... WHERE b IN (1,2,3) AND c NOT NULL AND d='hello'

索引完全不可用，因為索引的最左邊的列（列"a"）沒有受到約束。假設沒有其他索引，上述查詢將導致全表掃描。

對于上面的索引和類似這樣的WHERE子句：

... WHERE a=5 OR b IN (1,2,3) OR c NOT NULL OR d='hello'

索引不可用，因為WHERE子句的項由OR而不是AND連接。這個查詢將導致全表掃描。然而，如果添加了三個額外的索引，這些索引包含了列b、c和d作為它們的最左邊的列，那么可能會應用OR子句優化。

3. BETWEEN優化

如果WHERE子句的一個項是以下形式：

  expr1 BETWEEN expr2 AND expr3

那么將添加兩個"虛擬"項，如下所示：

  expr1 >= expr2 AND expr1 <= expr3

虛擬項僅用于分析，不會生成任何字節碼。如果兩個虛擬項最終都被用作索引的約束，那么原始的BETWEEN項將被省略，對輸入行不進行相應的測試。因此，如果BETWEEN項最終被用作索引約束，那么對該項的測試永遠不會被執行。另一方面，虛擬項本身永遠不會導致對輸入行的測試。因此，如果BETWEEN項沒有被用作索引約束，而必須用來測試輸入行，那么expr1表達式只會被評估一次。

4. OR優化

由OR而不是AND連接的WHERE子句約束可以用兩種不同的方式處理。

4.1. 將OR連接的約束轉換為IN運算符

如果一個項由多個包含公共列名的子項組成，并由OR分隔，如下所示：

  column = expr1 OR column = expr2 OR column = expr3 OR ...

那么該項將被重寫為以下形式：

  column IN (expr1,expr2,expr3,...)

然后重寫的項可能會按照IN運算符的正常規則約束索引。請注意，列必須在每個OR連接的子項中都是相同的列，盡管列可以出現在=運算符的左邊或右邊。

4.2. 分別評估OR約束并取結果的并集

如果且僅當先前描述的將OR轉換為IN運算符的方法不起作用時，將嘗試第二個OR子句優化。假設OR子句由多個子項組成，如下所示：

  expr1 OR expr2 OR expr3

單個子項可以是單個比較表達式，如a=5或x>y，也可以是LIKE或BETWEEN表達式，或者子項可以是帶括號的由AND連接的子子項列表。每個子項都被分析，就像它本身是整個WHERE子句一樣，以查看該子項是否可以單獨進行索引。如果OR子句的每個子項都可以單獨進行索引，那么可能會對OR子句進行編碼，以便對OR子句的每個項使用單獨的索引。可以這樣想象SQLite如何為每個OR子句項使用單獨的索引：想象一下，WHERE子句被重寫為以下形式：

  rowid IN (SELECT rowid FROM table WHERE expr1UNION SELECT rowid FROM table WHERE expr2UNION SELECT rowid FROM table WHERE expr3)

上面的重寫表達式是概念性的；包含OR的WHERE子句實際上并沒有以這種方式重寫。實際上，OR子句的實現使用了一種更高效的機制，即使對于WITHOUT ROWID表或"rowid"不可訪問的表也可以工作。然而，通過上述語句可以捕捉到實現的本質：對于每個OR子句項，使用單獨的索引查找候選結果行，最終結果是這些行的并集。

請注意，在大多數情況下，SQLite只會為查詢的FROM子句中的每個表使用一個索引。這里描述的第二個OR子句優化是該規則的例外。對于OR子句，每個子項可能使用不同的索引。

對于任何給定的查詢，這里描述的OR子句優化可以使用的事實并不保證它會被使用。SQLite使用基于成本的查詢計劃器，估計各種競爭查詢計劃的CPU和磁盤I/O成本，并選擇它認為最快的計劃。如果WHERE子句中有許多OR項，或者如果某些OR子句子項上的索引不是很有選擇性，那么SQLite可能會決定使用不同的查詢算法，甚至全表掃描。應用程序開發人員可以在語句前面使用EXPLAIN QUERY PLAN前綴，以獲取所選查詢策略的高級概述。

5. LIKE優化

使用LIKE或GLOB運算符的WHERE子句項有時可以與索引一起使用，以進行范圍搜索，就像LIKE或GLOB是BETWEEN運算符的替代品一樣。這種優化有許多條件：

LIKE或GLOB的右側必須是一個字符串字面量，或者一個綁定到不以通配符字符開頭的字符串字面量的參數。
不能通過在LIKE或GLOB運算符的左側有一個數值（而不是字符串或blob）使LIKE或GLOB運算符為真。這意味著：
- LIKE或GLOB運算符的左側是具有TEXT親和性的索引列的名稱，或者
- 右側的模式參數不以負號（“-”）或數字開頭。
  這個約束源于數字不按字典順序排序的事實。例如：9<10但’9’>‘10’。
不能使用sqlite3_create_function() API來重載實現LIKE和GLOB的內置函數。
對于GLOB運算符，列必須使用內置的BINARY排序序列進行索引。
對于LIKE運算符，如果啟用了case_sensitive_like模式，則列必須使用BINARY排序序列進行索引，如果禁用了case_sensitive_like模式，則列必須使用內置的NOCASE排序序列進行索引。
如果使用了ESCAPE選項，則ESCAPE字符必須是ASCII，或者在UTF-8中是單字節字符。

LIKE運算符有兩種模式，可以通過pragma設置。默認模式是讓LIKE比較對于拉丁1字符的大小寫不敏感。因此，默認情況下，以下表達式為真：

'a' LIKE 'A'

如果啟用了case_sensitive_like pragma，如下所示：

PRAGMA case_sensitive_like=ON;

那么LIKE運算符將注意大小寫，上面的示例將被評估為假。注意，大小寫不敏感只適用于拉丁1字符 - 基本上是ASCII的低127字節代碼中的英文大寫和小寫字母。SQLite中的國際字符集是大小寫敏感的，除非提供了考慮非ASCII字符的應用程序定義的排序序列和like() SQL函數。如果提供了應用程序定義的排序序列和/或like() SQL函數，那么這里描述的LIKE優化將永遠不會被采用。

LIKE運算符默認是大小寫不敏感的，因為這是SQL標準要求的。您可以在編譯時使用SQLITE_CASE_SENSITIVE_LIKE命令行選項更改默認行為。

LIKE優化可能會發生，如果運算符左邊的列名使用內置的BINARY排序序列進行索引，并且case_sensitive_like已經打開。或者優化可能會發生，如果列使用內置的NOCASE排序序列進行索引，并且case_sensitive_like模式關閉。這些是LIKE運算符將被優化的唯一兩種組合。

GLOB運算符總是區分大小寫。GLOB運算符左邊的列必須始終使用內置的BINARY排序序列，否則不會嘗試使用索引優化該運算符。

只有當GLOB或LIKE運算符的右側是字面字符串或綁定到字面字符串的參數時，才會嘗試LIKE優化。字符串字面量不能以通配符開頭；如果右側以通配符字符開頭，則不會嘗試此優化。如果右側是綁定到字符串的參數，那么只有在包含表達式的預編譯語句使用sqlite3_prepare_v2()或sqlite3_prepare16_v2()編譯時，才會嘗試此優化。如果右側是參數，并且語句使用sqlite3_prepare()或sqlite3_prepare16()準備，則不會嘗試LIKE優化。

假設LIKE或GLOB運算符的右側的非通配符字符的初始序列是x。我們使用單個字符來表示這個非通配符前綴，但讀者應該理解，前綴可以由多于1個字符組成。讓y是與/x/長度相同但比x大的最小字符串。例如，如果x是’hello’，那么y將是’hellp’。然后，LIKE或GLOB優化將運算符重寫為以下形式：

  column >= x AND column < y

然后，優化器將嘗試使用索引來滿足這兩個新的虛擬約束。如果成功，那么將使用索引來滿足LIKE或GLOB運算符。如果失敗，那么將回退到全表掃描。在任何情況下，都將使用LIKE或GLOB運算符對所有候選行進行測試，以確保它們符合LIKE或GLOB模式。這是因為索引只能用于確定前綴匹配。索引不能用于處理LIKE或GLOB模式中可能出現的通配符。

6. 跳躍掃描優化

一般規則是，索引只有在 WHERE 子句約束了索引的最左側列時才有用。然而，在某些情況下，即使索引的前幾列被 WHERE 子句省略，但后面的列被包含，SQLite 也能夠使用索引。

考慮如下表：

CREATE TABLE people(name TEXT PRIMARY KEY,role TEXT NOT NULL,height INT NOT NULL, -- in cmCHECK( role IN ('student','teacher') )
);
CREATE INDEX people_idx1 ON people(role, height);

people 表包含了一個大型組織中的每個人的條目。每個人要么是 “student”，要么是 “teacher”，由 “role” 字段確定。該表還記錄了每個人的身高（以厘米為單位）。角色和身高都被索引。注意，索引的最左側列的選擇性不高 - 它只包含兩個可能的值。

現在考慮一個查詢，找出組織中身高為180cm或更高的每個人的名字：

SELECT name FROM people WHERE height>=180;

因為索引的最左側列沒有出現在查詢的 WHERE 子句中，人們可能會得出索引在這里無法使用的結論。然而，SQLite 能夠使用索引。從概念上講，SQLite 使用索引就像查詢更像下面的形式：

SELECT name FROM peopleWHERE role IN (SELECT DISTINCT role FROM people)AND height>=180;

或者這樣：

SELECT name FROM people WHERE role='teacher' AND height>=180
UNION ALL
SELECT name FROM people WHERE role='student' AND height>=180;

上面顯示的替代查詢公式只是概念性的。SQLite 并沒有真正改變查詢。實際的查詢計劃是這樣的：SQLite 定位到 “role” 的第一個可能值，它可以通過將 “people_idx1” 索引倒回到開始并讀取第一條記錄來做到這一點。SQLite 將這個第一個 “role” 值存儲在一個我們在這里稱為 “ $ro l e " 的內部變量中。然后 SQ L i t e 運行一個類似于 " SE L ECT nam e FROMp eo pl e W H ERE ro l e =$ role AND height>=180” 的查詢。這個查詢在索引的最左側列上有一個相等約束，所以索引可以用來解決這個查詢。一旦這個查詢完成，SQLite 然后使用 “people_idx1” 索引來定位 “role” 列的下一個值，使用的代碼在邏輯上類似于 “SELECT role FROM people WHERE role>$role LIMIT 1”。這個新的 “role” 值覆蓋了 $role 變量，這個過程重復，直到檢查了所有可能的 “role” 值。

我們稱這種索引使用方式為 “跳躍掃描”，因為數據庫引擎基本上是在對索引進行全掃描，但是通過偶爾跳躍到下一個候選值來優化掃描（使其少于 “全”）。

SQLite 可能會在索引上使用跳躍掃描，如果它知道第一列或更多列包含許多重復值。如果在索引的最左側列中有太少的重復項，那么簡單地向前走到下一個值，從而進行全表掃描，會比在索引上進行二分搜索來定位下一個左列值更快。

SQLite 只有在對數據庫運行 ANALYZE 命令后才能知道索引的最左側列中有許多重復項。沒有 ANALYZE 的結果，SQLite 不得不猜測表中數據的 “形狀”，默認猜測是在索引的最左側列中每個值有平均10個重復項。當重復項的數量大約為18個或更多時，跳躍掃描才變得有利可圖（它只是比全表掃描更快）。因此，在沒有分析過的數據庫上，永遠不會使用跳躍掃描。

7. 連接

SQLite 通過嵌套循環實現連接。在連接的嵌套循環的默認順序中，FROM 子句中最左側的表形成外循環，最右側的表形成內循環。然而，如果這樣做有助于選擇更好的索引，SQLite 將以不同的順序嵌套循環。

內連接可以自由重新排序。然而，外連接既不可交換也不可關聯，因此不會被重新排序。如果優化器認為這樣做是有利的，那么外連接左側和右側的內連接可能會被重新排序，但外連接總是按照它們出現的順序進行評估。

SQLite 對 CROSS JOIN 運算符進行特殊處理。從理論上講，CROSS JOIN 運算符是可交換的。然而，SQLite 選擇永遠不重新排序 CROSS JOIN 中的表。這提供了一種通過編程方式強制 SQLite 選擇特定循環嵌套順序的機制。

在選擇連接中的表順序時，SQLite 使用了一種高效的多項式時間圖算法，該算法在下一代查詢規劃器文檔中有描述。正因為如此，SQLite 能夠在微秒級別規劃具有50個或60個連接的查詢。

連接重新排序是自動的，通常工作得很好，程序員不必考慮它，特別是如果已經使用 ANALYZE 收集了有關可用索引的統計信息，盡管偶爾需要程序員的一些提示。例如，考慮以下模式：

CREATE TABLE node(id INTEGER PRIMARY KEY,name TEXT
);
CREATE INDEX node_idx ON node(name);
CREATE TABLE edge(orig INTEGER REFERENCES node,dest INTEGER REFERENCES node,PRIMARY KEY(orig, dest)
);
CREATE INDEX edge_idx ON edge(dest,orig);

上述模式定義了一個有向圖，可以在每個節點處存儲一個名稱。現在考慮針對此模式的查詢：

SELECT *FROM edge AS e,node AS n1,node AS n2WHERE n1.name = 'alice'AND n2.name = 'bob'AND e.orig = n1.idAND e.dest = n2.id;

這個查詢要求的是從標有 “alice” 的節點到標有 “bob” 的節點的所有邊的信息。SQLite 查詢優化器基本上有兩種選擇來實現這個查詢。（實際上有六種不同的選擇，但我們在這里只考慮其中的兩種。）下面是演示這兩種選擇的偽代碼。

選項 1：

foreach n1 where n1.name='alice' do:foreach n2 where n2.name='bob' do:foreach e where e.orig=n1.id and e.dest=n2.idreturn n1.*, n2.*, e.*endend
end

選項 2：

foreach n1 where n1.name='alice' do:foreach e where e.orig=n1.id do:foreach n2 where n2.id=e.dest and n2.name='bob' do:return n1.*, n2.*, e.*endend
end

這兩個實現選項中，每個循環都使用相同的索引來加速。這兩個查詢計劃的唯一區別是循環的嵌套順序。

那么哪個查詢計劃更好呢？結果取決于節點表和邊表中的數據類型。

假設有 M 個 alice 節點，N 個 bob 節點。考慮兩種情況。在第一種情況中，M 和 N 都為2，但每個節點有數千條邊。在這種情況下，選項1更優。對于選項1，內循環檢查一對節點之間是否存在邊，并在找到時輸出結果。因為只有2個 alice 和 bob 節點，所以內循環只需要運行四次，查詢就非常快了。選項2在這里會花費更長的時間。選項2的外循環只執行兩次，但因為每個 alice 節點都有大量的邊，所以中間循環必須迭代數千次。它會慢得多。所以在第一種情況下，我們更傾向于使用選項1。

現在考慮 M 和 N 都為3500的情況。Alice 節點非常多。這次假設這些節點中的每一個只通過一兩條邊連接。現在選項2更優。對于選項2，外循環仍然需要運行3500次，但是每個外循環中，中間循環只運行一次或兩次，內循環只有在每個中間循環中才會運行一次，如果有的話。所以內循環的總迭代次數大約是7000次。另一方面，選項1必須分別運行其外循環和中間循環3500次，導致中間循環的迭代次數達到1200萬次。因此，在第二種情況下，選項2比選項1快近2000倍。

所以你可以看到，根據表中數據的結構，查詢計劃1或查詢計劃2可能更好。SQLite 默認選擇哪個計劃呢？在3.6.18版本中，如果沒有運行 ANALYZE，SQLite 將選擇選項2。如果運行了 ANALYZE 命令以收集統計信息，如果統計信息表明另一種選擇可能運行得更快，可能會做出不同的選擇。