Documentation Source Text

Check-in [cb9d13f931]
Login

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

Overview
Comment:Convert the RTree documentation to fancy-format.
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: cb9d13f9313bb61e01e8f81df58c51b150156ba4
User & Date: drh 2016-07-13 14:17:01
Context
2016-07-15
02:59
Fix typo in the when-to-use document. check-in: faf1f46a56 user: drh tags: trunk
2016-07-13
14:17
Convert the RTree documentation to fancy-format. check-in: cb9d13f931 user: drh tags: trunk
13:57
Add documentation on the dbhash.exe utility and an entry in the change-log. check-in: f80207b028 user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to pages/rtree.in.

     1      1   <title>The SQLite R*Tree Module</title>
     2      2   <tcl>hd_keywords *rtree *RTREE {R-Tree extension} {R-Trees}</tcl>
     3         -<h1 align="center">The SQLite R*Tree Module</h1>
            3  +<table_of_contents>
     4      4   
     5         -<h2>1.0 Overview</h2>
            5  +<h1>Overview</h1>
     6      6   
     7      7   <p>
     8      8   An [http://en.wikipedia.org/wiki/R-tree | R-Tree] is a special
     9      9   index that is designed for doing range queries.  R-Trees are most commonly
    10     10   used in geospatial systems where each entry is a rectangle with minimum and
    11     11   maximum X and Y coordinates.  Given a query rectangle, an R-Tree is able
    12     12   to quickly find all entries that are contained within the query rectangle
................................................................................
    29     29   The implementation found in SQLite is a refinement of Guttman's original
    30     30   idea, commonly called "R*Trees", that was described by
    31     31   Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger:
    32     32   <em>The R*-Tree: An Efficient and Robust Access Method for Points
    33     33   and Rectangles.</em> SIGMOD Conference 1990: 322-331.
    34     34   </p>
    35     35   
    36         -<h2>2.0 Compiling The R*Tree Module</h2>
           36  +<h1>Compiling The R*Tree Module</h1>
    37     37   
    38     38   <p>
    39     39   The source code to the SQLite R*Tree module is included as part
    40     40   of the [amalgamation] but is disabled by default.  To enable the
    41     41   R*Tree module, simply compile with the [SQLITE_ENABLE_RTREE] 
    42     42   C-preprocessor macro defined.  With many compilers, this is accomplished
    43     43   by adding the option "-DSQLITE_ENABLE_RTREE=1" to the compiler
    44     44   command-line.
    45     45   </p>
    46     46   
    47         -<h2>3.0 Using the R*Tree Module</h2>
           47  +<h1>Using the R*Tree Module</h1>
    48     48   
    49     49   <p>
    50     50   The SQLite R*Tree module is implemented as a
    51     51   [sqlite3_create_module | virtual table].  ^Each R*Tree index is a
    52     52   virtual table with an odd number of columns between 3 and 11.
    53     53   ^The first column is always a 64-bit signed integer primary key.
    54     54   ^The other columns are pairs, one pair per dimension, containing the
................................................................................
    74     74   "rtree" virtual tables or as 32-bit signed integers in "rtree_i32" virtual
    75     75   tables.  ^Unlike regular SQLite tables which can store data in a variety of
    76     76   datatypes and formats, the R*Tree rigidly enforce these storage types. 
    77     77   If any other type of value is inserted into such a column, the r-tree
    78     78   module silently converts it to the required type before writing the
    79     79   new record to the database.
    80     80   
    81         -<h3>3.1 Creating An R*Tree Index</h3>
           81  +<h2>Creating An R*Tree Index</h2>
    82     82   
    83     83   ^(<p>
    84     84   A new R*Tree index is created as follows:
    85     85   </p>
    86     86   
    87     87   <blockquote><pre>
    88     88   CREATE VIRTUAL TABLE <em>&lt;name&gt;</em> USING rtree(<em>&lt;column-names&gt;</em>);
................................................................................
   121    121   CREATE VIRTUAL TABLE demo_index USING rtree(
   122    122      id,              -- Integer primary key
   123    123      minX, maxX,      -- Minimum and maximum X coordinate
   124    124      minY, maxY       -- Minimum and maximum Y coordinate
   125    125   );
   126    126   </pre></blockquote>)^
   127    127   
   128         -<h3>3.2 Populating An R*Tree Index</h3>
          128  +<h2>Populating An R*Tree Index</h2>
   129    129   
   130    130   <p>
   131    131   ^The usual [INSERT], [UPDATE], and [DELETE] commands work on an R*Tree
   132    132   index just like on regular tables.  ^(So to insert some data into our sample
   133    133   R*Tree index, we can do something like this:
   134    134   </p>
   135    135   
................................................................................
   149    149   <p>
   150    150   The entries above might represent (for example) a bounding box around
   151    151   the main office for SQLite.org and bounding box around the
   152    152   12th Congressional District of North Carolina (prior to the 2011
   153    153   redistricting) in which SQLite.org was located.  
   154    154   </p>
   155    155   
   156         -<h3>3.3 Querying An R*Tree Index</h3>
          156  +<h2>Querying An R*Tree Index</h2>
   157    157   
   158    158   <p>
   159    159   ^Any valid query will work against an R*Tree index.  But the R*Tree
   160    160   implementation is designed to make two kinds of queries especially
   161    161   efficient.  ^(First, queries against the primary key are efficient:
   162    162   </p>
   163    163   
................................................................................
   215    215   
   216    216   <p>
   217    217   But, generally speaking, the more constraints that the R*Tree module
   218    218   has to work with, and the smaller the bounding box, the faster the
   219    219   results will come back.
   220    220   </p>
   221    221   
   222         -<h3>3.3 Roundoff Error</h3>
          222  +<h2>Roundoff Error</h2>
   223    223   
   224    224   <p>
   225    225   By default, coordinates are stored in an R*Tree using 32-bit floating
   226    226   point values.  When a coordinate cannot be exactly represented by a
   227    227   32-bit floating point number, the lower-bound coordinates are rounded down
   228    228   and the upper-bound coordinates are rounded up.  Thus, bounding boxes might
   229    229   be slightly larger than specified, but will never be any smaller.  This
................................................................................
   237    237   <p>However, for a "contained-within" style query, rounding the bounding
   238    238   boxes outward might cause some entries to be excluded from the result set
   239    239   if the edge of the entry bounding box corresponds to the edge of the query
   240    240   bounding box.  To guard against this, applications should expand their
   241    241   contained-within query boxes slightly (by 0.000012%) by rounding down the
   242    242   lower coordinates and rounding up the top coordinates, in each dimension.
   243    243   
   244         -<h2>4.0 Using R*Trees Effectively</h2>
          244  +<h1>Using R*Trees Effectively</h1>
   245    245   
   246    246   <p>
   247    247   The only information that an R*Tree index stores about an object is
   248    248   its integer ID and its bounding box.  Additional information needs to
   249    249   be stored in separate tables and related to the R*Tree index using
   250    250   the primary key.  ^(For the example above, one might create an auxiliary
   251    251   table as follows:
................................................................................
   322    322   contained_in() function to millions of entries in the demo_data table.
   323    323   The use of the R*Tree in the penultimate query reduces the number of
   324    324   calls to contained_in() function to a small subset of the entire table.
   325    325   The R*Tree index did not find the exact answer itself, it merely
   326    326   limited the search space.</p>
   327    327   
   328    328   <tcl>hd_fragment {intrtree} {integer-valued r-trees}</tcl>
   329         -<h2>5.0 Integer-Valued R-Trees</h2>
          329  +<h1>Integer-Valued R-Trees</h1>
   330    330   
   331    331   <p>
   332    332   The default virtual table ("rtree") normally stores coordinates as
   333    333   single-precision (4-byte) floating point numbers.  If integer coordinates
   334    334   are desired, declare the table using "rtree_i32" instead:
   335    335   
   336    336   <blockquote><pre>
................................................................................
   344    344   it might be desirable to have a pure integer implementation of r-trees.
   345    345   This is accomplished by compiling with the [SQLITE_RTREE_INT_ONLY] option.
   346    346   When SQLITE_RTREE_INT_ONLY is used, both the "rtree" and the "rtree_i32"
   347    347   virtual tables store 32-bit integers and only integer values are used for
   348    348   internal computations.
   349    349   
   350    350   <tcl>hd_fragment {customquery} {custom r-tree queries}</tcl>
   351         -<h2>6.0 Custom R-Tree Queries</h2>
          351  +<h1>Custom R-Tree Queries</h1>
   352    352   
   353    353   <p>By using standard SQL expressions in the WHERE clause of a SELECT query,
   354    354   a programmer can query for all R*Tree entries that have a spatial relationship
   355    355   (they intersect with or are contained within) a particular bounding-box.
   356    356   Custom R*Tree queries, using the MATCH
   357    357   operator in the WHERE clause of a SELECT, allow the programmer to query for 
   358    358   the set of R*Tree entries that intersect any arbitrary region or shape, not 
................................................................................
   401    401   </blockquote></pre>)^
   402    402   
   403    403   <p>^The SQL syntax for custom queries is the same regardless of which
   404    404   interface, sqlite3_rtree_geometry_callback() or sqlite3_rtree_query_callback(),
   405    405   is used to register the SQL function.  However, the newer query-style
   406    406   callbacks give the application greater control over how the query proceeds.
   407    407   
   408         -<h3>6.1 The Legacy xGeom Callback</h3>
          408  +<h2>The Legacy xGeom Callback</h2>
   409    409   
   410    410   <p>^The legacy xGeom callback is invoked with four arguments.  ^The first
   411    411   argument is a pointer to an sqlite3_rtree_geometry structure which provides
   412    412   information about how the SQL function was invoked.  ^The second argument
   413    413   is the number of coordinates in each r-tree entry, and is always the same
   414    414   for any given R*Tree.  ^The number of coordinates is 2 for a 1-dimensional R*Tree,
   415    415   4 for a 2-dimensional R*Tree, 6 for a 3-dimensional R*Tree, and so forth.
................................................................................
   460    460   value of the pUser variable as the only argument. In other words, xDelUser
   461    461   may be set to a destructor function for the pUser value.
   462    462   
   463    463   <p>^The xGeom callback always does a depth-first search of the r-tree.
   464    464   
   465    465   <tcl>hd_fragment xquery {xQueryFunc R*Tree callback} {sqlite3_rtree_query_callback}
   466    466   </tcl>
   467         -<h3>6.2 The New xQueryFunc Callback</h3>
          467  +<h2>The New xQueryFunc Callback</h2>
   468    468   
   469    469   <p>The newer xQueryFunc callback receives more information from the r-tree
   470    470   query engine on each call, and it sends more information back to the query engine
   471    471   before it returns.
   472    472   To help keep the interface manageable, the xQueryFunc callback sends and receives
   473    473   information from the query engine as fields in the
   474    474   sqlite3_rtree_query_info structure:
................................................................................
   552    552   is the rowid (the first of the 3 to 11 columns in the R*Tree) for the element
   553    553   being considered.  iRowid is only valid for leaves.)^  ^The eParentWithin and
   554    554   rParentScore values are copies of the eWithin and rScore values from the
   555    555   containing subtree of the current row.  ^The anQueue field is an array
   556    556   of mxLevel+1 unsigned integers that tell the current number of elements in
   557    557   the priority queue at each level.
   558    558   
   559         -<h3>6.3 Additional Considerations for Custom Queries</h3>
          559  +<h2>Additional Considerations for Custom Queries</h2>
   560    560   
   561    561   <p>
   562    562   ^The MATCH operator of a custom R*Tree query function must be a top-level
   563    563   AND-connected term of the WHERE clause, or else it will not be usable
   564    564   by the R*Tree query optimizer and the query will not be runnable.
   565    565   ^If the MATCH operator is connected to other terms of the WHERE clause 
   566    566   via an OR operator, for example, the query will fail with an error.