| 1 |
<!DOCTYPE html> |
| 2 |
<html><head> |
| 3 |
<meta name="viewport" content="width=device-width, initial-scale=1.0"> |
| 4 |
<meta http-equiv="content-type" content="text/html; charset=UTF-8"> |
| 5 |
<link href="sqlite.css" rel="stylesheet"> |
| 6 |
<title>The Virtual Database Engine of SQLite</title> |
| 7 |
<!-- path= --> |
| 8 |
</head> |
| 9 |
<body> |
| 10 |
<div class=nosearch> |
| 11 |
<a href="index.html"> |
| 12 |
<img class="logo" src="images/sqlite370_banner.svg" alt="SQLite" border="0"> |
| 13 |
</a> |
| 14 |
<div><!-- IE hack to prevent disappearing logo --></div> |
| 15 |
<div class="tagline desktoponly"> |
| 16 |
Small. Fast. Reliable.<br>Choose any three. |
| 17 |
</div> |
| 18 |
<div class="menu mainmenu"> |
| 19 |
<ul> |
| 20 |
<li><a href="index.html">Home</a> |
| 21 |
<li class='mobileonly'><a href="javascript:void(0)" onclick='toggle_div("submenu")'>Menu</a> |
| 22 |
<li class='wideonly'><a href='about.html'>About</a> |
| 23 |
<li class='desktoponly'><a href="docs.html">Documentation</a> |
| 24 |
<li class='desktoponly'><a href="download.html">Download</a> |
| 25 |
<li class='wideonly'><a href='copyright.html'>License</a> |
| 26 |
<li class='desktoponly'><a href="support.html">Support</a> |
| 27 |
<li class='desktoponly'><a href="prosupport.html">Purchase</a> |
| 28 |
<li class='search' id='search_menubutton'> |
| 29 |
<a href="javascript:void(0)" onclick='toggle_search()'>Search</a> |
| 30 |
</ul> |
| 31 |
</div> |
| 32 |
<div class="menu submenu" id="submenu"> |
| 33 |
<ul> |
| 34 |
<li><a href='about.html'>About</a> |
| 35 |
<li><a href='docs.html'>Documentation</a> |
| 36 |
<li><a href='download.html'>Download</a> |
| 37 |
<li><a href='support.html'>Support</a> |
| 38 |
<li><a href='prosupport.html'>Purchase</a> |
| 39 |
</ul> |
| 40 |
</div> |
| 41 |
<div class="searchmenu" id="searchmenu"> |
| 42 |
<form method="GET" action="search"> |
| 43 |
<select name="s" id="searchtype"> |
| 44 |
<option value="d">Search Documentation</option> |
| 45 |
<option value="c">Search Changelog</option> |
| 46 |
</select> |
| 47 |
<input type="text" name="q" id="searchbox" value=""> |
| 48 |
<input type="submit" value="Go"> |
| 49 |
</form> |
| 50 |
</div> |
| 51 |
</div> |
| 52 |
<script> |
| 53 |
function toggle_div(nm) { |
| 54 |
var w = document.getElementById(nm); |
| 55 |
if( w.style.display=="block" ){ |
| 56 |
w.style.display = "none"; |
| 57 |
}else{ |
| 58 |
w.style.display = "block"; |
| 59 |
} |
| 60 |
} |
| 61 |
function toggle_search() { |
| 62 |
var w = document.getElementById("searchmenu"); |
| 63 |
if( w.style.display=="block" ){ |
| 64 |
w.style.display = "none"; |
| 65 |
} else { |
| 66 |
w.style.display = "block"; |
| 67 |
setTimeout(function(){ |
| 68 |
document.getElementById("searchbox").focus() |
| 69 |
}, 30); |
| 70 |
} |
| 71 |
} |
| 72 |
function div_off(nm){document.getElementById(nm).style.display="none";} |
| 73 |
window.onbeforeunload = function(e){div_off("submenu");} |
| 74 |
/* Disable the Search feature if we are not operating from CGI, since */ |
| 75 |
/* Search is accomplished using CGI and will not work without it. */ |
| 76 |
if( !location.origin || !location.origin.match || !location.origin.match(/http/) ){ |
| 77 |
document.getElementById("search_menubutton").style.display = "none"; |
| 78 |
} |
| 79 |
/* Used by the Hide/Show button beside syntax diagrams, to toggle the */ |
| 80 |
function hideorshow(btn,obj){ |
| 81 |
var x = document.getElementById(obj); |
| 82 |
var b = document.getElementById(btn); |
| 83 |
if( x.style.display!='none' ){ |
| 84 |
x.style.display = 'none'; |
| 85 |
b.innerHTML='show'; |
| 86 |
}else{ |
| 87 |
x.style.display = ''; |
| 88 |
b.innerHTML='hide'; |
| 89 |
} |
| 90 |
return false; |
| 91 |
} |
| 92 |
var antiRobot = 0; |
| 93 |
function antiRobotGo(){ |
| 94 |
if( antiRobot!=3 ) return; |
| 95 |
antiRobot = 7; |
| 96 |
var j = document.getElementById("mtimelink"); |
| 97 |
if(j && j.hasAttribute("data-href")) j.href=j.getAttribute("data-href"); |
| 98 |
} |
| 99 |
function antiRobotDefense(){ |
| 100 |
document.body.onmousedown=function(){ |
| 101 |
antiRobot |= 2; |
| 102 |
antiRobotGo(); |
| 103 |
document.body.onmousedown=null; |
| 104 |
} |
| 105 |
document.body.onmousemove=function(){ |
| 106 |
antiRobot |= 2; |
| 107 |
antiRobotGo(); |
| 108 |
document.body.onmousemove=null; |
| 109 |
} |
| 110 |
setTimeout(function(){ |
| 111 |
antiRobot |= 1; |
| 112 |
antiRobotGo(); |
| 113 |
}, 100) |
| 114 |
antiRobotGo(); |
| 115 |
} |
| 116 |
antiRobotDefense(); |
| 117 |
</script> |
| 118 |
|
| 119 |
<h2>The Virtual Database Engine of SQLite</h2> |
| 120 |
|
| 121 |
<blockquote><font color="red"> |
| 122 |
<b>Obsolete Documentation Warning:</b> |
| 123 |
This document describes the virtual machine used in SQLite version 2.8.0. |
| 124 |
The virtual machine in SQLite version 3.0 and 3.1 is similar in |
| 125 |
concept but is now register-based instead of stack-based, has five |
| 126 |
operands per opcode instead of three, and has a different set of |
| 127 |
opcodes from those shown below. See the <a href="opcode.html">virtual machine instructions</a> |
| 128 |
document for the current set of VDBE opcodes and a brief overview |
| 129 |
of how the VDBE operates. This document is retained as an historical |
| 130 |
reference. |
| 131 |
</font></blockquote> |
| 132 |
|
| 133 |
|
| 134 |
<p>If you want to know how the SQLite library works internally, |
| 135 |
you need to begin with a solid understanding of the Virtual Database |
| 136 |
Engine or VDBE. The VDBE occurs right in the middle of the |
| 137 |
processing stream (see the <a href="arch.html">architecture diagram</a>) |
| 138 |
and so it seems to touch most parts of the library. Even |
| 139 |
parts of the code that do not directly interact with the VDBE |
| 140 |
are usually in a supporting role. The VDBE really is the heart of |
| 141 |
SQLite.</p> |
| 142 |
|
| 143 |
<p>This article is a brief introduction to how the VDBE |
| 144 |
works and in particular how the various VDBE instructions |
| 145 |
(documented <a href="opcode.html">here</a>) work together |
| 146 |
to do useful things with the database. The style is tutorial, |
| 147 |
beginning with simple tasks and working toward solving more |
| 148 |
complex problems. Along the way we will visit most |
| 149 |
submodules in the SQLite library. After completing this tutorial, |
| 150 |
you should have a pretty good understanding of how SQLite works |
| 151 |
and will be ready to begin studying the actual source code.</p> |
| 152 |
|
| 153 |
<h2>Preliminaries</h2> |
| 154 |
|
| 155 |
<p>The VDBE implements a virtual computer that runs a program in |
| 156 |
its virtual machine language. The goal of each program is to |
| 157 |
interrogate or change the database. Toward this end, the machine |
| 158 |
language that the VDBE implements is specifically designed to |
| 159 |
search, read, and modify databases.</p> |
| 160 |
|
| 161 |
<p>Each instruction of the VDBE language contains an opcode and |
| 162 |
three operands labeled P1, P2, and P3. Operand P1 is an arbitrary |
| 163 |
integer. P2 is a non-negative integer. P3 is a pointer to a data |
| 164 |
structure or zero-terminated string, possibly null. Only a few VDBE |
| 165 |
instructions use all three operands. Many instructions use only |
| 166 |
one or two operands. A significant number of instructions use |
| 167 |
no operands at all but instead take their data and store their results |
| 168 |
on the execution stack. The details of what each instruction |
| 169 |
does and which operands it uses are described in the separate |
| 170 |
<a href="opcode.html">opcode description</a> document.</p> |
| 171 |
|
| 172 |
<p>A VDBE program begins |
| 173 |
execution on instruction 0 and continues with successive instructions |
| 174 |
until it either (1) encounters a fatal error, (2) executes a |
| 175 |
Halt instruction, or (3) advances the program counter past the |
| 176 |
last instruction of the program. When the VDBE completes execution, |
| 177 |
all open database cursors are closed, all memory is freed, and |
| 178 |
everything is popped from the stack. |
| 179 |
So there are never any worries about memory leaks or |
| 180 |
undeallocated resources.</p> |
| 181 |
|
| 182 |
<p>If you have done any assembly language programming or have |
| 183 |
worked with any kind of abstract machine before, all of these |
| 184 |
details should be familiar to you. So let's jump right in and |
| 185 |
start looking at some code.</p> |
| 186 |
|
| 187 |
<a name="insert1"></a> |
| 188 |
<h2>Inserting Records Into The Database</h2> |
| 189 |
|
| 190 |
<p>We begin with a problem that can be solved using a VDBE program |
| 191 |
that is only a few instructions long. Suppose we have an SQL |
| 192 |
table that was created like this:</p> |
| 193 |
|
| 194 |
<blockquote><pre> |
| 195 |
CREATE TABLE examp(one text, two int); |
| 196 |
</pre></blockquote> |
| 197 |
|
| 198 |
<p>In words, we have a database table named "examp" that has two |
| 199 |
columns of data named "one" and "two". Now suppose we want to insert a single |
| 200 |
record into this table. Like this:</p> |
| 201 |
|
| 202 |
<blockquote><pre> |
| 203 |
INSERT INTO examp VALUES('Hello, World!',99); |
| 204 |
</pre></blockquote> |
| 205 |
|
| 206 |
<p>We can see the VDBE program that SQLite uses to implement this |
| 207 |
INSERT using the <b>sqlite</b> command-line utility. First start |
| 208 |
up <b>sqlite</b> on a new, empty database, then create the table. |
| 209 |
Next change the output format of <b>sqlite</b> to a form that |
| 210 |
is designed to work with VDBE program dumps by entering the |
| 211 |
".explain" command. |
| 212 |
Finally, enter the [INSERT] statement shown above, but precede the |
| 213 |
[INSERT] with the special keyword [EXPLAIN]. The [EXPLAIN] keyword |
| 214 |
will cause <b>sqlite</b> to print the VDBE program rather than |
| 215 |
execute it. We have:</p> |
| 216 |
<blockquote><tt>$ <b>sqlite test_database_1</b><br> |
| 217 |
sqlite> <b>CREATE TABLE examp(one text, two int);</b><br> |
| 218 |
sqlite> <b>.explain</b><br> |
| 219 |
sqlite> <b>EXPLAIN INSERT INTO examp VALUES('Hello, World!',99);</b><br> |
| 220 |
addr opcode p1 p2 p3 <br> |
| 221 |
---- ------------ ----- ----- -----------------------------------<br> |
| 222 |
0 Transaction 0 0 <br> |
| 223 |
1 VerifyCookie 0 81 <br> |
| 224 |
2 Transaction 1 0 <br> |
| 225 |
3 Integer 0 0 <br> |
| 226 |
4 OpenWrite 0 3 examp <br> |
| 227 |
5 NewRecno 0 0 <br> |
| 228 |
6 String 0 0 Hello, World! <br> |
| 229 |
7 Integer 99 0 99 <br> |
| 230 |
8 MakeRecord 2 0 <br> |
| 231 |
9 PutIntKey 0 1 <br> |
| 232 |
10 Close 0 0 <br> |
| 233 |
11 Commit 0 0 <br> |
| 234 |
12 Halt 0 0</tt></blockquote><p>As you can see above, our simple insert statement is |
| 235 |
implemented in 12 instructions. The first 3 and last 2 instructions are |
| 236 |
a standard prologue and epilogue, so the real work is done in the middle |
| 237 |
7 instructions. There are no jumps, so the program executes once through |
| 238 |
from top to bottom. Let's now look at each instruction in detail.<p> |
| 239 |
<blockquote><tt>0 Transaction 0 0 <br> |
| 240 |
1 VerifyCookie 0 81 <br> |
| 241 |
2 Transaction 1 0</tt></blockquote> |
| 242 |
<p>The instruction <a href="opcode.html#Transaction">Transaction</a> |
| 243 |
begins a transaction. The transaction ends when a Commit or Rollback |
| 244 |
opcode is encountered. P1 is the index of the database file on which |
| 245 |
the transaction is started. Index 0 is the main database file. A write |
| 246 |
lock is obtained on the database file when a transaction is started. |
| 247 |
No other process can read or write the file while the transaction is |
| 248 |
underway. Starting a transaction also creates a rollback journal. A |
| 249 |
transaction must be started before any changes can be made to the |
| 250 |
database.</p> |
| 251 |
|
| 252 |
<p>The instruction <a href="opcode.html#VerifyCookie">VerifyCookie</a> |
| 253 |
checks cookie 0 (the database schema version) to make sure it is equal |
| 254 |
to P2 (the value obtained when the database schema was last read). |
| 255 |
P1 is the database number (0 for the main database). This is done to |
| 256 |
make sure the database schema hasn't been changed by another thread, in |
| 257 |
which case it has to be reread.</p> |
| 258 |
|
| 259 |
<p> The second <a href="opcode.html#Transaction">Transaction</a> |
| 260 |
instruction begins a transaction and starts a rollback journal for |
| 261 |
database 1, the database used for temporary tables.</p> |
| 262 |
<blockquote><tt>3 Integer 0 0 <br> |
| 263 |
4 OpenWrite 0 3 examp</tt></blockquote> |
| 264 |
<p> The instruction <a href="opcode.html#Integer">Integer</a> pushes |
| 265 |
the integer value P1 (0) onto the stack. Here 0 is the number of the |
| 266 |
database to use in the following OpenWrite instruction. If P3 is not |
| 267 |
NULL then it is a string representation of the same integer. Afterwards |
| 268 |
the stack looks like this:</p> |
| 269 |
<blockquote><table border=2><tr><td align=left>(integer) 0</td></tr></table></blockquote> |
| 270 |
<p> The instruction <a href="opcode.html#OpenWrite">OpenWrite</a> opens |
| 271 |
a new read/write cursor with handle P1 (0 in this case) on table "examp", |
| 272 |
whose root page is P2 (3, in this database file). Cursor handles can be |
| 273 |
any non-negative integer. But the VDBE allocates cursors in an array |
| 274 |
with the size of the array being one more than the largest cursor. So |
| 275 |
to conserve memory, it is best to use handles beginning with zero and |
| 276 |
working upward consecutively. Here P3 ("examp") is the name of the |
| 277 |
table being opened, but this is unused, and only generated to make the |
| 278 |
code easier to read. This instruction pops the database number to use |
| 279 |
(0, the main database) from the top of the stack, so afterwards the |
| 280 |
stack is empty again.</p> |
| 281 |
<blockquote><tt>5 NewRecno 0 0</tt></blockquote> |
| 282 |
<p> The instruction <a href="opcode.html#NewRecno">NewRecno</a> creates |
| 283 |
a new integer record number for the table pointed to by cursor P1. The |
| 284 |
record number is one not currently used as a key in the table. The new |
| 285 |
record number is pushed onto the stack. Afterwards the stack looks like |
| 286 |
this:</p> |
| 287 |
<blockquote><table border=2><tr><td align=left>(integer) new record key</td></tr></table></blockquote><blockquote><tt>6 String 0 0 Hello, World!</tt></blockquote> |
| 288 |
<p> The instruction <a href="opcode.html#String">String</a> pushes its |
| 289 |
P3 operand onto the stack. Afterwards the stack looks like this:</p> |
| 290 |
<blockquote><table border=2><tr><td align=left>(string) "Hello, World!"</td></tr><tr><td align=left>(integer) new record key</td></tr></table></blockquote><blockquote><tt>7 Integer 99 0 99</tt></blockquote> |
| 291 |
<p> The instruction <a href="opcode.html#Integer">Integer</a> pushes |
| 292 |
its P1 operand (99) onto the stack. Afterwards the stack looks like |
| 293 |
this:</p> |
| 294 |
<blockquote><table border=2><tr><td align=left>(integer) 99</td></tr><tr><td align=left>(string) "Hello, World!"</td></tr><tr><td align=left>(integer) new record key</td></tr></table></blockquote><blockquote><tt>8 MakeRecord 2 0</tt></blockquote> |
| 295 |
<p> The instruction <a href="opcode.html#MakeRecord">MakeRecord</a> pops |
| 296 |
the top P1 elements off the stack (2 in this case) and converts them into |
| 297 |
the binary format used for storing records in a database file. |
| 298 |
(See the <a href="fileformat.html">file format</a> description for |
| 299 |
details.) The new record generated by the MakeRecord instruction is |
| 300 |
pushed back onto the stack. Afterwards the stack looks like this:</p> |
| 301 |
</ul> |
| 302 |
<blockquote><table border=2><tr><td align=left>(record) "Hello, World!", 99</td></tr><tr><td align=left>(integer) new record key</td></tr></table></blockquote><blockquote><tt>9 PutIntKey 0 1</tt></blockquote> |
| 303 |
<p> The instruction <a href="opcode.html#PutIntKey">PutIntKey</a> uses |
| 304 |
the top 2 stack entries to write an entry into the table pointed to by |
| 305 |
cursor P1. A new entry is created if it doesn't already exist or the |
| 306 |
data for an existing entry is overwritten. The record data is the top |
| 307 |
stack entry, and the key is the next entry down. The stack is popped |
| 308 |
twice by this instruction. Because operand P2 is 1 the row change count |
| 309 |
is incremented and the rowid is stored for subsequent return by the |
| 310 |
sqlite_last_insert_rowid() function. If P2 is 0 the row change count is |
| 311 |
unmodified. This instruction is where the insert actually occurs.</p> |
| 312 |
<blockquote><tt>10 Close 0 0</tt></blockquote> |
| 313 |
<p> The instruction <a href="opcode.html#Close">Close</a> closes a |
| 314 |
cursor previously opened as P1 (0, the only open cursor). If P1 is not |
| 315 |
currently open, this instruction is a no-op.</p> |
| 316 |
<blockquote><tt>11 Commit 0 0</tt></blockquote> |
| 317 |
<p> The instruction <a href="opcode.html#Commit">Commit</a> causes all |
| 318 |
modifications to the database that have been made since the last |
| 319 |
Transaction to actually take effect. No additional modifications are |
| 320 |
allowed until another transaction is started. The Commit instruction |
| 321 |
deletes the journal file and releases the write lock on the database. |
| 322 |
A read lock continues to be held if there are still cursors open.</p> |
| 323 |
<blockquote><tt>12 Halt 0 0</tt></blockquote> |
| 324 |
<p> The instruction <a href="opcode.html#Halt">Halt</a> causes the VDBE |
| 325 |
engine to exit immediately. All open cursors, Lists, Sorts, etc are |
| 326 |
closed automatically. P1 is the result code returned by sqlite_exec(). |
| 327 |
For a normal halt, this should be SQLITE_OK (0). For errors, it can be |
| 328 |
some other value. The operand P2 is only used when there is an error. |
| 329 |
There is an implied "Halt 0 0 0" instruction at the end of every |
| 330 |
program, which the VDBE appends when it prepares a program to run.</p> |
| 331 |
|
| 332 |
|
| 333 |
<a name="trace"></a> |
| 334 |
<h2>Tracing VDBE Program Execution</h2> |
| 335 |
|
| 336 |
<p>If the SQLite library is compiled without the NDEBUG preprocessor |
| 337 |
macro, then the PRAGMA <a href="pragma.html#pragma_vdbe_trace">vdbe_trace |
| 338 |
</a> causes the VDBE to trace the execution of programs. Though this |
| 339 |
feature was originally intended for testing and debugging, it can also |
| 340 |
be useful in learning about how the VDBE operates. |
| 341 |
Use "<tt>PRAGMA vdbe_trace=ON;</tt>" to turn tracing on and |
| 342 |
"<tt>PRAGMA vdbe_trace=OFF</tt>" to turn tracing back off. |
| 343 |
Like this:</p> |
| 344 |
<blockquote><tt>sqlite> <b>PRAGMA vdbe_trace=ON;</b><br> |
| 345 |
0 Halt 0 0<br> |
| 346 |
sqlite> <b>INSERT INTO examp VALUES('Hello, World!',99);</b><br> |
| 347 |
0 Transaction 0 0<br> |
| 348 |
1 VerifyCookie 0 81<br> |
| 349 |
2 Transaction 1 0<br> |
| 350 |
3 Integer 0 0<br> |
| 351 |
Stack: i:0<br> |
| 352 |
4 OpenWrite 0 3 examp<br> |
| 353 |
5 NewRecno 0 0<br> |
| 354 |
Stack: i:2<br> |
| 355 |
6 String 0 0 Hello, World!<br> |
| 356 |
Stack: t[Hello,.World!] i:2<br> |
| 357 |
7 Integer 99 0 99<br> |
| 358 |
Stack: si:99 t[Hello,.World!] i:2<br> |
| 359 |
8 MakeRecord 2 0<br> |
| 360 |
Stack: s[...Hello,.World!.99] i:2<br> |
| 361 |
9 PutIntKey 0 1<br> |
| 362 |
10 Close 0 0<br> |
| 363 |
11 Commit 0 0<br> |
| 364 |
12 Halt 0 0</tt></blockquote> |
| 365 |
<p>With tracing mode on, the VDBE prints each instruction prior |
| 366 |
to executing it. After the instruction is executed, the top few |
| 367 |
entries in the stack are displayed. The stack display is omitted |
| 368 |
if the stack is empty.</p> |
| 369 |
|
| 370 |
<p>On the stack display, most entries are shown with a prefix |
| 371 |
that tells the datatype of that stack entry. Integers begin |
| 372 |
with "<tt>i:</tt>". Floating point values begin with "<tt>r:</tt>". |
| 373 |
(The "r" stands for "real-number".) Strings begin with either |
| 374 |
"<tt>s:</tt>", "<tt>t:</tt>", "<tt>e:</tt>" or "<tt>z:</tt>". |
| 375 |
The difference among the string prefixes is caused by how their |
| 376 |
memory is allocated. The z: strings are stored in memory obtained |
| 377 |
from <b>malloc()</b>. The t: strings are statically allocated. |
| 378 |
The e: strings are ephemeral. All other strings have the s: prefix. |
| 379 |
This doesn't make any difference to you, |
| 380 |
the observer, but it is vitally important to the VDBE since the |
| 381 |
z: strings need to be passed to <b>free()</b> when they are |
| 382 |
popped to avoid a memory leak. Note that only the first 10 |
| 383 |
characters of string values are displayed and that binary |
| 384 |
values (such as the result of the MakeRecord instruction) are |
| 385 |
treated as strings. The only other datatype that can be stored |
| 386 |
on the VDBE stack is a NULL, which is displayed without prefix |
| 387 |
as simply "<tt>NULL</tt>". If an integer has been placed on the |
| 388 |
stack as both an integer and a string, its prefix is "<tt>si:</tt>". |
| 389 |
|
| 390 |
|
| 391 |
<a name="query1"></a> |
| 392 |
<h2>Simple Queries</h2> |
| 393 |
|
| 394 |
<p>At this point, you should understand the basics of how the VDBE |
| 395 |
writes to a database. Now let's look at how it does queries. |
| 396 |
We will use the following simple SELECT statement as our example:</p> |
| 397 |
|
| 398 |
<blockquote><pre> |
| 399 |
SELECT * FROM examp; |
| 400 |
</pre></blockquote> |
| 401 |
|
| 402 |
<p>The VDBE program generated for this SQL statement is as follows:</p> |
| 403 |
<blockquote><tt>sqlite> <b>EXPLAIN SELECT * FROM examp;</b><br> |
| 404 |
addr opcode p1 p2 p3 <br> |
| 405 |
---- ------------ ----- ----- -----------------------------------<br> |
| 406 |
0 ColumnName 0 0 one <br> |
| 407 |
1 ColumnName 1 0 two <br> |
| 408 |
2 Integer 0 0 <br> |
| 409 |
3 OpenRead 0 3 examp <br> |
| 410 |
4 VerifyCookie 0 81 <br> |
| 411 |
5 Rewind 0 10 <br> |
| 412 |
6 Column 0 0 <br> |
| 413 |
7 Column 0 1 <br> |
| 414 |
8 Callback 2 0 <br> |
| 415 |
9 Next 0 6 <br> |
| 416 |
10 Close 0 0 <br> |
| 417 |
11 Halt 0 0</tt></blockquote> |
| 418 |
<p>Before we begin looking at this problem, let's briefly review |
| 419 |
how queries work in SQLite so that we will know what we are trying |
| 420 |
to accomplish. For each row in the result of a query, |
| 421 |
SQLite will invoke a callback function with the following |
| 422 |
prototype:</p> |
| 423 |
|
| 424 |
<blockquote><pre> |
| 425 |
int Callback(void *pUserData, int nColumn, char *azData[], char *azColumnName[]); |
| 426 |
</pre></blockquote> |
| 427 |
|
| 428 |
<p>The SQLite library supplies the VDBE with a pointer to the callback function |
| 429 |
and the <b>pUserData</b> pointer. (Both the callback and the user data were |
| 430 |
originally passed in as arguments to the <b>sqlite_exec()</b> API function.) |
| 431 |
The job of the VDBE is to |
| 432 |
come up with values for <b>nColumn</b>, <b>azData[]</b>, |
| 433 |
and <b>azColumnName[]</b>. |
| 434 |
<b>nColumn</b> is the number of columns in the results, of course. |
| 435 |
<b>azColumnName[]</b> is an array of strings where each string is the name |
| 436 |
of one of the result columns. <b>azData[]</b> is an array of strings holding |
| 437 |
the actual data.</p> |
| 438 |
<blockquote><tt>0 ColumnName 0 0 one <br> |
| 439 |
1 ColumnName 1 0 two</tt></blockquote> |
| 440 |
<p>The first two instructions in the VDBE program for our query are |
| 441 |
concerned with setting up values for <b>azColumn</b>. |
| 442 |
The <a href="opcode.html#ColumnName">ColumnName</a> instructions tell |
| 443 |
the VDBE what values to fill in for each element of the <b>azColumnName[]</b> |
| 444 |
array. Every query will begin with one ColumnName instruction for each |
| 445 |
column in the result, and there will be a matching Column instruction for |
| 446 |
each one later in the query. |
| 447 |
</p> |
| 448 |
<blockquote><tt>2 Integer 0 0 <br> |
| 449 |
3 OpenRead 0 3 examp <br> |
| 450 |
4 VerifyCookie 0 81</tt></blockquote> |
| 451 |
<p>Instructions 2 and 3 open a read cursor on the database table that is |
| 452 |
to be queried. This works the same as the OpenWrite instruction in the |
| 453 |
INSERT example except that the cursor is opened for reading this time |
| 454 |
instead of for writing. Instruction 4 verifies the database schema as |
| 455 |
in the INSERT example.</p> |
| 456 |
<blockquote><tt>5 Rewind 0 10</tt></blockquote> |
| 457 |
<p> The <a href="opcode.html#Rewind">Rewind</a> instruction initializes |
| 458 |
a loop that iterates over the "examp" table. It rewinds the cursor P1 |
| 459 |
to the first entry in its table. This is required by the Column and |
| 460 |
Next instructions, which use the cursor to iterate through the table. |
| 461 |
If the table is empty, then jump to P2 (10), which is the instruction just |
| 462 |
past the loop. If the table is not empty, fall through to the following |
| 463 |
instruction at 6, which is the beginning of the loop body.</p> |
| 464 |
<blockquote><tt>6 Column 0 0 <br> |
| 465 |
7 Column 0 1 <br> |
| 466 |
8 Callback 2 0</tt></blockquote> |
| 467 |
<p> The instructions 6 through 8 form the body of the loop that will |
| 468 |
execute once for each record in the database file. |
| 469 |
|
| 470 |
The <a href="opcode.html#Column">Column</a> instructions at addresses 6 |
| 471 |
and 7 each take the P2-th column from the P1-th cursor and push it onto |
| 472 |
the stack. In this example, the first Column instruction is pushing the |
| 473 |
value for the column "one" onto the stack and the second Column |
| 474 |
instruction is pushing the value for column "two". |
| 475 |
|
| 476 |
The <a href="opcode.html#Callback">Callback</a> instruction at address 8 |
| 477 |
invokes the callback() function. The P1 operand to Callback becomes the |
| 478 |
value for <b>nColumn</b>. The Callback instruction pops P1 values from |
| 479 |
the stack and uses them to fill the <b>azData[]</b> array.</p> |
| 480 |
<blockquote><tt>9 Next 0 6</tt></blockquote> |
| 481 |
<p>The instruction at address 9 implements the branching part of the |
| 482 |
loop. Together with the Rewind at address 5 it forms the loop logic. |
| 483 |
This is a key concept that you should pay close attention to. |
| 484 |
The <a href="opcode.html#Next">Next</a> instruction advances the cursor |
| 485 |
P1 to the next record. If the cursor advance was successful, then jump |
| 486 |
immediately to P2 (6, the beginning of the loop body). If the cursor |
| 487 |
was at the end, then fall through to the following instruction, which |
| 488 |
ends the loop.</p> |
| 489 |
<blockquote><tt>10 Close 0 0 <br> |
| 490 |
11 Halt 0 0</tt></blockquote> |
| 491 |
<p>The Close instruction at the end of the program closes the |
| 492 |
cursor that points into the table "examp". It is not really necessary |
| 493 |
to call Close here since all cursors will be automatically closed |
| 494 |
by the VDBE when the program halts. But we needed an instruction |
| 495 |
for the Rewind to jump to so we might as well go ahead and have that |
| 496 |
instruction do something useful. |
| 497 |
The Halt instruction ends the VDBE program.</p> |
| 498 |
|
| 499 |
<p>Note that the program for this SELECT query didn't contain the |
| 500 |
Transaction and Commit instructions used in the INSERT example. Because |
| 501 |
the SELECT is a read operation that doesn't alter the database, it |
| 502 |
doesn't require a transaction.</p> |
| 503 |
|
| 504 |
<a name="query2"></a> |
| 505 |
<h2>A Slightly More Complex Query</h2> |
| 506 |
|
| 507 |
<p>The key points of the previous example were the use of the Callback |
| 508 |
instruction to invoke the callback function, and the use of the Next |
| 509 |
instruction to implement a loop over all records of the database file. |
| 510 |
This example attempts to drive home those ideas by demonstrating a |
| 511 |
slightly more complex query that involves more columns of |
| 512 |
output, some of which are computed values, and a WHERE clause that |
| 513 |
limits which records actually make it to the callback function. |
| 514 |
Consider this query:</p> |
| 515 |
|
| 516 |
<blockquote><pre> |
| 517 |
SELECT one, two, one || two AS 'both' |
| 518 |
FROM examp |
| 519 |
WHERE one LIKE 'H%' |
| 520 |
</pre></blockquote> |
| 521 |
|
| 522 |
<p>This query is perhaps a bit contrived, but it does serve to |
| 523 |
illustrate our points. The result will have three columns with |
| 524 |
names "one", "two", and "both". The first two columns are direct |
| 525 |
copies of the two columns in the table and the third result |
| 526 |
column is a string formed by concatenating the first and |
| 527 |
second columns of the table. |
| 528 |
Finally, the |
| 529 |
WHERE clause says that we will only choose rows for the |
| 530 |
results where the "one" column begins with an "H". |
| 531 |
Here is what the VDBE program looks like for this query:</p> |
| 532 |
<blockquote><tt>addr opcode p1 p2 p3 <br> |
| 533 |
---- ------------ ----- ----- -----------------------------------<br> |
| 534 |
0 ColumnName 0 0 one<br> |
| 535 |
1 ColumnName 1 0 two<br> |
| 536 |
2 ColumnName 2 0 both<br> |
| 537 |
3 Integer 0 0<br> |
| 538 |
4 OpenRead 0 3 examp<br> |
| 539 |
5 VerifyCookie 0 81<br> |
| 540 |
6 Rewind 0 18<br> |
| 541 |
7 String 0 0 H% <br> |
| 542 |
8 Column 0 0<br> |
| 543 |
9 Function 2 0 ptr(0x7f1ac0)<br> |
| 544 |
10 IfNot 1 17<br> |
| 545 |
11 Column 0 0<br> |
| 546 |
12 Column 0 1<br> |
| 547 |
13 Column 0 0<br> |
| 548 |
14 Column 0 1<br> |
| 549 |
15 Concat 2 0<br> |
| 550 |
16 Callback 3 0<br> |
| 551 |
17 Next 0 7<br> |
| 552 |
18 Close 0 0<br> |
| 553 |
19 Halt 0 0</tt></blockquote> |
| 554 |
<p>Except for the WHERE clause, the structure of the program for |
| 555 |
this example is very much like the prior example, just with an |
| 556 |
extra column. There are now 3 columns, instead of 2 as before, |
| 557 |
and there are three ColumnName instructions. |
| 558 |
A cursor is opened using the OpenRead instruction, just like in the |
| 559 |
prior example. The Rewind instruction at address 6 and the |
| 560 |
Next at address 17 form a loop over all records of the table. |
| 561 |
The Close instruction at the end is there to give the |
| 562 |
Rewind instruction something to jump to when it is done. All of |
| 563 |
this is just like in the first query demonstration.</p> |
| 564 |
|
| 565 |
<p>The Callback instruction in this example has to generate |
| 566 |
data for three result columns instead of two, but is otherwise |
| 567 |
the same as in the first query. When the Callback instruction |
| 568 |
is invoked, the left-most column of the result should be |
| 569 |
the lowest in the stack and the right-most result column should |
| 570 |
be the top of the stack. We can see the stack being set up |
| 571 |
this way at addresses 11 through 15. The Column instructions at |
| 572 |
11 and 12 push the values for the first two columns in the result. |
| 573 |
The two Column instructions at 13 and 14 pull in the values needed |
| 574 |
to compute the third result column and the Concat instruction at |
| 575 |
15 joins them together into a single entry on the stack.</p> |
| 576 |
|
| 577 |
<p>The only thing that is really new about the current example |
| 578 |
is the WHERE clause which is implemented by instructions at |
| 579 |
addresses 7 through 10. Instructions at address 7 and 8 push |
| 580 |
onto the stack the value of the "one" column from the table |
| 581 |
and the literal string "H%". |
| 582 |
The <a href="opcode.html#Function">Function</a> instruction at address 9 |
| 583 |
pops these two values from the stack and pushes the result of the LIKE() |
| 584 |
function back onto the stack. |
| 585 |
The <a href="opcode.html#IfNot">IfNot</a> instruction pops the top stack |
| 586 |
value and causes an immediate jump forward to the Next instruction if the |
| 587 |
top value was false (<em>not</em> not like the literal string "H%"). |
| 588 |
Taking this jump effectively skips the callback, which is the whole point |
| 589 |
of the WHERE clause. If the result |
| 590 |
of the comparison is true, the jump is not taken and control |
| 591 |
falls through to the Callback instruction below.</p> |
| 592 |
|
| 593 |
<p>Notice how the LIKE operator is implemented. It is a user-defined |
| 594 |
function in SQLite, so the address of its function definition is |
| 595 |
specified in P3. The operand P1 is the number of function arguments for |
| 596 |
it to take from the stack. In this case the LIKE() function takes 2 |
| 597 |
arguments. The arguments are taken off the stack in reverse order |
| 598 |
(right-to-left), so the pattern to match is the top stack element, and |
| 599 |
the next element is the data to compare. The return value is pushed |
| 600 |
onto the stack.</p> |
| 601 |
|
| 602 |
|
| 603 |
<a name="pattern1"></a> |
| 604 |
<h2>A Template For SELECT Programs</h2> |
| 605 |
|
| 606 |
<p>The first two query examples illustrate a kind of template that |
| 607 |
every SELECT program will follow. Basically, we have:</p> |
| 608 |
|
| 609 |
<p> |
| 610 |
<ol> |
| 611 |
<li>Initialize the <b>azColumnName[]</b> array for the callback.</li> |
| 612 |
<li>Open a cursor into the table to be queried.</li> |
| 613 |
<li>For each record in the table, do: |
| 614 |
<ol type="a"> |
| 615 |
<li>If the WHERE clause evaluates to FALSE, then skip the steps that |
| 616 |
follow and continue to the next record.</li> |
| 617 |
<li>Compute all columns for the current row of the result.</li> |
| 618 |
<li>Invoke the callback function for the current row of the result.</li> |
| 619 |
</ol> |
| 620 |
<li>Close the cursor.</li> |
| 621 |
</ol> |
| 622 |
</p> |
| 623 |
|
| 624 |
<p>This template will be expanded considerably as we consider |
| 625 |
additional complications such as joins, compound selects, using |
| 626 |
indices to speed the search, sorting, and aggregate functions |
| 627 |
with and without GROUP BY and HAVING clauses. |
| 628 |
But the same basic ideas will continue to apply.</p> |
| 629 |
|
| 630 |
<h2>UPDATE And DELETE Statements</h2> |
| 631 |
|
| 632 |
<p>The UPDATE and DELETE statements are coded using a template |
| 633 |
that is very similar to the SELECT statement template. The main |
| 634 |
difference, of course, is that the end action is to modify the |
| 635 |
database rather than invoke a callback function. Because it modifies |
| 636 |
the database it will also use transactions. Let's begin |
| 637 |
by looking at a DELETE statement:</p> |
| 638 |
|
| 639 |
<blockquote><pre> |
| 640 |
DELETE FROM examp WHERE two<50; |
| 641 |
</pre></blockquote> |
| 642 |
|
| 643 |
<p>This DELETE statement will remove every record from the "examp" |
| 644 |
table where the "two" column is less than 50. |
| 645 |
The code generated to do this is as follows:</p> |
| 646 |
<blockquote><tt>addr opcode p1 p2 p3 <br> |
| 647 |
---- ------------ ----- ----- -----------------------------------<br> |
| 648 |
0 Transaction 1 0<br> |
| 649 |
1 Transaction 0 0<br> |
| 650 |
2 VerifyCookie 0 178<br> |
| 651 |
3 Integer 0 0<br> |
| 652 |
4 OpenRead 0 3 examp<br> |
| 653 |
5 Rewind 0 12<br> |
| 654 |
6 Column 0 1<br> |
| 655 |
7 Integer 50 0 50<br> |
| 656 |
8 Ge 1 11<br> |
| 657 |
9 Recno 0 0<br> |
| 658 |
10 ListWrite 0 0<br> |
| 659 |
11 Next 0 6<br> |
| 660 |
12 Close 0 0<br> |
| 661 |
13 ListRewind 0 0<br> |
| 662 |
14 Integer 0 0<br> |
| 663 |
15 OpenWrite 0 3<br> |
| 664 |
16 ListRead 0 20<br> |
| 665 |
17 NotExists 0 19<br> |
| 666 |
18 Delete 0 1<br> |
| 667 |
19 Goto 0 16<br> |
| 668 |
20 ListReset 0 0<br> |
| 669 |
21 Close 0 0<br> |
| 670 |
22 Commit 0 0<br> |
| 671 |
23 Halt 0 0</tt></blockquote> |
| 672 |
<p>Here is what the program must do. First it has to locate all of |
| 673 |
the records in the table "examp" that are to be deleted. This is |
| 674 |
done using a loop very much like the loop used in the SELECT examples |
| 675 |
above. Once all records have been located, then we can go back through |
| 676 |
and delete them one by one. Note that we cannot delete each record |
| 677 |
as soon as we find it. We have to locate all records first, then |
| 678 |
go back and delete them. This is because the SQLite database |
| 679 |
backend might change the scan order after a delete operation. |
| 680 |
And if the scan |
| 681 |
order changes in the middle of the scan, some records might be |
| 682 |
visited more than once and other records might not be visited at all.</p> |
| 683 |
|
| 684 |
<p>So the implementation of DELETE is really in two loops. The first loop |
| 685 |
(instructions 5 through 11) locates the records that are to be deleted |
| 686 |
and saves their keys onto a temporary list, and the second loop |
| 687 |
(instructions 16 through 19) uses the key list to delete the records one |
| 688 |
by one. </p> |
| 689 |
<blockquote><tt>0 Transaction 1 0<br> |
| 690 |
1 Transaction 0 0<br> |
| 691 |
2 VerifyCookie 0 178<br> |
| 692 |
3 Integer 0 0<br> |
| 693 |
4 OpenRead 0 3 examp</tt></blockquote> |
| 694 |
<p>Instructions 0 though 4 are as in the INSERT example. They start |
| 695 |
transactions for the main and temporary databases, verify the database |
| 696 |
schema for the main database, and open a read cursor on the table |
| 697 |
"examp". Notice that the cursor is opened for reading, not writing. At |
| 698 |
this stage of the program we are only going to be scanning the table, |
| 699 |
not changing it. We will reopen the same table for writing later, at |
| 700 |
instruction 15.</p> |
| 701 |
<blockquote><tt>5 Rewind 0 12</tt></blockquote> |
| 702 |
<p>As in the SELECT example, the <a href="opcode.html#Rewind">Rewind</a> |
| 703 |
instruction rewinds the cursor to the beginning of the table, readying |
| 704 |
it for use in the loop body.</p> |
| 705 |
<blockquote><tt>6 Column 0 1<br> |
| 706 |
7 Integer 50 0 50<br> |
| 707 |
8 Ge 1 11</tt></blockquote> |
| 708 |
<p>The WHERE clause is implemented by instructions 6 through 8. |
| 709 |
The job of the where clause is to skip the ListWrite if the WHERE |
| 710 |
condition is false. To this end, it jumps ahead to the Next instruction |
| 711 |
if the "two" column (extracted by the Column instruction) is |
| 712 |
greater than or equal to 50.</p> |
| 713 |
|
| 714 |
<p>As before, the Column instruction uses cursor P1 and pushes the data |
| 715 |
record in column P2 (1, column "two") onto the stack. The Integer |
| 716 |
instruction pushes the value 50 onto the top of the stack. After these |
| 717 |
two instructions the stack looks like:</p> |
| 718 |
<blockquote><table border=2><tr><td align=left>(integer) 50</td></tr><tr><td align=left>(record) current record for column "two" </td></tr></table></blockquote> |
| 719 |
<p>The <a href="opcode.html#Ge">Ge</a> operator compares the top two |
| 720 |
elements on the stack, pops them, and then branches based on the result |
| 721 |
of the comparison. If the second element is >= the top element, then |
| 722 |
jump to address P2 (the Next instruction at the end of the loop). |
| 723 |
Because P1 is true, if either operand is NULL (and thus the result is |
| 724 |
NULL) then take the jump. If we don't jump, just advance to the next |
| 725 |
instruction.</p> |
| 726 |
<blockquote><tt>9 Recno 0 0<br> |
| 727 |
10 ListWrite 0 0</tt></blockquote> |
| 728 |
<p>The <a href="opcode.html#Recno">Recno</a> instruction pushes onto the |
| 729 |
stack an integer which is the first 4 bytes of the key to the current |
| 730 |
entry in a sequential scan of the table pointed to by cursor P1. |
| 731 |
The <a href="opcode.html#ListWrite">ListWrite</a> instruction writes the |
| 732 |
integer on the top of the stack into a temporary storage list and pops |
| 733 |
the top element. This is the important work of this loop, to store the |
| 734 |
keys of the records to be deleted so we can delete them in the second |
| 735 |
loop. After this ListWrite instruction the stack is empty again.</p> |
| 736 |
<blockquote><tt>11 Next 0 6<br> |
| 737 |
12 Close 0 0</tt></blockquote> |
| 738 |
<p> The Next instruction increments the cursor to point to the next |
| 739 |
element in the table pointed to by cursor P0, and if it was successful |
| 740 |
branches to P2 (6, the beginning of the loop body). The Close |
| 741 |
instruction closes cursor P1. It doesn't affect the temporary storage |
| 742 |
list because it isn't associated with cursor P1; it is instead a global |
| 743 |
working list (which can be saved with ListPush).</p> |
| 744 |
<blockquote><tt>13 ListRewind 0 0</tt></blockquote> |
| 745 |
<p> The <a href="opcode.html#ListRewind">ListRewind</a> instruction |
| 746 |
rewinds the temporary storage list to the beginning. This prepares it |
| 747 |
for use in the second loop.</p> |
| 748 |
<blockquote><tt>14 Integer 0 0<br> |
| 749 |
15 OpenWrite 0 3</tt></blockquote> |
| 750 |
<p> As in the INSERT example, we push the database number P1 (0, the main |
| 751 |
database) onto the stack and use OpenWrite to open the cursor P1 on table |
| 752 |
P2 (base page 3, "examp") for modification.</p> |
| 753 |
<blockquote><tt>16 ListRead 0 20<br> |
| 754 |
17 NotExists 0 19<br> |
| 755 |
18 Delete 0 1<br> |
| 756 |
19 Goto 0 16</tt></blockquote> |
| 757 |
<p>This loop does the actual deleting. It is organized differently from |
| 758 |
the one in the UPDATE example. The ListRead instruction plays the role |
| 759 |
that the Next did in the INSERT loop, but because it jumps to P2 on |
| 760 |
failure, and Next jumps on success, we put it at the start of the loop |
| 761 |
instead of the end. This means that we have to put a Goto at the end of |
| 762 |
the loop to jump back to the loop test at the beginning. So this |
| 763 |
loop has the form of a C while(){...} loop, while the loop in the INSERT |
| 764 |
example had the form of a do{...}while() loop. The Delete instruction |
| 765 |
fills the role that the callback function did in the preceding examples. |
| 766 |
</p> |
| 767 |
<p>The <a href="opcode.html#ListRead">ListRead</a> instruction reads an |
| 768 |
element from the temporary storage list and pushes it onto the stack. |
| 769 |
If this was successful, it continues to the next instruction. If this |
| 770 |
fails because the list is empty, it branches to P2, which is the |
| 771 |
instruction just after the loop. Afterwards the stack looks like:</p> |
| 772 |
<blockquote><table border=2><tr><td align=left>(integer) key for current record</td></tr></table></blockquote> |
| 773 |
<p>Notice the similarity between the ListRead and Next instructions. |
| 774 |
Both operations work according to this rule: |
| 775 |
</p> |
| 776 |
<blockquote> |
| 777 |
Push the next "thing" onto the stack and fall through OR jump to P2, |
| 778 |
depending on whether or not there is a next "thing" to push. |
| 779 |
</blockquote> |
| 780 |
<p>One difference between Next and ListRead is their idea of a "thing". |
| 781 |
The "things" for the Next instruction are records in a database file. |
| 782 |
"Things" for ListRead are integer keys in a list. Another difference |
| 783 |
is whether to jump or fall through if there is no next "thing". In this |
| 784 |
case, Next falls through, and ListRead jumps. Later on, we will see |
| 785 |
other looping instructions (NextIdx and SortNext) that operate using the |
| 786 |
same principle.</p> |
| 787 |
|
| 788 |
<p>The <a href="opcode.html#NotExists">NotExists</a> instruction pops |
| 789 |
the top stack element and uses it as an integer key. If a record with |
| 790 |
that key does not exist in table P1, then jump to P2. If a record does |
| 791 |
exist, then fall through to the next instruction. In this case P2 takes |
| 792 |
us to the Goto at the end of the loop, which jumps back to the ListRead |
| 793 |
at the beginning. This could have been coded to have P2 be 16, the |
| 794 |
ListRead at the start of the loop, but the SQLite parser which generated |
| 795 |
this code didn't make that optimization.</p> |
| 796 |
<p>The <a href="opcode.html#Delete">Delete</a> does the work of this |
| 797 |
loop; it pops an integer key off the stack (placed there by the |
| 798 |
preceding ListRead) and deletes the record of cursor P1 that has that key. |
| 799 |
Because P2 is true, the row change counter is incremented.</p> |
| 800 |
<p>The <a href="opcode.html#Goto">Goto</a> jumps back to the beginning |
| 801 |
of the loop. This is the end of the loop.</p> |
| 802 |
<blockquote><tt>20 ListReset 0 0<br> |
| 803 |
21 Close 0 0<br> |
| 804 |
22 Commit 0 0<br> |
| 805 |
23 Halt 0 0</tt></blockquote> |
| 806 |
<p>This block of instruction cleans up the VDBE program. Three of these |
| 807 |
instructions aren't really required, but are generated by the SQLite |
| 808 |
parser from its code templates, which are designed to handle more |
| 809 |
complicated cases.</p> |
| 810 |
<p>The <a href="opcode.html#ListReset">ListReset</a> instruction empties |
| 811 |
the temporary storage list. This list is emptied automatically when the |
| 812 |
VDBE program terminates, so it isn't necessary in this case. The Close |
| 813 |
instruction closes the cursor P1. Again, this is done by the VDBE |
| 814 |
engine when it is finished running this program. The Commit ends the |
| 815 |
current transaction successfully, and causes all changes that occurred |
| 816 |
in this transaction to be saved to the database. The final Halt is also |
| 817 |
unnecessary, since it is added to every VDBE program when it is |
| 818 |
prepared to run.</p> |
| 819 |
|
| 820 |
|
| 821 |
<p>UPDATE statements work very much like DELETE statements except |
| 822 |
that instead of deleting the record they replace it with a new one. |
| 823 |
Consider this example: |
| 824 |
</p> |
| 825 |
|
| 826 |
<blockquote><pre> |
| 827 |
UPDATE examp SET one= '(' || one || ')' WHERE two < 50; |
| 828 |
</pre></blockquote> |
| 829 |
|
| 830 |
<p>Instead of deleting records where the "two" column is less than |
| 831 |
50, this statement just puts the "one" column in parentheses |
| 832 |
The VDBE program to implement this statement follows:</p> |
| 833 |
<blockquote><tt>addr opcode p1 p2 p3 <br> |
| 834 |
---- ------------ ----- ----- -----------------------------------<br> |
| 835 |
0 Transaction 1 0 <br> |
| 836 |
1 Transaction 0 0 <br> |
| 837 |
2 VerifyCookie 0 178 <br> |
| 838 |
3 Integer 0 0 <br> |
| 839 |
4 OpenRead 0 3 examp <br> |
| 840 |
5 Rewind 0 12 <br> |
| 841 |
6 Column 0 1 <br> |
| 842 |
7 Integer 50 0 50 <br> |
| 843 |
8 Ge 1 11 <br> |
| 844 |
9 Recno 0 0 <br> |
| 845 |
10 ListWrite 0 0 <br> |
| 846 |
11 Next 0 6 <br> |
| 847 |
12 Close 0 0 <br> |
| 848 |
13 Integer 0 0 <br> |
| 849 |
14 OpenWrite 0 3 <br> |
| 850 |
15 ListRewind 0 0 <br> |
| 851 |
16 ListRead 0 28 <br> |
| 852 |
17 Dup 0 0 <br> |
| 853 |
18 NotExists 0 16 <br> |
| 854 |
19 String 0 0 ( <br> |
| 855 |
20 Column 0 0 <br> |
| 856 |
21 Concat 2 0 <br> |
| 857 |
22 String 0 0 ) <br> |
| 858 |
23 Concat 2 0 <br> |
| 859 |
24 Column 0 1 <br> |
| 860 |
25 MakeRecord 2 0 <br> |
| 861 |
26 PutIntKey 0 1 <br> |
| 862 |
27 Goto 0 16 <br> |
| 863 |
28 ListReset 0 0 <br> |
| 864 |
29 Close 0 0 <br> |
| 865 |
30 Commit 0 0 <br> |
| 866 |
31 Halt 0 0</tt></blockquote> |
| 867 |
<p>This program is essentially the same as the DELETE program except |
| 868 |
that the body of the second loop has been replaced by a sequence of |
| 869 |
instructions (at addresses 17 through 26) that update the record rather |
| 870 |
than delete it. Most of this instruction sequence should already be |
| 871 |
familiar to you, but there are a couple of minor twists so we will go |
| 872 |
over it briefly. Also note that the order of some of the instructions |
| 873 |
before and after the 2nd loop has changed. This is just the way the |
| 874 |
SQLite parser chose to output the code using a different template.</p> |
| 875 |
|
| 876 |
<p>As we enter the interior of the second loop (at instruction 17) |
| 877 |
the stack contains a single integer which is the key of the |
| 878 |
record we want to modify. We are going to need to use this |
| 879 |
key twice: once to fetch the old value of the record and |
| 880 |
a second time to write back the revised record. So the first instruction |
| 881 |
is a Dup to make a duplicate of the key on the top of the stack. The |
| 882 |
Dup instruction will duplicate any element of the stack, not just the top |
| 883 |
element. You specify which element to duplication using the |
| 884 |
P1 operand. When P1 is 0, the top of the stack is duplicated. |
| 885 |
When P1 is 1, the next element down on the stack duplication. |
| 886 |
And so forth.</p> |
| 887 |
|
| 888 |
<p>After duplicating the key, the next instruction, NotExists, |
| 889 |
pops the stack once and uses the value popped as a key to |
| 890 |
check the existence of a record in the database file. If there is no record |
| 891 |
for this key, it jumps back to the ListRead to get another key.</p> |
| 892 |
|
| 893 |
<p>Instructions 19 through 25 construct a new database record |
| 894 |
that will be used to replace the existing record. This is |
| 895 |
the same kind of code that we saw |
| 896 |
in the description of INSERT and will not be described further. |
| 897 |
After instruction 25 executes, the stack looks like this:</p> |
| 898 |
<blockquote><table border=2><tr><td align=left>(record) new data record</td></tr><tr><td align=left>(integer) key</td></tr></table></blockquote> |
| 899 |
<p>The PutIntKey instruction (also described |
| 900 |
during the discussion about INSERT) writes an entry into the |
| 901 |
database file whose data is the top of the stack and whose key |
| 902 |
is the next on the stack, and then pops the stack twice. The |
| 903 |
PutIntKey instruction will overwrite the data of an existing record |
| 904 |
with the same key, which is what we want here. Overwriting was not |
| 905 |
an issue with INSERT because with INSERT the key was generated |
| 906 |
by the NewRecno instruction which is guaranteed to provide a key |
| 907 |
that has not been used before.</p> |
| 908 |
|
| 909 |
<h2>CREATE and DROP</h2> |
| 910 |
|
| 911 |
<p>Using CREATE or DROP to create or destroy a table or index is |
| 912 |
really the same as doing an INSERT or DELETE from the special |
| 913 |
"sqlite_master" table, at least from the point of view of the VDBE. |
| 914 |
The sqlite_master table is a special table that is automatically |
| 915 |
created for every SQLite database. It looks like this:</p> |
| 916 |
|
| 917 |
<blockquote><pre> |
| 918 |
CREATE TABLE sqlite_master ( |
| 919 |
type TEXT, -- either "table" or "index" |
| 920 |
name TEXT, -- name of this table or index |
| 921 |
tbl_name TEXT, -- for indices: name of associated table |
| 922 |
sql TEXT -- SQL text of the original CREATE statement |
| 923 |
) |
| 924 |
</pre></blockquote> |
| 925 |
|
| 926 |
<p>Every table (except the "sqlite_master" table itself) |
| 927 |
and every named index in an SQLite database has an entry |
| 928 |
in the sqlite_master table. You can query this table using |
| 929 |
a SELECT statement just like any other table. But you are |
| 930 |
not allowed to directly change the table using UPDATE, INSERT, |
| 931 |
or DELETE. Changes to sqlite_master have to occur using |
| 932 |
the CREATE and DROP commands because SQLite also has to update |
| 933 |
some of its internal data structures when tables and indices |
| 934 |
are added or destroyed.</p> |
| 935 |
|
| 936 |
<p>But from the point of view of the VDBE, a CREATE works |
| 937 |
pretty much like an INSERT and a DROP works like a DELETE. |
| 938 |
When the SQLite library opens to an existing database, |
| 939 |
the first thing it does is a SELECT to read the "sql" |
| 940 |
columns from all entries of the sqlite_master table. |
| 941 |
The "sql" column contains the complete SQL text of the |
| 942 |
CREATE statement that originally generated the index or |
| 943 |
table. This text is fed back into the SQLite parser |
| 944 |
and used to reconstruct the |
| 945 |
internal data structures describing the index or table.</p> |
| 946 |
|
| 947 |
<h2>Using Indexes To Speed Searching</h2> |
| 948 |
|
| 949 |
<p>In the example queries above, every row of the table being |
| 950 |
queried must be loaded off of the disk and examined, even if only |
| 951 |
a small percentage of the rows end up in the result. This can |
| 952 |
take a long time on a big table. To speed things up, SQLite |
| 953 |
can use an index.</p> |
| 954 |
|
| 955 |
<p>An SQLite file associates a key with some data. For an SQLite |
| 956 |
table, the database file is set up so that the key is an integer |
| 957 |
and the data is the information for one row of the table. |
| 958 |
Indices in SQLite reverse this arrangement. The index key |
| 959 |
is (some of) the information being stored and the index data |
| 960 |
is an integer. |
| 961 |
To access a table row that has some particular |
| 962 |
content, we first look up the content in the index table to find |
| 963 |
its integer index, then we use that integer to look up the |
| 964 |
complete record in the table.</p> |
| 965 |
|
| 966 |
<p>Note that SQLite uses b-trees, which are a sorted data structure, |
| 967 |
so indices can be used when the WHERE clause of the SELECT statement |
| 968 |
contains tests for equality or inequality. Queries like the following |
| 969 |
can use an index if it is available:</p> |
| 970 |
|
| 971 |
<blockquote><pre> |
| 972 |
SELECT * FROM examp WHERE two==50; |
| 973 |
SELECT * FROM examp WHERE two<50; |
| 974 |
SELECT * FROM examp WHERE two IN (50, 100); |
| 975 |
</pre></blockquote> |
| 976 |
|
| 977 |
<p>If there exists an index that maps the "two" column of the "examp" |
| 978 |
table into integers, then SQLite will use that index to find the integer |
| 979 |
keys of all rows in examp that have a value of 50 for column two, or |
| 980 |
all rows that are less than 50, etc. |
| 981 |
But the following queries cannot use the index:</p> |
| 982 |
|
| 983 |
<blockquote><pre> |
| 984 |
SELECT * FROM examp WHERE two%50 == 10; |
| 985 |
SELECT * FROM examp WHERE two&127 == 3; |
| 986 |
</pre></blockquote> |
| 987 |
|
| 988 |
<p>Note that the SQLite parser will not always generate code to use an |
| 989 |
index, even if it is possible to do so. The following queries will not |
| 990 |
currently use the index:</p> |
| 991 |
|
| 992 |
<blockquote><pre> |
| 993 |
SELECT * FROM examp WHERE two+10 == 50; |
| 994 |
SELECT * FROM examp WHERE two==50 OR two==100; |
| 995 |
</pre></blockquote> |
| 996 |
|
| 997 |
<p>To understand better how indices work, lets first look at how |
| 998 |
they are created. Let's go ahead and put an index on the two |
| 999 |
column of the examp table. We have:</p> |
| 1000 |
|
| 1001 |
<blockquote><pre> |
| 1002 |
CREATE INDEX examp_idx1 ON examp(two); |
| 1003 |
</pre></blockquote> |
| 1004 |
|
| 1005 |
<p>The VDBE code generated by the above statement looks like the |
| 1006 |
following:</p> |
| 1007 |
<blockquote><tt>addr opcode p1 p2 p3 <br> |
| 1008 |
---- ------------ ----- ----- -----------------------------------<br> |
| 1009 |
0 Transaction 1 0 <br> |
| 1010 |
1 Transaction 0 0 <br> |
| 1011 |
2 VerifyCookie 0 178 <br> |
| 1012 |
3 Integer 0 0 <br> |
| 1013 |
4 OpenWrite 0 2 <br> |
| 1014 |
5 NewRecno 0 0 <br> |
| 1015 |
6 String 0 0 index <br> |
| 1016 |
7 String 0 0 examp_idx1 <br> |
| 1017 |
8 String 0 0 examp <br> |
| 1018 |
9 CreateIndex 0 0 ptr(0x791380) <br> |
| 1019 |
10 Dup 0 0 <br> |
| 1020 |
11 Integer 0 0 <br> |
| 1021 |
12 OpenWrite 1 0 <br> |
| 1022 |
13 String 0 0 CREATE INDEX examp_idx1 ON examp(tw<br> |
| 1023 |
14 MakeRecord 5 0 <br> |
| 1024 |
15 PutIntKey 0 0 <br> |
| 1025 |
16 Integer 0 0 <br> |
| 1026 |
17 OpenRead 2 3 examp <br> |
| 1027 |
18 Rewind 2 24 <br> |
| 1028 |
19 Recno 2 0 <br> |
| 1029 |
20 Column 2 1 <br> |
| 1030 |
21 MakeIdxKey 1 0 n <br> |
| 1031 |
22 IdxPut 1 0 indexed columns are not unique <br> |
| 1032 |
23 Next 2 19 <br> |
| 1033 |
24 Close 2 0 <br> |
| 1034 |
25 Close 1 0 <br> |
| 1035 |
26 Integer 333 0 <br> |
| 1036 |
27 SetCookie 0 0 <br> |
| 1037 |
28 Close 0 0 <br> |
| 1038 |
29 Commit 0 0 <br> |
| 1039 |
30 Halt 0 0</tt></blockquote> |
| 1040 |
<p>Remember that every table (except sqlite_master) and every named |
| 1041 |
index has an entry in the sqlite_master table. Since we are creating |
| 1042 |
a new index, we have to add a new entry to sqlite_master. This is |
| 1043 |
handled by instructions 3 through 15. Adding an entry to sqlite_master |
| 1044 |
works just like any other INSERT statement so we will not say any more |
| 1045 |
about it here. In this example, we want to focus on populating the |
| 1046 |
new index with valid data, which happens on instructions 16 through |
| 1047 |
23.</p> |
| 1048 |
<blockquote><tt>16 Integer 0 0 <br> |
| 1049 |
17 OpenRead 2 3 examp</tt></blockquote> |
| 1050 |
<p>The first thing that happens is that we open the table being |
| 1051 |
indexed for reading. In order to construct an index for a table, |
| 1052 |
we have to know what is in that table. The index has already been |
| 1053 |
opened for writing using cursor 0 by instructions 3 and 4.</p> |
| 1054 |
<blockquote><tt>18 Rewind 2 24 <br> |
| 1055 |
19 Recno 2 0 <br> |
| 1056 |
20 Column 2 1 <br> |
| 1057 |
21 MakeIdxKey 1 0 n <br> |
| 1058 |
22 IdxPut 1 0 indexed columns are not unique <br> |
| 1059 |
23 Next 2 19</tt></blockquote> |
| 1060 |
<p>Instructions 18 through 23 implement a loop over every row of the |
| 1061 |
table being indexed. For each table row, we first extract the integer |
| 1062 |
key for that row using Recno in instruction 19, then get the value of |
| 1063 |
the "two" column using Column in instruction 20. |
| 1064 |
The <a href="opcode.html#MakeIdxKey">MakeIdxKey</a> instruction at 21 |
| 1065 |
converts data from the "two" column (which is on the top of the stack) |
| 1066 |
into a valid index key. For an index on a single column, this is |
| 1067 |
basically a no-op. But if the P1 operand to MakeIdxKey had been |
| 1068 |
greater than one multiple entries would have been popped from the stack |
| 1069 |
and converted into a single index key. |
| 1070 |
The <a href="opcode.html#IdxPut">IdxPut</a> instruction at 22 is what |
| 1071 |
actually creates the index entry. IdxPut pops two elements from the |
| 1072 |
stack. The top of the stack is used as a key to fetch an entry from the |
| 1073 |
index table. Then the integer which was second on stack is added to the |
| 1074 |
set of integers for that index and the new record is written back to the |
| 1075 |
database file. Note |
| 1076 |
that the same index entry can store multiple integers if there |
| 1077 |
are two or more table entries with the same value for the two |
| 1078 |
column. |
| 1079 |
</p> |
| 1080 |
|
| 1081 |
<p>Now let's look at how this index will be used. Consider the |
| 1082 |
following query:</p> |
| 1083 |
|
| 1084 |
<blockquote><pre> |
| 1085 |
SELECT * FROM examp WHERE two==50; |
| 1086 |
</pre></blockquote> |
| 1087 |
|
| 1088 |
<p>SQLite generates the following VDBE code to handle this query:</p> |
| 1089 |
<blockquote><tt>addr opcode p1 p2 p3 <br> |
| 1090 |
---- ------------ ----- ----- -----------------------------------<br> |
| 1091 |
0 ColumnName 0 0 one <br> |
| 1092 |
1 ColumnName 1 0 two <br> |
| 1093 |
2 Integer 0 0 <br> |
| 1094 |
3 OpenRead 0 3 examp <br> |
| 1095 |
4 VerifyCookie 0 256 <br> |
| 1096 |
5 Integer 0 0 <br> |
| 1097 |
6 OpenRead 1 4 examp_idx1 <br> |
| 1098 |
7 Integer 50 0 50 <br> |
| 1099 |
8 MakeKey 1 0 n <br> |
| 1100 |
9 MemStore 0 0 <br> |
| 1101 |
10 MoveTo 1 19 <br> |
| 1102 |
11 MemLoad 0 0 <br> |
| 1103 |
12 IdxGT 1 19 <br> |
| 1104 |
13 IdxRecno 1 0 <br> |
| 1105 |
14 MoveTo 0 0 <br> |
| 1106 |
15 Column 0 0 <br> |
| 1107 |
16 Column 0 1 <br> |
| 1108 |
17 Callback 2 0 <br> |
| 1109 |
18 Next 1 11 <br> |
| 1110 |
19 Close 0 0 <br> |
| 1111 |
20 Close 1 0 <br> |
| 1112 |
21 Halt 0 0</tt></blockquote> |
| 1113 |
<p>The SELECT begins in a familiar fashion. First the column |
| 1114 |
names are initialized and the table being queried is opened. |
| 1115 |
Things become different beginning with instructions 5 and 6 where |
| 1116 |
the index file is also opened. Instructions 7 and 8 make |
| 1117 |
a key with the value of 50. |
| 1118 |
The <a href="opcode.html#MemStore">MemStore</a> instruction at 9 stores |
| 1119 |
the index key in VDBE memory location 0. The VDBE memory is used to |
| 1120 |
avoid having to fetch a value from deep in the stack, which can be done, |
| 1121 |
but makes the program harder to generate. The following instruction |
| 1122 |
<a href="opcode.html#MoveTo">MoveTo</a> at address 10 pops the key off |
| 1123 |
the stack and moves the index cursor to the first row of the index with |
| 1124 |
that key. This initializes the cursor for use in the following loop.</p> |
| 1125 |
|
| 1126 |
<p>Instructions 11 through 18 implement a loop over all index records |
| 1127 |
with the key that was fetched by instruction 8. All of the index |
| 1128 |
records with this key will be contiguous in the index table, so we walk |
| 1129 |
through them and fetch the corresponding table key from the index. |
| 1130 |
This table key is then used to move the cursor to that row in the table. |
| 1131 |
The rest of the loop is the same as the loop for the non-indexed SELECT |
| 1132 |
query.</p> |
| 1133 |
|
| 1134 |
<p>The loop begins with the <a href="opcode.html#MemLoad">MemLoad</a> |
| 1135 |
instruction at 11 which pushes a copy of the index key back onto the |
| 1136 |
stack. The instruction <a href="opcode.html#IdxGT">IdxGT</a> at 12 |
| 1137 |
compares the key to the key in the current index record pointed to by |
| 1138 |
cursor P1. If the index key at the current cursor location is greater |
| 1139 |
than the index we are looking for, then jump out of the loop.</p> |
| 1140 |
|
| 1141 |
<p>The instruction <a href="opcode.html#IdxRecno">IdxRecno</a> at 13 |
| 1142 |
pushes onto the stack the table record number from the index. The |
| 1143 |
following MoveTo pops it and moves the table cursor to that row. The |
| 1144 |
next 3 instructions select the column data the same way as in the non- |
| 1145 |
indexed case. The Column instructions fetch the column data and the |
| 1146 |
callback function is invoked. The final Next instruction advances the |
| 1147 |
index cursor, not the table cursor, to the next row, and then branches |
| 1148 |
back to the start of the loop if there are any index records left.</p> |
| 1149 |
|
| 1150 |
<p>Since the index is used to look up values in the table, |
| 1151 |
it is important that the index and table be kept consistent. |
| 1152 |
Now that there is an index on the examp table, we will have |
| 1153 |
to update that index whenever data is inserted, deleted, or |
| 1154 |
changed in the examp table. Remember the first example above |
| 1155 |
where we were able to insert a new row into the "examp" table using |
| 1156 |
12 VDBE instructions. Now that this table is indexed, 19 |
| 1157 |
instructions are required. The SQL statement is this:</p> |
| 1158 |
|
| 1159 |
<blockquote><pre> |
| 1160 |
INSERT INTO examp VALUES('Hello, World!',99); |
| 1161 |
</pre></blockquote> |
| 1162 |
|
| 1163 |
<p>And the generated code looks like this:</p> |
| 1164 |
<blockquote><tt>addr opcode p1 p2 p3 <br> |
| 1165 |
---- ------------ ----- ----- -----------------------------------<br> |
| 1166 |
0 Transaction 1 0 <br> |
| 1167 |
1 Transaction 0 0 <br> |
| 1168 |
2 VerifyCookie 0 256 <br> |
| 1169 |
3 Integer 0 0 <br> |
| 1170 |
4 OpenWrite 0 3 examp <br> |
| 1171 |
5 Integer 0 0 <br> |
| 1172 |
6 OpenWrite 1 4 examp_idx1 <br> |
| 1173 |
7 NewRecno 0 0 <br> |
| 1174 |
8 String 0 0 Hello, World! <br> |
| 1175 |
9 Integer 99 0 99 <br> |
| 1176 |
10 Dup 2 1 <br> |
| 1177 |
11 Dup 1 1 <br> |
| 1178 |
12 MakeIdxKey 1 0 n <br> |
| 1179 |
13 IdxPut 1 0 <br> |
| 1180 |
14 MakeRecord 2 0 <br> |
| 1181 |
15 PutIntKey 0 1 <br> |
| 1182 |
16 Close 0 0 <br> |
| 1183 |
17 Close 1 0 <br> |
| 1184 |
18 Commit 0 0 <br> |
| 1185 |
19 Halt 0 0</tt></blockquote> |
| 1186 |
<p>At this point, you should understand the VDBE well enough to |
| 1187 |
figure out on your own how the above program works. So we will |
| 1188 |
not discuss it further in this text.</p> |
| 1189 |
|
| 1190 |
<h2>Joins</h2> |
| 1191 |
|
| 1192 |
<p>In a join, two or more tables are combined to generate a single |
| 1193 |
result. The result table consists of every possible combination |
| 1194 |
of rows from the tables being joined. The easiest and most natural |
| 1195 |
way to implement this is with nested loops.</p> |
| 1196 |
|
| 1197 |
<p>Recall the query template discussed above where there was a |
| 1198 |
single loop that searched through every record of the table. |
| 1199 |
In a join we have basically the same thing except that there |
| 1200 |
are nested loops. For example, to join two tables, the query |
| 1201 |
template might look something like this:</p> |
| 1202 |
|
| 1203 |
<p> |
| 1204 |
<ol> |
| 1205 |
<li>Initialize the <b>azColumnName[]</b> array for the callback.</li> |
| 1206 |
<li>Open two cursors, one to each of the two tables being queried.</li> |
| 1207 |
<li>For each record in the first table, do: |
| 1208 |
<ol type="a"> |
| 1209 |
<li>For each record in the second table do: |
| 1210 |
<ol type="i"> |
| 1211 |
<li>If the WHERE clause evaluates to FALSE, then skip the steps that |
| 1212 |
follow and continue to the next record.</li> |
| 1213 |
<li>Compute all columns for the current row of the result.</li> |
| 1214 |
<li>Invoke the callback function for the current row of the result.</li> |
| 1215 |
</ol></li> |
| 1216 |
</ol> |
| 1217 |
<li>Close both cursors.</li> |
| 1218 |
</ol> |
| 1219 |
</p> |
| 1220 |
|
| 1221 |
<p>This template will work, but it is likely to be slow since we |
| 1222 |
are now dealing with an O(N<sup>2</sup>) loop. But it often works |
| 1223 |
out that the WHERE clause can be factored into terms and that one or |
| 1224 |
more of those terms will involve only columns in the first table. |
| 1225 |
When this happens, we can factor part of the WHERE clause test out of |
| 1226 |
the inner loop and gain a lot of efficiency. So a better template |
| 1227 |
would be something like this:</p> |
| 1228 |
|
| 1229 |
<p> |
| 1230 |
<ol> |
| 1231 |
<li>Initialize the <b>azColumnName[]</b> array for the callback.</li> |
| 1232 |
<li>Open two cursors, one to each of the two tables being queried.</li> |
| 1233 |
<li>For each record in the first table, do: |
| 1234 |
<ol type="a"> |
| 1235 |
<li>Evaluate terms of the WHERE clause that only involve columns from |
| 1236 |
the first table. If any term is false (meaning that the whole |
| 1237 |
WHERE clause must be false) then skip the rest of this loop and |
| 1238 |
continue to the next record.</li> |
| 1239 |
<li>For each record in the second table do: |
| 1240 |
<ol type="i"> |
| 1241 |
<li>If the WHERE clause evaluates to FALSE, then skip the steps that |
| 1242 |
follow and continue to the next record.</li> |
| 1243 |
<li>Compute all columns for the current row of the result.</li> |
| 1244 |
<li>Invoke the callback function for the current row of the result.</li> |
| 1245 |
</ol></li> |
| 1246 |
</ol> |
| 1247 |
<li>Close both cursors.</li> |
| 1248 |
</ol> |
| 1249 |
</p> |
| 1250 |
|
| 1251 |
<p>Additional speed-up can occur if an index can be used to speed |
| 1252 |
the search of either or the two loops.</p> |
| 1253 |
|
| 1254 |
<p>SQLite always constructs the loops in the same order as the |
| 1255 |
tables appear in the FROM clause of the SELECT statement. The |
| 1256 |
left-most table becomes the outer loop and the right-most table |
| 1257 |
becomes the inner loop. It is possible, in theory, to reorder |
| 1258 |
the loops in some circumstances to speed the evaluation of the |
| 1259 |
join. But SQLite does not attempt this optimization.</p> |
| 1260 |
|
| 1261 |
<p>You can see how SQLite constructs nested loops in the following |
| 1262 |
example:</p> |
| 1263 |
|
| 1264 |
<blockquote><pre> |
| 1265 |
CREATE TABLE examp2(three int, four int); |
| 1266 |
SELECT * FROM examp, examp2 WHERE two<50 AND four==two; |
| 1267 |
</pre></blockquote> |
| 1268 |
<blockquote><tt>addr opcode p1 p2 p3 <br> |
| 1269 |
---- ------------ ----- ----- -----------------------------------<br> |
| 1270 |
0 ColumnName 0 0 examp.one <br> |
| 1271 |
1 ColumnName 1 0 examp.two <br> |
| 1272 |
2 ColumnName 2 0 examp2.three <br> |
| 1273 |
3 ColumnName 3 0 examp2.four <br> |
| 1274 |
4 Integer 0 0 <br> |
| 1275 |
5 OpenRead 0 3 examp <br> |
| 1276 |
6 VerifyCookie 0 909 <br> |
| 1277 |
7 Integer 0 0 <br> |
| 1278 |
8 OpenRead 1 5 examp2 <br> |
| 1279 |
9 Rewind 0 24 <br> |
| 1280 |
10 Column 0 1 <br> |
| 1281 |
11 Integer 50 0 50 <br> |
| 1282 |
12 Ge 1 23 <br> |
| 1283 |
13 Rewind 1 23 <br> |
| 1284 |
14 Column 1 1 <br> |
| 1285 |
15 Column 0 1 <br> |
| 1286 |
16 Ne 1 22 <br> |
| 1287 |
17 Column 0 0 <br> |
| 1288 |
18 Column 0 1 <br> |
| 1289 |
19 Column 1 0 <br> |
| 1290 |
20 Column 1 1 <br> |
| 1291 |
21 Callback 4 0 <br> |
| 1292 |
22 Next 1 14 <br> |
| 1293 |
23 Next 0 10 <br> |
| 1294 |
24 Close 0 0 <br> |
| 1295 |
25 Close 1 0 <br> |
| 1296 |
26 Halt 0 0</tt></blockquote> |
| 1297 |
<p>The outer loop over table examp is implemented by instructions |
| 1298 |
7 through 23. The inner loop is instructions 13 through 22. |
| 1299 |
Notice that the "two<50" term of the WHERE expression involves |
| 1300 |
only columns from the first table and can be factored out of |
| 1301 |
the inner loop. SQLite does this and implements the "two<50" |
| 1302 |
test in instructions 10 through 12. The "four==two" test is |
| 1303 |
implemented by instructions 14 through 16 in the inner loop.</p> |
| 1304 |
|
| 1305 |
<p>SQLite does not impose any arbitrary limits on the tables in |
| 1306 |
a join. It also allows a table to be joined with itself.</p> |
| 1307 |
|
| 1308 |
<h2>The ORDER BY clause</h2> |
| 1309 |
|
| 1310 |
<p>For historical reasons, and for efficiency, all sorting is currently |
| 1311 |
done in memory.</p> |
| 1312 |
|
| 1313 |
<p>SQLite implements the ORDER BY clause using a special |
| 1314 |
set of instructions to control an object called a sorter. In the |
| 1315 |
inner-most loop of the query, where there would normally be |
| 1316 |
a Callback instruction, instead a record is constructed that |
| 1317 |
contains both callback parameters and a key. This record |
| 1318 |
is added to the sorter (in a linked list). After the query loop |
| 1319 |
finishes, the list of records is sorted and this list is walked. For |
| 1320 |
each record on the list, the callback is invoked. Finally, the sorter |
| 1321 |
is closed and memory is deallocated.</p> |
| 1322 |
|
| 1323 |
<p>We can see the process in action in the following query:</p> |
| 1324 |
|
| 1325 |
<blockquote><pre> |
| 1326 |
SELECT * FROM examp ORDER BY one DESC, two; |
| 1327 |
</pre></blockquote> |
| 1328 |
<blockquote><tt>addr opcode p1 p2 p3 <br> |
| 1329 |
---- ------------ ----- ----- -----------------------------------<br> |
| 1330 |
0 ColumnName 0 0 one <br> |
| 1331 |
1 ColumnName 1 0 two <br> |
| 1332 |
2 Integer 0 0 <br> |
| 1333 |
3 OpenRead 0 3 examp <br> |
| 1334 |
4 VerifyCookie 0 909 <br> |
| 1335 |
5 Rewind 0 14 <br> |
| 1336 |
6 Column 0 0 <br> |
| 1337 |
7 Column 0 1 <br> |
| 1338 |
8 SortMakeRec 2 0 <br> |
| 1339 |
9 Column 0 0 <br> |
| 1340 |
10 Column 0 1 <br> |
| 1341 |
11 SortMakeKey 2 0 D+ <br> |
| 1342 |
12 SortPut 0 0 <br> |
| 1343 |
13 Next 0 6 <br> |
| 1344 |
14 Close 0 0 <br> |
| 1345 |
15 Sort 0 0 <br> |
| 1346 |
16 SortNext 0 19 <br> |
| 1347 |
17 SortCallback 2 0 <br> |
| 1348 |
18 Goto 0 16 <br> |
| 1349 |
19 SortReset 0 0 <br> |
| 1350 |
20 Halt 0 0</tt></blockquote> |
| 1351 |
<p>There is only one sorter object, so there are no instructions to open |
| 1352 |
or close it. It is opened automatically when needed, and it is closed |
| 1353 |
when the VDBE program halts.</p> |
| 1354 |
|
| 1355 |
<p>The query loop is built from instructions 5 through 13. Instructions |
| 1356 |
6 through 8 build a record that contains the azData[] values for a single |
| 1357 |
invocation of the callback. A sort key is generated by instructions |
| 1358 |
9 through 11. Instruction 12 combines the invocation record and the |
| 1359 |
sort key into a single entry and puts that entry on the sort list.<p> |
| 1360 |
|
| 1361 |
<p>The P3 argument of instruction 11 is of particular interest. The |
| 1362 |
sort key is formed by prepending one character from P3 to each string |
| 1363 |
and concatenating all the strings. The sort comparison function will |
| 1364 |
look at this character to determine whether the sort order is |
| 1365 |
ascending or descending, and whether to sort as a string or number. |
| 1366 |
In this example, the first column should be sorted as a string |
| 1367 |
in descending order so its prefix is "D" and the second column should |
| 1368 |
sorted numerically in ascending order so its prefix is "+". Ascending |
| 1369 |
string sorting uses "A", and descending numeric sorting uses "-".</p> |
| 1370 |
|
| 1371 |
<p>After the query loop ends, the table being queried is closed at |
| 1372 |
instruction 14. This is done early in order to allow other processes |
| 1373 |
or threads to access that table, if desired. The list of records |
| 1374 |
that was built up inside the query loop is sorted by the instruction |
| 1375 |
at 15. Instructions 16 through 18 walk through the record list |
| 1376 |
(which is now in sorted order) and invoke the callback once for |
| 1377 |
each record. Finally, the sorter is closed at instruction 19.</p> |
| 1378 |
|
| 1379 |
<h2>Aggregate Functions And The GROUP BY and HAVING Clauses</h2> |
| 1380 |
|
| 1381 |
<p>To compute aggregate functions, the VDBE implements a special |
| 1382 |
data structure and instructions for controlling that data structure. |
| 1383 |
The data structure is an unordered set of buckets, where each bucket |
| 1384 |
has a key and one or more memory locations. Within the query |
| 1385 |
loop, the GROUP BY clause is used to construct a key and the bucket |
| 1386 |
with that key is brought into focus. A new bucket is created with |
| 1387 |
the key if one did not previously exist. Once the bucket is in |
| 1388 |
focus, the memory locations of the bucket are used to accumulate |
| 1389 |
the values of the various aggregate functions. After the query |
| 1390 |
loop terminates, each bucket is visited once to generate a |
| 1391 |
single row of the results.</p> |
| 1392 |
|
| 1393 |
<p>An example will help to clarify this concept. Consider the |
| 1394 |
following query:</p> |
| 1395 |
|
| 1396 |
<blockquote><pre> |
| 1397 |
SELECT three, min(three+four)+avg(four) |
| 1398 |
FROM examp2 |
| 1399 |
GROUP BY three; |
| 1400 |
</pre></blockquote> |
| 1401 |
|
| 1402 |
|
| 1403 |
<p>The VDBE code generated for this query is as follows:</p> |
| 1404 |
<blockquote><tt>addr opcode p1 p2 p3 <br> |
| 1405 |
---- ------------ ----- ----- -----------------------------------<br> |
| 1406 |
0 ColumnName 0 0 three <br> |
| 1407 |
1 ColumnName 1 0 min(three+four)+avg(four) <br> |
| 1408 |
2 AggReset 0 3 <br> |
| 1409 |
3 AggInit 0 1 ptr(0x7903a0) <br> |
| 1410 |
4 AggInit 0 2 ptr(0x790700) <br> |
| 1411 |
5 Integer 0 0 <br> |
| 1412 |
6 OpenRead 0 5 examp2 <br> |
| 1413 |
7 VerifyCookie 0 909 <br> |
| 1414 |
8 Rewind 0 23 <br> |
| 1415 |
9 Column 0 0 <br> |
| 1416 |
10 MakeKey 1 0 n <br> |
| 1417 |
11 AggFocus 0 14 <br> |
| 1418 |
12 Column 0 0 <br> |
| 1419 |
13 AggSet 0 0 <br> |
| 1420 |
14 Column 0 0 <br> |
| 1421 |
15 Column 0 1 <br> |
| 1422 |
16 Add 0 0 <br> |
| 1423 |
17 Integer 1 0 <br> |
| 1424 |
18 AggFunc 0 1 ptr(0x7903a0) <br> |
| 1425 |
19 Column 0 1 <br> |
| 1426 |
20 Integer 2 0 <br> |
| 1427 |
21 AggFunc 0 1 ptr(0x790700) <br> |
| 1428 |
22 Next 0 9 <br> |
| 1429 |
23 Close 0 0 <br> |
| 1430 |
24 AggNext 0 31 <br> |
| 1431 |
25 AggGet 0 0 <br> |
| 1432 |
26 AggGet 0 1 <br> |
| 1433 |
27 AggGet 0 2 <br> |
| 1434 |
28 Add 0 0 <br> |
| 1435 |
29 Callback 2 0 <br> |
| 1436 |
30 Goto 0 24 <br> |
| 1437 |
31 Noop 0 0 <br> |
| 1438 |
32 Halt 0 0</tt></blockquote> |
| 1439 |
<p>The first instruction of interest is the |
| 1440 |
<a href="opcode.html#AggReset">AggReset</a> at 2. |
| 1441 |
The AggReset instruction initializes the set of buckets to be the |
| 1442 |
empty set and specifies the number of memory slots available in each |
| 1443 |
bucket as P2. In this example, each bucket will hold 3 memory slots. |
| 1444 |
It is not obvious, but if you look closely at the rest of the program |
| 1445 |
you can figure out what each of these slots is intended for.</p> |
| 1446 |
|
| 1447 |
<blockquote><table border="2" cellpadding="5"> |
| 1448 |
<tr><th>Memory Slot</th><th>Intended Use Of This Memory Slot</th></tr> |
| 1449 |
<tr><td>0</td><td>The "three" column -- the key to the bucket</td></tr> |
| 1450 |
<tr><td>1</td><td>The minimum "three+four" value</td></tr> |
| 1451 |
<tr><td>2</td><td>The sum of all "four" values. This is used to compute |
| 1452 |
"avg(four)".</td></tr> |
| 1453 |
</table></blockquote> |
| 1454 |
|
| 1455 |
<p>The query loop is implemented by instructions 8 through 22. |
| 1456 |
The aggregate key specified by the GROUP BY clause is computed |
| 1457 |
by instructions 9 and 10. Instruction 11 causes the appropriate |
| 1458 |
bucket to come into focus. If a bucket with the given key does |
| 1459 |
not already exist, a new bucket is created and control falls |
| 1460 |
through to instructions 12 and 13 which initialize the bucket. |
| 1461 |
If the bucket does already exist, then a jump is made to instruction |
| 1462 |
14. The values of aggregate functions are updated by the instructions |
| 1463 |
between 11 and 21. Instructions 14 through 18 update memory |
| 1464 |
slot 1 to hold the next value "min(three+four)". Then the sum of the |
| 1465 |
"four" column is updated by instructions 19 through 21.</p> |
| 1466 |
|
| 1467 |
<p>After the query loop is finished, the table "examp2" is closed at |
| 1468 |
instruction 23 so that its lock will be released and it can be |
| 1469 |
used by other threads or processes. The next step is to loop |
| 1470 |
over all aggregate buckets and output one row of the result for |
| 1471 |
each bucket. This is done by the loop at instructions 24 |
| 1472 |
through 30. The AggNext instruction at 24 brings the next bucket |
| 1473 |
into focus, or jumps to the end of the loop if all buckets have |
| 1474 |
been examined already. The 3 columns of the result are fetched from |
| 1475 |
the aggregator bucket in order at instructions 25 through 27. |
| 1476 |
Finally, the callback is invoked at instruction 29.</p> |
| 1477 |
|
| 1478 |
<p>In summary then, any query with aggregate functions is implemented |
| 1479 |
by two loops. The first loop scans the input table and computes |
| 1480 |
aggregate information into buckets and the second loop scans through |
| 1481 |
all the buckets to compute the final result.</p> |
| 1482 |
|
| 1483 |
<p>The realization that an aggregate query is really two consecutive |
| 1484 |
loops makes it much easier to understand the difference between |
| 1485 |
a WHERE clause and a HAVING clause in th3 SQL query statement. The |
| 1486 |
WHERE clause is a restriction on the first loop and the HAVING |
| 1487 |
clause is a restriction on the second loop. You can see this |
| 1488 |
by adding both a WHERE and a HAVING clause to our example query:</p> |
| 1489 |
|
| 1490 |
|
| 1491 |
<blockquote><pre> |
| 1492 |
SELECT three, min(three+four)+avg(four) |
| 1493 |
FROM examp2 |
| 1494 |
WHERE three>four |
| 1495 |
GROUP BY three |
| 1496 |
HAVING avg(four)<10; |
| 1497 |
</pre></blockquote> |
| 1498 |
<blockquote><tt>addr opcode p1 p2 p3 <br> |
| 1499 |
---- ------------ ----- ----- -----------------------------------<br> |
| 1500 |
0 ColumnName 0 0 three <br> |
| 1501 |
1 ColumnName 1 0 min(three+four)+avg(four) <br> |
| 1502 |
2 AggReset 0 3 <br> |
| 1503 |
3 AggInit 0 1 ptr(0x7903a0) <br> |
| 1504 |
4 AggInit 0 2 ptr(0x790700) <br> |
| 1505 |
5 Integer 0 0 <br> |
| 1506 |
6 OpenRead 0 5 examp2 <br> |
| 1507 |
7 VerifyCookie 0 909 <br> |
| 1508 |
8 Rewind 0 26 <br> |
| 1509 |
9 Column 0 0 <br> |
| 1510 |
10 Column 0 1 <br> |
| 1511 |
11 Le 1 25 <br> |
| 1512 |
12 Column 0 0 <br> |
| 1513 |
13 MakeKey 1 0 n <br> |
| 1514 |
14 AggFocus 0 17 <br> |
| 1515 |
15 Column 0 0 <br> |
| 1516 |
16 AggSet 0 0 <br> |
| 1517 |
17 Column 0 0 <br> |
| 1518 |
18 Column 0 1 <br> |
| 1519 |
19 Add 0 0 <br> |
| 1520 |
20 Integer 1 0 <br> |
| 1521 |
21 AggFunc 0 1 ptr(0x7903a0) <br> |
| 1522 |
22 Column 0 1 <br> |
| 1523 |
23 Integer 2 0 <br> |
| 1524 |
24 AggFunc 0 1 ptr(0x790700) <br> |
| 1525 |
25 Next 0 9 <br> |
| 1526 |
26 Close 0 0 <br> |
| 1527 |
27 AggNext 0 37 <br> |
| 1528 |
28 AggGet 0 2 <br> |
| 1529 |
29 Integer 10 0 10 <br> |
| 1530 |
30 Ge 1 27 <br> |
| 1531 |
31 AggGet 0 0 <br> |
| 1532 |
32 AggGet 0 1 <br> |
| 1533 |
33 AggGet 0 2 <br> |
| 1534 |
34 Add 0 0 <br> |
| 1535 |
35 Callback 2 0 <br> |
| 1536 |
36 Goto 0 27 <br> |
| 1537 |
37 Noop 0 0 <br> |
| 1538 |
38 Halt 0 0</tt></blockquote> |
| 1539 |
<p>The code generated in this last example is the same as the |
| 1540 |
previous except for the addition of two conditional jumps used |
| 1541 |
to implement the extra WHERE and HAVING clauses. The WHERE |
| 1542 |
clause is implemented by instructions 9 through 11 in the query |
| 1543 |
loop. The HAVING clause is implemented by instructions 28 through |
| 1544 |
30 in the output loop.</p> |
| 1545 |
|
| 1546 |
<h2>Using SELECT Statements As Terms In An Expression</h2> |
| 1547 |
|
| 1548 |
<p>The very name "Structured Query Language" tells us that SQL should |
| 1549 |
support nested queries. And, in fact, two different kinds of nesting |
| 1550 |
are supported. Any SELECT statement that returns a single-row, single-column |
| 1551 |
result can be used as a term in an expression of another SELECT statement. |
| 1552 |
And, a SELECT statement that returns a single-column, multi-row result |
| 1553 |
can be used as the right-hand operand of the IN and NOT IN operators. |
| 1554 |
We will begin this section with an example of the first kind of nesting, |
| 1555 |
where a single-row, single-column SELECT is used as a term in an expression |
| 1556 |
of another SELECT. Here is our example:</p> |
| 1557 |
|
| 1558 |
<blockquote><pre> |
| 1559 |
SELECT * FROM examp |
| 1560 |
WHERE two!=(SELECT three FROM examp2 |
| 1561 |
WHERE four=5); |
| 1562 |
</pre></blockquote> |
| 1563 |
|
| 1564 |
<p>The way SQLite deals with this is to first run the inner SELECT |
| 1565 |
(the one against examp2) and store its result in a private memory |
| 1566 |
cell. SQLite then substitutes the value of this private memory |
| 1567 |
cell for the inner SELECT when it evaluates the outer SELECT. |
| 1568 |
The code looks like this:</p> |
| 1569 |
<blockquote><tt>addr opcode p1 p2 p3 <br> |
| 1570 |
---- ------------ ----- ----- -----------------------------------<br> |
| 1571 |
0 String 0 0 <br> |
| 1572 |
1 MemStore 0 1 <br> |
| 1573 |
2 Integer 0 0 <br> |
| 1574 |
3 OpenRead 1 5 examp2 <br> |
| 1575 |
4 VerifyCookie 0 909 <br> |
| 1576 |
5 Rewind 1 13 <br> |
| 1577 |
6 Column 1 1 <br> |
| 1578 |
7 Integer 5 0 5 <br> |
| 1579 |
8 Ne 1 12 <br> |
| 1580 |
9 Column 1 0 <br> |
| 1581 |
10 MemStore 0 1 <br> |
| 1582 |
11 Goto 0 13 <br> |
| 1583 |
12 Next 1 6 <br> |
| 1584 |
13 Close 1 0 <br> |
| 1585 |
14 ColumnName 0 0 one <br> |
| 1586 |
15 ColumnName 1 0 two <br> |
| 1587 |
16 Integer 0 0 <br> |
| 1588 |
17 OpenRead 0 3 examp <br> |
| 1589 |
18 Rewind 0 26 <br> |
| 1590 |
19 Column 0 1 <br> |
| 1591 |
20 MemLoad 0 0 <br> |
| 1592 |
21 Eq 1 25 <br> |
| 1593 |
22 Column 0 0 <br> |
| 1594 |
23 Column 0 1 <br> |
| 1595 |
24 Callback 2 0 <br> |
| 1596 |
25 Next 0 19 <br> |
| 1597 |
26 Close 0 0 <br> |
| 1598 |
27 Halt 0 0</tt></blockquote> |
| 1599 |
<p>The private memory cell is initialized to NULL by the first |
| 1600 |
two instructions. Instructions 2 through 13 implement the inner |
| 1601 |
SELECT statement against the examp2 table. Notice that instead of |
| 1602 |
sending the result to a callback or storing the result on a sorter, |
| 1603 |
the result of the query is pushed into the memory cell by instruction |
| 1604 |
10 and the loop is abandoned by the jump at instruction 11. |
| 1605 |
The jump at instruction at 11 is vestigial and never executes.</p> |
| 1606 |
|
| 1607 |
<p>The outer SELECT is implemented by instructions 14 through 25. |
| 1608 |
In particular, the WHERE clause that contains the nested select |
| 1609 |
is implemented by instructions 19 through 21. You can see that |
| 1610 |
the result of the inner select is loaded onto the stack by instruction |
| 1611 |
20 and used by the conditional jump at 21.</p> |
| 1612 |
|
| 1613 |
<p>When the result of a sub-select is a scalar, a single private memory |
| 1614 |
cell can be used, as shown in the previous |
| 1615 |
example. But when the result of a sub-select is a vector, such |
| 1616 |
as when the sub-select is the right-hand operand of IN or NOT IN, |
| 1617 |
a different approach is needed. In this case, |
| 1618 |
the result of the sub-select is |
| 1619 |
stored in a transient table and the contents of that table |
| 1620 |
are tested using the Found or NotFound operators. Consider this |
| 1621 |
example:</p> |
| 1622 |
|
| 1623 |
<blockquote><pre> |
| 1624 |
SELECT * FROM examp |
| 1625 |
WHERE two IN (SELECT three FROM examp2); |
| 1626 |
</pre></blockquote> |
| 1627 |
|
| 1628 |
<p>The code generated to implement this last query is as follows:</p> |
| 1629 |
<blockquote><tt>addr opcode p1 p2 p3 <br> |
| 1630 |
---- ------------ ----- ----- -----------------------------------<br> |
| 1631 |
0 OpenTemp 1 1 <br> |
| 1632 |
1 Integer 0 0 <br> |
| 1633 |
2 OpenRead 2 5 examp2 <br> |
| 1634 |
3 VerifyCookie 0 909 <br> |
| 1635 |
4 Rewind 2 10 <br> |
| 1636 |
5 Column 2 0 <br> |
| 1637 |
6 IsNull -1 9 <br> |
| 1638 |
7 String 0 0 <br> |
| 1639 |
8 PutStrKey 1 0 <br> |
| 1640 |
9 Next 2 5 <br> |
| 1641 |
10 Close 2 0 <br> |
| 1642 |
11 ColumnName 0 0 one <br> |
| 1643 |
12 ColumnName 1 0 two <br> |
| 1644 |
13 Integer 0 0 <br> |
| 1645 |
14 OpenRead 0 3 examp <br> |
| 1646 |
15 Rewind 0 25 <br> |
| 1647 |
16 Column 0 1 <br> |
| 1648 |
17 NotNull -1 20 <br> |
| 1649 |
18 Pop 1 0 <br> |
| 1650 |
19 Goto 0 24 <br> |
| 1651 |
20 NotFound 1 24 <br> |
| 1652 |
21 Column 0 0 <br> |
| 1653 |
22 Column 0 1 <br> |
| 1654 |
23 Callback 2 0 <br> |
| 1655 |
24 Next 0 16 <br> |
| 1656 |
25 Close 0 0 <br> |
| 1657 |
26 Halt 0 0</tt></blockquote> |
| 1658 |
<p>The transient table in which the results of the inner SELECT are |
| 1659 |
stored is created by the <a href="opcode.html#OpenTemp">OpenTemp</a> |
| 1660 |
instruction at 0. This opcode is used for tables that exist for the |
| 1661 |
duration of a single SQL statement only. The transient cursor is always |
| 1662 |
opened read/write even if the main database is read-only. The transient |
| 1663 |
table is deleted automatically when the cursor is closed. The P2 value |
| 1664 |
of 1 means the cursor points to a BTree index, which has no data but can |
| 1665 |
have an arbitrary key.</p> |
| 1666 |
|
| 1667 |
<p>The inner SELECT statement is implemented by instructions 1 through 10. |
| 1668 |
All this code does is make an entry in the temporary table for each |
| 1669 |
row of the examp2 table with a non-NULL value for the "three" column. |
| 1670 |
The key for each temporary table entry is the "three" column of examp2 |
| 1671 |
and the data is an empty string since it is never used.</p> |
| 1672 |
|
| 1673 |
<p>The outer SELECT is implemented by instructions 11 through 25. In |
| 1674 |
particular, the WHERE clause containing the IN operator is implemented |
| 1675 |
by instructions at 16, 17, and 20. Instruction 16 pushes the value of |
| 1676 |
the "two" column for the current row onto the stack and instruction 17 |
| 1677 |
checks to see that it is non-NULL. If this is successful, execution |
| 1678 |
jumps to 20, where it tests to see if top of the stack matches any key |
| 1679 |
in the temporary table. The rest of the code is the same as what has |
| 1680 |
been shown before.</p> |
| 1681 |
|
| 1682 |
<h2>Compound SELECT Statements</h2> |
| 1683 |
|
| 1684 |
<p>SQLite also allows two or more SELECT statements to be joined as |
| 1685 |
peers using operators UNION, UNION ALL, INTERSECT, and EXCEPT. These |
| 1686 |
compound select statements are implemented using transient tables. |
| 1687 |
The implementation is slightly different for each operator, but the |
| 1688 |
basic ideas are the same. For an example we will use the EXCEPT |
| 1689 |
operator.</p> |
| 1690 |
|
| 1691 |
<blockquote><pre> |
| 1692 |
SELECT two FROM examp |
| 1693 |
EXCEPT |
| 1694 |
SELECT four FROM examp2; |
| 1695 |
</pre></blockquote> |
| 1696 |
|
| 1697 |
<p>The result of this last example should be every unique value |
| 1698 |
of the "two" column in the examp table, except any value that is |
| 1699 |
in the "four" column of examp2 is removed. The code to implement |
| 1700 |
this query is as follows:</p> |
| 1701 |
<blockquote><tt>addr opcode p1 p2 p3 <br> |
| 1702 |
---- ------------ ----- ----- -----------------------------------<br> |
| 1703 |
0 OpenTemp 0 1 <br> |
| 1704 |
1 KeyAsData 0 1 <br> |
| 1705 |
2 Integer 0 0 <br> |
| 1706 |
3 OpenRead 1 3 examp <br> |
| 1707 |
4 VerifyCookie 0 909 <br> |
| 1708 |
5 Rewind 1 11 <br> |
| 1709 |
6 Column 1 1 <br> |
| 1710 |
7 MakeRecord 1 0 <br> |
| 1711 |
8 String 0 0 <br> |
| 1712 |
9 PutStrKey 0 0 <br> |
| 1713 |
10 Next 1 6 <br> |
| 1714 |
11 Close 1 0 <br> |
| 1715 |
12 Integer 0 0 <br> |
| 1716 |
13 OpenRead 2 5 examp2 <br> |
| 1717 |
14 Rewind 2 20 <br> |
| 1718 |
15 Column 2 1 <br> |
| 1719 |
16 MakeRecord 1 0 <br> |
| 1720 |
17 NotFound 0 19 <br> |
| 1721 |
18 Delete 0 0 <br> |
| 1722 |
19 Next 2 15 <br> |
| 1723 |
20 Close 2 0 <br> |
| 1724 |
21 ColumnName 0 0 four <br> |
| 1725 |
22 Rewind 0 26 <br> |
| 1726 |
23 Column 0 0 <br> |
| 1727 |
24 Callback 1 0 <br> |
| 1728 |
25 Next 0 23 <br> |
| 1729 |
26 Close 0 0 <br> |
| 1730 |
27 Halt 0 0</tt></blockquote> |
| 1731 |
<p>The transient table in which the result is built is created by |
| 1732 |
instruction 0. Three loops then follow. The loop at instructions |
| 1733 |
5 through 10 implements the first SELECT statement. The second |
| 1734 |
SELECT statement is implemented by the loop at instructions 14 through |
| 1735 |
19. Finally, a loop at instructions 22 through 25 reads the transient |
| 1736 |
table and invokes the callback once for each row in the result.</p> |
| 1737 |
|
| 1738 |
<p>Instruction 1 is of particular importance in this example. Normally, |
| 1739 |
the Column instruction extracts the value of a column from a larger |
| 1740 |
record in the data of an SQLite file entry. Instruction 1 sets a flag on |
| 1741 |
the transient table so that Column will instead treat the key of the |
| 1742 |
SQLite file entry as if it were data and extract column information from |
| 1743 |
the key.</p> |
| 1744 |
|
| 1745 |
<p>Here is what is going to happen: The first SELECT statement |
| 1746 |
will construct rows of the result and save each row as the key of |
| 1747 |
an entry in the transient table. The data for each entry in the |
| 1748 |
transient table is never used so we fill it in with an empty string. |
| 1749 |
The second SELECT statement also constructs rows, but the rows |
| 1750 |
constructed by the second SELECT are removed from the transient table. |
| 1751 |
That is why we want the rows to be stored in the key of the SQLite file |
| 1752 |
instead of in the data -- so they can be easily located and deleted.</p> |
| 1753 |
|
| 1754 |
<p>Let's look more closely at what is happening here. The first |
| 1755 |
SELECT is implemented by the loop at instructions 5 through 10. |
| 1756 |
Instruction 5 initializes the loop by rewinding its cursor. |
| 1757 |
Instruction 6 extracts the value of the "two" column from "examp" |
| 1758 |
and instruction 7 converts this into a row. Instruction 8 pushes |
| 1759 |
an empty string onto the stack. Finally, instruction 9 writes the |
| 1760 |
row into the temporary table. But remember, the PutStrKey opcode uses |
| 1761 |
the top of the stack as the record data and the next on stack as the |
| 1762 |
key. For an INSERT statement, the row generated by the |
| 1763 |
MakeRecord opcode is the record data and the record key is an integer |
| 1764 |
created by the NewRecno opcode. But here the roles are reversed and |
| 1765 |
the row created by MakeRecord is the record key and the record data is |
| 1766 |
just an empty string.</p> |
| 1767 |
|
| 1768 |
<p>The second SELECT is implemented by instructions 14 through 19. |
| 1769 |
Instruction 14 initializes the loop by rewinding its cursor. |
| 1770 |
A new result row is created from the "four" column of table "examp2" |
| 1771 |
by instructions 15 and 16. But instead of using PutStrKey to write this |
| 1772 |
new row into the temporary table, we instead call Delete to remove |
| 1773 |
it from the temporary table if it exists.</p> |
| 1774 |
|
| 1775 |
<p>The result of the compound select is sent to the callback routine |
| 1776 |
by the loop at instructions 22 through 25. There is nothing new |
| 1777 |
or remarkable about this loop, except for the fact that the Column |
| 1778 |
instruction at 23 will be extracting a column out of the record key |
| 1779 |
rather than the record data.</p> |
| 1780 |
|
| 1781 |
<h2>Summary</h2> |
| 1782 |
|
| 1783 |
<p>This article has reviewed all of the major techniques used by |
| 1784 |
SQLite's VDBE to implement SQL statements. What has not been shown |
| 1785 |
is that most of these techniques can be used in combination to |
| 1786 |
generate code for an appropriately complex query statement. For |
| 1787 |
example, we have shown how sorting is accomplished on a simple query |
| 1788 |
and we have shown how to implement a compound query. But we did |
| 1789 |
not give an example of sorting in a compound query. This is because |
| 1790 |
sorting a compound query does not introduce any new concepts: it |
| 1791 |
merely combines two previous ideas (sorting and compounding) |
| 1792 |
in the same VDBE program.</p> |
| 1793 |
|
| 1794 |
<p>For additional information on how the SQLite library |
| 1795 |
functions, the reader is directed to look at the SQLite source |
| 1796 |
code directly. If you understand the material in this article, |
| 1797 |
you should not have much difficulty in following the sources. |
| 1798 |
Serious students of the internals of SQLite will probably |
| 1799 |
also want to make a careful study of the VDBE opcodes |
| 1800 |
as documented <a href="opcode.html">here</a>. Most of the |
| 1801 |
opcode documentation is extracted from comments in the source |
| 1802 |
code using a script so you can also get information about the |
| 1803 |
various opcodes directly from the <b>vdbe.c</b> source file. |
| 1804 |
If you have successfully read this far, you should have little |
| 1805 |
difficulty understanding the rest.</p> |
| 1806 |
|
| 1807 |
<p>If you find errors in either the documentation or the code, |
| 1808 |
feel free to fix them and/or contact the author at |
| 1809 |
<a href="mailto:[email protected]">[email protected]</a>. Your bug fixes or |
| 1810 |
suggestions are always welcomed.</p> |
| 1811 |
|
| 1812 |
<p align="center"><small><i>This page was last updated on 2025-05-12 11:14:48Z </small></i></p> |
| 1813 |
|