extension_spatialindex.adoc

RTree Spatial Indexes

Introduction

This extension adds a new capability for spatially indexing columns with geometries encoded per clause [gpb_format] and [extension_geometry_encoding].

The RTree index extension provides a means to encode an RTree index for geometry values in a GeoPackage. An RTree index 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.

Spatial indexes provide 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.^[1]

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 rtree 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, and the column_name of the spatially indexed column.

Requirement 77

A GeoPackage SHALL implement spatial indexes on feature table geometry columns using the SQLite Virtual Table RTrees 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

RTree spatial indexes on geometry columns SHALL be created using the SQLite Virtual Table RTree 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 rtree 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 rtree index.

Load Spatial Index Values

The indexes provided by the SQLite Virtual Table RTree extension are not automatic indices. 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 <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 rtree */
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;

/* Conditions: Update of geometry column to non-empty geometry
               No row ID change
   Actions   : Update record in rtree */
CREATE TRIGGER rtree_<t>_<c>_update1 AFTER UPDATE OF <c> ON <t>
  WHEN OLD.<i> = NEW.<i> AND
       (NEW.<c> NOTNULL 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;

/* Conditions: Update of geometry column to empty geometry
               No row ID change
   Actions   : Remove record from rtree */
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;

/* Conditions: Update of any column
               Row ID change
               Non-empty geometry
   Actions   : Remove record from rtree for old <i>
               Insert record into rtree for new <i> */
CREATE TRIGGER rtree_<t>_<c>_update3 AFTER UPDATE OF <c> 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 of any column
               Row ID change
               Empty geometry
   Actions   : Remove record from rtree 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: Row deleted
   Actions   : Remove record from rtree 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.

GeoPackage SQLite Configuration

Definition of SQLite configuration settings

Setting compile or runtime	Option	Shall / Not (Value)	Discussion
compile	SQLITE_ENABLE_RTREE	Shall	RTrees ares used for GeoPackage Spatial Indexes
compile	SQLITE_RTREE_INT_ONLY	Not	RTrees 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

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.

Abstract Test Suite

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_contents WHERE data_type == 'features')) 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 Not testable if result set is empty 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 tname = 'rtree_' || result_set_table_name || '_' || result_set_column_name || '_insert' Fail if returned sql != result of populating insert triggers 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%' Fail if returned sql != result of populating 4 update triggers templates using result_set_table_name for <t> and result_set_column_name for <c> 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> Log pass otherwise Pass if logged pass and no fails
Reference	Annex F.3 Req 75
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 76
Test Type	Capability

Extensions Name

Test Case ID	/reg_ext/features/spatial_indexes/extension_name
Test Purpose	Verify that the "gpkg_rtree_index" extension name is used to register spatial index extensions.
Test Method	SELECT table_name, column_name FROM gpkg_geometry_columns WHERE table_name IN (SELECT table_name FROM gpkg_contents WHERE data_type == 'features')) Not testable if result set is empty For each row table_name, column_name from step 3 SELECT sql FROM sqlite_master WHERE tbl_name = 'rtree_' || result_set_table_name || '_' || result_set_column_name Not testable if returns an empty result set /opt/extension_mechanism/extensions/data/table_def Fail if failed SELECT extension_name from gpkg_extensions WHERE table_name = result_set_table_name AND column_name = result_set_column_name Log pass if result is "gpkg_rtree_index" Fail otherwise Pass if logged pass and no fails
Reference	Annex F.3 Req 77
Test Type	Basic

Extensions Row

Test Case ID	/reg_ext/features/spatial_indexes/extension_row
Test Purpose	Verify that spatial index extensions are registered using the "gpkg_rtree_index" name in the gpkg_extensions table.
Test Method	/reg_ext/features/spatial_indexes/extension_name
Reference	Annex F.3 Req 78
Test Type	Capability

---

1. If an application process will make many updates, it is often faster to drop the indexes, do the updates, and then recreate the indexes.