/ Check-in [937c27b7]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment::-) (CVS 108)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 937c27b7e18505d0f8b85d2040db8d6a8b7cd441
User & Date: drh 2000-06-26 12:02:51
Context
2000-07-28
14:32
added the sqlite_busy_handler() interface (CVS 109) check-in: 4fe8e51c user: drh tags: trunk
2000-06-26
12:02
:-) (CVS 108) check-in: 937c27b7 user: drh tags: trunk
2000-06-23
19:16
Begin writing the VDBE tutorial (CVS 107) check-in: 79ce59cf user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to www/vdbe.tcl.

     1      1   #
     2      2   # Run this Tcl script to generate the vdbe.html file.
     3      3   #
     4         -set rcsid {$Id: vdbe.tcl,v 1.2 2000/06/23 19:16:23 drh Exp $}
            4  +set rcsid {$Id: vdbe.tcl,v 1.3 2000/06/26 12:02:51 drh Exp $}
     5      5   
     6      6   puts {<html>
     7      7   <head>
     8      8     <title>The Virtual Database Engine of SQLite</title>
     9      9   </head>
    10     10   <body bgcolor=white>
    11     11   <h1 align=center>
................................................................................
    21     21   }
    22     22   
    23     23   puts {
    24     24   <p>If you want to know how the SQLite library works internally,
    25     25   you need to begin with a solid understanding of the Virtual Database
    26     26   Engine or VDBE.  The VDBE occurs right in the middle of the
    27     27   processing stream (see the <a href="arch.html">architecture diagram</a>)
    28         -and so it seems to touch most as parts of the library.  Even
           28  +and so it seems to touch most parts of the library.  Even
    29     29   parts of the code that do not directly interact with the VDBE
    30     30   are usually in a supporting role.  The VDBE really is the heart of
    31     31   SQLite.</p>
    32     32   
    33         -<p>This article is a brief tutorial introduction to how the VDBE
           33  +<p>This article is a brief introduction to how the VDBE
    34     34   works and in particular how the various VDBE instructions
    35     35   (documented <a href="opcode.html">here</a>) work together
    36     36   to do useful things with the database.  The style is tutorial,
    37     37   beginning with simple tasks and working toward solving more
    38         -complex problems.  Along the way we will touch briefly on most
    39         -aspects of the SQLite library.  After completeing this tutorial,
           38  +complex problems.  Along the way we will visit most
           39  +submodules in the SQLite library.  After completeing this tutorial,
    40     40   you should have a pretty good understanding of how SQLite works
    41     41   and will be ready to begin studying the actual source code.</p>
    42     42   
    43     43   <h2>Preliminaries</h2>
    44     44   
    45     45   <p>The VDBE implements a virtual computer that runs a program in
    46     46   its virtual machine language.  The goal of each program is to 
    47         -interagate or change the database.  Toward this end, the machine
           47  +interrogate or change the database.  Toward this end, the machine
    48     48   language that the VDBE implements is specifically designed to
    49         -work with databases.</p>
           49  +search, read, and modify databases.</p>
    50     50   
    51     51   <p>Each instruction of the VDBE language contains an opcode and
    52     52   three operands labeled P1, P2, and P3.  Operand P1 is an arbitrary
    53     53   integer.   P2 is a non-negative integer.  P3 is a null-terminated
    54     54   string, or possibly just a null pointer.  Only a few VDBE
    55     55   instructions use all three operands.  Many instructions use only
    56     56   one or two operands.  A significant number of instructions use
    57         -no operands at all, taking there data and storing their results
           57  +no operands at all but instead take their data and storing their results
    58     58   on the execution stack.  The details of what each instruction
    59     59   does and which operands it uses are described in the separate
    60     60   <a href="opcode.html">opcode description</a> document.</p>
    61     61   
    62     62   <p>A VDBE program begins
    63     63   execution on instruction 0 and continues with successive instructions
    64     64   until it either (1) encounters a fatal error, (2) executes a
................................................................................
    78     78   <h2>Inserting Records Into The Database</h2>
    79     79   
    80     80   <p>We begin with a problem that can be solved using a VDBE program
    81     81   that is only a few instructions long.  Suppose we have an SQL
    82     82   table that was created like this:</p>
    83     83   
    84     84   <blockquote><pre>
    85         -CREATE TABLE ex(one text, two int);
           85  +CREATE TABLE examp(one text, two int);
    86     86   </pre></blockquote>
    87     87   
    88         -<p>In words, we have a database table named "ex" that has two
           88  +<p>In words, we have a database table named "examp" that has two
    89     89   columns of data named "one" and "two".  Now suppose we want to insert a single
    90     90   record into this table.  Like this:</p>
    91     91   
    92     92   <blockquote><pre>
    93         -INSERT INTO ex VALUES('Hello, World!',99);
           93  +INSERT INTO examp VALUES('Hello, World!',99);
    94     94   </pre></blockquote>
    95     95   
    96     96   <p>We can see the VDBE program that SQLite uses to implement this
    97     97   INSERT using the <b>sqlite</b> command-line utility.  First start
    98     98   up <b>sqlite</b> on a new, empty database, then create the table.
    99     99   Finally, enter the INSERT statement shown above, but precede the
   100    100   INSERT with the special keyword "EXPLAIN".  The EXPLAIN keyword
................................................................................
   192    192   onto the stack, so that after the 5th instruction executes,
   193    193   the stack looks like this:</p>
   194    194   }
   195    195   
   196    196   stack {A data record holding "Hello, World!" and 99} \
   197    197     {A random integer key}
   198    198   
   199         -puts {<p>The last instruction pops top elements from the stack
          199  +puts {<p>The last instruction pops the top two elements from the stack
   200    200   and uses them as data and key to make a new entry in database
   201    201   database file pointed to by cursor P1.  This instruction is where
   202    202   the insert actually occurs.</p>
   203    203   
   204    204   <p>After the last instruction executes, the program counter
   205    205   advances to one past the last instruction, which causes the
   206    206   VDBE to halt.  When the VDBE halts, it automatically closes
   207    207   all open cursors, frees any elements left on the stack,
   208    208   and releases any other resources we may have allocated.
   209    209   In this case, the only cleanup necessary is to close the
   210         -open cursor to the "examp" file.</p>
          210  +cursor to the "examp" file.</p>
   211    211   
   212    212   <a name="trace">
   213    213   <h2>Tracing VDBE Program Execution</h2>
   214    214   
   215    215   <p>If the SQLite library is compiled without the NDEBUG 
   216         -preprocessor macro being defined, then
          216  +preprocessor macro, then
   217    217   there is a special SQL comment that will cause the 
   218    218   the VDBE to traces the execution of programs.
   219    219   Though this features was originally intended for testing
   220    220   and debugging, it might also be useful in learning about
   221    221   how the VDBE operates.
   222    222   Use the "<tt>--vdbe-trace-on--</tt>" comment to
   223    223   turn tracing on and "<tt>--vdbe-trace-off--</tt>" to turn tracing
................................................................................
   241    241   
   242    242   puts {
   243    243   <p>With tracing mode on, the VDBE prints each instruction prior
   244    244   to executing it.  After the instruction is executed, the top few
   245    245   entries in the stack are displayed.  The stack display is omitted
   246    246   if the stack is empty.</p>
   247    247   
   248         -<p>On the stack display, most entries are show with a prefix
          248  +<p>On the stack display, most entries are shown with a prefix
   249    249   that tells the datatype of that stack entry.  Integers begin
   250    250   with "<tt>i:</tt>".  Floating point values begin with "<tt>r:</tt>".
   251    251   (The "r" stands for "real-number".)  Strings begin with either
   252    252   "<tt>s:</tt>" or "<tt>z:</tt>".  The difference between s: and
   253    253   z: strings is that z: strings are stored in memory obtained
   254    254   from <b>malloc()</b>.  This doesn't make any difference to you,
   255    255   the observer, but it is vitally important to the VDBE since the
................................................................................
   522    522   }
   523    523   
   524    524   puts {
   525    525   <p>Here is what the program must do.  First it has to locate all of
   526    526   the records in the "examp" database that are to be deleted.  This is
   527    527   done using a loop very much like the loop used in the SELECT examples
   528    528   above.  Once all records have been located, then we can go back through
   529         -an delete them one by one.  Note that we cannot delete each record
          529  +and delete them one by one.  Note that we cannot delete each record
   530    530   as soon as we find it.  We have to locate all records first, then
   531    531   go back and delete them.  This is because the GDBM database
   532    532   backend might change the scan order after a delete operation.
   533    533   And if the scan
   534    534   order changes in the middle of the scan, some records might be
   535         -tested more than once, and some records might not be tested at all.</p>
          535  +visited more than once and other records might not be visited at all.</p>
   536    536   
   537    537   <p>So the implemention of DELETE is really in two loops.  The
   538    538   first loop (instructions 2 through 8 in the example) locates the records that
   539    539   are to be deleted and the second loop (instructions 12 through 14)
   540         -do the actual deleting.</p>
          540  +does the actual deleting.</p>
   541    541   
   542    542   <p>The very first instruction in the program, the ListOpen instruction,
   543    543   creates a new List object in which we can store the keys of the records
   544    544   that are to be deleted.  The P1 operand serves as a handle to the
   545    545   list.  As with cursors, you can open as many lists as you like
   546    546   (though in practice we never need more than one at a time.)  Each list
   547    547   has a handle specified by P1 which is a non-negative integer.  The
................................................................................
   577    577   
   578    578   <p>At the end of the first loop, the cursor is closed at instruction 9,
   579    579   and the list is rewound back to the beginning at instruction 10.
   580    580   The Open instruction at 11 reopens the same database file, but for
   581    581   writing this time.  The loop that does the actual deleting of records
   582    582   is on instructions 12, 13, and 14.</p>
   583    583   
   584         -<p>The ListRead instruction as 12 reads a single integer key from
          584  +<p>The ListRead instruction at 12 reads a single integer key from
   585    585   the list and pushes that key onto the stack.  If there are no
   586    586   more keys, nothing gets pushed onto the stack but instead a jump
   587    587   is made to instruction 15.  Notice the similarity 
   588    588   between the ListRead and Next instructions.  Both operations work
   589    589   according to this rule:</p>
   590    590   
   591    591   <blockquote>
................................................................................
   594    594   </blockquote>
   595    595   
   596    596   <p>The only difference between Next and ListRead is their idea
   597    597   of a "thing". The "things" for the Next instruction are records
   598    598   in a database file.  "Things" for ListRead are integer keys in a list.
   599    599   Later on,
   600    600   we will see other looping instructions (NextIdx and SortNext) that
   601         -operating using the same principle.</p>
          601  +operate using the same principle.</p>
   602    602   
   603    603   <p>The Delete instruction at address 13 pops an integer key from
   604    604   the stack (the key was put there by the preceding ListRead
   605    605   instruction) and deletes the record of cursor P1 that has that key.
   606    606   If there is no record in the database with the given key, then
   607    607   Delete is a no-op.</p>
   608    608   
................................................................................
   620    620   </p>
   621    621   
   622    622   <blockquote><pre>
   623    623   UPDATE examp SET one= '(' || one || ')' WHERE two < 50;
   624    624   </pre></blockquote>
   625    625   
   626    626   <p>Instead of deleting records where the "two" column is less than
   627         -50, this statement just puts the "one" column in paraentheses
          627  +50, this statement just puts the "one" column in parentheses
   628    628   The VDBE program to implement this statement follows:</p>
   629    629   }
   630    630   
   631    631   Code {
   632    632   addr  opcode        p1     p2     p3                                      
   633    633   ----  ------------  -----  -----  ----------------------------------------
   634    634   0     ListOpen      0      0