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?

  • Perhaps duplicate with an answer by a PostGIS developer gis.stackexchange.com/questions/103647/… – user30184 Nov 28 '17 at 19:02
  • My question is actually a follow-up on the accepted answer; what is the scenario which requires PostGIS to implement its own R-Tree if PostgreSQL already implements it -- and both through GiST (so native R-Tree limitations are not relevant)? – Zeruno Nov 29 '17 at 16:31
  • Let's see if @Paul Ramsey reacts. – user30184 Nov 29 '17 at 16:53

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.

  • Thank you for relevant information and incredible insights! – Zeruno Dec 8 '17 at 16:17

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.