# 第9章 SQLite內核 本章是SQLite各主要子系統的一個概覽。它的靈感來自一次會議上Richard Hipp對SQLite所做的介紹。即使你沒有看過SQLite的源代碼，你也會發現這些內容是如此的有趣。即使SQLite還在發展，但本章所介紹的概念一時不會改變。 現在，你應該已經熟悉SQLite的主要組件了。第1章有一個概述，第5章介紹了B-tree和pager，這些概念本章就不再介紹了。本章會從虛擬機入手，它是SQLite的心臟；然后是存儲層；最后是編譯器，它可能是系統中最復雜的部分。 ## 虛擬數據庫引擎(VDBE) VDBE是SQLite的核心，它的上層模塊和下層模塊本質上都是為它服務的，它的實現位于vbde.c、vdbe.h、vdbeapi.c、vdbeInt.h和vdbemem.c等幾個文件中。如第5章所述，一個語句(statement)會編譯為一個完整的VDBE程序，執行一條單獨的SQL命令。它通過底層的基礎設施B-tree執行由編譯器(Compiler)生成的字節代碼，這種字節代碼程序語言是為了進行查詢、讀取和修改數據庫而專門設計的。 字節代碼在內存中被封裝成sqlite3_stmt對象(內部叫做Vdbe，見vdbeInt.h)，Vdbe(或者說statement)包含執行程序所需要的一切，包括： + VDBE程序 + 程序計數器 + 結果字段的名稱和類型 + 參數的綁定值 + 運行棧和固定數量的編號的內在單元 + 其它的運行時狀態信息，如B-tree游標 VDBE是一個虛擬機，它的字節代碼指令和匯編程序十分類似，每一條指令由操作碼和三個操作數構成：<opcode, P1, P2, P3>。Opcode為一定功能的操作碼，為了理解，可以看成一個函數。p1是32位的有符號整數，p2是31位的無符號整數，它通常是跳轉(jump)指令的目標地址(destination)，當然還有其它用途；p3為一個以null結尾的字符串或者其它結構體的指針。目前SQLite中有128個操作碼。和C API不同的是，VDBE操作碼經常變化，所以不應該用字節碼編寫自己的程序。 下面的幾個C API直接和VDBE交互： + sqlite3_bind_xxx() functions + sqlite3_step() + sqlite3_reset() + sqlite3_column_xxx() functions + sqlite3_finalize() 一般情況下，所有的API都是用來執行一個查詢并在VDBE相關的結果集中步進操作。它們有一個共同點：都以一個語句句柄做參數。這是因為它們都需要句柄中的VDBE代碼或相關資源來完成任務。注意：sqlite3_prepare()工作于開始階段，用于產生VDBE代碼，它不參與執行。 所有SQL命令的VDBE程序都可以通過EXPLAIN命令得到，如： ``` sqlite> .m col sqlite> .h on sqlite> .w 4 15 3 3 15 sqlite> explain select * from episodes; addr??????? opcode????????????????? p1??? p2??? p3 0??????????? Goto ?????????????????? 0 ??? 12 1 ?????????? Integer ??????????????? 0 ??? 0 2 ?????????? OpenRead ??????????? 0 ??? 2 ??? # episodes 3 ?????????? SetNumColumns ? 0 ??? 3 4 ?????????? Rewind ??????????????? 0 ??? 10 5 ?????????? Recno ????????????????? 0 ??? 0 6 ?????????? Column ?????????????? 0 ??? 1 7 ?????????? Column ?????????????? 0 ??? 2 8 ?????????? Callback??????????????? 3 ??? 0 9 ?????????? Next ??????????????????? 0 ??? 5 10 ???????? Close ?????????????????? 0 ??? 0 11 ???????? Halt ??????????????????? 0 ??? 0 12 ???????? Transaction ????????? 0 ??? 0 13 ???????? VerifyCookie ??????? 0 ??? 10 14 ???????? Goto ?????????????????? 0 ??? 1 15 ???????? Noop ?????????????????? 0 ??? 0 ``` 上面使用了4條命令，前面的命令用于調試和格式化。另外，我在編譯SQLite時使用了SQLITE_DEBUG選項，這個選擇可以提供運行棧更多的信息，比如包含在p3里面的表名。 空注：當前版本的SQLite(3.6.18)確實有較大變化，現在執行EXPLAIN命令的結果如下。 ``` addr? opcode?????????? p1?? p2?? p3???? p4????????? p5??? comment ----? ---------------? ---? ---? -----? ----------? ----? ---------- 0???? Trace??????????? 0??? 0??? 0???????????????? ?00 1???? Goto???????????? 0??? 11?? 0????????????????? 00 2???? OpenRead???????? 0??? 2??? 0????? 3?????????? 00 3???? Rewind?????????? 0??? 9??? 0????????????????? 00 4???? Rowid??????????? 0??? 1??? 0????????????????? 00 5???? Column?????????? 0??? 1?? ?2????????????????? 00 6???? Column?????????? 0??? 2??? 3????????????????? 00 7???? ResultRow??????? 1??? 3??? 0????????????????? 00 8???? Next???????????? 0??? 4??? 0????????????????? 01 9???? Close??????????? 0??? 0??? 0????????????????? 00 10??? Halt?? ??????????0??? 0??? 0????????????????? 00 11??? Transaction????? 0??? 0??? 0????????????????? 00 12??? VerifyCookie???? 0??? 40?? 0????????????????? 00 13??? TableLock??????? 0??? 2??? 0????? episodes??? 00 14??? Goto???????????? 0??? 2??? 0?????????????? ???00 ``` 空注：有關VDBE的最詳細參考在vbde.c中，也可以參考SQLite網站提供的文檔http://www.sqlite.org/opcode.html。 空注：后面的內容還按原文翻譯。 ## 棧(Stack) 一個VDBE程序通常由幾個完成特定任務的段(section)構成，每一個段中都有一些操作棧的指令。這么做是因為不同的指令有不同數量的參數，有些指令只有一個參數；有些指令沒有參數；有些指令有好幾個參數，這時三個操作數就不夠了。 考慮到這些情況，指令采用棧來傳遞參數。而這些指令本身不會做這些工作，所以在它們之前需要其它一些指令的幫助，以取得需要的參數。VDBE把計算的中間結果保存到內存單元(memory cell)中，其實堆棧和內存單元都基于Mem結構(見vdbeInt.h)。 ## 程序體 讓我們來看前面打開episodes表的例子。它的第一個段主要包括指令1~3。 第一條指令(Integer)是為第二條指令作準備的，也就是把第二條指令執行需要的參數壓入堆棧，OpenRead從堆棧中取出參數值然后執行。 SQLite可以通過ATTACH命令在一個連接中打開多個數據庫文件，每當SQLite打開一個數據庫，它就為之賦一個索引號(index)，主數據庫的索引為0，附加的第一個數據庫為1，依次類推。Integer指令將數據庫索引的值壓入棧(本例為0，代表主數據庫)，而OpenRead從中取出值，并決定操作哪個數據庫。它用P2來確定需要打開表的根頁(root page)。然后它打開一個指定數據庫中指定表的B-tree游標。所有這些在VDBE代碼文檔中都有解釋，例如，OpenRead命令在SQLite文檔中的解釋如下： 為數據庫表打開一個只讀游標，這個表的根頁在數據庫文件的P2處。數據庫文件由棧頂的一個整數指定。0表示主數據庫，1表示用于存放臨時表的數據庫。新打開游標的標識符在P1中。P1的值不必是相鄰的，但應該是一個小整數。如果其值為負，表示錯誤。If P2==0 then take the root page number from off of the stack. 只要有游標打開，就會有一個讀鎖加載到數據庫上。如果數據庫本來是未加鎖的，此命令的部分工作包括獲得一個讀鎖。讀鎖允許其它進程讀數據庫，但是禁止任何進程改數據庫。讀鎖在所有游標都關閉時釋放。如果此指令在申請讀鎖時失敗，程序結束并返回SQLITE_BUSY錯誤碼。 P3的值是指向一個結構的指針，該結構定義索引的內容和排序序列的關鍵信息。當不指向索引時，P3的內容為空。 這個關于OpenRead的文檔與其它指令的文檔一樣，可以直接在源程序文件中找到，特別是vdbe.c中。 最終，SetNumColumns指令設置游標需要處理的列的數量，這是由所要處理的表包含的列數決定的。P1為游標的索引(這里為0，是剛剛打開的游標的索引號)。P2為列的數目，episodes表有三列。 繼續本例，Rewind指令將游標設置到表的開始，它會檢查表是否為空(“空”即沒有記錄)。如果沒有記錄，它會導致指令指針跳轉到P2指定的指令處。此處P2為10，即Close指令。一旦Rewind設置游標，接下來就會執行下一段(指令5~9)的幾條指令。它們的主要功能是遍歷結果集，Recno把由游標P1指定的記錄的關鍵字段值壓入堆棧。Column指令從由P1指定的游標，P2指定的列取值。5,6,7三條指令分別把id(primary key)、season和name字段(游標0所指明的表episodes的全部3個字段)的值壓入棧。接下來，Callback指令從棧中取出三個值(由P1指定)，然后形成一個記錄數組，存儲在內存單元 (memory cell) 中。然后，Callback會掛起VDBE的執行，把控制權交給sqlite3_step()，該函數將返回SQLITE_ROW。  圖9-1 VDBE的步驟：Open和Read 一旦VDBE創建了記錄結構(該結構同樣關聯于語句(statement)句柄)，程序就可以通過sqlite3_column_xxx() 函數從記錄結構內取出字段值。當下次調用sqlite3_step()時，指令指針會指向Next指令。Next指令會把游標移向表的下一行，如果有其它的記錄，它會跳到由P2指定的指令，在這里為指令5(Recno指令)，創建一個新的記錄結構，進入下一次循環。如果已經沒有其它記錄可讀，Next不跳轉，而是執行下一條指令，這里是Close指令。Close指令會關閉游標，然后執行Halt指令，結束VDBE程序，并且sqlite3_step()函數會返回SQLITE_DONE。 ## 程序開始與停止 前面介紹了程序的核心部分，現在來看看其余的指令，這些指令與啟動和初始化有關，見圖9-2。第一條指令是Goto指令，它是一條跳轉指令，跳到P2處，本例中是跳到第12條指令。 指令12是Transaction，它開始一個新的事務；然后執行下一條指令VerifyCookie，它的主要功能是確定VDBE程序編譯后，數據庫schema是否改變(即是否進行過更新操作)。這在SQLite中是一個很重要的概念，在SQL被sqlite3_prepare()編譯成VDBE代碼至程序調用sqlite3_step()執行字節碼的這段時間內，另一個SQL命令可能會改變數據庫模式(比如ALTER TABLE、DROP TABLE或CREATE TABLE)。一旦發生這種情況，schema版本就會改變，之前編譯的語句(statement)就會變得無效。當前的數據庫schema信息記錄在數據庫文件的根頁中。類似地，每個語句都有一份用于比較的在編譯時刻該模式的備份，VerifyCookie的功能就是檢查它們是否匹配，如果不匹配，就要采取適當的措施。  圖9-2 VDBE的步驟：程序開始 語句的版本號由VerifyCookie的P2參數指定，將它與磁盤上的數據庫schema版本號進行比較。如果schema沒有改變，兩個版本號應該一致。如果不一致，則VDBE程序失效。在此情況下，VerifyCookie將會終止程序并返回SQLITE_SCHEMA錯誤。在此情況下，應用程序需要重新編譯SQL語句，基于新的schema版本生成新的VDBE程序。 如果兩者匹配，會執行下一條指令Goto；它會跳到程序的主要部分，即第一條指令，打開表讀取記錄。這里有兩點值得注意： (1)Transaction指令本身不會獲取鎖。它的功能相當于BEGIN，而共享鎖實際是由OpenRead指令獲取的。當事務關閉時釋放鎖，由Halt指令完成，它會進行掃尾工作。 (2) 語句對象(VDBE程序)所需的存儲空間在程序執行前就已經確定。這緣于兩個重要事實：首先，棧的深度不會比指令的數目還多。其次，內存單元(memory cell)的數量永遠不會多于指令的數量(通常少得多)。在執行VDBE程序之前，SQLite可以計算出分配資源所需要的內存。 ## 指令的類型 VDBE同時只會執行一條指令。每條指令都完成一項簡單的任務，而且通常和該指令前面、后面的指令有關。大體上來說，指令可分為三類： (1)處理值：這些指令通常完成算術運算，比如加、減和除；邏輯運算，比如與和或；還有字符串操作。 (2)數據管理：這些指令操作在內存和磁盤上的數據。內存指令進行棧操作或者在內存單元之間傳遞數據。磁盤操作指令控制B-tree和pager打開或操作游標，開始或結束事務，等等。 (3)流程控制：控制指令主要是有條件地或無條件地移動指令指針。 一旦熟悉了指令集，就不難明白VDBE程序是如何工作的。至少你可以了解如何使用棧來為后面指令的執行做準備。 ## B-Tree和Pager模型 B-tree使VDBE執行查找、插入和刪除的效率達到O(logN)，以及在O(1)的效率下雙向遍歷結果集。它是自平衡的，可自動地執行碎片整理和空間回收。B-tree本身不會直接讀寫磁盤，它僅僅維護著頁(page)之間的關系。當B-tree需要頁或者修改頁時，它就會調用pager。當修改頁時，pager保證原始頁首先寫入日志文件。當它完成寫操作時，pager根據事務狀態決定如何做。 ## 數據庫文件格式 數據庫中所有的頁從1開始順序編號。一個數據庫由多個多重B-tree構成——B-tree用于每一個表和索引。每個表和索引的第1個頁(地址)稱為根頁。所有表和索引的根頁都存儲在sqlite_master表中。 數據庫中第一個頁(page 1)有點特殊，page 1的前100個字節是一個對數據庫文件進行描述的特殊文件頭。它包括庫的版本、格式的版本、頁大小、編碼等所有創建數據庫時設置的永久性參數。有關這個特殊文件頭的文檔在btree.c中，page 1也是sqlite_master表的根頁。 ### 頁重用及回收 SQLite利用一個空閑頁鏈表(free list)完成頁的循環使用。當一個頁的所有記錄都被刪除時，就被插入到該鏈表。當有新信息需要進入數據庫時，臨近的空閑頁先被選中，當沒有空閑頁時，才創建新的頁(會增加文件的大小)。當運行VACUUM命令時，會清空空閑頁鏈表，所以數據庫會縮小。本質上它是在新的文件中重新建立數據庫，而所正使用的頁都被拷貝過去，而空閑頁鏈表不拷，結果就是一個新的，變小了的數據庫。當數據庫的autovacuum開啟時，SQLite不會使用空閑頁鏈表，而且在每一次事務提交時自動壓縮數據庫。 ### B-Tree記錄 B-tree中的頁由B-tree記錄組成，也叫做payload(有效載荷)。每一個B-tree記錄(或payload)有兩個域：關鍵字域(key field)和數據域(data field)。關鍵字域就是ROWID的值，也就是每個數據庫表都會提供的關鍵字的值。從B-tree的角度，數據域可以是任何無結構的數據。數據庫的記錄就保存在這些數據域中。B-tree的任務就是排序和遍歷，這僅需要關鍵字段。Payload的大小是不定的，這與內部的關鍵字和數據域有關。平均情況下，每個頁一般包含多個payload，當然也可能一個payload占用幾個頁(當一個payload太大不能存在一個頁內)。 ### B+樹 B-tree按關鍵字的順序存儲，在一個B-tree中所有的關鍵字必須唯一(這一點自動地由ROWID主鍵字段保證)。表采用B+tree，B+tree的內部結點不包含表數據(數據庫記錄)。圖9-3是一個表的B+tree的示例：  圖9-3 B+tree的組織(表) B+tree中的根頁(root page)和內部頁(internal page)都是用來導航的，這些頁的數據域都是指向下級頁的指針，僅僅包含關鍵字。所有的數據庫記錄都存儲在葉子頁(leaf page)內。在葉節點一級，記錄和頁都是按照關鍵字的順序排列的，這使B-tree游標只使用頁結點就能正向和反向(水平地)遍歷記錄，并使遍歷的效率(時間復雜度)可能達到O(1)。 ### 記錄和字段 數據庫記錄位于葉子頁的數據域，由VDBE管理(前面在介紹Callback命令時介紹過)。數據庫記錄以二進制的形式存儲，但有一定的數據格式，這種格式描述了記錄中的所有字段。記錄格式是連續的字節流，其組成包括一個邏輯頭(logical header)和一個數據區(data segment)，邏輯頭包括“頭大小(可變長的64位整數)”和一個數據類型(也是可變長的64位整數)數組，數據類型用來描述存儲在數據區的字段的類型，如圖9-4所示。64位整數用Huffman編碼實現。  圖9-4 記錄結構 類型入口的數量與字段數量相等。類型數組與字段數組的元素按下標相對應。一個類型入口表明它對應字段的數據類型和寬度。類型入口的可能取值及其含義在表9-1中列出。 表9-1 字段類型值 | 類型值 | 含義 | 數據寬度 | | --- | --- | --- | | 0 | NULL | 0 | | N in 1..4 | 有符號整數 | N | | 5 | 有符號整數 | 6 | | 6 | 有符號整數 | 8 | | 7 | IEEE符點數 | 8 | | 8-11 | 未使用 | N/A | | N>12的偶數 | BLOB | (N-12)/2 | | N>13的奇數 | TEXT | (N-13)/2 | 例如，取episodes表的第1條記錄： ``` sqlite> SELECT * FROM episodes ORDER BY id LIMIT 1; id??? season???? name 0???? 1??????????? Good News Bad News ``` 這條記錄的內部記錄格式如圖9-5所示。  表9-5 episodes表的第1條記錄 記錄頭長4字節。頭的大小反映頭內各要素都是單字節編碼。第一個類型，對應id字段，是一個1字節有符號整數。第二個類型，對應season字段，也是一個1字節有符號整數。Name字段的類型入口是一個大于13的奇數，表示它是一個text值，該值占(49-13)/2=18個字節。通過這些信息，VDBE可以解析記錄的數據段并取出獨立的字段值。 ### 層次數據組織 SQLite的層次數據組織模型如圖9-6所示。在模型中，每層處理特定的數據單元。從下向上，數據越來越結構化；從上往下，數據越來越無序。C-API處理字段值，VDBE處理記錄，B-tree處理健值的數據，pager處理頁，OS接口處理二進制的數據和原始存儲器。  圖9-6 模型和各層所對應的數據 Each module takes part in managing its own specific portion of the data in the database, and relies on the layer below it to supply it with a more crude form from which to extract its respective pieces. ### 溢出頁 如前所述，B-tree記錄具有可變的大小，而頁的大小是固定的。這就有可能一個B-tree記錄比一個單獨的頁還要大。這時，超大的B-tree記錄就溢出到由溢出頁組成的鏈表上，如圖9-7所示。 在圖中，第4個頁太大，B-tree模塊就創建一個溢出頁來容納它。如果一個溢出頁還不夠，就再鏈接第2個。這實際上也是二進制大對象的處理方法。請記住：當你使用大的BLOB時，它實際上是存儲在頁鏈表中的。如果BLOB實在太大，鏈表就會很長，操作就會很低效。這種情況下，將BLOB存儲在一個外部文件中而在數據庫中只保存其文件名也許更好一些。  圖9-7 溢出頁 ## B-Tree API B-Tree模塊有它自己的API，它可以獨立于C API使用。也就是說，如果你愿意，你可以把它當作一個獨立的運行庫來使用，或在SQLite中直接存取庫表。SQLite B-tree模塊的另一個好處就是它本身支持事務。由pager處理的事務、鎖和日志都是為B-tree服務的。根據功能，可將B-Tree API分為以下幾類： ### 訪問和事務函數 包括： + sqlite3BtreeOpen: 打開一個新的數據庫文件，返回一個B-tree對象。 + sqlite3BtreeClose: 關閉一個數據庫。 + sqlite3BtreeBeginTrans: 開始一個新的事務。 + sqlite3BtreeCommit: 提交當前事務。 + sqlite3BtreeRollback: 回卷當前事務。 + sqlite3BtreeBeginStmt: 開始一個statement事務。 + sqlite3BtreeCommitStmt: 提交一個statement事務。 + sqlite3BtreeRollbackStmt: 回卷一個statement事務。 ### 表函數 包括： + sqlite3BtreeCreateTable: 在數據庫文件中創建一個新的、空的B-tree。其參數決定是采用表格式(B+tree)還是索引格式(B-tree)。 + sqlite3BtreeDropTable: 從數據庫中刪除一個B-tree。 + sqlite3BtreeClearTable: 從B-tree中刪除所有數據，但保持B-tree的結構。 ### 游標函數 包括： + sqlite3BtreeCursor: Creates a new cursor pointing to a particular B-tree. Cursors can be either a read cursor or a write cursor. Read and write cursors may not exist in the same B-tree at the same time. + sqlite3BtreeCloseCursor: Closes the B-tree cursor. + sqlite3BtreeFirst: Moves the cursor to the first element in a B-tree. + sqlite3BtreeLast: Moves the cursor to the last element in a B-tree. + sqlite3BtreeNext: Moves the cursor to the next element after the one it is currently pointing to. + sqlite3BtreePrevious: Moves the cursor to the previous element before the one it is currently pointing to. + sqlite3BtreeMoveto: Moves the cursor to an element that matches the key value passed in as a parameter. If there is no match, leaves the cursor pointing to an element that would be on either side of the matching element, had it existed. ### 記錄函數 包括： + sqlite3BtreeDelete: Deletes the record that the cursor is pointing to. + sqlite3BtreeInsert: Inserts a new element in the appropriate place of the B-tree. + sqlite3BtreeKeySize: Returns the number of bytes in the key of the record that the cursor is pointing to. + sqlite3BtreeKey: Returns the key of the record the cursor is currently pointing to. + sqlite3BtreeDataSize: Returns the number of bytes in the data record that the cursor is currently pointing to. + sqlite3BtreeData: Returns the data in the record the cursor is currently pointing to. ### 配置函數 包括： + sqlite3BtreeSetCacheSize: Controls the page cache size as well as the synchronous writes (as defined in the synchronous pragma). + sqlite3BtreeSetSafetyLevel: Changes the way data is synced to disk in order to increase or decrease how well the database resists damage due to OS crashes and power failures. Level 1 is the same as asynchronous (no syncs() occur and there is a high probability of damage). This is the equivalent to pragma synchronous=OFF. Level 2 is the default. There is a very low but non-zero probability of damage. This is the equivalent to pragma synchronous=NORMAL. Level 3 reduces the probability of damage to near zero but with a write performance reduction. This is the equivalent to pragma synchronous=FULL. + sqlite3BtreeSetPageSize: Sets the database page size. + sqlite3BtreeGetPageSize: Returns the database page size. + sqlite3BtreeSetAutoVacuum: Sets the autovacuum property of the database. + sqlite3BtreeGetAutoVacuum: Returns whether the database uses autovacuum. + sqlite3BtreeSetBusyHandler: Sets the busy handler. 還有其它的函數，所有這些函數在btree.h和btree.c中都有很完備的文檔，但上面列出的函數可以使你建立一個總體印象。 ## 編譯器 前面已經介紹了VDBE以下直到OS層的各層次。下面介紹VDBE程序是怎么來的。編譯器的輸入是一個單獨的SQL命令，輸出是最終經過優化的VDBE程序，這些工作在3個階段上完成：分詞器(Tokenizer)、分析器(Parser)和代碼生成器(Code Generator)。 ## 分詞器(Tokenizer) 編譯的第一步是對SQL命令分詞。分詞器將一個命令分解成一串單獨的詞匯(token)。詞可以是有特定含義的一個字符或一個字符序列。每個詞都有其關聯的詞類(token class)，詞類是一個數字標識，表明這個詞是什么。例如左括號的詞類是TK_LP，保留字SELECT的詞類是TK_SELECT。所有詞類在parse.h中定義。例如下面的SQL語句： ``` SELECT rowid FROM foo where name='bar' LIMIT 1 ORDER BY rowid; ``` 經分詞器處理之后的部分結果在表9-2中給出。 表9-2 一個分詞后SELECT語句 | 文本 | 詞類 | 動作 | | --- | --- | --- | | SELECT | TK_SELECT | 發給分析器 | | " " | TK_SPACE | 丟棄 | | Rowid | TK_ID | 發給分析器 | | " " | TK_SPACE | 丟棄 | | FROM | TK_FROM | 發給分析器 | | " " | TK_SPACE | 丟棄 | | foo | TK_ID | 發給分析器 | | " " | TK_SPACE | 丟棄 | | WHERE | TK_WHERE | 發給分析器 | | " " | TK_SPACE | 丟棄 | | name | TK_ID | 發給分析器 | | = | TK_EQ | 發給分析器 | | … | 總之，分詞器按照SQL的詞法定義把它切分為一個一個的詞，并傳遞給分析器(Parser)進行語法分析(忽略空格)。 ### 保留字 分詞器是手工編寫的(hand-coded)，主要在Tokenize.c中實現。因為是手工代碼，不是用自動生成的代碼來對SQL保留字分類。保留字在keywordhash.h文件中定義。這個文件是一個最優化的、將所有SQL保留字壓縮到可能最小的緩沖區，方法是公共的字符序列重疊存放。SQLite使用指明了每個保留字偏移量和大小的數組來識別保留字入口。這種方法是一種空間優化的方法，有利于內嵌式的應用程序。一個生成了的緩沖區的例子如下： ``` static int keywordCode(const char *z, int n){ static const char zText[537] = "ABORTABLEFTEMPORARYADDATABASELECTHENDEFAULTRANSACTIONATURALTER" "AISEACHECKEYAFTEREFERENCESCAPELSEXCEPTRIGGEREGEXPLAINITIALLYANALYZE" "XCLUSIVEXISTSTATEMENTANDEFERRABLEATTACHAVINGLOBEFOREIGNOREINDEX" "AUTOINCREMENTBEGINNERENAMEBETWEENOTNULLIKEBYCASCADEFERREDELETE" "CASECASTCOLLATECOLUMNCOMMITCONFLICTCONSTRAINTERSECTCREATECROSS" "CURRENT_DATECURRENT_TIMESTAMPLANDESCDETACHDISTINCTDROPRAGMATCH" "FAILIMITFROMFULLGROUPDATEIFIMMEDIATEINSERTINSTEADINTOFFSETISNULL" "JOINORDEREPLACEOUTERESTRICTPRIMARYQUERYRIGHTROLLBACKROWHENUNION" "UNIQUEUSINGVACUUMVALUESVIEWHERE"; ``` The keywordhash.h file includes a routine sqlite3KeywordCode(), which allows the tokenizer to quickly match the keyword with its appropriate token class with minimal space. So, the tokenizer first tries to match a token with what it knows, and failing that, it resorts to sqlite3KeywordCode(), which will return either a keyword token class or a generic TK_ID. The tokenizer and parser work hand in hand, one token at a time. As the tokenizer resolves each token, it passes the token to the parser. The parser takes the tokens and builds a parse tree, which is a hierarchical representation of the statement. ## 分析器(Parser) SQLite的語法分析器是用Lemon生成的(Lemon是一個開源的LALR(1)語法分析器的生成器，SQLite在使用時進行了定制)。該分析器用parse.c內定義的語法規則將一串詞組織成層次結構的分析樹(parse tree)。 The parse tree is primarily composed of expressions and lists of expressions. An expression itself is a recursive structure that can contain subexpressions under it. For example, the WHERE clause in a SELECT parse tree is represented by a single expression. The SELECT clause, on the other hand, is represented as a list of expressions; each expression is a column that will be returned in the result set. 例如，如下簡單的SQL語句： ``` SELECT rowid, name, season FROM episodes WHERE rowid=1 LIMIT 1 ``` 可以組織成如圖9-8所示的分析樹。  圖9-8 簡化了的分析樹 一旦語句經過分詞和分析，分析樹作為一種結果會傳送給代碼生成器。 ## 代碼生成器(Code Generator) 代碼生成器是SQLite中最龐大、最復雜的部分。與其它模塊不同，代碼生成器沒有定義明確的接口，但它與分析器關系緊密。代碼生成器由多個源文件組成，這些源文件大多針對特定的SQL操作。例如，生成SELECT語句的代碼在select.c中，其它的源文件包括update.c、insert.c、delete.c和trigger.c等等。 代碼生成器根據語法分析樹生成VDBE程序。樹的每一部分生成一個VDBE指令序列來完成特定的任務。The values for the operands are taken from the data structures associated with the parse tree. 例如，下面是一個讀操作中打開表的代碼的生成實現： ``` /* Generate code that will open a table for reading.*/ void sqlite3OpenTableForReading( ? Vdbe *v,??????? /* Generate code into this VDBE */ ? int iCur,?????? /* The cursor number of the table */ ? Table *pTab???? /* The table to be opened */ ){ ? sqlite3VdbeAddOp(v, OP_Integer, pTab->iDb, 0); ? sqlite3VdbeAddOp(v, OP_OpenRead, iCur, pTab->tnum); ? VdbeComment((v, "# %s", pTab->zName)); ? sqlite3VdbeAddOp(v, OP_SetNumColumns, iCur, pTab->nCol); } ``` Sqlite3vdbeAddOp函數有三個參數：(1)VDBE實例(它將添加指令)，(2)操作碼(一條指令)，(3)兩個操作數。它增加一條指令到VDBE程序。上例中，sqlite3OpenTableForReading增加了3條指令，即圖9-1中的指令1~3，功能是打開一個表的B-tree用于讀。為方便起見，將圖9-1中的指令序列重列于此： ``` sqlite> explain select * from episodes; addr??????? opcode????????????????? p1??? p2??? p3 0??????????? Goto ?????????????????? 0 ??? 12 1 ?????????? Integer ??????????????? 0 ??? 0 2 ?????????? OpenRead ??????????? 0 ??? 2 ??? # episodes 3 ?????????? SetNumColumns ? 0 ??? 3 4 ?????????? Rewind ??????????????? 0 ??? 10 5 ?????????? Recno ????????????????? 0 ??? 0 6 ?????????? Column ?????????????? 0 ??? 1 7 ?????????? Column ?????????????? 0 ??? 2 8 ?????????? Callback??????????????? 3 ??? 0 9 ?????????? Next ??????????????????? 0 ??? 5 10 ???????? Close ?????????????????? 0 ??? 0 11 ???????? Halt ??????????????????? 0 ??? 0 12 ???????? Transaction ????????? 0 ??? 0 13 ???????? VerifyCookie ??????? 0 ??? 10 14 ???????? Goto ?????????????????? 0 ??? 1 15 ???????? Noop ?????????????????? 0 ??? 0 ``` ## 優化 代碼生成器不僅負責生成代碼，也負責進行查詢優化。優化是代碼生成的一部分，主要的實現位于where.c中。生成的WHERE子句通常被其它模塊共享，比如select.c、update.c和delete.c。這些模塊調用sqlite3WhereBegin()開始WHERE語句塊的指令生成，然后將返回的代碼加入到它們自己的VDBE代碼中，最后調用sqlite3WhereEnd()，生成結束WHERE子句代碼的VDBE指令。程序的一般結構如圖9-9所示：  圖9-9 WHERE子句的VDBE代碼的生成 優化發生在sqlite3WhereBegin()階段。 它在已完成工作的基礎上，尋找可以使用的索引，尋找可以重寫的表達式，等等。 為了能對優化先有一個感覺， 我們從一個不含WHERE子句的簡單SELECT語句開始，如圖9-10所示：  圖9-10 一個不含WHERE子句的SELECT語句