Documentation Source Text

chng {2014-06-?? (3.8.5)} {
<li>Added support for sorting subsets of the result when the result comes out of the query
    engine already partially sorted.
<li>Enhance the query planner so that it always prefers an index that uses a superset of
    WHERE clause terms relative to some other index.
<li>Added the [SQLITE_TESTCTRL_BYTEORDER] test control.

<p><b>Bug Fixes:</b>
<li>OFFSET clause ignored on queries without a FROM clause.
    Ticket [http://www.sqlite.org/src/info/07d6a0453d | 07d6a0453d]
<li>Assertion fault on queries involving expressions of the form
    "x IN (?)".  Ticket [http://www.sqlite.org/src/info/e39d032577|e39d032577].
<li>Incorrect column datatype reported.
    Ticket [http://www.sqlite.org/src/info/a8a0d2996a | a8a0d2996a]

chng {2014-06-?? (3.8.5)} {
<li>Added support for sorting subsets of the result when the result comes out of the query
    engine already partially sorted.
<li>Enhance the query planner so that it always prefers an index that uses a superset of
    WHERE clause terms relative to some other index.
<li>Added the [SQLITE_TESTCTRL_BYTEORDER] test control.
<li>Added the [sqlite3_rtree_query_callback()] interface to [R-Tree extension]
<p><b>Bug Fixes:</b>
<li>OFFSET clause ignored on queries without a FROM clause.
    Ticket [http://www.sqlite.org/src/info/07d6a0453d | 07d6a0453d]
<li>Assertion fault on queries involving expressions of the form
    "x IN (?)".  Ticket [http://www.sqlite.org/src/info/e39d032577|e39d032577].
<li>Incorrect column datatype reported.
    Ticket [http://www.sqlite.org/src/info/a8a0d2996a | a8a0d2996a]

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
or which overlap the query rectangle.  This idea is easily extended to
three dimensions for use in CAD systems.  R-Trees also find use in time-domain
range look-ups.  For example, suppose a database records the starting and
ending times for a large number of events.  A R-Tree is able to quickly
find all events, for example, that were active at any time during a given
time interval, or all events that started during a particular time interval,
or all events that both started and ended within a given time interval.
And so forth.
</p>

<p>
The R-Tree concept originated with 
................................................................................
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
32-bit floating point numbers) for each
dimension.  ^A 1-dimensional R*Tree thus has 3 columns.  
^A 2-dimensional R*Tree (the most common case) has 5 columns.


^A 5-dimensional R*Tree has 11 columns.  The SQLite R*Tree implementation
does not support R*Trees wider than 5 dimensions.
</p>

<p>
^The first column of an SQLite R*Tree must always be an integer
primary key.
^The min/max-value pair columns are always stored as
................................................................................
<p>
^The shadow tables are ordinary SQLite data tables.  You can query them 
directly if you like, though this unlikely to reveal anything particularly
useful. 
^And you can [UPDATE], [DELETE], [INSERT] or even [DROP TABLE | DROP] 
the shadow tables, though doing so will corrupt your R*Tree index.
So it is best to simply ignore the shadow tables.  Recognize that they
are there to hold your R*Tree index information and let it go as that.
</p>

<p>
^(As an example, consider creating a two-dimensional R*Tree index for use in 
spatial queries:
</p>

................................................................................
^(This second query would find both entry 1 (the SQLite.org office) which
is entirely contained within the query box and also
the 12th Congressional District which extends well outside the
query box but still overlaps the query box.)^
</p>

<p>
^Note that is not necessary for all coordinates in an R*Tree index
to be constrained in order for the index search to be efficient.
^(One might, for example, want to query all objects that overlap with
the 35th parallel:
</p>

<blockquote><pre>
SELECT id FROM demo_index
................................................................................
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.




<p>Regions for custom r-tree queries are defined by r-tree geometry callbacks

implemented by the application and registered with SQLite via a call to the 
following API:

<blockquote><pre>







int sqlite3_rtree_geometry_callback(
  sqlite3 *db,
  const char *zGeom,
  int (*xGeom)(sqlite3_rtree_geometry *, int nCoord, double *aCoord, int *pRes),
  void *pContext
);
</pre></blockquote>

<p>A call to the above API registers an r-tree geometry callback named zGeom.
If an r-tree geometry callback or ordinary SQL user function named zGeom 
already exists when sqlite3_rtree_geometry_callback() is called, it is replaced
by the new r-tree geometry callback. If the xGeom parameter is passed a NULL
value, then any existing r-tree geometry callback or SQL user function is
removed from the system, but no new r-tree geometry callback is registered.

<p>When the r-tree geometry callback is used in a custom r-tree query, the
registered callback is invoked one or more times by SQLite to test whether or
not the user-defined region intersects with specific bounding boxes.
The bounding box being tested is defined by the contents of the aCoord[] 
array (size nCoord) passed to the callback. The aCoord[] array always contains
the same number of entries as there are coordinate columns in the r-tree table
(one less than the total number of columns, since the object id column does not
contain a coordinate). They define a bounding-box in the same way as each row
of the r-tree table itself does - the first scalar coordinate contains the
minimum value for the first dimension, followed by the maximum value for the
first dimension, followed by the minimum value for the second dimension, and so
on. If the specified bounding box intersects with the custom query region, then
the implementation of the callback must set the output parameter *pRes to
non-zero and return SQLITE_OK. If the specified bounding box does not intersect
the queried region, *pRes should be set to zero before returning SQLITE_OK. If
an error occurs, the callback may return an SQLite error code other than
SQLITE_OK, in which case the value of *pRes is ignored by SQLite and the query
abandoned.

<p>A registered r-tree geometry callback is used in an r-tree query by adding
a MATCH condition to the WHERE clause of a SELECT statement. For example,
assuming a custom geometry callback named "circle" has been registered, it may
be used in a query on the two-dimensional r-tree table "demo_index" defined in
earlier examples as follows: 

<blockquote><pre>
SELECT * FROM demo_index WHERE id MATCH circle(45.3, 22.9, 5.0)
</blockquote></pre>

<p>The left-hand side of the MATCH operator may be any column from the r-tree
table, including the object id column. It makes no difference which column is
used. The right-hand side of the MATCH operator is passed the results of an
SQL function with the same name as the r-tree geometry callback. Zero or more
function parameters may be specified by the user. Parameters are always
interpreted as 64-bit real values. If a text, integer or blob value is passed
as a parameter to an r-tree geometry callback function, it is converted to
a real value as if by a [CAST expression]. If an SQL NULL value is passed to
an r-tree geometry callback function, it is converted to the value 0.0.

<p>Parameters passed to r-tree geometry callback functions may be used by the
implementation of the r-tree geometry callback to define the specified
region in any way. For example, the three parameters passed to the "circle"
geometry callback above could identify the center point and radius of the
circular region of interest.

<p>The first argument to each invocation of an r-tree geometry callback is
a pointer to a structure of the following type. The contents of the structure
are not modified between multiple calls to the r-tree geometry callback
associated with a single query (unless the pUser or xDelUser member variables
are modified by the callback implementation - see below).

<blockquote><pre>
typedef struct sqlite3_rtree_geometry sqlite3_rtree_geometry;
struct sqlite3_rtree_geometry {
  void *pContext;                 /* Copy of pContext passed to s_r_g_c() */
  int nParam;                     /* Size of array aParam */
  double *aParam;                 /* Parameters passed to SQL geom function */
  void *pUser;                    /* Callback implementation user data */
  void (*xDelUser)(void *);       /* Called by SQLite to clean up pUser */
};
</pre></blockquote>

<p>The pContext member of the structure is always set to a copy of the pContext
argument passed to sqlite3_rtree_geometry_callback() when the r-tree geometry
callback is registered. The aParam[] array (size nParam) contains the parameter
values passed to the r-tree geometry callback as part of the SQL query. In
the example "circle" query above, nParam would be set to 3 and the aParam[]
array would contain the three values 45.3, 22.9 and 5.0.

<p>The pUser and xDelUser members of the sqlite3_rtree_geometry structure are
initially set to NULL. The pUser variable may be set by the callback
implementation to any arbitrary value that may be useful to subsequent
invocations of the callback within the same custom r-tree query (for example, a
pointer to a complicated data structure used to test for region intersection).
If the xDelUser variable is set to a non-NULL value, then after the custom
r-tree query has finished running SQLite automatically invokes it with the
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>Example code implementing the "circle" r-tree geometry callback may be
found in the file 

<a href=http://www.sqlite.org/src/doc/trunk/src/test_rtree.c>test_rtree.c</a>.

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
or which overlap the query rectangle.  This idea is easily extended to
three dimensions for use in CAD systems.  R-Trees also find use in time-domain
range look-ups.  For example, suppose a database records the starting and
ending times for a large number of events.  A R-Tree is able to quickly
find all events that were active at any time during a given
time interval, or all events that started during a particular time interval,
or all events that both started and ended within a given time interval.
And so forth.
</p>

<p>
The R-Tree concept originated with 
................................................................................
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
32-bit floating point numbers) for each
dimension.  ^A 1-dimensional R*Tree thus has 3 columns.  
^A 2-dimensional R*Tree has 5 columns.
^A 3-dimensional R*Tree has 7 columns.
^A 4-dimensional R*Tree has 9 columns.
^And a 5-dimensional R*Tree has 11 columns.  The SQLite R*Tree implementation
does not support R*Trees wider than 5 dimensions.
</p>

<p>
^The first column of an SQLite R*Tree must always be an integer
primary key.
^The min/max-value pair columns are always stored as
................................................................................
<p>
^The shadow tables are ordinary SQLite data tables.  You can query them 
directly if you like, though this unlikely to reveal anything particularly
useful. 
^And you can [UPDATE], [DELETE], [INSERT] or even [DROP TABLE | DROP] 
the shadow tables, though doing so will corrupt your R*Tree index.
So it is best to simply ignore the shadow tables.  Recognize that they
hold your R*Tree index information and let it go as that.
</p>

<p>
^(As an example, consider creating a two-dimensional R*Tree index for use in 
spatial queries:
</p>

................................................................................
^(This second query would find both entry 1 (the SQLite.org office) which
is entirely contained within the query box and also
the 12th Congressional District which extends well outside the
query box but still overlaps the query box.)^
</p>

<p>
^Note that it is not necessary for all coordinates in an R*Tree index
to be constrained in order for the index search to be efficient.
^(One might, for example, want to query all objects that overlap with
the 35th parallel:
</p>

<blockquote><pre>
SELECT id FROM demo_index
................................................................................
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 
just a box.  This capability is useful, for example, in computing the 
subset of objects in the R*Tree that are visible from a camera positioned 
in 3-D space.


<p>Regions for custom R*Tree queries are defined by R*Tree geometry callbacks
implemented by the application and registered with SQLite via a call to one
of the following two APIs:

<blockquote><pre>
int sqlite3_rtree_query_callback(
  sqlite3 *db,
  const char *zQueryFunc,
  int (*xQueryFunc)(sqlite3_rtree_query_info*),
  void *pContext,
  void (*xDestructor)(void*)
);
int sqlite3_rtree_geometry_callback(
  sqlite3 *db,
  const char *zGeom,
  int (*xGeom)(sqlite3_rtree_geometry *, int nCoord, double *aCoord, int *pRes),
  void *pContext
);
</pre></blockquote>

<p>The sqlite3_rtree_query_callback() became available with SQLite
[version 3.8.5] and is the preferred interface.
The sqlite3_rtree_geometry_callback() is an older and less flexible
interface that is supported for backwards compatiblity.

<p>A call to one of the above APIs creates a new SQL function named by the
second parameter (zQueryFunc or zGeom).  When that SQL function appears
on the right-hand side of the MATCH operator and the left-hand side of the
MATCH operator is any column in the R*Tree virtual table, then the callback 
defined by the third argument (xQueryFunc or xGeom) is invoked to determine
if a particular object or subtree overlaps the desired region.

<p>For example, a query like the following might be used to find all
R*Tree entries that overlap with a circle centered a 45.3,22.9 with a
radius of 5.0:

<blockquote><pre>
SELECT id FROM demo_index WHERE id MATCH circle(45.3, 22.9, 5.0)
</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 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.
The third argument, aCoord[], is an array of nCoord coordinates that defines
a bounding box to be tested.  The last argument is a pointer into which 
the callback result should be written.  The result is zero
if the bounding-box defined by aCoord[] is completely outside
the region defined by the xGeom callback and the result is non-zero if
the bounding-box is inside or overlaps with the xGeom region.  The xGeom
callback should normally return SQLITE_OK.  If xGeom returns anything other
than SQLITE_OK, then the r-tree query will abort with an error.

<p>The sqlite3_rtree_geometry structure that the first argument to the
xGeom callback points to has a structure shown below.  The exact same
structure is used for every callback for same MATCH operator in the same
query.  The contents of the structure are initialized by SQLite but are
not subsequently modifed.  The callback is free to make changes to the
pUser and xDelUser elements of the structure if desired.










<blockquote><pre>
typedef struct sqlite3_rtree_geometry sqlite3_rtree_geometry;
struct sqlite3_rtree_geometry {
  void *pContext;                 /* Copy of pContext passed to s_r_g_c() */
  int nParam;                     /* Size of array aParam */
  double *aParam;                 /* Parameters passed to SQL geom function */
  void *pUser;                    /* Callback implementation user data */
  void (*xDelUser)(void *);       /* Called by SQLite to clean up pUser */
};
</pre></blockquote>

<p>The pContext member of the structure is always set to a copy of the pContext
argument passed to sqlite3_rtree_geometry_callback() when the
callback is registered. The aParam[] array (size nParam) contains the parameter
values passed to the SQL function on the right-hand side of the MATCH operator.
In the example "circle" query above, nParam would be set to 3 and the aParam[]
array would contain the three values 45.3, 22.9 and 5.0.

<p>The pUser and xDelUser members of the sqlite3_rtree_geometry structure are
initially set to NULL. The pUser variable may be set by the callback
implementation to any arbitrary value that may be useful to subsequent
invocations of the callback within the same query (for example, a
pointer to a complicated data structure used to test for region intersection).
If the xDelUser variable is set to a non-NULL value, then after the
query has finished running SQLite automatically invokes it with the
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 send 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:

<blockquote><pre>
struct sqlite3_rtree_query_info {
  void *pContext;                   /* pContext from when function registered */
  int nParam;                       /* Number of function parameters */
  sqlite3_rtree_dbl *aParam;        /* value of function parameters */
  void *pUser;                      /* callback can use this, if desired */
  void (*xDelUser)(void*);          /* function to free pUser */
  sqlite3_rtree_dbl *aCoord;        /* Coordinates of node or entry to check */
  unsigned int *anQueue;            /* Number of pending entries in the queue */
  int nCoord;                       /* Number of coordinates */
  int iLevel;                       /* Level of current node or entry */
  int mxLevel;                      /* The largest iLevel value in the tree */
  sqlite3_int64 iRowid;             /* Rowid for current entry */
  sqlite3_rtree_dbl rParentScore;   /* Score of parent node */
  int eParentWithin;                /* Visibility of parent node */
  int eWithin;                      /* OUT: Visiblity */
  sqlite3_rtree_dbl rScore;         /* OUT: Write the score here */
};
</pre></blockquote>

<p>The first five fields of the sqlite3_rtree_query_info structure are identical
to the sqlite3_rtree_geometry structure, and have exactly the same meaning.
The sqlite3_rtree_query_info structure also contains nCoord and aCoord fields 
which have the same meaning as the parameter of the same name in the xGeom callback.

<p>The xQueryFunc must set the eWithin field of sqlite3_rtree_query_info to
on of the values NOT_WITHIN, PARTLY_WITHIN, or FULLY_WITHIN depending on whether
or not the bounding box defined by aCoord[] is completely outside the region,
overlaps the region, or is completely inside the region, respectively.  In
addition, the xQueryFunc must set the rScore field to a non-negative value that
indicates the order in which subtrees and entries of the query should be analyzed
and returned.  Smaller scores are processed first.

<p>As its name implies, an R*Tree is organized as a tree.  Each node of the
tree is a bounding box.  The root of the tree is a bounding box that encapsulates
all elements of the tree.  Beneath the root are a number of subtrees (typically
20 or more) each with their own smaller bounding boxes and each containing some
subset of the R*Tree entries.  The subtrees may have sub-subtrees, and so forth
until finally one reaches the leaves of the tree which are the actual R*Tree
entries.

<p>An R*Tree query is initialized by making the root node the only entry
in a priority queue sorted by rScore.
The query proceeds by extracting the entry from the priority queue that has
the lowest score.  If that entry is a leaf (meaning that it is an actual
R*Tree entry and not a subtree) then that entry
is returned as one row of the query result.  
If the extracted priority queue entry is a node (a subtree),
then sub-subtrees or leaves contained within that entry are passed to the
xQueryFunc callback, one by one.  Those subelements for which the xQueryFunc
callback sets eWithin to PARTLY_WITHIN or FULLY_WITHIN are added to the priority
queue using the score supplied by the callback.  Subelements that return
NOT_WITHIN are discarded.  The query runs until the priority queue is empty.

<p>Every leaf entry and node (subtree) within the R*Tree has an integer "level".
The leaves have a level of 0.  The first containing subtree of the leaves has
a level of 1.  The root of the R*Tree has the largest level value.  The
mxLevel entry in the sqlite3_rtree_query_info structure is the level value for
the root of the R*Tree.  The iLevel entry in sqlite3_rtree_query_info gives the
level for the object being interrogated.

<p>Most R*Tree queries use a depth-first search.  This is accomplished by setting
the rScore equal to iLevel.  A depth-first search is usually preferred since it
minimizes the number of elements in the priority queue, which reduces memory
requirements and speeds processing.  However, some application may prefer a
breadth-first search, which can be accomplished by setting rScore to mxLevel-iLevel.
By creating more complex formulas for rScore, applications can exercise
detailed control over the order in which subtree are searched and leaf
R*Tree entries are returned.  For example, in an application with many
millions of R*Tree entries, the rScore might be arranged so that the
largest or most significant entries are returned first, allowing the
application to display the most important information quickly, and
filling in smaller and less important details as they become available.

<p>Other information fields of the sqlite3_rtree_query_info structure are
available for use by the xQueryFunc callback, if desired.  The iRowid field
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.