This is an automated email from the ASF dual-hosted git repository.
JingsongLi pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/paimon.git
The following commit(s) were added to refs/heads/master by this push:
new c6d20ade78 [core] Optimize bitmap range conversion and selected-row
reads (#10007)
c6d20ade78 is described below
commit c6d20ade78cbcc96c6377b930301a48ef77e51e6
Author: Jingsong Lee <[email protected]>
AuthorDate: Sun Sep 20 17:20:52 2026 +0800
[core] Optimize bitmap range conversion and selected-row reads (#10007)
---
.../apache/paimon/reader/FileRecordIterator.java | 25 ++--
.../apache/paimon/utils/RoaringNavigableMap64.java | 16 ++-
.../paimon/reader/FileRecordIteratorTest.java | 151 ++++++++++++++++++++-
.../paimon/utils/RoaringNavigableMap64Test.java | 45 ++++++
4 files changed, 221 insertions(+), 16 deletions(-)
diff --git
a/paimon-common/src/main/java/org/apache/paimon/reader/FileRecordIterator.java
b/paimon-common/src/main/java/org/apache/paimon/reader/FileRecordIterator.java
index dc61e586f0..d856f8f60b 100644
---
a/paimon-common/src/main/java/org/apache/paimon/reader/FileRecordIterator.java
+++
b/paimon-common/src/main/java/org/apache/paimon/reader/FileRecordIterator.java
@@ -25,7 +25,6 @@ import org.apache.paimon.utils.RoaringBitmap32;
import javax.annotation.Nullable;
import java.io.IOException;
-import java.util.Iterator;
import java.util.function.Function;
/**
@@ -117,9 +116,8 @@ public interface FileRecordIterator<T> extends
RecordReader.RecordIterator<T> {
default FileRecordIterator<T> selection(RoaringBitmap32 selection) {
FileRecordIterator<T> thisIterator = this;
- final Iterator<Integer> selects = selection.iterator();
return new FileRecordIterator<T>() {
- private long nextExpected = selects.hasNext() ? selects.next() :
-1;
+ private long nextExpected = selection.nextValue(0);
@Override
public long returnedPosition() {
@@ -142,10 +140,7 @@ public interface FileRecordIterator<T> extends
RecordReader.RecordIterator<T> {
if (next == null) {
return null;
}
- while (nextExpected != -1 && nextExpected <
returnedPosition()) {
- nextExpected = selects.hasNext() ? selects.next() : -1;
- }
- if (nextExpected == returnedPosition()) {
+ if (isSelected()) {
return next;
}
}
@@ -157,15 +152,23 @@ public interface FileRecordIterator<T> extends
RecordReader.RecordIterator<T> {
if (nextExpected == -1 || !thisIterator.skip()) {
return false;
}
- while (nextExpected != -1 && nextExpected <
returnedPosition()) {
- nextExpected = selects.hasNext() ? selects.next() : -1;
- }
- if (nextExpected == returnedPosition()) {
+ if (isSelected()) {
return true;
}
}
}
+ private boolean isSelected() {
+ long position = returnedPosition();
+ if (nextExpected < position) {
+ // A batch may start far into the file or skip entire
pages. Seek to its
+ // position instead of walking the selection again from
the file's start.
+ nextExpected =
+ position > 0xFFFFFFFFL ? -1 :
selection.nextValue((int) position);
+ }
+ return nextExpected == position;
+ }
+
@Override
public void releaseBatch() {
thisIterator.releaseBatch();
diff --git
a/paimon-common/src/main/java/org/apache/paimon/utils/RoaringNavigableMap64.java
b/paimon-common/src/main/java/org/apache/paimon/utils/RoaringNavigableMap64.java
index 006c92a46c..418788d9f2 100644
---
a/paimon-common/src/main/java/org/apache/paimon/utils/RoaringNavigableMap64.java
+++
b/paimon-common/src/main/java/org/apache/paimon/utils/RoaringNavigableMap64.java
@@ -209,13 +209,21 @@ public class RoaringNavigableMap64 implements
Iterable<Long>, Serializable {
previous = current;
samples++;
}
+ // A high hit ratio can still mean many short runs (for example nine
hits followed
+ // by one gap). Repeated select calls are expensive for those; use the
iterator.
return consecutive * 4 >= samples * 3
- && isNextAt(cardinality / 2)
- && isNextAt(cardinality - 2);
+ && hasLongRunAt(cardinality / 2)
+ && hasLongRunAt(cardinality - 2 *
RANGE_LIST_SELECT_SAMPLE_SIZE - 1);
}
- private boolean isNextAt(long index) {
- return isNext(roaring64NavigableMap.select(index),
roaring64NavigableMap.select(index + 1));
+ private boolean hasLongRunAt(long index) {
+ // Probe both halves so an isolated gap in a long run does not force a
linear scan.
+ long middle = index + RANGE_LIST_SELECT_SAMPLE_SIZE;
+ return isContiguous(roaring64NavigableMap.select(index), index, middle)
+ || isContiguous(
+ roaring64NavigableMap.select(middle),
+ middle,
+ middle + RANGE_LIST_SELECT_SAMPLE_SIZE);
}
private List<Range> toRangeListByIterator() {
diff --git
a/paimon-common/src/test/java/org/apache/paimon/reader/FileRecordIteratorTest.java
b/paimon-common/src/test/java/org/apache/paimon/reader/FileRecordIteratorTest.java
index 50001cd9f7..6a65e34f07 100644
---
a/paimon-common/src/test/java/org/apache/paimon/reader/FileRecordIteratorTest.java
+++
b/paimon-common/src/test/java/org/apache/paimon/reader/FileRecordIteratorTest.java
@@ -28,6 +28,7 @@ import javax.annotation.Nullable;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
+import java.util.Iterator;
import java.util.List;
import static org.assertj.core.api.Assertions.assertThat;
@@ -196,7 +197,14 @@ public class FileRecordIteratorTest {
@Test
public void testSelectionSkip() throws IOException {
- FileRecordIterator<Long> iterator = createIterator(Arrays.asList(0L,
1L, 2L, 3L, 4L, 5L));
+ int[] materialized = {0};
+ FileRecordIterator<Long> iterator =
+ createIterator(Arrays.asList(0L, 1L, 2L, 3L, 4L, 5L))
+ .transform(
+ value -> {
+ materialized[0]++;
+ return value;
+ });
RoaringBitmap32 selection = new RoaringBitmap32();
selection.add(1);
@@ -206,11 +214,152 @@ public class FileRecordIteratorTest {
FileRecordIterator<Long> selected = iterator.selection(selection);
assertThat(selected.skip()).isTrue();
assertThat(selected.returnedPosition()).isEqualTo(1L);
+ assertThat(materialized[0]).isZero();
assertThat(selected.next()).isEqualTo(3L);
assertThat(selected.returnedPosition()).isEqualTo(3L);
assertThat(selected.skip()).isTrue();
assertThat(selected.returnedPosition()).isEqualTo(5L);
assertThat(selected.skip()).isFalse();
+ assertThat(materialized[0]).isEqualTo(2);
+ }
+
+ @Test
+ public void testSelectionSeeksWithoutWalkingPrefixesOrGaps() throws
IOException {
+ int[] accesses = {0};
+ RoaringBitmap32 selection =
+ new RoaringBitmap32() {
+ @Override
+ public long nextValue(int fromValue) {
+ accesses[0]++;
+ return super.nextValue(fromValue);
+ }
+
+ @Override
+ public Iterator<Integer> iterator() {
+ Iterator<Integer> iterator = super.iterator();
+ return new Iterator<Integer>() {
+ @Override
+ public boolean hasNext() {
+ return iterator.hasNext();
+ }
+
+ @Override
+ public Integer next() {
+ accesses[0]++;
+ return iterator.next();
+ }
+ };
+ }
+ };
+ selection.flip(0, 100_000);
+ FileRecordIterator<Long> selected =
+ createPositionIterator(Arrays.asList(99_990L, 99_991L,
99_999L), new int[1])
+ .selection(selection);
+ assertThat(collectAll(selected)).containsExactly(99_990L, 99_991L,
99_999L);
+ assertThat(accesses[0]).isLessThanOrEqualTo(4);
+
+ selection.clear();
+ selection.add(0);
+ selection.add(100_000);
+ accesses[0] = 0;
+ List<Long> positions = new ArrayList<>();
+ for (long i = 0; i < 1000; i++) {
+ positions.add(i);
+ }
+ int[] releases = {0};
+ selected = createPositionIterator(positions,
releases).selection(selection);
+ assertThat(selected.skip()).isTrue();
+ assertThat(selected.returnedPosition()).isZero();
+ assertThat(selected.next()).isNull();
+ assertThat(accesses[0]).isLessThanOrEqualTo(3);
+ selected.releaseBatch();
+ assertThat(releases[0]).isOne();
+ }
+
+ @Test
+ public void testSelectionAcrossBatchesAndPositionGaps() throws IOException
{
+ RoaringBitmap32 selection = new RoaringBitmap32();
+ selection.flip(0, 100_000);
+ selection.remove(99_992);
+ selection.remove(99_996);
+ // Each batch uses file-relative positions and the same selection. The
underlying
+ // reader may already have skipped rows, for example through Parquet
page pruning.
+ for (List<Long> positions :
+ Arrays.asList(
+ Arrays.asList(99_990L, 99_992L, 99_994L),
+ Arrays.asList(99_996L, 99_998L, 100_000L))) {
+ int[] released = {0};
+ FileRecordIterator<Long> selected =
+ createPositionIterator(positions,
released).selection(selection);
+ List<Long> expected = new ArrayList<>();
+ for (long position : positions) {
+ if (selection.contains((int) position)) {
+ expected.add(position);
+ }
+ }
+ assertThat(collectAll(selected)).isEqualTo(expected);
+ selected.releaseBatch();
+ assertThat(released[0]).isOne();
+
+ selected = createPositionIterator(positions,
released).selection(selection);
+ assertThat(selected.skip()).isTrue();
+ assertThat(selected.returnedPosition()).isEqualTo(expected.get(0));
+ assertThat(collectAll(selected)).isEqualTo(expected.subList(1,
expected.size()));
+ }
+ assertThat(selection.getCardinality()).isEqualTo(99_998);
+ }
+
+ @Test
+ public void testSelectionAtMaximumPosition() throws IOException {
+ RoaringBitmap32 selection =
+ RoaringBitmap32.bitmapOf(Integer.MAX_VALUE, Integer.MIN_VALUE,
-1);
+ FileRecordIterator<Long> selected =
+ createPositionIterator(
+ Arrays.asList(
+ (long) Integer.MAX_VALUE - 1,
+ (long) Integer.MAX_VALUE,
+ 1L << 31,
+ 0xFFFFFFFFL,
+ 1L << 32),
+ new int[1])
+ .selection(selection);
+ assertThat(selected.next()).isEqualTo((long) Integer.MAX_VALUE);
+ assertThat(selected.skip()).isTrue();
+ assertThat(selected.returnedPosition()).isEqualTo(1L << 31);
+ assertThat(selected.next()).isEqualTo(0xFFFFFFFFL);
+ assertThat(selected.next()).isNull();
+ assertThat(selected.skip()).isFalse();
+ }
+
+ private FileRecordIterator<Long> createPositionIterator(List<Long>
positions, int[] released) {
+ return new FileRecordIterator<Long>() {
+ private int index = -1;
+
+ @Override
+ public long returnedPosition() {
+ return positions.get(index);
+ }
+
+ @Override
+ public Path filePath() {
+ return new Path("test-file.parquet");
+ }
+
+ @Override
+ public Long next() {
+ return skip() ? positions.get(index) : null;
+ }
+
+ @Override
+ public boolean skip() {
+ return ++index < positions.size();
+ }
+
+ @Override
+ public void releaseBatch() {
+ released[0]++;
+ }
+ };
}
@Test
diff --git
a/paimon-common/src/test/java/org/apache/paimon/utils/RoaringNavigableMap64Test.java
b/paimon-common/src/test/java/org/apache/paimon/utils/RoaringNavigableMap64Test.java
index a51262c261..9f78b0488c 100644
---
a/paimon-common/src/test/java/org/apache/paimon/utils/RoaringNavigableMap64Test.java
+++
b/paimon-common/src/test/java/org/apache/paimon/utils/RoaringNavigableMap64Test.java
@@ -20,7 +20,9 @@ package org.apache.paimon.utils;
import org.junit.jupiter.api.Test;
+import java.lang.reflect.Method;
import java.util.ArrayList;
+import java.util.Arrays;
import java.util.List;
import static org.assertj.core.api.Assertions.assertThat;
@@ -167,6 +169,49 @@ public class RoaringNavigableMap64Test {
bitmap.addRange(new Range(0, 9999));
assertThat(bitmap.toRangeList()).containsExactly(new Range(0, 9999));
+
+ RoaringNavigableMap64 withEarlyGap = new RoaringNavigableMap64();
+ withEarlyGap.addRange(new Range(0, 8));
+ withEarlyGap.addRange(new Range(10, 9999));
+ assertThat(withEarlyGap.toRangeList())
+ .containsExactly(new Range(0, 8), new Range(10, 9999));
+ }
+
+ @Test
+ public void testToRangeListForDenseShortRuns() {
+ for (int runLength : new int[] {1, 9, 31, 64, 256}) {
+ RoaringNavigableMap64 bitmap = new RoaringNavigableMap64();
+ List<Range> expected = new ArrayList<>();
+ // Cross 32-bit bitmap containers and the 64-bit bitmap's high-key
boundary.
+ long start = (1L << 32) - 10_000;
+ for (int run = 0; run < 1000; run++) {
+ Range range = new Range(start, start + runLength - 1);
+ bitmap.addRange(range);
+ expected.add(range);
+ start += runLength + 1;
+ }
+ assertThat(bitmap.toRangeList()).isEqualTo(expected);
+ }
+ }
+
+ @Test
+ public void testSelectPathForLargeRangesWithIsolatedGaps() throws
Exception {
+ Method useSelect =
+
RoaringNavigableMap64.class.getDeclaredMethod("shouldUseSelectRanges",
long.class);
+ useSelect.setAccessible(true);
+ for (long gap : new long[] {9, 600_032, 1_199_970}) {
+ for (int width : new int[] {1, 17}) {
+ List<Range> expected =
+ Arrays.asList(new Range(0, gap - 1), new Range(gap +
width, 1_199_999));
+ RoaringNavigableMap64 bitmap = new RoaringNavigableMap64();
+ expected.forEach(bitmap::addRange);
+ // Verify the algorithmic bound without a timing assertion: a
hole within a
+ // sample must not cause us to walk a million values for just
two ranges.
+ assertThat((boolean) useSelect.invoke(bitmap,
bitmap.getLongCardinality()))
+ .isTrue();
+ assertThat(bitmap.toRangeList()).isEqualTo(expected);
+ }
+ }
}
@Test
