Documentation Source Text

Check-in [7ee2137b43]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Fix typos in the fileformat2.html document.
Timelines: family | ancestors | descendants | both | branch-3.10
Files: files | file ages | folders
SHA1: 7ee2137b43fc2ea563ce67888314ddfd79eb5036
User & Date: drh 2016-02-10 03:47:49
Context
2016-02-10
13:38
Add the snapshot tarball to the list of possible download files. check-in: 6af983fad9 user: drh tags: branch-3.10
03:48
Merge typo fixes from the 3.10 branch. check-in: f26e661484 user: drh tags: trunk
03:47
Fix typos in the fileformat2.html document. check-in: 7ee2137b43 user: drh tags: branch-3.10
2016-02-02
01:56
Add a mention of sqlite3_column() to the SQLITE_RANGE documentation. check-in: 2111e3600c user: drh tags: branch-3.10
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to pages/fileformat2.in.

496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
...
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
...
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
...
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
...
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
...
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
....
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
....
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
....
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
....
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
....
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
that consists of a single page that is both a leaf and the root.
Because there are pointers from parents to children, every page of a
complete b-tree can be located if only the root page is known.  Hence,
b-trees are identified by their root page number.</p>

<p>A b-tree page is either a table b-tree page or an index b-tree page.
All pages within each complete b-tree are of the same type: either table
or index.  There is a one table b-trees in the database file
for each rowid table in the database schema, including system tables
such as sqlite_master.  There is one index b-trees
in the database file for each index in the schema, including implied indexes
created by uniqueness constraints.  There are no b-trees associated with
[virtual tables].  Specific virtual table implementations might make use
of [shadow tables] for storage, but those shadow tables will have separate
entries in the database schema.  [WITHOUT ROWID] tables use index b-trees
rather than a table b-trees, so there is one
index b-tree in the database file for each [WITHOUT ROWID] table.
................................................................................

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

<p>A variable-length integer or "varint" is a static Huffman encoding
of 64-bit twos-complement integers that uses less space for small positive 
values. 
A varint is between 1 and 9 bytes in length.  The varint consists of either
zero or more byte which have the high-order bit set followed by a single byte
with the high-order bit clear, or nine bytes, whichever is shorter.
The lower seven bits of each of the first eight bytes and all 8 bits of
the ninth byte are used to reconstruct the 64-bit twos-complement integer.
Varints are big-endian: bits taken from the earlier byte of the varint
are the more significant than bits taken from the later bytes. </p>

<p>The format of a cell depends on which kind of b-tree page the cell
................................................................................
pages.
<li>A 4-byte big-endian integer page number for the first page of the
overflow page list - omitted if all payload fits on the b-tree page.
</ul></p></dd>

<dt><p>Index B-Tree Interior Cell (header 0x02):</p></dt>
<dd><p><ul>
<li>A 4-byte big-endianpage number which is the left child pointer.
<li>A varint which is the total number of bytes of key payload, including any
overflow
<li>The initial portion of the payload that does not spill to overflow
pages.
<li>A 4-byte big-endian integer page number for the first page of the
overflow page list - omitted if all payload fits on the b-tree page.
</ul></p></dd>
................................................................................

<blockquote><dl>
<dt>Table B-Tree Leaf Cell:</dt>
<dd><p>
^If the payload size P is less than or equal to U-35 then
the entire payload is stored on the b-tree leaf 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 leaf page is the smaller of
M+((P-M)%(U-4)) and U-35.)^
^(Note that number of bytes stored on the leaf page is never less than M.)^
</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
................................................................................
</p></dd>

<dt>Index B-Tree Leaf Or Interior Cell:</dt>
<dd><p>
^(Let X be ((U-12)*64/255)-23).  If the payload size P is less than
or equal to X then the entire payload is stored on the b-tree page.)^
^(Let M be ((U-12)*32/255)-23.  If P is greater than X then the number
of byte stored on the b-tree page is the smaller of
M+((P-M)%(U-4)) and X.)^
^(Note that number of bytes stored on the index page is never less than M.)^
</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
................................................................................
<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>
................................................................................
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
................................................................................
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 
................................................................................

<ul>
<li><p>Indices with names of the form "sqlite_autoindex_TABLE_N" that
       are used to implement [UNIQUE] and [PRIMARY KEY] constraints on
       ordinary tables.

<li><p>A table with the name "sqlite_sequence" that is used to keep track
       of the maximum historical [INTEGER PRIMARY KEY] for a table that
       using [AUTOINCREMENT].

<li><p>Tables with names of the form "sqlite_statN" where N is an integer.
       Such tables store database statistics gathered by the [ANALYZE]
       command and used by the query planner to help determine the best
       algorithm to use for each query.
</ul>
................................................................................
that contain between 10 and 40 samples that are distributed across
the key space and with large nEq values.

<p>^(In a well-formed sqlite_stat3 table, the samples for any single
index must appear in the same order that they occur in the index.  
In other words, if the entry with left-most column S1 is earlier in
the index b-tree than the
entry with lef-most column S2, then in the sqlite_stat3 table, 
sample S1 must have a smaller rowid than sample S2.)^

<tcl>hd_fragment stat4tab {sqlite_stat4} SQLITE_STAT4</tcl>
<h4>2.6.6 The sqlite_stat4 table</h4>

<p>The sqlite_stat4 is only created and is only used if SQLite is compiled
with [SQLITE_ENABLE_STAT4] and if the SQLite version number is
................................................................................
    <td>^(The sqlite_stat4.nLt column holds a list of N integers where
    the K-th integer is the approximate number of entries in the
    index whose K left-most columns are collectively less than the 
    K left-most columns of the sample.)^

<tr><td valign="top" align="right">nDLt:</td>
    <td>^(The sqlite_stat4.nDLt column holds a list of N integers where
    the K-th integers is the approximate
    number of entries in the index that are distinct in the first K columns and
    that are whose left-most K columns are collectively less than the left-most
    K columns of the sample.)^
</table>
</center>

<p>The sqlite_stat4 is a generalization of the sqlite_stat3 table.  The
sqlite_stat3 table provides information about the left-most column of an
index whereas the sqlite_stat4 table provides information about all columns







|

|







 







|







 







|







 







|







 







|







 







|







 







|







 







|







 







|







 







|







 







|

|







496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
...
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
...
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
...
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
...
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
...
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
....
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
....
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
....
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
....
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
....
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
that consists of a single page that is both a leaf and the root.
Because there are pointers from parents to children, every page of a
complete b-tree can be located if only the root page is known.  Hence,
b-trees are identified by their root page number.</p>

<p>A b-tree page is either a table b-tree page or an index b-tree page.
All pages within each complete b-tree are of the same type: either table
or index.  There is one table b-trees in the database file
for each rowid table in the database schema, including system tables
such as sqlite_master.  There is one index b-tree
in the database file for each index in the schema, including implied indexes
created by uniqueness constraints.  There are no b-trees associated with
[virtual tables].  Specific virtual table implementations might make use
of [shadow tables] for storage, but those shadow tables will have separate
entries in the database schema.  [WITHOUT ROWID] tables use index b-trees
rather than a table b-trees, so there is one
index b-tree in the database file for each [WITHOUT ROWID] table.
................................................................................

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

<p>A variable-length integer or "varint" is a static Huffman encoding
of 64-bit twos-complement integers that uses less space for small positive 
values. 
A varint is between 1 and 9 bytes in length.  The varint consists of either
zero or more bytes which have the high-order bit set followed by a single byte
with the high-order bit clear, or nine bytes, whichever is shorter.
The lower seven bits of each of the first eight bytes and all 8 bits of
the ninth byte are used to reconstruct the 64-bit twos-complement integer.
Varints are big-endian: bits taken from the earlier byte of the varint
are the more significant than bits taken from the later bytes. </p>

<p>The format of a cell depends on which kind of b-tree page the cell
................................................................................
pages.
<li>A 4-byte big-endian integer page number for the first page of the
overflow page list - omitted if all payload fits on the b-tree page.
</ul></p></dd>

<dt><p>Index B-Tree Interior Cell (header 0x02):</p></dt>
<dd><p><ul>
<li>A 4-byte big-endian page number which is the left child pointer.
<li>A varint which is the total number of bytes of key payload, including any
overflow
<li>The initial portion of the payload that does not spill to overflow
pages.
<li>A 4-byte big-endian integer page number for the first page of the
overflow page list - omitted if all payload fits on the b-tree page.
</ul></p></dd>
................................................................................

<blockquote><dl>
<dt>Table B-Tree Leaf Cell:</dt>
<dd><p>
^If the payload size P is less than or equal to U-35 then
the entire payload is stored on the b-tree leaf page.  
^(Let M be ((U-12)*32/255)-23.  If P is greater than U-35
then the number of bytes stored on the b-tree leaf page is the smaller of
M+((P-M)%(U-4)) and U-35.)^
^(Note that number of bytes stored on the leaf page is never less than M.)^
</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
................................................................................
</p></dd>

<dt>Index B-Tree Leaf Or Interior Cell:</dt>
<dd><p>
^(Let X be ((U-12)*64/255)-23).  If the payload size P is less than
or equal to X then the entire payload is stored on the b-tree page.)^
^(Let M be ((U-12)*32/255)-23.  If P is greater than X then the number
of bytes stored on the b-tree page is the smaller of
M+((P-M)%(U-4)) and X.)^
^(Note that number of bytes stored on the index page is never less than M.)^
</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
................................................................................
<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 the 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>
................................................................................
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 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
................................................................................
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 recreate 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 
................................................................................

<ul>
<li><p>Indices with names of the form "sqlite_autoindex_TABLE_N" that
       are used to implement [UNIQUE] and [PRIMARY KEY] constraints on
       ordinary tables.

<li><p>A table with the name "sqlite_sequence" that is used to keep track
       of the maximum historical [INTEGER PRIMARY KEY] for a table
       using [AUTOINCREMENT].

<li><p>Tables with names of the form "sqlite_statN" where N is an integer.
       Such tables store database statistics gathered by the [ANALYZE]
       command and used by the query planner to help determine the best
       algorithm to use for each query.
</ul>
................................................................................
that contain between 10 and 40 samples that are distributed across
the key space and with large nEq values.

<p>^(In a well-formed sqlite_stat3 table, the samples for any single
index must appear in the same order that they occur in the index.  
In other words, if the entry with left-most column S1 is earlier in
the index b-tree than the
entry with left-most column S2, then in the sqlite_stat3 table, 
sample S1 must have a smaller rowid than sample S2.)^

<tcl>hd_fragment stat4tab {sqlite_stat4} SQLITE_STAT4</tcl>
<h4>2.6.6 The sqlite_stat4 table</h4>

<p>The sqlite_stat4 is only created and is only used if SQLite is compiled
with [SQLITE_ENABLE_STAT4] and if the SQLite version number is
................................................................................
    <td>^(The sqlite_stat4.nLt column holds a list of N integers where
    the K-th integer is the approximate number of entries in the
    index whose K left-most columns are collectively less than the 
    K left-most columns of the sample.)^

<tr><td valign="top" align="right">nDLt:</td>
    <td>^(The sqlite_stat4.nDLt column holds a list of N integers where
    the K-th integer is the approximate
    number of entries in the index that are distinct in the first K columns and
    where the left-most K columns are collectively less than the left-most
    K columns of the sample.)^
</table>
</center>

<p>The sqlite_stat4 is a generalization of the sqlite_stat3 table.  The
sqlite_stat3 table provides information about the left-most column of an
index whereas the sqlite_stat4 table provides information about all columns