Add Hilbert-curve clustering strategy for `rewrite_data_files`

[C-Loftus]

Feature Request / Improvement

The Java version of iceberg added support for hilbert curve clustering in apache/iceberg#16827 which, to my understanding, should be present in iceberg 1.12

This rewrite strategy can improve the performance of geospatial queries and improve the usefulness of row group metadata.

As such I am wondering if it would make sense to add to iceberg-go for parity. I would be interested in working on this if so. However, from what I can see it seems like the PR in the Java version builds on top of the Z order curve functionality, which to my understanding is not yet in iceberg-go. Perhaps that would make sense to tackle first.

Feel free to close if not appropriate for this repo.

Thanks!

[nssalian]

CC: @GGraziadei to help with this, I know there were some follow up work pending in java. Definitely worth being consistent across the implementations.

[GGraziadei]

Hi @C-Loftus, thanks for your comment. I agree with you, and more generally with @nssalian, who is doing a great job on this direction. I think that maintaining alignment across implementations of the proposed features is one of the hardest challenges for Iceberg.

I’d like to report the current status of Hilbert in Java. This comment is a good starting point: apache/iceberg#16827 (comment).

Currently, Hilbert is available only in Spark 4.1. There are two PRs that I think should be completed before we propagate the feature horizontally across implementations (go and cpp) and vertically across versions (Spark 4.2 and Spark 4.0).

One of these PRs changes the bit-interleaving strategy to use a lut, while the other introduces the concept of a MultiTerm column and is interconnected with the v4.

I definitely agree that different implementations can work in parallel. However, in this case, what about waiting for these two PRs to land first? In the meantime, if you have some bandwidth, @C-Loftus, would you mind reviewing this PR? I believe this is quite aligned with your mathematical background: apache/iceberg#17774

[C-Loftus]

@GGraziadei Thanks for your message, your hard work on those PRs, and that context!

There are two PRs that I think should be completed before we propagate the feature horizontally across implementations (go and cpp) and vertically across versions (Spark 4.2 and Spark 4.0).

I agree, that makes sense to me. Once everyone feels the implementation is propagated and stable, happy to revisit this. Also if you feel that there should be a separate issue for Z-order in iceberg-go and that should be done first, happy to make an issue for that. I am personally mainly interested in hilbert curves for geospatial use cases, but I recognize that Z-order may make sense to implement first from a code perspective.

would you mind reviewing this PR? apache/iceberg#17774

I took a look through. It seems reasonable to me at a high level although honestly I would need to take some more time to refresh myself on some of the algorithms / spin up tests/benchmarks, for me to give a confident review one way or another. So take that with a grain of salt 😃