vdbe.tcl

sqlite嵌入式数据库源码

Code {
18    Rewind        2      24                                             
19    Recno         2      0                                         
20    Column        2      1                                         
21    MakeIdxKey    1      0      n                                  
22    IdxPut        1      0      indexed columns are not unique     
23    Next          2      19                                             
}
puts {
<p>Instructions 18 through 23 implement a loop over every row of the 
table being indexed.  For each table row, we first extract the integer 
key for that row using Recno in instruction 19, then get the value of 
the "two" column using Column in instruction 20.  
The <a href="opcode.html#MakeIdxKey">MakeIdxKey</a> instruction at 21 
converts data from the "two" column (which is on the top of the stack) 
into a valid index key.  For an index on a single column, this is 
basically a no-op.  But if the P1 operand to MakeIdxKey had been 
greater than one multiple entries would have been popped from the stack 
and converted into a single index key.  
The <a href="opcode.html#IdxPut">IdxPut</a> instruction at 22 is what 
actually creates the index entry.  IdxPut pops two elements from the 
stack.  The top of the stack is used as a key to fetch an entry from the 
index table.  Then the integer which was second on stack is added to the 
set of integers for that index and the new record is written back to the 
database file.  Note
that the same index entry can store multiple integers if there
are two or more table entries with the same value for the two
column.
</p>

<p>Now let's look at how this index will be used.  Consider the
following query:</p>

<blockquote><pre>
SELECT * FROM examp WHERE two==50;
</pre></blockquote>

<p>SQLite generates the following VDBE code to handle this query:</p>
}

Code {
addr  opcode        p1     p2     p3                                      
----  ------------  -----  -----  -----------------------------------
0     ColumnName    0      0      one                                
1     ColumnName    1      0      two                                
2     Integer       0      0                                         
3     OpenRead      0      3      examp                              
4     VerifyCookie  0      256                                            
5     Integer       0      0                                         
6     OpenRead      1      4      examp_idx1                         
7     Integer       50     0      50                            
8     MakeKey       1      0      n                                  
9     MemStore      0      0                                         
10    MoveTo        1      19                                             
11    MemLoad       0      0                                         
12    IdxGT         1      19                                             
13    IdxRecno      1      0                                         
14    MoveTo        0      0                                         
15    Column        0      0                                         
16    Column        0      1                                         
17    Callback      2      0                                         
18    Next          1      11                                        
19    Close         0      0                                         
20    Close         1      0                                         
21    Halt          0      0                                         
}

puts {
<p>The SELECT begins in a familiar fashion.  First the column
names are initialized and the table being queried is opened.
Things become different beginning with instructions 5 and 6 where
the index file is also opened.  Instructions 7 and 8 make
a key with the value of 50.  
The <a href="opcode.html#MemStore">MemStore</a> instruction at 9 stores 
the index key in VDBE memory location 0.  The VDBE memory is used to 
avoid having to fetch a value from deep in the stack, which can be done,
but makes the program harder to generate.  The following instruction 
<a href="opcode.html#MoveTo">MoveTo</a> at address 10 pops the key off 
the stack and moves the index cursor to the first row of the index with 
that key.  This initializes the cursor for use in the following loop.</p>

<p>Instructions 11 through 18 implement a loop over all index records 
with the key that was fetched by instruction 8.  All of the index 
records with this key will be contiguous in the index table, so we walk 
through them and fetch the corresponding table key from the index.  
This table key is then used to move the cursor to that row in the table.  
The rest of the loop is the same as the loop for the non-indexed SELECT 
query.</p>

<p>The loop begins with the <a href="opcode.html#MemLoad">MemLoad</a> 
instruction at 11 which pushes a copy of the index key back onto the 
stack.  The instruction <a href="opcode.html#IdxGT">IdxGT</a> at 12 
compares the key to the key in the current index record pointed to by 
cursor P1.  If the index key at the current cursor location is greater 
than the the index we are looking for, then jump out of the loop.</p>

<p>The instruction <a href="opcode.html#IdxRecno">IdxRecno</a> at 13 
pushes onto the stack the table record number from the index.  The 
following MoveTo pops it and moves the table cursor to that row.  The 
next 3 instructions select the column data the same way as in the non-
indexed case. The Column instructions fetch the column data and the 
callback function is invoked.  The final Next instruction advances the 
index cursor, not the table cursor, to the next row, and then branches 
back to the start of the loop if there are any index records left.</p>

<p>Since the index is used to look up values in the table,
it is important that the index and table be kept consistent.
Now that there is an index on the examp table, we will have
to update that index whenever data is inserted, deleted, or
changed in the examp table.  Remember the first example above
where we were able to insert a new row into the "examp" table using
12 VDBE instructions.  Now that this table is indexed, 19
instructions are required.  The SQL statement is this:</p>

<blockquote><pre>
INSERT INTO examp VALUES('Hello, World!',99);
</pre></blockquote>

<p>And the generated code looks like this:</p>
}

Code {
addr  opcode        p1     p2     p3                                      
----  ------------  -----  -----  -----------------------------------
0     Transaction   1      0                                         
1     Transaction   0      0                                         
2     VerifyCookie  0      256                                            
3     Integer       0      0                                         
4     OpenWrite     0      3      examp                              
5     Integer       0      0                                         
6     OpenWrite     1      4      examp_idx1                         
7     NewRecno      0      0                                         
8     String        0      0      Hello, World!                      
9     Integer       99     0      99                                 
10    Dup           2      1                                         
11    Dup           1      1                                         
12    MakeIdxKey    1      0      n                                  
13    IdxPut        1      0                                         
14    MakeRecord    2      0                                         
15    PutIntKey     0      1                                         
16    Close         0      0                                         
17    Close         1      0                                         
18    Commit        0      0                                         
19    Halt          0      0                                         
}

puts {
<p>At this point, you should understand the VDBE well enough to
figure out on your own how the above program works.  So we will
not discuss it further in this text.</p>

<h2>Joins</h2>

<p>In a join, two or more tables are combined to generate a single
result.  The result table consists of every possible combination
of rows from the tables being joined.  The easiest and most natural
way to implement this is with nested loops.</p>

<p>Recall the query template discussed above where there was a
single loop that searched through every record of the table.
In a join we have basically the same thing except that there
are nested loops.  For example, to join two tables, the query
template might look something like this:</p>

<p>
<ol>
<li>Initialize the <b>azColumnName[]</b> array for the callback.</li>
<li>Open two cursors, one to each of the two tables being queried.</li>
<li>For each record in the first table, do:
    <ol type="a">
    <li>For each record in the second table do:
      <ol type="i">
      <li>If the WHERE clause evaluates to FALSE, then skip the steps that
          follow and continue to the next record.</li>
      <li>Compute all columns for the current row of the result.</li>
      <li>Invoke the callback function for the current row of the result.</li>
      </ol></li>
    </ol>
<li>Close both cursors.</li>
</ol>
</p>

<p>This template will work, but it is likely to be slow since we
are now dealing with an O(N<sup>2</sup>) loop.  But it often works
out that the WHERE clause can be factored into terms and that one or
more of those terms will involve only columns in the first table.
When this happens, we can factor part of the WHERE clause test out of
the inner loop and gain a lot of efficiency.  So a better template
would be something like this:</p>

<p>
<ol>
<li>Initialize the <b>azColumnName[]</b> array for the callback.</li>
<li>Open two cursors, one to each of the two tables being queried.</li>
<li>For each record in the first table, do:
    <ol type="a">
    <li>Evaluate terms of the WHERE clause that only involve columns from
        the first table.  If any term is false (meaning that the whole
        WHERE clause must be false) then skip the rest of this loop and
        continue to the next record.</li>
    <li>For each record in the second table do:
      <ol type="i">
      <li>If the WHERE clause evaluates to FALSE, then skip the steps that
          follow and continue to the next record.</li>
      <li>Compute all columns for the current row of the result.</li>
      <li>Invoke the callback function for the current row of the result.</li>
      </ol></li>
    </ol>
<li>Close both cursors.</li>
</ol>
</p>

<p>Additional speed-up can occur if an index can be used to speed
the search of either or the two loops.</p>

<p>SQLite always constructs the loops in the same order as the
tables appear in the FROM clause of the SELECT statement.  The
left-most table becomes the outer loop and the right-most table
becomes the inner loop.  It is possible, in theory, to reorder
the loops in some circumstances to speed the evaluation of the
join.  But SQLite does not attempt this optimization.</p>

<p>You can see how SQLite constructs nested loops in the following
example:</p>

<blockquote><pre>
CREATE TABLE examp2(three int, four int);
SELECT * FROM examp, examp2 WHERE two<50 AND four==two;
</pre></blockquote>
}

Code {
addr  opcode        p1     p2     p3                                      
----  ------------  -----  -----  -----------------------------------
0     ColumnName    0      0      examp.one                          
1     ColumnName    1      0      examp.two                          
2     ColumnName    2      0      examp2.three                       
3     ColumnName    3      0      examp2.four                        
4     Integer       0      0                                         
5     OpenRead      0      3      examp                              
6     VerifyCookie  0      909                                            
7     Integer       0      0                                         
8     OpenRead      1      5      examp2                             
9     Rewind        0      24                                             
10    Column        0      1                                         
11    Integer       50     0      50                                 
12    Ge            1      23                                             
13    Rewind        1      23                                             
14    Column        1      1                                         
15    Column        0      1                                         
16    Ne            1      22                                        
17    Column        0      0                                         
18    Column        0      1                                         
19    Column        1      0                                         
20    Column        1      1                                         
21    Callback      4      0                                         
22    Next          1      14                                             
23    Next          0      10                                        
24    Close         0      0                                         
25    Close         1      0                                         
26    Halt          0      0                                         
}

puts {
<p>The outer loop over table examp is implement by instructions
7 through 23.  The inner loop is instructions 13 through 22.
Notice that the "two<50" term of the WHERE expression involves
only columns from the first table and can be factored out of
the inner loop.  SQLite does this and implements the "two<50"
test in instructions 10 through 12.  The "four==two" test is
implement by instructions 14 through 16 in the inner loop.</p>

<p>SQLite does not impose any arbitrary limits on the tables in
a join.  It also allows a table to be joined with itself.</p>

<h2>The ORDER BY clause</h2>

<p>For historical reasons, and for efficiency, all sorting is currently 
done in memory.</p>

<p>SQLite implements the ORDER BY clause using a special
set of instructions to control an object called a sorter.  In the
inner-most loop of the query, where there would normally be
a Callback instruction, instead a record is constructed that
contains both callback parameters and a key.  This record
is added to the sorter (in a linked list).  After the query loop 
finishes, the list of records is sorted and this list is walked.  For 
each record on the list, the callback is invoked.  Finally, the sorter
is closed and memory is deallocated.</p>

<p>We can see the process in action in the following query:</p>

<blockquote><p