diff options
13 files changed, 157 insertions, 105 deletions
diff --git a/searchcore/src/vespa/searchcore/proton/matching/match_tools.cpp b/searchcore/src/vespa/searchcore/proton/matching/match_tools.cpp index b5224281724..565604826ee 100644 --- a/searchcore/src/vespa/searchcore/proton/matching/match_tools.cpp +++ b/searchcore/src/vespa/searchcore/proton/matching/match_tools.cpp @@ -203,7 +203,8 @@ MatchToolsFactory(QueryLimiter & queryLimiter, trace.addEvent(5, "Build query execution plan"); _query.reserveHandles(_requestContext, searchContext, _mdl); trace.addEvent(5, "Optimize query execution plan"); - _query.optimize(SortBlueprintsByCost::check(_queryEnv.getProperties(), rankSetup.sort_blueprints_by_cost())); + bool sort_by_cost = SortBlueprintsByCost::check(_queryEnv.getProperties(), rankSetup.sort_blueprints_by_cost()); + _query.optimize(sort_by_cost); trace.addEvent(4, "Perform dictionary lookups and posting lists initialization"); double hitRate = std::min(1.0, double(maxNumHits)/double(searchContext.getDocIdLimit())); bool create_postinglist_when_non_strict = CreatePostingListWhenNonStrict::check(_queryEnv.getProperties(), rankSetup.create_postinglist_when_non_strict()); @@ -216,7 +217,8 @@ MatchToolsFactory(QueryLimiter & queryLimiter, _query.handle_global_filter(_requestContext, searchContext.getDocIdLimit(), _attribute_blueprint_params.global_filter_lower_limit, _attribute_blueprint_params.global_filter_upper_limit, - trace, create_postinglist_when_non_strict, use_estimate_for_fetch_postings); + trace, create_postinglist_when_non_strict, use_estimate_for_fetch_postings, + sort_by_cost); } _query.freeze(); trace.addEvent(5, "Prepare shared state for multi-threaded rank executors"); diff --git a/searchcore/src/vespa/searchcore/proton/matching/query.cpp b/searchcore/src/vespa/searchcore/proton/matching/query.cpp index 149828b0a91..dfa1bd91157 100644 --- a/searchcore/src/vespa/searchcore/proton/matching/query.cpp +++ b/searchcore/src/vespa/searchcore/proton/matching/query.cpp @@ -201,7 +201,7 @@ void Query::optimize(bool sort_by_cost) { (void) sort_by_cost; - _blueprint = Blueprint::optimize(std::move(_blueprint)); + _blueprint = Blueprint::optimize(std::move(_blueprint), sort_by_cost); LOG(debug, "optimized blueprint:\n%s\n", _blueprint->asString().c_str()); } @@ -215,7 +215,8 @@ void Query::handle_global_filter(const IRequestContext & requestContext, uint32_t docid_limit, double global_filter_lower_limit, double global_filter_upper_limit, search::engine::Trace& trace, - bool create_postinglist_when_non_strict, bool use_estimate_for_fetch_postings) + bool create_postinglist_when_non_strict, bool use_estimate_for_fetch_postings, + bool sort_by_cost) { if (!handle_global_filter(*_blueprint, docid_limit, global_filter_lower_limit, global_filter_upper_limit, requestContext.thread_bundle(), &trace)) @@ -224,7 +225,7 @@ Query::handle_global_filter(const IRequestContext & requestContext, uint32_t doc } // optimized order may change after accounting for global filter: trace.addEvent(5, "Optimize query execution plan to account for global filter"); - _blueprint = Blueprint::optimize(std::move(_blueprint)); + _blueprint = Blueprint::optimize(std::move(_blueprint), sort_by_cost); LOG(debug, "blueprint after handle_global_filter:\n%s\n", _blueprint->asString().c_str()); // strictness may change if optimized order changed: fetchPostings(ExecuteInfo::create(true, 1.0, requestContext.getDoom(), requestContext.thread_bundle(), diff --git a/searchcore/src/vespa/searchcore/proton/matching/query.h b/searchcore/src/vespa/searchcore/proton/matching/query.h index 8062f12b70d..b468b4b8f33 100644 --- a/searchcore/src/vespa/searchcore/proton/matching/query.h +++ b/searchcore/src/vespa/searchcore/proton/matching/query.h @@ -109,7 +109,8 @@ public: void handle_global_filter(const IRequestContext & requestContext, uint32_t docid_limit, double global_filter_lower_limit, double global_filter_upper_limit, search::engine::Trace& trace, - bool create_postinglist_when_non_strict, bool use_estimate_for_fetch_postings); + bool create_postinglist_when_non_strict, bool use_estimate_for_fetch_postings, + bool sort_by_cost); /** * Calculates and handles the global filter if needed by the blueprint tree. diff --git a/searchlib/src/tests/queryeval/blueprint/blueprint_test.cpp b/searchlib/src/tests/queryeval/blueprint/blueprint_test.cpp index eefca5c82e9..f800e124bdc 100644 --- a/searchlib/src/tests/queryeval/blueprint/blueprint_test.cpp +++ b/searchlib/src/tests/queryeval/blueprint/blueprint_test.cpp @@ -1,6 +1,7 @@ // Copyright Vespa.ai. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. #include "mysearch.h" #include <vespa/vespalib/testkit/testapp.h> +#include <vespa/searchlib/queryeval/flow.h> #include <vespa/searchlib/queryeval/blueprint.h> #include <vespa/searchlib/queryeval/intermediate_blueprints.h> #include <vespa/vespalib/objects/objectdumper.h> @@ -22,8 +23,12 @@ class MyOr : public IntermediateBlueprint { private: public: - double calculate_cost() const final { return 1.0; } - double calculate_relative_estimate() const final { return 0.5; } + double calculate_cost() const final { + return cost_of(get_children(), OrFlow()); + } + double calculate_relative_estimate() const final { + return estimate_of(get_children(), OrFlow()); + } HitEstimate combine(const std::vector<HitEstimate> &data) const override { return max(data); } @@ -32,7 +37,7 @@ public: return mixChildrenFields(); } - void sort(Children &children) const override { + void sort(Children &children, bool) const override { std::sort(children.begin(), children.end(), TieredGreaterEstimate()); } @@ -440,7 +445,8 @@ TEST_F("testChildAndNotCollapsing", Fixture) ) ); TEST_DO(f.check_not_equal(*sorted, *unsorted)); - unsorted = Blueprint::optimize(std::move(unsorted)); + unsorted->setDocIdLimit(1000); + unsorted = Blueprint::optimize(std::move(unsorted), true); TEST_DO(f.check_equal(*sorted, *unsorted)); } @@ -479,7 +485,8 @@ TEST_F("testChildAndCollapsing", Fixture) ); TEST_DO(f.check_not_equal(*sorted, *unsorted)); - unsorted = Blueprint::optimize(std::move(unsorted)); + unsorted->setDocIdLimit(1000); + unsorted = Blueprint::optimize(std::move(unsorted), true); TEST_DO(f.check_equal(*sorted, *unsorted)); } @@ -517,7 +524,8 @@ TEST_F("testChildOrCollapsing", Fixture) .add(MyLeafSpec(1).addField(2, 42).create()) ); TEST_DO(f.check_not_equal(*sorted, *unsorted)); - unsorted = Blueprint::optimize(std::move(unsorted)); + unsorted->setDocIdLimit(1000); + unsorted = Blueprint::optimize(std::move(unsorted), true); TEST_DO(f.check_equal(*sorted, *unsorted)); } @@ -560,7 +568,8 @@ TEST_F("testChildSorting", Fixture) ); TEST_DO(f.check_not_equal(*sorted, *unsorted)); - unsorted = Blueprint::optimize(std::move(unsorted)); + unsorted->setDocIdLimit(1000); + unsorted = Blueprint::optimize(std::move(unsorted), true); TEST_DO(f.check_equal(*sorted, *unsorted)); } diff --git a/searchlib/src/tests/queryeval/blueprint/intermediate_blueprints_test.cpp b/searchlib/src/tests/queryeval/blueprint/intermediate_blueprints_test.cpp index 234ff5a9d19..ab1c004c721 100644 --- a/searchlib/src/tests/queryeval/blueprint/intermediate_blueprints_test.cpp +++ b/searchlib/src/tests/queryeval/blueprint/intermediate_blueprints_test.cpp @@ -15,6 +15,7 @@ #include <vespa/searchlib/query/tree/simplequery.h> #include <vespa/searchlib/common/bitvectoriterator.h> #include <vespa/vespalib/util/overload.h> +#include <vespa/vespalib/util/approx.h> #include <vespa/vespalib/data/simple_buffer.h> #include <vespa/vespalib/data/slime/slime.h> #include <vespa/vespalib/data/slime/inserter.h> @@ -75,7 +76,8 @@ void check_sort_order(IntermediateBlueprint &self, BlueprintVector children, std for (const auto & child: children) { unordered.push_back(child.get()); } - self.sort(children); + // TODO: sort by cost (requires both setDocIdLimit and optimize to be called) + self.sort(children, false); for (size_t i = 0; i < children.size(); ++i) { EXPECT_EQUAL(children[i].get(), unordered[order[i]]); } @@ -129,7 +131,7 @@ TEST("test AndNot Blueprint") { template <typename BP> void optimize(std::unique_ptr<BP> &ref) { - auto optimized = Blueprint::optimize(std::move(ref)); + auto optimized = Blueprint::optimize(std::move(ref), true); ref.reset(dynamic_cast<BP*>(optimized.get())); ASSERT_TRUE(ref); optimized.release(); @@ -141,8 +143,8 @@ TEST("test And propagates updated histestimate") { bp->addChild(ap(MyLeafSpec(20).create<RememberExecuteInfo>()->setSourceId(2))); bp->addChild(ap(MyLeafSpec(200).create<RememberExecuteInfo>()->setSourceId(2))); bp->addChild(ap(MyLeafSpec(2000).create<RememberExecuteInfo>()->setSourceId(2))); - optimize(bp); bp->setDocIdLimit(5000); + optimize(bp); bp->fetchPostings(ExecuteInfo::TRUE); EXPECT_EQUAL(3u, bp->childCnt()); for (uint32_t i = 0; i < bp->childCnt(); i++) { @@ -161,8 +163,8 @@ TEST("test Or propagates updated histestimate") { bp->addChild(ap(MyLeafSpec(2000).create<RememberExecuteInfo>()->setSourceId(2))); bp->addChild(ap(MyLeafSpec(800).create<RememberExecuteInfo>()->setSourceId(2))); bp->addChild(ap(MyLeafSpec(20).create<RememberExecuteInfo>()->setSourceId(2))); - optimize(bp); bp->setDocIdLimit(5000); + optimize(bp); bp->fetchPostings(ExecuteInfo::TRUE); EXPECT_EQUAL(4u, bp->childCnt()); for (uint32_t i = 0; i < bp->childCnt(); i++) { @@ -514,36 +516,45 @@ vespalib::string to_str(const Inspector &value) { } void compare(const Blueprint &bp1, const Blueprint &bp2, bool expect_eq) { - auto ignore_cost = [expect_eq](const auto &path, const auto &a, const auto &b) { - if (!path.empty() && std::holds_alternative<vespalib::stringref>(path.back())) { - vespalib::stringref field = std::get<vespalib::stringref>(path.back()); - if (field == "cost") { - return true; - } - } - if (expect_eq) { - fprintf(stderr, " mismatch at %s: %s vs %s\n", path_to_str(path).c_str(), - to_str(a).c_str(), to_str(b).c_str()); - } - return false; - }; + auto cmp_hook = [expect_eq](const auto &path, const auto &a, const auto &b) { + if (!path.empty() && std::holds_alternative<vespalib::stringref>(path.back())) { + vespalib::stringref field = std::get<vespalib::stringref>(path.back()); + if (field == "cost") { + return true; + } + if (field == "relative_estimate") { + double a_val = a.asDouble(); + double b_val = b.asDouble(); + if (a_val != 0.0 && b_val != 0.0 && vespalib::approx_equal(a_val, b_val)) { + return true; + } + } + } + if (expect_eq) { + fprintf(stderr, " mismatch at %s: %s vs %s\n", path_to_str(path).c_str(), + to_str(a).c_str(), to_str(b).c_str()); + } + return false; + }; Slime a; Slime b; bp1.asSlime(SlimeInserter(a)); bp2.asSlime(SlimeInserter(b)); if (expect_eq) { - EXPECT_TRUE(vespalib::slime::are_equal(a.get(), b.get(), ignore_cost)); + EXPECT_TRUE(vespalib::slime::are_equal(a.get(), b.get(), cmp_hook)); } else { - EXPECT_FALSE(vespalib::slime::are_equal(a.get(), b.get(), ignore_cost)); + EXPECT_FALSE(vespalib::slime::are_equal(a.get(), b.get(), cmp_hook)); } } void -optimize_and_compare(Blueprint::UP top, Blueprint::UP expect) { +optimize_and_compare(Blueprint::UP top, Blueprint::UP expect, bool sort_by_cost = true) { + top->setDocIdLimit(1000); + expect->setDocIdLimit(1000); TEST_DO(compare(*top, *expect, false)); - top = Blueprint::optimize(std::move(top)); + top = Blueprint::optimize(std::move(top), sort_by_cost); TEST_DO(compare(*top, *expect, true)); - expect = Blueprint::optimize(std::move(expect)); + expect = Blueprint::optimize(std::move(expect), sort_by_cost); TEST_DO(compare(*expect, *top, true)); } @@ -670,11 +681,11 @@ TEST("test empty root node optimization and safeness") { //------------------------------------------------------------------------- auto expect_up = std::make_unique<EmptyBlueprint>(); - EXPECT_EQUAL(expect_up->asString(), Blueprint::optimize(std::move(top1))->asString()); - EXPECT_EQUAL(expect_up->asString(), Blueprint::optimize(std::move(top2))->asString()); - EXPECT_EQUAL(expect_up->asString(), Blueprint::optimize(std::move(top3))->asString()); - EXPECT_EQUAL(expect_up->asString(), Blueprint::optimize(std::move(top4))->asString()); - EXPECT_EQUAL(expect_up->asString(), Blueprint::optimize(std::move(top5))->asString()); + EXPECT_EQUAL(expect_up->asString(), Blueprint::optimize(std::move(top1), true)->asString()); + EXPECT_EQUAL(expect_up->asString(), Blueprint::optimize(std::move(top2), true)->asString()); + EXPECT_EQUAL(expect_up->asString(), Blueprint::optimize(std::move(top3), true)->asString()); + EXPECT_EQUAL(expect_up->asString(), Blueprint::optimize(std::move(top4), true)->asString()); + EXPECT_EQUAL(expect_up->asString(), Blueprint::optimize(std::move(top5), true)->asString()); } TEST("and with one empty child is optimized away") { @@ -682,7 +693,7 @@ TEST("and with one empty child is optimized away") { Blueprint::UP top = ap((new SourceBlenderBlueprint(*selector))-> addChild(ap(MyLeafSpec(10).create())). addChild(addLeafs(std::make_unique<AndBlueprint>(), {{0, true}, 10, 20}))); - top = Blueprint::optimize(std::move(top)); + top = Blueprint::optimize(std::move(top), true); Blueprint::UP expect_up(ap((new SourceBlenderBlueprint(*selector))-> addChild(ap(MyLeafSpec(10).create())). addChild(std::make_unique<EmptyBlueprint>()))); @@ -857,8 +868,8 @@ TEST("require that replaced blueprints retain source id") { addChild(ap(MyLeafSpec(30).create()->setSourceId(55))))); Blueprint::UP expect2_up(ap(MyLeafSpec(30).create()->setSourceId(42))); //------------------------------------------------------------------------- - top1_up = Blueprint::optimize(std::move(top1_up)); - top2_up = Blueprint::optimize(std::move(top2_up)); + top1_up = Blueprint::optimize(std::move(top1_up), true); + top2_up = Blueprint::optimize(std::move(top2_up), true); EXPECT_EQUAL(expect1_up->asString(), top1_up->asString()); EXPECT_EQUAL(expect2_up->asString(), top2_up->asString()); EXPECT_EQUAL(13u, top1_up->getSourceId()); @@ -1177,7 +1188,7 @@ TEST("require that children of near are not optimized") { auto expect_up = ap((new NearBlueprint(10))-> addChild(addLeafs(std::make_unique<OrBlueprint>(), {20, {0, true}})). addChild(addLeafs(std::make_unique<OrBlueprint>(), {{0, true}, 30}))); - top_up = Blueprint::optimize(std::move(top_up)); + top_up = Blueprint::optimize(std::move(top_up), true); TEST_DO(compare(*top_up, *expect_up, true)); } @@ -1188,27 +1199,27 @@ TEST("require that children of onear are not optimized") { auto expect_up = ap((new ONearBlueprint(10))-> addChild(addLeafs(std::make_unique<OrBlueprint>(), {20, {0, true}})). addChild(addLeafs(std::make_unique<OrBlueprint>(), {{0, true}, 30}))); - top_up = Blueprint::optimize(std::move(top_up)); + top_up = Blueprint::optimize(std::move(top_up), true); TEST_DO(compare(*top_up, *expect_up, true)); } TEST("require that ANDNOT without children is optimized to empty search") { Blueprint::UP top_up = std::make_unique<AndNotBlueprint>(); auto expect_up = std::make_unique<EmptyBlueprint>(); - top_up = Blueprint::optimize(std::move(top_up)); + top_up = Blueprint::optimize(std::move(top_up), true); EXPECT_EQUAL(expect_up->asString(), top_up->asString()); } TEST("require that highest cost tier sorts last for OR") { Blueprint::UP top = addLeafsWithCostTier(std::make_unique<OrBlueprint>(), {{50, 1}, {30, 3}, {20, 2}, {10, 1}}); Blueprint::UP expect = addLeafsWithCostTier(std::make_unique<OrBlueprint>(), {{50, 1}, {10, 1}, {20, 2}, {30, 3}}); - optimize_and_compare(std::move(top), std::move(expect)); + optimize_and_compare(std::move(top), std::move(expect), false); } TEST("require that highest cost tier sorts last for AND") { Blueprint::UP top = addLeafsWithCostTier(std::make_unique<AndBlueprint>(), {{10, 1}, {20, 3}, {30, 2}, {50, 1}}); Blueprint::UP expect = addLeafsWithCostTier(std::make_unique<AndBlueprint>(), {{10, 1}, {50, 1}, {30, 2}, {20, 3}}); - optimize_and_compare(std::move(top), std::move(expect)); + optimize_and_compare(std::move(top), std::move(expect), false); } template<typename BP> @@ -1325,7 +1336,7 @@ void verify_cost(make &&mk, double expect) { .cost(1.2).leaf(300) .cost(1.3).leaf(500); bp->setDocIdLimit(1000); - bp = Blueprint::optimize(std::move(bp)); + bp = Blueprint::optimize(std::move(bp), true); EXPECT_EQUAL(bp->cost(), expect); } diff --git a/searchlib/src/tests/queryeval/filter_search/filter_search_test.cpp b/searchlib/src/tests/queryeval/filter_search/filter_search_test.cpp index f910ff5be1b..1180206279d 100644 --- a/searchlib/src/tests/queryeval/filter_search/filter_search_test.cpp +++ b/searchlib/src/tests/queryeval/filter_search/filter_search_test.cpp @@ -48,7 +48,7 @@ concept ChildCollector = requires(T a, std::unique_ptr<Blueprint> bp) { // inherit Blueprint to capture the default filter factory struct DefaultBlueprint : Blueprint { double calculate_relative_estimate() const override { abort(); } - void optimize(Blueprint* &, OptimizePass) override { abort(); } + void optimize(Blueprint* &, OptimizePass, bool) override { abort(); } const State &getState() const override { abort(); } void fetchPostings(const ExecuteInfo &) override { abort(); } void freeze() override { abort(); } diff --git a/searchlib/src/tests/queryeval/same_element/same_element_test.cpp b/searchlib/src/tests/queryeval/same_element/same_element_test.cpp index d05e6c8e4f4..7c535e5d3d5 100644 --- a/searchlib/src/tests/queryeval/same_element/same_element_test.cpp +++ b/searchlib/src/tests/queryeval/same_element/same_element_test.cpp @@ -46,7 +46,7 @@ std::unique_ptr<SameElementBlueprint> make_blueprint(const std::vector<FakeResul } Blueprint::UP finalize(Blueprint::UP bp, bool strict) { - Blueprint::UP result = Blueprint::optimize(std::move(bp)); + Blueprint::UP result = Blueprint::optimize(std::move(bp), true); result->fetchPostings(ExecuteInfo::createForTest(strict)); result->freeze(); return result; diff --git a/searchlib/src/vespa/searchlib/queryeval/blueprint.cpp b/searchlib/src/vespa/searchlib/queryeval/blueprint.cpp index 71d53ade2f7..ee383f18ea4 100644 --- a/searchlib/src/vespa/searchlib/queryeval/blueprint.cpp +++ b/searchlib/src/vespa/searchlib/queryeval/blueprint.cpp @@ -130,15 +130,15 @@ Blueprint::Blueprint() noexcept Blueprint::~Blueprint() = default; Blueprint::UP -Blueprint::optimize(Blueprint::UP bp) { +Blueprint::optimize(Blueprint::UP bp, bool sort_by_cost) { Blueprint *root = bp.release(); - root->optimize(root, OptimizePass::FIRST); - root->optimize(root, OptimizePass::LAST); + root->optimize(root, OptimizePass::FIRST, sort_by_cost); + root->optimize(root, OptimizePass::LAST, sort_by_cost); return Blueprint::UP(root); } void -Blueprint::optimize_self(OptimizePass) +Blueprint::optimize_self(OptimizePass, bool) { } @@ -549,19 +549,19 @@ IntermediateBlueprint::should_do_termwise_eval(const UnpackInfo &unpack, double } void -IntermediateBlueprint::optimize(Blueprint* &self, OptimizePass pass) +IntermediateBlueprint::optimize(Blueprint* &self, OptimizePass pass, bool sort_by_cost) { assert(self == this); if (should_optimize_children()) { for (auto &child : _children) { auto *child_ptr = child.release(); - child_ptr->optimize(child_ptr, pass); + child_ptr->optimize(child_ptr, pass, sort_by_cost); child.reset(child_ptr); } } - optimize_self(pass); + optimize_self(pass, sort_by_cost); if (pass == OptimizePass::LAST) { - sort(_children); + sort(_children, sort_by_cost); set_cost(calculate_cost()); } maybe_eliminate_self(self, get_replacement()); @@ -759,10 +759,10 @@ LeafBlueprint::getRange(vespalib::string &, vespalib::string &) const { } void -LeafBlueprint::optimize(Blueprint* &self, OptimizePass pass) +LeafBlueprint::optimize(Blueprint* &self, OptimizePass pass, bool sort_by_cost) { assert(self == this); - optimize_self(pass); + optimize_self(pass, sort_by_cost); maybe_eliminate_self(self, get_replacement()); } diff --git a/searchlib/src/vespa/searchlib/queryeval/blueprint.h b/searchlib/src/vespa/searchlib/queryeval/blueprint.h index 66d55015f62..7caeeddd01c 100644 --- a/searchlib/src/vespa/searchlib/queryeval/blueprint.h +++ b/searchlib/src/vespa/searchlib/queryeval/blueprint.h @@ -172,6 +172,20 @@ public: // lower limit for docid_limit: max child estimate static HitEstimate sat_sum(const std::vector<HitEstimate> &data, uint32_t docid_limit); + // sort children to minimize total cost of OR flow + struct MinimalOrCost { + bool operator () (const auto &a, const auto &b) const noexcept { + return a->estimate() / a->cost() > b->estimate() / b->cost(); + } + }; + + // sort children to minimize total cost of AND flow + struct MinimalAndCost { + bool operator () (const auto &a, const auto &b) const noexcept { + return (1.0 - a->estimate()) / a->cost() > (1.0 - b->estimate()) / b->cost(); + } + }; + // utility to get the greater estimate to sort first, higher tiers last struct TieredGreaterEstimate { bool operator () (const auto &a, const auto &b) const noexcept { @@ -246,9 +260,9 @@ public: virtual void setDocIdLimit(uint32_t limit) noexcept { _docid_limit = limit; } uint32_t get_docid_limit() const noexcept { return _docid_limit; } - static Blueprint::UP optimize(Blueprint::UP bp); - virtual void optimize(Blueprint* &self, OptimizePass pass) = 0; - virtual void optimize_self(OptimizePass pass); + static Blueprint::UP optimize(Blueprint::UP bp, bool sort_by_cost); + virtual void optimize(Blueprint* &self, OptimizePass pass, bool sort_by_cost) = 0; + virtual void optimize_self(OptimizePass pass, bool sort_by_cost); virtual Blueprint::UP get_replacement(); virtual bool should_optimize_children() const { return true; } @@ -376,7 +390,7 @@ public: void setDocIdLimit(uint32_t limit) noexcept final; - void optimize(Blueprint* &self, OptimizePass pass) final; + void optimize(Blueprint* &self, OptimizePass pass, bool sort_by_cost) final; void set_global_filter(const GlobalFilter &global_filter, double estimated_hit_ratio) override; IndexList find(const IPredicate & check) const; @@ -393,7 +407,7 @@ public: virtual double calculate_cost() const = 0; virtual HitEstimate combine(const std::vector<HitEstimate> &data) const = 0; virtual FieldSpecBaseList exposeFields() const = 0; - virtual void sort(Children &children) const = 0; + virtual void sort(Children &children, bool sort_by_cost) const = 0; virtual bool inheritStrict(size_t i) const = 0; virtual SearchIteratorUP createIntermediateSearch(MultiSearch::Children subSearches, @@ -413,7 +427,7 @@ class LeafBlueprint : public Blueprint private: State _state; protected: - void optimize(Blueprint* &self, OptimizePass pass) final; + void optimize(Blueprint* &self, OptimizePass pass, bool sort_by_cost) final; void setEstimate(HitEstimate est) { _state.estimate(est); _state.relative_estimate(calculate_relative_estimate()); diff --git a/searchlib/src/vespa/searchlib/queryeval/intermediate_blueprints.cpp b/searchlib/src/vespa/searchlib/queryeval/intermediate_blueprints.cpp index 364602cba03..a3f32c6eb7b 100644 --- a/searchlib/src/vespa/searchlib/queryeval/intermediate_blueprints.cpp +++ b/searchlib/src/vespa/searchlib/queryeval/intermediate_blueprints.cpp @@ -33,7 +33,7 @@ size_t lookup_create_source(std::vector<std::unique_ptr<CombineType> > &sources, } template <typename CombineType> -void optimize_source_blenders(IntermediateBlueprint &self, size_t begin_idx) { +void optimize_source_blenders(IntermediateBlueprint &self, size_t begin_idx, bool sort_by_cost) { std::vector<size_t> source_blenders; const SourceBlenderBlueprint * reference = nullptr; for (size_t i = begin_idx; i < self.childCnt(); ++i) { @@ -63,7 +63,7 @@ void optimize_source_blenders(IntermediateBlueprint &self, size_t begin_idx) { top->addChild(std::move(sources.back())); sources.pop_back(); } - blender_up = Blueprint::optimize(std::move(blender_up)); + blender_up = Blueprint::optimize(std::move(blender_up), sort_by_cost); self.addChild(std::move(blender_up)); } } @@ -114,7 +114,7 @@ AndNotBlueprint::exposeFields() const } void -AndNotBlueprint::optimize_self(OptimizePass pass) +AndNotBlueprint::optimize_self(OptimizePass pass, bool sort_by_cost) { if (childCnt() == 0) { return; @@ -152,7 +152,7 @@ AndNotBlueprint::optimize_self(OptimizePass pass) } } if (pass == OptimizePass::LAST) { - optimize_source_blenders<OrBlueprint>(*this, 1); + optimize_source_blenders<OrBlueprint>(*this, 1, sort_by_cost); } } @@ -166,10 +166,14 @@ AndNotBlueprint::get_replacement() } void -AndNotBlueprint::sort(Children &children) const +AndNotBlueprint::sort(Children &children, bool sort_by_cost) const { if (children.size() > 2) { - std::sort(children.begin() + 1, children.end(), TieredGreaterEstimate()); + if (sort_by_cost) { + std::sort(children.begin() + 1, children.end(), MinimalOrCost()); + } else { + std::sort(children.begin() + 1, children.end(), TieredGreaterEstimate()); + } } } @@ -231,7 +235,7 @@ AndBlueprint::exposeFields() const } void -AndBlueprint::optimize_self(OptimizePass pass) +AndBlueprint::optimize_self(OptimizePass pass, bool sort_by_cost) { if (pass == OptimizePass::FIRST) { for (size_t i = 0; i < childCnt(); ++i) { @@ -244,7 +248,7 @@ AndBlueprint::optimize_self(OptimizePass pass) } } if (pass == OptimizePass::LAST) { - optimize_source_blenders<AndBlueprint>(*this, 0); + optimize_source_blenders<AndBlueprint>(*this, 0, sort_by_cost); } } @@ -258,9 +262,13 @@ AndBlueprint::get_replacement() } void -AndBlueprint::sort(Children &children) const +AndBlueprint::sort(Children &children, bool sort_by_cost) const { - std::sort(children.begin(), children.end(), TieredLessEstimate()); + if (sort_by_cost) { + std::sort(children.begin(), children.end(), MinimalAndCost()); + } else { + std::sort(children.begin(), children.end(), TieredLessEstimate()); + } } bool @@ -344,7 +352,7 @@ OrBlueprint::exposeFields() const } void -OrBlueprint::optimize_self(OptimizePass pass) +OrBlueprint::optimize_self(OptimizePass pass, bool sort_by_cost) { if (pass == OptimizePass::FIRST) { for (size_t i = 0; (childCnt() > 1) && (i < childCnt()); ++i) { @@ -359,7 +367,7 @@ OrBlueprint::optimize_self(OptimizePass pass) } } if (pass == OptimizePass::LAST) { - optimize_source_blenders<OrBlueprint>(*this, 0); + optimize_source_blenders<OrBlueprint>(*this, 0, sort_by_cost); } } @@ -373,9 +381,13 @@ OrBlueprint::get_replacement() } void -OrBlueprint::sort(Children &children) const +OrBlueprint::sort(Children &children, bool sort_by_cost) const { - std::sort(children.begin(), children.end(), TieredGreaterEstimate()); + if (sort_by_cost) { + std::sort(children.begin(), children.end(), MinimalOrCost()); + } else { + std::sort(children.begin(), children.end(), TieredGreaterEstimate()); + } } bool @@ -452,7 +464,7 @@ WeakAndBlueprint::exposeFields() const } void -WeakAndBlueprint::sort(Children &) const +WeakAndBlueprint::sort(Children &, bool) const { // order needs to stay the same as _weights } @@ -516,9 +528,13 @@ NearBlueprint::exposeFields() const } void -NearBlueprint::sort(Children &children) const +NearBlueprint::sort(Children &children, bool sort_by_cost) const { - std::sort(children.begin(), children.end(), TieredLessEstimate()); + if (sort_by_cost) { + std::sort(children.begin(), children.end(), MinimalAndCost()); + } else { + std::sort(children.begin(), children.end(), TieredLessEstimate()); + } } bool @@ -579,10 +595,9 @@ ONearBlueprint::exposeFields() const } void -ONearBlueprint::sort(Children &children) const +ONearBlueprint::sort(Children &, bool) const { // ordered near cannot sort children here - (void)children; } bool @@ -648,7 +663,7 @@ RankBlueprint::exposeFields() const } void -RankBlueprint::optimize_self(OptimizePass pass) +RankBlueprint::optimize_self(OptimizePass pass, bool sort_by_cost) { if (pass == OptimizePass::FIRST) { for (size_t i = 1; i < childCnt(); ++i) { @@ -658,7 +673,7 @@ RankBlueprint::optimize_self(OptimizePass pass) } } if (pass == OptimizePass::LAST) { - optimize_source_blenders<OrBlueprint>(*this, 1); + optimize_source_blenders<OrBlueprint>(*this, 1, sort_by_cost); } } @@ -672,9 +687,8 @@ RankBlueprint::get_replacement() } void -RankBlueprint::sort(Children &children) const +RankBlueprint::sort(Children &, bool) const { - (void)children; } bool @@ -751,7 +765,7 @@ SourceBlenderBlueprint::exposeFields() const } void -SourceBlenderBlueprint::sort(Children &) const +SourceBlenderBlueprint::sort(Children &, bool) const { } diff --git a/searchlib/src/vespa/searchlib/queryeval/intermediate_blueprints.h b/searchlib/src/vespa/searchlib/queryeval/intermediate_blueprints.h index 14672c2a5cd..ff4360c0f15 100644 --- a/searchlib/src/vespa/searchlib/queryeval/intermediate_blueprints.h +++ b/searchlib/src/vespa/searchlib/queryeval/intermediate_blueprints.h @@ -19,10 +19,10 @@ public: double calculate_relative_estimate() const final; HitEstimate combine(const std::vector<HitEstimate> &data) const override; FieldSpecBaseList exposeFields() const override; - void optimize_self(OptimizePass pass) override; + void optimize_self(OptimizePass pass, bool sort_by_cost) override; AndNotBlueprint * asAndNot() noexcept final { return this; } Blueprint::UP get_replacement() override; - void sort(Children &children) const override; + void sort(Children &children, bool sort_by_cost) const override; bool inheritStrict(size_t i) const override; SearchIterator::UP createIntermediateSearch(MultiSearch::Children subSearches, @@ -47,10 +47,10 @@ public: double calculate_relative_estimate() const final; HitEstimate combine(const std::vector<HitEstimate> &data) const override; FieldSpecBaseList exposeFields() const override; - void optimize_self(OptimizePass pass) override; + void optimize_self(OptimizePass pass, bool sort_by_cost) override; AndBlueprint * asAnd() noexcept final { return this; } Blueprint::UP get_replacement() override; - void sort(Children &children) const override; + void sort(Children &children, bool sort_by_cost) const override; bool inheritStrict(size_t i) const override; SearchIterator::UP createIntermediateSearch(MultiSearch::Children subSearches, @@ -73,10 +73,10 @@ public: double calculate_relative_estimate() const final; HitEstimate combine(const std::vector<HitEstimate> &data) const override; FieldSpecBaseList exposeFields() const override; - void optimize_self(OptimizePass pass) override; + void optimize_self(OptimizePass pass, bool sort_by_cost) override; OrBlueprint * asOr() noexcept final { return this; } Blueprint::UP get_replacement() override; - void sort(Children &children) const override; + void sort(Children &children, bool sort_by_cost) const override; bool inheritStrict(size_t i) const override; SearchIterator::UP createIntermediateSearch(MultiSearch::Children subSearches, @@ -101,7 +101,7 @@ public: double calculate_relative_estimate() const final; HitEstimate combine(const std::vector<HitEstimate> &data) const override; FieldSpecBaseList exposeFields() const override; - void sort(Children &children) const override; + void sort(Children &children, bool sort_by_cost) const override; bool inheritStrict(size_t i) const override; bool always_needs_unpack() const override; WeakAndBlueprint * asWeakAnd() noexcept final { return this; } @@ -133,7 +133,7 @@ public: HitEstimate combine(const std::vector<HitEstimate> &data) const override; FieldSpecBaseList exposeFields() const override; bool should_optimize_children() const override { return false; } - void sort(Children &children) const override; + void sort(Children &children, bool sort_by_cost) const override; bool inheritStrict(size_t i) const override; SearchIteratorUP createSearch(fef::MatchData &md, bool strict) const override; SearchIterator::UP @@ -157,7 +157,7 @@ public: HitEstimate combine(const std::vector<HitEstimate> &data) const override; FieldSpecBaseList exposeFields() const override; bool should_optimize_children() const override { return false; } - void sort(Children &children) const override; + void sort(Children &children, bool sort_by_cost) const override; bool inheritStrict(size_t i) const override; SearchIteratorUP createSearch(fef::MatchData &md, bool strict) const override; SearchIterator::UP @@ -177,9 +177,9 @@ public: double calculate_relative_estimate() const final; HitEstimate combine(const std::vector<HitEstimate> &data) const override; FieldSpecBaseList exposeFields() const override; - void optimize_self(OptimizePass pass) override; + void optimize_self(OptimizePass pass, bool sort_by_cost) override; Blueprint::UP get_replacement() override; - void sort(Children &children) const override; + void sort(Children &children, bool sort_by_cost) const override; bool inheritStrict(size_t i) const override; bool isRank() const noexcept final { return true; } SearchIterator::UP @@ -206,7 +206,7 @@ public: double calculate_relative_estimate() const final; HitEstimate combine(const std::vector<HitEstimate> &data) const override; FieldSpecBaseList exposeFields() const override; - void sort(Children &children) const override; + void sort(Children &children, bool sort_by_cost) const override; bool inheritStrict(size_t i) const override; SearchIterator::UP createIntermediateSearch(MultiSearch::Children subSearches, diff --git a/searchlib/src/vespa/searchlib/queryeval/same_element_blueprint.cpp b/searchlib/src/vespa/searchlib/queryeval/same_element_blueprint.cpp index f0c75173671..bd677289218 100644 --- a/searchlib/src/vespa/searchlib/queryeval/same_element_blueprint.cpp +++ b/searchlib/src/vespa/searchlib/queryeval/same_element_blueprint.cpp @@ -45,7 +45,7 @@ SameElementBlueprint::addTerm(Blueprint::UP term) } void -SameElementBlueprint::optimize_self(OptimizePass pass) +SameElementBlueprint::optimize_self(OptimizePass pass, bool) { if (pass == OptimizePass::LAST) { std::sort(_terms.begin(), _terms.end(), diff --git a/searchlib/src/vespa/searchlib/queryeval/same_element_blueprint.h b/searchlib/src/vespa/searchlib/queryeval/same_element_blueprint.h index 6a988e67149..06c20339e81 100644 --- a/searchlib/src/vespa/searchlib/queryeval/same_element_blueprint.h +++ b/searchlib/src/vespa/searchlib/queryeval/same_element_blueprint.h @@ -34,7 +34,7 @@ public: // used by create visitor void addTerm(Blueprint::UP term); - void optimize_self(OptimizePass pass) override; + void optimize_self(OptimizePass pass, bool sort_by_cost) override; void fetchPostings(const ExecuteInfo &execInfo) override; std::unique_ptr<SameElementSearch> create_same_element_search(search::fef::TermFieldMatchData& tfmd, bool strict) const; |