airborne12 opened a new pull request, #69908:
URL: https://github.com/apache/doris/pull/69908
### What problem does this PR solve?
Issue Number: None
Related PR: None
Problem Summary: A range filter on a numeric SNII index reads the leaves
that lie wholly inside the
range one at a time, gathers their doc ids, radix-sorts them and adds them
to a roaring bitmap. On a
99M-row table, 71% of the SNII stack samples of a query with a wide
`latency_ms` range were in this
path: 15% in the sort, 9% in `addMany`, and about 27% in reading, mostly
per-call overhead, since a
leaf is a few KB and takes one positioned read of its own.
- Whole-leaf hits lie next to each other in `bkd_data`, so one read now
takes up to about 1 MiB of
them. The bytes read are the same, in far fewer calls, and sequentially
when they are not cached.
- A wide range sets the doc ids in a flat bitmap instead, which needs no
sort. It is loaded into a
Roaring through the portable format, a published spec, because CRoaring
2.1.2 has no call that
takes a bitset. A narrow range keeps the sort: a flat bitmap costs a pass
over all its words, so it
is used from about one point per 256 documents.
- The bitmap stops at doc id 2^28, which is 32 MiB. The doc ids of a leaf
past that take the sort as
before, so a damaged leaf cannot make it allocate more.
- The leaf decoder reuses its vector of value runs instead of allocating one
per leaf.
The on-disk format and the write path do not change.
| Query (99M rows), new/previous | Hot | Cold |
|---|---|---|
| filters and `latency_ms BETWEEN 2000 AND 6000`, no text | 0.42 / 0.39 /
0.37 (212 ms to 85 ms) | 0.87 |
| phrase with `latency_ms >= 3000` | 0.62 / 0.61 / 0.58 | 1.00 |
| phrase with `latency_ms >= 8000` | 0.90 / 0.89 / 0.87 | 1.00 |
| phrase with a 7-day date range | 1.01 / 0.98 / 1.00 | |
Hot: both versions interleaved in one BE process on a quiet host, three runs
each. The 21 queries of
the bench with no range do not reach this code and read 0.86-1.02 in one
run, which is the noise of
that run. Cold: BE restarted and the index files evicted before every run,
configuration order
alternated, 5 runs each; the wide range gains and the others wait on other
reads. All 25 queries
return the same results with both versions. The build also had #69879,
#69882, #69887, #69891 and
#69895.
A wide range briefly holds about three times its result in memory: the flat
bitmap, the portable
image and the bitmap loaded from it. That is one bit per row of the segment
each, and it is freed
when the range ends. The chunks of gathered doc ids it replaces took 8 MiB
at most.
### Release note
Speed up SNII range filters on numeric columns that match many rows.
### Check List (For Author)
- Test: Unit Test (`BkdReaderTest`: wide and narrow ranges match brute force
for dense, sparse and
multi-valued doc ids and for doc ids on both sides of the bitmap's limit,
which is itself checked;
containers of exactly 4096 and 4097 documents; only the touched leaves'
bytes are read; reads are
bounded; a damaged leaf is reported from inside a read; every bitmap passes
`roaring_bitmap_internal_validate`; mutants of the new code fail tests,
except two that change
nothing but read one more leaf or size a 4096-document array container by
its equal bitset size;
all inverted index tests pass under ASAN).
`ReadsExactlyOnePositionedReadPerTouchedLeaf` became
`ReadsOnlyTheTouchedLeavesAndWholeLeafHitsInOneRead`, which checks the
bytes read instead.
Manual test: the hot and cold A/B above.
- Behavior changed: No
- Does this need documentation: No
🤖 Generated with [Claude Code](https://claude.com/claude-code)
--
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]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
