Debian Codegraph @

www/whybytecode.html

raw
1 <!DOCTYPE html>
2 <html><head>
3 <meta name="viewport" content="width=device-width, initial-scale=1.0">
4 <meta http-equiv="content-type" content="text/html; charset=UTF-8">
5 <link href="sqlite.css" rel="stylesheet">
6 <title>Why SQLite Uses Bytecode</title>
7 <!-- path= -->
8 </head>
9 <body>
10 <div class=nosearch>
11 <a href="index.html">
12 <img class="logo" src="images/sqlite370_banner.svg" alt="SQLite" border="0">
13 </a>
14 <div><!-- IE hack to prevent disappearing logo --></div>
15 <div class="tagline desktoponly">
16 Small. Fast. Reliable.<br>Choose any three.
17 </div>
18 <div class="menu mainmenu">
19 <ul>
20 <li><a href="index.html">Home</a>
21 <li class='mobileonly'><a href="javascript:void(0)" onclick='toggle_div("submenu")'>Menu</a>
22 <li class='wideonly'><a href='about.html'>About</a>
23 <li class='desktoponly'><a href="docs.html">Documentation</a>
24 <li class='desktoponly'><a href="download.html">Download</a>
25 <li class='wideonly'><a href='copyright.html'>License</a>
26 <li class='desktoponly'><a href="support.html">Support</a>
27 <li class='desktoponly'><a href="prosupport.html">Purchase</a>
28 <li class='search' id='search_menubutton'>
29 <a href="javascript:void(0)" onclick='toggle_search()'>Search</a>
30 </ul>
31 </div>
32 <div class="menu submenu" id="submenu">
33 <ul>
34 <li><a href='about.html'>About</a>
35 <li><a href='docs.html'>Documentation</a>
36 <li><a href='download.html'>Download</a>
37 <li><a href='support.html'>Support</a>
38 <li><a href='prosupport.html'>Purchase</a>
39 </ul>
40 </div>
41 <div class="searchmenu" id="searchmenu">
42 <form method="GET" action="search">
43 <select name="s" id="searchtype">
44 <option value="d">Search Documentation</option>
45 <option value="c">Search Changelog</option>
46 </select>
47 <input type="text" name="q" id="searchbox" value="">
48 <input type="submit" value="Go">
49 </form>
50 </div>
51 </div>
52 <script>
53 function toggle_div(nm) {
54 var w = document.getElementById(nm);
55 if( w.style.display=="block" ){
56 w.style.display = "none";
57 }else{
58 w.style.display = "block";
59 }
60 }
61 function toggle_search() {
62 var w = document.getElementById("searchmenu");
63 if( w.style.display=="block" ){
64 w.style.display = "none";
65 } else {
66 w.style.display = "block";
67 setTimeout(function(){
68 document.getElementById("searchbox").focus()
69 }, 30);
70 }
71 }
72 function div_off(nm){document.getElementById(nm).style.display="none";}
73 window.onbeforeunload = function(e){div_off("submenu");}
74 /* Disable the Search feature if we are not operating from CGI, since */
75 /* Search is accomplished using CGI and will not work without it. */
76 if( !location.origin || !location.origin.match || !location.origin.match(/http/) ){
77 document.getElementById("search_menubutton").style.display = "none";
78 }
79 /* Used by the Hide/Show button beside syntax diagrams, to toggle the */
80 function hideorshow(btn,obj){
81 var x = document.getElementById(obj);
82 var b = document.getElementById(btn);
83 if( x.style.display!='none' ){
84 x.style.display = 'none';
85 b.innerHTML='show';
86 }else{
87 x.style.display = '';
88 b.innerHTML='hide';
89 }
90 return false;
91 }
92 var antiRobot = 0;
93 function antiRobotGo(){
94 if( antiRobot!=3 ) return;
95 antiRobot = 7;
96 var j = document.getElementById("mtimelink");
97 if(j && j.hasAttribute("data-href")) j.href=j.getAttribute("data-href");
98 }
99 function antiRobotDefense(){
100 document.body.onmousedown=function(){
101 antiRobot |= 2;
102 antiRobotGo();
103 document.body.onmousedown=null;
104 }
105 document.body.onmousemove=function(){
106 antiRobot |= 2;
107 antiRobotGo();
108 document.body.onmousemove=null;
109 }
110 setTimeout(function(){
111 antiRobot |= 1;
112 antiRobotGo();
113 }, 100)
114 antiRobotGo();
115 }
116 antiRobotDefense();
117 </script>
118 <div class=fancy>
119 <div class=nosearch>
120 <div class="fancy_title">
121 Why SQLite Uses Bytecode
122 </div>
123 <details class="fancy_toc">
124 <summary>Table Of Contents</summary>
125 <div id="toc_sub"><div class="fancy-toc1"><a href="#introduction">1. Introduction</a></div>
126 <div class="fancy-toc2"><a href="#how_to_provide_feedback">1.1. How To Provide Feedback</a></div>
127 <div class="fancy-toc2"><a href="#definition_of_bytecode_">1.2. Definition Of "Bytecode"</a></div>
128 <div class="fancy-toc2"><a href="#definition_of_abstract_syntax_tree_or_ast_">1.3. Definition Of "Abstract Syntax Tree" or "AST"</a></div>
129 <div class="fancy-toc2"><a href="#dataflow_programming">1.4. Dataflow Programming</a></div>
130 <div class="fancy-toc1"><a href="#advantages_to_compiling_into_bytecode">2. Advantages To Compiling Into Bytecode</a></div>
131 <div class="fancy-toc2"><a href="#bytecode_is_easier_to_understand">2.1. Bytecode Is Easier To Understand</a></div>
132 <div class="fancy-toc2"><a href="#bytecode_is_easier_to_debug">2.2. Bytecode Is Easier To Debug</a></div>
133 <div class="fancy-toc2"><a href="#bytecode_can_be_run_incrementally">2.3. Bytecode Can Be Run Incrementally</a></div>
134 <div class="fancy-toc2"><a href="#bytecode_is_smaller">2.4. Bytecode Is Smaller</a></div>
135 <div class="fancy-toc2"><a href="#bytecode_is_faster">2.5. Bytecode Is Faster</a></div>
136 <div class="fancy-toc1"><a href="#advantages_of_compiling_into_a_tree_of_objects">3. Advantages Of Compiling Into A Tree Of Objects</a></div>
137 <div class="fancy-toc2"><a href="#query_planning_decisions_can_be_deferred_until_runtime">3.1. Query Planning Decisions Can Be Deferred Until Runtime</a></div>
138 <div class="fancy-toc2"><a href="#dataflow_programs_are_easy_to_parallelize">3.2. Dataflow Programs Are Easy To Parallelize</a></div>
139 </div>
140 </details>
141 </div>
142
143
144
145
146
147 <h1 id="introduction"><span>1. </span>Introduction</h1>
148
149 <p>Every SQL database engine works in roughly the same way: It first
150 translates the input SQL text into a "prepared statement". Then it "executes"
151 the prepared statement to generate a result.
152
153 </p><p>A prepared statement is an object that represents the steps needed
154 to accomplish the input SQL. Or, to think of it in another way,
155 the prepared statement is the SQL statement translated into a form that is
156 more easily understood by the computer.
157
158 </p><p>In SQLite, a prepared statement is an instance of the
159 <a href="c3ref/stmt.html">sqlite3_stmt object</a>. In other systems, the prepared
160 statement is usually an internal data structure that is not directly visible to
161 the application programmer. Developers of other SQL database engines
162 do not necessarily call these objects "prepared statements".
163 But such objects exist, whatever they might be called.
164 This paper will use the term "prepared statement".
165
166 </p><p>There are countless ways of implementing a prepared statement. This
167 paper will look at the two most common methods:
168
169 </p><ol>
170 <li><p>
171 <b>Bytecode</b> &rarr; The input SQL is translated into a virtual machine language
172 that is then run by a virtual machine interpreter. This is the technique
173 used by SQLite.
174
175 </p></li><li><p>
176 <b>Tree-Of-Objects</b> &rarr; The input SQL is translated into a tree of objects
177 that represent the processing to be done. The SQL is executed by walking this
178 tree. This is the technique used by MySQL and PostgreSQL.
179 </p></li></ol>
180
181 <p>
182 There are advantages and disadvantages to each of these representations of
183 a prepared statement. The purpose of this paper is to articulate some of those
184 advantages and disadvantages.
185
186 </p><h2 id="how_to_provide_feedback"><span>1.1. </span>How To Provide Feedback</h2>
187
188 <p>
189 This document is written from the perspective of the original author of SQLite.
190 If you disagree with any of the opinions offered in this document, you are
191 welcomed to offer corrections and/or contrary views on the
192 <a href="https://sqlite.org/forum">SQLite Forum</a>. Or you can email the author
193 directly.
194
195 </p><h2 id="definition_of_bytecode_"><span>1.2. </span>Definition Of "Bytecode"</h2>
196
197 <p>The <a href="opcode.html">bytecode generated by SQLite</a> might be a little different from what
198 many readers think of as bytecode. The bytecode used (for example) by the
199 <a href="https://en.wikipedia.org/wiki/Java_virtual_machine">Java virtual machine</a> or
200 by <a href="https://en.wikipedia.org/wiki/WebAssembly">WebAssembly</a> consists almost
201 entirely of low-level operations, similar to what physical CPUs implement:
202 basic math operators, comparisons, conditional jumps, and
203 instructions to move content between different memory locations. SQLite bytecode
204 has these kinds of low-level instructions, too. But SQLite bytecode also contains
205 some high-level operations that are specific to the needs of a database engine.
206 Here are just a few examples:
207
208 </p><p>
209 </p><ul>
210 <li><p><b>OP_Column</b> &rarr; Extract the value from the N-th column of the
211 database row that a particular cursor is currently pointing at.
212 </p></li><li><p><b>OP_CreateBtree</b> &rarr; Allocate space for a new B-Tree in the
213 database file.
214 </p></li><li><p><b>OP_ParseSchema</b> &rarr; Reread and reparse all or part of the
215 <a href="schematab.html">sqlite_schema table</a> and refresh internal symbol tables accordingly.
216 </p></li><li><p><b>OP_SeekGE</b> &rarr; Move a cursor on a particular B-Tree to the first
217 entry that is greater than or equal to a given key.
218 </p></li><li><p><b>OP_Next</b> &rarr; Advance a cursor on a particular B-Tree to the next
219 entry in the B-Tree and jump, or fall through if there are no more entries in that
220 B-Tree.
221 </p></li></ul>
222
223 <p>In other words, the "bytecode" used by SQLite is not so much a set of CPU
224 instructions as it is a list of database primitives that are to be run
225 in a particular order.
226
227 </p><h2 id="definition_of_abstract_syntax_tree_or_ast_"><span>1.3. </span>Definition Of "Abstract Syntax Tree" or "AST"</h2>
228
229 <p>
230 An "<a href="https://en.wikipedia.org/wiki/Abstract_syntax_tree">Abstract Syntax Tree</a>" or AST
231 is a data structure that describes a program or statement in some kind of formal
232 language. In our context, the formal language is SQL. An AST is typically
233 implemented as a tree of objects where each object represents one small part of
234 the overall SQL statement. ASTs emerge naturally from parsers for formal languages.
235 The usual technique is to use an
236 <a href="https://en.wikipedia.org/wiki/LALR_parser">LALR(1) parser</a>.
237 With such a parser, each terminal
238 symbol holds metadata that will become a leaf of the AST, and each non-terminal
239 symbol holds metadata that will become a sub-branch of the overall AST.
240 As rules of the grammar are "reduced" by the parser, new nodes of the AST are
241 allocated and connected to subnodes.
242 After the parse completes, the start-symbol of the grammar is left holding the
243 root of the AST.
244
245 </p><p>An AST is a tree of objects. But an AST is not a suitable form for
246 a prepared statement. After being generated, an AST first needs to be
247 transformed in various ways before it can be executed. Symbols need to be
248 resolved. Semantic rules need to be checked. Optimizations need to be
249 applied that transform input SQL statements into different forms that
250 execute more quickly. Finally, the AST needs to be translated into an
251 alternative representation that is more amenable to execution.
252
253 </p><p>Some people refer to the tree of objects that is used as the
254 executable form for MySQL and PostgreSQL as an AST. This is probably a
255 misuse of the term "AST", because by the time the tree of objects is
256 ready to be executed, it has been changed so much that it has little
257 resemblance to the original SQL text. The confusion arises in part because
258 both the final prepared statement object and the original AST are both
259 trees of objects. The usual technique is for the original AST that comes
260 directly out of the parser to be transformed little by little, in multiple
261 passes, until at the end it is fully converted into an tree of objects
262 that is no longer strictly an AST but that can be evaluated to
263 generate a result. There is not necessarily a clear point during this
264 process when the tree-of-objects ceases to be an AST and becomes a
265 prepared statement instead. And because there is no clear boundary between an
266 AST and a prepared statement, people often refer to a prepared statement
267 that is represented as a tree of objects as an "AST", even though that
268 description is not precise.
269
270 </p><h2 id="dataflow_programming"><span>1.4. </span>Dataflow Programming</h2>
271
272 <p><a href="https://en.wikipedia.org/wiki/Dataflow_programming">Dataflow programming</a>
273 is a style of programming in which individual nodes specialize in doing
274 one small part of the overall computation. Each node receives inputs from
275 other nodes and sends its output to other nodes. Thus the nodes form a
276 directed graph that carry inputs into outputs.
277
278 </p><p>
279 A "dataflow program" is perhaps a better description than "AST" for
280 the tree of objects that an SQL database engine uses as a prepared statement.
281
282 </p><h1 id="advantages_to_compiling_into_bytecode"><span>2. </span>Advantages To Compiling Into Bytecode</h1>
283
284 <p>SQLite compiles to bytecode, and the SQLite developers are very happy
285 with this approach. Here is why:
286
287 </p><h2 id="bytecode_is_easier_to_understand"><span>2.1. </span>Bytecode Is Easier To Understand</h2>
288
289 <p>A flat list of opcodes can be easily printed to see exactly
290 how an SQL statement is being implemented. This is what happens in SQLite
291 when you preface an SQL statement with the "EXPLAIN" keyword: Instead of
292 actually running the SQL, the result is a listing of the bytecode
293 that would have been used to implement that SQL.
294
295 </p><p>Bytecode lends itself to this because a bytecode program is easily
296 represented as a table. In SQLite bytecode, each instruction
297 has one opcode and five operands. Thus a prepared statement can be
298 rendered as if it were a query against a six-column table.
299
300 </p><p>A tree-of-objects representation is more difficult to publish in
301 a human-readable form. The objects that comprise the tree tend to
302 all be very different, and thus it is tricky to come up with a
303 consistent and simple table representation with which to display
304 the objects. Any such table representation that you do come up
305 with would almost certainly have more than six columns, probably many more.
306 The problem of rendering a tree-of-objects as a table is sufficiently
307 difficult that nobody does it, as far as I know. Hence, no
308 tree-of-objects database engine provides the level
309 of detail in their "EXPLAIN" output that SQLite provides.
310
311 </p><h2 id="bytecode_is_easier_to_debug"><span>2.2. </span>Bytecode Is Easier To Debug</h2>
312
313 <p>Bytecode provides a clear separation between front-end parsing and
314 analysis and back-end evaluation of an SQL statement. When problems arise
315 (incorrect answers and/or poor performance), the developers can examine
316 the bytecode to quickly determine if the source of the trouble is either the
317 front-end analysis or the back-end data storage section of the product.
318
319 </p><p>In debugging builds of SQLite, the <a href="pragma.html#pragma_vdbe_trace">PRAGMA vdbe_trace=ON;</a> command will
320 cause a trace of the bytecode execution to appear on the console.
321
322 </p><h2 id="bytecode_can_be_run_incrementally"><span>2.3. </span>Bytecode Can Be Run Incrementally</h2>
323
324 <p>
325 SQL statements written in bytecode can be evaluated incrementally.
326 For example, a statement can be run until it generates just its first
327 row of output. The statement then pauses until it is stepped again.
328 It is not necessary to run the statement to completion before examining
329 the first row of output.
330
331 </p><p>
332 This is more difficult to achieve in a tree-of-objects design. When
333 the prepared statement is a tree-of-objects, execution is normally
334 accomplished by walking the tree. To pause the statement in the middle
335 of a computation means unwinding the stack back up to the caller, all
336 the while saving enough state to resume evaluation where it last left
337 off. This is not impossible to do, but is sufficiently difficult that
338 I have never seen it actually done.
339
340 </p><p>
341 Most SQL database engines do not really need to do incremental
342 execution of prepared statements because most SQL database engines
343 are client/server. In client/server engines, a single SQL statement is sent
344 to the server, then the complete reply comes back over the wire
345 all at once. Thus each statement runs to completion in a single go.
346 But SQLite is not client/server. SQLite is a library
347 that runs in the same address space and using the same stack as the
348 application. Being able to easily and reliably perform incremental
349 execution of an SQL statement is important to SQLite.
350
351 </p><h2 id="bytecode_is_smaller"><span>2.4. </span>Bytecode Is Smaller</h2>
352
353 <p>
354 The bytecode generated by SQLite is usually smaller than the corresponding
355 AST coming out of the parser. During initial processing of SQL text
356 (during the call to <a href="c3ref/prepare.html">sqlite3_prepare()</a> and similar) both the AST and the
357 bytecode exist in memory at the same time, so more memory is used then.
358 But that is a transient state. The AST
359 is quickly discarded and its memory recycled, even before the call to
360 <a href="c3ref/prepare.html">sqlite3_prepare()</a> returns, so the resulting <a href="c3ref/stmt.html">prepared statement</a> ends
361 up consuming less memory in its bytecode representation than it did as an AST.
362 This is important because calls to <a href="c3ref/prepare.html">sqlite3_prepare()</a> are transient, but
363 prepared statements are often cached for possible reuse and persist in memory
364 for a long time.
365
366 </p><h2 id="bytecode_is_faster"><span>2.5. </span>Bytecode Is Faster</h2>
367
368 <p>
369 I <i>believe</i> that a bytecode representation of a prepared statement
370 runs faster, because fewer decisions need to be made for each step of
371 the computation. Emphasis on "believe" in the previous sentence
372 &rarr; it is difficult to verify
373 this claim experimentally since nobody has ever put in the multiple years
374 of effort necessary to generate equivalent bytecode and tree-of-object
375 representations of a prepared statement to see which one actually runs faster.
376 We do know that <a href="fasterthanfs.html">SQLite is very fast</a>, but we
377 do not have good side-by-side comparisons with other SQL databases since
378 the other databases spend a lot of time doing client/server message processing,
379 and it is difficult to untangle the message round-trip overhead from the
380 actual processing time.
381
382 </p><h1 id="advantages_of_compiling_into_a_tree_of_objects"><span>3. </span>Advantages Of Compiling Into A Tree Of Objects</h1>
383
384 <p>The SQLite developers think that the bytecode approach is
385 best, at least for the use cases the SQLite tries to fill, but the
386 tree-of-objects approach to processing SQL does have some advantages over
387 bytecode. There are always tradeoffs.
388
389 </p><h2 id="query_planning_decisions_can_be_deferred_until_runtime"><span>3.1. </span>Query Planning Decisions Can Be Deferred Until Runtime</h2>
390
391 <p>
392 When a prepared statement is bytecode, once the bytecode has been generated,
393 the algorithm is fixed and cannot be subsequently changed without completely
394 rewriting the bytecode.
395 This is not the case with a tree-of-objects prepared
396 statement. A tree-of-objects is easier to modify on-the-fly. The query
397 plan is mutable and can be tweaked as it is running, based on the progress
398 of the query. Thus a query can be dynamically self-tuning.
399
400 </p><h2 id="dataflow_programs_are_easy_to_parallelize"><span>3.2. </span>Dataflow Programs Are Easy To Parallelize</h2>
401
402 <p>In a dataflow program, each processing node can be assigned to a
403 different thread. There needs to be some kind of threadsafe queuing
404 mechanism for transferring intermediate results from one node to the
405 next. But no synchronization primitives are typically needed within
406 each node of the program. Node schedule is trivial: A node becomes
407 eligible to run when it has data available and there is space in its
408 output queue.
409
410 </p><p>This is an important consideration for database engines that are
411 designed to run large analytic queries
412 (<a href="https://en.wikipedia.org/wiki/Online_analytical_processing">OLAP</a>)
413 on large multi-core servers.
414 The primary focus of SQLite is transaction processing
415 (<a href="https://en.wikipedia.org/wiki/Online_transaction_processing">OLTP</a>)
416 on the internet-of-things, so there is less need to
417 represent prepared statements as dataflow programs in SQLite.
418 </p><p align="center"><small><i>This page was last updated on 2025-05-09 15:56:17Z </small></i></p>
419