Documentation Source Text

<title>The SQLite R*Tree Module</title>
<tcl>hd_keywords *rtree *RTREE {R-Tree extension} {R-Trees}</tcl>
<h1 align="center">The SQLite R*Tree Module</h1>

<h2>1.0 Overview</h2>

<p>
An [http://en.wikipedia.org/wiki/R-tree | R-Tree] is a special
index that is designed for doing range queries.  R-Trees are most commonly
used in geospatial systems where each entry is a rectangle with minimum and
maximum X and Y coordinates.  Given a query rectangle, an R-Tree is able
to quickly find all entries that are contained within the query rectangle
................................................................................
The implementation found in SQLite is a refinement of Guttman's original
idea, commonly called "R*Trees", that was described by
Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger:
<em>The R*-Tree: An Efficient and Robust Access Method for Points
and Rectangles.</em> SIGMOD Conference 1990: 322-331.
</p>

<h2>2.0 Compiling The R*Tree Module</h2>

<p>
The source code to the SQLite R*Tree module is included as part
of the [amalgamation] but is disabled by default.  To enable the
R*Tree module, simply compile with the [SQLITE_ENABLE_RTREE] 
C-preprocessor macro defined.  With many compilers, this is accomplished
by adding the option "-DSQLITE_ENABLE_RTREE=1" to the compiler
command-line.
</p>

<h2>3.0 Using the R*Tree Module</h2>

<p>
The SQLite R*Tree module is implemented as a
[sqlite3_create_module | virtual table].  ^Each R*Tree index is a
virtual table with an odd number of columns between 3 and 11.
^The first column is always a 64-bit signed integer primary key.
^The other columns are pairs, one pair per dimension, containing the
................................................................................
"rtree" virtual tables or as 32-bit signed integers in "rtree_i32" virtual
tables.  ^Unlike regular SQLite tables which can store data in a variety of
datatypes and formats, the R*Tree rigidly enforce these storage types. 
If any other type of value is inserted into such a column, the r-tree
module silently converts it to the required type before writing the
new record to the database.

<h3>3.1 Creating An R*Tree Index</h3>

^(<p>
A new R*Tree index is created as follows:
</p>

<blockquote><pre>
CREATE VIRTUAL TABLE <em>&lt;name&gt;</em> USING rtree(<em>&lt;column-names&gt;</em>);
................................................................................
CREATE VIRTUAL TABLE demo_index USING rtree(
   id,              -- Integer primary key
   minX, maxX,      -- Minimum and maximum X coordinate
   minY, maxY       -- Minimum and maximum Y coordinate
);
</pre></blockquote>)^

<h3>3.2 Populating An R*Tree Index</h3>

<p>
^The usual [INSERT], [UPDATE], and [DELETE] commands work on an R*Tree
index just like on regular tables.  ^(So to insert some data into our sample
R*Tree index, we can do something like this:
</p>

................................................................................
<p>
The entries above might represent (for example) a bounding box around
the main office for SQLite.org and bounding box around the
12th Congressional District of North Carolina (prior to the 2011
redistricting) in which SQLite.org was located.  
</p>

<h3>3.3 Querying An R*Tree Index</h3>

<p>
^Any valid query will work against an R*Tree index.  But the R*Tree
implementation is designed to make two kinds of queries especially
efficient.  ^(First, queries against the primary key are efficient:
</p>

................................................................................

<p>
But, generally speaking, the more constraints that the R*Tree module
has to work with, and the smaller the bounding box, the faster the
results will come back.
</p>

<h3>3.3 Roundoff Error</h3>

<p>
By default, coordinates are stored in an R*Tree using 32-bit floating
point values.  When a coordinate cannot be exactly represented by a
32-bit floating point number, the lower-bound coordinates are rounded down
and the upper-bound coordinates are rounded up.  Thus, bounding boxes might
be slightly larger than specified, but will never be any smaller.  This
................................................................................
<p>However, for a "contained-within" style query, rounding the bounding
boxes outward might cause some entries to be excluded from the result set
if the edge of the entry bounding box corresponds to the edge of the query
bounding box.  To guard against this, applications should expand their
contained-within query boxes slightly (by 0.000012%) by rounding down the
lower coordinates and rounding up the top coordinates, in each dimension.

<h2>4.0 Using R*Trees Effectively</h2>

<p>
The only information that an R*Tree index stores about an object is
its integer ID and its bounding box.  Additional information needs to
be stored in separate tables and related to the R*Tree index using
the primary key.  ^(For the example above, one might create an auxiliary
table as follows:
................................................................................
contained_in() function to millions of entries in the demo_data table.
The use of the R*Tree in the penultimate query reduces the number of
calls to contained_in() function to a small subset of the entire table.
The R*Tree index did not find the exact answer itself, it merely
limited the search space.</p>

<tcl>hd_fragment {intrtree} {integer-valued r-trees}</tcl>
<h2>5.0 Integer-Valued R-Trees</h2>

<p>
The default virtual table ("rtree") normally stores coordinates as
single-precision (4-byte) floating point numbers.  If integer coordinates
are desired, declare the table using "rtree_i32" instead:

<blockquote><pre>
................................................................................
it might be desirable to have a pure integer implementation of r-trees.
This is accomplished by compiling with the [SQLITE_RTREE_INT_ONLY] option.
When SQLITE_RTREE_INT_ONLY is used, both the "rtree" and the "rtree_i32"
virtual tables store 32-bit integers and only integer values are used for
internal computations.

<tcl>hd_fragment {customquery} {custom r-tree queries}</tcl>
<h2>6.0 Custom R-Tree Queries</h2>

<p>By using standard SQL expressions in the WHERE clause of a SELECT query,
a programmer can query for all R*Tree entries that have a spatial relationship
(they intersect with or are contained within) a particular bounding-box.
Custom R*Tree queries, using the MATCH
operator in the WHERE clause of a SELECT, allow the programmer to query for 
the set of R*Tree entries that intersect any arbitrary region or shape, not 
................................................................................
</blockquote></pre>)^

<p>^The SQL syntax for custom queries is the same regardless of which
interface, sqlite3_rtree_geometry_callback() or sqlite3_rtree_query_callback(),
is used to register the SQL function.  However, the newer query-style
callbacks give the application greater control over how the query proceeds.

<h3>6.1 The Legacy xGeom Callback</h3>

<p>^The legacy xGeom callback is invoked with four arguments.  ^The first
argument is a pointer to an sqlite3_rtree_geometry structure which provides
information about how the SQL function was invoked.  ^The second argument
is the number of coordinates in each r-tree entry, and is always the same
for any given R*Tree.  ^The number of coordinates is 2 for a 1-dimensional R*Tree,
4 for a 2-dimensional R*Tree, 6 for a 3-dimensional R*Tree, and so forth.
................................................................................
value of the pUser variable as the only argument. In other words, xDelUser
may be set to a destructor function for the pUser value.

<p>^The xGeom callback always does a depth-first search of the r-tree.

<tcl>hd_fragment xquery {xQueryFunc R*Tree callback} {sqlite3_rtree_query_callback}
</tcl>
<h3>6.2 The New xQueryFunc Callback</h3>

<p>The newer xQueryFunc callback receives more information from the r-tree
query engine on each call, and it sends more information back to the query engine
before it returns.
To help keep the interface manageable, the xQueryFunc callback sends and receives
information from the query engine as fields in the
sqlite3_rtree_query_info structure:
................................................................................
is the rowid (the first of the 3 to 11 columns in the R*Tree) for the element
being considered.  iRowid is only valid for leaves.)^  ^The eParentWithin and
rParentScore values are copies of the eWithin and rScore values from the
containing subtree of the current row.  ^The anQueue field is an array
of mxLevel+1 unsigned integers that tell the current number of elements in
the priority queue at each level.

<h3>6.3 Additional Considerations for Custom Queries</h3>

<p>
^The MATCH operator of a custom R*Tree query function must be a top-level
AND-connected term of the WHERE clause, or else it will not be usable
by the R*Tree query optimizer and the query will not be runnable.
^If the MATCH operator is connected to other terms of the WHERE clause 
via an OR operator, for example, the query will fail with an error.

<title>The SQLite R*Tree Module</title>
<tcl>hd_keywords *rtree *RTREE {R-Tree extension} {R-Trees}</tcl>
<table_of_contents>

<h1>Overview</h1>

<p>
An [http://en.wikipedia.org/wiki/R-tree | R-Tree] is a special
index that is designed for doing range queries.  R-Trees are most commonly
used in geospatial systems where each entry is a rectangle with minimum and
maximum X and Y coordinates.  Given a query rectangle, an R-Tree is able
to quickly find all entries that are contained within the query rectangle
................................................................................
The implementation found in SQLite is a refinement of Guttman's original
idea, commonly called "R*Trees", that was described by
Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger:
<em>The R*-Tree: An Efficient and Robust Access Method for Points
and Rectangles.</em> SIGMOD Conference 1990: 322-331.
</p>

<h1>Compiling The R*Tree Module</h1>

<p>
The source code to the SQLite R*Tree module is included as part
of the [amalgamation] but is disabled by default.  To enable the
R*Tree module, simply compile with the [SQLITE_ENABLE_RTREE] 
C-preprocessor macro defined.  With many compilers, this is accomplished
by adding the option "-DSQLITE_ENABLE_RTREE=1" to the compiler
command-line.
</p>

<h1>Using the R*Tree Module</h1>

<p>
The SQLite R*Tree module is implemented as a
[sqlite3_create_module | virtual table].  ^Each R*Tree index is a
virtual table with an odd number of columns between 3 and 11.
^The first column is always a 64-bit signed integer primary key.
^The other columns are pairs, one pair per dimension, containing the
................................................................................
"rtree" virtual tables or as 32-bit signed integers in "rtree_i32" virtual
tables.  ^Unlike regular SQLite tables which can store data in a variety of
datatypes and formats, the R*Tree rigidly enforce these storage types. 
If any other type of value is inserted into such a column, the r-tree
module silently converts it to the required type before writing the
new record to the database.

<h2>Creating An R*Tree Index</h2>

^(<p>
A new R*Tree index is created as follows:
</p>

<blockquote><pre>
CREATE VIRTUAL TABLE <em>&lt;name&gt;</em> USING rtree(<em>&lt;column-names&gt;</em>);
................................................................................
CREATE VIRTUAL TABLE demo_index USING rtree(
   id,              -- Integer primary key
   minX, maxX,      -- Minimum and maximum X coordinate
   minY, maxY       -- Minimum and maximum Y coordinate
);
</pre></blockquote>)^

<h2>Populating An R*Tree Index</h2>

<p>
^The usual [INSERT], [UPDATE], and [DELETE] commands work on an R*Tree
index just like on regular tables.  ^(So to insert some data into our sample
R*Tree index, we can do something like this:
</p>

................................................................................
<p>
The entries above might represent (for example) a bounding box around
the main office for SQLite.org and bounding box around the
12th Congressional District of North Carolina (prior to the 2011
redistricting) in which SQLite.org was located.  
</p>

<h2>Querying An R*Tree Index</h2>

<p>
^Any valid query will work against an R*Tree index.  But the R*Tree
implementation is designed to make two kinds of queries especially
efficient.  ^(First, queries against the primary key are efficient:
</p>

................................................................................

<p>
But, generally speaking, the more constraints that the R*Tree module
has to work with, and the smaller the bounding box, the faster the
results will come back.
</p>

<h2>Roundoff Error</h2>

<p>
By default, coordinates are stored in an R*Tree using 32-bit floating
point values.  When a coordinate cannot be exactly represented by a
32-bit floating point number, the lower-bound coordinates are rounded down
and the upper-bound coordinates are rounded up.  Thus, bounding boxes might
be slightly larger than specified, but will never be any smaller.  This
................................................................................
<p>However, for a "contained-within" style query, rounding the bounding
boxes outward might cause some entries to be excluded from the result set
if the edge of the entry bounding box corresponds to the edge of the query
bounding box.  To guard against this, applications should expand their
contained-within query boxes slightly (by 0.000012%) by rounding down the
lower coordinates and rounding up the top coordinates, in each dimension.

<h1>Using R*Trees Effectively</h1>

<p>
The only information that an R*Tree index stores about an object is
its integer ID and its bounding box.  Additional information needs to
be stored in separate tables and related to the R*Tree index using
the primary key.  ^(For the example above, one might create an auxiliary
table as follows:
................................................................................
contained_in() function to millions of entries in the demo_data table.
The use of the R*Tree in the penultimate query reduces the number of
calls to contained_in() function to a small subset of the entire table.
The R*Tree index did not find the exact answer itself, it merely
limited the search space.</p>

<tcl>hd_fragment {intrtree} {integer-valued r-trees}</tcl>
<h1>Integer-Valued R-Trees</h1>

<p>
The default virtual table ("rtree") normally stores coordinates as
single-precision (4-byte) floating point numbers.  If integer coordinates
are desired, declare the table using "rtree_i32" instead:

<blockquote><pre>
................................................................................
it might be desirable to have a pure integer implementation of r-trees.
This is accomplished by compiling with the [SQLITE_RTREE_INT_ONLY] option.
When SQLITE_RTREE_INT_ONLY is used, both the "rtree" and the "rtree_i32"
virtual tables store 32-bit integers and only integer values are used for
internal computations.

<tcl>hd_fragment {customquery} {custom r-tree queries}</tcl>
<h1>Custom R-Tree Queries</h1>

<p>By using standard SQL expressions in the WHERE clause of a SELECT query,
a programmer can query for all R*Tree entries that have a spatial relationship
(they intersect with or are contained within) a particular bounding-box.
Custom R*Tree queries, using the MATCH
operator in the WHERE clause of a SELECT, allow the programmer to query for 
the set of R*Tree entries that intersect any arbitrary region or shape, not 
................................................................................
</blockquote></pre>)^

<p>^The SQL syntax for custom queries is the same regardless of which
interface, sqlite3_rtree_geometry_callback() or sqlite3_rtree_query_callback(),
is used to register the SQL function.  However, the newer query-style
callbacks give the application greater control over how the query proceeds.

<h2>The Legacy xGeom Callback</h2>

<p>^The legacy xGeom callback is invoked with four arguments.  ^The first
argument is a pointer to an sqlite3_rtree_geometry structure which provides
information about how the SQL function was invoked.  ^The second argument
is the number of coordinates in each r-tree entry, and is always the same
for any given R*Tree.  ^The number of coordinates is 2 for a 1-dimensional R*Tree,
4 for a 2-dimensional R*Tree, 6 for a 3-dimensional R*Tree, and so forth.
................................................................................
value of the pUser variable as the only argument. In other words, xDelUser
may be set to a destructor function for the pUser value.

<p>^The xGeom callback always does a depth-first search of the r-tree.

<tcl>hd_fragment xquery {xQueryFunc R*Tree callback} {sqlite3_rtree_query_callback}
</tcl>
<h2>The New xQueryFunc Callback</h2>

<p>The newer xQueryFunc callback receives more information from the r-tree
query engine on each call, and it sends more information back to the query engine
before it returns.
To help keep the interface manageable, the xQueryFunc callback sends and receives
information from the query engine as fields in the
sqlite3_rtree_query_info structure:
................................................................................
is the rowid (the first of the 3 to 11 columns in the R*Tree) for the element
being considered.  iRowid is only valid for leaves.)^  ^The eParentWithin and
rParentScore values are copies of the eWithin and rScore values from the
containing subtree of the current row.  ^The anQueue field is an array
of mxLevel+1 unsigned integers that tell the current number of elements in
the priority queue at each level.

<h2>Additional Considerations for Custom Queries</h2>

<p>
^The MATCH operator of a custom R*Tree query function must be a top-level
AND-connected term of the WHERE clause, or else it will not be usable
by the R*Tree query optimizer and the query will not be runnable.
^If the MATCH operator is connected to other terms of the WHERE clause 
via an OR operator, for example, the query will fail with an error.