Hi Tanmay, Thanks for the validation, and for taking the time to go through the code as well.
On scanned bytes: I agree it's the more direct proxy for I/O in principle, but it wouldn't add much in this particular setup. For convenience I wrote each file with a single row group, so any file that isn't skipped is read in full at ~16 MB per file, scanned bytes would just be a rescaling of the file count. That's admittedly not a realistic production layout, but keeping it fixed is what lets the comparison stay focused on the curve itself rather than on the layout. Measuring properly at the byte level would also pull in a fair amount of unrelated variance: differences between Hadoop/filesystem implementations, compression and encoding effects, object-store read behaviour on S3, and the need to first settle on a reasonable file-size / row-group configuration. That's enough noise that I'd rather it get its own thread than be folded into this one. Agreed on the maintainer review for the public API addition and the expectations around broader engine support. It would also be useful to hear from whoever worked on the bit-interleaving in the Z-order implementation, since the Hilbert path reuses that byte encoding. Cheers, Gianluca ggraziadei Il giorno mar 28 lug 2026 alle ore 16:41 Tanmay Rauth <[email protected]> ha scritto: > Hi Gianluca, > > Thanks for turning this around so quickly. > > The file-scan result looks like the strongest evidence to me: 16/98 files > for Z-order versus 11/98 for Hilbert is a deterministic planning-time > measurement, so it is not affected by the runtime noise seen in the latency > results. The roughly 31% reduction across the six queries also appears > consistent with the analytical basis you cited. > > Adding scanned bytes in a follow-up would still be useful since it would > more directly represent I/O. I also agree that the latency results should > not be treated as evidence given the variance and swap pressure. The > disagreement with the overlap metric may still be worth understanding, but > the scan-set measurement seems more directly relevant here. > > From my perspective, this addresses the benchmarking question I raised. > > I also reviewed the change more closely. The API shape appears consistent > with the existing Z-order path: hilbert(...)parallels zOrder(...), the > Hilbert term follows the same general pattern as Zorder, and the > implementation reuses the existing Z-order byte encoding. The evidence and > overall design direction look reasonable to me. It would be useful to hear > maintainers’ views on the public API addition and expectations for broader > engine support. > > Thanks again for putting the comparison together. > > Regards, > Tanmay > > > On Mon, Jul 27, 2026 at 11:53 AM Gianluca Graziadei < > [email protected]> wrote: > > > > Hi Tanmay, > > > > Ran the end-to-end comparison you asked for. Report attached; headline > numbers here. > > > > Here the report: > https://docs.google.com/document/d/1b7TCuotV-zqTwzW0C9hqmcvQntlbuhXPLMmV8RguFTI/edit?usp=sharing > > > > TPC-H SF10 lineitem, same source data and clustered columns in both > arms, 58 files rewritten into 98. The queries are the stock TPC-H ones with > predicates slightly extended to filter on all three multidimensional index > columns — the originals lean on single-column filters and wouldn't exercise > the case this change targets. Identical queries in both arms, and each one > is run 10 times. > > > > - Files scanned: 16/98 (Z-order) vs 11/98 (Hilbert) a 31.25% reduction, > consistent across all six queries. Planning-time measurement, so it's > deterministic rather than timed; the repeats don't affect it. > > - Rewrite: 169.8 s vs 196.0 s, +15.4% for Hilbert. Breaks even after ~18 > query passes. > > > > Caveats I'd rather state up front than defend later: > > > > Query latency was 12–38% lower for Hilbert, but I wouldn't quote those > numbers as evidence. The 10 repeats are what makes that clear: Z-order's > coefficient of variation lands at 20–52% against Hilbert's 3–11%, and swap > was near-exhausted for the duration of the run. A clustering change shifts > the mean, not the variance, so that asymmetry is the platform rather than > the algorithm. On most queries the gap sits inside one standard deviation. > > > > The pairwise file overlap metric ranks Hilbert worse while the actual > scan set ranks it better. Section 5 of the report argues the metric is the > unreliable one, but that's an argument rather than a demonstration. > > > > On file size: 16 MB, chosen to get enough files for the comparison to be > resolvable on a laptop. Worth being precise about what this does and > doesn't limit. The report isn't trying to identify an optimal file size, > and TPC-H is scale-invariant, scaling the dataset and the file size > together (say SF100 at 160 MB) gives the same 98 files over the same > key-space distribution, so the pruning ratio should carry over. What > wouldn't carry over is holding SF10 fixed and moving to 256 MB files: that > leaves a handful of files, and neither curve would have the granularity to > express a 31% difference. The measurement is of the algorithms' clustering > behaviour, not of a production configuration. > > > > I captured file counts but not scanned bytes, easy to add on the next > run. > > > > Short version: the pruning improvement is real and well measured, the > timing improvement is plausible but unproven, and the magnitudes hold for a > fixed file count rather than a fixed file size. Let me know if you'd want > the scaled run before this progresses. > > > > > > 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 > >>
