R-16717-50504-54717-12200-54209-43488-56382-57633 tcl slt th3 src
Each R*Tree index is a virtual table with an odd number of columns between 3 and 11.
/* IMP: R-16717-50504 */
# EVIDENCE-OF: R-16717-50504 Each R*Tree index is a virtual table with # an odd number of columns between 3 and 11.
R-46619-65417-10138-19214-14415-00475-28219-65444 tcl slt th3 src
The first column is always a 64-bit signed integer primary key.
/* IMP: R-46619-65417 */
# EVIDENCE-OF: R-46619-65417 The first column is always a 64-bit signed # integer primary key.
R-64317-38978-24132-13511-50003-08766-02219-42213 tcl slt th3 src
The other columns are pairs, one pair per dimension, containing the minimum and maximum values for that dimension, respectively.
/* IMP: R-64317-38978 */
# EVIDENCE-OF: R-64317-38978 The other columns are pairs, one pair per # dimension, containing the minimum and maximum values for that # dimension, respectively.
R-15060-13876-27196-24328-29262-37207-52735-33647 tcl slt th3 src
A 1-dimensional R*Tree thus has 3 columns.
/* IMP: R-15060-13876 */
# EVIDENCE-OF: R-15060-13876 A 1-dimensional R*Tree thus has 3 columns.
R-19353-19546-22807-46023-33784-34102-06986-46730 tcl slt th3 src
A 2-dimensional R*Tree has 5 columns.
/* IMP: R-19353-19546 */
# EVIDENCE-OF: R-19353-19546 A 2-dimensional R*Tree has 5 columns.
R-13615-19528-18270-26667-29979-02127-30381-22829 tcl slt th3 src
A 3-dimensional R*Tree has 7 columns.
/* IMP: R-13615-19528 */
# EVIDENCE-OF: R-13615-19528 A 3-dimensional R*Tree has 7 columns.
R-53479-41922-39952-24779-27153-12886-60849-40367 tcl slt th3 src
A 4-dimensional R*Tree has 9 columns.
/* IMP: R-53479-41922 */
# EVIDENCE-OF: R-53479-41922 A 4-dimensional R*Tree has 9 columns.
R-13981-28768-38524-42691-40554-58455-18349-16495 tcl slt th3 src
And a 5-dimensional R*Tree has 11 columns.
/* IMP: R-13981-28768 */
# EVIDENCE-OF: R-13981-28768 And a 5-dimensional R*Tree has 11 columns.
R-61533-25862-33162-64388-19135-16857-63238-64063 tcl slt th3 src
The SQLite R*Tree implementation does not support R*Trees wider than 5 dimensions.
/* IMP: R-61533-25862 */
# EVIDENCE-OF: R-61533-25862 The SQLite R*Tree implementation does not # support R*Trees wider than 5 dimensions.
R-17874-21123-26215-56857-37279-50732-34133-47276 tcl slt th3 src
The first column of an SQLite R*Tree is similar to an integer primary key column of a normal SQLite table.
/* IMP: R-17874-21123 */
# EVIDENCE-OF: R-17874-21123 The first column of an SQLite R*Tree is # similar to an integer primary key column of a normal SQLite table.
R-08054-15429-02256-10004-55638-18867-37025-44792 tcl slt th3 src
The min/max-value pair columns are stored as 32-bit floating point values for "rtree" virtual tables or as 32-bit signed integers in "rtree_i32" virtual tables.
/* IMP: R-08054-15429 */
# EVIDENCE-OF: R-08054-15429 The min/max-value pair columns are stored # as 32-bit floating point values for "rtree" virtual tables or as # 32-bit signed integers in "rtree_i32" virtual tables.
R-47371-54529-47056-05139-21545-30146-30084-29428 tcl slt th3 src
Unlike regular SQLite tables which can store data in a variety of datatypes and formats, the R*Tree rigidly enforce these storage types.
/* IMP: R-47371-54529 */
# EVIDENCE-OF: R-47371-54529 Unlike regular SQLite tables which can # store data in a variety of datatypes and formats, the R*Tree rigidly # enforce these storage types.
R-13543-33261-54186-53828-50711-48001-20973-48866 tcl slt th3 src
A new R*Tree index is created as follows:
CREATE VIRTUAL TABLE <name> USING rtree(<column-names>);
The <name> is the name your application chooses for the R*Tree index and <column-names> is a comma separated list of between 3 and 11 columns. ^(The virtual <name> table creates three shadow tables to actually store its content. The names of these shadow tables are:
<name>_node
<name>_rowid
<name>_parent
^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 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.
^(As an example, consider creating a two-dimensional R*Tree index for use in spatial queries:
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 );
^(In the argments to "rtree" in the CREATE VIRTUAL TABLE statement, the names of the columns are taken from the first token of each argument. All subsequent tokens within each argument are silently ignored.
/* IMP: R-13543-33261 */
# EVIDENCE-OF: R-13543-33261 A new R*Tree index is created as follows: # CREATE VIRTUAL TABLE <name> USING rtree(<column-names>); # The <name> is the name your application chooses for the R*Tree # index and <column-names> is a comma separated list of between 3 # and 11 columns. ^(The virtual <name> table creates three shadow # tables to actually store its content. The names of these shadow tables # are: <name>_node <name>_rowid <name>_parent ^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 # 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. ^(As an # example, consider creating a two-dimensional R*Tree index for use in # spatial queries: 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 ); 3.1.1. Column naming # details ^(In the argments to "rtree" in the CREATE VIRTUAL TABLE # statement, the names of the columns are taken from the first token of # each argument. All subsequent tokens within each argument are silently # ignored.
R-47962-27004-38595-48890-59288-41835-42483-18817 tcl slt th3 src
In an RTREE virtual table, the first column always has a type affinity of INTEGER and all other data columns have a type affinity of NUMERIC.
/* IMP: R-47962-27004 */
# EVIDENCE-OF: R-47962-27004 In an RTREE virtual table, the first column # always has a type affinity of INTEGER and all other data columns have # a type affinity of NUMERIC.
R-36195-31555-35544-12860-62754-30693-28143-39954 tcl slt th3 src
The usual INSERT, UPDATE, and DELETE commands work on an R*Tree index just like on regular tables.
/* IMP: R-36195-31555 */
# EVIDENCE-OF: R-36195-31555 The usual INSERT, UPDATE, and DELETE # commands work on an R*Tree index just like on regular tables.
R-52566-22867-38000-46800-13895-09420-20056-05293 tcl slt th3 src
So to insert some data into our sample R*Tree index, we can do something like this:
INSERT INTO demo_index VALUES( 1, -- Primary key -- SQLite.org headquarters -80.7749, -80.7747, -- Longitude range 35.3776, 35.3778 -- Latitude range ); INSERT INTO demo_index VALUES( 2, -- NC 12th Congressional District in 2010 -81.0, -79.6, 35.0, 36.2 );
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.
^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:
SELECT * FROM demo_index WHERE id=1;
Of course, an ordinary SQLite table will also do a query against its integer primary key efficiently, so the previous is no big deal. The real reason for using an R*Tree is so that you can efficiently do inequality queries against the coordinate ranges. ^(To find all elements of the index that are contained within the vicinity of Charlotte, North Carolina, one might do:
SELECT id FROM demo_index WHERE minX>=-81.08 AND maxX<=-80.58 AND minY>=35.00 AND maxY<=35.44;
^The query above would very quickly locate the id of 1 even if the R*Tree contained millions of entries. The previous is an example of a "contained-within" query. The R*Tree also supports "overlapping" queries. ^(For example, to find all bounding boxes that overlap the Charlotte area:
SELECT id FROM demo_index WHERE maxX>=-81.08 AND minX<=-80.58 AND maxY>=35.00 AND minY<=35.44;
^(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.
/* IMP: R-52566-22867 */
# EVIDENCE-OF: R-52566-22867 So to insert some data into our sample # R*Tree index, we can do something like this: INSERT INTO demo_index # VALUES( 1, -- Primary key -- SQLite.org headquarters -80.7749, # -80.7747, -- Longitude range 35.3776, 35.3778 -- Latitude range ); # INSERT INTO demo_index VALUES( 2, -- NC 12th Congressional District in # 2010 -81.0, -79.6, 35.0, 36.2 ); 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. # 3.3. Querying An R*Tree Index ^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: SELECT * FROM demo_index WHERE id=1; Of # course, an ordinary SQLite table will also do a query against its # integer primary key efficiently, so the previous is no big deal. The # real reason for using an R*Tree is so that you can efficiently do # inequality queries against the coordinate ranges. ^(To find all # elements of the index that are contained within the vicinity of # Charlotte, North Carolina, one might do: SELECT id FROM demo_index # WHERE minX>=-81.08 AND maxX<=-80.58 AND minY>=35.00 AND # maxY<=35.44; ^The query above would very quickly locate the id of 1 # even if the R*Tree contained millions of entries. The previous is an # example of a "contained-within" query. The R*Tree also supports # "overlapping" queries. ^(For example, to find all bounding boxes that # overlap the Charlotte area: SELECT id FROM demo_index WHERE # maxX>=-81.08 AND minX<=-80.58 AND maxY>=35.00 AND # minY<=35.44; ^(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.
R-02723-34107-58585-29932-59518-10370-60775-12212 tcl slt th3 src
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.
/* IMP: R-02723-34107 */
# EVIDENCE-OF: R-02723-34107 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.
R-57988-35998-58808-15770-21594-63900-64654-02557 tcl slt th3 src
One might, for example, want to query all objects that overlap with the 35th parallel:
SELECT id FROM demo_index WHERE maxY>=35.0 AND minY<=35.0;
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.
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 is exactly what is desired for doing the more common "overlapping" queries where the application wants to find every entry in the R*Tree that overlaps a query bounding box. Rounding the entry bounding boxes outward might cause a few extra entries to appears in an overlapping query if the edge of the entry bounding box corresponds to an edge of the query bounding box. But the overlapping query will never miss a valid table entry.
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.
It is the nature of the Guttman R-Tree algorithm that any write might radically restructure the tree, and in the process change the scan order of the nodes. For this reason, it is not generally possible to modify the R-Tree in the middle of a query of the R-Tree. Attempts to do so will fail with a SQLITE_LOCKED "database table is locked" error.
So, for example, suppose an application runs one query against an R-Tree like this:
SELECT id FROM demo_index WHERE maxY>=35.0 AND minY<=35.0;
Then for each "id" value returned, suppose the application creates an UPDATE statement like the following and binds the "id" value returned against the "?1" parameter:
UPDATE demo_index SET maxY=maxY+0.5 WHERE id=?1;
Then the UPDATE might fail with an SQLITE_LOCKED error. The reason is that the initial query has not run to completion. It is remembering its place in the middle of a scan of the R-Tree. So an update to the R-Tree cannot be tolerated as this would disrupt the scan.
It is also possible to express this kind of simultaneous read and write on an R-Tree within a single query, for example if an UPDATE statement tries to change the value of one row of the R-Tree based on a complicated query from another row of the same R-Tree, perhaps something like this:
UPDATE demo_index SET maxY = (SELECT max(maxX) FROM demo_index AS x2 WHERE x2.maxY>demo_index.x2) WHERE maxY>=35.0 AND minY<=35.0;
This is a limitation of the R-Tree extension only. Ordinary tables in SQLite are able to read and write at the same time. Other virtual tables might (or might not) also that capability. And R-Tree can appear to read and write at the same time in some circumstances, if it can figure out how to reliably run the query to completion before starting the update. But you shouldn't count on that for every query. Generally speaking, it is best to avoid running queries and updates to the same R-Tree at the same time.
If you really need to update an R-Tree based on complex queries against the same R-Tree, it is best to run the complex queries first and store the results in a temporary table, then update the R-Tree based on the values stored in the temporary table.
For SQLite versions prior to 3.24.0 (2018-06-04), 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:
CREATE TABLE demo_data( id INTEGER PRIMARY KEY, -- primary key objname TEXT, -- name of the object objtype TEXT, -- object type boundary BLOB -- detailed boundary of object );
In this example, the demo_data.boundary field is intended to hold some kind of binary representation of the precise boundaries of the object. The R*Tree index only holds an axis-aligned rectangular boundary for the object. The R*Tree boundary is just an approximation of the true object boundary. So what typically happens is that the R*Tree index is used to narrow a search down to a list of candidate objects and then more detailed and expensive computations are done on each candidate to find if the candidate truly meets the search criteria.
Key Point: An R*Tree index does not normally provide the exact answer but merely reduces the set of potential answers from millions to dozens.
Suppose the demo_data.boundary field holds some proprietary data description of a complex two-dimensional boundary for an object and suppose that the application has used the sqlite3_create_function() interface to created application-defined functions "contained_in" and "overlaps" accepting two demo_data.boundary objects and return true or false. One may assume that "contained_in" and "overlaps" are relatively slow functions that we do not want to invoke too frequently. ^(Then an efficient way to find the name of all objects located within the North Carolina 12th District, one may be to run a query like this:
SELECT objname FROM demo_data, demo_index WHERE demo_data.id=demo_index.id AND contained_in(demo_data.boundary, :boundary) AND minX>=-81.0 AND maxX<=-79.6 AND minY>=35.0 AND maxY>=36.2;
In the query above, one would presumably bind the binary BLOB description of the precise boundary of the 12th district to the ":boundary" parameter.
Notice how the query above works: The R*Tree index runs in the outer loop to find entries that are contained within the bounding box of longitude -81..-79.6 and latitude 35.0..36.2. For each object identifier found, SQLite looks up the corresponding entry in the demo_data table. It then uses the boundary field from the demo_data table as a parameter to the contained_in() function and if that function returns true, the objname field from the demo_data table is returned as the next row of query result.
One would get the same answer without the use of the R*Tree index using the following simpler query:
SELECT objname FROM demo_data WHERE contained_in(demo_data.boundary, :boundary);
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.
Beginning with SQLite version 3.24.0 (2018-06-04), r-tree tables can have auxiliary columns that store arbitrary data. Auxiliary columns can be used in place of secondary tables such as "demo_data".
Auxiliary columns are marked with a "+" symbol before the column name. Auxiliary columns must come after all of the coordinate boundary columns. There is a limit of no more than 100 auxiliary columns. The following example shows an r-tree table with auxiliary columns that is equivalent to the two tables "demo_index" and "demo_data" above: ^(
CREATE VIRTUAL TABLE demo_index2 USING rtree( id, -- Integer primary key minX, maxX, -- Minimum and maximum X coordinate minY, maxY, -- Minimum and maximum Y coordinate +objname TEXT, -- name of the object +objtype TEXT, -- object type +boundary BLOB -- detailed boundary of object );
/* IMP: R-57988-35998 */
# EVIDENCE-OF: R-57988-35998 One might, for example, want to query all # objects that overlap with the 35th parallel: SELECT id FROM demo_index # WHERE maxY>=35.0 AND minY<=35.0; 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. 3.4. # Roundoff Error 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 is exactly what is # desired for doing the more common "overlapping" queries where the # application wants to find every entry in the R*Tree that overlaps a # query bounding box. Rounding the entry bounding boxes outward might # cause a few extra entries to appears in an overlapping query if the # edge of the entry bounding box corresponds to an edge of the query # bounding box. But the overlapping query will never miss a valid table # entry. 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. 3.5. Reading And Writing At # The Same Time It is the nature of the Guttman R-Tree algorithm that # any write might radically restructure the tree, and in the process # change the scan order of the nodes. For this reason, it is not # generally possible to modify the R-Tree in the middle of a query of # the R-Tree. Attempts to do so will fail with a SQLITE_LOCKED "database # table is locked" error. So, for example, suppose an application runs # one query against an R-Tree like this: SELECT id FROM demo_index WHERE # maxY>=35.0 AND minY<=35.0; Then for each "id" value returned, # suppose the application creates an UPDATE statement like the following # and binds the "id" value returned against the "?1" parameter: UPDATE # demo_index SET maxY=maxY+0.5 WHERE id=?1; Then the UPDATE might fail # with an SQLITE_LOCKED error. The reason is that the initial query has # not run to completion. It is remembering its place in the middle of a # scan of the R-Tree. So an update to the R-Tree cannot be tolerated as # this would disrupt the scan. It is also possible to express this kind # of simultaneous read and write on an R-Tree within a single query, for # example if an UPDATE statement tries to change the value of one row of # the R-Tree based on a complicated query from another row of the same # R-Tree, perhaps something like this: UPDATE demo_index SET maxY = # (SELECT max(maxX) FROM demo_index AS x2 WHERE # x2.maxY>demo_index.x2) WHERE maxY>=35.0 AND minY<=35.0; This # is a limitation of the R-Tree extension only. Ordinary tables in # SQLite are able to read and write at the same time. Other virtual # tables might (or might not) also that capability. And R-Tree can # appear to read and write at the same time in some circumstances, if it # can figure out how to reliably run the query to completion before # starting the update. But you shouldn't count on that for every query. # Generally speaking, it is best to avoid running queries and updates to # the same R-Tree at the same time. If you really need to update an # R-Tree based on complex queries against the same R-Tree, it is best to # run the complex queries first and store the results in a temporary # table, then update the R-Tree based on the values stored in the # temporary table. 4. Using R*Trees Effectively For SQLite versions # prior to 3.24.0 (2018-06-04), 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: CREATE TABLE # demo_data( id INTEGER PRIMARY KEY, -- primary key objname TEXT, -- # name of the object objtype TEXT, -- object type boundary BLOB -- # detailed boundary of object ); In this example, the demo_data.boundary # field is intended to hold some kind of binary representation of the # precise boundaries of the object. The R*Tree index only holds an # axis-aligned rectangular boundary for the object. The R*Tree boundary # is just an approximation of the true object boundary. So what # typically happens is that the R*Tree index is used to narrow a search # down to a list of candidate objects and then more detailed and # expensive computations are done on each candidate to find if the # candidate truly meets the search criteria. Key Point: An R*Tree index # does not normally provide the exact answer but merely reduces the set # of potential answers from millions to dozens. Suppose the # demo_data.boundary field holds some proprietary data description of a # complex two-dimensional boundary for an object and suppose that the # application has used the sqlite3_create_function() interface to # created application-defined functions "contained_in" and "overlaps" # accepting two demo_data.boundary objects and return true or false. One # may assume that "contained_in" and "overlaps" are relatively slow # functions that we do not want to invoke too frequently. ^(Then an # efficient way to find the name of all objects located within the North # Carolina 12th District, one may be to run a query like this: SELECT # objname FROM demo_data, demo_index WHERE demo_data.id=demo_index.id # AND contained_in(demo_data.boundary, :boundary) AND minX>=-81.0 AND # maxX<=-79.6 AND minY>=35.0 AND maxY>=36.2; In the query # above, one would presumably bind the binary BLOB description of the # precise boundary of the 12th district to the ":boundary" parameter. # Notice how the query above works: The R*Tree index runs in the outer # loop to find entries that are contained within the bounding box of # longitude -81..-79.6 and latitude 35.0..36.2. For each object # identifier found, SQLite looks up the corresponding entry in the # demo_data table. It then uses the boundary field from the demo_data # table as a parameter to the contained_in() function and if that # function returns true, the objname field from the demo_data table is # returned as the next row of query result. One would get the same # answer without the use of the R*Tree index using the following simpler # query: SELECT objname FROM demo_data WHERE # contained_in(demo_data.boundary, :boundary); 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. # 4.1. Auxiliary Columns Beginning with SQLite version 3.24.0 # (2018-06-04), r-tree tables can have auxiliary columns that store # arbitrary data. Auxiliary columns can be used in place of secondary # tables such as "demo_data". Auxiliary columns are marked with a "+" # symbol before the column name. Auxiliary columns must come after all # of the coordinate boundary columns. There is a limit of no more than # 100 auxiliary columns. The following example shows an r-tree table # with auxiliary columns that is equivalent to the two tables # "demo_index" and "demo_data" above: ^(CREATE VIRTUAL TABLE demo_index2 # USING rtree( id, -- Integer primary key minX, maxX, -- Minimum and # maximum X coordinate minY, maxY, -- Minimum and maximum Y coordinate # +objname TEXT, -- name of the object +objtype TEXT, -- object type # +boundary BLOB -- detailed boundary of object );
R-03895-01427-35147-59695-24656-05504-11276-13521 tcl slt th3 src
SELECT objname FROM demo_index2 WHERE contained_in(boundary, :boundary) AND minX>=-81.0 AND maxX<=-79.6 AND minY>=35.0 AND maxY>=36.2;
/* IMP: R-03895-01427 */
# EVIDENCE-OF: R-03895-01427 SELECT objname FROM demo_index2 WHERE # contained_in(boundary, :boundary) AND minX>=-81.0 AND # maxX<=-79.6 AND minY>=35.0 AND maxY>=36.2;
R-35254-48865-63817-52724-57944-24327-24630-05485 tcl slt th3 src
A call to one of the above APIs creates a new SQL function named by the second parameter (zQueryFunc or zGeom).
/* IMP: R-35254-48865 */
# EVIDENCE-OF: R-35254-48865 A call to one of the above APIs creates a # new SQL function named by the second parameter (zQueryFunc or zGeom).
R-59634-51678-29795-22623-60513-10487-06107-08719 tcl slt th3 src
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.
/* IMP: R-59634-51678 */
# EVIDENCE-OF: R-59634-51678 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.
R-61427-46983-18669-51894-26690-07828-25787-33323 tcl slt th3 src
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:
SELECT id FROM demo_index WHERE id MATCH circle(45.3, 22.9, 5.0)
/* IMP: R-61427-46983 */
# EVIDENCE-OF: R-61427-46983 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: SELECT id FROM demo_index # WHERE id MATCH circle(45.3, 22.9, 5.0)
R-16907-50223-28692-47460-07440-02664-00215-50680 tcl slt th3 src
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.
/* IMP: R-16907-50223 */
# EVIDENCE-OF: R-16907-50223 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.
R-00693-36727-57706-32123-30185-00000-05163-54607 tcl slt th3 src
The legacy xGeom callback is invoked with four arguments.
/* IMP: R-00693-36727 */
# EVIDENCE-OF: R-00693-36727 The legacy xGeom callback is invoked with # four arguments.
R-50437-53270-64199-48076-12233-35385-13777-56267 tcl slt th3 src
The first argument is a pointer to an sqlite3_rtree_geometry structure which provides information about how the SQL function was invoked.
/* IMP: R-50437-53270 */
# EVIDENCE-OF: R-50437-53270 The first argument is a pointer to an # sqlite3_rtree_geometry structure which provides information about how # the SQL function was invoked.
R-02424-24769-08747-39368-55205-12781-22154-40957 tcl slt th3 src
The second argument is the number of coordinates in each r-tree entry, and is always the same for any given R*Tree.
/* IMP: R-02424-24769 */
# EVIDENCE-OF: R-02424-24769 The second argument is the number of # coordinates in each r-tree entry, and is always the same for any given # R*Tree.
R-40260-16838-48833-50335-31686-26847-17814-00082 tcl slt th3 src
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.
/* IMP: R-40260-16838 */
# EVIDENCE-OF: R-40260-16838 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.
R-00090-24248-38638-40643-10159-25596-30389-07024 tcl slt th3 src
The third argument, aCoord[], is an array of nCoord coordinates that defines a bounding box to be tested.
/* IMP: R-00090-24248 */
# EVIDENCE-OF: R-00090-24248 The third argument, aCoord[], is an array # of nCoord coordinates that defines a bounding box to be tested.
R-28207-40885-37612-34994-37916-57388-29422-16350 tcl slt th3 src
The last argument is a pointer into which the callback result should be written.
/* IMP: R-28207-40885 */
# EVIDENCE-OF: R-28207-40885 The last argument is a pointer into which # the callback result should be written.
R-28051-48608-28159-47201-29527-20252-33499-18741 tcl slt th3 src
If xGeom returns anything other than SQLITE_OK, then the r-tree query will abort with an error.
/* IMP: R-28051-48608 */
# EVIDENCE-OF: R-28051-48608 If xGeom returns anything other than # SQLITE_OK, then the r-tree query will abort with an error.
R-53759-57366-14099-11673-51182-17816-42165-23586 tcl slt th3 src
The exact same sqlite3_rtree_geometry structure is used for every callback for same MATCH operator in the same query.
/* IMP: R-53759-57366 */
# EVIDENCE-OF: R-53759-57366 The exact same sqlite3_rtree_geometry # structure is used for every callback for same MATCH operator in the # same query.
R-60247-35692-05586-10115-22101-12155-14694-19352 tcl slt th3 src
The contents of the sqlite3_rtree_geometry structure are initialized by SQLite but are not subsequently modified.
/* IMP: R-60247-35692 */
# EVIDENCE-OF: R-60247-35692 The contents of the sqlite3_rtree_geometry # structure are initialized by SQLite but are not subsequently modified.
R-31246-29731-62646-60277-08521-29245-49284-60874 tcl slt th3 src
The pContext member of the sqlite3_rtree_geometry structure is always set to a copy of the pContext argument passed to sqlite3_rtree_geometry_callback() when the callback is registered.
/* IMP: R-31246-29731 */
# EVIDENCE-OF: R-31246-29731 The pContext member of the # sqlite3_rtree_geometry structure is always set to a copy of the # pContext argument passed to sqlite3_rtree_geometry_callback() when the # callback is registered.
R-09904-19077-60402-31152-09250-23294-22236-64637 tcl slt th3 src
The aParam[] array (size nParam) contains the parameter values passed to the SQL function on the right-hand side of the MATCH operator.
/* IMP: R-09904-19077 */
# EVIDENCE-OF: R-09904-19077 The aParam[] array (size nParam) contains # the parameter values passed to the SQL function on the right-hand side # of the MATCH operator.
R-44448-00687-59565-33416-30258-38835-37742-50898 tcl slt th3 src
The pUser and xDelUser members of the sqlite3_rtree_geometry structure are initially set to NULL.
/* IMP: R-44448-00687 */
# EVIDENCE-OF: R-44448-00687 The pUser and xDelUser members of the # sqlite3_rtree_geometry structure are initially set to NULL.
R-55837-00155-61561-08494-32854-35753-30155-49706 tcl slt th3 src
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).
/* IMP: R-55837-00155 */
# EVIDENCE-OF: R-55837-00155 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).
R-34745-08839-34242-42308-04034-17314-18313-24494 tcl slt th3 src
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.
/* IMP: R-34745-08839 */
# EVIDENCE-OF: R-34745-08839 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.
R-28176-28813-25399-58317-42934-47980-64589-03329 tcl slt th3 src
The xGeom callback always does a depth-first search of the r-tree.
/* IMP: R-28176-28813 */
# EVIDENCE-OF: R-28176-28813 The xGeom callback always does a # depth-first search of the r-tree.
R-47257-47871-22083-44604-28744-21660-36470-17217 tcl slt th3 src
Smaller scores are processed first.
/* IMP: R-47257-47871 */
# EVIDENCE-OF: R-47257-47871 Smaller scores are processed first.
R-19244-03478-32061-23000-56536-05403-47491-06826 tcl slt th3 src
The leaves have a level of 0.
/* IMP: R-19244-03478 */
# EVIDENCE-OF: R-19244-03478 The leaves have a level of 0.
R-26102-39000-00300-53165-31110-34521-05669-39517 tcl slt th3 src
The mxLevel entry in the sqlite3_rtree_query_info structure is the level value for the root of the R*Tree.
/* IMP: R-26102-39000 */
# EVIDENCE-OF: R-26102-39000 The mxLevel entry in the # sqlite3_rtree_query_info structure is the level value for the root of # the R*Tree.
R-17759-10613-53810-53402-33339-35108-00085-57750 tcl slt th3 src
Most R*Tree queries use a depth-first search. This is accomplished by setting the rScore equal to iLevel.
/* IMP: R-17759-10613 */
# EVIDENCE-OF: R-17759-10613 Most R*Tree queries use a depth-first # search. This is accomplished by setting the rScore equal to iLevel.
R-44638-50196-46982-43265-31220-24766-09972-56099 tcl slt th3 src
However, some application may prefer a breadth-first search, which can be accomplished by setting rScore to mxLevel-iLevel.
/* IMP: R-44638-50196 */
# EVIDENCE-OF: R-44638-50196 However, some application may prefer a # breadth-first search, which can be accomplished by setting rScore to # mxLevel-iLevel.
R-33113-07215-37933-59376-21317-00912-14100-16891 tcl slt th3 src
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.
/* IMP: R-33113-07215 */
# EVIDENCE-OF: R-33113-07215 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.
R-21171-34919-23602-58467-34631-37001-49601-29313 tcl slt th3 src
The eParentWithin and rParentScore values are copies of the eWithin and rScore values from the containing subtree of the current row.
/* IMP: R-21171-34919 */
# EVIDENCE-OF: R-21171-34919 The eParentWithin and rParentScore values # are copies of the eWithin and rScore values from the containing # subtree of the current row.
R-38049-49177-51808-41050-10295-13822-05309-22802 tcl slt th3 src
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.
/* IMP: R-38049-49177 */
# EVIDENCE-OF: R-38049-49177 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.
R-09347-53396-09377-17353-50136-41410-13881-29341 tcl slt th3 src
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.
/* IMP: R-09347-53396 */
# EVIDENCE-OF: R-09347-53396 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.
R-23552-22587-27822-03022-61455-36680-30849-34520 tcl slt th3 src
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.
/* IMP: R-23552-22587 */
# EVIDENCE-OF: R-23552-22587 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.
R-06024-54164-19422-11836-49964-56179-07103-14892 tcl slt th3 src
Two or more MATCH operators are allowed in the same WHERE clause, as long as they are connected by AND operators.
/* IMP: R-06024-54164 */
# EVIDENCE-OF: R-06024-54164 Two or more MATCH operators are allowed in # the same WHERE clause, as long as they are connected by AND operators.
R-48498-17552-64242-05980-09276-07161-21761-29741 tcl slt th3 src
The priority assigned to each node in the search is the lowest priority returned by any of the MATCH operators.
/* IMP: R-48498-17552 */
# EVIDENCE-OF: R-48498-17552 The priority assigned to each node in the # search is the lowest priority returned by any of the MATCH operators.