Debian Codegraph @

www/howitworks.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>How SQLite Works</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 How SQLite Works
122 </div>
123 <details class="fancy_toc">
124 <summary>Table Of Contents</summary>
125 <div id="toc_sub"><div class="fancy-toc1"><a href="#background">1. Background</a></div>
126 <div class="fancy-toc2"><a href="#sqlite_is_different_from_most_other_sql_databases">1.1. SQLite Is Different From Most Other SQL Databases</a></div>
127 <div class="fancy-toc1"><a href="#sql_is_a_programming_language">2. SQL Is A Programming Language</a></div>
128 <div class="fancy-toc2"><a href="#programming_language_processing_steps">2.1. Programming Language Processing Steps</a></div>
129 <div class="fancy-toc2"><a href="#compiling_sqlite_programs">2.2. Compiling SQLite Programs</a></div>
130 <div class="fancy-toc1"><a href="#further_reading">3. Further Reading</a></div>
131 </div>
132 </details>
133 </div>
134
135
136
137
138
139 <h1 id="background"><span>1. </span>Background</h1>
140
141 <p>
142 SQLite is a <a href="https://en.wikipedia.org/wiki/Library_(computing)">software library</a>
143 that translates high-level disk I/O requests generated by an application
144 into low-level I/O operations that
145 can be carried out by the operating system. The application constructs
146 high-level I/O requests using the
147 <a href="https://en.wikipedia.org/wiki/SQL">SQL language</a>.
148 SQLite translates each high-level SQL statement into a sequence of
149 many low-level I/O requests (open a file, read a few bytes from a file,
150 write a few bytes into a file, etc.) that do the work requested by
151 the SQL.
152
153
154 </p><p>
155 An application program could do all its disk I/O by direct calls to
156 operating system I/O routines
157 or by using a key/value storage engine like
158 <a href="https://en.wikipedia.org/wiki/Berkeley_DB">Berkeley DB</a> or
159 <a href="https://en.wikipedia.org/wiki/RocksDB">RocksDB</a> (to name but two).
160 But there are advantages to using a higher-level interface based
161 on the SQL language.
162
163 </p><ol>
164 <li><p>
165 SQL is a very high-level language.
166 A few lines of SQL can replace hundreds or thousands of lines of
167 procedural code. SQL thus reduces
168 the amount of work needed to develop and maintain the application,
169 and thereby helps to reduce the number of bugs in the application.
170
171 </p></li><li><p>
172 SQL and SQLite are
173 <a href="https://en.wikipedia.org/wiki/Database_transaction">transactional</a>.
174 The use of a transactional storage system makes it much easier to
175 reason about the behavior of the application, and to write applications
176 that are robust, even in the face of software bugs, hardware faults,
177 or power losses.
178
179 </p></li><li><p>
180 SQLite is often
181 <a href="fasterthanfs.html">faster than direct low-level I/O</a>.
182 This is counterintuitive. One would expect that a
183 high-level interface such as SQLite would impose a run-time penalty.
184 And, theoretically, that is correct. But in practice, SQL-based
185 systems such as SQLite do so many behind-the-scenes optimizations
186 that an application developer would never have time to create and
187 maintain, that the SQL-based systems end up providing
188 a net performance gain.
189 </p></li></ol>
190
191 <h2 id="sqlite_is_different_from_most_other_sql_databases"><span>1.1. </span>SQLite Is Different From Most Other SQL Databases</h2>
192
193 <p>
194 There are many SQL-based database management systems available, besides
195 SQLite. Common options include MySQL, PostgreSQL, and SQL-Server.
196 All these systems use the SQL langauge to communicate with the
197 application, just like SQLite. But these other systems different
198 from SQLite in important respects.
199
200 </p><ol>
201 <li><p>
202 SQLite is a <a href="serverless.html">serverless</a> software library, whereas the other
203 systems are client-server based. With MySQL, PostgreSQL, SQL-Server,
204 and others, the application sends a message containing some SQL
205 over to a separate server thread or process. That separate
206 thread or process performs the requested I/O, then send the results
207 back to the application. But there is no separate thread or
208 process with SQLite. SQLite runs in the same address space as
209 the application, using the same program counter and heap storage.
210 SQLite does no interprocess communication (IPC). When an application
211 sends an SQL statement into SQLite (by invoking the appropriate
212 SQLite library subroutine), SQLite interprets the SQL
213 in the same thread as the caller. When an SQLite API routine
214 returns, it does not leave behind any background tasks that
215 run separately from the application.
216
217 </p></li><li><p>
218 An SQLite database is a single ordinary file on disk
219 (with a <a href="fileformat2.html">well-defined file format</a>). With other
220 systems, a "database" is usually a large number of separate
221 files hidden away in obscure directories of the filesystem, or
222 even spread across multiple machines. But with SQLite, a
223 complete database is just an ordinary disk file.
224 </p></li></ol>
225
226 <h1 id="sql_is_a_programming_language"><span>2. </span>SQL Is A Programming Language</h1>
227
228 <p>
229 The best way to understand how SQL database engines work is to
230 think of SQL as a programming language, not as a "query language".
231 Each SQL statement is a separate program. Applications construct
232 SQL program source files and send them to the database engine.
233 The database engine compiles the SQL source code into executable
234 form, runs that executable, then sends the result back to the
235 application.
236
237 </p><p>
238 While SQL is a programming language, it is different from other
239 programming languages like C, Javascript, Python, or Go in that
240 SQL is a
241 <a href="https://en.wikipedia.org/wiki/Declarative_programming">declarative language</a>
242 where the others are
243 <a href="https://en.wikipedia.org/wiki/Imperative_programming">imperative languages</a>.
244 This is an important difference that has implications for the
245 design of the compiler used to translate program source text into an
246 executable format. However, those details
247 should not detract from the fact that
248 SQL is really just another programming language.
249
250 </p><h2 id="programming_language_processing_steps"><span>2.1. </span>Programming Language Processing Steps</h2>
251
252 <p>
253 All programming languages are processed in two steps:
254
255 </p><ol>
256 <li><p>
257 Translate the program source text into an executable format.
258 </p></li><li><p>
259 Run the executable generated in the previous step in order to
260 carry out the desired action.
261 </p></li></ol>
262
263 <p>
264 All programming languages use those two basic steps.
265 The main difference is in the executable format.
266
267 </p><p>
268 "Compiled" languages like C++ and Rust translate
269 the source text into machine code that can be directly executed
270 by the underlying hardware. There exist SQL database systems
271 that do the same with SQL - they translate each SQL statement
272 directly into machine code. But that approach is uncommon and
273 is not the approach taken by SQLite.
274
275 </p><p>
276 Other languages like Java, Perl, Python, and TCL
277 typically translate the program source text into bytecode.
278 This bytecode is then run through an interpreter that
279 reads the bytecode and carries out the desired operations.
280 SQLite uses this bytecode approach. If you preceed
281 any SQL statement with the "<a href="lang_explain.html">EXPLAIN</a>" keyword in SQLite,
282 it will show you the bytecode that is generated rather
283 than run the bytecode.
284
285 </p><p>
286 Another approach is to translate the program source text
287 into a tree of objects in memory. This tree is the "executable".
288 An interpret runs the executable by walking the tree.
289 This is the technique used by MySQL, PostgreSQL, and
290 SQL-Server.
291
292 </p><p>
293 Of course, not every language fits neatly into one of the
294 above categories. This applies to both SQL database engines
295 and more familiar imperative programming languages. Javascript
296 is famous for using a hybrid execution model, where the code
297 is initially compiled into a tree of objects, but might be
298 further translating (using just-in-time compilation) down into
299 more efficient bytecode or machine code, as a means of boosting
300 performance.
301
302 </p><p>
303 The executable format really ends up being just an implementation
304 detail. The key point is that all languages have a compiler
305 step which translates programs into an executable format and
306 a run step that executes the compiled program.
307
308
309 </p><h2 id="compiling_sqlite_programs"><span>2.2. </span>Compiling SQLite Programs</h2>
310
311 <p>
312 When an SQL program is submitted to SQLite, the first step is
313 to split the source text into "tokens". A token might be:
314
315 </p><ul>
316 <li>A language keyword like "SELECT" or "UPDATE".
317 </li><li>An identifier for a table or column or variable.
318 </li><li>Punctuation characters like "," or "==" or ";".
319 </li><li>Literal values: numeric or string constants.
320 </li><li>Whitespace or comments.
321 </li></ul>
322
323 <p>
324 Whitespace and comment tokens are discarded. All other tokens
325 are fed into an
326 <a href="https://en.wikipedia.org/wiki/LALR_parser">LALR(1) Parser</a>
327 that analyzes the structure of the input program and generates an
328 <a href="https://en.wikipedia.org/wiki/Abstract_syntax_tree">Abstract Syntax Tree (AST)</a>
329 for the input program.
330
331 </p><p>
332 The parser forwards the AST on to the code generator.
333 The code generator is the heart of SQLite, and is where most of
334 the magic happens.
335 The code generator resolves symbolic names in the AST - matching
336 the names of columns and tables in the input SQL into actual
337 columns and tables of the database. The code generator also does
338 various transformations on the AST to "optimize" it. Finally
339 the code generator chooses appropriate algorithms to implement
340 the operations requested by the AST and constructs bytecode to
341 carry out those operations.
342
343 </p><p>
344 The bytecode generated by the code generator is called a
345 "<a href="c3ref/stmt.html">prepared statement</a>". Translating SQL source text into a
346 prepared statement is analogous to converting a C++ program
347 into machine code by invoking gcc or clang. Human-readable
348 source text (SQL or C++) goes in, and a machine readable executable
349 (bytecode or machine code) comes out.
350
351 </p><h1 id="further_reading"><span>3. </span>Further Reading</h1>
352
353 <ul>
354 <li><p>
355 The <a href="atomiccommit.html">Atomic Commit</a> document describes how SQLite implements
356 transactions.
357
358 </p></li><li><p>
359 The <a href="opcode.html">bytecode engine</a> document has more information
360 on the bytecode format used by SQLite, and how to view and interpret
361 an SQLite prepared statement.
362
363 </p></li><li><p>
364 The <a href="optoverview.html">SQLite query planner</a> and
365 <a href="queryplanner-ng.html">Next Generation Query Planner</a> documents have further details
366 on the algorithms SQLite uses to implement SQL statements and
367 how it goes above choosing an appropriate algorithm for each
368 individual SQL statement.
369 </p></li></ul>
370 <p align="center"><small><i>This page was last updated on 2025-05-31 13:08:22Z </small></i></p>
371