## Run this Tcl script to generate the vdbe.html file.#set rcsid {$Id: vdbe.tcl,v 1.14 2005/03/12 15:55:11 drh Exp $}source common.tclheader {The Virtual Database Engine of SQLite}puts {<h2>The Virtual Database Engine of SQLite</h2><blockquote><b>This document describes the virtual machine used in SQLite version 2.8.0. The virtual machine in SQLite version 3.0 and 3.1 is very similar inconcept but many of the opcodes have changed and the algorithms aresomewhat different.  Use this document as a rough guide to the ideabehind the virtual machine in SQLite version 3, not as a reference onhow the virtual machine works.</b></blockquote>}puts {<p>If you want to know how the SQLite library works internally,you need to begin with a solid understanding of the Virtual DatabaseEngine or VDBE.  The VDBE occurs right in the middle of theprocessing stream (see the <a href="arch.html">architecture diagram</a>)and so it seems to touch most parts of the library.  Evenparts of the code that do not directly interact with the VDBEare usually in a supporting role.  The VDBE really is the heart ofSQLite.</p><p>This article is a brief introduction to how the VDBEworks and in particular how the various VDBE instructions(documented <a href="opcode.html">here</a>) work togetherto do useful things with the database.  The style is tutorial,beginning with simple tasks and working toward solving morecomplex problems.  Along the way we will visit mostsubmodules in the SQLite library.  After completeing this tutorial,you should have a pretty good understanding of how SQLite worksand will be ready to begin studying the actual source code.</p><h2>Preliminaries</h2><p>The VDBE implements a virtual computer that runs a program inits virtual machine language.  The goal of each program is to interrogate or change the database.  Toward this end, the machinelanguage that the VDBE implements is specifically designed tosearch, read, and modify databases.</p><p>Each instruction of the VDBE language contains an opcode andthree operands labeled P1, P2, and P3.  Operand P1 is an arbitraryinteger.   P2 is a non-negative integer.  P3 is a pointer to a data structure or null-terminated string, possibly null.  Only a few VDBEinstructions use all three operands.  Many instructions use onlyone or two operands.  A significant number of instructions useno operands at all but instead take their data and store their resultson the execution stack.  The details of what each instructiondoes and which operands it uses are described in the separate<a href="opcode.html">opcode description</a> document.</p><p>A VDBE program beginsexecution on instruction 0 and continues with successive instructionsuntil it either (1) encounters a fatal error, (2) executes aHalt instruction, or (3) advances the program counter past thelast instruction of the program.  When the VDBE completes execution,all open database cursors are closed, all memory is freed, and everything is popped from the stack.So there are never any worries about memory leaks or undeallocated resources.</p><p>If you have done any assembly language programming or haveworked with any kind of abstract machine before, all of thesedetails should be familiar to you.  So let's jump right in andstart looking as some code.</p><a name="insert1"><h2>Inserting Records Into The Database</h2><p>We begin with a problem that can be solved using a VDBE programthat is only a few instructions long.  Suppose we have an SQLtable that was created like this:</p><blockquote><pre>CREATE TABLE examp(one text, two int);</pre></blockquote><p>In words, we have a database table named "examp" that has twocolumns of data named "one" and "two".  Now suppose we want to insert a singlerecord into this table.  Like this:</p><blockquote><pre>INSERT INTO examp VALUES('Hello, World!',99);</pre></blockquote><p>We can see the VDBE program that SQLite uses to implement thisINSERT using the <b>sqlite</b> command-line utility.  First startup <b>sqlite</b> on a new, empty database, then create the table.Next change the output format of <b>sqlite</b> to a form thatis designed to work with VDBE program dumps by entering the".explain" command.Finally, enter the INSERT statement shown above, but precede theINSERT with the special keyword "EXPLAIN".  The EXPLAIN keywordwill cause <b>sqlite</b> to print the VDBE program rather than execute it.  We have:</p>}proc Code {body} {  puts {<blockquote><tt>}  regsub -all {&} [string trim $body] {\&amp;} body  regsub -all {>} $body {\&gt;} body  regsub -all {<} $body {\&lt;} body  regsub -all {\(\(\(} $body {<b>} body  regsub -all {\)\)\)} $body {</b>} body  regsub -all { } $body {\&nbsp;} body  regsub -all \n $body <br>\n body  puts $body  puts {</tt></blockquote>}}Code {$ (((sqlite test_database_1)))sqlite> (((CREATE TABLE examp(one text, two int);)))sqlite> (((.explain)))sqlite> (((EXPLAIN INSERT INTO examp VALUES('Hello, World!',99);)))addr  opcode        p1     p2     p3                                      ----  ------------  -----  -----  -----------------------------------0     Transaction   0      0                                         1     VerifyCookie  0      81                                        2     Transaction   1      0                                         3     Integer       0      0                                         4     OpenWrite     0      3      examp                              5     NewRecno      0      0                                         6     String        0      0      Hello, World!                      7     Integer       99     0      99                                 8     MakeRecord    2      0                                         9     PutIntKey     0      1                                         10    Close         0      0                                         11    Commit        0      0                                         12    Halt          0      0                                         }puts {<p>As you can see above, our simple insert statement isimplemented in 12 instructions.  The first 3 and last 2 instructions are a standard prologue and epilogue, so the real work is done in the middle 7 instructions.  There are no jumps, so the program executes once through from top to bottom.  Let's now look at each instruction in detail.<p>}Code {0     Transaction   0      0                                         1     VerifyCookie  0      81                                        2     Transaction   1      0                                         }puts {<p>The instruction <a href="opcode.html#Transaction">Transaction</a> begins a transaction.  The transaction ends when a Commit or Rollback opcode is encountered.  P1 is the index of the database file on which the transaction is started.  Index 0 is the main database file.  A write lock is obtained on the database file when a transaction is started.  No other process can read or write the file while the transaction is underway.  Starting a transaction also creates a rollback journal.  A transaction must be started before any changes can be made to the database.</p><p>The instruction <a href="opcode.html#VerifyCookie">VerifyCookie</a>checks cookie 0 (the database schema version) to make sure it is equal to P2 (the value obtained when the database schema was last read).  P1 is the database number (0 for the main database).  This is done to make sure the database schema hasn't been changed by another thread, in which case it has to be reread.</p><p> The second <a href="opcode.html#Transaction">Transaction</a> instruction begins a transaction and starts a rollback journal for database 1, the database used for temporary tables.</p>}proc stack args {  puts "<blockquote><table border=2>"  foreach elem $args {    puts "<tr><td align=left>$elem</td></tr>"  }  puts "</table></blockquote>"}Code {3     Integer       0      0                                    4     OpenWrite     0      3      examp                         }puts {<p> The instruction <a href="opcode.html#Integer">Integer</a> pushes the integer value P1 (0) onto the stack.  Here 0 is the number of the database to use in the following OpenWrite instruction.  If P3 is not NULL then it is a string representation of the same integer.  Afterwards the stack looks like this:</p>}stack {(integer) 0}puts {<p> The instruction <a href="opcode.html#OpenWrite">OpenWrite</a> opens a new read/write cursor with handle P1 (0 in this case) on table "examp", whose root page is P2 (3, in this database file).  Cursor handles can be any non-negative integer.  But the VDBE allocates cursors in an array with the size of the array being one more than the largest cursor.  So to conserve memory, it is best to use handles beginning with zero and working upward consecutively.  Here P3 ("examp") is the name of the table being opened, but this is unused, and only generated to make the code easier to read.  This instruction pops the database number to use (0, the main database) from the top of the stack, so afterwards the stack is empty again.</p>}Code {5     NewRecno      0      0                                    }puts {<p> The instruction <a href="opcode.html#NewRecno">NewRecno</a> creates a new integer record number for the table pointed to by cursor P1.  The record number is one not currently used as a key in the table.  The new record number is pushed onto the stack.  Afterwards the stack looks like this:</p>}stack {(integer) new record key}Code {6     String        0      0      Hello, World!                 }puts {<p> The instruction <a href="opcode.html#String">String</a> pushes its P3 operand onto the stack.  Afterwards the stack looks like this:</p>}stack {(string) "Hello, World!"} \ {(integer) new record key}Code {7     Integer       99     0      99                            }puts {<p> The instruction <a href="opcode.html#Integer">Integer</a> pushes its P1 operand (99) onto the stack.  Afterwards the stack looks like this:</p>}stack {(integer) 99} \ {(string) "Hello, World!"} \ {(integer) new record key}Code {8     MakeRecord    2      0                                    }puts {<p> The instruction <a href="opcode.html#MakeRecord">MakeRecord</a> pops the top P1 elements off the stack (2 in this case) and converts them into the binary format used for storing records in a database file.  (See the <a href="fileformat.html">file format</a> description for details.)  The new record generated by the MakeRecord instruction is pushed back onto the stack.  Afterwards the stack looks like this:</p></ul>}stack {(record) "Hello, World!", 99} \ {(integer) new record key}Code {9     PutIntKey     0      1                                    }puts {<p> The instruction <a href="opcode.html#PutIntKey">PutIntKey</a> uses the top 2 stack entries to write an entry into the table pointed to by cursor P1.  A new entry is created if it doesn't already exist or the data for an existing entry is overwritten.  The record data is the top stack entry, and the key is the next entry down.  The stack is popped twice by this instruction.  Because operand P2 is 1 the row change count is incremented and the rowid is stored for subsequent return by the sqlite_last_insert_rowid() function.  If P2 is 0 the row change count is unmodified.  This instruction is where the insert actually occurs.</p>}Code {10    Close         0      0                                         }puts {<p> The instruction <a href="opcode.html#Close">Close</a> closes a cursor previously opened as P1 (0, the only open cursor). If P1 is not currently open, this instruction is a no-op.</p>}Code {11    Commit        0      0                                         }puts {<p> The instruction <a href="opcode.html#Commit">Commit</a> causes all modifications to the database that have been made since the last Transaction to actually take effect.  No additional modifications are allowed until another transaction is started.  The Commit instruction deletes the journal file and releases the write lock on the database.  A read lock continues to be held if there are still cursors open.</p>}