本文譯自《Query Planning》

概述

SQL最好的特性就是它是一種描述性語言也榄，而不是過程式語言巡莹。不光是SQLite，在所有的SQL實現(xiàn)中它都是這樣甜紫。當你編寫SQL時降宅，你告訴系統(tǒng)你想要得到的結果，而不是如何去計算它棵介。決定“如何計算結果”這件事由數(shù)據(jù)庫引擎中的查詢計劃器來完成钉鸯。

對于每一條給定的SQL語句，可能有成百上千種不同的算法可以實現(xiàn)它邮辽。盡管每種算法都能得出正確結果，但有些算法比其他的運行的更快贸营。查詢計劃器是一個AI吨述，它盡量為每條SQL語句找出最快最高效的算法。

大多數(shù)情況下钞脂，SQLite的查詢計劃器工作的很好揣云。然而，查詢計劃器需要與索引配合冰啃，這些索引通常必須由程序員指定邓夕。查詢計劃器在個別時候也會得出次優(yōu)解刘莹，這時程序員可能希望提供額外的提示來指導查詢計劃器的工作。

這篇文檔提供了關于SQLite查詢計劃器和查詢引擎工作原理的背景知識焚刚。程序員可以使用這些信息創(chuàng)建出更有效的索引点弯，或在必要時向查詢計劃器發(fā)出提示。

更多的信息請參考 SQLite query planner和next generation query planner等文檔矿咕。

1. 搜索

1.1 不加索引的表

SQLite中絕大多數(shù)表都包含一個unique列抢肛，如 rowid 或INTEGER PRIMARY KEY，有一類表是例外碳柱，那就是無ROWID的表捡絮。邏輯上講，各個行按rowid的升序存儲莲镣。本文以FruitsForSale這個表為例福稳，這個表記錄了各種水果的名稱，產(chǎn)地和市價瑞侮。表的schema如下：

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

我們向表中插入一些數(shù)據(jù)（純屬虛構）灵寺，這張表的邏輯存儲結構如圖1：

圖1：FruitsForSale表的邏輯結構

在這個例子中，rowid不是連續(xù)的区岗，但是是有序的略板。SQLite通常從1開始創(chuàng)建rowid，并每次自增1慈缔。但如果行被刪除了叮称，rowid之間可能出現(xiàn)空隙。應用層可以選擇控制rowid的分配藐鹤，所以新的行不一定會被添加到最底部瓤檐。不過無論如何，rowid是唯一的娱节，并保持升序挠蛉。

假如你想要查詢peach的價格，那么SQL語句如下所示：

SELECT price FROM fruitsforsale WHERE fruit='Peach';

為了滿足這個查詢肄满，SQLite讀取表中的每一行谴古，檢查fruit列是否為Peach，如果是則輸出對應的price稠歉。這個過程如圖2所示掰担。

圖2：全表掃描

這個算法被稱為全表掃描，因為必須遍歷表才能找到感興趣的行怒炸。對于只有7行的表來說带饱，全表掃描可以接受，但如果表包含7百萬行的話，全表掃描為了找出幾字節(jié)的數(shù)就要讀取幾M字節(jié)勺疼。因此教寂，我們要盡力避免全表掃描。

1.2 按rowid查找

一種避免全表掃描的技術是按rowid查找（或者按 INTEGER PRIMARY KEY查找执庐，它們等價）酪耕。為了查找peach的價格，我們查詢rowid為4的行：

SELECT price FROM fruitsforsale WHERE rowid=4;

因為信息按照rowid順序存儲在表中耕肩，SQLite可以用二分法找出正確的行因妇。對于N行的表，可以用O（logN）的時間查出所需要的行猿诸，而全表掃描需要O（N）的時間婚被。如果表包含一千萬條數(shù)據(jù)，按rowid查找快了大約一百萬倍梳虽。

image.png

1.3 按索引查找

按rowid查找的問題就是址芯，我們想查的是peach的價格，誰知道peach的rowid是不是4呢窜觉？

為了讓最初的查詢更有效率谷炸，我們可以為fruit列增加索引：

CREATE INDEX Idx1 ON fruitsforsale(fruit);

索引是與原fruitsforsale表相似的另一張表，但是被索引內容（這個例子中是fruit列）被放在rowid前邊禀挫，并且所有的行按被索引列排序旬陡。圖4給出了Idx1的邏輯視圖。

圖4：fruit列的索引

fruit列是用來給元素排序的主鍵语婴，而rowid是在fruit相同時給元素排序的次級鍵描孟。注意，因為rowid是唯一的砰左，因此rowid和fruit組成的復合鍵也是唯一的匿醒。

新的索引可以被用作實現(xiàn)一個更快的查找peach價格的算法。

一開始缠导，先對Idx1索引進行fruit=‘Peach’的二分查詢廉羔，SQLite能在Idex1上進行二分查詢，是因為Idex1是按照fruit列排序的僻造。在Idx1查找到fruit=‘Peach’的行之后憋他，數(shù)據(jù)庫引擎可以提取出rowid。然后數(shù)據(jù)庫引擎根據(jù)rowid嫡意，對原表再進行一次二分查找举瑰。最后根據(jù)原表的行，可以得到Peach對應的price蔬螟。這個過程如圖5所示：

圖5：使用索引查找Peach的價格

使用上邊的方法，SQLite必須使用兩次二分查找來查出peach的價格汽畴。然而對于一個數(shù)據(jù)量大的表來說旧巾，這仍比全表掃描快很多耸序。

1.4 多行結果

前一個查詢中，fruit=‘Peach’這個約束只有一行滿足鲁猩。但是當結果為多行時坎怪，也可以使用相同的技術。假設我們現(xiàn)在查找Oranges的價格

SELECT price FROM fruitsforsale WHERE fruit='Orange'

圖6：使用索引查找Orange的價格

在這種情況下廓握，SQLite仍然使用一次二分查找來搜索第一個fruit=‘Orange’的行搅窿。然后它根據(jù)rowid回原表中查找價格。不過與原先不同隙券，數(shù)據(jù)庫引擎讀取下一行男应，并將回原表查詢的操作重復一遍。讀取索引的下一行的開銷遠遠低于一次二分查找娱仔，以至于可以忽略不計沐飘，因為下一行往往與剛讀取的行在相同的頁中。所以我們估計總開銷為3次二分查找牲迫。如果有K行結果耐朴，那么查詢的開銷為（K+1）*logN。

1.5 多個AND連接的WHERE子句

接下來盹憎，假設你不管要查Orange的價格筛峭，而且要求Orange的產(chǎn)地是California。SQL語句如下所示：

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

一種可選方案是先找出所有Orange行陪每，然后再過濾產(chǎn)地不為CA的行影晓，這個過程如圖7所示

圖7

大多數(shù)情況下，這是個很合理的方案奶稠。不過數(shù)據(jù)庫引擎必須為Florida的Orange做額外的二分查找俯艰，所以可能沒有我們期望的那么快，盡管對多數(shù)應用來說锌订，這足夠快了竹握。

假設我們再為state創(chuàng)建索引：

CREATE INDEX Idx2 ON fruitsforsale(state);

state索引和fruit索引的原理相同，只不過主鍵變成了state辆飘。在我們的例子中啦辐，state列的取值比較少，因此索引中每個state對應的行較多蜈项。

使用新的Idx2索引芹关，SQLite有了更多選擇：查出所有產(chǎn)自CA的水果，然后從其中過濾出Orange紧卒。

圖9

使用Idx2代替Idx1導致SQLite得出了不同的行集侥衬，但是最終結果是相同的。這非常重要，索引不改變查詢結果轴总，只是加快查詢速度直颅。這里使用Idx1和使用Idx2的查詢時間相同，所以Idx2并沒有提升性能怀樟。

最終兩個查詢花費了相同的時間功偿，那么SQLite最終會選擇哪個索引呢？如果ANALYZE命令在數(shù)據(jù)庫上執(zhí)行往堡，那么SQLite會獲得一個收集索引數(shù)據(jù)的機會械荷，然后SQLite會知道Idx1通常將查詢范圍縮小到1行，而Idx2通常將查詢范圍縮小到2行虑灰。所以吨瞎，如果沒有其他條件，SQLite將會選擇Idx1瘩缆，因為它通常會讓搜索范圍變得更小关拒。

這個選擇不是確定的，因為它依賴ANALYZE提供的數(shù)據(jù)庸娱。如果ANALYZE沒有運行着绊，那這個選擇就是隨意的。

1.6 多列索引

為了實現(xiàn)多個AND連接的WHERE子句的最大性能熟尉，你十分需要一個多列索引來覆蓋每一個AND子句归露。這種情況下，我們創(chuàng)建在fruit列和state列上創(chuàng)建一個新的索引斤儿。

CREATE INDEX Idx3 ON FruitsForSale(fruit, state);

圖10：一個兩列索引

多列索引和單列索引的形式相同剧包，都是rowid跟在被索引列后邊。唯一的區(qū)別是現(xiàn)在被索引列有兩個往果。最左邊的列是用來給整個索引排序的主鍵疆液。因為rowid確保是唯一的，所以即使所有除rowid的列都相同陕贮，也能保證索引行的唯一性堕油。

使用新的多列索引Idx3，SQLite有可能只用兩次二分查找就能找出CA的Orange肮之。

圖11

因為Idx3包含了所有WHERE子句中要查找的列掉缺，所以SQLite可以用一次二分查找搜索出一個rowid，然后回原表再做一次二分查找戈擒。這里沒有無效的查找眶明，因此效率更高。

注意筐高，這里Idx3包含了Idx1的所有信息搜囱，所以在Idx3存在的情況下丑瞧，我們不再需要Idx1。如果要查找Peach的價格犬辰，我們只需要使用Idx3嗦篱，并忽略它的“state”列冰单。

SELECT price FROM fruitsforsale WHERE fruit='Peach';

圖12

由此可見幌缝，數(shù)據(jù)庫設計的一條原則是，schema不應該包含兩個這樣的索引诫欠，其中一個索引是另一個索引的前綴涵卵。刪除其中列較少的索引，SQLite仍能高效地查找荒叼。

1.7 覆蓋索引

通過雙列索引轿偎，查詢California Orange的價格變得更快。但是如果創(chuàng)建一個包含price的三列索引被廓，SQLite可以做的更快坏晦。

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

圖13

新的索引包含了查詢所要用到的所有列，WHERE子句中的和要輸出的嫁乘。我們稱這種索引為覆蓋索引昆婿。使用這種索引時，SQLite不需要回原表查詢蜓斧。

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

圖14

由此可見仓蛆，將被輸出的列也加入索引，我們可以避免回原表查詢的操作挎春，來讓二分查找的次數(shù)減半看疙。這可以讓查詢速度獲得大概兩倍的提升。但是另一方面直奋，這只是一個細微的優(yōu)化能庆，兩倍的提升并不像剛加索引時百萬倍的提升那樣戲劇性。對大多數(shù)查詢來說脚线，1ms和2ms的開銷沒什么差別搁胆。

1.8 多個OR連接的WHERE子句

多列索引只在約束條件用AND連接時起作用。所以Idx3和Idx4只在搜索既是Orange殉挽，又生長在California的水果時有用丰涉。如果我們想要查找Orange，或者生長在California的水果斯碌，這兩個索引則起不到作用一死。

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

當處理OR連接的WHERE子句時，SQLite檢查每個被OR連接的條件傻唾，并且盡力對每個子句都使用索引投慈。然后對各個條件查出的rowid取并集承耿。這個過程如下圖所示：

圖15

上圖顯示了SQLite先計算各個組的rowid，然后對它們取并集伪煤，最后回原表查詢加袋。實際上rowid查找和求并集是交替進行的。SQLite一次使用一個索引來查找rowid抱既，同時將它們標記為已查過职烧，來避免之后出現(xiàn)重復。當然防泵，這只是一個實現(xiàn)細節(jié)蚀之。上圖很好地概述了算法過程，雖然不是完全精確捷泞。

為了讓上邊的取并集技術（OR-by-UNION）奏效足删，每個被OR連接的WHERE子句必須要有一個索引。即使只有一個子句沒被索引锁右，那么為了找出這個子句對應的rowid失受，SQLite必須進行全表掃描。如果要進行全表掃描咏瑟，那么之前那些并集拂到，二分查找操作也就么必要了，直接在全表掃描時全都查出來就行了响蕴。

我們可以發(fā)現(xiàn)谆焊，通過取并集實現(xiàn)OR（OR-by-UNION）的技術可以被推廣到AND。被AND連接的WHERE子句可以使用多個索引查詢rowid浦夷，然后取交集辖试。許多數(shù)據(jù)庫引擎就是這么做的。但是這比只是用一個索引的性能提升很小劈狐，所以SQLite目前沒有實現(xiàn)這種技術罐孝。然而，SQLite未來版本可能會支持取交集實現(xiàn)AND（AND-by-INTERSECT）肥缔。

2. 排序

除了加快查找莲兢，SQLite以及其他的SQL數(shù)據(jù)庫引擎也可以使用索引來完成ORDER BY子句。換句話說，索引除了能加快搜索，也能加快排序焊唬。

當沒有合適的索引可以用時，一個帶ORDER BY的查詢必須分步驟進行排序谒兄。考慮如下的查詢：

SELECT * FROM fruitsforsale ORDER BY fruit;

SQLite先查出所有輸出社付，然后通過sorter對結果進行排序承疲。

圖16

如果輸出行數(shù)為K邻耕，排序的復雜度為K*logK。如果K很小燕鸽，那么排序的時間無關緊要兄世，但如果像上邊這樣，K等于表的總行數(shù)啊研，那么排序花費的時間會遠大于全表掃描的時間御滩。此外，整個輸出的中間結果被存在臨時存儲中（可能是硬盤悲伶，也可能是內存艾恼，取決于許多編譯時和運行時的設置），這意味著查詢將消耗大量臨時存儲空間麸锉。

2.1 按rowid排序

因為排序操作開銷很大，SQLite會努力避免排序舆声。如果SQLite能確定輸出結果已經(jīng)按照指定的方式排序花沉，那么它不會在進行排序操作。所以媳握，比如你希望輸出按照rowid的順序碱屁，那么排序操作就不會執(zhí)行。

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

為了查出按fruit排序的rowid，Idx1索引被從前到后掃描（如果有DESC椿肩，那么就是從后到前掃描）瞻颂。對于每一個rowid，都需要用一次二分查詢來查出對應的行郑象。通過這種方式贡这，不需要額外的排序步驟就能使結果按順序輸出。

但這真的節(jié)省了時間么扣唱？如果我們不使用索引藕坯，全表排序的復雜度為NlogN团南，因為他要為N個數(shù)據(jù)排序。然而當我們使用Idx1時炼彪，我們必須要做N次復雜度為logN的二分查找吐根，所以復雜度仍然是NlogN。

SQLite使用基于開銷的查詢計劃器辐马。當有兩個或更多可選方案時拷橘，SQLite試圖分析各個方案的總開銷，然后選擇開銷最低的方案喜爷。開銷的計算主要考慮運行時間冗疮，它可能根據(jù)表的大小和WHERE子句的情況而變化。但通常來講檩帐，索引排序可能會被選擇术幔。因為它不需要將結果集存進臨時存儲中，因而空間開銷更小湃密。

2.3 使用覆蓋索引排序

如果能使用覆蓋索引诅挑，那么多次根據(jù)rowid回原表查詢的操作就能避免，開銷會產(chǎn)生戲劇性的降低泛源。

圖19

通過一個覆蓋索引拔妥，SQLite可以直接將索引從頭到尾遍歷一遍，然后輸出結果达箍，這只需要O（N）的開銷没龙，也不需要大量的額外存儲。