eldenmoon opened a new pull request, #68202:
URL: https://github.com/apache/doris/pull/68202
### What problem does this PR solve?
Issue Number: None
Related PR: #68039, #53980
Problem Summary:
A VARIANT column copies each inverted index definition to every materialized
path, so one SNII segment holds one logical index per (path, definition). Most
paths are sparse, and two SNII structures cost one entry per segment row
regardless of how many rows hold a value:
- **BM25 norms**: an analyzed index with positions stores one byte per row,
NULL rows included.
- **NULL bitmaps**: `NullBitmapWriter` serialized its CRoaring bitmap
without `runOptimize`, so every 65536-row container of a mostly NULL path
stayed an 8 KiB bitset (about N/8 bytes per index per segment). The definitions
on one path also stored identical copies.
On top of that, BM25 used the segment row count as the document count, so on
sparse paths avgdl came out far too small and idf differences were flattened.
This PR has two commits.
**Commit 1: no on-disk format change**
1. `NullBitmapWriter` run-optimizes and shrinks the bitmap before sizing and
writing it. The inverted index, direct SNII index compaction and the BKD blob's
`bkd_nulls` all go through this writer. Run containers are part of the portable
CRoaring format, so older builds read them.
2. The compound writer stores one null bitmap per subcolumn. It remembers
the last null bitmap it appended (suffix, XXH3-128 hash, length, region). When
the next logical index on the same suffix produces an identical bitmap, it
references that region instead of appending a copy. Region references are
absolute offsets and no reader assumes a region belongs to one index, so the
format is unchanged.
3. `CollectionStatistics` keeps a document count per field. SNII uses the
field's `indexed_doc_count` (non-NULL rows) for both avgdl and idf N, which is
what Lucene's `docCount` means. CLucene numbers are unchanged.
**Commit 2: sparse BM25 norms behind a switch**
- New section type `kNormsSparse` (15). It stores norms only for the
documents that carry one: present docids in 65536-docid blocks (ALL / ARRAY /
BITSET with a rank table / RUNS), plus one byte per present document, or a
single byte when all norms are equal.
- The writer keeps the existing dense `kNormsPod` (14) section,
byte-identical to before, when no document lacks a norm or when dense is not
larger.
- New mutable BE config `enable_snii_sparse_norms`, default `true`. The only
decision point is `LogicalIndexWriter::finalize_build`, which load, compaction,
schema change and BUILD INDEX all go through. Readers accept both layouts
regardless of the config.
- We also compared a CRoaring-based encoding of the present set on the same
data:
- Section bytes differed by under 1%.
- Its per-document lookups were 2–34x slower on a RELEASE build. They were
1.7–2.4x slower even with a batch API at 5% density, the most common density we
measured.
- Its zero-copy frozen view cannot be used safely on untrusted offsets.
- The hand-written block format was therefore kept.
**End-to-end results.** Each row compares master with this PR on the same
data, measured as the bytes of one compacted segment file on an ASAN build.
| Table | master | this PR | Detail |
|---|---|---|---|
| 1.02M-row VARIANT table, 1000 paths at 0.8% density, 11 index definitions
(3 analyzed with phrase) | 601.2 MB | **77.4 MB (7.8x)** | norms 382.5 → 6.2
MB; inverted null bitmaps 114.8 → 16.4 MB; BKD null bitmaps 65.6 → 16.4 MB;
dictionary / postings / BKD data unchanged |
| 677k-row GitHub-events table, payload `parser=none` + `parser=english`
(phrase) | 913.1 MB | **571.9 MB (1.60x)** | norms 324.3 → 39.8 MB; inverted
null bitmaps 86.4 → 31.9 MB; dictionary 351.2 MB unchanged |
| Same 1.02M-row data, `enable_snii_sparse_norms = false`, 10 load rowsets |
647.1 MB | 453.7 MB | null bitmaps only; norms stay in the dense layout |
BM25 scores are bit-identical between the dense and sparse layouts: after an
in-place upgrade, on tables mixing master-written and new segments, and after
full compaction into the new layout. `score()` latency did not regress.
**Compatibility (tested by swapping BE binaries over the same storage)**
| Case | Result |
|---|---|
| This PR reading segments written by master | MATCH, MATCH_PHRASE,
equality, IS NULL and BKD range counts identical |
| Master reading segments written by this PR with the config off | Read
natively, 0 fallbacks, `score()` works; commit 1 needs no switch |
| Master reading sparse norms sections | The index cannot be opened. Filters
fall back to row-by-row evaluation with correct results; `score()` fails with
E-6012. A full compaction by the older binary rewrites the index densely and
restores `score()`. Turn the config off while older BEs may read newly written
segments. |
### Release note
- BM25 scores (`score()`) of SNII inverted indexes on columns or VARIANT
paths with NULL rows change: avgdl and idf now use the field's non-NULL
document count instead of the segment row count, as Lucene does. Filtering
results do not change.
- SNII NULL bitmaps are run-length encoded and stored once per subcolumn;
the format is unchanged.
- New mutable BE config `enable_snii_sparse_norms` (default `true`): SNII
stores BM25 norms only for rows that carry one when that is smaller. BEs
without this change cannot use indexes written this way (filters fall back to
row-by-row evaluation and `score()` fails); set it to `false` while such BEs
may read newly written segments, e.g. during a rolling upgrade or before a
downgrade.
### Check List (For Author)
- Test <!-- At least one of them must be included. -->
- [x] Regression test
- [x] Unit Test
- [x] Manual test (add detailed scripts or steps below)
- [ ] No need to test or manual test. Explain why:
- [ ] This is a refactor/code format and no logic has been changed.
- [ ] Previous test can cover this change.
- [ ] No code files have been changed.
- [ ] Other reason <!-- Add your reason? -->
**Unit tests** (both commits built and tested on their own):
- Commit 1: 1788 SNII / norms / NULL bitmap / BM25 tests, 1779 pass.
- Final head: 1803 tests, 1794 pass.
- In both runs the only failures are 8 environment-specific
`SniiBatchRangeFetcher.*` / `SniiLocalFile.*` tests (their fixed `/tmp` files
belong to another OS user on the test host), and
`SniiGoldenCorpus.WriteOrVerify` is skipped without `SNII_GOLDEN_DIR`.
- New suites: `SniiNormsSection`, `SniiSparseNormsTest`,
`SniiSharedNullBitmap`, plus extended `SniiNullBitmap`,
`SniiIndexCompactionTest` (mixed dense/sparse sources, config on and off) and
`CollectionStatisticsTest`.
**Regression tests:**
- New `test_storage_format_snii_sparse_norms`: config on / off / toggled
per batch, full compaction, identical results and scores across layouts.
- `test_storage_format_snii_norms`: expectations regenerated for the new
BM25 statistics and hand-checked.
- These pass unchanged: `test_storage_format_snii`, `_utf8_wildcard`,
`_custom_analyzer`, `test_variant_search_subcolumn_snii`,
`regression_test_variant_var_index_snii`,
`regression_test_variant_snii_compaction`, `test_variant_v2_snii_index`,
`test_timestamp_ns_index`.
**Manual test:** the end-to-end A/B, upgrade and rollback runs
summarized above, on two clusters built from master and from this PR.
- Behavior changed:
- [ ] No.
- [x] Yes. <!-- Explain the behavior change -->
- `score()` values change for SNII indexes on fields with NULL rows
(see release note).
- With `enable_snii_sparse_norms` on, new SNII segments may carry
the new `kNormsSparse` section, which BEs without this change cannot use.
- Does this need documentation?
- [ ] No.
- [x] Yes. <!-- Add document PR link here. eg:
https://github.com/apache/doris-website/pull/1214 -->
- An entry for `enable_snii_sparse_norms` in the BE configuration
reference, and a note on the BM25 statistics in the scoring docs.
- Doc PR to follow.
### Check List (For Reviewer who merge this PR)
- [ ] Confirm the release note
- [ ] Confirm test cases
- [ ] Confirm document
- [ ] Add branch pick label <!-- Add branch pick label that this PR should
merge into -->
🤖 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]
