extension_spatialindex.adoc

R-tree Spatial Indexes

Introduction

The R-tree Spatial Indexes extension provides a means to encode an R-tree index for geometry values in a GeoPackage. An R-tree index [B28] provides a significant performance advantage for searches with basic envelope spatial criteria that return subsets of the rows in a feature table with a non-trivial number (thousands or more) of rows.^[K26]

Extension Author

GeoPackage SWG, author_name gpkg.

Extension Name or Template

gpkg_rtree_index

Extension Type

New Requirement dependent on clauses [gpb_format] and [extension_geometry_encoding].

Applicability

This extension applies to any column specified in the gpkg_geometry_columns table.

Scope

Write-only, because it does not change the result of reads, although it may improve their performance.

Requirements

This extension uses the R-tree implementation provided by the SQLite R*Tree Module extension documented at http://www.sqlite.org/rtree.html.

GeoPackage

Requirement 75

The "gpkg_rtree_index" extension name SHALL be used as a gpkg_extensions table extension_name column value to specify implementation of spatial indexes on a geometry column.

Requirement 76

A GeoPackage that implements spatial indexes SHALL have a gpkg_extensions table that contains a row for each spatially indexed column with extension_name "gpkg_rtree_index", the table_name of the table with a spatially indexed column, the column_name of the spatially indexed column, and a scope of "write-only".

Requirement 77

A GeoPackage SHALL implement spatial indexes on feature table geometry columns using the SQLite Virtual Table R-trees and triggers specified below. The tables below contain SQL templates with variables. Replace the following template variables with the specified values to create the required SQL statements:
<t>: The name of the feature table containing the geometry column
<c>: The name of the geometry column in <t> that is being indexed
<i>: The name of the integer primary key column in <t> as specified in [r29]

Create Virtual Table

R-tree spatial indexes on geometry columns SHALL be created using the SQLite Virtual Table R-tree extension. An application that creates a spatial index SHALL create it using the following SQL statement template:

CREATE VIRTUAL TABLE rtree_<t>_<c> USING rtree(id, minx, maxx, miny, maxy)

where <t> and <c> are replaced with the names of the feature table and geometry column being indexed. The R-tree function id parameter becomes the virtual table 64-bit signed integer primary key id column, and the min/max x/y parameters are min- and max-value pairs (stored as 32-bit floating point numbers) for each dimension that become the virtual table data columns that are populated to create the spatial R-tree index.

Load Spatial Index Values

The indexes provided by the SQLite Virtual Table R-tree extension are not automatic indexes. This means the index data structure needs to be manually populated, updated and queried. Each newly created spatial index SHALL be populated using the following SQL statement

INSERT OR REPLACE INTO rtree_<t>_<c>
  SELECT <i>, ST_MinX(<c>), ST_MaxX(<c>), ST_MinY(<c>), ST_MaxY(<c>) FROM <t> WHERE <c> NOT NULL AND NOT ST_IsEmpty(<c>);

where <t> and <c> are replaced with the names of the feature table and geometry column being indexed and <i> is replaced with the name of the feature table integer primary key column.

Define Triggers to Maintain Spatial Index Values

For each spatial index in a GeoPackage, corresponding insert, update and delete triggers that update the spatial index SHALL be present on the indexed geometry column. These spatial index triggers SHALL be defined as follows:

/* Conditions: Insertion of non-empty geometry
   Actions   : Insert record into R-tree */
CREATE TRIGGER rtree_<t>_<c>_insert AFTER INSERT ON <t>
  WHEN (new.<c> NOT NULL AND NOT ST_IsEmpty(NEW.<c>))
BEGIN
  INSERT OR REPLACE INTO rtree_<t>_<c> VALUES (
    NEW.<i>,
    ST_MinX(NEW.<c>), ST_MaxX(NEW.<c>),
    ST_MinY(NEW.<c>), ST_MaxY(NEW.<c>)
  );
END;

/* rtree_<t>_<c>_update1 is deprecated and is replaced by
    rtree_<t>_<c>_update6 and rtree_<t>_<c>_update7 */

/* Conditions: Update of geometry column to empty geometry
               No row ID change
   Actions   : Remove record from R-tree */
CREATE TRIGGER rtree_<t>_<c>_update2 AFTER UPDATE OF <c> ON <t>
  WHEN OLD.<i> = NEW.<i> AND
       (NEW.<c> ISNULL OR ST_IsEmpty(NEW.<c>))
BEGIN
  DELETE FROM rtree_<t>_<c> WHERE id = OLD.<i>;
END;

/* rtree_<t>_<c>_update3 is deprecated and is replaced by
    rtree_<t>_<c>_update5 */

/* Conditions: Update of any column
               Row ID change
               Empty geometry
   Actions   : Remove record from R-tree for old and new <i> */
CREATE TRIGGER rtree_<t>_<c>_update4 AFTER UPDATE ON <t>
  WHEN OLD.<i> != NEW.<i> AND
       (NEW.<c> ISNULL OR ST_IsEmpty(NEW.<c>))
BEGIN
  DELETE FROM rtree_<t>_<c> WHERE id IN (OLD.<i>, NEW.<i>);
END;

/* Conditions: Update of any column
               Row ID change
               Non-empty geometry
   Actions   : Remove record from R-tree for old <i>
               Insert record into R-tree for new <i> */
CREATE TRIGGER rtree_<t>_<c>_update5 AFTER UPDATE ON <t>
  WHEN OLD.<i> != NEW.<i> AND
       (NEW.<c> NOTNULL AND NOT ST_IsEmpty(NEW.<c>))
BEGIN
  DELETE FROM rtree_<t>_<c> WHERE id = OLD.<i>;
  INSERT OR REPLACE INTO rtree_<t>_<c> VALUES (
    NEW.<i>,
    ST_MinX(NEW.<c>), ST_MaxX(NEW.<c>),
    ST_MinY(NEW.<c>), ST_MaxY(NEW.<c>)
  );
END;

/* Conditions: Update a non-empty geometry with another non-empty geometry
   Actions   : Replace record from R-tree for <i> */
CREATE TRIGGER rtree_<t>_<c>_update6 AFTER UPDATE OF <c> ON <t>
  WHEN OLD.<i> = NEW.<i> AND
       (NEW.<c> NOTNULL AND NOT ST_IsEmpty(NEW.<c>)) AND
       (OLD.<c> NOTNULL AND NOT ST_IsEmpty(OLD.<c>))
BEGIN
  UPDATE rtree_<t>_<c> SET
    minx = ST_MinX(NEW.<c>),
    maxx = ST_MaxX(NEW.<c>),
    miny = ST_MinY(NEW.<c>),
    maxy = ST_MaxY(NEW.<c>)
  WHERE id = NEW.<i>;
END;

/* Conditions: Update a null/empty geometry with a non-empty geometry
   Actions   : Insert record into R-tree for new <i> */
CREATE TRIGGER rtree_<t>_<c>_update7 AFTER UPDATE OF <c> ON <t>
  WHEN OLD.<i> = NEW.<i> AND
       (NEW.<c> NOTNULL AND NOT ST_IsEmpty(NEW.<c>)) AND
       (OLD.<c> ISNULL OR ST_IsEmpty(OLD.<c>))
BEGIN
  INSERT INTO rtree_<t>_<c> VALUES (
    NEW.<i>,
    ST_MinX(NEW.<c>), ST_MaxX(NEW.<c>),
    ST_MinY(NEW.<c>), ST_MaxY(NEW.<c>)
  );
END;

/* Conditions: Row deleted
   Actions   : Remove record from R-tree for old <i> */
CREATE TRIGGER rtree_<t>_<c>_delete AFTER DELETE ON <t>
  WHEN old.<c> NOT NULL
BEGIN
  DELETE FROM rtree_<t>_<c> WHERE id = OLD.<i>;
END;

where <t> and <c> are replaced with the names of the feature table and geometry column being indexed and <i> is replaced with the name of the feature table integer primary key column.

Warning

GeoPackage Versions 1.2.0 and prior have an incorrect update3 trigger that will fail in certain circumstances. GeoPackage Version 1.2.1 fixes this issue by replacing the update3 trigger. In GeoPackage 1.4.0, the decision was made to deprecate the update3 trigger and replace it with the new update5 trigger. This will allow clients to easily detect whether the correct trigger is in place. It is strongly recommended to update older GeoPackages by dropping the update3 trigger and adding the update5 trigger. The GeoPackage Executable Test Suite has been updated to accept either version of the trigger in older versions and to mandate the corrected version in versions after 1.2.0. In addition, GeoPackage Versions 1.3.1 and prior have a single update1 trigger that is incompatible with upsert statements. GeoPackage Version 1.4.0 fixes this issue by replacing the update1 trigger with the new update6 and update7 triggers. It is strongly recommended to update older GeoPackages by dropping the update1 trigger and adding the update6 and update7 triggers. The GeoPackage Executable Test Suite will be updated to accept either version of the trigger in older versions and to mandate the corrected version in versions after 1.3.1. If present, the deprecated triggers can be dropped with a DROP TRIGGER command. DROP TRIGGER rtree_<t>_<c>_update1; DROP TRIGGER rtree_<t>_<c>_update3;

GeoPackage SQLite Configuration

Definition of SQLite configuration settings

Setting compile or runtime	Option	Shall / Not (Value)	Discussion
compile	SQLITE_ENABLE_RTREE	Shall	R-trees are used for GeoPackage Spatial Indexes
compile	SQLITE_RTREE_INT_ONLY	Not	R-trees with floating point values are used for GeoPackage spatial indexes

GeoPackage SQLite Extension

Definition of SQL functions

SQL Function	Description	Use
ST_IsEmpty(geom Geometry): integer	Returns 1 if geometry value is empty, 0 if not empty, NULL if geometry value is NULL	Test if a geometry value corresponds to the empty set
ST_MinX(geom Geometry): real	Returns the minimum X value of the bounding envelope of a geometry	Update the spatial index on a geometry column in a feature table
ST_MaxX(geom Geometry): real	Returns the maximum Y value of the bounding envelope of a geometry	Update the spatial index on a geometry column in a feature table
ST_MinY(geom Geometry): real	Returns the minimum X value of the bounding envelope of a geometry	Update the spatial index on a geometry column in a feature table
ST_MaxY(geom Geometry): real	Returns the maximum Y value of the bounding envelope of a geometry	Update the spatial index on a geometry column in a feature table

Requirement 78

The SQL functions on geometries in this SQLite Extension SHALL operate correctly on extended geometry types specified by [extension_geometry_encoding] and/or [extension_geometry_types] when those extensions are also implemented.

Note

The minimum bounding indexes created within the R-tree Extension for GeoPackage should reflect the appropriate bounding area for the indexed feature. However, due to varying precision implementations, it is not practical to assert this practice through a requirement or test. Clients should exercise care when using these indexes during queries because the SQLite R-tree module might round bounding boxes slightly outward (up to 0.000012%). Queries using spatial indexes should contain slightly expanded bounding boxes to guard against this.

Abstract Test Suite

Extension Name

Test Case ID	/extensions/rtree/extension_name
Test Purpose	Verify that spatial index extensions are registered using the "gpkg_rtree_index" name in the gpkg_extensions table.
Test Method	SELECT COUNT(*) FROM gpkg_extensions WHERE extension_name = 'gpkg_rtree_index'; Extension not testable if count = 0
Reference	Annex F.3 Req 75
Test Type	Capability

Extensions Row

Test Case ID	/extensions/rtree/extension_row
Test Purpose	Verify that the "gpkg_rtree_index" extension name is used to register spatial index extensions.
Test Method	SELECT table_name, column_name, scope FROM gpkg_extensions WHERE extension_name = 'gpkg_rtree_index' Not testable if result set is empty Fail if any column_name is NULL Fail if any scope is not 'write-only' Fail if any column_name is not a column in table_name Pass otherwise
Reference	Annex F.3 Req 76
Test Type	Basic

Implementation

Test Case ID	/reg_ext/features/spatial_indexes/implementation
Test Purpose	Verify the correct implementation of spatial indexes on feature table geometry columns.
Test Method	SELECT table_name, column_name FROM gpkg_geometry_columns WHERE table_name IN (SELECT table_name FROM gpkg_extensions WHERE extension_name == 'gpkg_rtree_index') Not testable if result set is empty For each row table_name, column_name from step 1 SELECT sql FROM sqlite_master WHERE tbl_name = 'rtree_' || result_set_table_name || '_' || result_set_column_name Fail if returned sql != 'CREATE VIRTUAL TABLE "rtree_' || result_set_table_name || '_' || result_set_column_name ||'" USING rtree(id, minx, maxx, miny, maxy)' SELECT sql FROM sqlite_master WHERE type = 'trigger' AND name = 'rtree_' || result_set_table_name || '_' || result_set_column_name || '_insert' Fail if returned sql != result of populating insert trigger template using result_set_table_name for <t> and result_set_column_name for <c> SELECT sql FROM sqlite_master WHERE type = 'trigger' AND name LIKE 'rtree_' || result_set_table_name || '_' || result_set_column_name || '_update%' ORDER BY name ASC Fail if returned sql != result of populating 4 5 update triggers templates using result_set_table_name for <t> and result_set_column_name for <c> Fail if the result set contains the deprecated update1 and/or update3 triggers. SELECT sql FROM sqlite_master WHERE type='trigger' AND name = 'rtree_' || result_set_table_name || '_' || result_set_column_name || '_delete' Fail if returned sql != result of populating delete trigger template using result_set_table_name for <t> and result_set_column_name for <c> Pass if no fails
Reference	Annex F.3 Req 77
Test Type	Capability

Test Case ID	/reg_ext/features/spatial_indexes/implementation/sql_functions
Test Purpose	Verify the correct implementation of sql functions used in spatial indexes on feature table geometry columns.
Test Method	Open Geometry Test Data Set GeoPackage with GeoPackage SQLite Extension For each Geometry Test Data Set <gtype_test> data table row for each geometry type in Annex G, for an assortment of srs_ids, for an assortment of coordinate values including empty geometries, without and with z and / or m values, in both big and little endian encodings: SELECT 'Fail' FROM <gtype_test> WHERE ST_IsEmpty(geom.) != empty SELECT 'Fail' FROM <gtype_test> WHERE ST_MinX(geom) != minx SELECT 'Fail' FROM <gtype_test> WHERE ST_MaxX(geom) != maxx SELECT 'Fail' FROM <gtype_test> WHERE ST_MinY(geom) != miny SELECT 'Fail' FROM <gtype_test> WHERE ST_MaxY(geom) != maxy Pass if no 'Fail' selected from step 2
Reference	Annex F.3 Req 78
Test Type	Capability