Z-order curve usage to decrease dimensionality to 1

Most people know you can use Z/C-curve encodings to dynamically content address point data. There is a (very useful) generalization to hyper-rectangle types, perfect for content-addressing non-point geometries etc, but those types can't be meaningfully sequentialized at all in big systems. Most non-trivial spatial analytics involve non-point geometries, so being able to sequentialize points has limited utility.

Second, the computational cost of sorting along the curve, assuming you are using only points, is prohibitively high for negligible benefit. Modern storage engines use small shards, which are adaptively re-sharded as needed, and medium-sized pages. For insert, the content-addressing mechanic gets you to a single page; it would be significantly more expensive if you were sorting along the curve. For query, the typical selectivity on a shard is so high due to small adaptive shards, that you are better off treating it as an unsorted vector anyway. In short, much slower inserts and few (if any) query benefits.

As an optimization, it tends to only be applicable in cases where the architecture is significantly suboptimal anyway e.g. the use of gigantic shards. You'd get more benefit by fixing the architecture than trying to optimize poor architecture if at all possible.

    zorder64_inv:
        movabsq $0x5555555555555555, %rax
        pextq   %rax, %rcx, %rdx
        shrq    %rcx
        pextq   %rax, %rcx, %rcx
        shlq    $32, %rcx
        movl    %edx, %eax
        orq     %rcx, %rax
        retq

    zorder64:
        movl    %ecx, %eax
        movabsq $0x5555555555555555, %r8
        pdepq   %r8, %rax, %rcx
        movl    %edx, %eax
        pdepq   %r8, %rax, %rax
        addq    %rax, %rax
        orq     %rcx, %rax
        retq

I haven’t ever seen any convincing benchmarks or other analysis where the Hilbert curve created any notable performance advantage vs. Z order; the only time you really need it is if moving along the linearized coordinate must never have jumps in the multidimensional coordinates, but I’m not convinced there are many if any real-world cases where that is important (note that in either case small movements in the multidimensional coordinates are associated with large jumps in the linearized coordinate). If the only goal is to minimize memory fetches, etc. then the Z ordering works just fine.

(If you know any good comparisons where the Hilbert curve comes out ahead, I’d be curious to read them.)

And I'm sure that constructing H-curves doesn't need to be as complicated as that linked academic code makes it look, but for now I don't know of any implementation.

Thanks for the link though :)