Debian Codegraph @

www/rtree.html

raw
1 <!DOCTYPE html>
2 <html><head>
3 <meta name="viewport" content="width=device-width, initial-scale=1.0">
4 <meta http-equiv="content-type" content="text/html; charset=UTF-8">
5 <link href="sqlite.css" rel="stylesheet">
6 <title>The SQLite R*Tree Module</title>
7 <!-- path= -->
8 </head>
9 <body>
10 <div class=nosearch>
11 <a href="index.html">
12 <img class="logo" src="images/sqlite370_banner.svg" alt="SQLite" border="0">
13 </a>
14 <div><!-- IE hack to prevent disappearing logo --></div>
15 <div class="tagline desktoponly">
16 Small. Fast. Reliable.<br>Choose any three.
17 </div>
18 <div class="menu mainmenu">
19 <ul>
20 <li><a href="index.html">Home</a>
21 <li class='mobileonly'><a href="javascript:void(0)" onclick='toggle_div("submenu")'>Menu</a>
22 <li class='wideonly'><a href='about.html'>About</a>
23 <li class='desktoponly'><a href="docs.html">Documentation</a>
24 <li class='desktoponly'><a href="download.html">Download</a>
25 <li class='wideonly'><a href='copyright.html'>License</a>
26 <li class='desktoponly'><a href="support.html">Support</a>
27 <li class='desktoponly'><a href="prosupport.html">Purchase</a>
28 <li class='search' id='search_menubutton'>
29 <a href="javascript:void(0)" onclick='toggle_search()'>Search</a>
30 </ul>
31 </div>
32 <div class="menu submenu" id="submenu">
33 <ul>
34 <li><a href='about.html'>About</a>
35 <li><a href='docs.html'>Documentation</a>
36 <li><a href='download.html'>Download</a>
37 <li><a href='support.html'>Support</a>
38 <li><a href='prosupport.html'>Purchase</a>
39 </ul>
40 </div>
41 <div class="searchmenu" id="searchmenu">
42 <form method="GET" action="search">
43 <select name="s" id="searchtype">
44 <option value="d">Search Documentation</option>
45 <option value="c">Search Changelog</option>
46 </select>
47 <input type="text" name="q" id="searchbox" value="">
48 <input type="submit" value="Go">
49 </form>
50 </div>
51 </div>
52 <script>
53 function toggle_div(nm) {
54 var w = document.getElementById(nm);
55 if( w.style.display=="block" ){
56 w.style.display = "none";
57 }else{
58 w.style.display = "block";
59 }
60 }
61 function toggle_search() {
62 var w = document.getElementById("searchmenu");
63 if( w.style.display=="block" ){
64 w.style.display = "none";
65 } else {
66 w.style.display = "block";
67 setTimeout(function(){
68 document.getElementById("searchbox").focus()
69 }, 30);
70 }
71 }
72 function div_off(nm){document.getElementById(nm).style.display="none";}
73 window.onbeforeunload = function(e){div_off("submenu");}
74 /* Disable the Search feature if we are not operating from CGI, since */
75 /* Search is accomplished using CGI and will not work without it. */
76 if( !location.origin || !location.origin.match || !location.origin.match(/http/) ){
77 document.getElementById("search_menubutton").style.display = "none";
78 }
79 /* Used by the Hide/Show button beside syntax diagrams, to toggle the */
80 function hideorshow(btn,obj){
81 var x = document.getElementById(obj);
82 var b = document.getElementById(btn);
83 if( x.style.display!='none' ){
84 x.style.display = 'none';
85 b.innerHTML='show';
86 }else{
87 x.style.display = '';
88 b.innerHTML='hide';
89 }
90 return false;
91 }
92 var antiRobot = 0;
93 function antiRobotGo(){
94 if( antiRobot!=3 ) return;
95 antiRobot = 7;
96 var j = document.getElementById("mtimelink");
97 if(j && j.hasAttribute("data-href")) j.href=j.getAttribute("data-href");
98 }
99 function antiRobotDefense(){
100 document.body.onmousedown=function(){
101 antiRobot |= 2;
102 antiRobotGo();
103 document.body.onmousedown=null;
104 }
105 document.body.onmousemove=function(){
106 antiRobot |= 2;
107 antiRobotGo();
108 document.body.onmousemove=null;
109 }
110 setTimeout(function(){
111 antiRobot |= 1;
112 antiRobotGo();
113 }, 100)
114 antiRobotGo();
115 }
116 antiRobotDefense();
117 </script>
118 <div class=fancy>
119 <div class=nosearch>
120 <div class="fancy_title">
121 The SQLite R*Tree Module
122 </div>
123 <details class="fancy_toc">
124 <summary>Table Of Contents</summary>
125 <div id="toc_sub"><div class="fancy-toc1"><a href="#overview">1. Overview</a></div>
126 <div class="fancy-toc1"><a href="#compiling_the_r_tree_module">2. Compiling The R*Tree Module</a></div>
127 <div class="fancy-toc1"><a href="#using_the_r_tree_module">3. Using the R*Tree Module</a></div>
128 <div class="fancy-toc2"><a href="#creating_an_r_tree_index">3.1. Creating An R*Tree Index</a></div>
129 <div class="fancy-toc3"><a href="#column_naming_details">3.1.1. Column naming details</a></div>
130 <div class="fancy-toc2"><a href="#populating_an_r_tree_index">3.2. Populating An R*Tree Index</a></div>
131 <div class="fancy-toc2"><a href="#querying_an_r_tree_index">3.3. Querying An R*Tree Index</a></div>
132 <div class="fancy-toc2"><a href="#roundoff_error">3.4. Roundoff Error</a></div>
133 <div class="fancy-toc2"><a href="#reading_and_writing_at_the_same_time">3.5. Reading And Writing At The Same Time</a></div>
134 <div class="fancy-toc1"><a href="#using_r_trees_effectively">4. Using R*Trees Effectively</a></div>
135 <div class="fancy-toc2"><a href="#auxiliary_columns">4.1. Auxiliary Columns</a></div>
136 <div class="fancy-toc3"><a href="#limitations">4.1.1. Limitations</a></div>
137 <div class="fancy-toc1"><a href="#integer_valued_r_trees">5. Integer-Valued R-Trees</a></div>
138 <div class="fancy-toc1"><a href="#custom_r_tree_queries">6. Custom R-Tree Queries</a></div>
139 <div class="fancy-toc2"><a href="#the_legacy_xgeom_callback">6.1. The Legacy xGeom Callback</a></div>
140 <div class="fancy-toc2"><a href="#the_new_xqueryfunc_callback">6.2. The New xQueryFunc Callback</a></div>
141 <div class="fancy-toc2"><a href="#additional_considerations_for_custom_queries">6.3. Additional Considerations for Custom Queries</a></div>
142 <div class="fancy-toc1"><a href="#implementation_details">7. Implementation Details</a></div>
143 <div class="fancy-toc2"><a href="#shadow_tables">7.1. Shadow Tables</a></div>
144 <div class="fancy-toc2"><a href="#integrity_check_using_the_rtreecheck_sql_function">7.2. Integrity Check using the rtreecheck() SQL function</a></div>
145 </div>
146 </details>
147 </div>
148
149
150
151
152 <h1 id="overview"><span>1. </span>Overview</h1>
153
154 <p>
155 An <a href="http://en.wikipedia.org/wiki/R-tree">R-Tree</a> is a special
156 index that is designed for doing range queries. R-Trees are most commonly
157 used in geospatial systems where each entry is a rectangle with minimum and
158 maximum X and Y coordinates. Given a query rectangle, an R-Tree is able
159 to quickly find all entries that are contained within the query rectangle
160 or which overlap the query rectangle. This idea is easily extended to
161 three dimensions for use in CAD systems. R-Trees also find use in time-domain
162 range look-ups. For example, suppose a database records the starting and
163 ending times for a large number of events. A R-Tree is able to quickly
164 find all events that were active at any time during a given
165 time interval, or all events that started during a particular time interval,
166 or all events that both started and ended within a given time interval.
167 And so forth.
168 </p>
169
170 <p>
171 The R-Tree concept originated with
172 <a href="https://link.springer.com/referenceworkentry/10.1007/978-0-387-35973-1_1151">Toni Guttman</a>:
173 <em>R-Trees: A Dynamic Index Structure for Spatial Searching</em>,
174 Proc. 1984 ACM SIGMOD International Conference on Management of Data,
175 pp. 47-57.
176 The implementation found in SQLite is a refinement of Guttman's original
177 idea, commonly called "R*Trees", that was described by
178 Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger:
179 <em>The R*-Tree: An Efficient and Robust Access Method for Points
180 and Rectangles.</em> SIGMOD Conference 1990: 322-331.
181 </p>
182
183 <h1 id="compiling_the_r_tree_module"><span>2. </span>Compiling The R*Tree Module</h1>
184
185 <p>
186 The source code to the SQLite R*Tree module is included as part
187 of the <a href="amalgamation.html">amalgamation</a>. However, depending on configuration options
188 and the particular version of SQLite you are using, it may or may not
189 be enabled by default. To ensure that the R*Tree module is enabled,
190 simply compile with the <a href="compile.html#enable_rtree">SQLITE_ENABLE_RTREE</a>
191 C-preprocessor macro defined. With many compilers, this is accomplished
192 by adding the option "-DSQLITE_ENABLE_RTREE=1" to the compiler
193 command-line.
194 </p>
195
196 <h1 id="using_the_r_tree_module"><span>3. </span>Using the R*Tree Module</h1>
197
198 <p>
199 The SQLite R*Tree module is implemented as a
200 <a href="c3ref/create_module.html">virtual table</a>. Each R*Tree index is a
201 virtual table with an odd number of columns between 3 and 11.
202 The first column is always a 64-bit signed integer primary key.
203 The other columns are pairs, one pair per dimension, containing the
204 minimum and maximum values for that dimension, respectively.
205 A 1-dimensional R*Tree thus has 3 columns.
206 A 2-dimensional R*Tree has 5 columns.
207 A 3-dimensional R*Tree has 7 columns.
208 A 4-dimensional R*Tree has 9 columns.
209 And a 5-dimensional R*Tree has 11 columns. The SQLite R*Tree implementation
210 does not support R*Trees wider than 5 dimensions.
211 </p>
212
213 <p>
214 The first column of an SQLite R*Tree is similar to an integer primary
215 key column of a normal SQLite table. It may only store a 64-bit signed
216 integer value. Inserting a NULL value into this column causes SQLite
217 to automatically generate a new unique primary key value. If an attempt
218 is made to insert any other non-integer value into this column,
219 the r-tree module silently converts it to an integer before writing it
220 into the database.
221 </p><p>
222 The min/max-value pair columns are stored as 32-bit floating point values for
223 "rtree" virtual tables or as 32-bit signed integers in "rtree_i32" virtual
224 tables. Unlike regular SQLite tables which can store data in a variety of
225 datatypes and formats, the R*Tree rigidly enforce these storage types.
226 If any other type of value is inserted into such a column, the r-tree
227 module silently converts it to the required type before writing the
228 new record to the database.
229
230 </p><h2 id="creating_an_r_tree_index"><span>3.1. </span>Creating An R*Tree Index</h2>
231
232 <p>
233 A new R*Tree index is created as follows:
234 </p>
235
236 <div class="codeblock"><pre>CREATE VIRTUAL TABLE <em>&lt;name&gt;</em> USING rtree(<em>&lt;column-names&gt;</em>);
237 </pre></div>
238
239 <p>
240 The <em>&lt;name&gt;</em> is the name your application chooses for the
241 R*Tree index and <em>&lt;column-names&gt;</em> is a comma separated list
242 of between 3 and 11 columns.
243 The virtual &lt;name&gt; table creates three <a href="vtab.html#xshadowname">shadow tables</a> to actually
244 store its content. The names of these shadow tables are:
245 </p>
246
247 <div class="codeblock"><pre><em>&lt;name&gt;</em><strong>_node</strong><br>
248 <em>&lt;name&gt;</em><strong>_rowid</strong><br>
249 <em>&lt;name&gt;</em><strong>_parent</strong>
250 </pre></div>
251
252
253 <p>
254 The shadow tables are ordinary SQLite data tables. You can query them
255 directly if you like, though this unlikely to reveal anything particularly
256 useful.
257 And you can <a href="lang_update.html">UPDATE</a>, <a href="lang_delete.html">DELETE</a>, <a href="lang_insert.html">INSERT</a> or even <a href="lang_droptable.html">DROP</a>
258 the shadow tables, though doing so will corrupt your R*Tree index.
259 So it is best to simply ignore the shadow tables. Recognize that they
260 hold your R*Tree index information and let it go as that.
261 </p>
262
263 <p>
264 As an example, consider creating a two-dimensional R*Tree index for use in
265 spatial queries:
266 </p>
267
268 <div class="codeblock"><pre>CREATE VIRTUAL TABLE demo_index USING rtree(
269 id, -- Integer primary key
270 minX, maxX, -- Minimum and maximum X coordinate
271 minY, maxY -- Minimum and maximum Y coordinate
272 );
273 </pre></div>
274
275
276 <h3 id="column_naming_details"><span>3.1.1. </span>Column naming details</h3>
277
278 <p>
279 In the argments to "rtree" in the CREATE VIRTUAL TABLE statement, the
280 names of the columns are taken from the first token of each argument.
281 All subsequent tokens within each argument are silently ignored.
282 This means, for example, that if you try to give a column a
283 <a href="datatype3.html#affinity">type affinity</a> or add a constraint such as UNIQUE or NOT NULL or DEFAULT to
284 a column, those extra tokens are accepted as valid, but they do not change
285 the behavior of the rtree.
286 In an RTREE virtual table, the first column always has a
287 <a href="datatype3.html#affinity">type affinity</a> of INTEGER and all other data columns have a
288 <a href="datatype3.html#affinity">type affinity</a> of REAL.
289 In an RTREE_I32 virtual table, all columns have type affinity of INTEGER.
290
291 </p><p>
292 Recommended practice is to omit any extra tokens in the rtree specification.
293 Let each argument to "rtree" be a single ordinary label that is the name of
294 the corresponding column, and omit all other tokens from the argument list.
295
296 </p><h2 id="populating_an_r_tree_index"><span>3.2. </span>Populating An R*Tree Index</h2>
297
298 <p>
299 The usual <a href="lang_insert.html">INSERT</a>, <a href="lang_update.html">UPDATE</a>, and <a href="lang_delete.html">DELETE</a> commands work on an R*Tree
300 index just like on regular tables. So to insert some data into our sample
301 R*Tree index, we can do something like this:
302 </p>
303
304 <div class="codeblock"><pre>INSERT INTO demo_index VALUES
305 (28215, -80.781227, -80.604706, 35.208813, 35.297367),
306 (28216, -80.957283, -80.840599, 35.235920, 35.367825),
307 (28217, -80.960869, -80.869431, 35.133682, 35.208233),
308 (28226, -80.878983, -80.778275, 35.060287, 35.154446),
309 (28227, -80.745544, -80.555382, 35.130215, 35.236916),
310 (28244, -80.844208, -80.841988, 35.223728, 35.225471),
311 (28262, -80.809074, -80.682938, 35.276207, 35.377747),
312 (28269, -80.851471, -80.735718, 35.272560, 35.407925),
313 (28270, -80.794983, -80.728966, 35.059872, 35.161823),
314 (28273, -80.994766, -80.875259, 35.074734, 35.172836),
315 (28277, -80.876793, -80.767586, 35.001709, 35.101063),
316 (28278, -81.058029, -80.956375, 35.044701, 35.223812),
317 (28280, -80.844208, -80.841972, 35.225468, 35.227203),
318 (28282, -80.846382, -80.844193, 35.223972, 35.225655);
319 </pre></div>
320
321
322 <p>
323 The entries above are bounding boxes (longitude and latitude) for 14
324 zipcodes near Charlotte, NC. A real database would have many thousands,
325 millions, or billions of such entries, but this small 14-row sample will
326 be sufficient to illustrate the ideas.
327 </p>
328
329 <h2 id="querying_an_r_tree_index"><span>3.3. </span>Querying An R*Tree Index</h2>
330
331 <p>
332 Any valid query will work against an R*Tree index. The R*Tree
333 implementation just makes some kinds of queries especially
334 efficient. Queries against the primary key are efficient:
335 </p>
336
337 <div class="codeblock"><pre>SELECT * FROM demo_index WHERE id=28269;
338 </pre></div>
339
340
341 <p>
342 Of course, an ordinary SQLite table will also do a query against its
343 integer primary key efficiently, so the previous is not important.
344 The big reason for using an R*Tree is so that
345 you can efficiently do range queries against the coordinate
346 ranges. For example, the main office of the SQLite project is
347 located at 35.37785, -80.77470.
348 To find which zipcodes might service that office, one could write:
349 </p>
350
351 <div class="codeblock"><pre>SELECT id FROM demo_index
352 WHERE minX&lt;=-80.77470 AND maxX&gt;=-80.77470
353 AND minY&lt;=35.37785 AND maxY&gt;=35.37785;
354 </pre></div>
355
356
357 <p>
358 The query above will quickly locate all zipcodes that contain
359 the SQLite main office in their bounding box, even if the
360 R*Tree contains many entries. The previous is an example
361 of a "contained-within" query. The R*Tree also supports "overlapping"
362 queries. For example, to find all zipcode bounding boxes that overlap
363 with the 28269 zipcode:
364 </p>
365
366 <div class="codeblock"><pre>SELECT A.id FROM demo_index AS A, demo_index AS B
367 WHERE A.maxX&gt;=B.minX AND A.minX&lt;=B.maxX
368 AND A.maxY&gt;=B.minY AND A.minY&lt;=B.maxY
369 AND B.id=28269;
370 </pre></div>
371
372
373 <p>
374 This second query will find both the 28269 entry (since every bounding box
375 overlaps with itself) and also any other zipcodes that are close enough to
376 28269 that their bounding boxes overlap.
377 </p>
378
379 <p>
380 Note that it is not necessary for all coordinates in an R*Tree index
381 to be constrained in order for the index search to be efficient.
382 One might, for example, want to query all objects that overlap with
383 the 35th parallel:
384 </p>
385
386 <div class="codeblock"><pre>SELECT id FROM demo_index
387 WHERE maxY&gt;=35.0 AND minY&lt;=35.0;
388 </pre></div>
389
390
391 <p>
392 But, generally speaking, the more constraints that the R*Tree module
393 has to work with, and the smaller the bounding box, the faster the
394 results will come back.
395 </p>
396
397 <h2 id="roundoff_error"><span>3.4. </span>Roundoff Error</h2>
398
399 <p>
400 By default, coordinates are stored in an R*Tree using 32-bit floating
401 point values. When a coordinate cannot be exactly represented by a
402 32-bit floating point number, the lower-bound coordinates are rounded down
403 and the upper-bound coordinates are rounded up. Thus, bounding boxes might
404 be slightly larger than specified, but will never be any smaller. This
405 is exactly what is desired for doing the more common "overlapping" queries
406 where the application wants to find every entry in the R*Tree that overlaps
407 a query bounding box. Rounding the entry bounding boxes outward might cause a
408 few extra entries to appear in an overlapping query if the edge of the
409 entry bounding box corresponds to an edge of the query bounding box. But
410 the overlapping query will never miss a valid table entry.
411
412 </p><p>However, for a "contained-within" style query, rounding the bounding
413 boxes outward might cause some entries to be excluded from the result set
414 if the edge of the entry bounding box corresponds to the edge of the query
415 bounding box. To guard against this, applications should expand their
416 contained-within query boxes slightly (by 0.000012%) by rounding down the
417 lower coordinates and rounding up the top coordinates, in each dimension.
418
419 <a name="readwrite"></a>
420
421 </p><h2 id="reading_and_writing_at_the_same_time"><span>3.5. </span>Reading And Writing At The Same Time</h2>
422
423 <p>
424 It is the nature of the Guttman R-Tree algorithm that any write might
425 radically restructure the tree, and in the process change the scan order
426 of the nodes. For this reason, it is not generally possible to modify
427 the R-Tree in the middle of a query of the R-Tree. Attempts to do so
428 will fail with a <a href="rescode.html#locked">SQLITE_LOCKED</a> "database table is locked" error.
429
430 </p><p>
431 So, for example, suppose an application runs one query against an R-Tree like
432 this:
433
434 </p><div class="codeblock"><pre>SELECT id FROM demo_index
435 WHERE maxY&gt;=35.0 AND minY&lt;=35.0;
436 </pre></div>
437
438 <p>
439 Then for each "id" value returned, suppose the application creates an
440 UPDATE statement like the following and binds the "id" value returned against
441 the "?1" parameter:
442
443 </p><div class="codeblock"><pre>UPDATE demo_index SET maxY=maxY+0.5 WHERE id=?1;
444 </pre></div>
445
446 <p>
447 Then the UPDATE might fail with an SQLITE_LOCKED error. The reason is that
448 the initial query has not run to completion. It is remembering its place
449 in the middle of a scan of the R-Tree. So an update to the R-Tree cannot
450 be tolerated as this would disrupt the scan.
451
452 </p><p>
453 This is a limitation of the R-Tree extension only. Ordinary tables in
454 SQLite are able to read and write at the same time. Other virtual tables
455 might (or might not) also have that capability. And R-Tree can appear to read
456 and write at the same time in some circumstances, if it can figure out how
457 to reliably run the query to completion before starting the update. But
458 you shouldn't count on that for every query. Generally speaking, it is
459 best to avoid running queries and updates to the same R-Tree at the same
460 time.
461
462 </p><p>
463 If you really need to update an R-Tree based on complex queries against
464 the same R-Tree, it is best to run the complex queries first and store
465 the results in a temporary table, then update the R-Tree based on the values
466 stored in the temporary table.
467
468 </p><h1 id="using_r_trees_effectively"><span>4. </span>Using R*Trees Effectively</h1>
469
470 <p>
471 For SQLite versions prior to 3.24.0 (2018-06-04),
472 the only information that an R*Tree index stores about an object is
473 its integer ID and its bounding box. Additional information needs to
474 be stored in separate tables and related to the R*Tree index using
475 the primary key. For the example above, one might create an auxiliary
476 table as follows:
477 </p>
478
479 <div class="codeblock"><pre>CREATE TABLE demo_data(
480 id INTEGER PRIMARY KEY, -- primary key
481 objname TEXT, -- name of the object
482 objtype TEXT, -- object type
483 boundary BLOB -- detailed boundary of object
484 );
485 </pre></div>
486
487 <p>
488 In this example, the demo_data.boundary field is intended to hold some
489 kind of binary representation of the precise boundaries of the object.
490 The R*Tree index only holds an axis-aligned rectangular boundary for the
491 object. The R*Tree boundary is just an approximation of the true object
492 boundary. So what typically happens is that the R*Tree index is used to
493 narrow a search down to a list of candidate objects and then more detailed
494 and expensive computations are done on each candidate to find if the
495 candidate truly meets the search criteria.
496 </p>
497
498 <blockquote><p>
499 <strong>Key Point:</strong>
500 An R*Tree index does not normally provide the exact answer but merely
501 reduces the set of potential answers from millions to dozens.
502 </p></blockquote>
503
504 <p>
505 Suppose the demo_data.boundary field holds some proprietary data description
506 of a complex two-dimensional boundary for a zipcode and suppose that the
507 application has used the <a href="c3ref/create_function.html">sqlite3_create_function()</a> interface to
508 created an application-defined function "contained_in(boundary,lat,long)"
509 that accepts the demo_data.boundary object and a latitute and longitude
510 and returns return true or false if the lat/long is contained within
511 the boundary.
512 One may assume that "contained_in()" is a relatively slow
513 functions that we do not want to invoke too frequently.
514 Then an efficient way to find the specific ZIP code for the main
515 SQLite office would be to run a query like this:
516 </p>
517
518 <a name="diquery"></a>
519 <div class="codeblock"><pre>SELECT objname FROM demo_data, demo_index
520 WHERE demo_data.id=demo_index.id
521 AND contained_in(demo_data.boundary, 35.37785, -80.77470)
522 AND minX&lt;=-80.77470 AND maxX&gt;=-80.77470
523 AND minY&lt;=35.37785 AND maxY&gt;=35.37785;
524 </pre></div>
525
526 <p>Notice how the query above works: The R*Tree index runs in the outer
527 loop to find entries that contain the SQLite main office in their
528 boundary box.
529 For each row found, SQLite looks up
530 the corresponding entry in the demo_data table. It then uses the boundary
531 field from the demo_data table as a parameter to the contained_in()
532 function and if that function returns true, then we know the sought after
533 coordinate is in that ZIP code boundary.</p>
534
535 <p>One would get the same answer without the use of the R*Tree index
536 using the following simpler query:</p>
537
538 <div class="codeblock"><pre>SELECT objname FROM demo_data
539 WHERE contained_in(demo_data.boundary, 35.37785, -80.77470);
540 </pre></div>
541
542 <p>The problem with this latter query is that it must apply the
543 contained_in() function to all entries in the demo_data table.
544 The use of the R*Tree in the penultimate query reduces the number of
545 calls to contained_in() function to a small subset of the entire table.
546 The R*Tree index did not find the exact answer itself, it merely
547 limited the search space.</p>
548
549 <a name="auxcol"></a>
550
551 <h2 id="auxiliary_columns"><span>4.1. </span>Auxiliary Columns</h2>
552
553 <p>
554 Beginning with SQLite version 3.24.0 (2018-06-04), r-tree tables
555 can have auxiliary columns that store arbitrary data.
556 Auxiliary columns can be used in place of
557 secondary tables such as "demo_data".
558
559 </p><p>
560 Auxiliary columns are marked with a "+" symbol before the column name.
561 Auxiliary columns must come after all of the coordinate boundary columns.
562 An RTREE table can have no more than 100 columns total. In other words,
563 the count of columns including the integer primary key column,
564 the coordinate boundary columns, and all auxiliary columns must be 100 or less.
565 The following example shows an r-tree table with auxiliary columns that
566 is equivalent to the two tables "demo_index" and "demo_data" above:
567
568 </p><div class="codeblock"><pre>CREATE VIRTUAL TABLE demo_index2 USING rtree(
569 id, -- Integer primary key
570 minX, maxX, -- Minimum and maximum X coordinate
571 minY, maxY, -- Minimum and maximum Y coordinate
572 +objname TEXT, -- name of the object
573 +objtype TEXT, -- object type
574 +boundary BLOB -- detailed boundary of object
575 );
576 </pre></div>
577
578 <p>
579 By combining location data and related information into the same
580 table, auxiliary columns can provide a cleaner model
581 and reduce the need for joins.
582 For example, the earlier
583 <a href="#diquery">join between demo_index and demo_data</a> can now
584 be written as a simple query, like this:
585
586 </p><div class="codeblock"><pre>SELECT objname FROM demo_index2
587 WHERE contained_in(boundary, 35.37785, -80.77470)
588 AND minX&lt;=-80.77470 AND maxX&gt;=-80.77470
589 AND minY&lt;=35.37785 AND maxY&gt;=35.37785;
590 </pre></div>
591
592 <h3 id="limitations"><span>4.1.1. </span>Limitations</h3>
593
594 <p>
595 For auxiliary columns, only the name of the column matters.
596 The <a href="datatype3.html#affinity">type affinity</a> is ignored.
597 Constraints such as NOT NULL, UNIQUE, REFERENCES, or CHECK
598 are also ignored. However, future versions
599 of SQLite might start paying attention to the type affinity and
600 constraints, so users of auxiliary columns are advised to leave
601 both blank, to avoid future compatibility problems.
602
603 <a name="intrtree"></a>
604
605 </p><h1 id="integer_valued_r_trees"><span>5. </span>Integer-Valued R-Trees</h1>
606
607 <p>
608 The default virtual table ("rtree") stores coordinates as
609 single-precision (4-byte) floating point numbers. If integer coordinates
610 are desired, declare the table using "rtree_i32" instead:
611
612 </p><div class="codeblock"><pre>CREATE VIRTUAL TABLE intrtree USING rtree_i32(id,x0,x1,y0,y1,z0,z1);
613 </pre></div>
614
615 <p>
616 An rtree_i32 stores coordinates as 32-bit signed integers.
617 Even though it stores values using integers, the rtree_i32 virtual
618 table still uses floating point computations internally as part of
619 the r-tree algorithm.
620
621 <a name="customquery"></a>
622
623 </p><h1 id="custom_r_tree_queries"><span>6. </span>Custom R-Tree Queries</h1>
624
625 <p>By using standard SQL expressions in the WHERE clause of a SELECT query,
626 a programmer can query for all R*Tree entries that
627 intersect with or are contained within a particular bounding-box.
628 Custom R*Tree queries, using the MATCH
629 operator in the WHERE clause of a SELECT, allow the programmer to query for
630 the set of R*Tree entries that intersect any arbitrary region or shape, not
631 just a box. This capability is useful, for example, in computing the
632 subset of objects in the R*Tree that are visible from a camera positioned
633 in 3-D space.
634
635 </p><p>Regions for custom R*Tree queries are defined by R*Tree geometry callbacks
636 implemented by the application and registered with SQLite via a call to one
637 of the following two APIs:
638
639 </p><div class="codeblock"><pre>int sqlite3_rtree_query_callback(
640 sqlite3 *db,
641 const char *zQueryFunc,
642 int (*xQueryFunc)(sqlite3_rtree_query_info*),
643 void *pContext,
644 void (*xDestructor)(void*)
645 );
646 int sqlite3_rtree_geometry_callback(
647 sqlite3 *db,
648 const char *zGeom,
649 int (*xGeom)(sqlite3_rtree_geometry *, int nCoord, double *aCoord, int *pRes),
650 void *pContext
651 );
652 </pre></div>
653
654 <p>The sqlite3_rtree_query_callback() became available with SQLite
655 <a href="releaselog/3_8_5.html">version 3.8.5</a> (2014-06-04) and is the preferred interface.
656 The sqlite3_rtree_geometry_callback() is an older and less flexible
657 interface that is supported for backwards compatibility.
658
659 </p><p>A call to one of the above APIs creates a new SQL function named by the
660 second parameter (zQueryFunc or zGeom). When that SQL function appears
661 on the right-hand side of the MATCH operator and the left-hand side of the
662 MATCH operator is any column in the R*Tree virtual table, then the callback
663 defined by the third argument (xQueryFunc or xGeom) is invoked to determine
664 if a particular object or subtree overlaps the desired region.
665
666 </p><p>For example, a query like the following might be used to find all
667 R*Tree entries that overlap with a circle centered at 45.3,22.9 with a
668 radius of 5.0:
669
670 </p><div class="codeblock"><pre>SELECT id FROM demo_index WHERE id MATCH circle(45.3, 22.9, 5.0)
671 </pre></div>
672
673 <p>The SQL syntax for custom queries is the same regardless of which
674 interface, sqlite3_rtree_geometry_callback() or sqlite3_rtree_query_callback(),
675 is used to register the SQL function. However, the newer query-style
676 callbacks give the application greater control over how the query proceeds.
677
678 </p><h2 id="the_legacy_xgeom_callback"><span>6.1. </span>The Legacy xGeom Callback</h2>
679
680 <p>The legacy xGeom callback is invoked with four arguments. The first
681 argument is a pointer to an sqlite3_rtree_geometry structure which provides
682 information about how the SQL function was invoked. The second argument
683 is the number of coordinates in each r-tree entry, and is always the same
684 for any given R*Tree. The number of coordinates is 2 for a 1-dimensional R*Tree,
685 4 for a 2-dimensional R*Tree, 6 for a 3-dimensional R*Tree, and so forth.
686 The third argument, aCoord[], is an array of nCoord coordinates that defines
687 a bounding box to be tested. The last argument is a pointer into which
688 the callback result should be written. The result is zero
689 if the bounding-box defined by aCoord[] is completely outside
690 the region defined by the xGeom callback and the result is non-zero if
691 the bounding-box is inside or overlaps with the xGeom region. The xGeom
692 callback should normally return SQLITE_OK. If xGeom returns anything other
693 than SQLITE_OK, then the r-tree query will abort with an error.
694
695 </p><p>The sqlite3_rtree_geometry structure that the first argument to the
696 xGeom callback points to has a structure shown below. The exact same
697 sqlite3_rtree_geometry
698 structure is used for every callback for same MATCH operator in the same
699 query. The contents of the sqlite3_rtree_geometry
700 structure are initialized by SQLite but are
701 not subsequently modified. The callback is free to make changes to the
702 pUser and xDelUser elements of the structure if desired.
703
704 </p><div class="codeblock"><pre>typedef struct sqlite3_rtree_geometry sqlite3_rtree_geometry;
705 struct sqlite3_rtree_geometry {
706 void *pContext; /* Copy of pContext passed to s_r_g_c() */
707 int nParam; /* Size of array aParam */
708 double *aParam; /* Parameters passed to SQL geom function */
709 void *pUser; /* Callback implementation user data */
710 void (*xDelUser)(void *); /* Called by SQLite to clean up pUser */
711 };
712 </pre></div>
713
714 <p>The pContext member of the sqlite3_rtree_geometry
715 structure is always set to a copy of the pContext
716 argument passed to sqlite3_rtree_geometry_callback() when the
717 callback is registered. The aParam[] array (size nParam) contains the parameter
718 values passed to the SQL function on the right-hand side of the MATCH operator.
719 In the example "circle" query above, nParam would be set to 3 and the aParam[]
720 array would contain the three values 45.3, 22.9 and 5.0.
721
722 </p><p>The pUser and xDelUser members of the sqlite3_rtree_geometry structure are
723 initially set to NULL. The pUser variable may be set by the callback
724 implementation to any arbitrary value that may be useful to subsequent
725 invocations of the callback within the same query (for example, a
726 pointer to a complicated data structure used to test for region intersection).
727 If the xDelUser variable is set to a non-NULL value, then after the
728 query has finished running SQLite automatically invokes it with the
729 value of the pUser variable as the only argument. In other words, xDelUser
730 may be set to a destructor function for the pUser value.
731
732 </p><p>The xGeom callback always does a depth-first search of the r-tree.
733
734 <a name="xquery"></a>
735
736 </p><h2 id="the_new_xqueryfunc_callback"><span>6.2. </span>The New xQueryFunc Callback</h2>
737
738 <p>The newer xQueryFunc callback receives more information from the r-tree
739 query engine on each call, and it sends more information back to the query engine
740 before it returns.
741 To help keep the interface manageable, the xQueryFunc callback sends and receives
742 information from the query engine as fields in the
743 sqlite3_rtree_query_info structure:
744
745 </p><div class="codeblock"><pre>struct sqlite3_rtree_query_info {
746 void *pContext; /* pContext from when function registered */
747 int nParam; /* Number of function parameters */
748 sqlite3_rtree_dbl *aParam; /* value of function parameters */
749 void *pUser; /* callback can use this, if desired */
750 void (*xDelUser)(void*); /* function to free pUser */
751 sqlite3_rtree_dbl *aCoord; /* Coordinates of node or entry to check */
752 unsigned int *anQueue; /* Number of pending entries in the queue */
753 int nCoord; /* Number of coordinates */
754 int iLevel; /* Level of current node or entry */
755 int mxLevel; /* The largest iLevel value in the tree */
756 sqlite3_int64 iRowid; /* Rowid for current entry */
757 sqlite3_rtree_dbl rParentScore; /* Score of parent node */
758 int eParentWithin; /* Visibility of parent node */
759 int eWithin; /* OUT: Visiblity */
760 sqlite3_rtree_dbl rScore; /* OUT: Write the score here */
761 /* The following fields are only available in 3.8.11 and later */
762 sqlite3_value **apSqlParam; /* Original SQL values of parameters */
763 };
764 </pre></div>
765
766 <p>The first five fields of the sqlite3_rtree_query_info structure are identical
767 to the sqlite3_rtree_geometry structure, and have exactly the same meaning.
768 The sqlite3_rtree_query_info structure also contains nCoord and aCoord fields
769 which have the same meaning as the parameter of the same name in the xGeom callback.
770
771 </p><p>The xQueryFunc must set the eWithin field of sqlite3_rtree_query_info to
772 one of the values NOT_WITHIN, PARTLY_WITHIN, or FULLY_WITHIN depending on whether
773 or not the bounding box defined by aCoord[] is completely outside the region,
774 overlaps the region, or is completely inside the region, respectively. In
775 addition, the xQueryFunc must set the rScore field to a non-negative value that
776 indicates the order in which subtrees and entries of the query should be analyzed
777 and returned. Smaller scores are processed first.
778
779 </p><p>As its name implies, an R*Tree is organized as a tree. Each node of the
780 tree is a bounding box. The root of the tree is a bounding box that encapsulates
781 all elements of the tree. Beneath the root are a number of subtrees (typically
782 20 or more) each with their own smaller bounding boxes and each containing some
783 subset of the R*Tree entries. The subtrees may have sub-subtrees, and so forth
784 until finally one reaches the leaves of the tree which are the actual R*Tree
785 entries.
786
787 </p><p>An R*Tree query is initialized by making the root node the only entry
788 in a priority queue sorted by rScore.
789 The query proceeds by extracting the entry from the priority queue that has
790 the lowest score. If that entry is a leaf (meaning that it is an actual
791 R*Tree entry and not a subtree) then that entry
792 is returned as one row of the query result.
793 If the extracted priority queue entry is a node (a subtree),
794 then the next child of that node is passed to the xQueryFunc callback.
795 If the node has more children then it is returned to the priority queue.
796 Otherwise it is discarded. Those subelements for which the xQueryFunc
797 callback sets eWithin to PARTLY_WITHIN or FULLY_WITHIN are added to the
798 priority queue using the score supplied by the callback. Subelements that
799 return NOT_WITHIN are discarded. The query runs until the priority queue is
800 empty.
801
802 </p><p>Every leaf entry and node (subtree) within the R*Tree has an integer "level".
803 The leaves have a level of 0. The first containing subtree of the leaves has
804 a level of 1. The root of the R*Tree has the largest level value. The
805 mxLevel entry in the sqlite3_rtree_query_info structure is the level value for
806 the root of the R*Tree. The iLevel entry in sqlite3_rtree_query_info gives the
807 level for the object being interrogated.
808
809 </p><p>Most R*Tree queries use a depth-first search. This is accomplished by setting
810 the rScore equal to iLevel. A depth-first search is usually preferred since it
811 minimizes the number of elements in the priority queue, which reduces memory
812 requirements and speeds processing. However, some applications may prefer a
813 breadth-first search, which can be accomplished by setting rScore to mxLevel-iLevel.
814 By creating more complex formulas for rScore, applications can exercise
815 detailed control over the order in which subtrees are searched and leaf
816 R*Tree entries are returned. For example, in an application with many
817 millions of R*Tree entries, the rScore might be arranged so that the
818 largest or most significant entries are returned first, allowing the
819 application to display the most important information quickly, and
820 filling in smaller and less important details as they become available.
821
822 </p><p>Other information fields of the sqlite3_rtree_query_info structure are
823 available for use by the xQueryFunc callback, if desired. The iRowid field
824 is the rowid (the first of the 3 to 11 columns in the R*Tree) for the element
825 being considered. iRowid is only valid for leaves. The eParentWithin and
826 rParentScore values are copies of the eWithin and rScore values from the
827 containing subtree of the current row. The anQueue field is an array
828 of mxLevel+1 unsigned integers that tell the current number of elements in
829 the priority queue at each level.
830
831 </p><h2 id="additional_considerations_for_custom_queries"><span>6.3. </span>Additional Considerations for Custom Queries</h2>
832
833 <p>
834 The MATCH operator of a custom R*Tree query function must be a top-level
835 AND-connected term of the WHERE clause, or else it will not be usable
836 by the R*Tree query optimizer and the query will not be runnable.
837 If the MATCH operator is connected to other terms of the WHERE clause
838 via an OR operator, for example, the query will fail with an error.
839
840 </p><p>
841 Two or more MATCH operators are allowed in the same WHERE clause, as long
842 as they are connected by AND operators. However,
843 the R*Tree query engine only contains a single priority queue. The priority
844 assigned to each node in the search is the lowest priority returned by any
845 of the MATCH operators.
846
847 </p><h1 id="implementation_details"><span>7. </span>Implementation Details</h1>
848
849 <p>
850 The following sections describe some low-level details of the R*Tree implementation,
851 that might be useful for trouble-shooting or performance analysis.
852
853 <a name="xshadow"></a>
854
855 </p><h2 id="shadow_tables"><span>7.1. </span>Shadow Tables</h2>
856
857 <p>The content of an R*Tree index is actually stored in three ordinary
858 SQLite tables with names derived from the name of the R*Tree. These
859 three tables are called "<a href="vtab.html#xshadowname">shadow tables</a>". This is their schema:
860
861 </p><div class="codeblock"><pre>CREATE TABLE %_node(nodeno INTEGER PRIMARY KEY, data)
862 CREATE TABLE %_parent(nodeno INTEGER PRIMARY KEY, parentnode)
863 CREATE TABLE %_rowid(rowid INTEGER PRIMARY KEY, nodeno)
864 </pre></div>
865
866 <p>The "%" in the name of each shadow table is replaced by the name of the
867 R*Tree virtual table. So, if the name of the R*Tree table is "xyz" then
868 the three shadow tables would be "xyz_node", "xyz_parent", and "xyz_rowid".
869
870 </p><p>There is one entry in the %_node table for each R*Tree node. An
871 R*Tree node consists of one or more entries that are proximate to one another.
872 The nodes of an R*Tree for a tree. All nodes other than the root have an
873 entry in the %_parent shadow table that identifies the parent node.
874 Each entry in an R*Tree has a rowid. The %_rowid shadow table maps entry
875 rowids to the node that contains that entry.
876
877 </p><p>Extra columns appended to the %_rowid table hold the
878 content of <a href="rtree.html#auxcol">auxiliary columns</a>. The names of these extra
879 %_rowid columns are probably not the same as the
880 actual auxiliary column names.
881
882 <a name="rtreecheck"></a>
883
884 </p><h2 id="integrity_check_using_the_rtreecheck_sql_function"><span>7.2. </span>Integrity Check using the rtreecheck() SQL function</h2>
885
886 <p>The scalar SQL function rtreecheck(R) or rtreecheck(S,R) runs an
887 integrity check on the rtree table named R contained within database S.
888 The function returns a human-language description of any problems found,
889 or the string 'ok' if everything is ok. Running rtreecheck() on an R*Tree
890 virtual table is similar to running <a href="pragma.html#pragma_integrity_check">PRAGMA integrity_check</a> on a
891 database.
892
893 </p><p>Example: To verify that an R*Tree named "demo_index" is well-formed
894 and internally consistent, run:
895
896 </p><div class="codeblock"><pre>SELECT rtreecheck('demo_index');
897 </pre></div>
898
899 <p>The rtreecheck() function performs the following checks:
900
901 </p><ol>
902 <li><p>
903 For each cell in the r-tree structure (%_node table), that:
904 </p><ol type="a">
905 <li><p> for each dimension, (coord1 &lt;= coord2).
906 </p></li><li><p> unless the cell is on the root node, that the cell is bounded
907 by the parent cell on the parent node.
908 </p></li><li><p> for leaf nodes, that there is an entry in the %_rowid
909 table corresponding to the cell's rowid value that
910 points to the correct node.
911 </p></li><li><p> for cells on non-leaf nodes, that there is an entry in the
912 %_parent table mapping from the cell's child node to the
913 node that it resides on.
914 </p></li></ol>
915 </li><li><p>
916 That there are the same number of entries in the %_rowid table
917 as there are leaf cells in the r-tree structure, and that there
918 is a leaf cell that corresponds to each entry in the %_rowid table.
919 </p></li><li><p>
920 That there are the same number of entries in the %_parent table
921 as there are non-leaf cells in the r-tree structure, and that
922 there is a non-leaf cell that corresponds to each entry in the
923 %_parent table.
924 </p></li></ol>
925 <p align="center"><small><i>This page was last updated on 2025-05-31 13:08:22Z </small></i></p>
926