Spatial Partitioning Indexes
A partitioning index divides space into non-overlapping regions. In GIS, common partitioning indexes are the quad-tree and kd-tree. PostGIS currently uses a balanced index, the r-tree for all spatial indexing. R-tree's are good general purpose indexes for range data, but since GIS data tends to be accessed in discrete regions, spatial partitioning indexes are a better fit for the work-load.
Early benchmarking of a partitioning approach has shown as much as a several-times improvement in access speed over the r-tree index. Implementing a generic partitioning API, called "SP-GiST" inside PostgreSQL will open the possibility for PostGIS to expose quad-tree and kd-tree indexes to users.
Implementation of this performance enhancement will be in cooperation with the SP-GiST authors (Bartunov and Sigaev) and include the following items:
- Definition of the final SP-GiST API in consultation with the PostGIS team.
- Write-ahead log support for SP-GiST indexes.
- Concurrency and locking support for SP-GiST indexes.
- Documentation of the SP-GiST code to PostgreSQL standards.
- Implementation of SP-GiST quad-trees index bindings within PostGIS.
Funding
This roadmap item is currently unfunded.
Add your support for this item by contacting us for a quote and discussion of the particular features you need.
Get a quote now!
Get a quote or read more about core development to add your support to a road-map item.
Other Roadmap Items
Support for ST_Union(), ST_Difference(), and true/false predicate tests calculated natively on the sphere for the GEOGRAPHY type introduced in PostGIS 1.5.
The support for dimensions higher than X/Y is uneven as currently implemented. Most operations support clean handling of the Z dimension (but a few do not). A reasonable number of important functions do not support handling of the M dimension. This item would fix functions not handling higher dimensions.
For GIS data, spatial partitioning indexes (quadtree, kd-tree) have been shown to be significantly faster than more general balanced indexes (r-tree). PostGIS currently uses an r-tree index. Adding SP-GiST (a generic API for partitioned indexes) to PostgreSQL will allow much faster spatial searching in PostGIS.