Merge pull request #10520 from vespa-engine/havardpe/blueprint-tiering

added cost tier to blueprints

7 files changed, 138 insertions, 19 deletions

diff --git a/searchlib/src/tests/queryeval/blueprint/blueprint_test.cpp b/searchlib/src/tests/queryeval/blueprint/blueprint_test.cpp
index 108b7b9d20d..72a686fddda 100644
--- a/searchlib/src/tests/queryeval/blueprint/blueprint_test.cpp
+++ b/searchlib/src/tests/queryeval/blueprint/blueprint_test.cpp
@@ -31,7 +31,7 @@ public:
     }
 
     virtual void sort(std::vector<Blueprint*> &children) const override {
-        std::sort(children.begin(), children.end(), GreaterEstimate());
+        std::sort(children.begin(), children.end(), TieredGreaterEstimate());
     }
 
     virtual bool inheritStrict(size_t i) const override {
@@ -672,6 +672,7 @@ getExpectedBlueprint()
            "    estimate: HitEstimate {\n"
            "        empty: false\n"
            "        estHits: 9\n"
+           "        cost_tier: 1\n"
            "        tree_size: 2\n"
            "        allow_termwise_eval: 0\n"
            "    }\n"
@@ -690,6 +691,7 @@ getExpectedBlueprint()
            "            estimate: HitEstimate {\n"
            "                empty: false\n"
            "                estHits: 9\n"
+           "                cost_tier: 1\n"
            "                tree_size: 1\n"
            "                allow_termwise_eval: 1\n"
            "            }\n"
@@ -718,6 +720,7 @@ getExpectedSlimeBlueprint() {
            "        '[type]': 'HitEstimate',"
            "        empty: false,"
            "        estHits: 9,"
+           "        cost_tier: 1,"
            "        tree_size: 2,"
            "        allow_termwise_eval: 0"
            "    },"
@@ -741,6 +744,7 @@ getExpectedSlimeBlueprint() {
            "                '[type]': 'HitEstimate',"
            "                empty: false,"
            "                estHits: 9,"
+           "                cost_tier: 1,"
            "                tree_size: 1,"
            "                allow_termwise_eval: 1"
            "            },"
diff --git a/searchlib/src/tests/queryeval/blueprint/intermediate_blueprints_test.cpp b/searchlib/src/tests/queryeval/blueprint/intermediate_blueprints_test.cpp
index eaab732d970..9be238edba9 100644
--- a/searchlib/src/tests/queryeval/blueprint/intermediate_blueprints_test.cpp
+++ b/searchlib/src/tests/queryeval/blueprint/intermediate_blueprints_test.cpp
@@ -1335,4 +1335,65 @@ TEST("require that ANDNOT without children is optimized to empty search") {
     EXPECT_EQUAL(expect_up->asString(), top_up->asString());
 }
 
+TEST("require that highest cost tier sorts last for OR") {
+    //-------------------------------------------------------------------------
+    Blueprint::UP top_up(
+            ap((new OrBlueprint())->
+               addChild(ap(MyLeafSpec(50).cost_tier(1).create())).
+               addChild(ap(MyLeafSpec(30).cost_tier(3).create())).
+               addChild(ap(MyLeafSpec(20).cost_tier(2).create())).
+               addChild(ap(MyLeafSpec(10).cost_tier(1).create()))));
+    //-------------------------------------------------------------------------
+    Blueprint::UP expect_up(
+            ap((new OrBlueprint())->
+               addChild(ap(MyLeafSpec(50).cost_tier(1).create())).
+               addChild(ap(MyLeafSpec(10).cost_tier(1).create())).
+               addChild(ap(MyLeafSpec(20).cost_tier(2).create())).
+               addChild(ap(MyLeafSpec(30).cost_tier(3).create()))));
+    //-------------------------------------------------------------------------
+    EXPECT_NOT_EQUAL(expect_up->asString(), top_up->asString());
+    top_up = Blueprint::optimize(std::move(top_up));
+    EXPECT_EQUAL(expect_up->asString(), top_up->asString());
+    expect_up = Blueprint::optimize(std::move(expect_up));
+    EXPECT_EQUAL(expect_up->asString(), top_up->asString());
+}
+
+TEST("require that highest cost tier sorts last for AND") {
+    //-------------------------------------------------------------------------
+    Blueprint::UP top_up(
+            ap((new AndBlueprint())->
+               addChild(ap(MyLeafSpec(10).cost_tier(1).create())).
+               addChild(ap(MyLeafSpec(20).cost_tier(3).create())).
+               addChild(ap(MyLeafSpec(30).cost_tier(2).create())).
+               addChild(ap(MyLeafSpec(50).cost_tier(1).create()))));
+    //-------------------------------------------------------------------------
+    Blueprint::UP expect_up(
+            ap((new AndBlueprint())->
+               addChild(ap(MyLeafSpec(10).cost_tier(1).create())).
+               addChild(ap(MyLeafSpec(50).cost_tier(1).create())).
+               addChild(ap(MyLeafSpec(30).cost_tier(2).create())).
+               addChild(ap(MyLeafSpec(20).cost_tier(3).create()))));
+    //-------------------------------------------------------------------------
+    EXPECT_NOT_EQUAL(expect_up->asString(), top_up->asString());
+    top_up = Blueprint::optimize(std::move(top_up));
+    EXPECT_EQUAL(expect_up->asString(), top_up->asString());
+    expect_up = Blueprint::optimize(std::move(expect_up));
+    EXPECT_EQUAL(expect_up->asString(), top_up->asString());
+}
+
+TEST("require that intermediate cost tier is minimum cost tier of children") {
+    Blueprint::UP bp1(
+            ap((new AndBlueprint())->
+               addChild(ap(MyLeafSpec(10).cost_tier(1).create())).
+               addChild(ap(MyLeafSpec(20).cost_tier(2).create())).
+               addChild(ap(MyLeafSpec(30).cost_tier(3).create()))));
+    Blueprint::UP bp2(
+            ap((new AndBlueprint())->
+               addChild(ap(MyLeafSpec(10).cost_tier(3).create())).
+               addChild(ap(MyLeafSpec(20).cost_tier(2).create())).
+               addChild(ap(MyLeafSpec(30).cost_tier(2).create()))));
+    EXPECT_EQUAL(bp1->getState().cost_tier(), 1u);
+    EXPECT_EQUAL(bp2->getState().cost_tier(), 2u);
+}
+
 TEST_MAIN() { TEST_DEBUG("lhs.out", "rhs.out"); TEST_RUN_ALL(); }
diff --git a/searchlib/src/tests/queryeval/blueprint/mysearch.h b/searchlib/src/tests/queryeval/blueprint/mysearch.h
index c47014e1e77..dbd73b6f40e 100644
--- a/searchlib/src/tests/queryeval/blueprint/mysearch.h
+++ b/searchlib/src/tests/queryeval/blueprint/mysearch.h
@@ -2,6 +2,7 @@
 #include <vespa/searchlib/queryeval/blueprint.h>
 #include <vespa/searchlib/queryeval/multisearch.h>
 #include <vespa/vespalib/objects/visit.hpp>
+#include <cassert>
 
 namespace search::queryeval {
 
@@ -124,6 +125,11 @@ public:
         setEstimate(HitEstimate(hits, empty));
         return *this;
     }
+
+    MyLeaf &cost_tier(uint32_t value) {
+        set_cost_tier(value);
+        return *this;
+    }
 };
 
 //-----------------------------------------------------------------------------
@@ -133,18 +139,27 @@ class MyLeafSpec
 private:
     FieldSpecBaseList      _fields;
     Blueprint::HitEstimate _estimate;
+    uint32_t               _cost_tier;
 
 public:
     explicit MyLeafSpec(uint32_t estHits, bool empty = false)
-        : _fields(), _estimate(estHits, empty) {}
+        : _fields(), _estimate(estHits, empty), _cost_tier(0) {}
 
     MyLeafSpec &addField(uint32_t fieldId, uint32_t handle) {
         _fields.add(FieldSpecBase(fieldId, handle));
         return *this;
     }
+    MyLeafSpec &cost_tier(uint32_t value) {
+        assert(value > 0);
+        _cost_tier = value;
+        return *this;
+    }
     MyLeaf *create() const {
         MyLeaf *leaf = new MyLeaf(_fields);
         leaf->estimate(_estimate.estHits, _estimate.empty);
+        if (_cost_tier > 0) {
+            leaf->cost_tier(_cost_tier);
+        }
         return leaf;
     }
 };
diff --git a/searchlib/src/tests/queryeval/parallel_weak_and/parallel_weak_and_test.cpp b/searchlib/src/tests/queryeval/parallel_weak_and/parallel_weak_and_test.cpp
index 0de450bdff7..607e6100f90 100644
--- a/searchlib/src/tests/queryeval/parallel_weak_and/parallel_weak_and_test.cpp
+++ b/searchlib/src/tests/queryeval/parallel_weak_and/parallel_weak_and_test.cpp
@@ -591,6 +591,7 @@ TEST_F("require that asString() on blueprint works", BlueprintAsStringFixture)
                               "    estimate: HitEstimate {\n"
                               "        empty: false\n"
                               "        estHits: 2\n"
+                              "        cost_tier: 1\n"
                               "        tree_size: 2\n"
                               "        allow_termwise_eval: 0\n"
                               "    }\n"
@@ -612,6 +613,7 @@ TEST_F("require that asString() on blueprint works", BlueprintAsStringFixture)
                               "            estimate: HitEstimate {\n"
                               "                empty: false\n"
                               "                estHits: 2\n"
+                              "                cost_tier: 1\n"
                               "                tree_size: 1\n"
                               "                allow_termwise_eval: 1\n"
                               "            }\n"
diff --git a/searchlib/src/vespa/searchlib/queryeval/blueprint.cpp b/searchlib/src/vespa/searchlib/queryeval/blueprint.cpp
index 3f3b4a2300e..b0f8245f488 100644
--- a/searchlib/src/vespa/searchlib/queryeval/blueprint.cpp
+++ b/searchlib/src/vespa/searchlib/queryeval/blueprint.cpp
@@ -66,6 +66,7 @@ Blueprint::min(const std::vector<HitEstimate> &data)
 Blueprint::State::State(const FieldSpecBaseList &fields_in)
     : _fields(fields_in),
       _estimate(),
+      _cost_tier(COST_TIER_NORMAL),
       _tree_size(1),
       _allow_termwise_eval(true)
 {
@@ -154,6 +155,7 @@ Blueprint::visitMembers(vespalib::ObjectVisitor &visitor) const
     visitor.openStruct("estimate", "HitEstimate");
     visitor.visitBool("empty", state.estimate().empty);
     visitor.visitInt("estHits", state.estimate().estHits);
+    visitor.visitInt("cost_tier", state.cost_tier());
     visitor.visitInt("tree_size", state.tree_size());
     visitor.visitInt("allow_termwise_eval", state.allow_termwise_eval());
     visitor.closeStruct();
@@ -168,7 +170,7 @@ namespace blueprint {
 void
 StateCache::updateState() const
 {
-    calculateState().swap(_state);
+    _state = calculateState();
     _stale = false;
 }
 
@@ -205,6 +207,16 @@ IntermediateBlueprint::calculateEstimate() const
 }
 
 uint32_t
+IntermediateBlueprint::calculate_cost_tier() const
+{
+    uint32_t cost_tier = State::COST_TIER_MAX;
+    for (const Blueprint * child : _children) {
+        cost_tier = std::min(cost_tier, child->getState().cost_tier());
+    }
+    return cost_tier;
+}
+
+uint32_t
 IntermediateBlueprint::calculate_tree_size() const
 {
     uint32_t nodes = 1;
@@ -290,6 +302,7 @@ IntermediateBlueprint::calculateState() const
 {
     State state(exposeFields());
     state.estimate(calculateEstimate());
+    state.cost_tier(calculate_cost_tier());
     state.allow_termwise_eval(infer_allow_termwise_eval());
     state.tree_size(calculate_tree_size());
     return state;
@@ -517,6 +530,13 @@ LeafBlueprint::setEstimate(HitEstimate est)
 }
 
 void
+LeafBlueprint::set_cost_tier(uint32_t value)
+{
+    _state.cost_tier(value);
+    notifyChange();
+}
+
+void
 LeafBlueprint::set_allow_termwise_eval(bool value)
 {
     _state.allow_termwise_eval(value);
diff --git a/searchlib/src/vespa/searchlib/queryeval/blueprint.h b/searchlib/src/vespa/searchlib/queryeval/blueprint.h
index 8e828157c70..2f9dbabe52e 100644
--- a/searchlib/src/vespa/searchlib/queryeval/blueprint.h
+++ b/searchlib/src/vespa/searchlib/queryeval/blueprint.h
@@ -57,18 +57,21 @@ public:
     private:
         FieldSpecBaseList _fields;
         HitEstimate       _estimate;
+        uint32_t          _cost_tier;
         uint32_t          _tree_size;
         bool              _allow_termwise_eval;
 
     public:
+        static constexpr uint32_t COST_TIER_NORMAL = 1;
+        static constexpr uint32_t COST_TIER_EXPENSIVE = 2;
+        static constexpr uint32_t COST_TIER_MAX = 999;
+
         State(const FieldSpecBaseList &fields_in);
+        State(const State &rhs) = delete;
+        State(State &&rhs) = default;
+        State &operator=(const State &rhs) = delete;
+        State &operator=(State &&rhs) = default;
         ~State();
-        void swap(State & rhs) {
-            _fields.swap(rhs._fields);
-            std::swap(_estimate, rhs._estimate);
-            std::swap(_tree_size, rhs._tree_size);
-            std::swap(_allow_termwise_eval, rhs._allow_termwise_eval);
-        }
 
         bool isTermLike() const { return !_fields.empty(); }
         const FieldSpecBaseList &fields() const { return _fields; }
@@ -95,6 +98,8 @@ public:
         uint32_t tree_size() const { return _tree_size; }
         void allow_termwise_eval(bool value) { _allow_termwise_eval = value; }
         bool allow_termwise_eval() const { return _allow_termwise_eval; }
+        void cost_tier(uint32_t value) { _cost_tier = value; }
+        uint32_t cost_tier() const { return _cost_tier; }
     };
 
     // utility that just takes maximum estimate
@@ -103,17 +108,27 @@ public:
     // utility that just takes minium estimate
     static HitEstimate min(const std::vector<HitEstimate> &data);
 
-    // utility to get the greater estimate to sort first
-    struct GreaterEstimate {
+    // utility to get the greater estimate to sort first, higher tiers last
+    struct TieredGreaterEstimate {
         bool operator () (Blueprint * const &a, Blueprint * const &b) const {
-            return (b->getState().estimate() < a->getState().estimate());
+            const auto &lhs = a->getState();
+            const auto &rhs = b->getState();
+            if (lhs.cost_tier() != rhs.cost_tier()) {
+                return (lhs.cost_tier() < rhs.cost_tier());
+            }
+            return (rhs.estimate() < lhs.estimate());
         }
     };
 
-    // utility to get the lesser estimate to sort first
-    struct LessEstimate {
+    // utility to get the lesser estimate to sort first, higher tiers last
+    struct TieredLessEstimate {
         bool operator () (Blueprint * const &a, const Blueprint * const &b) const {
-            return (a->getState().estimate() < b->getState().estimate());
+            const auto &lhs = a->getState();
+            const auto &rhs = b->getState();
+            if (lhs.cost_tier() != rhs.cost_tier()) {
+                return (lhs.cost_tier() < rhs.cost_tier());
+            }
+            return (lhs.estimate() < rhs.estimate());
         }
     };
 
@@ -226,6 +241,7 @@ public:
 private:
     Children _children;
     HitEstimate calculateEstimate() const;
+    uint32_t calculate_cost_tier() const;
     uint32_t calculate_tree_size() const;
     bool infer_allow_termwise_eval() const;
 
@@ -285,6 +301,7 @@ private:
 protected:
     void optimize(Blueprint* &self) override final;
     void setEstimate(HitEstimate est);
+    void set_cost_tier(uint32_t value);
     void set_allow_termwise_eval(bool value);
     void set_tree_size(uint32_t value);
 
diff --git a/searchlib/src/vespa/searchlib/queryeval/intermediate_blueprints.cpp b/searchlib/src/vespa/searchlib/queryeval/intermediate_blueprints.cpp
index bf7b659dea7..c24eb29a318 100644
--- a/searchlib/src/vespa/searchlib/queryeval/intermediate_blueprints.cpp
+++ b/searchlib/src/vespa/searchlib/queryeval/intermediate_blueprints.cpp
@@ -138,7 +138,7 @@ void
 AndNotBlueprint::sort(std::vector<Blueprint*> &children) const
 {
     if (children.size() > 2) {
-        std::sort(children.begin() + 1, children.end(), GreaterEstimate());
+        std::sort(children.begin() + 1, children.end(), TieredGreaterEstimate());
     }
 }
 
@@ -211,7 +211,7 @@ AndBlueprint::get_replacement()
 void
 AndBlueprint::sort(std::vector<Blueprint*> &children) const
 {
-    std::sort(children.begin(), children.end(), LessEstimate());
+    std::sort(children.begin(), children.end(), TieredLessEstimate());
 }
 
 bool
@@ -288,7 +288,7 @@ OrBlueprint::get_replacement()
 void
 OrBlueprint::sort(std::vector<Blueprint*> &children) const
 {
-    std::sort(children.begin(), children.end(), GreaterEstimate());
+    std::sort(children.begin(), children.end(), TieredGreaterEstimate());
 }
 
 bool
@@ -379,7 +379,7 @@ NearBlueprint::exposeFields() const
 void
 NearBlueprint::sort(std::vector<Blueprint*> &children) const
 {
-    std::sort(children.begin(), children.end(), LessEstimate());
+    std::sort(children.begin(), children.end(), TieredLessEstimate());
 }
 
 bool