Repository navigation
Commit 58005f7
committed
[improvement](be) Intersect dense postings without a branch per candidate and list a lone term straight into the result
### What problem does this PR solve?
Issue Number: None
Related PR: #68758
Problem Summary: After terms held by every row are skipped, two dense MATCH_ALL cases on
V2 stay slower than before #68758. For `get http`, the term left alone is listed into an
array of every row it holds before the result bitmap is built from it, which costs about
1,200 extra page faults per query on 2M rows. For `alpha beta`, two unrelated terms each
held by half the rows, the bit-set intersection tests each candidate with a branch that
mispredicts about half the time; it takes 30% of the scan thread's cycles.
A lone term now lists its blocks straight into the result, a dense block as a range. The
bit-set intersection writes every candidate and keeps it only when its bit is set, so no
branch depends on whether a candidate matches. On a 2M-row V2 segment the index filter of
`get http` drops to 0.74 and that of `alpha beta` to 0.73 of the previous commit, 0.98 and
0.92 of their time before #68758; on SNII they drop to 0.79 and 0.70.
### Release note
None
### Check List (For Author)
- Test: Unit Test. ListedTermsTest.ALoneTermListsItsRowsOrThoseAmongTheCandidates and
CursorChainedPostings.IntersectionHandlesRandomDensities; each fails when the code it
covers is broken on purpose. Manual test: the dense MATCH_ALL benchmark of the previous
commit, and the 18 queries used to accept #68758, which stay within 0.97 and 1.02 of the
previous commit.
- Behavior changed: No.
- Does this need documentation: No1 parent 7cf3131 commit 58005f7
5 files changed
Lines changed: 80 additions & 7 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 | |
|---|---|---|---|
| |||
109 | 109 | | |
110 | 110 | | |
111 | 111 | | |
| 112 | + | |
| 113 | + | |
| 114 | + | |
| 115 | + | |
| 116 | + | |
| 117 | + | |
| 118 | + | |
112 | 119 | | |
113 | 120 | | |
114 | 121 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
96 | 96 | | |
97 | 97 | | |
98 | 98 | | |
| 99 | + | |
| 100 | + | |
| 101 | + | |
| 102 | + | |
| 103 | + | |
| 104 | + | |
99 | 105 | | |
100 | 106 | | |
101 | | - | |
102 | | - | |
103 | | - | |
| 107 | + | |
| 108 | + | |
104 | 109 | | |
| 110 | + | |
105 | 111 | | |
106 | 112 | | |
107 | 113 | | |
| |||
192 | 198 | | |
193 | 199 | | |
194 | 200 | | |
195 | | - | |
196 | | - | |
197 | | - | |
198 | | - | |
| 201 | + | |
199 | 202 | | |
200 | 203 | | |
201 | 204 | | |
| |||
| 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 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
524 | 524 | | |
525 | 525 | | |
526 | 526 | | |
| 527 | + | |
| 528 | + | |
| 529 | + | |
| 530 | + | |
| 531 | + | |
| 532 | + | |
| 533 | + | |
| 534 | + | |
| 535 | + | |
| 536 | + | |
| 537 | + | |
| 538 | + | |
| 539 | + | |
| 540 | + | |
| 541 | + | |
| 542 | + | |
| 543 | + | |
| 544 | + | |
| 545 | + | |
| 546 | + | |
| 547 | + | |
| 548 | + | |
| 549 | + | |
| 550 | + | |
| 551 | + | |
527 | 552 | | |
528 | 553 | | |
529 | 554 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
22 | 22 | | |
23 | 23 | | |
24 | 24 | | |
| 25 | + | |
25 | 26 | | |
26 | 27 | | |
27 | 28 | | |
| |||
320 | 321 | | |
321 | 322 | | |
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 | + | |
323 | 352 | | |
324 | 353 | | |
325 | 354 | | |
| |||
0 commit comments