Documentation Source Text

<li>Report the name of specific [CHECK] constraints that fail.
<li>In the command-line shell, use popen() instead of fopen() if the first
    character of the argument to the ".output" command is "|".
<li>Make use of OVERLAPPED in the windows [VFS] to avoid some system calls
    and thereby obtain a performance improvement.
<li>More aggressive optimization of the AND operator when one side or the
    other is always false.
<li>Add the [SQLITE_RTREE_INT_ONLY] compile-time option to force the
    [rtree | R*Tree Extension Module] to use integer instead of
    floating point values for both storage and computation.
<li>Bug fix: Fix the [RELEASE] command so that it does not cancel pending
    queries.  This fixes a problem introduced in 3.7.11.

}

chng {2012 March 20 (3.7.11)} {
<li>Enhance the [INSERT] syntax to allow multiple rows to be inserted

  subject to certain operating constraints.
}

COMPILE_OPTION {SQLITE_ENABLE_RTREE} {
  This option causes SQLite to include support for the
  [rtree | R*Tree index extension].
}

COMPILE_OPTION {SQLITE_RTREE_INT_ONLY} {
  If this option is used together with [SQLITE_ENABLE_RTREE] then the
  [rtree | R*Tree extension] will only store 32-bit signed integer
  coordinates and all internal computations will be done using integers
  instead of floating point numbers.
}

COMPILE_OPTION {SQLITE_ENABLE_STAT2} {
  This option used to cause the [ANALYZE] command to collect
  index histogram data in the <b>sqlite_stat2</b> table.  But that
  functionality was superceded by [SQLITE_ENABLE_STAT3] as of
  SQLite version 3.7.9.  The SQLITE_ENABLE_STAT2 compile-time option
  is now a no-op.

<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 minimum- and maximum-value pairs (stored as

can store data in a variety of datatypes and formats, the R*Tree
indices rigidly enforce these two storage types.  ^Attempts to insert
something other than an integer into the first column, or something
other than a floating point value into the other columns, will result
in an error.
</p>

<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 offices for SQLite.org and bounding box around the
12th Congressional District of North Carolina in which SQLite.org is 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>

<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:

<p>The problem with this latter query is that it must apply the
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>
CREATE VIRTUAL TABLE intrtree USING rtree_i32(id,x0,x1,y0,y1,z0,y1);
</pre></blockquote>

<p>
An rtree_i32 stores coordinates as 32-bit signed integers.  But it still
using floating point computations internally as part of the r-tree algorithm.
For applications running on processors without hardware floating point,
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 user may query for all r-tree entries that intersect a specified
bounding-box, or for all entries that are completely encapsulated by a
specified bounding-box. Custom r-tree queries, which use the special MATCH
operator in the WHERE clause of a SELECT, allow the user to query for the set
of r-tree entries that intersect any arbitrarily defined region.