Documentation Source Text: Check-in [712d82fbd7]

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

Overview

Comment:	Updates to fileformat.html.
Timelines:	family \| ancestors \| descendants \| both \| trunk
Files:	files \| file ages \| folders
SHA1:	712d82fbd7e044730695f55a289a32c084dd3c83
User & Date:	dan 2009-04-27 11:59:29

Context

2009-04-27
18:20		Further updates to fileformat.html. check-in: 47c1a4a97e user: dan tags: trunk
11:59		Updates to fileformat.html. check-in: 712d82fbd7 user: dan tags: trunk
2009-04-21
16:14		Added a new FAQ to explain how the syntax diagrams are created. check-in: 74c109fae7 user: drh tags: trunk

Changes

Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to pages/fileformat.in.

      journal file and the rules for correctly reading a database image from
      the combination of a database file and journal file. The same section
      also includes guidelines and requirements describing the intended method
      for atomically updating the database image within the file-system without
      risking database corruption.

    <p>
      <b>Section <cite>locking_protocol</cite></b> contains a description of
      and software requirements related to:

    <ul>
      <li>The locking protocol used by SQLite to manage read and write access
          to the database and journal files within the file-system, and
      <li>the change-counter and schema-cookie protocols that must be followed
          by all database writers to facilitate the implementation of
................................................................................
      is required to interpret or create SQLite database images may be found
      in section <cite>database_file_format</cite>. Requirements and guidelines
      for software required to safely read and write database images to disk
      using an SQLite compatible system failure recovery mechanism to prevent
      database corruption or data loss are found in section 
      <cite>file_system_usage</cite>. Finally, rules and requirements for software 
      systems required to read and write live SQLite databases within a system that
      includes real SQLite clients that may also read and write to databases
      are presented in section <cite>locking_protocol</cite>.

  [h2 "Glossary"]
    <table id=glossary>
      <tr><td>Auto-vacuum last root-page<td>
        A page number stored as 32-bit integer at byte offset 52 of the
        database file header (see section <cite>file_header</cite>). In
        an auto-vacuum database, this is the numerically largest 
................................................................................
h1 "SQLite Database Files" sqlite_database_files
 
  <p>
    The bulk of this document, section <cite>database_file_format</cite>,
    contains the definition of a <i>well-formed SQLite database file</i>.
    SQLite is required to create database files that meet this definition.

  <p class=req id=H30010>
          [fileformat_import_requirement H30010]

  <p>
    Additionally, the database file should contain a serialized version
    of the logical database produced by the transaction. For all but the
    most trivial logical databases, there are many possible serial 
    representations.

  <p class=req id=H30020>
          [fileformat_import_requirement H30020]
-->

<!--
  <p>
    Section <cite>database_file_manipulation</cite> contains requirements
    describing in more detail the way in which SQLite manipulates the
    fields and data structures described in section
................................................................................
        Some of the following requirements state that certain database header
        fields must contain defined constant values, even though the sqlite 
        database file format is designed to allow various values. This is
        done to artificially constrain the definition of a 
        <i>well-formed database</i> in order to make implementation and 
        testing more practical.

      <p class=req id=H30030>
          [fileformat_import_requirement H30030]

      <p>
        Following the 16 byte magic string in the file header is the
        <i>page size</i>, a 2-byte field. See section
        <cite>pages_and_page_types</cite> for details.

      <p class=req id=H30040>
          [fileformat_import_requirement H30040]
      <p class=req id=H30050>
          [fileformat_import_requirement H30050]

      <p class=req id=H30060>
          [fileformat_import_requirement H30060]

      <p class=req id=H30070>
          [fileformat_import_requirement H30070]
      <p class=req id=H30080>
          [fileformat_import_requirement H30080]
      <p class=req id=H30090>
          [fileformat_import_requirement H30090]
      <p class=req id=H30100>
          [fileformat_import_requirement H30100]

      <p>
        Following the <i>file change counter</i> in the database header are
        two 4-byte fields related to the database file <i>free page list</i>.
        See section <cite>free_page_list</cite> for details.

      <p class=req id=H30110>
          [fileformat_import_requirement H30110]

      <p class=req id=H30120>
          [fileformat_import_requirement H30120]

      <p class=req id=H30130>
          [fileformat_import_requirement H30130]

      <p class=req id=H30140>
          [fileformat_import_requirement H30140]

      <p class=req id=H30150>
          [fileformat_import_requirement H30150]

      <p class=req id=H30160>
          [fileformat_import_requirement H30160]

      <p class=req id=H30170>
          [fileformat_import_requirement H30170]

      <p class=req id=H30180>
          [fileformat_import_requirement H30180]

    [h3 "Pages and Page Types" "pages_and_page_types"]
      <p>
        The entire database file is divided into pages, each page consisting
        of <i>page-size</i> bytes, where <i>page-size</i> is the 2-byte 
        integer value stored at offset 16 of the file header (see above).
        The <i>page-size</i> is always a power of two between 512 
................................................................................
            permanently designated "pointer-map" pages. See section 
            <cite>pointer_map_pages</cite> for details.
        <li><b>The locking page</b>. The database page that starts at
            byte offset 2<sup>30</sup>, if it is large enough to contain
            such a page, is always left unused.
      </ul>

      <p class=req id=H30190>
          [fileformat_import_requirement H30190]
      <p class=req id=H30200>
          [fileformat_import_requirement H30200]
      <p class=req id=H30210>
          [fileformat_import_requirement H30210]
      <p class=req id=H30220>
          [fileformat_import_requirement H30220]
        

    [h3 "The Schema Table" schema_table]
      <p>
        Apart from being the page that contains the file-header, page 1 of
        the database file is special because it is the root page of the
        B-Tree structure that contains the schema table data. From the SQL
................................................................................
        [Tr]<td>index <td>i1 <td>abc <td>3 <td>CREATE INDEX i1 ON abc(b, c)
        [Tr]<td>table <td>def <td>def <td>4 <td>CREATE TABLE def(a PRIMARY KEY, b, c, UNIQUE(b, c))
        [Tr]<td>index <td>sqlite_autoindex_def_1 <td>def <td>5 <td>
        [Tr]<td>index <td>sqlite_autoindex_def_2 <td>def <td>6 <td>
        [Tr]<td>view <td>v1 <td>v1 <td>0 <td>CREATE VIEW v1 AS SELECT * FROM abc
      </table>

      <p class=req id=H30230>
          [fileformat_import_requirement H30230]
      <p class=req id=H30240>
          [fileformat_import_requirement H30240]

      <p>The following requirements describe "table" records.

      <p class=req id=H30250>
          [fileformat_import_requirement H30250]

      <p class=req id=H30260>
          [fileformat_import_requirement H30260]

      <p class=req id=H30270>
          [fileformat_import_requirement H30270]

      <p class=req id=H30280>
          [fileformat_import_requirement H30280]

      <p class=req id=H30290>
          [fileformat_import_requirement H30290]

      <p class=req id=H30300>
          [fileformat_import_requirement H30300]

      <p class=req id=H30310>
          [fileformat_import_requirement H30310]

      <p>The following requirements describe "implicit index" records.

      <p class=req id=H30320>
          [fileformat_import_requirement H30320]

      <p class=req id=H30330>
          [fileformat_import_requirement H30330]
      <p class=req id=H30340>
          [fileformat_import_requirement H30340]
      <p class=req id=H30350>
          [fileformat_import_requirement H30350]

      <p>The following requirements describe "explicit index" records.

      <p class=req id=H30360>
          [fileformat_import_requirement H30360]
      <p class=req id=H30370>
          [fileformat_import_requirement H30370]
      <p class=req id=H30380>
          [fileformat_import_requirement H30380]
      <p class=req id=H30390>
          [fileformat_import_requirement H30390]

      <p>The following requirements describe "view" records.

      <p class=req id=H30400>
          [fileformat_import_requirement H30400]

      <p class=req id=H30410>
          [fileformat_import_requirement H30410]

      <p class=req id=H30420>
          [fileformat_import_requirement H30420]

      <p class=req id=H30430>
          [fileformat_import_requirement H30430]

      <p>The following requirements describe "trigger" records.

      <p class=req id=H30440>
          [fileformat_import_requirement H30440]

      <p class=req id=H30450>
          [fileformat_import_requirement H30450]

      <p class=req id=H30460>
          [fileformat_import_requirement H30460]

      <p class=req id=H30470>
          [fileformat_import_requirement H30470]

      <p>The following requirements describe the placement of B-Tree root 
         pages in auto-vacuum databases.

      <p class=req id=H30480>
          [fileformat_import_requirement H30480]

      <p class=req id=H30490>
          [fileformat_import_requirement H30490]


 
  [h2 "B-Tree Structures" "btree_structures"]
    <p>
      A large part of any SQLite database file is given over to one or more
      B-Tree structures. A single B-Tree structure is stored using one or more
      database pages. Each page contains a single B-Tree node.
................................................................................
          B-Tree structures are described in detail in section 
          <cite>table_btrees</cite>.
      <li>The <b>index B-Tree</b>, which uses database records as keys. Index
          B-Tree structures are described in detail in section 
          <cite>index_btrees</cite>.
    </ul>

    <p class=req id=H30500>
          [fileformat_import_requirement H30500]
    <p class=req id=H30510>
          [fileformat_import_requirement H30510]

    [h3 "Variable Length Integer Format" "varint_format"]
      <p>
        In several parts of the B-Tree structure, 64-bit twos-complement signed
        integer values are stored in the "variable length integer format"
        described here.
      <p>
................................................................................
        [Tr]<td>200815 <td>0x000000000003106F <td>0x8C 0xA0 0x6F
        [Tr]<td>-1     <td>0xFFFFFFFFFFFFFFFF 
            <td>0xFF 0xFF 0xFF 0xFF 0xFF 0xFF 0xFF 0xFF 0xFF
        [Tr]<td>-78056 <td>0xFFFFFFFFFFFECD56
            <td>0xFF 0xFF 0xFF 0xFF 0xFF 0xFF 0xFD 0xCD 0x56
      </table>

    <p class=req id=H30520>
          [fileformat_import_requirement H30520]

    <p class=req id=H30530>
          [fileformat_import_requirement H30530]

    <p class=req id=H30540>
          [fileformat_import_requirement H30540]

    <p class=req id=H30550>
          [fileformat_import_requirement H30550]
      

    [h3 "Database Record Format" "record_format"]
      <p>
        A database record is a blob of data that represents an ordered
        list of one or more SQL values. Database records are used in two
        places in SQLite database files - as the associated data for entries
................................................................................
        the length of the data field is as described in the table above.
      <p>
        The data field associated with a string value contains the string
        encoded using the database encoding, as defined in the database
        file header (see section <cite>file_header</cite>). No 
        nul-terminator character is stored in the database.

      <p class=req id=H30560>
          [fileformat_import_requirement H30560]

      <p class=req id=H30570>
          [fileformat_import_requirement H30570]

      <p class=req id=H30580>
          [fileformat_import_requirement H30580]

      <p class=req id=H30590>
          [fileformat_import_requirement H30590]

      <p class=req id=H30600>
          [fileformat_import_requirement H30600]
      <p class=req id=H30610>
          [fileformat_import_requirement H30610]
      <p class=req id=H30620>
          [fileformat_import_requirement H30620]
      <p class=req id=H30630>
          [fileformat_import_requirement H30630]
      <p class=req id=H30640>
          [fileformat_import_requirement H30640]
      <p class=req id=H30650>
          [fileformat_import_requirement H30650]

      <p class=req id=H30660>
          [fileformat_import_requirement H30660]

      <p class=req id=H30670>
          [fileformat_import_requirement H30670]

      <p class=req id=H30680>
          [fileformat_import_requirement H30680]

      <p class=req id=H30690>
          [fileformat_import_requirement H30690]

      <p class=req id=H30700>
          [fileformat_import_requirement H30700]

      <p>
        The following database file properties define restrictions on the 
        integer values that may be stored within a 
        <i>database record header</i>.

      <p class=req id=H30710>
          [fileformat_import_requirement H30710]
      <p class=req id=H30720>
          [fileformat_import_requirement H30720]

    [h3 "Index B-Trees" index_btrees]
      <p>
        As specified in section <cite>fileformat_overview</cite>, index 
        B-Tree structures store a unique set of the database records described
        in the previous section. While in some cases, when there are very
        few entries in the B-Tree, the entire structure may fit on a single
................................................................................
        Figure <cite>figure_indextree</cite> depicts one possible record
        distribution for an index B-Tree containing records R1 to R26, assuming
        that for all values of N, <i>R(N+1)&gt;R(N)</i>. In total the B-Tree
        structure uses 11 database file pages. Internal tree nodes contain
        database records and references to child node pages. Leaf nodes contain
        database records only.

      <p class=req id=H30730>
          [fileformat_import_requirement H30730]

      <p class=req id=H30740>
          [fileformat_import_requirement H30740]

      <p class=req id=H30750>
          [fileformat_import_requirement H30750]

      <p class=req id=H30760>
          [fileformat_import_requirement H30760]

      <p>
        The precise way in which index B-Tree pages and cells are formatted is
        described in subsequent sections.


        [h4 "Index B-Tree Content"]
................................................................................
          <p>
            An index B-Tree contains an entry for each row in its associated
            database table. The fields of the record used as the index B-Tree
            key are copies of each of the indexed columns of the associated 
            database row, in order, followed by the rowid value of the same 
            row. See figure <cite>figure_examplepop</cite> for an example.

        <p class=req id=H30770>
          [fileformat_import_requirement H30770]

        <p class=req id=H30780>
          [fileformat_import_requirement H30780]

        <p class=req id=H30790>
          [fileformat_import_requirement H30790]

        <p class=req id=H30800>
          [fileformat_import_requirement H30800]
 
      [h4 "Record Sort Order" "index_btree_compare_func"]
        <p>
          This section defines the comparison function used when database
          records are used as B-Tree keys for index B-Trees. The comparison
          function is only defined when both database records contain the same
          number of fields.
................................................................................
            the page) of the next block in the list stored as a big-endian
            unsigned integer. The first two bytes of the final block in the 
            list are set to zero. The third and fourth bytes of each free
            block contain the total size of the free block in bytes, stored
            as a 2 byte big-endian unsigned integer.
      </ul>

      <p class=req id=H30810>
          [fileformat_import_requirement H30810]
      <p class=req id=H30820>
          [fileformat_import_requirement H30820]

      <p>
        The following requirements describe the <i>B-Tree page header</i>
        present at the start of both index and table B-Tree pages.

      <p class=req id=H30830>
          [fileformat_import_requirement H30830]

      <p class=req id=H30840>
          [fileformat_import_requirement H30840]

      <p class=req id=H30850>
          [fileformat_import_requirement H30850]

      <p class=req id=H30860>
          [fileformat_import_requirement H30860]

      <p>
        This requirement describes the cell content offset array. It applies
        to both B-Tree variants.

      <p class=req id=H30870>
          [fileformat_import_requirement H30870]

      <p class=req id=H30880>
          [fileformat_import_requirement H30880]

      <p class=req id=H30890>
          [fileformat_import_requirement H30890]

      <p class=req id=H30900>
          [fileformat_import_requirement H30900]

      <p class=req id=H30910>
          [fileformat_import_requirement H30910]

      <p>
        The following requirements govern management of free-space within the
        page content area (both table and index B-Tree pages).

      <p class=req id=H30920>
          [fileformat_import_requirement H30920]

      <p class=req id=H30930>
          [fileformat_import_requirement H30930]

      <p class=req id=H30940>
          [fileformat_import_requirement H30940]

      <p class=req id=H30950>
          [fileformat_import_requirement H30950]


      <p class=req id=H30960>
          [fileformat_import_requirement H30960]

      [h4 "Index B-Tree Cell Format" index_btree_cell_format]
        <p> 
          For index B-Tree internal tree node pages, each B-Tree cell begins
          with a child page-number, stored as a 4-byte big-endian unsigned
          integer. This field is omitted for leaf pages, which have no 
          children.
................................................................................
          in bytes less the number of unused bytes left at the end of every
          page (as read from byte offset 20 of the file header), and
          <i>max-embedded-fraction</i> and <i>min-embedded-fraction</i> are
          the values read from byte offsets 21 and 22 of the file header,
          respectively.
        [Figure indexlongrecord.gif figure_indexlongrecord "Large Record Index B-Tree Cell"]

      <p class=req id=H30970>
          [fileformat_import_requirement H30970]

      <p class=req id=H30980>
          [fileformat_import_requirement H30980]

      <p class=req id=H30990>
          [fileformat_import_requirement H30990]

      <p class=req id=H31000>
          [fileformat_import_requirement H31000]

      <p class=req id=H31010>
          [fileformat_import_requirement H31010]

      <p>
        Requirements H31010 and H30990 are similar to the algorithms 
        presented in the text above. However instead of 
        <i>min-embedded-fraction</i> and <i>max-embedded-fraction</i> the
        requirements use the constant values 32 and 64, as well-formed 
        database files are required by H30080 and H30070 to store these 
................................................................................
        Figure <cite>figure_tabletree</cite> depicts a table B-Tree containing
        a contiguous set of 14 integer keys starting with 1. Each key <i>n</i>
        has an associated database record R<i>n</i>. All the keys and their
        associated records are stored in the leaf pages. The internal node
        pages contain no database data, their only purpose is to provide
        a way to navigate the tree structure.

      <p class=req id=H31020>
          [fileformat_import_requirement H31020]

      <p class=req id=H31030>
          [fileformat_import_requirement H31030]

      <p class=req id=H31040>
          [fileformat_import_requirement H31040]

      <p class=req id=H31050>
          [fileformat_import_requirement H31050]

      <p>
        The precise way in which table B-Tree pages and cells are formatted is
        described in subsequent sections.

      [h4 "Table B-Tree Content" table_btree_content]
        <p>
................................................................................
          are SQL NULL. If the schema layer file-format is greater than
          2, then the values associated with the "missing" fields are 
          determined by the default value of the associated database table 
          columns.
          <span class=todo>Reference to CREATE TABLE syntax. How are default
          values determined?</span>

        <p class=req id=H31060>
          [fileformat_import_requirement H31060]

        <p class=req id=H31070>
          [fileformat_import_requirement H31070]

        <p class=req id=H31080>
          [fileformat_import_requirement H31080]

        <p class=req id=H31090>
          [fileformat_import_requirement H31090]

        <p>The following database properties discuss table B-Tree records 
           with implicit (default) values.

          <p class=req id=H31100>
          [fileformat_import_requirement H31100]

          <p class=req id=H31110>
          [fileformat_import_requirement H31110]

          <p class=req id=H31120>
          [fileformat_import_requirement H31120]

      [h4 "Table B-Tree Page Format"]
        <p>
          Table B-Tree structures use the same page format as index B-Tree 
          structures, described in section <cite>index_btree_page_format</cite>,
          with the following differences:
        <ul>
................................................................................
              section <cite>table_btree_cell_format</cite> for details.
          <li>The format of page 1 is the same as any other table B-Tree,
              except that 100 bytes less than usual is available for content.
              The first 100 bytes of page 1 is consumed by the database
              file header.
        </ul>

      <p class=req id=H31130>
          [fileformat_import_requirement H31130]
      <p class=req id=H31140>
          [fileformat_import_requirement H31140]
        
      <p>
        Most of the requirements specified in section 
        <cite>index_btree_page_format</cite> also apply to table B-Tree 
        pages. The wording of the requirements make it clear when this is
        the case, either by refering to generic "B-Tree pages" or by
        explicitly stating that the statement applies to both "table and
................................................................................
          header).

        <p>
          The following requirements describe the format of table B-Tree 
          cells, and the distribution thereof between B-Tree and overflow
          pages.

        <p class=req id=H31150>
          [fileformat_import_requirement H31150]

        <p class=req id=H31160>
          [fileformat_import_requirement H31160]

        <p class=req id=H31170>
          [fileformat_import_requirement H31170]

        <p class=req id=H31180>
          [fileformat_import_requirement H31180]

        <p class=req id=H31190>
          [fileformat_import_requirement H31190]
        
        <p>
          Requirement H31190 is very similar to the algorithm presented in
          the text above. Instead of <i>min-embedded-fraction</i>, it uses
          the constant value 32, as well-formed database files are required
          by H30090 to store this value in the relevant database file 
          header field.
................................................................................
      <p>
        Each overflow page except for the last one in the linked list 
        contains <i>available-space</i> bytes of record data. The last
        page in the list contains the remaining data, starting at byte
        offset 4. The value of the "next page" field on the last page
        in an overflow chain is undefined.

      <p class=req id=H31200>
          [fileformat_import_requirement H31200]

      <p class=req id=H31210>
          [fileformat_import_requirement H31210]

      <p class=req id=H31220>
          [fileformat_import_requirement H31220]

      <p class=req id=H31230>
          [fileformat_import_requirement H31230]

  [h2 "The Free Page List" free_page_list]
    <p>
      Sometimes, after deleting data from the database, SQLite removes pages
      from B-Tree structures. If these pages are not immediately required
      for some other purpose, they are placed on the free page list. The
      free page list contains those pages that are not currently being
................................................................................
    <p>
      All trunk pages in the free-list except for the first contain the 
      maximum possible number of references to leaf pages. <span class=todo>Is this actually true in an auto-vacuum capable database?</span> The page number
      of the first page in the linked list of free-list trunk pages is 
      stored as a 4-byte big-endian unsigned integer at offset 32 of the
      file header (section <cite>file_header</cite>).

    <p class=req id=H31240>
          [fileformat_import_requirement H31240]

    <p class=req id=H31250>
          [fileformat_import_requirement H31250]

    <p class=req id=H31260>
          [fileformat_import_requirement H31260]

    <p class=req id=H31270>
          [fileformat_import_requirement H31270]

    <p class=req id=H31280>
          [fileformat_import_requirement H31280]

    <p class=req id=H31290>
          [fileformat_import_requirement H31290]

    <p class=req id=H31300>
          [fileformat_import_requirement H31300]

    <p>The following statements govern the two 4-byte big-endian integers
       associated with the <i>free page list</i> structure in the database
       file header.

    <p class=req id=H31310>
          [fileformat_import_requirement H31310]

    <p class=req id=H31320>
          [fileformat_import_requirement H31320]
  

  [h2 "Pointer Map Pages" pointer_map_pages]
    <p>
      Pointer map pages are only present in auto-vacuum capable databases.
      A database is an auto-vacuum capable database if the value stored 
      at byte offset 52 of the file-header is non-zero.
................................................................................
      table entries for the <i>num-entries</i> pages that follow it in the
      database file:
    <pre>
        <i>pointer-map-page-number</i> := 2 + <i>n</i> * <i>num-entries</i>
</pre>


    <p class=req id=H31330>
          [fileformat_import_requirement H31330]

    <p class=req id=H31340>
          [fileformat_import_requirement H31340]

    <p class=req id=H31350>
          [fileformat_import_requirement H31350]

    <p class=req id=H31360>
          [fileformat_import_requirement H31360]

    <p class=req id=H31370>
          [fileformat_import_requirement H31370]

    <p>
      The following requirements govern the content of pointer-map entries.

    <p class=req id=H31380>
          [fileformat_import_requirement H31380]
    <p class=req id=H31390>
          [fileformat_import_requirement H31390]
    <p class=req id=H31400>
          [fileformat_import_requirement H31400]
    <p class=req id=H31410>
          [fileformat_import_requirement H31410]
    <p class=req id=H31420>
          [fileformat_import_requirement H31420]

[h1 "Database File-System Representation" file_system_usage]

    <p>
      The previous section, section <cite>database_file_format</cite> 
      describes the format of an SQLite database image. A database
      image is the serialized form of a logical SQLite database. Normally,
      a database image is stored within the file-system in a single
      file, a database file. In this case no other data is stored
      within the database file, the first byte of the <i>database
      file</i> is the first byte of the database image, and the last 
      byte of the database file is the last byte of the <i>database 
      image</i>. For this reason, SQLite is often described as a "single-file 
      database system", implying that the contents of a database are always 
      stored in a single file within the file-system. However, this is not
      always the case. It is also possible for an SQLite database image
      to be distributed between the database file and a 
      journal file. A third file, a <i>master-journal file</i> may
      also be part of the file-system representation. Although a
      <i>master-journal file</i> never contains any part of the <i>database
      image</i>, it can contain meta-data that helps determine which parts of 
      the database image are stored within the database file, and
      which parts are stored within the journal file.

    <p>
      In other words, the file-system representation of an SQLite database
      consists of the following:

    <ul>
      <li> <p>A main <b>database file</b>. The database file is
................................................................................
      the database image to commit a database transaction. In practice,
      a database reader only encounters such a configuration if a previous
      attempt to modify the database image on disk was interrupted by an
      application, OS or power failure. The most practical approach (and
      that taken by SQLite) is to extract the subset of the database image
      currently stored within the journal file and write it into the database
      file, thus restoring the system to a state where the database file
      contains the verbatim database image. Other SQLite documentation, and 
      the comments in the SQLite source code, identify this process as <i>hot 
      journal rollback</i>. Instead of focusing on the <i>hot journal
      rollback</i> process, this document describes only how the data within
      a journal file should be interpret to extract the current database 
      image, not how the database file should be transformed as a result of 
      it.


    <p>
      Sub-section <cite>journal_file_formats</cite> describes the formats 
      used by <i>journal</i> and <i>master-journal</i> files.

    <p>
      Sub-section <cite>reading_from_files</cite> contains a precise 
................................................................................
  <p>
    A <i>master-journal file</i> contains the full paths to two or more
    <i>journal files</i>, each encoded using UTF-8 encoding and terminated
    by a single nul character (byte value 0x00). There is no padding 
    between the journal paths, each UTF-8 encoded path begins immediately
    after the nul character that terminates the previous one.






[h2 "Reading an SQLite Database" reading_from_files]

  <p>
    As described in section <cite>pages_and_page_types</cite> of this document,
    an SQLite database image is a set of contiguously numbered fixed size 
    pages. The numbering starts at 1, not 0. Page 1 contains the 
    <i>database file header</i> and the root page of the <i>schema table</i>, 
    and all other pages within the database image are somehow referred to 
    by number from page 1, either directly or indirectly. In order to be able
    to read the database image from within the file-system, a database
    reader needs to be able to ascertain:

  <ol>
    <li> The <i>page-size</i> used by the database image,
    <li> The number of pages in the database image, and
    <li> The content of each database page.
  </ol>

  <p>
    Usually, the database file contains the complete, unadulterated 
    database image. In this case, reading the database image is 
    straightforward. The <i>page-size</i> used by the database image can be
    read from the 2-byte big-endian integer field stored at byte offset 16 of
    the database file (see section <cite>file_header). The number of pages in
    the database image can be determined by querying the size of
    the database file in bytes and then dividing by the <i>page-size</i>.
    Reading the contents of a <i>database page</i> is a simple matter of 
    reading a block of <i>page-size</i> bytes from an offset calculated from
    the page-number of the required page.



    
  <p>
    However, if there is a valid journal file corresponding to the 
    database file present within the file-system then the situation 
    is more complicated. The file-system is considered to contain a valid 
    journal file if each of the following conditions are met:

................................................................................
    for each of these is stored in the database file. Even though the contents
    of the file-system is quite different in representation 2 as in
    representation 1, the stored database image is the same in each case: 4
    pages of page-size bytes each, content A, B, C and D respectively.

    [Figure filesystem1.gif figure_filesystem1 "Two ways to store the same database image"]








  <p>
    These requirements describe the way a database reader must determine
    whether or not there is a valid journal file within the 
    file-system.

    [fileformat_import_requirement2 H32000]
    [fileformat_import_requirement2 H32010]
................................................................................
    [fileformat_import_requirement2 H32080]

[h2 "Writing to an SQLite Database" writing_to_files]

  <p>
    When an SQLite user commits a transaction that modifies the contents
    of the database, the database representation on disk must be modified
    to reflect the new contents of the database image. SQLite is required 

























































    to do make all modifications associated with the transaction such that 
    the database image is modified atomically. If an application, OS or 
    power failure occurs while SQLite is updating the database, upon recovery 
    the contents of the database must reflect either that all modifications 
    associated with the database transaction were successfully applied, or 
    that none of the modifications were applied and the contents of the 
    database are as they were before the failed attempt to modify the database.














  <p>
    Some operations on a file-system may be considered atomic. For example
    deleting a file, or on some systems writing to a single disk sector.
    However, in general there exists no atomic file-system operation
    that may be used to update an SQLite database file with the effects
    of an arbitrary database transaction, which may remove, modify or
    add multiple database rows, tables or indexes. Therefore, a two stage
................................................................................
    <li> The file-system representation of the database is manipulated to
         a state where a single atomic operation may be used to transform
         the logical contents of the database from its initial state to
         the required final state.
    <li> The required atomic operation is applied.
  </ol>






  <p>
    Step 1 of the above must be accomplished such that all interim states
    of the file-system correspond to the logical contents of the database
    as they were before the procedure began. This way, if an application,
    OS or power failure occurs during step 1, upon recovery the database
    contents remain unchanged. It is not possible for such a failure to
    occur "during" step 2, as step 2 consists of a single atomic operation.
................................................................................
    operation can be used to effect all required changes to the logical
    database contents.

  <p>
    The following two sub-sections describe the specific ways in which 
    SQLite achieves this for single and multiple database transactions.

  [h3 "Single Database Transactions" single_db_transactions]

  <p>
    In order to atomically modify the database image stored in the 
    file-system from database image A to database image B, the file-system must
    first be manipulated to a state where it contains the database image A,
    but can by a single atomic operation be modified to contain database 
    image B. A file-system state that has the following properties satisfies
................................................................................

    [Figure filesystem2.gif figure_filesystem2 "Interim file-system state used to atomically overwrite database image ABCD with AEC"]

  <p class=todo>
    The exception for free-list leaves.


  [h3 "Multiple Database Transactions" multi_db_transactions]

  <p class=todo>
    Deleting the master-journal is used as the atomic operation.









[h1 "SQLite Interoperabilty Requirements" locking_protocol]


















  <p class=todo>
    This section will describe the things that an SQLite compatible database
    client has to do in order to safely operate on a database at the same
    time as regular SQLite clients. Specifically, implementing the the 
    locking protocol and updating the change-counter in the database image
    header each time the database is modified.








[h1 References]

  <table id="refs" style="width:auto; margin: 1em 5ex">
    <tr><td style="width:5ex" id="ref_comer_btree">\[1\]<td>
     Douglas Comer, <u>Ubiquitous B-Tree</u>, ACM Computing Surveys (CSUR),
     v.11 n.2, pages 121-137, June 1979.








|







 







|
|







 







<
|







<
|







 







<
|






<
|
<
|
<
<
|
<
<
|
<
|
<
|
<
|






<
|
<
<
|
<
<
|
<
<
|
<
<
|
<
<
|
<
<
|
<
<
|







 







<
|
<
|
<
|
<
|







 







<
|
<
|



<
|
<
<
|
<
<
|
<
<
|
<
<
|
<
<
|
<
<
|



<
|
<
<
|
<
|
<
|



<
|
<
|
<
|
<
|



<
|
<
<
|
<
<
|
<
<
|



<
|
<
<
|
<
<
|
<
<
|




<
|
<
<
|
<







 







<
|
<
|







 







<
|
<
<
|
<
<
|
<
<
|







 







<
|
<
<
|
<
<
|
<
<
|
<
<
|
<
|
<
|
<
|
<
|
<
|
<
<
|
<
<
|
<
<
|
<
<
|
<
<
|






<
|
<
|







 







<
|
<
<
|
<
<
|
<
<
|







 







<
|
<
<
|
<
<
|
<
<
|







 







<
|
<
|





<
|
<
<
|
<
<
|
<
<
|





<
|
<
<
|
<
<
|
<
<
|
<
<
|





<
|
<
<
|
<
<
|
<
<
|
<
<
<
|







 







<
|
<
<
|
<
<
|
<
<
|
<
<
|







 







<
|
<
<
|
<
<
|
<
<
|







 







<
|
<
<
|
<
<
|
<
<
|




<
|
<
<
|
<
<
|







 







<
|
<
|







 







<
|
<
<
|
<
<
|
<
<
|
<
<
|







 







<
|
<
<
|
<
<
|
<
<
|







 







<
|
<
<
|
<
<
|
<
<
|
<
<
|
<
<
|
<
<
|





<
|
<
<
|







 







<
|
<
<
|
<
<
|
<
<
|
<
<
|




<
|
<
|
<
|
<
|
<
|









|



|
|
<
|
|
|
|
|
<
|







 







|


|
|
|
<
>







 







>
>
>
>
>







|
|
|
|








|
|
|
|
|
|



|
>
>
>







 







>
>
>
>
>
>
>







 







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








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







 







>
>
>
>
>







 







|







 







|




>

>
>
>
>
>
>
|

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

<
<
<
<
<
>
>
>
>
>
>
>

      journal file and the rules for correctly reading a database image from
      the combination of a database file and journal file. The same section
      also includes guidelines and requirements describing the intended method
      for atomically updating the database image within the file-system without
      risking database corruption.

    <p>
      <b>Section <cite>interoperability_requirements</cite></b> contains a description of
      and software requirements related to:

    <ul>
      <li>The locking protocol used by SQLite to manage read and write access
          to the database and journal files within the file-system, and
      <li>the change-counter and schema-cookie protocols that must be followed
          by all database writers to facilitate the implementation of
................................................................................
      is required to interpret or create SQLite database images may be found
      in section <cite>database_file_format</cite>. Requirements and guidelines
      for software required to safely read and write database images to disk
      using an SQLite compatible system failure recovery mechanism to prevent
      database corruption or data loss are found in section 
      <cite>file_system_usage</cite>. Finally, rules and requirements for software 
      systems required to read and write live SQLite databases within a system that
      includes real SQLite clients that may also read and write databases
      are presented in section <cite>interoperability_requirements</cite>.

  [h2 "Glossary"]
    <table id=glossary>
      <tr><td>Auto-vacuum last root-page<td>
        A page number stored as 32-bit integer at byte offset 52 of the
        database file header (see section <cite>file_header</cite>). In
        an auto-vacuum database, this is the numerically largest 
................................................................................
h1 "SQLite Database Files" sqlite_database_files
 
  <p>
    The bulk of this document, section <cite>database_file_format</cite>,
    contains the definition of a <i>well-formed SQLite database file</i>.
    SQLite is required to create database files that meet this definition.


          [fileformat_import_requirement2 H30010]

  <p>
    Additionally, the database file should contain a serialized version
    of the logical database produced by the transaction. For all but the
    most trivial logical databases, there are many possible serial 
    representations.


          [fileformat_import_requirement2 H30020]
-->

<!--
  <p>
    Section <cite>database_file_manipulation</cite> contains requirements
    describing in more detail the way in which SQLite manipulates the
    fields and data structures described in section
................................................................................
        Some of the following requirements state that certain database header
        fields must contain defined constant values, even though the sqlite 
        database file format is designed to allow various values. This is
        done to artificially constrain the definition of a 
        <i>well-formed database</i> in order to make implementation and 
        testing more practical.


          [fileformat_import_requirement2 H30030]

      <p>
        Following the 16 byte magic string in the file header is the
        <i>page size</i>, a 2-byte field. See section
        <cite>pages_and_page_types</cite> for details.


          [fileformat_import_requirement2 H30040]

          [fileformat_import_requirement2 H30050]


          [fileformat_import_requirement2 H30060]


          [fileformat_import_requirement2 H30070]

          [fileformat_import_requirement2 H30080]

          [fileformat_import_requirement2 H30090]

          [fileformat_import_requirement2 H30100]

      <p>
        Following the <i>file change counter</i> in the database header are
        two 4-byte fields related to the database file <i>free page list</i>.
        See section <cite>free_page_list</cite> for details.


          [fileformat_import_requirement2 H30110]


          [fileformat_import_requirement2 H30120]


          [fileformat_import_requirement2 H30130]


          [fileformat_import_requirement2 H30140]


          [fileformat_import_requirement2 H30150]


          [fileformat_import_requirement2 H30160]


          [fileformat_import_requirement2 H30170]


          [fileformat_import_requirement2 H30180]

    [h3 "Pages and Page Types" "pages_and_page_types"]
      <p>
        The entire database file is divided into pages, each page consisting
        of <i>page-size</i> bytes, where <i>page-size</i> is the 2-byte 
        integer value stored at offset 16 of the file header (see above).
        The <i>page-size</i> is always a power of two between 512 
................................................................................
            permanently designated "pointer-map" pages. See section 
            <cite>pointer_map_pages</cite> for details.
        <li><b>The locking page</b>. The database page that starts at
            byte offset 2<sup>30</sup>, if it is large enough to contain
            such a page, is always left unused.
      </ul>


          [fileformat_import_requirement2 H30190]

          [fileformat_import_requirement2 H30200]

          [fileformat_import_requirement2 H30210]

          [fileformat_import_requirement2 H30220]
        

    [h3 "The Schema Table" schema_table]
      <p>
        Apart from being the page that contains the file-header, page 1 of
        the database file is special because it is the root page of the
        B-Tree structure that contains the schema table data. From the SQL
................................................................................
        [Tr]<td>index <td>i1 <td>abc <td>3 <td>CREATE INDEX i1 ON abc(b, c)
        [Tr]<td>table <td>def <td>def <td>4 <td>CREATE TABLE def(a PRIMARY KEY, b, c, UNIQUE(b, c))
        [Tr]<td>index <td>sqlite_autoindex_def_1 <td>def <td>5 <td>
        [Tr]<td>index <td>sqlite_autoindex_def_2 <td>def <td>6 <td>
        [Tr]<td>view <td>v1 <td>v1 <td>0 <td>CREATE VIEW v1 AS SELECT * FROM abc
      </table>


          [fileformat_import_requirement2 H30230]

          [fileformat_import_requirement2 H30240]

      <p>The following requirements describe "table" records.


          [fileformat_import_requirement2 H30250]


          [fileformat_import_requirement2 H30260]


          [fileformat_import_requirement2 H30270]


          [fileformat_import_requirement2 H30280]


          [fileformat_import_requirement2 H30290]


          [fileformat_import_requirement2 H30300]


          [fileformat_import_requirement2 H30310]

      <p>The following requirements describe "implicit index" records.


          [fileformat_import_requirement2 H30320]


          [fileformat_import_requirement2 H30330]

          [fileformat_import_requirement2 H30340]

          [fileformat_import_requirement2 H30350]

      <p>The following requirements describe "explicit index" records.


          [fileformat_import_requirement2 H30360]

          [fileformat_import_requirement2 H30370]

          [fileformat_import_requirement2 H30380]

          [fileformat_import_requirement2 H30390]

      <p>The following requirements describe "view" records.


          [fileformat_import_requirement2 H30400]


          [fileformat_import_requirement2 H30410]


          [fileformat_import_requirement2 H30420]


          [fileformat_import_requirement2 H30430]

      <p>The following requirements describe "trigger" records.


          [fileformat_import_requirement2 H30440]


          [fileformat_import_requirement2 H30450]


          [fileformat_import_requirement2 H30460]


          [fileformat_import_requirement2 H30470]

      <p>The following requirements describe the placement of B-Tree root 
         pages in auto-vacuum databases.


          [fileformat_import_requirement2 H30480]


          [fileformat_import_requirement2 H30490]


 
  [h2 "B-Tree Structures" "btree_structures"]
    <p>
      A large part of any SQLite database file is given over to one or more
      B-Tree structures. A single B-Tree structure is stored using one or more
      database pages. Each page contains a single B-Tree node.
................................................................................
          B-Tree structures are described in detail in section 
          <cite>table_btrees</cite>.
      <li>The <b>index B-Tree</b>, which uses database records as keys. Index
          B-Tree structures are described in detail in section 
          <cite>index_btrees</cite>.
    </ul>


          [fileformat_import_requirement2 H30500]

          [fileformat_import_requirement2 H30510]

    [h3 "Variable Length Integer Format" "varint_format"]
      <p>
        In several parts of the B-Tree structure, 64-bit twos-complement signed
        integer values are stored in the "variable length integer format"
        described here.
      <p>
................................................................................
        [Tr]<td>200815 <td>0x000000000003106F <td>0x8C 0xA0 0x6F
        [Tr]<td>-1     <td>0xFFFFFFFFFFFFFFFF 
            <td>0xFF 0xFF 0xFF 0xFF 0xFF 0xFF 0xFF 0xFF 0xFF
        [Tr]<td>-78056 <td>0xFFFFFFFFFFFECD56
            <td>0xFF 0xFF 0xFF 0xFF 0xFF 0xFF 0xFD 0xCD 0x56
      </table>


          [fileformat_import_requirement2 H30520]


          [fileformat_import_requirement2 H30530]


          [fileformat_import_requirement2 H30540]


          [fileformat_import_requirement2 H30550]
      

    [h3 "Database Record Format" "record_format"]
      <p>
        A database record is a blob of data that represents an ordered
        list of one or more SQL values. Database records are used in two
        places in SQLite database files - as the associated data for entries
................................................................................
        the length of the data field is as described in the table above.
      <p>
        The data field associated with a string value contains the string
        encoded using the database encoding, as defined in the database
        file header (see section <cite>file_header</cite>). No 
        nul-terminator character is stored in the database.


          [fileformat_import_requirement2 H30560]


          [fileformat_import_requirement2 H30570]


          [fileformat_import_requirement2 H30580]


          [fileformat_import_requirement2 H30590]


          [fileformat_import_requirement2 H30600]

          [fileformat_import_requirement2 H30610]

          [fileformat_import_requirement2 H30620]

          [fileformat_import_requirement2 H30630]

          [fileformat_import_requirement2 H30640]

          [fileformat_import_requirement2 H30650]


          [fileformat_import_requirement2 H30660]


          [fileformat_import_requirement2 H30670]


          [fileformat_import_requirement2 H30680]


          [fileformat_import_requirement2 H30690]


          [fileformat_import_requirement2 H30700]

      <p>
        The following database file properties define restrictions on the 
        integer values that may be stored within a 
        <i>database record header</i>.


          [fileformat_import_requirement2 H30710]

          [fileformat_import_requirement2 H30720]

    [h3 "Index B-Trees" index_btrees]
      <p>
        As specified in section <cite>fileformat_overview</cite>, index 
        B-Tree structures store a unique set of the database records described
        in the previous section. While in some cases, when there are very
        few entries in the B-Tree, the entire structure may fit on a single
................................................................................
        Figure <cite>figure_indextree</cite> depicts one possible record
        distribution for an index B-Tree containing records R1 to R26, assuming
        that for all values of N, <i>R(N+1)&gt;R(N)</i>. In total the B-Tree
        structure uses 11 database file pages. Internal tree nodes contain
        database records and references to child node pages. Leaf nodes contain
        database records only.


          [fileformat_import_requirement2 H30730]


          [fileformat_import_requirement2 H30740]


          [fileformat_import_requirement2 H30750]


          [fileformat_import_requirement2 H30760]

      <p>
        The precise way in which index B-Tree pages and cells are formatted is
        described in subsequent sections.


        [h4 "Index B-Tree Content"]
................................................................................
          <p>
            An index B-Tree contains an entry for each row in its associated
            database table. The fields of the record used as the index B-Tree
            key are copies of each of the indexed columns of the associated 
            database row, in order, followed by the rowid value of the same 
            row. See figure <cite>figure_examplepop</cite> for an example.


          [fileformat_import_requirement2 H30770]


          [fileformat_import_requirement2 H30780]


          [fileformat_import_requirement2 H30790]


          [fileformat_import_requirement2 H30800]
 
      [h4 "Record Sort Order" "index_btree_compare_func"]
        <p>
          This section defines the comparison function used when database
          records are used as B-Tree keys for index B-Trees. The comparison
          function is only defined when both database records contain the same
          number of fields.
................................................................................
            the page) of the next block in the list stored as a big-endian
            unsigned integer. The first two bytes of the final block in the 
            list are set to zero. The third and fourth bytes of each free
            block contain the total size of the free block in bytes, stored
            as a 2 byte big-endian unsigned integer.
      </ul>


          [fileformat_import_requirement2 H30810]

          [fileformat_import_requirement2 H30820]

      <p>
        The following requirements describe the <i>B-Tree page header</i>
        present at the start of both index and table B-Tree pages.


          [fileformat_import_requirement2 H30830]


          [fileformat_import_requirement2 H30840]


          [fileformat_import_requirement2 H30850]


          [fileformat_import_requirement2 H30860]

      <p>
        This requirement describes the cell content offset array. It applies
        to both B-Tree variants.


          [fileformat_import_requirement2 H30870]


          [fileformat_import_requirement2 H30880]


          [fileformat_import_requirement2 H30890]


          [fileformat_import_requirement2 H30900]


          [fileformat_import_requirement2 H30910]

      <p>
        The following requirements govern management of free-space within the
        page content area (both table and index B-Tree pages).


          [fileformat_import_requirement2 H30920]


          [fileformat_import_requirement2 H30930]


          [fileformat_import_requirement2 H30940]


          [fileformat_import_requirement2 H30950]



          [fileformat_import_requirement2 H30960]

      [h4 "Index B-Tree Cell Format" index_btree_cell_format]
        <p> 
          For index B-Tree internal tree node pages, each B-Tree cell begins
          with a child page-number, stored as a 4-byte big-endian unsigned
          integer. This field is omitted for leaf pages, which have no 
          children.
................................................................................
          in bytes less the number of unused bytes left at the end of every
          page (as read from byte offset 20 of the file header), and
          <i>max-embedded-fraction</i> and <i>min-embedded-fraction</i> are
          the values read from byte offsets 21 and 22 of the file header,
          respectively.
        [Figure indexlongrecord.gif figure_indexlongrecord "Large Record Index B-Tree Cell"]


          [fileformat_import_requirement2 H30970]


          [fileformat_import_requirement2 H30980]


          [fileformat_import_requirement2 H30990]


          [fileformat_import_requirement2 H31000]


          [fileformat_import_requirement2 H31010]

      <p>
        Requirements H31010 and H30990 are similar to the algorithms 
        presented in the text above. However instead of 
        <i>min-embedded-fraction</i> and <i>max-embedded-fraction</i> the
        requirements use the constant values 32 and 64, as well-formed 
        database files are required by H30080 and H30070 to store these 
................................................................................
        Figure <cite>figure_tabletree</cite> depicts a table B-Tree containing
        a contiguous set of 14 integer keys starting with 1. Each key <i>n</i>
        has an associated database record R<i>n</i>. All the keys and their
        associated records are stored in the leaf pages. The internal node
        pages contain no database data, their only purpose is to provide
        a way to navigate the tree structure.


          [fileformat_import_requirement2 H31020]


          [fileformat_import_requirement2 H31030]


          [fileformat_import_requirement2 H31040]


          [fileformat_import_requirement2 H31050]

      <p>
        The precise way in which table B-Tree pages and cells are formatted is
        described in subsequent sections.

      [h4 "Table B-Tree Content" table_btree_content]
        <p>
................................................................................
          are SQL NULL. If the schema layer file-format is greater than
          2, then the values associated with the "missing" fields are 
          determined by the default value of the associated database table 
          columns.
          <span class=todo>Reference to CREATE TABLE syntax. How are default
          values determined?</span>


          [fileformat_import_requirement2 H31060]


          [fileformat_import_requirement2 H31070]


          [fileformat_import_requirement2 H31080]


          [fileformat_import_requirement2 H31090]

        <p>The following database properties discuss table B-Tree records 
           with implicit (default) values.


          [fileformat_import_requirement2 H31100]


          [fileformat_import_requirement2 H31110]


          [fileformat_import_requirement2 H31120]

      [h4 "Table B-Tree Page Format"]
        <p>
          Table B-Tree structures use the same page format as index B-Tree 
          structures, described in section <cite>index_btree_page_format</cite>,
          with the following differences:
        <ul>
................................................................................
              section <cite>table_btree_cell_format</cite> for details.
          <li>The format of page 1 is the same as any other table B-Tree,
              except that 100 bytes less than usual is available for content.
              The first 100 bytes of page 1 is consumed by the database
              file header.
        </ul>


          [fileformat_import_requirement2 H31130]

          [fileformat_import_requirement2 H31140]
        
      <p>
        Most of the requirements specified in section 
        <cite>index_btree_page_format</cite> also apply to table B-Tree 
        pages. The wording of the requirements make it clear when this is
        the case, either by refering to generic "B-Tree pages" or by
        explicitly stating that the statement applies to both "table and
................................................................................
          header).

        <p>
          The following requirements describe the format of table B-Tree 
          cells, and the distribution thereof between B-Tree and overflow
          pages.


          [fileformat_import_requirement2 H31150]


          [fileformat_import_requirement2 H31160]


          [fileformat_import_requirement2 H31170]


          [fileformat_import_requirement2 H31180]


          [fileformat_import_requirement2 H31190]
        
        <p>
          Requirement H31190 is very similar to the algorithm presented in
          the text above. Instead of <i>min-embedded-fraction</i>, it uses
          the constant value 32, as well-formed database files are required
          by H30090 to store this value in the relevant database file 
          header field.
................................................................................
      <p>
        Each overflow page except for the last one in the linked list 
        contains <i>available-space</i> bytes of record data. The last
        page in the list contains the remaining data, starting at byte
        offset 4. The value of the "next page" field on the last page
        in an overflow chain is undefined.


          [fileformat_import_requirement2 H31200]


          [fileformat_import_requirement2 H31210]


          [fileformat_import_requirement2 H31220]


          [fileformat_import_requirement2 H31230]

  [h2 "The Free Page List" free_page_list]
    <p>
      Sometimes, after deleting data from the database, SQLite removes pages
      from B-Tree structures. If these pages are not immediately required
      for some other purpose, they are placed on the free page list. The
      free page list contains those pages that are not currently being
................................................................................
    <p>
      All trunk pages in the free-list except for the first contain the 
      maximum possible number of references to leaf pages. <span class=todo>Is this actually true in an auto-vacuum capable database?</span> The page number
      of the first page in the linked list of free-list trunk pages is 
      stored as a 4-byte big-endian unsigned integer at offset 32 of the
      file header (section <cite>file_header</cite>).


          [fileformat_import_requirement2 H31240]


          [fileformat_import_requirement2 H31250]


          [fileformat_import_requirement2 H31260]


          [fileformat_import_requirement2 H31270]


          [fileformat_import_requirement2 H31280]


          [fileformat_import_requirement2 H31290]


          [fileformat_import_requirement2 H31300]

    <p>The following statements govern the two 4-byte big-endian integers
       associated with the <i>free page list</i> structure in the database
       file header.


          [fileformat_import_requirement2 H31310]


          [fileformat_import_requirement2 H31320]
  

  [h2 "Pointer Map Pages" pointer_map_pages]
    <p>
      Pointer map pages are only present in auto-vacuum capable databases.
      A database is an auto-vacuum capable database if the value stored 
      at byte offset 52 of the file-header is non-zero.
................................................................................
      table entries for the <i>num-entries</i> pages that follow it in the
      database file:
    <pre>
        <i>pointer-map-page-number</i> := 2 + <i>n</i> * <i>num-entries</i>
</pre>



          [fileformat_import_requirement2 H31330]


          [fileformat_import_requirement2 H31340]


          [fileformat_import_requirement2 H31350]


          [fileformat_import_requirement2 H31360]


          [fileformat_import_requirement2 H31370]

    <p>
      The following requirements govern the content of pointer-map entries.


          [fileformat_import_requirement2 H31380]

          [fileformat_import_requirement2 H31390]

          [fileformat_import_requirement2 H31400]

          [fileformat_import_requirement2 H31410]

          [fileformat_import_requirement2 H31420]

[h1 "Database File-System Representation" file_system_usage]

    <p>
      The previous section, section <cite>database_file_format</cite> 
      describes the format of an SQLite database image. A database
      image is the serialized form of a logical SQLite database. Normally,
      a database image is stored within the file-system in a single
      file, a database file. In this case no other data is stored
      within the database file. The first byte of the <i>database
      file</i> is the first byte of the database image, and the last 
      byte of the database file is the last byte of the <i>database 
      image</i>. For this reason, SQLite is often described as a "single-file 
      database system". However, an SQLite database image is not always 
      stored in a single file within the file-system. It is also possible 

      for it to be distributed between the database file and a journal file. A
      third file, a <i>master-journal file</i> may also be part of the
      file-system representation. Although a <i>master-journal file</i> never
      contains any part of the <i>database image</i>, it can contain meta-data
      that helps determine which parts of the database image are stored within

      the database file, and which parts are stored within the journal file.

    <p>
      In other words, the file-system representation of an SQLite database
      consists of the following:

    <ul>
      <li> <p>A main <b>database file</b>. The database file is
................................................................................
      the database image to commit a database transaction. In practice,
      a database reader only encounters such a configuration if a previous
      attempt to modify the database image on disk was interrupted by an
      application, OS or power failure. The most practical approach (and
      that taken by SQLite) is to extract the subset of the database image
      currently stored within the journal file and write it into the database
      file, thus restoring the system to a state where the database file
      contains the entire database image. Other SQLite documentation, and 
      the comments in the SQLite source code, identify this process as <i>hot 
      journal rollback</i>. Instead of focusing on the <i>hot journal
      rollback</i> process, this document describes how journal and
      master-journal files must be interpreted in order to extract the 
      current database image from the file-system representation in the

      general case.

    <p>
      Sub-section <cite>journal_file_formats</cite> describes the formats 
      used by <i>journal</i> and <i>master-journal</i> files.

    <p>
      Sub-section <cite>reading_from_files</cite> contains a precise 
................................................................................
  <p>
    A <i>master-journal file</i> contains the full paths to two or more
    <i>journal files</i>, each encoded using UTF-8 encoding and terminated
    by a single nul character (byte value 0x00). There is no padding 
    between the journal paths, each UTF-8 encoded path begins immediately
    after the nul character that terminates the previous one.

  <p class=todo>
    Note that the contents of a master-journal is not really all that
    important, and is not required at all to read the database image. 
    Used for cleanup only.

[h2 "Reading an SQLite Database" reading_from_files]

  <p>
    As described in section <cite>pages_and_page_types</cite> of this document,
    an SQLite database image is a set of contiguously numbered fixed size 
    pages. The numbering starts at 1, not 0. Page 1 contains the 
    <i>database file header</i> and the root page of the <i>schema table</i>, 
    and all other pages within the database image are somehow referenced
    by number, either directly or indirectly, from page 1, either directly 
    or indirectly. In order to be able to read the database image from within
    the file-system, a database reader needs to be able to ascertain:

  <ol>
    <li> The <i>page-size</i> used by the database image,
    <li> The number of pages in the database image, and
    <li> The content of each database page.
  </ol>

  <p>
    Usually, the database image is simply the contents of the database file. 
    In this case, reading the database image is straightforward. The
    page-size used by the database image can be read from the 2-byte
    big-endian integer field stored at byte offset 16 of
    the database file (see section <cite>file_header</cite>). The number of
    pages in the database image can be determined by querying the size of
    the database file in bytes and then dividing by the <i>page-size</i>.
    Reading the contents of a <i>database page</i> is a simple matter of 
    reading a block of <i>page-size</i> bytes from an offset calculated from
    the page-number of the required page:
    <pre>
        <i>offset</i> := (<i>page-number</i> - 1) * page-size
</pre>
    
  <p>
    However, if there is a valid journal file corresponding to the 
    database file present within the file-system then the situation 
    is more complicated. The file-system is considered to contain a valid 
    journal file if each of the following conditions are met:

................................................................................
    for each of these is stored in the database file. Even though the contents
    of the file-system is quite different in representation 2 as in
    representation 1, the stored database image is the same in each case: 4
    pages of page-size bytes each, content A, B, C and D respectively.

    [Figure filesystem1.gif figure_filesystem1 "Two ways to store the same database image"]

  <p class=todo>
    The requirements that follow talk about "well-formed" journal sections,
    records and master-journal-pointers. There should be some kind of reference
    back to the definitions of these things. Either in the requirements
    themselves (refer to other requirements by number) or in the surrounding
    text (point to document sections). Or, better, both.

  <p>
    These requirements describe the way a database reader must determine
    whether or not there is a valid journal file within the 
    file-system.

    [fileformat_import_requirement2 H32000]
    [fileformat_import_requirement2 H32010]
................................................................................
    [fileformat_import_requirement2 H32080]

[h2 "Writing to an SQLite Database" writing_to_files]

  <p>
    When an SQLite user commits a transaction that modifies the contents
    of the database, the database representation on disk must be modified
    to reflect the new contents of the database image. In doing so, SQLite
    is required to ensure that if an application, operating system or power 
    failure occurs while updating the database file-system representation, 
    the database image stored within the file-system is found to be in a 
    valid state following recovery. If the transaction being committed to the 
    database file replaces database image A with database image B, then all
    database images equivalent to A or B are considered valid database image
    states.

  <p>
    Two database images are considered to be equivalent if each of the 
    following are true:

    <ul>
      <li> <p> The two database images have the same page-size.
      <li> <p> The two database images have the same number of pages.
      <li> <p> The content of each page in the first database image that is not
               a free-list leaf page is identical to the corresponding page in
               the second database image.
    </ul>

  <p> 
    The exception for free-list leaf pages (see section
    <cite>free_page_list</cite>) in the third bullet point above is made
    because free-list leaf pages contain no valid data and are never read
    by SQLite database readers. Since the blob of data stored on such a
    page is never read for any purpose, two database images may have a
    different blob stored on a free-list leaf page and still be considered
    equivalent. This concept can sometimes be exploited to more efficiently
    update an SQLite database file-system representation.

    [fileformat_import_requirement2 H32290]

  <p>
    The following two requirements constrain the way in which a database 
    file-system representation may be updated. In many ways, they are 
    equivalent to "do not corrupt the database file-system representation".

    [fileformat_import_requirement2 H32300]
    [fileformat_import_requirement2 H32310]

  <p>
    The following two sections, sections <cite>rollback_journal_method</cite>
    and <cite>rollforward_journal_method</cite> are somewhat advisory in nature.
    They contain descriptions of two different methods that could be used to
    modify a database image within a database file-system representation in
    accordance with the above requirements. These are not the only methods
    which could be used. So long as the above requirements (and, if applicable,
    those in section <cite>interoperability_requirements</cite>) are honoured,
    any method may be used by an SQLite database writer to update the database
    file-system representation. SQLite itself uses the "rollback-journal method"
    described in section <cite>rollback_journal_method</cite>. For this reason,
    section <cite>rollback_journal_method</cite> contains numbered requirements
    but section <cite>rollforward_journal_method</cite> does not.

  [h3 "The Rollback-Journal Method" rollback_journal_method]
  <p>
    SQLite is required 
    to do make all modifications associated with the transaction such that 
    the database image is modified atomically. If an application, OS or 
    power failure occurs while SQLite is updating the database, upon recovery 
    the contents of the database must reflect either that all modifications 
    associated with the database transaction were successfully applied, or 
    that none of the modifications were applied and the contents of the 
    database are as they were before the failed attempt to modify the database.

  <p>
    Therefore, when modifying the file-system representation of a database
    image so as to commit a transaction that modifies the database image
    from state A to state B, it must be ensured that the file-system at
    all times contains a database image in either state A or state B. And
    that if an OS or power failure occurs before, during or after any IO
    operation, following recovery the file-system must contain a database
    image in either state A or state B.

  <p class=todo>
    Should introduce requirements here - that the file-system be modified
    such that the file is always in state A or state B.

  <p>
    Some operations on a file-system may be considered atomic. For example
    deleting a file, or on some systems writing to a single disk sector.
    However, in general there exists no atomic file-system operation
    that may be used to update an SQLite database file with the effects
    of an arbitrary database transaction, which may remove, modify or
    add multiple database rows, tables or indexes. Therefore, a two stage
................................................................................
    <li> The file-system representation of the database is manipulated to
         a state where a single atomic operation may be used to transform
         the logical contents of the database from its initial state to
         the required final state.
    <li> The required atomic operation is applied.
  </ol>

  <p class=todo>
    The paragraph below is not quite accurate. Each interim state must
    correspond to either state A or state B. Not necessarily state A.
    And the above is not completely general either, for the same reason.

  <p>
    Step 1 of the above must be accomplished such that all interim states
    of the file-system correspond to the logical contents of the database
    as they were before the procedure began. This way, if an application,
    OS or power failure occurs during step 1, upon recovery the database
    contents remain unchanged. It is not possible for such a failure to
    occur "during" step 2, as step 2 consists of a single atomic operation.
................................................................................
    operation can be used to effect all required changes to the logical
    database contents.

  <p>
    The following two sub-sections describe the specific ways in which 
    SQLite achieves this for single and multiple database transactions.

  [h4 "Single Database Transactions" single_db_transactions]

  <p>
    In order to atomically modify the database image stored in the 
    file-system from database image A to database image B, the file-system must
    first be manipulated to a state where it contains the database image A,
    but can by a single atomic operation be modified to contain database 
    image B. A file-system state that has the following properties satisfies
................................................................................

    [Figure filesystem2.gif figure_filesystem2 "Interim file-system state used to atomically overwrite database image ABCD with AEC"]

  <p class=todo>
    The exception for free-list leaves.


  [h4 "Multiple Database Transactions" multi_db_transactions]

  <p class=todo>
    Deleting the master-journal is used as the atomic operation.

  [h3 "The Rollforward-Journal Method" rollforward_journal_method]

    <p class=todo>
      Describe the how the journal file can also be used as a roll 
      forward journal or "transaction log". This section does not 
      contain requirements.


[h1 "SQLite Interoperabilty Requirements" interoperability_requirements]

  [h2 "SQLite Locking Protocol" locking_protocol]

    <p>
      Basic rules:

    [fileformat_import_requirement2 H33000]
    [fileformat_import_requirement2 H33020]

    <p>
      Special requirement for RESERVED locks:

    [fileformat_import_requirement2 H33010]
    [fileformat_import_requirement2 H33030]
  

  [h2 "SQLite Database Header Cookie Protocol" database_header_cookies_protocol]

  <p class=todo>





    The following need to take into account (a) integer overflow and (b)
    exclusive-locking mode.

    [fileformat_import_requirement2 H33040]
    [fileformat_import_requirement2 H33050]



[h1 References]

  <table id="refs" style="width:auto; margin: 1em 5ex">
    <tr><td style="width:5ex" id="ref_comer_btree">\[1\]<td>
     Douglas Comer, <u>Ubiquitous B-Tree</u>, ACM Computing Surveys (CSUR),
     v.11 n.2, pages 121-137, June 1979.

Changes to req/hlr30000.txt.

as an 8-bit unsigned integer, starting at offset 4 of the buffer and continuing
until offset (buffer-size - 16) (the 17th last byte of the buffer).



HLR H32210
A buffer shall be considered to contain a well-formed journal section 
record if it is not excluded from this category by requirements H32220,
H32230 or H32240.

HLR H32220
A buffer shall only be considered to contain a well-formed journal section 
if the first 28 bytes of it contain a well-formed journal header.

HLR H32230
A buffer shall only be considered to contain a well-formed journal section 
................................................................................
A journal record shall only be considered a valid journal record if the journal
section to which it belongs begins with a well-formed journal header.

HLR H32280
A journal record shall only be considered a valid journal record if all journal
sections that occur before the journal section containing the journal record
are well-formed journal sections.








|
|







 







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

as an 8-bit unsigned integer, starting at offset 4 of the buffer and continuing
until offset (buffer-size - 16) (the 17th last byte of the buffer).



HLR H32210
A buffer shall be considered to contain a well-formed journal section 
if it is not excluded from this category by requirements H32220, H32230 or
H32240.

HLR H32220
A buffer shall only be considered to contain a well-formed journal section 
if the first 28 bytes of it contain a well-formed journal header.

HLR H32230
A buffer shall only be considered to contain a well-formed journal section 
................................................................................
A journal record shall only be considered a valid journal record if the journal
section to which it belongs begins with a well-formed journal header.

HLR H32280
A journal record shall only be considered a valid journal record if all journal
sections that occur before the journal section containing the journal record
are well-formed journal sections.

HLR H32290
Two database images shall be considered to be equivalent if they (a) have the
same page size, (b) contain the same number of pages and (c) the content of
each page of the first database image that is not a free-list leaf page is
the same as the content of the corresponding page in the second database image.

HLR H32300
When writing to an SQLite database file-system representation in order to 
replace database image A with database image B, the file-system representation
shall at all times contain a database image equivalent to either A or B.

HLR H32310
If, while writing to an SQLite database file-system representation in 
order to replace database image A with database image B, an operating
system or power failure should occur, then following recovery the database
file-system representation shall contain a database image equivalent to
either A or B.





HLR H33000
Before reading from a database file or journal file, a database
reader shall establish a SHARED or greater lock on the database file.

HLR H33010
Before writing to a journal file, a database writer shall establish
a RESERVED or greater lock on the database file.

HLR H33020
Before writing to a database file, a database writer shall establish
an EXCLUSIVE lock on the database file.

HLR H33030
Before establishing a RESERVED or PENDING lock on a database file, a 
database writer shall ensure that the database file contains a valid 
database image.


HLR H33040
When updating a database image stored within a file-system, a database writer
shall ensure that the database header change-counter field in the updated
database image is larger than the same value in the original database image.

HLR H33050
When updating a database image stored within a file-system such that the
contents of the schema table is changed, a database writer shall ensure that
the database header schema-cookie field in the updated database image is larger
than the same value in the original database image.