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