JingsongLi opened a new pull request, #10007:
URL: https://github.com/apache/paimon/pull/10007
### Purpose
Reduce traversal overhead when scalar indexes return many row IDs,
particularly for Data Evolution tables with column-group reads. This PR changes
two shared traversal helpers and their regression tests only; it does not add a
memory-budget option, scan fallback, cost model, or storage/split-format change.
#### 1. Seek within the selection instead of rescanning its prefix for every
batch
`FileRecordIterator.selection` previously created a fresh iterator over the
whole file selection for each batch. A batch starting late in the file walked
all earlier selected positions again. With many batches and a large selection,
this repeated-prefix work dominates the actual read.
Use `RoaringBitmap32.nextValue` to seek directly to the current
file-relative position and cache the next selected position. Both `next()` and
`skip()` use the same check; unselected gaps do not trigger a fresh seek for
every row. Batch release, selection ownership, and unsigned 32-bit position
boundaries are covered by tests.
#### 2. Avoid the select-based bitmap-to-ranges path for dense but short runs
`RoaringNavigableMap64` previously sampled adjacent values at the middle and
tail. A pattern such as nine matching rows followed by one gap can look dense
to those samples, yet create many short ranges. Repeated rank-based `select`
calls are expensive for that shape.
Probe longer contiguous windows before selecting that path. Split each
window into two halves so that an isolated gap inside a long run does not force
a full value-by-value traversal. The existing exact range construction is
unchanged: gaps are never filled or approximated.
### Performance
Local synthetic benchmark: JDK 8, RoaringBitmap 1.2.1, default Parquet
configuration, Data Evolution column groups (`key`/`flag` and a separate
payload group). BTree V1 and V2 were tested separately; V2 was explicitly
enabled. The payload was checked against the key while fully consuming the
results.
Each variant was warmed up once, followed by three rotated rounds; the table
reports median planning + full-read latency for **1.2 million rows**, excluding
table creation, writes, and index construction.
| BTree version | Result shape | Before (ms) | After (ms) | Before / after |
|---|---|---:|---:|---:|
| V1 | 90% matches, 120,000 nine-row ranges | 4,379.6 | 212.7 | 20.6x |
| V2 | 90% matches, 120,000 nine-row ranges | 4,341.8 | 190.7 | 22.8x |
| V1 | 10% matches, 120,000 singleton ranges | 538.9 | 63.3 | 8.5x |
| V2 | 10% matches, 120,000 singleton ranges | 569.1 | 63.8 | 8.9x |
| V1 | 90% matches, one contiguous range | 3,516.2 | 180.2 | 19.5x |
| V2 | 90% matches, one contiguous range | 3,548.8 | 250.9 | 14.1x |
How the measurements relate to the changes:
- **Read-side selection seeking:** V1's single-contiguous-range read phase
fell from **3,491.2 ms to 145.0 ms**. Singleton-range planning was
approximately unchanged (8.2 ms to 7.7 ms), while its read phase fell from
**530.6 ms to 55.4 ms**.
- **Bitmap-to-ranges path selection:** V1's nine-row-range planning phase
fell from **541.7 ms to 18.5 ms**. In a conversion-only probe over a
1.2-million-position domain, the nine-hit/one-gap shape took **2.8 ms** with
the new path choice versus **495.3 ms** when forcing the existing select path.
A fully contiguous bitmap retained the select fast path (approximately **0.01
ms**, versus 2.9 ms with the iterator). This probe used three warm-ups and five
alternating measured rounds.
- **Selective-query sanity check:** single-row lookups remained around 7–8
ms for both versions; narrow-AND-wide queries returning one row remained around
16 ms for V1 and 7 ms for V2 in the 1.2-million-row benchmark.
Measurement scope and limitations:
- These are development-time measurements based on `2f16b3872b`, comparing
the old and retained new traversal implementations. At that time an
experimental range-memory guard was present but **disabled on both sides**, so
these numbers do not include fallback-to-scan gains. That guard and its
configuration are absent from this PR. These are not newly measured timings of
the final rebased commit.
- Compared variants within each run used the same snapshot. Before/after
code runs rebuilt equivalent synthetic data with the same generation rules,
rather than sharing one physical snapshot across revisions.
- Timings cover the Paimon API, not distributed Spark/Flink SQL planning or
scheduling. They are not production speedup claims. The machine was not
isolated; JVM/GC and system-load noise remain. Phase medians need not sum to
the total median.
- This is not a general index-versus-scan policy: broad indexed reads can
still be slower than a plain scan. The heuristic also does not optimize every
run length (for example, 256-row runs still preferred select in the probe).
### Tests
Regression coverage avoids wall-clock thresholds:
- Count bitmap accesses to prove that a late batch does not walk 100,000
preceding selected positions and that gaps reuse the cached next match. The
same late-batch test fails against the original iterator (100,000 accesses,
expected at most 4).
- Check cross-batch and skipped-page positions, mixed `next`/`skip`,
non-materializing `skip`, release forwarding, an unchanged shared selection,
and unsigned 32-bit boundaries.
- Check exact ranges for run lengths 1/9/31/64/256 across high-32-bit
boundaries, and preserve the select path for large ranges with isolated 1- or
17-row gaps near the beginning, middle, and tail.
After rebasing onto master `54d8596ce7`, the focused regression suite passed
**290 tests**: Common 29, Parquet 14, Core 227, and Lance 20. Coverage includes
BTree V1/V2, bitmap/multivalue indexes, vector/full-text filtering, indexed
splits, column-group reads, and deletion vectors.
```bash
mvn -pl paimon-lance -am -Pfast-build \
-DfailIfNoTests=false -DwildcardSuites=none \
-Dtest=FileRecordIteratorTest,RoaringNavigableMap64Test,RowRangeIndexTest,BtreeGlobalIndexTableTest,BitmapGlobalIndexTableTest,MultiValueGlobalIndexTableTest,VectorSearchBuilderTest,FullTextSearchBuilderTest,IndexedSplitTest,IndexedSplitRecordReaderTest,DataEvolutionReadTest,DataEvolutionSplitReadTest,PrimaryKeyIndexedSplitReadTest,DataEvolutionFileIndexTest,DataEvolutionDeletionVectorTest,ParquetFormatReadWriteTest,LanceBTreeGlobalIndexTest
\
test
```
On the local JDK 8 environment, Mockito's dynamic attach was unavailable, so
the test command additionally preloaded the project's Byte Buddy 1.10.13 agent
via `-DextraJavaTestArgs=-javaagent:<local-agent-jar>`. No dependency or
build-file changes were needed.
Non-fast-build verification also passed:
```bash
mvn -pl paimon-api,paimon-common,paimon-core -DskipTests compile
git diff --check
```
--
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]
