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