SQLite 學習筆記之六 - Query Planner

※ 本文主要是 SQLite 官方網頁「The SQLite Query Planner」的翻譯整理，希望能對大家有幫助！

依據 SQL statement 與 DB schema 的複雜度，同一個 SQL statement 的處理方式可能會有很多種。而 Query Planner 的任務便是在多個方案之中找出一個  Disk I/O 與 CPU 開銷最小的方案。

 

一、WHERE 子句分析

1. 如果查詢中的「WHERE」子句包含了「AND」運算元，SQLite 會以「AND」為分隔，將其拆解為更細的條件式（term）。如果 WHERE  包含了「OR 」  運算元，則整個子句都會被視為一個條件式。
2. SQLite 會分析 WHERE 字句裡的條件式是否可利用「索引」來輔助查詢？
1. 如果完全沒有索引可資利用，則 SQLite 就會對表格進行逐列檢驗（table scan）。
2. 如果完全依賴索引就可完成查詢，則  SQLite 就不會對表格做任何檢驗（如：覆蓋式索引 / covering index）。
3. 有時候，雖然有一個或多個條件式可利用索引來輔助查詢，但 SQLite 仍須對表格進行逐列檢驗。
3. SQLite 對條件式進行分析以後，可能會在 WHERE 子句中又產生新的「虛擬條件」 （virtual term） 。虛擬條件可和索引一起使用，而且虛擬條件絕不會對原始表格進行表格掃瞄。
4. 若要讓 SQLite 使用索引，則條件式必須符合以下形式之一（※ 注意：沒有「<>」！）：

   column = expression column > expression column >= expression column < expression column <= expression expression = column expression > column

   expression >= column expression < column expression <= column column IN (expression-list) column IN (subquery) column IS NULL

5. 請先建立如下的表格與「多欄位索引」（此索引也算「覆蓋式索引」）：
    
     CREATE TABLE ex1(a, b, c, d);
     CREATE INDEX idx_ex1 ON ex1(a, b, c, d);
    
6. 如果多欄位索引的起始欄位有出現在 WHERE 子句之中，那麼 SQLite 就可能會使用這個索引， 如以下查詢就是從起始欄位 a 開始、然後接著是欄位 b：
    
   sqlite> EXPLAIN QUERY PLAN SELECT * FROM ex1 WHERE a=1 AND b=1;
   0|0|0|SEARCH TABLE ex1 USING COVERING INDEX idx_ex1 (a=? AND b=?) (~9 rows
    
7. 但如果條件式使用的欄位之間有縫隙（gap），SQLite 就只會使用縫隙之前的欄位。如下查詢的條件式中使用了 a、b、d 欄位，但卻未使用「c」欄位：
    
   sqlite> EXPLAIN QUERY PLAN SELECT * FROM ex1 WHERE a=1 AND b=1 AND d=1;
   0|0|0|SEARCH TABLE ex1 USING COVERING INDEX idx_ex1 (a=? AND b=?) (~2 rows)
    
8. 承上，索引起始欄位只能和「=」或「IN」的運算元一起使用，否則 SQLite 是不會使用到右方欄位（b, c, d）的，例如：
    
   sqlite> EXPLAIN QUERY PLAN SELECT * FROM ex1 WHERE a>1 AND b=1;
   0|0|0|SEARCH TABLE ex1 USING COVERING INDEX idx_ex1 (a>?) (~25000 rows)
    
9. 承上，但有一個例外狀況，亦即起始欄位使用「=」或「IN」，而靠右方欄位是使用不相等條件式（>, >=, <, <=），例如：
    
   sqlite> EXPLAIN QUERY PLAN SELECT * FROM ex1 WHERE a=1 AND b>1;
   0|0|0|SEARCH TABLE ex1 USING COVERING INDEX idx_ex1 (a=? AND b>?) (~2 rows)
   sqlite> EXPLAIN QUERY PLAN SELECT * FROM ex1 WHERE a=1 AND b=1 AND c>1;
   0|0|0|SEARCH TABLE ex1 USING COVERING INDEX idx_ex1 (a=? AND b=? AND c>?) (~2 rows)
   sqlite> EXPLAIN QUERY PLAN SELECT * FROM ex1 WHERE a=1 AND b=1 AND c=1 AND d>1;
   0|0|0|SEARCH TABLE ex1 USING COVERING INDEX idx_ex1 (a=? AND b=? AND c=? AND d>?) (~2 rows)
    
10. 承上，但是靠右方欄位最多只能使用到兩個不等條件式： 
     
    sqlite> EXPLAIN QUERY PLAN SELECT * FROM ex1 WHERE a=1 AND b>1 AND b<5;
    0|0|0|SEARCH TABLE ex1 USING COVERING INDEX idx_ex1 (a=? AND b>? AND b<?) (~1 rows)

以下是「索引條件式」的一些例子：

1.  ... WHERE a=5 AND b IN (1,2,3) AND c IS NULL AND d='hello'
   多欄位索引中的 4 個欄位（a, b, c, d）皆會被 SQLite 使用，因為這些條件式是從索引的起始欄位開始、中間沒有縫隙，而且都是相等條件式（equality constraints ）。
2. ... WHERE a=5 AND b IN (1,2,3) AND c>12 AND d='hello'
   多欄位索引中只有 a, b 和 c 欄位會被 SQLite 使用、d 欄位不會被使用，因為 d 在索引中是在  c 的右邊、而且 c 又是使用不相等條件式。
3. ... WHERE a=5 AND b IN (1,2,3) AND d='hello'
   多欄位索引中只有 a 和 b 兩個欄位會被 SQLite 使用，d 欄位不會被使用，因為少了 c 欄位的條件式，所以產生了縫隙。
4. ... WHERE b IN (1,2,3) AND c NOT NULL AND d='hello'
   SQLite 完全不會使用這個多欄位索引，因為沒有 a 欄位的條件式，而 a 欄位是索引中最左邊的欄位，此查詢將造成「全表掃瞄」（full table scan）。
5. ... WHERE a=5 OR b IN (1,2,3) OR c NOT NULL OR d='hello'
   SQLite 完全不會使用這個多欄位索引，因為條件式都是以「OR」連接、而非以「AND」連接。此查詢將造成「全表掃瞄」。但是如果 b, c, d 這三個欄位自己也有自己個別的索引，則 SQLite 可能會採用「OR 條件式優化」的方式（或 OR-by-UNION）。 

二、BETWEEN 優化

1. 假設某 WHERE 子句的條件式如下：
    
   expr1 BETWEEN expr2 AND expr3
    
2. 則 SQLite 可能會自動加入如下的「虛擬條件式」 （virtual terms）（由一個 BETWEEN 轉換為 >= 和 <=）：
    
   expr1 >= expr2 AND expr1 <= expr3
    
3. 如果這兩個虛擬條件式最後有都被成功轉為「索引條件式」（如：BETWEEN 1 AND 3  轉換為  a >= 1 AND a <= 3），那麼 SQLite 就會忽略原來的 BETWEEN 條件式，而且也不需要對原表格進行相關的逐列檢驗了（table scan）。
4. 如果 BETWEEN 條件式沒辦法被轉換為索引條件式，而必須要對原表格進行逐行掃瞄時，而 expr1 也只會被評估一次。

三、OR 優化

SQLite  共有兩種 OR 優化方法：「將多個  OR  轉換為一個 IN」與「OR-by-UNION」。

1.  將多個 OR 轉換為一個 IN

1. 如果 WHERE 子句中以「OR」連接的條件式像下面這樣包含了多個子條件式（subterm），而這些子條件式都是同一個欄位並以多個 OR 連接：
    
     column = expr1 OR column = expr2 OR column = expr3 OR ...
    
   那麼該條件式就會重寫成像下面這個樣子（將多個  OR  轉換為一個 IN）：
    
     column IN (expr1,expr2,expr3,expr4,...)
    
2. 重寫過後的條件式如果轉為「索引條件式」，那 SQLite 就能利用索引來提升查詢效率。注意在每個以 OR 連接的子條件式裡的欄位都必須是同一個欄位，而欄位可以在「=」運算子的左邊或右邊。 

2. OR-by-UNION

1. 子條件式有可能是像「a=5」或「x>y」這樣的單一運算式，也有可能是 LIKE 或 BETWEEN 運算式，或是在一對刮號內又包含了以 AND 連接的子條件式…等等。為了要確定這些子條件式是否都能被轉換成「索引條件式」，SQLite 會把每一個子條件都視為一個完整的 WHERE 子句進行分析。
2. 如果分析的結果是每個 OR 子條件式是對應到不同的索引上，SQLite 就會像下面這樣來處理查詢（OR-by-UNION）：
    
    rowid IN (SELECT rowid FROM table WHERE expr1
     UNION SELECT rowid FROM table WHERE expr2
     UNION SELECT rowid FROM table WHERE expr3)
    
3. 上一頁重寫過後的表示式只是概念性的表示式。實際上包含 OR 限制式的 WHERE 子句並不是真的會被重寫成這個樣子。SQLite 內部的實作方式會使用比子查詢更有效率的機制（即使原表格中的「ROWID」欄位名稱因其他用途被重載，而不再指向真正的 ROWID了）。
4. 簡言之，就是先用多個索引找出每個 OR 條件式的中間結果列（candidate result）以後，再將這些列使用 UNION 操作求出最終結果列。

3. 小結

1. 在大部分的狀況下，SQLite 對 FROM 子句中的一個表格只會使用單一個索引，但上述的第二種 OR 優化方法「OR-by-UNION」則是其中的例外。在此情況下，SQLite 可能會針對個別 OR 子條件式採用不同的索引。
2. SQLite 並不一定會對任何查詢都採用上述的 OR 優化方法。SQLite 的 query planner 是以成本為基礎的（cost-based），所以會在評估各計畫可能消耗的 CPU 和磁碟 I/O 成本之後，再從中選擇最快的計畫。
3. 如果 WHERE 子句中的 OR 子條件式很多、或者個別 OR 子條件式中的索引並不是那麼有利用價值，那 SQLite 可能會決定採用不同的演算法，甚至進行全表掃瞄。
4. 應用程式開發人員可以在 SQL 前面加上「EXPLAIN QUERY PLAN」，以對 SQLite 選定的查詢計畫取得比較高層次的瞭解。

四、LIKE 優化

LIKE 或 GLOB 運算子有時候也可以用來限縮索引，但使用上有如下諸多限制：

1. LIKE 或 GLOB 左邊必須是具備「TEXT 親和性」（affinity）的索引欄位。
2. LIKE 或 GLOB 右邊必須是「字串」或「字串參數」（parameter），但開頭不能是萬用字元。
3. LIKE 運算子不能出現 ESCAPE 運算子。
4. 用來實作 LIKE 和 GLOB 的內建函式必須未被 sqlite3_create_function() API 重載過（overload）。
5. 如果是 GLOB 運算子，索引欄位必須使用內建的「BINARY」整理序列（collation sequence）。
6. 如果是 LIKE 運算子：
1. 在「case_sensitive_like」模式開啟的狀況下，索引欄位就必須是「BINARY」整理序列（collation sequence），此時對於 latin1 字元（ASCII 編碼 127 以下）是區分大小寫的，例如「'a' LIKE 'A'」的結果為 true。
2. 在「case_sensitive_like」模式關閉的狀況下，索引欄位就必須是「 NOCASE」整理序列，此時對於 latin1 字元是忽略大小寫的， 例如「‘a’ LIKE ‘A’」的結果為 false。
3. 國際性編碼在 SQLite 中都是 case-sensitive 的，除非 AP 自行定義了整理序列或者在 like() 函式使用了非 ASCII 字元。

更多詳細資訊請參考 SQLite 官方網頁「The SQLite Query Planner – 4.0 The Like optimization」一節。

五、JOIN

SQLite 在進行「WHERE 子句分析」之前，INNER JOIN 裡的 ON 和 USING 子句都會被轉換成 WHERE 子句中的限制式。因此，使用較新的 SQL92 JOIN 語法並不會比使用 SQL89 以逗號分隔的 JOIN 語法得到較多好處。兩者最終都能達到同樣的目的。

如果是 LEFT OUTER JOIN，狀況會比較複雜，以下兩個查詢是不相等的；如果是 INNER JOIN，以下兩個查詢會是相等的：

 

  SELECT * FROM tab1 LEFT JOIN tab2 ON tab1.x=tab2.y;

  SELECT * FROM tab1 LEFT JOIN tab2 WHERE tab1.x=tab2.y;

 

SQLite 會對 OUTER JOIN 中的 ON 和 USING 子句進行特殊處理：如果 JOIN 右方的表格是在空列上（null row），則 ON 和 USING 子句裡的限制式就不適用；但如果是在 WHERE 子句中就適用。

SQLite 會把 LEFT JOIN 的 ON 或 USING 子句放入 WHERE 子句之中，最後的結果就是被其轉換為一般的 INNER JOIN — 儘管 INNER JOIN 的執行速度會比較慢。

 

1. 表格 JOIN 順序

1. 目前 SQLite 只使用迴圈式 JOIN。也就是說，在 SQLite 內部，JOIN 其實是以「巢狀迴圈」（nested loops）實作的。
2. 預設的巢狀迴圈 JOIN 順序是：FROM 子句最左邊的表格會成為外層迴圈（outer loop）、而最右邊的表格式則會成為內層迴圈（inner loop）。
3. 改變巢狀迴圈的順序如果能幫助 SQLite 選擇更好的索引，那 SQLite 可能就會這麼做。
1. INNER JOIN 的迴圈順序可能會被  SQLite 改變。
2. LEFT OUTER JOIN 的迴圈順序絕不會被 SQLite 改變（因為改變以後，意義就不同，結果也會不一樣了）。
3. OUTER JOIN 左右兩邊的 INNER JOIN 的迴圈順序也可能會被 SQLite 改變（如果 SQLite 認為這是有利的），但 OUTER JOIN 還是會依照其出現的先後順序來運算。
4. 當選擇 JOIN 子句中的表格順序時，SQLite 會使用貪婪的演算法（greedy algorithm） ，其時間複雜度為 O(N²) 。正因如此，SQLite 可以對 50 ~ 60 種連接方式的 JOIN 進行有效的規劃。
5. 改變 JOIN 順序是自動進行的，而且通常運作良好，所以程式設計人員不須為此費心，特別是當有用「ANALYZE」指令來蒐集索引的統計資訊時。但偶爾還是需要程式設計師提供一些線索。
6. 考慮以下的 schema：
   
    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);
7. 以上的 schema 定義了一個有向圖（directed graph）的資料結構， 並儲存了每一個點（node）的名稱（name）。現在再考慮以下的 INNER JOIN 查詢：
   
    SELECT *
       FROM edge AS e,
            node AS n1,
            node AS n2
      WHERE n1.name = 'alice'
        AND n2.name = 'bob'
        AND e.orig = n1.id
        AND e.dest = n2.id;
8. 以上查詢希望找出所有從節點「alice」到節點「bob」的邊。對此，SQLite  可能會有兩個方案（事實上會有 6 種不同的方案，但是在這邊我們只要考慮這兩個就好了）。虛擬碼（pseudocode）如下：
1. 方案 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.id
           return n1.*, n2.*, e.*
         end
       end
     end
2. 方案 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.*
         end
       end
     end
9. 這兩個選擇都會使用同樣的索引來加速每一個迴圈。唯一差別在於這些迴圈出現於巢狀的順序。
10. 所以哪一個查詢計畫比較好呢？答案取決於在 node 和 edge 表格內會找到什麼樣的資料。假設「alice」節點的數量是 M、而「bob」節點的數量是 N。考慮下列兩種情況：
1. 第一個情況：如果 M 和 N 都是 2，但在這 4 個點上都有上千個邊。在此狀況下，選擇「方案一」較好。使用「方案一」，內層迴圈會尋找兩點之間的邊。但因為「alice」和「bob」都只有 2 個而已，因此內層迴圈總共只要執行 4 次即可，比「方案二」快很多。方案二的最外層迴圈雖然只執行 2 次，但是因為來自 alice 的邊數量很多，所以第二層迴圈可能就會執行數千次，相當之慢。因此在此情況下，我們偏好「方案一」。
2. 第二個情況：如果 M 和 N 都是 3500。此時 Alice 的數量很多，但是這些節點之間只有 1 ~ 2 個邊相連。在此狀況下，選擇「方案二」較好。使用方案二，外層迴圈仍然要執行 3500 次，但是中間迴圈卻只要執行 1~2 次、內層迴圈只要執行 1 次。所以內層迴圈執行總次數約為 7000 次。另一方面，方案一外層與中間迴圈都要執行 3500 次，結果中間迴圈就要執行  1200 萬次。因此，在第二個情況下，方案二比方案一快了 2000 倍！
11. 由上例可以看出「方案一」或「方案二」比較好，主要是取決於表格內的資料結構。但是 SQLite 預設會選擇哪一個方案？從 3.6.18 版以後，若未執行 ANALYZE，SQLite 會選擇「方案二」。但若執行過 ANALYZE，SQLite 就會依據統計資訊選擇較快的方案。 

2. 查詢計畫的手動控制

有兩種方式可對查詢計畫進行手動控制，一種是捏造  ANALYZE 的統計數據（儲存於 sqlite_stat1 和 sqlite_stat2 表格中），另一種是使用 CROSS JOIN。

• 捏造 ANALYZE 的統計數據：
1. 一般不建議採用此方法，除非是像下面這樣的情境。
2. 在開發時期，先建立一個包含特定資料的雛形 DB，然後執行  ANALYZE 指令以針對該 DB 蒐集統計資訊，然後再把這些統計資訊與應用程式儲存在一起。
3. 在部署時期，建立一個新的 DB 檔案，執行  ANALYZE 指令以建立 sqlite_stat1 和 sqlite_stat2 表格，然後再把之前從雛形 DB 取得的統計資訊複製進這兩個表格。如此，應用程式就可以使用這些統計資訊了。
• 使用 CROSS JOIN：
1. 使用 CROSS JOIN，以這個語法連接的兩張表格就不會被 SQLite 改變順序。
2. 假設原查詢如下：
   
   SELECT *
       FROM node AS n1,
            edge AS e,
            node AS n2
      WHERE n1.name = 'alice'
        AND n2.name = 'bob'
        AND e.orig = n1.id
        AND e.dest = n2.id;
3. 用「CROSS JOIN」取代逗號「,」，原來邏輯仍然不變，但可將表格的順序固定成： n1, e, n2。
   
   SELECT *
       FROM node AS n1 CROSS JOIN
            edge AS e CROSS JOIN
            node AS n2
      WHERE n1.name = 'alice'
        AND n2.name = 'bob'
        AND e.orig = n1.id
        AND e.dest = n2.id;
   
4. 如果改成上面這個樣子，SQLite 就會改採「方案二」了。
5. 注意，一定要使用關鍵字「CROSS JOIN」才能關掉表格 JOIN 順序的最佳化
6. INNER JOIN, NATURAL JOIN, JOIN 以及其他組合的運作方式其實也跟以逗號連接的 JOIN 一樣，SQLite 都會視狀況進行表格 JOIN 順序的調整，所以也可使用這個方法
7. 注意， SQLite 本來就不會對「OUTER JOIN」進行表格 JOIN 順序的調整（因為改變表格 JOIN 順序會改變查詢的結果）。 

六、在多個索引之間做選擇

1. SQLite 針對在 FROM 子句中的每個表格最多只會使用一個索引（「OR 優化」除外），也會盡可能對每張表格至少使用一個索引。有時候，一個表格可能會有兩個或更多的索引可供 SQLite 選擇。例如：
    
     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;
    
2. 以上例的 SELECT 來說，SQLite 有可能先使用 ex2i1 去尋找表格 ex2 中包含「x=5」的資料列，然後再對 ex2 進行「y=6」的逐列檢驗；也有可能先使用  ex2i2 去尋找表格 ex2 中包含「y=6」的資料列，然後再對 ex2 進行「x=5」的逐列檢驗。
3. 當遇到有多個索引可以選擇的問題時，SQLite 試著估計每個查詢計畫的總工作量。然後從中選出總工作量最小的查詢計畫。
4. 為了幫助 SQLite 能估計出更精確的工作量，使用者可執行「ANALYZE」指令來掃瞄 DB 中所有索引並且蒐集相關統計資料。蒐集到的統計資料會儲存在以「sqlite_stat」開頭的表格之中。因為這些表格不會在 DB 內容改變之後自動更新，所以最好再重新執行一次 ANALYZE。
5. 「sqlite_statN」表格包含了這些索引的可用性。例如，表格「sqlite_stat1」可能指出在欄位 x 的相等條件式會平均減少10 列的搜尋空間、而在欄位 y 的相等條件式可能會平均減少 3 列的搜尋空間。在這種狀況下，SQLite 可能就會選擇「ex2i2」這個索引（有問題!?）。
6. 如想讓 SQLite 對 WHERE 子句裡的條件式不使用索引，可在欄位名稱前加上「+」這個一元運算子。「+」是一個 no-op，不會讓該條件式的檢驗變慢。如果將上例查詢改寫成像下面這樣，這會強制 SQLite 不使用「ex2i1」索引，所以會改用「ex2i2」索引：
    
   SELECT z FROM ex2 WHERE +x=5 AND y=6;
    
7. 注意「+」也會使表示式中的「型態親和性」（Type Affinity）失效，而某些狀況下也會改變表示式的意義。例如，假設上例的 x 欄位原先具備「TEXT 親和性」，那表示式「x=5」將會以文字處理。但因為「+」運算子移除了這個親和性。所以「+x=5」表示式將會把 x 欄位中的文字拿來跟數值 5 做比較，其結果就會變成 false。 

七、範圍查詢

1. 假設上一個情境微調成下面這樣：
    
   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;
    
2. 接著我們假設欄位 x 的值介於 0~1,000,000 之間，而欄位 y 的值介於 0~1,000 之間。在這個情況下，在 x 欄位上的範圍限制將會用 10,000 的因數（factor）來減少搜尋空間、在 y 欄位上的範圍限制只會用 10 的因數來減少搜尋空間。因此 SQLite 應該會選擇 「ex2i2」索引。
3. 但是只有在編譯時期，有把「SQLITE_ENABLE_STAT3」選項打開，SQLite 才會採取這樣的查詢計畫。 「SQLITE_ENABLE_STAT3」選項會使「ANALYZE」蒐集欄位內容的統計資料（並儲存於「sqlite_stat3」表格內），以便 SQLite 在「範圍查詢」時做出更好的策略。
4. 「sqlite_stat3」表格裡的統計資料只有在條件右手邊是常數或參數，而非運算式的時候有用。另外一個限制是：這些統計資料只用於索引最左邊的欄位。例如以下的狀況：
    
   CREATE TABLE ex2(w,x,y,z);
   CREATE INDEX ex2i1 ON ex2(w, x);
   CREATE INDEX ex2i2 ON ex2(w, y);
   SELECT z FROM ex3 WHERE w=5 AND x BETWEEN 1 AND 100 AND y BETWEEN 1 AND 100;
    
5. 因為此時欄位 x 和 y 都不是索引的最左方欄位。所以蒐集到的統計資料並無法幫助此查詢在欄位 x 和 y 找出合適的範圍限制。 

八、避免表格掃瞄

1. 當 SQLite 使用索引來加速查詢時，一般流程都是先在索引上進行 binary search，然後從索引取出 ROWID，最後再在原始表格上進行一次 binary search。
2. 因此索引查詢通常包含了兩次 binary search。但如果查詢所需要的欄位都已經可以從索引中取得的話，SQLite 就會直接使用索引中的值，而不會對原始表格進行資料查找。所以會少掉一次對每一資料列的 binary search（表格掃瞄），而且會讓許多查詢變快兩倍，請參考「涵蓋式索引」（covering index）。 

九、ORDER BY 優化

1. SQLite 會盡可能地嘗試利用索引來滿足查詢中的 ORDER BY 子句，其分析的步驟和「WHERE 子句分析」類似，SQLite 會從中選出最快的方案。
2. 詳細可參考「WHERE 子句分析」和「QUERY PLANNING – 排序」。

十、子查詢扁平化（Subquery flattening）

1. 當 FROM 裡頭出現子查詢時，最簡單的方式就是先將該子查詢轉成暫存表格（ transient table），然後再對該表格進行 SELECT 查詢。但因為這個暫存表格上面並沒有任何索引，而且外層 SELECT 查詢（很可能是 JOIN）可能對這個表格進行「全表掃瞄」，所以這個方法並不是那麼好。
2. 要解決這個問題，SQLite 會嘗試將 FROM 子句中的子查詢扁平化（subquery flattening） 。大致的步驟是，先將子查詢的 FROM 子句插入外圍的查詢，然後重寫外層的查詢以取得原子查詢的結果集。例如：
   
   SELECT a FROM (SELECT x+y AS a FROM t1 WHERE z<100) WHERE a>5;
   經過「子查詢扁平化」可能會變成下面這個樣子：
   
   SELECT x+y AS a FROM t1 WHERE z<100 AND a>5;
3. 必須符合下列所有條件，SQLite 才會對查詢進行扁平化 ：
1. 子查詢和外層查詢都不能使用聚合函式（Aggregate Functions ，如：AVG()、COUNT()、MAX()、MIN()、SUM()、TOTAL()…等）。
2. 子查詢不是一個聚合函式或外層查詢不是 JOIN。
3. 子查詢不是 LEFT OUTER JOIN 的右方運算元。
4. 子查詢不是 DISTINCT 或外層查詢不是 JOIN。
5. 子查詢不是 DISTINCT 或外層查詢沒有使用聚合函式。
6. 子查詢未使用聚合函式或者外層查詢不是 DISTINCT。
7. 子查詢必須有 FROM 子句。
8. 子查詢沒有使用 LIMIT 或外層查詢不是 JOIN。
9. 子查詢沒有使用 LIMIT 或外層查詢沒有使用 聚合函式。
10. 子查詢未使用聚合函式或外層查詢沒有使用 LIMIT。
11. 子查詢和外層查詢都沒有 ORDER BY 子句。
12. 子查詢和外層查詢都沒有使用 LIMIT。
13. 子查詢沒有使用 OFFSET。
14. 外層查詢不是複合 SELECT （compound select） 的一部份或子查詢內沒有 ORDER BY 和 LIMIT 子句。
15. 外層查詢不是聚合函式或子查詢沒有 ORDER BY。
16. 子查詢不是複合 SELECT ，或者是完全以非聚合函式組成的 UNION ALL 複合子句，而且：
1. 父查詢不是複合 SELECT 的一部份。
2. 父查詢不是聚合函式或 DISTINCT 查詢
3. 父查詢的 FROM 子句中沒有其他表格或者 sub-select。
4. 父查詢和子查詢可能包含 WHERE 子句。並遵守規則 11、12 以及 13，他們可能也包含 ORDER BY 、LIMIT 或 OFFSET 子句。
17. 如果子查詢是複合式 SELECT 那父查詢 ORDER BY 子句的所有條件式必須是子查詢的欄位簡單參照。
18. 子查詢不能使用 LIMIT 或外層查詢沒有 WHERE 子句。
19. 如果子查詢是複合式 SELECT，那必須沒有使用 ORDER BY 子句。
4. 讀者不需瞭解或記得以上的規則。此份規則只是在強調 SQLite 內部決定要對查詢進行扁平化工作是相當複雜的。
5. 因為 VIEW  會被轉換為子查詢，所以就 VIEW  來說，「查詢扁平化」是一項重要的優化技巧。 

十一、MIN/MAX 優化

1. 假設有合適索引可資使用、而查詢又符合下列形式的話，那執行此類查詢的時間複雜度就會是對數時間（ logarithmic time）：
    
      SELECT MIN(x) FROM table;
      SELECT MAX(x) FROM table;
    
2. 查詢必須完全符合以上的形式，SQLite 才會對此進行優化（亦即只有欄位和表格的名稱可以改變而已）。加上 WHERE 子句或者對結果進行任何算術運算都是不允許的。而且結果集只能是單一欄位。而 MIN 或 MAX 函式中的欄位必須是索引過的欄位。

十二、自動索引（Automatic Indices）

1. 當如果沒有索引可以用來加速查詢時，SQLite 可能會在單一 SQL 執行期間建立一個自動索引，並使用該索引來提升查詢效能。但因為建立自動索引的時間複雜度是 O(NlogN)（N 是表格中的資料列數）、而執行「全表掃瞄」只有 O(N)，所以只有當 SQLite 預期「全表掃瞄」的次數會大於 logN 時，SQLite 才會採用自動索引。假設以下範例：
    
     CREATE TABLE t1(a,b);
     CREATE TABLE t2(c,d);
     -- Insert many rows into both t1 and t2
     SELECT * FROM t1, t2 WHERE a=c;
   

    
2. 在上例中，如果 t1 和 t2 都約有 N 列，如果沒有任何索引的話，該查詢約需要 O(N*N)  的時間。另一方面，先為 t2 表格建立索引需要 O(NlogN) 的時間、再利用該索引去進行查詢需要再一個 O(NlogN) 的時間 。如果沒有執行過 ANALYZE，SQLite 會猜測 N 是 100 萬，因此它會認為建立自動索引會是比較便宜的方案。
3. 自動索引或許能用在如下的子查詢：
   
     CREATE TABLE t1(a,b);
    CREATE TABLE t2(c,d);
    -- Insert many rows into both t1 and t2
    SELECT a, (SELECT d FROM t2 WHERE c=b) FROM t1;
4. 在這個例子裡表格，表格 t2 被用在子查詢之中，並以欄位 c 參照到  t1 表格的 b 欄位。如果兩張表都包含 N 列，SQLite 會認為子查詢會執行 N 次，因此它會認為在表格 t2 上面建立一個自動的、暫時的索引，然後用這個索引來加速子查詢。
5. 此功能可在執行時期以「PRAGMA automatic_index;」指令來關閉，也可在編譯時期用「SQLITE_OMIT_AUTOMATIC_INDEX」選項來