# 2021 September 13

#

# The author disclaims copyright to this source code. In place of

# a legal notice, here is a blessing:

#

# May you do good and not evil.

# May you find forgiveness for yourself and forgive others.

# May you share freely, never taking more than you give.

#

#***********************************************************************

#

# The focus of this file is testing the r-tree extension.

#

if {![info exists testdir]} {

set testdir [file join [file dirname [info script]] .. .. test]

}

source [file join [file dirname [info script]] rtree_util.tcl]

source $testdir/tester.tcl

set testprefix rtreedoc

ifcapable !rtree {

finish_test

return

}

# This command returns the number of columns in table $tbl within the

# database opened by database handle $db

proc column_count {db tbl} {

set nCol 0

$db eval "PRAGMA table_info = $tbl" { incr nCol }

return $nCol

}

proc column_name_list {db tbl} {

set lCol [list]

$db eval "PRAGMA table_info = $tbl" {

lappend lCol $name

}

return $lCol

}

unset -nocomplain res

#-------------------------------------------------------------------------

#-------------------------------------------------------------------------

# Section 3 of documentation.

#-------------------------------------------------------------------------

#-------------------------------------------------------------------------

set testprefix rtreedoc-1

# EVIDENCE-OF: R-15060-13876 A 1-dimensional R*Tree thus has 3 columns.

do_execsql_test 1.1.1 { CREATE VIRTUAL TABLE rt1 USING rtree(id, x1,x2) }

do_test 1.1.2 { column_count db rt1 } 3

# EVIDENCE-OF: R-19353-19546 A 2-dimensional R*Tree has 5 columns.

do_execsql_test 1.2.1 { CREATE VIRTUAL TABLE rt2 USING rtree(id,x1,x2, y1,y2) }

do_test 1.2.2 { column_count db rt2 } 5

# EVIDENCE-OF: R-13615-19528 A 3-dimensional R*Tree has 7 columns.

do_execsql_test 1.3.1 {

CREATE VIRTUAL TABLE rt3 USING rtree(id, x1,x2, y1,y2, z1,z2)

}

do_test 1.3.2 { column_count db rt3 } 7

# EVIDENCE-OF: R-53479-41922 A 4-dimensional R*Tree has 9 columns.

do_execsql_test 1.4.1 {

CREATE VIRTUAL TABLE rt4 USING rtree(id, x1,x2, y1,y2, z1,z2, v1,v2)

}

do_test 1.4.2 { column_count db rt4 } 9

# EVIDENCE-OF: R-13981-28768 And a 5-dimensional R*Tree has 11 columns.

do_execsql_test 1.5.1 {

CREATE VIRTUAL TABLE rt5 USING rtree(id, x1,x2, y1,y2, z1,z2, v1,v2, w1,w2)

}

do_test 1.5.2 { column_count db rt5 } 11

# Attempt to create r-tree tables with 6 and 7 dimensions.

#

# EVIDENCE-OF: R-61533-25862 The SQLite R*Tree implementation does not

# support R*Trees wider than 5 dimensions.

do_catchsql_test 2.1.1 {

CREATE VIRTUAL TABLE rt6 USING rtree(

id, x1,x2, y1,y2, z1,z2, v1,v2, w1,w2, a1,a2

)

} {1 {Too many columns for an rtree table}}

do_catchsql_test 2.1.2 {

CREATE VIRTUAL TABLE rt6 USING rtree(

id, x1,x2, y1,y2, z1,z2, v1,v2, w1,w2, a1,a2, b1, b2

)

} {1 {Too many columns for an rtree table}}

# Attempt to create r-tree tables with no columns, a single column, or

# an even number of columns. This and the tests above establish that:

#

# EVIDENCE-OF: R-16717-50504 Each R*Tree index is a virtual table with

# an odd number of columns between 3 and 11.

foreach {tn cols err} {

1 "" "Too few columns for an rtree table"

2 "x" "Too few columns for an rtree table"

3 "x,y" "Too few columns for an rtree table"

4 "a,b,c,d" "Wrong number of columns for an rtree table"

5 "a,b,c,d,e,f" "Wrong number of columns for an rtree table"

6 "a,b,c,d,e,f,g,h" "Wrong number of columns for an rtree table"

7 "a,b,c,d,e,f,g,h,i,j" "Wrong number of columns for an rtree table"

8 "a,b,c,d,e,f,g,h,i,j,k,l" "Too many columns for an rtree table"

} {

do_catchsql_test 3.$tn "

CREATE VIRTUAL TABLE xyz USING rtree($cols)

" [list 1 $err]

}

# 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.

#

# EVIDENCE-OF: R-46619-65417 The first column is always a 64-bit signed

# integer primary key.

#

# EVIDENCE-OF: R-46866-24036 It may only store a 64-bit signed integer

# value.

#

# 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.

#

do_execsql_test 4.0 { CREATE VIRTUAL TABLE rt USING rtree(id, x1, x2) }

foreach {tn val res} {

1 10 10

2 10.6 10

3 10.99 10

4 '123' 123

5 X'313233' 123

6 -10 -10

7 9223372036854775807 9223372036854775807

8 -9223372036854775808 -9223372036854775808

9 '9223372036854775807' 9223372036854775807

10 '-9223372036854775808' -9223372036854775808

11 'hello+world' 0

} {

do_execsql_test 4.$tn.1 "

DELETE FROM rt;

INSERT INTO rt VALUES($val, 10, 20);

"

do_execsql_test 4.$tn.2 {

SELECT typeof(id), id FROM rt

} [list integer $res]

}

# EVIDENCE-OF: R-15544-29079 Inserting a NULL value into this column

# causes SQLite to automatically generate a new unique primary key

# value.

do_execsql_test 5.1 {

DELETE FROM rt;

INSERT INTO rt VALUES(100, 1, 2);

INSERT INTO rt VALUES(NULL, 1, 2);

}

do_execsql_test 5.2 { SELECT id FROM rt } {100 101}

do_execsql_test 5.3 {

INSERT INTO rt VALUES(9223372036854775807, 1, 2);

INSERT INTO rt VALUES(NULL, 1, 2);

}

do_execsql_test 5.4 {

SELECT count(*) FROM rt;

} 4

do_execsql_test 5.5 {

SELECT id IN(100, 101, 9223372036854775807) FROM rt ORDER BY 1;

} {0 1 1 1}

# EVIDENCE-OF: R-64317-38978 The other columns are pairs, one pair per

# dimension, containing the minimum and maximum values for that

# dimension, respectively.

#

# Show this by observing that attempts to insert rows with max>min fail.

#

do_execsql_test 6.1 {

CREATE VIRTUAL TABLE rtF USING rtree(id, x1,x2, y1,y2);

CREATE VIRTUAL TABLE rtI USING rtree_i32(id, x1,x2, y1,y2, z1,z2);

}

foreach {tn x1 x2 y1 y2 ok} {

1 10.3 20.1 30.9 40.2 1

2 10.3 20.1 40.2 30.9 0

3 10.3 30.9 20.1 40.2 1

4 20.1 10.3 30.9 40.2 0

} {

do_test 6.2.$tn {

catch { db eval { INSERT INTO rtF VALUES(NULL, $x1, $x2, $y1, $y2) } }

} [expr $ok==0]

}

foreach {tn x1 x2 y1 y2 z1 z2 ok} {

1 10 20 30 40 50 60 1

2 10 20 30 40 60 50 0

3 10 20 30 50 40 60 1

4 10 20 40 30 50 60 0

5 10 30 20 40 50 60 1

6 20 10 30 40 50 60 0

} {

do_test 6.3.$tn {

catch { db eval { INSERT INTO rtI VALUES(NULL,$x1,$x2,$y1,$y2,$z1,$z2) } }

} [expr $ok==0]

}

# 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.

#

# Show this by showing that large values are rounded in ways consistent

# with those two 32-bit types.

do_execsql_test 7.1 {

DELETE FROM rtI;

INSERT INTO rtI VALUES(

0, -2000000000, 2000000000, -5000000000, 5000000000,

-1000000000000, 10000000000000

);

SELECT * FROM rtI;

} {

0 -2000000000 2000000000 -705032704 705032704 727379968 1316134912

}

do_execsql_test 7.2 {

DELETE FROM rtF;

INSERT INTO rtF VALUES(

0, -2000000000, 2000000000,

-1000000000000, 10000000000000

);

SELECT * FROM rtF;

} {

0 -2000000000.0 2000000000.0 -1000000126976.0 10000000876544.0

}

# 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.

#

# 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.

do_execsql_test 8.1 {

DELETE FROM rtI;

INSERT INTO rtI VALUES(

1, 'hello world', X'616263', NULL, 44.5, 1000, 9999.9999

);

SELECT * FROM rtI;

} {

1 0 0 0 44 1000 9999

}

do_execsql_test 8.2 {

SELECT

typeof(x1), typeof(x2), typeof(y1), typeof(y2), typeof(z1), typeof(z2)

FROM rtI

} {integer integer integer integer integer integer}

do_execsql_test 8.3 {

DELETE FROM rtF;

INSERT INTO rtF VALUES(

1, 'hello world', X'616263', NULL, 44

);

SELECT * FROM rtF;

} {

1 0.0 0.0 0.0 44.0

}

do_execsql_test 8.4 {

SELECT

typeof(x1), typeof(x2), typeof(y1), typeof(y2)

FROM rtF

} {real real real real}

#-------------------------------------------------------------------------

#-------------------------------------------------------------------------

# Section 3.1 of documentation.

#-------------------------------------------------------------------------

#-------------------------------------------------------------------------

set testprefix rtreedoc-2

reset_db

foreach {tn name clist} {

1 t1 "id x1 x2"

2 t2 "id x1 x2 y1 y2 z1 z2"

} {

# EVIDENCE-OF: R-15142-18077 A new R*Tree index is created as follows:

# CREATE VIRTUAL TABLE <name> USING rtree(<column-names>);

do_execsql_test 1.$tn.1 "

CREATE VIRTUAL TABLE $name USING rtree([join $clist ,])

"

# 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.

do_test 1.$tn.2 { column_name_list db $name } [list {*}$clist]

# EVIDENCE-OF: R-50130-53472 The virtual <name> table creates

# three shadow tables to actually store its content.

do_execsql_test 1.$tn.3 {

SELECT count(*) FROM sqlite_schema

} [expr 1+3]

# EVIDENCE-OF: R-45256-35998 The names of these shadow tables are:

# <name>_node <name>_rowid <name>_parent

do_execsql_test 1.$tn.4 {

SELECT name FROM sqlite_schema WHERE rootpage>0 ORDER BY 1

} [list ${name}_node ${name}_parent ${name}_rowid]

do_execsql_test 1.$tn.5 "DROP TABLE $name"

}

# 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 );

do_execsql_test 2.0 {

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

);

INSERT INTO demo_index VALUES(1,2,3,4,5);

INSERT INTO demo_index VALUES(6,7,8,9,10);

}

# EVIDENCE-OF: R-02287-33529 The shadow tables are ordinary SQLite data

# tables.

#

# Ordinary tables. With ordinary sqlite_schema entries.

do_execsql_test 2.1 {

SELECT type, name, sql FROM sqlite_schema WHERE sql NOT LIKE '%virtual%'

} {

table demo_index_rowid

{CREATE TABLE "demo_index_rowid"(rowid INTEGER PRIMARY KEY,nodeno)}

table demo_index_node

{CREATE TABLE "demo_index_node"(nodeno INTEGER PRIMARY KEY,data)}

table demo_index_parent

{CREATE TABLE "demo_index_parent"(nodeno INTEGER PRIMARY KEY,parentnode)}

}

# EVIDENCE-OF: R-10863-13089 You can query them directly if you like,

# though this unlikely to reveal anything particularly useful.

#

# Querying:

do_execsql_test 2.2 {

SELECT count(*) FROM demo_index_node;

SELECT count(*) FROM demo_index_rowid;

SELECT count(*) FROM demo_index_parent;

} {1 2 0}

# 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.

do_execsql_test 2.3 {

DELETE FROM demo_index_rowid;

INSERT INTO demo_index_parent VALUES(2, 3);

UPDATE demo_index_node SET data = 'hello world'

}

do_catchsql_test 2.4 {

SELECT * FROM demo_index WHERE minX>10 AND maxX<30

} {1 {database disk image is malformed}}

do_execsql_test 2.5 {

DROP TABLE demo_index_rowid

}

#-------------------------------------------------------------------------

#-------------------------------------------------------------------------

# Section 3.1.1 of documentation.

#-------------------------------------------------------------------------

#-------------------------------------------------------------------------

set testprefix rtreedoc-3

reset_db

# 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.

#

foreach {tn cols lCol} {

1 {(id TEXT, x1 TEXT, x2 TEXT, y1 TEXT, y2 TEXT)} {id x1 x2 y1 y2}

2 {(id TEXT, x1 UNIQUE, x2 TEXT, y1 NOT NULL, y2 TEXT)} {id x1 x2 y1 y2}

3 {(id, x1 DEFAULT 4, x2 TEXT, y1 NOT NULL, y2 TEXT)} {id x1 x2 y1 y2}

} {

do_execsql_test 1.$tn.1 " CREATE VIRTUAL TABLE abc USING rtree $cols "

do_test 1.$tn.2 { column_name_list db abc } $lCol

# 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.

# Show there are no UNIQUE constraints

do_execsql_test 1.$tn.3 {

INSERT INTO abc VALUES(1, 10.0, 20.0, 10.0, 20.0);

INSERT INTO abc VALUES(2, 10.0, 20.0, 10.0, 20.0);

}

# Show the default values have not been modified

do_execsql_test 1.$tn.4 {

INSERT INTO abc DEFAULT VALUES;

SELECT * FROM abc WHERE rowid NOT IN (1,2)

} {3 0.0 0.0 0.0 0.0}

# Show that there are no NOT NULL constraints

do_execsql_test 1.$tn.5 {

INSERT INTO abc VALUES(NULL, NULL, NULL, NULL, NULL);

SELECT * FROM abc WHERE rowid NOT IN (1,2,3)

} {4 0.0 0.0 0.0 0.0}

# 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.

do_execsql_test 1.$tn.5 {

INSERT INTO abc VALUES('5', '5', '5', '5', '5');

SELECT * FROM abc WHERE rowid NOT IN (1,2,3,4)

} {5 5.0 5.0 5.0 5.0}

do_execsql_test 1.$tn.6 {

SELECT type FROM pragma_table_info('abc') ORDER BY cid

} {INT REAL REAL REAL REAL}

do_execsql_test 1.$tn.7 " CREATE VIRTUAL TABLE abc2 USING rtree_i32 $cols "

# EVIDENCE-OF: R-06224-52418 In an RTREE_I32 virtual table, all columns

# have type affinity of INTEGER.

do_execsql_test 1.$tn.8 {

INSERT INTO abc2 VALUES('6.0', '6.0', '6.0', '6.0', '6.0');

SELECT * FROM abc2

} {6 6 6 6 6}

do_execsql_test 1.$tn.9 {

SELECT type FROM pragma_table_info('abc2') ORDER BY cid

} {INT INT INT INT INT}

do_execsql_test 1.$tn.10 {

DROP TABLE abc;

DROP TABLE abc2;

}

}

#-------------------------------------------------------------------------

#-------------------------------------------------------------------------

# Section 3.2 of documentation.

#-------------------------------------------------------------------------

#-------------------------------------------------------------------------

set testprefix rtreedoc-4

reset_db

# EVIDENCE-OF: R-36195-31555 The usual INSERT, UPDATE, and DELETE

# commands work on an R*Tree index just like on regular tables.

#

# Create a regular table and an rtree table. Perform INSERT, UPDATE and

# DELETE operations, then observe that the contents of the two tables

# are identical.

do_execsql_test 1.0 {

CREATE VIRTUAL TABLE rt USING rtree(id, x1, x2);

CREATE TABLE t1(id INTEGER PRIMARY KEY, x1 REAL, x2 REAL);

}

foreach {tn sql} {

1 "INSERT INTO %TBL% VALUES(5, 11,12)"

2 "INSERT INTO %TBL% VALUES(11, -11,14.5)"

3 "UPDATE %TBL% SET x1=-99 WHERE id=11"

4 "DELETE FROM %TBL% WHERE x2=14.5"

5 "DELETE FROM %TBL%"

} {

set sql1 [string map {%TBL% rt} $sql]

set sql2 [string map {%TBL% t1} $sql]

do_execsql_test 1.$tn.0 $sql1

do_execsql_test 1.$tn.1 $sql2

set data1 [execsql {SELECT * FROM rt ORDER BY 1}]

set data2 [execsql {SELECT * FROM t1 ORDER BY 1}]

set res [expr {$data1==$data2}]

do_test 1.$tn.2 {set res} 1

}

# EVIDENCE-OF: R-56987-45305

do_execsql_test 2.0 {

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

);

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);

}

#-------------------------------------------------------------------------

#-------------------------------------------------------------------------

# Section 3.3 of documentation.

#-------------------------------------------------------------------------

#-------------------------------------------------------------------------

set testprefix rtreedoc-5

do_execsql_test 1.0 {

INSERT INTO demo_index

SELECT NULL, minX, maxX, minY+0.2, maxY+0.2 FROM demo_index;

INSERT INTO demo_index

SELECT NULL, minX+0.2, maxX+0.2, minY, maxY FROM demo_index;

INSERT INTO demo_index

SELECT NULL, minX, maxX, minY+0.4, maxY+0.4 FROM demo_index;

INSERT INTO demo_index

SELECT NULL, minX+0.4, maxX+0.4, minY, maxY FROM demo_index;

INSERT INTO demo_index

SELECT NULL, minX, maxX, minY+0.8, maxY+0.8 FROM demo_index;

INSERT INTO demo_index

SELECT NULL, minX+0.8, maxX+0.8, minY, maxY FROM demo_index;

SELECT count(*) FROM demo_index;

} {896}

proc do_vmstep_test {tn sql expr} {

execsql $sql

set step [db status vmstep]

do_test $tn.$step "expr {[subst $expr]}" 1

}

# EVIDENCE-OF: R-45880-07724 Any valid query will work against an R*Tree

# index.

do_execsql_test 1.1.0 {

CREATE TABLE demo_tbl AS SELECT * FROM demo_index;

}

foreach {tn sql} {

1 {SELECT * FROM %TBL% ORDER BY 1}

2 {SELECT max(minX) FROM %TBL% ORDER BY 1}

3 {SELECT max(minX) FROM %TBL% GROUP BY round(minY) ORDER BY 1}

} {

set sql1 [string map {%TBL% demo_index} $sql]

set sql2 [string map {%TBL% demo_tbl} $sql]

do_execsql_test 1.1.$tn $sql1 [execsql $sql2]

}

# EVIDENCE-OF: R-60814-18273 The R*Tree implementation just makes some

# kinds of queries especially efficient.

#

# The second query is more efficient than the first.

do_vmstep_test 1.2.1 {SELECT * FROM demo_index WHERE +rowid=28269} {$step>2000}

do_vmstep_test 1.2.2 {SELECT * FROM demo_index WHERE rowid=28269} {$step<100}

# EVIDENCE-OF: R-37800-50174 Queries against the primary key are

# efficient: SELECT * FROM demo_index WHERE id=28269;

do_vmstep_test 2.2 { SELECT * FROM demo_index WHERE id=28269 } {$step < 100}

# 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.

#

# EVIDENCE-OF: R-49927-54202

do_vmstep_test 2.3 {

SELECT id FROM demo_index

WHERE minX<=-80.77470 AND maxX>=-80.77470

AND minY<=35.37785 AND maxY>=35.37785;

} {$step < 100}

# 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.

#

do_execsql_test 2.4 {

SELECT id FROM demo_index

WHERE minX<=-80.77470 AND maxX>=-80.77470

AND minY<=35.37785 AND maxY>=35.37785;

} {

28322 28269

}

# 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;

#

# Also check that it is efficient

#

# 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.

#

# 28269 is there in the result.

#

do_vmstep_test 2.5.1 {

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

} {$step < 100}

do_execsql_test 2.5.2 {

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 ORDER BY +A.id;

} {

28215

28216

28262

28269

28286

28287

28291

28293

28298

28313

28320

28322

28336

}

# 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.

#

# 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;

do_vmstep_test 2.6.1 {

SELECT id FROM demo_index

WHERE maxY>=35.0 AND minY<=35.0;

} {$step < 100}

do_execsql_test 2.6.2 {

SELECT id FROM demo_index

WHERE maxY>=35.0 AND minY<=35.0;

} {}

#-------------------------------------------------------------------------

#-------------------------------------------------------------------------

# Section 3.4 of documentation.

#-------------------------------------------------------------------------

#-------------------------------------------------------------------------

set testprefix rtreedoc-6

reset_db

# EVIDENCE-OF: R-08327-00674 By default, coordinates are stored in an

# R*Tree using 32-bit floating point values.

#

# EVIDENCE-OF: R-22000-53613 The default virtual table ("rtree") stores

# coordinates as single-precision (4-byte) floating point numbers.

#

# Show this by showing that rounding is consistent with 32-bit float

# rounding.

do_execsql_test 1.0 {

CREATE VIRTUAL TABLE rt USING rtree(id, a,b);

}

do_execsql_test 1.1 {

INSERT INTO rt VALUES(14, -1000000000000, 1000000000000);

SELECT * FROM rt;

} {14 -1000000126976.0 1000000126976.0}

# 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.

foreach {tn val} {

1 100000000000

2 200000000000

3 300000000000

4 400000000000

5 -100000000000

6 -200000000000

7 -300000000000

8 -400000000000

} {

set val [expr $val]

do_execsql_test 2.$tn.0 {DELETE FROM rt}

do_execsql_test 2.$tn.1 {INSERT INTO rt VALUES(23, $val, $val)}

do_execsql_test 2.$tn.2 {

SELECT $val>=a, $val<=b, a!=b FROM rt

} {1 1 1}

}

do_execsql_test 3.0 {

DROP TABLE rt;

CREATE VIRTUAL TABLE rt USING rtree(id, x1,x2, y1,y2);

}

# EVIDENCE-OF: R-45870-62834 Thus, bounding boxes might be slightly

# larger than specified, but will never be any smaller.

foreach {tn x1 x2 y1 y2} {

1 100000000000 200000000000 300000000000 400000000000

} {

set val [expr $val]

do_execsql_test 3.$tn.0 {DELETE FROM rt}

do_execsql_test 3.$tn.1 {INSERT INTO rt VALUES(23, $x1, $x2, $y1, $y2)}

do_execsql_test 3.$tn.2 {

SELECT (x2-x1)*(y2-y1) >= ($x2-$x1)*($y2-$y1) FROM rt

} {1}

}

#-------------------------------------------------------------------------

#-------------------------------------------------------------------------

# Section 3.5 of documentation.

#-------------------------------------------------------------------------

#-------------------------------------------------------------------------

set testprefix rtreedoc-7

reset_db

# 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.

#

# In the test below, the INSERT marked "THIS INSERT!!" does not affect

# the results of queries with an ORDER BY, but does affect the results

# of one without an ORDER BY. Therefore the INSERT changed the scan

# order.

do_execsql_test 1.0 {

CREATE VIRTUAL TABLE rt USING rtree(id, minX, maxX);

WITH s(i) AS (

SELECT 1 UNION ALL SELECT i+1 FROM s WHERE i<51

)

INSERT INTO rt SELECT NULL, i%10, (i%10)+5 FROM s

}

do_execsql_test 1.1 { SELECT count(*) FROM rt_node } 1

do_test 1.2 {

set res1 [db eval {SELECT * FROM rt WHERE maxX < 30}]

set res1o [db eval {SELECT * FROM rt WHERE maxX < 30 ORDER BY +id}]

db eval { INSERT INTO rt VALUES(NULL, 50, 50) } ;# THIS INSERT!!

set res2 [db eval {SELECT * FROM rt WHERE maxX < 30}]

set res2o [db eval {SELECT * FROM rt WHERE maxX < 30 ORDER BY +id}]

list [expr {$res1==$res2}] [expr {$res1o==$res2o}]

} {0 1}

do_execsql_test 1.3 { SELECT count(*) FROM rt_node } 3

# 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.

#

# SQLITE_LOCKED==6

#

do_test 1.4 {

set nCnt 3

db eval { SELECT * FROM rt WHERE minX>0 AND maxX<12 } {

incr nCnt -1

if {$nCnt==0} {

set rc [catch {db eval {

INSERT INTO rt VALUES(NULL, 51, 51);

}} msg]

set errorcode [db errorcode]

break

}

}

list $errorcode $rc $msg

} {6 1 {database table is locked}}

# 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;

#

# EVIDENCE-OF: R-52919-32711 Then the UPDATE might fail with an

# SQLITE_LOCKED error.

do_execsql_test 2.0 {

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

);

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);

}

do_test 2.1 {

db eval { SELECT id FROM demo_index WHERE maxY>=35.0 AND minY<=35.0 } {

set rc [catch {

db eval { UPDATE demo_index SET maxY=maxY+0.5 WHERE id=$id }

} msg]

set errorcode [db errorcode]

break

}

list $errorcode $rc $msg

} {6 1 {database table is locked}}

# EVIDENCE-OF: R-32604-49843 Ordinary tables in SQLite are able to read

# and write at the same time.

#

do_execsql_test 3.0 {

CREATE TABLE x1(a INTEGER PRIMARY KEY, b, c);

INSERT INTO x1 VALUES(1, 1, 1);

INSERT INTO x1 VALUES(2, 2, 2);

INSERT INTO x1 VALUES(3, 3, 3);

INSERT INTO x1 VALUES(4, 4, 4);

}

do_test 3.1 {

unset -nocomplain res

set res [list]

db eval { SELECT * FROM x1 } {

lappend res $a $b $c

switch -- $a {

1 {

db eval { INSERT INTO x1 VALUES(5, 5, 5) }

}

2 {

db eval { UPDATE x1 SET c=20 WHERE a=2 }

}

3 {

db eval { DELETE FROM x1 WHERE c IN (3,4) }

}

}

}

set res

} {1 1 1 2 2 2 3 3 3 5 5 5}

do_execsql_test 3.2 {

SELECT * FROM x1

} {1 1 1 2 2 20 5 5 5}

# 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.

#

# In 8.2, it can, it 8.1, it cannot.

do_test 8.1 {

db eval { SELECT * FROM rt } {

set rc [catch { db eval { INSERT INTO rt VALUES(53,53,53) } } msg]

break;

}

list $rc $msg

} {1 {database table is locked}}

do_test 8.2 {

db eval { SELECT * FROM rt ORDER BY +id } {

set rc [catch { db eval { INSERT INTO rt VALUES(53,53,53) } } msg]

break

}

list $rc $msg

} {0 {}}

#-------------------------------------------------------------------------

#-------------------------------------------------------------------------

# Section 4 of documentation.

#-------------------------------------------------------------------------

#-------------------------------------------------------------------------

set testprefix rtreedoc-8

reset_db

# 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 );

#

# One might.

#

do_execsql_test 1.0 {

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

);

}

do_execsql_test 1.1 {

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

);

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);

INSERT INTO demo_index

SELECT NULL, minX, maxX, minY+0.2, maxY+0.2 FROM demo_index;

INSERT INTO demo_index

SELECT NULL, minX+0.2, maxX+0.2, minY, maxY FROM demo_index;

INSERT INTO demo_index

SELECT NULL, minX, maxX, minY+0.4, maxY+0.4 FROM demo_index;

INSERT INTO demo_index

SELECT NULL, minX+0.4, maxX+0.4, minY, maxY FROM demo_index;

INSERT INTO demo_index

SELECT NULL, minX, maxX, minY+0.8, maxY+0.8 FROM demo_index;

INSERT INTO demo_index

SELECT NULL, minX+0.8, maxX+0.8, minY, maxY FROM demo_index;

INSERT INTO demo_data(id) SELECT id FROM demo_index;

SELECT count(*) FROM demo_index;

} {896}

set ::contained_in 0

proc contained_in {args} {incr ::contained_in ; return 0}

db func contained_in contained_in

# 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;

do_vmstep_test 1.2 {

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;

} {$step<100}

set ::contained_in1 $::contained_in

# 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);

set ::contained_in 0

do_vmstep_test 1.3 {

SELECT objname FROM demo_data

WHERE contained_in(demo_data.boundary, 35.37785, -80.77470);

} {$step>3200}

# 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.

#

# 896 of them, IIRC.

do_test 1.4 {

set ::contained_in

} 896

# 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.

#

# 2 is a small subset of 896.

#

# EVIDENCE-OF: R-39057-63901 The R*Tree index did not find the exact

# answer itself, it merely limited the search space.

#

# contained_in() filtered out those 2 rows.

do_test 1.5 {

set ::contained_in1

} {2}

#-------------------------------------------------------------------------

#-------------------------------------------------------------------------

# Section 4.1 of documentation.

#-------------------------------------------------------------------------

#-------------------------------------------------------------------------

set testprefix rtreedoc-9

reset_db

# 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".

#

# EVIDENCE-OF: R-41287-48160 Auxiliary columns are marked with a "+"

# symbol before the column name.

#

# This interface cannot conveniently be used to prove anything about

# versions of SQLite prior to 3.24.0.

#

do_execsql_test 1.0 {

CREATE VIRTUAL TABLE rta USING rtree(

id, u1,u2, v1,v2, +aux

);

INSERT INTO rta(aux) VALUES(NULL);

INSERT INTO rta(aux) VALUES(45);

INSERT INTO rta(aux) VALUES(22.3);

INSERT INTO rta(aux) VALUES('hello');

INSERT INTO rta(aux) VALUES(X'ABCD');

SELECT typeof(aux), quote(aux) FROM rta;

} {

null NULL

integer 45

real 22.3