guptashivam04 opened a new pull request, #69438:
URL: https://github.com/apache/doris/pull/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 set sign, so a segment without CDC deletes
costs nothing extra.
- 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 tests each against a bitset of the
hidden rows, so its cost follows the smaller of the two. 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
rows stand for (`IndexSource::sum_norm_lengths()` minus
`sum_norm_lengths_of(hidden rows)`), 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 23 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.
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.
Tables without a delete bitmap (duplicate key, merge-on-read, or
`skip_delete_bitmap`) are unchanged.
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`, rows written with the delete sign are
returned but still left out of the statistics.
- 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.
### 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 rows
visible to the query, and the average document length comes from the indexed
norms.
### Check List (For Author)
- Test
- [x] Regression test:
`inverted_index_p0/test_bm25_score_replica_statistics`. It loads overwrites,
`DELETE`s and delete-sign rows, then expects every row to score exactly as in a
table freshly loaded with the visible rows. It checks before compaction, with
one replica compacted (≥ 3 BEs: 10 runs and `use_fix_replica = 0/1/2`), and
after compacting all replicas. Without this change it fails before any
compaction (`1352 rows score differently from a freshly loaded table`). With
it, it passes on a 3-BE cluster.
- [x] Existing suites: all 24 suites that use `score()` (in
`inverted_index_p0`, `search`, `ann_index_p0`, `variant_p0` and
`nereids_rules_p0`) pass on a 3-BE cluster. One expected value changes: in
`test_bm25_score`, table `t2` is a merge-on-write table whose row `a = 3` was
updated, so the old version of that row no longer counts. Two documents count
instead of three, and the score of `hello world` goes from 1.0925692 to
0.8025915.
- [x] Unit Test:
`CollectionStatisticsTest.HiddenRowsAreCollectedLikeCompactedAway` (real
CLucene segments: a segment with a hidden 31-token row collects the same doc
count, token count, df, avgdl and idf as the segment without the row),
`CollectionStatisticsHiddenRowsTest.*` (counting hidden rows in postings by
scanning and by leaping, over sparse and dense blocks; norm sums; rows beyond
the index; indexes without norms). The test file compiles against current
master with `-Werror` and no warnings; running it needs the full BE unit-test
binary, which did not finish building in reasonable time on the test machine,
so CI is the first run.
- [x] Manual test: master with #69352, with and without this change,
macOS arm64, 3 BEs on one host, the reproduction above. `use_fix_replica` pins
one replica; "random" lets the FE pick a replica per tablet per query.
| State | without this change | with this change |
|---|---|---|
| replicas identical | 0 of 3,799 rows change across 10 runs, 950
scores | 0 rows change, 950 scores |
| full compaction on one replica, random replica, 10 runs | **3,799 of
3,799 rows change, 1,900 scores** | 0 rows change, 950 scores |
| same, `use_fix_replica = 0/1/2` compared | **every row differs
between replicas** | identical |
| all replicas compacted | stable, but differs from a fresh load of
the same rows on every row | identical to the one-replica-compacted state and
to a fresh load, bit for bit |
Same result for a 2-replica table with `BUCKETS AUTO`, the `unicode`
parser with `lower_case`, 4 indexed text columns queried by `SEARCH('a:x OR b:x
OR c:x OR d:x')` plus a non-index filter, auto compaction on, updates by
`INSERT INTO ... SELECT` and deletes by `DELETE FROM`. Before: every row
differed between the replicas (e.g. 3.30 vs 2.69). After: identical on both and
equal to a fresh load. The same holds with 1–10 MB text values.
Overhead, measured from query profiles with a 4-field `SEARCH(... OR
...)` and a non-index filter. Each number is the median of 15 runs on the same
data and query:
| Table | without this change | with this change |
|---|---|---|
| 11 k rows, 3 replicas | 27 ms | 15 ms (within noise) |
| 1.75 M visible rows, 1.3 M hidden (43 % of stored rows), 8 buckets |
35 ms | 36 ms |
The cost grows with the rows compaction has not removed yet, and comes
from two parts. To count the hidden rows that hold a term, the collector leaps
from hidden row to hidden row when they are much rarer than the term's postings
(32 times rarer). Otherwise it decodes the postings once and tests each against
a bitset of the hidden rows. Norms are summed through a length table.
- [ ] No need to test or manual test.
- Behavior changed:
- [x] Yes. On merge-on-write tables, BM25 statistics leave out rows
hidden by the delete bitmap or the delete sign, and avgdl is computed from the
norms of the visible rows. Scores no longer depend on the replica or on
compaction. They also shift once on tables without deletes, because norms store
long lengths only approximately. Measured on freshly loaded tables:
| Texts | Mean score change | Largest change | Row pairs that swap
order | Top 100 |
|---|---|---|---|---|
| short to medium (up to ~45 words) | 0.27 % | 0.59 % | 0.021 % |
unchanged |
| long (~380 words on average) | 1.75 % | 2.6 % | 0.085 %, all
near-ties | 1 near-tie at the boundary |
| with 19 documents of 1–10 MB | 1.47 % | 6.2 % | 0.11 % | unchanged |
- 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]
