Documentation Source Text

Check-in [9ec8b470d5]
Login

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

Overview
Comment:Correct and clarify the computation of local and overflow payload sizes in the file format documentation.
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 9ec8b470d5a5d6dc16b2d55166b892f4061dbb9b
User & Date: drh 2016-03-08 17:23:11
Context
2016-03-09
15:56
Updates to the change log for 3.12.0. check-in: 92353888aa user: drh tags: trunk
2016-03-08
17:23
Correct and clarify the computation of local and overflow payload sizes in the file format documentation. check-in: 9ec8b470d5 user: drh tags: trunk
16:42
Update documentation for SQLITE_DEFAULT_SYNCHRONOUS and related changes. check-in: ab3cf23c74 user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to pages/fileformat2.in.

745
746
747
748
749
750
751
752




753
754
755
756
757
758

759
760
761

762
763
764
765
766
767
768
769
770
771
772
773
774

775
776
777

778
779
780















781
782
783
784
785
786
787


<tr><td align=center valign=top>

<p>The amount of payload that spills onto overflow pages also depends on
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 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
any payload to spill.
</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
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 changed







|
>
>
>
>




|
|
>
|
|
<
>













>
|
|
<
>



>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765

766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782

783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808


<tr><td align=center valign=top>

<p>The amount of payload that spills onto overflow pages also depends on
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.  In the following,
symbol X represents the maximum amount of payload that can be stored directly
on the b-tree page without spilling onto an overflow page and symbol M
represents the minimum amount of payload that must be stored on the btree
page before spilling is allowed.</p>

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

if K is less or equal to X or M otherwise.)^
^(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
any payload to spill.
</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 and let K be M+((P-M)%(U-4)).
If P is greater than X then the number
of bytes stored on the index b-tree page is K if K is less than or

equal to X or M otherwise.)^
^(Note that number of bytes stored on the index page is never less than M.)^
</p></dd>
</dl></blockquote>

<p>Here is an alternative description of the same computation:

<ul>
<li>X is U-35 for table btree leaf pages or
    ((U-12)*64/255)-23 for index pages.
<li>M is always ((U-12)*32/255)-23.
<li>Let K be M+((P-M)%(U-4)).
<li>^If P<=X then all P bytes of payload are stored directly on the 
    btree page without overflow.
<li>^If P>X and K<=X then the first K bytes of P are stored on the 
    btree page and the remaining P-K bytes are stored on overflow pages.
<li>^If P>X and K>X then the first M bytes of P are stored on the
    btree page and the remaining P-M bytes are stored on overflow pages.
</ul>

<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 changed