apache / apache/iceberg

Core, Spark: Introduce a shared multi-column term to de-duplicate Z-order and Hilbert clustering

Open
#17,657 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Java
Stars
9.2k
Forks
3.5k
Avg merge
2d 11h
Merged PRs (30d)
132

Description

### Feature Request / Improvement

Follow-up to #16827, which adds a Hilbert-curve clustering strategy for `rewrite_data_files`.
**This should be picked up once #16827 is merged** — it is a refactor of the surface that PR
introduces, so doing it beforehand would just create conflicts.

#### Background

#16827 deliberately mirrors the existing Z-order implementation rather than refactoring it, to
keep the diff reviewable and leave the well-tested Z-order path untouched. That was agreed as the
right call during review, with the clean-up explicitly deferred to a follow-up:

> I think this is fine for now, but we'll probably want a "MultiColumnTerm" or something like that
> in the future. That can wait though until we start doing more complicated work with expressions
> I think.
> — @RussellSpitzer, https://github.com/apache/iceberg/pull/16827#discussion_r3776677662

> This looks good to me, I know we are copying a lot of surface area from ZOrder that I was hoping
> we would have time to clean up by now but we can always save that for later. Now that we have
> Expressions and such we probably have a much larger refactor we can do to allow for an arbitrary
> function in here.
> — @RussellSpitzer, https://github.com/apache/iceberg/pull/16827#pullrequestreview-4930856309

> +1 to doing a expressions-based refactor as a follow up and de-dupe the z-order work here.
> — @nssalian, https://github.com/apache/iceberg/pull/16827#discussion_r3779005936

#### Duplication to address

Once #16827 lands, the following are near-identical pairs:

- `org.apache.iceberg.expressions.Zorder` and `org.apache.iceberg.expressions.Hilbert` — identical
apart from the class name. Both are a `Term` wrapping an ordered list of column references, which
is the `MultiColumnTerm` abstraction Russell describes.
- `SparkZOrderFileRewriteRunner` and `SparkHilbertFileRewriteRunner` — differ only in the internal
column name and the final combine step. In particular `validZOrderColNames` and
`validHilbertColNames` are byte-for-byte the same logic.
- `SparkZOrderUDF` and `SparkHilbertUDF` — the per-column ordered-byte conversion is already shared
(the Hilbert runner reuses `SparkZOrderUDF.sortedLexicographically`); only the combine differs
(`interleaveBits` vs `HilbertByteUtils.hilbertIndex`).
- The `zorder` / `hilbert` dispatch in `Spark3Util.toIcebergTerm` and the corresponding branches in
the sort-strategy plumbing.

#### Suggested scope

1. Introduce a shared multi-column term in `org.apache.iceberg.expressions` and express both
`Zorder` and `Hilbert` in terms of it, keeping the public API and the parsed SQL grammar
unchanged.
2. Factor the Spark runners onto a common base that is parameterised by the internal column name
and the combine function, so adding a further curve is a small, local change.
3. Keep the engine-side behaviour bit-for-bit identical — the existing Z-order and Hilbert tests
should pass unmodified, which is the main safety net for this refactor.

Russell's wider point about allowing an arbitrary function via `Expressions` is a natural extension
of (1) and could either be folded in here or split out again, depending on how large it turns out.

#### Query engine

Spark

Contributor guide

Open the contributing guide

Research direction

Start after #16827 merges by comparing the named Zorder and Hilbert terms, SparkZOrderFileRewriteRunner and SparkHilbertFileRewriteRunner, and the two UDFs. Trace Spark3Util.toIcebergTerm and the sort-strategy branches before designing the shared abstraction. Done means the duplicated surface is factored out, public APIs and SQL grammar remain unchanged, and the existing Z-order and Hilbert tests pass unmodified.

Written by the indexing model from the issue text.

Assessment

Tech stack
java, spark
Domain
data
Issue type
Refactor
Difficulty
4/5
Estimated time
3-5 days
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
48/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.