From 3b4a94c933ffb4c2525ca4e44043f7a5775fa287 Mon Sep 17 00:00:00 2001 From: Håvard Pettersen Date: Wed, 13 Mar 2024 13:07:18 +0000 Subject: stop using non-heap strict OR --- .../blueprint/intermediate_blueprints_test.cpp | 12 ++++--- .../attribute/attribute_blueprint_factory.cpp | 18 +++++++--- .../vespa/searchlib/queryeval/children_iterators.h | 2 ++ .../src/vespa/searchlib/queryeval/equivsearch.cpp | 38 +++++++++++++--------- .../src/vespa/searchlib/queryeval/orlikesearch.h | 19 ++++++----- 5 files changed, 56 insertions(+), 33 deletions(-) diff --git a/searchlib/src/tests/queryeval/blueprint/intermediate_blueprints_test.cpp b/searchlib/src/tests/queryeval/blueprint/intermediate_blueprints_test.cpp index f192ea93b0e..d2df4a8c24f 100644 --- a/searchlib/src/tests/queryeval/blueprint/intermediate_blueprints_test.cpp +++ b/searchlib/src/tests/queryeval/blueprint/intermediate_blueprints_test.cpp @@ -36,6 +36,8 @@ using vespalib::slime::SlimeInserter; using vespalib::make_string_short::fmt; using Path = std::vector>; +vespalib::string strict_equiv_name = "search::queryeval::EquivImpl >"; + struct InvalidSelector : ISourceSelector { InvalidSelector() : ISourceSelector(Source()) {} void setSource(uint32_t, Source) override { abort(); } @@ -1141,7 +1143,7 @@ TEST("require that children does not optimize when parents refuse them to") { MatchData::UP md = MatchData::makeTestInstance(100, 10); top_up->fetchPostings(ExecuteInfo::FALSE); SearchIterator::UP search = top_up->createSearch(*md, true); - EXPECT_EQUAL("search::queryeval::EquivImpl", search->getClassName()); + EXPECT_EQUAL(strict_equiv_name, search->getClassName()); { const auto & e = dynamic_cast(*search); EXPECT_EQUAL("search::BitVectorIteratorStrictT", e.getChildren()[0]->getClassName()); @@ -1151,7 +1153,7 @@ TEST("require that children does not optimize when parents refuse them to") { md->resolveTermField(12)->tagAsNotNeeded(); search = top_up->createSearch(*md, true); - EXPECT_EQUAL("search::queryeval::EquivImpl", search->getClassName()); + EXPECT_EQUAL(strict_equiv_name, search->getClassName()); { const auto & e = dynamic_cast(*search); EXPECT_EQUAL("search::BitVectorIteratorStrictT", e.getChildren()[0]->getClassName()); @@ -1179,7 +1181,7 @@ TEST("require_that_unpack_optimization_is_not_overruled_by_equiv") { MatchData::UP md = MatchData::makeTestInstance(100, 10); top_up->fetchPostings(ExecuteInfo::FALSE); SearchIterator::UP search = top_up->createSearch(*md, true); - EXPECT_EQUAL("search::queryeval::EquivImpl", search->getClassName()); + EXPECT_EQUAL(strict_equiv_name, search->getClassName()); { const auto & e = dynamic_cast(*search); EXPECT_EQUAL("search::queryeval::StrictHeapOrSearch", @@ -1188,7 +1190,7 @@ TEST("require_that_unpack_optimization_is_not_overruled_by_equiv") { md->resolveTermField(2)->tagAsNotNeeded(); search = top_up->createSearch(*md, true); - EXPECT_EQUAL("search::queryeval::EquivImpl", search->getClassName()); + EXPECT_EQUAL(strict_equiv_name, search->getClassName()); { const auto & e = dynamic_cast(*search); EXPECT_EQUAL("search::queryeval::StrictHeapOrSearch", @@ -1198,7 +1200,7 @@ TEST("require_that_unpack_optimization_is_not_overruled_by_equiv") { md->resolveTermField(1)->tagAsNotNeeded(); md->resolveTermField(3)->tagAsNotNeeded(); search = top_up->createSearch(*md, true); - EXPECT_EQUAL("search::queryeval::EquivImpl", search->getClassName()); + EXPECT_EQUAL(strict_equiv_name, search->getClassName()); { const auto & e = dynamic_cast(*search); EXPECT_EQUAL("search::queryeval::StrictHeapOrSearch", diff --git a/searchlib/src/vespa/searchlib/attribute/attribute_blueprint_factory.cpp b/searchlib/src/vespa/searchlib/attribute/attribute_blueprint_factory.cpp index 2129ac40724..e70c498d3c3 100644 --- a/searchlib/src/vespa/searchlib/attribute/attribute_blueprint_factory.cpp +++ b/searchlib/src/vespa/searchlib/attribute/attribute_blueprint_factory.cpp @@ -88,6 +88,7 @@ using search::queryeval::PredicateBlueprint; using search::queryeval::SearchIterator; using search::queryeval::Searchable; using search::queryeval::SimpleLeafBlueprint; +using search::queryeval::StrictHeapOrSearch; using search::queryeval::WeightedSetTermBlueprint; using search::queryeval::flow::btree_cost; using search::queryeval::flow::btree_strict_cost; @@ -235,11 +236,11 @@ AttributeFieldBlueprint::visitMembers(vespalib::ObjectVisitor &visitor) const //----------------------------------------------------------------------------- -template -struct LocationPreFilterIterator : public OrLikeSearch +template +struct LocationPreFilterIterator : public Parent { explicit LocationPreFilterIterator(OrSearch::Children children) - : OrLikeSearch(std::move(children), NoUnpack()) {} + : Parent(std::move(children), NoUnpack()) {} void doUnpack(uint32_t) override {} }; @@ -312,9 +313,16 @@ public: children.push_back(search->createIterator(tfmda[0], strict)); } if (strict) { - return std::make_unique>(std::move(children)); + if (children.size() < 0x70) { + using Parent = StrictHeapOrSearch; + return std::make_unique>(std::move(children)); + } else { + using Parent = StrictHeapOrSearch; + return std::make_unique>(std::move(children)); + } } else { - return std::make_unique>(std::move(children)); + using Parent = OrLikeSearch; + return std::make_unique>(std::move(children)); } } SearchIteratorUP createFilterSearch(bool strict, FilterConstraint constraint) const override { diff --git a/searchlib/src/vespa/searchlib/queryeval/children_iterators.h b/searchlib/src/vespa/searchlib/queryeval/children_iterators.h index 1a8a10c764e..3e579ac0f51 100644 --- a/searchlib/src/vespa/searchlib/queryeval/children_iterators.h +++ b/searchlib/src/vespa/searchlib/queryeval/children_iterators.h @@ -18,6 +18,8 @@ class ChildrenIterators { : _data(std::move(data)) {} ChildrenIterators(ChildrenIterators && other) = default; + size_t size() const noexcept { return _data.size(); } + // convenience constructors for unit tests: template ChildrenIterators(SearchIterator::UP a, Args&&... args) { diff --git a/searchlib/src/vespa/searchlib/queryeval/equivsearch.cpp b/searchlib/src/vespa/searchlib/queryeval/equivsearch.cpp index 9e1b634da95..d712f104274 100644 --- a/searchlib/src/vespa/searchlib/queryeval/equivsearch.cpp +++ b/searchlib/src/vespa/searchlib/queryeval/equivsearch.cpp @@ -1,11 +1,12 @@ // Copyright Vespa.ai. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. #include "equivsearch.h" +#include namespace search::queryeval { -template -class EquivImpl : public OrLikeSearch +template +class EquivImpl : public Parent { private: fef::MatchData::UP _inputMatchData; @@ -27,22 +28,22 @@ public: const fef::TermFieldMatchDataArray &outputs); }; -template -EquivImpl::EquivImpl(MultiSearch::Children children, - fef::MatchData::UP inputMatchData, - const fef::TermMatchDataMerger::Inputs &inputs, - const fef::TermFieldMatchDataArray &outputs) +template +EquivImpl::EquivImpl(MultiSearch::Children children, + fef::MatchData::UP inputMatchData, + const fef::TermMatchDataMerger::Inputs &inputs, + const fef::TermFieldMatchDataArray &outputs) - : OrLikeSearch(std::move(children), NoUnpack()), - _inputMatchData(std::move(inputMatchData)), - _merger(inputs, outputs), - _valid(outputs.valid()) + : Parent(std::move(children), NoUnpack()), + _inputMatchData(std::move(inputMatchData)), + _merger(inputs, outputs), + _valid(outputs.valid()) { } -template +template void -EquivImpl::doUnpack(uint32_t docid) +EquivImpl::doUnpack(uint32_t docid) { if (_valid) { MultiSearch::doUnpack(docid); @@ -58,9 +59,16 @@ EquivSearch::create(Children children, bool strict) { if (strict) { - return std::make_unique>(std::move(children), std::move(inputMatchData), inputs, outputs); + if (children.size() < 0x70) { + using Parent = StrictHeapOrSearch; + return std::make_unique>(std::move(children), std::move(inputMatchData), inputs, outputs); + } else { + using Parent = StrictHeapOrSearch; + return std::make_unique>(std::move(children), std::move(inputMatchData), inputs, outputs); + } } else { - return std::make_unique>(std::move(children), std::move(inputMatchData), inputs, outputs); + using Parent = OrLikeSearch; + return std::make_unique>(std::move(children), std::move(inputMatchData), inputs, outputs); } } diff --git a/searchlib/src/vespa/searchlib/queryeval/orlikesearch.h b/searchlib/src/vespa/searchlib/queryeval/orlikesearch.h index a15a87c2d03..bd383f72d87 100644 --- a/searchlib/src/vespa/searchlib/queryeval/orlikesearch.h +++ b/searchlib/src/vespa/searchlib/queryeval/orlikesearch.h @@ -67,7 +67,7 @@ private: }; template -class StrictHeapOrSearch final : public OrSearch +class StrictHeapOrSearch : public OrSearch { private: struct Less { @@ -88,12 +88,12 @@ private: _data[i] = i; } } - void onRemove(size_t index) override { + void onRemove(size_t index) final { _unpacker.onRemove(index); _child_docid.erase(_child_docid.begin() + index); init_data(); } - void onInsert(size_t index) override { + void onInsert(size_t index) final { _unpacker.onInsert(index); _child_docid.insert(_child_docid.begin() + index, getChildren()[index]->getDocId()); init_data(); @@ -116,7 +116,8 @@ public: HEAP::require_left_heap(); init_data(); } - void initRange(uint32_t begin, uint32_t end) override { + ~StrictHeapOrSearch() override; + void initRange(uint32_t begin, uint32_t end) final { OrSearch::initRange(begin, end); for (size_t i = 0; i < getChildren().size(); ++i) { _child_docid[i] = getChildren()[i]->getDocId(); @@ -125,24 +126,26 @@ public: HEAP::push(data_begin(), data_pos(i), Less(_child_docid)); } } - void doSeek(uint32_t docid) override { + void doSeek(uint32_t docid) final { while (_child_docid[HEAP::front(data_begin(), data_end())] < docid) { seek_child(HEAP::front(data_begin(), data_end()), docid); HEAP::adjust(data_begin(), data_end(), Less(_child_docid)); } setDocId(_child_docid[HEAP::front(data_begin(), data_end())]); } - void doUnpack(uint32_t docid) override { + void doUnpack(uint32_t docid) override { // <- not final _unpacker.each([&](ref_t child) { if (__builtin_expect(_child_docid[child] == docid, false)) { getChildren()[child]->doUnpack(docid); } }, getChildren().size()); } - bool needUnpack(size_t index) const override { + bool needUnpack(size_t index) const final { return _unpacker.needUnpack(index); } - Trinary is_strict() const override { return Trinary::True; } + Trinary is_strict() const final { return Trinary::True; } }; +template +StrictHeapOrSearch::~StrictHeapOrSearch() = default; } -- cgit v1.2.3