guptashivam04 opened a new pull request, #69752:
URL: https://github.com/apache/doris/pull/69752
### What problem does this PR solve?
Issue Number: None
Related PR: #69438 (this is its backport to branch-4.2), #69352 and its
branch-4.2 pick #69440 (BM25 statistics shared across the parallel scanners of
a tablet)
Problem Summary:
Backport of #69438 to branch-4.2.
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, and pagination over
`ORDER BY score()` repeats and skips rows from one page to the next.
`CollectionStatistics::process_segment()` takes the document count, the token
count and each term's document frequency straight from every segment's inverted
index. Rows a later load overwrote or deleted (marked only in the delete
bitmap) and rows written with the delete sign (CDC deletes, `DELETE`) stay in
the index and are counted until compaction removes them, and each replica
compacts on its own schedule.
On branch-4.2 (3 BEs, `replication_num = 3`, 8 buckets, CDC-style upserts
and delete-sign deletes, the replicas on one BE fully compacted), all 1,731
matching rows of a `SEARCH(... OR ...)` query got more than one score over 15
runs and differed between `use_fix_replica = 0/1/2`.
Fix: the same change as #69438. 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 (#69440).
- Per segment, the hidden rows are the rows the delete bitmap marks at the
read version plus the rows whose `__DORIS_DELETE_SIGN__` is set. The
delete-sign column is read only for segments whose zone map shows a non-zero
sign (or cannot tell), following 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()` subtracts the
hidden rows a term's postings list, leaping between them when they are much
rarer than the postings, otherwise walking them alongside the decoded postings.
- Token count: the sum of the document lengths the norms of the returned
non-NULL rows stand for (NULL rows left out through the index's null bitmap),
or the returned row count for an index without norms. Every replica counts the
same, compacted or not.
- CLucene norms are read one segment at a time into a buffer of the
statistics' own and not kept; the non-NULL norm length sum of a field and the
length sums of its last four sets of hidden rows are kept with the cached
searcher (`CluceneSearcherCacheValue`).
- A tablet whose rows are all hidden reports zero documents instead of
failing the query.
Tables without a delete bitmap collect the same statistics as before. For
every `score()` query, the statistics' I/O context follows `disable_file_cache`
and `inverted_index_snii_read_no_write_file_cache`, and a CLucene searcher the
statistics open drops the query's I/O context once its meta is read; a CLucene
error while opening it fails the query.
Differences from #69438, for branch-4.2: segments are identified by their id
instead of `RowsetSegmentView`, and the delete-sign column reader comes from
`Segment::get_column_reader()` (branch-4.2 has no
`get_column_reader_for_pruning`), a segment without the column reading as no
deletes. The tests are adapted the same way.
Not covered (as in #69438): merge-on-read unique tables and duplicate tables
with `DELETE` predicates; rows deleted by a delete predicate
(`enable_mow_light_delete`); rows written with the delete sign that the query
returns (`skip_delete_sign`, `show_hidden_columns`) are still left out; an
analyzed empty string, and on SNII any text that yields no token, counts as one
token on a merge-on-write table; SNII norm length sums are not cached.
Statistics stay per tablet.
### Release note
Fix BM25 `score()` on merge-on-write tables differing between the replicas
of a tablet, and before and after compaction. Statistics now count only the
rows a query can return, and the average document length comes from the indexed
norms.
### Check List (For Author)
- Test
- [x] Regression test:
- New: `inverted_index_p0/test_bm25_score_replica_statistics` and
`fault_injection_p0/test_bm25_score_statistics_searcher_io_context` (same
suites as #69438). Updated `.out`: `test_bm25_score.out`,
`test_score_filter_matrix.out` (V2, V3 and SNII merge-on-write cases), same
values as #69438.
- All 26 branch-4.2 suites that use `score()` (`inverted_index_p0`,
`search`, `ann_index_p0`, `variant_p0`, `nereids_rules_p0`,
`fault_injection_p0`) pass with this change on a 3-BE cluster. Without it, the
replica suite, the fault-injection suite (the query fails with `[E-6002] The
'is_index_data' flag should be false for non-meta inverted index files.`) and
the two updated suites fail.
- [x] Unit Test: the tests of #69438
(`CollectionStatisticsTest.HiddenRowsAreCollectedLikeCompactedAway`,
`AllRowsHiddenCollectsEmptyStatistics`,
`NullRowsCountAsDocumentsWithoutTokens`, `CollectionStatisticsHiddenRowsTest.*`
for `count_listed_docs`, `exclude_hidden_docs` and `exclude_hidden_term_docs`,
`CluceneSearcherCacheValueTest.*`,
`MultiSegmentCollectorTest.NormLengthSumsReadEachSegment`,
`OlapScannerTest.BuildScoreRuntimeCollectionIoContextFollowsQueryFileCacheOptions`),
with the existing collection statistics, BM25, searcher cache, multi-segment,
query engine, SNII and `SEARCH` function tests: 427 tests in 35 suites pass in
an ASAN build on macOS arm64.
- [x] Manual test (3 BEs, macOS arm64, `replication_num = 3`, auto
compaction off, `enable_sql_cache = false`), base = branch-4.2 without this
change, same data and compaction state for both builds:
| Check | branch-4.2 | with this change |
|---|---|---|
| CDC-style table (8 buckets, upserts, delete-sign deletes, NULLs, 4
fields), one BE's replicas fully compacted with inverted index compaction off:
rows with more than one score over 15 runs / differing between replicas 0, 1, 2
(of 1,731) | 1,731 / 1,731 | 0 / 0 |
| Same, scores differing from a freshly loaded copy of the visible
rows | — | 0 of 1,731 |
| Partial-column updates, sequence column, stream load with the
delete sign and `merge_type: DELETE`, group commit, keyword and
lowercase-normalizer indexes, partitions, variant, SNII: rows differing between
replicas after one replica compacted | 84–790 per table (8 of 9 checks) | 0 in
every check, all equal to a fresh copy |
| Merge-on-write vs duplicate table with 50 % NULL rows, V3 and SNII
| 0 of 250 differ | 0 of 250 differ |
Cost, query `SEARCH('content:jobs OR content:try') ORDER BY score()
DESC LIMIT 100`, one bucket, median of 15 warm runs; `StatisticsCollectTime`
with one scanner, query total of `SEARCH('content:jobs')` with the default
parallel scan:
| Table | Statistics | Query total |
|---|---|---|
| V2, 8 M rows + 200 k overwritten + 50 k delete-sign rows | 0.3 ms
→ 6.7 ms | 68 ms → 76 ms |
| V3, 6 M rows + 2 M overwritten + 200 k delete-sign rows (2.2 M
hidden, 6 % NULL) | 0.3 ms → 55 ms | 61 ms → 113 ms |
| V2, 6 M rows + 2 M overwritten, no NULL rows | 0.3 ms → 7.2 ms |
56 ms → 61 ms |
| SNII, 2 M rows + 500 k overwritten + 200 k delete-sign rows | 0.2
ms → 23 ms | 49 ms → 71 ms |
The cost grows with the rows compaction has not removed yet. With
NULL rows, most of it is leaving the NULL rows out of the hidden rows on every
query (`exclude_hidden_docs`), as in #69438.
Memory (BE allocated bytes, sum of 3 BEs, a 4-field merge-on-write
table of 41 segments): no growth beyond the noise of the measurement (after 4
queries +26 MB → +25 MB with key pruning; +142 MB → below the starting value
scoring all segments).
- Behavior changed:
- [x] Yes. On merge-on-write tables, BM25 statistics leave out rows
hidden by the delete bitmap and rows with the delete sign, and avgdl is
computed from the norms of the visible rows, so scores no longer depend on the
replica or on compaction. Scores of merge-on-write tables shift once, also
without deletes, because norms store long lengths approximately.
- Does this need documentation?
- [x] No.
### Check List (For Reviewer who merge this PR)
- [ ] Confirm the release note
- [ ] Confirm test cases
- [ ] Confirm document
- [ ] Add branch pick label
--
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]
