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 f42822761c [common] Optimize RoaringNavigableMap64 toRangeList (#8457)
f42822761c is described below
commit f42822761c50dd50b5f4c8a5ee6bb991d9f3d829
Author: Jingsong Lee <[email protected]>
AuthorDate: Sat Jul 4 14:37:52 2026 +0800
[common] Optimize RoaringNavigableMap64 toRangeList (#8457)
Optimize `RoaringNavigableMap64#toRangeList` so large contiguous bitmaps
do not have to expand every row id through the boxed iterator path. The
implementation uses an adaptive path: dense-looking bitmaps use `select`
with exponential/binary range discovery, while sparse bitmaps fall back
to a primitive `LongIterator` scan.
---
.../apache/paimon/utils/RoaringNavigableMap64.java | 123 ++++++++++++++++++++-
.../paimon/utils/RoaringNavigableMap64Test.java | 30 +++++
2 files changed, 151 insertions(+), 2 deletions(-)
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 c70623817c..9411d76038 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
@@ -18,6 +18,7 @@
package org.apache.paimon.utils;
+import org.roaringbitmap.longlong.LongIterator;
import org.roaringbitmap.longlong.Roaring64NavigableMap;
import java.io.ByteArrayInputStream;
@@ -26,6 +27,7 @@ import java.io.DataInputStream;
import java.io.DataOutputStream;
import java.io.IOException;
import java.io.Serializable;
+import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Objects;
@@ -35,6 +37,10 @@ public class RoaringNavigableMap64 implements
Iterable<Long>, Serializable {
private static final long serialVersionUID = 1L;
+ private static final long RANGE_LIST_SELECT_MIN_CARDINALITY = 4096;
+
+ private static final int RANGE_LIST_SELECT_SAMPLE_SIZE = 64;
+
private final Roaring64NavigableMap roaring64NavigableMap;
public RoaringNavigableMap64() {
@@ -141,8 +147,121 @@ public class RoaringNavigableMap64 implements
Iterable<Long>, Serializable {
* <p>This is useful for interoperability with APIs that expect
List<Range>.
*/
public List<Range> toRangeList() {
- // TODO Optimize this to avoid iterator all ids
- return Range.toRanges(roaring64NavigableMap::iterator);
+ long cardinality = roaring64NavigableMap.getLongCardinality();
+ if (!shouldUseSelectRanges(cardinality)) {
+ return toRangeListByIterator();
+ }
+
+ return toRangeListBySelect(cardinality);
+ }
+
+ private boolean shouldUseSelectRanges(long cardinality) {
+ if (cardinality < RANGE_LIST_SELECT_MIN_CARDINALITY) {
+ return false;
+ }
+
+ LongIterator iterator = roaring64NavigableMap.getLongIterator();
+ long previous = iterator.next();
+ int samples = 0;
+ int consecutive = 0;
+ while (samples < RANGE_LIST_SELECT_SAMPLE_SIZE && iterator.hasNext()) {
+ long current = iterator.next();
+ if (isNext(previous, current)) {
+ consecutive++;
+ }
+ previous = current;
+ samples++;
+ }
+ return consecutive * 4 >= samples * 3
+ && isNextAt(cardinality / 2)
+ && isNextAt(cardinality - 2);
+ }
+
+ private boolean isNextAt(long index) {
+ return isNext(roaring64NavigableMap.select(index),
roaring64NavigableMap.select(index + 1));
+ }
+
+ private List<Range> toRangeListByIterator() {
+ List<Range> ranges = new ArrayList<>();
+ LongIterator iterator = roaring64NavigableMap.getLongIterator();
+ if (!iterator.hasNext()) {
+ return ranges;
+ }
+
+ long rangeStart = iterator.next();
+ long rangeEnd = rangeStart;
+ while (iterator.hasNext()) {
+ long current = iterator.next();
+ if (isNext(rangeEnd, current)) {
+ rangeEnd = current;
+ } else {
+ ranges.add(new Range(rangeStart, rangeEnd));
+ rangeStart = current;
+ rangeEnd = current;
+ }
+ }
+ ranges.add(new Range(rangeStart, rangeEnd));
+ return ranges;
+ }
+
+ private List<Range> toRangeListBySelect(long cardinality) {
+ List<Range> ranges = new ArrayList<>();
+ long rangeStartIndex = 0;
+ while (rangeStartIndex < cardinality) {
+ long rangeStart = roaring64NavigableMap.select(rangeStartIndex);
+ long rangeEndIndex = findRangeEndIndex(rangeStartIndex,
cardinality, rangeStart);
+ long rangeOffset = rangeEndIndex - rangeStartIndex;
+ ranges.add(new Range(rangeStart, rangeStart + rangeOffset));
+ rangeStartIndex = rangeEndIndex + 1;
+ }
+
+ return ranges;
+ }
+
+ private long findRangeEndIndex(long rangeStartIndex, long cardinality,
long rangeStart) {
+ long lower = rangeStartIndex;
+ long upper;
+ long step = 1;
+
+ while (true) {
+ long candidateIndex = rangeStartIndex + step;
+ if (candidateIndex < 0 || candidateIndex >= cardinality) {
+ upper = cardinality - 1;
+ break;
+ }
+
+ if (!isContiguous(rangeStart, rangeStartIndex, candidateIndex)) {
+ upper = candidateIndex - 1;
+ break;
+ }
+
+ lower = candidateIndex;
+ if (step > Long.MAX_VALUE / 2) {
+ upper = cardinality - 1;
+ break;
+ }
+ step <<= 1;
+ }
+
+ while (lower < upper) {
+ long mid = lower + ((upper - lower + 1) >>> 1);
+ if (isContiguous(rangeStart, rangeStartIndex, mid)) {
+ lower = mid;
+ } else {
+ upper = mid - 1;
+ }
+ }
+ return lower;
+ }
+
+ private boolean isContiguous(long rangeStart, long rangeStartIndex, long
candidateIndex) {
+ long offset = candidateIndex - rangeStartIndex;
+ return rangeStart <= Long.MAX_VALUE - offset
+ && roaring64NavigableMap.select(candidateIndex) == rangeStart
+ offset;
+ }
+
+ private static boolean isNext(long previous, long current) {
+ return previous != Long.MAX_VALUE && current == previous + 1;
}
public static RoaringNavigableMap64 bitmapOf(long... dat) {
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 ded850fb7d..c2f25888c8 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
@@ -108,4 +108,34 @@ public class RoaringNavigableMap64Test {
assertThat(values.get(0)).isEqualTo(start);
assertThat(values.get(100)).isEqualTo(end);
}
+
+ @Test
+ public void testToRangeListAcrossHighBitmapBoundary() {
+ RoaringNavigableMap64 bitmap = new RoaringNavigableMap64();
+ long start = (1L << 32) - 2;
+ long end = (1L << 32) + 2;
+ bitmap.addRange(new Range(start, end));
+
+ assertThat(bitmap.toRangeList()).containsExactly(new Range(start,
end));
+ }
+
+ @Test
+ public void testToRangeListForLargeContiguousRange() {
+ RoaringNavigableMap64 bitmap = new RoaringNavigableMap64();
+ bitmap.addRange(new Range(0, 9999));
+
+ assertThat(bitmap.toRangeList()).containsExactly(new Range(0, 9999));
+ }
+
+ @Test
+ public void testToRangeListDoesNotMergeUnsignedWrapAround() {
+ RoaringNavigableMap64 bitmap = new RoaringNavigableMap64();
+ bitmap.add(Long.MAX_VALUE);
+ bitmap.add(Long.MIN_VALUE);
+
+ assertThat(bitmap.toRangeList())
+ .containsExactly(
+ new Range(Long.MAX_VALUE, Long.MAX_VALUE),
+ new Range(Long.MIN_VALUE, Long.MIN_VALUE));
+ }
}
