airborne12 opened a new pull request, #69895:
URL: https://github.com/apache/doris/pull/69895
### What problem does this PR solve?
Issue Number: None
Related PR: None
Problem Summary: An equality filter on an indexed string column, such as
`tenant = 'x'`, collects
its whole posting list into a roaring bitmap, and a value can cover tens of
percent of the table.
`RoaringDocIdSink::append_sorted` gets those documents in sorted windows
that mostly fall in one 64K
container, but `Roaring::addMany` goes through the container's type for
every document. On a 99M-row
table that was about 20% of the SNII stack samples of a filtered phrase
prefix query.
`append_sorted` now splits a span at container boundaries and fills each
container directly:
- A bitset container gets one write per 64-bit word, with the bits gathered
in a register, because
neighbouring documents mostly share a word and a store per document would
wait on the one before
it.
- An array container gets its tail appended in one loop, up to its limit of
4096. The next document
turns it into a bitset, which then takes the rest.
- Anything else goes through `addMany` as before: run containers, documents
that fall inside an
existing array, and spans that are not strictly ascending, which the sink
does not rule out and a
damaged posting could produce.
The containers end up the same as with `addMany`.
Two things to look at in review:
- The sink is shared by every inverted index format, so V3 queries take the
same path.
- The code writes to CRoaring's container structs. `null_bitmap.cpp` already
includes those headers,
but only reads their sizes, so an upgrade of CRoaring has to keep this
code in mind. CRoaring 2.1.2
has no public call that adds a sorted run to a container.
| Query (99M rows), new/previous | SNII hot | V3 hot | SNII cold |
|---|---|---|---|
| phrase with tenant, app, type and status | 0.80 / 0.80 / 0.78 | 0.90 |
0.95 |
| phrase with a latency filter | 0.78 / 0.77 / 0.78 | 0.78 | |
| MATCH_ALL with the same four filters | 0.79 / 0.77 / 0.81 | 0.95 | 0.98 |
| filters and a latency range, no text | 0.83 / 0.87 / 0.88 | 0.80 | |
| phrase prefix with tenant and app | 0.93 / 0.92 / 0.92 | 0.93 | 0.98 |
| top-50 with tenant and payload equalities | 0.77 | 0.82 | |
| top-50 tool failures | 0.93 | 0.77 | |
| the other 18 queries | 0.89-1.04 | 0.91-1.04 | |
Hot: both versions interleaved in one BE process, three runs where three are
shown, on a host with a
load of about 100 to 140 from other builds. An earlier round at a load of
230 to 400 read up to 1.41
on some queries that do not gain; their reruns gave 0.95-1.07. Cold: BE
restarted and the index files
evicted before every run, configuration order alternated, 5 runs each; the
change only saves CPU, so
cold runs stay about level. The build also had #69879, #69882, #69887 and
#69891, with
`snii_inline_read_max_segments` at 16.
### Release note
Speed up inverted index filters that match many rows.
### Check List (For Author)
- Test: Unit Test (`RoaringDocIdSinkTest`: random postings of 0.05% to 90%
density, even and in
bursts, in batches from 1 document to the whole posting, match adding the
documents one by one and
pass `roaring_bitmap_internal_validate`; the array limit, merging into
array, bitset and run
containers, repeats across spans, chunk edges up to the last document, and
spans that are not
strictly ascending; seven mutants all fail tests; 2153 inverted index
tests pass under ASAN).
Manual test: the hot and cold A/B above; the 25 queries of the bench
return the same results with
both versions on SNII and on V3.
- 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]
