DocBook 的 Line Numbering 和 Code Highlighting

最近在製作 DocBook 文件時，遇到了「Line Numbering」和「Code Highlighting」問題，花了三天的時間終於解決，特別筆記在此紀錄一下解決的步驟。

首先，說一下前置作業：

1. 取得「docbook-xsl」。從 SourceForge下載「docbook-xsl-1.?.?.zip」，請特別留意版本號！不要太新、也不要太舊，網址在：http://sourceforge.net/projects/docbook/files/docbook-xsl/ ，我自己下載的是 「docbook-xsl-1.78.1.zip」。
2. 取得 XSLT 1.0 proccessor —— Saxon 或 Xalan，也一樣請留意版本號：
1. Saxon：請從 http://saxon.sourceforge.net/#F6.5.5 下載，取得 Saxon 6.5.5 就好了，我自己下載的是「saxon6-5-5.zip」。
2. Xalan：它被包在 Xerces2 Java 裡了，請從 http://xerces.apache.org/mirrors.cgi#binary
   下載 Binary 和 Tools，我自己下載的是「Xerces-J-bin.2.11.0.zip」和「Xerces-J-tools.2.11.0.zip」。
3. 取得 XSLT Syntax Highlight  —— xslthl，請從 http://sourceforge.net/projects/xslthl/ 下載，我自己下載的是「xslthl-2.1.0-dist.zip」。
4. 下載完上述檔案後，把它們解開在「D:\docbook」下方，也就是像這樣：
• docbook-xsl-1.78.1\
• saxon6-5-5\
• tools\
• xerces-2_11_0\
• xslthl-2.1.0\
5. 閱讀「DocBook XSL: The Complete Guide 4th Edition」的這兩篇：
1. Chapter 27. Program listings - Line numbering
2. Chapter 27. Program listings - Syntax highlighting

此外，要提醒的是：只有「Saxon」和「Xalan」才支援「Line Numbering」和「Code Highlighting」這兩項功能， xmltproc 並不支援喔！

接著，請準備好以下三個檔案（其內容列於本文底部），並盡量都使用一樣的編碼（如 UTF-8），也放到 D:\docbook  下面：

1. my_article.xml：DocBook 文件。
2. my_article.xsl：DocBook XSL 樣式檔。
3. my_code.java：一段 Java 程式碼。

然後，在 D:\docbook 下執行以下指令，就可將 DocBook 格式轉換為 HTML 格式了：

1. 如果你是用 Saxon 的話：

   java -cp "D:\docbook\xslthl-2.1.0\xslthl-2.1.0.jar;D:\docbook\saxon6-5-5\saxon.jar;D:\docbook\docbook-xsl-1.78.1\extensions\saxon65.jar" -Dxslthl.config="file:///D:/docbook/docbook-xsl-1.78.1/highlighting/xslthl-config.xml" com.icl.saxon.StyleSheet -o output\my_aritcle.html my_article.xml my_article.xsl use.extensions=1
   

2. 如果你是用 Xalan 的話：

   java -cp "D:\docbook\xslthl-2.1.0\xslthl-2.1.0.jar;D:\docbook\tools\xalan.jar;D:\docbook\xerces-2_11_0\xml-apis.jar;D:\docbook\xerces-2_11_0\xercesImpl.jar;D:\docbook\docbook-xsl-1.78.1\extensions\xalan27.jar" -Dxslthl.config="file:///D:/docbook/docbook-xsl-1.78.1/highlighting/xslthl-config.xml" org.apache.xalan.xslt.Process -OUT output\my_article.html -IN my_article.xml -XSL my_article.xsl -L -PARAM use.extensions 1
   

轉換完的 my_article.html 內容就像下面這個樣子：




加上行號與程式碼 highlight 的 my_article.html

最後，我發現一個問題，就是 Xalan 在轉換外部檔案「my_code.java」時，即使有在<textdata> 標籤加上「encoding="UTF-8"」屬性，中文（在註解的位置）會變成亂碼，但 Saxon 就不會。

至於其原因，我暫時沒時間去探究。因此，如果你也遇到同樣的問題，建議就先改用 Saxon 吧！（或者幫忙查一下原因，並回饋給小弟，:-p）

前面所提到的三個檔案內容如下：

1. my_article.xml：

<?xml version='1.0' encoding="UTF-8"?>
<!DOCTYPE article PUBLIC "-//OASIS//DTD DocBook XML V4.2//EN" "http://www.oasis-open.org/docbook/xml/4.2/docbookx.dtd">

<article lang="zh_tw">
  <title>快來測試 Line Numbering 和 Code Highlighting 的功能吧！</title>
  <sect1>
    <title>my_code.java</title>
      <programlisting linenumbering="numbered" startinglinenumber="1" language="java"><?dbhtml linenumbering.everyNth="1" linenumbering.separator=" " linenumbering.width="4"?><?dbfo linenumbering.everyNth="1" linenumbering.separator=" " linenumbering.width="4"?><textobject><textdata fileref="file:///D:/docbook/my_code.java" encoding="UTF-8" /></textobject></programlisting>        
  </sect1>
</article>

2.  my_article.xsl：

<?xml version='1.0'?>
<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform" 
                xmlns:saxon="http://icl.com/saxon"
                extension-element-prefixes="saxon" 
                version='1.0'>

<xsl:import href="file:///D:/docbook/docbook-xsl-1.78.1/html/docbook.xsl"/>
<xsl:import href="file:///D:/docbook/docbook-xsl-1.78.1/html/highlight.xsl"/>

<xsl:output method="html" 
            encoding="UTF-8"
            indent="yes"
            saxon:character-representation="native;decimal"/>
<!--=====================================​=======================================
Code Line Numbering & Highlighting Global Settings
====================================================​=========================-->
<xsl:param name="linenumbering.extension" select="1"></xsl:param>
<xsl:param name="linenumbering.everyNth">1</xsl:param>
<xsl:param name="linenumbering.width">4</xsl:param>
<xsl:param name="linenumbering.separator"><xsl:text> </xsl:text></xsl:param>
<xsl:param name="highlight.source" select="1"></xsl:param>
</xsl:stylesheet>

3. my_code.java：

/**
 * 使用「Adapter」Design Pattern 
 */
abstract class HumanWorkerAdpater implements IWorker {
   public void work();
   public void eat();
}
abstract class RobotWorker implements IWorker {
   public void work();
}
IWoker HumanWorker = new HumanWorkerAdpater() {
   public work() {
      // working....
   }
   public eat() {
      // eating....
   }
}
IWoker RobotWorker = new RobotWorkerAdpater() {
   public work() {
      // working....
   }
}

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」選項來

SQLite 學習筆記之五 - Explain Query Plan

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

我們可在 SQL 前加上「EXPLAIN QUERY PLAN」，以瞭解 SQLite 內部的實際運作流程與如何使用索引。除了 SELECT，也適用於：UPDATE、DELETE、INSERT INTO ... SELECT 等指令。更可用此指令來調校 SQL 與 DB schema，並進而改善效能。

一、輸出結果

此指令輸出的結果共有 4 個欄位：selectid、order、 from、detail ，其中以「detail」欄位提供的資訊最為有用。

欄位	說明
selectid	通常是 0（代表是最頂層的 SELECT）。只有當查詢中包含了「子查詢」（subquery，sub-select）時，此欄位才會出現非 0 的數值，代表這是第幾個子查詢。
order	因為 SQLite 的 join 動作都是使用「巢狀迴圈掃瞄」（nested scans），所以這個欄位代表此掃瞄動作是在第幾層迴圈，由 0 開始，0 代表最外層迴圈、1 代表第二層迴圈…依此類推。
from	代表此掃瞄/搜尋動作是發生在 FROM 子句中的第幾個 table，由 0 開始，0 代表第一個 table，1 則代表第二個 table…依此類推。
detail	開頭通常是「SCAN」或「SEARCH」。「SCAN」代表是 full-table scan，也包含了依據某 index 定義之順序對 table 內所有資料進行遍訪；「SEARCH」代表只有對 table 內的某子集合（subset）進行遍訪。而每一個「SCAN」或「SEARCH」還包含了以下資訊： 讀取資料的 table 名稱。 是否使用 index（或 automatic index）？ 是否使用「涵蓋式索引」（covering index）來最佳化？ WHERE 中的哪一個子句被用於 index？ SQLite 可能拜訪的資料列數（估計值）。

二、表格與索引掃瞄

1. 例一、表示 SQLite 會對 t1 進行全表掃瞄，並估計可能會巡訪 100,000 列的資料。若您覺得這個估計值不準，可以再執行「ANALYZE」指令以更新表格與索引的統計資訊：
   
   sqlite> EXPLAIN QUERY PLAN SELECT a, b FROM t1 WHERE a=1;
   0|0|0|SCAN TABLE t1 (~100000 rows)
2. 例二、如果 SQLite 發現有索引可用，則 SCAN / SEARCH 就會顯示此計畫所使用的索引名稱。若是「SEARCH」的話，還會顯示 SQLite 是依據哪些限制條件來過濾的。例如下面這個例子就表示 SQLite 是利用索引「i1」來最佳化 WHERE 中的「a=?」子句，而且 SQLite 預估約有 10 列會符合「a=1」子句：
   
   sqlite> CREATE INDEX i1 ON t1(a);
   sqlite> EXPLAIN QUERY PLAN SELECT a, b FROM t1 WHERE a=1;
   0|0|0|SEARCH TABLE t1 USING INDEX i1 (a=?) (~10 rows)
3. 例三、這個例子則表示 SQLite 利用了「涵蓋式索引」（covering index ）：
   
   sqlite> CREATE INDEX i2 ON t1(a, b);
   sqlite> EXPLAIN QUERY PLAN SELECT a, b FROM t1 WHERE a=1;
   
   0|0|0|SEARCH TABLE t1 USING COVERING INDEX i2 (a=?) (~10 rows)
4. 例四、這個例子說明第二個欄位（order）與第三個欄位（from）之意義。第一列 SEARCH TABLE 的「order=0」表示這是外層迴圈的掃瞄，第二列 SCAN TABLE 的「order=1」表示這是內層迴圈的掃瞄。至於第一列的「from=0」表示 t1 是在 FROM 子句中的第一個表格，而第二列的「from=1」表示 t2 是在 FROM 子句中的第二個表格。
   
   sqlite> EXPLAIN QUERY PLAN SELECT t1.*, t2.* FROM t1, t2 WHERE t1.a=1 AND t1.b>2;
   0|0|0|SEARCH TABLE t1 USING COVERING INDEX i2 (a=? AND b>?) (~3 rows)
   0|1|1|SCAN TABLE t2 (~1000000 rows)
5. 例五、若對調上例 SQL「FROM」子句中的表格順序，則可發現 SQLite 仍使用相同的查詢策略，唯 from 欄位的值會跟著改變：
   
   sqlite> EXPLAIN QUERY PLAN SELECT t1.*, t2.* FROM t2, t1 WHERE t1.a=1 AND t1.b>2;
   0|0|1|SEARCH TABLE t1 USING COVERING INDEX i2 (a=? AND b>?) (~3 rows)
   0|1|0|SCAN TABLE t2 (~1000000 rows) 
6. 例六、若 WHERE 子句包含了「OR」限制式，則 SQLite 可能會採用所謂的「OR by union」策略。在此狀況下，可能會有兩筆「SEARCH」紀錄（一筆對一個索引），而且「order」與「from」欄位的值都會一樣。
   
   sqlite> CREATE INDEX i3 ON t1(b);
   sqlite> EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE a=1 OR b=2;
   0|0|0|SEARCH TABLE t1 USING COVERING INDEX i2 (a=?) (~10 rows)
   0|0|0|SEARCH TABLE t1 USING INDEX i3 (b=?) (~10 rows)

三、暫時用來排序的 B-Tree

1. 如果在 SELECT 查詢中包含了 ORDER BY、GROUP BY 或 DISTINCT 子句，則 SQLite 可能會使用「暫時性的 B-Tree 結構」來對輸出資料列進行排序。或者利用索引，而使用索引會比使用 B-Tree 來得有效率。
2. 如果 SQLite 決定採用 B-Tree 排序的話，則在「detail」欄位會出現類似「USE TEMP B-TREE FOR xxx」的訊息，其中「xxx」可能是「ORDER BY」、「GROUP BY」或「DISTINCT」。
   sqlite> EXPLAIN QUERY PLAN SELECT c, d FROM t2 ORDER BY c;
   0|0|0|SCAN TABLE t2 (~1000000 rows)
   0|0|0|USE TEMP B-TREE FOR ORDER BY
3. 若希望 SQLite 避免採用「暫時性的 B-Tree 結構」來排序的話，可參考下例在要排序的欄位上建立一個索引：
   sqlite> CREATE INDEX i4 ON t2(c);
   sqlite> EXPLAIN QUERY PLAN SELECT c, d FROM t2 ORDER BY c;
   0|0|0|SCAN TABLE t2 USING INDEX i4 (~1000000 rows) 

四、子查詢

1. 在前面的例子中，第一個欄位（selectid）都是 0。但如果查詢中包含了子查詢（subquery、sub-select），不管是在 FROM 子句或者是 SQL 的一部份，那麼該欄位就會出現非 0 值。而最頂層的 SELECT 的 selectid 總是 0。
2. 下例中，我們看到有兩個子查詢的 selectid 分別是「1」和「2」。另外，還有一列 SCAN 以及兩列 EXECUTE。這兩個 EXECUTE 代表這兩個子查詢都是由最頂層的查詢所執行的。
   
   sqlite> EXPLAIN QUERY PLAN SELECT (SELECT b FROM t1 WHERE a=0), (SELECT a FROM t1 WHERE b=t2.c) FROM t2;
   0|0|0|SCAN TABLE t2 (~1000000 rows)
   0|0|0|EXECUTE SCALAR SUBQUERY 1
   1|0|0|SEARCH TABLE t1 USING COVERING INDEX i2 (a=?) (~10 rows)
   0|0|0|EXECUTE CORRELATED SCALAR SUBQUERY 2
   2|0|0|SEARCH TABLE t1 USING INDEX i3 (b=?) (~10 rows)
3. 而 EXECUTE 紀錄中的「CORRELATED」代表第二個子查詢與最頂層的查詢是相關的，也就是說從頂層找出一個資料列以後會再執行一次第二個子查詢。至於第一個子查詢中沒有出現此修飾詞，則代表此查詢只會執行一次，而且執行結果會被 cache。換句話說，因為第二個子查詢會執行多次，所以是提升效能的關鍵。
4. 除非是 SQLite 對子查詢採用了「扁平優化」（flattening optimization），否則在 FROM 子句裡的子查詢，其查詢結果會被先儲存在暫存表格之內，後續 SQLite 會再用這個暫存表格裡的資料來取代子查詢並提供給上層的父查詢（parent query）使用。而在 EXPLAIN QUERY PLAN 的結果中，我們就可以看到「SCAN TABLE」會變成「SCAN SUBQUERY」：
   sqlite> EXPLAIN QUERY PLAN SELECT count(*) FROM (SELECT max(b) AS x FROM t1 GROUP BY a) GROUP BY x;
   1|0|0|SCAN TABLE t1 USING COVERING INDEX i2 (~1000000 rows)
   0|0|0|SCAN SUBQUERY 1 (~1000000 rows)
   0|0|0|USE TEMP B-TREE FOR GROUP BY
5. 如果 SQLite 對子查詢採用了「扁平優化」，就看不到「SCAN SUBQUERY」出現。反之，我們會看到 SQLite 對表格 t1 與 t2 執行了「巢狀迴圈 join」（nested loop join）：
   sqlite> EXPLAIN QUERY PLAN SELECT * FROM (SELECT * FROM t2 WHERE c=1), t1;
   0|0|0|SEARCH TABLE t2 USING INDEX i4 (c=?) (~10 rows)
   0|1|1|SCAN TABLE t1 (~1000000 rows) 

五、複合查詢

1.  如果是 UNION、UNION ALL 、EXCEPT 或 INTERSECT 這類的「複合式查詢」（compound queries），則 SQLite 會個別指派一個專屬的 selectid 給每一個子查詢、然後報告其查詢計畫。至於父查詢（複合式查詢）的報告，則會獨立顯示在另外一行，如下例中的「COMPOUND SUBQUERIES……」：
   sqlite> EXPLAIN QUERY PLAN SELECT a FROM t1 UNION SELECT c FROM t2;
   1|0|0|SCAN TABLE t1 (~1000000 rows)
   2|0|0|SCAN TABLE t2 (~1000000 rows)
   0|0|0|COMPOUND SUBQUERIES 1 AND 2 USING TEMP B-TREE (UNION)
2. 上例中的「USING TEMP B-TREE」還說明了 SQLite 使用「暫存的 B-Tree結構」來進行兩個子查詢的結果集的 UNION 操作。
3. 如果 SQLite 沒有使用到「暫存的 B-Tree結構」，則此訊息就不會出現，如下所示：
   sqlite> EXPLAIN QUERY PLAN SELECT a FROM t1 EXCEPT SELECT d FROM t2 ORDER BY 1;
   1|0|0|SCAN TABLE t1 USING COVERING INDEX i2 (~1000000 rows)
   2|0|0|SCAN TABLE t2 (~1000000 rows)
   2|0|0|USE TEMP B-TREE FOR ORDER BY
   0|0|0|COMPOUND SUBQUERIES 1 AND 2 (EXCEPT)

SQLite 學習筆記之四 - Query Planning

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

一、搜尋

1. 未建立索引的表格

1. SQLite 中的所有表格都有 0 到多列資料，而每一列皆包含一個唯一的整數鍵（ROWID 或 INTEGER PRIMARY KEY）與內容。而每一列資料皆按照 ROWID 由小到大的順序進行儲存。
2. 接下來，我們會以如下結構的 table 來說明：
   
   CREATE TABLE FruitsForSale(
    Fruit TEXT,
    State TEXT,
    Price REAL
   );

   

   圖1: 表格「FruitsForSale」的邏輯結構

3. 請注意在此例中的「ROWID」欄位值是不連續的，但卻是有順序性的（由小而大）。ROWID 通常從 1 開始，每增加一列資料，ROWID 就會加 1。但如果某些列被刪除，就可能會有空隙發生。
4. 假設你想要查詢桃子的價格，可執行如下 SQL：
   
   SELECT price FROM FruitsForSale WHERE fruit='Peach';
5. SQLite 會讀取此 table 中的每一列，並檢查 「fruit」欄位值是否為「Peach」？此過 程稱為「全表掃瞄」（full table scan），如圖 2所示。若資料量很多時，全表掃瞄的效 能就會變得很差，所以我們應盡可能避免。
   

   

   圖2: 全表掃瞄（Full Table Scan）

2. 利用 ROWID 進行查詢

 

1. 一個避免「全表掃瞄」的方法是使用「ROWID」（或者 INTGER PRIMARY KEY）。例如要查詢桃子的價格，可以查詢 rowid 為 「4」的資料列：
   
     SELECT price FROM FruitsForSale WHERE rowid=4;
2. 因為資料是依據 ROWID 的順序儲存於 table 中的，所以 SQLite 可以在 ROWID 欄位上使用  binary search 以找到正確的資料列。如果 table 包含了 N 筆資料列，那麼找到正確資料列的時間複雜度是 O(logN)，而非「全表掃瞄」的 O(N)。如果表內包含了 1,000 萬筆資料列，用此方法會比全表掃瞄快上 100 萬倍（N/logN =10000000/LOG(10000000, 10) = 1428571.429 ）。
   

   

   圖3: 使用 ROWID 查詢

3. 利用索引進行查詢

1. 使用 ROWID 查詢的問題是你根本不關心「物件 4」的價格，你想知道的是「桃子」的價格，所以使用 ROWID 查詢並無濟於事。
2. 如下，我們可以在「fruit」欄位上加上索引「idx1」：
   
   CREATE INDEX idx1 ON FruitsForSale(fruit);
3. 如圖 4 所示，所謂的「索引」是另一張類似原來 FruitsForSale 的 表格，只是每一列的最前面是「內容」（即「fruit」欄位），後面再跟著「ROWID」欄位，並依據「內容」的順序儲存。

   

   圖 4: fruit 欄位上的索引

4. 由於 ROWID 是唯一的（unique），所以即使 fruit 欄位有可能重複， 但複合鍵「fruit+ ROWID」仍然會是唯一的。
5. 就「查詢桃子價格」這個問題，我們可以利用索引設計另一個查詢計畫：
   
   SELECT price FROM FruitsForSale WHERE fruit='Peach';
6. 這個查詢會先以 binary search 在 idx1 索引上尋找「fruit='Peach'」對應的  ROWIDs ，再用這些 ROWIDs 去尋找 FruitsForSale 表格上對應的資料列，最後再取出這些資料列的 price 欄位，過程如圖 5 所示：
   

   

   圖 5: 利用索引查詢桃子（Peach）的價格

7. 在此例中，雖然 SQLite 必須做兩次 binary search 才能找到桃子的價格，但在一張資料列很多的 table 裡這個方法仍會比「全表掃瞄」快很多。

 4. 多筆結果列

1. 上例「fruit='Peach'」的查詢只有將結果限縮到一列資料而已。但是同樣的技巧也可用來限縮結果到多列資料。假設我們這次想查詢「Orange」的價格：
   
     SELECT price FROM FruitsForSale WHERE fruit='Orange';
2. 就本例而言，SQLite 仍只會做一次 binary search 以尋找符合「fruit='Orange'」的第一筆索引。從索引中取得對應的 ROWID 後，再使用 binary search 去原來的 table 裡尋找 ROWID 所對應的資料列、並輸出價格。但此時，DB 引擎的工作還不會結束，它會繼續前往索引中的下一列，並重複尋找「fruit='Orange'」資料列的程序。整個過程如圖 6 所示：
   

   

   圖 6: 利用索引查詢柳橙（Orange）的價格

3. 由於下一列通常與當前列在同一 DB 分頁上，所以繼續前往索引的下一列會比再做一次 binary search 的成本低（事實上，低到幾乎可以忽略不計）。所以這個查詢的總成本是 3 次 binary search
4. 假設輸出的資料總筆數是 K，而 table 內的資料總筆數是 N，那麼一般的狀況下，執行此類查詢的成本約是  (K+1)* logN（此處的「1」代表在索引執行的1次 binary search，「K」則代表在原表格執行的 binary search）。

5. 當 WHERE 子句裡面有多個  AND 條件

1. 假設你不是想查詢所有柳橙的價格，而只想查詢加州（CA, California）生產的柳橙價格，您可能會執行的查詢如下：
   
     SELECT price FROM FruitsForSale WHERE fruit='Orange' AND state='CA';
2. 如圖 7 所示，有一個方法是先找出「fruit='Orange'」的資料列，然後再將那些產地不在「加州」的資料剔除掉。因為這個方法會多做一次的 binary search，所以比較沒有效率（找到佛羅里達州（FL, Florida）出產的柳橙，然後再剔除掉）。
   

   

   圖 7: 利用索引查詢加州柳橙的價格

3. 假設我們也建立 state 欄位的索引：
   
     CREATE INDEX idx2 ON FruitsForSale(state);
   

   

   圖 8: state 欄位上的索引

4. state 索引的作用和 fruit 索引一樣，都是一張新表格，其中有兩個欄位：state 和 ROWID，並依照 state 排序。差別只在於 idx1 的第一欄是「fruit」，而 idx2 的第一欄是「state」。
5. 在我們的範例資料中，雖然 state 欄位中資料重複的現象比 fruit 欄位更多，但仍可透過「ROWID」來區分。
6. 藉由 state 欄位上的 idx2 索引，SQLite 可以用另外一個方法來查詢加州柳橙的價格 — 首先找出所有在加州生產的水果，然後再把那些不是柳橙的資料列剔除：
   

   

   圖 9: 利用索引查詢加州柳橙的價格

7. 由 idx1 改為使用 idx2 ，會讓 SQLite 去檢驗不同的資料列，但最終都會得到相同的答案（請記得：索引並不會改變答案，只會幫助 SQLite 更快地找到答案），而且執行的工作量一樣多。所以，就本例而言， idx2 在效能上並無助益。
8. 在這個例子中，不管是使用 idx1 或 idx2，最後兩個查詢所花費的時間一樣多。所以 SQLite 會選用哪一個索引呢？如果先前有執行過「ANALYZE」指令，SQLite 會依據 ANALYZE 所蒐集到的索引相關統計資訊來決定要使用哪一個索引。若 SQLite 發現使用 idx1 可將搜尋動作限縮在一筆資料列，而 idx2 會限縮到兩筆，則 SQLite 會選擇使用「idx1」（不過，本例的「fruit='Orange'」是例外）。如果兩者相等呢？SQLite 會選擇「idx1」。但如果尚未執行過「ANALYZE」指令呢？則 SQLite 會隨機選擇其中一個索引。 

6. 多欄位索引（Multi-Column Indices）

1. 對於「WHERE 子句裡有多個 AND 條件」這類查詢（如 WHERE fruit='Orange' AND state='CA'），若希望獲得最大效能，則必須使用「多欄位索引」（而且索引中須包含所有 「AND 」條件的欄位，如：fruit 和 state）。
2. 舉例來說，我們可建立如下的多欄位索引：
   
     CREATE INDEX idx3 ON FruitsForSale(fruit, state);
3. 「多欄位索引」與「單一欄位」的索引一樣，都是在 ROWID 欄位前面增加內容欄位，唯一的差別只在於欄位數量比較多。 最左邊的欄位是用來排序索引之中的資料列。而第二個欄位 則用來做索引的細分（亦即當第一個欄位相同時，可再結合 此欄位進行比較）。如果還有第三或更多欄位，也是依此類 推。因為 ROWID 一定會是唯一的，所以即使內容欄位都一樣 ，索引中的每一列也都會是唯一的。
   

   

   圖10: 由兩個欄位組成的索引

4. 現在有了「idx3」這個多欄位索引，SQLite 執行兩次 binary search 就可以找到加州柳橙的價格了：
   
   SELECT price FROM FruitsForSale WHERE fruit='Orange' AND state='CA';
   

   

   圖11: 使用兩個欄位組成的索引進行查詢

5. 因為 idx3 包含了 WHERE 子句中的兩個條件欄位，所以 SQLite 只要做一次 binary search 就可以找到加州柳橙的 ROWID，然後再到原 table 中找出對應資料列裡的價格即可。完全沒有死角，也沒有不必要的 binary search，所以這是一個比較有效率的查詢。
6. 另外，值得注意的是：因為 idx3 也涵蓋了 idx1 的所有資訊，所以其實我們也可以不需要 idx1 了。而「查詢桃子價格」的問題其實也透過 idx3 來就可以解決，SQLite 會自動忽略 idx3 中的「state」欄位：
   
     SELECT price FROM FruitsForSale WHERE fruit='Peach';
   
   

   

   圖12: 使用兩欄索引來進行單欄查詢

7. 因此，以上這個例子說明了一個很重要的經驗法則：絕對不要在 DB 裡建立兩個前置欄位相同的索引！請將欄位比較少的索引移除，因為 SQLite 仍然可以透過比較長的索引進行有效查詢。

7. 涵蓋式索引（Covering indecies）

1. 「兩欄位索引」可提高「查詢加州柳橙價格」問題的處理效率。但如果把「price」欄位也建到索引裡面，透過這個「三欄索引」， SQLite 的查詢效率會更好：
   
    CREATE INDEX idx4 ON FruitsForSale(fruit, state, price);
   

   

   圖13: 涵蓋式索引（Covering Index）

2. 這個新的索引包含了對「FruitsForSale」進行 查詢時要用到的所有欄位 — 搜尋條件與輸出欄位 。所以我們稱這類索引為「涵蓋式索引」 （Covering Index）。因為所需要的資訊全都包含 在這個索引當中了，所以 SQLite 不需要再到原表 格裡查詢價格：
   
   SELECT price FROM FruitsForSale WHERE fruit='Orange' AND state='CA';
   

   

   圖14: 使用涵蓋式索引的查詢

3. 因此，藉由在每列索引後方再加上一個用於輸出結果的欄位，就可以避免對原表格的參照，也減少了一半的 binary search 次數。
4. 這是一個常數因子（constant-factor）的性能改善（大約增加一倍的速度）。另一方面，這也是一種優化。在剛開始為 table 建立索引時，兩倍與一百萬倍的性能提升很難看出來。而且就大部分的查詢來說，1 毫秒與 2 毫秒之間的差異也很難被發現。
5. 「涵蓋式索引」也是「多欄位索引」的一種。 

8. 當 WHERE 子句裡面有多個 OR 條件

1. 由於多欄位索引只會在「WHERE 子句裡有多個 AND 條件」的狀況下發揮作用，所以 idx3 和 idx4 也只有在搜尋「柳橙 AND  所有在加州生產的水果」的物件時有用。但是如果我們想查詢「柳橙  OR 所有在加州生產的水果」的物件時，這兩個索引就沒有用了：
   
     SELECT price FROM FruitsForSale WHERE fruit='Orange' OR state='CA';
2. 當「WHERE 子句裡有多個 OR 條件」時，SQLite 會分別檢驗每個 OR 條件，並試著使用索引去找出每個條件裡頭相關的 ROWIDs，然後再用這些 ROWIDs 的 UNION 操作去找出最終結果。下圖說明了這個過程：
   
   

   

   圖15: 使用 OR 限制式的查詢

3. 如上圖所示，SQLite 會先找出所有的 ROWID，然後用 UNION 操作將這些 ROWID 合併起來，最後再到原始表格中去搜尋這些 ROWID。而事實上，在 rowid 的搜尋之間還穿插著 ROWID 的計算。事實上，SQLite 每次會使用一個索引（idx1 和 idx3）來尋找 ROWID，找到以後就會記下來，並自動避開之前已經找到的 ROWID。這是程式實作細節，所以上圖並不完全準確，在此只是提供給讀者瞭解大致的流程。而這樣的技巧稱為「OR-by-UNION」。
4. 若要讓「OR-by-UNION」技巧發揮作用，一定要透過索引來解析 WHERE 裡頭的 OR 子句。如果所有 OR 字句裡面的欄位都沒有建立索引，那麼 SQLite 就會使用「全表掃瞄」來搜尋。而且也只會在一個步驟內就把所有結果都從原始表格中找出來，而不會再混合使用 UNION 操作與 binary search。
5. 有人可能會想到：既然 SQLite 可以透過多個索引與 UNION 操作來提升這類查詢的效能，那應該也能用多個索引與 INTERSECT 操作來提升「WHERE 子句裡有多個 AND 條件」查詢的效能吧！？有許多資料庫引擎確實也都是這麼做的。但是跟只使用單一索引相比，這個方法所提升的效能很小，所以 SQLite 目前並未實作此技術。或許將來SQLite 的新版會支援此項「AND-by-INTERSECT」技術。

二、排序 

1. SQLite 除了可以利用索引來加快查詢速度之外，也可用索引來處理查詢中的「ORDER BY」子句。換句話說，索引可以用在「排序」與「搜尋」的加速。
2. 當沒有合適的索引可用時，SQLite 在處理一個含有「ORDER BY」子句的查詢，必須把排序視為另一個單獨的步驟。考慮以下狀況：
   
   SELECT * FROM FruitsForSale ORDER BY fruit;
3. SQLite 會先蒐集所有的查詢結果，然後再透過「排序元件」（sorter）來執行輸出：
   

   

   圖16: 不使用索引來排序

4. 若輸出的結果列數是 K，則排序的時間複雜度是 O(KlogK)。如果 K 很小，那排序的時間就不是影響效能主要關鍵。但若是像上面這個查詢，那 SQLite 用在排序的時間的時間會遠大於「全表掃瞄」。再者，由於整個輸出都是先累積在一塊暫存空間（視編譯與執行時期的設定而定，有可能是主記憶體或磁碟），所以這意味著  SQLite 要完成這個查詢，還必須要先有一塊很大的暫存空間才行。

1. 利用 ROWID來排序

1. 因為排序的成本很高，所以 SQLite 會盡力地將 ORDER BY 子句轉換為 no-ops（不進行任何操作，組合語言的一種指令）。若未指定輸出結果要依據特定順序顯示，SQLite 就不會進行任何排序工作。舉例來說，如果您要求依照 ROWID 順序輸出， SQLite 就不會進行任何排序工作：
   
   SELECT * FROM FruitsForSale ORDER BY rowid;
   

   

   圖17: 依據 rowid 來排序

2. 您也可以像下面這樣指定反向的排序方式：
   
   SELECT * FROM FruitsForSale ORDER BY rowid DESC;
   
   SQLite 仍將忽略排序步驟。但為了讓輸出結果依據正確順序顯示，SQLite 將會從表格尾端一直掃瞄到表格開頭，而不是像圖 17 那樣，從開頭掃到結尾。

 2. 利用索引來排序

1. 依據 ROWID 來排序查詢輸出結果並沒什麼用處，通常我們會希望依據某個欄位來排列輸出的結果。
2. 如果在「ORDER BY」子句中的欄位有索引可用，SQLite 就會利用該索引進行排序。假設我們希望所有的項目都能依據「fruit」欄位來排序：
   
     SELECT * FROM FruitsForSale ORDER BY fruit;
   

   

   圖18: 利用索引來排序

3. 那麼 SQLite 就會依據 fruit  的順序從「idx1」索引的開頭掃瞄到尾端以找出每一項目的 ROWID。然後再針對每筆 ROWID 執行 binary search，並輸出該列資料。
4. 與「不利用索引來排序」相比，這個方式的時間複雜度同樣也是 O(NlogN)，所以並沒有比較節省時間！
5. SQLite 使用「以成本為基礎」（cost-based ）的 query planner。所以當同一查詢有多種解決方式時，SQLite 會先試著估計每一個查詢計畫的總時間，再從中選出 cost 最小的查詢計畫。
6. 成本的計算主要來自於估計花費時間（estimated time），所以就這個例子來說，SQLite 可能會依據表格大小、WHERE 子句中的限制條件或諸如此類的因素來選擇。但是，一般狀況下，SQLite 會選用「利用索引來排序」（indexed sort）的方式。因為在開始排序之前， SQLite 不需要先將整個結果集都儲存在暫存空間，所以只需使用很少的暫存空間。

3. 利用涵蓋式索引來排序

1.  查詢時若能利用「涵蓋式索引」（covering index），便可避免多個 ROWID 的查詢與以及大幅減少查詢成本。
   

   

   圖19: 利用涵蓋式索引來排序

2. 藉由「涵蓋式索引」，SQLite 只需要從索引的一端走到另一端並輸出結果就可以了，而不需配置一大塊緩衝區以保留結果集。 

三、同時進行搜尋與排序

1. 使用多欄索引

1. 前面我們分別就「搜尋」與「排序」兩個主題進行了討論，但實務上，同一時間執行搜尋與排序會是比較常見的狀況。很幸運地，SQLite 有可能使用一個索引就能辦到。
2. 假設我們希望找出所有柳橙的價格、並依照產地的州別（state）排序，可以使用如下查詢：
   
     SELECT price FROM FruitForSale WHERE fruit='Orange' ORDER BY state;
3. 此查詢中包含了 WHERE 子句與 ORDER 子句，使用兩欄索引 idx3 就可達成同時搜尋與排序的需求。
   

   

   圖20: 利用多欄索引進行搜尋和排序

4. SQLite 會先在索引上從頭到尾做一次 binary search 以找出符合「fruit='Orange'」的索引列（因為「fruit」是索引最左邊的欄位，而且其中資料也是依據這個欄位做排列的，所以相同的「fruit」列會被排在一起），接著再用這些  ROWID 到原始表格中做 binary search ，以找出價格。
5. 您應該注意到了在上圖裡並沒有出現「排序元件」（sorter），這是因為「ORDER BY」子句已經變成 no-op 了。因為這個查詢是要求輸出結果必須依據「state」欄位來排序，而「state」欄位剛好是索引中「fruit」後面的欄位。這個索引本來就是先依據「state」排序、再依據「fruit」欄位排序過的，所以 SQLite 只需單純地由上而下進行掃瞄就好了。 

2. 使用覆蓋式索引 

1. 「覆蓋式索引」也可用於同時搜尋與排序。考慮以下查詢：
   
   SELECT * FROM FruitForSale WHERE fruit='Orange' ORDER BY state;
    

   

   圖21: 利用覆蓋式索引進行搜尋和排序

2. 同樣地，SQLite 會先在覆蓋式索引上由上而下進行一次 binary search 以找出滿足 WHERE 子句要求的索引列。而由於這個索引本來就是先依據「state」排序、再依據「fruit」欄位排序過的，所以其結果就可以直接拿來使用（輸出）。因此這個查詢是相當有效率的。
3. SQLite 也將類似技巧應用在「降冪  ORDER BY」（descending ORDER BY）上：
   
   SELECT * FROM fruitforsale WHERE fruit='Orange' ORDER BY state DESC;
4. 除了掃瞄的方向從「由上而下」改成「由下而上」，SQLite 按照同樣的基本邏輯，將輸出結果依據「state」欄位降冪排序後輸出。