Documentation Source Text

scenario and so are uncommon, but they are part of the state of an SQLite
database and so should not be ignored.  This document will define the format
of a rollback journal, but most of the content of this document will focus
on the main database file.</p>

<h3>1.1 Pages</h3>

<p>The main database file consists of one or more pages.  The size of a
page is a power of two between 512 and 32768 inclusive.  All pages within
the same database are the same size.  The page size for a database file
is determined by the 2-byte integer located at an offset of
16 bytes from the beginning of the database file.</p>

<p>Pages are numbered beginning with 1.  The maximum page number is
2147483646 (2<sup><small>31</small></sup> - 2).  The minimum size
SQLite database is a single 512-byte page.
The maximum size database would be 2147483646 pages at 32768 bytes per
page or 70,368,744,112,128 bytes (about 70 terabytes).  Usually SQLite will
hit the maximum file size limit of the underlying filesystem or disk
hardware size limit long before it hits its own internal size limit.</p>

<p>In common use, SQLite databases tend to range in size from a few kilobytes
to a few gigabytes.</p>

<p>At any point in time, every page in the main database has a single
................................................................................
<li>An index b-tree leaf page
</ul>
<li>A payload overflow page
<li>A pointer map page
</ul>
</p>

<p>All reads from and writes to the main database file begin at a page
boundary and all writes are an integer number of pages in size.  Reads
are also usually an integer number of pages in size, with the one exception
that when the database is first opened, the first 100 bytes of the
database file (the database file header) are read as a sub-page size unit.</p>

<p>Before any information-bearing page of the database is modified, 
the original unmodified content of that page is written into the 
rollback journal.  If a transaction is interrupted and needs to be 
rolled back, the rollback journal can then be used to restore the
database to its original state.  Freelist leaf pages bear no
information that would need to be restored on a rollback and so they
are not written to the journal prior to modification, in order to
reduce disk I/O.</p>

<tcl>hd_fragment database_header {database header}</tcl>
<h3>1.2 The Database Header</h3>

................................................................................
The [version-valid-for number].
<tr><td valign=top align=center>96<td valign=top align=center>4<td align=left>
[SQLITE_VERSION_NUMBER]
</table></center>

<h4>1.2.1 Magic Header String</h4>

<p>Every SQLite database file begins with the following 16 bytes (in hex):
53 51 4c 69 74 65 20 66 6f 72 6d 61 74 20 33 00.  This byte sequence
corresponds to the UTF-8 string "SQLite format 3" including the nul
terminator character at the end.</p>

<h4>1.2.2 Page Size</h4>

<p>The two-byte value beginning at offset 16 determines the page size of 
the database.  For SQLite versions 3.7.0.1 and earlier, this value is 
................................................................................
512 and 32768, inclusive.  Beginning with SQLite version 3.7.1, a page
size of 65536 bytes is supported.  The value 65536 will not fit in a
two-byte integer, so to specify a 65536-byte page size, the value is
at offset 16 is 0x00 0x01.
This value can be interpreted as a big-endian
1 and thought of is as a magic number to represent the 65536 page size.
Or one can view the two-byte field as a little endian number and say
that it represents the page size divided by 256.</p>


<h4>1.2.3 File format version numbers</h4>

<p>The file format write version and file format read version at offsets
18 and 19 are intended to allow for enhancements of the file format
in future versions of SQLite.  In current versions of SQLite, both of
these values are 1 for rollback journalling modes and 2 for [WAL]
................................................................................
greater than 2 is encounter, then that database cannot be read or written.</p>

<h4>1.2.4 Reserved bytes per page</h4>

<p>SQLite has the ability to set aside a small number of extra bytes at
the end of every page for use by extensions.  These extra bytes are
used, for example, by the SQLite Encryption Extension to store a nonce
and/or cryptographic checksum associated with each page.  The 
"reserved space" size in the 1-byte integer at offset 20 is the number
of bytes of space at the end of each page to reserve for extensions.
This value is usually 0.  The value can be odd.</p>

<tcl>hd_fragment usable_size {usable size}</tcl>
<p>The "usable size" of a database page is the page size specify by the
2-byte integer at offset 16 in the header less the "reserved" space size
recorded in the 1-byte integer at offset 20 in the header.  The usable
size of a page might be an odd number.  However, the usable size is not
allowed to be less than 480.  In other words, if the page size is 512,
then the reserved space size cannot exceed 32.</p>

<h4>1.2.5 Payload fractions</h4>

<p>The maximum and minimum embedded payload fractions and the leaf
payload fraction values must be 64, 32, and 32.  These values were
originally intended to as tunable parameters that could be used to
modify the storage format of the b-tree algorithm.  However, that
functionality is not supported and there are no current plans to add
support in the future.  Hence, these three bytes are fixed at the
values specified.</p>

<h4>1.2.6 File change counter</h4>

<tcl>hd_fragment chngctr {change counter}</tcl>
<p>The file change counter is a 4-byte big-endian integer which is
incremented whenever the database file is changed in rollback mode.  

When two or more processes are reading the same database file, each 
process can detect database changes from other processes by monitoring 
the change counter.
A process will normally want to flush its database page cache when
another process modified the database, since the cache has become stale.
The file change counter facilitates this.</p>

................................................................................
<p>In WAL mode, changes to the database are detected using the wal-index
and so the change counter is not needed.  Hence, the change counter might
not be incremented on each transaction in WAL mode.</p>

<h4>1.2.7 In-header database size</h4>

<tcl>hd_fragment filesize {in-header database size}</tcl>
<p>The 4-byte big-endian integer at offset 28 into the header 
stores the size of the database file in pages.  If this in-header
datasize size is not valid (see the next paragraph), then the database 
size is computed by looking
at the actual size of the database file. Older versions of SQLite
ignored the in-header database size and used the actual file size
exclusively.  Newer versions of SQLite use the in-header database
size if it is available but fall back to the actual file size if
the in-header database size is not valid.</p>

<p>The in-header database size is only considered to be valid if
it is non-zero and if the 4-byte [change counter] at offset 24
exactly matches the 4-byte [version-valid-for number] at offset 92.
The in-header database size should always be valid 
when the database is only modified using recent versions of SQLite
(versions 3.7.0 and later).
If a legacy version of SQLite writes to the database, it will not
know to update the in-header database size and so the in-header
database size could be incorrect.  But legacy versions of SQLite
will also leave the version-valid-for number at offset 92 unchanged
so it will not match the change-counter.  Hence, invalid in-header
database sizes can be detected (and ignored) by observing when
the change-counter does not match the version-valid-for number.</p>

<h4>1.2.8 Free page list</h4>

<p>Unused pages in the database file are stored on a freelist.  The
4-byte big-endian integer at offset 32 stores the page number of
the first page of the freelist, or zero if the freelist is empty.
The 4-byte big-endian integer at offset 36 stores stores the total 
number of pages on the freelist.</p>

<h4>1.2.9 Schema cookie</h4>

<p>The schema cookie is a 4-byte big-endian integer at offset 40
that is incremented whenever the database schema changes.  A 
prepared statement is compiled against a specific version of the
database schema.  Whenever the database schema changes, the statement
must be reprepared.  Whenever a prepared statement runs, it first checks
the schema cookie to make sure the value is the same as when the statement

was prepared and if not it aborts to force the statement to be reprepared.</p>

<h4>1.2.10 Schema format number</h4>

<p>The schema format number is a 4-byte big-endian integer at offset 44.
The schema format number is similar to the file format read and write
version numbers at offsets 18 and 19 except that the schema format number
refers to the high-level SQL formatting rather than the low-level b-tree
................................................................................
[ALTER TABLE | ALTER TABLE ... ADD COLUMN] functionality.  Support for
reading and writing format 2 was added in SQLite version 3.1.3 
on 2005-02-19.</li>
<li value=3>Format 3 adds the ability of extra columns added by
[ALTER TABLE | ALTER TABLE ... ADD COLUMN] to have non-NULL default
values.  This capability was added in SQLite version 3.1.4 
on 2005-03-11.</li>
<li value=4>Format 4 causes SQLite to respect the DESC keyword on
index declarations.  (The DESC keyword is ignored in indices for 
formats 1, 2, and 3.)
Format 4 also adds two new boolean record type values ([serial types]
8 and 9.)  Support for format 4 was added in SQLite 3.3.0 on
2006-01-10.</li>
</ol>

<p>New database files created by SQLite use format 1 by default, so
that database files created by newer versions of SQLite can still
be read by older versions of SQLite.
The [legacy_file_format pragma] can be used to cause SQLite
to create new database files using format 4.  Future versions of 
SQLite may begin to create files using format 4 by default.</p>

<h4>1.2.11 Suggested cache size</h4>

<p>The 4-byte big-endian signed integer at offset 48 is the suggest
cache size in pages for the database file.  The value is a suggestion
................................................................................
only and SQLite is under no obligation to honor it.  The absolute value
of the integer is used as the suggested size.  The suggested cache size
can be set using the [default_cache_size pragma].</p>

<h4>1.2.12 Incremental vacuum settings</h4>

<p>The two 4-byte big-endian integers at offsets 52 and 64 are used
to manage the [auto_vacuum] and [incremental_vacuum] modes.  If
the integer at offset 52 is zero then pointer-map (ptrmap) pages are
omitted from the database file and neither auto_vacuum nor
incremental_vacuum are supported.  If the integer at offset 52 is
non-zero then it is the page number of the largest root page in the
database file, the database file contain ptrmap pages, and the
mode must be either auto_vacuum or incremental_vacuum.  In this latter
case, the integer at offset 64 is true for incremental_vacuum and
false for auto_vacuum.  If the integer at offset 52 is zero then
the integer at offset 64 must also be zero.</p>

<h4>1.2.13 Text encoding</h4>

<p>The 4-byte big-endian integer at offset 56 determines the encoding
used for all text strings stored in the database.  A value of 1 means
UTF-8.  A value of 2 means UTF-16le.  A value of 3 means UTF-16be.
No other values are allowed.</p>

<h4>1.2.14 User version number</h4>

<p>The 4-byte big-endian integer at offset 60 is the user version which
is set and queried by the [user_version pragma].  The user version is
not used by SQLite.</p>

<tcl>hd_fragment validfor {version-valid-for number}</tcl>
<h4>1.2.15 Write library version number and version-valid-for number</h4>

<p>The 4-byte big-endian integer at offset 96 stores the 

[SQLITE_VERSION_NUMBER] value.  The 4-byte big-ending integer at
offset 92 is the value of the [change counter] when the version number
was stored.  The integer at offset 92 indicates which transaction
the version number is valid for and is sometimes called the
"version-valid-for number".

<h4>1.2.16 Header space reserved for expansion</h4>

................................................................................
inclusive.  A database file that is less than or equal to 1073741824 bytes 
in size contains no lock-byte page.  A database file larger than
1073741824 contains exactly one lock-byte page.
</p>

<p>The lock-byte page is set aside for use by the operating-system specific
VFS implementation in implementing the database file locking primitives.
SQLite will not use the lock-byte page; it will never be read or written
by the SQLite core, though operating-system specific VFS implementations may
choose to read or write bytes on the lock-byte page according to the 
needs and proclivities of the underlying system.  The unix and win32
VFS implementations that come built into SQLite do not write to the
lock-byte page, but we are aware of third-party VFS implementations for
other operating systems that do sometimes write to the lock-byte page.</p>

................................................................................
<p>The freelist is organized as a linked list of freelist trunk pages
with each trunk pages containing page numbers for zero or more freelist
leaf pages.</p>

<p>A freelist trunk page consists of an array of 4-byte big-endian integers.
The size of the array is as many integers as will fit in the usable space
of a page.  The minimum usable space is 480 bytes so the array will always
be at least 120 entries in length.  The first integer in the array 
is the page number of the next freelist trunk page in the list or zero 
if this is the last freelist trunk page.  The second integer in the array
is the number of leaf page pointers to follow.  Call the second integer L.
If L is greater than zero then integers with array indexes between 2 and
L+1 inclusive contain page numbers for freelist leaf pages.</p>

<p>Freelist leaf pages contain no information.  SQLite avoid reading or
writing freelist leaf pages in order to reduce disk I/O.</p>

<p>A bug in SQLite versions prior to 3.6.0 caused the database to be
reported as corrupt if any last 6 entries in the freelist trunk page 
array contained non-zero values.  Newer versions of SQLite do not have
this problem.  However, newer versions of SQLite still avoid using the 
last six entries in the freelist trunk page array in order that database
files created by newer versions of SQLite can be read by older versions
of SQLite.</p>

<p>The number of freelist pages is stored as a 4-byte big-endian integer
in the database header at an offset of 36 from the beginning of the file.
The database header also stores the page number of the first freelist trunk
page as a 4-byte big-endian integer at an offset of 32 from the beginning
of the file.</p>

<h3>1.5 B-tree Pages</h3>

<p>A b-tree page is either an interior page or a leaf page.
A leaf page contains keys and in the case of a table b-tree each
................................................................................
key has associated content.  An interior page contains
K keys without content but with K+1 pointers to child b-tree pages.
A "pointer" in an interior b-tree page is just the 31-bit integer
page number of the child page.</p>


<p>Define the depth
of a leaf b-tree to be 1 and that the depth of any interior b-tree to be one
more than the maximum depth of any of its children.  In a well-formed
database, all children of any one interior b-tree have the same depth.</p>

<p>In an interior b-tree page, the pointers and keys logically alternate 
with a pointer on both ends. (The previous sentence is to be understood
conceptually - the actual layout of the keys and
pointers within the page is more complicated and will be described in
the sequel.)  All keys within the same page are unique and are organized


in ascending order from left to right.  For any key X, pointers to the left
of a X refer to b-tree pages on which alls keys are less than or equal to X.
Pointers to the right of X refer to pages where all keys are greater than X.</p>


<p>Within an interior b-tree page, each key and the pointer to its
immediate left are combined into a structure called a "cell".  The
right-most pointer is held separately.  A leaf b-tree page has no
pointers, but it still uses the cell structure to hold keys for
index b-trees or keys and content for table b-trees.</p>
</p>
................................................................................

<p>The 100-byte database file header is found only on page 1, which is
always a table b-tree page.  All other b-tree pages in the database file
omit this 100-byte header.</p>

<p>The reserved region is an area of unused space at the end of every
page (except the locking page) that extensions can use to hold per-page
information.  The size of the reserved region is determined by the one-byte
unsigned integer found at an offset of 20 into the database file header.
The size of the reserved region is usually zero.</p>

<p>The b-tree page header is 8 bytes in size for leaf pages and 12
bytes for interior pages.  All multibyte values in the page header
are big-endian.
The b-tree page header is composed of the following fields:</p>
................................................................................

<center>
<i>B-tree Page Header Format</i><br>
<table border=1 width="80%">
<tr><th>Offset<th>Size<th>Description
<tr><td align=center valign=top>0<td align=center valign=top>1<td align=left>
A flag indicating the b-tree page type
A value of 2 means the page is an interior index b-tree page.
A value of 5 means the page is an interior table b-tree page.
A value of 10 means the page is a leaf index b-tree page.
A value of 13 means the page is a leaf table b-tree page.
Any other value is an error.
<tr><td align=center valign=top>1<td align=center valign=top>2<td align=left>
Byte offset into the page of the first freeblock
<tr><td align=center valign=top>3<td align=center valign=top>2<td align=left>
Number of cells on this page
<tr><td align=center valign=top>5<td align=center valign=top>2<td align=left>
Offset to the first byte of the cell content area.  A zero value is used to represent an offset of 65536, which occurs on an empty root page when using a 65536-byte page size.
<tr><td align=center valign=top>7<td align=center valign=top>1<td align=left>
Number of fragmented free bytes within the cell content area
<tr><td align=center valign=top>8<td align=center valign=top>4<td align=left>
The right-most pointer (interior b-tree pages only)
</table></blockquote></center>

<p>The cell pointer array of a b-tree page immediately follows the b-tree
page header.  Let K be the number of cells on the btree.  The cell pointer
array consists of K 2-byte integer offsets to the cell contents.  The
cell pointers are arranged in key order with left-most cell (the cell with the
smallest key) first and the right-most cell (the cell with the largest
key) last.</p>

<p>Cell content is stored in the cell content region of the b-tree page.
SQLite strives to place cells as far toward the end of the b-tree page as
it can, in order to leave space for future growth of the cell pointer array.
The area in between the last cell pointer array entry and the beginning of
the first cell is the unallocated region.
</p>

<p>If a page contains no cells (which is only possible for a root page
of a table that contains no rows) then the offset to the cell content
area will equal the page size minus the bytes of reserved space.  If
the database uses a 65536-byte page size and the reserved space is zero
(the usual value for reserved space) then the cell content offset would

want to be 65536.  However, that integer is too large to be stored in a
2-byte unsigned integer, so a value of 0 is used in its place.

<p>A freeblock is a structure used to identify unallocated space within
a b-tree page.  Freeblocks are organized on a chain.  The first 2 bytes of
a freeblock are a big-endian integer which is the offset in the b-tree page
of the next freeblock in the chain, or zero if the freeblock is the last on
the chain.  The third and fourth bytes of each freeblock form
a big-endian integer which is the size of the freeblock in bytes, including
the 4-byte header.  Freeblocks are always connected in order 
of increasing offset.  The second field of the b-tree page header is the
offset of the first freeblock, or zero if there are no freeblocks on the
page.  In a well-formed b-tree page, there will always be at least one cell
before the first freeblock.</p>

<p>A freeblock requires at least 4 bytes of space.  If there is an isolated
group of 1, 2, or 3 unused bytes within the cell content area, those bytes
comprise a fragment.  The total number of bytes in all fragments is stored
in the fifth field of the b-tree page header.  In a well-formed b-tree page,
the total number of bytes in fragments may not exceed 60.</p>

<p>The total amount of free space on a b-tree page consists of the size
of the unallocated region plus the total size of all freeblocks plus the
number of fragmented free bytes.  SQLite may from time to time reorganize
a b-tree page so that there are no freeblocks or fragment bytes, all
unused bytes are contained in the unallocated space region, and all
cells are packed tightly at the end of the page.  This is called 
"defragmenting" the b-tree page.</p>

<tcl>hd_fragment varint {variable-length integer} {varint}</tcl>

................................................................................
the page type.  For the following computations, let U be the usable size
of a database page, the total page size less the reserved space at the
end of each page.  And let P be the payload size.</p>

<blockquote><dl>
<dt>Table B-Tree Leaf Cell:</dt>
<dd><p>
If the payload size P is less than U-36 then the entire payload is stored
on the b-tree page.  Let M be ((U-12)*32/255)-23.  If P is greater than U-35
then the number of byte stored on the b-tree page is the lessor of
M+((P-M)%(U-4)) and U-35.
</p></dd>

<dt>Table B-Tree Interior Cell:</dt>
<dd><p>
Interior pages of table b-trees have no payload and so there is never
any payload to spill.
</p></dd>

<dt>Index B-Tree Leaf Or Interior Cell:</dt>
<dd><p>
If the payload size P is less than ((U-12)*64/255)-22 then the entire
payload is stored on the b-tree page.  
Let M be ((U-12)*32/255)-23.  If P is greater than ((U-12)*64/255)-23
then the number of byte stored on the b-tree page is the lessor of
M+((P-M)%(U-4)) and ((U-12)*64/255)-23.
</p></dd>
</dl></blockquote>

<p>The overflow thresholds are designed to give a minimum fanout of
4 for index b-trees and to make sure enough of the payload
is on the b-tree page that the record header can usually be accessed
without consulting an overflow page.  In hindsight, the designers of
................................................................................
the SQLite b-tree logic realize that these thresholds could have been
made much simpler.  However, the computations cannot be now be changed
without resulting in an incompatible file format.  And the current computations
work well, even if they are a little complex.</p>

<h3>1.6 Cell Payload Overflow Pages</h3>

<p>When the payload of a b-tree cell is too large for the b-tree page,
the surplus is spilled onto overflow pages.  Overflow pages form a linked
list.  The first four bytes of each overflow page are a big-endian
integer which is the page number of the next page in the chain, or zero
for the final page in the chain.  The fifth byte through the last usable
byte are used to hold overflow content.</p>

<h3>1.7 Pointer Map or Ptrmap Pages</h3>

<p>Pointer map or ptrmap pages are extra pages inserted into the database
to make the operation of [auto_vacuum] and [incremental_vacuum] modes
more efficient.  Other page types in the database typically have pointers
from parent to child.  For example, a interior b-tree page contains pointers
to its child b-tree pages and an overflow chain has a pointer
from earlier to later links in the chain.  A ptrmap page contains linkage
information going in the opposite direction, from child to parent.</p>

<p>Ptrmap pages must exist in any database file which has a non-zero
largest root b-tree page value at offset 52 in the database header.
If the largest root b-tree page value is zero, then the database must not
contain ptrmap pages.</p>

<p>In a database with ptrmap pages, the first ptrmap page is page 2.
A ptrmap page consists of an array of 5-byte entries.  Let J be the
number of 5-byte entries that will fit in the usable space of a page.
(In other words, J=U/5.)  The first ptrmap page will contain back pointer
information for pages 3 through J+2, inclusive.  The next pointer map
page will be on page J+3 and that ptrmap page will provide back pointer
information for pages J+4 through 2*J+3 inclusive.  An so forth for
the entire database file.</p>

<p>In a database that uses ptrmap pages, all pages at locations identified
by the computation in the previous paragraph must be ptrmap page and no
other page may be a ptrmap page.  Except, if the byte-lock page happens to
fall on the same page number as a ptrmap page, then the ptrmap is moved
to the following page for that one case.</p>

<p>Each 5-byte entry on a ptrmap page provides back-link information about 
one of pages that immediately follow the pointer map.  If page B is
ptrmap page then back-link information about page B+1 is provided by
the first entry on the pointer map.  Information about page B+2 is
provided by the second entry.  And so forth.</p>

<p>Each 5-byte ptrmap entry consists of one byte of "page type" information
followed by a 4-byte big-endian page number.  Five page types are recognized:
</p>

<ol>
<li>A b-tree root page.  The
................................................................................
<li>A page in an overflow chain
other than the first page.  The page number is the prior page of the
overflow chain.
<li>A non-root b-tree page.  The
page number is the parent b-tree page.
</ol>

<p>In any database file that contains ptrmap pages, all b-tree root pages 
must come before any non-root b-tree page, cell payload overflow page, or
freelist page.</p>








<h2>2.0 Schema Layer</h2>

<p>The foregoing text describes low-level aspects of the SQLite file
format.  The b-tree mechanism provides powerful and efficient means of
accessing a large data set.  This section will describe how the
low-level b-tree layer is used to implement higher-level SQL
capabilities.</p>

<tcl>hd_fragment record_format {record format}</tcl>
<h3>2.1 Record Format</h3>

<p>The content of a table b-tree leaf page and the key
of any index b-tree page was characterized above
as an arbitrary sequence of bytes.
The prior discussion mentioned one key being less than another, but
did not define what "less than" meant.  The current section will address
these deficiencies.</p>

<p>Payload, be it table content or index keys, is always in the "record
format".  The record format defines a sequence of values corresponding to
to columns in a table or index.  The record format specifies the number
of columns, the datatype of each column, and the content of each column.</p>

<p>The record format makes extensive use of the 
[variable-length integer] or [varint]
representation of 64-bit signed integers defined above.</p>

<tcl>hd_fragment serialtype {serial type} {serial types}</tcl>
<p>A record contains a header and a body, in that order.  
The header begins with a single varint which determines the total number
of bytes in the header.  The varint value is the size of the header in
byte including the size varint itself.  Following the size varint are
one or more additional varints, one per column.  These additional varints
are called "serial type" numbers and
determine the datatype of each column, according to the following key:</p>

<center>
<i>Serial Type Codes Of The Record Format</i><br>
<table width="80%" border=1>
<tr><th>Serial Type<th>Content Size<th>Meaning
<tr><td valign=top align=center>0<td valign=top align=center>0<td align=left>
NULL
<tr><td valign=top align=center>1<td valign=top align=center>1<td align=left>
8-bit twos-complement integer
<tr><td valign=top align=center>2<td valign=top align=center>2<td align=left>
................................................................................
<tr><td valign=top align=center>N&#x2265;12 and even
    <td valign=top align=center>(N-12)/2<td align=left>
A string in the database encoding and (N-12)/2 bytes in length.
The nul terminator is omitted.
<tr><td valign=top align=center>N&#x2265;13 and odd
    <td valign=top align=center>(N-13)/2<td align=left>
A BLOB that is (N-13)/2 bytes in length
</table></center>

<p>Note that because of the way varints are defined, the header size varint
and serial type varints will usually consist of a single byte.  The
serial type varints for large strings and BLOBs might extend to two or three
byte varints, but that is the exception rather than the rule. 
The varint format is very efficient at coding the record header.</p>

<p>The values for each column in the record immediately follow the header.
Note that for serial types 0, 8, 9, 12, and 13, the value is zero bytes in
length.  If all columns are of these types then the body section of the
record is empty.</p>

<h3>2.2 Record Sort Order</h3>

<p>The order of keys in an index b-tree is determined by the sort order of
the records that the keys represent.  Record comparison proceeds column
by column.  Columns of a record are examined from left to right.  The
first pair of columns that are not equal determines the relative order
of the two records.  The sort order of individual columns is as
follows:</p>

<ol>
<li>NULL values (serial type 0) sort first
<li>Numeric values (serial types 1 through 9) sort next and in numeric order
<li>Text values (even serial types 12 and larger) sort next in the order
    determined by the columns collating function
<li>BLOB values (odd serial types 13 and larger) sort last in order 
    determined by memcmp().
</ol>

<p>A collating function for each column is necessary in order to compute
the order of text fields.  SQLite defines three built-in collating functions:
</p>

<blockquote><table border=0 cellspacing=10>
<tr><td valign=top>BINARY
    <td>Strings are compared byte by byte using the memcmp() function
        from the standard C library.
<tr><td valign=top>NOCASE
    <td>Like BINARY except that uppercase ASCII characters ('A' through 'Z')
        are folded into their lowercase equivalents prior to running the
        comparison.  Note that only ASCII characters are case-folded.  NOCASE
        does not implement a general purpose unicode caseless comparison.
<tr><td valign=top>RTRIM
    <td>Like BINARY except that spaces at the end of the string are elided
        prior to comparison.
</table></blockquote>

<p>Additional application-specific collating functions can be added to
SQLite using the [sqlite3_create_collation()] interface.</p>

<p>The default collating function for all strings is BINARY.
Alternative collating functions for table columns can be specified in the
[CREATE TABLE] statement using the COLLATE clause on the column definition.
When a column is indexed, the same collating function specified in the
[CREATE TABLE] statement is used for the column in the index, by default,
though this can be overridden using a COLLATE clause in the 
[CREATE INDEX] statement.

<h3>2.3 Representation Of SQL Tables</h3>

<p>Each ordinary SQL table in the database schema is represented on disk
................................................................................
by a table b-tree.  Each entry in the table b-tree corresponds to a row
of the SQL table.  The [rowid] of the SQL table is the 64-bit signed
integer key for each entry in the table b-tree.</p>

<p>The content of each SQL table row is stored in the database file by
first combining the values in the various columns into a byte array
in the record format, then storing that byte array as the payload in
an entry in the table b-tree.  The order of values in the record is
the same as the order of columns in the SQL table definition.
When an SQL table that includes an
[INTEGER PRIMARY KEY] column (which aliases the [rowid]) then that
column appears in the record as a NULL value.  SQLite will know to use
the table b-tree key rather than the NULL value when referencing the
[INTEGER PRIMARY KEY] column.</p>

<p>If the [affinity] of a column is REAL and that column contains a
value that can be converted to an integer without loss of information
(if the value contains no fractional part and is not too large to be
represented as an integer) then the column may be stored in the record
as an integer.  SQLite will know to convert the value back to floating
point when extracting it from the record.</p>


<h3>2.4 Representation Of SQL Indices</h3>

<p>Each SQL index, whether explicitly declared via a [CREATE INDEX] statement
or implied by a UNIQUE constraint, corresponds to an index b-tree in the
database file.
There is one entry in index b-tree for each row in the corresponding table.
The key to an index b-tree is
a record composed of the columns that are being indexed followed by the
[rowid] of the table row.  Because every row in a table has a unique
rowid and all keys in an index contain the rowid, all keys in an index
are unique.</p>

<p>There is a one-to-one mapping between rows in a table and
entries in each index associated with that table.
Corresponding rows int the index and table b-trees share the same rowid
value, and contain the same value for all indexed columns.</p>

<h3>2.5 Storage Of The SQL Database Schema</h3>

<p>Page 1 of a database file is the root page of a table b-tree that
holds a special table named "sqlite_master" (or "sqlite_temp_master" in
the case of a TEMP database) which stores the complete
database schema.  The structure of the sqlite_master table is as
if it had been created using the following SQL:</p>

<blockquote><pre>
CREATE TABLE sqlite_master(
  type text,
  name text,
  tbl_name text,
  rootpage integer,
  sql text
);
</pre></blockquote>

<p>The sqlite_master table contains a row for each table, index, view,
and trigger in the database schema, except there is no entry for the
sqlite_master table itself.</p>

<p>The sqlite_master.type column will be one
of the following text strings:  'table', 'index', 'view', or 'trigger'
according to the type of object defined.  The 'table' string is used
for both ordinary and [virtual tables].</p>

</p>The sqlite_master.name column will hold the name of the object.
For indices that are automatically created by UNIQUE constraints, the
name is "sqlite_autoindex_TABLE_N" where TABLE is replaced by the name

of the table that contains the UNIQUE constraint and N is an integer beginning
with 1 and increasing by one with each UNIQUE constraint seen.</p>

<p>The sqlite_master.tbl_name column holds the name of a table or view
that the object is associated with.  For a table or view, the
tbl_name column is a copy of the name column.  For an index, the tbl_name
is the name of the table that is indexed.  For a trigger, the tbl_name
column stores the name of the table or view that causes the trigger 
to fire.</p>

<p>The sqlite_master.rootpage column stores the page number of the root
b-tree page for tables and indices.  For rows that define views, triggers,
and virtual tables, the rootpage column is 0 or NULL.</p>

<p>The sqlite_master.sql column stores SQL text that describes the
object.  This SQL text is a [CREATE TABLE], [CREATE VIRTUAL TABLE],
[CREATE INDEX],
[CREATE VIEW], or [CREATE TRIGGER] statement that if evaluated against
the database file when it is the main database of a [database connection]
would recreated the object.  The text is usually a copy of the original
statement used to create the object but with normalizations applied so
that the text conforms to the following rules:

<ul>
<li>The CREATE, TABLE, VIEW, TRIGGER, and INDEX keywords at the beginning
of the statement are converted to all upper case letters.
<li>The TEMP or TEMPORARY keyword is removed if it occurs after the 
initial CREATE keyword.
<li>Any database name qualifier that occurs prior to the name of the
object being created is removed.
<li>Leading spaces are removed.
<li>All spaces following the first two keywords are converted into a single
space.
</ul>

<p>The text in the sqlite_master.sql column is a copy of the original
CREATE statement text that created the object, except normalized as
described above and as modified by subsequent [ALTER TABLE] statements.</p>

<p>For indices that are automatically created by UNIQUE constraints,
the sqlite_master.sql field is NULL.</p>


<tcl>hd_fragment rollbackjournal {rollback journal format}</tcl>
<h2>3.0 The Rollback Journal</h2>

<p>The rollback journal is a file associated with each SQLite database
fail that hold information used to restore the database file to its initial
state during the course of a transaction.
The rollback journal file is always located in the directory as the database
file and has the same name as the database file but with the string
"<tt>-journal</tt>" appended.  There can only be a single rollback journal
associated with a give database and hence there can only be one write
transaction open against a single database at one time.</p>

<p>If a transaction is aborted due to an application crash, an operating
system crash, or a hardware power failure or crash, then the database may
be left in an inconsistent state.  The next time SQLite attempts to open
the database file, the presence of the rollback journal file will be 
detected and the journal will be automatically played back to restore the
database to its state at the start of the incomplete transaction.</p>

<p>A rollback journal is only considered to be valid if it exists and
contains a valid header.  Hence a transaction can be committed in one
of three ways:
<ol>
<li>The rollback journal file can be deleted,
<li>The rollback journal file can be truncated to zero length, or
<li>The header of the rollback journal can be overwritten with
invalid header text (for example, all zeros).
</ol>
These three ways of committing a transaction correspond to the DELETE,
TRUNCATE, and PERSIST settings, respectively, of the [journal_mode pragma].
</p>


<p>A valid rollback journal begins with a header in the following format:</p>

<center>
<i>Rollback Journal Header Format</i><br>
<table width="80%" border=1>
<tr><th>Offset<th>Size<th>Description
<tr><td valign=top align=center>0
    <td valign=top align=center>8
    <td>Header string:  0xd9, 0xd5, 0x05, 0xf9, 0x20, 0xa1, 0x63, 0xd7
<tr><td valign=top align=center>8
    <td valign=top align=center>4
    <td>The "Page Count" - The number of pages in the next segment of the 
        journal, or -1 to
        mean all content to the end of the file
<tr><td valign=top align=center>12
    <td valign=top align=center>4
    <td>A random nonce for the checksum
<tr><td valign=top align=center>16
    <td valign=top align=center>4
    <td>Initial size of the database in pages
<tr><td valign=top align=center>20
    <td valign=top align=center>4
    <td>Size of a disk sector assumed by the process that wrote this
        journal.
<tr><td valign=top align=center>24
    <td valign=top align=center>4
    <td>Size of pages in this journal.
</table>
</center>

<p>A rollback journal header is padded with zeros out to the size of a 
single sector (as defined by the sector size integer at offset 20).
The header is in a sector by itself so that if a power loss occurs while
writing the sector, information that follows the header will be
(hopefully) undamaged.</p>

<p>After the header and zero padding are zero or more page records.  Each
page record stores a copy of the content of a page from the database file
before it was changed.  The same page may not appear more than once
within a single rollback journal.
To rollback an incomplete transaction, a process
has merely to read the rollback journal from beginning to end and
write pages found in the journal back into the database file at the
appropriate location.</p>

<p>Let the database page size (the value of the integer at offset 24 
................................................................................
in the journal header) be N.
Then the format of a page record is as follows:</p>

<center>
<i>Rollback Journal Page Record Format</i><br>
<table width="80%" border=1>
<tr><th>Offset<th>Size<th>Description
<tr><td valign=top align=center>0
    <td valign=top align=center>4
    <td>The page number in the database file
<tr><td valign=top align=center>4
    <td valign=top align=center>N
    <td>Original content of the page prior to the start of the transaction
<tr><td valign=top align=center>N+4
    <td valign=top align=center>4
    <td>Checksum
</table>
</center>


<p>The checksum is an unsigned 32-bit integer computed as follows:</p>

<ol>
<li>Initialize the checksum to the checksum nonce value found in the
journal header at offset 12.
<li>Initialize index X to be N-200 (where N is the size of a database page
in bytes.
<li>Interpret the four bytes at offset X into the page as a 4-byte big-endian
unsigned integer.  Add the value of that integer to the checksum.
<li>Subtrace 200 from X.
<li>If X is greater than or equal to zero, go back to step 3.
</ol>

<p>The checksum value is used to guard against incomplete writes of
a journal page record following a power failure.  A different random nonce
is used each time a transaction is started in order to minimize the risk
that unwritten sectors might by chance contain data from the same page
that was a part of prior journals.  By changing the nonce for each
transaction, stale data on disk will still generate an incorrect checksum
and be detected with high probability.  The checksum only uses a sparce sample
of 32-bit words from the data record for performance reasons - design studies 
during the planning phases of SQLite 3.0.0 showed
a significant performance hit in checksumming the entire page.</p>

<p>Let the page count value at offset 8 in the journal header by M.
If M is greater than zero then after M page records the journal file
may be zero padded out to the next multiple of the sector size and another
journal header may be inserted.  All journal headers within the same
journal must contain the same database page size and sector size.</p>

<p>If M is -1 in the initial journal header, then the number of page records
that follow is computed by figure out how many page records will fit in
the available space of the remainder of the journal file.</p>

<tcl>hd_fragment walformat {WAL format}</tcl>
<h2>4.0 The Write-Ahead Log</h2>

<p>Beginning with [version 3.7.0], SQLite supports a new transaction
control mechanism called "[WAL | write-ahead log]" or "[WAL]".
When a database is in WAL mode, all connections to that database must
use the WAL.  A particular database will use either a rollback journal
or a WAL, but not both at the same time.
The WAL is always located in the directory as the database
file and has the same name as the database file but with the string
"<tt>-wal</tt>" appended.</p>

<h3>4.1 WAL File Format</h4>

<p>A WAL file consists of a header followed by zero or more "frames".
Each frame records the revised content of a single page from the
database file.  All changes to the database are recorded by writing
frames into the WAL.  Transactions commit when a frame is written that
contains a commit marker.  A single WAL can and usually does record 
multiple transactions.  Periodically, the content of the WAL is
transferred back into the database file in an operation called a
"checkpoint".</p>

<p>A single WAL file can be reused multiple times.  In other words, the
WAL can fill up with frames and then be checkpointed and then new
frames can overwrite the old ones.  A WAL always grows from beginning
toward the end.  Checksums and counters attached to each frame are
used to determine which frames within the WAL are valid and which
are leftovers from prior checkpoints.</p>

<p>The WAL header is 32 bytes in size and consists of the following eight
big-endian 32-bit unsigned integer values:</p>

................................................................................
<tr><td valign=top align=center>16<td valign=top align=center>4
    <td>Checksum-1:  Cumulative checksum up through and including this page
<tr><td valign=top align=center>20<td valign=top align=center>4
    <td>Checksum-2:  Second half of the cumulative checksum.
</table>
</center>

<p>A frame is considered valid if and only if the following conditions are
true:</p>

<ol>
<li><p>The salt-1 and salt-2 values in the frame-header match
       salt values in the wal-header</p></li>

<li><p>The checksum values in the final 8 bytes of the frame-header
       exactly match the checksum computed consecutively on the
       WAL header and the first 8 bytes and the content of all frames
       up to and including the current frame.</p></li></li>
</ol>

<tcl>hd_fragment walcksm {WAL checksum algorithm}</tcl>
<h3>4.2 Checksum Algorithm</h3>

<p>The checksum is computed by interpreting the input as
an even number of unsigned 32-bit integers: x(0) through x(N).
The 32-bit integers are big-endian if the
magic number in the first 4 bytes of the WAL header is 0x377f0683 and
the integers are little-endian the magic number is 0x377f0682.
The checksum values are always stored in the frame header in a
big-endian format regardless of which byte order is used to compute
the checksum.</p>

<p>The checksum algorithm only works for content which is a multiple of
8 bytes in length.  In other words, if the inputs are x(0) through x(N)
then N must be odd.
The checksum algorithm is as follows:

<blockquote><pre> 
s0 = s1 = 0
for i from 0 to n-1 step 2:
   s0 += x(i) + s1;
   s1 += x(i+1) + s0;
endfor
# result in s0 and s1
</pre></blockquote>

<p>The outputs s0 and s1 are both weighted checksums using fibonacci weights
in reverse order (the largest fibonacci weight occurs on the first element
of the sequence being summed.)  The s1 value spans all 32-bit integer
terms of the sequence whereas s0 omits the final term.</p>

<h3>4.3 Checkpoint Algorithm</h3>
................................................................................
Then valid content of the WAL is transferred into the database file.
Finally, the database is flushed to persistent storage using another
xSync method call.
The xSync operations serve as write barriers - all writes launched
before the xSync must complete before any write that launches after the
xSync begins.</p>

<p>After each checkpoint, the WAL header salt-1 value is incremented and the 
salt-2 value is randomized.  This prevents old and new frames in the WAL from
being considered valid at the same time and being checkpointing together
following a crash.</p>

<tcl>hd_fragment walread {WAL read algorithm}</tcl>
<h3>4.4 Reader Algorithm</h3>

<p>To read a page from the database (call it page number P), a reader
first checks the WAL to see if it contains page P.  If so, then the
last valid instance of page P that is a followed by a commit frame
or is a commit frame itself becomes the value read.  If the WAL
contains no copies of page P that are valid and which are a commit
frame or are followed by a commit frame, then page P is read from
the database file.</p>

<p>To start a read transaction, the reader records the index of the last
valid frame in the WAL.  The reader uses this recorded "mxFrame" value
for all subsequent read operations.  New transactions can be appended
to the WAL, but as long as the reader uses its original mxFrame value
and ignores subsequently appended content, the reader will see a 
consistent snapshot of the database from a single point in time.  
This technique allows multiple concurrent readers to view different 
versions of the database content simultaneously.</p>

<p>The reader algorithm in the previous paragraphs works correctly, but 
because frames for page P can appear anywhere within the WAL, the
reader has to scan the entire WAL looking for page P frames.  If the
WAL is large (multiple megabytes is typical) that scan can be slow,
and read performance suffers.  To overcome this problem, a separate
data structure called the wal-index is maintained to expedite the
search for frames of a particular page.</p>

<tcl>hd_fragment walindexformat {wal-index} {WAL-index format}</tcl>
<h3>4.5 WAL-Index Format</h3>

<p>Conceptually, the wal-index is shared memory, though the current
................................................................................

<p>The <i>M</i> value in the previous paragraph is the "mxFrame" value
defined in [WAL read algorithm | section 4.4] that is read at the start 
of a transaction and which defines the maximum frame from the WAL that 
the reader will use.</p>

<p>The wal-index is transient.  After a crash, the wal-index is
reconstructed from the original WAL file.  The VFS is required
to either truncate or zero the header of the wal-index when the last
connection to it closes.  Because the wal-index is transient, it can
use an architecture-specific format; it does not have to be cross-platform.
Hence, unlike the database and WAL file formats which store all values
as big endian, the wal-index stores multi-byte values in the native
byte order of the host computer.</p>

<p>This document is concerned with the persist state of the database
file, and since the wal-index is a transient structure, no further 
information about the format of the wal-index will be provided here.
Complete details on the format of the wal-index are contained within
comments in SQLite source code.</p>

scenario and so are uncommon, but they are part of the state of an SQLite
database and so should not be ignored.  This document will define the format
of a rollback journal, but most of the content of this document will focus
on the main database file.</p>

<h3>1.1 Pages</h3>

<p>The main database file consists of one or more pages.  ^The size of a
page is a power of two between 512 and 65536 inclusive.  All pages within
the same database are the same size.  ^The page size for a database file
is determined by the 2-byte integer located at an offset of
16 bytes from the beginning of the database file.</p>

<p>Pages are numbered beginning with 1.  The maximum page number is
2147483646 (2<sup><small>31</small></sup> - 2).  The minimum size
SQLite database is a single 512-byte page.
The maximum size database would be 2147483646 pages at 65536 bytes per
page or 140,737,488,224,256 bytes (about 140 terabytes).  Usually SQLite will
hit the maximum file size limit of the underlying filesystem or disk
hardware size limit long before it hits its own internal size limit.</p>

<p>In common use, SQLite databases tend to range in size from a few kilobytes
to a few gigabytes.</p>

<p>At any point in time, every page in the main database has a single
................................................................................
<li>An index b-tree leaf page
</ul>
<li>A payload overflow page
<li>A pointer map page
</ul>
</p>

<p>^All reads from and writes to the main database file begin at a page
boundary and all writes are an integer number of pages in size.  ^Reads
are also usually an integer number of pages in size, with the one exception
that when the database is first opened, the first 100 bytes of the
database file (the database file header) are read as a sub-page size unit.</p>

<p>^Before any information-bearing page of the database is modified, 
the original unmodified content of that page is written into the 
rollback journal.  If a transaction is interrupted and needs to be 
rolled back, the rollback journal can then be used to restore the
database to its original state.  ^Freelist leaf pages bear no
information that would need to be restored on a rollback and so they
are not written to the journal prior to modification, in order to
reduce disk I/O.</p>

<tcl>hd_fragment database_header {database header}</tcl>
<h3>1.2 The Database Header</h3>

................................................................................
The [version-valid-for number].
<tr><td valign=top align=center>96<td valign=top align=center>4<td align=left>
[SQLITE_VERSION_NUMBER]
</table></center>

<h4>1.2.1 Magic Header String</h4>

<p>^Every valid SQLite database file begins with the following 16 bytes 
(in hex): 53 51 4c 69 74 65 20 66 6f 72 6d 61 74 20 33 00.  This byte sequence
corresponds to the UTF-8 string "SQLite format 3" including the nul
terminator character at the end.</p>

<h4>1.2.2 Page Size</h4>

<p>The two-byte value beginning at offset 16 determines the page size of 
the database.  For SQLite versions 3.7.0.1 and earlier, this value is 
................................................................................
512 and 32768, inclusive.  Beginning with SQLite version 3.7.1, a page
size of 65536 bytes is supported.  The value 65536 will not fit in a
two-byte integer, so to specify a 65536-byte page size, the value is
at offset 16 is 0x00 0x01.
This value can be interpreted as a big-endian
1 and thought of is as a magic number to represent the 65536 page size.
Or one can view the two-byte field as a little endian number and say
that it represents the page size divided by 256.  These two 
interpretations of the page-size field are equivelent.</p>

<h4>1.2.3 File format version numbers</h4>

<p>The file format write version and file format read version at offsets
18 and 19 are intended to allow for enhancements of the file format
in future versions of SQLite.  In current versions of SQLite, both of
these values are 1 for rollback journalling modes and 2 for [WAL]
................................................................................
greater than 2 is encounter, then that database cannot be read or written.</p>

<h4>1.2.4 Reserved bytes per page</h4>

<p>SQLite has the ability to set aside a small number of extra bytes at
the end of every page for use by extensions.  These extra bytes are
used, for example, by the SQLite Encryption Extension to store a nonce
and/or cryptographic checksum associated with each page.  ^The 
"reserved space" size in the 1-byte integer at offset 20 is the number
of bytes of space at the end of each page to reserve for extensions.
This value is usually 0.  The value can be odd.</p>

<tcl>hd_fragment usable_size {usable size}</tcl>
<p>The "usable size" of a database page is the page size specify by the
2-byte integer at offset 16 in the header less the "reserved" space size
recorded in the 1-byte integer at offset 20 in the header.  The usable
size of a page might be an odd number.  ^(However, the usable size is not
allowed to be less than 480.  In other words, if the page size is 512,
then the reserved space size cannot exceed 32.)^</p>

<h4>1.2.5 Payload fractions</h4>

<p>^The maximum and minimum embedded payload fractions and the leaf
payload fraction values must be 64, 32, and 32.  These values were
originally intended to as tunable parameters that could be used to
modify the storage format of the b-tree algorithm.  However, that
functionality is not supported and there are no current plans to add
support in the future.  Hence, these three bytes are fixed at the
values specified.</p>

<h4>1.2.6 File change counter</h4>

<tcl>hd_fragment chngctr {change counter}</tcl>
<p>^The file change counter is a 4-byte big-endian integer which is
incremented whenever the database file is unlocked after having
been modified.
When two or more processes are reading the same database file, each 
process can detect database changes from other processes by monitoring 
the change counter.
A process will normally want to flush its database page cache when
another process modified the database, since the cache has become stale.
The file change counter facilitates this.</p>

................................................................................
<p>In WAL mode, changes to the database are detected using the wal-index
and so the change counter is not needed.  Hence, the change counter might
not be incremented on each transaction in WAL mode.</p>

<h4>1.2.7 In-header database size</h4>

<tcl>hd_fragment filesize {in-header database size}</tcl>
<p>^The 4-byte big-endian integer at offset 28 into the header 
stores the size of the database file in pages.  ^If this in-header
datasize size is not valid (see the next paragraph), then the database 
size is computed by looking
at the actual size of the database file. Older versions of SQLite
ignored the in-header database size and used the actual file size
exclusively.  ^Newer versions of SQLite use the in-header database
size if it is available but fall back to the actual file size if
the in-header database size is not valid.</p>

<p>^The in-header database size is only considered to be valid if
it is non-zero and if the 4-byte [change counter] at offset 24
exactly matches the 4-byte [version-valid-for number] at offset 92.
^The in-header database size is always valid 
when the database is only modified using recent versions of SQLite
(versions 3.7.0 and later).
If a legacy version of SQLite writes to the database, it will not
know to update the in-header database size and so the in-header
database size could be incorrect.  But legacy versions of SQLite
will also leave the version-valid-for number at offset 92 unchanged
so it will not match the change-counter.  Hence, invalid in-header
database sizes can be detected (and ignored) by observing when
the change-counter does not match the version-valid-for number.</p>

<h4>1.2.8 Free page list</h4>

<p>Unused pages in the database file are stored on a freelist.  ^The
4-byte big-endian integer at offset 32 stores the page number of
the first page of the freelist, or zero if the freelist is empty.
^The 4-byte big-endian integer at offset 36 stores stores the total 
number of pages on the freelist.</p>

<h4>1.2.9 Schema cookie</h4>

<p>^The schema cookie is a 4-byte big-endian integer at offset 40
that is incremented whenever the database schema changes.  A 
prepared statement is compiled against a specific version of the
database schema.  ^Whenever the database schema changes, the statement
must be reprepared.  ^Whenever a prepared statement runs, it first checks
the schema cookie to make sure the value is the same as when the statement
was prepared and if the schema cookie has changed, the statement aborts
in order to force the statement to be reprepared.</p>

<h4>1.2.10 Schema format number</h4>

<p>The schema format number is a 4-byte big-endian integer at offset 44.
The schema format number is similar to the file format read and write
version numbers at offsets 18 and 19 except that the schema format number
refers to the high-level SQL formatting rather than the low-level b-tree
................................................................................
[ALTER TABLE | ALTER TABLE ... ADD COLUMN] functionality.  Support for
reading and writing format 2 was added in SQLite version 3.1.3 
on 2005-02-19.</li>
<li value=3>Format 3 adds the ability of extra columns added by
[ALTER TABLE | ALTER TABLE ... ADD COLUMN] to have non-NULL default
values.  This capability was added in SQLite version 3.1.4 
on 2005-03-11.</li>
<li value=4>^Format 4 causes SQLite to respect the DESC keyword on
index declarations.  (^The DESC keyword is ignored in indices for 
formats 1, 2, and 3.)
^Format 4 also adds two new boolean record type values ([serial types]
8 and 9.)  Support for format 4 was added in SQLite 3.3.0 on
2006-01-10.</li>
</ol>

<p>^New database files created by SQLite use format 1 by default, so
that database files created by newer versions of SQLite can still
be read by older versions of SQLite.
^The [legacy_file_format pragma] can be used to cause SQLite
to create new database files using format 4.  Future versions of 
SQLite may begin to create files using format 4 by default.</p>

<h4>1.2.11 Suggested cache size</h4>

<p>The 4-byte big-endian signed integer at offset 48 is the suggest
cache size in pages for the database file.  The value is a suggestion
................................................................................
only and SQLite is under no obligation to honor it.  The absolute value
of the integer is used as the suggested size.  The suggested cache size
can be set using the [default_cache_size pragma].</p>

<h4>1.2.12 Incremental vacuum settings</h4>

<p>The two 4-byte big-endian integers at offsets 52 and 64 are used
to manage the [auto_vacuum] and [incremental_vacuum] modes.  ^If
the integer at offset 52 is zero then pointer-map (ptrmap) pages are
omitted from the database file and neither auto_vacuum nor
incremental_vacuum are supported.  ^If the integer at offset 52 is
non-zero then it is the page number of the largest root page in the
database file, the database file contain ptrmap pages, and the
mode must be either auto_vacuum or incremental_vacuum.  ^In this latter
case, the integer at offset 64 is true for incremental_vacuum and
false for auto_vacuum.  ^If the integer at offset 52 is zero then
the integer at offset 64 must also be zero.</p>

<h4>1.2.13 Text encoding</h4>

<p>^The 4-byte big-endian integer at offset 56 determines the encoding
used for all text strings stored in the database.  ^A value of 1 means
UTF-8.  ^A value of 2 means UTF-16le.  ^A value of 3 means UTF-16be.
No other values are allowed.</p>

<h4>1.2.14 User version number</h4>

<p>^The 4-byte big-endian integer at offset 60 is the user version which
is set and queried by the [user_version pragma].  The user version is
not used by SQLite.</p>

<tcl>hd_fragment validfor {version-valid-for number}</tcl>
<h4>1.2.15 Write library version number and version-valid-for number</h4>

<p>^The 4-byte big-endian integer at offset 96 stores the 
[SQLITE_VERSION_NUMBER] value for the SQLite library that most
recently modified the database file.  ^The 4-byte big-ending integer at
offset 92 is the value of the [change counter] when the version number
was stored.  The integer at offset 92 indicates which transaction
the version number is valid for and is sometimes called the
"version-valid-for number".

<h4>1.2.16 Header space reserved for expansion</h4>

................................................................................
inclusive.  A database file that is less than or equal to 1073741824 bytes 
in size contains no lock-byte page.  A database file larger than
1073741824 contains exactly one lock-byte page.
</p>

<p>The lock-byte page is set aside for use by the operating-system specific
VFS implementation in implementing the database file locking primitives.
^SQLite will not use the lock-byte page; it will never be read or written
by the SQLite core, though operating-system specific VFS implementations may
choose to read or write bytes on the lock-byte page according to the 
needs and proclivities of the underlying system.  The unix and win32
VFS implementations that come built into SQLite do not write to the
lock-byte page, but we are aware of third-party VFS implementations for
other operating systems that do sometimes write to the lock-byte page.</p>

................................................................................
<p>The freelist is organized as a linked list of freelist trunk pages
with each trunk pages containing page numbers for zero or more freelist
leaf pages.</p>

<p>A freelist trunk page consists of an array of 4-byte big-endian integers.
The size of the array is as many integers as will fit in the usable space
of a page.  The minimum usable space is 480 bytes so the array will always
be at least 120 entries in length.  ^The first integer in the array 
is the page number of the next freelist trunk page in the list or zero 
if this is the last freelist trunk page.  ^The second integer in the array
is the number of leaf page pointers to follow.  Call the second integer L.
^If L is greater than zero then integers with array indexes between 2 and
L+1 inclusive contain page numbers for freelist leaf pages.</p>

<p>Freelist leaf pages contain no information.  ^SQLite avoid reading or
writing freelist leaf pages in order to reduce disk I/O.</p>

<p>A bug in SQLite versions prior to 3.6.0 caused the database to be
reported as corrupt if any last 6 entries in the freelist trunk page 
array contained non-zero values.  Newer versions of SQLite do not have
this problem.  ^However, newer versions of SQLite still avoid using the 
last six entries in the freelist trunk page array in order that database
files created by newer versions of SQLite can be read by older versions
of SQLite.</p>

<p>^The number of freelist pages is stored as a 4-byte big-endian integer
in the database header at an offset of 36 from the beginning of the file.
^The database header also stores the page number of the first freelist trunk
page as a 4-byte big-endian integer at an offset of 32 from the beginning
of the file.</p>

<h3>1.5 B-tree Pages</h3>

<p>A b-tree page is either an interior page or a leaf page.
A leaf page contains keys and in the case of a table b-tree each
................................................................................
key has associated content.  An interior page contains
K keys without content but with K+1 pointers to child b-tree pages.
A "pointer" in an interior b-tree page is just the 31-bit integer
page number of the child page.</p>


<p>Define the depth
of a leaf b-tree to be 1 and the the depth of any interior b-tree to be one
more than the maximum depth of any of its children.  ^In a well-formed
database, all children of any one interior b-tree have the same depth.</p>

<p>In an interior b-tree page, the pointers and keys logically alternate 
with a pointer on both ends. (The previous sentence is to be understood
conceptually - the actual layout of the keys and
pointers within the page is more complicated and will be described in
the sequel.)  All keys within the same page are unique and are logically
organized in ascending order from left to right.  (Again, this ordering
is logical, not physical.  The actual location of keys within the page
is arbitrary.) ^For any key X, pointers to the left
of a X refer to b-tree pages on which alls keys are less than or equal to X.
^Pointers to the right of X refer to pages where all keys are 
greater than X.</p>

<p>Within an interior b-tree page, each key and the pointer to its
immediate left are combined into a structure called a "cell".  The
right-most pointer is held separately.  A leaf b-tree page has no
pointers, but it still uses the cell structure to hold keys for
index b-trees or keys and content for table b-trees.</p>
</p>
................................................................................

<p>The 100-byte database file header is found only on page 1, which is
always a table b-tree page.  All other b-tree pages in the database file
omit this 100-byte header.</p>

<p>The reserved region is an area of unused space at the end of every
page (except the locking page) that extensions can use to hold per-page
information.  ^The size of the reserved region is determined by the one-byte
unsigned integer found at an offset of 20 into the database file header.
The size of the reserved region is usually zero.</p>

<p>The b-tree page header is 8 bytes in size for leaf pages and 12
bytes for interior pages.  All multibyte values in the page header
are big-endian.
The b-tree page header is composed of the following fields:</p>
................................................................................

<center>
<i>B-tree Page Header Format</i><br>
<table border=1 width="80%">
<tr><th>Offset<th>Size<th>Description
<tr><td align=center valign=top>0<td align=center valign=top>1<td align=left>
A flag indicating the b-tree page type
^A value of 2 means the page is an interior index b-tree page.
^A value of 5 means the page is an interior table b-tree page.
^A value of 10 means the page is a leaf index b-tree page.
^A value of 13 means the page is a leaf table b-tree page.
^Any other value for the b-tree page type is an error.
<tr><td align=center valign=top>1<td align=center valign=top>2<td align=left>
Byte offset into the page of the first freeblock
<tr><td align=center valign=top>3<td align=center valign=top>2<td align=left>
Number of cells on this page
<tr><td align=center valign=top>5<td align=center valign=top>2<td align=left>
Offset to the first byte of the cell content area.  A zero value is used to represent an offset of 65536, which occurs on an empty root page when using a 65536-byte page size.
<tr><td align=center valign=top>7<td align=center valign=top>1<td align=left>
Number of fragmented free bytes within the cell content area
<tr><td align=center valign=top>8<td align=center valign=top>4<td align=left>
The right-most pointer (interior b-tree pages only)
</table></blockquote></center>

<p>^The cell pointer array of a b-tree page immediately follows the b-tree
page header.  Let K be the number of cells on the btree.  ^The cell pointer
array consists of K 2-byte integer offsets to the cell contents.  ^The
cell pointers are arranged in key order with left-most cell (the cell with the
smallest key) first and the right-most cell (the cell with the largest
key) last.</p>

<p>Cell content is stored in the cell content region of the b-tree page.
SQLite strives to place cells as far toward the end of the b-tree page as
it can, in order to leave space for future growth of the cell pointer array.
The area in between the last cell pointer array entry and the beginning of
the first cell is the unallocated region.
</p>

<p>^If a page contains no cells (which is only possible for a root page
of a table that contains no rows) then the offset to the cell content
area will equal the page size minus the bytes of reserved space.  ^(If
the database uses a 65536-byte page size and the reserved space is zero
(the usual value for reserved space) then the cell content offset of an
empty page wants to be 65536.  
However, that integer is too large to be stored in a
2-byte unsigned integer, so a value of 0 is used in its place.)^

<p>A freeblock is a structure used to identify unallocated space within
a b-tree page.  Freeblocks are organized as a chain.  ^The first 2 bytes of
a freeblock are a big-endian integer which is the offset in the b-tree page
of the next freeblock in the chain, or zero if the freeblock is the last on
the chain.  ^The third and fourth bytes of each freeblock form
a big-endian integer which is the size of the freeblock in bytes, including
the 4-byte header.  ^Freeblocks are always connected in order 
of increasing offset.  ^The second field of the b-tree page header is the
offset of the first freeblock, or zero if there are no freeblocks on the
page.  ^In a well-formed b-tree page, there will always be at least one cell
before the first freeblock.</p>

<p>A freeblock requires at least 4 bytes of space.  If there is an isolated
group of 1, 2, or 3 unused bytes within the cell content area, those bytes
comprise a fragment.  ^The total number of bytes in all fragments is stored
in the fifth field of the b-tree page header.  ^In a well-formed b-tree page,
the total number of bytes in fragments may not exceed 60.</p>

<p>The total amount of free space on a b-tree page consists of the size
of the unallocated region plus the total size of all freeblocks plus the
number of fragmented free bytes.  ^SQLite may from time to time reorganize
a b-tree page so that there are no freeblocks or fragment bytes, all
unused bytes are contained in the unallocated space region, and all
cells are packed tightly at the end of the page.  This is called 
"defragmenting" the b-tree page.</p>

<tcl>hd_fragment varint {variable-length integer} {varint}</tcl>

................................................................................
the page type.  For the following computations, let U be the usable size
of a database page, the total page size less the reserved space at the
end of each page.  And let P be the payload size.</p>

<blockquote><dl>
<dt>Table B-Tree Leaf Cell:</dt>
<dd><p>
^If the payload size P is less than U-36 then the entire payload is stored
on the b-tree page.  ^(Let M be ((U-12)*32/255)-23.  If P is greater than U-35
then the number of byte stored on the b-tree page is the lessor of
M+((P-M)%(U-4)) and U-35.)^
</p></dd>

<dt>Table B-Tree Interior Cell:</dt>
<dd><p>
Interior pages of table b-trees have no payload and so there is never
any payload to spill.
</p></dd>

<dt>Index B-Tree Leaf Or Interior Cell:</dt>
<dd><p>
^If the payload size P is less than ((U-12)*64/255)-22 then the entire
payload is stored on the b-tree page.  
^(Let M be ((U-12)*32/255)-23.  If P is greater than ((U-12)*64/255)-23
then the number of byte stored on the b-tree page is the lessor of
M+((P-M)%(U-4)) and ((U-12)*64/255)-23.)^
</p></dd>
</dl></blockquote>

<p>The overflow thresholds are designed to give a minimum fanout of
4 for index b-trees and to make sure enough of the payload
is on the b-tree page that the record header can usually be accessed
without consulting an overflow page.  In hindsight, the designers of
................................................................................
the SQLite b-tree logic realize that these thresholds could have been
made much simpler.  However, the computations cannot be now be changed
without resulting in an incompatible file format.  And the current computations
work well, even if they are a little complex.</p>

<h3>1.6 Cell Payload Overflow Pages</h3>

<p>^When the payload of a b-tree cell is too large for the b-tree page,
the surplus is spilled onto overflow pages.  ^Overflow pages form a linked
list.  ^The first four bytes of each overflow page are a big-endian
integer which is the page number of the next page in the chain, or zero
for the final page in the chain.  ^The fifth byte through the last usable
byte are used to hold overflow content.</p>

<h3>1.7 Pointer Map or Ptrmap Pages</h3>

<p>Pointer map or ptrmap pages are extra pages inserted into the database
to make the operation of [auto_vacuum] and [incremental_vacuum] modes
more efficient.  Other page types in the database typically have pointers
from parent to child.  For example, a interior b-tree page contains pointers
to its child b-tree pages and an overflow chain has a pointer
from earlier to later links in the chain.  A ptrmap page contains linkage
information going in the opposite direction, from child to parent.</p>

<p>^Ptrmap pages must exist in any database file which has a non-zero
largest root b-tree page value at offset 52 in the database header.
^If the largest root b-tree page value is zero, then the database must not
contain ptrmap pages.</p>

<p>^In a database with ptrmap pages, the first ptrmap page is page 2.
A ptrmap page consists of an array of 5-byte entries.  Let J be the
number of 5-byte entries that will fit in the usable space of a page.
(In other words, J=U/5.)  ^The first ptrmap page will contain back pointer
information for pages 3 through J+2, inclusive.  ^The second pointer map
page will be on page J+3 and that ptrmap page will provide back pointer
information for pages J+4 through 2*J+3 inclusive.  An so forth for
the entire database file.</p>

<p>^(In a database that uses ptrmap pages, all pages at locations identified
by the computation in the previous paragraph must be ptrmap page and no
other page may be a ptrmap page.  Except, if the byte-lock page happens to
fall on the same page number as a ptrmap page, then the ptrmap is moved
to the following page for that one case.)^</p>

<p>Each 5-byte entry on a ptrmap page provides back-link information about 
one of pages that immediately follow the pointer map.  ^(If page B is a
ptrmap page then back-link information about page B+1 is provided by
the first entry on the pointer map.  Information about page B+2 is
provided by the second entry.  And so forth.)^</p>

<p>Each 5-byte ptrmap entry consists of one byte of "page type" information
followed by a 4-byte big-endian page number.  Five page types are recognized:
</p>

<ol>
<li>A b-tree root page.  The
................................................................................
<li>A page in an overflow chain
other than the first page.  The page number is the prior page of the
overflow chain.
<li>A non-root b-tree page.  The
page number is the parent b-tree page.
</ol>

<p>^In any database file that contains ptrmap pages, all b-tree root pages 
must come before any non-root b-tree page, cell payload overflow page, or
freelist page.  This restriction ensures that a root page will never
be moved during an auto-vacuum or incremental-vacuum.  The auto-vacuum
logic is not to update the root_page field of the sqlite_master
table and so it is necessary to prevent root pages from being moved
during an auto-vacuum in order to preserve the integrity of the
sqlite_master table.  ^Root pages are moved to the beginning of the
database file by the CREATE TABLE, CREATE INDEX, DROP TABLE, and
DROP INDEX operations.</p>

<h2>2.0 Schema Layer</h2>

<p>The foregoing text describes low-level aspects of the SQLite file
format.  The b-tree mechanism provides a powerful and efficient means of
accessing a large data set.  This section will describe how the
low-level b-tree layer is used to implement higher-level SQL
capabilities.</p>

<tcl>hd_fragment record_format {record format}</tcl>
<h3>2.1 Record Format</h3>

<p>The content of a table b-tree leaf page and the key
of any index b-tree page was characterized above
as an arbitrary sequence of bytes.
The prior discussion mentioned one key being less than another, but
did not define what "less than" meant.  The current section will address
these omissions.</p>

<p>Payload, be it table content or index keys, is always in the "record
format".  The record format defines a sequence of values corresponding to
to columns in a table or index.  The record format specifies the number
of columns, the datatype of each column, and the content of each column.</p>

<p>The record format makes extensive use of the 
[variable-length integer] or [varint]
representation of 64-bit signed integers defined above.</p>

<tcl>hd_fragment serialtype {serial type} {serial types}</tcl>
<p>A record contains a header and a body, in that order.  
^(The header begins with a single varint which determines the total number
of bytes in the header.  The varint value is the size of the header in
bytes including the size varint itself.)^  ^Following the size varint are
one or more additional varints, one per column.  These additional varints
are called "serial type" numbers and
determine the datatype of each column, according to the following key:</p>

<center>
^(<i>Serial Type Codes Of The Record Format</i><br>
<table width="80%" border=1>
<tr><th>Serial Type<th>Content Size<th>Meaning
<tr><td valign=top align=center>0<td valign=top align=center>0<td align=left>
NULL
<tr><td valign=top align=center>1<td valign=top align=center>1<td align=left>
8-bit twos-complement integer
<tr><td valign=top align=center>2<td valign=top align=center>2<td align=left>
................................................................................
<tr><td valign=top align=center>N&#x2265;12 and even
    <td valign=top align=center>(N-12)/2<td align=left>
A string in the database encoding and (N-12)/2 bytes in length.
The nul terminator is omitted.
<tr><td valign=top align=center>N&#x2265;13 and odd
    <td valign=top align=center>(N-13)/2<td align=left>
A BLOB that is (N-13)/2 bytes in length
</table></center>)^

<p>Note that because of the way varints are defined, the header size varint
and serial type varints will usually consist of a single byte.  The
serial type varints for large strings and BLOBs might extend to two or three
byte varints, but that is the exception rather than the rule. 
The varint format is very efficient at coding the record header.</p>

<p>The values for each column in the record immediately follow the header.
^(Note that for serial types 0, 8, 9, 12, and 13, the value is zero bytes in
length.  If all columns are of these types then the body section of the
record is empty.)^</p>

<h3>2.2 Record Sort Order</h3>

<p>The order of keys in an index b-tree is determined by the sort order of
the records that the keys represent.  Record comparison proceeds column
by column.  Columns of a record are examined from left to right.  The
first pair of columns that are not equal determines the relative order
of the two records.  The sort order of individual columns is as
follows:</p>

<ol>
<li>^NULL values (serial type 0) sort first
<li>^Numeric values (serial types 1 through 9) sort next and in numeric order
<li>^Text values (even serial types 12 and larger) sort next in the order
    determined by the columns collating function
<li>^BLOB values (odd serial types 13 and larger) sort last in order 
    determined by memcmp().
</ol>

<p>A collating function for each column is necessary in order to compute
the order of text fields.  SQLite defines three built-in collating functions:
</p>

<blockquote><table border=0 cellspacing=10>
<tr>^<td valign=top>BINARY
    <td>Strings are compared byte by byte using the memcmp() function
        from the standard C library.
<tr>^<td valign=top>NOCASE
    <td>Like BINARY except that uppercase ASCII characters ('A' through 'Z')
        are folded into their lowercase equivalents prior to running the
        comparison.  Note that only ASCII characters are case-folded.  ^NOCASE
        does not implement a general purpose unicode caseless comparison.
<tr>^<td valign=top>RTRIM
    <td>Like BINARY except that spaces at the end of the string are elided
        prior to comparison.
</table></blockquote>

<p>^Additional application-specific collating functions can be added to
SQLite using the [sqlite3_create_collation()] interface.</p>

<p>^The default collating function for all strings is BINARY.
^Alternative collating functions for table columns can be specified in the
[CREATE TABLE] statement using the COLLATE clause on the column definition.
^When a column is indexed, the same collating function specified in the
[CREATE TABLE] statement is used for the column in the index, by default,
though this can be overridden using a COLLATE clause in the 
[CREATE INDEX] statement.

<h3>2.3 Representation Of SQL Tables</h3>

<p>Each ordinary SQL table in the database schema is represented on disk
................................................................................
by a table b-tree.  Each entry in the table b-tree corresponds to a row
of the SQL table.  The [rowid] of the SQL table is the 64-bit signed
integer key for each entry in the table b-tree.</p>

<p>The content of each SQL table row is stored in the database file by
first combining the values in the various columns into a byte array
in the record format, then storing that byte array as the payload in
an entry in the table b-tree.  ^The order of values in the record is
the same as the order of columns in the SQL table definition.
^When an SQL table that includes an
[INTEGER PRIMARY KEY] column (which aliases the [rowid]) then that
column appears in the record as a NULL value.  ^SQLite will always use
the table b-tree key rather than the NULL value when referencing the
[INTEGER PRIMARY KEY] column.</p>

<p>^If the [affinity] of a column is REAL and that column contains a
value that can be converted to an integer without loss of information
(if the value contains no fractional part and is not too large to be
represented as an integer) then the column may be stored in the record
as an integer.  ^SQLite will convert the value back to floating
point when extracting it from the record.</p>


<h3>2.4 Representation Of SQL Indices</h3>

<p>^Each SQL index, whether explicitly declared via a [CREATE INDEX] statement
or implied by a UNIQUE constraint, corresponds to an index b-tree in the
database file.
^There is one entry in index b-tree for each row in the corresponding table.
^The key to an index b-tree is
a record composed of the columns that are being indexed followed by the
[rowid] of the table row.  Because every row in a table has a unique
rowid and all keys in an index contain the rowid, all keys in an index
are unique.</p>

<p>^There is a one-to-one mapping between rows in a table and
entries in each index associated with that table.
^Corresponding rows int the index and table b-trees share the same rowid
value, and contain the same value for all indexed columns.</p>

<h3>2.5 Storage Of The SQL Database Schema</h3>

<p>^Page 1 of a database file is the root page of a table b-tree that
holds a special table named "sqlite_master" (or "sqlite_temp_master" in
the case of a TEMP database) which stores the complete
database schema.  ^(The structure of the sqlite_master table is as
if it had been created using the following SQL:</p>

<blockquote><pre>
CREATE TABLE sqlite_master(
  type text,
  name text,
  tbl_name text,
  rootpage integer,
  sql text
);
</pre></blockquote>)^

<p>^The sqlite_master table contains a row for each table, index, view,
and trigger in the database schema, except there is no entry for the
sqlite_master table itself.</p>

<p>^(The sqlite_master.type column will be one
of the following text strings:  'table', 'index', 'view', or 'trigger'
according to the type of object defined.  ^The 'table' string is used
for both ordinary and [virtual tables].)^</p>

</p>^(The sqlite_master.name column will hold the name of the object.
^For indices that are automatically created by UNIQUE or PRIMARY KEY
constraints, the name is "sqlite_autoindex_TABLE_N" where TABLE is 
replaced by the name of the table that contains the constraint and N 
is an integer beginning
with 1 and increasing by one with each constraint seen.)^</p>

<p>The sqlite_master.tbl_name column holds the name of a table or view
that the object is associated with.  ^For a table or view, the
tbl_name column is a copy of the name column.  ^For an index, the tbl_name
is the name of the table that is indexed.  ^For a trigger, the tbl_name
column stores the name of the table or view that causes the trigger 
to fire.</p>

<p>^(The sqlite_master.rootpage column stores the page number of the root
b-tree page for tables and indices.)^  ^For rows that define views, triggers,
and virtual tables, the rootpage column is 0 or NULL.</p>

<p>^(The sqlite_master.sql column stores SQL text that describes the
object.  This SQL text is a [CREATE TABLE], [CREATE VIRTUAL TABLE],
[CREATE INDEX],
[CREATE VIEW], or [CREATE TRIGGER] statement that if evaluated against
the database file when it is the main database of a [database connection]
would recreated the object.)  The text is usually a copy of the original
statement used to create the object but with normalizations applied so
that the text conforms to the following rules:

<ul>
<li>^The CREATE, TABLE, VIEW, TRIGGER, and INDEX keywords at the beginning
of the statement are converted to all upper case letters.
<li>^The TEMP or TEMPORARY keyword is removed if it occurs after the 
initial CREATE keyword.
<li>^Any database name qualifier that occurs prior to the name of the
object being created is removed.
<li>^Leading spaces are removed.
<li>^All spaces following the first two keywords are converted into a single
space.
</ul>

<p>^(The text in the sqlite_master.sql column is a copy of the original
CREATE statement text that created the object, except normalized as
described above and as modified by subsequent [ALTER TABLE] statements.)^</p>

<p>^(For indices that are automatically created by UNIQUE or
PRIMARY KEY constraints, the sqlite_master.sql field is NULL.)^</p>


<tcl>hd_fragment rollbackjournal {rollback journal format}</tcl>
<h2>3.0 The Rollback Journal</h2>

<p>The rollback journal is a file associated with each SQLite database
fail that hold information used to restore the database file to its initial
state during the course of a transaction.
^The rollback journal file is always located in the directory as the database
file and has the same name as the database file but with the string
"<tt>-journal</tt>" appended.  There can only be a single rollback journal
associated with a give database and hence there can only be one write
transaction open against a single database at one time.</p>

<p>If a transaction is aborted due to an application crash, an operating
system crash, or a hardware power failure or crash, then the database may
be left in an inconsistent state.  ^The next time SQLite attempts to open
the database file, the presence of the rollback journal file will be 
detected and the journal will be automatically played back to restore the
database to its state at the start of the incomplete transaction.</p>

<p>^A rollback journal is only considered to be valid if it exists and
contains a valid header.  Hence a transaction can be committed in one
of three ways:
<ol>
<li>^The rollback journal file can be deleted,
<li>^The rollback journal file can be truncated to zero length, or
<li>^The header of the rollback journal can be overwritten with
invalid header text (for example, all zeros).
</ol>
^These three ways of committing a transaction correspond to the DELETE,
TRUNCATE, and PERSIST settings, respectively, of the [journal_mode pragma].
</p>


<p>A valid rollback journal begins with a header in the following format:</p>

<center>
<i>Rollback Journal Header Format</i><br>
<table width="80%" border=1>
<tr><th>Offset<th>Size<th>Description
<tr>^(<td valign=top align=center>0
    <td valign=top align=center>8
    <td>Header string:  0xd9, 0xd5, 0x05, 0xf9, 0x20, 0xa1, 0x63, 0xd7)^
<tr>^(<td valign=top align=center>8
    <td valign=top align=center>4
    <td>The "Page Count" - The number of pages in the next segment of the 
        journal, or -1 to
        mean all content to the end of the file)^
<tr>^(<td valign=top align=center>12
    <td valign=top align=center>4
    <td>A random nonce for the checksum)^
<tr>^(<td valign=top align=center>16
    <td valign=top align=center>4
    <td>Initial size of the database in pages)^
<tr>^(<td valign=top align=center>20
    <td valign=top align=center>4
    <td>Size of a disk sector assumed by the process that wrote this
        journal.)^
<tr>^(<td valign=top align=center>24
    <td valign=top align=center>4
    <td>Size of pages in this journal.)^
</table>
</center>

<p>^A rollback journal header is padded with zeros out to the size of a 
single sector (as defined by the sector size integer at offset 20).
The header is in a sector by itself so that if a power loss occurs while
writing the sector, information that follows the header will be
(hopefully) undamaged.</p>

<p>^After the header and zero padding are zero or more page records.  ^Each
page record stores a copy of the content of a page from the database file
before it was changed.  ^The same page may not appear more than once
within a single rollback journal.
To rollback an incomplete transaction, a process
has merely to read the rollback journal from beginning to end and
write pages found in the journal back into the database file at the
appropriate location.</p>

<p>Let the database page size (the value of the integer at offset 24 
................................................................................
in the journal header) be N.
Then the format of a page record is as follows:</p>

<center>
<i>Rollback Journal Page Record Format</i><br>
<table width="80%" border=1>
<tr><th>Offset<th>Size<th>Description
<tr>^(<td valign=top align=center>0
    <td valign=top align=center>4
    <td>The page number in the database file)^
<tr>^(<td valign=top align=center>4
    <td valign=top align=center>N
    <td>Original content of the page prior to the start of the transaction)^
<tr>^(<td valign=top align=center>N+4
    <td valign=top align=center>4
    <td>Checksum)^
</table>
</center>


<p>^(The checksum is an unsigned 32-bit integer computed as follows:</p>

<ol>
<li>Initialize the checksum to the checksum nonce value found in the
journal header at offset 12.
<li>Initialize index X to be N-200 (where N is the size of a database page
in bytes.
<li>Interpret the four bytes at offset X into the page as a 4-byte big-endian
unsigned integer.  Add the value of that integer to the checksum.
<li>Subtrace 200 from X.
<li>If X is greater than or equal to zero, go back to step 3.
</ol>)^

<p>The checksum value is used to guard against incomplete writes of
a journal page record following a power failure.  A different random nonce
is used each time a transaction is started in order to minimize the risk
that unwritten sectors might by chance contain data from the same page
that was a part of prior journals.  By changing the nonce for each
transaction, stale data on disk will still generate an incorrect checksum
and be detected with high probability.  The checksum only uses a sparce sample
of 32-bit words from the data record for performance reasons - design studies 
during the planning phases of SQLite 3.0.0 showed
a significant performance hit in checksumming the entire page.</p>

<p>Let the page count value at offset 8 in the journal header be M.
^If M is greater than zero then after M page records the journal file
may be zero padded out to the next multiple of the sector size and another
journal header may be inserted.  ^All journal headers within the same
journal must contain the same database page size and sector size.</p>

<p>^If M is -1 in the initial journal header, then the number of page records
that follow is computed by computing how many page records will fit in
the available space of the remainder of the journal file.</p>

<tcl>hd_fragment walformat {WAL format}</tcl>
<h2>4.0 The Write-Ahead Log</h2>

<p>Beginning with [version 3.7.0], SQLite supports a new transaction
control mechanism called "[WAL | write-ahead log]" or "[WAL]".
^When a database is in WAL mode, all connections to that database must
use the WAL.  ^A particular database will use either a rollback journal
or a WAL, but not both at the same time.
^The WAL is always located in the directory as the database
file and has the same name as the database file but with the string
"<tt>-wal</tt>" appended.</p>

<h3>4.1 WAL File Format</h4>

<p>A WAL file consists of a header followed by zero or more "frames".
Each frame records the revised content of a single page from the
database file.  All changes to the database are recorded by writing
frames into the WAL.  Transactions commit when a frame is written that
contains a commit marker.  ^A single WAL can and usually does record 
multiple transactions.  Periodically, the content of the WAL is
transferred back into the database file in an operation called a
"checkpoint".</p>

<p>^A single WAL file can be reused multiple times.  ^In other words, the
WAL can fill up with frames and then be checkpointed and then new
frames can overwrite the old ones.  ^A WAL always grows from beginning
toward the end.  Checksums and counters attached to each frame are
used to determine which frames within the WAL are valid and which
are leftovers from prior checkpoints.</p>

<p>The WAL header is 32 bytes in size and consists of the following eight
big-endian 32-bit unsigned integer values:</p>

................................................................................
<tr><td valign=top align=center>16<td valign=top align=center>4
    <td>Checksum-1:  Cumulative checksum up through and including this page
<tr><td valign=top align=center>20<td valign=top align=center>4
    <td>Checksum-2:  Second half of the cumulative checksum.
</table>
</center>

^(<p>A frame is considered valid if and only if the following conditions are
true:</p>

<ol>
<li><p>The salt-1 and salt-2 values in the frame-header match
       salt values in the wal-header</p></li>

<li><p>The checksum values in the final 8 bytes of the frame-header
       exactly match the checksum computed consecutively on the
       WAL header and the first 8 bytes and the content of all frames
       up to and including the current frame.</p></li></li>
</ol>)^

<tcl>hd_fragment walcksm {WAL checksum algorithm}</tcl>
<h3>4.2 Checksum Algorithm</h3>

<p>The checksum is computed by interpreting the input as
an even number of unsigned 32-bit integers: x(0) through x(N).
^The 32-bit integers are big-endian if the
magic number in the first 4 bytes of the WAL header is 0x377f0683 and
the integers are little-endian the magic number is 0x377f0682.
^The checksum values are always stored in the frame header in a
big-endian format regardless of which byte order is used to compute
the checksum.</p>

<p>The checksum algorithm only works for content which is a multiple of
8 bytes in length.  In other words, if the inputs are x(0) through x(N)
then N must be odd.
^(The checksum algorithm is as follows:

<blockquote><pre> 
s0 = s1 = 0
for i from 0 to n-1 step 2:
   s0 += x(i) + s1;
   s1 += x(i+1) + s0;
endfor
# result in s0 and s1
</pre></blockquote>)^

<p>The outputs s0 and s1 are both weighted checksums using fibonacci weights
in reverse order (the largest fibonacci weight occurs on the first element
of the sequence being summed.)  The s1 value spans all 32-bit integer
terms of the sequence whereas s0 omits the final term.</p>

<h3>4.3 Checkpoint Algorithm</h3>
................................................................................
Then valid content of the WAL is transferred into the database file.
Finally, the database is flushed to persistent storage using another
xSync method call.
The xSync operations serve as write barriers - all writes launched
before the xSync must complete before any write that launches after the
xSync begins.</p>

<p>^After each checkpoint, the WAL header salt-1 value is incremented and the 
salt-2 value is randomized.  This prevents old and new frames in the WAL from
being considered valid at the same time and being checkpointing together
following a crash.</p>

<tcl>hd_fragment walread {WAL read algorithm}</tcl>
<h3>4.4 Reader Algorithm</h3>

<p>^(To read a page from the database (call it page number P), a reader
first checks the WAL to see if it contains page P.  If so, then the
last valid instance of page P that is followed by a commit frame
or is a commit frame itself becomes the value read.)^  ^If the WAL
contains no copies of page P that are valid and which are a commit
frame or are followed by a commit frame, then page P is read from
the database file.</p>

<p>To start a read transaction, the reader records the index of the last
valid frame in the WAL.  The reader uses this recorded "mxFrame" value
for all subsequent read operations.  New transactions can be appended
to the WAL, but as long as the reader uses its original mxFrame value
and ignores subsequently appended content, the reader will see a 
consistent snapshot of the database from a single point in time.  
^This technique allows multiple concurrent readers to view different 
versions of the database content simultaneously.</p>

<p>The reader algorithm in the previous paragraphs works correctly, but 
because frames for page P can appear anywhere within the WAL, the
reader has to scan the entire WAL looking for page P frames.  If the
WAL is large (multiple megabytes is typical) that scan can be slow,
and read performance suffers.  ^To overcome this problem, a separate
data structure called the wal-index is maintained to expedite the
search for frames of a particular page.</p>

<tcl>hd_fragment walindexformat {wal-index} {WAL-index format}</tcl>
<h3>4.5 WAL-Index Format</h3>

<p>Conceptually, the wal-index is shared memory, though the current
................................................................................

<p>The <i>M</i> value in the previous paragraph is the "mxFrame" value
defined in [WAL read algorithm | section 4.4] that is read at the start 
of a transaction and which defines the maximum frame from the WAL that 
the reader will use.</p>

<p>The wal-index is transient.  After a crash, the wal-index is
reconstructed from the original WAL file.  ^The VFS is required
to either truncate or zero the header of the wal-index when the last
connection to it closes.  Because the wal-index is transient, it can
use an architecture-specific format; it does not have to be cross-platform.
Hence, unlike the database and WAL file formats which store all values
as big endian, the wal-index stores multi-byte values in the native
byte order of the host computer.</p>

<p>This document is concerned with the persist state of the database
file, and since the wal-index is a transient structure, no further 
information about the format of the wal-index will be provided here.
Complete details on the format of the wal-index are contained within
comments in SQLite source code.</p>