diff options
Diffstat (limited to 'searchlib')
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 |