Re: Yet another fast GiST build

On Wed, Feb 19, 2020 at 8:00 PM Thomas Munro <thomas(dot)munro(at)gmail(dot)com> wrote:
> Could this function please have a comment that explains why it works?
> I mean, just a breadcrumb... the name of the technique or something...
> so that uninitiated hackers can google their way to a clue (is it
> "Morton encoding"?)

Ok I think I get it now after doing some homework.

1. We expect floats to be in IEEE format, and the sort order of IEEE
floats is mostly correlated to the binary sort order of the bits
reinterpreted as an int. It isn't in some special cases, but for this
use case we don't really care about that, we're just trying to
encourage locality.
2. We generate a Morton code that interleaves the bits of N integers
to produce a single integer that preserves locality: things that were
close in the N dimensional space are close in the resulting integer.

Cool.

+static int
+my_fastcmp(Datum x, Datum y, SortSupport ssup)
+{
+ /* esteblish order between x and y */
+
+ return z1 == z2 ? 0 : z1 > z2 ? 1 : -1;
+}

This example code from the documentation looks wrong, probably missing
eg int64 z1 = DatumGetInt64(x).