Hi Tanmay, Thanks for looking at this! Worth flagging that the advantage here has an analytical basis, not only an empirical one. Moon, Jagadish, Faloutsos and Saltz (IEEE TKDE) https://www.cs.cmu.edu/~christos/PUBLICATIONS/ieee-tkde-hilbert.pdf prove that the average number of clusters, runs of consecutively ordered points, within a query region converges to the region's surface area divided by twice the dimensionality under Hilbert ordering. In 2D that's a quarter of the query perimeter. The equivalent result for Z-order is a third of the perimeter plus two thirds of the side length in the unfavored direction, so Hilbert wins outright, and the gap widens as the query region gets more elongated along one axis, which is what multi-column predicates with differing selectivities produce. Their 3D simulations show 22–31% fewer clusters than Z-order.
Fewer clusters means fewer non-consecutive reads, which is the mechanism data skipping benefits from, so the theory gives a reasonable prior on the direction of the result. On the magnitude, I'm running a TPC-H benchmark to back this empirically: same dataset written with Z-order and with Hilbert on the same columns, reporting planned and scanned files/bytes alongside rewrite and query time. I'll focus on the skipping-sensitive queries (Q6 and Q19 in particular) plus a few synthetic multi-column predicates, since TPC-H's own predicates are mostly single-column and won't stress the multidimensional case much on their own. I'll post the numbers once the runs are done. Cheers, Gianluca Il giorno dom 26 lug 2026 alle ore 08:32 Tanmay Rauth <[email protected]> ha scritto: > Hi Gianluca, > > Thanks for putting this together. The approach is well motivated, and > reusing the existing Z-order byte encodings seems like a good way to keep > the change focused. > > One thing that would help strengthen the case is a small end-to-end > comparison with the existing Z-order implementation. The current JMH > benchmark measures Hilbert-index computation, but it would be useful to > also see the impact on data skipping using the same dataset and > multi-column predicates, for example, planned or scanned files/bytes and > rewrite or query time. > > I think this would make it easier to understand the practical benefit of > the additional API/core and Spark implementation surface. > > Overall, this looks promising and worth pursuing. > > Cheers, > Tanmay > > On Sat, Jul 25, 2026 at 12:09 AM Gianluca Graziadei < > [email protected]> wrote: > > > > Hi folks, > > > > I’ve opened a PR to add support for Hilbert curve ordering in > rewrite_data_files, offering an alternative spatial clustering strategy > alongside the existing Z-order implementation. > > > > CALL system.rewrite_data_files( > > table => 'db.tbl', > > strategy => 'sort', > > sort_order => 'hilbert(c1, c2)' > > ); > > > > When mapping multi-column space onto a 1D sequence for file compaction, > the goal is to keep points that are close in space close together on disk > to maximize file skipping during range filters.While Z-order works well, it > suffers from periodic "jumps" across space. Hilbert curves avoid these > discontinuous jumps, neighboring points on the curve are always true > neighbors in the multi-dimensional space. In practice, this provides > tighter spatial clustering and better data skipping (improving reading > performance, reducing the number of parquet files analyzed per query) when > queries filter across multiple columns simultaneously. > > > > Implementation: > > > > Reuses existing infra: Under the hood, the implementation leverages > Iceberg's existing, well-tested Z-order byte encodings and builds the curve > math on top. The existing Z-order codebase remains completely untouched. > > > > Algorithm & Context: Based on J. Skilling’s standard algorithm, > "Programming the Hilbert curve" (AIP Conf. Proc. 707, 381, 2004; see also > UMD Reference). Note that a similar approach has been proven in the > ecosystem, with Apache Hudi supporting Hilbert curves since v0.10.0 > (details here). > > > > Scope: Currently limited to Spark 4.1 (other engines will fall back > gracefully). > > > > Testing: Ships with full test coverage including curve-correctness > checks (bijection and neighbor-locality guarantees), runner/action/SQL > integration tests. No benchmark provided. > > > > I’d love to get feedback from the community on the approach and would > appreciate a review when you have a moment: > https://github.com/apache/iceberg/pull/16827 > > > > Looking forward to your thoughts! > > > > Cheers, > > Gianluca > >>
