| 1 |
# 2021 September 13 |
| 2 |
# |
| 3 |
# The author disclaims copyright to this source code. In place of |
| 4 |
# a legal notice, here is a blessing: |
| 5 |
# |
| 6 |
# May you do good and not evil. |
| 7 |
# May you find forgiveness for yourself and forgive others. |
| 8 |
# May you share freely, never taking more than you give. |
| 9 |
# |
| 10 |
#*********************************************************************** |
| 11 |
# |
| 12 |
# The focus of this file is testing the r-tree extension. |
| 13 |
# |
| 14 |
|
| 15 |
if {![info exists testdir]} { |
| 16 |
set testdir [file join [file dirname [info script]] .. .. test] |
| 17 |
} |
| 18 |
source [file join [file dirname [info script]] rtree_util.tcl] |
| 19 |
source $testdir/tester.tcl |
| 20 |
set testprefix rtreedoc |
| 21 |
|
| 22 |
ifcapable !rtree { |
| 23 |
finish_test |
| 24 |
return |
| 25 |
} |
| 26 |
|
| 27 |
# This command returns the number of columns in table $tbl within the |
| 28 |
# database opened by database handle $db |
| 29 |
proc column_count {db tbl} { |
| 30 |
set nCol 0 |
| 31 |
$db eval "PRAGMA table_info = $tbl" { incr nCol } |
| 32 |
return $nCol |
| 33 |
} |
| 34 |
|
| 35 |
proc column_name_list {db tbl} { |
| 36 |
set lCol [list] |
| 37 |
$db eval "PRAGMA table_info = $tbl" { |
| 38 |
lappend lCol $name |
| 39 |
} |
| 40 |
return $lCol |
| 41 |
} |
| 42 |
unset -nocomplain res |
| 43 |
|
| 44 |
#------------------------------------------------------------------------- |
| 45 |
#------------------------------------------------------------------------- |
| 46 |
# Section 3 of documentation. |
| 47 |
#------------------------------------------------------------------------- |
| 48 |
#------------------------------------------------------------------------- |
| 49 |
set testprefix rtreedoc-1 |
| 50 |
|
| 51 |
# EVIDENCE-OF: R-15060-13876 A 1-dimensional R*Tree thus has 3 columns. |
| 52 |
do_execsql_test 1.1.1 { CREATE VIRTUAL TABLE rt1 USING rtree(id, x1,x2) } |
| 53 |
do_test 1.1.2 { column_count db rt1 } 3 |
| 54 |
|
| 55 |
# EVIDENCE-OF: R-19353-19546 A 2-dimensional R*Tree has 5 columns. |
| 56 |
do_execsql_test 1.2.1 { CREATE VIRTUAL TABLE rt2 USING rtree(id,x1,x2, y1,y2) } |
| 57 |
do_test 1.2.2 { column_count db rt2 } 5 |
| 58 |
|
| 59 |
# EVIDENCE-OF: R-13615-19528 A 3-dimensional R*Tree has 7 columns. |
| 60 |
do_execsql_test 1.3.1 { |
| 61 |
CREATE VIRTUAL TABLE rt3 USING rtree(id, x1,x2, y1,y2, z1,z2) |
| 62 |
} |
| 63 |
do_test 1.3.2 { column_count db rt3 } 7 |
| 64 |
|
| 65 |
# EVIDENCE-OF: R-53479-41922 A 4-dimensional R*Tree has 9 columns. |
| 66 |
do_execsql_test 1.4.1 { |
| 67 |
CREATE VIRTUAL TABLE rt4 USING rtree(id, x1,x2, y1,y2, z1,z2, v1,v2) |
| 68 |
} |
| 69 |
do_test 1.4.2 { column_count db rt4 } 9 |
| 70 |
|
| 71 |
# EVIDENCE-OF: R-13981-28768 And a 5-dimensional R*Tree has 11 columns. |
| 72 |
do_execsql_test 1.5.1 { |
| 73 |
CREATE VIRTUAL TABLE rt5 USING rtree(id, x1,x2, y1,y2, z1,z2, v1,v2, w1,w2) |
| 74 |
} |
| 75 |
do_test 1.5.2 { column_count db rt5 } 11 |
| 76 |
|
| 77 |
|
| 78 |
# Attempt to create r-tree tables with 6 and 7 dimensions. |
| 79 |
# |
| 80 |
# EVIDENCE-OF: R-61533-25862 The SQLite R*Tree implementation does not |
| 81 |
# support R*Trees wider than 5 dimensions. |
| 82 |
do_catchsql_test 2.1.1 { |
| 83 |
CREATE VIRTUAL TABLE rt6 USING rtree( |
| 84 |
id, x1,x2, y1,y2, z1,z2, v1,v2, w1,w2, a1,a2 |
| 85 |
) |
| 86 |
} {1 {Too many columns for an rtree table}} |
| 87 |
do_catchsql_test 2.1.2 { |
| 88 |
CREATE VIRTUAL TABLE rt6 USING rtree( |
| 89 |
id, x1,x2, y1,y2, z1,z2, v1,v2, w1,w2, a1,a2, b1, b2 |
| 90 |
) |
| 91 |
} {1 {Too many columns for an rtree table}} |
| 92 |
|
| 93 |
# Attempt to create r-tree tables with no columns, a single column, or |
| 94 |
# an even number of columns. This and the tests above establish that: |
| 95 |
# |
| 96 |
# EVIDENCE-OF: R-16717-50504 Each R*Tree index is a virtual table with |
| 97 |
# an odd number of columns between 3 and 11. |
| 98 |
foreach {tn cols err} { |
| 99 |
1 "" "Too few columns for an rtree table" |
| 100 |
2 "x" "Too few columns for an rtree table" |
| 101 |
3 "x,y" "Too few columns for an rtree table" |
| 102 |
4 "a,b,c,d" "Wrong number of columns for an rtree table" |
| 103 |
5 "a,b,c,d,e,f" "Wrong number of columns for an rtree table" |
| 104 |
6 "a,b,c,d,e,f,g,h" "Wrong number of columns for an rtree table" |
| 105 |
7 "a,b,c,d,e,f,g,h,i,j" "Wrong number of columns for an rtree table" |
| 106 |
8 "a,b,c,d,e,f,g,h,i,j,k,l" "Too many columns for an rtree table" |
| 107 |
} { |
| 108 |
do_catchsql_test 3.$tn " |
| 109 |
CREATE VIRTUAL TABLE xyz USING rtree($cols) |
| 110 |
" [list 1 $err] |
| 111 |
} |
| 112 |
|
| 113 |
# EVIDENCE-OF: R-17874-21123 The first column of an SQLite R*Tree is |
| 114 |
# similar to an integer primary key column of a normal SQLite table. |
| 115 |
# |
| 116 |
# EVIDENCE-OF: R-46619-65417 The first column is always a 64-bit signed |
| 117 |
# integer primary key. |
| 118 |
# |
| 119 |
# EVIDENCE-OF: R-46866-24036 It may only store a 64-bit signed integer |
| 120 |
# value. |
| 121 |
# |
| 122 |
# EVIDENCE-OF: R-00250-64843 If an attempt is made to insert any other |
| 123 |
# non-integer value into this column, the r-tree module silently |
| 124 |
# converts it to an integer before writing it into the database. |
| 125 |
# |
| 126 |
do_execsql_test 4.0 { CREATE VIRTUAL TABLE rt USING rtree(id, x1, x2) } |
| 127 |
foreach {tn val res} { |
| 128 |
1 10 10 |
| 129 |
2 10.6 10 |
| 130 |
3 10.99 10 |
| 131 |
4 '123' 123 |
| 132 |
5 X'313233' 123 |
| 133 |
6 -10 -10 |
| 134 |
7 9223372036854775807 9223372036854775807 |
| 135 |
8 -9223372036854775808 -9223372036854775808 |
| 136 |
9 '9223372036854775807' 9223372036854775807 |
| 137 |
10 '-9223372036854775808' -9223372036854775808 |
| 138 |
11 'hello+world' 0 |
| 139 |
} { |
| 140 |
do_execsql_test 4.$tn.1 " |
| 141 |
DELETE FROM rt; |
| 142 |
INSERT INTO rt VALUES($val, 10, 20); |
| 143 |
" |
| 144 |
do_execsql_test 4.$tn.2 { |
| 145 |
SELECT typeof(id), id FROM rt |
| 146 |
} [list integer $res] |
| 147 |
} |
| 148 |
|
| 149 |
# EVIDENCE-OF: R-15544-29079 Inserting a NULL value into this column |
| 150 |
# causes SQLite to automatically generate a new unique primary key |
| 151 |
# value. |
| 152 |
do_execsql_test 5.1 { |
| 153 |
DELETE FROM rt; |
| 154 |
INSERT INTO rt VALUES(100, 1, 2); |
| 155 |
INSERT INTO rt VALUES(NULL, 1, 2); |
| 156 |
} |
| 157 |
do_execsql_test 5.2 { SELECT id FROM rt } {100 101} |
| 158 |
do_execsql_test 5.3 { |
| 159 |
INSERT INTO rt VALUES(9223372036854775807, 1, 2); |
| 160 |
INSERT INTO rt VALUES(NULL, 1, 2); |
| 161 |
} |
| 162 |
do_execsql_test 5.4 { |
| 163 |
SELECT count(*) FROM rt; |
| 164 |
} 4 |
| 165 |
do_execsql_test 5.5 { |
| 166 |
SELECT id IN(100, 101, 9223372036854775807) FROM rt ORDER BY 1; |
| 167 |
} {0 1 1 1} |
| 168 |
|
| 169 |
|
| 170 |
# EVIDENCE-OF: R-64317-38978 The other columns are pairs, one pair per |
| 171 |
# dimension, containing the minimum and maximum values for that |
| 172 |
# dimension, respectively. |
| 173 |
# |
| 174 |
# Show this by observing that attempts to insert rows with max>min fail. |
| 175 |
# |
| 176 |
do_execsql_test 6.1 { |
| 177 |
CREATE VIRTUAL TABLE rtF USING rtree(id, x1,x2, y1,y2); |
| 178 |
CREATE VIRTUAL TABLE rtI USING rtree_i32(id, x1,x2, y1,y2, z1,z2); |
| 179 |
} |
| 180 |
foreach {tn x1 x2 y1 y2 ok} { |
| 181 |
1 10.3 20.1 30.9 40.2 1 |
| 182 |
2 10.3 20.1 40.2 30.9 0 |
| 183 |
3 10.3 30.9 20.1 40.2 1 |
| 184 |
4 20.1 10.3 30.9 40.2 0 |
| 185 |
} { |
| 186 |
do_test 6.2.$tn { |
| 187 |
catch { db eval { INSERT INTO rtF VALUES(NULL, $x1, $x2, $y1, $y2) } } |
| 188 |
} [expr $ok==0] |
| 189 |
} |
| 190 |
foreach {tn x1 x2 y1 y2 z1 z2 ok} { |
| 191 |
1 10 20 30 40 50 60 1 |
| 192 |
2 10 20 30 40 60 50 0 |
| 193 |
3 10 20 30 50 40 60 1 |
| 194 |
4 10 20 40 30 50 60 0 |
| 195 |
5 10 30 20 40 50 60 1 |
| 196 |
6 20 10 30 40 50 60 0 |
| 197 |
} { |
| 198 |
do_test 6.3.$tn { |
| 199 |
catch { db eval { INSERT INTO rtI VALUES(NULL,$x1,$x2,$y1,$y2,$z1,$z2) } } |
| 200 |
} [expr $ok==0] |
| 201 |
} |
| 202 |
|
| 203 |
# EVIDENCE-OF: R-08054-15429 The min/max-value pair columns are stored |
| 204 |
# as 32-bit floating point values for "rtree" virtual tables or as |
| 205 |
# 32-bit signed integers in "rtree_i32" virtual tables. |
| 206 |
# |
| 207 |
# Show this by showing that large values are rounded in ways consistent |
| 208 |
# with those two 32-bit types. |
| 209 |
do_execsql_test 7.1 { |
| 210 |
DELETE FROM rtI; |
| 211 |
INSERT INTO rtI VALUES( |
| 212 |
0, -2000000000, 2000000000, -5000000000, 5000000000, |
| 213 |
-1000000000000, 10000000000000 |
| 214 |
); |
| 215 |
SELECT * FROM rtI; |
| 216 |
} { |
| 217 |
0 -2000000000 2000000000 -705032704 705032704 727379968 1316134912 |
| 218 |
} |
| 219 |
do_execsql_test 7.2 { |
| 220 |
DELETE FROM rtF; |
| 221 |
INSERT INTO rtF VALUES( |
| 222 |
0, -2000000000, 2000000000, |
| 223 |
-1000000000000, 10000000000000 |
| 224 |
); |
| 225 |
SELECT * FROM rtF; |
| 226 |
} { |
| 227 |
0 -2000000000.0 2000000000.0 -1000000126976.0 10000000876544.0 |
| 228 |
} |
| 229 |
|
| 230 |
# EVIDENCE-OF: R-47371-54529 Unlike regular SQLite tables which can |
| 231 |
# store data in a variety of datatypes and formats, the R*Tree rigidly |
| 232 |
# enforce these storage types. |
| 233 |
# |
| 234 |
# EVIDENCE-OF: R-39153-14977 If any other type of value is inserted into |
| 235 |
# such a column, the r-tree module silently converts it to the required |
| 236 |
# type before writing the new record to the database. |
| 237 |
do_execsql_test 8.1 { |
| 238 |
DELETE FROM rtI; |
| 239 |
INSERT INTO rtI VALUES( |
| 240 |
1, 'hello world', X'616263', NULL, 44.5, 1000, 9999.9999 |
| 241 |
); |
| 242 |
SELECT * FROM rtI; |
| 243 |
} { |
| 244 |
1 0 0 0 44 1000 9999 |
| 245 |
} |
| 246 |
|
| 247 |
do_execsql_test 8.2 { |
| 248 |
SELECT |
| 249 |
typeof(x1), typeof(x2), typeof(y1), typeof(y2), typeof(z1), typeof(z2) |
| 250 |
FROM rtI |
| 251 |
} {integer integer integer integer integer integer} |
| 252 |
|
| 253 |
do_execsql_test 8.3 { |
| 254 |
DELETE FROM rtF; |
| 255 |
INSERT INTO rtF VALUES( |
| 256 |
1, 'hello world', X'616263', NULL, 44 |
| 257 |
); |
| 258 |
SELECT * FROM rtF; |
| 259 |
} { |
| 260 |
1 0.0 0.0 0.0 44.0 |
| 261 |
} |
| 262 |
do_execsql_test 8.4 { |
| 263 |
SELECT |
| 264 |
typeof(x1), typeof(x2), typeof(y1), typeof(y2) |
| 265 |
FROM rtF |
| 266 |
} {real real real real} |
| 267 |
|
| 268 |
|
| 269 |
|
| 270 |
|
| 271 |
#------------------------------------------------------------------------- |
| 272 |
#------------------------------------------------------------------------- |
| 273 |
# Section 3.1 of documentation. |
| 274 |
#------------------------------------------------------------------------- |
| 275 |
#------------------------------------------------------------------------- |
| 276 |
set testprefix rtreedoc-2 |
| 277 |
reset_db |
| 278 |
|
| 279 |
foreach {tn name clist} { |
| 280 |
1 t1 "id x1 x2" |
| 281 |
2 t2 "id x1 x2 y1 y2 z1 z2" |
| 282 |
} { |
| 283 |
# EVIDENCE-OF: R-15142-18077 A new R*Tree index is created as follows: |
| 284 |
# CREATE VIRTUAL TABLE <name> USING rtree(<column-names>); |
| 285 |
do_execsql_test 1.$tn.1 " |
| 286 |
CREATE VIRTUAL TABLE $name USING rtree([join $clist ,]) |
| 287 |
" |
| 288 |
|
| 289 |
# EVIDENCE-OF: R-51698-09302 The <name> is the name your |
| 290 |
# application chooses for the R*Tree index and <column-names> is a |
| 291 |
# comma separated list of between 3 and 11 columns. |
| 292 |
do_test 1.$tn.2 { column_name_list db $name } [list {*}$clist] |
| 293 |
|
| 294 |
# EVIDENCE-OF: R-50130-53472 The virtual <name> table creates |
| 295 |
# three shadow tables to actually store its content. |
| 296 |
do_execsql_test 1.$tn.3 { |
| 297 |
SELECT count(*) FROM sqlite_schema |
| 298 |
} [expr 1+3] |
| 299 |
|
| 300 |
# EVIDENCE-OF: R-45256-35998 The names of these shadow tables are: |
| 301 |
# <name>_node <name>_rowid <name>_parent |
| 302 |
do_execsql_test 1.$tn.4 { |
| 303 |
SELECT name FROM sqlite_schema WHERE rootpage>0 ORDER BY 1 |
| 304 |
} [list ${name}_node ${name}_parent ${name}_rowid] |
| 305 |
|
| 306 |
do_execsql_test 1.$tn.5 "DROP TABLE $name" |
| 307 |
} |
| 308 |
|
| 309 |
# EVIDENCE-OF: R-11241-54478 As an example, consider creating a |
| 310 |
# two-dimensional R*Tree index for use in spatial queries: CREATE |
| 311 |
# VIRTUAL TABLE demo_index USING rtree( id, -- Integer primary key minX, |
| 312 |
# maxX, -- Minimum and maximum X coordinate minY, maxY -- Minimum and |
| 313 |
# maximum Y coordinate ); |
| 314 |
do_execsql_test 2.0 { |
| 315 |
CREATE VIRTUAL TABLE demo_index USING rtree( |
| 316 |
id, -- Integer primary key |
| 317 |
minX, maxX, -- Minimum and maximum X coordinate |
| 318 |
minY, maxY -- Minimum and maximum Y coordinate |
| 319 |
); |
| 320 |
INSERT INTO demo_index VALUES(1,2,3,4,5); |
| 321 |
INSERT INTO demo_index VALUES(6,7,8,9,10); |
| 322 |
} |
| 323 |
|
| 324 |
# EVIDENCE-OF: R-02287-33529 The shadow tables are ordinary SQLite data |
| 325 |
# tables. |
| 326 |
# |
| 327 |
# Ordinary tables. With ordinary sqlite_schema entries. |
| 328 |
do_execsql_test 2.1 { |
| 329 |
SELECT type, name, sql FROM sqlite_schema WHERE sql NOT LIKE '%virtual%' |
| 330 |
} { |
| 331 |
table demo_index_rowid |
| 332 |
{CREATE TABLE "demo_index_rowid"(rowid INTEGER PRIMARY KEY,nodeno)} |
| 333 |
table demo_index_node |
| 334 |
{CREATE TABLE "demo_index_node"(nodeno INTEGER PRIMARY KEY,data)} |
| 335 |
table demo_index_parent |
| 336 |
{CREATE TABLE "demo_index_parent"(nodeno INTEGER PRIMARY KEY,parentnode)} |
| 337 |
} |
| 338 |
|
| 339 |
# EVIDENCE-OF: R-10863-13089 You can query them directly if you like, |
| 340 |
# though this unlikely to reveal anything particularly useful. |
| 341 |
# |
| 342 |
# Querying: |
| 343 |
do_execsql_test 2.2 { |
| 344 |
SELECT count(*) FROM demo_index_node; |
| 345 |
SELECT count(*) FROM demo_index_rowid; |
| 346 |
SELECT count(*) FROM demo_index_parent; |
| 347 |
} {1 2 0} |
| 348 |
|
| 349 |
# EVIDENCE-OF: R-05650-46070 And you can UPDATE, DELETE, INSERT or even |
| 350 |
# DROP the shadow tables, though doing so will corrupt your R*Tree |
| 351 |
# index. |
| 352 |
do_execsql_test 2.3 { |
| 353 |
DELETE FROM demo_index_rowid; |
| 354 |
INSERT INTO demo_index_parent VALUES(2, 3); |
| 355 |
UPDATE demo_index_node SET data = 'hello world' |
| 356 |
} |
| 357 |
do_catchsql_test 2.4 { |
| 358 |
SELECT * FROM demo_index WHERE minX>10 AND maxX<30 |
| 359 |
} {1 {database disk image is malformed}} |
| 360 |
do_execsql_test 2.5 { |
| 361 |
DROP TABLE demo_index_rowid |
| 362 |
} |
| 363 |
|
| 364 |
#------------------------------------------------------------------------- |
| 365 |
#------------------------------------------------------------------------- |
| 366 |
# Section 3.1.1 of documentation. |
| 367 |
#------------------------------------------------------------------------- |
| 368 |
#------------------------------------------------------------------------- |
| 369 |
set testprefix rtreedoc-3 |
| 370 |
reset_db |
| 371 |
|
| 372 |
# EVIDENCE-OF: R-44253-50720 In the argments to "rtree" in the CREATE |
| 373 |
# VIRTUAL TABLE statement, the names of the columns are taken from the |
| 374 |
# first token of each argument. All subsequent tokens within each |
| 375 |
# argument are silently ignored. |
| 376 |
# |
| 377 |
foreach {tn cols lCol} { |
| 378 |
1 {(id TEXT, x1 TEXT, x2 TEXT, y1 TEXT, y2 TEXT)} {id x1 x2 y1 y2} |
| 379 |
2 {(id TEXT, x1 UNIQUE, x2 TEXT, y1 NOT NULL, y2 TEXT)} {id x1 x2 y1 y2} |
| 380 |
3 {(id, x1 DEFAULT 4, x2 TEXT, y1 NOT NULL, y2 TEXT)} {id x1 x2 y1 y2} |
| 381 |
} { |
| 382 |
do_execsql_test 1.$tn.1 " CREATE VIRTUAL TABLE abc USING rtree $cols " |
| 383 |
do_test 1.$tn.2 { column_name_list db abc } $lCol |
| 384 |
|
| 385 |
# EVIDENCE-OF: R-52032-06717 This means, for example, that if you try to |
| 386 |
# give a column a type affinity or add a constraint such as UNIQUE or |
| 387 |
# NOT NULL or DEFAULT to a column, those extra tokens are accepted as |
| 388 |
# valid, but they do not change the behavior of the rtree. |
| 389 |
|
| 390 |
# Show there are no UNIQUE constraints |
| 391 |
do_execsql_test 1.$tn.3 { |
| 392 |
INSERT INTO abc VALUES(1, 10.0, 20.0, 10.0, 20.0); |
| 393 |
INSERT INTO abc VALUES(2, 10.0, 20.0, 10.0, 20.0); |
| 394 |
} |
| 395 |
|
| 396 |
# Show the default values have not been modified |
| 397 |
do_execsql_test 1.$tn.4 { |
| 398 |
INSERT INTO abc DEFAULT VALUES; |
| 399 |
SELECT * FROM abc WHERE rowid NOT IN (1,2) |
| 400 |
} {3 0.0 0.0 0.0 0.0} |
| 401 |
|
| 402 |
# Show that there are no NOT NULL constraints |
| 403 |
do_execsql_test 1.$tn.5 { |
| 404 |
INSERT INTO abc VALUES(NULL, NULL, NULL, NULL, NULL); |
| 405 |
SELECT * FROM abc WHERE rowid NOT IN (1,2,3) |
| 406 |
} {4 0.0 0.0 0.0 0.0} |
| 407 |
|
| 408 |
# EVIDENCE-OF: R-06893-30579 In an RTREE virtual table, the first column |
| 409 |
# always has a type affinity of INTEGER and all other data columns have |
| 410 |
# a type affinity of REAL. |
| 411 |
do_execsql_test 1.$tn.5 { |
| 412 |
INSERT INTO abc VALUES('5', '5', '5', '5', '5'); |
| 413 |
SELECT * FROM abc WHERE rowid NOT IN (1,2,3,4) |
| 414 |
} {5 5.0 5.0 5.0 5.0} |
| 415 |
do_execsql_test 1.$tn.6 { |
| 416 |
SELECT type FROM pragma_table_info('abc') ORDER BY cid |
| 417 |
} {INT REAL REAL REAL REAL} |
| 418 |
|
| 419 |
do_execsql_test 1.$tn.7 " CREATE VIRTUAL TABLE abc2 USING rtree_i32 $cols " |
| 420 |
|
| 421 |
# EVIDENCE-OF: R-06224-52418 In an RTREE_I32 virtual table, all columns |
| 422 |
# have type affinity of INTEGER. |
| 423 |
do_execsql_test 1.$tn.8 { |
| 424 |
INSERT INTO abc2 VALUES('6.0', '6.0', '6.0', '6.0', '6.0'); |
| 425 |
SELECT * FROM abc2 |
| 426 |
} {6 6 6 6 6} |
| 427 |
do_execsql_test 1.$tn.9 { |
| 428 |
SELECT type FROM pragma_table_info('abc2') ORDER BY cid |
| 429 |
} {INT INT INT INT INT} |
| 430 |
|
| 431 |
|
| 432 |
do_execsql_test 1.$tn.10 { |
| 433 |
DROP TABLE abc; |
| 434 |
DROP TABLE abc2; |
| 435 |
} |
| 436 |
} |
| 437 |
|
| 438 |
#------------------------------------------------------------------------- |
| 439 |
#------------------------------------------------------------------------- |
| 440 |
# Section 3.2 of documentation. |
| 441 |
#------------------------------------------------------------------------- |
| 442 |
#------------------------------------------------------------------------- |
| 443 |
set testprefix rtreedoc-4 |
| 444 |
reset_db |
| 445 |
|
| 446 |
# EVIDENCE-OF: R-36195-31555 The usual INSERT, UPDATE, and DELETE |
| 447 |
# commands work on an R*Tree index just like on regular tables. |
| 448 |
# |
| 449 |
# Create a regular table and an rtree table. Perform INSERT, UPDATE and |
| 450 |
# DELETE operations, then observe that the contents of the two tables |
| 451 |
# are identical. |
| 452 |
do_execsql_test 1.0 { |
| 453 |
CREATE VIRTUAL TABLE rt USING rtree(id, x1, x2); |
| 454 |
CREATE TABLE t1(id INTEGER PRIMARY KEY, x1 REAL, x2 REAL); |
| 455 |
} |
| 456 |
foreach {tn sql} { |
| 457 |
1 "INSERT INTO %TBL% VALUES(5, 11,12)" |
| 458 |
2 "INSERT INTO %TBL% VALUES(11, -11,14.5)" |
| 459 |
3 "UPDATE %TBL% SET x1=-99 WHERE id=11" |
| 460 |
4 "DELETE FROM %TBL% WHERE x2=14.5" |
| 461 |
5 "DELETE FROM %TBL%" |
| 462 |
} { |
| 463 |
set sql1 [string map {%TBL% rt} $sql] |
| 464 |
set sql2 [string map {%TBL% t1} $sql] |
| 465 |
do_execsql_test 1.$tn.0 $sql1 |
| 466 |
do_execsql_test 1.$tn.1 $sql2 |
| 467 |
|
| 468 |
set data1 [execsql {SELECT * FROM rt ORDER BY 1}] |
| 469 |
set data2 [execsql {SELECT * FROM t1 ORDER BY 1}] |
| 470 |
|
| 471 |
set res [expr {$data1==$data2}] |
| 472 |
do_test 1.$tn.2 {set res} 1 |
| 473 |
} |
| 474 |
|
| 475 |
# EVIDENCE-OF: R-56987-45305 |
| 476 |
do_execsql_test 2.0 { |
| 477 |
CREATE VIRTUAL TABLE demo_index USING rtree( |
| 478 |
id, -- Integer primary key |
| 479 |
minX, maxX, -- Minimum and maximum X coordinate |
| 480 |
minY, maxY -- Minimum and maximum Y coordinate |
| 481 |
); |
| 482 |
|
| 483 |
INSERT INTO demo_index VALUES |
| 484 |
(28215, -80.781227, -80.604706, 35.208813, 35.297367), |
| 485 |
(28216, -80.957283, -80.840599, 35.235920, 35.367825), |
| 486 |
(28217, -80.960869, -80.869431, 35.133682, 35.208233), |
| 487 |
(28226, -80.878983, -80.778275, 35.060287, 35.154446), |
| 488 |
(28227, -80.745544, -80.555382, 35.130215, 35.236916), |
| 489 |
(28244, -80.844208, -80.841988, 35.223728, 35.225471), |
| 490 |
(28262, -80.809074, -80.682938, 35.276207, 35.377747), |
| 491 |
(28269, -80.851471, -80.735718, 35.272560, 35.407925), |
| 492 |
(28270, -80.794983, -80.728966, 35.059872, 35.161823), |
| 493 |
(28273, -80.994766, -80.875259, 35.074734, 35.172836), |
| 494 |
(28277, -80.876793, -80.767586, 35.001709, 35.101063), |
| 495 |
(28278, -81.058029, -80.956375, 35.044701, 35.223812), |
| 496 |
(28280, -80.844208, -80.841972, 35.225468, 35.227203), |
| 497 |
(28282, -80.846382, -80.844193, 35.223972, 35.225655); |
| 498 |
} |
| 499 |
|
| 500 |
#------------------------------------------------------------------------- |
| 501 |
#------------------------------------------------------------------------- |
| 502 |
# Section 3.3 of documentation. |
| 503 |
#------------------------------------------------------------------------- |
| 504 |
#------------------------------------------------------------------------- |
| 505 |
set testprefix rtreedoc-5 |
| 506 |
|
| 507 |
do_execsql_test 1.0 { |
| 508 |
INSERT INTO demo_index |
| 509 |
SELECT NULL, minX, maxX, minY+0.2, maxY+0.2 FROM demo_index; |
| 510 |
INSERT INTO demo_index |
| 511 |
SELECT NULL, minX+0.2, maxX+0.2, minY, maxY FROM demo_index; |
| 512 |
INSERT INTO demo_index |
| 513 |
SELECT NULL, minX, maxX, minY+0.4, maxY+0.4 FROM demo_index; |
| 514 |
INSERT INTO demo_index |
| 515 |
SELECT NULL, minX+0.4, maxX+0.4, minY, maxY FROM demo_index; |
| 516 |
INSERT INTO demo_index |
| 517 |
SELECT NULL, minX, maxX, minY+0.8, maxY+0.8 FROM demo_index; |
| 518 |
INSERT INTO demo_index |
| 519 |
SELECT NULL, minX+0.8, maxX+0.8, minY, maxY FROM demo_index; |
| 520 |
|
| 521 |
SELECT count(*) FROM demo_index; |
| 522 |
} {896} |
| 523 |
|
| 524 |
proc do_vmstep_test {tn sql expr} { |
| 525 |
execsql $sql |
| 526 |
set step [db status vmstep] |
| 527 |
do_test $tn.$step "expr {[subst $expr]}" 1 |
| 528 |
} |
| 529 |
|
| 530 |
# EVIDENCE-OF: R-45880-07724 Any valid query will work against an R*Tree |
| 531 |
# index. |
| 532 |
do_execsql_test 1.1.0 { |
| 533 |
CREATE TABLE demo_tbl AS SELECT * FROM demo_index; |
| 534 |
} |
| 535 |
foreach {tn sql} { |
| 536 |
1 {SELECT * FROM %TBL% ORDER BY 1} |
| 537 |
2 {SELECT max(minX) FROM %TBL% ORDER BY 1} |
| 538 |
3 {SELECT max(minX) FROM %TBL% GROUP BY round(minY) ORDER BY 1} |
| 539 |
} { |
| 540 |
set sql1 [string map {%TBL% demo_index} $sql] |
| 541 |
set sql2 [string map {%TBL% demo_tbl} $sql] |
| 542 |
|
| 543 |
do_execsql_test 1.1.$tn $sql1 [execsql $sql2] |
| 544 |
} |
| 545 |
|
| 546 |
# EVIDENCE-OF: R-60814-18273 The R*Tree implementation just makes some |
| 547 |
# kinds of queries especially efficient. |
| 548 |
# |
| 549 |
# The second query is more efficient than the first. |
| 550 |
do_vmstep_test 1.2.1 {SELECT * FROM demo_index WHERE +rowid=28269} {$step>2000} |
| 551 |
do_vmstep_test 1.2.2 {SELECT * FROM demo_index WHERE rowid=28269} {$step<100} |
| 552 |
|
| 553 |
# EVIDENCE-OF: R-37800-50174 Queries against the primary key are |
| 554 |
# efficient: SELECT * FROM demo_index WHERE id=28269; |
| 555 |
do_vmstep_test 2.2 { SELECT * FROM demo_index WHERE id=28269 } {$step < 100} |
| 556 |
|
| 557 |
# EVIDENCE-OF: R-35847-18866 The big reason for using an R*Tree is so |
| 558 |
# that you can efficiently do range queries against the coordinate |
| 559 |
# ranges. |
| 560 |
# |
| 561 |
# EVIDENCE-OF: R-49927-54202 |
| 562 |
do_vmstep_test 2.3 { |
| 563 |
SELECT id FROM demo_index |
| 564 |
WHERE minX<=-80.77470 AND maxX>=-80.77470 |
| 565 |
AND minY<=35.37785 AND maxY>=35.37785; |
| 566 |
} {$step < 100} |
| 567 |
|
| 568 |
# EVIDENCE-OF: R-12823-37176 The query above will quickly locate all |
| 569 |
# zipcodes that contain the SQLite main office in their bounding box, |
| 570 |
# even if the R*Tree contains many entries. |
| 571 |
# |
| 572 |
do_execsql_test 2.4 { |
| 573 |
SELECT id FROM demo_index |
| 574 |
WHERE minX<=-80.77470 AND maxX>=-80.77470 |
| 575 |
AND minY<=35.37785 AND maxY>=35.37785; |
| 576 |
} { |
| 577 |
28322 28269 |
| 578 |
} |
| 579 |
|
| 580 |
# EVIDENCE-OF: R-07351-00257 For example, to find all zipcode bounding |
| 581 |
# boxes that overlap with the 28269 zipcode: SELECT A.id FROM demo_index |
| 582 |
# AS A, demo_index AS B WHERE A.maxX>=B.minX AND A.minX<=B.maxX |
| 583 |
# AND A.maxY>=B.minY AND A.minY<=B.maxY AND B.id=28269; |
| 584 |
# |
| 585 |
# Also check that it is efficient |
| 586 |
# |
| 587 |
# EVIDENCE-OF: R-39094-01937 This second query will find both 28269 |
| 588 |
# entry (since every bounding box overlaps with itself) and also other |
| 589 |
# zipcode that is close enough to 28269 that their bounding boxes |
| 590 |
# overlap. |
| 591 |
# |
| 592 |
# 28269 is there in the result. |
| 593 |
# |
| 594 |
do_vmstep_test 2.5.1 { |
| 595 |
SELECT A.id FROM demo_index AS A, demo_index AS B |
| 596 |
WHERE A.maxX>=B.minX AND A.minX<=B.maxX |
| 597 |
AND A.maxY>=B.minY AND A.minY<=B.maxY |
| 598 |
AND B.id=28269 |
| 599 |
} {$step < 100} |
| 600 |
do_execsql_test 2.5.2 { |
| 601 |
SELECT A.id FROM demo_index AS A, demo_index AS B |
| 602 |
WHERE A.maxX>=B.minX AND A.minX<=B.maxX |
| 603 |
AND A.maxY>=B.minY AND A.minY<=B.maxY |
| 604 |
AND B.id=28269 ORDER BY +A.id; |
| 605 |
} { |
| 606 |
28215 |
| 607 |
28216 |
| 608 |
28262 |
| 609 |
28269 |
| 610 |
28286 |
| 611 |
28287 |
| 612 |
28291 |
| 613 |
28293 |
| 614 |
28298 |
| 615 |
28313 |
| 616 |
28320 |
| 617 |
28322 |
| 618 |
28336 |
| 619 |
} |
| 620 |
|
| 621 |
# EVIDENCE-OF: R-02723-34107 Note that it is not necessary for all |
| 622 |
# coordinates in an R*Tree index to be constrained in order for the |
| 623 |
# index search to be efficient. |
| 624 |
# |
| 625 |
# EVIDENCE-OF: R-22490-27246 One might, for example, want to query all |
| 626 |
# objects that overlap with the 35th parallel: SELECT id FROM demo_index |
| 627 |
# WHERE maxY>=35.0 AND minY<=35.0; |
| 628 |
do_vmstep_test 2.6.1 { |
| 629 |
SELECT id FROM demo_index |
| 630 |
WHERE maxY>=35.0 AND minY<=35.0; |
| 631 |
} {$step < 100} |
| 632 |
do_execsql_test 2.6.2 { |
| 633 |
SELECT id FROM demo_index |
| 634 |
WHERE maxY>=35.0 AND minY<=35.0; |
| 635 |
} {} |
| 636 |
|
| 637 |
|
| 638 |
#------------------------------------------------------------------------- |
| 639 |
#------------------------------------------------------------------------- |
| 640 |
# Section 3.4 of documentation. |
| 641 |
#------------------------------------------------------------------------- |
| 642 |
#------------------------------------------------------------------------- |
| 643 |
set testprefix rtreedoc-6 |
| 644 |
reset_db |
| 645 |
|
| 646 |
# EVIDENCE-OF: R-08327-00674 By default, coordinates are stored in an |
| 647 |
# R*Tree using 32-bit floating point values. |
| 648 |
# |
| 649 |
# EVIDENCE-OF: R-22000-53613 The default virtual table ("rtree") stores |
| 650 |
# coordinates as single-precision (4-byte) floating point numbers. |
| 651 |
# |
| 652 |
# Show this by showing that rounding is consistent with 32-bit float |
| 653 |
# rounding. |
| 654 |
do_execsql_test 1.0 { |
| 655 |
CREATE VIRTUAL TABLE rt USING rtree(id, a,b); |
| 656 |
} |
| 657 |
do_execsql_test 1.1 { |
| 658 |
INSERT INTO rt VALUES(14, -1000000000000, 1000000000000); |
| 659 |
SELECT * FROM rt; |
| 660 |
} {14 -1000000126976.0 1000000126976.0} |
| 661 |
|
| 662 |
# EVIDENCE-OF: R-39127-51288 When a coordinate cannot be exactly |
| 663 |
# represented by a 32-bit floating point number, the lower-bound |
| 664 |
# coordinates are rounded down and the upper-bound coordinates are |
| 665 |
# rounded up. |
| 666 |
foreach {tn val} { |
| 667 |
1 100000000000 |
| 668 |
2 200000000000 |
| 669 |
3 300000000000 |
| 670 |
4 400000000000 |
| 671 |
|
| 672 |
5 -100000000000 |
| 673 |
6 -200000000000 |
| 674 |
7 -300000000000 |
| 675 |
8 -400000000000 |
| 676 |
} { |
| 677 |
set val [expr $val] |
| 678 |
do_execsql_test 2.$tn.0 {DELETE FROM rt} |
| 679 |
do_execsql_test 2.$tn.1 {INSERT INTO rt VALUES(23, $val, $val)} |
| 680 |
do_execsql_test 2.$tn.2 { |
| 681 |
SELECT $val>=a, $val<=b, a!=b FROM rt |
| 682 |
} {1 1 1} |
| 683 |
} |
| 684 |
|
| 685 |
do_execsql_test 3.0 { |
| 686 |
DROP TABLE rt; |
| 687 |
CREATE VIRTUAL TABLE rt USING rtree(id, x1,x2, y1,y2); |
| 688 |
} |
| 689 |
|
| 690 |
# EVIDENCE-OF: R-45870-62834 Thus, bounding boxes might be slightly |
| 691 |
# larger than specified, but will never be any smaller. |
| 692 |
foreach {tn x1 x2 y1 y2} { |
| 693 |
1 100000000000 200000000000 300000000000 400000000000 |
| 694 |
} { |
| 695 |
set val [expr $val] |
| 696 |
do_execsql_test 3.$tn.0 {DELETE FROM rt} |
| 697 |
do_execsql_test 3.$tn.1 {INSERT INTO rt VALUES(23, $x1, $x2, $y1, $y2)} |
| 698 |
do_execsql_test 3.$tn.2 { |
| 699 |
SELECT (x2-x1)*(y2-y1) >= ($x2-$x1)*($y2-$y1) FROM rt |
| 700 |
} {1} |
| 701 |
} |
| 702 |
|
| 703 |
#------------------------------------------------------------------------- |
| 704 |
#------------------------------------------------------------------------- |
| 705 |
# Section 3.5 of documentation. |
| 706 |
#------------------------------------------------------------------------- |
| 707 |
#------------------------------------------------------------------------- |
| 708 |
set testprefix rtreedoc-7 |
| 709 |
reset_db |
| 710 |
|
| 711 |
# EVIDENCE-OF: R-55979-39402 It is the nature of the Guttman R-Tree |
| 712 |
# algorithm that any write might radically restructure the tree, and in |
| 713 |
# the process change the scan order of the nodes. |
| 714 |
# |
| 715 |
# In the test below, the INSERT marked "THIS INSERT!!" does not affect |
| 716 |
# the results of queries with an ORDER BY, but does affect the results |
| 717 |
# of one without an ORDER BY. Therefore the INSERT changed the scan |
| 718 |
# order. |
| 719 |
do_execsql_test 1.0 { |
| 720 |
CREATE VIRTUAL TABLE rt USING rtree(id, minX, maxX); |
| 721 |
WITH s(i) AS ( |
| 722 |
SELECT 1 UNION ALL SELECT i+1 FROM s WHERE i<51 |
| 723 |
) |
| 724 |
INSERT INTO rt SELECT NULL, i%10, (i%10)+5 FROM s |
| 725 |
} |
| 726 |
do_execsql_test 1.1 { SELECT count(*) FROM rt_node } 1 |
| 727 |
do_test 1.2 { |
| 728 |
set res1 [db eval {SELECT * FROM rt WHERE maxX < 30}] |
| 729 |
set res1o [db eval {SELECT * FROM rt WHERE maxX < 30 ORDER BY +id}] |
| 730 |
|
| 731 |
db eval { INSERT INTO rt VALUES(NULL, 50, 50) } ;# THIS INSERT!! |
| 732 |
|
| 733 |
set res2 [db eval {SELECT * FROM rt WHERE maxX < 30}] |
| 734 |
set res2o [db eval {SELECT * FROM rt WHERE maxX < 30 ORDER BY +id}] |
| 735 |
list [expr {$res1==$res2}] [expr {$res1o==$res2o}] |
| 736 |
} {0 1} |
| 737 |
|
| 738 |
do_execsql_test 1.3 { SELECT count(*) FROM rt_node } 3 |
| 739 |
|
| 740 |
# EVIDENCE-OF: R-00683-48865 For this reason, it is not generally |
| 741 |
# possible to modify the R-Tree in the middle of a query of the R-Tree. |
| 742 |
# Attempts to do so will fail with a SQLITE_LOCKED "database table is |
| 743 |
# locked" error. |
| 744 |
# |
| 745 |
# SQLITE_LOCKED==6 |
| 746 |
# |
| 747 |
do_test 1.4 { |
| 748 |
set nCnt 3 |
| 749 |
db eval { SELECT * FROM rt WHERE minX>0 AND maxX<12 } { |
| 750 |
incr nCnt -1 |
| 751 |
if {$nCnt==0} { |
| 752 |
set rc [catch {db eval { |
| 753 |
INSERT INTO rt VALUES(NULL, 51, 51); |
| 754 |
}} msg] |
| 755 |
set errorcode [db errorcode] |
| 756 |
break |
| 757 |
} |
| 758 |
} |
| 759 |
|
| 760 |
list $errorcode $rc $msg |
| 761 |
} {6 1 {database table is locked}} |
| 762 |
|
| 763 |
# EVIDENCE-OF: R-19740-29710 So, for example, suppose an application |
| 764 |
# runs one query against an R-Tree like this: SELECT id FROM demo_index |
| 765 |
# WHERE maxY>=35.0 AND minY<=35.0; Then for each "id" value |
| 766 |
# returned, suppose the application creates an UPDATE statement like the |
| 767 |
# following and binds the "id" value returned against the "?1" |
| 768 |
# parameter: UPDATE demo_index SET maxY=maxY+0.5 WHERE id=?1; |
| 769 |
# |
| 770 |
# EVIDENCE-OF: R-52919-32711 Then the UPDATE might fail with an |
| 771 |
# SQLITE_LOCKED error. |
| 772 |
do_execsql_test 2.0 { |
| 773 |
CREATE VIRTUAL TABLE demo_index USING rtree( |
| 774 |
id, -- Integer primary key |
| 775 |
minX, maxX, -- Minimum and maximum X coordinate |
| 776 |
minY, maxY -- Minimum and maximum Y coordinate |
| 777 |
); |
| 778 |
INSERT INTO demo_index VALUES |
| 779 |
(28215, -80.781227, -80.604706, 35.208813, 35.297367), |
| 780 |
(28216, -80.957283, -80.840599, 35.235920, 35.367825), |
| 781 |
(28217, -80.960869, -80.869431, 35.133682, 35.208233), |
| 782 |
(28226, -80.878983, -80.778275, 35.060287, 35.154446); |
| 783 |
} |
| 784 |
do_test 2.1 { |
| 785 |
db eval { SELECT id FROM demo_index WHERE maxY>=35.0 AND minY<=35.0 } { |
| 786 |
set rc [catch { |
| 787 |
db eval { UPDATE demo_index SET maxY=maxY+0.5 WHERE id=$id } |
| 788 |
} msg] |
| 789 |
set errorcode [db errorcode] |
| 790 |
break |
| 791 |
} |
| 792 |
list $errorcode $rc $msg |
| 793 |
} {6 1 {database table is locked}} |
| 794 |
|
| 795 |
# EVIDENCE-OF: R-32604-49843 Ordinary tables in SQLite are able to read |
| 796 |
# and write at the same time. |
| 797 |
# |
| 798 |
do_execsql_test 3.0 { |
| 799 |
CREATE TABLE x1(a INTEGER PRIMARY KEY, b, c); |
| 800 |
INSERT INTO x1 VALUES(1, 1, 1); |
| 801 |
INSERT INTO x1 VALUES(2, 2, 2); |
| 802 |
INSERT INTO x1 VALUES(3, 3, 3); |
| 803 |
INSERT INTO x1 VALUES(4, 4, 4); |
| 804 |
} |
| 805 |
do_test 3.1 { |
| 806 |
unset -nocomplain res |
| 807 |
set res [list] |
| 808 |
db eval { SELECT * FROM x1 } { |
| 809 |
lappend res $a $b $c |
| 810 |
switch -- $a { |
| 811 |
1 { |
| 812 |
db eval { INSERT INTO x1 VALUES(5, 5, 5) } |
| 813 |
} |
| 814 |
2 { |
| 815 |
db eval { UPDATE x1 SET c=20 WHERE a=2 } |
| 816 |
} |
| 817 |
3 { |
| 818 |
db eval { DELETE FROM x1 WHERE c IN (3,4) } |
| 819 |
} |
| 820 |
} |
| 821 |
} |
| 822 |
set res |
| 823 |
} {1 1 1 2 2 2 3 3 3 5 5 5} |
| 824 |
do_execsql_test 3.2 { |
| 825 |
SELECT * FROM x1 |
| 826 |
} {1 1 1 2 2 20 5 5 5} |
| 827 |
|
| 828 |
# EVIDENCE-OF: R-06177-00576 And R-Tree can appear to read and write at |
| 829 |
# the same time in some circumstances, if it can figure out how to |
| 830 |
# reliably run the query to completion before starting the update. |
| 831 |
# |
| 832 |
# In 8.2, it can, it 8.1, it cannot. |
| 833 |
do_test 8.1 { |
| 834 |
db eval { SELECT * FROM rt } { |
| 835 |
set rc [catch { db eval { INSERT INTO rt VALUES(53,53,53) } } msg] |
| 836 |
break; |
| 837 |
} |
| 838 |
list $rc $msg |
| 839 |
} {1 {database table is locked}} |
| 840 |
do_test 8.2 { |
| 841 |
db eval { SELECT * FROM rt ORDER BY +id } { |
| 842 |
set rc [catch { db eval { INSERT INTO rt VALUES(53,53,53) } } msg] |
| 843 |
break |
| 844 |
} |
| 845 |
list $rc $msg |
| 846 |
} {0 {}} |
| 847 |
|
| 848 |
#------------------------------------------------------------------------- |
| 849 |
#------------------------------------------------------------------------- |
| 850 |
# Section 4 of documentation. |
| 851 |
#------------------------------------------------------------------------- |
| 852 |
#------------------------------------------------------------------------- |
| 853 |
set testprefix rtreedoc-8 |
| 854 |
reset_db |
| 855 |
|
| 856 |
# EVIDENCE-OF: R-21062-30088 For the example above, one might create an |
| 857 |
# auxiliary table as follows: CREATE TABLE demo_data( id INTEGER PRIMARY |
| 858 |
# KEY, -- primary key objname TEXT, -- name of the object objtype TEXT, |
| 859 |
# -- object type boundary BLOB -- detailed boundary of object ); |
| 860 |
# |
| 861 |
# One might. |
| 862 |
# |
| 863 |
do_execsql_test 1.0 { |
| 864 |
CREATE TABLE demo_data( |
| 865 |
id INTEGER PRIMARY KEY, -- primary key |
| 866 |
objname TEXT, -- name of the object |
| 867 |
objtype TEXT, -- object type |
| 868 |
boundary BLOB -- detailed boundary of object |
| 869 |
); |
| 870 |
} |
| 871 |
|
| 872 |
do_execsql_test 1.1 { |
| 873 |
CREATE VIRTUAL TABLE demo_index USING rtree( |
| 874 |
id, -- Integer primary key |
| 875 |
minX, maxX, -- Minimum and maximum X coordinate |
| 876 |
minY, maxY -- Minimum and maximum Y coordinate |
| 877 |
); |
| 878 |
|
| 879 |
INSERT INTO demo_index VALUES |
| 880 |
(28215, -80.781227, -80.604706, 35.208813, 35.297367), |
| 881 |
(28216, -80.957283, -80.840599, 35.235920, 35.367825), |
| 882 |
(28217, -80.960869, -80.869431, 35.133682, 35.208233), |
| 883 |
(28226, -80.878983, -80.778275, 35.060287, 35.154446), |
| 884 |
(28227, -80.745544, -80.555382, 35.130215, 35.236916), |
| 885 |
(28244, -80.844208, -80.841988, 35.223728, 35.225471), |
| 886 |
(28262, -80.809074, -80.682938, 35.276207, 35.377747), |
| 887 |
(28269, -80.851471, -80.735718, 35.272560, 35.407925), |
| 888 |
(28270, -80.794983, -80.728966, 35.059872, 35.161823), |
| 889 |
(28273, -80.994766, -80.875259, 35.074734, 35.172836), |
| 890 |
(28277, -80.876793, -80.767586, 35.001709, 35.101063), |
| 891 |
(28278, -81.058029, -80.956375, 35.044701, 35.223812), |
| 892 |
(28280, -80.844208, -80.841972, 35.225468, 35.227203), |
| 893 |
(28282, -80.846382, -80.844193, 35.223972, 35.225655); |
| 894 |
|
| 895 |
INSERT INTO demo_index |
| 896 |
SELECT NULL, minX, maxX, minY+0.2, maxY+0.2 FROM demo_index; |
| 897 |
INSERT INTO demo_index |
| 898 |
SELECT NULL, minX+0.2, maxX+0.2, minY, maxY FROM demo_index; |
| 899 |
INSERT INTO demo_index |
| 900 |
SELECT NULL, minX, maxX, minY+0.4, maxY+0.4 FROM demo_index; |
| 901 |
INSERT INTO demo_index |
| 902 |
SELECT NULL, minX+0.4, maxX+0.4, minY, maxY FROM demo_index; |
| 903 |
INSERT INTO demo_index |
| 904 |
SELECT NULL, minX, maxX, minY+0.8, maxY+0.8 FROM demo_index; |
| 905 |
INSERT INTO demo_index |
| 906 |
SELECT NULL, minX+0.8, maxX+0.8, minY, maxY FROM demo_index; |
| 907 |
|
| 908 |
INSERT INTO demo_data(id) SELECT id FROM demo_index; |
| 909 |
|
| 910 |
SELECT count(*) FROM demo_index; |
| 911 |
} {896} |
| 912 |
|
| 913 |
set ::contained_in 0 |
| 914 |
proc contained_in {args} {incr ::contained_in ; return 0} |
| 915 |
db func contained_in contained_in |
| 916 |
|
| 917 |
# EVIDENCE-OF: R-32671-43888 Then an efficient way to find the specific |
| 918 |
# ZIP code for the main SQLite office would be to run a query like this: |
| 919 |
# SELECT objname FROM demo_data, demo_index WHERE |
| 920 |
# demo_data.id=demo_index.id AND contained_in(demo_data.boundary, |
| 921 |
# 35.37785, -80.77470) AND minX<=-80.77470 AND maxX>=-80.77470 AND |
| 922 |
# minY<=35.37785 AND maxY>=35.37785; |
| 923 |
do_vmstep_test 1.2 { |
| 924 |
SELECT objname FROM demo_data, demo_index |
| 925 |
WHERE demo_data.id=demo_index.id |
| 926 |
AND contained_in(demo_data.boundary, 35.37785, -80.77470) |
| 927 |
AND minX<=-80.77470 AND maxX>=-80.77470 |
| 928 |
AND minY<=35.37785 AND maxY>=35.37785; |
| 929 |
} {$step<100} |
| 930 |
set ::contained_in1 $::contained_in |
| 931 |
|
| 932 |
# EVIDENCE-OF: R-32761-23915 One would get the same answer without the |
| 933 |
# use of the R*Tree index using the following simpler query: SELECT |
| 934 |
# objname FROM demo_data WHERE contained_in(demo_data.boundary, |
| 935 |
# 35.37785, -80.77470); |
| 936 |
set ::contained_in 0 |
| 937 |
do_vmstep_test 1.3 { |
| 938 |
SELECT objname FROM demo_data |
| 939 |
WHERE contained_in(demo_data.boundary, 35.37785, -80.77470); |
| 940 |
} {$step>3200} |
| 941 |
|
| 942 |
# EVIDENCE-OF: R-40261-32799 The problem with this latter query is that |
| 943 |
# it must apply the contained_in() function to all entries in the |
| 944 |
# demo_data table. |
| 945 |
# |
| 946 |
# 896 of them, IIRC. |
| 947 |
do_test 1.4 { |
| 948 |
set ::contained_in |
| 949 |
} 896 |
| 950 |
|
| 951 |
# EVIDENCE-OF: R-24212-52761 The use of the R*Tree in the penultimate |
| 952 |
# query reduces the number of calls to contained_in() function to a |
| 953 |
# small subset of the entire table. |
| 954 |
# |
| 955 |
# 2 is a small subset of 896. |
| 956 |
# |
| 957 |
# EVIDENCE-OF: R-39057-63901 The R*Tree index did not find the exact |
| 958 |
# answer itself, it merely limited the search space. |
| 959 |
# |
| 960 |
# contained_in() filtered out those 2 rows. |
| 961 |
do_test 1.5 { |
| 962 |
set ::contained_in1 |
| 963 |
} {2} |
| 964 |
|
| 965 |
|
| 966 |
#------------------------------------------------------------------------- |
| 967 |
#------------------------------------------------------------------------- |
| 968 |
# Section 4.1 of documentation. |
| 969 |
#------------------------------------------------------------------------- |
| 970 |
#------------------------------------------------------------------------- |
| 971 |
set testprefix rtreedoc-9 |
| 972 |
reset_db |
| 973 |
|
| 974 |
# EVIDENCE-OF: R-46566-43213 Beginning with SQLite version 3.24.0 |
| 975 |
# (2018-06-04), r-tree tables can have auxiliary columns that store |
| 976 |
# arbitrary data. Auxiliary columns can be used in place of secondary |
| 977 |
# tables such as "demo_data". |
| 978 |
# |
| 979 |
# EVIDENCE-OF: R-41287-48160 Auxiliary columns are marked with a "+" |
| 980 |
# symbol before the column name. |
| 981 |
# |
| 982 |
# This interface cannot conveniently be used to prove anything about |
| 983 |
# versions of SQLite prior to 3.24.0. |
| 984 |
# |
| 985 |
do_execsql_test 1.0 { |
| 986 |
CREATE VIRTUAL TABLE rta USING rtree( |
| 987 |
id, u1,u2, v1,v2, +aux |
| 988 |
); |
| 989 |
|
| 990 |
INSERT INTO rta(aux) VALUES(NULL); |
| 991 |
INSERT INTO rta(aux) VALUES(45); |
| 992 |
INSERT INTO rta(aux) VALUES(22.3); |
| 993 |
INSERT INTO rta(aux) VALUES('hello'); |
| 994 |
INSERT INTO rta(aux) VALUES(X'ABCD'); |
| 995 |
|
| 996 |
SELECT typeof(aux), quote(aux) FROM rta; |
| 997 |
} { |
| 998 |
null NULL |
| 999 |
integer 45 |
| 1000 |
real 22.3 |
| 1001 |
text 'hello' |
| 1002 |
blob X'ABCD' |
| 1003 |
} |
| 1004 |
|
| 1005 |
# EVIDENCE-OF: R-30514-26093 Auxiliary columns must come after all of |
| 1006 |
# the coordinate boundary columns. |
| 1007 |
foreach {tn cols} { |
| 1008 |
1 "id x1,x2, +extra, y1,y2" |
| 1009 |
2 "extra, +id x1,x2, y1,y2" |
| 1010 |
3 "id, x1,+x2, extra, y1,y2" |
| 1011 |
} { |
| 1012 |
do_catchsql_test 2.$tn " |
| 1013 |
CREATE VIRTUAL TABLE rrr USING rtree($cols) |
| 1014 |
" {1 {Auxiliary rtree columns must be last}} |
| 1015 |
} |
| 1016 |
do_catchsql_test 3.0 { |
| 1017 |
CREATE VIRTUAL TABLE rrr USING rtree(+id, extra, x1, x2); |
| 1018 |
} {1 {near "+": syntax error}} |
| 1019 |
|
| 1020 |
# EVIDENCE-OF: R-01280-03635 An RTREE table can have no more than 100 |
| 1021 |
# columns total. In other words, the count of columns including the |
| 1022 |
# integer primary key column, the coordinate boundary columns, and all |
| 1023 |
# auxiliary columns must be 100 or less. |
| 1024 |
do_catchsql_test 3.1 { |
| 1025 |
CREATE VIRTUAL TABLE r1 USING rtree(intid, u1,u2, |
| 1026 |
+c00, +c01, +c02, +c03, +c04, +c05, +c06, +c07, +c08, +c09, |
| 1027 |
+c10, +c11, +c12, +c13, +c14, +c15, +c16, +c17, +c18, +c19, |
| 1028 |
+c20, +c21, +c22, +c23, +c24, +c25, +c26, +c27, +c28, +c29, |
| 1029 |
+c30, +c31, +c32, +c33, +c34, +c35, +c36, +c37, +c38, +c39, |
| 1030 |
+c40, +c41, +c42, +c43, +c44, +c45, +c46, +c47, +c48, +c49, |
| 1031 |
+c50, +c51, +c52, +c53, +c54, +c55, +c56, +c57, +c58, +c59, |
| 1032 |
+c60, +c61, +c62, +c63, +c64, +c65, +c66, +c67, +c68, +c69, |
| 1033 |
+c70, +c71, +c72, +c73, +c74, +c75, +c76, +c77, +c78, +c79, |
| 1034 |
+c80, +c81, +c82, +c83, +c84, +c85, +c86, +c87, +c88, +c89, |
| 1035 |
+c90, +c91, +c92, +c93, +c94, +c95, +c96 |
| 1036 |
); |
| 1037 |
} {0 {}} |
| 1038 |
do_catchsql_test 3.2 { |
| 1039 |
DROP TABLE r1; |
| 1040 |
CREATE VIRTUAL TABLE r1 USING rtree(intid, u1,u2, |
| 1041 |
+c00, +c01, +c02, +c03, +c04, +c05, +c06, +c07, +c08, +c09, |
| 1042 |
+c10, +c11, +c12, +c13, +c14, +c15, +c16, +c17, +c18, +c19, |
| 1043 |
+c20, +c21, +c22, +c23, +c24, +c25, +c26, +c27, +c28, +c29, |
| 1044 |
+c30, +c31, +c32, +c33, +c34, +c35, +c36, +c37, +c38, +c39, |
| 1045 |
+c40, +c41, +c42, +c43, +c44, +c45, +c46, +c47, +c48, +c49, |
| 1046 |
+c50, +c51, +c52, +c53, +c54, +c55, +c56, +c57, +c58, +c59, |
| 1047 |
+c60, +c61, +c62, +c63, +c64, +c65, +c66, +c67, +c68, +c69, |
| 1048 |
+c70, +c71, +c72, +c73, +c74, +c75, +c76, +c77, +c78, +c79, |
| 1049 |
+c80, +c81, +c82, +c83, +c84, +c85, +c86, +c87, +c88, +c89, |
| 1050 |
+c90, +c91, +c92, +c93, +c94, +c95, +c96, +c97 |
| 1051 |
); |
| 1052 |
} {1 {Too many columns for an rtree table}} |
| 1053 |
do_catchsql_test 3.3 { |
| 1054 |
CREATE VIRTUAL TABLE r1 USING rtree(intid, u1,u2, v1,v2, |
| 1055 |
+c00, +c01, +c02, +c03, +c04, +c05, +c06, +c07, +c08, +c09, |
| 1056 |
+c10, +c11, +c12, +c13, +c14, +c15, +c16, +c17, +c18, +c19, |
| 1057 |
+c20, +c21, +c22, +c23, +c24, +c25, +c26, +c27, +c28, +c29, |
| 1058 |
+c30, +c31, +c32, +c33, +c34, +c35, +c36, +c37, +c38, +c39, |
| 1059 |
+c40, +c41, +c42, +c43, +c44, +c45, +c46, +c47, +c48, +c49, |
| 1060 |
+c50, +c51, +c52, +c53, +c54, +c55, +c56, +c57, +c58, +c59, |
| 1061 |
+c60, +c61, +c62, +c63, +c64, +c65, +c66, +c67, +c68, +c69, |
| 1062 |
+c70, +c71, +c72, +c73, +c74, +c75, +c76, +c77, +c78, +c79, |
| 1063 |
+c80, +c81, +c82, +c83, +c84, +c85, +c86, +c87, +c88, +c89, |
| 1064 |
+c90, +c91, +c92, +c93, +c94, |
| 1065 |
); |
| 1066 |
} {0 {}} |
| 1067 |
do_catchsql_test 3.4 { |
| 1068 |
DROP TABLE r1; |
| 1069 |
CREATE VIRTUAL TABLE r1 USING rtree(intid, u1,u2, v1,v2, |
| 1070 |
+c00, +c01, +c02, +c03, +c04, +c05, +c06, +c07, +c08, +c09, |
| 1071 |
+c10, +c11, +c12, +c13, +c14, +c15, +c16, +c17, +c18, +c19, |
| 1072 |
+c20, +c21, +c22, +c23, +c24, +c25, +c26, +c27, +c28, +c29, |
| 1073 |
+c30, +c31, +c32, +c33, +c34, +c35, +c36, +c37, +c38, +c39, |
| 1074 |
+c40, +c41, +c42, +c43, +c44, +c45, +c46, +c47, +c48, +c49, |
| 1075 |
+c50, +c51, +c52, +c53, +c54, +c55, +c56, +c57, +c58, +c59, |
| 1076 |
+c60, +c61, +c62, +c63, +c64, +c65, +c66, +c67, +c68, +c69, |
| 1077 |
+c70, +c71, +c72, +c73, +c74, +c75, +c76, +c77, +c78, +c79, |
| 1078 |
+c80, +c81, +c82, +c83, +c84, +c85, +c86, +c87, +c88, +c89, |
| 1079 |
+c90, +c91, +c92, +c93, +c94, +c95, |
| 1080 |
); |
| 1081 |
} {1 {Too many columns for an rtree table}} |
| 1082 |
|
| 1083 |
# EVIDENCE-OF: R-05552-15084 |
| 1084 |
do_execsql_test 4.0 { |
| 1085 |
CREATE VIRTUAL TABLE demo_index2 USING rtree( |
| 1086 |
id, -- Integer primary key |
| 1087 |
minX, maxX, -- Minimum and maximum X coordinate |
| 1088 |
minY, maxY, -- Minimum and maximum Y coordinate |
| 1089 |
+objname TEXT, -- name of the object |
| 1090 |
+objtype TEXT, -- object type |
| 1091 |
+boundary BLOB -- detailed boundary of object |
| 1092 |
); |
| 1093 |
} |
| 1094 |
do_execsql_test 4.1 { |
| 1095 |
CREATE VIRTUAL TABLE demo_index USING rtree( |
| 1096 |
id, -- Integer primary key |
| 1097 |
minX, maxX, -- Minimum and maximum X coordinate |
| 1098 |
minY, maxY -- Minimum and maximum Y coordinate |
| 1099 |
); |
| 1100 |
CREATE TABLE demo_data( |
| 1101 |
id INTEGER PRIMARY KEY, -- primary key |
| 1102 |
objname TEXT, -- name of the object |
| 1103 |
objtype TEXT, -- object type |
| 1104 |
boundary BLOB -- detailed boundary of object |
| 1105 |
); |
| 1106 |
|
| 1107 |
INSERT INTO demo_index2(id) VALUES(1); |
| 1108 |
INSERT INTO demo_index(id) VALUES(1); |
| 1109 |
INSERT INTO demo_data(id) VALUES(1); |
| 1110 |
} |
| 1111 |
do_test 4.2 { |
| 1112 |
catch { array unset R } |
| 1113 |
db eval {SELECT * FROM demo_index2} R { set r1 [array names R] } |
| 1114 |
catch { array unset R } |
| 1115 |
db eval {SELECT * FROM demo_index NATURAL JOIN demo_data } R { |
| 1116 |
set r2 [array names R] |
| 1117 |
} |
| 1118 |
expr {$r1==$r2} |
| 1119 |
} {1} |
| 1120 |
|
| 1121 |
# EVIDENCE-OF: R-26099-32169 SELECT objname FROM demo_index2 WHERE |
| 1122 |
# contained_in(boundary, 35.37785, -80.77470) AND minX<=-80.77470 AND |
| 1123 |
# maxX>=-80.77470 AND minY<=35.37785 AND maxY>=35.37785; |
| 1124 |
do_execsql_test 4.3.1 { |
| 1125 |
DELETE FROM demo_index2; |
| 1126 |
INSERT INTO demo_index2(id,minX,maxX,minY,maxY) VALUES |
| 1127 |
(28215, -80.781227, -80.604706, 35.208813, 35.297367), |
| 1128 |
(28216, -80.957283, -80.840599, 35.235920, 35.367825), |
| 1129 |
(28217, -80.960869, -80.869431, 35.133682, 35.208233), |
| 1130 |
(28226, -80.878983, -80.778275, 35.060287, 35.154446), |
| 1131 |
(28227, -80.745544, -80.555382, 35.130215, 35.236916), |
| 1132 |
(28244, -80.844208, -80.841988, 35.223728, 35.225471), |
| 1133 |
(28262, -80.809074, -80.682938, 35.276207, 35.377747), |
| 1134 |
(28269, -80.851471, -80.735718, 35.272560, 35.407925), |
| 1135 |
(28270, -80.794983, -80.728966, 35.059872, 35.161823), |
| 1136 |
(28273, -80.994766, -80.875259, 35.074734, 35.172836), |
| 1137 |
(28277, -80.876793, -80.767586, 35.001709, 35.101063), |
| 1138 |
(28278, -81.058029, -80.956375, 35.044701, 35.223812), |
| 1139 |
(28280, -80.844208, -80.841972, 35.225468, 35.227203), |
| 1140 |
(28282, -80.846382, -80.844193, 35.223972, 35.225655); |
| 1141 |
} |
| 1142 |
set ::contained_in 0 |
| 1143 |
proc contained_in {args} { |
| 1144 |
incr ::contained_in |
| 1145 |
return 0 |
| 1146 |
} |
| 1147 |
db func contained_in contained_in |
| 1148 |
do_execsql_test 4.3.2 { |
| 1149 |
SELECT objname FROM demo_index2 |
| 1150 |
WHERE contained_in(boundary, 35.37785, -80.77470) |
| 1151 |
AND minX<=-80.77470 AND maxX>=-80.77470 |
| 1152 |
AND minY<=35.37785 AND maxY>=35.37785; |
| 1153 |
} |
| 1154 |
do_test 4.3.3 { |
| 1155 |
# Function invoked only once because r-tree filtering happened first. |
| 1156 |
set ::contained_in |
| 1157 |
} 1 |
| 1158 |
set ::contained_in 0 |
| 1159 |
do_execsql_test 4.3.4 { |
| 1160 |
SELECT objname FROM demo_index2 |
| 1161 |
WHERE contained_in(boundary, 35.37785, -80.77470) |
| 1162 |
} |
| 1163 |
do_test 4.3.3 { |
| 1164 |
# Function invoked 14 times because no r-tree filtering. Inefficient. |
| 1165 |
set ::contained_in |
| 1166 |
} 14 |
| 1167 |
|
| 1168 |
#------------------------------------------------------------------------- |
| 1169 |
#------------------------------------------------------------------------- |
| 1170 |
# Section 4.1.1 of documentation. |
| 1171 |
#------------------------------------------------------------------------- |
| 1172 |
#------------------------------------------------------------------------- |
| 1173 |
set testprefix rtreedoc-9 |
| 1174 |
reset_db |
| 1175 |
|
| 1176 |
# EVIDENCE-OF: R-24021-02490 For auxiliary columns, only the name of the |
| 1177 |
# column matters. The type affinity is ignored. |
| 1178 |
# |
| 1179 |
# EVIDENCE-OF: R-39906-44154 Constraints such as NOT NULL, UNIQUE, |
| 1180 |
# REFERENCES, or CHECK are also ignored. |
| 1181 |
do_execsql_test 1.0 { PRAGMA foreign_keys = on } |
| 1182 |
foreach {tn auxcol nm} { |
| 1183 |
1 "+extra INTEGER" extra |
| 1184 |
2 "+extra TEXT" extra |
| 1185 |
3 "+extra BLOB" extra |
| 1186 |
4 "+extra REAL" extra |
| 1187 |
|
| 1188 |
5 "+col NOT NULL" col |
| 1189 |
6 "+col CHECK (col IS NOT NULL)" col |
| 1190 |
7 "+col REFERENCES tbl(x)" col |
| 1191 |
} { |
| 1192 |
do_execsql_test 1.$tn.1 " |
| 1193 |
CREATE VIRTUAL TABLE rt USING rtree_i32(k, a,b, $auxcol) |
| 1194 |
" |
| 1195 |
|
| 1196 |
# Check that the aux column has no affinity. Or NOT NULL constraint. |
| 1197 |
# And that the aux column is the child key of an FK constraint. |
| 1198 |
# |
| 1199 |
do_execsql_test 1.$tn.2 " |
| 1200 |
INSERT INTO rt($nm) VALUES(NULL), (45), (-123.2), ('456'), (X'ABCD'); |
| 1201 |
SELECT typeof($nm), quote($nm) FROM rt; |
| 1202 |
" { |
| 1203 |
null NULL |
| 1204 |
integer 45 |
| 1205 |
real -123.2 |
| 1206 |
text '456' |
| 1207 |
blob X'ABCD' |
| 1208 |
} |
| 1209 |
|
| 1210 |
# Check that there is no UNIQUE constraint either. |
| 1211 |
# |
| 1212 |
do_execsql_test 1.$tn.3 " |
| 1213 |
INSERT INTO rt($nm) VALUES('xyz'), ('xyz'), ('xyz'); |
| 1214 |
" |
| 1215 |
|
| 1216 |
do_execsql_test 1.$tn.2 { |
| 1217 |
DROP TABLE rt |
| 1218 |
} |
| 1219 |
} |
| 1220 |
|
| 1221 |
#------------------------------------------------------------------------- |
| 1222 |
#------------------------------------------------------------------------- |
| 1223 |
# Section 5 of documentation. |
| 1224 |
#------------------------------------------------------------------------- |
| 1225 |
#------------------------------------------------------------------------- |
| 1226 |
set testprefix rtreedoc-10 |
| 1227 |
|
| 1228 |
# EVIDENCE-OF: R-21011-43790 If integer coordinates are desired, declare |
| 1229 |
# the table using "rtree_i32" instead: CREATE VIRTUAL TABLE intrtree |
| 1230 |
# USING rtree_i32(id,x0,x1,y0,y1,z0,z1); |
| 1231 |
do_execsql_test 1.0 { |
| 1232 |
CREATE VIRTUAL TABLE intrtree USING rtree_i32(id,x0,x1,y0,y1,z0,z1); |
| 1233 |
INSERT INTO intrtree DEFAULT VALUES; |
| 1234 |
SELECT typeof(x0) FROM intrtree; |
| 1235 |
} {integer} |
| 1236 |
|
| 1237 |
# EVIDENCE-OF: R-09193-49806 An rtree_i32 stores coordinates as 32-bit |
| 1238 |
# signed integers. |
| 1239 |
# |
| 1240 |
# Show that coordinates are cast in a way consistent with casting to |
| 1241 |
# a signed 32-bit integer. |
| 1242 |
do_execsql_test 1.1 { |
| 1243 |
DELETE FROM intrtree; |
| 1244 |
INSERT INTO intrtree VALUES(333, |
| 1245 |
1<<44, (1<<44)+1, |
| 1246 |
10000000000, 10000000001, |
| 1247 |
-10000000001, -10000000000 |
| 1248 |
); |
| 1249 |
SELECT * FROM intrtree; |
| 1250 |
} { |
| 1251 |
333 0 1 1410065408 1410065409 -1410065409 -1410065408 |
| 1252 |
} |
| 1253 |
|
| 1254 |
#------------------------------------------------------------------------- |
| 1255 |
#------------------------------------------------------------------------- |
| 1256 |
# Section 7.1 of documentation. |
| 1257 |
#------------------------------------------------------------------------- |
| 1258 |
#------------------------------------------------------------------------- |
| 1259 |
set testprefix rtreedoc-11 |
| 1260 |
reset_db |
| 1261 |
|
| 1262 |
# This command assumes that the argument is a node blob for a 2 dimensional |
| 1263 |
# i32 r-tree table. It decodes and returns a list of cells from the node |
| 1264 |
# as a list. Each cell is itself a list of the following form: |
| 1265 |
# |
| 1266 |
# {$rowid $minX $maxX $minY $maxY} |
| 1267 |
# |
| 1268 |
# For internal (non-leaf) nodes, the rowid is replaced by the child node |
| 1269 |
# number. |
| 1270 |
# |
| 1271 |
proc rnode {aData} { |
| 1272 |
set nDim 2 |
| 1273 |
|
| 1274 |
set nData [string length $aData] |
| 1275 |
set nBytePerCell [expr (8 + 2*$nDim*4)] |
| 1276 |
binary scan [string range $aData 2 3] S nCell |
| 1277 |
|
| 1278 |
set res [list] |
| 1279 |
for {set i 0} {$i < $nCell} {incr i} { |
| 1280 |
set iOff [expr $i*$nBytePerCell+4] |
| 1281 |
set cell [string range $aData $iOff [expr $iOff+$nBytePerCell-1]] |
| 1282 |
binary scan $cell WIIII rowid x1 x2 y1 y2 |
| 1283 |
lappend res [list $rowid $x1 $x2 $y1 $y2] |
| 1284 |
} |
| 1285 |
|
| 1286 |
return $res |
| 1287 |
} |
| 1288 |
|
| 1289 |
# aData must be a node blob. This command returns true if the node contains |
| 1290 |
# rowid $rowid, or false otherwise. |
| 1291 |
# |
| 1292 |
proc rnode_contains {aData rowid} { |
| 1293 |
set L [rnode $aData] |
| 1294 |
foreach cell $L { |
| 1295 |
set r [lindex $cell 0] |
| 1296 |
if {$r==$rowid} { return 1 } |
| 1297 |
} |
| 1298 |
return 0 |
| 1299 |
} |
| 1300 |
|
| 1301 |
proc rnode_replace_cell {aData iCell cell} { |
| 1302 |
set aCell [binary format WIIII {*}$cell] |
| 1303 |
set nDim 2 |
| 1304 |
set nBytePerCell [expr (8 + 2*$nDim*4)] |
| 1305 |
set iOff [expr $iCell*$nBytePerCell+4] |
| 1306 |
|
| 1307 |
set aNew [binary format a*a*a* \ |
| 1308 |
[string range $aData 0 $iOff-1] \ |
| 1309 |
$aCell \ |
| 1310 |
[string range $aData $iOff+$nBytePerCell end] \ |
| 1311 |
] |
| 1312 |
return $aNew |
| 1313 |
} |
| 1314 |
|
| 1315 |
db function rnode rnode |
| 1316 |
db function rnode_contains rnode_contains |
| 1317 |
db function rnode_replace_cell rnode_replace_cell |
| 1318 |
|
| 1319 |
foreach {tn nm} { |
| 1320 |
1 x1 |
| 1321 |
2 asdfghjkl |
| 1322 |
3 hello_world |
| 1323 |
} { |
| 1324 |
do_execsql_test 1.$tn.1 " |
| 1325 |
CREATE VIRTUAL TABLE $nm USING rtree(a,b,c,d,e); |
| 1326 |
" |
| 1327 |
|
| 1328 |
# EVIDENCE-OF: R-33789-46762 The content of an R*Tree index is actually |
| 1329 |
# stored in three ordinary SQLite tables with names derived from the |
| 1330 |
# name of the R*Tree. |
| 1331 |
# |
| 1332 |
# EVIDENCE-OF: R-39849-06566 This is their schema: CREATE TABLE |
| 1333 |
# %_node(nodeno INTEGER PRIMARY KEY, data) CREATE TABLE %_parent(nodeno |
| 1334 |
# INTEGER PRIMARY KEY, parentnode) CREATE TABLE %_rowid(rowid INTEGER |
| 1335 |
# PRIMARY KEY, nodeno) |
| 1336 |
# |
| 1337 |
# EVIDENCE-OF: R-07489-10051 The "%" in the name of each shadow table is |
| 1338 |
# replaced by the name of the R*Tree virtual table. So, if the name of |
| 1339 |
# the R*Tree table is "xyz" then the three shadow tables would be |
| 1340 |
# "xyz_node", "xyz_parent", and "xyz_rowid". |
| 1341 |
do_execsql_test 1.$tn.2 { |
| 1342 |
SELECT sql FROM sqlite_schema WHERE name!=$nm ORDER BY 1 |
| 1343 |
} [string map [list % $nm] " |
| 1344 |
{CREATE TABLE \"%_node\"(nodeno INTEGER PRIMARY KEY,data)} |
| 1345 |
{CREATE TABLE \"%_parent\"(nodeno INTEGER PRIMARY KEY,parentnode)} |
| 1346 |
{CREATE TABLE \"%_rowid\"(rowid INTEGER PRIMARY KEY,nodeno)} |
| 1347 |
"] |
| 1348 |
|
| 1349 |
do_execsql_test 1.$tn "DROP TABLE $nm" |
| 1350 |
} |
| 1351 |
|
| 1352 |
|
| 1353 |
# EVIDENCE-OF: R-51070-59303 There is one entry in the %_node table for |
| 1354 |
# each R*Tree node. |
| 1355 |
# |
| 1356 |
# The following creates a 6 node r-tree structure. |
| 1357 |
# |
| 1358 |
do_execsql_test 2.0 { |
| 1359 |
CREATE VIRTUAL TABLE r1 USING rtree_i32(i, x1,x2, y1,y2); |
| 1360 |
WITH t(i) AS ( |
| 1361 |
VALUES(1) UNION SELECT i+1 FROM t WHERE i<110 |
| 1362 |
) |
| 1363 |
INSERT INTO r1 SELECT i, (i%10), (i%10)+2, (i%6), (i%7)+6 FROM t; |
| 1364 |
} |
| 1365 |
do_execsql_test 2.1 { |
| 1366 |
SELECT count(*) FROM r1_node; |
| 1367 |
} 6 |
| 1368 |
|
| 1369 |
# EVIDENCE-OF: R-27261-09153 All nodes other than the root have an entry |
| 1370 |
# in the %_parent shadow table that identifies the parent node. |
| 1371 |
# |
| 1372 |
# In this case nodes 2-6 are the children of node 1. |
| 1373 |
# |
| 1374 |
do_execsql_test 2.3 { |
| 1375 |
SELECT nodeno, parentnode FROM r1_parent |
| 1376 |
} {2 1 3 1 4 1 5 1 6 1} |
| 1377 |
|
| 1378 |
# EVIDENCE-OF: R-02358-35037 The %_rowid shadow table maps entry rowids |
| 1379 |
# to the node that contains that entry. |
| 1380 |
# |
| 1381 |
do_execsql_test 2.4 { |
| 1382 |
SELECT 'failed' FROM r1_rowid WHERE 0==rnode_contains( |
| 1383 |
(SELECT data FROM r1_node WHERE nodeno=r1_rowid.nodeno), rowid |
| 1384 |
) |
| 1385 |
} |
| 1386 |
do_test 2.5 { |
| 1387 |
db eval { SELECT nodeno, data FROM r1_node WHERE nodeno!=1 } { |
| 1388 |
set L [rnode $data] |
| 1389 |
foreach cell $L { |
| 1390 |
set rowid [lindex $cell 0] |
| 1391 |
set rowid_nodeno 0 |
| 1392 |
db eval {SELECT nodeno AS rowid_nodeno FROM r1_rowid WHERE rowid=$rowid} { |
| 1393 |
break |
| 1394 |
} |
| 1395 |
if {$rowid_nodeno!=$nodeno} { error "data mismatch!" } |
| 1396 |
} |
| 1397 |
} |
| 1398 |
} {} |
| 1399 |
|
| 1400 |
# EVIDENCE-OF: R-65201-22208 Extra columns appended to the %_rowid table |
| 1401 |
# hold the content of auxiliary columns. |
| 1402 |
# |
| 1403 |
# EVIDENCE-OF: R-44161-28345 The names of these extra %_rowid columns |
| 1404 |
# are probably not the same as the actual auxiliary column names. |
| 1405 |
# |
| 1406 |
# In this case, the auxiliary columns are named "e1" and "e2". The |
| 1407 |
# extra %_rowid columns are named "a0" and "a1". |
| 1408 |
# |
| 1409 |
do_execsql_test 3.0 { |
| 1410 |
CREATE VIRTUAL TABLE rtaux USING rtree(id, x1,x2, y1,y2, +e1, +e2); |
| 1411 |
SELECT sql FROM sqlite_schema WHERE name='rtaux_rowid'; |
| 1412 |
} { |
| 1413 |
{CREATE TABLE "rtaux_rowid"(rowid INTEGER PRIMARY KEY,nodeno,a0,a1)} |
| 1414 |
} |
| 1415 |
do_execsql_test 3.1 { |
| 1416 |
INSERT INTO rtaux(e1, e2) VALUES('hello', 'world'), (123, 456); |
| 1417 |
} |
| 1418 |
do_execsql_test 3.2 { |
| 1419 |
SELECT a0, a1 FROM rtaux_rowid; |
| 1420 |
} { |
| 1421 |
hello world 123 456 |
| 1422 |
} |
| 1423 |
|
| 1424 |
#------------------------------------------------------------------------- |
| 1425 |
#------------------------------------------------------------------------- |
| 1426 |
# Section 7.2 of documentation. |
| 1427 |
#------------------------------------------------------------------------- |
| 1428 |
#------------------------------------------------------------------------- |
| 1429 |
set testprefix rtreedoc-12 |
| 1430 |
reset_db |
| 1431 |
forcedelete test.db2 |
| 1432 |
|
| 1433 |
db function rnode rnode |
| 1434 |
db function rnode_contains rnode_contains |
| 1435 |
db function rnode_replace_cell rnode_replace_cell |
| 1436 |
|
| 1437 |
# EVIDENCE-OF: R-13571-45795 The scalar SQL function rtreecheck(R) or |
| 1438 |
# rtreecheck(S,R) runs an integrity check on the rtree table named R |
| 1439 |
# contained within database S. |
| 1440 |
# |
| 1441 |
# EVIDENCE-OF: R-36011-59963 The function returns a human-language |
| 1442 |
# description of any problems found, or the string 'ok' if everything is |
| 1443 |
# ok. |
| 1444 |
# |
| 1445 |
do_execsql_test 1.0 { |
| 1446 |
CREATE VIRTUAL TABLE rt1 USING rtree(id, a, b); |
| 1447 |
WITH s(i) AS ( |
| 1448 |
VALUES(1) UNION ALL SELECT i+1 FROM s WHERE i<200 |
| 1449 |
) |
| 1450 |
INSERT INTO rt1 SELECT i, i, i FROM s; |
| 1451 |
|
| 1452 |
ATTACH 'test.db2' AS 'aux'; |
| 1453 |
CREATE VIRTUAL TABLE aux.rt1 USING rtree(id, a, b); |
| 1454 |
INSERT INTO aux.rt1 SELECT * FROM rt1; |
| 1455 |
} |
| 1456 |
|
| 1457 |
do_execsql_test 1.1.1 { SELECT rtreecheck('rt1'); } {ok} |
| 1458 |
do_execsql_test 1.1.2 { SELECT rtreecheck('main', 'rt1'); } {ok} |
| 1459 |
do_execsql_test 1.1.3 { SELECT rtreecheck('aux', 'rt1'); } {ok} |
| 1460 |
do_catchsql_test 1.1.4 { |
| 1461 |
SELECT rtreecheck('nosuchdb', 'rt1'); |
| 1462 |
} {1 {SQL logic error}} |
| 1463 |
|
| 1464 |
# Corrupt the table in database 'main': |
| 1465 |
do_execsql_test 1.2.1 { UPDATE rt1_node SET nodeno=21 WHERE nodeno=3; } |
| 1466 |
do_execsql_test 1.2.1 { SELECT rtreecheck('rt1')=='ok'; } {0} |
| 1467 |
do_execsql_test 1.2.2 { SELECT rtreecheck('main', 'rt1')=='ok'; } {0} |
| 1468 |
do_execsql_test 1.2.3 { SELECT rtreecheck('aux', 'rt1')=='ok'; } {1} |
| 1469 |
do_execsql_test 1.2.4 { UPDATE rt1_node SET nodeno=3 WHERE nodeno=21; } |
| 1470 |
|
| 1471 |
# Corrupt the table in database 'aux': |
| 1472 |
do_execsql_test 1.2.1 { UPDATE aux.rt1_node SET nodeno=21 WHERE nodeno=3; } |
| 1473 |
do_execsql_test 1.2.1 { SELECT rtreecheck('rt1')=='ok'; } {1} |
| 1474 |
do_execsql_test 1.2.2 { SELECT rtreecheck('main', 'rt1')=='ok'; } {1} |
| 1475 |
do_execsql_test 1.2.3 { SELECT rtreecheck('aux', 'rt1')=='ok'; } {0} |
| 1476 |
do_execsql_test 1.2.4 { UPDATE rt1_node SET nodeno=3 WHERE nodeno=21; } |
| 1477 |
|
| 1478 |
# EVIDENCE-OF: R-45759-33459 Example: To verify that an R*Tree named |
| 1479 |
# "demo_index" is well-formed and internally consistent, run: SELECT |
| 1480 |
# rtreecheck('demo_index'); |
| 1481 |
do_execsql_test 2.0 { |
| 1482 |
CREATE VIRTUAL TABLE demo_index USING rtree(id, x1,x2, y1,y2); |
| 1483 |
INSERT INTO demo_index SELECT id, a, b, a, b FROM rt1; |
| 1484 |
} |
| 1485 |
do_execsql_test 2.1 { SELECT rtreecheck('demo_index') } {ok} |
| 1486 |
do_execsql_test 2.2 { |
| 1487 |
UPDATE demo_index_rowid SET nodeno=44 WHERE rowid=44; |
| 1488 |
SELECT rtreecheck('demo_index'); |
| 1489 |
} {{Found (44 -> 44) in %_rowid table, expected (44 -> 4)}} |
| 1490 |
|
| 1491 |
|
| 1492 |
do_execsql_test 3.0 { |
| 1493 |
CREATE VIRTUAL TABLE rt2 USING rtree_i32(id, a, b, c, d); |
| 1494 |
WITH s(i) AS ( |
| 1495 |
VALUES(1) UNION ALL SELECT i+1 FROM s WHERE i<200 |
| 1496 |
) |
| 1497 |
INSERT INTO rt2 SELECT i, i, i+2, i, i+2 FROM s; |
| 1498 |
} |
| 1499 |
|
| 1500 |
# EVIDENCE-OF: R-02555-31045 for each dimension, (coord1 <= coord2). |
| 1501 |
# |
| 1502 |
execsql BEGIN |
| 1503 |
do_test 3.1 { |
| 1504 |
set cell [ |
| 1505 |
lindex [execsql {SELECT rnode(data) FROM rt2_node WHERE nodeno=3}] 0 3 |
| 1506 |
] |
| 1507 |
set cell [list [lindex $cell 0] \ |
| 1508 |
[lindex $cell 2] [lindex $cell 1] \ |
| 1509 |
[lindex $cell 3] [lindex $cell 4] \ |
| 1510 |
] |
| 1511 |
execsql { |
| 1512 |
UPDATE rt2_node SET data=rnode_replace_cell(data, 3, $cell) WHERE nodeno=3 |
| 1513 |
} |
| 1514 |
execsql { SELECT rtreecheck('rt2') } |
| 1515 |
} {{Dimension 0 of cell 3 on node 3 is corrupt}} |
| 1516 |
execsql ROLLBACK |
| 1517 |
|
| 1518 |
# EVIDENCE-OF: R-13844-15873 unless the cell is on the root node, that |
| 1519 |
# the cell is bounded by the parent cell on the parent node. |
| 1520 |
# |
| 1521 |
execsql BEGIN |
| 1522 |
do_test 3.2 { |
| 1523 |
set cell [ |
| 1524 |
lindex [execsql {SELECT rnode(data) FROM rt2_node WHERE nodeno=3}] 0 3 |
| 1525 |
] |
| 1526 |
lset cell 3 450 |
| 1527 |
lset cell 4 451 |
| 1528 |
execsql { |
| 1529 |
UPDATE rt2_node SET data=rnode_replace_cell(data, 3, $cell) WHERE nodeno=3 |
| 1530 |
} |
| 1531 |
execsql { SELECT rtreecheck('rt2') } |
| 1532 |
} {{Dimension 1 of cell 3 on node 3 is corrupt relative to parent}} |
| 1533 |
execsql ROLLBACK |
| 1534 |
|
| 1535 |
# EVIDENCE-OF: R-02505-03621 for leaf nodes, that there is an entry in |
| 1536 |
# the %_rowid table corresponding to the cell's rowid value that points |
| 1537 |
# to the correct node. |
| 1538 |
# |
| 1539 |
execsql BEGIN |
| 1540 |
do_test 3.3 { |
| 1541 |
execsql { |
| 1542 |
UPDATE rt2_rowid SET rowid=452 WHERE rowid=100 |
| 1543 |
} |
| 1544 |
execsql { SELECT rtreecheck('rt2') } |
| 1545 |
} {{Mapping (100 -> 6) missing from %_rowid table}} |
| 1546 |
execsql ROLLBACK |
| 1547 |
|
| 1548 |
# EVIDENCE-OF: R-50927-02218 for cells on non-leaf nodes, that there is |
| 1549 |
# an entry in the %_parent table mapping from the cell's child node to |
| 1550 |
# the node that it resides on. |
| 1551 |
# |
| 1552 |
execsql BEGIN |
| 1553 |
do_test 3.4.1 { |
| 1554 |
execsql { |
| 1555 |
UPDATE rt2_parent SET parentnode=123 WHERE nodeno=3 |
| 1556 |
} |
| 1557 |
execsql { SELECT rtreecheck('rt2') } |
| 1558 |
} {{Found (3 -> 123) in %_parent table, expected (3 -> 1)}} |
| 1559 |
execsql ROLLBACK |
| 1560 |
execsql BEGIN |
| 1561 |
do_test 3.4.2 { |
| 1562 |
execsql { |
| 1563 |
UPDATE rt2_parent SET nodeno=123 WHERE nodeno=3 |
| 1564 |
} |
| 1565 |
execsql { SELECT rtreecheck('rt2') } |
| 1566 |
} {{Mapping (3 -> 1) missing from %_parent table}} |
| 1567 |
execsql ROLLBACK |
| 1568 |
|
| 1569 |
# EVIDENCE-OF: R-23235-09153 That there are the same number of entries |
| 1570 |
# in the %_rowid table as there are leaf cells in the r-tree structure, |
| 1571 |
# and that there is a leaf cell that corresponds to each entry in the |
| 1572 |
# %_rowid table. |
| 1573 |
execsql BEGIN |
| 1574 |
do_test 3.5 { |
| 1575 |
execsql { INSERT INTO rt2_rowid VALUES(1000, 1000) } |
| 1576 |
execsql { SELECT rtreecheck('rt2') } |
| 1577 |
} {{Wrong number of entries in %_rowid table - expected 200, actual 201}} |
| 1578 |
execsql ROLLBACK |
| 1579 |
|
| 1580 |
# EVIDENCE-OF: R-62800-43436 That there are the same number of entries |
| 1581 |
# in the %_parent table as there are non-leaf cells in the r-tree |
| 1582 |
# structure, and that there is a non-leaf cell that corresponds to each |
| 1583 |
# entry in the %_parent table. |
| 1584 |
execsql BEGIN |
| 1585 |
do_test 3.6 { |
| 1586 |
execsql { INSERT INTO rt2_parent VALUES(1000, 1000) } |
| 1587 |
execsql { SELECT rtreecheck('rt2') } |
| 1588 |
} {{Wrong number of entries in %_parent table - expected 10, actual 11}} |
| 1589 |
execsql ROLLBACK |
| 1590 |
|
| 1591 |
|
| 1592 |
|
| 1593 |
finish_test |