Documentation Source Text

Check-in [2ccafeedbe]
Login

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

Overview
Comment:Flesh out the description of shadow tables and the rtreecheck() function in the R*Tree documentation.
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256: 2ccafeedbe9ffde64cdb42a23983246de9523fec6d32c64cda9ab686d60d6482
User & Date: drh 2018-01-04 19:10:11
Context
2018-01-04
19:28
Documentation on the sqlite_offset() SQL function. check-in: 4ce0a400c2 user: drh tags: trunk
19:10
Flesh out the description of shadow tables and the rtreecheck() function in the R*Tree documentation. check-in: 2ccafeedbe user: drh tags: trunk
16:41
Fix broken documentation hyperlinks. check-in: dfa0a34e07 user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to pages/rtree.in.

   570    570   
   571    571   <p>
   572    572   The following sections describe some low-level details of the R*Tree implementation,
   573    573   that might be useful for trouble-shooting or performance analysis.
   574    574   
   575    575   <h2>Shadow Tables</h2>
   576    576   
   577         -<p><i>TBD</i>
          577  +<p>The content of an R*Tree index is actually stored in three ordinary
          578  +SQLite tables with names derived from the name of the R*Tree.  These
          579  +three tables are called "shadow tables".  This is their schema:
          580  +
          581  +<codeblock>
          582  +CREATE TABLE %_node(nodeno INTEGER PRIMARY KEY, data BLOB)
          583  +CREATE TABLE %_parent(nodeno INTEGER PRIMARY KEY, parentnode INTEGER)
          584  +CREATE TABLE %_rowid(rowid INTEGER PRIMARY KEY, nodeno INTEGER)
          585  +</codeblock>
          586  +
          587  +<p>The "%" in the name of each shadow table is replaced by the name of the
          588  +R*Tree virtual table.  So, if the name of the R*Tree table is "xyz" then
          589  +the three shadow tables would be "xyz_node", "xyz_parent", and "xyz_rowid".
          590  +
          591  +<p>There is one entry in the %_node table for each R*Tree node.  An
          592  +R*Tree node consists of one or more entries that are proximate to one another.
          593  +The nodes of an R*Tree for a tree.  All nodes other than the root have an
          594  +entry in the %_parent shadow table that identifies the parent node.
          595  +Each entry in an R*Tree has a rowid.  The %_rowid shadow table maps entry
          596  +rowids to the node that contains that entry.
   578    597   
   579    598   <tcl>hd_fragment rtreecheck rtreecheck()</tcl>
   580    599   <h2>Integrity Check using the rtreecheck() SQL function</h2>
   581    600   
   582    601   <p>The scalar SQL function rtreecheck(R) or rtreecheck(S,R) runs an
   583    602   integrity check on the rtree table named R containing in database S.
   584    603   The function returns a human-language description of any problems found,
   585         -or the string 'ok' if everything is ok.
          604  +or the string 'ok' if everything is ok.  Running rtreecheck() on an R*Tree
          605  +virtual table is similar to running [PRAGMA integrity_check] on an
          606  +database.
          607  +
          608  +<p>Example: To verify that an R*Tree named "demo_index" is well-formed
          609  +and internally consistent, run:
          610  +
          611  +<codeblock>
          612  +SELECT rtreecheck('demo_index');
          613  +</codeblock>
          614  +
          615  +<p>The rtreecheck() function performs the following checks:
          616  +
          617  +<ol>
          618  +<li><p>
          619  +For each cell in the r-tree structure (%_node table), that:
          620  +<ol type=a>
          621  +<li><p> for each dimension, (coord1 &lt;= coord2).
          622  +<li><p> unless the cell is on the root node, that the cell is bounded
          623  +        by the parent cell on the parent node.
          624  +<li><p> for leaf nodes, that there is an entry in the %_rowid 
          625  +        table corresponding to the cell's rowid value that 
          626  +        points to the correct node.
          627  +<li><p> for cells on non-leaf nodes, that there is an entry in the 
          628  +        %_parent table mapping from the cell's child node to the
          629  +        node that it resides on.
          630  +</ol>
          631  +<li><p>
          632  +That there are the same number of entries in the %_rowid table
          633  +as there are leaf cells in the r-tree structure, and that there
          634  +is a leaf cell that corresponds to each entry in the %_rowid table.
          635  +<li><p>
          636  +That there are the same number of entries in the %_parent table
          637  +as there are non-leaf cells in the r-tree structure, and that 
          638  +there is a non-leaf cell that corresponds to each entry in the 
          639  +%_parent table.
          640  +</ol>