Skip to content

Commit f937d95

Browse files
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/listed_terms.cpp‎

Lines changed: 34 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -90,8 +90,41 @@ index_query::TruthSet ListedTerms::conjunction(const std::vector<uint32_t>* cand
9090
if (has_absent_term()) {
9191
return result;
9292
}
93+
// A term held by every row the source lists cannot narrow the conjunction, so the chain
94+
// lists only the other terms.
95+
const uint32_t doc_count = _source->doc_count();
96+
std::vector<index_query::PostingsCursor*> narrowing;
97+
for (const auto& cursor : _cursors) {
98+
if (cursor->doc_freq() != doc_count) {
99+
narrowing.push_back(cursor.get());
100+
}
101+
}
102+
if (narrowing.empty()) {
103+
if (candidates == nullptr) {
104+
result.true_rows.addRange(0, doc_count);
105+
} else {
106+
const auto end = std::ranges::lower_bound(*candidates, doc_count);
107+
result.true_rows.addMany(static_cast<size_t>(end - candidates->begin()),
108+
candidates->data());
109+
}
110+
return result;
111+
}
112+
// A lone term lists its blocks straight into the result instead of through a list of its rows.
113+
if (narrowing.size() == 1 && candidates == nullptr) {
114+
THROW_IF_ERROR(narrowing.front()->prefetch(nullptr, /*positions=*/false));
115+
index_query::RoaringDocIdSink sink(result.true_rows);
116+
THROW_IF_ERROR(index_query::list_blocks(*narrowing.front(), sink));
117+
return result;
118+
}
119+
// A source reading on demand intersects the terms a batch of rows at a time, straight into
120+
// the result, instead of listing every row of the cheapest term first.
121+
if (candidates == nullptr && !_source->batches_reads()) {
122+
index_query::RoaringDocIdSink sink(result.true_rows);
123+
THROW_IF_ERROR(index_query::stream_cursors(narrowing, sink));
124+
return result;
125+
}
93126
std::vector<uint32_t> docs;
94-
THROW_IF_ERROR(index_query::chain_cursors(_cursors, candidates, &docs));
127+
THROW_IF_ERROR(index_query::chain_cursors(narrowing, candidates, &docs));
95128
result.true_rows.addMany(docs.size(), docs.data());
96129
return result;
97130
}

‎be/src/storage/index/inverted/query/exec/cursor_chained_postings.cpp‎

Lines changed: 160 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -22,6 +22,7 @@
2222
#include <bit>
2323
#include <numeric>
2424

25+
#include "common/check.h"
2526
#include "storage/index/inverted/query/exec/docid_sink.h"
2627

2728
namespace doris::index_query {
@@ -96,12 +97,18 @@ void intersect_through_bit_set(std::span<const uint32_t> docs, std::span<const u
9697
preceding += static_cast<uint32_t>(std::popcount(bits[word]));
9798
}
9899
} else {
100+
// Every candidate is written and kept only when its bit is set, so no branch depends on
101+
// whether it matches.
102+
std::vector<uint32_t>& rows = *out.rows;
103+
const size_t begin = rows.size();
104+
rows.resize(begin + candidates.size());
105+
uint32_t* next = rows.data() + begin;
99106
for (const uint32_t candidate : candidates) {
100107
const uint32_t off = candidate - first;
101-
if ((bits[off >> 6] & (uint64_t {1} << (off & 63))) != 0) {
102-
out.append(candidate, 0);
103-
}
108+
*next = candidate;
109+
next += (bits[off >> 6] >> (off & 63)) & 1;
104110
}
111+
rows.resize(static_cast<size_t>(next - rows.data()));
105112
}
106113
}
107114

@@ -192,10 +199,7 @@ Status CursorChainedPostings::collect(std::vector<uint32_t>* out) {
192199
if (_candidates == nullptr) {
193200
out->reserve(out->size() + _cursor.doc_freq());
194201
VectorDocIdSink sink(*out);
195-
return for_each_block(_cursor, [&sink](const PostingsBlock& block) {
196-
return block.dense ? sink.append_range(block.range_begin, block.range_end)
197-
: sink.append_sorted(block.docs);
198-
});
202+
return list_blocks(_cursor, sink);
199203
}
200204
out->reserve(out->size() + std::min<uint64_t>(_candidates->size(), _cursor.doc_freq()));
201205
return for_each_candidate_block(
@@ -219,8 +223,11 @@ Status CursorChainedPostings::collect(std::vector<uint32_t>* out) {
219223
});
220224
}
221225

222-
Status chain_cursors(std::span<const std::unique_ptr<PostingsCursor>> cursors,
223-
const std::vector<uint32_t>* candidates, std::vector<uint32_t>* rows) {
226+
namespace {
227+
228+
template <typename Cursors>
229+
Status chain(const Cursors& cursors, const std::vector<uint32_t>* candidates,
230+
std::vector<uint32_t>* rows) {
224231
std::vector<CursorChainedPostings> terms;
225232
terms.reserve(cursors.size());
226233
std::vector<ChainedPostings*> chain;
@@ -232,4 +239,148 @@ Status chain_cursors(std::span<const std::unique_ptr<PostingsCursor>> cursors,
232239
return chained_conjunction(chain, candidates, rows);
233240
}
234241

242+
} // namespace
243+
244+
Status chain_cursors(std::span<const std::unique_ptr<PostingsCursor>> cursors,
245+
const std::vector<uint32_t>* candidates, std::vector<uint32_t>* rows) {
246+
return chain(cursors, candidates, rows);
247+
}
248+
249+
Status chain_cursors(std::span<PostingsCursor* const> cursors,
250+
const std::vector<uint32_t>* candidates, std::vector<uint32_t>* rows) {
251+
return chain(cursors, candidates, rows);
252+
}
253+
254+
namespace {
255+
256+
// The most rows of the cheapest cursor a stream lists at once.
257+
constexpr size_t kStreamRows = size_t {1} << 16;
258+
259+
// The cheapest cursor of a stream, handing on its rows a batch at a time.
260+
class StreamLead {
261+
public:
262+
explicit StreamLead(PostingsCursor& cursor) : _cursor(cursor) {}
263+
264+
Status start() { return _cursor.next_block(&_block, &_eof); }
265+
bool exhausted() const { return _eof; }
266+
267+
// Replaces `rows` by the cursor's next rows, at most kStreamRows of them; the rest of the
268+
// current block waits for the next batch.
269+
Status take_batch(std::vector<uint32_t>* rows) {
270+
rows->clear();
271+
while (!_eof) {
272+
const size_t size = _block.size();
273+
const size_t stop = std::min(size, _taken + (kStreamRows - rows->size()));
274+
if (_block.dense) {
275+
const size_t old = rows->size();
276+
rows->resize(old + stop - _taken);
277+
std::iota(rows->begin() + old, rows->end(),
278+
static_cast<uint32_t>(_block.range_begin + _taken));
279+
} else {
280+
rows->insert(rows->end(), _block.docs.begin() + _taken, _block.docs.begin() + stop);
281+
}
282+
if (stop < size) {
283+
_taken = stop;
284+
return Status::OK();
285+
}
286+
RETURN_IF_ERROR(_cursor.next_block(&_block, &_eof));
287+
_taken = 0;
288+
if (rows->size() == kStreamRows) {
289+
return Status::OK();
290+
}
291+
}
292+
return Status::OK();
293+
}
294+
295+
private:
296+
PostingsCursor& _cursor;
297+
PostingsBlock _block;
298+
size_t _taken = 0;
299+
bool _eof = false;
300+
};
301+
302+
// A cursor narrowing a stream's rows; it keeps its current block for the next batch's rows.
303+
class StreamFollower {
304+
public:
305+
explicit StreamFollower(PostingsCursor& cursor) : _cursor(cursor) {}
306+
307+
// Appends the ascending `rows` the cursor holds to `out`; `ended` once it holds no later row.
308+
Status narrow(std::span<const uint32_t> rows, std::vector<uint32_t>* out, bool* ended) {
309+
size_t next = 0;
310+
while (next < rows.size()) {
311+
if (!_loaded || _last < rows[next]) {
312+
bool eof = false;
313+
RETURN_IF_ERROR(_cursor.seek_block(rows[next], &_block, &eof));
314+
if (eof) {
315+
*ended = true;
316+
return Status::OK();
317+
}
318+
_loaded = true;
319+
_last = _block.doc_at(_block.size() - 1);
320+
}
321+
const uint32_t first = _block.doc_at(0);
322+
const size_t begin =
323+
gallop_past(rows, next, [first](uint32_t doc) { return doc < first; });
324+
next = gallop_past(rows, begin, [this](uint32_t doc) { return doc <= _last; });
325+
if (next == begin) {
326+
continue;
327+
}
328+
const auto slice = rows.subspan(begin, next - begin);
329+
// A dense block holds every row in its span.
330+
if (_block.dense) {
331+
out->insert(out->end(), slice.begin(), slice.end());
332+
} else {
333+
intersect_block(_block.docs, slice, DocumentOutput {out});
334+
}
335+
}
336+
return Status::OK();
337+
}
338+
339+
private:
340+
PostingsCursor& _cursor;
341+
PostingsBlock _block;
342+
uint32_t _last = 0;
343+
bool _loaded = false;
344+
};
345+
346+
} // namespace
347+
348+
Status stream_cursors(std::span<PostingsCursor* const> cursors, DocIdSink& sink) {
349+
DORIS_CHECK(!cursors.empty());
350+
std::vector<PostingsCursor*> order(cursors.begin(), cursors.end());
351+
std::ranges::stable_sort(order, {},
352+
[](const PostingsCursor* cursor) { return cursor->doc_freq(); });
353+
for (PostingsCursor* cursor : order) {
354+
RETURN_IF_ERROR(cursor->prefetch(nullptr, /*positions=*/false));
355+
}
356+
StreamLead lead(*order.front());
357+
std::vector<StreamFollower> followers;
358+
followers.reserve(order.size() - 1);
359+
for (size_t i = 1; i < order.size(); ++i) {
360+
followers.emplace_back(*order[i]);
361+
}
362+
std::vector<uint32_t> rows;
363+
std::vector<uint32_t> narrowed;
364+
RETURN_IF_ERROR(lead.start());
365+
while (!lead.exhausted()) {
366+
RETURN_IF_ERROR(lead.take_batch(&rows));
367+
bool ended = false;
368+
for (StreamFollower& follower : followers) {
369+
narrowed.clear();
370+
RETURN_IF_ERROR(follower.narrow(rows, &narrowed, &ended));
371+
rows.swap(narrowed);
372+
if (rows.empty()) {
373+
break;
374+
}
375+
}
376+
if (!rows.empty()) {
377+
RETURN_IF_ERROR(sink.append_sorted(rows));
378+
}
379+
if (ended) {
380+
return Status::OK();
381+
}
382+
}
383+
return Status::OK();
384+
}
385+
235386
} // namespace doris::index_query

‎be/src/storage/index/inverted/query/exec/cursor_chained_postings.h‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -26,6 +26,7 @@
2626

2727
#include "common/status.h"
2828
#include "storage/index/inverted/query/exec/chained_conjunction.h"
29+
#include "storage/index/inverted/query/exec/docid_sink.h"
2930
#include "storage/index/inverted/query/spi/postings_cursor.h"
3031

3132
namespace doris::index_query {
@@ -60,6 +61,14 @@ Status for_each_block(PostingsCursor& cursor, Visit&& visit) {
6061
}
6162
}
6263

64+
// Appends every document the cursor lists from its position to `sink`, a dense block as a range.
65+
inline Status list_blocks(PostingsCursor& cursor, DocIdSink& sink) {
66+
return for_each_block(cursor, [&sink](const PostingsBlock& block) {
67+
return block.dense ? sink.append_range(block.range_begin, block.range_end)
68+
: sink.append_sorted(block.docs);
69+
});
70+
}
71+
6372
// Calls `visit(block, slice)` for every block of the cursor that can hold one of the
6473
// ascending `candidates`, with the candidates between its first and last document. Only those
6574
// blocks are decoded.
@@ -123,5 +132,12 @@ class CursorChainedPostings final : public ChainedPostings {
123132
// narrows the cheapest cursor's rows by the others.
124133
Status chain_cursors(std::span<const std::unique_ptr<PostingsCursor>> cursors,
125134
const std::vector<uint32_t>* candidates, std::vector<uint32_t>* rows);
135+
Status chain_cursors(std::span<PostingsCursor* const> cursors,
136+
const std::vector<uint32_t>* candidates, std::vector<uint32_t>* rows);
137+
138+
// Appends to `sink` the rows every one of `cursors` holds, a batch of at most 2^16 rows of the
139+
// cheapest cursor at a time, which the others narrow, so no list holds more than a batch. Each
140+
// cursor is read in order, which suits a source that reads on demand.
141+
Status stream_cursors(std::span<PostingsCursor* const> cursors, DocIdSink& sink);
126142

127143
} // namespace doris::index_query

0 commit comments

Comments
 (0)