You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@iceberg.apache.org by "GGraziadei (via GitHub)" <gi...@apache.org> on 2026/06/15 23:17:51 UTC
[PR] Add Hilbert-curve clustering strategy for `rewrite_data_files` [iceberg]
GGraziadei opened a new pull request, #16827:
URL: https://github.com/apache/iceberg/pull/16827
This PR lets you cluster table data along a Hilbert space-filling curve when compacting files, a new option alongside the existing Z-order strategy.
Just run:
```sql
CALL system.rewrite_data_files(
table => 'db.tbl',
strategy => 'sort',
sort_order => 'hilbert(c1, c2)'
);
```
Why Hilbert? When you sort multi-column data onto a single curve, the goal is for rows that are close in your columns to land close together on disk, so queries with range filters can skip more files. Hilbert curves do this better than Z-order because they never make the big "jumps" across space that Z-order does neighbouring points on the curve are always true neighbours in the data. In practice, that means tighter clustering and better data skipping for queries that filter on several columns at once.
Under the hood, the change is small and low-risk: it reuses Iceberg's existing, well-tested Z-order byte encodings and only adds the curve math on top, following the standard algorithm from J. Skilling, *"Programming the Hilbert curve"* (AIP Conf. Proc. 707, 381, 2004; <https://doi.org/10.1063/1.1751381>). The Z-order code is left untouched. Scope is limited to Spark 4.1 for now (other engines fall back gracefully), and the change ships with full test coverage including curve-correctness checks (bijection + neighbour-locality), runner/action/SQL tests, and a JMH benchmark.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] API, Core, Spark: Add Hilbert-curve clustering strategy for `rewrite_data_files` [iceberg]
Posted by "GGraziadei (via GitHub)" <gi...@apache.org>.
GGraziadei commented on PR #16827:
URL: https://github.com/apache/iceberg/pull/16827#issuecomment-5151873435
Hi @nssalian ,
Thank you again for your message and for taking the time to review this PR.
Starting with your first point, thank you for bringing it up. I have prepared a design document and shared it here https://docs.google.com/document/d/1zIvnqcjG1qnHvNYnOacx3baykE4JPlJbmwe6u7ALlHc/edit?usp=sharing . I've also linked it from the PR description to provide more context around the motivation and expected benefits of introducing Hilbert as a new public sort strategy.
For now, I have granted comment access to the document. If anyone would like to contribute directly, please let me know your email address and I'll be happy to grant editing permissions. I hope this helps gather feedback and encourages further discussion from the community.
Regarding the documentation, thanks for pointing that out. I have updated the PR description to explicitly state "4.1 first, backport to 4.0 to follow." I also added the reference, as suggested by Russell, to the Hilbert algorithm implementation used as the basis for this PR. In addition, I updated ` docs/docs/spark-procedures.md ` to include the `hilbert(c1,c2,....,cn)` sort strategy. If the API grammar changes during the design discussion, I'll update the documentation accordingly.
Now, moving on to the technical points.
6. SparkHilbertUDF serialization
Confirmed `testHilbertSort` exercises a genuine multi-partition shuffle on executors, so `readObject` is executed.
The test forces `TARGET_FILE_SIZE_BYTES ` to half the average file size and asserts that more than 40 output files are written from a single file group https://github.com/apache/iceberg/pull/16827/changes#diff-3f078bcb19378f3b0e2fd46061c5ddecf34f751da6d6ef97ed9f78b9d65817fbR1873-R1882. `SparkShufflingFileRewriteRunner` derives the shuffle width directly from this (numShufflePartitions = Math.max(1, expectedOutputFiles * numShufflePartitionsPerFile)), resulting in approximately 40 shuffle partitions rather than a single partition.
5. Benchmark
I completely agree that I can rerun the benchmarks under more controlled conditions, and I'm happy to do so.
That said, I believe the overall trend is already quite clear. Beyond the experimental results, there is also strong theoretical support in the literature demonstrating that Hilbert curves provide better locality preservation than Z-order. The mathematical properties of Hilbert space-filling curves have been studied extensively, and they explain why the observed improvements are expected rather than accidental.
There is also practical evidence from the data lake ecosystem: both Delta and Apache Hudi already provide Hilbert-based clustering implementations. While every implementation has its own design choices, I think their adoption provides additional confidence that this is a meaningful optimization to explore in Iceberg as well.
Regarding the suggestion to report the exact number of scanned bytes, I mentioned my reasoning previously on the dev@ thread, but I'll summarize it here as well.
In my opinion, scanned bytes are highly dependent on the storage layout and the specific Hadoop implementation. I would prefer not to introduce additional variables that could add noise to the evaluation.
In these benchmarks every data file is approx 16 MB and contains a single parquet row group. Because of the way Spark reads files, once a row group is selected it is read in its entirety. As a consequence, the number of scanned bytes is effectively proportional to the number of scanned files, making it straightforward to derive one metric from the other by multiplying by the file size.
If we want to investigate the impact of Parquet configuration parameters such as row-group sizing, page indexes, or different row-group counts per file, I think that deserves a separate discussion or follow-up issue. Those are interesting optimization topics on their own, but for this proposal I'd prefer to keep the scope focused on evaluating the geometric clustering strategy itself.
Your suggestion about measuring the impact on `MERGE`/copy-on-write operations is an excellent one.
You're absolutely right that this is currently missing from the benchmark suite, and I plan to add it.
To keep the scope manageable while still producing a meaningful comparison, I'll initially focus on metrics such as the number of ` deleted data files` during copy-on-write operations. I think this is a good proxy for write amplification and should provide a practical way to evaluate whether improved clustering translates into less data rewriting during updates.
If the results are encouraging, we can always extend the benchmark suite with additional write-path metrics in a follow-up.
Thanks again for the thoughtful review and for all the suggestions.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] API, Core, Spark: Add Hilbert-curve clustering strategy for `rewrite_data_files` [iceberg]
Posted by "RussellSpitzer (via GitHub)" <gi...@apache.org>.
RussellSpitzer commented on PR #16827:
URL: https://github.com/apache/iceberg/pull/16827#issuecomment-5373624365
Great Catch, do we have any other feedback from reviewers here? Remember we always can do followups
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] API, Core, Spark: Add Hilbert-curve clustering strategy for `rewrite_data_files` [iceberg]
Posted by "RussellSpitzer (via GitHub)" <gi...@apache.org>.
RussellSpitzer commented on code in PR #16827:
URL: https://github.com/apache/iceberg/pull/16827#discussion_r3776677662
##########
core/src/main/java/org/apache/iceberg/expressions/Hilbert.java:
##########
@@ -0,0 +1,34 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.expressions;
+
+import java.util.Arrays;
+import java.util.List;
+
+public class Hilbert implements Term {
Review Comment:
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.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] API, Core, Spark: Add Hilbert-curve clustering strategy for `rewrite_data_files` [iceberg]
Posted by "GGraziadei (via GitHub)" <gi...@apache.org>.
GGraziadei commented on PR #16827:
URL: https://github.com/apache/iceberg/pull/16827#issuecomment-5095488368
## Benchmarck
Ran the end-to-end comparison Z-Order vs Hilbert.
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.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] API, Core, Spark: Add Hilbert-curve clustering strategy for `rewrite_data_files` [iceberg]
Posted by "GGraziadei (via GitHub)" <gi...@apache.org>.
GGraziadei commented on code in PR #16827:
URL: https://github.com/apache/iceberg/pull/16827#discussion_r3692181620
##########
core/src/main/java/org/apache/iceberg/util/HilbertByteUtils.java:
##########
@@ -0,0 +1,140 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.util;
+
+import java.nio.ByteBuffer;
+import org.apache.iceberg.relocated.com.google.common.base.Preconditions;
+
+/**
+ * Maps a set of columns (each already converted to fixed-width, lexicographically-ordered unsigned
+ * bytes by {@link ZOrderByteUtils}) onto a single byte array whose unsigned big-endian
+ * lexicographic ordering follows the multi-dimensional Hilbert space-filling curve.
+ *
+ * <p>Unlike Z-ordering, the Hilbert transform requires every dimension to contribute the same
+ * number of bits, so each column is read to a fixed {@code bitsPerColumn} precision.
+ *
+ * <p>The transform is the standard "axes to transposed Hilbert index" algorithm from J. Skilling,
+ * "Programming the Hilbert curve" (2004); the transposed index is then serialized to a scalar with
+ * {@link ZOrderByteUtils#interleaveBits}.
+ */
+public class HilbertByteUtils {
+
+ private HilbertByteUtils() {}
+
+ /** See {@link #hilbertIndex(byte[][], int, ByteBuffer)}. */
+ public static byte[] hilbertIndex(byte[][] columnsBinary, int bitsPerColumn) {
+ int outputBytes = columnsBinary.length * (bitsPerColumn / 8);
+ return hilbertIndex(columnsBinary, bitsPerColumn, ByteBuffer.allocate(outputBytes));
+ }
+
+ /**
+ * Compute the Hilbert index for the given columns.
+ *
+ * @param columnsBinary one ordered-byte array per column; each must be at least {@code
+ * bitsPerColumn / 8} bytes long (only the leading bytes are used)
+ * @param bitsPerColumn bits taken from each column; a positive multiple of 8, no greater than 64
+ * @param reuse a buffer with capacity at least {@code numColumns * bitsPerColumn / 8}
+ * @return the Hilbert index, of length {@code numColumns * bitsPerColumn / 8}
+ */
+ public static byte[] hilbertIndex(byte[][] columnsBinary, int bitsPerColumn, ByteBuffer reuse) {
+ Preconditions.checkArgument(
+ bitsPerColumn > 0 && bitsPerColumn % 8 == 0,
+ "Hilbert bitsPerColumn must be a positive multiple of 8, was %s",
+ bitsPerColumn);
+ Preconditions.checkArgument(
+ bitsPerColumn <= 64,
+ "Hilbert bitsPerColumn must be no greater than 64, was %s",
+ bitsPerColumn);
+ Preconditions.checkArgument(
+ columnsBinary.length > 0, "Cannot compute a Hilbert index for zero columns");
+
+ int numColumns = columnsBinary.length;
+ int bytesPerColumn = bitsPerColumn / 8;
+
+ long[] transpose = new long[numColumns];
+ for (int i = 0; i < numColumns; i++) {
+ Preconditions.checkArgument(
+ columnsBinary[i].length >= bytesPerColumn,
+ "Column %s contributes %s bytes but %s are required",
+ i,
+ columnsBinary[i].length,
+ bytesPerColumn);
+ transpose[i] = readBigEndian(columnsBinary[i], bytesPerColumn);
+ }
+
+ axesToTranspose(transpose, bitsPerColumn);
+
+ byte[][] transposedBytes = new byte[numColumns][bytesPerColumn];
+ for (int i = 0; i < numColumns; i++) {
+ writeBigEndian(transpose[i], transposedBytes[i], bytesPerColumn);
+ }
+
+ return ZOrderByteUtils.interleaveBits(transposedBytes, numColumns * bytesPerColumn, reuse);
+ }
+
+ // please refer to the paper
Review Comment:
Hi Russell, thanks for checking the code.
I am adding the reference to J. Skilling, "Programming the Hilbert curve" (AIP Conf. Proc. 707, 381, 2004; https://doi.org/10.1063/1.1751381)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] API, Core, Spark: Add Hilbert-curve clustering strategy for `rewrite_data_files` [iceberg]
Posted by "manuzhang (via GitHub)" <gi...@apache.org>.
manuzhang commented on code in PR #16827:
URL: https://github.com/apache/iceberg/pull/16827#discussion_r3780990670
##########
spark/v4.1/spark/src/main/java/org/apache/iceberg/spark/actions/SparkHilbertFileRewriteRunner.java:
##########
@@ -0,0 +1,166 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.spark.actions;
+
+import static org.apache.spark.sql.functions.array;
+
+import java.util.List;
+import java.util.Set;
+import java.util.function.Function;
+import org.apache.iceberg.NullOrder;
+import org.apache.iceberg.Schema;
+import org.apache.iceberg.SortDirection;
+import org.apache.iceberg.SortOrder;
+import org.apache.iceberg.Table;
+import org.apache.iceberg.relocated.com.google.common.base.Preconditions;
+import org.apache.iceberg.relocated.com.google.common.collect.ImmutableList;
+import org.apache.iceberg.relocated.com.google.common.collect.Lists;
+import org.apache.iceberg.spark.SparkUtil;
+import org.apache.iceberg.types.Types;
+import org.apache.iceberg.util.ZOrderByteUtils;
+import org.apache.spark.sql.Column;
+import org.apache.spark.sql.Dataset;
+import org.apache.spark.sql.Row;
+import org.apache.spark.sql.SparkSession;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+class SparkHilbertFileRewriteRunner extends SparkShufflingFileRewriteRunner {
+ private static final Logger LOG = LoggerFactory.getLogger(SparkHilbertFileRewriteRunner.class);
+
+ private static final String H_COLUMN = "ICEHVALUE";
+ private static final Schema H_SCHEMA =
+ new Schema(Types.NestedField.required(0, H_COLUMN, Types.BinaryType.get()));
+ private static final SortOrder H_SORT_ORDER =
+ SortOrder.builderFor(H_SCHEMA)
+ .sortBy(H_COLUMN, SortDirection.ASC, NullOrder.NULLS_LAST)
+ .build();
+
+ /**
+ * The number of bits contributed by each column to the Hilbert index.
+ *
+ * <p>This is fixed at the full width of {@link ZOrderByteUtils#PRIMITIVE_BUFFER_SIZE}. A smaller,
+ * configurable width is unsafe with the shared {@link ZOrderByteUtils} encodings: whole-number
+ * types (int, date, small longs, ...) are widened into an 8-byte key with their magnitude in the
+ * low-order bytes, so truncating to fewer high-order bytes would discard all magnitude and
+ * collapse those columns to a single coordinate. Supporting a narrower width correctly would
+ * require tracking each column's significant bit width, which is out of scope here.
+ */
+ private static final int BITS_PER_COLUMN = ZOrderByteUtils.PRIMITIVE_BUFFER_SIZE * Byte.SIZE;
+
+ private final List<String> hilbertColNames;
+
+ SparkHilbertFileRewriteRunner(SparkSession spark, Table table, List<String> hilbertColNames) {
+ super(spark, table);
+ this.hilbertColNames = validHilbertColNames(spark, table, hilbertColNames);
+ }
+
+ @Override
+ public String description() {
+ return "HILBERT";
+ }
+
+ @Override
+ protected SortOrder sortOrder() {
+ return H_SORT_ORDER;
+ }
+
+ /**
+ * Overrides the sortSchema method to include columns from H_SCHEMA.
+ *
+ * <p>This method generates a new Schema object which consists of columns from the original table
+ * schema and H_SCHEMA.
+ */
+ @Override
+ protected Schema sortSchema() {
+ return new Schema(
+ new ImmutableList.Builder<Types.NestedField>()
+ .addAll(table().schema().columns())
+ .addAll(H_SCHEMA.columns())
+ .build());
+ }
+
+ @Override
+ protected Dataset<Row> sortedDF(Dataset<Row> df, Function<Dataset<Row>, Dataset<Row>> sortFunc) {
+ Dataset<Row> hValueDF = df.withColumn(H_COLUMN, hilbertValue(df));
+ Dataset<Row> sortedDF = sortFunc.apply(hValueDF);
+ return sortedDF.drop(H_COLUMN);
+ }
+
+ private Column hilbertValue(Dataset<Row> df) {
+ // Reuse the Z-order byte conversions. Every column contributes the full primitive width so the
+ // Hilbert transform sees a uniform per-dimension width with no magnitude loss.
+ SparkZOrderUDF byteUDF =
+ new SparkZOrderUDF(
+ hilbertColNames.size(), ZOrderByteUtils.PRIMITIVE_BUFFER_SIZE, Integer.MAX_VALUE);
+
+ Column[] orderedCols =
+ hilbertColNames.stream()
+ .map(df.schema()::apply)
+ .map(col -> byteUDF.sortedLexicographically(df.col(col.name()), col.dataType()))
+ .toArray(Column[]::new);
+
+ SparkHilbertUDF hilbertUDF = new SparkHilbertUDF(hilbertColNames.size(), BITS_PER_COLUMN);
+ return hilbertUDF.hilbertValue(array(orderedCols));
+ }
+
+ private List<String> validHilbertColNames(
+ SparkSession spark, Table table, List<String> inputHilbertColNames) {
+
+ Preconditions.checkArgument(
+ inputHilbertColNames != null && !inputHilbertColNames.isEmpty(),
+ "Cannot HILBERT when no columns are specified");
+
+ Schema schema = table.schema();
+ Set<Integer> identityPartitionFieldIds = table.spec().identitySourceIds();
+ boolean caseSensitive = SparkUtil.caseSensitive(spark);
Review Comment:
When case sensitivity being disabled, validation can pass but the caller's spelling is retained. It could eventually fail with FIELD_NOT_FOUND exception.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] API, Core, Spark: Add Hilbert-curve clustering strategy for `rewrite_data_files` [iceberg]
Posted by "GGraziadei (via GitHub)" <gi...@apache.org>.
GGraziadei commented on code in PR #16827:
URL: https://github.com/apache/iceberg/pull/16827#discussion_r3785542721
##########
spark/v4.1/spark/src/main/java/org/apache/iceberg/spark/actions/SparkHilbertFileRewriteRunner.java:
##########
@@ -0,0 +1,166 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.spark.actions;
+
+import static org.apache.spark.sql.functions.array;
+
+import java.util.List;
+import java.util.Set;
+import java.util.function.Function;
+import org.apache.iceberg.NullOrder;
+import org.apache.iceberg.Schema;
+import org.apache.iceberg.SortDirection;
+import org.apache.iceberg.SortOrder;
+import org.apache.iceberg.Table;
+import org.apache.iceberg.relocated.com.google.common.base.Preconditions;
+import org.apache.iceberg.relocated.com.google.common.collect.ImmutableList;
+import org.apache.iceberg.relocated.com.google.common.collect.Lists;
+import org.apache.iceberg.spark.SparkUtil;
+import org.apache.iceberg.types.Types;
+import org.apache.iceberg.util.ZOrderByteUtils;
+import org.apache.spark.sql.Column;
+import org.apache.spark.sql.Dataset;
+import org.apache.spark.sql.Row;
+import org.apache.spark.sql.SparkSession;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+class SparkHilbertFileRewriteRunner extends SparkShufflingFileRewriteRunner {
Review Comment:
Thanks! I compacted the concers about this topic in this follow-up issue:
https://github.com/apache/iceberg/issues/17657
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] API, Core, Spark: Add Hilbert-curve clustering strategy for `rewrite_data_files` [iceberg]
Posted by "GGraziadei (via GitHub)" <gi...@apache.org>.
GGraziadei commented on code in PR #16827:
URL: https://github.com/apache/iceberg/pull/16827#discussion_r3785518163
##########
core/src/main/java/org/apache/iceberg/expressions/Hilbert.java:
##########
@@ -0,0 +1,34 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.expressions;
+
+import java.util.Arrays;
+import java.util.List;
+
+public class Hilbert implements Term {
Review Comment:
Thanks. I formalized these points in the issue below, incorporating also the Neelesh's feedback and condensing the main takeaways:
https://github.com/apache/iceberg/issues/17657
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] API, Core, Spark: Add Hilbert-curve clustering strategy for `rewrite_data_files` [iceberg]
Posted by "nssalian (via GitHub)" <gi...@apache.org>.
nssalian commented on code in PR #16827:
URL: https://github.com/apache/iceberg/pull/16827#discussion_r3779006716
##########
spark/v4.1/spark/src/main/java/org/apache/iceberg/spark/actions/SparkHilbertUDF.java:
##########
@@ -0,0 +1,70 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.spark.actions;
+
+import java.io.IOException;
+import java.io.ObjectInputStream;
+import java.io.Serializable;
+import java.nio.ByteBuffer;
+import org.apache.iceberg.util.HilbertByteUtils;
+import org.apache.spark.sql.Column;
+import org.apache.spark.sql.expressions.UserDefinedFunction;
+import org.apache.spark.sql.functions;
+import org.apache.spark.sql.types.DataTypes;
+import scala.collection.JavaConverters;
+import scala.collection.Seq;
+
+/**
+ * Combines per-column ordered bytes (produced by {@link SparkZOrderUDF#sortedLexicographically})
+ * into a single Hilbert-curve value. Mirrors the combine step of {@link SparkZOrderUDF}
+ * (interleave), replacing it with {@link HilbertByteUtils#hilbertIndex}.
+ */
+class SparkHilbertUDF implements Serializable {
+
+ private transient ThreadLocal<ByteBuffer> outputBuffer;
+
+ private final int numCols;
+ private final int bitsPerColumn;
+ private final int outputBytes;
+
+ SparkHilbertUDF(int numCols, int bitsPerColumn) {
+ this.numCols = numCols;
+ this.bitsPerColumn = bitsPerColumn;
+ this.outputBytes = numCols * (bitsPerColumn / 8);
+ }
+
+ private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
+ in.defaultReadObject();
+ outputBuffer = ThreadLocal.withInitial(() -> ByteBuffer.allocate(outputBytes));
+ }
+
+ private byte[] hilbertValue(Seq<byte[]> scalaBinary) {
+ byte[][] columnsBinary = JavaConverters.seqAsJavaList(scalaBinary).toArray(new byte[numCols][]);
Review Comment:
allocates a fresh `new byte[numCols][]` holder on every row, whereas the class it mirrors, `SparkZOrderUDF`, reuses a `ThreadLocal<byte[][]> inputHolder` (`.toArray(inputHolder.get())`). Should be an easy fix is by adding a transient `ThreadLocal<byte[][]>` reinitialized in `readObject`
##########
spark/v4.1/spark/src/main/java/org/apache/iceberg/spark/Spark3Util.java:
##########
@@ -400,6 +402,12 @@ public static Term toIcebergTerm(Expression expr) {
.map(ref -> DOT.join(ref.fieldNames()))
.map(org.apache.iceberg.expressions.Expressions::ref)
.collect(Collectors.toList()));
+ case "hilbert":
+ return new org.apache.iceberg.expressions.Hilbert(
Review Comment:
can we use the imported name like ZOrder versus the fully qualified import?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] API, Core, Spark: Add Hilbert-curve clustering strategy for `rewrite_data_files` [iceberg]
Posted by "GGraziadei (via GitHub)" <gi...@apache.org>.
GGraziadei commented on code in PR #16827:
URL: https://github.com/apache/iceberg/pull/16827#discussion_r3785589983
##########
spark/v4.1/spark/src/main/java/org/apache/iceberg/spark/actions/SparkHilbertUDF.java:
##########
@@ -0,0 +1,70 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.spark.actions;
+
+import java.io.IOException;
+import java.io.ObjectInputStream;
+import java.io.Serializable;
+import java.nio.ByteBuffer;
+import org.apache.iceberg.util.HilbertByteUtils;
+import org.apache.spark.sql.Column;
+import org.apache.spark.sql.expressions.UserDefinedFunction;
+import org.apache.spark.sql.functions;
+import org.apache.spark.sql.types.DataTypes;
+import scala.collection.JavaConverters;
+import scala.collection.Seq;
+
+/**
+ * Combines per-column ordered bytes (produced by {@link SparkZOrderUDF#sortedLexicographically})
+ * into a single Hilbert-curve value. Mirrors the combine step of {@link SparkZOrderUDF}
+ * (interleave), replacing it with {@link HilbertByteUtils#hilbertIndex}.
+ */
+class SparkHilbertUDF implements Serializable {
+
+ private transient ThreadLocal<ByteBuffer> outputBuffer;
+
+ private final int numCols;
+ private final int bitsPerColumn;
+ private final int outputBytes;
+
+ SparkHilbertUDF(int numCols, int bitsPerColumn) {
+ this.numCols = numCols;
+ this.bitsPerColumn = bitsPerColumn;
+ this.outputBytes = numCols * (bitsPerColumn / 8);
+ }
+
+ private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
+ in.defaultReadObject();
+ outputBuffer = ThreadLocal.withInitial(() -> ByteBuffer.allocate(outputBytes));
+ }
+
+ private byte[] hilbertValue(Seq<byte[]> scalaBinary) {
+ byte[][] columnsBinary = JavaConverters.seqAsJavaList(scalaBinary).toArray(new byte[numCols][]);
Review Comment:
Fixed. Added a `transient ThreadLocal<byte[][]> inputHolder` re-initialised in `readObject`
and switched to `.toArray(inputHolder.get())`, matching `SparkZOrderUDF`.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] API, Core, Spark: Add Hilbert-curve clustering strategy for `rewrite_data_files` [iceberg]
Posted by "GGraziadei (via GitHub)" <gi...@apache.org>.
GGraziadei commented on code in PR #16827:
URL: https://github.com/apache/iceberg/pull/16827#discussion_r3785554640
##########
spark/v4.1/spark/src/test/java/org/apache/iceberg/spark/actions/TestRewriteDataFilesAction.java:
##########
@@ -1831,6 +1831,84 @@ public void testZOrderSort() {
.isGreaterThan(filesScannedC2C3);
}
+ @TestTemplate
+ public void testHilbertWithHColumnCollision() {
Review Comment:
Thanks, I adeguated to the style rules!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] API, Core, Spark: Add Hilbert-curve clustering strategy for `rewrite_data_files` [iceberg]
Posted by "nssalian (via GitHub)" <gi...@apache.org>.
nssalian commented on code in PR #16827:
URL: https://github.com/apache/iceberg/pull/16827#discussion_r3779003615
##########
spark/v4.1/spark/src/test/java/org/apache/iceberg/spark/actions/TestSparkFileRewriteRunners.java:
##########
@@ -136,4 +136,38 @@ public void testInvalidValuesForZOrderDataOptions() {
.hasMessageContaining("Cannot use less than 1 byte for variable length types with ZOrder")
.hasMessageContaining("'var-length-contribution' was set to 0");
}
+
+ @Test
+ public void testInvalidConstructorUsagesHilbertData() {
Review Comment:
Some enhancement suggestions: could you add a column-not-found case (hilbert("nonexistent")) and a mixed identity+data case (hilbert("dep", "id")) to testInvalidConstructorUsagesHilbertData, plus a zero-columns case (hilbertIndex(new byte[0][], 8)) in TestHilbertByteUtils, to cover the "Cannot find column", identity-filtering, and "zero columns" guards?
##########
core/src/main/java/org/apache/iceberg/util/HilbertByteUtils.java:
##########
@@ -0,0 +1,141 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.util;
+
+import java.nio.ByteBuffer;
+import org.apache.iceberg.relocated.com.google.common.base.Preconditions;
+
+/**
+ * Maps a set of columns (each already converted to fixed-width, lexicographically-ordered unsigned
+ * bytes by {@link ZOrderByteUtils}) onto a single byte array whose unsigned big-endian
+ * lexicographic ordering follows the multi-dimensional Hilbert space-filling curve.
+ *
+ * <p>Unlike Z-ordering, the Hilbert transform requires every dimension to contribute the same
+ * number of bits, so each column is read to a fixed {@code bitsPerColumn} precision.
+ *
+ * <p>The transform is the standard "axes to transposed Hilbert index" algorithm from J. Skilling,
+ * "Programming the Hilbert curve" (2004); the transposed index is then serialized to a scalar with
Review Comment:
nit: do we want to copy the full reference with the citation here?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] API, Core, Spark: Add Hilbert-curve clustering strategy for `rewrite_data_files` [iceberg]
Posted by "GGraziadei (via GitHub)" <gi...@apache.org>.
GGraziadei commented on PR #16827:
URL: https://github.com/apache/iceberg/pull/16827#issuecomment-5402048757
Hi @nssalian, thanks for your comment—it helped clarify the feature for me. Here are the next steps I’m planning:
* **Spark:** Backport Hilbert-curve sort compaction to Spark 4.0 and 3.5 — #17805
* **ZOrderByteUtils:** `interleaveBits` currently interleaves one bit at a time; using a bit-spreading table is 7–9× faster (in practice, ~10×) — #17758 *(1 approval)*
* **Z-order:** Fix NPEs on null booleans and case-insensitive column resolution — #17669 *(1 approval)*
* **Shared multi-column term:** Introduce a shared term to de-duplicate Z-order and Hilbert clustering — #17657
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] API, Core, Spark: Add Hilbert-curve clustering strategy for `rewrite_data_files` [iceberg]
Posted by "manuzhang (via GitHub)" <gi...@apache.org>.
manuzhang commented on code in PR #16827:
URL: https://github.com/apache/iceberg/pull/16827#discussion_r3781026230
##########
spark/v4.1/spark/src/test/java/org/apache/iceberg/spark/actions/TestRewriteDataFilesAction.java:
##########
@@ -1831,6 +1831,84 @@ public void testZOrderSort() {
.isGreaterThan(filesScannedC2C3);
}
+ @TestTemplate
+ public void testHilbertWithHColumnCollision() {
Review Comment:
avoid using test prefix for new tests.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] API, Core, Spark: Add Hilbert-curve clustering strategy for `rewrite_data_files` [iceberg]
Posted by "manuzhang (via GitHub)" <gi...@apache.org>.
manuzhang commented on code in PR #16827:
URL: https://github.com/apache/iceberg/pull/16827#discussion_r3780990670
##########
spark/v4.1/spark/src/main/java/org/apache/iceberg/spark/actions/SparkHilbertFileRewriteRunner.java:
##########
@@ -0,0 +1,166 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.spark.actions;
+
+import static org.apache.spark.sql.functions.array;
+
+import java.util.List;
+import java.util.Set;
+import java.util.function.Function;
+import org.apache.iceberg.NullOrder;
+import org.apache.iceberg.Schema;
+import org.apache.iceberg.SortDirection;
+import org.apache.iceberg.SortOrder;
+import org.apache.iceberg.Table;
+import org.apache.iceberg.relocated.com.google.common.base.Preconditions;
+import org.apache.iceberg.relocated.com.google.common.collect.ImmutableList;
+import org.apache.iceberg.relocated.com.google.common.collect.Lists;
+import org.apache.iceberg.spark.SparkUtil;
+import org.apache.iceberg.types.Types;
+import org.apache.iceberg.util.ZOrderByteUtils;
+import org.apache.spark.sql.Column;
+import org.apache.spark.sql.Dataset;
+import org.apache.spark.sql.Row;
+import org.apache.spark.sql.SparkSession;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+class SparkHilbertFileRewriteRunner extends SparkShufflingFileRewriteRunner {
+ private static final Logger LOG = LoggerFactory.getLogger(SparkHilbertFileRewriteRunner.class);
+
+ private static final String H_COLUMN = "ICEHVALUE";
+ private static final Schema H_SCHEMA =
+ new Schema(Types.NestedField.required(0, H_COLUMN, Types.BinaryType.get()));
+ private static final SortOrder H_SORT_ORDER =
+ SortOrder.builderFor(H_SCHEMA)
+ .sortBy(H_COLUMN, SortDirection.ASC, NullOrder.NULLS_LAST)
+ .build();
+
+ /**
+ * The number of bits contributed by each column to the Hilbert index.
+ *
+ * <p>This is fixed at the full width of {@link ZOrderByteUtils#PRIMITIVE_BUFFER_SIZE}. A smaller,
+ * configurable width is unsafe with the shared {@link ZOrderByteUtils} encodings: whole-number
+ * types (int, date, small longs, ...) are widened into an 8-byte key with their magnitude in the
+ * low-order bytes, so truncating to fewer high-order bytes would discard all magnitude and
+ * collapse those columns to a single coordinate. Supporting a narrower width correctly would
+ * require tracking each column's significant bit width, which is out of scope here.
+ */
+ private static final int BITS_PER_COLUMN = ZOrderByteUtils.PRIMITIVE_BUFFER_SIZE * Byte.SIZE;
+
+ private final List<String> hilbertColNames;
+
+ SparkHilbertFileRewriteRunner(SparkSession spark, Table table, List<String> hilbertColNames) {
+ super(spark, table);
+ this.hilbertColNames = validHilbertColNames(spark, table, hilbertColNames);
+ }
+
+ @Override
+ public String description() {
+ return "HILBERT";
+ }
+
+ @Override
+ protected SortOrder sortOrder() {
+ return H_SORT_ORDER;
+ }
+
+ /**
+ * Overrides the sortSchema method to include columns from H_SCHEMA.
+ *
+ * <p>This method generates a new Schema object which consists of columns from the original table
+ * schema and H_SCHEMA.
+ */
+ @Override
+ protected Schema sortSchema() {
+ return new Schema(
+ new ImmutableList.Builder<Types.NestedField>()
+ .addAll(table().schema().columns())
+ .addAll(H_SCHEMA.columns())
+ .build());
+ }
+
+ @Override
+ protected Dataset<Row> sortedDF(Dataset<Row> df, Function<Dataset<Row>, Dataset<Row>> sortFunc) {
+ Dataset<Row> hValueDF = df.withColumn(H_COLUMN, hilbertValue(df));
+ Dataset<Row> sortedDF = sortFunc.apply(hValueDF);
+ return sortedDF.drop(H_COLUMN);
+ }
+
+ private Column hilbertValue(Dataset<Row> df) {
+ // Reuse the Z-order byte conversions. Every column contributes the full primitive width so the
+ // Hilbert transform sees a uniform per-dimension width with no magnitude loss.
+ SparkZOrderUDF byteUDF =
+ new SparkZOrderUDF(
+ hilbertColNames.size(), ZOrderByteUtils.PRIMITIVE_BUFFER_SIZE, Integer.MAX_VALUE);
+
+ Column[] orderedCols =
+ hilbertColNames.stream()
+ .map(df.schema()::apply)
+ .map(col -> byteUDF.sortedLexicographically(df.col(col.name()), col.dataType()))
+ .toArray(Column[]::new);
+
+ SparkHilbertUDF hilbertUDF = new SparkHilbertUDF(hilbertColNames.size(), BITS_PER_COLUMN);
+ return hilbertUDF.hilbertValue(array(orderedCols));
+ }
+
+ private List<String> validHilbertColNames(
+ SparkSession spark, Table table, List<String> inputHilbertColNames) {
+
+ Preconditions.checkArgument(
+ inputHilbertColNames != null && !inputHilbertColNames.isEmpty(),
+ "Cannot HILBERT when no columns are specified");
+
+ Schema schema = table.schema();
+ Set<Integer> identityPartitionFieldIds = table.spec().identitySourceIds();
+ boolean caseSensitive = SparkUtil.caseSensitive(spark);
Review Comment:
When case sensitivity being disabled, validation can pass but the caller's spelling is retained. It will eventually fail with FIELD_NOT_FOUND exception.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] API, Core, Spark: Add Hilbert-curve clustering strategy for `rewrite_data_files` [iceberg]
Posted by "GGraziadei (via GitHub)" <gi...@apache.org>.
GGraziadei commented on PR #16827:
URL: https://github.com/apache/iceberg/pull/16827#issuecomment-5361125612
## JMH: Hilbert curve math vs Z-order interleaving
Answering the question about whether the JMH run compares against Z-order interleaving on the same inputs, and the request for a relative number. It does, and the figures are below.
> **Scope note.** Sections 1, 2 and 4 describe the branch as pushed. Section 3 measures an allocation fix that is **not yet pushed**; it is reported here because the benchmark is what surfaced the defect, but the current diff does not yet contain it.
### Method
`HilbertByteUtilsBenchmark` and `ZOrderByteUtilsBenchmark` are structurally matched: identical `NUM_ENTRIES = 10_000_000`, identical `new Random(42)` seed, identical setup loop. Both arms therefore see byte-for-byte identical input, and both were executed in a single JMH invocation so they share one JIT and GC context.
```
JMH 1.37 · JDK 17.0.19 · 1 fork · 1 thread · SingleShotTime
5 warmup + 15 measurement iterations · -Xmx8g · gc profiler
1 op = one pass over 10M rows, 64 bits per column
```
One methodological caveat worth stating up front: the committed benchmark classes declare no `@Warmup` and only 5 iterations. Measured that way, confidence intervals reach ±43% and — more seriously — the reported allocation rates are dominated by JIT compilation artifacts rather than by the code under test. Running the unmodified Z-order benchmark under the two configurations yields 396 MB/op without warmup versus 3.71 MB/op with it, a two-order-of-magnitude discrepancy attributable entirely to measurement rather than to any code change. All figures below use warmup and 15 iterations and are consequently **not** comparable to a default run of the committed classes.
### 1. Time
```
s/op, lower is better
2 cols Hilbert ████████████████████████▏ 14.64
Z-order ██████▏ 3.71
3 cols Hilbert ███████████████████████████████▌ 19.09
Z-order █████████ 5.43
4 cols Hilbert ██████████████████████████████████████ 22.88
Z-order ████████████▏ 7.45
```
| Columns | Hilbert (s/op) | Z-order (s/op) | Ratio | Added cost |
|--------:|---------------:|---------------:|------:|-----------:|
| 2 | 14.644 ± 0.447 | 3.707 ± 0.119 | 3.95x | +1.09 µs/row |
| 3 | 19.094 ± 0.512 | 5.433 ± 0.100 | 3.51x | +1.37 µs/row |
| 4 | 22.881 ± 0.537 | 7.452 ± 0.278 | 3.07x | +1.54 µs/row |
**`hilbertIndex` costs 3.1–4.0x a pure Z-order interleave on identical inputs.** This is a structural rather than incidental result: `hilbertIndex` issues the same `ZOrderByteUtils.interleaveBits` call and adds `axesToTranspose` on top, so the ratio is precisely the price of the curve transform. The ratio decreases with dimensionality because the interleave grows linearly in the number of columns while the transpose does not.
### 2. Attribution
Stack profiler, 4 columns, percentages of RUNNABLE thread state.
```
Hilbert Z-order
axesToTranspose ██████ 30.8% interleaveBits ██████████ 49.8%
interleaveBits ███ 15.1% unattributed ██████████ 50.0%
hilbertIndex ▌ 3.1%
read/writeBigEndian ▏ 0.8%
unattributed ██████████ 50.0%
```
Within Hilbert the curve transform costs approximately twice the interleave it wraps (30.8% versus 15.1%), which corroborates the ~3x aggregate through an independent measurement path. Half the samples are unattributed, which is expected for a sampling profiler against inlined frames; these proportions should be read as indicative rather than exact.
### 3. Allocation
The benchmark surfaced a defect worth fixing independently of the timing question. `hilbertIndex` allocated a `long[numColumns]` and a `new byte[numColumns][bytesPerColumn]` **per invocation**, i.e. per row, while the output `ByteBuffer` was already correctly reused. At four columns that is six objects per row and 60M objects per pass.
```
bytes per op, log10 scale
before Hilbert ███████████████████████████████████ 1.77 GB
Z-order ████████████████████████▌ 3.71 MB
after Hilbert ██████████████▌ 6.7 KB
Z-order ██████████████▌ 6.6 KB
```
| | Hilbert | Z-order |
|---|---:|---:|
| before | 1.774 GB/op, 8 GC pauses | 3.711 MB/op, 0 GC pauses |
| after | 6 743 B/op, 0 GC pauses | 6 570 B/op, 0 GC pauses |
The remedy is an overload accepting caller-owned scratch — the same `reuse` convention `ZOrderByteUtils` applies throughout — with `SparkHilbertUDF` holding it in the `ThreadLocal`s it already maintains. The three-argument overload is unchanged and still allocates, so no existing caller is affected. The residual ~6.6 KB/op is JMH's own per-op baseline and is identical across both arms.
**Hilbert now allocates no more than Z-order, and neither triggers a single garbage collection across 10M rows.**
### 4. Interpretation and limits
- **The allocation fix produced no measurable time improvement** (−0.2%, +2.6%, −9.5% across the three widths). The inconsistent signs identify this as noise. The −9.5% at four columns is regression to the mean of a prior outlier, whose interval was ±2.463 before and ±0.537 after. This is the expected outcome: the objects were short-lived and young-generation-cheap, and GC accounted for 0.5% of wall time even before the fix. The benefit is reduced allocator pressure across concurrent Spark tasks, which a single-threaded micro-benchmark cannot exhibit.
- **The 3x applies to the combine step in isolation.** In an end-to-end rewrite that step is a minor term next to I/O, shuffle, and the per-column ordered-byte conversion. The measured end-to-end penalty is **+15.4%** (169.8s → 196.0s), and the gap between 3x and 15.4% is itself evidence that the combine does not dominate.
- **Absolute values are machine-specific.** These were collected on a developer workstation with other applications resident. Since both arms executed in the same fork against the same inputs, the Hilbert-to-Z-order ratio is the robust quantity; the absolute s/op figures are not.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] API, Core, Spark: Add Hilbert-curve clustering strategy for `rewrite_data_files` [iceberg]
Posted by "RussellSpitzer (via GitHub)" <gi...@apache.org>.
RussellSpitzer commented on code in PR #16827:
URL: https://github.com/apache/iceberg/pull/16827#discussion_r3692294720
##########
core/src/main/java/org/apache/iceberg/util/HilbertByteUtils.java:
##########
@@ -0,0 +1,140 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.util;
+
+import java.nio.ByteBuffer;
+import org.apache.iceberg.relocated.com.google.common.base.Preconditions;
+
+/**
+ * Maps a set of columns (each already converted to fixed-width, lexicographically-ordered unsigned
+ * bytes by {@link ZOrderByteUtils}) onto a single byte array whose unsigned big-endian
+ * lexicographic ordering follows the multi-dimensional Hilbert space-filling curve.
+ *
+ * <p>Unlike Z-ordering, the Hilbert transform requires every dimension to contribute the same
+ * number of bits, so each column is read to a fixed {@code bitsPerColumn} precision.
+ *
+ * <p>The transform is the standard "axes to transposed Hilbert index" algorithm from J. Skilling,
+ * "Programming the Hilbert curve" (2004); the transposed index is then serialized to a scalar with
+ * {@link ZOrderByteUtils#interleaveBits}.
+ */
+public class HilbertByteUtils {
+
+ private HilbertByteUtils() {}
+
+ /** See {@link #hilbertIndex(byte[][], int, ByteBuffer)}. */
+ public static byte[] hilbertIndex(byte[][] columnsBinary, int bitsPerColumn) {
+ int outputBytes = columnsBinary.length * (bitsPerColumn / 8);
+ return hilbertIndex(columnsBinary, bitsPerColumn, ByteBuffer.allocate(outputBytes));
+ }
+
+ /**
+ * Compute the Hilbert index for the given columns.
+ *
+ * @param columnsBinary one ordered-byte array per column; each must be at least {@code
+ * bitsPerColumn / 8} bytes long (only the leading bytes are used)
+ * @param bitsPerColumn bits taken from each column; a positive multiple of 8, no greater than 64
+ * @param reuse a buffer with capacity at least {@code numColumns * bitsPerColumn / 8}
+ * @return the Hilbert index, of length {@code numColumns * bitsPerColumn / 8}
+ */
+ public static byte[] hilbertIndex(byte[][] columnsBinary, int bitsPerColumn, ByteBuffer reuse) {
+ Preconditions.checkArgument(
+ bitsPerColumn > 0 && bitsPerColumn % 8 == 0,
+ "Hilbert bitsPerColumn must be a positive multiple of 8, was %s",
+ bitsPerColumn);
+ Preconditions.checkArgument(
+ bitsPerColumn <= 64,
+ "Hilbert bitsPerColumn must be no greater than 64, was %s",
+ bitsPerColumn);
+ Preconditions.checkArgument(
+ columnsBinary.length > 0, "Cannot compute a Hilbert index for zero columns");
+
+ int numColumns = columnsBinary.length;
+ int bytesPerColumn = bitsPerColumn / 8;
+
+ long[] transpose = new long[numColumns];
+ for (int i = 0; i < numColumns; i++) {
+ Preconditions.checkArgument(
+ columnsBinary[i].length >= bytesPerColumn,
+ "Column %s contributes %s bytes but %s are required",
+ i,
+ columnsBinary[i].length,
+ bytesPerColumn);
+ transpose[i] = readBigEndian(columnsBinary[i], bytesPerColumn);
+ }
+
+ axesToTranspose(transpose, bitsPerColumn);
+
+ byte[][] transposedBytes = new byte[numColumns][bytesPerColumn];
+ for (int i = 0; i < numColumns; i++) {
+ writeBigEndian(transpose[i], transposedBytes[i], bytesPerColumn);
+ }
+
+ return ZOrderByteUtils.interleaveBits(transposedBytes, numColumns * bytesPerColumn, reuse);
+ }
+
+ // please refer to the paper
Review Comment:
I'll go through the rest later, just skimmed by and it looked solid to me. I'm off next week though
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] API, Core, Spark: Add Hilbert-curve clustering strategy for `rewrite_data_files` [iceberg]
Posted by "RussellSpitzer (via GitHub)" <gi...@apache.org>.
RussellSpitzer commented on code in PR #16827:
URL: https://github.com/apache/iceberg/pull/16827#discussion_r3776875514
##########
core/src/main/java/org/apache/iceberg/util/HilbertByteUtils.java:
##########
@@ -0,0 +1,141 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.util;
+
+import java.nio.ByteBuffer;
+import org.apache.iceberg.relocated.com.google.common.base.Preconditions;
+
+/**
+ * Maps a set of columns (each already converted to fixed-width, lexicographically-ordered unsigned
+ * bytes by {@link ZOrderByteUtils}) onto a single byte array whose unsigned big-endian
+ * lexicographic ordering follows the multi-dimensional Hilbert space-filling curve.
+ *
+ * <p>Unlike Z-ordering, the Hilbert transform requires every dimension to contribute the same
+ * number of bits, so each column is read to a fixed {@code bitsPerColumn} precision.
+ *
+ * <p>The transform is the standard "axes to transposed Hilbert index" algorithm from J. Skilling,
Review Comment:
Please add the full reference here too
* J. Skilling, "Programming the Hilbert curve," AIP Conf. Proc. 707, 381 (2004).
* https://doi.org/10.1063/1.1751381
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] API, Core, Spark: Add Hilbert-curve clustering strategy for `rewrite_data_files` [iceberg]
Posted by "gimgit (via GitHub)" <gi...@apache.org>.
gimgit commented on PR #16827:
URL: https://github.com/apache/iceberg/pull/16827#issuecomment-5363530778
Nice — 1.7 GB/op to ~6.7 KB/op from buffering the transpose is a great outcome, and the matched-arm JMH setup (same seed, single invocation) makes the 3-4x curve cost a number reviewers can actually trust. Glad the question was useful.
On locality-as-density-variance: that framing makes sense for space-filling curves, and it's a better fit than per-column bounds there. Looking forward to the follow-up issue — happy to compare notes with the linear-order detection in #17504 once it's up.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] API, Core, Spark: Add Hilbert-curve clustering strategy for `rewrite_data_files` [iceberg]
Posted by "GGraziadei (via GitHub)" <gi...@apache.org>.
GGraziadei commented on code in PR #16827:
URL: https://github.com/apache/iceberg/pull/16827#discussion_r3785562696
##########
spark/v4.1/spark/src/main/java/org/apache/iceberg/spark/actions/SparkHilbertFileRewriteRunner.java:
##########
@@ -0,0 +1,166 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.spark.actions;
+
+import static org.apache.spark.sql.functions.array;
+
+import java.util.List;
+import java.util.Set;
+import java.util.function.Function;
+import org.apache.iceberg.NullOrder;
+import org.apache.iceberg.Schema;
+import org.apache.iceberg.SortDirection;
+import org.apache.iceberg.SortOrder;
+import org.apache.iceberg.Table;
+import org.apache.iceberg.relocated.com.google.common.base.Preconditions;
+import org.apache.iceberg.relocated.com.google.common.collect.ImmutableList;
+import org.apache.iceberg.relocated.com.google.common.collect.Lists;
+import org.apache.iceberg.spark.SparkUtil;
+import org.apache.iceberg.types.Types;
+import org.apache.iceberg.util.ZOrderByteUtils;
+import org.apache.spark.sql.Column;
+import org.apache.spark.sql.Dataset;
+import org.apache.spark.sql.Row;
+import org.apache.spark.sql.SparkSession;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+class SparkHilbertFileRewriteRunner extends SparkShufflingFileRewriteRunner {
+ private static final Logger LOG = LoggerFactory.getLogger(SparkHilbertFileRewriteRunner.class);
+
+ private static final String H_COLUMN = "ICEHVALUE";
+ private static final Schema H_SCHEMA =
+ new Schema(Types.NestedField.required(0, H_COLUMN, Types.BinaryType.get()));
+ private static final SortOrder H_SORT_ORDER =
+ SortOrder.builderFor(H_SCHEMA)
+ .sortBy(H_COLUMN, SortDirection.ASC, NullOrder.NULLS_LAST)
+ .build();
+
+ /**
+ * The number of bits contributed by each column to the Hilbert index.
+ *
+ * <p>This is fixed at the full width of {@link ZOrderByteUtils#PRIMITIVE_BUFFER_SIZE}. A smaller,
+ * configurable width is unsafe with the shared {@link ZOrderByteUtils} encodings: whole-number
+ * types (int, date, small longs, ...) are widened into an 8-byte key with their magnitude in the
+ * low-order bytes, so truncating to fewer high-order bytes would discard all magnitude and
+ * collapse those columns to a single coordinate. Supporting a narrower width correctly would
+ * require tracking each column's significant bit width, which is out of scope here.
+ */
+ private static final int BITS_PER_COLUMN = ZOrderByteUtils.PRIMITIVE_BUFFER_SIZE * Byte.SIZE;
+
+ private final List<String> hilbertColNames;
+
+ SparkHilbertFileRewriteRunner(SparkSession spark, Table table, List<String> hilbertColNames) {
+ super(spark, table);
+ this.hilbertColNames = validHilbertColNames(spark, table, hilbertColNames);
+ }
+
+ @Override
+ public String description() {
+ return "HILBERT";
+ }
+
+ @Override
+ protected SortOrder sortOrder() {
+ return H_SORT_ORDER;
+ }
+
+ /**
+ * Overrides the sortSchema method to include columns from H_SCHEMA.
+ *
+ * <p>This method generates a new Schema object which consists of columns from the original table
+ * schema and H_SCHEMA.
+ */
+ @Override
+ protected Schema sortSchema() {
+ return new Schema(
+ new ImmutableList.Builder<Types.NestedField>()
+ .addAll(table().schema().columns())
+ .addAll(H_SCHEMA.columns())
+ .build());
+ }
+
+ @Override
+ protected Dataset<Row> sortedDF(Dataset<Row> df, Function<Dataset<Row>, Dataset<Row>> sortFunc) {
+ Dataset<Row> hValueDF = df.withColumn(H_COLUMN, hilbertValue(df));
+ Dataset<Row> sortedDF = sortFunc.apply(hValueDF);
+ return sortedDF.drop(H_COLUMN);
+ }
+
+ private Column hilbertValue(Dataset<Row> df) {
+ // Reuse the Z-order byte conversions. Every column contributes the full primitive width so the
+ // Hilbert transform sees a uniform per-dimension width with no magnitude loss.
+ SparkZOrderUDF byteUDF =
+ new SparkZOrderUDF(
Review Comment:
Thanks, this is a real bug. I created a dedicated issue https://github.com/apache/iceberg/issues/17658
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] API, Core, Spark: Add Hilbert-curve clustering strategy for `rewrite_data_files` [iceberg]
Posted by "RussellSpitzer (via GitHub)" <gi...@apache.org>.
RussellSpitzer merged PR #16827:
URL: https://github.com/apache/iceberg/pull/16827
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] API, Core, Spark: Add Hilbert-curve clustering strategy for `rewrite_data_files` [iceberg]
Posted by "GGraziadei (via GitHub)" <gi...@apache.org>.
GGraziadei commented on PR #16827:
URL: https://github.com/apache/iceberg/pull/16827#issuecomment-4996169040
Hi @RussellSpitzer and @singhpk234 ,
Since you both worked heavily on Z-Order implementation and compaction/rewrite actions, I'd love to get your thoughts on this PR.
I am introducing Hilbert space-filling clustering (conceptually aligned with liquid clustering) to optimize multidimensional sorting and layout in Iceberg.
Given your deep expertise in this specific area, your feedback on how this hooks into the existing `RewriteDataFiles` strategies and the overall sorting logic would be incredibly valuable.
Whenever you have some time, I’d highly appreciate it if you could take a look!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] API, Core, Spark: Add Hilbert-curve clustering strategy for `rewrite_data_files` [iceberg]
Posted by "GGraziadei (via GitHub)" <gi...@apache.org>.
GGraziadei commented on code in PR #16827:
URL: https://github.com/apache/iceberg/pull/16827#discussion_r3785562696
##########
spark/v4.1/spark/src/main/java/org/apache/iceberg/spark/actions/SparkHilbertFileRewriteRunner.java:
##########
@@ -0,0 +1,166 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.spark.actions;
+
+import static org.apache.spark.sql.functions.array;
+
+import java.util.List;
+import java.util.Set;
+import java.util.function.Function;
+import org.apache.iceberg.NullOrder;
+import org.apache.iceberg.Schema;
+import org.apache.iceberg.SortDirection;
+import org.apache.iceberg.SortOrder;
+import org.apache.iceberg.Table;
+import org.apache.iceberg.relocated.com.google.common.base.Preconditions;
+import org.apache.iceberg.relocated.com.google.common.collect.ImmutableList;
+import org.apache.iceberg.relocated.com.google.common.collect.Lists;
+import org.apache.iceberg.spark.SparkUtil;
+import org.apache.iceberg.types.Types;
+import org.apache.iceberg.util.ZOrderByteUtils;
+import org.apache.spark.sql.Column;
+import org.apache.spark.sql.Dataset;
+import org.apache.spark.sql.Row;
+import org.apache.spark.sql.SparkSession;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+class SparkHilbertFileRewriteRunner extends SparkShufflingFileRewriteRunner {
+ private static final Logger LOG = LoggerFactory.getLogger(SparkHilbertFileRewriteRunner.class);
+
+ private static final String H_COLUMN = "ICEHVALUE";
+ private static final Schema H_SCHEMA =
+ new Schema(Types.NestedField.required(0, H_COLUMN, Types.BinaryType.get()));
+ private static final SortOrder H_SORT_ORDER =
+ SortOrder.builderFor(H_SCHEMA)
+ .sortBy(H_COLUMN, SortDirection.ASC, NullOrder.NULLS_LAST)
+ .build();
+
+ /**
+ * The number of bits contributed by each column to the Hilbert index.
+ *
+ * <p>This is fixed at the full width of {@link ZOrderByteUtils#PRIMITIVE_BUFFER_SIZE}. A smaller,
+ * configurable width is unsafe with the shared {@link ZOrderByteUtils} encodings: whole-number
+ * types (int, date, small longs, ...) are widened into an 8-byte key with their magnitude in the
+ * low-order bytes, so truncating to fewer high-order bytes would discard all magnitude and
+ * collapse those columns to a single coordinate. Supporting a narrower width correctly would
+ * require tracking each column's significant bit width, which is out of scope here.
+ */
+ private static final int BITS_PER_COLUMN = ZOrderByteUtils.PRIMITIVE_BUFFER_SIZE * Byte.SIZE;
+
+ private final List<String> hilbertColNames;
+
+ SparkHilbertFileRewriteRunner(SparkSession spark, Table table, List<String> hilbertColNames) {
+ super(spark, table);
+ this.hilbertColNames = validHilbertColNames(spark, table, hilbertColNames);
+ }
+
+ @Override
+ public String description() {
+ return "HILBERT";
+ }
+
+ @Override
+ protected SortOrder sortOrder() {
+ return H_SORT_ORDER;
+ }
+
+ /**
+ * Overrides the sortSchema method to include columns from H_SCHEMA.
+ *
+ * <p>This method generates a new Schema object which consists of columns from the original table
+ * schema and H_SCHEMA.
+ */
+ @Override
+ protected Schema sortSchema() {
+ return new Schema(
+ new ImmutableList.Builder<Types.NestedField>()
+ .addAll(table().schema().columns())
+ .addAll(H_SCHEMA.columns())
+ .build());
+ }
+
+ @Override
+ protected Dataset<Row> sortedDF(Dataset<Row> df, Function<Dataset<Row>, Dataset<Row>> sortFunc) {
+ Dataset<Row> hValueDF = df.withColumn(H_COLUMN, hilbertValue(df));
+ Dataset<Row> sortedDF = sortFunc.apply(hValueDF);
+ return sortedDF.drop(H_COLUMN);
+ }
+
+ private Column hilbertValue(Dataset<Row> df) {
+ // Reuse the Z-order byte conversions. Every column contributes the full primitive width so the
+ // Hilbert transform sees a uniform per-dimension width with no magnitude loss.
+ SparkZOrderUDF byteUDF =
+ new SparkZOrderUDF(
Review Comment:
Thanks, this is a real bug which affects as well as Zorder.
I created a dedicated issue https://github.com/apache/iceberg/issues/17658
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] API, Core, Spark: Add Hilbert-curve clustering strategy for `rewrite_data_files` [iceberg]
Posted by "GGraziadei (via GitHub)" <gi...@apache.org>.
GGraziadei commented on code in PR #16827:
URL: https://github.com/apache/iceberg/pull/16827#discussion_r3785609483
##########
core/src/test/java/org/apache/iceberg/util/TestHilbertByteUtils.java:
##########
@@ -0,0 +1,135 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.util;
+
+import static org.assertj.core.api.Assertions.assertThat;
+import static org.assertj.core.api.Assertions.assertThatThrownBy;
+
+import java.util.Set;
+import org.apache.iceberg.relocated.com.google.common.collect.Sets;
+import org.junit.jupiter.api.Test;
+
+public class TestHilbertByteUtils {
Review Comment:
Added `bijectionAndLocalityInThreeDimensions` (full 8-bit 256^3 sweep: bijection onto 1..2^24-1 plus L1 adjacency between consecutive indices) and `bijectionAndLocalityInFourDimensions`
For 4-D, a full 8-bit enumeration is 2^ 32 points, so that test walks the (0,16)^4 sub-cube instead.
Because only the low four bits of each axis are set, those points land on exactly the first 2^16 indices of the curve, verified contiguous, so bijection and adjacency are still checked exactly rather than sampled.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] API, Core, Spark: Add Hilbert-curve clustering strategy for `rewrite_data_files` [iceberg]
Posted by "nssalian (via GitHub)" <gi...@apache.org>.
nssalian commented on PR #16827:
URL: https://github.com/apache/iceberg/pull/16827#issuecomment-5122662316
Hey @GGraziadei thank you for this. I took some time to look at this and here are some high level suggestions:
1. Adding a new public sort strategy to the RewriteDataFiles API is a design decision, not just an implementation, so it'll want community buy-in before a deep review. I know you sent a note to the list, but if you have a document that would help ground a lot of what you are proposing i.e. the motivation, the benefit, etc. There's longstanding prior interest here (see #3836). Worth getting something concretely written and linking it here if you haven't already.
2. Docs: docs/docs/spark-procedures.md documents zorder(...) in the sort_order row and has an options section for the zorder sort strategy, but there's no hilbert equivalent yet. This would need to be added.
3. Spark version scope: This only touches spark/v4.1, but v4.0 is also supported. Developing in the latest version first is fine, but could you state the intent explicitly in the PR description (e.g. "4.1 first, backport to 4.0 to follow") so the scope reads as intentional?
4. Hilbert.java is currently identical to Zorder.java. Mirroring is the right call for now; a shared base class is worth considering, but I'd leave that as a follow-up rather than block this PR on it.
5. Benchmarks. I appreciate how candid the benchmark writeup is. The file-pruning result (16 → 11 files scanned, deterministic planning-time measurement) is the one I'd lead with. The latency numbers are confounded by
the swap-thrashing you noted (Z-order CoV 20-52% vs Hilbert 3-11%), so I'd either drop them or reproduce on a box that isn't swapping, and capture scanned bytes as well as file counts. A rerun at a fixed file count would make the pruning claim airtight.
One more measurement that would be compelling if it's feasible: whether the tighter clustering reduces write amplification on subsequent upserts - i.e., a MERGE/copy-on-write touching fewer data files because updated
rows are more localized than under z-order. It's data-dependent (only when the merge keys align with the clustering columns), but it would speak directly to a real-world benefit beyond read pruning.
6. SparkHilbertUDF serialization. The transient ThreadLocal + readObject re-init pattern matches SparkZOrderUDF, so this looks right. Since the UDF ships to executors, can you just confirm testHilbertSort actually exercises a multi-partition shuffle so we know the reused buffer round-trips after deserialization?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] API, Core, Spark: Add Hilbert-curve clustering strategy for `rewrite_data_files` [iceberg]
Posted by "GGraziadei (via GitHub)" <gi...@apache.org>.
GGraziadei commented on PR #16827:
URL: https://github.com/apache/iceberg/pull/16827#issuecomment-5361599235
Hi @gimgit,
Thanks for your question helped to improve drastically the quality of this work.
I would like to start from point 2. I measured and compared the memory allocation with a profiler, and I reported the results here: https://github.com/apache/iceberg/pull/16827#issuecomment-5361125612 (Claude helped me put together a quick report).
While conducting this analysis, I was already aware that the main cost was the transpose operation and that it was not buffered. I then buffered the transpose, which significantly improved memory allocation: from **1.7 GB/op before buffering to only ~6.7 KB/op afterward as for ZOrder**. The improvement is impressive, thanks a lot for focusing on this point!
Regarding point 1, I want to clarify something. I really appreciate your PR effort here, because this is exactly what allows us to track the quality of the clustering strategy.
For the past couple of months, I was convinced that the overlap of the file min/max ranges was what defined a good clustering strategy. However, I now realize that this is an **anti-pattern**: it works only for uniform distributions.
The real metric for evaluating cluster quality is locality. In my mind, this can be understood as the variance in density across clusters. This is where I see the real advantage of Hilbert over Z-order.
So your question is absolutely correct: how do we trigger this? I will open an issue and address it in a separate PR once this one is merged.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] API, Core, Spark: Add Hilbert-curve clustering strategy for `rewrite_data_files` [iceberg]
Posted by "GGraziadei (via GitHub)" <gi...@apache.org>.
GGraziadei commented on PR #16827:
URL: https://github.com/apache/iceberg/pull/16827#issuecomment-5361944128
Hi @gimgit,
Thanks for your question helped to improve drastically the quality of this work.
I would like to start from point 2. I measured and compared the memory allocation with a profiler, and I reported the results here: https://github.com/apache/iceberg/pull/16827#issuecomment-5361125612 (Claude helped me put together a quick report).
While conducting this analysis, I was already aware that the main cost was the transpose operation and that it was not buffered. I then buffered the transpose, which significantly improved memory allocation: from 1.7 GB/op before buffering to only ~6.7 KB/op afterward as for ZOrder. The improvement is impressive, thanks a lot for focusing on this point!
Regarding point 1, I want to clarify something. I really appreciate your PR effort here, because this is exactly what allows us to track the quality of the clustering strategy.
The real metric for evaluating cluster quality is locality. In my mind, this can be understood as the variance in density across clusters. This is where I see the real advantage of Hilbert over Z-order.
So your question is absolutely correct: how do we trigger this? I will open an issue and address it in a separate PR once this one is merged.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] API, Core, Spark: Add Hilbert-curve clustering strategy for `rewrite_data_files` [iceberg]
Posted by "manuzhang (via GitHub)" <gi...@apache.org>.
manuzhang commented on code in PR #16827:
URL: https://github.com/apache/iceberg/pull/16827#discussion_r3780935134
##########
spark/v4.1/spark/src/main/java/org/apache/iceberg/spark/actions/SparkHilbertFileRewriteRunner.java:
##########
@@ -0,0 +1,166 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.spark.actions;
+
+import static org.apache.spark.sql.functions.array;
+
+import java.util.List;
+import java.util.Set;
+import java.util.function.Function;
+import org.apache.iceberg.NullOrder;
+import org.apache.iceberg.Schema;
+import org.apache.iceberg.SortDirection;
+import org.apache.iceberg.SortOrder;
+import org.apache.iceberg.Table;
+import org.apache.iceberg.relocated.com.google.common.base.Preconditions;
+import org.apache.iceberg.relocated.com.google.common.collect.ImmutableList;
+import org.apache.iceberg.relocated.com.google.common.collect.Lists;
+import org.apache.iceberg.spark.SparkUtil;
+import org.apache.iceberg.types.Types;
+import org.apache.iceberg.util.ZOrderByteUtils;
+import org.apache.spark.sql.Column;
+import org.apache.spark.sql.Dataset;
+import org.apache.spark.sql.Row;
+import org.apache.spark.sql.SparkSession;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+class SparkHilbertFileRewriteRunner extends SparkShufflingFileRewriteRunner {
+ private static final Logger LOG = LoggerFactory.getLogger(SparkHilbertFileRewriteRunner.class);
+
+ private static final String H_COLUMN = "ICEHVALUE";
+ private static final Schema H_SCHEMA =
+ new Schema(Types.NestedField.required(0, H_COLUMN, Types.BinaryType.get()));
+ private static final SortOrder H_SORT_ORDER =
+ SortOrder.builderFor(H_SCHEMA)
+ .sortBy(H_COLUMN, SortDirection.ASC, NullOrder.NULLS_LAST)
+ .build();
+
+ /**
+ * The number of bits contributed by each column to the Hilbert index.
+ *
+ * <p>This is fixed at the full width of {@link ZOrderByteUtils#PRIMITIVE_BUFFER_SIZE}. A smaller,
+ * configurable width is unsafe with the shared {@link ZOrderByteUtils} encodings: whole-number
+ * types (int, date, small longs, ...) are widened into an 8-byte key with their magnitude in the
+ * low-order bytes, so truncating to fewer high-order bytes would discard all magnitude and
+ * collapse those columns to a single coordinate. Supporting a narrower width correctly would
+ * require tracking each column's significant bit width, which is out of scope here.
+ */
+ private static final int BITS_PER_COLUMN = ZOrderByteUtils.PRIMITIVE_BUFFER_SIZE * Byte.SIZE;
+
+ private final List<String> hilbertColNames;
+
+ SparkHilbertFileRewriteRunner(SparkSession spark, Table table, List<String> hilbertColNames) {
+ super(spark, table);
+ this.hilbertColNames = validHilbertColNames(spark, table, hilbertColNames);
+ }
+
+ @Override
+ public String description() {
+ return "HILBERT";
+ }
+
+ @Override
+ protected SortOrder sortOrder() {
+ return H_SORT_ORDER;
+ }
+
+ /**
+ * Overrides the sortSchema method to include columns from H_SCHEMA.
+ *
+ * <p>This method generates a new Schema object which consists of columns from the original table
+ * schema and H_SCHEMA.
+ */
+ @Override
+ protected Schema sortSchema() {
+ return new Schema(
+ new ImmutableList.Builder<Types.NestedField>()
+ .addAll(table().schema().columns())
+ .addAll(H_SCHEMA.columns())
+ .build());
+ }
+
+ @Override
+ protected Dataset<Row> sortedDF(Dataset<Row> df, Function<Dataset<Row>, Dataset<Row>> sortFunc) {
+ Dataset<Row> hValueDF = df.withColumn(H_COLUMN, hilbertValue(df));
+ Dataset<Row> sortedDF = sortFunc.apply(hValueDF);
+ return sortedDF.drop(H_COLUMN);
+ }
+
+ private Column hilbertValue(Dataset<Row> df) {
+ // Reuse the Z-order byte conversions. Every column contributes the full primitive width so the
+ // Hilbert transform sees a uniform per-dimension width with no magnitude loss.
+ SparkZOrderUDF byteUDF =
+ new SparkZOrderUDF(
Review Comment:
Its boolean converter dereferences the boxed value without a null check. Any selected optional Boolean containing null aborts the rewrite with NPE.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] API, Core, Spark: Add Hilbert-curve clustering strategy for `rewrite_data_files` [iceberg]
Posted by "nssalian (via GitHub)" <gi...@apache.org>.
nssalian commented on code in PR #16827:
URL: https://github.com/apache/iceberg/pull/16827#discussion_r3779005073
##########
core/src/test/java/org/apache/iceberg/util/TestHilbertByteUtils.java:
##########
@@ -0,0 +1,135 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.util;
+
+import static org.assertj.core.api.Assertions.assertThat;
+import static org.assertj.core.api.Assertions.assertThatThrownBy;
+
+import java.util.Set;
+import org.apache.iceberg.relocated.com.google.common.collect.Sets;
+import org.junit.jupiter.api.Test;
+
+public class TestHilbertByteUtils {
Review Comment:
This test suite covers 2D dimensions but we could consider adding an 8-bit 3-D (and 4-D) bijection + adjacency test so the Gray-encode/adjust path is locked in beyond 2-D.
##########
spark/v4.1/spark/src/main/java/org/apache/iceberg/spark/actions/SparkHilbertFileRewriteRunner.java:
##########
@@ -0,0 +1,166 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.spark.actions;
+
+import static org.apache.spark.sql.functions.array;
+
+import java.util.List;
+import java.util.Set;
+import java.util.function.Function;
+import org.apache.iceberg.NullOrder;
+import org.apache.iceberg.Schema;
+import org.apache.iceberg.SortDirection;
+import org.apache.iceberg.SortOrder;
+import org.apache.iceberg.Table;
+import org.apache.iceberg.relocated.com.google.common.base.Preconditions;
+import org.apache.iceberg.relocated.com.google.common.collect.ImmutableList;
+import org.apache.iceberg.relocated.com.google.common.collect.Lists;
+import org.apache.iceberg.spark.SparkUtil;
+import org.apache.iceberg.types.Types;
+import org.apache.iceberg.util.ZOrderByteUtils;
+import org.apache.spark.sql.Column;
+import org.apache.spark.sql.Dataset;
+import org.apache.spark.sql.Row;
+import org.apache.spark.sql.SparkSession;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+class SparkHilbertFileRewriteRunner extends SparkShufflingFileRewriteRunner {
Review Comment:
+1 to doing a expressions-based refactor as a follow up and de-dupe the z-order work here.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] API, Core, Spark: Add Hilbert-curve clustering strategy for `rewrite_data_files` [iceberg]
Posted by "RussellSpitzer (via GitHub)" <gi...@apache.org>.
RussellSpitzer commented on code in PR #16827:
URL: https://github.com/apache/iceberg/pull/16827#discussion_r3679111302
##########
core/src/main/java/org/apache/iceberg/util/HilbertByteUtils.java:
##########
@@ -0,0 +1,140 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.util;
+
+import java.nio.ByteBuffer;
+import org.apache.iceberg.relocated.com.google.common.base.Preconditions;
+
+/**
+ * Maps a set of columns (each already converted to fixed-width, lexicographically-ordered unsigned
+ * bytes by {@link ZOrderByteUtils}) onto a single byte array whose unsigned big-endian
+ * lexicographic ordering follows the multi-dimensional Hilbert space-filling curve.
+ *
+ * <p>Unlike Z-ordering, the Hilbert transform requires every dimension to contribute the same
+ * number of bits, so each column is read to a fixed {@code bitsPerColumn} precision.
+ *
+ * <p>The transform is the standard "axes to transposed Hilbert index" algorithm from J. Skilling,
+ * "Programming the Hilbert curve" (2004); the transposed index is then serialized to a scalar with
+ * {@link ZOrderByteUtils#interleaveBits}.
+ */
+public class HilbertByteUtils {
+
+ private HilbertByteUtils() {}
+
+ /** See {@link #hilbertIndex(byte[][], int, ByteBuffer)}. */
+ public static byte[] hilbertIndex(byte[][] columnsBinary, int bitsPerColumn) {
+ int outputBytes = columnsBinary.length * (bitsPerColumn / 8);
+ return hilbertIndex(columnsBinary, bitsPerColumn, ByteBuffer.allocate(outputBytes));
+ }
+
+ /**
+ * Compute the Hilbert index for the given columns.
+ *
+ * @param columnsBinary one ordered-byte array per column; each must be at least {@code
+ * bitsPerColumn / 8} bytes long (only the leading bytes are used)
+ * @param bitsPerColumn bits taken from each column; a positive multiple of 8, no greater than 64
+ * @param reuse a buffer with capacity at least {@code numColumns * bitsPerColumn / 8}
+ * @return the Hilbert index, of length {@code numColumns * bitsPerColumn / 8}
+ */
+ public static byte[] hilbertIndex(byte[][] columnsBinary, int bitsPerColumn, ByteBuffer reuse) {
+ Preconditions.checkArgument(
+ bitsPerColumn > 0 && bitsPerColumn % 8 == 0,
+ "Hilbert bitsPerColumn must be a positive multiple of 8, was %s",
+ bitsPerColumn);
+ Preconditions.checkArgument(
+ bitsPerColumn <= 64,
+ "Hilbert bitsPerColumn must be no greater than 64, was %s",
+ bitsPerColumn);
+ Preconditions.checkArgument(
+ columnsBinary.length > 0, "Cannot compute a Hilbert index for zero columns");
+
+ int numColumns = columnsBinary.length;
+ int bytesPerColumn = bitsPerColumn / 8;
+
+ long[] transpose = new long[numColumns];
+ for (int i = 0; i < numColumns; i++) {
+ Preconditions.checkArgument(
+ columnsBinary[i].length >= bytesPerColumn,
+ "Column %s contributes %s bytes but %s are required",
+ i,
+ columnsBinary[i].length,
+ bytesPerColumn);
+ transpose[i] = readBigEndian(columnsBinary[i], bytesPerColumn);
+ }
+
+ axesToTranspose(transpose, bitsPerColumn);
+
+ byte[][] transposedBytes = new byte[numColumns][bytesPerColumn];
+ for (int i = 0; i < numColumns; i++) {
+ writeBigEndian(transpose[i], transposedBytes[i], bytesPerColumn);
+ }
+
+ return ZOrderByteUtils.interleaveBits(transposedBytes, numColumns * bytesPerColumn, reuse);
+ }
+
+ // please refer to the paper
Review Comment:
Probably would be worth having a citation here :)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] API, Core, Spark: Add Hilbert-curve clustering strategy for `rewrite_data_files` [iceberg]
Posted by "GGraziadei (via GitHub)" <gi...@apache.org>.
GGraziadei commented on code in PR #16827:
URL: https://github.com/apache/iceberg/pull/16827#discussion_r3785639383
##########
spark/v4.1/spark/src/main/java/org/apache/iceberg/spark/actions/SparkHilbertFileRewriteRunner.java:
##########
@@ -0,0 +1,166 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.spark.actions;
+
+import static org.apache.spark.sql.functions.array;
+
+import java.util.List;
+import java.util.Set;
+import java.util.function.Function;
+import org.apache.iceberg.NullOrder;
+import org.apache.iceberg.Schema;
+import org.apache.iceberg.SortDirection;
+import org.apache.iceberg.SortOrder;
+import org.apache.iceberg.Table;
+import org.apache.iceberg.relocated.com.google.common.base.Preconditions;
+import org.apache.iceberg.relocated.com.google.common.collect.ImmutableList;
+import org.apache.iceberg.relocated.com.google.common.collect.Lists;
+import org.apache.iceberg.spark.SparkUtil;
+import org.apache.iceberg.types.Types;
+import org.apache.iceberg.util.ZOrderByteUtils;
+import org.apache.spark.sql.Column;
+import org.apache.spark.sql.Dataset;
+import org.apache.spark.sql.Row;
+import org.apache.spark.sql.SparkSession;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+class SparkHilbertFileRewriteRunner extends SparkShufflingFileRewriteRunner {
+ private static final Logger LOG = LoggerFactory.getLogger(SparkHilbertFileRewriteRunner.class);
+
+ private static final String H_COLUMN = "ICEHVALUE";
+ private static final Schema H_SCHEMA =
+ new Schema(Types.NestedField.required(0, H_COLUMN, Types.BinaryType.get()));
+ private static final SortOrder H_SORT_ORDER =
+ SortOrder.builderFor(H_SCHEMA)
+ .sortBy(H_COLUMN, SortDirection.ASC, NullOrder.NULLS_LAST)
+ .build();
+
+ /**
+ * The number of bits contributed by each column to the Hilbert index.
+ *
+ * <p>This is fixed at the full width of {@link ZOrderByteUtils#PRIMITIVE_BUFFER_SIZE}. A smaller,
+ * configurable width is unsafe with the shared {@link ZOrderByteUtils} encodings: whole-number
+ * types (int, date, small longs, ...) are widened into an 8-byte key with their magnitude in the
+ * low-order bytes, so truncating to fewer high-order bytes would discard all magnitude and
+ * collapse those columns to a single coordinate. Supporting a narrower width correctly would
+ * require tracking each column's significant bit width, which is out of scope here.
+ */
+ private static final int BITS_PER_COLUMN = ZOrderByteUtils.PRIMITIVE_BUFFER_SIZE * Byte.SIZE;
+
+ private final List<String> hilbertColNames;
+
+ SparkHilbertFileRewriteRunner(SparkSession spark, Table table, List<String> hilbertColNames) {
+ super(spark, table);
+ this.hilbertColNames = validHilbertColNames(spark, table, hilbertColNames);
+ }
+
+ @Override
+ public String description() {
+ return "HILBERT";
+ }
+
+ @Override
+ protected SortOrder sortOrder() {
+ return H_SORT_ORDER;
+ }
+
+ /**
+ * Overrides the sortSchema method to include columns from H_SCHEMA.
+ *
+ * <p>This method generates a new Schema object which consists of columns from the original table
+ * schema and H_SCHEMA.
+ */
+ @Override
+ protected Schema sortSchema() {
+ return new Schema(
+ new ImmutableList.Builder<Types.NestedField>()
+ .addAll(table().schema().columns())
+ .addAll(H_SCHEMA.columns())
+ .build());
+ }
+
+ @Override
+ protected Dataset<Row> sortedDF(Dataset<Row> df, Function<Dataset<Row>, Dataset<Row>> sortFunc) {
+ Dataset<Row> hValueDF = df.withColumn(H_COLUMN, hilbertValue(df));
+ Dataset<Row> sortedDF = sortFunc.apply(hValueDF);
+ return sortedDF.drop(H_COLUMN);
+ }
+
+ private Column hilbertValue(Dataset<Row> df) {
+ // Reuse the Z-order byte conversions. Every column contributes the full primitive width so the
+ // Hilbert transform sees a uniform per-dimension width with no magnitude loss.
+ SparkZOrderUDF byteUDF =
+ new SparkZOrderUDF(
+ hilbertColNames.size(), ZOrderByteUtils.PRIMITIVE_BUFFER_SIZE, Integer.MAX_VALUE);
+
+ Column[] orderedCols =
+ hilbertColNames.stream()
+ .map(df.schema()::apply)
+ .map(col -> byteUDF.sortedLexicographically(df.col(col.name()), col.dataType()))
+ .toArray(Column[]::new);
+
+ SparkHilbertUDF hilbertUDF = new SparkHilbertUDF(hilbertColNames.size(), BITS_PER_COLUMN);
+ return hilbertUDF.hilbertValue(array(orderedCols));
+ }
+
+ private List<String> validHilbertColNames(
+ SparkSession spark, Table table, List<String> inputHilbertColNames) {
+
+ Preconditions.checkArgument(
+ inputHilbertColNames != null && !inputHilbertColNames.isEmpty(),
+ "Cannot HILBERT when no columns are specified");
+
+ Schema schema = table.schema();
+ Set<Integer> identityPartitionFieldIds = table.spec().identitySourceIds();
+ boolean caseSensitive = SparkUtil.caseSensitive(spark);
Review Comment:
Thanks I compacted in #17658
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] API, Core, Spark: Add Hilbert-curve clustering strategy for `rewrite_data_files` [iceberg]
Posted by "RussellSpitzer (via GitHub)" <gi...@apache.org>.
RussellSpitzer commented on PR #16827:
URL: https://github.com/apache/iceberg/pull/16827#issuecomment-5400347276
@nssalian and @gimgit Any remaining comments?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] API, Core, Spark: Add Hilbert-curve clustering strategy for `rewrite_data_files` [iceberg]
Posted by "RussellSpitzer (via GitHub)" <gi...@apache.org>.
RussellSpitzer commented on code in PR #16827:
URL: https://github.com/apache/iceberg/pull/16827#discussion_r3776779925
##########
core/src/test/java/org/apache/iceberg/util/TestHilbertByteUtils.java:
##########
@@ -0,0 +1,135 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.util;
+
+import static org.assertj.core.api.Assertions.assertThat;
+import static org.assertj.core.api.Assertions.assertThatThrownBy;
+
+import java.util.Set;
+import org.apache.iceberg.relocated.com.google.common.collect.Sets;
+import org.junit.jupiter.api.Test;
+
+public class TestHilbertByteUtils {
+
+ private static int toInt(byte[] bytes) {
+ int value = 0;
+ for (byte b : bytes) {
+ value = (value << 8) | (b & 0xFF);
+ }
+ return value;
+ }
+
+ /**
+ * Over an 8-bit, 2-dimensional space (a 256x256 grid) the Hilbert index must be a bijection onto
+ * 0..65535: every (x, y) maps to a distinct index and every index is produced exactly once.
+ */
+ @Test
+ public void testBijectionTwoDimensions() {
+ Set<Integer> seen = Sets.newHashSet();
+ for (int x = 0; x < 256; x++) {
+ for (int y = 0; y < 256; y++) {
+ byte[][] cols = new byte[][] {new byte[] {(byte) x}, new byte[] {(byte) y}};
+ int index = toInt(HilbertByteUtils.hilbertIndex(cols, 8));
+ assertThat(seen.add(index))
+ .as("duplicate hilbert index %s for (%s,%s)", index, x, y)
+ .isTrue();
+ assertThat(index).isBetween(0, 65535);
+ }
+ }
+ assertThat(seen).hasSize(65536);
+ }
+
+ /**
+ * The defining Hilbert property: consecutive index values map to grid points that are direct
+ * neighbours (Manhattan distance 1). This is what distinguishes it from Z-order.
+ */
+ @Test
+ public void testLocalityTwoDimensions() {
+ int[] xByIndex = new int[65536];
+ int[] yByIndex = new int[65536];
+ for (int x = 0; x < 256; x++) {
+ for (int y = 0; y < 256; y++) {
+ byte[][] cols = new byte[][] {new byte[] {(byte) x}, new byte[] {(byte) y}};
+ int index = toInt(HilbertByteUtils.hilbertIndex(cols, 8));
+ xByIndex[index] = x;
+ yByIndex[index] = y;
+ }
+ }
+ for (int index = 1; index < 65536; index++) {
+ int manhattan =
+ Math.abs(xByIndex[index] - xByIndex[index - 1])
+ + Math.abs(yByIndex[index] - yByIndex[index - 1]);
+ assertThat(manhattan).as("indices %s and %s are not adjacent", index - 1, index).isEqualTo(1);
+ }
+ }
+
+ /** A single dimension degenerates to the identity ordering. */
+ @Test
+ public void testSingleDimensionIsIdentity() {
+ for (int x = 0; x < 256; x++) {
+ byte[][] cols = new byte[][] {new byte[] {(byte) x}};
+ assertThat(toInt(HilbertByteUtils.hilbertIndex(cols, 8))).isEqualTo(x);
+ }
+ }
+
+ /** Same input always yields the same output, and the output has the expected length. */
+ @Test
+ public void testDeterministicAndSized() {
+ byte[][] cols =
+ new byte[][] {
+ new byte[] {1, 2, 3, 4, 5, 6, 7, 8},
+ new byte[] {8, 7, 6, 5, 4, 3, 2, 1},
+ new byte[] {0, 0, 0, 0, 0, 0, 0, 9}
+ };
+ byte[] first = HilbertByteUtils.hilbertIndex(cols, 64);
+ byte[] second = HilbertByteUtils.hilbertIndex(cols, 64);
+ assertThat(first).isEqualTo(second);
+ assertThat(first).hasSize(3 * 8);
+ }
+
+ /** Only the high {@code bitsPerColumn} bits of each column participate. */
+ @Test
+ public void testReadsLeadingBytesOnly() {
+ byte[][] leadingOnly =
+ new byte[][] {new byte[] {5, 0, 0, 0, 0, 0, 0, 0}, new byte[] {9, 0, 0, 0, 0, 0, 0, 0}};
+ byte[][] withTrailing =
+ new byte[][] {new byte[] {5, 77, 0, 0, 0, 0, 0, 0}, new byte[] {9, 13, 0, 0, 0, 0, 0, 0}};
+ assertThat(HilbertByteUtils.hilbertIndex(leadingOnly, 8))
+ .isEqualTo(HilbertByteUtils.hilbertIndex(withTrailing, 8));
+ }
+
+ @Test
+ public void testInvalidBitsPerColumn() {
+ byte[][] cols = new byte[][] {new byte[] {0}, new byte[] {0}};
+ assertThatThrownBy(() -> HilbertByteUtils.hilbertIndex(cols, 7))
+ .isInstanceOf(IllegalArgumentException.class)
+ .hasMessageContaining("multiple of 8");
+ assertThatThrownBy(() -> HilbertByteUtils.hilbertIndex(cols, 72))
+ .isInstanceOf(IllegalArgumentException.class)
+ .hasMessageContaining("no greater than 64");
+ }
+
+ @Test
+ public void testColumnTooShort() {
+ byte[][] cols = new byte[][] {new byte[] {0}, new byte[] {0}};
+ assertThatThrownBy(() -> HilbertByteUtils.hilbertIndex(cols, 16))
+ .isInstanceOf(IllegalArgumentException.class)
+ .hasMessageContaining("bytes");
Review Comment:
Probably not enough to really test this failure? Nit again
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] API, Core, Spark: Add Hilbert-curve clustering strategy for `rewrite_data_files` [iceberg]
Posted by "RussellSpitzer (via GitHub)" <gi...@apache.org>.
RussellSpitzer commented on code in PR #16827:
URL: https://github.com/apache/iceberg/pull/16827#discussion_r3776771616
##########
core/src/test/java/org/apache/iceberg/util/TestHilbertByteUtils.java:
##########
@@ -0,0 +1,135 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.util;
+
+import static org.assertj.core.api.Assertions.assertThat;
+import static org.assertj.core.api.Assertions.assertThatThrownBy;
+
+import java.util.Set;
+import org.apache.iceberg.relocated.com.google.common.collect.Sets;
+import org.junit.jupiter.api.Test;
+
+public class TestHilbertByteUtils {
+
+ private static int toInt(byte[] bytes) {
+ int value = 0;
+ for (byte b : bytes) {
+ value = (value << 8) | (b & 0xFF);
+ }
+ return value;
+ }
+
+ /**
+ * Over an 8-bit, 2-dimensional space (a 256x256 grid) the Hilbert index must be a bijection onto
+ * 0..65535: every (x, y) maps to a distinct index and every index is produced exactly once.
+ */
+ @Test
+ public void testBijectionTwoDimensions() {
+ Set<Integer> seen = Sets.newHashSet();
+ for (int x = 0; x < 256; x++) {
+ for (int y = 0; y < 256; y++) {
+ byte[][] cols = new byte[][] {new byte[] {(byte) x}, new byte[] {(byte) y}};
+ int index = toInt(HilbertByteUtils.hilbertIndex(cols, 8));
+ assertThat(seen.add(index))
+ .as("duplicate hilbert index %s for (%s,%s)", index, x, y)
+ .isTrue();
+ assertThat(index).isBetween(0, 65535);
+ }
+ }
+ assertThat(seen).hasSize(65536);
+ }
+
+ /**
+ * The defining Hilbert property: consecutive index values map to grid points that are direct
+ * neighbours (Manhattan distance 1). This is what distinguishes it from Z-order.
+ */
+ @Test
+ public void testLocalityTwoDimensions() {
+ int[] xByIndex = new int[65536];
+ int[] yByIndex = new int[65536];
+ for (int x = 0; x < 256; x++) {
+ for (int y = 0; y < 256; y++) {
+ byte[][] cols = new byte[][] {new byte[] {(byte) x}, new byte[] {(byte) y}};
+ int index = toInt(HilbertByteUtils.hilbertIndex(cols, 8));
+ xByIndex[index] = x;
+ yByIndex[index] = y;
+ }
+ }
+ for (int index = 1; index < 65536; index++) {
+ int manhattan =
+ Math.abs(xByIndex[index] - xByIndex[index - 1])
+ + Math.abs(yByIndex[index] - yByIndex[index - 1]);
+ assertThat(manhattan).as("indices %s and %s are not adjacent", index - 1, index).isEqualTo(1);
+ }
+ }
+
+ /** A single dimension degenerates to the identity ordering. */
+ @Test
+ public void testSingleDimensionIsIdentity() {
+ for (int x = 0; x < 256; x++) {
+ byte[][] cols = new byte[][] {new byte[] {(byte) x}};
+ assertThat(toInt(HilbertByteUtils.hilbertIndex(cols, 8))).isEqualTo(x);
+ }
+ }
+
+ /** Same input always yields the same output, and the output has the expected length. */
+ @Test
+ public void testDeterministicAndSized() {
+ byte[][] cols =
+ new byte[][] {
+ new byte[] {1, 2, 3, 4, 5, 6, 7, 8},
+ new byte[] {8, 7, 6, 5, 4, 3, 2, 1},
+ new byte[] {0, 0, 0, 0, 0, 0, 0, 9}
+ };
+ byte[] first = HilbertByteUtils.hilbertIndex(cols, 64);
+ byte[] second = HilbertByteUtils.hilbertIndex(cols, 64);
+ assertThat(first).isEqualTo(second);
+ assertThat(first).hasSize(3 * 8);
+ }
+
+ /** Only the high {@code bitsPerColumn} bits of each column participate. */
+ @Test
+ public void testReadsLeadingBytesOnly() {
+ byte[][] leadingOnly =
+ new byte[][] {new byte[] {5, 0, 0, 0, 0, 0, 0, 0}, new byte[] {9, 0, 0, 0, 0, 0, 0, 0}};
+ byte[][] withTrailing =
+ new byte[][] {new byte[] {5, 77, 0, 0, 0, 0, 0, 0}, new byte[] {9, 13, 0, 0, 0, 0, 0, 0}};
+ assertThat(HilbertByteUtils.hilbertIndex(leadingOnly, 8))
+ .isEqualTo(HilbertByteUtils.hilbertIndex(withTrailing, 8));
+ }
+
+ @Test
+ public void testInvalidBitsPerColumn() {
Review Comment:
We could probably splits these two asserts into separate tests, nit
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] API, Core, Spark: Add Hilbert-curve clustering strategy for `rewrite_data_files` [iceberg]
Posted by "GGraziadei (via GitHub)" <gi...@apache.org>.
GGraziadei commented on PR #16827:
URL: https://github.com/apache/iceberg/pull/16827#issuecomment-5295920897
Hi @RussellSpitzer @manuzhang @nssalian
Thanks for the review and contributions! I've just pushed a commit to address your points:
- Extended test coverage to 3d and 4d
- Opened follow-up issues, grouping related comments into the same scope. Since these derive from the ZOrder implementation, fixing them will improve ZOrder as well
- Minors and nits
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] API, Core, Spark: Add Hilbert-curve clustering strategy for `rewrite_data_files` [iceberg]
Posted by "RussellSpitzer (via GitHub)" <gi...@apache.org>.
RussellSpitzer commented on PR #16827:
URL: https://github.com/apache/iceberg/pull/16827#issuecomment-5415984339
Merged, Thanks @GGraziadei for all your work on this and thank you to @nssalian and @gimgit for your work on reviews.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] API, Core, Spark: Add Hilbert-curve clustering strategy for `rewrite_data_files` [iceberg]
Posted by "gimgit (via GitHub)" <gi...@apache.org>.
gimgit commented on PR #16827:
URL: https://github.com/apache/iceberg/pull/16827#issuecomment-5354594882
Nice writeup — the neighbour-locality argument over Z-order is well made, and reusing the existing Z-order byte encodings keeps the surface small. One design question from adjacent work (#17504, overlap-based selection):
1. **Re-selection after clustering degrades.** The Hilbert runner plugs into the same size-based planner as sort/zorder, so once a table is Hilbert-clustered and its files sit in the healthy size band, newly ingested files that overlap in curve space are invisible to selection — `rewrite_data_files` reports `rewritten=0` as success and clustering quietly degrades (#17489 shows this for linear sort). For linear orders, bounds on the first sort field give a cheap detection signal (#17504). For Hilbert, per-column bounds get wide by construction, so I don't see an obvious metadata-only signal for "this table needs re-clustering". Does the companion doc have thoughts on detecting when a Hilbert rewrite is due, as opposed to how to perform it? Even a rough curve-space health metric would make the strategy operable long-term, not just at initial layout.
2. Small one: `SparkHilbertUDF` reuses a `ThreadLocal<byte[][]>` holder and re-initializes it in `readObject` — same pattern as the Z-order UDF, looks right. Did the JMH run compare against Z-order interleaving on the same inputs? A one-line relative number in the PR body would help reviewers weigh the added curve math.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] API, Core, Spark: Add Hilbert-curve clustering strategy for `rewrite_data_files` [iceberg]
Posted by "gimgit (via GitHub)" <gi...@apache.org>.
gimgit commented on PR #16827:
URL: https://github.com/apache/iceberg/pull/16827#issuecomment-5403737409
No remaining comments from me. Both points I raised were addressed — the benchmark report answered the cost question (and the transpose buffering that came out of it was a nice win), and the re-clustering detection question is deferred to a follow-up issue, which I think is the right call. LGTM.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] API, Core, Spark: Add Hilbert-curve clustering strategy for `rewrite_data_files` [iceberg]
Posted by "GGraziadei (via GitHub)" <gi...@apache.org>.
GGraziadei commented on PR #16827:
URL: https://github.com/apache/iceberg/pull/16827#issuecomment-5373746498
Hi @RussellSpitzer, following my profiler analysis, I have a quick note regarding bit interleaving. Since it intersects with Zorder as well, I've opened a separate issue for it. We can keep this thread moving asynchronously:
https://github.com/apache/iceberg/issues/17758
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org