Add GiST and SP-GiST support

[zachasme]

We should support GiST and SP-GiST indexes for operations like contains and contained by.

Ongoing work in separate PRs:

• GiST in GiST support #42
• SP-GiST in SP-GiST support #43

[AbelVM]

Hi, any news on this? The PR looks stalled as it's 1 year old, but there's no info on the blockers or the status.

How can we help? 🔨

[zachasme]

If I recall correctly, the state of the branch (which hasn't been touched in a year 😮) is that we managed to get GiST and SP-GiST operator classes to compile and run. However, tests either returned wrong results or were significantly slower than no index. There probably is either a logical error or a misimplementation of (SP-)GiST.

Help is very much welcomed!

The branch should be rebased (or maybe it's easier to simply copy the opclass since so much has changed). Then, we need to figure out what is wrong with our implementation. My implementation is based off the SP-GiST docs and GiST docs but if anyone has some other reference implementation that could be helpful.

[AbelVM]

Cool, we will take a look at it. I have some ideas I'd like to test 😃

But first, I have a question related to these functions (gist_cmp and common_ancestor, mainly) in the PR: You have defined a lot of bitwise logic in h3index.h, but then in the index related functions, you use high-level methods from the core API instead. Is there any reason for that? Looks like a lot of redundant (implicit) operations to me 🤔

[zachasme]

That sounds great 😃

You are correct that the bitwise logic is mostly unused. I have directly copied h3index.h from the h3 repository since I needed the H3_GET_INDEX_DIGIT macro. I actually made this related issue uber/h3#277 since it is not exposed to library consumers.

The branch is very much a work-in-progress, and it would probably better to only include the necessary macros.

[AbelVM]

As you asked for some references about GiST:

• GiST bible
• PostGIS implementation (gserialized_gist*.* a bit spread over here and here)

And, regarding the bitwise version, I just made a PR instead of a codeblock in this comment :)

[zachasme]

I've split the old branch into two, so we can get GiST working and merged before moving on to SP-GiST.

[multi-spectral]

Hi, you mentioned above that using the GiST index can lead to slower results - is there more known about the causes of this? Are some kinds of queries more affected than others?

[zachasme]

It is not a problem with GiST generally, but a problem with my initial implementation. Specifically I need to come up with good algorithms for penalty and picksplit (see https://www.postgresql.org/docs/current/gist-extensibility.html). I just haven't yet been able to dedicate the time necessary to solve this.

[zachasme]

Discussion continued in:

• GiST in GiST support #42
• SP-GiST in SP-GiST support #43