Skip to content

Commit 58005f7

Browse files
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: No
1 parent 7cf3131 commit 58005f7

5 files changed

Lines changed: 80 additions & 7 deletions

File tree

‎be/src/storage/index/inverted/query/engine/boolean_query/listed_terms.cpp‎

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -109,6 +109,13 @@ index_query::TruthSet ListedTerms::conjunction(const std::vector<uint32_t>* cand
109109
}
110110
return result;
111111
}
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+
}
112119
std::vector<uint32_t> docs;
113120
THROW_IF_ERROR(index_query::chain_cursors(narrowing, candidates, &docs));
114121
result.true_rows.addMany(docs.size(), docs.data());

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

Lines changed: 10 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -96,12 +96,18 @@ void intersect_through_bit_set(std::span<const uint32_t> docs, std::span<const u
9696
preceding += static_cast<uint32_t>(std::popcount(bits[word]));
9797
}
9898
} else {
99+
// Every candidate is written and kept only when its bit is set, so no branch depends on
100+
// whether it matches.
101+
std::vector<uint32_t>& rows = *out.rows;
102+
const size_t begin = rows.size();
103+
rows.resize(begin + candidates.size());
104+
uint32_t* next = rows.data() + begin;
99105
for (const uint32_t candidate : candidates) {
100106
const uint32_t off = candidate - first;
101-
if ((bits[off >> 6] & (uint64_t {1} << (off & 63))) != 0) {
102-
out.append(candidate, 0);
103-
}
107+
*next = candidate;
108+
next += (bits[off >> 6] >> (off & 63)) & 1;
104109
}
110+
rows.resize(static_cast<size_t>(next - rows.data()));
105111
}
106112
}
107113

@@ -192,10 +198,7 @@ Status CursorChainedPostings::collect(std::vector<uint32_t>* out) {
192198
if (_candidates == nullptr) {
193199
out->reserve(out->size() + _cursor.doc_freq());
194200
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-
});
201+
return list_blocks(_cursor, sink);
199202
}
200203
out->reserve(out->size() + std::min<uint64_t>(_candidates->size(), _cursor.doc_freq()));
201204
return for_each_candidate_block(

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

Lines changed: 9 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.

‎be/test/storage/index/inverted/query/engine/boolean_query/listed_terms_test.cpp‎

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -524,6 +524,31 @@ TEST_F(ListedTermsTest, AConjunctionOfTermsHeldByEveryRowHoldsEveryRow) {
524524
EXPECT_TRUE(input->prefetches["each"].empty());
525525
}
526526

527+
// The one term left beside a term held by every row lists its own rows, or those among the
528+
// candidates.
529+
TEST_F(ListedTermsTest, ALoneTermListsItsRowsOrThoseAmongTheCandidates) {
530+
for (const bool batches : {false, true}) {
531+
auto input = source(batches);
532+
input->add("every", every_row(input->doc_count()));
533+
const auto lone = [&] {
534+
ListedTerms group(input, nullptr);
535+
group.add(0, "every");
536+
group.add(1, "c");
537+
group.open(/*conjunctive=*/true);
538+
return group;
539+
};
540+
EXPECT_EQ(lone().conjunction(nullptr).true_rows,
541+
roaring::Roaring::bitmapOf(3, 3U, 8U, 20U));
542+
const std::vector<uint32_t> candidates {2, 8, 20, 30};
543+
EXPECT_EQ(lone().conjunction(&candidates).true_rows,
544+
roaring::Roaring::bitmapOf(2, 8U, 20U));
545+
ASSERT_EQ(input->prefetches["c"].size(), 2U);
546+
EXPECT_TRUE(input->prefetches["c"][0].whole);
547+
EXPECT_EQ(input->prefetches["c"][1].candidates, candidates);
548+
EXPECT_TRUE(input->prefetches["every"].empty());
549+
}
550+
}
551+
527552
// Collecting every row of a scored disjunction lists its terms one after another; a TopK on a
528553
// source that does not batch its reads streams them side by side instead of holding every
529554
// matching row and score first, and ranks the rows alike.

‎be/test/storage/index/inverted/query/exec/cursor_chained_postings_test.cpp‎

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -22,6 +22,7 @@
2222
#include <algorithm>
2323
#include <cstdint>
2424
#include <limits>
25+
#include <random>
2526
#include <span>
2627
#include <utility>
2728
#include <vector>
@@ -320,6 +321,34 @@ TEST(CursorChainedPostings, OrdinalIntersectionCoversSparseWideAndBoundedBlocks)
320321
}
321322
}
322323

324+
// Random documents and candidates of a block's span, as unrelated terms of several densities meet.
325+
TEST(CursorChainedPostings, IntersectionHandlesRandomDensities) {
326+
std::mt19937 random(20261016);
327+
for (const uint32_t span : {256U, 1024U, 16384U}) {
328+
for (const double doc_rate : {0.05, 0.5, 0.95}) {
329+
for (const double candidate_rate : {0.05, 0.5, 0.95}) {
330+
std::bernoulli_distribution holds_doc(doc_rate);
331+
std::bernoulli_distribution holds_candidate(candidate_rate);
332+
std::vector<uint32_t> docs;
333+
std::vector<uint32_t> candidates;
334+
for (uint32_t doc = 0; doc < span; ++doc) {
335+
if (holds_doc(random)) {
336+
docs.push_back(doc);
337+
}
338+
if (holds_candidate(random)) {
339+
candidates.push_back(doc);
340+
}
341+
}
342+
ASSERT_FALSE(docs.empty());
343+
std::erase_if(candidates, [&](uint32_t doc) {
344+
return doc < docs.front() || doc > docs.back();
345+
});
346+
check_ordinals(docs, candidates);
347+
}
348+
}
349+
}
350+
}
351+
323352
TEST(CursorChainedPostings, RetainsPartialSparseBlockOrdinals) {
324353
BlockedCursor cursor({BlockedCursor::listed({1, 3, 8}), BlockedCursor::dense(10, 13),
325354
BlockedCursor::listed({20, 21}), BlockedCursor::listed({30, 34, 40})});

0 commit comments

Comments
 (0)