Documentation Source Text

Check-in [7e421e2c51]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Add documentation for custom r-tree geometry callbacks to rtree.in
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 7e421e2c517cce4a04c6fd51bd6ce7cce537b2ad
User & Date: dan 2010-08-31 11:01:26
Context
2010-08-31
15:03
Add a link to example geometry callback code to rtree.in. check-in: ed402895f8 user: dan tags: trunk
11:01
Add documentation for custom r-tree geometry callbacks to rtree.in check-in: 7e421e2c51 user: dan tags: trunk
2010-08-30
15:10
More typo and spelling fixes. check-in: d7a2085524 user: shaneh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to pages/rtree.in.

258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
...
289
290
291
292
293
294
295














































































































the North Carolina 12th District, one may be to run a query like this:
</p>

<blockquote><pre>
SELECT objname FROM demo_data, demo_index
 WHERE demo_data.id=demo_index.id
   AND contained_in(demo_data.boundary, :boundary)
   AND minX>=-81.0 AND max<=-79.6
   AND minY>=35.0 AND maxY<=36.2;
</pre></blockquote>)^

<p>In the query above, one would presumably bind the binary BLOB 
description of the precise boundary of the 12th district to the
":boundary" parameter.</p>

................................................................................

<p>The problem with this latter query is that it must apply the
contained_in() function to millions of entries in the demo_data table.
The use of the R*Tree in the penultimate query reduces the number of
calls to contained_in() function to a small subset of the entire table.
The R*Tree index did not find the exact answer itself, it merely
limited the search space.</p>





















































































































|







 







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
...
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
the North Carolina 12th District, one may be to run a query like this:
</p>

<blockquote><pre>
SELECT objname FROM demo_data, demo_index
 WHERE demo_data.id=demo_index.id
   AND contained_in(demo_data.boundary, :boundary)
   AND minX>=-81.0 AND maxX<=-79.6
   AND minY>=35.0 AND maxY<=36.2;
</pre></blockquote>)^

<p>In the query above, one would presumably bind the binary BLOB 
description of the precise boundary of the 12th district to the
":boundary" parameter.</p>

................................................................................

<p>The problem with this latter query is that it must apply the
contained_in() function to millions of entries in the demo_data table.
The use of the R*Tree in the penultimate query reduces the number of
calls to contained_in() function to a small subset of the entire table.
The R*Tree index did not find the exact answer itself, it merely
limited the search space.</p>

<h1>5.0 Custom R-Tree Queries</h1>

<p>By using standard SQL expressions in the WHERE clause of a SELECT query,
a user may query for all r-tree entries that intersect a specified
bounding-box, or for all entries that are completely encapsulated by a
specified bounding-box. Custom r-tree queries, which use the special MATCH
operator in the WHERE clause of a SELECT, allow the user to query for the set
of r-tree entries that intersect any arbitrarily defined region.

<p>Regions for custom r-tree queries are defined by r-tree geometry callbacks
implemented by the application and registered with SQLite via a call to the 
following API:

<blockquote><pre>
int sqlite3_rtree_geometry_callback(
  sqlite3 *db,
  const char *zGeom,
  int (*xGeom)(sqlite3_rtree_geometry *, int nCoord, double *aCoord, int *pRes),
  void *pContext
);
</pre></blockquote>

<p>A call to the above API registers an r-tree geometry callback named zGeom.
If an r-tree geometry callback or ordinary SQL user function named zGeom 
already exists when sqlite3_rtree_geometry_callback() is called, it is replaced
by the new r-tree geometry callback. If the xGeom parameter is passed a NULL
value, then any existing r-tree geometry callback or SQL user function is
removed from the system, but no new r-tree geometry callback is registered.

<p>When the r-tree geometry callback is used in a custom r-tree query, the
registered callback is invoked one or more times by SQLite to test whether or
not the user-defined region intersects with specific bounding boxes.
The bounding box being tested is defined by the contents of the aCoord[] 
array (size nCoord) passed to the callback. The aCoord[] array always contains
the same number of entries as there are coordinate columns in the r-tree table
(one less than the total number of columns, since the object id column does not
contain a coordinate). They define a bounding-box in the same way as each row
of the r-tree table itself does - the first scalar coordinate contains the
minimum value for the first dimension, followed by the maximum value for the
first dimension, followed by the minimum value for the second dimension, and so
on. If the specified bounding box intersects with the custom query region, then
the implementation of the callback must set the output parameter *pRes to
non-zero and return SQLITE_OK. If the specified bounding box does not intersect
the queried region, *pRes should be set to zero before returning SQLITE_OK. If
an error occurs, the callback may return an SQLite error code other than
SQLITE_OK, in which case the value of *pRes is ignored by SQLite and the query
abandoned.

<p>A registered r-tree geometry callback is used in an r-tree query by adding
a MATCH condition to the WHERE clause of a SELECT statement. For example,
assuming a custom geometry callback named "circle" has been registered, it may
be used in a query on the two-dimensional r-tree table "demo_index" defined in
earlier examples as follows: 

<blockquote><pre>
SELECT * FROM demo_index WHERE id MATCH circle(45.3, 22.9, 5.0)
</blockquote></pre>

<p>The left-hand side of the MATCH operator may be any column from the r-tree
table, including the object id column. It makes no difference which column is
used. The right-hand side of the MATCH operator is passed the results of an
SQL function with the same name as the r-tree geometry callback. Zero or more
function parameters may be specified by the user. Parameters are always
interpreted as 64-bit real values. If a text, integer or blob value is passed
as a parameter to an r-tree geometry callback function, it is converted to
a real value as if by a [CAST expression]. If an SQL NULL value is passed to
an r-tree geometry callback function, it is converted to the value 0.0.

<p>Parameters passed to r-tree geometry callback functions may be used by the
implementation of the r-tree geometry callback to define the specified
region in any way. For example, the three parameters passed to the "circle"
geometry callback above could identify the center point and radius of the
circular region of interest.

<p>The first argument to each invocation of an r-tree geometry callback is
a pointer to a structure of the following type. The contents of the structure
are not modified between multiple calls to the r-tree geometry callback
associated with a single query (unless the pUser or xDelUser member variables
are modified by the callback implementation - see below).

<blockquote><pre>
typedef struct sqlite3_rtree_geometry sqlite3_rtree_geometry;
struct sqlite3_rtree_geometry {
  void *pContext;                 /* Copy of pContext passed to s_r_g_c() */
  int nParam;                     /* Size of array aParam */
  double *aParam;                 /* Parameters passed to SQL geom function */
  void *pUser;                    /* Callback implementation user data */
  void (*xDelUser)(void *);       /* Called by SQLite to clean up pUser */
};
</pre></blockquote>

<p>The pContext member of the structure is always set to a copy of the pContext
argument passed to sqlite3_rtree_geometry_callback() when the r-tree geometry
callback is registered. The aParam[] array (size nParam) contains the parameter
values passed to the r-tree geometry callback as part of the SQL query. In
the example "circle" query above, nParam would be set to 3 and the aParam[]
array would contain the three values 45.3, 22.9 and 5.0.

<p>The pUser and xDelUser members of the sqlite3_rtree_geometry structure are
initially set to NULL. The pUser variable may be set by the callback
implementation to any arbitrary value that may be useful to subsequent
invocations of the callback within the same custom r-tree query (for example, a
pointer to a complicated data structure used to test for region intersection).
If the xDelUser variable is set to a non-NULL value, then after the custom
r-tree query has finished running SQLite automatically invokes it with the
value of the pUser variable as the only argument. In other words, xDelUser
may be set to a destructor function for the pUser value.