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 Unified Diffs Show Whitespace Changes Patch

Changes to pages/rtree.in.

570
571
572
573
574
575
576
577


578

















579
580
581
582
583
584
585





































<p>
The following sections describe some low-level details of the R*Tree implementation,
that might be useful for trouble-shooting or performance analysis.

<h2>Shadow Tables</h2>

<p><i>TBD</i>




















<tcl>hd_fragment rtreecheck rtreecheck()</tcl>
<h2>Integrity Check using the rtreecheck() SQL function</h2>

<p>The scalar SQL function rtreecheck(R) or rtreecheck(S,R) runs an
integrity check on the rtree table named R containing in database S.
The function returns a human-language description of any problems found,
or the string 'ok' if everything is ok.











































|
>
>

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






|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640

<p>
The following sections describe some low-level details of the R*Tree implementation,
that might be useful for trouble-shooting or performance analysis.

<h2>Shadow Tables</h2>

<p>The content of an R*Tree index is actually stored in three ordinary
SQLite tables with names derived from the name of the R*Tree.  These
three tables are called "shadow tables".  This is their schema:

<codeblock>
CREATE TABLE %_node(nodeno INTEGER PRIMARY KEY, data BLOB)
CREATE TABLE %_parent(nodeno INTEGER PRIMARY KEY, parentnode INTEGER)
CREATE TABLE %_rowid(rowid INTEGER PRIMARY KEY, nodeno INTEGER)
</codeblock>

<p>The "%" in the name of each shadow table is replaced by the name of the
R*Tree virtual table.  So, if the name of the R*Tree table is "xyz" then
the three shadow tables would be "xyz_node", "xyz_parent", and "xyz_rowid".

<p>There is one entry in the %_node table for each R*Tree node.  An
R*Tree node consists of one or more entries that are proximate to one another.
The nodes of an R*Tree for a tree.  All nodes other than the root have an
entry in the %_parent shadow table that identifies the parent node.
Each entry in an R*Tree has a rowid.  The %_rowid shadow table maps entry
rowids to the node that contains that entry.

<tcl>hd_fragment rtreecheck rtreecheck()</tcl>
<h2>Integrity Check using the rtreecheck() SQL function</h2>

<p>The scalar SQL function rtreecheck(R) or rtreecheck(S,R) runs an
integrity check on the rtree table named R containing in database S.
The function returns a human-language description of any problems found,
or the string 'ok' if everything is ok.  Running rtreecheck() on an R*Tree
virtual table is similar to running [PRAGMA integrity_check] on an
database.

<p>Example: To verify that an R*Tree named "demo_index" is well-formed
and internally consistent, run:

<codeblock>
SELECT rtreecheck('demo_index');
</codeblock>

<p>The rtreecheck() function performs the following checks:

<ol>
<li><p>
For each cell in the r-tree structure (%_node table), that:
<ol type=a>
<li><p> for each dimension, (coord1 &lt;= coord2).
<li><p> unless the cell is on the root node, that the cell is bounded
        by the parent cell on the parent node.
<li><p> for leaf nodes, that there is an entry in the %_rowid 
        table corresponding to the cell's rowid value that 
        points to the correct node.
<li><p> for cells on non-leaf nodes, that there is an entry in the 
        %_parent table mapping from the cell's child node to the
        node that it resides on.
</ol>
<li><p>
That there are the same number of entries in the %_rowid table
as there are leaf cells in the r-tree structure, and that there
is a leaf cell that corresponds to each entry in the %_rowid table.
<li><p>
That there are the same number of entries in the %_parent table
as there are non-leaf cells in the r-tree structure, and that 
there is a non-leaf cell that corresponds to each entry in the 
%_parent table.
</ol>