Category list

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.

SQLite Architecture

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

Interface

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 core interface is defined in the main.c file of the SQLite source distribution. A few other files contain ancillary functions; for instance, printf.c contains sqlite_mprintf() and its derivatives.

After a command is received through the interface, it is passed into the SQL Command Processor, which consists of three separate steps.

Tokenizer

The tokenizer handles the process of breaking up a character string containing SQL statements into tokens that can be understood by the parser. Each individual component of the SQL language is a tokeneach combination of characters that forms a keyword or identifier and each symbol or sequence of symbols that forms an operator.

Parser

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 tool/lemon.c . Though it does much the same job as BISON or YACC, Lemon was chosen for its ability to generate a parser that is thread-safe and less prone to memory leaks.

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.

Code Generator

The parser assembles the tokenized SQL components into statements, checking that its syntax is valid before calling the Code Generator to produce virtual machine code that will do the actual work of executing the SQL statement. We'll look at the way the virtual machine works shortly.

Many SQL statements have their own source code file to handle the conversion to virtual machine code. For instance, select.c , insert.c , update.c , and delete.c deal with SELECT , INSERT , UPDATE , and DELETE statements respectively. The WHERE clause is processed by where.c , and code to evaluate expressions is generated by expr.c .

Virtual Machine

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 .

Backend

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.

B-Tree

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.

Pager

The B-tree storage mechanism requests data from the disk in 1KB chunks. The pager layer implements a page caching system that handles the reading, writing, and caching of these chunks , including the rollback and commit operations needed to implement atomic transactions.

The pager implementation and its interface can be found in pager.c and pager.h respectively.

OS Interface

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.

Red/Black Tree

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 P1 , must be an integer. P2 is also an integer but must be non-negative. P2 will always contain the jump destination for an operation that may cause a jump. P3 can be either a NULL - terminated string, or simply NULL .

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 happened for it to trace just yet. The zero at the start of the line is the instruction numberas we'll see shortly, lines from the trace are numbered to indicate the sequence of operationfollowed by the Halt opcode with operands P1 and P2 both zero.

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."

When P1 is non-zero , the return code indicates an error has occurred and the value of P2 tells the virtual machine whether to roll back the current transaction. The values OE_Fail , OE_Rollback , and OE_Abort defined in sqliteInt.h will cause the transaction to be saved, rolled back, or aborted.

A different set of operands to Halt would be seen if we violate a database constraint, for instance. The following operation was the final trace step of a command that attempted to insert a duplicate value into a PRIMARY KEY column:

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 SELECT statement that evaluates an expression without using any database table. The following trace output shows the VDBE opcodes along with the values on the stack as the operation takes place:

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 ColumnName and contain the name and data type of the result column respectively. P1 is the number of the column, beginning at zero, for which the name in P3 is being assigned. P2 has a value of 1 to indicate the last column in the result. Remember that, with the show_datatypes pragma on, the data types are passed to the callback as later column index numbers in the result set.

The Integer opcode causes the integer value of P1 to be pushed onto the stack. P3 contains a string representation of the same integer. After line 2 the stack trace shows si:2 , where si indicates that the value was placed onto the stack as both a string and an integer.

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 next . Listing 10.2 contains the virtual machine program code generated by the EXPLAIN command for a SELECT query that fetches two columns from the contacts table using an equality condition in the WHERE clause.

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

Although EXPLAIN shows the complete program code that would be executed for a given SQL statement, the statement is not executed. However, the vdbe_trace 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 jumps in the trace output.

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 OpenRead opcode opens a read-only cursor for a database table with the root page at the value of P2 in the database identified by P1 . In this example the contacts table is opened from root page 4 of the main database. The temporary database has value 1 and any attached databases are given subsequent sequential numbers.

The VerifyCookie instruction checks that the schema version number of database P1 is equal to the value of P2 . The schema version number is an arbitrary integer that changes whenever the schema is updated and is used so that SQLite knows when the schema has to be reread.

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 StrNe 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 passes them to the callback function.

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.

Finally the Next instruction has no more rows to fetch and the virtual machine program calls a Close on the open table cursor and does a Halt with return code SQLITE_OK in instruction 16.

The complete list of opcodes for the SQLite VDBE is extensive and too large to cover in this chapter. A comprehensive list is maintained as part of the online documentation at http://sqlite.org/opcode.html if you find you want to analyze a particular SQL command in this level of detail.