SQLite Requirement Matrix Details
rtree.html
Index Summary Markup Original
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.
tcl/rtreedoc.test:96 th3/req1/rtreereq01.test: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.
tcl/rtreedoc.test:116 th3/req1/rtreereq01.test:90
/* 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.
tcl/rtreedoc.test:170 th3/req1/rtreereq03.test:29
/* 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.
tcl/rtreedoc.test:51 th3/req1/rtreereq01.test:18
/* 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.
tcl/rtreedoc.test:55 th3/req1/rtreereq01.test:20
/* 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.
tcl/rtreedoc.test:59 th3/req1/rtreereq01.test:22
/* 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.
tcl/rtreedoc.test:65 th3/req1/rtreereq01.test:24
/* 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.
tcl/rtreedoc.test:71 th3/req1/rtreereq01.test:26
/* 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.
tcl/rtreedoc.test:80 th3/req1/rtreereq01.test:68
/* 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.
tcl/rtreedoc.test:113 th3/req1/rtreereq01.test:139
/* 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-46866-24036-53947-28237-58028-26702-04025-02337 tcl slt th3 src
It may only store a 64-bit signed integer value.
tcl/rtreedoc.test:119 th3/req1/rtreereq01.test:149
/* IMP: R-46866-24036 */
# EVIDENCE-OF: R-46866-24036 It may only store a 64-bit signed integer # value.
R-15544-29079-59468-56673-65004-28971-16108-35057 tcl slt th3 src
Inserting a NULL value into this column causes SQLite to automatically generate a new unique primary key value.
tcl/rtreedoc.test:149 th3/req1/rtreereq01.test:152
/* IMP: R-15544-29079 */
# EVIDENCE-OF: R-15544-29079 Inserting a NULL value into this column # causes SQLite to automatically generate a new unique primary key # value.
R-00250-64843-03340-59080-00214-51349-19518-37616 tcl slt th3 src
If an attempt is made to insert any other non-integer value into this column, the r-tree module silently converts it to an integer before writing it into the database.
tcl/rtreedoc.test:122 th3/req1/rtreereq01.test:156
/* IMP: R-00250-64843 */
# EVIDENCE-OF: R-00250-64843 If an attempt is made to insert any other # non-integer value into this column, the r-tree module silently # converts it to an integer before writing it into the database.
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.
tcl/rtreedoc.test:203 th3/req1/rtreereq01.test:198
/* 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.
tcl/rtreedoc.test:230 th3/req1/rtreereq01.test:210
/* 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-39153-14977-19052-49938-18299-33449-45520-33553 tcl slt th3 src
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.
tcl/rtreedoc.test:234 th3/req1/rtreereq01.test:214
/* IMP: R-39153-14977 */
# EVIDENCE-OF: R-39153-14977 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.
R-15142-18077-19638-26452-28411-07428-50333-27294 tcl slt th3 src
A new R*Tree index is created as follows:
CREATE VIRTUAL TABLE <name> USING rtree(<column-names>);
tcl/rtreedoc.test:283 th3/req1/rtreereq02.test:12
/* IMP: R-15142-18077 */
# EVIDENCE-OF: R-15142-18077 A new R*Tree index is created as follows: # CREATE VIRTUAL TABLE <name> USING rtree(<column-names>);
R-51698-09302-57495-51617-34464-63477-12867-40927 tcl slt th3 src
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.
tcl/rtreedoc.test:289 th3/req1/rtreereq01.test:14
/* IMP: R-51698-09302 */
# EVIDENCE-OF: R-51698-09302 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.
R-50130-53472-08801-49768-51865-55888-22455-32076 tcl slt th3 src
The virtual <name> table creates three shadow tables to actually store its content.
tcl/rtreedoc.test:294 th3/req1/rtreereq02.test:23
/* IMP: R-50130-53472 */
# EVIDENCE-OF: R-50130-53472 The virtual <name> table creates # three shadow tables to actually store its content.
R-45256-35998-36415-19291-28291-06839-08654-39658 tcl slt th3 src
The names of these shadow tables are:
<name>_node
<name>_rowid
<name>_parent
tcl/rtreedoc.test:300 th3/req1/rtreereq02.test:26
/* IMP: R-45256-35998 */
# EVIDENCE-OF: R-45256-35998 The names of these shadow tables are: # <name>_node <name>_rowid <name>_parent
R-02287-33529-57702-51380-05125-54682-23740-46632 tcl slt th3 src
The shadow tables are ordinary SQLite data tables.
tcl/rtreedoc.test:324 th3/req1/rtreereq02.test:66
/* IMP: R-02287-33529 */
# EVIDENCE-OF: R-02287-33529 The shadow tables are ordinary SQLite data # tables.
R-10863-13089-16518-46448-48155-27413-52501-54942 tcl slt th3 src
You can query them directly if you like, though this unlikely to reveal anything particularly useful.
tcl/rtreedoc.test:339 th3/req1/rtreereq02.test:69
/* IMP: R-10863-13089 */
# EVIDENCE-OF: R-10863-13089 You can query them directly if you like, # though this unlikely to reveal anything particularly useful.
R-05650-46070-32640-12192-03987-30502-33558-23123 tcl slt th3 src
And you can UPDATE, DELETE, INSERT or even DROP the shadow tables, though doing so will corrupt your R*Tree index.
tcl/rtreedoc.test:349 th3/req1/rtreereq02.test:92
/* IMP: R-05650-46070 */
# EVIDENCE-OF: R-05650-46070 And you can UPDATE, DELETE, INSERT or even # DROP the shadow tables, though doing so will corrupt your R*Tree # index.
R-11241-54478-18941-45655-01844-39578-11562-47598 tcl slt th3 src
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 );
tcl/rtreedoc.test:309 th3/cov1/rtree17.test:13
/* IMP: R-11241-54478 */
# EVIDENCE-OF: R-11241-54478 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 );
R-44253-50720-20114-27313-10573-47729-39091-54779 tcl slt th3 src
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.
tcl/rtreedoc.test:372 th3/cov1/rtree17.test:35
/* IMP: R-44253-50720 */
# EVIDENCE-OF: R-44253-50720 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-52032-06717-09203-13355-40298-11149-14076-60739 tcl slt th3 src
This means, for example, that if you try to give a column a type affinity or add a constraint such as UNIQUE or NOT NULL or DEFAULT to a column, those extra tokens are accepted as valid, but they do not change the behavior of the rtree.
tcl/rtreedoc.test:385 th3/cov1/rtree17.test:40
/* IMP: R-52032-06717 */
# EVIDENCE-OF: R-52032-06717 This means, for example, that if you try to # give a column a type affinity or add a constraint such as UNIQUE or # NOT NULL or DEFAULT to a column, those extra tokens are accepted as # valid, but they do not change the behavior of the rtree.
R-06893-30579-58161-11067-55212-01528-39309-12280 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 REAL.
tcl/rtreedoc.test:408 th3/cov1/rtree17.test:69
/* IMP: R-06893-30579 */
# EVIDENCE-OF: R-06893-30579 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 REAL.
R-06224-52418-62263-52571-38406-27585-18905-65018 tcl slt th3 src
In an RTREE_I32 virtual table, all columns have type affinity of INTEGER.
tcl/rtreedoc.test:421 th3/cov1/rtree17.test:73
/* IMP: R-06224-52418 */
# EVIDENCE-OF: R-06224-52418 In an RTREE_I32 virtual table, all columns # have type affinity of INTEGER.
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.
tcl/rtreedoc.test:446 th3/cov1/rtree01.test:12
/* 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-56987-45305-59514-58142-26369-61446-32398-17394 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 (28215, -80.781227, -80.604706, 35.208813, 35.297367), (28216, -80.957283, -80.840599, 35.235920, 35.367825), (28217, -80.960869, -80.869431, 35.133682, 35.208233), (28226, -80.878983, -80.778275, 35.060287, 35.154446), (28227, -80.745544, -80.555382, 35.130215, 35.236916), (28244, -80.844208, -80.841988, 35.223728, 35.225471), (28262, -80.809074, -80.682938, 35.276207, 35.377747), (28269, -80.851471, -80.735718, 35.272560, 35.407925), (28270, -80.794983, -80.728966, 35.059872, 35.161823), (28273, -80.994766, -80.875259, 35.074734, 35.172836), (28277, -80.876793, -80.767586, 35.001709, 35.101063), (28278, -81.058029, -80.956375, 35.044701, 35.223812), (28280, -80.844208, -80.841972, 35.225468, 35.227203), (28282, -80.846382, -80.844193, 35.223972, 35.225655);
tcl/rtreedoc.test:475 th3/req1/rtreereq03.test:14
/* IMP: R-56987-45305 */
# EVIDENCE-OF: R-56987-45305 So to insert some data into our sample # R*Tree index, we can do something like this: INSERT INTO demo_index # VALUES (28215, -80.781227, -80.604706, 35.208813, 35.297367), (28216, # -80.957283, -80.840599, 35.235920, 35.367825), (28217, -80.960869, # -80.869431, 35.133682, 35.208233), (28226, -80.878983, -80.778275, # 35.060287, 35.154446), (28227, -80.745544, -80.555382, 35.130215, # 35.236916), (28244, -80.844208, -80.841988, 35.223728, 35.225471), # (28262, -80.809074, -80.682938, 35.276207, 35.377747), (28269, # -80.851471, -80.735718, 35.272560, 35.407925), (28270, -80.794983, # -80.728966, 35.059872, 35.161823), (28273, -80.994766, -80.875259, # 35.074734, 35.172836), (28277, -80.876793, -80.767586, 35.001709, # 35.101063), (28278, -81.058029, -80.956375, 35.044701, 35.223812), # (28280, -80.844208, -80.841972, 35.225468, 35.227203), (28282, # -80.846382, -80.844193, 35.223972, 35.225655);
R-45880-07724-18025-09257-41536-03477-46499-61988 tcl slt th3 src
Any valid query will work against an R*Tree index.
tcl/rtreedoc.test:530 th3/cov1/rtree01.test:15
/* IMP: R-45880-07724 */
# EVIDENCE-OF: R-45880-07724 Any valid query will work against an R*Tree # index.
R-60814-18273-28443-15335-58927-41663-48386-29950 tcl slt th3 src
The R*Tree implementation just makes some kinds of queries especially efficient.
tcl/rtreedoc.test:546 th3/req1/rtreereq03.test:121
/* IMP: R-60814-18273 */
# EVIDENCE-OF: R-60814-18273 The R*Tree implementation just makes some # kinds of queries especially efficient.
R-37800-50174-18959-63478-23278-16020-00862-51147 tcl slt th3 src
Queries against the primary key are efficient:
SELECT * FROM demo_index WHERE id=28269;
tcl/rtreedoc.test:553 th3/req1/rtreereq03.test:179
/* IMP: R-37800-50174 */
# EVIDENCE-OF: R-37800-50174 Queries against the primary key are # efficient: SELECT * FROM demo_index WHERE id=28269;
R-35847-18866-22056-42363-43514-34366-42944-42710 tcl slt th3 src
The big reason for using an R*Tree is so that you can efficiently do range queries against the coordinate ranges.
tcl/rtreedoc.test:557 th3/req1/rtreereq03.test:117
/* IMP: R-35847-18866 */
# EVIDENCE-OF: R-35847-18866 The big reason for using an R*Tree is so # that you can efficiently do range queries against the coordinate # ranges.
R-49927-54202-04522-64908-10346-59629-31272-28673 tcl slt th3 src
For example, the main office of the SQLite project is located at 35.37785, -80.77470. To find which zipcodes might service that office, one could right:
SELECT id FROM demo_index WHERE minX<=-80.77470 AND maxX>=-80.77470 AND minY<=35.37785 AND maxY>=35.37785;
tcl/rtreedoc.test:561 th3/req1/rtreereq03.test:61
/* IMP: R-49927-54202 */
# EVIDENCE-OF: R-49927-54202 For example, the main office of the SQLite # project is located at 35.37785, -80.77470. To find which zipcodes # might service that office, one could right: SELECT id FROM demo_index # WHERE minX<=-80.77470 AND maxX>=-80.77470 AND minY<=35.37785 # AND maxY>=35.37785;
R-12823-37176-29858-38232-19401-37371-04323-52385 tcl slt th3 src
The query above will quickly locate all zipcodes that contain the SQLite main office in their bounding box, even if the R*Tree contains many entries.
tcl/rtreedoc.test:568 th3/req1/rtreereq03.test:113
/* IMP: R-12823-37176 */
# EVIDENCE-OF: R-12823-37176 The query above will quickly locate all # zipcodes that contain the SQLite main office in their bounding box, # even if the R*Tree contains many entries.
R-07351-00257-44890-08238-20091-47969-07482-23238 tcl slt th3 src
For example, to find all zipcode bounding boxes that overlap with the 28269 zipcode:
SELECT A.id FROM demo_index AS A, demo_index AS B WHERE A.maxX>=B.minX AND A.minX<=B.maxX AND A.maxY>=B.minY AND A.minY<=B.maxY AND B.id=28269;
tcl/rtreedoc.test:580 th3/req1/rtreereq03.test:79
/* IMP: R-07351-00257 */
# EVIDENCE-OF: R-07351-00257 For example, to find all zipcode bounding # boxes that overlap with the 28269 zipcode: SELECT A.id FROM demo_index # AS A, demo_index AS B WHERE A.maxX>=B.minX AND A.minX<=B.maxX # AND A.maxY>=B.minY AND A.minY<=B.maxY AND B.id=28269;
R-39094-01937-60067-64937-11731-20352-55473-40783 tcl slt th3 src
This second query will find both 28269 entry (since every bounding box overlaps with itself) and also other zipcode that is close enough to 28269 that their bounding boxes overlap.
tcl/rtreedoc.test:587 th3/req1/rtreereq03.test:84
/* IMP: R-39094-01937 */
# EVIDENCE-OF: R-39094-01937 This second query will find both 28269 # entry (since every bounding box overlaps with itself) and also other # zipcode that is close enough to 28269 that their bounding boxes # overlap.
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.
tcl/rtreedoc.test:611 th3/req1/rtreereq03.test:140
/* 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-22490-27246-39721-62527-58944-44667-39725-60392 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;
tcl/rtreedoc.test:615 th3/req1/rtreereq03.test:160
/* IMP: R-22490-27246 */
# EVIDENCE-OF: R-22490-27246 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;
R-08327-00674-34025-59801-39794-03725-53451-62789 tcl slt th3 src
By default, coordinates are stored in an R*Tree using 32-bit floating point values.
tcl/rtreedoc.test:636
/* IMP: R-08327-00674 */
# EVIDENCE-OF: R-08327-00674 By default, coordinates are stored in an # R*Tree using 32-bit floating point values.
R-39127-51288-21828-60522-16075-50686-33622-44137 tcl slt th3 src
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.
tcl/rtreedoc.test:652
/* IMP: R-39127-51288 */
# EVIDENCE-OF: R-39127-51288 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.
R-45870-62834-50679-52704-16239-12927-26811-24549 tcl slt th3 src
Thus, bounding boxes might be slightly larger than specified, but will never be any smaller.
tcl/rtreedoc.test:680
/* IMP: R-45870-62834 */
# EVIDENCE-OF: R-45870-62834 Thus, bounding boxes might be slightly # larger than specified, but will never be any smaller.
R-55979-39402-28756-48871-04161-58570-28531-57962 tcl slt th3 src
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.
tcl/rtreedoc.test:701
/* IMP: R-55979-39402 */
# EVIDENCE-OF: R-55979-39402 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.
R-00683-48865-45449-58832-46192-63065-52178-15689 tcl slt th3 src
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.
tcl/rtreedoc.test:730 th3/cov1/rtree22.test:33
/* IMP: R-00683-48865 */
# EVIDENCE-OF: R-00683-48865 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.
R-19740-29710-17840-49748-00054-03690-60264-24597 tcl slt th3 src
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;
tcl/rtreedoc.test:753 th3/cov1/rtree22.test:59
/* IMP: R-19740-29710 */
# EVIDENCE-OF: R-19740-29710 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;
R-52919-32711-64947-32390-17992-62474-27613-56874 tcl slt th3 src
Then the UPDATE might fail with an SQLITE_LOCKED error.
tcl/rtreedoc.test:760 th3/cov1/rtree22.test:66
/* IMP: R-52919-32711 */
# EVIDENCE-OF: R-52919-32711 Then the UPDATE might fail with an # SQLITE_LOCKED error.
R-32604-49843-58229-61598-46331-12065-60335-40228 tcl slt th3 src
Ordinary tables in SQLite are able to read and write at the same time.
tcl/rtreedoc.test:785 th3/cov1/rtree22.test:90
/* IMP: R-32604-49843 */
# EVIDENCE-OF: R-32604-49843 Ordinary tables in SQLite are able to read # and write at the same time.
R-06177-00576-54284-57124-19622-29934-36403-49341 tcl slt th3 src
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.
tcl/rtreedoc.test:818 th3/cov1/rtree22.test:49
/* IMP: R-06177-00576 */
# EVIDENCE-OF: R-06177-00576 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.
R-21062-30088-46553-38702-08225-06060-08730-53281 tcl slt th3 src
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 );
tcl/rtreedoc.test:846 th3/cov1/rtree18.test:131
/* IMP: R-21062-30088 */
# EVIDENCE-OF: R-21062-30088 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 );
R-32671-43888-13335-47508-57448-46084-07377-01269 tcl slt th3 src
Then an efficient way to find the specific ZIP code for the main SQLite office would 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, 35.37785, -80.77470) AND minX<=-80.77470 AND maxX>=-80.77470 AND minY<=35.37785 AND maxY>=35.37785;
tcl/rtreedoc.test:907 th3/cov1/rtree18.test:147
/* IMP: R-32671-43888 */
# EVIDENCE-OF: R-32671-43888 Then an efficient way to find the specific # ZIP code for the main SQLite office would 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, # 35.37785, -80.77470) AND minX<=-80.77470 AND maxX>=-80.77470 AND # minY<=35.37785 AND maxY>=35.37785;
R-32761-23915-57805-21917-52612-65333-62768-05976 tcl slt th3 src
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, 35.37785, -80.77470);
tcl/rtreedoc.test:922 th3/cov1/rtree18.test:180
/* IMP: R-32761-23915 */
# EVIDENCE-OF: R-32761-23915 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, # 35.37785, -80.77470);
R-40261-32799-46297-03234-48132-23711-35487-26926 tcl slt th3 src
The problem with this latter query is that it must apply the contained_in() function to all entries in the demo_data table.
tcl/rtreedoc.test:932 th3/cov1/rtree18.test:194
/* IMP: R-40261-32799 */
# EVIDENCE-OF: R-40261-32799 The problem with this latter query is that # it must apply the contained_in() function to all entries in the # demo_data table.
R-24212-52761-31234-49044-16935-34331-57442-65460 tcl slt th3 src
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.
tcl/rtreedoc.test:941 th3/cov1/rtree18.test:172
/* IMP: R-24212-52761 */
# EVIDENCE-OF: R-24212-52761 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.
R-39057-63901-55190-21860-54230-15728-49391-11241 tcl slt th3 src
The R*Tree index did not find the exact answer itself, it merely limited the search space.
tcl/rtreedoc.test:947 th3/cov1/rtree18.test:185
/* IMP: R-39057-63901 */
# EVIDENCE-OF: R-39057-63901 The R*Tree index did not find the exact # answer itself, it merely limited the search space.
R-46566-43213-59555-56161-21828-03379-13796-34244 tcl slt th3 src
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".
tcl/rtreedoc.test:964 th3/cov1/rtree18.test:50
/* IMP: R-46566-43213 */
# EVIDENCE-OF: R-46566-43213 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".
R-41287-48160-23788-20080-08902-48898-03032-27224 tcl slt th3 src
Auxiliary columns are marked with a "+" symbol before the column name.
tcl/rtreedoc.test:969 th3/cov1/rtree18.test:55
/* IMP: R-41287-48160 */
# EVIDENCE-OF: R-41287-48160 Auxiliary columns are marked with a "+" # symbol before the column name.
R-30514-26093-50789-47903-26935-14001-56493-58208 tcl slt th3 src
Auxiliary columns must come after all of the coordinate boundary columns.
tcl/rtreedoc.test:995 th3/cov1/rtree18.test:85
/* IMP: R-30514-26093 */
# EVIDENCE-OF: R-30514-26093 Auxiliary columns must come after all of # the coordinate boundary columns.
R-01280-03635-04913-09225-39257-42860-12445-27024 tcl slt th3 src
An RTREE table can have no more than 100 columns total. In other words, the count of columns including the integer primary key column, the coordinate boundary columns, and all auxiliary columns must be 100 or less.
tcl/rtreedoc.test:1010 th3/cov1/rtree18.test:96
/* IMP: R-01280-03635 */
# EVIDENCE-OF: R-01280-03635 An RTREE table can have no more than 100 # columns total. In other words, the count of columns including the # integer primary key column, the coordinate boundary columns, and all # auxiliary columns must be 100 or less.
R-05552-15084-05102-10878-43028-26070-39117-22765 tcl slt th3 src
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 );
tcl/rtreedoc.test:1073 th3/cov1/rtree18.test:58
/* IMP: R-05552-15084 */
# EVIDENCE-OF: R-05552-15084 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-26099-32169-00127-03094-09261-00142-37858-62464 tcl slt th3 src
SELECT objname FROM demo_index2 WHERE contained_in(boundary, 35.37785, -80.77470) AND minX<=-80.77470 AND maxX>=-80.77470 AND minY<=35.37785 AND maxY>=35.37785;
tcl/rtreedoc.test:1111 th3/cov1/rtree18.test:202
/* IMP: R-26099-32169 */
# EVIDENCE-OF: R-26099-32169 SELECT objname FROM demo_index2 WHERE # contained_in(boundary, 35.37785, -80.77470) AND minX<=-80.77470 AND # maxX>=-80.77470 AND minY<=35.37785 AND maxY>=35.37785;
R-24021-02490-44193-43433-07494-30276-16135-35345 tcl slt th3 src
For auxiliary columns, only the name of the column matters. The type affinity is ignored.
tcl/rtreedoc.test:1166 th3/cov1/rtree18.test:217
/* IMP: R-24021-02490 */
# EVIDENCE-OF: R-24021-02490 For auxiliary columns, only the name of the # column matters. The type affinity is ignored.
R-39906-44154-56692-22287-22902-21770-04912-62564 tcl slt th3 src
Constraints such as NOT NULL, UNIQUE, REFERENCES, or CHECK are also ignored.
tcl/rtreedoc.test:1169 th3/cov1/rtree18.test:228
/* IMP: R-39906-44154 */
# EVIDENCE-OF: R-39906-44154 Constraints such as NOT NULL, UNIQUE, # REFERENCES, or CHECK are also ignored.
R-22000-53613-20552-31854-09839-01114-23095-55500 tcl slt th3 src
The default virtual table ("rtree") stores coordinates as single-precision (4-byte) floating point numbers.
tcl/rtreedoc.test:639
/* IMP: R-22000-53613 */
# EVIDENCE-OF: R-22000-53613 The default virtual table ("rtree") stores
# coordinates as single-precision (4-byte) floating point numbers.
R-21011-43790-08313-49545-30750-27979-18807-17557 tcl slt th3 src
If integer coordinates are desired, declare the table using "rtree_i32" instead:
CREATE VIRTUAL TABLE intrtree USING rtree_i32(id,x0,x1,y0,y1,z0,z1);
tcl/rtreedoc.test:1218
/* IMP: R-21011-43790 */
# EVIDENCE-OF: R-21011-43790 If integer coordinates are desired, declare # the table using "rtree_i32" instead: CREATE VIRTUAL TABLE intrtree # USING rtree_i32(id,x0,x1,y0,y1,z0,z1);
R-09193-49806-52898-46442-20087-60215-15458-19610 tcl slt th3 src
An rtree_i32 stores coordinates as 32-bit signed integers.
tcl/rtreedoc.test:1227
/* IMP: R-09193-49806 */
# EVIDENCE-OF: R-09193-49806 An rtree_i32 stores coordinates as 32-bit # signed integers.
R-26131-19960-12825-50697-19032-51955-35203-04436 tcl slt th3 src
Even though it stores values using integer, the rtree_i32 virtual table still uses floating point computations internally as part of the r-tree algorithm.
/* IMP: R-26131-19960 */
# EVIDENCE-OF: R-26131-19960 Even though it stores values using integer, # the rtree_i32 virtual table still uses floating point computations # internally as part of the r-tree algorithm.
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).
tcl/rtreedoc2.test:34 th3/cov1/rtree03.test:114 th3/cov1/rtree04.test:93
/* 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.
tcl/rtreedoc2.test:81 th3/cov1/rtree03.test:157 th3/cov1/rtree04.test:177
/* 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)
tcl/rtreedoc2.test:61
/* 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.
tcl/rtreedoc2.test:72 th3/cov1/rtree03.test:164 th3/cov1/rtree04.test:184
/* 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.
tcl/test_rtreedoc.c:131 th3/cov1/rtree03.test:15
/* 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.
tcl/test_rtreedoc.c:134 tcl/test_rtreedoc.c:146 th3/cov1/rtree03.test:18
/* 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.
tcl/rtreedoc2.test:111 tcl/test_rtreedoc.c:147
/* 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.
tcl/rtreedoc2.test:115 th3/cov1/rtree03.test:51
/* 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.
tcl/test_rtreedoc.c:138 tcl/test_rtreedoc.c:148 th3/cov1/rtree03.test:23
/* 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.
tcl/test_rtreedoc.c:141 tcl/test_rtreedoc.c:149 tcl/test_rtreedoc.c:161 tcl/test_rtreedoc.c:167 th3/cov1/rtree03.test:26
/* 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.
tcl/rtreedoc2.test:146 th3/cov1/rtree03.test:188
/* 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.
tcl/rtreedoc2.test:163 th3/cov1/rtree03.test:71
/* 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.
tcl/rtreedoc2.test:181
/* 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.
tcl/rtreedoc2.test:203 th3/cov1/rtree03.test:44
/* 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.
tcl/rtreedoc2.test:230
/* 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.
tcl/rtreedoc2.test:252 th3/cov1/rtree03.test:76
/* 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).
tcl/rtreedoc2.test:265 th3/cov1/rtree03.test:91
/* 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.
tcl/rtreedoc2.test:271 th3/cov1/rtree03.test:82
/* 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.
tcl/rtreedoc2.test:301
/* 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.
tcl/rtreedoc3.test:117
/* IMP: R-47257-47871 */
# EVIDENCE-OF: R-47257-47871 Smaller scores are processed first.
R-54708-13595-17062-38783-63256-30039-55932-60035 tcl slt th3 src
An R*Tree query is initialized by making the root node the only entry in a priority queue sorted by rScore.
tcl/rtreedoc3.test:100
/* IMP: R-54708-13595 */
# EVIDENCE-OF: R-54708-13595 An R*Tree query is initialized by making # the root node the only entry in a priority queue sorted by rScore.
R-60002-49798-32276-44958-26437-44603-53115-17285 tcl slt th3 src
The query proceeds by extracting the entry from the priority queue that has the lowest score.
tcl/rtreedoc3.test:130
/* IMP: R-60002-49798 */
# EVIDENCE-OF: R-60002-49798 The query proceeds by extracting the entry # from the priority queue that has the lowest score.
R-13214-54017-56527-15900-43523-22557-52387-44538 tcl slt th3 src
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.
tcl/rtreedoc3.test:225
/* IMP: R-13214-54017 */
# EVIDENCE-OF: R-13214-54017 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.
R-65127-42665-35537-26123-60886-44164-20363-50210 tcl slt th3 src
If the extracted priority queue entry is a node (a subtree), then the next child of that node is passed to the xQueryFunc callback.
tcl/rtreedoc3.test:164
/* IMP: R-65127-42665 */
# EVIDENCE-OF: R-65127-42665 If the extracted priority queue entry is a # node (a subtree), then the next child of that node is passed to the # xQueryFunc callback.
R-07194-63805-34087-03143-36787-50993-50249-34192 tcl slt th3 src
If the node has more children then it is returned to the priority queue. Otherwise it is discarded.
tcl/rtreedoc3.test:209
/* IMP: R-07194-63805 */
# EVIDENCE-OF: R-07194-63805 If the node has more children then it is # returned to the priority queue. Otherwise it is discarded.
R-28754-35153-48498-07178-42088-22812-48106-51904 tcl slt th3 src
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.
tcl/rtreedoc3.test:194
/* IMP: R-28754-35153 */
# EVIDENCE-OF: R-28754-35153 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.
R-08681-45277-14100-51312-28696-23775-11578-48916 tcl slt th3 src
Subelements that return NOT_WITHIN are discarded.
tcl/rtreedoc3.test:198 th3/cov1/rtree04.test:64
/* IMP: R-08681-45277 */
# EVIDENCE-OF: R-08681-45277 Subelements that return NOT_WITHIN are # discarded.
R-57438-45968-34478-11728-33446-10820-01022-63673 tcl slt th3 src
The query runs until the priority queue is empty.
tcl/rtreedoc3.test:242
/* IMP: R-57438-45968 */
# EVIDENCE-OF: R-57438-45968 The query runs until the priority queue is # empty.
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.
th3/cov1/rtree04.test:291
/* 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.
th3/cov1/rtree04.test:287
/* 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.
th3/cov1/rtree04.test:277
/* 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.
R-33789-46762-48757-32242-41831-26284-33607-40788 tcl slt th3 src
The content of an R*Tree index is actually stored in three ordinary SQLite tables with names derived from the name of the R*Tree.
tcl/rtreedoc.test:1318 th3/req1/rtreereq02.test:29
/* IMP: R-33789-46762 */
# EVIDENCE-OF: R-33789-46762 The content of an R*Tree index is actually # stored in three ordinary SQLite tables with names derived from the # name of the R*Tree.
R-39849-06566-59022-51394-17295-59441-01164-37583 tcl slt th3 src
This is their schema:
CREATE TABLE %_node(nodeno INTEGER PRIMARY KEY, data) CREATE TABLE %_parent(nodeno INTEGER PRIMARY KEY, parentnode) CREATE TABLE %_rowid(rowid INTEGER PRIMARY KEY, nodeno)
tcl/rtreedoc.test:1322 th3/req1/rtreereq02.test:47
/* IMP: R-39849-06566 */
# EVIDENCE-OF: R-39849-06566 This is their schema: CREATE TABLE # %_node(nodeno INTEGER PRIMARY KEY, data) CREATE TABLE %_parent(nodeno # INTEGER PRIMARY KEY, parentnode) CREATE TABLE %_rowid(rowid INTEGER # PRIMARY KEY, nodeno)
R-07489-10051-36321-14153-64085-37809-17765-53517 tcl slt th3 src
The "%" in the name of each shadow table is replaced by the name of the R*Tree virtual table. So, if the name of the R*Tree table is "xyz" then the three shadow tables would be "xyz_node", "xyz_parent", and "xyz_rowid".
tcl/rtreedoc.test:1327 th3/req1/rtreereq02.test:52
/* IMP: R-07489-10051 */
# EVIDENCE-OF: R-07489-10051 The "%" in the name of each shadow table is # replaced by the name of the R*Tree virtual table. So, if the name of # the R*Tree table is "xyz" then the three shadow tables would be # "xyz_node", "xyz_parent", and "xyz_rowid".
R-51070-59303-35224-08762-04161-61049-26155-15772 tcl slt th3 src
There is one entry in the %_node table for each R*Tree node.
tcl/rtreedoc.test:1343 th3/req1/rtreereq04.test:22
/* IMP: R-51070-59303 */
# EVIDENCE-OF: R-51070-59303 There is one entry in the %_node table for # each R*Tree node.
R-27261-09153-10518-18545-23647-39902-53687-11529 tcl slt th3 src
All nodes other than the root have an entry in the %_parent shadow table that identifies the parent node.
tcl/rtreedoc.test:1359 th3/req1/rtreereq04.test:37
/* IMP: R-27261-09153 */
# EVIDENCE-OF: R-27261-09153 All nodes other than the root have an entry # in the %_parent shadow table that identifies the parent node.
R-02358-35037-18853-36293-47263-41920-32022-30649 tcl slt th3 src
The %_rowid shadow table maps entry rowids to the node that contains that entry.
tcl/rtreedoc.test:1368 th3/req1/rtreereq04.test:48
/* IMP: R-02358-35037 */
# EVIDENCE-OF: R-02358-35037 The %_rowid shadow table maps entry rowids # to the node that contains that entry.
R-65201-22208-38592-41579-38769-23544-65327-05998 tcl slt th3 src
Extra columns appended to the %_rowid table hold the content of auxiliary columns.
tcl/rtreedoc.test:1390
/* IMP: R-65201-22208 */
# EVIDENCE-OF: R-65201-22208 Extra columns appended to the %_rowid table # hold the content of auxiliary columns.
R-44161-28345-50691-59749-28348-63101-44161-38481 tcl slt th3 src
The names of these extra %_rowid columns are probably not the same as the actual auxiliary column names.
tcl/rtreedoc.test:1393
/* IMP: R-44161-28345 */
# EVIDENCE-OF: R-44161-28345 The names of these extra %_rowid columns # are probably not the same as the actual auxiliary column names.
R-13571-45795-18222-46807-04385-60941-40437-40817 tcl slt th3 src
The scalar SQL function rtreecheck(R) or rtreecheck(S,R) runs an integrity check on the rtree table named R contained within database S.
tcl/rtreedoc.test:1427 th3/cov1/rtree25.test:11
/* IMP: R-13571-45795 */
# EVIDENCE-OF: R-13571-45795 The scalar SQL function rtreecheck(R) or # rtreecheck(S,R) runs an integrity check on the rtree table named R # contained within database S.
R-36011-59963-14175-08508-02648-47269-55860-35860 tcl slt th3 src
The function returns a human-language description of any problems found, or the string 'ok' if everything is ok.
tcl/rtreedoc.test:1431 th3/cov1/rtree25.test:15
/* IMP: R-36011-59963 */
# EVIDENCE-OF: R-36011-59963 The function returns a human-language # description of any problems found, or the string 'ok' if everything is # ok.
R-45759-33459-43041-40737-28230-64845-22840-44318 tcl slt th3 src
Example: To verify that an R*Tree named "demo_index" is well-formed and internally consistent, run:
SELECT rtreecheck('demo_index');
tcl/rtreedoc.test:1468 th3/cov1/rtree25.test:230
/* IMP: R-45759-33459 */
# EVIDENCE-OF: R-45759-33459 Example: To verify that an R*Tree named
# "demo_index" is well-formed and internally consistent, run: SELECT
# rtreecheck('demo_index');
R-02555-31045-40373-53400-00989-29508-46660-48239 tcl slt th3 src
for each dimension, (coord1 <= coord2).
tcl/rtreedoc.test:1490 th3/cov1/rtree25.test:76
/* IMP: R-02555-31045 */
# EVIDENCE-OF: R-02555-31045 for each dimension, (coord1 <= coord2).
R-13844-15873-15285-53366-38279-55189-17563-43149 tcl slt th3 src
unless the cell is on the root node, that the cell is bounded by the parent cell on the parent node.
tcl/rtreedoc.test:1508 th3/cov1/rtree25.test:129
/* IMP: R-13844-15873 */
# EVIDENCE-OF: R-13844-15873 unless the cell is on the root node, that # the cell is bounded by the parent cell on the parent node.
R-02505-03621-00543-52540-17854-51798-01746-35880 tcl slt th3 src
for leaf nodes, that there is an entry in the %_rowid table corresponding to the cell's rowid value that points to the correct node.
tcl/rtreedoc.test:1525 th3/cov1/rtree25.test:218
/* IMP: R-02505-03621 */
# EVIDENCE-OF: R-02505-03621 for leaf nodes, that there is an entry in # the %_rowid table corresponding to the cell's rowid value that points # to the correct node.
R-50927-02218-50350-41045-59042-38975-34474-07107 tcl slt th3 src
for cells on non-leaf nodes, that there is an entry in the %_parent table mapping from the cell's child node to the node that it resides on.
tcl/rtreedoc.test:1538 th3/cov1/rtree25.test:206
/* IMP: R-50927-02218 */
# EVIDENCE-OF: R-50927-02218 for cells on non-leaf nodes, that there is # an entry in the %_parent table mapping from the cell's child node to # the node that it resides on.
R-23235-09153-11012-31105-54596-46572-36199-18601 tcl slt th3 src
That there are the same number of entries in the %_rowid table as there are leaf cells in the r-tree structure, and that there is a leaf cell that corresponds to each entry in the %_rowid table.
tcl/rtreedoc.test:1559
/* IMP: R-23235-09153 */
# EVIDENCE-OF: R-23235-09153 That there are the same number of entries # in the %_rowid table as there are leaf cells in the r-tree structure, # and that there is a leaf cell that corresponds to each entry in the # %_rowid table.
R-62800-43436-06493-51425-45940-03173-57151-39282 tcl slt th3 src
That there are the same number of entries in the %_parent table as there are non-leaf cells in the r-tree structure, and that there is a non-leaf cell that corresponds to each entry in the %_parent table.
tcl/rtreedoc.test:1570
/* IMP: R-62800-43436 */
# EVIDENCE-OF: R-62800-43436 That there are the same number of entries # in the %_parent table as there are non-leaf cells in the r-tree # structure, and that there is a non-leaf cell that corresponds to each # entry in the %_parent table.