Skip to content

[fix](be) Preserve BM25 statistics through CLucene compaction - #69313

Open
Authorlove wants to merge 4 commits into
apache:masterfrom
Authorlove:fix/bm25-compaction-token-count
Open

Authorlove wants to merge 4 commits into
apache:masterfrom
Authorlove:fix/bm25-compaction-token-count

Conversation

@Authorlove

@Authorlove Authorlove commented Oct 20, 2026 •

Copy link
Copy Markdown

What problem does this PR solve?

Issue Number: None

Related PR: apache/doris-thirdparty#420

CLucene index compaction removes and redistributes postings, but the old implementation copied every source field's token total into the first destination and wrote zero to other destinations. BM25 therefore used incorrect average document lengths after deletes or multi-segment output. Two retained documents of lengths 1 and 16 should contribute 17 tokens, not the 529 tokens of their source rowsets.

Integrate the token-accounting fix from the merged third-party PR. For analyzed norms-bearing indexes without stored term frequencies, use Doris's existing raw-column rebuild path: quantized norms cannot reconstruct exact totals. Check every sibling index of a column before selecting native compaction, because eligibility is recorded per column and a frequency-bearing sibling must not re-enable an invalid native merge.

The dependency is pinned to the tested fix revision f2864e07f08583b5cc948e87e82294fd0fd5de16. The upstream squash-merge tree also contains a separate posting-codec replacement; this PR retains the isolated fix rather than introducing that additional dependency change.

This is independent of query-time visibility statistics. #69438 makes normal MoW queries use norms-based visible statistics, but other table paths still consume the persisted token total. DUP coverage is therefore essential: MoW score parity alone can mask an incorrect physical token total. SNII compaction selection is unchanged.

Release note

Correct BM25 token totals after CLucene inverted-index compaction removes or redistributes documents. Norms-bearing indexes without stored frequencies are rebuilt from column data during compaction.

Check List (For Author)

  • Built the master FE and patched ASAN BE through build.sh, using master baseline 8e10b23. Optional BE Java extensions disabled locally.

  • test_bm25_compaction_statistics passes all 24 combinations on that cluster: V2/V3, phrase support true/false, DUP DELETE, MoW light DELETE, MoW bitmap DELETE, delete-sign rows and overwritten versions; plus four same-column mixed-index cases covering both sibling orderings.

  • Each source rowset contains a surviving and a discarded document, exercising partial posting remapping. Compare independently loaded clean tables with compacted tables for visible rows, scores, TopK and offset; compare all hits when frequency-free MATCH_ANY has ties.

  • The identical regression fails on a freshly built pure-master ASAN BE at the first DUP DELETE score assertion: expected 0.285307 / 0.200849, actual 0.307739 / 0.340724. The FE and test inputs are unchanged.

  • clang-format 16, build hygiene, git diff --check and changed-line clang-tidy passed.

  • Dependency validation recorded in Add Md5Digest to util #420: 17 ASAN native tests passed, including deletion and multiple destination fields/segments; three new tests fail on the original dependency. Those historical dependency results are not a claim of rerunning the full native suite here.

  • Behavior changed: Yes. Corrected persisted statistics can change BM25 scores/ranking; frequency-free norms-bearing indexes rebuild from the original column during compaction.

  • Does this need documentation: No new configuration or storage format.

Performance tradeoff

The native fix reuses the posting merge traversal. Prior controlled CLucene measurements in #420 showed a small measurable cost. Raw-column rebuilding is materially more expensive: earlier 4.1.5 path-control measurements were 1.81–3.46 times the native merge elapsed time, and same-column sibling indexes amplify that cost. Those are historical single-host measurements, not a performance-neutrality or production-capacity claim for this build.

### What problem does this PR solve?

Issue Number: None

Related PR: CLucene token-statistics fix (to be linked)

Problem Summary:

Native CLucene compaction copied source token totals even when it removed documents, so an index built by compaction could score and rank the same visible rows differently from a freshly built index. Update the CLucene dependency to accumulate exact frequencies of retained postings per destination field.

Norms-bearing indexes with `support_phrase=false` do not retain the frequencies needed to reconstruct exact token totals. Select the existing raw-column rebuild path for their columns instead of invoking native CLucene compaction. The selection examines every sibling index because CLucene compaction eligibility is currently tracked per column. Normal frequency-bearing indexes retain native compaction; SNII selection is unchanged.

The regression compares scores and TopK/offset results of independently built clean indexes with full-compacted histories across V2/V3, `support_phrase=true/false`, delete-sign rows and overwritten versions. It does not encode a new BM25 formula or require immediate visible-row statistics before compaction.

This PR depends on the linked third-party change. Keep it in draft until that dependency's final commit is available and the Doris integration checks pass.

### Release note

Correct BM25 token statistics after CLucene inverted-index compaction removes or redistributes documents. Norms-bearing indexes without stored frequencies are rebuilt from column data during compaction.

### Check List (For Author)

- Test
    - [x] Unit Test (dependency: 16 ASAN tests passed; new tests fail on its original implementation)
    - [x] Manual test (pre-fix reproduction and native-merge versus rebuild comparison on Doris 4.1.5)
    - [ ] Regression test (added; execution status to be updated)
    - [ ] Full Doris master BE/FE build and end-to-end execution
    - `build-support/clang-format.sh` and `build-support/check-format.sh` with clang-format 16.
    - `build-support/check-build-hygiene.sh` and `git diff --check`.
    - Full Doris build/clang-tidy requires the current third-party build bundle; no `compile_commands.json` is available yet.
- Behavior changed:
    - [x] Yes. Corrected compaction statistics can change scores/ranking. Norms-bearing CLucene indexes without frequencies use raw-column rebuilds during compaction.
- Does this need documentation?
    - [x] No. No new configuration or storage format.

### Check List (For Reviewer who merge this PR)

- [ ] Confirm the release note
- [ ] Confirm test cases
- [ ] Confirm document
- [ ] Add branch pick label
@hello-stephen

Copy link
Copy Markdown
Contributor

Thank you for your contribution to Apache Doris.
Don't know what should be done next? See How to process your PR.

Please clearly describe your PR:

  1. What problem was fixed (it's best to include specific error reporting information). How it was fixed.
  2. Which behaviors were modified. What was the previous behavior, what is it now, why was it modified, and what possible impacts might there be.
  3. What features were added. Why was this function added?
  4. Which code was refactored and why was this part of the code refactored?
  5. Which functions were optimized and what is the difference before and after the optimization?

### What problem does this PR solve?

Issue Number: None

Related PR: apache#69313
Related PR: apache/doris-thirdparty#420

Problem Summary:

Extend BM25 compaction parity coverage to DUP DELETE and both MoW deletion
modes across V2/V3 and phrase-support settings. Put retained and deleted
documents in each source rowset to exercise partial posting remapping.
Compare all MATCH_ANY hits without frequencies because equal scores leave
TopK ties unspecified. Run non-concurrently while changing the BE setting.
Update CLucene to include the matching single-destination regression.

### Release note

None (test coverage and dependency test update for the existing fix).

### Check List (For Author)

- Test: All 12 ordinary-DELETE manual comparisons reproduce the unpatched
  4.1.5 merge discrepancy; raw-column rebuilds match clean indexes.
  The repository regression script fails at the expected score assertion
  on 4.1.5. A rebuild-control copy passes all 20 combinations. 17 CLucene
  ASAN tests pass. Patched full Doris integration remains pending.
- Behavior changed: No additional production behavior changes.
- Does this need documentation: No.
Authorlove pushed a commit to Authorlove/doris that referenced this pull request Oct 21, 2026
### What problem does this PR solve?

Issue Number: None

Related PR: apache#69313
Related PR: apache/doris-thirdparty#420

Problem Summary:

DELETE and overwrite histories change BM25 scores for identical visible rows
because collection statistics read physical index metadata. Collect live N,
token totals and term document frequencies from the captured query snapshot
for CLucene V2/V3 DUP and merge-on-write UNIQUE tables, without compaction.

Share complete tablet statistics across split scanners. Read physical row IDs
through the storage reader's synthetic column. Cache immutable exact document
lengths in a bounded LRU, reconstructing them from frequencies or original text
where frequencies were omitted. Correct DF against the smaller visible or
excluded set. Publish complete cache loads only and allow waiters to cancel.
Preserve the keyword/normalizer unit-length convention for indexes without norms.

### Release note

Supported BM25 queries honor visible rows immediately after DML becomes visible.
Scores, ranking and score thresholds can change. Cold statistics initialization
and per-document length caches introduce query and memory costs. SNII, MOR/AGG
and changelog paths retain their existing scoring behavior.

### Check List (For Author)

- Test: 75 targeted ASAN BE tests passed through run-be-ut.sh, using temporary
  source selection for the complete selected suites and required test harness.
  Test source enumeration was restored afterward. Added a 20-combination SQL
  regression covering repeated reads, deletes, overwrites, reinserts, empty
  snapshots and forced scanner splitting with compaction disabled.
- Behavior changed: Yes, visible-snapshot BM25 statistics in the supported paths.
- Does this need documentation: No new syntax/configuration; scope and costs are
  documented in the PR description and release note.
airborne12 pushed a commit that referenced this pull request Oct 22, 2026
…of a tablet (#69352)

### What problem does this PR solve?

Issue Number: None

Related PR: #69313 (BM25 statistics after compaction), #66979 (deleted
documents in score TopN)

Problem Summary:

A parallel scan (`ParallelScannerBuilder`) splits one tablet into
several scanners. Each `OlapScanner` then calls
`CollectionStatistics::collect()` with only the `rs_splits` of its own
split, so the BM25 doc count, avgdl and term doc frequencies come from a
subset of the tablet's rowsets. Rows with identical text get different
scores depending on which scanner reads them.

The split depends on the tablet's total row count,
`parallel_scan_max_scanners_count` (defaulting to the core count) and
`parallel_scan_min_rows_per_scanner`. A row's score and its rank in
`ORDER BY score()` therefore change when unrelated rows are loaded into
the tablet, and differ between BEs with different core counts.
Pagination over a score-ordered search returns repeated and missing
rows.

Reproduction (one bucket, one replica, no concurrent writes):

```sql
CREATE TABLE t (
    id BIGINT,
    content TEXT,
    INDEX idx_content (content) USING INVERTED PROPERTIES("parser" = "english")
) UNIQUE KEY(id) DISTRIBUTED BY HASH(id) BUCKETS 1
PROPERTIES ("replication_num" = "1", "enable_unique_key_merge_on_write" = "true",
            "disable_auto_compaction" = "true");

-- 8 loads (8 rowsets), each with a different share of matching rows
INSERT INTO t SELECT 0 * 2000 + number, IF(number % 2  = 0, 'we should try these jobs today', 'call the candidate about salary') FROM numbers("number" = "2000");
INSERT INTO t SELECT 1 * 2000 + number, IF(number % 5  = 0, 'we should try these jobs today', 'call the candidate about salary') FROM numbers("number" = "2000");
-- ... batches 2..7 with modulus 8, 11, 14, 17, 20, 23

SELECT /*+ SET_VAR(enable_parallel_scan=true, parallel_scan_min_rows_per_scanner=1024, parallel_scan_max_scanners_count=16) */
       score() AS s, count(*)
FROM (SELECT score() FROM t WHERE SEARCH('content:jobs OR content:try') ORDER BY score() DESC LIMIT 100000) x
GROUP BY s;
```

On 4.1.4, the 2,280 matching rows all have the same text but get **15
distinct scores (1.34 to 5.81)**. With `enable_parallel_scan=false` they
all get 3.647686. On a production-sized table, the default thresholds
give the same behavior.

Fix:

- `TabletCollectionStatistics` holds the rowsets of a tablet's entire
read source. The first scanner of the tablet to prepare collects the
statistics once with `collect_full_collection()`, and every scanner of
that tablet copies them into its own `CollectionStatistics`. Later
scanners wait for the first collection and get its result or error.
- `CollectionStatistics::copy_collected_from()` copies the collected
counters and resets the derived idf/avgdl caches, so no cache is shared
between scanner threads.
- `ParallelScannerBuilder` creates one holder per tablet, only when the
scan has a `score()` runtime. Both the by-rowid and per-segment build
paths pass it to their scanners.
- The non-parallel path is unchanged. Each of its scanners already
receives the tablet's full read source.

Statistics remain per tablet. Making them consistent across tablets and
BEs (as with Elasticsearch's `dfs_query_then_fetch`) is out of scope.
airborne12 pushed a commit that referenced this pull request Oct 26, 2026
…erge-on-write tables (#69438)

### What problem does this PR solve?

Issue Number: None

Related PR: #69352 (BM25 statistics shared across the parallel scanners
of a tablet; this PR is its follow-up for replicas), #69313 (BM25 token
totals after CLucene compaction)

Problem Summary:

On a merge-on-write table, BM25 `score()` gives the same row a different
score on each replica of its tablet. A query picks one replica per
tablet, so with `replication_num = 3` a row has up to three scores.
Pagination over `ORDER BY score()` then repeats and skips rows from one
page to the next. Each replica is stable on its own (`use_fix_replica`
pins the scores), but the replicas disagree.

`CollectionStatistics::process_segment()` takes the document count, the
token count and each term's document frequency straight from every
segment's inverted index. Under merge-on-write, a row overwritten or
deleted by a later load stays in its segment's index, marked only in the
delete bitmap. A row written with the delete sign, which CDC deletes and
`DELETE` produce, stays as a normal row that queries filter out by
predicate. Both kinds are counted until compaction removes them, and
each replica compacts on its own schedule. So each replica counts a
different set of rows nobody can see.

Reproduction (3 BEs, `replication_num = 3`, 8 buckets, auto compaction
off): 8 loads, 3 rounds of overwriting a quarter of the rows, a
`DELETE`, and full rows inserted with `__DORIS_DELETE_SIGN__ = 1`. Then
a full compaction (`POST /api/compaction/run?compact_type=full`) of the
tablets on one BE only. On master with #69352, the query below changed
the score of all 3,799 matching rows from run to run: 1,900 distinct
scores instead of 950. With `use_fix_replica = 0/1/2` each replica was
stable, but the three disagreed.

```sql
SELECT id, score() FROM rt WHERE SEARCH('content:jobs OR content:try') ORDER BY score() DESC LIMIT 100000;
```

The token total has a second, replica-independent problem: CLucene index
compaction (`inverted_index_compaction_enable`, on by default) copies
the source token totals even when it drops rows, which #69313 addresses.
On master, the same rows scored differently in a compacted table and in
a table freshly loaded with its visible rows.

Fix:

When the scan reads a delete bitmap (merge-on-write),
`CollectionStatistics` describes only the rows the scan returns:

- `OlapScanner` passes the scan's delete bitmap and read version
(`MowHiddenRows`) to `collect()`, or to
`TabletCollectionStatistics::copy_to()` for a split tablet. Every
scanner of a tablet reads with the same bitmap and version, so the
statistics shared by #69352 stay correct.
- For each segment, the hidden rows are the rows the delete bitmap marks
at the read version (`get_agg`, the same call the rowset reader uses),
plus the rows whose hidden `__DORIS_DELETE_SIGN__` column is set. Every
unique-key table has that column, and `DELETE` on a merge-on-write table
writes such rows unless `enable_mow_light_delete` is on. The delete-sign
column is read only for segments whose zone map shows a non-zero sign
(or cannot tell), so a segment without CDC deletes costs nothing extra.
The read follows the query's `enable_segment_cache` and
`enable_page_cache`.
- Document count: the index's document count minus the hidden rows.
- Term document frequency: `IndexSource::scoring_doc_freq_among()`
counts how many hidden rows a term's postings list. When the hidden rows
are much rarer than the term's postings, it leaps between them with
`seek_block`. Otherwise it decodes the postings once and walks the
hidden rows alongside them, with no allocation, and a term without
postings costs nothing. SNII overrides it so that reserved-namespace
scoring terms resolve as `scoring_doc_freq` resolves them.
- Token count: the sum of the document lengths the norms of the returned
non-NULL rows stand for, or the returned row count for an index without
norms. The exact length of a hidden row is not stored anywhere: CLucene
and SNII keep only the encoded norm (exact up to 40 tokens for CLucene,
up to 254 for SNII). Subtracting decoded lengths from the exact
`sumTotalTermFreq` would still leave replicas apart. A row's norm is the
same in every segment it is written to, so summing norms gives every
replica the same count. It is also the same quantity the BM25 tf
normalization already divides, `dl / avgdl`, with `dl` taken from the
same norm.
- A NULL row has no tokens, but its norm stands for one (CLucene's
default norm, SNII's `encode_norm(0)`). Its length is left out, using
the index's null bitmap, and it still counts as a document, as before.
So on CLucene a table whose texts all have at most 40 tokens, and none
of which is an empty string, scores exactly as a duplicate-key table
with the same rows.
- The statistics read CLucene norms into a buffer of their own, one
segment at a time, and keep none. Asking a CLucene reader for a field's
norms makes it keep them for the searcher's lifetime, uncharged to the
searcher cache, and the statistics visit every segment of the read set,
including those the scan prunes and never scores. Reading per segment
also avoids the copy of all segments' norms a multi-segment reader would
keep.
- What the statistics keep instead is small and kept with the cached
searcher: the sum of a field's non-NULL norm lengths, and the sum of the
hidden rows' lengths for the last few sets of hidden rows of a field
(queries at one read version hide the same rows). So queries at an
unchanged version read no norms; a segment's norms are read again only
when its hidden rows change. The hidden and NULL row ID lists the
statistics build while collecting are charged to the query's memory.

Why the token count has to change too: a variant that left out hidden
rows only from the document count and the document frequencies, keeping
today's token total, made the replicas agree only while every replica
compacted through inverted index compaction, which carries dropped rows'
token counts forward. With one replica compacted with
`inverted_index_compaction_enable = false` (the index rebuilt from
column data), every row again scored differently on that replica. Its
scores were also 12–31 % off a fresh load of the visible rows on
average, because its token total still counted the hidden rows.

A tablet whose rows are all hidden (every row deleted or overwritten,
not yet compacted) has no document a query can match. Its statistics
report zero documents instead of failing the query with "No data
available for SimilarityCollector".

Tables without a delete bitmap (duplicate key, merge-on-read, or
`skip_delete_bitmap`) collect the same statistics as before.

For every `score()` query, with or without a delete bitmap:

- The statistics reads follow the query's `disable_file_cache` and
`inverted_index_snii_read_no_write_file_cache`, as the scan's reads do.
They run before the scan, so they are the reads that fill the file
cache. CLucene reads norms without a per-read context, as scoring does.
- A CLucene searcher the statistics open drops the query's I/O context
once its meta is read, as the query path already does
(`create_index_searcher`), and a CLucene error while opening it fails
the query; before, it escaped the scanner thread uncaught and aborted
the backend. Before, a searcher the statistics put into the searcher
cache kept the opening query's I/O context, including its file cache
statistics pointer, for later queries to read through.

Not covered:

- Merge-on-read unique tables and duplicate tables with `DELETE`
predicates also count rows that compaction later drops. They need merge
or predicate evaluation to tell which rows are visible, and are left for
a follow-up.
- With `skip_delete_sign = true` or `show_hidden_columns = true`, rows
written with the delete sign are returned but still left out of the
statistics. Rows deleted by a delete predicate
(`enable_mow_light_delete`) are still counted, as the delete bitmap does
not mark them.
- A row indexed without tokens that is not NULL keeps a norm that cannot
be told from a one-token row's, so on a merge-on-write table it counts
as one token: an analyzed empty string, which both formats index like a
NULL but leave out of the null bitmap, and on SNII any text that yields
no token (for example `'!!!'`, or text without ASCII letters or digits
under the `english` parser), whose norm SNII stores as that of one
token. On CLucene such a text has a zero norm and counts as zero tokens.
Telling these rows apart would mean reading the column.
- On SNII, the sum of the norm lengths is not cached yet: each
merge-on-write query reads the segment's norms.
- Leaving NULL rows out relies on the index's null bitmap, which CLucene
index compaction carries over; if reading a source bitmap fails there,
the compacted index loses it (existing behaviour of the vendored CLucene
compaction).
- Statistics stay per tablet, as before.

Interaction with #69313: that PR makes the token total of a CLucene
index built by compaction exact. With this PR, merge-on-write scans no
longer read that total, so their scores do not depend on it. Scans of
other tables still do. The two changes are independent.
Authorlove and others added 2 commits November 1, 2026 13:23
### What problem does this PR solve?

Issue Number: None

Related PR: apache#69313, apache/doris-thirdparty#420

Problem Summary:
Compaction eligibility is tracked per column. A frequency-bearing sibling must
not re-enable native merging when another index on the column needs raw-column
rebuilding. Extend the BM25 parity regression with both sibling orderings for
V2/V3 DUP DELETE, and use the ranges algorithm required by current clang-tidy.

### Release note

None. This extends validation of the existing BM25 compaction correctness fix.

### Check List (For Author)

- Test: All 24 regression combinations passed with a current-master FE and the
  patched ASAN BE; formatting, build hygiene and changed-line clang-tidy passed.
- Behavior changed: No additional production behavior beyond the existing fix.
- Does this need documentation: No.
@Authorlove
Authorlove marked this pull request as ready for review November 2, 2026 07:55
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants