R-Tree Index Packing
The PostGIS spatial index currently splits pages based on longest edge. This results in trees that have sub-optimal spatial clustering in the branches, which in turn makes for sub-optimal clustering. A packed R-Tree would provide the highest performance clustering.
Clustering is the act of re-writing a data table onto physical disk in the "index order", so that records that are close together in the index tree are close together on the disk. This makes physical data access faster. For spatial data, the optimal cluster is spatially oriented – spatially close together records should be close together on the disk.
The PostGIS R-Tree does not automatically pack records into spatial clusters. Often several branches of the index tree cover the same spatial area. A packed tree would have a minimum number of branches covering a particular spatial area. There are various algorithms for R-Tree index packing which could be useful, but they generally apply to in-memory indexes. The main development effort would be in figuring out how to create a packed structure in the PostgreSQL GiST disk-based index.
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
Client software, particularly software that does coordinate system reprojection, requires the extent of a layer in order to integrate it with other layers. Spatial databases are generally slow at returning that information.
Indexed Nearest Neighbor Searches
Currently nearest-neighbor searching is carried out with ad hoc tricks that expand a search radius until a candidate set is generated, then finding the closest value in the candidate set. A directly indexed approach would be optimally fast.
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.