Exploring the SQLite Virtual Database Engine
In this section we'll take a look under the hood of SQLite to see how the command process works and to examine the internals of the Virtual Database Engine (VDBE). Though it is not essential to know what goes on behind the scenes, a little insight into how the SQLite engine processes your queries can help you understand SQLite better, and if you want to gain a deeper knowledge of how SQLite is implemented, you will learn the roles of the different source code files.
Let's begin by looking at the steps SQLite goes through in order to process a query. Figure 10.1 shows a diagram of the flow of information between submitting a query for processing and the output being returned.
Figure 10.1. Architecture of the SQLite Database Engine
The interface is the C library through which all SQLite processing is programmed. Even if you are using a different language API, at a lower level it is implemented using the C library. The
After a command is received through the interface, it is passed into the SQL Command Processor, which consists of three separate steps.
The tokenizer handles the process of breaking up a character string containing SQL statements into tokens that can be
SQLite uses the Lemon LALR(1) parser generator, which is probably not already on your system, so the SQLite source code is distributed with the entire Lemon source code in a single file as
. Though it does much the same job as BISON or YACC, Lemon was
The source file parse.y contains the grammar definition for SQLite's implementation of SQL. Lemon reads this file and generates a corresponding C-language file for the actual parser.
There is a document giving an introduction to the Lemon parser at http://www.hwaci.com/sw/lemon/lemon.html.
The parser assembles the tokenized SQL
Many SQL statements have their own source code file to handle the conversion to virtual machine code. For instance,
statements respectively. The
The virtual machine implements an abstract computing engine for the specific purpose of manipulating database files. The virtual machine itself can be found in the source code files vdbe.c , and various utilities used to compile SQL statements to VDBE opcodes are contained in vdbeaux.c .
SQLite uses an abstraction layer between the virtual machine and the low-level storage and retrieval routines, implemented as a B-tree, page cache, and OS interface.
The database is stored to disk using a B-tree layera balanced tree structure that provides fast data access by minimizing the number of disk reads required to access a particular piece of information. The implementation and interface to SQLite's B-tree subsystem can be found in btree.c and btree.h .
Each table and index in the database is written using a separate B-tree though, as we have already seen, all the B-trees are stored in a single file on disk.
The B-tree storage mechanism
The pager implementation and its interface can be found in pager.c and pager.h respectively.
For portability between different platforms, SQLite has implemented an abstraction layer that interfaces with the underlying operating system.
The file os.c contains routines that deal with low-level filesystem access on Windows and Unix. The definitions are contained in preprocessor ifdef instructions to ensure that the relevant interface is built into SQLite at compile time.
SQLite stores in-memory databases using a red/black balanced binary tree structure, defined in btree_rb.c . No pager or OS interface is required for this part of the backend as the data is stored to RAM only.
Virtual Machine Opcodes
The VDBE's machine language contains more than 100 opcodes, defined in vdbe.c , that are used to handle every possible database operation. We will look at how a few common operations are translated into opcodes and use the vdbe_trace pragma to walk through the command execution process.
Each instruction in the virtual machine is made up of an opcode and between zero and three operands. The first operand, named
, must be an integer.
is also an integer but must be non-negative.
will always contain the jump destination for an operation that may cause a jump.
can be either a
To see SQL commands converted to VDBE opcodes as they are executed from the sqlite program, begin by turning on the vdbe_trace pragma. To use this feature, SQLite must have been compiled without the NDEBUG compile time option.
sqlite> PRAGMA vdbe_trace=ON; 0 Halt 0 0
Immediately we see some VDBE trace output, although not a lot has
The Halt opcode instructs the VDBE to exit immediately, tidying up any incomplete operations. We will always see the Halt instruction at the end of every command trace.
P1 will contain the return code, which is usually SQLITE_OK , which is defined with a value of zero. The full list of return codes can be found in Appendix E, "C/C++ Interface Reference."
A different set of operands to
would be seen if we
14 Halt 19 2 column id is not unique
Here P1 has a value of 19, which represents a return code of SQLITE_CONSTRAINT and P2 has a value of OE_Abort (2). Additionally, P3 contains a textual error message indicating the SQL error that caused this constraint to be violated.
Let's look at a very simple
sqlite> SELECT 2+3 AS result; 0 ColumnName 0 1 result 1 ColumnName 1 0 NUMERIC 2 Integer 2 0 2 Stack: si:2 3 Integer 3 0 3 Stack: si:3 si:2 4 Add 0 0 Stack: i:5 5 Callback 1 0 5 6 Halt 0 0
The first two opcodes on lines 0 and 1 are both
and contain the
opcode causes the integer value of
After line 3 the stack contains the values from both sides of the addition operator, and then the Add operation is performed. Add does not take any operands; it pops the top two elements from the stack, adds them together, and pushes the result back onto the stack. After this operation we can see that indeed the stack contains the value 5; however, this time it is shown as i:5 as the Add opcode has created only an integer result.
With the hard work done, the Callback opcode is called. Callback pops P1 values off the stack and invokes the callback function with an array of those values passed as the argv parameter.
The remainder of the trace shows the output of the callback function and a normal Halt operation.
Adding two integers isn't a complex operation, but it still has to be converted to VDBE opcodes in order to be evaluated by SQLite.
Let's look at an example of a database operation
Listing 10.2. Virtual Machine Program Generated by EXPLAIN
sqlite> .explain sqlite> EXPLAIN ...> SELECT first_name, last_name ...> FROM contacts ...> WHERE first_name = 'Chris'; addr opcode p1 p2 p3 ---- ------------ ---------- ---------- ----------------------------------- 0 ColumnName 0 0 first_name 1 ColumnName 1 1 last_name 2 ColumnName 2 0 CHAR 3 ColumnName 3 0 CHAR 4 Integer 0 0 5 OpenRead 0 4 contacts 6 VerifyCookie 0 3603 7 Rewind 0 15 8 Column 0 1 9 String 0 0 Chris 10 StrNe 1 14 11 Column 0 1 12 Column 0 2 13 Callback 2 0 14 Next 0 8 15 Close 0 0 16 Halt 0 0
shows the complete program code that would be executed for a given SQL statement, the statement is not executed. However, the
pragma produces its response while the query is being executed. The trace shows the commands as they are executed, and any jumps that alter the flow of the program result in corresponding
Listing 10.2 shows the VDBE trace for the same query featured in Listing 10.1. The operation numbers are the same in both listings so that you can compare the lines in the trace to the complete virtual machine code.
sqlite> PRAGMA vdbe_trace=on; sqlite> SELECT first_name, last_name ...> FROM contacts ...> WHERE first_name = 'Chris'; 0 ColumnName 0 0 first_name 1 ColumnName 1 1 last_name 2 ColumnName 2 0 CHAR 3 ColumnName 3 0 CHAR 4 Integer 0 0 Stack: i:0 5 OpenRead 0 4 contacts 6 VerifyCookie 0 3455 7 Rewind 0 15 8 Column 0 1 Stack: s[Chris] 9 String 0 0 Chris Stack: t[Chris] s[Chris] 10 StrNe 1 14 11 Column 0 1 Stack: s[Chris] 12 Column 0 2 Stack: s[Newman] s[Chris] 13 Callback 2 0 ChrisNewman 14 Next 0 8 8 Column 0 1 Stack: s[Paddy] 9 String 0 0 Chris Stack: t[Chris] s[Paddy] 10 StrNe 1 14 14 Next 0 8 8 Column 0 1 Stack: s[Tom] 9 String 0 0 Chris Stack: t[Chris] s[Tom] 10 StrNe 1 14 14 Next 0 8 8 Column 0 1 Stack: s[Bill] 9 String 0 0 Chris Stack: t[Chris] s[Bill] 10 StrNe 1 14 14 Next 0 8 8 Column 0 1 Stack: s[Jo] 9 String 0 0 Chris Stack: t[Chris] s[Jo] 10 StrNe 1 14 14 Next 0 8 15 Close 0 0 16 Halt 0 0
In operation 5, the
opcode opens a read-only cursor for a database table with the root page at the value of
in the database identified by
. In this example the
table is opened from root page 4 of the main database. The temporary database has value 1 and any attached databases are given
instruction checks that the schema version number of database
is equal to the value of
. The schema version number is an arbitrary integer that changes whenever the schema is updated and is used so that SQLite
Next a Rewind takes place so that the following Column instruction will begin from the first record in the table. The P2 operand to Rewind is the jump location should the operation failin this case execution will jump to line 15 to perform an immediate Close and Halt .
The Column opcode in instruction 8 causes the column indicated by P2 to be pushed onto the stack. In this case P2 is 1, indicating the first_name column (with the first column, id , having index 0). We can see that the stack contains the string Chris , the first_name of the first row in the database.
Instruction 9 pushes the argument in the WHERE clause onto the stack ready to be compared. The comparison is performed with the StrNe opcode, which pops two elements from the stack and jumps to P2 if they are not equal.
In this example
is used to implement an equality test by jumping past the conditional statement that returns execution to the top of the loop if the two strings are not equal. For this first record, the strings are equal, so operation continues to instruction 13 and pops the two fields in the result off the stack and
The Next opcode at instruction 14 is where the jump from StrNe ends up if the strings are not equal. The cursor in P1 is advanced to the next data row and, as long as there are more records to fetch, execution jumps to the instruction number in P2 .
Program execution continues for the remaining rows in the contacts table, with first_name values of Paddy, Tom, Bill, and Jo not being equal to the specified string, so no further Callback operations are performed.
instruction has no more rows to fetch and the virtual machine program calls a
The complete list of opcodes for the SQLite VDBE is