Documentation Source Text

Check-in [9949936e6e]
Login

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

Overview
Comment:Add a few interface requirements to btreemodule.html.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 9949936e6eb09e235887463cd6181ef94619ba58
User & Date: dan 2009-06-09 11:58:37.000
Context
2009-06-11
03:44
Add a diagram for delete operations. (check-in: dbcfaf4922 user: dan tags: trunk)
2009-06-09
11:58
Add a few interface requirements to btreemodule.html. (check-in: 9949936e6e user: dan tags: trunk)
00:52
Fill in a couple of missing details wrt balance_nonroot (balance-siblings). (check-in: 273d1c6fee user: dan tags: trunk)
Changes
Unified Diff Ignore Whitespace Patch
Changes to pages/btreemodule.in.
37
38
39
40
41
42
43






44
45
46
47
48
49
50

fancyformat_document "SQLite B-Tree Module" {hlr50000.txt llr50000.txt} {

  [h1 "Document Overview"]

  [h2 "Scope and Purpose"]







  <ul>
    <li><p> To make it easier to maintain, test and improve this critical
            sub-system of the SQLite software library.

    <li><p> To facilitate development of compatible backend modules that can 
            be used with other SQLite sub-systems, either for experimental or 
            production purposes.







>
>
>
>
>
>







37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

fancyformat_document "SQLite B-Tree Module" {hlr50000.txt llr50000.txt} {

  [h1 "Document Overview"]

  [h2 "Scope and Purpose"]

  <p>
    This document provides a description of the functionality of and public 
    interface offered by the SQLite b-tree module. It also, to a certain extent,
    describes the algorithm and implementation techniques used internally by
    the module. 

  <ul>
    <li><p> To make it easier to maintain, test and improve this critical
            sub-system of the SQLite software library.

    <li><p> To facilitate development of compatible backend modules that can 
            be used with other SQLite sub-systems, either for experimental or 
            production purposes.
731
732
733
734
735
736
737





738










739
740
741
742
743
744
745
                      sqlite3BtreePrevious sqlite3BtreeEof]

      [btree_api_defn sqlite3BtreeKeySize sqlite3BtreeKey sqlite3BtreeKeyFetch \
                      sqlite3BtreeDataFetch sqlite3BtreeDataSize sqlite3BtreeData]

      [btree_api_defn sqlite3BtreeCount]






      [btree_api_defn sqlite3BtreeMovetoUnpacked]











      <p class=todo>
	Not clear how to deal with these. Define an external module to
	encapsulate these and define sorting order etc.? That's tricky as things are
	because the UnpackedRecord.flags field defines the "search mode" used
        by sqlite3BtreeMovetoUnpacked.








>
>
>
>
>

>
>
>
>
>
>
>
>
>
>







737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
                      sqlite3BtreePrevious sqlite3BtreeEof]

      [btree_api_defn sqlite3BtreeKeySize sqlite3BtreeKey sqlite3BtreeKeyFetch \
                      sqlite3BtreeDataFetch sqlite3BtreeDataSize sqlite3BtreeData]

      [btree_api_defn sqlite3BtreeCount]

    [h3 sqlite3BtreeMovetoUnpacked]

      <p>
        The sqlite3BtreeMovetoUnpacked function is used to 

      [btree_api_defn sqlite3BtreeMovetoUnpacked]

      <p>
        The following requirements specify exactly how a b-tree cursor is to be moved
        by a successful call to sqlite3BtreeMovetoUnpacked.

      [fancyformat_import_requirement L50008]
      [fancyformat_import_requirement L50009]
      [fancyformat_import_requirement L50010]
      [fancyformat_import_requirement L50011]


      <p class=todo>
	Not clear how to deal with these. Define an external module to
	encapsulate these and define sorting order etc.? That's tricky as things are
	because the UnpackedRecord.flags field defines the "search mode" used
        by sqlite3BtreeMovetoUnpacked.

769
770
771
772
773
774
775
776


777


778
779






































780
781
782
783
784
785
786

      [btree_api_defn sqlite3BtreeCreateTable]

      [btree_api_defn BTREE_INTKEY BTREE_ZERODATA BTREE_LEAFDATA]

      [btree_api_defn sqlite3BtreeDropTable sqlite3BtreeClearTable sqlite3BtreeUpdateMeta]

      [btree_api_defn sqlite3BtreeDelete sqlite3BtreeInsert sqlite3BtreeCursorHasMoved sqlite3BtreePutData]





      [btree_api_defn sqlite3BtreeIncrVacuum]







































    [h2 "What do these do?"]

    <p class=todo>
      The following is used only from within VdbeExec() to check whether or not
      a cursor was opened on a table or index b-tree. Corruption tests can move into
      the b-tree layer.








|
>
>

>
>
|

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







790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849

      [btree_api_defn sqlite3BtreeCreateTable]

      [btree_api_defn BTREE_INTKEY BTREE_ZERODATA BTREE_LEAFDATA]

      [btree_api_defn sqlite3BtreeDropTable sqlite3BtreeClearTable sqlite3BtreeUpdateMeta]

      [btree_api_defn sqlite3BtreeDelete]
      [btree_api_defn sqlite3BtreeCursorHasMoved sqlite3BtreePutData]
      [btree_api_defn sqlite3BtreeIncrVacuum]

      [h3 sqlite3BtreeInsert]

        [btree_api_defn sqlite3BtreeInsert]

        [fancyformat_import_requirement L50001]

      <p class=todo>
        Or, if an entry with the specified key exists, it shall be replaced.

      <p class=todo>
        Malloc and IO error handling. Maybe these should be grouped together
        for a whole bunch of APIs. And hook into the above via a defintion of
        "successful call".

      <p>
        The requirement above implies that the results of passing anything else as 
        the first argument to sqlite3BtreeInsert, for example a read-only b-tree cursor,
        are undefined.

        [fancyformat_import_requirement L50002]
        [fancyformat_import_requirement L50003]
        [fancyformat_import_requirement L50004]

      <p>
        The following requirements describe the seventh and eighth paramaters passed
        to the sqlite3BtreeInsert function. Both of these are used to provide extra
        information used by sqlite3BtreeInsert to optimize the insert operation. They
        may be safely ignored by alternative b-tree implementations.

      <p class=todo>
        There should be some rationalization for these, eventually. Some tracebility
        from somewhere to show how the b-tree module offering these slightly esoteric
        interfaces is helpful to SQLite overall.

        [fancyformat_import_requirement L50005]
        [fancyformat_import_requirement L50006]

      <p>
        If a non-zero value is passed as the eighth parameter to sqlite3BtreeInsert 
        and the b-tree cursor has not been positioned as assumed by L50006, the
        results are undefined.

    [h2 "What do these do?"]

    <p class=todo>
      The following is used only from within VdbeExec() to check whether or not
      a cursor was opened on a table or index b-tree. Corruption tests can move into
      the b-tree layer.

826
827
828
829
830
831
832
833


834
835
836
837
838
839
840




841
842
843
844

845
846
847
848
849
850
851
    <li> sqlite3PagerBackupPtr
  </ul>
</ul>


  [h1 "Module Implementation"]

  [h2 "Database Image Traversal and Manipulation"]



     <p class=todo>
       This section should describe exactly how bits and bytes are shifted
       around when the database image is traversed and modified. i.e. how
       a cursor seek is implemented, how the b-tree balancing works, deleting
       an internal cell from an index b-tree etc.
   




    [h3 "B-Tree Insert"]
    [h3 "B-Tree Delete"]
    [h3 "B-Tree Balancing Algorithm"]



     <ul>
       <li><p>The <b>balance deeper</b> sub-algorithm is used when the root page of
           a b-tree is overfull. It creates a new page and copies the
           entire contents of the overfull root page to it. The root page
           is then zeroed and the new page installed as its only child.
           The balancing algorithm is then run on the new child page (in case







|
>
>



|
<
|
|
>
>
>
>
|
|
<

>







889
890
891
892
893
894
895
896
897
898
899
900
901
902

903
904
905
906
907
908
909
910

911
912
913
914
915
916
917
918
919
    <li> sqlite3PagerBackupPtr
  </ul>
</ul>


  [h1 "Module Implementation"]

  [h2 "Database Image Traversal"] 

  [h2 "Database Image Manipulation"]

     <p class=todo>
       This section should describe exactly how bits and bytes are shifted
       around when the database image is traversed and modified. i.e. how the b-tree 

       balancing works, deleting an internal cell from an index b-tree etc.

    [h3 "Creating a B-Tree Structure"]
    [h3 "Clearing a B-Tree Structure"]
    [h3 "Deleting a B-Tree Structure"]
   
    [h3 "B-Tree Insert/Replace Entry"]
    [h3 "B-Tree Delete Entry"]


    [h3 "B-Tree Balancing Algorithm"]

     <ul>
       <li><p>The <b>balance deeper</b> sub-algorithm is used when the root page of
           a b-tree is overfull. It creates a new page and copies the
           entire contents of the overfull root page to it. The root page
           is then zeroed and the new page installed as its only child.
           The balancing algorithm is then run on the new child page (in case
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
      </ol>

      [Figure btreemodule_balance_deeper.svg figure_balance_deeper "Example Balance Deeper Transform"]

    [h4 "Balance Shallower"]

      <ol>
        <li> Copy page data from child-page to root-page.
        <li> Fix pointer map entries associated with new root-page content.
        <li> Move child-page to database image free-list.
      </ol>

      [Figure btreemodule_balance_shallower.svg figure_balance_shallower "Example Balance Shallower Transform"]

    [h4 "Balance Quick"]







|







947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
      </ol>

      [Figure btreemodule_balance_deeper.svg figure_balance_deeper "Example Balance Deeper Transform"]

    [h4 "Balance Shallower"]

      <ol>
        <li> Copy node data from child-page to root-page.
        <li> Fix pointer map entries associated with new root-page content.
        <li> Move child-page to database image free-list.
      </ol>

      [Figure btreemodule_balance_shallower.svg figure_balance_shallower "Example Balance Shallower Transform"]

    [h4 "Balance Quick"]
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
        <li> Execute the balance procedure on the parent page.
      </ol>

      [Figure btreemodule_balance_quick.svg figure_balance_quick "Example Balance Quick Transform"]

    [h4 "Balance Siblings" balance_siblings]

      [fancyformat_import_requirement L50001]

    <p class=todo>
      The following description describes how balance() is to be implemented. This
      represents (I think) the lowest level of detail that should be in this document.
      One skilled in the art could use this description to reimplement SQLite's
      balance-siblings algorithm. We also need requirements at a higher level
      of detail in this section. Something to test!







|







980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
        <li> Execute the balance procedure on the parent page.
      </ol>

      [Figure btreemodule_balance_quick.svg figure_balance_quick "Example Balance Quick Transform"]

    [h4 "Balance Siblings" balance_siblings]

      [fancyformat_import_requirement L51001]

    <p class=todo>
      The following description describes how balance() is to be implemented. This
      represents (I think) the lowest level of detail that should be in this document.
      One skilled in the art could use this description to reimplement SQLite's
      balance-siblings algorithm. We also need requirements at a higher level
      of detail in this section. Something to test!
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079


1080
1081
1082
1083
1084
1085
1086
               has moved from one page to another the pointer-map entry associated with
               the cell's child page must be updated.
          <li> If the page being balanced is (was) not a leaf, then the pointer-map entry
               associated with each sibling's right-child page may need to be updated.
        </ol>
      </ol>

  [h3 "Page Allocation and Deallocation"]

     <p class=todo>
       Amongst other things, this section needs to explain our old pals the
       DontWrite() and DontRollback() optimizations.




  [h2 "Transactions and Savepoints"]

     <p class=todo>
       Requirements surrounding how transactions are made atomic and isolated.
       Also how savepoints are implemented. What happens to active cursors after







|




>
>







1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
               has moved from one page to another the pointer-map entry associated with
               the cell's child page must be updated.
          <li> If the page being balanced is (was) not a leaf, then the pointer-map entry
               associated with each sibling's right-child page may need to be updated.
        </ol>
      </ol>

    [h3 "Page Allocation and Deallocation"]

     <p class=todo>
       Amongst other things, this section needs to explain our old pals the
       DontWrite() and DontRollback() optimizations.




  [h2 "Transactions and Savepoints"]

     <p class=todo>
       Requirements surrounding how transactions are made atomic and isolated.
       Also how savepoints are implemented. What happens to active cursors after
Changes to pages/fancyformat.tcl.
146
147
148
149
150
151
152



153
154
155
156
157
158
159

160
161
162







163
164
165
166
167
168
169
}
proc fancyformat_import_requirement {reqid} {
  lappend ::Requirements $reqid
  set ret "<p class=req id=$reqid><span>[lindex $::ffreq($reqid) 1]</span>"
  if {[llength [lindex $::ffreq($reqid) 0]]} {
    append ret " (P: [lindex $::ffreq($reqid) 0])"
  } 



  append ret "</p>"
}

set ::Requirements [list]

proc fancyformat_document {zTitle lReqfile zBody} {
  unset -nocomplain ::ffreq

  foreach f $lReqfile {
    hd_read_requirement_file $::DOC/req/$f ::ffreq
  }







  set body [subst -novariables $zBody]
  hd_puts [subst {
    <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
    <html>
    <head>
    <link type="text/css" rel="stylesheet" href="images/fileformat/rtdocs.css">
    </head>







>
>
>







>



>
>
>
>
>
>
>







146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
}
proc fancyformat_import_requirement {reqid} {
  lappend ::Requirements $reqid
  set ret "<p class=req id=$reqid><span>[lindex $::ffreq($reqid) 1]</span>"
  if {[llength [lindex $::ffreq($reqid) 0]]} {
    append ret " (P: [lindex $::ffreq($reqid) 0])"
  } 
  if {[info exists ::ffreq_children($reqid)]} {
    append ret " (C: $::ffreq_children($reqid))"
  } 
  append ret "</p>"
}

set ::Requirements [list]

proc fancyformat_document {zTitle lReqfile zBody} {
  unset -nocomplain ::ffreq
  unset -nocomplain ::ffreq_children
  foreach f $lReqfile {
    hd_read_requirement_file $::DOC/req/$f ::ffreq
  }
  foreach req [array names ::ffreq] {
    foreach parent [lindex $::ffreq($req) 0] {
      lappend ::ffreq_children($parent) $req
    }
  }


  set body [subst -novariables $zBody]
  hd_puts [subst {
    <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
    <html>
    <head>
    <link type="text/css" rel="stylesheet" href="images/fileformat/rtdocs.css">
    </head>
Changes to req/llr50000.txt.



























1

















































2
3
4
5
6
7
8
9
10
11



























HLR L50001

















































The balance-siblings algorithm shall redistribute the b-tree cells currently 
stored on a overfull or underfull page and up to two sibling pages, adding
or removing siblings as required, such that no sibling page is overfull and
the minimum possible number of sibling pages is used to store the 
redistributed b-tree cells.


HLR L50002 L50001
The new pages 

>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>






<
<
<
<
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83





HLR L50001  H50128
A successful call to the sqlite3BtreeInsert function made with a read/write
b-tree cursor passed as the first argument shall insert a new entry into the
b-tree structure the b-tree cursor is open on.

HLR L50002  H50128
If the b-tree cursor passed to sqlite3BtreeInsert as the first argument is
open on a table b-tree, then the values passed as the second parameter (pKey) 
shall be ignored. The value passed as the third parameter (nKey) shall be
used as the integer key for the new entry.

HLR L50003  H50128
If the b-tree cursor passed to sqlite3BtreeInsert as the first argument is
open on a table b-tree, then the database record associated with the new entry
shall consist of a copy of the first nData bytes of the buffer pointed to by pData 
followed by nZero zero (0x00) bytes, where pData, nData and nZero are the
fourth, fifth and sixth parameters passed to sqlite3BtreeInsert, respectively.

HLR L50004  H50128
If the b-tree cursor passed to sqlite3BtreeInsert as the first argument is
open on an index b-tree, then the values passed as the fourth, fifth and sixth
parameters shall be ignored. The key (a database record) used by the new entry 
shall consist of the first nKey bytes of the buffer pointed to by pKey, where
pKey and nKey are the second and third parameters passed to sqlite3BtreeInsert,
respectively.

HLR L50005
If the value passed as the seventh parameter to a call to sqlite3BtreeInsert
is non-zero, sqlite3BtreeInsert shall interpret this to mean that it is likely
(but not certain) that the key belonging to the new entry is larger than the
largest key currently stored in the b-tree structure, and optimize accordingly.

HLR L50006
If the value passed as the eighth parameter to a call to sqlite3BtreeInsert
is non-zero, then the B-Tree module shall interpret this to mean that the
the b-tree cursor has already been positioned by a successful call to 
sqlite3BtreeMovetoUnpacked specifying the same key value as is being inserted,
and that sqlite3BtreeMovetoUnpacked has set the output value required by L50011 to
this value.



HLR L50008
If a call is made to sqlite3BtreeMovetoUnpacked specifying a key value for 
which there exists an entry with a matching key value in the b-tree structure,
the b-tree cursor shall be moved to point to this entry. In this case *pRes
(the value of the "int" variable pointed to by the pointer passed as the
fifth parameter to sqlite3BtreeMovetoUnpacked) shall be set to 0 before
returning.

HLR L50009
If a call is made to sqlite3BtreeMovetoUnpacked specifying a key value for
which there does not exist an entry with a matching key value in the b-tree
structure, the b-tree cursor shall be moved to point to an entry located
on the leaf page that would contain the requested entry, were it present.

HLR L50010
If the condition specified in L50009 is met and the b-tree structure 
contains one or more entries (is not empty), the b-tree cursor shall be left
pointing to an entry that would lie adjacent (immediately before or after in
order by key) to the requested entry on the leaf page, were it present.

HLR L50011
If the condition specified in L50009 is met and the b-tree cursor is left
pointing to an entry with a smaller key than that requested, or the cursor
is left pointing a no entry at all because the b-tree structure is completely
empty, *pRes (the value of the "int" variable pointed to by the pointer passed
as the fifth parameter to sqlite3BtreeMovetoUnpacked) shall be set to -1.
Otherwise, if the b-tree cursor is left pointing to an entry with a larger key
than that requested, *pRes shall be set to 1.





HLR L51001
The balance-siblings algorithm shall redistribute the b-tree cells currently 
stored on a overfull or underfull page and up to two sibling pages, adding
or removing siblings as required, such that no sibling page is overfull and
the minimum possible number of sibling pages is used to store the 
redistributed b-tree cells.