You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@iceberg.apache.org by "JeonDaehong (via GitHub)" <gi...@apache.org> on 2026/09/09 12:05:48 UTC
[PR] Core, Spark 4.2: Avoid per-row path rehashing in toPositionIndexes [iceberg]
JeonDaehong opened a new pull request, #18027:
URL: https://github.com/apache/iceberg/pull/18027
`ColumnarBatchUtil.buildRowIdMapping` and `buildIsDeleted` call `PositionDeleteIndex.isDeleted(pos)` once for every row in a batch. Because positions within a batch form a contiguous ascending range, each call repeats redundant work: extracting high/low keys, checking bitmap array bounds, and performing binary searches on the container array. None of this is amortized across the batch, even though consecutive calls target the same one or two containers.
This PR introduces `PositionDeleteIndex.forEachInRange(posStart, length, consumer)`, which efficiently traverses deleted positions within a given range in ascending order. The default implementation falls back to the existing per-position loop, while `BitmapPositionDeleteIndex` overrides it to resolve the range to at most two underlying 32-bit bitmaps and walk each once. `ColumnarBatchUtil` now leverages this path when no equality deletes are present; tables with equality deletes retain the previous behavior.
### Performance
Measured on 8M rows across 4 files (single-column projection, 3 runs per configuration in separate JVMs, sampled via async-profiler `ctimer` for delete-check CPU usage):
| delete density | container | current | patched | reduction |
|---|---|---|---|---|
| 0.5% | array | 674 | 79 | 8.6x |
| 6.1% | array | 873 | 94 | 9.3x |
| 7.0% | bitmap | 420 | 113 | 3.7x |
| 8.0% | bitmap | 499 | 142 | 3.5x |
| 50% | bitmap | 584 | 225 | 2.6x |
The largest speedup occurs just below the array/bitmap threshold, where eliminating per-row binary searches provides the biggest relief. Notably, `buildIsDeleted` sees a **14.9x–18.9x** improvement since it avoids filling gaps between deleted positions.
### Correctness & Scope
- **Correctness verified:** `count(*)`, `sum(id)`, and `min/max(id)` results across 7 test tables match the baseline identically. Tables with equality deletes show zero performance regression.
- **Scope:** This PR targets `spark/v4.2` first to keep the diff concise and reviewable. Since `ColumnarBatchUtil` is byte-identical in `v3.5`, `v4.0`, and `v4.1`, I will follow up with backports once the overall design is approved.
For additional benchmarks—including cross-microarchitecture validation, local vs. S3 performance, cold/warm cache behavior, scaling from 1–16 parallel tasks, cluster runs, and hardware counters—along with edge-case performance bounds, please refer to #18026.
Closes #18026
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "pvary (via GitHub)" <gi...@apache.org>.
pvary commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4003071316
##########
spark/v4.2/spark/src/main/java/org/apache/iceberg/spark/data/vectorized/ColumnarBatchUtil.java:
##########
@@ -83,6 +91,27 @@ public static Pair<int[], Integer> buildRowIdMapping(
return liveRowId == batchSize ? null : Pair.of(rowIdMapping, liveRowId);
}
+ // builds the mapping from the deleted positions in the batch range, without probing per row
+ private static Pair<int[], Integer> buildRowIdMapping(
+ PositionDeleteIndex deletedPositions,
+ DeleteFilter<InternalRow> deletes,
+ long rowStartPosInBatch,
+ int batchSize) {
+ RowIdMappingBuilder builder = new RowIdMappingBuilder(rowStartPosInBatch, batchSize);
Review Comment:
Could we shortcut if there are no deletes?
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4005585231
##########
core/src/test/java/org/apache/iceberg/deletes/TestPositionDeleteIndexForEachInRange.java:
##########
@@ -0,0 +1,227 @@
+/*
+ * 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.deletes;
+
+import static org.assertj.core.api.Assertions.assertThat;
+
+import java.util.List;
+import java.util.Random;
+import java.util.Set;
+import org.apache.iceberg.relocated.com.google.common.collect.Lists;
+import org.apache.iceberg.relocated.com.google.common.collect.Sets;
+import org.junit.jupiter.api.Test;
+
+/**
+ * Verifies that {@link PositionDeleteIndex#forEachInRange(long, int,
+ * java.util.function.LongConsumer)} returns exactly the positions that {@link
+ * PositionDeleteIndex#isDeleted(long)} reports as deleted in the same range, in ascending order,
+ * for every implementation.
+ */
+public class TestPositionDeleteIndexForEachInRange {
Review Comment:
The file is gone now, see below. the tests moved into the two existing classes and follow their style.
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "pvary (via GitHub)" <gi...@apache.org>.
pvary commented on PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#issuecomment-5660805618
Could you please add JMH test to show the gains?
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#issuecomment-5722242936
@nastra
Thanks for taking a look! I appreciate it. Please take your time with the tests, and let me know if you have any feedback.
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#issuecomment-5603751242
Hello @aokolnychyi @huaxingao
Tagging you as the people who have worked most on these files. No rush at all, a look whenever you have time would be much appreciated.
I tried to make this easy to evaluate rather than something you have to take on trust. The change was measured across delete densities from 0.5% to 50%, on three CPU microarchitectures, and on both local disk and S3. I also used hardware counters to verify the underlying mechanism instead of inferring it from timings, which is actually how I realized my initial explanation for the cost was incorrect. The linked issue also lists the conditions under which these numbers do not hold.
I am happy to adjust the approach if you see a better way forward. If this direction looks right, I will backport it to v3.5, v4.0, and v4.1 in a follow-up PR.
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "nastra (via GitHub)" <gi...@apache.org>.
nastra commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4060744867
##########
core/src/test/java/org/apache/iceberg/deletes/TestRoaringPositionBitmap.java:
##########
@@ -350,6 +350,132 @@ public void testAddAllSparseBitmaps() {
assertThat(bitmap1.cardinality()).isEqualTo(4);
}
+ @TestTemplate
+ public void testForEachInRange() {
+ RoaringPositionBitmap bitmap = new RoaringPositionBitmap();
+ bitmap.setRange(10L, 20L);
+
+ // the beginning is inclusive and the end is exclusive
Review Comment:
can be omitted
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "pvary (via GitHub)" <gi...@apache.org>.
pvary commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4003139668
##########
spark/v4.2/spark/src/main/java/org/apache/iceberg/spark/data/vectorized/ColumnarBatchUtil.java:
##########
@@ -119,6 +148,16 @@ public static boolean[] buildIsDeleted(
}
PositionDeleteIndex deletedPositions = deletes.deletedRowPositions();
+
+ if (deletedPositions != null && !deletes.hasEqDeletes()) {
+ IsDeletedBuilder builder = new IsDeletedBuilder(isDeleted, rowStartPosInBatch);
+ deletedPositions.forEachInRange(rowStartPosInBatch, batchSize, builder);
+ for (int index = 0; index < builder.deletedRowCount(); index++) {
+ deletes.incrementDeleteCount();
Review Comment:
Could we just call it inside the IsDeletedBuilder.accept?
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4005687649
##########
spark/v4.2/spark/src/main/java/org/apache/iceberg/spark/data/vectorized/ColumnarBatchUtil.java:
##########
@@ -119,6 +148,16 @@ public static boolean[] buildIsDeleted(
}
PositionDeleteIndex deletedPositions = deletes.deletedRowPositions();
+
+ if (deletedPositions != null && !deletes.hasEqDeletes()) {
+ IsDeletedBuilder builder = new IsDeletedBuilder(isDeleted, rowStartPosInBatch);
+ deletedPositions.forEachInRange(rowStartPosInBatch, batchSize, builder);
+ for (int index = 0; index < builder.deletedRowCount(); index++) {
+ deletes.incrementDeleteCount();
Review Comment:
Done. `IsDeletedBuilder` now takes the `DeleteFilter` and increments in `accept`, so the counter field and its accessor are gone along with the loop.
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#issuecomment-5636019001
Ah, thank you for the feedback!
I'll revise it and post it to the mailing list again.
I'd really appreciate it if you could take a look and give me some feedback once I post it there. 😄
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "pvary (via GitHub)" <gi...@apache.org>.
pvary commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4036700191
##########
core/src/main/java/org/apache/iceberg/deletes/PositionDeleteIndex.java:
##########
@@ -79,6 +80,32 @@ default void forEach(LongConsumer consumer) {
}
}
+ /**
+ * Traverses the deleted positions within the given range in ascending order, applying the
+ * provided consumer.
+ *
+ * <p>Callers that test a contiguous range of positions should prefer this method over calling
+ * {@link #isDeleted(long)} once per position.
+ *
+ * @param posStart inclusive beginning of position range
+ * @param posEnd exclusive ending of position range
+ * @param consumer a consumer for the deleted positions in the range
+ * @throws IllegalArgumentException if posStart > posEnd
+ */
+ default void forEachInRange(long posStart, long posEnd, LongConsumer consumer) {
Review Comment:
`PositionDeleteIndex.forEach(consumer)` only calls the `consumer` for the position set in the index. So for only the deleted positions. This is the same for the `forEachInRange`.
Good catch on the naming!
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4005701691
##########
spark/v4.2/spark/src/main/java/org/apache/iceberg/spark/data/vectorized/ColumnarBatchUtil.java:
##########
@@ -83,6 +91,27 @@ public static Pair<int[], Integer> buildRowIdMapping(
return liveRowId == batchSize ? null : Pair.of(rowIdMapping, liveRowId);
}
+ // builds the mapping from the deleted positions in the batch range, without probing per row
+ private static Pair<int[], Integer> buildRowIdMapping(
+ PositionDeleteIndex deletedPositions,
+ DeleteFilter<InternalRow> deletes,
+ long rowStartPosInBatch,
+ int batchSize) {
+ RowIdMappingBuilder builder = new RowIdMappingBuilder(rowStartPosInBatch, batchSize);
+ deletedPositions.forEachInRange(rowStartPosInBatch, batchSize, builder);
+ int liveRowId = builder.build();
+
+ if (liveRowId == batchSize) {
+ return null;
+ }
+
+ for (int index = liveRowId; index < batchSize; index++) {
+ deletes.incrementDeleteCount();
+ }
Review Comment:
I applied the same idea you suggested for `IsDeletedBuilder` here as well
`RowIdMappingBuilder.accept` is called once per deleted position, so incrementing there removes this loop entirely rather than making it easier to read. That means I didn't commit the suggestion literally — let me know if you'd rather keep an explicit loop.
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "pvary (via GitHub)" <gi...@apache.org>.
pvary commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4003118313
##########
core/src/test/java/org/apache/iceberg/deletes/TestPositionDeleteIndexForEachInRange.java:
##########
@@ -0,0 +1,227 @@
+/*
+ * 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.deletes;
+
+import static org.assertj.core.api.Assertions.assertThat;
+
+import java.util.List;
+import java.util.Random;
+import java.util.Set;
+import org.apache.iceberg.relocated.com.google.common.collect.Lists;
+import org.apache.iceberg.relocated.com.google.common.collect.Sets;
+import org.junit.jupiter.api.Test;
+
+/**
+ * Verifies that {@link PositionDeleteIndex#forEachInRange(long, int,
+ * java.util.function.LongConsumer)} returns exactly the positions that {@link
+ * PositionDeleteIndex#isDeleted(long)} reports as deleted in the same range, in ascending order,
+ * for every implementation.
+ */
+public class TestPositionDeleteIndexForEachInRange {
+
+ private static final long CHUNK_SIZE = 65536L;
+ private static final long BITMAP_SIZE = 0xFFFFFFFFL + 1L;
+
+ @Test
+ public void testEmptyIndex() {
Review Comment:
package private - no `test` prefix
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "pvary (via GitHub)" <gi...@apache.org>.
pvary commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4015586223
##########
core/src/main/java/org/apache/iceberg/deletes/RoaringPositionBitmap.java:
##########
@@ -192,6 +193,43 @@ public void forEach(LongConsumer consumer) {
}
}
+ /**
+ * Iterates over the positions set within the given range, in ascending order.
+ *
+ * <p>Each underlying 32-bit bitmap that the range covers is traversed once, instead of resolving
+ * the containing bitmap for every position as {@link #contains(long)} does.
+ *
+ * @param posStartInclusive inclusive beginning of position range
+ * @param posEndExclusive exclusive ending of position range
+ * @param consumer a consumer for the positions that are set within the range
+ */
+ public void forEachInRange(long posStartInclusive, long posEndExclusive, LongConsumer consumer) {
+ Preconditions.checkArgument(
+ posStartInclusive <= posEndExclusive,
+ "Start position must not exceed end position: [%s, %s)",
+ posStartInclusive,
+ posEndExclusive);
+
+ if (posStartInclusive == posEndExclusive) {
+ return;
+ }
+
+ validatePosition(posStartInclusive);
+ validatePosition(posEndExclusive - 1);
+
+ int startKey = key(posStartInclusive);
+ int endKey = key(posEndExclusive - 1);
+
+ for (int key = startKey; key <= endKey && key < bitmaps.length; key++) {
+ long lowStart = key == startKey ? Integer.toUnsignedLong(pos32Bits(posStartInclusive)) : 0L;
+ long lowEnd =
+ key == endKey
+ ? Integer.toUnsignedLong(pos32Bits(posEndExclusive - 1)) + 1
+ : MAX_POS_32_BITS + 1;
Review Comment:
Is this the same as `1L << 32` used elsewhere?
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "pvary (via GitHub)" <gi...@apache.org>.
pvary commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4015725518
##########
spark/v4.2/spark/src/main/java/org/apache/iceberg/spark/data/vectorized/ColumnarBatchUtil.java:
##########
@@ -64,6 +65,13 @@ public static Pair<int[], Integer> buildRowIdMapping(
}
PositionDeleteIndex deletedPositions = deletes.deletedRowPositions();
+
+ // positions in a batch form a contiguous ascending range, so the index can be traversed once
+ // for the whole range instead of being probed once per row
+ if (deletedPositions != null && !deletes.hasEqDeletes()) {
Review Comment:
Do we want to short circuit the `no-deletes` case as well?
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "pvary (via GitHub)" <gi...@apache.org>.
pvary commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4015656085
##########
spark/v4.2/spark/src/main/java/org/apache/iceberg/spark/data/vectorized/ColumnarBatchUtil.java:
##########
@@ -178,4 +207,71 @@ public static ColumnVector[] removeExtraColumns(
return columnVectors;
}
}
+
+ /**
+ * Consumes deleted positions in ascending order, filling the gaps between them with live row IDs.
+ */
+ private static class RowIdMappingBuilder implements LongConsumer {
Review Comment:
nit: rename, as it is not a Builder anymore
##########
spark/v4.2/spark/src/main/java/org/apache/iceberg/spark/data/vectorized/ColumnarBatchUtil.java:
##########
@@ -178,4 +207,71 @@ public static ColumnVector[] removeExtraColumns(
return columnVectors;
}
}
+
+ /**
+ * Consumes deleted positions in ascending order, filling the gaps between them with live row IDs.
+ */
+ private static class RowIdMappingBuilder implements LongConsumer {
+ private final DeleteFilter<InternalRow> deletes;
+ private final long rowStartPosInBatch;
+ private final int batchSize;
+ private final int[] rowIdMapping;
+ private int nextRowId = 0;
+ private int liveRowId = 0;
+
+ RowIdMappingBuilder(DeleteFilter<InternalRow> deletes, long rowStartPosInBatch, int batchSize) {
+ this.deletes = deletes;
+ this.rowStartPosInBatch = rowStartPosInBatch;
+ this.batchSize = batchSize;
+ this.rowIdMapping = new int[batchSize];
+ }
+
+ @Override
+ public void accept(long pos) {
+ int deletedRowId = (int) (pos - rowStartPosInBatch);
+ for (int rowId = nextRowId; rowId < deletedRowId; rowId++) {
+ rowIdMapping[liveRowId] = rowId;
+ liveRowId++;
+ }
+
+ deletes.incrementDeleteCount();
+ this.nextRowId = deletedRowId + 1;
+ }
+
+ /** Appends the live rows that follow the last deleted position in the batch. */
+ void appendRemainingLiveRows() {
+ for (int rowId = nextRowId; rowId < batchSize; rowId++) {
+ rowIdMapping[liveRowId] = rowId;
+ liveRowId++;
+ }
+ }
+
+ int liveRowCount() {
+ return liveRowId;
+ }
+
+ int[] rowIdMapping() {
+ return rowIdMapping;
+ }
+ }
+
+ /** Consumes deleted positions in a batch range, marking them in the given array. */
+ private static class IsDeletedBuilder implements LongConsumer {
Review Comment:
nit: rename, as it is not a Builder anymore
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4005615500
##########
core/src/test/java/org/apache/iceberg/deletes/TestPositionDeleteIndexForEachInRange.java:
##########
@@ -0,0 +1,227 @@
+/*
+ * 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.deletes;
+
+import static org.assertj.core.api.Assertions.assertThat;
+
+import java.util.List;
+import java.util.Random;
+import java.util.Set;
+import org.apache.iceberg.relocated.com.google.common.collect.Lists;
+import org.apache.iceberg.relocated.com.google.common.collect.Sets;
+import org.junit.jupiter.api.Test;
+
+/**
+ * Verifies that {@link PositionDeleteIndex#forEachInRange(long, int,
+ * java.util.function.LongConsumer)} returns exactly the positions that {@link
+ * PositionDeleteIndex#isDeleted(long)} reports as deleted in the same range, in ascending order,
+ * for every implementation.
+ */
+public class TestPositionDeleteIndexForEachInRange {
Review Comment:
Removed the file and moved the tests into the existing two classes to match their style.
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "pvary (via GitHub)" <gi...@apache.org>.
pvary commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4015485875
##########
core/src/main/java/org/apache/iceberg/deletes/RoaringPositionBitmap.java:
##########
@@ -192,6 +193,43 @@ public void forEach(LongConsumer consumer) {
}
}
+ /**
+ * Iterates over the positions set within the given range, in ascending order.
+ *
+ * <p>Each underlying 32-bit bitmap that the range covers is traversed once, instead of resolving
+ * the containing bitmap for every position as {@link #contains(long)} does.
+ *
+ * @param posStartInclusive inclusive beginning of position range
+ * @param posEndExclusive exclusive ending of position range
+ * @param consumer a consumer for the positions that are set within the range
+ */
+ public void forEachInRange(long posStartInclusive, long posEndExclusive, LongConsumer consumer) {
+ Preconditions.checkArgument(
Review Comment:
I would do this check for every implementation.
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4005851410
##########
spark/v4.2/spark/src/test/java/org/apache/iceberg/spark/data/vectorized/TestColumnarBatchUtil.java:
##########
@@ -288,6 +267,116 @@ void testRemoveExtraColumnsNotNeeded() {
assertThat(result.length).isEqualTo(3);
}
+ @Test
+ void testBuildRowIdMappingNonZeroBatchStart() {
+ // batches after the first one start at a non-zero position in the file
+ long rowStartPosInBatch = 1_000_000L;
+ when(deleteFilter.hasPosDeletes()).thenReturn(true);
+ when(deleteFilter.deletedRowPositions())
+ .thenReturn(positionIndex(1_000_000L, 1_000_003L, 1_000_009L));
+
+ var rowIdMapping =
+ ColumnarBatchUtil.buildRowIdMapping(columnVectors, deleteFilter, rowStartPosInBatch, 10);
+
+ assertThat(rowIdMapping).isNotNull();
+ int[] rowIds = (int[]) rowIdMapping.first();
+ int liveRows = (Integer) rowIdMapping.second();
+
+ assertThat(liveRows).isEqualTo(7);
+ assertThat(Arrays.copyOf(rowIds, liveRows)).containsExactly(1, 2, 4, 5, 6, 7, 8);
+ verify(deleteFilter, times(3)).incrementDeleteCount();
+ }
+
+ @Test
+ void testBuildRowIdMappingDeletesOutsideBatch() {
+ // the index covers the whole file, so most batches see no deletes at all
+ when(deleteFilter.hasPosDeletes()).thenReturn(true);
+ when(deleteFilter.deletedRowPositions()).thenReturn(positionIndex(5L, 6L, 500L, 501L));
+
+ var rowIdMapping = ColumnarBatchUtil.buildRowIdMapping(columnVectors, deleteFilter, 100L, 100);
+
+ assertThat(rowIdMapping).isNull();
+ verify(deleteFilter, times(0)).incrementDeleteCount();
+ }
+
+ @Test
+ void testBuildRowIdMappingAllRowsDeletedByPosition() {
+ when(deleteFilter.hasPosDeletes()).thenReturn(true);
+ when(deleteFilter.deletedRowPositions()).thenReturn(positionIndex(0L, 1L, 2L, 3L, 4L));
+
+ var rowIdMapping = ColumnarBatchUtil.buildRowIdMapping(columnVectors, deleteFilter, 0, 5);
+
+ assertThat(rowIdMapping).isNotNull();
+ assertThat((Integer) rowIdMapping.second()).isEqualTo(0);
+ verify(deleteFilter, times(5)).incrementDeleteCount();
+ }
+
+ @Test
+ void testBuildIsDeletedNonZeroBatchStart() {
+ when(deleteFilter.deletedRowPositions()).thenReturn(positionIndex(1_000_002L, 1_000_004L));
+
+ var isDeleted = ColumnarBatchUtil.buildIsDeleted(columnVectors, deleteFilter, 1_000_000L, 5);
+
+ assertThat(isDeleted).containsExactly(false, false, true, false, true);
+ verify(deleteFilter, times(2)).incrementDeleteCount();
+ }
+
+ @Test
+ void testPositionOnlyPathMatchesPerRowPath() {
+ // the range traversal must agree with a straightforward per-row probe on every batch
+ java.util.Random random = new java.util.Random(20260818L);
Review Comment:
Done !
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4037353092
##########
core/src/main/java/org/apache/iceberg/deletes/PositionDeleteIndex.java:
##########
@@ -79,6 +80,32 @@ default void forEach(LongConsumer consumer) {
}
}
+ /**
+ * Traverses the deleted positions within the given range in ascending order, applying the
+ * provided consumer.
+ *
+ * <p>Callers that test a contiguous range of positions should prefer this method over calling
+ * {@link #isDeleted(long)} once per position.
+ *
+ * @param posStart inclusive beginning of position range
+ * @param posEnd exclusive ending of position range
+ * @param consumer a consumer for the deleted positions in the range
+ * @throws IllegalArgumentException if posStart > posEnd
+ */
+ default void forEachInRange(long posStart, long posEnd, LongConsumer consumer) {
Review Comment:
Renamed in the interface and both implementations.
Thanks to Peter for the clarification -- keeping forEachInRange().
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4037273625
##########
core/src/main/java/org/apache/iceberg/deletes/PositionDeleteIndex.java:
##########
@@ -79,6 +80,32 @@ default void forEach(LongConsumer consumer) {
}
}
+ /**
+ * Traverses the deleted positions within the given range in ascending order, applying the
+ * provided consumer.
+ *
+ * <p>Callers that test a contiguous range of positions should prefer this method over calling
Review Comment:
Thanks for feedback.
I've removed it.
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "pvary (via GitHub)" <gi...@apache.org>.
pvary commented on PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#issuecomment-5763550994
Merged to main.
Thanks @JeonDaehong for the performance improvement PR and @nastra for the review!
@JeonDaehong: Please don't forget to create a PR to backport the changes to the other Spark branches.
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#issuecomment-5661289184
@pvary
Thanks a lot for the detailed feedback! I'll make sure to address all of your comments, including the JMH test, in about 5 hours after I wrap up work. :D
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "pvary (via GitHub)" <gi...@apache.org>.
pvary commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4003123455
##########
core/src/test/java/org/apache/iceberg/deletes/TestPositionDeleteIndexForEachInRange.java:
##########
@@ -0,0 +1,227 @@
+/*
+ * 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.deletes;
+
+import static org.assertj.core.api.Assertions.assertThat;
+
+import java.util.List;
+import java.util.Random;
+import java.util.Set;
+import org.apache.iceberg.relocated.com.google.common.collect.Lists;
+import org.apache.iceberg.relocated.com.google.common.collect.Sets;
+import org.junit.jupiter.api.Test;
+
+/**
+ * Verifies that {@link PositionDeleteIndex#forEachInRange(long, int,
+ * java.util.function.LongConsumer)} returns exactly the positions that {@link
+ * PositionDeleteIndex#isDeleted(long)} reports as deleted in the same range, in ascending order,
+ * for every implementation.
+ */
+public class TestPositionDeleteIndexForEachInRange {
Review Comment:
Why new test class?
Shall we put these into `TestRoaringPositionBitmap`, or `TestBitmapPositionDeleteIndex`?
##########
core/src/test/java/org/apache/iceberg/deletes/TestPositionDeleteIndexForEachInRange.java:
##########
@@ -0,0 +1,227 @@
+/*
+ * 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.deletes;
+
+import static org.assertj.core.api.Assertions.assertThat;
+
+import java.util.List;
+import java.util.Random;
+import java.util.Set;
+import org.apache.iceberg.relocated.com.google.common.collect.Lists;
+import org.apache.iceberg.relocated.com.google.common.collect.Sets;
+import org.junit.jupiter.api.Test;
+
+/**
+ * Verifies that {@link PositionDeleteIndex#forEachInRange(long, int,
+ * java.util.function.LongConsumer)} returns exactly the positions that {@link
+ * PositionDeleteIndex#isDeleted(long)} reports as deleted in the same range, in ascending order,
+ * for every implementation.
+ */
+public class TestPositionDeleteIndexForEachInRange {
+
+ private static final long CHUNK_SIZE = 65536L;
+ private static final long BITMAP_SIZE = 0xFFFFFFFFL + 1L;
+
+ @Test
+ public void testEmptyIndex() {
Review Comment:
package private - no `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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "pvary (via GitHub)" <gi...@apache.org>.
pvary commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4003098110
##########
core/src/main/java/org/apache/iceberg/deletes/RoaringPositionBitmap.java:
##########
@@ -192,6 +193,38 @@ public void forEach(LongConsumer consumer) {
}
}
+ /**
+ * Iterates over the positions set within the given range, in ascending order.
+ *
+ * <p>The range is resolved to at most two underlying 32-bit bitmaps, each of which is traversed
+ * once. This avoids the per-position key extraction, bounds check and container lookup that
+ * {@link #contains(long)} performs on every call.
+ *
+ * @param posStart the first position in the range, inclusive
+ * @param length the number of positions in the range
+ * @param consumer a consumer for the positions that are set within the range
+ */
+ public void forEachInRange(long posStart, int length, LongConsumer consumer) {
+ if (length <= 0) {
+ return;
+ }
Review Comment:
Shall we throw instead?
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4005526662
##########
core/src/main/java/org/apache/iceberg/deletes/PositionDeleteIndex.java:
##########
@@ -79,6 +79,28 @@ default void forEach(LongConsumer consumer) {
}
}
+ /**
+ * Traverses the deleted positions within the given range in ascending order, applying the
+ * provided consumer.
+ *
+ * <p>Callers that test a contiguous range of positions should prefer this method over calling
+ * {@link #isDeleted(long)} once per position. Implementations backed by a bitmap can locate the
+ * containers covering the range once and walk them, instead of resolving the container for every
+ * position.
+ *
+ * @param posStart the first position in the range, inclusive
+ * @param length the number of positions in the range
+ * @param consumer a consumer for the deleted positions in the range
+ */
+ default void forEachInRange(long posStart, int length, LongConsumer consumer) {
Review Comment:
Done, and thanks for catching it — this turned out to be more than just a rename.
The old implementation relied on `length` being an `int` to guarantee a range spans at most two 32-bit keys, and the comment said so explicitly. With a `long` end that no longer holds, so the per-key loop is now general, and the inner traversal chunks any sub-range wider than `Integer.MAX_VALUE` (`RoaringPositionBitmap.forEachInRange` takes an int length, so a fully covered middle bitmap cannot be expressed in one call).
`RoaringPositionBitmap.forEachInRange` now follows `setRange` for parameter names, for the precondition, and for treating an empty range as a no-op, so the two read the same way. Added a test for a range spanning three keys, which is the path that did not exist before.
##########
core/src/main/java/org/apache/iceberg/deletes/PositionDeleteIndex.java:
##########
@@ -79,6 +79,28 @@ default void forEach(LongConsumer consumer) {
}
}
+ /**
+ * Traverses the deleted positions within the given range in ascending order, applying the
+ * provided consumer.
+ *
+ * <p>Callers that test a contiguous range of positions should prefer this method over calling
+ * {@link #isDeleted(long)} once per position. Implementations backed by a bitmap can locate the
+ * containers covering the range once and walk them, instead of resolving the container for every
+ * position.
+ *
+ * @param posStart the first position in the range, inclusive
+ * @param length the number of positions in the range
+ * @param consumer a consumer for the deleted positions in the range
+ */
+ default void forEachInRange(long posStart, int length, LongConsumer consumer) {
Review Comment:
Done, and thanks for catching it... this turned out to be more than just a rename.
The old implementation relied on `length` being an `int` to guarantee a range spans at most two 32-bit keys, and the comment said so explicitly. With a `long` end that no longer holds, so the per-key loop is now general, and the inner traversal chunks any sub-range wider than `Integer.MAX_VALUE` (`RoaringPositionBitmap.forEachInRange` takes an int length, so a fully covered middle bitmap cannot be expressed in one call).
`RoaringPositionBitmap.forEachInRange` now follows `setRange` for parameter names, for the precondition, and for treating an empty range as a no-op, so the two read the same way. Added a test for a range spanning three keys, which is the path that did not exist before.
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4005544868
##########
core/src/main/java/org/apache/iceberg/deletes/PositionDeleteIndex.java:
##########
@@ -79,6 +79,28 @@ default void forEach(LongConsumer consumer) {
}
}
+ /**
+ * Traverses the deleted positions within the given range in ascending order, applying the
+ * provided consumer.
+ *
+ * <p>Callers that test a contiguous range of positions should prefer this method over calling
+ * {@link #isDeleted(long)} once per position. Implementations backed by a bitmap can locate the
+ * containers covering the range once and walk them, instead of resolving the container for every
+ * position.
Review Comment:
Done. dropped the paragraph about locating containers, left only the contract.
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4005585231
##########
core/src/test/java/org/apache/iceberg/deletes/TestPositionDeleteIndexForEachInRange.java:
##########
@@ -0,0 +1,227 @@
+/*
+ * 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.deletes;
+
+import static org.assertj.core.api.Assertions.assertThat;
+
+import java.util.List;
+import java.util.Random;
+import java.util.Set;
+import org.apache.iceberg.relocated.com.google.common.collect.Lists;
+import org.apache.iceberg.relocated.com.google.common.collect.Sets;
+import org.junit.jupiter.api.Test;
+
+/**
+ * Verifies that {@link PositionDeleteIndex#forEachInRange(long, int,
+ * java.util.function.LongConsumer)} returns exactly the positions that {@link
+ * PositionDeleteIndex#isDeleted(long)} reports as deleted in the same range, in ascending order,
+ * for every implementation.
+ */
+public class TestPositionDeleteIndexForEachInRange {
Review Comment:
The file is gone now, see below. the tests moved into the two existing classes and follow their style.
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#issuecomment-5689443195
@pvary
The kafka-connect job failed while resolving dependencies... Maven Central returned 403s for zstd-jni, lz4-java, and javax.ws.rs-api, all of which are pulled in by kafka-clients.
It failed after 18s before any tests ran, and this PR doesn't touch that module.
Looks like a transient issue.
I don't have permission to re-run it
could you kick it off when you get a chance?
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "nastra (via GitHub)" <gi...@apache.org>.
nastra commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4060724526
##########
core/src/test/java/org/apache/iceberg/deletes/TestBitmapPositionDeleteIndex.java:
##########
@@ -235,4 +366,60 @@ private List<Long> collect(PositionDeleteIndex index) {
index.forEach(positions::add);
return positions;
}
+
+ private static List<Long> collect(PositionDeleteIndex index, long posStart, long posEnd) {
Review Comment:
maybe name this `forEachInRange` or `positionsInRange`?
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#issuecomment-5693853644
@pvary
Thanks for the suggestion! I’d be happy to add it to the agenda and sync with the community, but I’m a little concerned about presenting in English given the timing in Korea.
Would it be okay to add it as a discussion item instead, so I can simply sync with the community without giving a formal presentation?
If so, where would I be able to follow up on the discussion, including any Q&A or feedback?
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4021003700
##########
spark/v4.2/spark/src/main/java/org/apache/iceberg/spark/data/vectorized/ColumnarBatchUtil.java:
##########
@@ -119,6 +144,14 @@ public static boolean[] buildIsDeleted(
}
PositionDeleteIndex deletedPositions = deletes.deletedRowPositions();
+
+ if (deletedPositions != null && !deletes.hasEqDeletes()) {
Review Comment:
Not intentional.
I folded the branches in `buildRowIdMapping`
and left `buildIsDeleted` behind, so the two read differently for the same
condition.
They now have the same shape, and `buildIsDeleted` also skips the per-row
loop when there is nothing deleted at all
```
if (!deletes.hasEqDeletes()) {
// positions in a batch form a contiguous ascending range, so the index
// can be traversed once for the whole range instead of being probed
// once per row
if (deletedPositions != null) {
IsDeletedCollector collector =
new IsDeletedCollector(deletes, isDeleted, rowStartPosInBatch);
deletedPositions.forEachInRange(
rowStartPosInBatch, rowStartPosInBatch + batchSize, collector);
}
return isDeleted;
}
```
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4005496711
##########
spark/v4.2/spark/src/main/java/org/apache/iceberg/spark/data/vectorized/ColumnarBatchUtil.java:
##########
@@ -83,6 +91,27 @@ public static Pair<int[], Integer> buildRowIdMapping(
return liveRowId == batchSize ? null : Pair.of(rowIdMapping, liveRowId);
}
+ // builds the mapping from the deleted positions in the batch range, without probing per row
+ private static Pair<int[], Integer> buildRowIdMapping(
+ PositionDeleteIndex deletedPositions,
+ DeleteFilter<InternalRow> deletes,
+ long rowStartPosInBatch,
+ int batchSize) {
+ RowIdMappingBuilder builder = new RowIdMappingBuilder(rowStartPosInBatch, batchSize);
Review Comment:
Done. The fast path now returns null right away when the index is empty, before touching the range.
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4005537738
##########
core/src/main/java/org/apache/iceberg/deletes/RoaringPositionBitmap.java:
##########
@@ -192,6 +193,38 @@ public void forEach(LongConsumer consumer) {
}
}
+ /**
+ * Iterates over the positions set within the given range, in ascending order.
+ *
+ * <p>The range is resolved to at most two underlying 32-bit bitmaps, each of which is traversed
+ * once. This avoids the per-position key extraction, bounds check and container lookup that
+ * {@link #contains(long)} performs on every call.
+ *
+ * @param posStart the first position in the range, inclusive
+ * @param length the number of positions in the range
+ * @param consumer a consumer for the positions that are set within the range
+ */
+ public void forEachInRange(long posStart, int length, LongConsumer consumer) {
+ if (length <= 0) {
+ return;
+ }
Review Comment:
Done. It now uses the same precondition and message as `setRange` ("Start position must not exceed end position: [%s, %s)"), and an empty range where start equals end stays a no-op, also matching `setRange`.
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4005683036
##########
core/src/test/java/org/apache/iceberg/deletes/TestPositionDeleteIndexForEachInRange.java:
##########
@@ -0,0 +1,227 @@
+/*
+ * 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.deletes;
+
+import static org.assertj.core.api.Assertions.assertThat;
+
+import java.util.List;
+import java.util.Random;
+import java.util.Set;
+import org.apache.iceberg.relocated.com.google.common.collect.Lists;
+import org.apache.iceberg.relocated.com.google.common.collect.Sets;
+import org.junit.jupiter.api.Test;
+
+/**
+ * Verifies that {@link PositionDeleteIndex#forEachInRange(long, int,
+ * java.util.function.LongConsumer)} returns exactly the positions that {@link
+ * PositionDeleteIndex#isDeleted(long)} reports as deleted in the same range, in ascending order,
+ * for every implementation.
+ */
+public class TestPositionDeleteIndexForEachInRange {
Review Comment:
Thought about creating a new test class, but on second thought it didn't seem right, so I dropped it and split the tests by what they actually exercise
* `TestRoaringPositionBitmap` : container and key boundaries, a range spanning three keys, ranges past the allocated bitmaps, run containers after runLengthEncode, the new precondition, and a randomized comparison against contains.
* `TestBitmapPositionDeleteIndex` : the range contract (inclusive start, exclusive end), ascending order, empty index and empty range, and a randomized comparison against isDeleted for both the bitmap-backed index and the interface default.
org.apache.iceberg.deletes went from 55 to 63 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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4005546540
##########
spark/v4.2/spark/src/test/java/org/apache/iceberg/spark/data/vectorized/TestColumnarBatchUtil.java:
##########
@@ -288,6 +267,116 @@ void testRemoveExtraColumnsNotNeeded() {
assertThat(result.length).isEqualTo(3);
}
+ @Test
+ void testBuildRowIdMappingNonZeroBatchStart() {
+ // batches after the first one start at a non-zero position in the file
+ long rowStartPosInBatch = 1_000_000L;
+ when(deleteFilter.hasPosDeletes()).thenReturn(true);
+ when(deleteFilter.deletedRowPositions())
+ .thenReturn(positionIndex(1_000_000L, 1_000_003L, 1_000_009L));
+
+ var rowIdMapping =
+ ColumnarBatchUtil.buildRowIdMapping(columnVectors, deleteFilter, rowStartPosInBatch, 10);
+
+ assertThat(rowIdMapping).isNotNull();
+ int[] rowIds = (int[]) rowIdMapping.first();
+ int liveRows = (Integer) rowIdMapping.second();
+
+ assertThat(liveRows).isEqualTo(7);
+ assertThat(Arrays.copyOf(rowIds, liveRows)).containsExactly(1, 2, 4, 5, 6, 7, 8);
+ verify(deleteFilter, times(3)).incrementDeleteCount();
+ }
+
+ @Test
+ void testBuildRowIdMappingDeletesOutsideBatch() {
+ // the index covers the whole file, so most batches see no deletes at all
+ when(deleteFilter.hasPosDeletes()).thenReturn(true);
+ when(deleteFilter.deletedRowPositions()).thenReturn(positionIndex(5L, 6L, 500L, 501L));
+
+ var rowIdMapping = ColumnarBatchUtil.buildRowIdMapping(columnVectors, deleteFilter, 100L, 100);
+
+ assertThat(rowIdMapping).isNull();
+ verify(deleteFilter, times(0)).incrementDeleteCount();
+ }
+
+ @Test
+ void testBuildRowIdMappingAllRowsDeletedByPosition() {
+ when(deleteFilter.hasPosDeletes()).thenReturn(true);
+ when(deleteFilter.deletedRowPositions()).thenReturn(positionIndex(0L, 1L, 2L, 3L, 4L));
+
+ var rowIdMapping = ColumnarBatchUtil.buildRowIdMapping(columnVectors, deleteFilter, 0, 5);
+
+ assertThat(rowIdMapping).isNotNull();
+ assertThat((Integer) rowIdMapping.second()).isEqualTo(0);
+ verify(deleteFilter, times(5)).incrementDeleteCount();
+ }
+
+ @Test
+ void testBuildIsDeletedNonZeroBatchStart() {
+ when(deleteFilter.deletedRowPositions()).thenReturn(positionIndex(1_000_002L, 1_000_004L));
+
+ var isDeleted = ColumnarBatchUtil.buildIsDeleted(columnVectors, deleteFilter, 1_000_000L, 5);
+
+ assertThat(isDeleted).containsExactly(false, false, true, false, true);
+ verify(deleteFilter, times(2)).incrementDeleteCount();
+ }
+
+ @Test
+ void testPositionOnlyPathMatchesPerRowPath() {
+ // the range traversal must agree with a straightforward per-row probe on every batch
+ java.util.Random random = new java.util.Random(20260818L);
Review Comment:
Done.
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#issuecomment-5664923219
@pvary
> Could you please add JMH test to show the gains?
Added PositionDeleteIndexBenchmark in core/src/jmh. It reads 5M positions in 5,000-position batches, the way the vectorized reader does, at densities on either side of the array/bitmap boundary.
JMH 1.37, JDK 21.0.10:
| Benchmark | (density) | Mode | Cnt | Score | Error | Units |
| :--- | :---: | :---: | :---: | :---: | :---: | :---: |
| `PositionDeleteIndexBenchmark.probePerPosition` | 0.5 | ss | 5 | 82.893 | ± 13.257 | ms/op |
| `PositionDeleteIndexBenchmark.probePerPosition` | 6.1 | ss | 5 | 111.101 | ± 43.291 | ms/op |
| `PositionDeleteIndexBenchmark.probePerPosition` | 12.0 | ss | 5 | 68.924 | ± 18.444 | ms/op |
| `PositionDeleteIndexBenchmark.traverseRange` | 0.5 | ss | 5 | 0.369 | ± 0.378 | ms/op |
| `PositionDeleteIndexBenchmark.traverseRange` | 6.1 | ss | 5 | 1.304 | ± 0.891 | ms/op |
| `PositionDeleteIndexBenchmark.traverseRange` | 12.0 | ss | 5 | 2.456 | ± 1.660 | ms/op |
The spread is wide at five single-shot iterations, but the two arms are two orders of magnitude apart, so the comparison holds either way.
Two things are worth noting here:
- **First, the per-position cost is not monotonic in density:** 6.1% is the worst case because the container is still a sorted array near its deepest, and 12% is cheaper because it has flipped to a bitmap.
- **Second, this ratio is much larger than the 2.6–9.3x quoted for the Spark path:** This is because this benchmark measures only the index lookup performance, whereas the delete-check subtree in a real scan also contains DV deserialization, the mapping array write, and the index wrapper, none of which this change touches.
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "pvary (via GitHub)" <gi...@apache.org>.
pvary commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4003116480
##########
core/src/test/java/org/apache/iceberg/deletes/TestPositionDeleteIndexForEachInRange.java:
##########
@@ -0,0 +1,227 @@
+/*
+ * 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.deletes;
+
+import static org.assertj.core.api.Assertions.assertThat;
+
+import java.util.List;
+import java.util.Random;
+import java.util.Set;
+import org.apache.iceberg.relocated.com.google.common.collect.Lists;
+import org.apache.iceberg.relocated.com.google.common.collect.Sets;
+import org.junit.jupiter.api.Test;
+
+/**
+ * Verifies that {@link PositionDeleteIndex#forEachInRange(long, int,
+ * java.util.function.LongConsumer)} returns exactly the positions that {@link
+ * PositionDeleteIndex#isDeleted(long)} reports as deleted in the same range, in ascending order,
+ * for every implementation.
+ */
+public class TestPositionDeleteIndexForEachInRange {
Review Comment:
package private
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4062498831
##########
core/src/test/java/org/apache/iceberg/deletes/TestBitmapPositionDeleteIndex.java:
##########
@@ -235,4 +366,60 @@ private List<Long> collect(PositionDeleteIndex index) {
index.forEach(positions::add);
return positions;
}
+
+ private static List<Long> collect(PositionDeleteIndex index, long posStart, long posEnd) {
Review Comment:
Renamed to `positionsInRange`. Parameters now match the other helper too.
##########
core/src/test/java/org/apache/iceberg/deletes/TestRoaringPositionBitmap.java:
##########
@@ -350,6 +350,132 @@ public void testAddAllSparseBitmaps() {
assertThat(bitmap1.cardinality()).isEqualTo(4);
}
+ @TestTemplate
+ public void testForEachInRange() {
+ RoaringPositionBitmap bitmap = new RoaringPositionBitmap();
+ bitmap.setRange(10L, 20L);
+
+ // the beginning is inclusive and the end is exclusive
Review Comment:
Removed.
##########
core/src/test/java/org/apache/iceberg/deletes/TestRoaringPositionBitmap.java:
##########
@@ -587,6 +713,13 @@ private void assertRandomPositions(RoaringPositionBitmap bitmap, Set<Long> posit
}
}
+ private static List<Long> collectInRange(
Review Comment:
Renamed to `positionsInRange` as well.
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "pvary (via GitHub)" <gi...@apache.org>.
pvary commented on PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#issuecomment-5712259769
> I was wondering if there were any updates or outcomes from the discussion. Would it be possible to know what was discussed?
You can find the recordings on the Apache Iceberg youtube channel.
There were no objections against adding the new API.
@nastra promised a second opinion on the PR.
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4037348989
##########
core/src/main/java/org/apache/iceberg/deletes/EmptyPositionDeleteIndex.java:
##########
@@ -48,6 +51,15 @@ public boolean isEmpty() {
return true;
}
+ @Override
+ public void forEachInRange(long posStart, long posEnd, LongConsumer consumer) {
+ Preconditions.checkArgument(
Review Comment:
Renamed in the interface and both implementations.
Thanks to Peter for the clarification -- keeping `forEachInRange()`. The predicate is probably moot now; let me know if you still want it.
##########
core/src/main/java/org/apache/iceberg/deletes/EmptyPositionDeleteIndex.java:
##########
@@ -48,6 +51,15 @@ public boolean isEmpty() {
return true;
}
+ @Override
+ public void forEachInRange(long posStart, long posEnd, LongConsumer consumer) {
+ Preconditions.checkArgument(
Review Comment:
Renamed in the interface and both implementations.
Thanks to Peter for the clarification -- keeping `forEachInRange()`. The predicate is probably moot now; let me know if you still want it.
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4037314062
##########
core/src/main/java/org/apache/iceberg/deletes/EmptyPositionDeleteIndex.java:
##########
@@ -48,6 +51,15 @@ public boolean isEmpty() {
return true;
}
+ @Override
+ public void forEachInRange(long posStart, long posEnd, LongConsumer consumer) {
+ Preconditions.checkArgument(
Review Comment:
Agreed
Thanks for the `BaseDeleteLoader` pointer, that is the case I had in mind too. Keeping it as is: the override also avoids the default implementation walking the whole range calling `isDeleted`, which is always false 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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "pvary (via GitHub)" <gi...@apache.org>.
pvary commented on PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#issuecomment-5635396466
@JeonDaehong: Could you please link the letter sent to the dev list?
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4005546540
##########
spark/v4.2/spark/src/test/java/org/apache/iceberg/spark/data/vectorized/TestColumnarBatchUtil.java:
##########
@@ -288,6 +267,116 @@ void testRemoveExtraColumnsNotNeeded() {
assertThat(result.length).isEqualTo(3);
}
+ @Test
+ void testBuildRowIdMappingNonZeroBatchStart() {
+ // batches after the first one start at a non-zero position in the file
+ long rowStartPosInBatch = 1_000_000L;
+ when(deleteFilter.hasPosDeletes()).thenReturn(true);
+ when(deleteFilter.deletedRowPositions())
+ .thenReturn(positionIndex(1_000_000L, 1_000_003L, 1_000_009L));
+
+ var rowIdMapping =
+ ColumnarBatchUtil.buildRowIdMapping(columnVectors, deleteFilter, rowStartPosInBatch, 10);
+
+ assertThat(rowIdMapping).isNotNull();
+ int[] rowIds = (int[]) rowIdMapping.first();
+ int liveRows = (Integer) rowIdMapping.second();
+
+ assertThat(liveRows).isEqualTo(7);
+ assertThat(Arrays.copyOf(rowIds, liveRows)).containsExactly(1, 2, 4, 5, 6, 7, 8);
+ verify(deleteFilter, times(3)).incrementDeleteCount();
+ }
+
+ @Test
+ void testBuildRowIdMappingDeletesOutsideBatch() {
+ // the index covers the whole file, so most batches see no deletes at all
+ when(deleteFilter.hasPosDeletes()).thenReturn(true);
+ when(deleteFilter.deletedRowPositions()).thenReturn(positionIndex(5L, 6L, 500L, 501L));
+
+ var rowIdMapping = ColumnarBatchUtil.buildRowIdMapping(columnVectors, deleteFilter, 100L, 100);
+
+ assertThat(rowIdMapping).isNull();
+ verify(deleteFilter, times(0)).incrementDeleteCount();
+ }
+
+ @Test
+ void testBuildRowIdMappingAllRowsDeletedByPosition() {
+ when(deleteFilter.hasPosDeletes()).thenReturn(true);
+ when(deleteFilter.deletedRowPositions()).thenReturn(positionIndex(0L, 1L, 2L, 3L, 4L));
+
+ var rowIdMapping = ColumnarBatchUtil.buildRowIdMapping(columnVectors, deleteFilter, 0, 5);
+
+ assertThat(rowIdMapping).isNotNull();
+ assertThat((Integer) rowIdMapping.second()).isEqualTo(0);
+ verify(deleteFilter, times(5)).incrementDeleteCount();
+ }
+
+ @Test
+ void testBuildIsDeletedNonZeroBatchStart() {
+ when(deleteFilter.deletedRowPositions()).thenReturn(positionIndex(1_000_002L, 1_000_004L));
+
+ var isDeleted = ColumnarBatchUtil.buildIsDeleted(columnVectors, deleteFilter, 1_000_000L, 5);
+
+ assertThat(isDeleted).containsExactly(false, false, true, false, true);
+ verify(deleteFilter, times(2)).incrementDeleteCount();
+ }
+
+ @Test
+ void testPositionOnlyPathMatchesPerRowPath() {
+ // the range traversal must agree with a straightforward per-row probe on every batch
+ java.util.Random random = new java.util.Random(20260818L);
Review Comment:
Done.
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "pvary (via GitHub)" <gi...@apache.org>.
pvary merged PR #18027:
URL: https://github.com/apache/iceberg/pull/18027
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "pvary (via GitHub)" <gi...@apache.org>.
pvary commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4015497182
##########
core/src/main/java/org/apache/iceberg/deletes/RoaringPositionBitmap.java:
##########
@@ -192,6 +193,43 @@ public void forEach(LongConsumer consumer) {
}
}
+ /**
+ * Iterates over the positions set within the given range, in ascending order.
+ *
+ * <p>Each underlying 32-bit bitmap that the range covers is traversed once, instead of resolving
+ * the containing bitmap for every position as {@link #contains(long)} does.
+ *
+ * @param posStartInclusive inclusive beginning of position range
+ * @param posEndExclusive exclusive ending of position range
+ * @param consumer a consumer for the positions that are set within the range
+ */
+ public void forEachInRange(long posStartInclusive, long posEndExclusive, LongConsumer consumer) {
+ Preconditions.checkArgument(
Review Comment:
nit: And maybe add to the javadoc
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4017186448
##########
core/src/main/java/org/apache/iceberg/deletes/RoaringPositionBitmap.java:
##########
@@ -192,6 +193,43 @@ public void forEach(LongConsumer consumer) {
}
}
+ /**
+ * Iterates over the positions set within the given range, in ascending order.
+ *
+ * <p>Each underlying 32-bit bitmap that the range covers is traversed once, instead of resolving
+ * the containing bitmap for every position as {@link #contains(long)} does.
+ *
+ * @param posStartInclusive inclusive beginning of position range
+ * @param posEndExclusive exclusive ending of position range
+ * @param consumer a consumer for the positions that are set within the range
+ */
+ public void forEachInRange(long posStartInclusive, long posEndExclusive, LongConsumer consumer) {
+ Preconditions.checkArgument(
+ posStartInclusive <= posEndExclusive,
+ "Start position must not exceed end position: [%s, %s)",
+ posStartInclusive,
+ posEndExclusive);
+
+ if (posStartInclusive == posEndExclusive) {
+ return;
+ }
+
+ validatePosition(posStartInclusive);
+ validatePosition(posEndExclusive - 1);
+
+ int startKey = key(posStartInclusive);
+ int endKey = key(posEndExclusive - 1);
+
+ for (int key = startKey; key <= endKey && key < bitmaps.length; key++) {
+ long lowStart = key == startKey ? Integer.toUnsignedLong(pos32Bits(posStartInclusive)) : 0L;
+ long lowEnd =
+ key == endKey
+ ? Integer.toUnsignedLong(pos32Bits(posEndExclusive - 1)) + 1
+ : MAX_POS_32_BITS + 1;
Review Comment:
Switched to 1L << 32 to keep it consistent, and removed the now-unused MAX_POS_32_BITS
##########
spark/v4.2/spark/src/main/java/org/apache/iceberg/spark/data/vectorized/ColumnarBatchUtil.java:
##########
@@ -178,4 +207,71 @@ public static ColumnVector[] removeExtraColumns(
return columnVectors;
}
}
+
+ /**
+ * Consumes deleted positions in ascending order, filling the gaps between them with live row IDs.
+ */
+ private static class RowIdMappingBuilder implements LongConsumer {
Review Comment:
Done. Renamed to `RowIdMappingCollector.`
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "pvary (via GitHub)" <gi...@apache.org>.
pvary commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4017780456
##########
spark/v4.2/spark/src/main/java/org/apache/iceberg/spark/data/vectorized/ColumnarBatchUtil.java:
##########
@@ -119,6 +144,14 @@ public static boolean[] buildIsDeleted(
}
PositionDeleteIndex deletedPositions = deletes.deletedRowPositions();
+
+ if (deletedPositions != null && !deletes.hasEqDeletes()) {
Review Comment:
Is this intentionally different from the similar check in `buildRowIdMapping`?
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "pvary (via GitHub)" <gi...@apache.org>.
pvary commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4003094388
##########
core/src/main/java/org/apache/iceberg/deletes/PositionDeleteIndex.java:
##########
@@ -79,6 +79,28 @@ default void forEach(LongConsumer consumer) {
}
}
+ /**
+ * Traverses the deleted positions within the given range in ascending order, applying the
+ * provided consumer.
+ *
+ * <p>Callers that test a contiguous range of positions should prefer this method over calling
+ * {@link #isDeleted(long)} once per position. Implementations backed by a bitmap can locate the
+ * containers covering the range once and walk them, instead of resolving the container for every
+ * position.
+ *
+ * @param posStart the first position in the range, inclusive
+ * @param length the number of positions in the range
+ * @param consumer a consumer for the deleted positions in the range
+ */
+ default void forEachInRange(long posStart, int length, LongConsumer consumer) {
Review Comment:
Other methods have `long posStart, long posEnd`. Shall we use that?
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "pvary (via GitHub)" <gi...@apache.org>.
pvary commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4003176937
##########
spark/v4.2/spark/src/main/java/org/apache/iceberg/spark/data/vectorized/ColumnarBatchUtil.java:
##########
@@ -83,6 +91,27 @@ public static Pair<int[], Integer> buildRowIdMapping(
return liveRowId == batchSize ? null : Pair.of(rowIdMapping, liveRowId);
}
+ // builds the mapping from the deleted positions in the batch range, without probing per row
+ private static Pair<int[], Integer> buildRowIdMapping(
+ PositionDeleteIndex deletedPositions,
+ DeleteFilter<InternalRow> deletes,
+ long rowStartPosInBatch,
+ int batchSize) {
+ RowIdMappingBuilder builder = new RowIdMappingBuilder(rowStartPosInBatch, batchSize);
+ deletedPositions.forEachInRange(rowStartPosInBatch, batchSize, builder);
+ int liveRowId = builder.build();
+
+ if (liveRowId == batchSize) {
+ return null;
+ }
+
+ for (int index = liveRowId; index < batchSize; index++) {
+ deletes.incrementDeleteCount();
+ }
Review Comment:
This is a bit tricky to read. Is this more clear? Optimizer will fix it anyways.
```suggestion
int deletedRowCount = batchSize - liveRowId;
for (int i = 0; i < deletedRowCount; i++) {
deletes.incrementDeleteCount();
}
```
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4005618470
##########
core/src/test/java/org/apache/iceberg/deletes/TestPositionDeleteIndexForEachInRange.java:
##########
@@ -0,0 +1,227 @@
+/*
+ * 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.deletes;
+
+import static org.assertj.core.api.Assertions.assertThat;
+
+import java.util.List;
+import java.util.Random;
+import java.util.Set;
+import org.apache.iceberg.relocated.com.google.common.collect.Lists;
+import org.apache.iceberg.relocated.com.google.common.collect.Sets;
+import org.junit.jupiter.api.Test;
+
+/**
+ * Verifies that {@link PositionDeleteIndex#forEachInRange(long, int,
+ * java.util.function.LongConsumer)} returns exactly the positions that {@link
+ * PositionDeleteIndex#isDeleted(long)} reports as deleted in the same range, in ascending order,
+ * for every implementation.
+ */
+public class TestPositionDeleteIndexForEachInRange {
+
+ private static final long CHUNK_SIZE = 65536L;
+ private static final long BITMAP_SIZE = 0xFFFFFFFFL + 1L;
+
+ @Test
+ public void testEmptyIndex() {
Review Comment:
also moved these into `TestRoaringPositionBitmap` and `TestBitmapPositionDeleteIndex` to follow the existing public void testX() convention.
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "nastra (via GitHub)" <gi...@apache.org>.
nastra commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4036853267
##########
core/src/main/java/org/apache/iceberg/deletes/PositionDeleteIndex.java:
##########
@@ -79,6 +80,32 @@ default void forEach(LongConsumer consumer) {
}
}
+ /**
+ * Traverses the deleted positions within the given range in ascending order, applying the
+ * provided consumer.
+ *
+ * <p>Callers that test a contiguous range of positions should prefer this method over calling
+ * {@link #isDeleted(long)} once per position.
+ *
+ * @param posStart inclusive beginning of position range
+ * @param posEnd exclusive ending of position range
+ * @param consumer a consumer for the deleted positions in the range
+ * @throws IllegalArgumentException if posStart > posEnd
+ */
+ default void forEachInRange(long posStart, long posEnd, LongConsumer consumer) {
Review Comment:
> PositionDeleteIndex.forEach(consumer) only calls the consumer for the position set in the index. So for only the deleted positions. This is the same for the forEachInRange.
sorry I missed that, in that case I'm ok with naming this `forEachInRange()`
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4037323673
##########
core/src/test/java/org/apache/iceberg/deletes/TestBitmapPositionDeleteIndex.java:
##########
@@ -74,6 +78,116 @@ public void testForEachEmptyIndex() {
assertThat(positions).isEmpty();
}
+ @Test
+ public void testForEachInRange() {
+ PositionDeleteIndex index = indexOf(10L, 11L, 12L, 13L);
+
+ // the beginning is inclusive and the end is exclusive
+ assertThat(collect(index, 11L, 13L)).containsExactly(11L, 12L);
+ assertThat(collect(index, 11L, 12L)).containsExactly(11L);
+
+ // a range that ends where the deletes start
+ assertThat(collect(index, 0L, 10L)).isEmpty();
+
+ // a range that starts after the deletes end
+ assertThat(collect(index, 14L, 24L)).isEmpty();
+ }
+
+ @Test
+ public void testForEachInRangeAscendingOrder() {
+ PositionDeleteIndex index = indexOf(9L, 3L, 7L, 1L, 5L);
+ assertThat(collect(index, 0L, 20L)).containsExactly(1L, 3L, 5L, 7L, 9L);
+ }
+
+ @Test
+ public void testForEachInRangeEmptyRange() {
+ PositionDeleteIndex index = indexOf(0L, 1L, 2L);
+ assertThat(collect(index, 0L, 0L)).isEmpty();
Review Comment:
Added `testForEachInRangeInvalidRange`. The range is validated in three separate places -- the default method, `BitmapPositionDeleteIndex` (via `RoaringPositionBitmap`) and `EmptyPositionDeleteIndex` -- so the test covers all three. I verified it by disabling each precondition in turn and confirming the test fails for each.
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "pvary (via GitHub)" <gi...@apache.org>.
pvary commented on PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#issuecomment-5699379063
> As an engineer who loves Iceberg, I'm thrilled to be a part of this journey.
See you there! 😄
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "pvary (via GitHub)" <gi...@apache.org>.
pvary commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4036767455
##########
core/src/main/java/org/apache/iceberg/deletes/EmptyPositionDeleteIndex.java:
##########
@@ -48,6 +51,15 @@ public boolean isEmpty() {
return true;
}
+ @Override
+ public void forEachInRange(long posStart, long posEnd, LongConsumer consumer) {
+ Preconditions.checkArgument(
Review Comment:
I requested that we should have the same behaviour between the implementations. That is why the check.
I'm not sure that throwing an UOE is a good idea. `BaseDeleteLoader` uses `PositionDeleteIndex.empty()` for data files where no position is deleted. We might throw if we start using `forEachInRange` there, even if the correct response is not to call the consumer at all.
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#issuecomment-5761170523
Thanks @nastra, and thanks @pvary for carrying the review this far.
Addressed the three nits: both test helpers are now `positionsInRange`, and the redundant comment is gone. `org.apache.iceberg.deletes` is 66 tests, no failures.
Once this is merged I will open the backport to Spark 3.5, 4.0 and 4.1 - `ColumnarBatchUtil` is byte-identical across those directories, so it should be a mechanical follow-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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#issuecomment-5689510216
@pvary
Thanks for suggesting that I present the proposal !
I’m giving some thought to the timing and the English presentation, and I’ll get back to you shortly.
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "pvary (via GitHub)" <gi...@apache.org>.
pvary commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4015892524
##########
core/src/test/java/org/apache/iceberg/deletes/TestRoaringPositionBitmap.java:
##########
@@ -350,6 +350,117 @@ public void testAddAllSparseBitmaps() {
assertThat(bitmap1.cardinality()).isEqualTo(4);
}
+ @TestTemplate
+ public void testForEachInRange() {
+ RoaringPositionBitmap bitmap = new RoaringPositionBitmap();
+ bitmap.setRange(10L, 20L);
+
+ // the beginning is inclusive and the end is exclusive
+ assertThat(collectInRange(bitmap, 12L, 15L)).containsExactly(12L, 13L, 14L);
+ assertThat(collectInRange(bitmap, 0L, 10L)).isEmpty();
+ assertThat(collectInRange(bitmap, 20L, 30L)).isEmpty();
+ }
+
+ @TestTemplate
+ public void testForEachInRangeEmptyRange() {
+ RoaringPositionBitmap bitmap = new RoaringPositionBitmap();
+ bitmap.setRange(10L, 20L);
+
+ assertThat(collectInRange(bitmap, 15L, 15L)).isEmpty();
+ }
+
+ @TestTemplate
+ public void testForEachInRangeInvalidRange() {
+ RoaringPositionBitmap bitmap = new RoaringPositionBitmap();
+
+ assertThatThrownBy(() -> bitmap.forEachInRange(20L, 10L, pos -> {}))
+ .isInstanceOf(IllegalArgumentException.class)
+ .hasMessageContaining("Start position must not exceed end position");
+ }
+
+ @TestTemplate
+ public void testForEachInRangeAcrossContainers() {
+ RoaringPositionBitmap bitmap = new RoaringPositionBitmap();
+ bitmap.setRange(CONTAINER_OFFSET - 2, CONTAINER_OFFSET + 2);
+
+ assertThat(collectInRange(bitmap, CONTAINER_OFFSET - 3, CONTAINER_OFFSET + 3))
+ .containsExactly(
+ CONTAINER_OFFSET - 2, CONTAINER_OFFSET - 1, CONTAINER_OFFSET, CONTAINER_OFFSET + 1);
+ }
+
+ @TestTemplate
+ public void testForEachInRangeAcrossKeys() {
Review Comment:
AI found this issue:
```
@TestTemplate
void forEachInRangeAcrossSignedIntBoundary() {
long boundary = Integer.MAX_VALUE + 1L;
RoaringPositionBitmap bitmap = new RoaringPositionBitmap();
bitmap.setRange(boundary - 4, boundary + 4);
bitmap.runLengthEncode();
assertThat(collectInRange(bitmap, boundary - 1, boundary + 1))
.containsExactly(boundary - 1, boundary);
}
```
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "pvary (via GitHub)" <gi...@apache.org>.
pvary commented on PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#issuecomment-5694687790
Sure thing!
No need to have a formal presentation.
Simply a few sentences:
- Identified a way to improve applying the delete filter for vectorized reads
- Improves performance significantly when there are only a few columns projected
- Needs a new API: PositionDeleteIndex.forEachInRange, RoaringPositionBitmap.forEachInRange - Are you ok with this?
- Link to the PR
The community members are clever, don't need too much detail. They will ask details if they need it.
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4017194896
##########
spark/v4.2/spark/src/main/java/org/apache/iceberg/spark/data/vectorized/ColumnarBatchUtil.java:
##########
@@ -64,6 +65,13 @@ public static Pair<int[], Integer> buildRowIdMapping(
}
PositionDeleteIndex deletedPositions = deletes.deletedRowPositions();
+
+ // positions in a batch form a contiguous ascending range, so the index can be traversed once
+ // for the whole range instead of being probed once per row
+ if (deletedPositions != null && !deletes.hasEqDeletes()) {
Review Comment:
Folded the branches since both checked !hasEqDeletes(). Also fixed a mock setup issue in the tests where hasEqDeletes() wasn't stubbed.
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4017198136
##########
core/src/test/java/org/apache/iceberg/deletes/TestRoaringPositionBitmap.java:
##########
@@ -350,6 +350,117 @@ public void testAddAllSparseBitmaps() {
assertThat(bitmap1.cardinality()).isEqualTo(4);
}
+ @TestTemplate
+ public void testForEachInRange() {
+ RoaringPositionBitmap bitmap = new RoaringPositionBitmap();
+ bitmap.setRange(10L, 20L);
+
+ // the beginning is inclusive and the end is exclusive
+ assertThat(collectInRange(bitmap, 12L, 15L)).containsExactly(12L, 13L, 14L);
+ assertThat(collectInRange(bitmap, 0L, 10L)).isEmpty();
+ assertThat(collectInRange(bitmap, 20L, 30L)).isEmpty();
+ }
+
+ @TestTemplate
+ public void testForEachInRangeEmptyRange() {
+ RoaringPositionBitmap bitmap = new RoaringPositionBitmap();
+ bitmap.setRange(10L, 20L);
+
+ assertThat(collectInRange(bitmap, 15L, 15L)).isEmpty();
+ }
+
+ @TestTemplate
+ public void testForEachInRangeInvalidRange() {
+ RoaringPositionBitmap bitmap = new RoaringPositionBitmap();
+
+ assertThatThrownBy(() -> bitmap.forEachInRange(20L, 10L, pos -> {}))
+ .isInstanceOf(IllegalArgumentException.class)
+ .hasMessageContaining("Start position must not exceed end position");
+ }
+
+ @TestTemplate
+ public void testForEachInRangeAcrossContainers() {
+ RoaringPositionBitmap bitmap = new RoaringPositionBitmap();
+ bitmap.setRange(CONTAINER_OFFSET - 2, CONTAINER_OFFSET + 2);
+
+ assertThat(collectInRange(bitmap, CONTAINER_OFFSET - 3, CONTAINER_OFFSET + 3))
+ .containsExactly(
+ CONTAINER_OFFSET - 2, CONTAINER_OFFSET - 1, CONTAINER_OFFSET, CONTAINER_OFFSET + 1);
+ }
+
+ @TestTemplate
+ public void testForEachInRangeAcrossKeys() {
Review Comment:
Thanks for sharing this! I've adopted a variation of this test and expanded it into an exhaustive sweep around the boundary to ensure it's fully covered.
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "nastra (via GitHub)" <gi...@apache.org>.
nastra commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4060747685
##########
core/src/test/java/org/apache/iceberg/deletes/TestRoaringPositionBitmap.java:
##########
@@ -587,6 +713,13 @@ private void assertRandomPositions(RoaringPositionBitmap bitmap, Set<Long> posit
}
}
+ private static List<Long> collectInRange(
Review Comment:
same naming as in the other test
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#issuecomment-5770900187
@pvary
Thanks for merging! I’ll create the backport PRs for the other Spark branches. 👍
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "nastra (via GitHub)" <gi...@apache.org>.
nastra commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4035815628
##########
core/src/main/java/org/apache/iceberg/deletes/PositionDeleteIndex.java:
##########
@@ -79,6 +80,32 @@ default void forEach(LongConsumer consumer) {
}
}
+ /**
+ * Traverses the deleted positions within the given range in ascending order, applying the
+ * provided consumer.
+ *
+ * <p>Callers that test a contiguous range of positions should prefer this method over calling
+ * {@link #isDeleted(long)} once per position.
+ *
+ * @param posStart inclusive beginning of position range
+ * @param posEnd exclusive ending of position range
+ * @param consumer a consumer for the deleted positions in the range
+ * @throws IllegalArgumentException if posStart > posEnd
+ */
+ default void forEachInRange(long posStart, long posEnd, LongConsumer consumer) {
Review Comment:
```suggestion
default void forEachInRange(long posStartInclusive, long posEndExclusive, LongConsumer consumer) {
```
we use similar naming in RoaringPositionBitmap.setRange(..), so I think being explicit about the ranges is helpful. Please also update the implementing methods
##########
core/src/main/java/org/apache/iceberg/deletes/PositionDeleteIndex.java:
##########
@@ -79,6 +80,32 @@ default void forEach(LongConsumer consumer) {
}
}
+ /**
+ * Traverses the deleted positions within the given range in ascending order, applying the
+ * provided consumer.
+ *
+ * <p>Callers that test a contiguous range of positions should prefer this method over calling
Review Comment:
not sure if that's helpful, maybe just remove this
##########
core/src/test/java/org/apache/iceberg/deletes/TestBitmapPositionDeleteIndex.java:
##########
@@ -74,6 +78,116 @@ public void testForEachEmptyIndex() {
assertThat(positions).isEmpty();
}
+ @Test
+ public void testForEachInRange() {
+ PositionDeleteIndex index = indexOf(10L, 11L, 12L, 13L);
+
+ // the beginning is inclusive and the end is exclusive
+ assertThat(collect(index, 11L, 13L)).containsExactly(11L, 12L);
+ assertThat(collect(index, 11L, 12L)).containsExactly(11L);
+
+ // a range that ends where the deletes start
+ assertThat(collect(index, 0L, 10L)).isEmpty();
+
+ // a range that starts after the deletes end
+ assertThat(collect(index, 14L, 24L)).isEmpty();
+ }
+
+ @Test
+ public void testForEachInRangeAscendingOrder() {
+ PositionDeleteIndex index = indexOf(9L, 3L, 7L, 1L, 5L);
+ assertThat(collect(index, 0L, 20L)).containsExactly(1L, 3L, 5L, 7L, 9L);
+ }
+
+ @Test
+ public void testForEachInRangeEmptyRange() {
+ PositionDeleteIndex index = indexOf(0L, 1L, 2L);
+ assertThat(collect(index, 0L, 0L)).isEmpty();
Review Comment:
we also need tests where end < start
##########
core/src/main/java/org/apache/iceberg/deletes/EmptyPositionDeleteIndex.java:
##########
@@ -48,6 +51,15 @@ public boolean isEmpty() {
return true;
}
+ @Override
+ public void forEachInRange(long posStart, long posEnd, LongConsumer consumer) {
+ Preconditions.checkArgument(
Review Comment:
what about just throwing an UOE stating that this isn't supported? Not sure we're adding any value by checking the start/end but essentially not doing anything
##########
core/src/main/java/org/apache/iceberg/deletes/PositionDeleteIndex.java:
##########
@@ -79,6 +80,32 @@ default void forEach(LongConsumer consumer) {
}
}
+ /**
+ * Traverses the deleted positions within the given range in ascending order, applying the
+ * provided consumer.
+ *
+ * <p>Callers that test a contiguous range of positions should prefer this method over calling
+ * {@link #isDeleted(long)} once per position.
+ *
+ * @param posStart inclusive beginning of position range
+ * @param posEnd exclusive ending of position range
+ * @param consumer a consumer for the deleted positions in the range
+ * @throws IllegalArgumentException if posStart > posEnd
+ */
+ default void forEachInRange(long posStart, long posEnd, LongConsumer consumer) {
Review Comment:
maybe we should make the predicate part of the method parameters
##########
core/src/main/java/org/apache/iceberg/deletes/PositionDeleteIndex.java:
##########
@@ -79,6 +80,32 @@ default void forEach(LongConsumer consumer) {
}
}
+ /**
+ * Traverses the deleted positions within the given range in ascending order, applying the
+ * provided consumer.
+ *
+ * <p>Callers that test a contiguous range of positions should prefer this method over calling
+ * {@link #isDeleted(long)} once per position.
+ *
+ * @param posStart inclusive beginning of position range
+ * @param posEnd exclusive ending of position range
+ * @param consumer a consumer for the deleted positions in the range
+ * @throws IllegalArgumentException if posStart > posEnd
+ */
+ default void forEachInRange(long posStart, long posEnd, LongConsumer consumer) {
Review Comment:
also I think it's not entirely clear from the method naming that this will only look at deleted positions in the range. `forEach` itself iterates over all positions, so one would assume that `forEachInRange` would do the same without checked for deleted positions
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#issuecomment-5706767460
@pvary
I was wondering if there were any updates or outcomes from the discussion. Would it be possible to know what was discussed?
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "pvary (via GitHub)" <gi...@apache.org>.
pvary commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4003107629
##########
core/src/main/java/org/apache/iceberg/deletes/PositionDeleteIndex.java:
##########
@@ -79,6 +79,28 @@ default void forEach(LongConsumer consumer) {
}
}
+ /**
+ * Traverses the deleted positions within the given range in ascending order, applying the
+ * provided consumer.
+ *
+ * <p>Callers that test a contiguous range of positions should prefer this method over calling
+ * {@link #isDeleted(long)} once per position. Implementations backed by a bitmap can locate the
+ * containers covering the range once and walk them, instead of resolving the container for every
+ * position.
Review Comment:
No impl details in the javadoc
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "pvary (via GitHub)" <gi...@apache.org>.
pvary commented on PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#issuecomment-5635727988
Ahh.. this went into the Spam folder for me 😢
I suggest way sorter letters and descriptions. Or at least a TL;DR; in the beginning otherwise maintainers pressed for time will skip your messages. I often make this mistake myself, but learning....
I ended up putting your description to an LLM, and I got this answer:
```
So if your query is:
- Narrow projection
- Scan-heavy
- DV-heavy
- Little aggregation/filtering
then you might actually see 13-19% faster queries.
```
Is this accurate?
You might want to highlight in which use-case your PR helps
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "pvary (via GitHub)" <gi...@apache.org>.
pvary commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4003111932
##########
spark/v4.2/spark/src/test/java/org/apache/iceberg/spark/data/vectorized/TestColumnarBatchUtil.java:
##########
@@ -288,6 +267,116 @@ void testRemoveExtraColumnsNotNeeded() {
assertThat(result.length).isEqualTo(3);
}
+ @Test
+ void testBuildRowIdMappingNonZeroBatchStart() {
+ // batches after the first one start at a non-zero position in the file
+ long rowStartPosInBatch = 1_000_000L;
+ when(deleteFilter.hasPosDeletes()).thenReturn(true);
+ when(deleteFilter.deletedRowPositions())
+ .thenReturn(positionIndex(1_000_000L, 1_000_003L, 1_000_009L));
+
+ var rowIdMapping =
+ ColumnarBatchUtil.buildRowIdMapping(columnVectors, deleteFilter, rowStartPosInBatch, 10);
+
+ assertThat(rowIdMapping).isNotNull();
+ int[] rowIds = (int[]) rowIdMapping.first();
+ int liveRows = (Integer) rowIdMapping.second();
+
+ assertThat(liveRows).isEqualTo(7);
+ assertThat(Arrays.copyOf(rowIds, liveRows)).containsExactly(1, 2, 4, 5, 6, 7, 8);
+ verify(deleteFilter, times(3)).incrementDeleteCount();
+ }
+
+ @Test
+ void testBuildRowIdMappingDeletesOutsideBatch() {
+ // the index covers the whole file, so most batches see no deletes at all
+ when(deleteFilter.hasPosDeletes()).thenReturn(true);
+ when(deleteFilter.deletedRowPositions()).thenReturn(positionIndex(5L, 6L, 500L, 501L));
+
+ var rowIdMapping = ColumnarBatchUtil.buildRowIdMapping(columnVectors, deleteFilter, 100L, 100);
+
+ assertThat(rowIdMapping).isNull();
+ verify(deleteFilter, times(0)).incrementDeleteCount();
+ }
+
+ @Test
+ void testBuildRowIdMappingAllRowsDeletedByPosition() {
+ when(deleteFilter.hasPosDeletes()).thenReturn(true);
+ when(deleteFilter.deletedRowPositions()).thenReturn(positionIndex(0L, 1L, 2L, 3L, 4L));
+
+ var rowIdMapping = ColumnarBatchUtil.buildRowIdMapping(columnVectors, deleteFilter, 0, 5);
+
+ assertThat(rowIdMapping).isNotNull();
+ assertThat((Integer) rowIdMapping.second()).isEqualTo(0);
+ verify(deleteFilter, times(5)).incrementDeleteCount();
+ }
+
+ @Test
+ void testBuildIsDeletedNonZeroBatchStart() {
+ when(deleteFilter.deletedRowPositions()).thenReturn(positionIndex(1_000_002L, 1_000_004L));
+
+ var isDeleted = ColumnarBatchUtil.buildIsDeleted(columnVectors, deleteFilter, 1_000_000L, 5);
+
+ assertThat(isDeleted).containsExactly(false, false, true, false, true);
+ verify(deleteFilter, times(2)).incrementDeleteCount();
+ }
+
+ @Test
+ void testPositionOnlyPathMatchesPerRowPath() {
+ // the range traversal must agree with a straightforward per-row probe on every batch
+ java.util.Random random = new java.util.Random(20260818L);
Review Comment:
nit: no fully qualified name
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#issuecomment-5635486213
@pvary
https://lists.apache.org/thread/5v8j1zj2l8ntygph47r0k61xyskxc5o1
Thank you
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#issuecomment-5634824937
@pvary
Hi, it’s been a while! I hope you’ve been doing well.
I reached out to the Core maintainers to ask for discussion and feedback on this PR, but I imagine everyone has been quite busy. So I wanted to ask if you might be able to take a look at it when you have a chance.
Eduard Tudenhoefner suggested on Slack that we discuss this through the mailing list, so I moved the discussion to the dev@iceberg mailing list. However, I haven’t received much response there yet, so I wasn’t quite sure how best to proceed and thought I’d reach out to you directly.
Sorry for the unexpected mention, and I’d really appreciate it if you could take a look when you have some time. Thank you!
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#issuecomment-5636284642
@pvary
I’ve resent the email as well! Here is a quick summary for you here too :D
**TL;DR** — yes, 13-19% is accurate and if anything conservative. But the
summary dropped three conditions, and one of them is backwards: more deletes
is *not* more benefit. I've rewritten the PR description to lead with when
this helps. Thanks for both points.
### Is 13-19% accurate?
It's measured rather than extrapolated, on projections of 5 columns or fewer,
all integer. A scan-only query with a single projected column came out at 29%
on a dedicated instance. At 10 columns or more it falls inside my noise floor
(9.7% median run-to-run spread) and I don't claim anything there.
### When it helps
| | |
|---|---|
| **Helps** | Narrow projection **and** the columns are integers |
| | Scan-dominated query, little aggregation |
| | Delete rate near the array/bitmap boundary (~6.25%) |
| | Fewer, larger files |
| **Doesn't help** | One md5 string column costs 8-10 integer columns of decode, which sinks it on its own |
| | Heavy aggregation — the CPU saved is constant, so its share falls to ~3% as the aggregation grows |
| | Many small files — per-file DV load cost dilutes it (60.7% of scan CPU at 4 files, 49.7% at 488) |
### The one that's backwards
"DV-heavy" reads as "more deletes, more benefit", and it's the other way
round. The worst case — and so the largest gain — is just *below* 6.25%,
where the Roaring container is still a sorted array at its deepest. Past that
it flips to a bitmap and gets cheaper on its own. Deleting more rows can make
the scan faster, which is the least intuitive thing I found here.
### One rule instead of six
The patch is worth it when the delete check is more than **~21% of scan CPU**.
That single threshold predicted the crossover better than column count or
column type did.
---
Point taken on length — I've added a "when this helps" paragraph at the top of
the description here, and I'll lead with a TL;DR on the list. Sorry it landed
in your spam folder; there's a thread on the dev list about devlist mail going
to gmail spam, so it may not be specific to my message.
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4017183165
##########
core/src/main/java/org/apache/iceberg/deletes/RoaringPositionBitmap.java:
##########
@@ -192,6 +193,43 @@ public void forEach(LongConsumer consumer) {
}
}
+ /**
+ * Iterates over the positions set within the given range, in ascending order.
+ *
+ * <p>Each underlying 32-bit bitmap that the range covers is traversed once, instead of resolving
+ * the containing bitmap for every position as {@link #contains(long)} does.
+ *
+ * @param posStartInclusive inclusive beginning of position range
+ * @param posEndExclusive exclusive ending of position range
+ * @param consumer a consumer for the positions that are set within the range
+ */
+ public void forEachInRange(long posStartInclusive, long posEndExclusive, LongConsumer consumer) {
+ Preconditions.checkArgument(
Review Comment:
Done. Added the check and updated the javadoc for all implementations.
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "pvary (via GitHub)" <gi...@apache.org>.
pvary commented on PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#issuecomment-5683403334
@JeonDaehong: I suggest adding this as a topic for tomorrow’s Iceberg Community Sync so you can present the proposal to the broader community and gather feedback. You can add it to the agenda here: https://docs.google.com/document/d/1YuGhUdukLP5gGiqCbk0A5_Wifqe2CZWgOd3TbhY3UQg/edit?tab=t.0#heading=h.z3dncl7gr8m1
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4005512531
##########
spark/v4.2/spark/src/main/java/org/apache/iceberg/spark/data/vectorized/ColumnarBatchUtil.java:
##########
@@ -178,4 +217,68 @@ public static ColumnVector[] removeExtraColumns(
return columnVectors;
}
}
+
+ /**
+ * Consumes deleted positions in ascending order, filling the gaps between them with live row IDs.
+ */
+ private static class RowIdMappingBuilder implements LongConsumer {
+ private final long rowStartPosInBatch;
+ private final int batchSize;
+ private final int[] rowIdMapping;
+ private int nextRowId = 0;
+ private int liveRowId = 0;
+
+ RowIdMappingBuilder(long rowStartPosInBatch, int batchSize) {
+ this.rowStartPosInBatch = rowStartPosInBatch;
+ this.batchSize = batchSize;
+ this.rowIdMapping = new int[batchSize];
+ }
+
+ @Override
+ public void accept(long pos) {
+ int deletedRowId = (int) (pos - rowStartPosInBatch);
+ for (int rowId = nextRowId; rowId < deletedRowId; rowId++) {
+ rowIdMapping[liveRowId] = rowId;
+ liveRowId++;
+ }
+
+ this.nextRowId = deletedRowId + 1;
+ }
+
+ /** Appends the live rows after the last deleted position and returns the live row count. */
+ int build() {
Review Comment:
Yep. Split into `appendRemainingLiveRows()` and `liveRowCount()`, so the side effect and the accessor are separate.
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4006296002
##########
spark/v4.2/spark/src/main/java/org/apache/iceberg/spark/data/vectorized/ColumnarBatchUtil.java:
##########
@@ -83,6 +91,27 @@ public static Pair<int[], Integer> buildRowIdMapping(
return liveRowId == batchSize ? null : Pair.of(rowIdMapping, liveRowId);
}
+ // builds the mapping from the deleted positions in the batch range, without probing per row
+ private static Pair<int[], Integer> buildRowIdMapping(
+ PositionDeleteIndex deletedPositions,
+ DeleteFilter<InternalRow> deletes,
+ long rowStartPosInBatch,
+ int batchSize) {
+ RowIdMappingBuilder builder = new RowIdMappingBuilder(rowStartPosInBatch, batchSize);
Review Comment:
We tried to optimize performance by checking if the bitmap index is empty before processing each batch, but it actually made things 53% slower because isEmpty() was doing an expensive full traversal under the hood. We’ve reverted the change.There is a cheap $O(1)$ alternative (highLowContainer.size() == 0), but since it touches shared methods outside this specific path, we left it out of this PR. Let me know if you'd like to pursue that in a follow-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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "pvary (via GitHub)" <gi...@apache.org>.
pvary commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4003076388
##########
spark/v4.2/spark/src/main/java/org/apache/iceberg/spark/data/vectorized/ColumnarBatchUtil.java:
##########
@@ -178,4 +217,68 @@ public static ColumnVector[] removeExtraColumns(
return columnVectors;
}
}
+
+ /**
+ * Consumes deleted positions in ascending order, filling the gaps between them with live row IDs.
+ */
+ private static class RowIdMappingBuilder implements LongConsumer {
+ private final long rowStartPosInBatch;
+ private final int batchSize;
+ private final int[] rowIdMapping;
+ private int nextRowId = 0;
+ private int liveRowId = 0;
+
+ RowIdMappingBuilder(long rowStartPosInBatch, int batchSize) {
+ this.rowStartPosInBatch = rowStartPosInBatch;
+ this.batchSize = batchSize;
+ this.rowIdMapping = new int[batchSize];
+ }
+
+ @Override
+ public void accept(long pos) {
+ int deletedRowId = (int) (pos - rowStartPosInBatch);
+ for (int rowId = nextRowId; rowId < deletedRowId; rowId++) {
+ rowIdMapping[liveRowId] = rowId;
+ liveRowId++;
+ }
+
+ this.nextRowId = deletedRowId + 1;
+ }
+
+ /** Appends the live rows after the last deleted position and returns the live row count. */
+ int build() {
Review Comment:
this is not a `build` method.
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#issuecomment-5698214452
@pvary
Thank you for guiding me!
```
[Daehong] Reducing per-row position delete index probes in the vectorized read path
* Vectorized reads probe the position delete index once per row, but the positions in a batch are a contiguous ascending range. The index can be traversed once instead.
* Significant gain when few columns are projected. Not visible end to end on wide projections, where the delete check is a small share of scan CPU.
* Needs a new API: PositionDeleteIndex.forEachInRange. Is the community OK with that?
* PR: #18027
```
I wrote it this way.
I hope it leads to a great discussion!
As an engineer who loves Iceberg, I'm thrilled to be a part of this journey.
--
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] Core, Spark 4.2: Add PositionDeleteIndex.forEachInRange and use it in vectorized delete checks [iceberg]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on code in PR #18027:
URL: https://github.com/apache/iceberg/pull/18027#discussion_r4017190557
##########
spark/v4.2/spark/src/main/java/org/apache/iceberg/spark/data/vectorized/ColumnarBatchUtil.java:
##########
@@ -178,4 +207,71 @@ public static ColumnVector[] removeExtraColumns(
return columnVectors;
}
}
+
+ /**
+ * Consumes deleted positions in ascending order, filling the gaps between them with live row IDs.
+ */
+ private static class RowIdMappingBuilder implements LongConsumer {
+ private final DeleteFilter<InternalRow> deletes;
+ private final long rowStartPosInBatch;
+ private final int batchSize;
+ private final int[] rowIdMapping;
+ private int nextRowId = 0;
+ private int liveRowId = 0;
+
+ RowIdMappingBuilder(DeleteFilter<InternalRow> deletes, long rowStartPosInBatch, int batchSize) {
+ this.deletes = deletes;
+ this.rowStartPosInBatch = rowStartPosInBatch;
+ this.batchSize = batchSize;
+ this.rowIdMapping = new int[batchSize];
+ }
+
+ @Override
+ public void accept(long pos) {
+ int deletedRowId = (int) (pos - rowStartPosInBatch);
+ for (int rowId = nextRowId; rowId < deletedRowId; rowId++) {
+ rowIdMapping[liveRowId] = rowId;
+ liveRowId++;
+ }
+
+ deletes.incrementDeleteCount();
+ this.nextRowId = deletedRowId + 1;
+ }
+
+ /** Appends the live rows that follow the last deleted position in the batch. */
+ void appendRemainingLiveRows() {
+ for (int rowId = nextRowId; rowId < batchSize; rowId++) {
+ rowIdMapping[liveRowId] = rowId;
+ liveRowId++;
+ }
+ }
+
+ int liveRowCount() {
+ return liveRowId;
+ }
+
+ int[] rowIdMapping() {
+ return rowIdMapping;
+ }
+ }
+
+ /** Consumes deleted positions in a batch range, marking them in the given array. */
+ private static class IsDeletedBuilder implements LongConsumer {
Review Comment:
Done. Renamed to `IsDeletedCollector`.
##########
spark/v4.2/spark/src/main/java/org/apache/iceberg/spark/data/vectorized/ColumnarBatchUtil.java:
##########
@@ -178,4 +207,71 @@ public static ColumnVector[] removeExtraColumns(
return columnVectors;
}
}
+
+ /**
+ * Consumes deleted positions in ascending order, filling the gaps between them with live row IDs.
+ */
+ private static class RowIdMappingBuilder implements LongConsumer {
Review Comment:
Done. Renamed to `RowIdMappingCollector`.
--
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