| blob | 4e610db8a2e7ea6a0d54decb449fbe861ef5fdb5 |
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 #
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
22 ifcapable !rtree {
23 finish_test
24 return
25 }
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 }
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
44 #-------------------------------------------------------------------------
45 #-------------------------------------------------------------------------
46 # Section 3 of documentation.
47 #-------------------------------------------------------------------------
48 #-------------------------------------------------------------------------
49 set testprefix rtreedoc-1
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
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
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
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
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
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}}
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 }
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 }
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}
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 }
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 }
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 }
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}
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}
271 #-------------------------------------------------------------------------
272 #-------------------------------------------------------------------------
273 # Section 3.1 of documentation.
274 #-------------------------------------------------------------------------
275 #-------------------------------------------------------------------------
276 set testprefix rtreedoc-2
277 reset_db
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 "
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]
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]
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]
306 do_execsql_test 1.$tn.5 "DROP TABLE $name"
307 }
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 }
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 }
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}
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 }
364 #-------------------------------------------------------------------------
365 #-------------------------------------------------------------------------
366 # Section 3.1.1 of documentation.
367 #-------------------------------------------------------------------------
368 #-------------------------------------------------------------------------
369 set testprefix rtreedoc-3
370 reset_db
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
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.
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 }
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}
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}
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}
419 do_execsql_test 1.$tn.7 " CREATE VIRTUAL TABLE abc2 USING rtree_i32 $cols "
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}
432 do_execsql_test 1.$tn.10 {
433 DROP TABLE abc;
434 DROP TABLE abc2;
435 }
436 }
438 #-------------------------------------------------------------------------
439 #-------------------------------------------------------------------------
440 # Section 3.2 of documentation.
441 #-------------------------------------------------------------------------
442 #-------------------------------------------------------------------------
443 set testprefix rtreedoc-4
444 reset_db
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
468 set data1 [execsql {SELECT * FROM rt ORDER BY 1}]
469 set data2 [execsql {SELECT * FROM t1 ORDER BY 1}]
471 set res [expr {$data1==$data2}]
472 do_test 1.$tn.2 {set res} 1
473 }
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 );
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 }
500 #-------------------------------------------------------------------------
501 #-------------------------------------------------------------------------
502 # Section 3.3 of documentation.
503 #-------------------------------------------------------------------------
504 #-------------------------------------------------------------------------
505 set testprefix rtreedoc-5
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;
521 SELECT count(*) FROM demo_index;
522 } {896}
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 }
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]
543 do_execsql_test 1.1.$tn $sql1 [execsql $sql2]
544 }
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}
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}
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}
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 }
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 }
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 } {}
638 #-------------------------------------------------------------------------
639 #-------------------------------------------------------------------------
640 # Section 3.4 of documentation.
641 #-------------------------------------------------------------------------
642 #-------------------------------------------------------------------------
643 set testprefix rtreedoc-6
644 reset_db
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}
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
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 }
685 do_execsql_test 3.0 {
686 DROP TABLE rt;
687 CREATE VIRTUAL TABLE rt USING rtree(id, x1,x2, y1,y2);
688 }
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 }
703 #-------------------------------------------------------------------------
704 #-------------------------------------------------------------------------
705 # Section 3.5 of documentation.
706 #-------------------------------------------------------------------------
707 #-------------------------------------------------------------------------
708 set testprefix rtreedoc-7
709 reset_db
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}]
731 db eval { INSERT INTO rt VALUES(NULL, 50, 50) } ;# THIS INSERT!!
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}
738 do_execsql_test 1.3 { SELECT count(*) FROM rt_node } 3
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 }
760 list $errorcode $rc $msg
761 } {6 1 {database table is locked}}
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}}
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}
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 {}}
848 #-------------------------------------------------------------------------
849 #-------------------------------------------------------------------------
850 # Section 4 of documentation.
851 #-------------------------------------------------------------------------
852 #-------------------------------------------------------------------------
853 set testprefix rtreedoc-8
854 reset_db
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 }
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 );
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);
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;
908 INSERT INTO demo_data(id) SELECT id FROM demo_index;
910 SELECT count(*) FROM demo_index;
911 } {896}
913 set ::contained_in 0
914 proc contained_in {args} {incr ::contained_in ; return 0}
915 db func contained_in contained_in
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
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}
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
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}
966 #-------------------------------------------------------------------------
967 #-------------------------------------------------------------------------
968 # Section 4.1 of documentation.
969 #-------------------------------------------------------------------------
970 #-------------------------------------------------------------------------
971 set testprefix rtreedoc-9
972 reset_db
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 );
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');
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 }
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}}
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}}
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 );
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}
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
1168 #-------------------------------------------------------------------------
1169 #-------------------------------------------------------------------------
1170 # Section 4.1.1 of documentation.
1171 #-------------------------------------------------------------------------
1172 #-------------------------------------------------------------------------
1173 set testprefix rtreedoc-9
1174 reset_db
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
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 "
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 }
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 "
1216 do_execsql_test 1.$tn.2 {
1217 DROP TABLE rt
1218 }
1219 }
1221 #-------------------------------------------------------------------------
1222 #-------------------------------------------------------------------------
1223 # Section 5 of documentation.
1224 #-------------------------------------------------------------------------
1225 #-------------------------------------------------------------------------
1226 set testprefix rtreedoc-10
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}
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 }
1254 #-------------------------------------------------------------------------
1255 #-------------------------------------------------------------------------
1256 # Section 7.1 of documentation.
1257 #-------------------------------------------------------------------------
1258 #-------------------------------------------------------------------------
1259 set testprefix rtreedoc-11
1260 reset_db
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
1274 set nData [string length $aData]
1275 set nBytePerCell [expr (8 + 2*$nDim*4)]
1276 binary scan [string range $aData 2 3] S nCell
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 }
1286 return $res
1287 }
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 }
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]
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 }
1315 db function rnode rnode
1316 db function rnode_contains rnode_contains
1317 db function rnode_replace_cell rnode_replace_cell
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 "
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 "]
1349 do_execsql_test 1.$tn "DROP TABLE $nm"
1350 }
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
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}
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 } {}
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 }
1424 #-------------------------------------------------------------------------
1425 #-------------------------------------------------------------------------
1426 # Section 7.2 of documentation.
1427 #-------------------------------------------------------------------------
1428 #-------------------------------------------------------------------------
1429 set testprefix rtreedoc-12
1430 reset_db
1431 forcedelete test.db2
1433 db function rnode rnode
1434 db function rnode_contains rnode_contains
1435 db function rnode_replace_cell rnode_replace_cell
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;
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 }
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}}
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; }
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; }
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)}}
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 }
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
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
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
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
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
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
1593 finish_test