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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
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
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
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
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
633
634
635
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
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
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
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
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
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
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
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
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
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
1363
1364
1365
1366
1367
1368
1369
1370
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
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
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
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
1713
1714
1715
1716
1717
1718
1719
1720
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
|
<!DOCTYPE html>
<html><head>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<link href="sqlite.css" rel="stylesheet">
<title>The Virtual Database Engine of SQLite</title>
<!-- path= -->
</head>
<body>
<div class=nosearch>
<a href="index.html">
<img class="logo" src="images/sqlite370_banner.gif" alt="SQLite" border="0">
</a>
<div><!-- IE hack to prevent disappearing logo --></div>
<div class="tagline desktoponly">
Small. Fast. Reliable.<br>Choose any three.
</div>
<div class="menu mainmenu">
<ul>
<li><a href="index.html">Home</a>
<li class='mobileonly'><a href="javascript:void(0)" onclick='toggle_div("submenu")'>Menu</a>
<li class='wideonly'><a href='about.html'>About</a>
<li class='desktoponly'><a href="docs.html">Documentation</a>
<li class='desktoponly'><a href="download.html">Download</a>
<li class='wideonly'><a href='copyright.html'>License</a>
<li class='desktoponly'><a href="support.html">Support</a>
<li class='desktoponly'><a href="prosupport.html">Purchase</a>
<li class='search' id='search_menubutton'>
<a href="javascript:void(0)" onclick='toggle_search()'>Search</a>
</ul>
</div>
<div class="menu submenu" id="submenu">
<ul>
<li><a href='about.html'>About</a>
<li><a href='docs.html'>Documentation</a>
<li><a href='download.html'>Download</a>
<li><a href='support.html'>Support</a>
<li><a href='prosupport.html'>Purchase</a>
</ul>
</div>
<div class="searchmenu" id="searchmenu">
<form method="GET" action="search">
<select name="s" id="searchtype">
<option value="d">Search Documentation</option>
<option value="c">Search Changelog</option>
</select>
<input type="text" name="q" id="searchbox" value="">
<input type="submit" value="Go">
</form>
</div>
</div>
<script>
function toggle_div(nm) {
var w = document.getElementById(nm);
if( w.style.display=="block" ){
w.style.display = "none";
}else{
w.style.display = "block";
}
}
function toggle_search() {
var w = document.getElementById("searchmenu");
if( w.style.display=="block" ){
w.style.display = "none";
} else {
w.style.display = "block";
setTimeout(function(){
document.getElementById("searchbox").focus()
}, 30);
}
}
function div_off(nm){document.getElementById(nm).style.display="none";}
window.onbeforeunload = function(e){div_off("submenu");}
/* Disable the Search feature if we are not operating from CGI, since */
/* Search is accomplished using CGI and will not work without it. */
if( !location.origin || !location.origin.match || !location.origin.match(/http/) ){
document.getElementById("search_menubutton").style.display = "none";
}
/* Used by the Hide/Show button beside syntax diagrams, to toggle the */
function hideorshow(btn,obj){
var x = document.getElementById(obj);
var b = document.getElementById(btn);
if( x.style.display!='none' ){
x.style.display = 'none';
b.innerHTML='show';
}else{
x.style.display = '';
b.innerHTML='hide';
}
return false;
}
var antiRobot = 0;
function antiRobotGo(){
if( antiRobot!=3 ) return;
antiRobot = 7;
var j = document.getElementById("mtimelink");
if(j && j.hasAttribute("data-href")) j.href=j.getAttribute("data-href");
}
function antiRobotDefense(){
document.body.onmousedown=function(){
antiRobot |= 2;
antiRobotGo();
document.body.onmousedown=null;
}
document.body.onmousemove=function(){
antiRobot |= 2;
antiRobotGo();
document.body.onmousemove=null;
}
setTimeout(function(){
antiRobot |= 1;
antiRobotGo();
}, 100)
antiRobotGo();
}
antiRobotDefense();
</script>
<h2>The Virtual Database Engine of SQLite</h2>
<blockquote><font color="red">
<b>Obsolete Documentation Warning:</b>
This document describes the virtual machine used in SQLite version 2.8.0.
The virtual machine in SQLite version 3.0 and 3.1 is similar in
concept but is now register-based instead of stack-based, has five
operands per opcode instead of three, and has a different set of
opcodes from those shown below. See the <a href="opcode.html">virtual machine instructions</a>
document for the current set of VDBE opcodes and a brief overview
of how the VDBE operates. This document is retained as an historical
reference.
</font></blockquote>
<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>)
and so it seems to touch most parts of the library. Even
parts of the code that do not directly interact with the VDBE
are usually in a supporting role. The VDBE really is the heart of
SQLite.</p>
<p>This article is a brief introduction to how the VDBE
works and in particular how the various VDBE instructions
(documented <a href="opcode.html">here</a>) work together
to do useful things with the database. The style is tutorial,
beginning with simple tasks and working toward solving more
complex problems. Along the way we will visit most
submodules in the SQLite library. After completing this tutorial,
you should have a pretty good understanding of how SQLite works
and will be ready to begin studying the actual source code.</p>
<h2>Preliminaries</h2>
<p>The VDBE implements a virtual computer that runs a program in
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 zero-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
Halt instruction, or (3) advances the program counter past the
last instruction of the program. When the VDBE completes execution,
all open database cursors are closed, all memory is freed, and
everything is popped from the stack.
So there are never any worries about memory leaks or
undeallocated resources.</p>
<p>If you have done any assembly language programming or have
worked with any kind of abstract machine before, all of these
details should be familiar to you. So let's jump right in and
start looking as some code.</p>
<a name="insert1"></a>
<h2>Inserting Records Into The Database</h2>
<p>We begin with a problem that can be solved using a VDBE program
that is only a few instructions long. Suppose we have an SQL
table that was created like this:</p>
<blockquote><pre>
CREATE TABLE examp(one text, two int);
</pre></blockquote>
<p>In words, we have a database table named "examp" that has two
columns of data named "one" and "two". Now suppose we want to insert a single
record into this table. Like this:</p>
<blockquote><pre>
INSERT INTO examp VALUES('Hello, World!',99);
</pre></blockquote>
<p>We can see the VDBE program that SQLite uses to implement this
INSERT using the <b>sqlite</b> command-line utility. First start
up <b>sqlite</b> on a new, empty database, then create the table.
Next change the output format of <b>sqlite</b> to a form that
is designed to work with VDBE program dumps by entering the
".explain" command.
Finally, enter the [INSERT] statement shown above, but precede the
[INSERT] with the special keyword [EXPLAIN]. The [EXPLAIN] keyword
will cause <b>sqlite</b> to print the VDBE program rather than
execute it. We have:</p>
<blockquote><tt>$ <b>sqlite test_database_1</b><br>
sqlite> <b>CREATE TABLE examp(one text, two int);</b><br>
sqlite> <b>.explain</b><br>
sqlite> <b>EXPLAIN INSERT INTO examp VALUES('Hello, World!',99);</b><br>
addr opcode p1 p2 p3 <br>
---- ------------ ----- ----- -----------------------------------<br>
0 Transaction 0 0 <br>
1 VerifyCookie 0 81 <br>
2 Transaction 1 0 <br>
3 Integer 0 0 <br>
4 OpenWrite 0 3 examp <br>
5 NewRecno 0 0 <br>
6 String 0 0 Hello, World! <br>
7 Integer 99 0 99 <br>
8 MakeRecord 2 0 <br>
9 PutIntKey 0 1 <br>
10 Close 0 0 <br>
11 Commit 0 0 <br>
12 Halt 0 0</tt></blockquote><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>
<blockquote><tt>0 Transaction 0 0 <br>
1 VerifyCookie 0 81 <br>
2 Transaction 1 0</tt></blockquote>
<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>
<blockquote><tt>3 Integer 0 0 <br>
4 OpenWrite 0 3 examp</tt></blockquote>
<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>
<blockquote><table border=2><tr><td align=left>(integer) 0</td></tr></table></blockquote>
<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>
<blockquote><tt>5 NewRecno 0 0</tt></blockquote>
<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>
<blockquote><table border=2><tr><td align=left>(integer) new record key</td></tr></table></blockquote><blockquote><tt>6 String 0 0 Hello, World!</tt></blockquote>
<p> The instruction <a href="opcode.html#String">String</a> pushes its
P3 operand onto the stack. Afterwards the stack looks like this:</p>
<blockquote><table border=2><tr><td align=left>(string) "Hello, World!"</td></tr><tr><td align=left>(integer) new record key</td></tr></table></blockquote><blockquote><tt>7 Integer 99 0 99</tt></blockquote>
<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>
<blockquote><table border=2><tr><td align=left>(integer) 99</td></tr><tr><td align=left>(string) "Hello, World!"</td></tr><tr><td align=left>(integer) new record key</td></tr></table></blockquote><blockquote><tt>8 MakeRecord 2 0</tt></blockquote>
<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>
<blockquote><table border=2><tr><td align=left>(record) "Hello, World!", 99</td></tr><tr><td align=left>(integer) new record key</td></tr></table></blockquote><blockquote><tt>9 PutIntKey 0 1</tt></blockquote>
<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>
<blockquote><tt>10 Close 0 0</tt></blockquote>
<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>
<blockquote><tt>11 Commit 0 0</tt></blockquote>
<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>
<blockquote><tt>12 Halt 0 0</tt></blockquote>
<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"></a>
<h2>Tracing VDBE Program Execution</h2>
<p>If the SQLite library is compiled without the NDEBUG preprocessor
macro, then the PRAGMA <a href="pragma.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>
<blockquote><tt>sqlite> <b>PRAGMA vdbe_trace=ON;</b><br>
0 Halt 0 0<br>
sqlite> <b>INSERT INTO examp VALUES('Hello, World!',99);</b><br>
0 Transaction 0 0<br>
1 VerifyCookie 0 81<br>
2 Transaction 1 0<br>
3 Integer 0 0<br>
Stack: i:0<br>
4 OpenWrite 0 3 examp<br>
5 NewRecno 0 0<br>
Stack: i:2<br>
6 String 0 0 Hello, World!<br>
Stack: t[Hello,.World!] i:2<br>
7 Integer 99 0 99<br>
Stack: si:99 t[Hello,.World!] i:2<br>
8 MakeRecord 2 0<br>
Stack: s[...Hello,.World!.99] i:2<br>
9 PutIntKey 0 1<br>
10 Close 0 0<br>
11 Commit 0 0<br>
12 Halt 0 0</tt></blockquote>
<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"></a>
<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>
<blockquote><tt>sqlite> <b>EXPLAIN SELECT * FROM examp;</b><br>
addr opcode p1 p2 p3 <br>
---- ------------ ----- ----- -----------------------------------<br>
0 ColumnName 0 0 one <br>
1 ColumnName 1 0 two <br>
2 Integer 0 0 <br>
3 OpenRead 0 3 examp <br>
4 VerifyCookie 0 81 <br>
5 Rewind 0 10 <br>
6 Column 0 0 <br>
7 Column 0 1 <br>
8 Callback 2 0 <br>
9 Next 0 6 <br>
10 Close 0 0 <br>
11 Halt 0 0</tt></blockquote>
<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
prototype:</p>
<blockquote><pre>
int Callback(void *pUserData, int nColumn, char *azData[], char *azColumnName[]);
</pre></blockquote>
<p>The SQLite library supplies the VDBE with a pointer to the callback function
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>
<blockquote><tt>0 ColumnName 0 0 one <br>
1 ColumnName 1 0 two</tt></blockquote>
<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>
<blockquote><tt>2 Integer 0 0 <br>
3 OpenRead 0 3 examp <br>
4 VerifyCookie 0 81</tt></blockquote>
<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>
<blockquote><tt>5 Rewind 0 10</tt></blockquote>
<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 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>
<blockquote><tt>6 Column 0 0 <br>
7 Column 0 1 <br>
8 Callback 2 0</tt></blockquote>
<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>
<blockquote><tt>9 Next 0 6</tt></blockquote>
<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>
<blockquote><tt>10 Close 0 0 <br>
11 Halt 0 0</tt></blockquote>
<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>
<a name="query2"></a>
<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>
<blockquote><pre>
SELECT one, two, one || two AS 'both'
FROM examp
WHERE one LIKE 'H%'
</pre></blockquote>
<p>This query is perhaps a bit contrived, but it does serve to
illustrate our points. The result will have three column with
names "one", "two", and "both". The first two columns are direct
copies of the two columns in the table and the third result
column is a string formed by concatenating the first and
second columns of the table.
Finally, the
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>
<blockquote><tt>addr opcode p1 p2 p3 <br>
---- ------------ ----- ----- -----------------------------------<br>
0 ColumnName 0 0 one<br>
1 ColumnName 1 0 two<br>
2 ColumnName 2 0 both<br>
3 Integer 0 0<br>
4 OpenRead 0 3 examp<br>
5 VerifyCookie 0 81<br>
6 Rewind 0 18<br>
7 String 0 0 H% <br>
8 Column 0 0<br>
9 Function 2 0 ptr(0x7f1ac0)<br>
10 IfNot 1 17<br>
11 Column 0 0<br>
12 Column 0 1<br>
13 Column 0 0<br>
14 Column 0 1<br>
15 Concat 2 0<br>
16 Callback 3 0<br>
17 Next 0 7<br>
18 Close 0 0<br>
19 Halt 0 0</tt></blockquote>
<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"></a>
<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>
<p>
<ol>
<li>Initialize the <b>azColumnName[]</b> array for the callback.</li>
<li>Open a cursor into the table to be queried.</li>
<li>For each record in the table, do:
<ol type="a">
<li>If the WHERE clause evaluates to FALSE, then skip the steps that
follow and continue to the next record.</li>
<li>Compute all columns for the current row of the result.</li>
<li>Invoke the callback function for the current row of the result.</li>
</ol>
<li>Close the cursor.</li>
</ol>
</p>
<p>This template will be expanded considerably as we consider
additional complications such as joins, compound selects, using
indices to speed the search, sorting, and aggregate functions
with and without GROUP BY and HAVING clauses.
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>
<blockquote><tt>addr opcode p1 p2 p3 <br>
---- ------------ ----- ----- -----------------------------------<br>
0 Transaction 1 0<br>
1 Transaction 0 0<br>
2 VerifyCookie 0 178<br>
3 Integer 0 0<br>
4 OpenRead 0 3 examp<br>
5 Rewind 0 12<br>
6 Column 0 1<br>
7 Integer 50 0 50<br>
8 Ge 1 11<br>
9 Recno 0 0<br>
10 ListWrite 0 0<br>
11 Next 0 6<br>
12 Close 0 0<br>
13 ListRewind 0 0<br>
14 Integer 0 0<br>
15 OpenWrite 0 3<br>
16 ListRead 0 20<br>
17 NotExists 0 19<br>
18 Delete 0 1<br>
19 Goto 0 16<br>
20 ListReset 0 0<br>
21 Close 0 0<br>
22 Commit 0 0<br>
23 Halt 0 0</tt></blockquote>
<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 implementation 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>
<blockquote><tt>0 Transaction 1 0<br>
1 Transaction 0 0<br>
2 VerifyCookie 0 178<br>
3 Integer 0 0<br>
4 OpenRead 0 3 examp</tt></blockquote>
<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>
<blockquote><tt>5 Rewind 0 12</tt></blockquote>
<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>
<blockquote><tt>6 Column 0 1<br>
7 Integer 50 0 50<br>
8 Ge 1 11</tt></blockquote>
<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>
<blockquote><table border=2><tr><td align=left>(integer) 50</td></tr><tr><td align=left>(record) current record for column "two" </td></tr></table></blockquote>
<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>
<blockquote><tt>9 Recno 0 0<br>
10 ListWrite 0 0</tt></blockquote>
<p>The <a href="opcode.html#Recno">Recno</a> instruction pushes onto the
stack an integer which is the first 4 bytes of 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>
<blockquote><tt>11 Next 0 6<br>
12 Close 0 0</tt></blockquote>
<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>
<blockquote><tt>13 ListRewind 0 0</tt></blockquote>
<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>
<blockquote><tt>14 Integer 0 0<br>
15 OpenWrite 0 3</tt></blockquote>
<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>
<blockquote><tt>16 ListRead 0 20<br>
17 NotExists 0 19<br>
18 Delete 0 1<br>
19 Goto 0 16</tt></blockquote>
<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 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>
<blockquote><table border=2><tr><td align=left>(integer) key for current record</td></tr></table></blockquote>
<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 through 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>
<blockquote><tt>20 ListReset 0 0<br>
21 Close 0 0<br>
22 Commit 0 0<br>
23 Halt 0 0</tt></blockquote>
<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
unnecessary, 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>
UPDATE examp SET one= '(' || one || ')' WHERE two < 50;
</pre></blockquote>
<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>
<blockquote><tt>addr opcode p1 p2 p3 <br>
---- ------------ ----- ----- -----------------------------------<br>
0 Transaction 1 0 <br>
1 Transaction 0 0 <br>
2 VerifyCookie 0 178 <br>
3 Integer 0 0 <br>
4 OpenRead 0 3 examp <br>
5 Rewind 0 12 <br>
6 Column 0 1 <br>
7 Integer 50 0 50 <br>
8 Ge 1 11 <br>
9 Recno 0 0 <br>
10 ListWrite 0 0 <br>
11 Next 0 6 <br>
12 Close 0 0 <br>
13 Integer 0 0 <br>
14 OpenWrite 0 3 <br>
15 ListRewind 0 0 <br>
16 ListRead 0 28 <br>
17 Dup 0 0 <br>
18 NotExists 0 16 <br>
19 String 0 0 ( <br>
20 Column 0 0 <br>
21 Concat 2 0 <br>
22 String 0 0 ) <br>
23 Concat 2 0 <br>
24 Column 0 1 <br>
25 MakeRecord 2 0 <br>
26 PutIntKey 0 1 <br>
27 Goto 0 16 <br>
28 ListReset 0 0 <br>
29 Close 0 0 <br>
30 Commit 0 0 <br>
31 Halt 0 0</tt></blockquote>
<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>
<blockquote><table border=2><tr><td align=left>(record) new data record</td></tr><tr><td align=left>(integer) key</td></tr></table></blockquote>
<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>
<h2>CREATE and DROP</h2>
<p>Using CREATE or DROP to create or destroy a table or index is
really the same as doing an INSERT or DELETE from the special
"sqlite_master" table, at least from the point of view of the VDBE.
The sqlite_master table is a special table that is automatically
created for every SQLite database. It looks like this:</p>
<blockquote><pre>
CREATE TABLE sqlite_master (
type TEXT, -- either "table" or "index"
name TEXT, -- name of this table or index
tbl_name TEXT, -- for indices: name of associated table
sql TEXT -- SQL text of the original CREATE statement
)
</pre></blockquote>
<p>Every table (except the "sqlite_master" table itself)
and every named index in an SQLite database has an entry
in the sqlite_master table. You can query this table using
a SELECT statement just like any other table. But you are
not allowed to directly change the table using UPDATE, INSERT,
or DELETE. Changes to sqlite_master have to occur using
the CREATE and DROP commands because SQLite also has to update
some of its internal data structures when tables and indices
are added or destroyed.</p>
<p>But from the point of view of the VDBE, a CREATE works
pretty much like an INSERT and a DROP works like a DELETE.
When the SQLite library opens to an existing database,
the first thing it does is a SELECT to read the "sql"
columns from all entries of the sqlite_master table.
The "sql" column contains the complete SQL text of the
CREATE statement that originally generated the index or
table. This text is fed back into the SQLite parser
and used to reconstruct the
internal data structures describing the index or table.</p>
<h2>Using Indexes To Speed Searching</h2>
<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);
</pre></blockquote>
<p>The VDBE code generated by the above statement looks like the
following:</p>
<blockquote><tt>addr opcode p1 p2 p3 <br>
---- ------------ ----- ----- -----------------------------------<br>
0 Transaction 1 0 <br>
1 Transaction 0 0 <br>
2 VerifyCookie 0 178 <br>
3 Integer 0 0 <br>
4 OpenWrite 0 2 <br>
5 NewRecno 0 0 <br>
6 String 0 0 index <br>
7 String 0 0 examp_idx1 <br>
8 String 0 0 examp <br>
9 CreateIndex 0 0 ptr(0x791380) <br>
10 Dup 0 0 <br>
11 Integer 0 0 <br>
12 OpenWrite 1 0 <br>
13 String 0 0 CREATE INDEX examp_idx1 ON examp(tw<br>
14 MakeRecord 5 0 <br>
15 PutIntKey 0 0 <br>
16 Integer 0 0 <br>
17 OpenRead 2 3 examp <br>
18 Rewind 2 24 <br>
19 Recno 2 0 <br>
20 Column 2 1 <br>
21 MakeIdxKey 1 0 n <br>
22 IdxPut 1 0 indexed columns are not unique <br>
23 Next 2 19 <br>
24 Close 2 0 <br>
25 Close 1 0 <br>
26 Integer 333 0 <br>
27 SetCookie 0 0 <br>
28 Close 0 0 <br>
29 Commit 0 0 <br>
30 Halt 0 0</tt></blockquote>
<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 any more
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>
<blockquote><tt>16 Integer 0 0 <br>
17 OpenRead 2 3 examp</tt></blockquote>
<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>
<blockquote><tt>18 Rewind 2 24 <br>
19 Recno 2 0 <br>
20 Column 2 1 <br>
21 MakeIdxKey 1 0 n <br>
22 IdxPut 1 0 indexed columns are not unique <br>
23 Next 2 19</tt></blockquote>
<p>Instructions 18 through 23 implement a loop over every row of the
table being indexed. For each table row, we first extract the integer
key for that row using Recno in instruction 19, then get the value of
the "two" column using Column in instruction 20.
The <a href="opcode.html#MakeIdxKey">MakeIdxKey</a> instruction at 21
converts data from the "two" column (which is on the top of the stack)
into a valid index key. For an index on a single column, this is
basically a no-op. But if the P1 operand to MakeIdxKey had been
greater than one multiple entries would have been popped from the stack
and converted into a single index key.
The <a href="opcode.html#IdxPut">IdxPut</a> instruction at 22 is what
actually creates the index entry. IdxPut pops two elements from the
stack. The top of the stack is used as a key to fetch an entry from the
index table. Then the integer which was second on stack is added to the
set of integers for that index and the new record is written back to the
database file. Note
that the same index entry can store multiple integers if there
are two or more table entries with the same value for the two
column.
</p>
<p>Now let's look at how this index will be used. Consider the
following query:</p>
<blockquote><pre>
SELECT * FROM examp WHERE two==50;
</pre></blockquote>
<p>SQLite generates the following VDBE code to handle this query:</p>
<blockquote><tt>addr opcode p1 p2 p3 <br>
---- ------------ ----- ----- -----------------------------------<br>
0 ColumnName 0 0 one <br>
1 ColumnName 1 0 two <br>
2 Integer 0 0 <br>
3 OpenRead 0 3 examp <br>
4 VerifyCookie 0 256 <br>
5 Integer 0 0 <br>
6 OpenRead 1 4 examp_idx1 <br>
7 Integer 50 0 50 <br>
8 MakeKey 1 0 n <br>
9 MemStore 0 0 <br>
10 MoveTo 1 19 <br>
11 MemLoad 0 0 <br>
12 IdxGT 1 19 <br>
13 IdxRecno 1 0 <br>
14 MoveTo 0 0 <br>
15 Column 0 0 <br>
16 Column 0 1 <br>
17 Callback 2 0 <br>
18 Next 1 11 <br>
19 Close 0 0 <br>
20 Close 1 0 <br>
21 Halt 0 0</tt></blockquote>
<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 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>
<blockquote><tt>addr opcode p1 p2 p3 <br>
---- ------------ ----- ----- -----------------------------------<br>
0 Transaction 1 0 <br>
1 Transaction 0 0 <br>
2 VerifyCookie 0 256 <br>
3 Integer 0 0 <br>
4 OpenWrite 0 3 examp <br>
5 Integer 0 0 <br>
6 OpenWrite 1 4 examp_idx1 <br>
7 NewRecno 0 0 <br>
8 String 0 0 Hello, World! <br>
9 Integer 99 0 99 <br>
10 Dup 2 1 <br>
11 Dup 1 1 <br>
12 MakeIdxKey 1 0 n <br>
13 IdxPut 1 0 <br>
14 MakeRecord 2 0 <br>
15 PutIntKey 0 1 <br>
16 Close 0 0 <br>
17 Close 1 0 <br>
18 Commit 0 0 <br>
19 Halt 0 0</tt></blockquote>
<p>At this point, you should understand the VDBE well enough to
figure out on your own how the above program works. So we will
not discuss it further in this text.</p>
<h2>Joins</h2>
<p>In a join, two or more tables are combined to generate a single
result. The result table consists of every possible combination
of rows from the tables being joined. The easiest and most natural
way to implement this is with nested loops.</p>
<p>Recall the query template discussed above where there was a
single loop that searched through every record of the table.
In a join we have basically the same thing except that there
are nested loops. For example, to join two tables, the query
template might look something like this:</p>
<p>
<ol>
<li>Initialize the <b>azColumnName[]</b> array for the callback.</li>
<li>Open two cursors, one to each of the two tables being queried.</li>
<li>For each record in the first table, do:
<ol type="a">
<li>For each record in the second table do:
<ol type="i">
<li>If the WHERE clause evaluates to FALSE, then skip the steps that
follow and continue to the next record.</li>
<li>Compute all columns for the current row of the result.</li>
<li>Invoke the callback function for the current row of the result.</li>
</ol></li>
</ol>
<li>Close both cursors.</li>
</ol>
</p>
<p>This template will work, but it is likely to be slow since we
are now dealing with an O(N<sup>2</sup>) loop. But it often works
out that the WHERE clause can be factored into terms and that one or
more of those terms will involve only columns in the first table.
When this happens, we can factor part of the WHERE clause test out of
the inner loop and gain a lot of efficiency. So a better template
would be something like this:</p>
<p>
<ol>
<li>Initialize the <b>azColumnName[]</b> array for the callback.</li>
<li>Open two cursors, one to each of the two tables being queried.</li>
<li>For each record in the first table, do:
<ol type="a">
<li>Evaluate terms of the WHERE clause that only involve columns from
the first table. If any term is false (meaning that the whole
WHERE clause must be false) then skip the rest of this loop and
continue to the next record.</li>
<li>For each record in the second table do:
<ol type="i">
<li>If the WHERE clause evaluates to FALSE, then skip the steps that
follow and continue to the next record.</li>
<li>Compute all columns for the current row of the result.</li>
<li>Invoke the callback function for the current row of the result.</li>
</ol></li>
</ol>
<li>Close both cursors.</li>
</ol>
</p>
<p>Additional speed-up can occur if an index can be used to speed
the search of either or the two loops.</p>
<p>SQLite always constructs the loops in the same order as the
tables appear in the FROM clause of the SELECT statement. The
left-most table becomes the outer loop and the right-most table
becomes the inner loop. It is possible, in theory, to reorder
the loops in some circumstances to speed the evaluation of the
join. But SQLite does not attempt this optimization.</p>
<p>You can see how SQLite constructs nested loops in the following
example:</p>
<blockquote><pre>
CREATE TABLE examp2(three int, four int);
SELECT * FROM examp, examp2 WHERE two<50 AND four==two;
</pre></blockquote>
<blockquote><tt>addr opcode p1 p2 p3 <br>
---- ------------ ----- ----- -----------------------------------<br>
0 ColumnName 0 0 examp.one <br>
1 ColumnName 1 0 examp.two <br>
2 ColumnName 2 0 examp2.three <br>
3 ColumnName 3 0 examp2.four <br>
4 Integer 0 0 <br>
5 OpenRead 0 3 examp <br>
6 VerifyCookie 0 909 <br>
7 Integer 0 0 <br>
8 OpenRead 1 5 examp2 <br>
9 Rewind 0 24 <br>
10 Column 0 1 <br>
11 Integer 50 0 50 <br>
12 Ge 1 23 <br>
13 Rewind 1 23 <br>
14 Column 1 1 <br>
15 Column 0 1 <br>
16 Ne 1 22 <br>
17 Column 0 0 <br>
18 Column 0 1 <br>
19 Column 1 0 <br>
20 Column 1 1 <br>
21 Callback 4 0 <br>
22 Next 1 14 <br>
23 Next 0 10 <br>
24 Close 0 0 <br>
25 Close 1 0 <br>
26 Halt 0 0</tt></blockquote>
<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>
<blockquote><tt>addr opcode p1 p2 p3 <br>
---- ------------ ----- ----- -----------------------------------<br>
0 ColumnName 0 0 one <br>
1 ColumnName 1 0 two <br>
2 Integer 0 0 <br>
3 OpenRead 0 3 examp <br>
4 VerifyCookie 0 909 <br>
5 Rewind 0 14 <br>
6 Column 0 0 <br>
7 Column 0 1 <br>
8 SortMakeRec 2 0 <br>
9 Column 0 0 <br>
10 Column 0 1 <br>
11 SortMakeKey 2 0 D+ <br>
12 SortPut 0 0 <br>
13 Next 0 6 <br>
14 Close 0 0 <br>
15 Sort 0 0 <br>
16 SortNext 0 19 <br>
17 SortCallback 2 0 <br>
18 Goto 0 16 <br>
19 SortReset 0 0 <br>
20 Halt 0 0</tt></blockquote>
<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
each record. Finally, the sorter is closed at instruction 19.</p>
<h2>Aggregate Functions And The GROUP BY and HAVING Clauses</h2>
<p>To compute aggregate functions, the VDBE implements a special
data structure and instructions for controlling that data structure.
The data structure is an unordered set of buckets, where each bucket
has a key and one or more memory locations. Within the query
loop, the GROUP BY clause is used to construct a key and the bucket
with that key is brought into focus. A new bucket is created with
the key if one did not previously exist. Once the bucket is in
focus, the memory locations of the bucket are used to accumulate
the values of the various aggregate functions. After the query
loop terminates, each bucket is visited once to generate a
single row of the results.</p>
<p>An example will help to clarify this concept. Consider the
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>
<blockquote><tt>addr opcode p1 p2 p3 <br>
---- ------------ ----- ----- -----------------------------------<br>
0 ColumnName 0 0 three <br>
1 ColumnName 1 0 min(three+four)+avg(four) <br>
2 AggReset 0 3 <br>
3 AggInit 0 1 ptr(0x7903a0) <br>
4 AggInit 0 2 ptr(0x790700) <br>
5 Integer 0 0 <br>
6 OpenRead 0 5 examp2 <br>
7 VerifyCookie 0 909 <br>
8 Rewind 0 23 <br>
9 Column 0 0 <br>
10 MakeKey 1 0 n <br>
11 AggFocus 0 14 <br>
12 Column 0 0 <br>
13 AggSet 0 0 <br>
14 Column 0 0 <br>
15 Column 0 1 <br>
16 Add 0 0 <br>
17 Integer 1 0 <br>
18 AggFunc 0 1 ptr(0x7903a0) <br>
19 Column 0 1 <br>
20 Integer 2 0 <br>
21 AggFunc 0 1 ptr(0x790700) <br>
22 Next 0 9 <br>
23 Close 0 0 <br>
24 AggNext 0 31 <br>
25 AggGet 0 0 <br>
26 AggGet 0 1 <br>
27 AggGet 0 2 <br>
28 Add 0 0 <br>
29 Callback 2 0 <br>
30 Goto 0 24 <br>
31 Noop 0 0 <br>
32 Halt 0 0</tt></blockquote>
<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 consecutive
loops makes it much easier to understand the difference between
a WHERE clause and a HAVING clause in SQL query statement. The
WHERE clause is a restriction on the first loop and the HAVING
clause is a restriction on the second loop. You can see this
by adding both a WHERE and a HAVING clause to our example query:</p>
<blockquote><pre>
SELECT three, min(three+four)+avg(four)
FROM examp2
WHERE three>four
GROUP BY three
HAVING avg(four)<10;
</pre></blockquote>
<blockquote><tt>addr opcode p1 p2 p3 <br>
---- ------------ ----- ----- -----------------------------------<br>
0 ColumnName 0 0 three <br>
1 ColumnName 1 0 min(three+four)+avg(four) <br>
2 AggReset 0 3 <br>
3 AggInit 0 1 ptr(0x7903a0) <br>
4 AggInit 0 2 ptr(0x790700) <br>
5 Integer 0 0 <br>
6 OpenRead 0 5 examp2 <br>
7 VerifyCookie 0 909 <br>
8 Rewind 0 26 <br>
9 Column 0 0 <br>
10 Column 0 1 <br>
11 Le 1 25 <br>
12 Column 0 0 <br>
13 MakeKey 1 0 n <br>
14 AggFocus 0 17 <br>
15 Column 0 0 <br>
16 AggSet 0 0 <br>
17 Column 0 0 <br>
18 Column 0 1 <br>
19 Add 0 0 <br>
20 Integer 1 0 <br>
21 AggFunc 0 1 ptr(0x7903a0) <br>
22 Column 0 1 <br>
23 Integer 2 0 <br>
24 AggFunc 0 1 ptr(0x790700) <br>
25 Next 0 9 <br>
26 Close 0 0 <br>
27 AggNext 0 37 <br>
28 AggGet 0 2 <br>
29 Integer 10 0 10 <br>
30 Ge 1 27 <br>
31 AggGet 0 0 <br>
32 AggGet 0 1 <br>
33 AggGet 0 2 <br>
34 Add 0 0 <br>
35 Callback 2 0 <br>
36 Goto 0 27 <br>
37 Noop 0 0 <br>
38 Halt 0 0</tt></blockquote>
<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.
And, a SELECT statement that returns a single-column, multi-row result
can be used as the right-hand operand of the IN and NOT IN operators.
We will begin this section with an example of the first kind of nesting,
where a single-row, single-column SELECT is used as a term in an expression
of another SELECT. Here is our example:</p>
<blockquote><pre>
SELECT * FROM examp
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>
<blockquote><tt>addr opcode p1 p2 p3 <br>
---- ------------ ----- ----- -----------------------------------<br>
0 String 0 0 <br>
1 MemStore 0 1 <br>
2 Integer 0 0 <br>
3 OpenRead 1 5 examp2 <br>
4 VerifyCookie 0 909 <br>
5 Rewind 1 13 <br>
6 Column 1 1 <br>
7 Integer 5 0 5 <br>
8 Ne 1 12 <br>
9 Column 1 0 <br>
10 MemStore 0 1 <br>
11 Goto 0 13 <br>
12 Next 1 6 <br>
13 Close 1 0 <br>
14 ColumnName 0 0 one <br>
15 ColumnName 1 0 two <br>
16 Integer 0 0 <br>
17 OpenRead 0 3 examp <br>
18 Rewind 0 26 <br>
19 Column 0 1 <br>
20 MemLoad 0 0 <br>
21 Eq 1 25 <br>
22 Column 0 0 <br>
23 Column 0 1 <br>
24 Callback 2 0 <br>
25 Next 0 19 <br>
26 Close 0 0 <br>
27 Halt 0 0</tt></blockquote>
<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>
<blockquote><tt>addr opcode p1 p2 p3 <br>
---- ------------ ----- ----- -----------------------------------<br>
0 OpenTemp 1 1 <br>
1 Integer 0 0 <br>
2 OpenRead 2 5 examp2 <br>
3 VerifyCookie 0 909 <br>
4 Rewind 2 10 <br>
5 Column 2 0 <br>
6 IsNull -1 9 <br>
7 String 0 0 <br>
8 PutStrKey 1 0 <br>
9 Next 2 5 <br>
10 Close 2 0 <br>
11 ColumnName 0 0 one <br>
12 ColumnName 1 0 two <br>
13 Integer 0 0 <br>
14 OpenRead 0 3 examp <br>
15 Rewind 0 25 <br>
16 Column 0 1 <br>
17 NotNull -1 20 <br>
18 Pop 1 0 <br>
19 Goto 0 24 <br>
20 NotFound 1 24 <br>
21 Column 0 0 <br>
22 Column 0 1 <br>
23 Callback 2 0 <br>
24 Next 0 16 <br>
25 Close 0 0 <br>
26 Halt 0 0</tt></blockquote>
<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>
<blockquote><tt>addr opcode p1 p2 p3 <br>
---- ------------ ----- ----- -----------------------------------<br>
0 OpenTemp 0 1 <br>
1 KeyAsData 0 1 <br>
2 Integer 0 0 <br>
3 OpenRead 1 3 examp <br>
4 VerifyCookie 0 909 <br>
5 Rewind 1 11 <br>
6 Column 1 1 <br>
7 MakeRecord 1 0 <br>
8 String 0 0 <br>
9 PutStrKey 0 0 <br>
10 Next 1 6 <br>
11 Close 1 0 <br>
12 Integer 0 0 <br>
13 OpenRead 2 5 examp2 <br>
14 Rewind 2 20 <br>
15 Column 2 1 <br>
16 MakeRecord 1 0 <br>
17 NotFound 0 19 <br>
18 Delete 0 0 <br>
19 Next 2 15 <br>
20 Close 2 0 <br>
21 ColumnName 0 0 four <br>
22 Rewind 0 26 <br>
23 Column 0 0 <br>
24 Callback 1 0 <br>
25 Next 0 23 <br>
26 Close 0 0 <br>
27 Halt 0 0</tt></blockquote>
<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 initializes 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 initializes 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
example, we have shown how sorting is accomplished on a simple query
and we have shown how to implement a compound query. But we did
not give an example of sorting in a compound query. This is because
sorting a compound query does not introduce any new concepts: it
merely combines two previous ideas (sorting and compounding)
in the same VDBE program.</p>
<p>For additional information on how the SQLite library
functions, the reader is directed to look at the SQLite source
code directly. If you understand the material in this article,
you should not have much difficulty in following the sources.
Serious students of the internals of SQLite will probably
also want to make a careful study of the VDBE opcodes
as documented <a href="opcode.html">here</a>. Most of the
opcode documentation is extracted from comments in the source
code using a script so you can also get information about the
various opcodes directly from the <b>vdbe.c</b> source file.
If you have successfully read this far, you should have little
difficulty understanding the rest.</p>
<p>If you find errors in either the documentation or the code,
feel free to fix them and/or contact the author at
<a href="mailto:drh@hwaci.com">drh@hwaci.com</a>. Your bug fixes or
suggestions are always welcomed.</p>
<p align="center"><small><i>This page last modified on <a href="https://sqlite.org/docsrc/honeypot" id="mtimelink" data-href="https://sqlite.org/docsrc/finfo/pages/vdbe.in?m=df423c1de68a1a915">2020-04-14 16:00:55</a> UTC </small></i></p>
|
