JingsongLi commented on code in PR #9141:
URL: https://github.com/apache/paimon/pull/9141#discussion_r3764686658
##########
paimon-core/src/main/java/org/apache/paimon/io/FileIndexEvaluator.java:
##########
@@ -97,15 +121,75 @@ public static FileIndexResult evaluate(
}
}
+ private static FileIndexResult createLimitSelection(
+ DataFileMeta file, @Nullable DeletionVector dv, int limit) {
+ if (dv == null) {
+ return new BitmapIndexResult(
+ () -> RoaringBitmap32.bitmapOfRange(0,
Math.min(file.rowCount(), limit)));
+ }
+
+ if (dv instanceof BitmapDeletionVector && file.rowCount() <=
RoaringBitmap32.MAX_VALUE) {
+ return createBaseSelection(file, dv).limit(limit);
+ }
+
+ RoaringBitmap32 selection = new RoaringBitmap32();
+ long position = 0;
+ int remaining = limit;
+ while (remaining > 0 && position < file.rowCount()) {
Review Comment:
This eagerly scans physical positions one by one until it finds `limit` live
rows. With a bitmap64 deletion vector containing a long deleted prefix, even
`LIMIT 1` can perform millions of `isDeleted` lookups before the reader is
opened; for a >32-bit file it can scan as far as `Integer.MAX_VALUE` before
falling back. Could we use the projected bitmap plus `andNot(...).limit(limit)`
within the 32-bit bound, and return `REMAIN` outside it? The final
`LimitRecordReader` already preserves correctness on fallback.
##########
paimon-core/src/main/java/org/apache/paimon/io/FileIndexEvaluator.java:
##########
@@ -97,15 +121,75 @@ public static FileIndexResult evaluate(
}
}
+ private static FileIndexResult createLimitSelection(
+ DataFileMeta file, @Nullable DeletionVector dv, int limit) {
+ if (dv == null) {
+ return new BitmapIndexResult(
+ () -> RoaringBitmap32.bitmapOfRange(0,
Math.min(file.rowCount(), limit)));
+ }
+
+ if (dv instanceof BitmapDeletionVector && file.rowCount() <=
RoaringBitmap32.MAX_VALUE) {
+ return createBaseSelection(file, dv).limit(limit);
+ }
+
+ RoaringBitmap32 selection = new RoaringBitmap32();
+ long position = 0;
+ int remaining = limit;
+ while (remaining > 0 && position < file.rowCount()) {
+ if (position > RoaringBitmap32.MAX_VALUE) {
+ return FileIndexResult.REMAIN;
+ }
+ if (!dv.isDeleted(position)) {
+ selection.add((int) position);
+ remaining--;
+ }
+ position++;
+ }
+ return new BitmapIndexResult(() -> selection);
+ }
+
private static BitmapIndexResult createBaseSelection(
DataFileMeta file, @Nullable DeletionVector dv) {
- BitmapIndexResult selection =
- new BitmapIndexResult(() -> RoaringBitmap32.bitmapOfRange(0,
file.rowCount()));
- if (dv instanceof BitmapDeletionVector) {
- RoaringBitmap32 deletion = ((BitmapDeletionVector) dv).get();
- selection = selection.andNot(deletion);
- }
- return selection;
+ return new BitmapIndexResult(
+ () -> {
+ RoaringBitmap32 selection =
RoaringBitmap32.bitmapOfRange(0, file.rowCount());
+ if (dv == null) {
+ return selection;
+ }
+
+ RoaringBitmap32 deletion;
+ if (dv instanceof BitmapDeletionVector) {
+ deletion = ((BitmapDeletionVector) dv).get();
+ } else if (dv instanceof Bitmap64DeletionVector) {
+ deletion = ((Bitmap64DeletionVector)
dv).projectToBitmap32(file.rowCount());
+ } else {
+ return selection;
+ }
+ selection.andNot(deletion);
+ return selection;
+ });
+ }
+
+ private static boolean supportsBitmapSelection(@Nullable DeletionVector
dv) {
+ return dv == null
+ || dv instanceof BitmapDeletionVector
+ || dv instanceof Bitmap64DeletionVector;
+ }
+
+ private static BitmapIndexResult excludeDeletedPositions(
+ BitmapIndexResult candidates, DeletionVector dv) {
+ return new BitmapIndexResult(
+ () -> {
+ RoaringBitmap32 result = new RoaringBitmap32();
+ Iterator<Integer> iterator = candidates.get().iterator();
Review Comment:
This rebuilds the result one candidate at a time. A low-selectivity
predicate that matches nearly every row turns reader creation into O(row count)
Java-level lookups and insertions while retaining both bitmaps. Could we use
`projectToBitmap32` followed by a bitmap `andNot` for broad candidate sets,
keeping point checks only for sparse results, for example via a
cardinality-based choice?
--
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
