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 bb71912a76 [core] Keep tied nulls in range bitmap TopN for multi-key
sorts (#9280)
bb71912a76 is described below
commit bb71912a76de014836b1b2c73a4fceaf08cc31c8
Author: jackylee <[email protected]>
AuthorDate: Thu Aug 20 10:02:00 2026 +0800
[core] Keep tied nulls in range bitmap TopN for multi-key sorts (#9280)
---
.../paimon/fileindex/rangebitmap/RangeBitmap.java | 18 ++++++--
.../rangebitmap/RangeBitmapFileIndexTest.java | 53 ++++++++++++++++++++++
2 files changed, 66 insertions(+), 5 deletions(-)
diff --git
a/paimon-common/src/main/java/org/apache/paimon/fileindex/rangebitmap/RangeBitmap.java
b/paimon-common/src/main/java/org/apache/paimon/fileindex/rangebitmap/RangeBitmap.java
index 5b44e1dfe1..784eb1fca2 100644
---
a/paimon-common/src/main/java/org/apache/paimon/fileindex/rangebitmap/RangeBitmap.java
+++
b/paimon-common/src/main/java/org/apache/paimon/fileindex/rangebitmap/RangeBitmap.java
@@ -285,7 +285,11 @@ public class RangeBitmap {
@Nullable RoaringBitmap32 foundSet,
boolean strict) {
return fillNulls(
- k, nullOrdering, foundSet, (l, r) ->
getBitSliceIndexBitmap().topK(l, r, strict));
+ k,
+ nullOrdering,
+ foundSet,
+ (l, r) -> getBitSliceIndexBitmap().topK(l, r, strict),
+ strict);
}
public RoaringBitmap32 bottomK(
@@ -297,14 +301,16 @@ public class RangeBitmap {
k,
nullOrdering,
foundSet,
- (l, r) -> getBitSliceIndexBitmap().bottomK(l, r, strict));
+ (l, r) -> getBitSliceIndexBitmap().bottomK(l, r, strict),
+ strict);
}
private RoaringBitmap32 fillNulls(
int k,
SortValue.NullOrdering nullOrdering,
@Nullable RoaringBitmap32 foundSet,
- BiFunction<Integer, RoaringBitmap32, RoaringBitmap32> function) {
+ BiFunction<Integer, RoaringBitmap32, RoaringBitmap32> function,
+ boolean strict) {
if (cardinality <= 0) {
return rid > 0 ? RoaringBitmap32.bitmapOfRange(0, rid) : new
RoaringBitmap32();
}
@@ -316,12 +322,14 @@ public class RangeBitmap {
if (cardinality >= k) {
return bitmap;
}
- bitmap.or(isNull(foundSet).limit((int) (k - cardinality)));
+ // Nulls are all tied, so keep the whole group when duplicates are
allowed.
+ RoaringBitmap32 nulls = isNull(foundSet);
+ bitmap.or(strict ? nulls.limit((int) (k - cardinality)) : nulls);
} else {
bitmap = isNull(foundSet);
long cardinality = bitmap.getCardinality();
if (cardinality >= k) {
- return bitmap.limit(k);
+ return strict ? bitmap.limit(k) : bitmap;
}
bitmap.or(function.apply((int) (k - cardinality), foundSet));
}
diff --git
a/paimon-common/src/test/java/org/apache/paimon/fileindex/rangebitmap/RangeBitmapFileIndexTest.java
b/paimon-common/src/test/java/org/apache/paimon/fileindex/rangebitmap/RangeBitmapFileIndexTest.java
index 01c072520b..8e94eba873 100644
---
a/paimon-common/src/test/java/org/apache/paimon/fileindex/rangebitmap/RangeBitmapFileIndexTest.java
+++
b/paimon-common/src/test/java/org/apache/paimon/fileindex/rangebitmap/RangeBitmapFileIndexTest.java
@@ -511,6 +511,59 @@ public class RangeBitmapFileIndexTest {
assertThat(actual).isEqualTo(RoaringBitmap32.bitmapOf(3, 0, 4)); //
values: 5, 10, 15
}
+ @Test
+ public void testTopNWithMultipleColumnsKeepsNullTies() {
+ IntType intType = new IntType();
+ FieldRef fieldRef1 = new FieldRef(0, "col1", intType);
+ FieldRef fieldRef2 = new FieldRef(1, "col2", intType);
+
+ RangeBitmapFileIndex bitmapFileIndex = new
RangeBitmapFileIndex(intType, new Options());
+ FileIndexWriter writer = bitmapFileIndex.createWriter();
+
+ writer.writeRecord(null);
+ writer.writeRecord(null);
+ writer.writeRecord(null);
+ writer.writeRecord(7);
+ writer.writeRecord(8);
+
+ byte[] bytes = writer.serializedBytes();
+ ByteArraySeekableStream stream = new ByteArraySeekableStream(bytes);
+ FileIndexReader reader = bitmapFileIndex.createReader(stream, 0,
bytes.length);
+ RoaringBitmap32 foundSet = RoaringBitmap32.bitmapOf(0, 1, 2, 3, 4);
+
+ // col2 decides among the tied nulls, so all of them must survive the
index selection
+ List<SortValue> multiple =
+ Arrays.asList(
+ new SortValue(fieldRef1, ASCENDING, NULLS_FIRST),
+ new SortValue(fieldRef2, DESCENDING, NULLS_FIRST));
+ FileIndexResult result =
+ reader.visitTopN(new TopN(multiple, 2), new
BitmapIndexResult(() -> foundSet));
+ assertThat(((BitmapIndexResult)
result).get()).isEqualTo(RoaringBitmap32.bitmapOf(0, 1, 2));
+
+ // a single order is exact, so the null group is still trimmed to the
limit
+ List<SortValue> single = Arrays.asList(new SortValue(fieldRef1,
ASCENDING, NULLS_FIRST));
+ result = reader.visitTopN(new TopN(single, 2), new
BitmapIndexResult(() -> foundSet));
+ assertThat(((BitmapIndexResult)
result).get()).isEqualTo(RoaringBitmap32.bitmapOf(0, 1));
+
+ // nulls sort last, so they tie while filling up the remaining limit
+ List<SortValue> multipleNullsLast =
+ Arrays.asList(
+ new SortValue(fieldRef1, ASCENDING, NULLS_LAST),
+ new SortValue(fieldRef2, DESCENDING, NULLS_LAST));
+ result =
+ reader.visitTopN(
+ new TopN(multipleNullsLast, 3), new
BitmapIndexResult(() -> foundSet));
+ assertThat(((BitmapIndexResult) result).get())
+ .isEqualTo(RoaringBitmap32.bitmapOf(0, 1, 2, 3, 4));
+
+ List<SortValue> singleNullsLast =
+ Arrays.asList(new SortValue(fieldRef1, ASCENDING, NULLS_LAST));
+ result =
+ reader.visitTopN(
+ new TopN(singleNullsLast, 3), new BitmapIndexResult(()
-> foundSet));
+ assertThat(((BitmapIndexResult)
result).get()).isEqualTo(RoaringBitmap32.bitmapOf(0, 3, 4));
+ }
+
@Test
public void testAllowDuplicatesAscBoundary() {
IntType intType = new IntType();
