Merge pull request #30612 from vespa-engine/havardpe/stop-using-non-heap-strict-ORv8.319.9

stop using non-heap strict OR

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<std::variant<size_t,vespalib::stringref>>;
 
+vespalib::string strict_equiv_name = "search::queryeval::EquivImpl<true, search::queryeval::StrictHeapOrSearch<search::queryeval::NoUnpack, vespalib::LeftArrayHeap, unsigned char> >";
+
 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<true>", search->getClassName());
+    EXPECT_EQUAL(strict_equiv_name, search->getClassName());
     {
         const auto & e = dynamic_cast<const MultiSearch &>(*search);
         EXPECT_EQUAL("search::BitVectorIteratorStrictT<false>", 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<true>", search->getClassName());
+    EXPECT_EQUAL(strict_equiv_name, search->getClassName());
     {
         const auto & e = dynamic_cast<const MultiSearch &>(*search);
         EXPECT_EQUAL("search::BitVectorIteratorStrictT<false>", 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<true>", search->getClassName());
+    EXPECT_EQUAL(strict_equiv_name, search->getClassName());
     {
         const auto & e = dynamic_cast<const MultiSearch &>(*search);
         EXPECT_EQUAL("search::queryeval::StrictHeapOrSearch<search::queryeval::(anonymous namespace)::FullUnpack, vespalib::LeftArrayHeap, unsigned char>",
@@ -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<true>", search->getClassName());
+    EXPECT_EQUAL(strict_equiv_name, search->getClassName());
     {
         const auto & e = dynamic_cast<const MultiSearch &>(*search);
         EXPECT_EQUAL("search::queryeval::StrictHeapOrSearch<search::queryeval::(anonymous namespace)::SelectiveUnpack, vespalib::LeftArrayHeap, unsigned char>",
@@ -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<true>", search->getClassName());
+    EXPECT_EQUAL(strict_equiv_name, search->getClassName());
     {
         const auto & e = dynamic_cast<const MultiSearch &>(*search);
         EXPECT_EQUAL("search::queryeval::StrictHeapOrSearch<search::queryeval::NoUnpack, vespalib::LeftArrayHeap, unsigned char>",
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 <bool is_strict>
-struct LocationPreFilterIterator : public OrLikeSearch<is_strict, NoUnpack>
+template <bool is_strict, typename Parent>
+struct LocationPreFilterIterator : public Parent
 {
     explicit LocationPreFilterIterator(OrSearch::Children children)
-        : OrLikeSearch<is_strict, NoUnpack>(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<LocationPreFilterIterator<true>>(std::move(children));
+            if (children.size() < 0x70) {
+                using Parent = StrictHeapOrSearch<NoUnpack, vespalib::LeftArrayHeap, uint8_t>;
+                return std::make_unique<LocationPreFilterIterator<true, Parent>>(std::move(children));
+            } else {
+                using Parent = StrictHeapOrSearch<NoUnpack, vespalib::LeftHeap, uint32_t>;
+                return std::make_unique<LocationPreFilterIterator<true, Parent>>(std::move(children));
+            }
         } else {
-            return std::make_unique<LocationPreFilterIterator<false>>(std::move(children));
+            using Parent = OrLikeSearch<false, NoUnpack>;
+            return std::make_unique<LocationPreFilterIterator<false, Parent>>(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 <typename... Args>
         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 <vespa/vespalib/util/left_right_heap.h>
 
 namespace search::queryeval {
 
-template <bool strict>
-class EquivImpl : public OrLikeSearch<strict, NoUnpack>
+template <bool strict, typename Parent>
+class EquivImpl : public Parent
 {
 private:
     fef::MatchData::UP        _inputMatchData;
@@ -27,22 +28,22 @@ public:
               const fef::TermFieldMatchDataArray &outputs);
 };
 
-template<bool strict>
-EquivImpl<strict>::EquivImpl(MultiSearch::Children children,
-                             fef::MatchData::UP inputMatchData,
-                             const fef::TermMatchDataMerger::Inputs &inputs,
-                             const fef::TermFieldMatchDataArray &outputs)
+template<bool strict, typename Parent>
+EquivImpl<strict, Parent>::EquivImpl(MultiSearch::Children children,
+                                     fef::MatchData::UP inputMatchData,
+                                     const fef::TermMatchDataMerger::Inputs &inputs,
+                                     const fef::TermFieldMatchDataArray &outputs)
 
-    : OrLikeSearch<strict, NoUnpack>(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<bool strict>
+template<bool strict, typename Parent>
 void
-EquivImpl<strict>::doUnpack(uint32_t docid)
+EquivImpl<strict, Parent>::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<EquivImpl<true>>(std::move(children), std::move(inputMatchData), inputs, outputs);
+        if (children.size() < 0x70) {
+            using Parent = StrictHeapOrSearch<NoUnpack, vespalib::LeftArrayHeap, uint8_t>;
+            return std::make_unique<EquivImpl<true, Parent>>(std::move(children), std::move(inputMatchData), inputs, outputs);
+        } else {
+            using Parent = StrictHeapOrSearch<NoUnpack, vespalib::LeftHeap, uint32_t>;
+            return std::make_unique<EquivImpl<true, Parent>>(std::move(children), std::move(inputMatchData), inputs, outputs);
+        }
     } else {
-        return std::make_unique<EquivImpl<false>>(std::move(children), std::move(inputMatchData), inputs, outputs);
+        using Parent = OrLikeSearch<false, NoUnpack>;
+        return std::make_unique<EquivImpl<false, Parent>>(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 <typename Unpack, typename HEAP, typename ref_t>
-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 <typename Unpack, typename HEAP, typename ref_t>
+StrictHeapOrSearch<Unpack, HEAP, ref_t>::~StrictHeapOrSearch() = default;
 
 }