| 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>Database File Format</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 |
Database File Format |
| 122 |
</div> |
| 123 |
<details class="fancy_toc"> |
| 124 |
<summary>Table Of Contents</summary> |
| 125 |
<div id="toc_sub"><div class="fancy-toc1"><a href="#the_database_file">1. The Database File</a></div> |
| 126 |
<div class="fancy-toc2"><a href="#hot_journals">1.1. Hot Journals</a></div> |
| 127 |
<div class="fancy-toc2"><a href="#pages">1.2. Pages</a></div> |
| 128 |
<div class="fancy-toc2"><a href="#the_database_header">1.3. The Database Header</a></div> |
| 129 |
<div class="fancy-toc3"><a href="#magic_header_string">1.3.1. Magic Header String</a></div> |
| 130 |
<div class="fancy-toc3"><a href="#page_size">1.3.2. Page Size</a></div> |
| 131 |
<div class="fancy-toc3"><a href="#file_format_version_numbers">1.3.3. File format version numbers</a></div> |
| 132 |
<div class="fancy-toc3"><a href="#reserved_bytes_per_page">1.3.4. Reserved bytes per page</a></div> |
| 133 |
<div class="fancy-toc3"><a href="#payload_fractions">1.3.5. Payload fractions</a></div> |
| 134 |
<div class="fancy-toc3"><a href="#file_change_counter">1.3.6. File change counter</a></div> |
| 135 |
<div class="fancy-toc3"><a href="#in_header_database_size">1.3.7. In-header database size</a></div> |
| 136 |
<div class="fancy-toc3"><a href="#free_page_list">1.3.8. Free page list</a></div> |
| 137 |
<div class="fancy-toc3"><a href="#schema_cookie">1.3.9. Schema cookie</a></div> |
| 138 |
<div class="fancy-toc3"><a href="#schema_format_number">1.3.10. Schema format number</a></div> |
| 139 |
<div class="fancy-toc3"><a href="#suggested_cache_size">1.3.11. Suggested cache size</a></div> |
| 140 |
<div class="fancy-toc3"><a href="#incremental_vacuum_settings">1.3.12. Incremental vacuum settings</a></div> |
| 141 |
<div class="fancy-toc3"><a href="#text_encoding">1.3.13. Text encoding</a></div> |
| 142 |
<div class="fancy-toc3"><a href="#user_version_number">1.3.14. User version number</a></div> |
| 143 |
<div class="fancy-toc3"><a href="#application_id">1.3.15. Application ID</a></div> |
| 144 |
<div class="fancy-toc3"><a href="#write_library_version_number_and_version_valid_for_number">1.3.16. Write library version number and version-valid-for number</a></div> |
| 145 |
<div class="fancy-toc3"><a href="#header_space_reserved_for_expansion">1.3.17. Header space reserved for expansion</a></div> |
| 146 |
<div class="fancy-toc2"><a href="#the_lock_byte_page">1.4. The Lock-Byte Page</a></div> |
| 147 |
<div class="fancy-toc2"><a href="#the_freelist">1.5. The Freelist</a></div> |
| 148 |
<div class="fancy-toc2"><a href="#b_tree_pages">1.6. B-tree Pages</a></div> |
| 149 |
<div class="fancy-toc2"><a href="#cell_payload_overflow_pages">1.7. Cell Payload Overflow Pages</a></div> |
| 150 |
<div class="fancy-toc2"><a href="#pointer_map_or_ptrmap_pages">1.8. Pointer Map or Ptrmap Pages</a></div> |
| 151 |
<div class="fancy-toc1"><a href="#schema_layer">2. Schema Layer</a></div> |
| 152 |
<div class="fancy-toc2"><a href="#record_format">2.1. Record Format</a></div> |
| 153 |
<div class="fancy-toc2"><a href="#record_sort_order">2.2. Record Sort Order</a></div> |
| 154 |
<div class="fancy-toc2"><a href="#representation_of_sql_tables">2.3. Representation Of SQL Tables</a></div> |
| 155 |
<div class="fancy-toc2"><a href="#representation_of_without_rowid_tables">2.4. Representation of WITHOUT ROWID Tables</a></div> |
| 156 |
<div class="fancy-toc3"><a href="#suppression_of_redundant_columns_in_the_primary_key_of_without_rowid_tables">2.4.1. Suppression of redundant columns in the PRIMARY KEY |
| 157 |
of WITHOUT ROWID tables</a></div> |
| 158 |
<div class="fancy-toc2"><a href="#representation_of_sql_indices">2.5. Representation Of SQL Indices</a></div> |
| 159 |
<div class="fancy-toc3"><a href="#suppression_of_redundant_columns_in_without_rowid_secondary_indexes_">2.5.1. Suppression of redundant columns in WITHOUT ROWID secondary indexes |
| 160 |
</a></div> |
| 161 |
<div class="fancy-toc2"><a href="#storage_of_the_sql_database_schema">2.6. Storage Of The SQL Database Schema</a></div> |
| 162 |
<div class="fancy-toc3"><a href="#alternative_names_for_the_schema_table">2.6.1. Alternative Names For The Schema Table</a></div> |
| 163 |
<div class="fancy-toc3"><a href="#internal_schema_objects">2.6.2. Internal Schema Objects</a></div> |
| 164 |
<div class="fancy-toc3"><a href="#the_sqlite_sequence_table">2.6.3. The sqlite_sequence table</a></div> |
| 165 |
<div class="fancy-toc3"><a href="#the_sqlite_stat1_table">2.6.4. The sqlite_stat1 table</a></div> |
| 166 |
<div class="fancy-toc3"><a href="#the_sqlite_stat2_table">2.6.5. The sqlite_stat2 table</a></div> |
| 167 |
<div class="fancy-toc3"><a href="#the_sqlite_stat3_table">2.6.6. The sqlite_stat3 table</a></div> |
| 168 |
<div class="fancy-toc3"><a href="#the_sqlite_stat4_table">2.6.7. The sqlite_stat4 table</a></div> |
| 169 |
<div class="fancy-toc1"><a href="#the_rollback_journal">3. The Rollback Journal</a></div> |
| 170 |
<div class="fancy-toc1"><a href="#the_write_ahead_log">4. The Write-Ahead Log</a></div> |
| 171 |
<div class="fancy-toc2"><a href="#wal_file_format">4.1. WAL File Format</a></div> |
| 172 |
<div class="fancy-toc2"><a href="#checksum_algorithm">4.2. Checksum Algorithm</a></div> |
| 173 |
<div class="fancy-toc2"><a href="#checkpoint_algorithm">4.3. Checkpoint Algorithm</a></div> |
| 174 |
<div class="fancy-toc2"><a href="#wal_reset">4.4. WAL Reset</a></div> |
| 175 |
<div class="fancy-toc2"><a href="#reader_algorithm">4.5. Reader Algorithm</a></div> |
| 176 |
<div class="fancy-toc2"><a href="#wal_index_format">4.6. WAL-Index Format</a></div> |
| 177 |
</div> |
| 178 |
</details> |
| 179 |
</div> |
| 180 |
|
| 181 |
|
| 182 |
|
| 183 |
|
| 184 |
|
| 185 |
|
| 186 |
<p>This document describes and defines the on-disk database file |
| 187 |
format used by all releases of SQLite since |
| 188 |
version 3.0.0 (2004-06-18).</p> |
| 189 |
|
| 190 |
<h1 id="the_database_file"><span>1. </span>The Database File</h1> |
| 191 |
|
| 192 |
<p>The complete state of an SQLite database is usually |
| 193 |
contained in a single file on disk called the "main database file".</p> |
| 194 |
|
| 195 |
<p>During a transaction, SQLite stores additional information |
| 196 |
in a second file called the "rollback journal", or if SQLite is in |
| 197 |
<a href="wal.html">WAL mode</a>, a write-ahead log file. |
| 198 |
|
| 199 |
<a name="hotjrnl"></a> |
| 200 |
|
| 201 |
</p><h2 id="hot_journals"><span>1.1. </span>Hot Journals</h2> |
| 202 |
<p>If the application or |
| 203 |
host computer crashes before the transaction completes, then the rollback |
| 204 |
journal or write-ahead log contains information needed |
| 205 |
to restore the main database file to a consistent state. When a rollback |
| 206 |
journal or write-ahead log contains information necessary for recovering |
| 207 |
the state of the database, they are called a "hot journal" or "hot WAL file". |
| 208 |
Hot journals and WAL files are only a factor during error recovery |
| 209 |
scenarios and so are uncommon, but they are part of the state of an SQLite |
| 210 |
database and so cannot be ignored. This document defines the format |
| 211 |
of a rollback journal and the write-ahead log file, but the focus is |
| 212 |
on the main database file.</p> |
| 213 |
|
| 214 |
<h2 id="pages"><span>1.2. </span>Pages</h2> |
| 215 |
|
| 216 |
<p>The main database file consists of one or more pages. The size of a |
| 217 |
page is a power of two between 512 and 65536 inclusive. All pages within |
| 218 |
the same database are the same size. The page size for a database file |
| 219 |
is determined by the 2-byte integer located at an offset of |
| 220 |
16 bytes from the beginning of the database file.</p> |
| 221 |
|
| 222 |
<p>Pages are numbered beginning with 1. The maximum page number is |
| 223 |
4294967294 (2<sup><small>32</small></sup> - 2). The minimum size |
| 224 |
SQLite database is a single 512-byte page. |
| 225 |
The maximum size database would be 4294967294 pages at 65536 bytes per |
| 226 |
page or 281,474,976,579,584 bytes (about 281 terabytes). Usually SQLite will |
| 227 |
hit the maximum file size limit of the underlying filesystem or disk |
| 228 |
hardware long before it hits its own internal size limit.</p> |
| 229 |
|
| 230 |
<p>In common use, SQLite databases tend to range in size from a few kilobytes |
| 231 |
to a few gigabytes, though terabyte-size SQLite databases are known to exist |
| 232 |
in production.</p> |
| 233 |
|
| 234 |
<p>At any point in time, every page in the main database has a single |
| 235 |
use which is one of the following: |
| 236 |
</p><ul> |
| 237 |
<li>A b-tree page |
| 238 |
<ul> |
| 239 |
<li>A table b-tree interior page |
| 240 |
</li><li>A table b-tree leaf page |
| 241 |
</li><li>An index b-tree interior page |
| 242 |
</li><li>An index b-tree leaf page |
| 243 |
</li></ul> |
| 244 |
</li><li>A freelist page |
| 245 |
<ul> |
| 246 |
<li>A freelist trunk page |
| 247 |
</li><li>A freelist leaf page |
| 248 |
</li></ul> |
| 249 |
</li><li>A payload overflow page |
| 250 |
</li><li>A pointer map page |
| 251 |
</li><li>The lock-byte page |
| 252 |
</li></ul> |
| 253 |
|
| 254 |
|
| 255 |
<p>All reads from and writes to the main database file begin at a page |
| 256 |
boundary and all writes are an integer number of pages in size. Reads |
| 257 |
are also usually an integer number of pages in size, with the one exception |
| 258 |
that when the database is first opened, the first 100 bytes of the |
| 259 |
database file (the database file header) are read as a sub-page size unit.</p> |
| 260 |
|
| 261 |
<a name="database_header"></a> |
| 262 |
|
| 263 |
<h2 id="the_database_header"><span>1.3. </span>The Database Header</h2> |
| 264 |
|
| 265 |
<p>The first 100 bytes of the database file comprise the database file |
| 266 |
header. The database file header is divided into fields as shown by |
| 267 |
the table below. All multibyte fields in the database file header are |
| 268 |
stored with the most significant byte first (big-endian).</p> |
| 269 |
|
| 270 |
<center> |
| 271 |
<i>Database Header Format</i><br> |
| 272 |
<table width="80%" border="1"> |
| 273 |
<tr><th>Offset</th><th>Size</th><th>Description |
| 274 |
</th></tr><tr><td valign="top" align="center">0</td><td valign="top" align="center">16</td><td align="left"> |
| 275 |
The header string: "SQLite format 3\000" |
| 276 |
</td></tr><tr><td valign="top" align="center">16</td><td valign="top" align="center">2</td><td align="left"> |
| 277 |
The database page size in bytes. Must be a power of two between 512 |
| 278 |
and 32768 inclusive, or the value 1 representing a page size of 65536. |
| 279 |
</td></tr><tr><td valign="top" align="center">18</td><td valign="top" align="center">1</td><td align="left"> |
| 280 |
File format write version. 1 for legacy; 2 for <a href="wal.html">WAL</a>. |
| 281 |
</td></tr><tr><td valign="top" align="center">19</td><td valign="top" align="center">1</td><td align="left"> |
| 282 |
File format read version. 1 for legacy; 2 for <a href="wal.html">WAL</a>. |
| 283 |
</td></tr><tr><td valign="top" align="center">20</td><td valign="top" align="center">1</td><td align="left"> |
| 284 |
Bytes of unused "reserved" space at the end of each page. Usually 0. |
| 285 |
</td></tr><tr><td valign="top" align="center">21</td><td valign="top" align="center">1</td><td align="left"> |
| 286 |
Maximum embedded payload fraction. Must be 64. |
| 287 |
</td></tr><tr><td valign="top" align="center">22</td><td valign="top" align="center">1</td><td align="left"> |
| 288 |
Minimum embedded payload fraction. Must be 32. |
| 289 |
</td></tr><tr><td valign="top" align="center">23</td><td valign="top" align="center">1</td><td align="left"> |
| 290 |
Leaf payload fraction. Must be 32. |
| 291 |
</td></tr><tr><td valign="top" align="center">24</td><td valign="top" align="center">4</td><td align="left"> |
| 292 |
File change counter. |
| 293 |
</td></tr><tr><td valign="top" align="center">28</td><td valign="top" align="center">4</td><td align="left"> |
| 294 |
Size of the database file in pages. The "in-header database size". |
| 295 |
</td></tr><tr><td valign="top" align="center">32</td><td valign="top" align="center">4</td><td align="left"> |
| 296 |
Page number of the first freelist trunk page. |
| 297 |
</td></tr><tr><td valign="top" align="center">36</td><td valign="top" align="center">4</td><td align="left"> |
| 298 |
Total number of freelist pages. |
| 299 |
</td></tr><tr><td valign="top" align="center">40</td><td valign="top" align="center">4</td><td align="left"> |
| 300 |
The schema cookie. |
| 301 |
</td></tr><tr><td valign="top" align="center">44</td><td valign="top" align="center">4</td><td align="left"> |
| 302 |
The schema format number. Supported schema formats are 1, 2, 3, and 4. |
| 303 |
</td></tr><tr><td valign="top" align="center">48</td><td valign="top" align="center">4</td><td align="left"> |
| 304 |
Default page cache size. |
| 305 |
</td></tr><tr><td valign="top" align="center">52</td><td valign="top" align="center">4</td><td align="left"> |
| 306 |
The page number of the largest root b-tree page when in auto-vacuum or |
| 307 |
incremental-vacuum modes, or zero otherwise. |
| 308 |
</td></tr><tr><td valign="top" align="center">56</td><td valign="top" align="center">4</td><td align="left"> |
| 309 |
The database text encoding. A value of 1 means UTF-8. A value of 2 |
| 310 |
means UTF-16le. A value of 3 means UTF-16be. |
| 311 |
</td></tr><tr><td valign="top" align="center">60</td><td valign="top" align="center">4</td><td align="left"> |
| 312 |
The "user version" as read and set by the <a href="pragma.html#pragma_user_version">user_version pragma</a>. |
| 313 |
</td></tr><tr><td valign="top" align="center">64</td><td valign="top" align="center">4</td><td align="left"> |
| 314 |
True (non-zero) for incremental-vacuum mode. False (zero) otherwise. |
| 315 |
</td></tr><tr><td valign="top" align="center">68</td><td valign="top" align="center">4</td><td align="left"> |
| 316 |
The "Application ID" set by <a href="pragma.html#pragma_application_id">PRAGMA application_id</a>. |
| 317 |
</td></tr><tr><td valign="top" align="center">72</td><td valign="top" align="center">20</td><td align="left"> |
| 318 |
Reserved for expansion. Must be zero. |
| 319 |
</td></tr><tr><td valign="top" align="center">92</td><td valign="top" align="center">4</td><td align="left"> |
| 320 |
The <a href="fileformat2.html#validfor">version-valid-for number</a>. |
| 321 |
</td></tr><tr><td valign="top" align="center">96</td><td valign="top" align="center">4</td><td align="left"> |
| 322 |
<a href="c3ref/c_scm_branch.html">SQLITE_VERSION_NUMBER</a> |
| 323 |
</td></tr></table></center> |
| 324 |
|
| 325 |
<h3 id="magic_header_string"><span>1.3.1. </span>Magic Header String</h3> |
| 326 |
|
| 327 |
<p>Every valid SQLite database file begins with the following 16 bytes |
| 328 |
(in hex): 53 51 4c 69 74 65 20 66 6f 72 6d 61 74 20 33 00. This byte sequence |
| 329 |
corresponds to the UTF-8 string "SQLite format 3" including the nul |
| 330 |
terminator character at the end.</p> |
| 331 |
|
| 332 |
<h3 id="page_size"><span>1.3.2. </span>Page Size</h3> |
| 333 |
|
| 334 |
<p>The two-byte value beginning at offset 16 determines the page size of |
| 335 |
the database. For SQLite versions 3.7.0.1 (2010-08-04) |
| 336 |
and earlier, this value is |
| 337 |
interpreted as a big-endian integer and must be a power of two between |
| 338 |
512 and 32768, inclusive. Beginning with SQLite <a href="releaselog/3_7_1.html">version 3.7.1</a> |
| 339 |
(2010-08-23), a page |
| 340 |
size of 65536 bytes is supported. The value 65536 will not fit in a |
| 341 |
two-byte integer, so to specify a 65536-byte page size, the value |
| 342 |
at offset 16 is 0x00 0x01. |
| 343 |
This value can be interpreted as a big-endian |
| 344 |
1 and thought of as a magic number to represent the 65536 page size. |
| 345 |
Or one can view the two-byte field as a little endian number and say |
| 346 |
that it represents the page size divided by 256. These two |
| 347 |
interpretations of the page-size field are equivalent.</p> |
| 348 |
|
| 349 |
<a name="vnums"></a> |
| 350 |
|
| 351 |
<h3 id="file_format_version_numbers"><span>1.3.3. </span>File format version numbers</h3> |
| 352 |
|
| 353 |
<p>The file format write version and file format read version at offsets |
| 354 |
18 and 19 are intended to allow for enhancements of the file format |
| 355 |
in future versions of SQLite. In current versions of SQLite, both of |
| 356 |
these values are 1 for rollback journalling modes and 2 for <a href="wal.html">WAL</a> |
| 357 |
journalling mode. If a version of SQLite coded to the current |
| 358 |
file format specification encounters a database file where the read |
| 359 |
version is 1 or 2 but the write version is greater than 2, then the database |
| 360 |
file must be treated as read-only. If a database file with a read version |
| 361 |
greater than 2 is encountered, then that database cannot be read or written.</p> |
| 362 |
|
| 363 |
<a name="resbyte"></a> |
| 364 |
|
| 365 |
<h3 id="reserved_bytes_per_page"><span>1.3.4. </span>Reserved bytes per page</h3> |
| 366 |
|
| 367 |
<p>SQLite has the ability to set aside a small number of extra bytes at |
| 368 |
the end of every page for use by extensions. These extra bytes are |
| 369 |
used, for example, by the SQLite Encryption Extension to store a nonce |
| 370 |
and/or cryptographic checksum associated with each page. The |
| 371 |
"reserved space" size in the 1-byte integer at offset 20 is the number |
| 372 |
of bytes of space at the end of each page to reserve for extensions. |
| 373 |
This value is usually 0. The value can be odd.</p> |
| 374 |
|
| 375 |
<a name="usable_size"></a> |
| 376 |
|
| 377 |
<p>The "usable size" of a database page is the page size specified by the |
| 378 |
2-byte integer at offset 16 in the header less the "reserved" space size |
| 379 |
recorded in the 1-byte integer at offset 20 in the header. The usable |
| 380 |
size of a page might be an odd number. However, the usable size is not |
| 381 |
allowed to be less than 480. In other words, if the page size is 512, |
| 382 |
then the reserved space size cannot exceed 32.</p> |
| 383 |
|
| 384 |
<h3 id="payload_fractions"><span>1.3.5. </span>Payload fractions</h3> |
| 385 |
|
| 386 |
<p>The maximum and minimum embedded payload fractions and the leaf |
| 387 |
payload fraction values must be 64, 32, and 32. These values were |
| 388 |
originally intended to be tunable parameters that could be used to |
| 389 |
modify the storage format of the b-tree algorithm. However, that |
| 390 |
functionality is not supported and there are no current plans to add |
| 391 |
support in the future. Hence, these three bytes are fixed at the |
| 392 |
values specified.</p> |
| 393 |
|
| 394 |
<a name="chngctr"></a> |
| 395 |
|
| 396 |
<h3 id="file_change_counter"><span>1.3.6. </span>File change counter</h3> |
| 397 |
|
| 398 |
<p>The file change counter is a 4-byte big-endian integer at |
| 399 |
offset 24 that is incremented whenever the database file is unlocked |
| 400 |
after having been modified. |
| 401 |
When two or more processes are reading the same database file, each |
| 402 |
process can detect database changes from other processes by monitoring |
| 403 |
the change counter. |
| 404 |
A process will normally want to flush its database page cache when |
| 405 |
another process modified the database, since the cache has become stale. |
| 406 |
The file change counter facilitates this.</p> |
| 407 |
|
| 408 |
<p>In WAL mode, changes to the database are detected using the wal-index |
| 409 |
and so the change counter is not needed. Hence, the change counter might |
| 410 |
not be incremented on each transaction in WAL mode.</p> |
| 411 |
|
| 412 |
<h3 id="in_header_database_size"><span>1.3.7. </span>In-header database size</h3> |
| 413 |
|
| 414 |
<a name="filesize"></a> |
| 415 |
|
| 416 |
<p>The 4-byte big-endian integer at offset 28 into the header |
| 417 |
stores the size of the database file in pages. If this in-header |
| 418 |
datasize size is not valid (see the next paragraph), then the database |
| 419 |
size is computed by looking |
| 420 |
at the actual size of the database file. Older versions of SQLite |
| 421 |
ignored the in-header database size and used the actual file size |
| 422 |
exclusively. Newer versions of SQLite use the in-header database |
| 423 |
size if it is available but fall back to the actual file size if |
| 424 |
the in-header database size is not valid.</p> |
| 425 |
|
| 426 |
<p>The in-header database size is only considered to be valid if |
| 427 |
it is non-zero and if the 4-byte <a href="fileformat2.html#chngctr">change counter</a> at offset 24 |
| 428 |
exactly matches the 4-byte <a href="fileformat2.html#validfor">version-valid-for number</a> at offset 92. |
| 429 |
The in-header database size is always valid |
| 430 |
when the database is only modified using recent versions of SQLite, |
| 431 |
versions 3.7.0 (2010-07-21) and later. |
| 432 |
If a legacy version of SQLite writes to the database, it will not |
| 433 |
know to update the in-header database size and so the in-header |
| 434 |
database size could be incorrect. But legacy versions of SQLite |
| 435 |
will also leave the version-valid-for number at offset 92 unchanged |
| 436 |
so it will not match the change-counter. Hence, invalid in-header |
| 437 |
database sizes can be detected (and ignored) by observing when |
| 438 |
the change-counter does not match the version-valid-for number.</p> |
| 439 |
|
| 440 |
<h3 id="free_page_list"><span>1.3.8. </span>Free page list</h3> |
| 441 |
|
| 442 |
<p>Unused pages in the database file are stored on a freelist. The |
| 443 |
4-byte big-endian integer at offset 32 stores the page number of |
| 444 |
the first page of the freelist, or zero if the freelist is empty. |
| 445 |
The 4-byte big-endian integer at offset 36 stores the total |
| 446 |
number of pages on the freelist.</p> |
| 447 |
|
| 448 |
<h3 id="schema_cookie"><span>1.3.9. </span>Schema cookie</h3> |
| 449 |
|
| 450 |
<p>The schema cookie is a 4-byte big-endian integer at offset 40 |
| 451 |
that is incremented whenever the database schema changes. A |
| 452 |
prepared statement is compiled against a specific version of the |
| 453 |
database schema. When the database schema changes, the statement |
| 454 |
must be reprepared. When a prepared statement runs, it first checks |
| 455 |
the schema cookie to ensure the value is the same as when the statement |
| 456 |
was prepared and if the schema cookie has changed, the statement either |
| 457 |
automatically reprepares and reruns or it aborts with an <a href="rescode.html#schema">SQLITE_SCHEMA</a> |
| 458 |
error.</p> |
| 459 |
|
| 460 |
<a name="schemaformat"></a> |
| 461 |
|
| 462 |
<h3 id="schema_format_number"><span>1.3.10. </span>Schema format number</h3> |
| 463 |
|
| 464 |
<p>The schema format number is a 4-byte big-endian integer at offset 44. |
| 465 |
The schema format number is similar to the file format read and write |
| 466 |
version numbers at offsets 18 and 19 except that the schema format number |
| 467 |
refers to the high-level SQL formatting rather than the low-level b-tree |
| 468 |
formatting. Four schema format numbers are currently defined:</p> |
| 469 |
|
| 470 |
<ol> |
| 471 |
<li value="1">Format 1 is understood by all versions of SQLite back to |
| 472 |
<a href="releaselog/3_0_0.html">version 3.0.0</a> (2004-06-18).</li> |
| 473 |
<li value="2">Format 2 adds the ability of rows within the same table |
| 474 |
to have a varying number of columns, in order to support the |
| 475 |
<a href="lang_altertable.html">ALTER TABLE ... ADD COLUMN</a> functionality. Support for |
| 476 |
reading and writing format 2 was added in SQLite |
| 477 |
<a href="releaselog/3_1_3.html">version 3.1.3</a> on 2005-02-20.</li> |
| 478 |
<li value="3">Format 3 adds the ability of extra columns added by |
| 479 |
<a href="lang_altertable.html">ALTER TABLE ... ADD COLUMN</a> to have non-NULL default |
| 480 |
values. This capability was added in SQLite <a href="releaselog/3_1_4.html">version 3.1.4</a> |
| 481 |
on 2005-03-11.</li> |
| 482 |
<li value="4">Format 4 causes SQLite to respect the |
| 483 |
<a href="lang_createindex.html#descidx">DESC keyword</a> on |
| 484 |
index declarations. (The DESC keyword is ignored in indexes for |
| 485 |
formats 1, 2, and 3.) |
| 486 |
Format 4 also adds two new boolean record type values (<a href="fileformat2.html#serialtype">serial types</a> |
| 487 |
8 and 9). Support for format 4 was added in SQLite 3.3.0 on |
| 488 |
2006-01-10.</li> |
| 489 |
</ol> |
| 490 |
|
| 491 |
<p>New database files created by SQLite use format 4 by default. |
| 492 |
The <a href="c3ref/c_dbconfig_defensive.html#sqlitedbconfiglegacyfileformat">SQLITE_DBCONFIG_LEGACY_FILE_FORMAT</a> option for the |
| 493 |
<a href="c3ref/db_config.html">sqlite3_db_config()</a> C-language interface can be used to cause SQLite |
| 494 |
to create new database files using format 1. The format version number |
| 495 |
can be made to default to 1 instead of 4 by setting |
| 496 |
<a href="compile.html#default_file_format">SQLITE_DEFAULT_FILE_FORMAT</a>=1 at compile-time. |
| 497 |
</p> |
| 498 |
|
| 499 |
<p>If the database is completely empty, if it has no schema, then the |
| 500 |
schema format number can be zero. |
| 501 |
|
| 502 |
</p><h3 id="suggested_cache_size"><span>1.3.11. </span>Suggested cache size</h3> |
| 503 |
|
| 504 |
<p>The 4-byte big-endian signed integer at offset 48 is the suggested |
| 505 |
cache size in pages for the database file. The value is a suggestion |
| 506 |
only and SQLite is under no obligation to honor it. The absolute value |
| 507 |
of the integer is used as the suggested size. The suggested cache size |
| 508 |
can be set using the <a href="pragma.html#pragma_default_cache_size">default_cache_size pragma</a>.</p> |
| 509 |
|
| 510 |
<h3 id="incremental_vacuum_settings"><span>1.3.12. </span>Incremental vacuum settings</h3> |
| 511 |
|
| 512 |
<p>The two 4-byte big-endian integers at offsets 52 and 64 are used |
| 513 |
to manage the <a href="pragma.html#pragma_auto_vacuum">auto_vacuum</a> and <a href="pragma.html#pragma_incremental_vacuum">incremental_vacuum</a> modes. If |
| 514 |
the integer at offset 52 is zero then pointer-map (ptrmap) pages are |
| 515 |
omitted from the database file and neither auto_vacuum nor |
| 516 |
incremental_vacuum are supported. If the integer at offset 52 is |
| 517 |
non-zero then it is the page number of the largest root page in the |
| 518 |
database file, the database file will contain ptrmap pages, and the |
| 519 |
mode must be either auto_vacuum or incremental_vacuum. In this latter |
| 520 |
case, the integer at offset 64 is true for incremental_vacuum and |
| 521 |
false for auto_vacuum. If the integer at offset 52 is zero then |
| 522 |
the integer at offset 64 must also be zero.</p> |
| 523 |
|
| 524 |
<a name="enc"></a> |
| 525 |
|
| 526 |
<h3 id="text_encoding"><span>1.3.13. </span>Text encoding</h3> |
| 527 |
|
| 528 |
<p>The 4-byte big-endian integer at offset 56 determines the encoding |
| 529 |
used for all text strings stored in the database. |
| 530 |
A value of 1 means UTF-8. |
| 531 |
A value of 2 means UTF-16le. |
| 532 |
A value of 3 means UTF-16be. |
| 533 |
No other values are allowed. |
| 534 |
The sqlite3.h header file defines C-preprocessor macros SQLITE_UTF8 as 1, |
| 535 |
SQLITE_UTF16LE as 2, and SQLITE_UTF16BE as 3, to use in place of |
| 536 |
the numeric codes for the text encoding.</p> |
| 537 |
|
| 538 |
<h3 id="user_version_number"><span>1.3.14. </span>User version number</h3> |
| 539 |
|
| 540 |
<p>The 4-byte big-endian integer at offset 60 is the user version which |
| 541 |
is set and queried by the <a href="pragma.html#pragma_user_version">user_version pragma</a>. The user version is |
| 542 |
not used by SQLite.</p> |
| 543 |
|
| 544 |
<a name="appid"></a> |
| 545 |
|
| 546 |
<h3 id="application_id"><span>1.3.15. </span>Application ID</h3> |
| 547 |
|
| 548 |
<p>The 4-byte big-endian integer at offset 68 is an "Application ID" that |
| 549 |
can be set by the <a href="pragma.html#pragma_application_id">PRAGMA application_id</a> command in order to identify the |
| 550 |
database as belonging to or associated with a particular application. |
| 551 |
The application ID is intended for database files used as an |
| 552 |
<a href="appfileformat.html">application file-format</a>. The application ID can be used by utilities |
| 553 |
such as <a href="http://www.darwinsys.com/file/">file(1)</a> to determine the specific |
| 554 |
file type rather than just reporting "SQLite3 Database". A list of |
| 555 |
assigned application IDs can be seen by consulting the |
| 556 |
<a href="https://sqlite.org/src/artifact?ci=trunk&filename=magic.txt">magic.txt</a> |
| 557 |
file in the SQLite source repository.</p> |
| 558 |
|
| 559 |
<a name="validfor"></a> |
| 560 |
|
| 561 |
<h3 id="write_library_version_number_and_version_valid_for_number"><span>1.3.16. </span>Write library version number and version-valid-for number</h3> |
| 562 |
|
| 563 |
<p>The 4-byte big-endian integer at offset 96 stores the |
| 564 |
<a href="c3ref/c_scm_branch.html">SQLITE_VERSION_NUMBER</a> value for the SQLite library that most |
| 565 |
recently modified the database file. The 4-byte big-endian integer at |
| 566 |
offset 92 is the value of the <a href="fileformat2.html#chngctr">change counter</a> when the version number |
| 567 |
was stored. The integer at offset 92 indicates which transaction |
| 568 |
the version number is valid for and is sometimes called the |
| 569 |
"version-valid-for number". |
| 570 |
|
| 571 |
</p><h3 id="header_space_reserved_for_expansion"><span>1.3.17. </span>Header space reserved for expansion</h3> |
| 572 |
|
| 573 |
<p>All other bytes of the database file header are reserved for |
| 574 |
future expansion and must be set to zero.</p> |
| 575 |
|
| 576 |
<a name="lockbyte"></a> |
| 577 |
|
| 578 |
<h2 id="the_lock_byte_page"><span>1.4. </span>The Lock-Byte Page</h2> |
| 579 |
|
| 580 |
<p>The lock-byte page is the single page of the database file |
| 581 |
that contains the bytes at offsets between 1073741824 and 1073742335, |
| 582 |
inclusive. A database file that is less than or equal to 1073741824 bytes |
| 583 |
in size contains no lock-byte page. A database file larger than |
| 584 |
1073741824 contains exactly one lock-byte page. |
| 585 |
</p> |
| 586 |
|
| 587 |
<p>The lock-byte page is set aside for use by the operating-system specific |
| 588 |
<a href="vfs.html">VFS</a> implementation in implementing the database file locking primitives. |
| 589 |
SQLite does not use the lock-byte page. The SQLite core |
| 590 |
will never read or write the lock-byte page, |
| 591 |
though operating-system specific <a href="vfs.html">VFS</a> |
| 592 |
implementations may choose to read or write bytes on the lock-byte |
| 593 |
page according to the |
| 594 |
needs and proclivities of the underlying system. The unix and win32 |
| 595 |
<a href="vfs.html">VFS</a> implementations that come built into SQLite do not write to the |
| 596 |
lock-byte page, but third-party VFS implementations for |
| 597 |
other operating systems might.</p> |
| 598 |
|
| 599 |
<p>The lock-byte page arose from the need to support Win95 which was the |
| 600 |
predominant operating system when this file format was designed and which |
| 601 |
only supported mandatory file locking. All modern operating systems that |
| 602 |
we know of support advisory file locking, and so the lock-byte page is |
| 603 |
not really needed any more, but is retained for backwards compatibility.</p> |
| 604 |
|
| 605 |
<a name="freelist"></a> |
| 606 |
|
| 607 |
<h2 id="the_freelist"><span>1.5. </span>The Freelist</h2> |
| 608 |
|
| 609 |
<p>A database file might contain one or more pages that are not in |
| 610 |
active use. Unused pages can come about, for example, when information |
| 611 |
is deleted from the database. Unused pages are stored on the freelist |
| 612 |
and are reused when additional pages are required.</p> |
| 613 |
|
| 614 |
<p>The freelist is organized as a linked list of freelist trunk pages |
| 615 |
with each trunk page containing page numbers for zero or more freelist |
| 616 |
leaf pages.</p> |
| 617 |
|
| 618 |
<p>A freelist trunk page consists of an array of 4-byte big-endian integers. |
| 619 |
The size of the array is as many integers as will fit in the usable space |
| 620 |
of a page. The minimum usable space is 480 bytes so the array will always |
| 621 |
be at least 120 entries in length. The first integer on a freelist trunk |
| 622 |
page is the page number of the next freelist trunk page in the list or zero |
| 623 |
if this is the last freelist trunk page. The second integer on a freelist |
| 624 |
trunk page is the number of leaf page pointers to follow. |
| 625 |
Call the second integer on a freelist trunk page L. |
| 626 |
If L is greater than zero then integers with array indexes between 2 and |
| 627 |
L+1 inclusive contain page numbers for freelist leaf pages.</p> |
| 628 |
|
| 629 |
<p>Freelist leaf pages contain no information. SQLite avoids reading or |
| 630 |
writing freelist leaf pages in order to reduce disk I/O.</p> |
| 631 |
|
| 632 |
<p>A bug in SQLite versions prior to 3.6.0 (2008-07-16) |
| 633 |
caused the database to be |
| 634 |
reported as corrupt if any of the last 6 entries in the freelist trunk page |
| 635 |
array contained non-zero values. Newer versions of SQLite do not have |
| 636 |
this problem. However, newer versions of SQLite still avoid using the |
| 637 |
last six entries in the freelist trunk page array in order that database |
| 638 |
files created by newer versions of SQLite can be read by older versions |
| 639 |
of SQLite.</p> |
| 640 |
|
| 641 |
<p>The number of freelist pages is stored as a 4-byte big-endian integer |
| 642 |
in the database header at an offset of 36 from the beginning of the file. |
| 643 |
The database header also stores the page number of the first freelist trunk |
| 644 |
page as a 4-byte big-endian integer at an offset of 32 from the beginning |
| 645 |
of the file.</p> |
| 646 |
|
| 647 |
<a name="btree"></a> |
| 648 |
|
| 649 |
<h2 id="b_tree_pages"><span>1.6. </span>B-tree Pages</h2> |
| 650 |
|
| 651 |
<p>The b-tree algorithm provides key/data storage with unique and |
| 652 |
ordered keys on page-oriented storage devices. |
| 653 |
For background information on b-trees, see |
| 654 |
Knuth, <u>The Art Of Computer Programming</u>, Volume 3 "Sorting |
| 655 |
and Searching", pages 471-479. Two variants of b-trees are used by |
| 656 |
SQLite. "Table b-trees" use a 64-bit signed integer key and store |
| 657 |
all data in the leaves. "Index b-trees" use arbitrary keys and store no |
| 658 |
data at all. |
| 659 |
|
| 660 |
</p><p>A b-tree page is either an interior page or a leaf page. |
| 661 |
A leaf page contains keys and in the case of a table b-tree each |
| 662 |
key has associated data. An interior page contains |
| 663 |
K keys together with K+1 pointers to child b-tree pages. |
| 664 |
A "pointer" in an interior b-tree page is just the 32-bit |
| 665 |
unsigned integer page number of the child page.</p><p> |
| 666 |
|
| 667 |
</p><p>The number of keys on an interior b-tree page, K, |
| 668 |
is almost always at least 2 and is usually much more than 2. |
| 669 |
The only exception is when page 1 is an interior b-tree page. |
| 670 |
Page 1 has 100 fewer bytes of storage space available, |
| 671 |
due to the presence of the database header at the beginning of that page, |
| 672 |
and so sometimes (rarely) if page 1 is an interior b-tree page, it can |
| 673 |
end up holding just a single key. In all other cases, K is 2 or more. |
| 674 |
The upper bound on K is as many keys as will fit on the page. Large keys |
| 675 |
on index b-trees are split up into <a href="fileformat2.html#ovflpgs">overflow pages</a> so that no single key |
| 676 |
uses more than one fourth of the available storage space on the page |
| 677 |
and hence every internal page is able to store at least 4 keys. |
| 678 |
The integer keys of table b-trees are never large enough to |
| 679 |
require overflow, so key overflow only occurs on index b-trees.</p> |
| 680 |
|
| 681 |
<p>Define the depth |
| 682 |
of a leaf b-tree to be 1 and the depth of any interior b-tree to be one |
| 683 |
more than the maximum depth of any of its children. In a well-formed |
| 684 |
database, all children of an interior b-tree have the same depth.</p> |
| 685 |
|
| 686 |
<p>In an interior b-tree page, the pointers and keys logically alternate |
| 687 |
with a pointer on both ends. (The previous sentence is to be understood |
| 688 |
conceptually - the actual layout of the keys and |
| 689 |
pointers within the page is more complicated and will be described in |
| 690 |
the sequel.) All keys within the same page are unique and are logically |
| 691 |
organized in ascending order from left to right. (Again, this ordering |
| 692 |
is logical, not physical. The actual location of keys within the page |
| 693 |
is arbitrary.) For any key X, pointers to the left |
| 694 |
of a X refer to b-tree pages on which all keys are less than or equal to X. |
| 695 |
Pointers to the right of X refer to pages where all keys are |
| 696 |
greater than X.</p> |
| 697 |
|
| 698 |
<p>Within an interior b-tree page, each key and the pointer to its |
| 699 |
immediate left are combined into a structure called a "cell". The |
| 700 |
right-most pointer is held separately. A leaf b-tree page has no |
| 701 |
pointers, but it still uses the cell structure to hold keys for |
| 702 |
index b-trees or keys and content for table b-trees. Data is also |
| 703 |
contained in the cell. |
| 704 |
</p> |
| 705 |
|
| 706 |
<p>Every b-tree page has at most one parent b-tree page. |
| 707 |
A b-tree page without a parent is called a root page. A root b-tree page |
| 708 |
together with the closure of its children form a complete b-tree. |
| 709 |
It is possible (and in fact rather common) to have a complete b-tree |
| 710 |
that consists of a single page that is both a leaf and the root. |
| 711 |
Because there are pointers from parents to children, every page of a |
| 712 |
complete b-tree can be located if only the root page is known. Hence, |
| 713 |
b-trees are identified by their root page number.</p> |
| 714 |
|
| 715 |
<a name="btypes"></a> |
| 716 |
|
| 717 |
<p>A b-tree page is either a table b-tree page or an index b-tree page. |
| 718 |
All pages within each complete b-tree are of the same type: either table |
| 719 |
or index. There is one table b-tree in the database file |
| 720 |
for each rowid table in the database schema, including system tables |
| 721 |
such as <a href="schematab.html">sqlite_schema</a>. There is one index b-tree |
| 722 |
in the database file for each index in the schema, including implied indexes |
| 723 |
created by uniqueness constraints. There are no b-trees associated with |
| 724 |
<a href="vtab.html">virtual tables</a>. Specific virtual table implementations might make use |
| 725 |
of <a href="vtab.html#xshadowname">shadow tables</a> for storage, but those shadow tables will have separate |
| 726 |
entries in the database schema. <a href="withoutrowid.html">WITHOUT ROWID</a> tables use index b-trees |
| 727 |
rather than table b-trees, so there is one |
| 728 |
index b-tree in the database file for each <a href="withoutrowid.html">WITHOUT ROWID</a> table. |
| 729 |
The b-tree corresponding to the sqlite_schema table is always a table |
| 730 |
b-tree and always has a root page of 1. |
| 731 |
The sqlite_schema table contains the root page number for every other |
| 732 |
table and index in the database file.</p> |
| 733 |
|
| 734 |
<p>Each entry in a table b-tree consists of a 64-bit signed integer key |
| 735 |
and up to 2147483647 bytes of arbitrary data. (The key of a table b-tree |
| 736 |
corresponds to the <a href="lang_createtable.html#rowid">rowid</a> of the SQL table that the b-tree implements.) |
| 737 |
Interior table b-trees hold only keys and pointers to children. |
| 738 |
All data is contained in the table b-tree leaves.</p> |
| 739 |
|
| 740 |
<p>Each entry in an index b-tree consists of an arbitrary key of up |
| 741 |
to 2147483647 bytes in length and no data.</p> |
| 742 |
|
| 743 |
<a name="cell_payload"></a> |
| 744 |
|
| 745 |
<p>Define the "payload" of a cell to be the arbitrary length section |
| 746 |
of the cell. For an index b-tree, the key is always arbitrary in length |
| 747 |
and hence the payload is the key. There are no arbitrary length elements |
| 748 |
in the cells of interior table b-tree pages and so those cells have no |
| 749 |
payload. Table b-tree leaf pages contain arbitrary length content and |
| 750 |
so for cells on those pages the payload is the content. |
| 751 |
</p><p>When the size of payload for a cell exceeds a certain threshold (to |
| 752 |
be defined later) then only the first few bytes of the payload |
| 753 |
are stored on the b-tree page and the balance is stored in a linked list |
| 754 |
of content overflow pages.</p> |
| 755 |
|
| 756 |
<p>A b-tree page is divided into regions in the following order: |
| 757 |
|
| 758 |
</p><ol> |
| 759 |
<li>The 100-byte database file header (found on page 1 only) |
| 760 |
</li><li>The 8 or 12 byte b-tree page header |
| 761 |
</li><li>The cell pointer array |
| 762 |
</li><li>Unallocated space |
| 763 |
</li><li>The cell content area |
| 764 |
</li><li>The reserved region |
| 765 |
</li></ol> |
| 766 |
|
| 767 |
|
| 768 |
<p>The 100-byte database file header is found only on page 1, which is |
| 769 |
always a table b-tree page. All other b-tree pages in the database file |
| 770 |
omit this 100-byte header.</p> |
| 771 |
|
| 772 |
<p>The reserved region is an area of unused space at the end of every |
| 773 |
page (except the locking page) that extensions can use to hold per-page |
| 774 |
information. The size of the reserved region is determined by the one-byte |
| 775 |
unsigned integer found at an offset of 20 into the database file header. |
| 776 |
The size of the reserved region is usually zero.</p> |
| 777 |
|
| 778 |
<p>The b-tree page header is 8 bytes in size for leaf pages and 12 |
| 779 |
bytes for interior pages. All multibyte values in the page header |
| 780 |
are big-endian. |
| 781 |
The b-tree page header is composed of the following fields:</p> |
| 782 |
|
| 783 |
<center> |
| 784 |
<i>B-tree Page Header Format</i><br> |
| 785 |
<table border="1" width="80%"> |
| 786 |
<tr><th>Offset</th><th>Size</th><th>Description |
| 787 |
</th></tr><tr><td align="center" valign="top">0</td><td align="center" valign="top">1</td><td align="left"> |
| 788 |
The one-byte flag at offset 0 indicating the b-tree page type.<ul> |
| 789 |
<li>A value of 2 (0x02) means the page is an interior index b-tree page. |
| 790 |
</li><li>A value of 5 (0x05) means the page is an interior table b-tree page. |
| 791 |
</li><li>A value of 10 (0x0a) means the page is a leaf index b-tree page. |
| 792 |
</li><li>A value of 13 (0x0d) means the page is a leaf table b-tree page.</li></ul> |
| 793 |
Any other value for the b-tree page type is an error. |
| 794 |
</td></tr><tr><td align="center" valign="top">1</td><td align="center" valign="top">2</td><td align="left"> |
| 795 |
The two-byte integer at offset 1 gives the start of the |
| 796 |
first freeblock on the page, or is zero if there are no freeblocks. |
| 797 |
</td></tr><tr><td align="center" valign="top">3</td><td align="center" valign="top">2</td><td align="left"> |
| 798 |
The two-byte integer at offset 3 gives the number of cells on the page. |
| 799 |
</td></tr><tr><td align="center" valign="top">5</td><td align="center" valign="top">2</td><td align="left"> |
| 800 |
The two-byte integer at offset 5 designates the start of the cell content |
| 801 |
area. A zero value for this integer is interpreted as 65536. |
| 802 |
</td></tr><tr><td align="center" valign="top">7</td><td align="center" valign="top">1</td><td align="left"> |
| 803 |
The one-byte integer at offset 7 gives the number of fragmented free |
| 804 |
bytes within the cell content area. |
| 805 |
</td></tr><tr><td align="center" valign="top">8</td><td align="center" valign="top">4</td><td align="left"> |
| 806 |
The four-byte page number at offset 8 is the right-most pointer. This |
| 807 |
value appears in the header of interior b-tree pages only and is omitted from |
| 808 |
all other pages. |
| 809 |
</td></tr></table></center> |
| 810 |
|
| 811 |
<p>The cell pointer array of a b-tree page immediately follows the b-tree |
| 812 |
page header. Let K be the number of cells on the btree. The cell pointer |
| 813 |
array consists of K 2-byte integer offsets to the cell contents. The |
| 814 |
cell pointers are arranged in key order with left-most cell (the cell with the |
| 815 |
smallest key) first and the right-most cell (the cell with the largest |
| 816 |
key) last.</p> |
| 817 |
|
| 818 |
<p>Cell content is stored in the cell content region of the b-tree page. |
| 819 |
SQLite strives to place cells as far toward the end of the b-tree page as |
| 820 |
it can, in order to leave space for future growth of the cell pointer array. |
| 821 |
The area in between the last cell pointer array entry and the beginning of |
| 822 |
the first cell is the unallocated region. |
| 823 |
</p> |
| 824 |
|
| 825 |
<p>If a page contains no cells (which is only possible for a root page |
| 826 |
of a table that contains no rows) then the offset to the |
| 827 |
cell content area will equal the page size minus the bytes of reserved space. |
| 828 |
If the database uses a 65536-byte page size and the reserved space is zero |
| 829 |
(the usual value for reserved space) then the cell content offset of an |
| 830 |
empty page wants to be 65536. |
| 831 |
However, that integer is too large to be stored in a |
| 832 |
2-byte unsigned integer, so a value of 0 is used in its place. |
| 833 |
|
| 834 |
</p><p>A freeblock is a structure used to identify unallocated space within |
| 835 |
a b-tree page. Freeblocks are organized as a chain. The first 2 bytes of |
| 836 |
a freeblock are a big-endian integer which is the offset in the b-tree page |
| 837 |
of the next freeblock in the chain, or zero if the freeblock is the last on |
| 838 |
the chain. The third and fourth bytes of each freeblock form |
| 839 |
a big-endian integer which is the size of the freeblock in bytes, including |
| 840 |
the 4-byte header. Freeblocks are always connected in order |
| 841 |
of increasing offset. The second field of the b-tree page header is the |
| 842 |
offset of the first freeblock, or zero if there are no freeblocks on the |
| 843 |
page. In a well-formed b-tree page, there will always be at least one cell |
| 844 |
before the first freeblock.</p> |
| 845 |
|
| 846 |
<p>A freeblock requires at least 4 bytes of space. If there is an isolated |
| 847 |
group of 1, 2, or 3 unused bytes within the cell content area, those bytes |
| 848 |
comprise a fragment. The total number of bytes in all fragments is stored |
| 849 |
in the fifth field of the b-tree page header. In a well-formed b-tree page, |
| 850 |
the total number of bytes in fragments may not exceed 60.</p> |
| 851 |
|
| 852 |
<p>The total amount of free space on a b-tree page consists of the size |
| 853 |
of the unallocated region plus the total size of all freeblocks plus the |
| 854 |
number of fragmented free bytes. SQLite may from time to time reorganize |
| 855 |
a b-tree page so that there are no freeblocks or fragment bytes, all |
| 856 |
unused bytes are contained in the unallocated space region, and all |
| 857 |
cells are packed tightly at the end of the page. This is called |
| 858 |
"defragmenting" the b-tree page.</p> |
| 859 |
|
| 860 |
<a name="varint"></a> |
| 861 |
|
| 862 |
|
| 863 |
<p>A variable-length integer or "varint" is a static Huffman encoding |
| 864 |
of 64-bit twos-complement integers that uses less space for small positive |
| 865 |
values. |
| 866 |
A varint is between 1 and 9 bytes in length. The varint consists of either |
| 867 |
zero or more bytes which have the high-order bit set followed by a single byte |
| 868 |
with the high-order bit clear, or nine bytes, whichever is shorter. |
| 869 |
The lower seven bits of each of the first eight bytes and all 8 bits of |
| 870 |
the ninth byte are used to reconstruct the 64-bit twos-complement integer. |
| 871 |
Varints are big-endian: bits taken from the earlier byte of the varint |
| 872 |
are more significant than bits taken from the later bytes. </p> |
| 873 |
|
| 874 |
<p>The format of a cell depends on which kind of b-tree page the cell |
| 875 |
appears on. The following table shows the elements of a cell, in |
| 876 |
order of appearance, for the various b-tree page types. |
| 877 |
|
| 878 |
</p><dl> |
| 879 |
<dt><p>Table B-Tree Leaf Cell (header 0x0d):</p></dt> |
| 880 |
<dd><p></p><ul> |
| 881 |
<li>A varint which is the total number of bytes of payload, including any |
| 882 |
overflow |
| 883 |
</li><li>A varint which is the integer key, a.k.a. "<a href="lang_createtable.html#rowid">rowid</a>" |
| 884 |
</li><li>The initial portion of the payload that does not spill to overflow |
| 885 |
pages. |
| 886 |
</li><li>A 4-byte big-endian integer page number for the first page of the |
| 887 |
overflow page list - omitted if all payload fits on the b-tree page. |
| 888 |
</li></ul></dd> |
| 889 |
|
| 890 |
<dt><p>Table B-Tree Interior Cell (header 0x05):</p></dt> |
| 891 |
<dd><p></p><ul> |
| 892 |
<li>A 4-byte big-endian page number which is the left child pointer. |
| 893 |
</li><li>A varint which is the integer key |
| 894 |
</li></ul></dd> |
| 895 |
|
| 896 |
<dt><p>Index B-Tree Leaf Cell (header 0x0a):</p></dt> |
| 897 |
<dd><p></p><ul> |
| 898 |
<li>A varint which is the total number of bytes of key payload, including any |
| 899 |
overflow |
| 900 |
</li><li>The initial portion of the payload that does not spill to overflow |
| 901 |
pages. |
| 902 |
</li><li>A 4-byte big-endian integer page number for the first page of the |
| 903 |
overflow page list - omitted if all payload fits on the b-tree page. |
| 904 |
</li></ul></dd> |
| 905 |
|
| 906 |
<dt><p>Index B-Tree Interior Cell (header 0x02):</p></dt> |
| 907 |
<dd><p></p><ul> |
| 908 |
<li>A 4-byte big-endian page number which is the left child pointer. |
| 909 |
</li><li>A varint which is the total number of bytes of key payload, including any |
| 910 |
overflow |
| 911 |
</li><li>The initial portion of the payload that does not spill to overflow |
| 912 |
pages. |
| 913 |
</li><li>A 4-byte big-endian integer page number for the first page of the |
| 914 |
overflow page list - omitted if all payload fits on the b-tree page. |
| 915 |
</li></ul></dd> |
| 916 |
</dl> |
| 917 |
|
| 918 |
<p>The information above can be recast into a table format as follows:</p> |
| 919 |
|
| 920 |
<a name="cellformat"></a> |
| 921 |
|
| 922 |
<center> |
| 923 |
<i>B-tree Cell Format</i> |
| 924 |
<table border="1" width="80%"> |
| 925 |
<tr><th rowspan="2">Datatype |
| 926 |
</th><th colspan="4">Appears in... |
| 927 |
</th><th rowspan="2">Description |
| 928 |
</th></tr><tr><th>Table Leaf (0x0d) |
| 929 |
</th><th>Table Interior (0x05) |
| 930 |
</th><th>Index Leaf (0x0a) |
| 931 |
</th><th>Index Interior (0x02) |
| 932 |
</th></tr><tr><td align="center" valign="top">4-byte integer |
| 933 |
</td><td align="center" valign="top"> |
| 934 |
</td><td align="center" valign="top">✔ |
| 935 |
</td><td align="center" valign="top"> |
| 936 |
</td><td align="center" valign="top">✔ |
| 937 |
</td><td align="left">Page number of left child |
| 938 |
</td></tr><tr><td align="center" valign="top">varint |
| 939 |
</td><td align="center" valign="top">✔ |
| 940 |
</td><td align="center" valign="top"> |
| 941 |
</td><td align="center" valign="top">✔ |
| 942 |
</td><td align="center" valign="top">✔ |
| 943 |
</td><td align="left">Number of bytes of payload |
| 944 |
</td></tr><tr><td align="center" valign="top">varint |
| 945 |
</td><td align="center" valign="top">✔ |
| 946 |
</td><td align="center" valign="top">✔ |
| 947 |
</td><td align="center" valign="top"> |
| 948 |
</td><td align="center" valign="top"> |
| 949 |
</td><td align="left">Rowid |
| 950 |
</td></tr><tr><td align="center" valign="top">byte array |
| 951 |
</td><td align="center" valign="top">✔ |
| 952 |
</td><td align="center" valign="top"> |
| 953 |
</td><td align="center" valign="top">✔ |
| 954 |
</td><td align="center" valign="top">✔ |
| 955 |
</td><td align="left">Payload |
| 956 |
</td></tr><tr><td align="center" valign="top">4-byte integer |
| 957 |
</td><td align="center" valign="top">✔ |
| 958 |
</td><td align="center" valign="top"> |
| 959 |
</td><td align="center" valign="top">✔ |
| 960 |
</td><td align="center" valign="top">✔ |
| 961 |
</td><td align="left">Page number of first overflow page |
| 962 |
</td></tr></table></center> |
| 963 |
|
| 964 |
|
| 965 |
<p>The amount of payload that spills onto overflow pages also depends on |
| 966 |
the page type. For the following computations, let U be the usable size |
| 967 |
of a database page, the total page size less the reserved space at the |
| 968 |
end of each page. And let P be the payload size. In the following, |
| 969 |
symbol X represents the maximum amount of payload that can be stored directly |
| 970 |
on the b-tree page without spilling onto an overflow page and symbol M |
| 971 |
represents the minimum amount of payload that must be stored on the btree |
| 972 |
page before spilling is allowed. |
| 973 |
|
| 974 |
</p><dl> |
| 975 |
<dt><p>Table B-Tree Leaf Cell:</p></dt> |
| 976 |
<dd><p> |
| 977 |
Let X be U-35. If the payload size P is less than or equal to X then |
| 978 |
the entire payload is stored on the b-tree leaf page. |
| 979 |
Let M be ((U-12)*32/255)-23 and let K be M+((P-M)%(U-4)). |
| 980 |
If P is greater than X |
| 981 |
then the number of bytes stored on the table b-tree leaf page is K |
| 982 |
if K is less or equal to X or M otherwise. |
| 983 |
The number of bytes stored on the leaf page is never less than M. |
| 984 |
</p></dd> |
| 985 |
|
| 986 |
<dt><p>Table B-Tree Interior Cell:</p></dt> |
| 987 |
<dd><p> |
| 988 |
Interior pages of table b-trees have no payload and so there is never |
| 989 |
any payload to spill. |
| 990 |
</p></dd> |
| 991 |
|
| 992 |
<dt><p>Index B-Tree Leaf Or Interior Cell:</p></dt> |
| 993 |
<dd><p> |
| 994 |
Let X be ((U-12)*64/255)-23. If the payload size P is less than |
| 995 |
or equal to X then the entire payload is stored on the b-tree page. |
| 996 |
Let M be ((U-12)*32/255)-23 and let K be M+((P-M)%(U-4)). |
| 997 |
If P is greater than X then the number |
| 998 |
of bytes stored on the index b-tree page is K if K is less than or |
| 999 |
equal to X or M otherwise. |
| 1000 |
The number of bytes stored on the index page is never less than M. |
| 1001 |
</p></dd> |
| 1002 |
</dl> |
| 1003 |
|
| 1004 |
<p>Here is an alternative description of the same computation: |
| 1005 |
|
| 1006 |
</p><ul> |
| 1007 |
<li>X is U-35 for table btree leaf pages or |
| 1008 |
((U-12)*64/255)-23 for index pages. |
| 1009 |
</li><li>M is always ((U-12)*32/255)-23. |
| 1010 |
</li><li>Let K be M+((P-M)%(U-4)). |
| 1011 |
</li><li>If P<=X then all P bytes of payload are stored directly on the |
| 1012 |
btree page without overflow. |
| 1013 |
</li><li>If P>X and K<=X then the first K bytes of P are stored on the |
| 1014 |
btree page and the remaining P-K bytes are stored on overflow pages. |
| 1015 |
</li><li>If P>X and K>X then the first M bytes of P are stored on the |
| 1016 |
btree page and the remaining P-M bytes are stored on overflow pages. |
| 1017 |
</li></ul> |
| 1018 |
|
| 1019 |
<p>The overflow thresholds are designed to give a minimum fanout of |
| 1020 |
4 for index b-trees and to make sure enough of the payload |
| 1021 |
is on the b-tree page that the record header can usually be accessed |
| 1022 |
without consulting an overflow page. In hindsight, the designer of |
| 1023 |
the SQLite b-tree logic realized that these thresholds could have been |
| 1024 |
made much simpler. However, the computations cannot be changed |
| 1025 |
without resulting in an incompatible file format. And the current computations |
| 1026 |
work well, even if they are a little complex.</p> |
| 1027 |
|
| 1028 |
<a name="ovflpgs"></a> |
| 1029 |
|
| 1030 |
<h2 id="cell_payload_overflow_pages"><span>1.7. </span>Cell Payload Overflow Pages</h2> |
| 1031 |
|
| 1032 |
<p>When the payload of a b-tree cell is too large for the b-tree page, |
| 1033 |
the surplus is spilled onto overflow pages. Overflow pages form a linked |
| 1034 |
list. The first four bytes of each overflow page are a big-endian |
| 1035 |
integer which is the page number of the next page in the chain, or zero |
| 1036 |
for the final page in the chain. The fifth byte through the last usable |
| 1037 |
byte are used to hold overflow content.</p> |
| 1038 |
|
| 1039 |
<h2 id="pointer_map_or_ptrmap_pages"><span>1.8. </span>Pointer Map or Ptrmap Pages</h2> |
| 1040 |
|
| 1041 |
<p>Pointer map or ptrmap pages are extra pages inserted into the database |
| 1042 |
to make the operation of <a href="pragma.html#pragma_auto_vacuum">auto_vacuum</a> and <a href="pragma.html#pragma_incremental_vacuum">incremental_vacuum</a> modes |
| 1043 |
more efficient. Other page types in the database typically have pointers |
| 1044 |
from parent to child. For example, an interior b-tree page contains pointers |
| 1045 |
to its child b-tree pages and an overflow chain has a pointer |
| 1046 |
from earlier to later links in the chain. A ptrmap page contains linkage |
| 1047 |
information going in the opposite direction, from child to parent.</p> |
| 1048 |
|
| 1049 |
<p>Ptrmap pages must exist in any database file which has a non-zero |
| 1050 |
largest root b-tree page value at offset 52 in the database header. |
| 1051 |
If the largest root b-tree page value is zero, then the database must not |
| 1052 |
contain ptrmap pages.</p> |
| 1053 |
|
| 1054 |
<p>In a database with ptrmap pages, the first ptrmap page is page 2. |
| 1055 |
A ptrmap page consists of an array of 5-byte entries. Let J be the |
| 1056 |
number of 5-byte entries that will fit in the usable space of a page. |
| 1057 |
(In other words, J=U/5.) The first ptrmap page will contain back pointer |
| 1058 |
information for pages 3 through J+2, inclusive. The second pointer map |
| 1059 |
page will be on page J+3 and that ptrmap page will provide back pointer |
| 1060 |
information for pages J+4 through 2*J+3 inclusive. And so forth for |
| 1061 |
the entire database file.</p> |
| 1062 |
|
| 1063 |
<p>In a database that uses ptrmap pages, all pages at locations identified |
| 1064 |
by the computation in the previous paragraph must be ptrmap page and no |
| 1065 |
other page may be a ptrmap page. Except, if the byte-lock page happens to |
| 1066 |
fall on the same page number as a ptrmap page, then the ptrmap is moved |
| 1067 |
to the following page for that one case.</p> |
| 1068 |
|
| 1069 |
<p>Each 5-byte entry on a ptrmap page provides back-link information about |
| 1070 |
one of the pages that immediately follow the pointer map. If page B is a |
| 1071 |
ptrmap page then back-link information about page B+1 is provided by |
| 1072 |
the first entry on the pointer map. Information about page B+2 is |
| 1073 |
provided by the second entry. And so forth.</p> |
| 1074 |
|
| 1075 |
<p>Each 5-byte ptrmap entry consists of one byte of "page type" information |
| 1076 |
followed by a 4-byte big-endian page number. Five page types are recognized: |
| 1077 |
</p> |
| 1078 |
|
| 1079 |
<ol> |
| 1080 |
<li>A b-tree root page. The |
| 1081 |
page number should be zero. |
| 1082 |
</li><li>A freelist page. The page number should be |
| 1083 |
zero. |
| 1084 |
</li><li>The first page of a |
| 1085 |
cell payload overflow chain. The page number is the b-tree page that |
| 1086 |
contains the cell whose content has overflowed. |
| 1087 |
</li><li>A page in an overflow chain |
| 1088 |
other than the first page. The page number is the prior page of the |
| 1089 |
overflow chain. |
| 1090 |
</li><li>A non-root b-tree page. The |
| 1091 |
page number is the parent b-tree page. |
| 1092 |
</li></ol> |
| 1093 |
|
| 1094 |
<p>In any database file that contains ptrmap pages, all b-tree root pages |
| 1095 |
must come before any non-root b-tree page, cell payload overflow page, or |
| 1096 |
freelist page. This restriction ensures that a root page will never |
| 1097 |
be moved during an auto-vacuum or incremental-vacuum. The auto-vacuum |
| 1098 |
logic does not know how to update the root_page field of the sqlite_schema |
| 1099 |
table and so it is necessary to prevent root pages from being moved |
| 1100 |
during an auto-vacuum in order to preserve the integrity of the |
| 1101 |
sqlite_schema table. Root pages are moved to the beginning of the |
| 1102 |
database file by the CREATE TABLE, CREATE INDEX, DROP TABLE, and |
| 1103 |
DROP INDEX operations.</p> |
| 1104 |
|
| 1105 |
<h1 id="schema_layer"><span>2. </span>Schema Layer</h1> |
| 1106 |
|
| 1107 |
<p>The foregoing text describes low-level aspects of the SQLite file |
| 1108 |
format. The b-tree mechanism provides a powerful and efficient means of |
| 1109 |
accessing a large data set. This section will describe how the |
| 1110 |
low-level b-tree layer is used to implement higher-level SQL |
| 1111 |
capabilities.</p> |
| 1112 |
|
| 1113 |
<a name="record_format"></a> |
| 1114 |
|
| 1115 |
<h2 id="record_format"><span>2.1. </span>Record Format</h2> |
| 1116 |
|
| 1117 |
<p>The data for a table b-tree leaf page and the key |
| 1118 |
of an index b-tree page was characterized above |
| 1119 |
as an arbitrary sequence of bytes. |
| 1120 |
The prior discussion mentioned one key being less than another, but |
| 1121 |
did not define what "less than" meant. The current section will address |
| 1122 |
these omissions.</p> |
| 1123 |
|
| 1124 |
<p>Payload, either table b-tree data or index b-tree keys, |
| 1125 |
is always in the "record format". |
| 1126 |
The record format defines a sequence of values corresponding |
| 1127 |
to columns in a table or index. The record format specifies the number |
| 1128 |
of columns, the datatype of each column, and the content of each column.</p> |
| 1129 |
|
| 1130 |
<p>The record format makes extensive use of the |
| 1131 |
<a href="fileformat2.html#varint">variable-length integer</a> or <a href="fileformat2.html#varint">varint</a> |
| 1132 |
representation of 64-bit signed integers defined above.</p> |
| 1133 |
|
| 1134 |
<a name="serialtype"></a> |
| 1135 |
|
| 1136 |
<p>A record contains a header and a body, in that order. |
| 1137 |
The header begins with a single varint which determines the total number |
| 1138 |
of bytes in the header. The varint value is the size of the header in |
| 1139 |
bytes including the size varint itself. Following the size varint are |
| 1140 |
one or more additional varints, one per column. These additional varints |
| 1141 |
are called "serial type" numbers and |
| 1142 |
determine the datatype of each column, according to the following chart:</p> |
| 1143 |
|
| 1144 |
<center> |
| 1145 |
<i>Serial Type Codes Of The Record Format</i><br> |
| 1146 |
<table width="80%" border="1"> |
| 1147 |
<tr><th>Serial Type</th><th>Content Size</th><th>Meaning |
| 1148 |
</th></tr><tr><td valign="top" align="center">0</td><td valign="top" align="center">0</td><td align="left"> |
| 1149 |
Value is a NULL. |
| 1150 |
</td></tr><tr><td valign="top" align="center">1</td><td valign="top" align="center">1</td><td align="left"> |
| 1151 |
Value is an 8-bit twos-complement integer. |
| 1152 |
</td></tr><tr><td valign="top" align="center">2</td><td valign="top" align="center">2</td><td align="left"> |
| 1153 |
Value is a big-endian 16-bit twos-complement integer. |
| 1154 |
</td></tr><tr><td valign="top" align="center">3</td><td valign="top" align="center">3</td><td align="left"> |
| 1155 |
Value is a big-endian 24-bit twos-complement integer. |
| 1156 |
</td></tr><tr><td valign="top" align="center">4</td><td valign="top" align="center">4</td><td align="left"> |
| 1157 |
Value is a big-endian 32-bit twos-complement integer. |
| 1158 |
</td></tr><tr><td valign="top" align="center">5</td><td valign="top" align="center">6</td><td align="left"> |
| 1159 |
Value is a big-endian 48-bit twos-complement integer. |
| 1160 |
</td></tr><tr><td valign="top" align="center">6</td><td valign="top" align="center">8</td><td align="left"> |
| 1161 |
Value is a big-endian 64-bit twos-complement integer. |
| 1162 |
</td></tr><tr><td valign="top" align="center">7</td><td valign="top" align="center">8</td><td align="left"> |
| 1163 |
Value is a big-endian IEEE 754-2008 64-bit floating point number. |
| 1164 |
</td></tr><tr><td valign="top" align="center">8</td><td valign="top" align="center">0</td><td align="left"> |
| 1165 |
Value is the integer 0. (Only available for <a href="fileformat2.html#schemaformat">schema format</a> 4 and higher.) |
| 1166 |
</td></tr><tr><td valign="top" align="center">9</td><td valign="top" align="center">0</td><td align="left"> |
| 1167 |
Value is the integer 1. (Only available for <a href="fileformat2.html#schemaformat">schema format</a> 4 and higher.) |
| 1168 |
</td></tr><tr><td valign="top" align="center">10,11 |
| 1169 |
</td><td valign="top" align="center"><i>variable</i></td><td align="left"> |
| 1170 |
<i>Reserved for internal use. These serial type codes will |
| 1171 |
never appear in a well-formed database file, but they |
| 1172 |
might be used in transient and temporary database files |
| 1173 |
that SQLite sometimes generates for its own use. |
| 1174 |
The meanings of these codes can shift from one release |
| 1175 |
of SQLite to the next.</i> |
| 1176 |
</td></tr><tr><td valign="top" align="center">N≥12 and even |
| 1177 |
</td><td valign="top" align="center">(N-12)/2</td><td align="left"> |
| 1178 |
Value is a BLOB that is (N-12)/2 bytes in length. |
| 1179 |
</td></tr><tr><td valign="top" align="center">N≥13 and odd |
| 1180 |
</td><td valign="top" align="center">(N-13)/2</td><td align="left"> |
| 1181 |
Value is a string in the <a href="fileformat2.html#enc">text encoding</a> and (N-13)/2 bytes in length. |
| 1182 |
The nul terminator is not stored. |
| 1183 |
</td></tr></table></center> |
| 1184 |
|
| 1185 |
<p>The header size varint |
| 1186 |
and serial type varints will usually consist of a single byte. The |
| 1187 |
serial type varints for large strings and BLOBs might extend to two or three |
| 1188 |
byte varints, but that is the exception rather than the rule. |
| 1189 |
The varint format is very efficient at coding the record header.</p> |
| 1190 |
|
| 1191 |
<p>The values for each column in the record immediately follow the header. |
| 1192 |
For serial types 0, 8, 9, 12, and 13, the value is zero bytes in |
| 1193 |
length. If all columns are of these types then the body section of the |
| 1194 |
record is empty.</p> |
| 1195 |
|
| 1196 |
<p>A record might have fewer values than the number of columns in the |
| 1197 |
corresponding table. This can happen, for example, after an |
| 1198 |
<a href="lang_altertable.html">ALTER TABLE ... ADD COLUMN</a> SQL statement has increased |
| 1199 |
the number of columns in the table schema without modifying preexisting rows |
| 1200 |
in the table. |
| 1201 |
Missing values at the end of the record are filled in using the |
| 1202 |
<a href="lang_createtable.html#dfltval">default value</a> for the corresponding columns defined in the table schema. |
| 1203 |
</p> |
| 1204 |
|
| 1205 |
|
| 1206 |
<h2 id="record_sort_order"><span>2.2. </span>Record Sort Order</h2> |
| 1207 |
|
| 1208 |
<p>The order of keys in an index b-tree is determined by the sort order of |
| 1209 |
the records that the keys represent. Record comparison progresses column |
| 1210 |
by column. Columns of a record are examined from left to right. The |
| 1211 |
first pair of columns that are not equal determines the relative order |
| 1212 |
of the two records. The sort order of individual columns is as |
| 1213 |
follows:</p> |
| 1214 |
|
| 1215 |
<ol> |
| 1216 |
<li>NULL values (serial type 0) sort first. |
| 1217 |
</li><li>Numeric values (serial types 1 through 9) sort after NULLs |
| 1218 |
and in numeric order. |
| 1219 |
</li><li>Text values (odd serial types 13 and larger) sort after numeric |
| 1220 |
values in the order determined by the columns <a href="datatype3.html#collation">collating function</a>. |
| 1221 |
</li><li>BLOB values (even serial types 12 and larger) sort last and in the order |
| 1222 |
determined by memcmp(). |
| 1223 |
</li></ol> |
| 1224 |
|
| 1225 |
<p>A <a href="datatype3.html#collation">collating function</a> for each column is necessary in order to compute |
| 1226 |
the order of text fields. |
| 1227 |
SQLite defines three built-in collating functions: |
| 1228 |
</p> |
| 1229 |
|
| 1230 |
<blockquote><table border="0" cellspacing="10"> |
| 1231 |
<tr><td valign="top">BINARY |
| 1232 |
</td><td> The built-in BINARY collation compares strings byte by byte |
| 1233 |
using the memcmp() function |
| 1234 |
from the standard C library. |
| 1235 |
</td></tr><tr><td valign="top">NOCASE |
| 1236 |
</td><td> The NOCASE collation is like BINARY except that uppercase |
| 1237 |
ASCII characters ('A' through 'Z') |
| 1238 |
are folded into their lowercase equivalents prior to running the |
| 1239 |
comparison. Only ASCII characters are case-folded. |
| 1240 |
NOCASE |
| 1241 |
does not implement a general purpose unicode caseless comparison. |
| 1242 |
</td></tr><tr><td valign="top">RTRIM |
| 1243 |
</td><td> RTRIM is like BINARY except that extra spaces at the end of either |
| 1244 |
string do not change the result. In other words, strings will |
| 1245 |
compare equal to one another as long as they |
| 1246 |
differ only in the number of spaces at the end. |
| 1247 |
</td></tr></table></blockquote> |
| 1248 |
|
| 1249 |
<p>Additional application-specific collating functions can be added to |
| 1250 |
SQLite using the <a href="c3ref/create_collation.html">sqlite3_create_collation()</a> interface.</p> |
| 1251 |
|
| 1252 |
<p>The default collating function for all strings is BINARY. |
| 1253 |
Alternative collating functions for table columns can be specified in the |
| 1254 |
<a href="lang_createtable.html">CREATE TABLE</a> statement using the COLLATE clause on the <a href="lang_createtable.html#tablecoldef">column definition</a>. |
| 1255 |
When a column is indexed, the same collating function specified in the |
| 1256 |
<a href="lang_createtable.html">CREATE TABLE</a> statement is used for the column in the index, by default, |
| 1257 |
though this can be overridden using a COLLATE clause in the |
| 1258 |
<a href="lang_createindex.html">CREATE INDEX</a> statement. |
| 1259 |
|
| 1260 |
<a name="#sqltab"></a> |
| 1261 |
|
| 1262 |
</p><h2 id="representation_of_sql_tables"><span>2.3. </span>Representation Of SQL Tables</h2> |
| 1263 |
|
| 1264 |
<p> Each ordinary SQL table in the database schema is represented on-disk |
| 1265 |
by a table b-tree. Each entry in the table b-tree corresponds to a row |
| 1266 |
of the SQL table. The <a href="lang_createtable.html#rowid">rowid</a> of the SQL table is the 64-bit signed |
| 1267 |
integer key for each entry in the table b-tree.</p> |
| 1268 |
|
| 1269 |
<p> The content of each SQL table row is stored in the database file by |
| 1270 |
first combining the values in the various columns into a byte array |
| 1271 |
in the record format, then storing that byte array as the payload in |
| 1272 |
an entry in the table b-tree. The order of values in the record is |
| 1273 |
the same as the order of columns in the SQL table definition. |
| 1274 |
When an SQL table includes an |
| 1275 |
<a href="lang_createtable.html#rowid">INTEGER PRIMARY KEY</a> column (which aliases the <a href="lang_createtable.html#rowid">rowid</a>) then that |
| 1276 |
column appears in the record as a NULL value. SQLite will always use |
| 1277 |
the table b-tree key rather than the NULL value when referencing the |
| 1278 |
<a href="lang_createtable.html#rowid">INTEGER PRIMARY KEY</a> column.</p> |
| 1279 |
|
| 1280 |
<p> If the <a href="datatype3.html#affinity">affinity</a> of a column is REAL and that column contains a |
| 1281 |
value that can be converted to an integer without loss of information |
| 1282 |
(if the value contains no fractional part and is not too large to be |
| 1283 |
represented as an integer) then the column may be stored in the record |
| 1284 |
as an integer. SQLite will convert the value back to floating |
| 1285 |
point when extracting it from the record.</p> |
| 1286 |
|
| 1287 |
<h2 id="representation_of_without_rowid_tables"><span>2.4. </span>Representation of WITHOUT ROWID Tables</h2> |
| 1288 |
|
| 1289 |
<p>If an SQL table is created using the "WITHOUT ROWID" clause at the |
| 1290 |
end of its CREATE TABLE statement, then that table is a <a href="withoutrowid.html">WITHOUT ROWID</a> |
| 1291 |
table and uses a different on-disk representation. A WITHOUT ROWID |
| 1292 |
table uses an index b-tree rather than a table b-tree for storage. |
| 1293 |
The key for each entry in the WITHOUT ROWID b-tree is a record composed |
| 1294 |
of the columns of the PRIMARY KEY followed by all remaining columns of |
| 1295 |
the table. The primary key columns appear in the order that they were |
| 1296 |
declared in the PRIMARY KEY clause and the remaining columns appear in |
| 1297 |
the order they occur in the CREATE TABLE statement. |
| 1298 |
|
| 1299 |
</p><p>Hence, the content encoding for a WITHOUT ROWID table is the same |
| 1300 |
as the content encoding for an ordinary rowid table, except that the |
| 1301 |
order of the columns is rearranged so that PRIMARY KEY columns come |
| 1302 |
first, and the content is used as the key in an index b-tree rather |
| 1303 |
than as the data in a table b-tree. |
| 1304 |
The special encoding rules for columns with REAL affinity |
| 1305 |
apply to WITHOUT ROWID tables the same as they do with rowid tables. |
| 1306 |
|
| 1307 |
</p><h3 id="suppression_of_redundant_columns_in_the_primary_key_of_without_rowid_tables"><span>2.4.1. </span>Suppression of redundant columns in the PRIMARY KEY |
| 1308 |
of WITHOUT ROWID tables</h3> |
| 1309 |
|
| 1310 |
<p>If the PRIMARY KEY of a WITHOUT ROWID tables uses the same columns |
| 1311 |
with the same collating sequence more than once, then the second and |
| 1312 |
subsequent occurrences of that column in the PRIMARY KEY definition are |
| 1313 |
ignored. For example, the following CREATE TABLE statements all specify |
| 1314 |
the same table, which will have the exact same representation on disk: |
| 1315 |
|
| 1316 |
</p><blockquote><pre> |
| 1317 |
CREATE TABLE t1(a,b,c,d,PRIMARY KEY(a,c)) WITHOUT ROWID; |
| 1318 |
CREATE TABLE t1(a,b,c,d,PRIMARY KEY(a,c,a,c)) WITHOUT ROWID; |
| 1319 |
CREATE TABLE t1(a,b,c,d,PRIMARY KEY(a,A,a,C)) WITHOUT ROWID; |
| 1320 |
CREATE TABLE t1(a,b,c,d,PRIMARY KEY(a,a,a,a,c)) WITHOUT ROWID; |
| 1321 |
</pre></blockquote> |
| 1322 |
|
| 1323 |
<p>The first example above is the preferred definition of the table, |
| 1324 |
of course. All of the examples create a WITHOUT ROWID table with |
| 1325 |
two PRIMARY KEY columns, "a" and "c", in that order, followed by |
| 1326 |
two data columns "b" and "d", also in that order. |
| 1327 |
|
| 1328 |
</p><h2 id="representation_of_sql_indices"><span>2.5. </span>Representation Of SQL Indices</h2> |
| 1329 |
|
| 1330 |
<p>Each SQL index, whether explicitly declared via a <a href="lang_createindex.html">CREATE INDEX</a> statement |
| 1331 |
or implied by a UNIQUE or PRIMARY KEY constraint, corresponds to an |
| 1332 |
index b-tree in the database file. |
| 1333 |
Each entry in the index b-tree corresponds to a single row in the |
| 1334 |
associated SQL table. |
| 1335 |
The key to an index b-tree is |
| 1336 |
a record composed of the columns that are being indexed followed by the |
| 1337 |
key of the corresponding table row. For ordinary tables, the row key is |
| 1338 |
the <a href="lang_createtable.html#rowid">rowid</a>, and for <a href="withoutrowid.html">WITHOUT ROWID</a> tables the row key is the PRIMARY KEY. |
| 1339 |
Because every row in the table has a unique row key, |
| 1340 |
all keys in an index are unique.</p> |
| 1341 |
|
| 1342 |
<p>In a normal index, there is a one-to-one mapping between rows in a |
| 1343 |
table and entries in each index associated with that table. |
| 1344 |
However, in a <a href="partialindex.html">partial index</a>, the index b-tree only contains entries |
| 1345 |
corresponding to table rows for which the WHERE clause expression on the |
| 1346 |
CREATE INDEX statement is true. |
| 1347 |
Corresponding rows in the index and table b-trees share the same rowid |
| 1348 |
or primary key values and contain the same value for all indexed columns.</p> |
| 1349 |
|
| 1350 |
<h3 id="suppression_of_redundant_columns_in_without_rowid_secondary_indexes_"><span>2.5.1. </span>Suppression of redundant columns in WITHOUT ROWID secondary indexes |
| 1351 |
</h3> |
| 1352 |
|
| 1353 |
<p> In an index on a WITHOUT ROWID table, if a column of the PRIMARY KEY |
| 1354 |
is also a column in the index and has a matching collating sequence, then the |
| 1355 |
indexed column is not repeated in the table-key suffix on the |
| 1356 |
end of the index record. As an example, consider the following SQL: |
| 1357 |
|
| 1358 |
</p><blockquote><pre> |
| 1359 |
CREATE TABLE ex25(a,b,c,d,e,PRIMARY KEY(d,c,a)) WITHOUT rowid; |
| 1360 |
CREATE INDEX ex25ce ON ex25(c,e); |
| 1361 |
CREATE INDEX ex25acde ON ex25(a,c,d,e); |
| 1362 |
CREATE INDEX ex25ae ON ex25(a COLLATE nocase,e); |
| 1363 |
</pre></blockquote> |
| 1364 |
|
| 1365 |
<p>Each row in the ex25ce index is a record |
| 1366 |
with these columns: c, e, d, a. The first two columns are |
| 1367 |
the columns being indexed, c and e. The remaining columns are the primary |
| 1368 |
key of the corresponding table row. Normally, the primary key would be |
| 1369 |
columns d, c, and a, but because column c already appears earlier in the |
| 1370 |
index, it is omitted from the key suffix.</p> |
| 1371 |
|
| 1372 |
<p>In the extreme case where the columns being indexed cover all columns |
| 1373 |
of the PRIMARY KEY, the index will consist of only the columns being |
| 1374 |
indexed. The ex25acde example above demonstrates this. Each entry in |
| 1375 |
the ex25acde index consists of only the columns a, c, d, and e, in that |
| 1376 |
order.</p> |
| 1377 |
|
| 1378 |
<p>Each row in ex25ae contains five columns: a, e, d, c, a. The "a" |
| 1379 |
column is repeated since the first occurrence of "a" has a collating |
| 1380 |
function of "nocase" and the second has a collating sequence of "binary". |
| 1381 |
If the "a" column is not repeated and if the table contains two or more |
| 1382 |
entries with the same "e" value and where "a" differs only in case, then |
| 1383 |
all of those table entries would correspond to a single entry in the |
| 1384 |
index, which would break the one-to-one correspondence between the table |
| 1385 |
and the index. |
| 1386 |
|
| 1387 |
</p><p> The suppression of redundant columns in the key suffix of an index |
| 1388 |
entry only occurs in WITHOUT ROWID tables. In an ordinary rowid table, |
| 1389 |
the index entry always ends with the rowid even if the <a href="lang_createtable.html#rowid">INTEGER PRIMARY KEY</a> |
| 1390 |
column is one of the columns being indexed.</p> |
| 1391 |
|
| 1392 |
<a name="ffschema"></a> |
| 1393 |
|
| 1394 |
<h2 id="storage_of_the_sql_database_schema"><span>2.6. </span>Storage Of The SQL Database Schema</h2> |
| 1395 |
|
| 1396 |
<p>Page 1 of a database file is the root page of a table b-tree that |
| 1397 |
holds a special table named "<a href="schematab.html">sqlite_schema</a>". This b-tree is known |
| 1398 |
as the "schema table" since it stores the complete |
| 1399 |
database schema. The structure of the sqlite_schema table is as |
| 1400 |
if it had been created using the following SQL:</p> |
| 1401 |
|
| 1402 |
<blockquote><pre> |
| 1403 |
CREATE TABLE sqlite_schema( |
| 1404 |
type text, |
| 1405 |
name text, |
| 1406 |
tbl_name text, |
| 1407 |
rootpage integer, |
| 1408 |
sql text |
| 1409 |
); |
| 1410 |
</pre></blockquote> |
| 1411 |
|
| 1412 |
<p>The sqlite_schema table contains one row for each table, index, view, |
| 1413 |
and trigger (collectively "objects") in the database schema, except there |
| 1414 |
is no entry for the sqlite_schema table itself. The sqlite_schema table |
| 1415 |
contains entries for <a href="fileformat2.html#intschema">internal schema objects</a> in addition to application- |
| 1416 |
and programmer-defined objects. |
| 1417 |
|
| 1418 |
|
| 1419 |
</p><p>The sqlite_schema.type column will be one |
| 1420 |
of the following text strings: 'table', 'index', 'view', or 'trigger' |
| 1421 |
according to the type of object defined. The 'table' string is used |
| 1422 |
for both ordinary and <a href="vtab.html">virtual tables</a>.</p> |
| 1423 |
|
| 1424 |
<p>The sqlite_schema.name column will hold the name of the object. |
| 1425 |
<a href="lang_createtable.html#uniqueconst">UNIQUE</a> and <a href="lang_createtable.html#primkeyconst">PRIMARY KEY</a> constraints on tables cause SQLite to create |
| 1426 |
<a href="fileformat2.html#intschema">internal indexes</a> with names of the form "sqlite_autoindex_TABLE_N" |
| 1427 |
where TABLE is replaced by the name of the table that contains the |
| 1428 |
constraint and N is an integer beginning with 1 and increasing by one |
| 1429 |
with each constraint seen in the table definition. |
| 1430 |
In a <a href="withoutrowid.html">WITHOUT ROWID</a> table, there is no sqlite_schema entry for the |
| 1431 |
PRIMARY KEY, but the "sqlite_autoindex_TABLE_N" name is set aside |
| 1432 |
for the PRIMARY KEY as if the sqlite_schema entry did exist. This |
| 1433 |
will affect the numbering of subsequent UNIQUE constraints. |
| 1434 |
The "sqlite_autoindex_TABLE_N" name is never allocated for an |
| 1435 |
<a href="lang_createtable.html#rowid">INTEGER PRIMARY KEY</a>, either in rowid tables or WITHOUT ROWID tables. |
| 1436 |
</p> |
| 1437 |
|
| 1438 |
<p>The sqlite_schema.tbl_name column holds the name of a table or view |
| 1439 |
that the object is associated with. For a table or view, the |
| 1440 |
tbl_name column is a copy of the name column. For an index, the tbl_name |
| 1441 |
is the name of the table that is indexed. For a trigger, the tbl_name |
| 1442 |
column stores the name of the table or view that causes the trigger |
| 1443 |
to fire.</p> |
| 1444 |
|
| 1445 |
<p>The sqlite_schema.rootpage column stores the page number of the root |
| 1446 |
b-tree page for tables and indexes. For rows that define views, triggers, |
| 1447 |
and virtual tables, the rootpage column is 0 or NULL.</p> |
| 1448 |
|
| 1449 |
<p>The sqlite_schema.sql column stores SQL text that describes the |
| 1450 |
object. This SQL text is a <a href="lang_createtable.html">CREATE TABLE</a>, <a href="lang_createvtab.html">CREATE VIRTUAL TABLE</a>, |
| 1451 |
<a href="lang_createindex.html">CREATE INDEX</a>, |
| 1452 |
<a href="lang_createview.html">CREATE VIEW</a>, or <a href="lang_createtrigger.html">CREATE TRIGGER</a> statement that if evaluated against |
| 1453 |
the database file when it is the main database of a <a href="c3ref/sqlite3.html">database connection</a> |
| 1454 |
would recreate the object. The text is usually a copy of the original |
| 1455 |
statement used to create the object but with normalizations applied so |
| 1456 |
that the text conforms to the following rules: |
| 1457 |
|
| 1458 |
</p><ul> |
| 1459 |
<li>The CREATE, TABLE, VIEW, TRIGGER, and INDEX keywords at the beginning |
| 1460 |
of the statement are converted to all upper case letters. |
| 1461 |
</li><li>The TEMP or TEMPORARY keyword is removed if it occurs after the |
| 1462 |
initial CREATE keyword. |
| 1463 |
</li><li>Any database name qualifier that occurs prior to the name of the |
| 1464 |
object being created is removed. |
| 1465 |
</li><li>Leading spaces are removed. |
| 1466 |
</li><li>All spaces following the first two keywords are converted into a single |
| 1467 |
space. |
| 1468 |
</li></ul> |
| 1469 |
|
| 1470 |
<p>The text in the sqlite_schema.sql column is a copy of the original |
| 1471 |
CREATE statement text that created the object, except normalized as |
| 1472 |
described above and as modified by subsequent <a href="lang_altertable.html">ALTER TABLE</a> statements. |
| 1473 |
The sqlite_schema.sql is NULL for the <a href="fileformat2.html#intschema">internal indexes</a> that are |
| 1474 |
automatically created by <a href="lang_createtable.html#uniqueconst">UNIQUE</a> or <a href="lang_createtable.html#primkeyconst">PRIMARY KEY</a> constraints.</p> |
| 1475 |
|
| 1476 |
<h3 id="alternative_names_for_the_schema_table"><span>2.6.1. </span>Alternative Names For The Schema Table</h3> |
| 1477 |
|
| 1478 |
<p>The name "sqlite_schema" does not appear anywhere in the file format. |
| 1479 |
That name is just a convention used by the database implementation. |
| 1480 |
Due to historical and operational considerations, the |
| 1481 |
"sqlite_schema" table can also sometimes be called by one of the |
| 1482 |
following aliases: |
| 1483 |
|
| 1484 |
</p><ol> |
| 1485 |
<li> sqlite_master |
| 1486 |
</li><li> sqlite_temp_schema |
| 1487 |
</li><li> sqlite_temp_master |
| 1488 |
</li></ol> |
| 1489 |
|
| 1490 |
<p>Because the name of the schema table does not appear anywhere in |
| 1491 |
the file format, the meaning of the database file is not changed if |
| 1492 |
the application chooses to refer to the schema table by one of |
| 1493 |
these alternative names. |
| 1494 |
|
| 1495 |
<a name="intschema"></a> |
| 1496 |
|
| 1497 |
</p><h3 id="internal_schema_objects"><span>2.6.2. </span>Internal Schema Objects</h3> |
| 1498 |
|
| 1499 |
<p>In addition to the tables, indexes, views, and triggers created by |
| 1500 |
the application and/or the developer using CREATE statements SQL, the |
| 1501 |
sqlite_schema table may contain zero or more entries for |
| 1502 |
<i>internal schema objects</i> that are created by SQLite for its |
| 1503 |
own internal use. The names of internal schema objects |
| 1504 |
always begin with "sqlite_" and any table, index, view, or trigger |
| 1505 |
whose name begins with "sqlite_" is an internal schema object. |
| 1506 |
SQLite prohibits applications from creating objects whose names begin |
| 1507 |
with "sqlite_". |
| 1508 |
|
| 1509 |
</p><p>Internal schema objects used by SQLite may include the following: |
| 1510 |
|
| 1511 |
</p><ul> |
| 1512 |
<li><p>Indices with names of the form "sqlite_autoindex_TABLE_N" that |
| 1513 |
are used to implement <a href="lang_createtable.html#uniqueconst">UNIQUE</a> and <a href="lang_createtable.html#primkeyconst">PRIMARY KEY</a> constraints on |
| 1514 |
ordinary tables. |
| 1515 |
|
| 1516 |
</p></li><li><p>A table with the name "sqlite_sequence" that is used to keep track |
| 1517 |
of the maximum historical <a href="lang_createtable.html#rowid">INTEGER PRIMARY KEY</a> for a table |
| 1518 |
using <a href="autoinc.html">AUTOINCREMENT</a>. |
| 1519 |
|
| 1520 |
</p></li><li><p>Tables with names of the form "sqlite_statN" where N is an integer. |
| 1521 |
Such tables store database statistics gathered by the <a href="lang_analyze.html">ANALYZE</a> |
| 1522 |
command and used by the query planner to help determine the best |
| 1523 |
algorithm to use for each query. |
| 1524 |
</p></li></ul> |
| 1525 |
|
| 1526 |
<p>New internal schema objects names, always beginning with "sqlite_", |
| 1527 |
may be added to the SQLite file format in future releases. |
| 1528 |
|
| 1529 |
<a name="seqtab"></a> |
| 1530 |
|
| 1531 |
</p><h3 id="the_sqlite_sequence_table"><span>2.6.3. </span>The sqlite_sequence table</h3> |
| 1532 |
|
| 1533 |
<p>The sqlite_sequence table is an internal table used to help implement |
| 1534 |
<a href="autoinc.html">AUTOINCREMENT</a>. The sqlite_sequence table is created automatically |
| 1535 |
whenever any ordinary table with an AUTOINCREMENT integer primary |
| 1536 |
key is created. Once created, the sqlite_sequence table exists in the |
| 1537 |
sqlite_schema table forever; it cannot be dropped. |
| 1538 |
The schema for the sqlite_sequence table is: |
| 1539 |
|
| 1540 |
</p><blockquote><pre> |
| 1541 |
CREATE TABLE sqlite_sequence(name,seq); |
| 1542 |
</pre></blockquote> |
| 1543 |
|
| 1544 |
<p>There is a single row in the sqlite_sequence table for each ordinary |
| 1545 |
table that uses AUTOINCREMENT. The name of the table (as it appears in |
| 1546 |
sqlite_schema.name) is in the sqlite_sequence.name field and the largest |
| 1547 |
<a href="lang_createtable.html#rowid">INTEGER PRIMARY KEY</a> ever inserted into that table is |
| 1548 |
in the sqlite_sequence.seq field. |
| 1549 |
New automatically generated integer primary keys for AUTOINCREMENT |
| 1550 |
tables are guaranteed to be larger than the sqlite_sequence.seq field for |
| 1551 |
that table. |
| 1552 |
If the sqlite_sequence.seq field of an AUTOINCREMENT table is already at |
| 1553 |
the largest integer value (9223372036854775807) then attempts to add new |
| 1554 |
rows to that table with an automatically generated integer primary will fail |
| 1555 |
with an <a href="rescode.html#full">SQLITE_FULL</a> error. |
| 1556 |
The sqlite_sequence.seq field is automatically updated if required when |
| 1557 |
new entries are inserted to an AUTOINCREMENT table. |
| 1558 |
The sqlite_sequence row for an AUTOINCREMENT table is automatically deleted |
| 1559 |
when the table is dropped. |
| 1560 |
If the sqlite_sequence row for an AUTOINCREMENT table does not exist when |
| 1561 |
the AUTOINCREMENT table is updated, then a new sqlite_sequence row is created. |
| 1562 |
If the sqlite_sequence.seq value for an AUTOINCREMENT table is manually |
| 1563 |
set to something other than an integer and there is a subsequent attempt to |
| 1564 |
insert the or update the AUTOINCREMENT table, then the behavior is undefined. |
| 1565 |
|
| 1566 |
</p><p>Application code is allowed to modify the sqlite_sequence table, to add |
| 1567 |
new rows, to delete rows, or to modify existing rows. However, application |
| 1568 |
code cannot create the sqlite_sequence table if it does not already exist. |
| 1569 |
Application code can delete all entries from the sqlite_sequence table, |
| 1570 |
but application code cannot drop the sqlite_sequence table. |
| 1571 |
|
| 1572 |
<a name="stat1tab"></a> |
| 1573 |
|
| 1574 |
</p><h3 id="the_sqlite_stat1_table"><span>2.6.4. </span>The sqlite_stat1 table</h3> |
| 1575 |
|
| 1576 |
<p>The sqlite_stat1 is an internal table created by the <a href="lang_analyze.html">ANALYZE</a> command |
| 1577 |
and used to hold supplemental information about tables and indexes that the |
| 1578 |
query planner can use to help it find better ways of performing queries. |
| 1579 |
Applications can update, delete from, insert into or drop the sqlite_stat1 |
| 1580 |
table, but may not create or alter the sqlite_stat1 table. |
| 1581 |
The schema of the sqlite_stat1 table is as follows: |
| 1582 |
|
| 1583 |
</p><blockquote><pre> |
| 1584 |
CREATE TABLE sqlite_stat1(tbl,idx,stat); |
| 1585 |
</pre></blockquote> |
| 1586 |
|
| 1587 |
<p> There is normally one row per index, with the index identified by the |
| 1588 |
name in the sqlite_stat1.idx column. The sqlite_stat1.tbl column is |
| 1589 |
the name of the table to which the index belongs. In each such row, |
| 1590 |
the sqlite_stat.stat column will be |
| 1591 |
a string consisting of a list of integers followed by zero or more |
| 1592 |
arguments. The first integer in this |
| 1593 |
list is the approximate number of rows in the index. (The number of |
| 1594 |
rows in the index is the same as the number of rows in the table, |
| 1595 |
except for <a href="partialindex.html">partial indexes</a>.) |
| 1596 |
The second integer is the approximate number of rows in the index |
| 1597 |
that have the same value in the first column of the index. The third |
| 1598 |
integer is the number of rows in the index that have |
| 1599 |
the same value for the first two columns. The N-th integer (for N>1) |
| 1600 |
is the estimated average number of rows in |
| 1601 |
the index which have the same value for the first N-1 columns. For |
| 1602 |
a K-column index, there will be K+1 integers in the stat column. If |
| 1603 |
the index is unique, then the last integer will be 1. |
| 1604 |
|
| 1605 |
</p><p>The list of integers in the stat column can optionally be followed |
| 1606 |
by arguments, each of which is a sequence of non-space characters. |
| 1607 |
All arguments are preceded by a single space. |
| 1608 |
Unrecognized arguments are silently ignored. |
| 1609 |
|
| 1610 |
</p><p>If the "unordered" argument is present, then the query planner assumes |
| 1611 |
that the index is unordered and will not use the index for a range query |
| 1612 |
or for sorting. |
| 1613 |
|
| 1614 |
</p><p>The "sz=NNN" argument (where NNN represents a sequence of 1 or more digits) |
| 1615 |
means that the average row size over all records of the table or |
| 1616 |
index is NNN bytes per row. The SQLite query planner might use the |
| 1617 |
estimated row size information provided by the "sz=NNN" token |
| 1618 |
to help it choose smaller tables and indexes that require less disk I/O. |
| 1619 |
|
| 1620 |
</p><p>The presence of the "noskipscan" token on the sqlite_stat1.stat field |
| 1621 |
of an index prevents that index from being used with the |
| 1622 |
<a href="optoverview.html#skipscan">skip-scan optimization</a>. |
| 1623 |
|
| 1624 |
</p><p>New text tokens may be added to the end of the stat column in future |
| 1625 |
enhancements to SQLite. For compatibility, unrecognized tokens at the end |
| 1626 |
of the stat column are silently ignored. |
| 1627 |
|
| 1628 |
</p><p>If the sqlite_stat1.idx column is NULL, then the sqlite_stat1.stat |
| 1629 |
column contains a single integer which is the approximate number of |
| 1630 |
rows in the table identified by sqlite_stat1.tbl. |
| 1631 |
If the sqlite_stat1.idx column is the same as the sqlite_stat1.tbl |
| 1632 |
column, then the table is a <a href="withoutrowid.html">WITHOUT ROWID</a> table and the sqlite_stat1.stat |
| 1633 |
field contains information about the index btree that implements the |
| 1634 |
WITHOUT ROWID table. |
| 1635 |
|
| 1636 |
<a name="stat2tab"></a> |
| 1637 |
|
| 1638 |
</p><h3 id="the_sqlite_stat2_table"><span>2.6.5. </span>The sqlite_stat2 table</h3> |
| 1639 |
|
| 1640 |
<p>The sqlite_stat2 is only created and is only used if SQLite is compiled |
| 1641 |
with SQLITE_ENABLE_STAT2 and if the SQLite version number is between |
| 1642 |
3.6.18 (2009-09-11) and 3.7.8 (2011-09-19). |
| 1643 |
The sqlite_stat2 table is neither read nor written by any |
| 1644 |
version of SQLite before 3.6.18 nor after 3.7.8. |
| 1645 |
The sqlite_stat2 table contains additional information |
| 1646 |
about the distribution of keys within an index. |
| 1647 |
The schema of the sqlite_stat2 table is as follows: |
| 1648 |
|
| 1649 |
</p><blockquote><pre> |
| 1650 |
CREATE TABLE sqlite_stat2(tbl,idx,sampleno,sample); |
| 1651 |
</pre></blockquote> |
| 1652 |
|
| 1653 |
<p>The sqlite_stat2.idx column and the sqlite_stat2.tbl column in each |
| 1654 |
row of the sqlite_stat2 table identify an index described by that row. |
| 1655 |
There are usually 10 rows in the sqlite_stat2 |
| 1656 |
table for each index. |
| 1657 |
|
| 1658 |
</p><p>The sqlite_stat2 entries for an index that have sqlite_stat2.sampleno |
| 1659 |
between 0 and 9 inclusive are samples of the left-most key value in the |
| 1660 |
index taken at evenly spaced points along the index. |
| 1661 |
Let C be the number of rows in the index. |
| 1662 |
Then the sampled rows are given by |
| 1663 |
|
| 1664 |
</p><blockquote> |
| 1665 |
rownumber = (i*C*2 + C)/20 |
| 1666 |
</blockquote> |
| 1667 |
|
| 1668 |
<p>The variable i in the previous expression varies between 0 and 9. |
| 1669 |
Conceptually, the index space is divided into |
| 1670 |
10 uniform buckets and the samples are the middle row from each bucket. |
| 1671 |
|
| 1672 |
</p><p>The format for sqlite_stat2 is recorded here for legacy reference. |
| 1673 |
Recent versions of SQLite no longer support sqlite_stat2 and the |
| 1674 |
sqlite_stat2 table, if is exists, is simply ignored. |
| 1675 |
|
| 1676 |
<a name="stat3tab"></a> |
| 1677 |
|
| 1678 |
</p><h3 id="the_sqlite_stat3_table"><span>2.6.6. </span>The sqlite_stat3 table</h3> |
| 1679 |
|
| 1680 |
<p>The sqlite_stat3 is only used if SQLite is compiled |
| 1681 |
with <a href="compile.html#enable_stat3">SQLITE_ENABLE_STAT3</a> or <a href="compile.html#enable_stat4">SQLITE_ENABLE_STAT4</a> |
| 1682 |
and if the SQLite version number is 3.7.9 (2011-11-01) or greater. |
| 1683 |
The sqlite_stat3 table is neither read nor written by any |
| 1684 |
version of SQLite before 3.7.9. |
| 1685 |
If the <a href="compile.html#enable_stat4">SQLITE_ENABLE_STAT4</a> compile-time option is used and the |
| 1686 |
SQLite version number is 3.8.1 (2013-10-17) or greater, |
| 1687 |
then sqlite_stat3 might be read but not written. |
| 1688 |
The sqlite_stat3 table contains additional information |
| 1689 |
about the distribution of keys within an index, information that the |
| 1690 |
query planner can use to devise better and faster query algorithms. |
| 1691 |
The schema of the sqlite_stat3 table is as follows: |
| 1692 |
|
| 1693 |
</p><blockquote><pre> |
| 1694 |
CREATE TABLE sqlite_stat3(tbl,idx,nEq,nLt,nDLt,sample); |
| 1695 |
</pre></blockquote> |
| 1696 |
|
| 1697 |
<p>There are usually multiple entries in the sqlite_stat3 table for each index. |
| 1698 |
The sqlite_stat3.sample column holds the value of the left-most field of an |
| 1699 |
index identified by sqlite_stat3.idx and sqlite_stat3.tbl. |
| 1700 |
The sqlite_stat3.nEq column holds the approximate |
| 1701 |
number of entries in the index whose left-most column exactly matches |
| 1702 |
the sample. |
| 1703 |
The sqlite_stat3.nLt holds the approximate number of entries in the |
| 1704 |
index whose left-most column is less than the sample. |
| 1705 |
The sqlite_stat3.nDLt column holds the approximate |
| 1706 |
number of distinct left-most entries in the index that are less than |
| 1707 |
the sample. |
| 1708 |
|
| 1709 |
</p><p>There can be an arbitrary number of sqlite_stat3 entries per index. |
| 1710 |
The <a href="lang_analyze.html">ANALYZE</a> command will typically generate sqlite_stat3 tables |
| 1711 |
that contain between 10 and 40 samples that are distributed across |
| 1712 |
the key space and with large nEq values. |
| 1713 |
|
| 1714 |
</p><p>In a well-formed sqlite_stat3 table, the samples for any single |
| 1715 |
index must appear in the same order that they occur in the index. |
| 1716 |
In other words, if the entry with left-most column S1 is earlier in |
| 1717 |
the index b-tree than the |
| 1718 |
entry with left-most column S2, then in the sqlite_stat3 table, |
| 1719 |
sample S1 must have a smaller rowid than sample S2. |
| 1720 |
|
| 1721 |
<a name="stat4tab"></a> |
| 1722 |
|
| 1723 |
</p><h3 id="the_sqlite_stat4_table"><span>2.6.7. </span>The sqlite_stat4 table</h3> |
| 1724 |
|
| 1725 |
<p>The sqlite_stat4 is only created and is only used if SQLite is compiled |
| 1726 |
with <a href="compile.html#enable_stat4">SQLITE_ENABLE_STAT4</a> and if the SQLite version number is |
| 1727 |
3.8.1 (2013-10-17) or greater. |
| 1728 |
The sqlite_stat4 table is neither read nor written by any |
| 1729 |
version of SQLite before 3.8.1. |
| 1730 |
The sqlite_stat4 table contains additional information |
| 1731 |
about the distribution of keys within an index or the distribution of |
| 1732 |
keys in the primary key of a <a href="withoutrowid.html">WITHOUT ROWID</a> table. |
| 1733 |
The query planner can sometimes use the additional information in |
| 1734 |
the sqlite_stat4 table to devise better and faster query algorithms. |
| 1735 |
The schema of the sqlite_stat4 table is as follows: |
| 1736 |
|
| 1737 |
</p><blockquote><pre> |
| 1738 |
CREATE TABLE sqlite_stat4(tbl,idx,nEq,nLt,nDLt,sample); |
| 1739 |
</pre></blockquote> |
| 1740 |
|
| 1741 |
<p>There are typically between 10 to 40 entries in the sqlite_stat4 table for |
| 1742 |
each index for which statistics are available, however these limits are |
| 1743 |
not hard bounds. |
| 1744 |
The meanings of the columns in the sqlite_stat4 table are as follows: |
| 1745 |
|
| 1746 |
</p><center> |
| 1747 |
<table border="0" width="100%" cellpadding="10"> |
| 1748 |
<tr><td valign="top" align="right">tbl:</td> |
| 1749 |
<td>The sqlite_stat4.tbl column holds name of the table that owns |
| 1750 |
the index that the row describes |
| 1751 |
|
| 1752 |
</td></tr><tr><td valign="top" align="right">idx:</td> |
| 1753 |
<td>The sqlite_stat4.idx column holds name of the index that the |
| 1754 |
row describes, or in the case of |
| 1755 |
an sqlite_stat4 entry for a <a href="withoutrowid.html">WITHOUT ROWID</a> table, the |
| 1756 |
name of the table itself. |
| 1757 |
|
| 1758 |
</td></tr><tr><td valign="top" align="right">sample:</td> |
| 1759 |
<td>The sqlite_stat4.sample column holds a BLOB |
| 1760 |
in the <a href="fileformat2.html#record_format">record format</a> that encodes the indexed columns followed by |
| 1761 |
the rowid for a rowid table or by the columns of the primary key |
| 1762 |
for a WITHOUT ROWID table. |
| 1763 |
The sqlite_stat4.sample BLOB for the WITHOUT ROWID table itself |
| 1764 |
contains just the columns of the primary key. |
| 1765 |
Let the number of columns encoded by the sqlite_stat4.sample blob be N. |
| 1766 |
For indexes on an ordinary rowid table, N will be one more than the number |
| 1767 |
of columns indexed. |
| 1768 |
For indexes on WITHOUT ROWID tables, N will be the number of columns |
| 1769 |
indexed plus the number of columns in the primary key. |
| 1770 |
For a WITHOUT ROWID table, N will be the number of columns in the |
| 1771 |
primary key. |
| 1772 |
|
| 1773 |
</td></tr><tr><td valign="top" align="right">nEq:</td> |
| 1774 |
<td>The sqlite_stat4.nEq column holds a list of N integers where |
| 1775 |
the K-th integer is the approximate number of entries in the index |
| 1776 |
whose left-most K columns exactly match the K left-most columns |
| 1777 |
of the sample. |
| 1778 |
|
| 1779 |
</td></tr><tr><td valign="top" align="right">nLt:</td> |
| 1780 |
<td>The sqlite_stat4.nLt column holds a list of N integers where |
| 1781 |
the K-th integer is the approximate number of entries in the |
| 1782 |
index whose K left-most columns are collectively less than the |
| 1783 |
K left-most columns of the sample. |
| 1784 |
|
| 1785 |
</td></tr><tr><td valign="top" align="right">nDLt:</td> |
| 1786 |
<td>The sqlite_stat4.nDLt column holds a list of N integers where |
| 1787 |
the K-th integer is the approximate |
| 1788 |
number of entries in the index that are distinct in the first K columns and |
| 1789 |
where the left-most K columns are collectively less than the left-most |
| 1790 |
K columns of the sample. |
| 1791 |
</td></tr></table> |
| 1792 |
</center> |
| 1793 |
|
| 1794 |
<p>The sqlite_stat4 is a generalization of the sqlite_stat3 table. The |
| 1795 |
sqlite_stat3 table provides information about the left-most column of an |
| 1796 |
index whereas the sqlite_stat4 table provides information about all columns |
| 1797 |
of the index. |
| 1798 |
|
| 1799 |
</p><p>There can be an arbitrary number of sqlite_stat4 entries per index. |
| 1800 |
The <a href="lang_analyze.html">ANALYZE</a> command will typically generate sqlite_stat4 tables |
| 1801 |
that contain between 10 and 40 samples that are distributed across |
| 1802 |
the key space and with large nEq values. |
| 1803 |
|
| 1804 |
</p><p>In a well-formed sqlite_stat4 table, the samples for any single |
| 1805 |
index must appear in the same order that they occur in the index. |
| 1806 |
In other words, if entry S1 is earlier in the index b-tree than |
| 1807 |
entry S2, then in the sqlite_stat4 table, sample S1 must have a |
| 1808 |
smaller rowid than sample S2. |
| 1809 |
|
| 1810 |
<a name="rollbackjournal"></a> |
| 1811 |
|
| 1812 |
</p><h1 id="the_rollback_journal"><span>3. </span>The Rollback Journal</h1> |
| 1813 |
|
| 1814 |
<p>The rollback journal is a file associated with each SQLite database |
| 1815 |
file that holds information used to restore the database file to its initial |
| 1816 |
state during the course of a transaction. |
| 1817 |
The rollback journal file is always located in the same |
| 1818 |
directory as the database |
| 1819 |
file and has the same name as the database file but with the string |
| 1820 |
"<tt>-journal</tt>" appended. There can only be a single rollback journal |
| 1821 |
associated with a give database and hence there can only be one write |
| 1822 |
transaction open against a single database at one time.</p> |
| 1823 |
|
| 1824 |
<p>Before any information-bearing page of the database is modified, |
| 1825 |
the original unmodified content of that page is written into the |
| 1826 |
rollback journal. If a transaction is interrupted and needs to be |
| 1827 |
rolled back, the rollback journal can then be used to restore the |
| 1828 |
database to its original state. Freelist leaf pages bear no |
| 1829 |
information that would need to be restored on a rollback and so they |
| 1830 |
are not written to the journal prior to modification, in order to |
| 1831 |
reduce disk I/O.</p> |
| 1832 |
|
| 1833 |
<p>If a transaction is aborted due to an application crash, or a single, |
| 1834 |
or an operating system crash, or a hardware power failure or crash, then |
| 1835 |
the main database file might be left in an inconsistent state. |
| 1836 |
The next time SQLite attempts to open |
| 1837 |
the database file, the presence of the rollback journal file will be |
| 1838 |
detected and the journal will be automatically played back to restore the |
| 1839 |
database to its state at the start of the incomplete transaction.</p> |
| 1840 |
|
| 1841 |
<p>A rollback journal is only considered to be valid if it exists and |
| 1842 |
contains a valid header. Hence a transaction can be committed in one |
| 1843 |
of three ways: |
| 1844 |
</p><ol> |
| 1845 |
<li>The rollback journal file can be deleted, |
| 1846 |
</li><li>The rollback journal file can be truncated to zero length, or |
| 1847 |
</li><li>The header of the rollback journal can be overwritten with |
| 1848 |
invalid header text (for example, all zeros). |
| 1849 |
</li></ol> |
| 1850 |
<p> |
| 1851 |
These three ways of committing a transaction correspond to the DELETE, |
| 1852 |
TRUNCATE, and PERSIST settings, respectively, of the <a href="pragma.html#pragma_journal_mode">journal_mode pragma</a>. |
| 1853 |
</p> |
| 1854 |
|
| 1855 |
|
| 1856 |
<p>A valid rollback journal begins with a header in the following format:</p> |
| 1857 |
|
| 1858 |
<center> |
| 1859 |
<i>Rollback Journal Header Format</i><br> |
| 1860 |
<table width="80%" border="1"> |
| 1861 |
<tr><th>Offset</th><th>Size</th><th>Description |
| 1862 |
</th></tr><tr><td valign="top" align="center">0 |
| 1863 |
</td><td valign="top" align="center">8 |
| 1864 |
</td><td>Header string: 0xd9, 0xd5, 0x05, 0xf9, 0x20, 0xa1, 0x63, 0xd7 |
| 1865 |
</td></tr><tr><td valign="top" align="center">8 |
| 1866 |
</td><td valign="top" align="center">4 |
| 1867 |
</td><td>The "Page Count" - The number of pages in the next segment of the |
| 1868 |
journal, or -1 to |
| 1869 |
mean all content to the end of the file |
| 1870 |
</td></tr><tr><td valign="top" align="center">12 |
| 1871 |
</td><td valign="top" align="center">4 |
| 1872 |
</td><td>A random nonce for the checksum |
| 1873 |
</td></tr><tr><td valign="top" align="center">16 |
| 1874 |
</td><td valign="top" align="center">4 |
| 1875 |
</td><td>Initial size of the database in pages |
| 1876 |
</td></tr><tr><td valign="top" align="center">20 |
| 1877 |
</td><td valign="top" align="center">4 |
| 1878 |
</td><td>Size of a disk sector assumed by the process that wrote this |
| 1879 |
journal. |
| 1880 |
</td></tr><tr><td valign="top" align="center">24 |
| 1881 |
</td><td valign="top" align="center">4 |
| 1882 |
</td><td>Size of pages in this journal. |
| 1883 |
</td></tr></table> |
| 1884 |
</center> |
| 1885 |
|
| 1886 |
<p>A rollback journal header is padded with zeros out to the size of a |
| 1887 |
single sector (as defined by the sector size integer at offset 20). |
| 1888 |
The header is in a sector by itself so that if a power loss occurs while |
| 1889 |
writing the sector, information that follows the header will be |
| 1890 |
(hopefully) undamaged.</p> |
| 1891 |
|
| 1892 |
<p>After the header and zero padding are zero or more page records. Each |
| 1893 |
page record stores a copy of the content of a page from the database file |
| 1894 |
before it was changed. The same page may not appear more than once |
| 1895 |
within a single rollback journal. |
| 1896 |
To rollback an incomplete transaction, a process |
| 1897 |
has merely to read the rollback journal from beginning to end and |
| 1898 |
write pages found in the journal back into the database file at the |
| 1899 |
appropriate location.</p> |
| 1900 |
|
| 1901 |
<p>Let the database page size (the value of the integer at offset 24 |
| 1902 |
in the journal header) be N. |
| 1903 |
Then the format of a page record is as follows:</p> |
| 1904 |
|
| 1905 |
<center> |
| 1906 |
<i>Rollback Journal Page Record Format</i><br> |
| 1907 |
<table width="80%" border="1"> |
| 1908 |
<tr><th>Offset</th><th>Size</th><th>Description |
| 1909 |
</th></tr><tr><td valign="top" align="center">0 |
| 1910 |
</td><td valign="top" align="center">4 |
| 1911 |
</td><td>The page number in the database file |
| 1912 |
</td></tr><tr><td valign="top" align="center">4 |
| 1913 |
</td><td valign="top" align="center">N |
| 1914 |
</td><td>Original content of the page prior to the start of the transaction |
| 1915 |
</td></tr><tr><td valign="top" align="center">N+4 |
| 1916 |
</td><td valign="top" align="center">4 |
| 1917 |
</td><td>Checksum |
| 1918 |
</td></tr></table> |
| 1919 |
</center> |
| 1920 |
|
| 1921 |
|
| 1922 |
<p>The checksum is an unsigned 32-bit integer computed as follows:</p> |
| 1923 |
|
| 1924 |
<ol> |
| 1925 |
<li>Initialize the checksum to the checksum nonce value found in the |
| 1926 |
journal header at offset 12. |
| 1927 |
</li><li>Initialize index X to be N-200 (where N is the size of a database page |
| 1928 |
in bytes. |
| 1929 |
</li><li>Interpret the byte at offset X into the page as an 8-bit unsigned integer |
| 1930 |
and add the value of that integer to the checksum. |
| 1931 |
</li><li>Subtract 200 from X. |
| 1932 |
</li><li>If X is greater than or equal to zero, go back to step 3. |
| 1933 |
</li></ol> |
| 1934 |
|
| 1935 |
<p>The checksum value is used to guard against incomplete writes of |
| 1936 |
a journal page record following a power failure. A different random nonce |
| 1937 |
is used each time a transaction is started in order to minimize the risk |
| 1938 |
that unwritten sectors might by chance contain data from the same page |
| 1939 |
that was a part of prior journals. By changing the nonce for each |
| 1940 |
transaction, stale data on disk will still generate an incorrect checksum |
| 1941 |
and be detected with high probability. The checksum only uses a sparse sample |
| 1942 |
of 32-bit words from the data record for performance reasons - design studies |
| 1943 |
during the planning phases of SQLite 3.0.0 showed |
| 1944 |
a significant performance hit in checksumming the entire page.</p> |
| 1945 |
|
| 1946 |
<p>Let the page count value at offset 8 in the journal header be M. |
| 1947 |
If M is greater than zero then after M page records the journal file |
| 1948 |
may be zero padded out to the next multiple of the sector size and another |
| 1949 |
journal header may be inserted. All journal headers within the same |
| 1950 |
journal must contain the same database page size and sector size.</p> |
| 1951 |
|
| 1952 |
<p>If M is -1 in the initial journal header, then the number of page records |
| 1953 |
that follow is computed by computing how many page records will fit in |
| 1954 |
the available space of the remainder of the journal file.</p> |
| 1955 |
|
| 1956 |
<a name="walformat"></a> |
| 1957 |
|
| 1958 |
<h1 id="the_write_ahead_log"><span>4. </span>The Write-Ahead Log</h1> |
| 1959 |
|
| 1960 |
<p>Beginning with <a href="releaselog/3_7_0.html">version 3.7.0</a> (2010-07-21), |
| 1961 |
SQLite supports a new transaction |
| 1962 |
control mechanism called "<a href="wal.html">write-ahead log</a>" or "<a href="wal.html">WAL</a>". |
| 1963 |
When a database is in WAL mode, all connections to that database must |
| 1964 |
use the WAL. A particular database will use either a rollback journal |
| 1965 |
or a WAL, but not both at the same time. |
| 1966 |
The WAL is always located in the same directory as the database |
| 1967 |
file and has the same name as the database file but with the string |
| 1968 |
"<tt>-wal</tt>" appended.</p> |
| 1969 |
|
| 1970 |
<h2 id="wal_file_format"><span>4.1. </span>WAL File Format</h2> |
| 1971 |
|
| 1972 |
<p>A <a href="wal.html#walfile">WAL file</a> consists of a header followed by zero or more "frames". |
| 1973 |
Each frame records the revised content of a single page from the |
| 1974 |
database file. All changes to the database are recorded by writing |
| 1975 |
frames into the WAL. Transactions commit when a frame is written that |
| 1976 |
contains a commit marker. A single WAL can and usually does record |
| 1977 |
multiple transactions. Periodically, the content of the WAL is |
| 1978 |
transferred back into the database file in an operation called a |
| 1979 |
"checkpoint".</p> |
| 1980 |
|
| 1981 |
<p>A single WAL file can be reused multiple times. In other words, the |
| 1982 |
WAL can fill up with frames and then be checkpointed and then new |
| 1983 |
frames can overwrite the old ones. A WAL always grows from beginning |
| 1984 |
toward the end. Checksums and counters attached to each frame are |
| 1985 |
used to determine which frames within the WAL are valid and which |
| 1986 |
are leftovers from prior checkpoints.</p> |
| 1987 |
|
| 1988 |
<p>The WAL header is 32 bytes in size and consists of the following eight |
| 1989 |
big-endian 32-bit unsigned integer values:</p> |
| 1990 |
|
| 1991 |
<center> |
| 1992 |
<i>WAL Header Format</i><br> |
| 1993 |
<table width="80%" border="1"> |
| 1994 |
<tr><th>Offset</th><th>Size</th><th>Description |
| 1995 |
</th></tr><tr><td valign="top" align="center">0</td><td valign="top" align="center">4 |
| 1996 |
</td><td>Magic number. 0x377f0682 or 0x377f0683 |
| 1997 |
</td></tr><tr><td valign="top" align="center">4</td><td valign="top" align="center">4 |
| 1998 |
</td><td>File format version. Currently 3007000. |
| 1999 |
</td></tr><tr><td valign="top" align="center">8</td><td valign="top" align="center">4 |
| 2000 |
</td><td>Database page size. Example: 1024 |
| 2001 |
</td></tr><tr><td valign="top" align="center">12</td><td valign="top" align="center">4 |
| 2002 |
</td><td>Checkpoint sequence number |
| 2003 |
</td></tr><tr><td valign="top" align="center">16</td><td valign="top" align="center">4 |
| 2004 |
</td><td>Salt-1: random integer incremented with each checkpoint |
| 2005 |
</td></tr><tr><td valign="top" align="center">20</td><td valign="top" align="center">4 |
| 2006 |
</td><td>Salt-2: a different random number for each checkpoint |
| 2007 |
</td></tr><tr><td valign="top" align="center">24</td><td valign="top" align="center">4 |
| 2008 |
</td><td>Checksum-1: First part of a checksum on the first 24 bytes of header |
| 2009 |
</td></tr><tr><td valign="top" align="center">28</td><td valign="top" align="center">4 |
| 2010 |
</td><td>Checksum-2: Second part of the checksum on the first 24 bytes of header |
| 2011 |
</td></tr></table> |
| 2012 |
</center> |
| 2013 |
|
| 2014 |
<p>Immediately following the wal-header are zero or more frames. Each |
| 2015 |
frame consists of a 24-byte frame-header followed by a <i>page-size</i> bytes |
| 2016 |
of page data. The frame-header is six big-endian 32-bit unsigned |
| 2017 |
integer values, as follows: |
| 2018 |
|
| 2019 |
</p><center> |
| 2020 |
<i>WAL Frame Header Format</i><br> |
| 2021 |
<table width="80%" border="1"> |
| 2022 |
<tr><th>Offset</th><th>Size</th><th>Description |
| 2023 |
</th></tr><tr><td valign="top" align="center">0</td><td valign="top" align="center">4 |
| 2024 |
</td><td>Page number |
| 2025 |
</td></tr><tr><td valign="top" align="center">4</td><td valign="top" align="center">4 |
| 2026 |
</td><td>For commit records, the size of the database file in pages |
| 2027 |
after the commit. For all other records, zero. |
| 2028 |
</td></tr><tr><td valign="top" align="center">8</td><td valign="top" align="center">4 |
| 2029 |
</td><td>Salt-1 copied from the WAL header |
| 2030 |
</td></tr><tr><td valign="top" align="center">12</td><td valign="top" align="center">4 |
| 2031 |
</td><td>Salt-2 copied from the WAL header |
| 2032 |
</td></tr><tr><td valign="top" align="center">16</td><td valign="top" align="center">4 |
| 2033 |
</td><td>Checksum-1: Cumulative checksum up through and including this page |
| 2034 |
</td></tr><tr><td valign="top" align="center">20</td><td valign="top" align="center">4 |
| 2035 |
</td><td>Checksum-2: Second half of the cumulative checksum. |
| 2036 |
</td></tr></table> |
| 2037 |
</center> |
| 2038 |
|
| 2039 |
<p>A frame is considered valid if and only if the following conditions are |
| 2040 |
true:</p> |
| 2041 |
|
| 2042 |
<ol> |
| 2043 |
<li><p>The salt-1 and salt-2 values in the frame-header match |
| 2044 |
salt values in the wal-header</p></li> |
| 2045 |
|
| 2046 |
<li><p>The checksum values in the final 8 bytes of the frame-header |
| 2047 |
exactly match the checksum computed consecutively on the |
| 2048 |
first 24 bytes of the WAL header and the first 8 bytes and |
| 2049 |
the content of all frames |
| 2050 |
up to and including the current frame.</p></li> |
| 2051 |
</ol> |
| 2052 |
|
| 2053 |
<a name="walcksm"></a> |
| 2054 |
|
| 2055 |
<h2 id="checksum_algorithm"><span>4.2. </span>Checksum Algorithm</h2> |
| 2056 |
|
| 2057 |
<p>The checksum is computed by interpreting the input as |
| 2058 |
an even number of unsigned 32-bit integers: x(0) through x(N). |
| 2059 |
The 32-bit integers are big-endian if the |
| 2060 |
magic number in the first 4 bytes of the WAL header is 0x377f0683 and |
| 2061 |
the integers are little-endian if the magic number is 0x377f0682. |
| 2062 |
The checksum values are always stored in the frame header in a |
| 2063 |
big-endian format regardless of which byte order is used to compute |
| 2064 |
the checksum.</p> |
| 2065 |
|
| 2066 |
<p>The checksum algorithm only works for content which is a multiple of |
| 2067 |
8 bytes in length. In other words, if the inputs are x(0) through x(N) |
| 2068 |
then N must be odd. |
| 2069 |
The checksum algorithm is as follows: |
| 2070 |
|
| 2071 |
</p><blockquote><pre> |
| 2072 |
s0 = s1 = 0 |
| 2073 |
for i from 0 to n-1 step 2: |
| 2074 |
s0 += x(i) + s1; |
| 2075 |
s1 += x(i+1) + s0; |
| 2076 |
endfor |
| 2077 |
# result in s0 and s1 |
| 2078 |
</pre></blockquote> |
| 2079 |
|
| 2080 |
<p>The outputs s0 and s1 are both weighted checksums using Fibonacci weights |
| 2081 |
in reverse order. (The largest Fibonacci weight occurs on the first element |
| 2082 |
of the sequence being summed.) The s1 value spans all 32-bit integer |
| 2083 |
terms of the sequence whereas s0 omits the final term.</p> |
| 2084 |
|
| 2085 |
<h2 id="checkpoint_algorithm"><span>4.3. </span>Checkpoint Algorithm</h2> |
| 2086 |
|
| 2087 |
<p>On a <a href="wal.html#ckpt">checkpoint</a>, the WAL is first flushed to persistent storage using |
| 2088 |
the xSync method of the <a href="c3ref/io_methods.html">VFS</a>. |
| 2089 |
Then valid content of the WAL is transferred into the database file. |
| 2090 |
Finally, the database is flushed to persistent storage using another |
| 2091 |
xSync method call. |
| 2092 |
The xSync operations serve as write barriers - all writes launched |
| 2093 |
before the xSync must complete before any write that launches after the |
| 2094 |
xSync begins.</p> |
| 2095 |
|
| 2096 |
<p>A checkpoint need not run to completion. It might be that some |
| 2097 |
readers are still using older transactions with data that is contained |
| 2098 |
in the database file. In that case, transferring content for newer |
| 2099 |
transactions from the WAL file into the database would delete the content |
| 2100 |
out from under readers still using the older transactions. To avoid that, |
| 2101 |
checkpoints only run to completion if all reader are using the |
| 2102 |
last transaction in the WAL. |
| 2103 |
|
| 2104 |
<a name="walreset"></a> |
| 2105 |
|
| 2106 |
</p><h2 id="wal_reset"><span>4.4. </span>WAL Reset</h2> |
| 2107 |
|
| 2108 |
<p>After a complete checkpoint, if no other connections are in transactions |
| 2109 |
that use the WAL, then subsequent write transactions can |
| 2110 |
overwrite the WAL file from the beginning. This is called "resetting the |
| 2111 |
WAL". At the start of the first new |
| 2112 |
write transaction, the WAL header salt-1 value is incremented |
| 2113 |
and the salt-2 value is randomized. These changes to the salts invalidate |
| 2114 |
old frames in the WAL that have already been checkpointed but not yet |
| 2115 |
overwritten, and prevent them from being checkpointed again.</p> |
| 2116 |
|
| 2117 |
<p>The WAL file can optionally be truncated on a reset, but it need not be. |
| 2118 |
Performance is usually a little better if the WAL is not truncated, since |
| 2119 |
filesystems generally will overwrite an existing file faster than they |
| 2120 |
will grow a file. |
| 2121 |
|
| 2122 |
<a name="walread"></a> |
| 2123 |
|
| 2124 |
</p><h2 id="reader_algorithm"><span>4.5. </span>Reader Algorithm</h2> |
| 2125 |
|
| 2126 |
<p>To read a page from the database (call it page number P), a reader |
| 2127 |
first checks the WAL to see if it contains page P. If so, then the |
| 2128 |
last valid instance of page P that is followed by a commit frame |
| 2129 |
or is a commit frame itself becomes the value read. If the WAL |
| 2130 |
contains no copies of page P that are valid and which are a commit |
| 2131 |
frame or are followed by a commit frame, then page P is read from |
| 2132 |
the database file.</p> |
| 2133 |
|
| 2134 |
<p>To start a read transaction, the reader records the number of value |
| 2135 |
frames in the WAL as "mxFrame". (<a href="walformat.html#mxframe">More detail</a>) |
| 2136 |
The reader uses this recorded mxFrame value |
| 2137 |
for all subsequent read operations. New transactions can be appended |
| 2138 |
to the WAL, but as long as the reader uses its original mxFrame value |
| 2139 |
and ignores subsequently appended content, the reader will see a |
| 2140 |
consistent snapshot of the database from a single point in time. |
| 2141 |
This technique allows multiple concurrent readers to view different |
| 2142 |
versions of the database content simultaneously.</p> |
| 2143 |
|
| 2144 |
<p>The reader algorithm in the previous paragraphs works correctly, but |
| 2145 |
because frames for page P can appear anywhere within the WAL, the |
| 2146 |
reader has to scan the entire WAL looking for page P frames. If the |
| 2147 |
WAL is large (multiple megabytes is typical) that scan can be slow, |
| 2148 |
and read performance suffers. To overcome this problem, a separate |
| 2149 |
data structure called the wal-index is maintained to expedite the |
| 2150 |
search for frames of a particular page.</p> |
| 2151 |
|
| 2152 |
<a name="walindexformat"></a> |
| 2153 |
|
| 2154 |
<h2 id="wal_index_format"><span>4.6. </span>WAL-Index Format</h2> |
| 2155 |
|
| 2156 |
<p>Conceptually, the wal-index is shared memory, though the current |
| 2157 |
VFS implementations use a memory-mapped file for operating-system |
| 2158 |
portability. The memory-mapped |
| 2159 |
file is in the same directory as the database and has the same name |
| 2160 |
as the database with a "<tt>-shm</tt>" suffix appended. Because |
| 2161 |
the wal-index is shared memory, SQLite does not support |
| 2162 |
<a href="pragma.html#pragma_journal_mode">journal_mode=WAL</a> |
| 2163 |
on a network filesystem when clients are on different machines, as |
| 2164 |
all clients of the database must be able to share the same memory.</p> |
| 2165 |
|
| 2166 |
<p>The purpose of the wal-index is to answer this question quickly:</p> |
| 2167 |
|
| 2168 |
<blockquote><i> |
| 2169 |
Given a page number P and a maximum WAL frame index M, |
| 2170 |
return the largest WAL frame index for page P that does not exceed M, |
| 2171 |
or return NULL if there are no frames for page P that do not exceed M. |
| 2172 |
</i></blockquote> |
| 2173 |
|
| 2174 |
<p>The <i>M</i> value in the previous paragraph is the "mxFrame" value |
| 2175 |
defined in <a href="fileformat2.html#walread">section 4.5</a> that is read at the start |
| 2176 |
of a transaction and which defines the maximum frame from the WAL that |
| 2177 |
the reader will use.</p> |
| 2178 |
|
| 2179 |
<p>The wal-index is transient. After a crash, the wal-index is |
| 2180 |
reconstructed from the original WAL file. The VFS is required |
| 2181 |
to either truncate or zero the header of the wal-index when the last |
| 2182 |
connection to it closes. Because the wal-index is transient, it can |
| 2183 |
use an architecture-specific format; it does not have to be cross-platform. |
| 2184 |
Hence, unlike the database and WAL file formats which store all values |
| 2185 |
as big endian, the wal-index stores multi-byte values in the native |
| 2186 |
byte order of the host computer.</p> |
| 2187 |
|
| 2188 |
<p>This document is concerned with the persistent state of the database |
| 2189 |
file, and since the wal-index is a transient structure, no further |
| 2190 |
information about the format of the wal-index will be provided here. |
| 2191 |
Additional details on the format of the wal-index are contained in |
| 2192 |
the separate <a href="walformat.html#walidxfmt">WAL-index File Format</a> document.</p> |
| 2193 |
<p align="center"><small><i>This page was last updated on 2025-12-25 10:33:36Z </small></i></p> |
| 2194 |
|