Repository navigation
Commit f937d95
authored
[improvement](be) Speed up dense unscored inverted index conjunctions (apache#69172)
### What problem does this PR solve?
Issue Number: N/A
Related PR: apache#68758
Problem Summary:
apache#68758 runs an unscored AND of terms on one field, such as MATCH_ALL, as
a chain: the rarest term's rows are listed into an array and the other
terms narrow them into another. On dense terms this was slower than the
bitmap intersection it replaced on V2 segments, and its arrays grew with
the segment (review comment M2 on apache#68758):
1. A term held by every row cannot remove any row, but the chain still
read its postings. For `MATCH_ALL 'http status'`, where both terms are
held by every row, it copied every row id twice and rebuilt the result
bitmap from the array: 14.4 ms on a 2M-row V2 segment, about 10 times
what it took before apache#68758.
2. A term left alone, such as `get` in `get http` once `http` is
skipped, was listed into an array of all its rows before the result
bitmap was built from it. For a term in 90% of 2M rows that cost about
1,200 extra page faults per query.
3. Intersecting a block through a bit set tested each candidate with a
branch. For two unrelated terms each in half the rows (`alpha beta`),
the branch mispredicted about half the time, and the intersection took
30% of the scan thread's cycles.
4. The arrays held up to 8 bytes per row of the segment in each scanner.
This PR:
- skips a term whose document frequency equals the source's document
count, so a conjunction whose terms are all held by every row returns
every row, or every candidate, without reading postings;
- lists a lone term's blocks straight into the result bitmap, a dense
block as a range;
- intersects a block through its bit set without a branch per candidate:
every candidate is written and kept only when its bit is set;
- streams a conjunction of several terms on a source that reads on
demand, such as a V2 segment: the cheapest term lists at most 2^16 of
its rows at a time, the others narrow them, and the rows left go
straight into the result, so no array holds more than a batch. The other
terms keep their current block from one batch to the next, so each block
is still decoded once. A batching source, such as SNII, keeps the chain,
which reads each term's blocks in one round.
Scored queries keep their path, and results are unchanged.
Index filter time of MATCH_ALL on a 2M-row V2 segment, as the median
ratio of 8 paired runs on fresh backends; each column is a separate
comparison and lower is faster:
| Query | Rows holding each term | vs apache#68758 | vs before apache#68758 |
|---|---|---|---|
| `http status` | 100%, 100% | 0.01 | 0.10 |
| `rare http` | 0.05%, 100% | 0.31 | 0.10 |
| `sparse http` | 0.5%, 100% | 0.23 | 0.31 |
| `get http` | 90%, 100% | 0.60 | 0.95 |
| `alpha beta` | 50%, 50% | 0.56 | 0.72 |
In the comparison with apache#68758, the `http status` filter drops from 16.9
ms to 0.15 ms and its end-to-end time to 0.63, and the end-to-end time
of `alpha beta` to 0.81. SNII segments take the same paths except the
stream; there these queries take 0.02 to 0.83 of apache#68758 and 0.02 to 0.93
of their time before apache#68758. Seven more shapes, from `rare alpha` and
`sparse alpha` to `alpha beta get` and the empty `get post`, take 0.20
to 0.89 of their time before apache#68758 on V2 and 0.57 to 1.00 on SNII.
Two-term MATCH_ALL queries on short text take 0.86 to 1.01 of apache#68758,
and the 18 queries used to accept apache#68758 (MATCH_PHRASE, MATCH_ANY and
SEARCH phrases on V2 and SNII) stay between 0.97 and 1.03 of it, every
95% interval including 1.
On V2 the stream holds at most two arrays of 2^16 rows per scanner, and
it cuts the page faults per query of `alpha beta` from 458 to 192 and
those of `get alpha` from 484 to 47. Its scan threads run within 1% of
the chain's instructions, and a cheapest term of at most 2^16 rows is
listed in one batch, as the chain lists it.
### Release note
None
### Check List (For Author)
- Test <!-- At least one of them must be included. -->
- [ ] 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 test: `ListedTermsTest.AConjunctionSkipsATermHeldByEveryRow` and
`ListedTermsTest.AConjunctionOfTermsHeldByEveryRowHoldsEveryRow` fail
before the first commit, because the chain read the term held by every
row, and pass after it.
`ListedTermsTest.AConjunctionOnAStreamingSourceStreamsItsTerms` replaces
`AConjunctionOnAStreamingSourceChainsItsTermsToo`, which recorded that
such a source chained its terms, and fails before the last commit.
`ListedTermsTest.ALoneTermListsItsRowsOrThoseAmongTheCandidates`,
`CursorChainedPostings.IntersectionHandlesRandomDensities` and the
`CursorChainedPostings.AStream*` tests cover the lone-term listing, the
intersection and the stream; each fails when the code it covers is
broken on purpose.
Manual test: a 2M-row corpus with terms held by 100%, 90%, 50%, 10%,
0.5% and 0.05% of the rows was loaded into a V2 table and an SNII table.
Each of 8 pairs started two fresh backends, one per build, swapping
which backend ran which build on alternate pairs; each query ran 4
warm-up and 16 measured times on each build, alternating between the
builds. Every result matched aggregates computed independently from the
corpus. Scan-thread CPU time, cycles, instructions and page faults were
sampled with `perf stat` over 200 runs of each query on each build.
- Behavior changed:
- [x] No.
- [ ] Yes. <!-- Explain the behavior change -->
- Does this need documentation?
- [x] No.
- [ ] Yes. <!-- Add document PR link here. eg:
apache/doris-website#1214 -->
### 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 -->1 parent 6c27d4d commit f937d95
5 files changed
Lines changed: 460 additions & 20 deletions
File tree
- be
- src/storage/index/inverted/query
- engine/boolean_query
- exec
- test/storage/index/inverted/query
- engine/boolean_query
- exec
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
90 | 90 | | |
91 | 91 | | |
92 | 92 | | |
| 93 | + | |
| 94 | + | |
| 95 | + | |
| 96 | + | |
| 97 | + | |
| 98 | + | |
| 99 | + | |
| 100 | + | |
| 101 | + | |
| 102 | + | |
| 103 | + | |
| 104 | + | |
| 105 | + | |
| 106 | + | |
| 107 | + | |
| 108 | + | |
| 109 | + | |
| 110 | + | |
| 111 | + | |
| 112 | + | |
| 113 | + | |
| 114 | + | |
| 115 | + | |
| 116 | + | |
| 117 | + | |
| 118 | + | |
| 119 | + | |
| 120 | + | |
| 121 | + | |
| 122 | + | |
| 123 | + | |
| 124 | + | |
| 125 | + | |
93 | 126 | | |
94 | | - | |
| 127 | + | |
95 | 128 | | |
96 | 129 | | |
97 | 130 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
22 | 22 | | |
23 | 23 | | |
24 | 24 | | |
| 25 | + | |
25 | 26 | | |
26 | 27 | | |
27 | 28 | | |
| |||
96 | 97 | | |
97 | 98 | | |
98 | 99 | | |
| 100 | + | |
| 101 | + | |
| 102 | + | |
| 103 | + | |
| 104 | + | |
| 105 | + | |
99 | 106 | | |
100 | 107 | | |
101 | | - | |
102 | | - | |
103 | | - | |
| 108 | + | |
| 109 | + | |
104 | 110 | | |
| 111 | + | |
105 | 112 | | |
106 | 113 | | |
107 | 114 | | |
| |||
192 | 199 | | |
193 | 200 | | |
194 | 201 | | |
195 | | - | |
196 | | - | |
197 | | - | |
198 | | - | |
| 202 | + | |
199 | 203 | | |
200 | 204 | | |
201 | 205 | | |
| |||
219 | 223 | | |
220 | 224 | | |
221 | 225 | | |
222 | | - | |
223 | | - | |
| 226 | + | |
| 227 | + | |
| 228 | + | |
| 229 | + | |
| 230 | + | |
224 | 231 | | |
225 | 232 | | |
226 | 233 | | |
| |||
232 | 239 | | |
233 | 240 | | |
234 | 241 | | |
| 242 | + | |
| 243 | + | |
| 244 | + | |
| 245 | + | |
| 246 | + | |
| 247 | + | |
| 248 | + | |
| 249 | + | |
| 250 | + | |
| 251 | + | |
| 252 | + | |
| 253 | + | |
| 254 | + | |
| 255 | + | |
| 256 | + | |
| 257 | + | |
| 258 | + | |
| 259 | + | |
| 260 | + | |
| 261 | + | |
| 262 | + | |
| 263 | + | |
| 264 | + | |
| 265 | + | |
| 266 | + | |
| 267 | + | |
| 268 | + | |
| 269 | + | |
| 270 | + | |
| 271 | + | |
| 272 | + | |
| 273 | + | |
| 274 | + | |
| 275 | + | |
| 276 | + | |
| 277 | + | |
| 278 | + | |
| 279 | + | |
| 280 | + | |
| 281 | + | |
| 282 | + | |
| 283 | + | |
| 284 | + | |
| 285 | + | |
| 286 | + | |
| 287 | + | |
| 288 | + | |
| 289 | + | |
| 290 | + | |
| 291 | + | |
| 292 | + | |
| 293 | + | |
| 294 | + | |
| 295 | + | |
| 296 | + | |
| 297 | + | |
| 298 | + | |
| 299 | + | |
| 300 | + | |
| 301 | + | |
| 302 | + | |
| 303 | + | |
| 304 | + | |
| 305 | + | |
| 306 | + | |
| 307 | + | |
| 308 | + | |
| 309 | + | |
| 310 | + | |
| 311 | + | |
| 312 | + | |
| 313 | + | |
| 314 | + | |
| 315 | + | |
| 316 | + | |
| 317 | + | |
| 318 | + | |
| 319 | + | |
| 320 | + | |
| 321 | + | |
| 322 | + | |
| 323 | + | |
| 324 | + | |
| 325 | + | |
| 326 | + | |
| 327 | + | |
| 328 | + | |
| 329 | + | |
| 330 | + | |
| 331 | + | |
| 332 | + | |
| 333 | + | |
| 334 | + | |
| 335 | + | |
| 336 | + | |
| 337 | + | |
| 338 | + | |
| 339 | + | |
| 340 | + | |
| 341 | + | |
| 342 | + | |
| 343 | + | |
| 344 | + | |
| 345 | + | |
| 346 | + | |
| 347 | + | |
| 348 | + | |
| 349 | + | |
| 350 | + | |
| 351 | + | |
| 352 | + | |
| 353 | + | |
| 354 | + | |
| 355 | + | |
| 356 | + | |
| 357 | + | |
| 358 | + | |
| 359 | + | |
| 360 | + | |
| 361 | + | |
| 362 | + | |
| 363 | + | |
| 364 | + | |
| 365 | + | |
| 366 | + | |
| 367 | + | |
| 368 | + | |
| 369 | + | |
| 370 | + | |
| 371 | + | |
| 372 | + | |
| 373 | + | |
| 374 | + | |
| 375 | + | |
| 376 | + | |
| 377 | + | |
| 378 | + | |
| 379 | + | |
| 380 | + | |
| 381 | + | |
| 382 | + | |
| 383 | + | |
| 384 | + | |
| 385 | + | |
235 | 386 | | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
26 | 26 | | |
27 | 27 | | |
28 | 28 | | |
| 29 | + | |
29 | 30 | | |
30 | 31 | | |
31 | 32 | | |
| |||
60 | 61 | | |
61 | 62 | | |
62 | 63 | | |
| 64 | + | |
| 65 | + | |
| 66 | + | |
| 67 | + | |
| 68 | + | |
| 69 | + | |
| 70 | + | |
| 71 | + | |
63 | 72 | | |
64 | 73 | | |
65 | 74 | | |
| |||
123 | 132 | | |
124 | 133 | | |
125 | 134 | | |
| 135 | + | |
| 136 | + | |
| 137 | + | |
| 138 | + | |
| 139 | + | |
| 140 | + | |
| 141 | + | |
126 | 142 | | |
127 | 143 | | |
0 commit comments