1. 引言

給定一個(gè)SQL語(yǔ)句，可能有數(shù)十種、數(shù)百種，甚至數(shù)千種方法來(lái)實(shí)現(xiàn)該語(yǔ)句，這取決于語(yǔ)句本身的復(fù)雜性和底層數(shù)據(jù)庫(kù)模式的復(fù)雜性。查詢計(jì)劃的任務(wù)是選擇最小化磁盤I/O和CPU開銷的算法。

2. WHERE子句分析

在分析之前，進(jìn)行以下轉(zhuǎn)換，將所有的連接約束轉(zhuǎn)移到WHERE子句中：

• 所有的NATURAL連接被轉(zhuǎn)換為帶有USING子句的連接。
• 所有的USING子句（包括上一步創(chuàng)建的）被轉(zhuǎn)換為等效的ON子句。
• 所有的ON子句（包括上一步創(chuàng)建的）作為新的連接詞（AND連接的項(xiàng)）添加到WHERE子句中。

SQLite不區(qū)分出現(xiàn)在WHERE子句中的連接約束和內(nèi)連接的ON子句中的約束，因?yàn)檫@種區(qū)別不會(huì)影響結(jié)果。然而，外連接的ON子句約束和WHERE子句約束是有區(qū)別的。因此，當(dāng)SQLite將一個(gè)外連接的ON子句約束移動(dòng)到WHERE子句時(shí)，它會(huì)在抽象語(yǔ)法樹（AST）中添加特殊的標(biāo)簽，以指示約束來(lái)自外連接，并且來(lái)自哪個(gè)外連接。在純SQL文本中無(wú)法添加這些標(biāo)簽。因此，SQL輸入必須在外連接上使用ON子句。但在內(nèi)部AST中，所有的約束都是WHERE子句的一部分，因?yàn)閷⑺械膬?nèi)容放在一個(gè)地方可以簡(jiǎn)化處理。

在所有的約束都轉(zhuǎn)移到WHERE子句之后，WHERE子句被分解為連接詞（以下稱為"項(xiàng)"）。換句話說(shuō)，WHERE子句被分解為由AND運(yùn)算符分隔的片段。如果WHERE子句由OR運(yùn)算符（析取式）分隔的約束組成，則整個(gè)子句被視為一個(gè)"項(xiàng)"，對(duì)其應(yīng)用OR子句優(yōu)化。

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

  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

如果使用像這樣的語(yǔ)句創(chuàng)建索引：

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

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

并非索引的每一列都必須出現(xiàn)在WHERE子句項(xiàng)中，才能使用該索引。然而，使用的索引列之間不能有間隙。因此，對(duì)于上面的示例索引，如果沒(méi)有WHERE子句項(xiàng)約束列c，那么約束列a和b的項(xiàng)可以使用索引，但不能使用約束列d到z的項(xiàng)。同樣，索引列通常不會(huì)被使用（用于索引目的），如果它們?cè)趦H受不等式約束的列的右邊。（請(qǐng)參閱下面的跳過(guò)掃描優(yōu)化以獲取例外。）

在表達(dá)式上的索引的情況下，無(wú)論上述文本中何時(shí)使用“列”這個(gè)詞，都可以替換為“索引表達(dá)式”（意思是出現(xiàn)在CREATE INDEX語(yǔ)句中的表達(dá)式的副本），一切都會(huì)按照相同的方式運(yùn)行。

2.1. 索引項(xiàng)使用示例

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

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

索引的前四列a、b、c和d將是可用的，因?yàn)檫@四列形成了索引的前綴，并且都被等式約束。

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

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

只有索引的a、b和c列將是可用的。d列將不可用，因?yàn)樗霈F(xiàn)在c的右邊，而c只受不等式約束。

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

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

只有索引的a和b列將是可用的。d列將不可用，因?yàn)榱衏沒(méi)有受到約束，索引可用的列集合中不能有空隙。

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

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

索引完全不可用，因?yàn)樗饕淖钭筮叺牧?#xff08;列"a"）沒(méi)有受到約束。假設(shè)沒(méi)有其他索引，上述查詢將導(dǎo)致全表掃描。

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

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

索引不可用，因?yàn)閃HERE子句的項(xiàng)由OR而不是AND連接。這個(gè)查詢將導(dǎo)致全表掃描。然而，如果添加了三個(gè)額外的索引，這些索引包含了列b、c和d作為它們的最左邊的列，那么可能會(huì)應(yīng)用OR子句優(yōu)化。

3. BETWEEN優(yōu)化

如果WHERE子句的一個(gè)項(xiàng)是以下形式：

  expr1 BETWEEN expr2 AND expr3

那么將添加兩個(gè)"虛擬"項(xiàng)，如下所示：

  expr1 >= expr2 AND expr1 <= expr3

虛擬項(xiàng)僅用于分析，不會(huì)生成任何字節(jié)碼。如果兩個(gè)虛擬項(xiàng)最終都被用作索引的約束，那么原始的BETWEEN項(xiàng)將被省略，對(duì)輸入行不進(jìn)行相應(yīng)的測(cè)試。因此，如果BETWEEN項(xiàng)最終被用作索引約束，那么對(duì)該項(xiàng)的測(cè)試永遠(yuǎn)不會(huì)被執(zhí)行。另一方面，虛擬項(xiàng)本身永遠(yuǎn)不會(huì)導(dǎo)致對(duì)輸入行的測(cè)試。因此，如果BETWEEN項(xiàng)沒(méi)有被用作索引約束，而必須用來(lái)測(cè)試輸入行，那么expr1表達(dá)式只會(huì)被評(píng)估一次。

4. OR優(yōu)化

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

4.1. 將OR連接的約束轉(zhuǎn)換為IN運(yùn)算符

如果一個(gè)項(xiàng)由多個(gè)包含公共列名的子項(xiàng)組成，并由OR分隔，如下所示：

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

那么該項(xiàng)將被重寫為以下形式：

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

然后重寫的項(xiàng)可能會(huì)按照IN運(yùn)算符的正常規(guī)則約束索引。請(qǐng)注意，列必須在每個(gè)OR連接的子項(xiàng)中都是相同的列，盡管列可以出現(xiàn)在=運(yùn)算符的左邊或右邊。

4.2. 分別評(píng)估OR約束并取結(jié)果的并集

如果且僅當(dāng)先前描述的將OR轉(zhuǎn)換為IN運(yùn)算符的方法不起作用時(shí)，將嘗試第二個(gè)OR子句優(yōu)化。假設(shè)OR子句由多個(gè)子項(xiàng)組成，如下所示：

  expr1 OR expr2 OR expr3

單個(gè)子項(xiàng)可以是單個(gè)比較表達(dá)式，如a=5或x>y，也可以是LIKE或BETWEEN表達(dá)式，或者子項(xiàng)可以是帶括號(hào)的由AND連接的子子項(xiàng)列表。每個(gè)子項(xiàng)都被分析，就像它本身是整個(gè)WHERE子句一樣，以查看該子項(xiàng)是否可以單獨(dú)進(jìn)行索引。如果OR子句的每個(gè)子項(xiàng)都可以單獨(dú)進(jìn)行索引，那么可能會(huì)對(duì)OR子句進(jìn)行編碼，以便對(duì)OR子句的每個(gè)項(xiàng)使用單獨(dú)的索引?？梢赃@樣想象SQLite如何為每個(gè)OR子句項(xiàng)使用單獨(dú)的索引：想象一下，WHERE子句被重寫為以下形式：

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

上面的重寫表達(dá)式是概念性的；包含OR的WHERE子句實(shí)際上并沒(méi)有以這種方式重寫。實(shí)際上，OR子句的實(shí)現(xiàn)使用了一種更高效的機(jī)制，即使對(duì)于WITHOUT ROWID表或"rowid"不可訪問(wèn)的表也可以工作。然而，通過(guò)上述語(yǔ)句可以捕捉到實(shí)現(xiàn)的本質(zhì)：對(duì)于每個(gè)OR子句項(xiàng)，使用單獨(dú)的索引查找候選結(jié)果行，最終結(jié)果是這些行的并集。

請(qǐng)注意，在大多數(shù)情況下，SQLite只會(huì)為查詢的FROM子句中的每個(gè)表使用一個(gè)索引。這里描述的第二個(gè)OR子句優(yōu)化是該規(guī)則的例外。對(duì)于OR子句，每個(gè)子項(xiàng)可能使用不同的索引。

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

5. LIKE優(yōu)化

使用LIKE或GLOB運(yùn)算符的WHERE子句項(xiàng)有時(shí)可以與索引一起使用，以進(jìn)行范圍搜索，就像LIKE或GLOB是BETWEEN運(yùn)算符的替代品一樣。這種優(yōu)化有許多條件：

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

LIKE運(yùn)算符有兩種模式，可以通過(guò)pragma設(shè)置。默認(rèn)模式是讓LIKE比較對(duì)于拉丁1字符的大小寫不敏感。因此，默認(rèn)情況下，以下表達(dá)式為真：

'a' LIKE 'A'

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

PRAGMA case_sensitive_like=ON;

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

LIKE運(yùn)算符默認(rèn)是大小寫不敏感的，因?yàn)檫@是SQL標(biāo)準(zhǔn)要求的。你可以在編譯時(shí)使用SQLITE_CASE_SENSITIVE_LIKE命令行選項(xiàng)更改默認(rèn)行為。

LIKE優(yōu)化可能會(huì)發(fā)生，如果運(yùn)算符左邊的列名使用內(nèi)置的BINARY排序序列進(jìn)行索引，并且case_sensitive_like已經(jīng)打開。或者優(yōu)化可能會(huì)發(fā)生，如果列使用內(nèi)置的NOCASE排序序列進(jìn)行索引，并且case_sensitive_like模式關(guān)閉。這些是LIKE運(yùn)算符將被優(yōu)化的唯一兩種組合。

GLOB運(yùn)算符總是區(qū)分大小寫。GLOB運(yùn)算符左邊的列必須始終使用內(nèi)置的BINARY排序序列，否則不會(huì)嘗試使用索引優(yōu)化該運(yùn)算符。

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

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

  column >= x AND column < y

然后，優(yōu)化器將嘗試使用索引來(lái)滿足這兩個(gè)新的虛擬約束。如果成功，那么將使用索引來(lái)滿足LIKE或GLOB運(yùn)算符。如果失敗，那么將回退到全表掃描。在任何情況下，都將使用LIKE或GLOB運(yùn)算符對(duì)所有候選行進(jìn)行測(cè)試，以確保它們符合LIKE或GLOB模式。這是因?yàn)樗饕荒苡糜诖_定前綴匹配。索引不能用于處理LIKE或GLOB模式中可能出現(xiàn)的通配符。

6. 跳躍掃描優(yōu)化

一般規(guī)則是，索引只有在 WHERE 子句約束了索引的最左側(cè)列時(shí)才有用。然而，在某些情況下，即使索引的前幾列被 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 表包含了一個(gè)大型組織中的每個(gè)人的條目。每個(gè)人要么是 “student”，要么是 “teacher”，由 “role” 字段確定。該表還記錄了每個(gè)人的身高（以厘米為單位）。角色和身高都被索引。注意，索引的最左側(cè)列的選擇性不高 - 它只包含兩個(gè)可能的值。

現(xiàn)在考慮一個(gè)查詢，找出組織中身高為180cm或更高的每個(gè)人的名字：

SELECT name FROM people WHERE height>=180;

因?yàn)樗饕淖钭髠?cè)列沒(méi)有出現(xiàn)在查詢的 WHERE 子句中，人們可能會(huì)得出索引在這里無(wú)法使用的結(jié)論。然而，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 并沒(méi)有真正改變查詢。實(shí)際的查詢計(jì)劃是這樣的：SQLite 定位到 “role” 的第一個(gè)可能值，它可以通過(guò)將 “people_idx1” 索引倒回到開始并讀取第一條記錄來(lái)做到這一點(diǎn)。SQLite 將這個(gè)第一個(gè) “role” 值存儲(chǔ)在一個(gè)我們?cè)谶@里稱為 “$role"的內(nèi)部變量中。然后SQLite運(yùn)行一個(gè)類似于"SELECTnameFROMpeopleWHERErole=$role AND height>=180” 的查詢。這個(gè)查詢?cè)谒饕淖钭髠?cè)列上有一個(gè)相等約束，所以索引可以用來(lái)解決這個(gè)查詢。一旦這個(gè)查詢完成，SQLite 然后使用 “people_idx1” 索引來(lái)定位 “role” 列的下一個(gè)值，使用的代碼在邏輯上類似于 “SELECT role FROM people WHERE role>$role LIMIT 1”。這個(gè)新的 “role” 值覆蓋了 $role 變量，這個(gè)過(guò)程重復(fù)，直到檢查了所有可能的 “role” 值。

我們稱這種索引使用方式為 “跳躍掃描”，因?yàn)閿?shù)據(jù)庫(kù)引擎基本上是在對(duì)索引進(jìn)行全掃描，但是通過(guò)偶爾跳躍到下一個(gè)候選值來(lái)優(yōu)化掃描（使其少于 “全”）。

SQLite 可能會(huì)在索引上使用跳躍掃描，如果它知道第一列或更多列包含許多重復(fù)值。如果在索引的最左側(cè)列中有太少的重復(fù)項(xiàng)，那么簡(jiǎn)單地向前走到下一個(gè)值，從而進(jìn)行全表掃描，會(huì)比在索引上進(jìn)行二分搜索來(lái)定位下一個(gè)左列值更快。

SQLite 只有在對(duì)數(shù)據(jù)庫(kù)運(yùn)行 ANALYZE 命令后才能知道索引的最左側(cè)列中有許多重復(fù)項(xiàng)。沒(méi)有 ANALYZE 的結(jié)果，SQLite 不得不猜測(cè)表中數(shù)據(jù)的 “形狀”，默認(rèn)猜測(cè)是在索引的最左側(cè)列中每個(gè)值有平均10個(gè)重復(fù)項(xiàng)。當(dāng)重復(fù)項(xiàng)的數(shù)量大約為18個(gè)或更多時(shí)，跳躍掃描才變得有利可圖（它只是比全表掃描更快）。因此，在沒(méi)有分析過(guò)的數(shù)據(jù)庫(kù)上，永遠(yuǎn)不會(huì)使用跳躍掃描。

7. 連接

SQLite 通過(guò)嵌套循環(huán)實(shí)現(xiàn)連接。在連接的嵌套循環(huán)的默認(rèn)順序中，FROM 子句中最左側(cè)的表形成外循環(huán)，最右側(cè)的表形成內(nèi)循環(huán)。然而，如果這樣做有助于選擇更好的索引，SQLite 將以不同的順序嵌套循環(huán)。

內(nèi)連接可以自由重新排序。然而，外連接既不可交換也不可關(guān)聯(lián)，因此不會(huì)被重新排序。如果優(yōu)化器認(rèn)為這樣做是有利的，那么外連接左側(cè)和右側(cè)的內(nèi)連接可能會(huì)被重新排序，但外連接總是按照它們出現(xiàn)的順序進(jìn)行評(píng)估。

SQLite 對(duì) CROSS JOIN 運(yùn)算符進(jìn)行特殊處理。從理論上講，CROSS JOIN 運(yùn)算符是可交換的。然而，SQLite 選擇永遠(yuǎn)不重新排序 CROSS JOIN 中的表。這提供了一種通過(guò)編程方式強(qiáng)制 SQLite 選擇特定循環(huán)嵌套順序的機(jī)制。

在選擇連接中的表順序時(shí)，SQLite 使用了一種高效的多項(xiàng)式時(shí)間圖算法，該算法在下一代查詢規(guī)劃器文檔中有描述。正因?yàn)槿绱?#xff0c;SQLite 能夠在微秒級(jí)別規(guī)劃具有50個(gè)或60個(gè)連接的查詢。

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

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);

上述模式定義了一個(gè)有向圖，可以在每個(gè)節(jié)點(diǎn)處存儲(chǔ)一個(gè)名稱?，F(xiàn)在考慮針對(duì)此模式的查詢：

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;

這個(gè)查詢要求的是從標(biāo)有 “alice” 的節(jié)點(diǎn)到標(biāo)有 “bob” 的節(jié)點(diǎn)的所有邊的信息。SQLite 查詢優(yōu)化器基本上有兩種選擇來(lái)實(shí)現(xiàn)這個(gè)查詢。（實(shí)際上有六種不同的選擇，但我們?cè)谶@里只考慮其中的兩種。）下面是演示這兩種選擇的偽代碼。

選項(xiàng) 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

選項(xiàng) 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

這兩個(gè)實(shí)現(xiàn)選項(xiàng)中，每個(gè)循環(huán)都使用相同的索引來(lái)加速。這兩個(gè)查詢計(jì)劃的唯一區(qū)別是循環(huán)的嵌套順序。

那么哪個(gè)查詢計(jì)劃更好呢？結(jié)果取決于節(jié)點(diǎn)表和邊表中的數(shù)據(jù)類型。

假設(shè)有 M 個(gè) alice 節(jié)點(diǎn)，N 個(gè) bob 節(jié)點(diǎn)?？紤]兩種情況。在第一種情況中，M 和 N 都為2，但每個(gè)節(jié)點(diǎn)有數(shù)千條邊。在這種情況下，選項(xiàng)1更優(yōu)。對(duì)于選項(xiàng)1，內(nèi)循環(huán)檢查一對(duì)節(jié)點(diǎn)之間是否存在邊，并在找到時(shí)輸出結(jié)果。因?yàn)橹挥?個(gè) alice 和 bob 節(jié)點(diǎn)，所以內(nèi)循環(huán)只需要運(yùn)行四次，查詢就非?？炝恕＿x項(xiàng)2在這里會(huì)花費(fèi)更長(zhǎng)的時(shí)間。選項(xiàng)2的外循環(huán)只執(zhí)行兩次，但因?yàn)槊總€(gè) alice 節(jié)點(diǎn)都有大量的邊，所以中間循環(huán)必須迭代數(shù)千次。它會(huì)慢得多。所以在第一種情況下，我們更傾向于使用選項(xiàng)1。

現(xiàn)在考慮 M 和 N 都為3500的情況。Alice 節(jié)點(diǎn)非常多。這次假設(shè)這些節(jié)點(diǎn)中的每一個(gè)只通過(guò)一兩條邊連接?，F(xiàn)在選項(xiàng)2更優(yōu)。對(duì)于選項(xiàng)2，外循環(huán)仍然需要運(yùn)行3500次，但是每個(gè)外循環(huán)中，中間循環(huán)只運(yùn)行一次或兩次，內(nèi)循環(huán)只有在每個(gè)中間循環(huán)中才會(huì)運(yùn)行一次，如果有的話。所以內(nèi)循環(huán)的總迭代次數(shù)大約是7000次。另一方面，選項(xiàng)1必須分別運(yùn)行其外循環(huán)和中間循環(huán)3500次，導(dǎo)致中間循環(huán)的迭代次數(shù)達(dá)到1200萬(wàn)次。因此，在第二種情況下，選項(xiàng)2比選項(xiàng)1快近2000倍。

所以你可以看到，根據(jù)表中數(shù)據(jù)的結(jié)構(gòu)，查詢計(jì)劃1或查詢計(jì)劃2可能更好。SQLite 默認(rèn)選擇哪個(gè)計(jì)劃呢？在3.6.18版本中，如果沒(méi)有運(yùn)行 ANALYZE，SQLite 將選擇選項(xiàng)2。如果運(yùn)行了 ANALYZE 命令以收集統(tǒng)計(jì)信息，如果統(tǒng)計(jì)信息表明另一種選擇可能運(yùn)行得更快，可能會(huì)做出不同的選擇。

7.1. 手動(dòng)控制連接順序

SQLite 幾乎總是自動(dòng)選擇最佳的連接順序。很少有開發(fā)者需要干預(yù)來(lái)給查詢規(guī)劃器提供關(guān)于最佳連接順序的提示。最好的策略是使用 PRAGMA optimize 確保查詢規(guī)劃器可以訪問(wèn)數(shù)據(jù)庫(kù)中數(shù)據(jù)形狀的最新統(tǒng)計(jì)信息。

本節(jié)描述了開發(fā)者如何控制 SQLite 中的連接順序，以解決可能出現(xiàn)的任何性能問(wèn)題。然而，除非作為最后的手段，否則不推薦使用這些技術(shù)。

如果你遇到一個(gè)情況，即使在運(yùn)行 PRAGMA optimize 后，SQLite 仍然選擇了次優(yōu)的連接順序，請(qǐng)?jiān)?SQLite 社區(qū)論壇上報(bào)告你的情況，以便 SQLite 的維護(hù)者可以對(duì)查詢規(guī)劃器進(jìn)行新的改進(jìn)，使得不需要手動(dòng)干預(yù)。

7.1.1. 使用 SQLITE_STAT 表手動(dòng)控制查詢計(jì)劃

SQLite 提供了一種能力，讓高級(jí)程序員可以控制優(yōu)化器選擇的查詢計(jì)劃。一種方法是在 sqlite_stat1 表中篡改 ANALYZE 的結(jié)果。

7.1.2. 使用 CROSS JOIN 手動(dòng)控制查詢計(jì)劃

程序員可以通過(guò)使用 CROSS JOIN 運(yùn)算符而不是 JOIN、INNER JOIN、NATURAL JOIN 或 “,” 連接，強(qiáng)制 SQLite 使用特定的循環(huán)嵌套順序。盡管理論上 CROSS JOIN 是可交換的，但 SQLite 選擇永遠(yuǎn)不重新排序 CROSS JOIN 中的表。因此，CROSS JOIN 的左表總是相對(duì)于右表處于外循環(huán)。

在以下查詢中，優(yōu)化器可以自由地以任何方式重新排序 FROM 子句中的表：

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

在以下邏輯等效的相同查詢中，將 “,” 替換為 “CROSS JOIN” 意味著表的順序必須是 N1、E、N2。

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

在后一個(gè)查詢中，查詢計(jì)劃必須是選項(xiàng)2。注意，我們必須使用關(guān)鍵字 “CROSS” 才能禁用表重新排序優(yōu)化；INNER JOIN、NATURAL JOIN、JOIN 和其他類似的組合就像逗號(hào)連接一樣，優(yōu)化器可以自由地根據(jù)需要重新排序表。（在外連接上也禁用了表重新排序，但這是因?yàn)橥膺B接既不是關(guān)聯(lián)的也不是可交換的。重新排序 OUTER JOIN 中的表會(huì)改變結(jié)果。）

8. 在多個(gè)索引之間進(jìn)行選擇

查詢的 FROM 子句中的每個(gè)表最多可以使用一個(gè)索引（除非 OR 子句優(yōu)化起作用），SQLite 盡力在每個(gè)表上使用至少一個(gè)索引。有時(shí)，兩個(gè)或多個(gè)索引可能是單個(gè)表的候選索引。例如：

CREATE TABLE ex2(x,y,z);
CREATE INDEX ex2i1 ON ex2(x);
CREATE INDEX ex2i2 ON ex2(y);
SELECT z FROM ex2 WHERE x=5 AND y=6;

對(duì)于上述 SELECT 語(yǔ)句，優(yōu)化器可以使用 ex2i1 索引查找 ex2 中包含 x=5 的行，然后針對(duì) y=6 項(xiàng)測(cè)試每一行?；蛘?#xff0c;它可以使用 ex2i2 索引查找 ex2 中包含 y=6 的行，然后針對(duì) x=5 項(xiàng)測(cè)試每個(gè)行。

在面臨兩個(gè)或多個(gè)索引的選擇時(shí)，SQLite 嘗試估計(jì)使用每個(gè)選項(xiàng)執(zhí)行查詢所需的總工作量。然后選擇估計(jì)工作量最少的選項(xiàng)。

為了幫助優(yōu)化器更準(zhǔn)確地估計(jì)使用各種索引涉及的工作量，用戶可以選擇運(yùn)行 ANALYZE 命令。ANALYZE 命令掃描數(shù)據(jù)庫(kù)中可能在兩個(gè)或多個(gè)索引之間進(jìn)行選擇的所有索引，并收集有關(guān)這些索引的選擇性的統(tǒng)計(jì)信息。此掃描收集的統(tǒng)計(jì)信息存儲(chǔ)在以 “sqlite_stat” 開頭的特殊數(shù)據(jù)庫(kù)表中。這些表的內(nèi)容不會(huì)隨著數(shù)據(jù)庫(kù)的更改而更新，因此在進(jìn)行重大更改后，重新運(yùn)行 ANALYZE 可能是明智的。ANALYZE命令的結(jié)果僅對(duì)在 ANALYZE 命令完成后打開的數(shù)據(jù)庫(kù)連接可用。

各種 sqlite_statN 表包含有關(guān)各種索引選擇性的信息。例如，sqlite_stat1 表可能指示，列 x 上的等式約束平均將搜索空間減少到10行，而列 y 上的等式約束平均將搜索空間減少到3行。在這種情況下，SQLite 會(huì)更喜歡使用 ex2i2 索引，因?yàn)樵撍饕哌x擇性。

8.1. 使用一元 “+” 取消 WHERE 子句條件

請(qǐng)注意，以這種方式取消 WHERE 子句條件不是推薦的做法。這是一種變通方法。只有在作為最后手段來(lái)獲得所需性能時(shí)才這樣做。

可以通過(guò)在列名前加上一元 + 運(yùn)算符來(lái)手動(dòng)取消 WHERE 子句中的條件以用于索引。一元 + 是一個(gè)空操作，不會(huì)在預(yù)處理語(yǔ)句中生成任何字節(jié)碼。然而，一元 + 運(yùn)算符將阻止該項(xiàng)約束索引。因此，在上面的示例中，如果查詢被重寫為：

SELECT z FROM ex2 WHERE +x=5 AND y=6;

x 列上的 + 運(yùn)算符將阻止該項(xiàng)約束索引。這將強(qiáng)制使用 ex2i2 索引。

注意，一元 + 運(yùn)算符還會(huì)從表達(dá)式中刪除類型關(guān)聯(lián)，而在某些情況下，這可能導(dǎo)致表達(dá)式含義的微妙變化。在上面的示例中，如果列 x 具有 TEXT 關(guān)聯(lián)，則比較 “x=5” 將作為文本進(jìn)行。+ 運(yùn)算符刪除了關(guān)聯(lián)。因此，比較 “+x=5” 將把列 x 中的文本與數(shù)字值 5 進(jìn)行比較，結(jié)果總是為假。

8.2. 范圍查詢

考慮一個(gè)稍微不同的場(chǎng)景：

CREATE TABLE ex2(x,y,z);
CREATE INDEX ex2i1 ON ex2(x);
CREATE INDEX ex2i2 ON ex2(y);
SELECT z FROM ex2 WHERE x BETWEEN 1 AND 100 AND y BETWEEN 1 AND 100;

進(jìn)一步假設(shè)列 x 包含分布在 0 到 1,000,000 之間的值，列 y 包含分布在 0 到 1,000 之間的值。在這種情況下，列 x 上的范圍約束應(yīng)該使搜索空間減少 10,000 倍，而列 y 上的范圍約束應(yīng)該使搜索空間減少 10 倍。因此，應(yīng)該優(yōu)先使用 ex2i1 索引。

SQLite 會(huì)做出這個(gè)決定，但前提是它已經(jīng)使用 SQLITE_ENABLE_STAT3 或 SQLITE_ENABLE_STAT4 編譯。SQLITE_ENABLE_STAT3 和 SQLITE_ENABLE_STAT4 選項(xiàng)會(huì)使 ANALYZE 命令在 sqlite_stat3 或 sqlite_stat4 表中收集列內(nèi)容的直方圖，并使用此直方圖為上述范圍約束等情況做出更好的查詢選擇。STAT3 和 STAT4 之間的主要區(qū)別在于，STAT3 僅記錄索引最左側(cè)列的直方圖數(shù)據(jù)，而 STAT4 記錄索引所有列的直方圖數(shù)據(jù)。對(duì)于單列索引，STAT3 和 STAT4 的工作方式相同。

直方圖數(shù)據(jù)僅在約束的右側(cè)是簡(jiǎn)單的編譯時(shí)常量或參數(shù)而不是表達(dá)式時(shí)有用。

直方圖數(shù)據(jù)的另一個(gè)限制是它只適用于索引的最左側(cè)的列。考慮以下情況：

CREATE TABLE ex3(w,x,y,z);
CREATE INDEX ex3i1 ON ex2(w, x);
CREATE INDEX ex3i2 ON ex2(w, y);
SELECT z FROM ex3 WHERE w=5 AND x BETWEEN 1 AND 100 AND y BETWEEN 1 AND 100;

這里的不等式在 x 和 y 列上，它們不是最左側(cè)的索引列。因此，收集的直方圖數(shù)據(jù)對(duì)于選擇 x 和 y 列上的范圍約束無(wú)用。

9. 覆蓋索引

在對(duì)一行進(jìn)行索引查找時(shí)，通常的過(guò)程是在索引上進(jìn)行二分查找以找到索引條目，然后從索引中提取 rowid，并使用該 rowid 在原始表上進(jìn)行二分查找。因此，典型的索引查找涉及兩次二分查找。然而，如果所有要從表中獲取的列已經(jīng)在索引中可用，SQLite 將使用索引中的值，而永遠(yuǎn)不會(huì)查找原始表行。這節(jié)省了每行的一次二分查找，可以使許多查詢運(yùn)行速度加倍。

當(dāng)一個(gè)索引包含查詢所需的所有數(shù)據(jù)，并且原始表永遠(yuǎn)不需要被查詢時(shí)，我們稱該索引為 “覆蓋索引”。

10. ORDER BY 優(yōu)化

SQLite 嘗試使用索引來(lái)滿足查詢的 ORDER BY 子句。當(dāng)面臨使用索引滿足 WHERE 子句約束或滿足 ORDER BY 子句的選擇時(shí)，SQLite 會(huì)進(jìn)行上述的成本分析，并選擇它認(rèn)為會(huì)得到最快答案的索引。

SQLite 還會(huì)嘗試使用索引來(lái)幫助滿足 GROUP BY 子句和 DISTINCT 關(guān)鍵字。如果可以將連接的嵌套循環(huán)排列成對(duì)于 GROUP BY 或 DISTINCT 來(lái)說(shuō)是連續(xù)的等價(jià)行，那么 GROUP BY 或 DISTINCT 邏輯只需通過(guò)比較當(dāng)前行和前一行就可以判斷當(dāng)前行是否屬于同一組或是否與當(dāng)前行不同。這比比較每一行和所有先前的行要快得多。

10.1. 通過(guò)索引部分 ORDER BY

如果查詢包含具有多個(gè)項(xiàng)的 ORDER BY 子句，SQLite 可能可以使用索引使行按 ORDER BY 中的某些前綴項(xiàng)的順序出現(xiàn)，但 ORDER BY 的后續(xù)項(xiàng)可能無(wú)法滿足。在這種情況下，SQLite 進(jìn)行塊排序。假設(shè) ORDER BY 子句有四個(gè)項(xiàng)，并且查詢結(jié)果的自然順序使行按前兩個(gè)項(xiàng)的順序出現(xiàn)。當(dāng)每一行由查詢引擎輸出并進(jìn)入排序器時(shí)，當(dāng)前行中與 ORDER BY 的前兩個(gè)項(xiàng)對(duì)應(yīng)的輸出與前一行進(jìn)行比較。如果它們已經(jīng)改變，當(dāng)前的排序就結(jié)束并輸出，然后開始新的排序。這會(huì)導(dǎo)致排序稍微快一些。更大的優(yōu)點(diǎn)是需要在內(nèi)存中保存的行數(shù)少得多，減少了內(nèi)存需求，并且在核心查詢運(yùn)行完成之前就可以開始出現(xiàn)輸出。

11. 子查詢展平

當(dāng)一個(gè)子查詢出現(xiàn)在 SELECT 的 FROM 子句中時(shí)，最簡(jiǎn)單的行為是將子查詢?cè)u(píng)估為一個(gè)臨時(shí)表，然后針對(duì)臨時(shí)表運(yùn)行外部 SELECT。這樣的計(jì)劃可能是次優(yōu)的，因?yàn)榕R時(shí)表不會(huì)有任何索引，而外部查詢（可能是一個(gè)連接）將被迫對(duì)臨時(shí)表進(jìn)行完全表掃描，或者在查詢時(shí)構(gòu)造一個(gè)臨時(shí)表索引，這兩者都可能不太快。

為了克服這個(gè)問(wèn)題，SQLite 嘗試展平 SELECT 的 FROM 子句中的子查詢。這涉及將子查詢的 FROM 子句插入到外部查詢的 FROM 子句中，并重寫在外部查詢中引用子查詢結(jié)果集的表達(dá)式。例如：

SELECT t1.a, t2.b FROM t2, (SELECT x+y AS a FROM t1 WHERE z<100) WHERE a>5

使用查詢展平重寫為：

SELECT t1.x+t1.y AS a, t2.b FROM t2, t1 WHERE z<100 AND a>5

必須滿足一長(zhǎng)串條件才能進(jìn)行查詢展平。其中一些約束由斜體文本標(biāo)記為過(guò)時(shí)。這些額外的約束保留在文檔中以保留其他約束的編號(hào)。

這里的重點(diǎn)是，展平規(guī)則是微妙而復(fù)雜的。多年來(lái)，由于過(guò)于激進(jìn)的查詢展平導(dǎo)致了多個(gè)錯(cuò)誤。另一方面，如果查詢展平更保守，那么復(fù)雜查詢和/或涉及視圖的查詢的性能可能會(huì)受到影響。

查詢展平是使用視圖時(shí)的重要優(yōu)化。視圖是嵌套查詢，因此查詢展平通?？梢詫⒁晥D查詢的部分或全部并入調(diào)用查詢，從而提高性能。

在某些情況下，查詢展平可能會(huì)導(dǎo)致查詢性能下降。這主要是因?yàn)檎蛊降牟樵兛赡軙?huì)導(dǎo)致更大的聯(lián)接，而更大的聯(lián)接可能會(huì)導(dǎo)致查詢計(jì)劃的搜索空間變得更大，從而導(dǎo)致查詢優(yōu)化器無(wú)法找到最佳的查詢計(jì)劃。SQLite 允許在視圖和子查詢名之前加上 “NOT INDEXED” 來(lái)禁止查詢展平。例如：

SELECT * FROM my_view NOT INDEXED WHERE ...;

在上面的查詢中，“my_view” 視圖將被評(píng)估為一個(gè)單獨(dú)的臨時(shí)表，然后臨時(shí)表將被插入到外部查詢中。這可能會(huì)導(dǎo)致查詢性能下降，但如果查詢展平導(dǎo)致查詢優(yōu)化器無(wú)法找到最佳的查詢計(jì)劃，那么這可能會(huì)提高性能。在這種情況下，“NOT INDEXED” 是一種有用的工具。

12. 子查詢協(xié)同程序

SQLite 以三種方式之一實(shí)現(xiàn) FROM 子句子查詢：

• 將子查詢展平到其外部查詢
• 將子查詢?cè)u(píng)估為一個(gè)臨時(shí)表，該表在執(zhí)行的一個(gè) SQL 語(yǔ)句的持續(xù)時(shí)間內(nèi)存在，然后針對(duì)該臨時(shí)表運(yùn)行外部查詢。
• 在與外部查詢并行運(yùn)行的協(xié)同程序中評(píng)估子查詢，根據(jù)需要向外部查詢提供行。

本節(jié)描述了第三種技術(shù)：將子查詢實(shí)現(xiàn)為協(xié)同程序。

協(xié)同程序類似于子程序，它在與調(diào)用者相同的線程中運(yùn)行，并最終將控制權(quán)返回給調(diào)用者。不同之處在于協(xié)同程序還具有在完成之前返回的能力，然后在下次調(diào)用時(shí)從中斷的地方繼續(xù)。

當(dāng)子查詢作為協(xié)同程序?qū)崿F(xiàn)時(shí)，生成字節(jié)碼以實(shí)現(xiàn)子查詢，就像它是一個(gè)獨(dú)立的查詢一樣，只是在計(jì)算每一行后，協(xié)同程序?qū)⒖刂茩?quán)返回給調(diào)用者，而不是將結(jié)果行返回給應(yīng)用程序。調(diào)用者可以使用計(jì)算出的一行作為其計(jì)算的一部分，然后在準(zhǔn)備好下一行時(shí)再次調(diào)用協(xié)同程序。

與在臨時(shí)表中存儲(chǔ)子查詢的完整結(jié)果集相比，協(xié)同程序更好，因?yàn)閰f(xié)同程序使用的內(nèi)存更少。對(duì)于協(xié)同程序，只需要記住結(jié)果的一行，而對(duì)于臨時(shí)表，需要存儲(chǔ)所有結(jié)果行。此外，由于協(xié)同程序在外部查詢開始工作之前不需要運(yùn)行到完成，因此輸出的第一行可以更快地出現(xiàn)，并且如果整個(gè)查詢?cè)谕瓿芍氨环艞?#xff0c;總體工作量會(huì)減少。

另一方面，如果子查詢的結(jié)果必須多次掃描（例如，因?yàn)樗沁B接中的一個(gè)表），那么最好使用臨時(shí)表來(lái)記住子查詢的整個(gè)結(jié)果，以避免多次計(jì)算子查詢。

12.1. 在排序后使用協(xié)同程序延遲工作

從 SQLite 版本 3.21.0（2017-10-24）開始，查詢規(guī)劃器將始終優(yōu)先使用協(xié)同程序?qū)崿F(xiàn)包含 ORDER BY 子句且不是連接的 FROM 子句子查詢，當(dāng)外部查詢的結(jié)果集是“復(fù)雜”的時(shí)候。此功能允許應(yīng)用程序在排序后將昂貴的計(jì)算從排序前移出，從而實(shí)現(xiàn)更快的操作。例如，考慮以下查詢：

SELECT expensive_function(a) FROM tab ORDER BY date DESC LIMIT 5;

此查詢的目標(biāo)是計(jì)算表中最近五個(gè)條目的某個(gè)值。在上面的查詢中，“expensive_function()”在排序之前調(diào)用，因此對(duì)表的每一行都調(diào)用，即使由于 LIMIT 子句最終省略了一些行?？梢允褂脜f(xié)同程序來(lái)解決這個(gè)問(wèn)題：

SELECT expensive_function(a) FROM (SELECT a FROM tab ORDER BY date DESC LIMIT 5
);

在修訂后的查詢中，子查詢由協(xié)同程序?qū)崿F(xiàn)，計(jì)算 “a” 的五個(gè)最近值。這五個(gè)值從協(xié)同程序傳遞到外部查詢，其中只對(duì)應(yīng)用程序關(guān)心的特定行調(diào)用 “expensive_function()”。

未來(lái)版本的 SQLite 查詢規(guī)劃器可能會(huì)變得足夠智能，可以自動(dòng)實(shí)現(xiàn)上述轉(zhuǎn)換，反向轉(zhuǎn)換。也就是說(shuō)，未來(lái)版本的 SQLite 可能會(huì)將第一種形式的查詢轉(zhuǎn)換為第二種形式，或者將以第二種方式編寫的查詢轉(zhuǎn)換為第一種形式。截至 SQLite 版本 3.22.0（2018-01-22），如果外部查詢?cè)谄浣Y(jié)果集中不使用任何用戶定義的函數(shù)或子查詢，查詢規(guī)劃器將展平子查詢。然而，對(duì)于上面顯示的示例，SQLite 按照編寫的查詢實(shí)現(xiàn)每個(gè)查詢。

13. MIN/MAX 優(yōu)化

包含單個(gè) MIN() 或 MAX() 聚合函數(shù)的查詢，其參數(shù)是索引的最左列，可以通過(guò)執(zhí)行單個(gè)索引查找而不是掃描整個(gè)表來(lái)滿足。例如：

SELECT MIN(x) FROM table;
SELECT MAX(x)+1 FROM table;

14. 自動(dòng)查詢時(shí)索引

當(dāng)沒(méi)有索引可用于輔助查詢?cè)u(píng)估時(shí)，SQLite 可能會(huì)創(chuàng)建一個(gè)僅在單個(gè) SQL 語(yǔ)句的持續(xù)時(shí)間內(nèi)存在的自動(dòng)索引。自動(dòng)索引有時(shí)也稱為“查詢時(shí)索引”。由于構(gòu)造自動(dòng)或查詢時(shí)索引的成本是 O(NlogN)（其中 N 是表中的條目數(shù)），而執(zhí)行完整表掃描的成本僅為 O(N)，因此僅當(dāng) SQLite 預(yù)計(jì)在 SQL 語(yǔ)句執(zhí)行過(guò)程中查找將運(yùn)行超過(guò) logN 次時(shí)，才會(huì)創(chuàng)建自動(dòng)索引。考慮一個(gè)例子：

CREATE TABLE t1(a,b);
CREATE TABLE t2(c,d);
-- 向 t1 和 t2 插入許多行
SELECT * FROM t1, t2 WHERE a=c;

在上面的查詢中，如果 t1 和 t2 都有大約 N 行，那么在沒(méi)有任何索引的情況下，查詢將需要 O(N*N) 時(shí)間。另一方面，創(chuàng)建表 t2 上的索引需要 O(NlogN) 時(shí)間，使用該索引評(píng)估查詢需要額外的 O(NlogN) 時(shí)間。在沒(méi)有 ANALYZE 信息的情況下，SQLite 猜測(cè) N 是一百萬(wàn)，因此它相信構(gòu)造自動(dòng)索引將是更便宜的方法。

自動(dòng)查詢時(shí)索引還可以用于子查詢：

CREATE TABLE t1(a,b);
CREATE TABLE t2(c,d);
-- 向 t1 和 t2 插入許多行
SELECT a, (SELECT d FROM t2 WHERE c=b) FROM t1;

在這個(gè)例子中，t2 表用于子查詢來(lái)轉(zhuǎn)換 t1.b 列的值。如果每個(gè)表包含 N 行，SQLite 預(yù)計(jì)子查詢將運(yùn)行 N 次，因此它會(huì)認(rèn)為首先在 t2 上構(gòu)建一個(gè)自動(dòng)的臨時(shí)索引，然后使用該索引滿足子查詢的 N 個(gè)實(shí)例是更快的方法。

使用自動(dòng)索引功能可以在運(yùn)行時(shí)使用 automatic_index 條目禁用。自動(dòng)索引默認(rèn)是開啟的，但可以使用 SQLITE_DEFAULT_AUTOMATIC_INDEX 編譯時(shí)選項(xiàng)將其更改為默認(rèn)關(guān)閉。通過(guò)使用 SQLITE_OMIT_AUTOMATIC_INDEX 編譯時(shí)選項(xiàng)完全禁用創(chuàng)建自動(dòng)索引的功能。

在 SQLite 版本 3.8.0（2013-08-26）及更高版本中，每次準(zhǔn)備使用自動(dòng)索引的語(yǔ)句時(shí)，都會(huì)將 SQLITE_WARNING_AUTOINDEX 消息發(fā)送到錯(cuò)誤日志。應(yīng)用程序開發(fā)人員可以并且應(yīng)該使用這些警告來(lái)識(shí)別模式中需要新的持久性索引的需求。

請(qǐng)勿將自動(dòng)索引與有時(shí)用于實(shí)現(xiàn) PRIMARY KEY 約束或 UNIQUE 約束的內(nèi)部索引（名稱類似于 “sqlite_autoindex_table_N”）混淆。這里描述的自動(dòng)索引僅在單個(gè)查詢的持續(xù)時(shí)間內(nèi)存在，永遠(yuǎn)不會(huì)持久化到磁盤，并且僅對(duì)單個(gè)數(shù)據(jù)庫(kù)連接可見(jiàn)。內(nèi)部索引是實(shí)現(xiàn) PRIMARY KEY 和 UNIQUE 約束的一部分，是長(zhǎng)期持久化到磁盤的，并且對(duì)所有數(shù)據(jù)庫(kù)連接可見(jiàn)。內(nèi)部索引的名稱中出現(xiàn)了 “autoindex” 一詞是由于歷史原因，并不表明內(nèi)部索引和自動(dòng)索引有關(guān)。

14.1. 哈希連接

自動(dòng)索引幾乎與哈希連接相同。唯一的區(qū)別是使用 B-Tree 而不是哈希表。如果你愿意說(shuō)為自動(dòng)索引構(gòu)造的臨時(shí) B-Tree 實(shí)際上只是一個(gè)花哨的哈希表，那么使用自動(dòng)索引的查詢就是一個(gè)哈希連接。

SQLite 在這種情況下構(gòu)造臨時(shí)索引而不是哈希表，因?yàn)樗呀?jīng)有了一個(gè)健壯且高性能的 B-Tree 實(shí)現(xiàn)，而哈希表需要添加。為了處理這一情況而添加一個(gè)單獨(dú)的哈希表實(shí)現(xiàn)會(huì)增加庫(kù)的大小（該庫(kù)設(shè)計(jì)用于低內(nèi)存嵌入式設(shè)備）并帶來(lái)最小的性能增益。SQLite 可能會(huì)在某一天增強(qiáng)哈希表實(shí)現(xiàn)，但是現(xiàn)在在客戶端/服務(wù)器數(shù)據(jù)庫(kù)引擎可能使用哈希連接的情況下繼續(xù)使用自動(dòng)索引似乎更好。

15. WHERE 子句下推優(yōu)化

如果子查詢不能展平到外部查詢，可能仍然可以通過(guò)將 WHERE 子句中的項(xiàng)從外部查詢“下推”到子查詢來(lái)提高性能?？紤]一個(gè)例子：

CREATE TABLE t1(a INT, b INT);
CREATE TABLE t2(x INT, y INT);
CREATE VIEW v1(a,b) AS SELECT DISTINCT a, b FROM t1;SELECT x, y, bFROM t2 JOIN v1 ON (x=a)WHERE b BETWEEN 10 AND 20;

視圖 v1 不能被展平，因?yàn)樗?DISTINCT。它必須作為子查詢運(yùn)行，結(jié)果存儲(chǔ)在一個(gè)臨時(shí)表中，然后在 t2 和臨時(shí)表之間進(jìn)行連接。下推優(yōu)化將 “b BETWEEN 10 AND 20” 項(xiàng)下推到視圖中。這使得臨時(shí)表更小，并且如果在 t1.b 上有索引，可以幫助子查詢更快地運(yùn)行。結(jié)果的評(píng)估如下：

SELECT x, y, bFROM t2JOIN (SELECT DISTINCT a, b FROM t1 WHERE b BETWEEN 10 AND 20)WHERE b BETWEEN 10 AND 20;

WHERE 子句下推優(yōu)化不能總是使用。例如，如果子查詢包含 LIMIT，那么從外部查詢下推 WHERE 子句的任何部分都可能改變內(nèi)部查詢的結(jié)果。還有其他限制，這在源代碼中實(shí)現(xiàn)此優(yōu)化的 pushDownWhereTerms() 函數(shù)的注釋中有解釋。

不要將此優(yōu)化與 MySQL 中名稱相似的優(yōu)化混淆。MySQL 的下推優(yōu)化改變了 WHERE 子句約束的評(píng)估順序，使得可以僅使用索引而不需要找到對(duì)應(yīng)的表行的約束先被評(píng)估，從而避免在約束失敗時(shí)不必要的表行查找。為了消除歧義，SQLite 稱其為 “MySQL 下推優(yōu)化”。SQLite 也做了 MySQL 下推優(yōu)化，除了 WHERE 子句下推優(yōu)化。但是，本節(jié)的重點(diǎn)是 WHERE 子句下推優(yōu)化。

16. OUTER JOIN 強(qiáng)度減小優(yōu)化

OUTER JOIN（LEFT JOIN，RIGHT JOIN 或 FULL JOIN）有時(shí)可以簡(jiǎn)化。LEFT 或 RIGHT JOIN 可以轉(zhuǎn)換為普通（INNER）JOIN，或者 FULL JOIN 可能被轉(zhuǎn)換為 LEFT 或 RIGHT JOIN。如果 WHERE 子句中的條件可以保證簡(jiǎn)化后的結(jié)果相同，那么就可以發(fā)生這種情況。例如，如果 LEFT JOIN 的右表中的任何列必須為非 NULL 以使 WHERE 子句為真，那么 LEFT JOIN 就降級(jí)為普通 JOIN。

確定連接是否可以簡(jiǎn)化的定理證明器是不完美的。它有時(shí)會(huì)返回假陰性。換句話說(shuō)，有時(shí)它無(wú)法證明減小 OUTER JOIN 的強(qiáng)度是安全的，實(shí)際上它是安全的。例如，證明器不知道 datetime() SQL 函數(shù)如果其第一個(gè)參數(shù)為 NULL，總是返回 NULL，因此它不會(huì)認(rèn)識(shí)到以下查詢中的 LEFT JOIN 可以進(jìn)行強(qiáng)度減小：

SELECT urls.urlFROM urlsLEFT JOIN(SELECT *FROM (SELECT url_id AS uid, max(retrieval_time) AS rtimeFROM lookups GROUP BY 1 ORDER BY 1)WHERE uid IN (358341,358341,358341)) recentON u.source_seed_id = recent.xyz OR u.url_id = recent.xyzWHEREDATETIME(recent.rtime) > DATETIME('now', '-5 days');

可能未來(lái)對(duì)證明器的增強(qiáng)可能使其能夠識(shí)別到某些內(nèi)置函數(shù)的 NULL 輸入總是導(dǎo)致 NULL 答案。然而，并非所有內(nèi)置函數(shù)都具有該屬性（例如 coalesce()），當(dāng)然，證明器將永遠(yuǎn)無(wú)法推理出應(yīng)用程序定義的 SQL 函數(shù)。

17. 省略 OUTER JOIN 優(yōu)化

有時(shí)可以完全從查詢中省略 LEFT 或 RIGHT JOIN，而不改變結(jié)果。只有在所有以下條件都為真時(shí)，才會(huì)發(fā)生這種情況：

• 查詢不是聚合
• 查詢是 DISTINCT，或者 OUTER JOIN 的 ON 或 USING 子句約束連接，使其只匹配一行
• LEFT JOIN 的右表或 RIGHT JOIN 的左表在查詢中的任何地方都不會(huì)在其自己的 USING 或 ON 子句之外使用。

當(dāng) OUTER JOIN 用于視圖內(nèi)部，然后以不引用 LEFT JOIN 的右表或 RIGHT JOIN 的左表的任何列的方式使用視圖時(shí)，通常會(huì)出現(xiàn) OUTER JOIN 消除。

這是省略 LEFT JOIN 的一個(gè)簡(jiǎn)單示例：

CREATE TABLE t1(ipk INTEGER PRIMARY KEY, v1);
CREATE TABLE t2(ipk INTEGER PRIMARY KEY, v2);
CREATE TABLE t3(ipk INTEGER PRIMARY KEY, v3);SELECT v1, v3 FROM t1 LEFT JOIN t2 ON (t1.ipk=t2.ipk)LEFT JOIN t3 ON (t1.ipk=t3.ipk)

在上面的查詢中，t2 表在查詢中完全未使用，因此查詢規(guī)劃器能夠?qū)崿F(xiàn)查詢，就像它是這樣寫的：

SELECT v1, v3 FROM t1 LEFT JOIN t3 ON (t1.ipk=t3.ipk)

在撰寫本文時(shí)，只有 LEFT JOIN 被省略。此優(yōu)化尚未推廣到 RIGHT JOIN，因?yàn)?RIGHT JOIN 是 SQLite 的一個(gè)相對(duì)新的添加。這種不對(duì)稱性可能會(huì)在未來(lái)的版本中得到糾正。

18. 常量傳播優(yōu)化

當(dāng) WHERE 子句包含兩個(gè)或多個(gè)由 AND 運(yùn)算符連接的等式約束，且所有約束的親和性都相同時(shí)，SQLite 可能會(huì)使用等式的傳遞性構(gòu)造新的“虛擬”約束，以簡(jiǎn)化表達(dá)式和/或提高性能。這被稱為“常量傳播優(yōu)化”。

例如，考慮以下模式和查詢：

CREATE TABLE t1(a INTEGER PRIMARY KEY, b INT, c INT);
SELECT * FROM t1 WHERE a=b AND b=5;

SQLite 查看 “a=b” 和 “b=5” 約束，并推斷出如果這兩個(gè)約束為真，那么 “a=5” 也必須為真。這意味著可以使用 5 作為 INTEGER PRIMARY KEY 快速查找所需的行。