| 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><name></em> USING rtree(<em><column-names></em>); |
| 237 |
</pre></div> |
| 238 |
|
| 239 |
<p> |
| 240 |
The <em><name></em> is the name your application chooses for the |
| 241 |
R*Tree index and <em><column-names></em> is a comma separated list |
| 242 |
of between 3 and 11 columns. |
| 243 |
The virtual <name> 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><name></em><strong>_node</strong><br> |
| 248 |
<em><name></em><strong>_rowid</strong><br> |
| 249 |
<em><name></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<=-80.77470 AND maxX>=-80.77470 |
| 353 |
AND minY<=35.37785 AND maxY>=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>=B.minX AND A.minX<=B.maxX |
| 368 |
AND A.maxY>=B.minY AND A.minY<=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>=35.0 AND minY<=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>=35.0 AND minY<=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<=-80.77470 AND maxX>=-80.77470 |
| 523 |
AND minY<=35.37785 AND maxY>=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<=-80.77470 AND maxX>=-80.77470 |
| 589 |
AND minY<=35.37785 AND maxY>=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 <= 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 |
|