PostGIS R-Tree: Why does it exist when PostgreSQL already implements its R-Tree with what appears to be the same algorithm?

Question

PostGIS implements its R-Tree algorithm via PostgreSQL's GiST. But PostgreSQL already implements its R-Tree and the logic appears almost identical to that PostGIS is also implementing.

So why are there 2 R-Trees in the PostgreSQL environment? I can think that it has to do with the fact that PostGIS offers additional data types. But was it really required that PostGIS adds its own (identical) R-Tree algorithm? It looks like redundant code to me (defining the same logic at two points). I can also think that there might have been differences in the past which required this inefficiency, but are they there now and so what would they be exactly?

Answer 1

You'll find there are multiple r-tree-over-gist implementations floating around. If you look in contrib/cube you'll find another one.

Fundamentally, the rtree-over-gist binding in core has not been built to be easy for extensions to make use of, it has been built for the type it supports: the internal box type.

That type differs from what's in PostGIS in a couple ways: it's a box, not a geometry; it assumes double precision, while PostGIS uses floats.

I suppose if the core code was generalized more, we could make use of it, maybe (the float/double issue might be insuperable). In addition to the 2D tree, which is quite similar, we also have an n-d tree, which is different (though it's similar to the contrib/cube implementation) and supports higher dimensional geometry indexing and geography indexing.

While DRY is a virtue in many cases, there's nothing fundamentally wrong with a little code copying. I found a wee bug in the core code back when I was code copying in the version under the 2.0 PostGIS release, thanks to having to read it very carefully while adapting it to our purposes for higher dimensionality.

Answer 2

From the FAQ,

Why aren't PostgreSQL R-Tree indexes supported?

Early versions of PostGIS used the PostgreSQL R-Tree indexes. However, PostgreSQL R-Trees have been completely discarded since version 0.6, and spatial indexing is provided with an R-Tree-over-GiST scheme.

Our tests have shown search speed for native R-Tree and GiST to be comparable. Native PostgreSQL R-Trees have two limitations which make them undesirable for use with GIS features (note that these limitations are due to the current PostgreSQL native R-Tree implementation, not the R-Tree concept in general):

• R-Tree indexes in PostgreSQL cannot handle features which are larger than 8K in size. GiST indexes can, using the "lossy" trick of substituting the bounding box for the feature itself.

• R-Tree indexes in PostgreSQL are not "null safe", so building an index on a geometry column which contains null geometries will fail. [GiST indexes are null-safe]

The TODO also has,

Fast extent estimation based on reading the head of the R-Tree.

So presumably they're a work-in-progress and they don't want to be tied to CORE to get their stuff accepted.

I think for a true explanation here you'd have to understand the commits and the differences.