<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                合規國際互聯網加速 OSASE為企業客戶提供高速穩定SD-WAN國際加速解決方案。 廣告
                # 第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是一個虛擬機,它的字節代碼指令和匯編程序十分類似,每一條指令由操作碼和三個操作數構成:&lt;opcode, P1, P2, P3&gt;。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。 ![](https://box.kancloud.cn/2016-05-17_573b066d6a1da.jpg) 圖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的功能就是檢查它們是否匹配,如果不匹配,就要采取適當的措施。 ![](https://box.kancloud.cn/2016-05-17_573b066d8221c.jpg) 圖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的示例: ![](https://box.kancloud.cn/2016-05-17_573b066d97084.jpg) 圖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編碼實現。 ![](https://box.kancloud.cn/2016-05-17_573b066dafdd4.jpg) 圖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&gt;12的偶數 | BLOB | (N-12)/2 | | N&gt;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所示。 ![](https://box.kancloud.cn/2016-05-17_573b066dc1c66.jpg) 表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接口處理二進制的數據和原始存儲器。 ![](https://box.kancloud.cn/2016-05-17_573b066dd58db.jpg) 圖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存儲在一個外部文件中而在數據庫中只保存其文件名也許更好一些。 ![](https://box.kancloud.cn/2016-05-17_573b066ea63e2.jpg) 圖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所示的分析樹。 ![](https://box.kancloud.cn/2016-05-17_573b066eb7b95.jpg) 圖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所示: ![](https://box.kancloud.cn/2016-05-17_573b066ecf6db.jpg) 圖9-9 WHERE子句的VDBE代碼的生成 優化發生在sqlite3WhereBegin()階段。 它在已完成工作的基礎上,尋找可以使用的索引,尋找可以重寫的表達式,等等。 為了能對優化先有一個感覺, 我們從一個不含WHERE子句的簡單SELECT語句開始,如圖9-10所示: ![](https://box.kancloud.cn/2016-05-17_573b066ee1dc3.jpg) 圖9-10 一個不含WHERE子句的SELECT語句
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看