diff options
Diffstat (limited to 'searchlib')
7 files changed, 140 insertions, 38 deletions
diff --git a/searchlib/src/tests/queryeval/sparse_vector_benchmark/sparse_vector_benchmark_test.cpp b/searchlib/src/tests/queryeval/sparse_vector_benchmark/sparse_vector_benchmark_test.cpp index ae2c0cac76f..94ecd8fa539 100644 --- a/searchlib/src/tests/queryeval/sparse_vector_benchmark/sparse_vector_benchmark_test.cpp +++ b/searchlib/src/tests/queryeval/sparse_vector_benchmark/sparse_vector_benchmark_test.cpp @@ -9,7 +9,6 @@ #include <vespa/searchlib/queryeval/andnotsearch.h> #include <vespa/searchlib/queryeval/andsearch.h> #include <vespa/searchlib/queryeval/dot_product_search.h> -#include <vespa/vespalib/util/rand48.h> #include <vespa/searchlib/queryeval/orsearch.h> #include <vespa/searchlib/queryeval/simpleresult.h> #include <vespa/searchlib/queryeval/wand/weak_and_search.h> @@ -27,9 +26,9 @@ namespace { struct Writer { FILE *file; - Writer(const std::string &file_name) { + explicit Writer(const std::string &file_name) { file = fopen(file_name.c_str(), "w"); - assert(file != 0); + assert(file != nullptr); } void write(const char *data, size_t size) const { fwrite(data, 1, size, file); @@ -53,7 +52,7 @@ private: Writer _html; public: - Report(const std::string &file) : _html(file) { + explicit Report(const std::string &file) : _html(file) { _html.fmt("<html>\n"); _html.fmt("<head><title>Sparse Vector Search Benchmark Report</title></head>\n"); _html.fmt("<body>\n"); @@ -82,7 +81,7 @@ private: public: using UP = std::unique_ptr<Graph>; - Graph(const std::string &file) : _writer(file) {} + explicit Graph(const std::string &file) : _writer(file) {} void addValue(double x, double y) { _writer.fmt("%g %g\n", x, y); } }; @@ -98,8 +97,10 @@ private: public: using UP = std::unique_ptr<Plot>; - Plot(const std::string &title) : _name(vespalib::make_string("plot.%d", _plots++)), _graphs(0), - _writer(vespalib::make_string("%s.gnuplot", _name.c_str())) { + explicit Plot(const std::string &title) + : _name(vespalib::make_string("plot.%d", _plots++)), _graphs(0), + _writer(vespalib::make_string("%s.gnuplot", _name.c_str())) + { std::string png_file = vespalib::make_string("%s.png", _name.c_str()); _writer.fmt("set term png size 1200,800\n"); _writer.fmt("set output '%s'\n", png_file.c_str()); @@ -118,10 +119,10 @@ public: _writer.fmt("%s '%s' using 1:2 title '%s' w lines", (_graphs == 0) ? "plot " : ",", file.c_str(), legend.c_str()); ++_graphs; - return Graph::UP(new Graph(file)); + return std::make_unique<Graph>(file); } - static UP createPlot(const std::string &title) { return UP(new Plot(title)); } + static UP createPlot(const std::string &title) { return std::make_unique<Plot>(title); } }; int Plot::_plots = 0; @@ -137,19 +138,19 @@ struct ChildFactory { ChildFactory() {} virtual std::string name() const = 0; virtual SearchIterator::UP createChild(uint32_t idx, uint32_t limit) const = 0; - virtual ~ChildFactory() {} + virtual ~ChildFactory() = default; }; struct SparseVectorFactory { virtual std::string name() const = 0; virtual SearchIterator::UP createSparseVector(ChildFactory &childFactory, uint32_t childCnt, uint32_t limit) const = 0; - virtual ~SparseVectorFactory() {} + virtual ~SparseVectorFactory() = default; }; struct FilterStrategy { virtual std::string name() const = 0; virtual SearchIterator::UP createRoot(SparseVectorFactory &vectorFactory, ChildFactory &childFactory, uint32_t childCnt, uint32_t limit) const = 0; - virtual ~FilterStrategy() {} + virtual ~FilterStrategy() = default; }; //----------------------------------------------------------------------------- @@ -158,7 +159,7 @@ struct ModSearch : SearchIterator { uint32_t step; uint32_t limit; ModSearch(uint32_t step_in, uint32_t limit_in) : step(step_in), limit(limit_in) { setDocId(step); } - virtual void doSeek(uint32_t docid) override { + void doSeek(uint32_t docid) override { assert(docid > getDocId()); uint32_t hit = (docid / step) * step; if (hit < docid) { @@ -171,14 +172,14 @@ struct ModSearch : SearchIterator { setAtEnd(); } } - virtual void doUnpack(uint32_t) override {} + void doUnpack(uint32_t) override {} }; struct ModSearchFactory : ChildFactory { uint32_t bias; ModSearchFactory() : bias(1) {} explicit ModSearchFactory(int b) : bias(b) {} - virtual std::string name() const override { + std::string name() const override { return vespalib::make_string("ModSearch(%u)", bias); } SearchIterator::UP createChild(uint32_t idx, uint32_t limit) const override { @@ -190,14 +191,14 @@ struct ModSearchFactory : ChildFactory { struct VespaWandFactory : SparseVectorFactory { uint32_t n; - VespaWandFactory(uint32_t n_in) : n(n_in) {} - virtual std::string name() const override { + explicit VespaWandFactory(uint32_t n_in) noexcept : n(n_in) {} + std::string name() const override { return vespalib::make_string("VespaWand(%u)", n); } SearchIterator::UP createSparseVector(ChildFactory &childFactory, uint32_t childCnt, uint32_t limit) const override { wand::Terms terms; for (size_t i = 0; i < childCnt; ++i) { - terms.push_back(wand::Term(childFactory.createChild(i, limit), default_weight, limit / (i + 1))); + terms.emplace_back(childFactory.createChild(i, limit), default_weight, limit / (i + 1)); } return WeakAndSearch::create(terms, n, true); } @@ -205,16 +206,16 @@ struct VespaWandFactory : SparseVectorFactory { struct RiseWandFactory : SparseVectorFactory { uint32_t n; - RiseWandFactory(uint32_t n_in) : n(n_in) {} - virtual std::string name() const override { + explicit RiseWandFactory(uint32_t n_in) : n(n_in) {} + std::string name() const override { return vespalib::make_string("RiseWand(%u)", n); } SearchIterator::UP createSparseVector(ChildFactory &childFactory, uint32_t childCnt, uint32_t limit) const override { wand::Terms terms; for (size_t i = 0; i < childCnt; ++i) { - terms.push_back(wand::Term(childFactory.createChild(i, limit), default_weight, limit / (i + 1))); + terms.emplace_back(childFactory.createChild(i, limit), default_weight, limit / (i + 1)); } - return SearchIterator::UP(new rise::TermFrequencyRiseWand(terms, n)); + return std::make_unique<rise::TermFrequencyRiseWand>(terms, n); } }; @@ -230,7 +231,7 @@ struct WeightedSetFactory : SparseVectorFactory { tfmd.tagAsNotNeeded(); } } - virtual std::string name() const override { + std::string name() const override { return vespalib::make_string("WeightedSet%s%s", (field_is_filter ? "-filter" : ""), (tfmd.isNotNeeded() ? "-unranked" : "")); } SearchIterator::UP createSparseVector(ChildFactory &childFactory, uint32_t childCnt, uint32_t limit) const override { @@ -257,7 +258,7 @@ struct DotProductFactory : SparseVectorFactory { tfmd.tagAsNotNeeded(); } } - virtual std::string name() const override { + std::string name() const override { return vespalib::make_string("DotProduct%s%s", (field_is_filter ? "-filter" : ""), (tfmd.isNotNeeded() ? "-unranked" : "")); } SearchIterator::UP createSparseVector(ChildFactory &childFactory, uint32_t childCnt, uint32_t limit) const override { @@ -280,7 +281,7 @@ struct DotProductFactory : SparseVectorFactory { }; struct OrFactory : SparseVectorFactory { - virtual std::string name() const override { + std::string name() const override { return vespalib::make_string("Or"); } SearchIterator::UP createSparseVector(ChildFactory &childFactory, uint32_t childCnt, uint32_t limit) const override { @@ -295,7 +296,7 @@ struct OrFactory : SparseVectorFactory { //----------------------------------------------------------------------------- struct NoFilterStrategy : FilterStrategy { - virtual std::string name() const override { + std::string name() const override { return vespalib::make_string("NoFilter"); } SearchIterator::UP createRoot(SparseVectorFactory &vectorFactory, ChildFactory &childFactory, uint32_t childCnt, uint32_t limit) const override { @@ -332,8 +333,8 @@ struct NegativeFilterAfterStrategy : FilterStrategy { struct Result { vespalib::duration time; uint32_t num_hits; - Result() : time(max_time), num_hits(0) {} - Result(vespalib::duration t, uint32_t n) : time(t), num_hits(n) {} + Result() noexcept : time(max_time), num_hits(0) {} + Result(vespalib::duration t, uint32_t n) noexcept : time(t), num_hits(n) {} void combine(const Result &r) { if (time == max_time) { *this = r; @@ -357,7 +358,7 @@ Result run_single_benchmark(FilterStrategy &filterStrategy, SparseVectorFactory ++num_hits; sb.unpack(sb.getDocId()); } - return Result(timer.elapsed(), num_hits); + return {timer.elapsed(), num_hits}; } //----------------------------------------------------------------------------- @@ -384,8 +385,7 @@ public: void benchmark(SparseVectorFactory &svf, const std::vector<uint32_t> &child_counts) { Graph::UP graph = _plot->createGraph(svf.name()); fprintf(stderr, " search operator: %s\n", svf.name().c_str()); - for (size_t i = 0; i < child_counts.size(); ++i) { - uint32_t childCnt = child_counts[i]; + for (unsigned int childCnt : child_counts) { Result result; for (int j = 0; j < 5; ++j) { result.combine(run_single_benchmark(_filterStrategy, svf, _childFactory, childCnt, _limit)); diff --git a/searchlib/src/vespa/searchlib/queryeval/blueprint.cpp b/searchlib/src/vespa/searchlib/queryeval/blueprint.cpp index d11ee25a7e5..7334db4b716 100644 --- a/searchlib/src/vespa/searchlib/queryeval/blueprint.cpp +++ b/searchlib/src/vespa/searchlib/queryeval/blueprint.cpp @@ -168,6 +168,31 @@ Blueprint::null_plan(InFlow in_flow, uint32_t docid_limit) sort(in_flow); } +double +Blueprint::estimate_actual_cost(InFlow in_flow) const noexcept +{ + double res = estimate_strict_cost_diff(in_flow); + if (in_flow.strict()) { + res += strict_cost(); + } else { + res += in_flow.rate() * cost(); + } + return res; +} + +double +Blueprint::estimate_strict_cost_diff(InFlow &in_flow) const noexcept +{ + if (in_flow.strict()) { + REQUIRE(strict()); + } else if (strict()) { + double rate = in_flow.rate(); + in_flow.force_strict(); + return flow::strict_cost_diff(estimate(), rate); + } + return 0.0; +} + Blueprint::UP Blueprint::optimize(Blueprint::UP bp) { Blueprint *root = bp.release(); @@ -598,6 +623,24 @@ IntermediateBlueprint::should_do_termwise_eval(const UnpackInfo &unpack, double return (count_termwise_nodes(unpack) > 1); } +double +IntermediateBlueprint::estimate_self_cost(InFlow) const noexcept +{ + return 0.0; +} + +double +IntermediateBlueprint::estimate_actual_cost(InFlow in_flow) const noexcept +{ + double res = estimate_strict_cost_diff(in_flow); + auto cost_of = [](const auto &child, InFlow child_flow)noexcept{ + return child->estimate_actual_cost(child_flow); + }; + res += flow::actual_cost_of(flow::DefaultAdapter(), _children, my_flow(in_flow), cost_of); + res += estimate_self_cost(in_flow); + return res; +} + void IntermediateBlueprint::optimize(Blueprint* &self, OptimizePass pass) { diff --git a/searchlib/src/vespa/searchlib/queryeval/blueprint.h b/searchlib/src/vespa/searchlib/queryeval/blueprint.h index a443f34f856..a493c725407 100644 --- a/searchlib/src/vespa/searchlib/queryeval/blueprint.h +++ b/searchlib/src/vespa/searchlib/queryeval/blueprint.h @@ -313,6 +313,20 @@ public: // optimal ordering. Used for testing. void null_plan(InFlow in_flow, uint32_t docid_limit); + // Estimate the actual cost of evaluating the (sub-)query + // represented by this blueprint with the given in-flow. This + // function should be called after query planning has been + // performed. This function could be useful to predict very + // expensive queries, but the initial use-case is to understand + // query cost better in micro-benchmarks to improve low-level cost + // tuning. + virtual double estimate_actual_cost(InFlow in_flow) const noexcept; + // Estimate the change in cost caused by having a strict iterator + // with a non-strict in-flow. Note that this function might force + // the in_flow to be strict in order to align it with the + // strictness of this blueprint. + double estimate_strict_cost_diff(InFlow &in_flow) const noexcept; + static Blueprint::UP optimize(Blueprint::UP bp); virtual void sort(InFlow in_flow) = 0; static Blueprint::UP optimize_and_sort(Blueprint::UP bp, InFlow in_flow, const Options &opts) { @@ -482,6 +496,9 @@ public: void setDocIdLimit(uint32_t limit) noexcept final; void each_node_post_order(const std::function<void(Blueprint&)> &f) override; + // additional cost not attributed to the children flow (heap merge/unpack/etc) + virtual double estimate_self_cost(InFlow in_flow) const noexcept; + double estimate_actual_cost(InFlow in_flow) const noexcept override; void optimize(Blueprint* &self, OptimizePass pass) final; void sort(InFlow in_flow) override; void set_global_filter(const GlobalFilter &global_filter, double estimated_hit_ratio) override; diff --git a/searchlib/src/vespa/searchlib/queryeval/flow.h b/searchlib/src/vespa/searchlib/queryeval/flow.h index 0dc92a6cf88..be7b9031c00 100644 --- a/searchlib/src/vespa/searchlib/queryeval/flow.h +++ b/searchlib/src/vespa/searchlib/queryeval/flow.h @@ -122,9 +122,18 @@ struct MinOrCost { } }; +// The difference in cost of doing 'after' seeks instead of 'before' +// seeks against a collection of strict iterators. This formula is +// used to estimate the cost of forcing an iterator to be strict in a +// non-strict context as well as calculating the change in cost when +// changing the order of strict iterators. +inline double strict_cost_diff(double before, double after) { + return 0.2 * (after - before); +} + // estimate the cost of evaluating a strict child in a non-strict context inline double forced_strict_cost(const FlowStats &stats, double rate) { - return 0.2 * (rate - stats.estimate) + stats.strict_cost; + return stats.strict_cost + strict_cost_diff(stats.estimate, rate); } // would it be faster to force a non-strict child to be strict @@ -195,6 +204,16 @@ double ordered_cost_of(ADAPTER adapter, const T &children, F flow, bool allow_fo return total_cost; } +static double actual_cost_of(auto adapter, const auto &children, auto flow, auto cost_of) noexcept { + double total_cost = 0.0; + for (const auto &child: children) { + double child_cost = cost_of(child, InFlow(flow.strict(), flow.flow())); + flow.update_cost(total_cost, child_cost); + flow.add(adapter.estimate(child)); + } + return total_cost; +} + auto select_strict_and_child(auto adapter, const auto &children, size_t first, double est, bool native_strict) { double cost = 0.0; size_t best_idx = first; @@ -218,10 +237,10 @@ auto select_strict_and_child(auto adapter, const auto &children, size_t first, d break; } target = candidate; - my_diff += (0.2 * child.estimate - 0.2 * other.estimate); + my_diff += strict_cost_diff(other.estimate, child.estimate); if (candidate == 0 && native_strict) { // the first iterator produces its own in-flow - my_diff += (0.2 * child.estimate - 0.2 * other.estimate); + my_diff += strict_cost_diff(other.estimate, child.estimate); } // note that 'my_diff' might overestimate the cost // (underestimate the benefit) of inserting 'child' before diff --git a/searchlib/src/vespa/searchlib/queryeval/flow_tuning.h b/searchlib/src/vespa/searchlib/queryeval/flow_tuning.h index 6389de35264..cf1d1a8c09f 100644 --- a/searchlib/src/vespa/searchlib/queryeval/flow_tuning.h +++ b/searchlib/src/vespa/searchlib/queryeval/flow_tuning.h @@ -5,6 +5,7 @@ #include <vespa/searchcommon/attribute/collectiontype.h> #include <cmath> #include <cstddef> +#include "flow.h" namespace search::queryeval::flow { @@ -81,17 +82,15 @@ inline double lookup_strict_cost(size_t num_indirections) { * Estimates the cost of evaluating an always strict iterator (e.g. btree) in a non-strict context. * * When the estimate and strict cost is low, this models the cost of checking whether - * the seek docid matches the docid the iterator is already positioned at (the 0.2 factor). + * the seek docid matches the docid the iterator is already positioned at. * * The resulting non-strict cost is most accurate when the inflow is 1.0. * The resulting non-strict cost is highly underestimated when the inflow goes to 0.0. * It is important to have a better estimate at higher inflows, * as the latency (time) penalty is higher if choosing wrong. - * - * Note: This formula is equal to forced_strict_cost() in flow.h. */ inline double non_strict_cost_of_strict_iterator(double estimate, double strict_cost) { - return 0.2 * (1.0 - estimate) + strict_cost; + return strict_cost + strict_cost_diff(estimate, 1.0); } // Strict cost of matching in a btree posting list (e.g. fast-search attribute or memory index field). diff --git a/searchlib/src/vespa/searchlib/queryeval/intermediate_blueprints.cpp b/searchlib/src/vespa/searchlib/queryeval/intermediate_blueprints.cpp index 2a0f1de0e44..33b249572f0 100644 --- a/searchlib/src/vespa/searchlib/queryeval/intermediate_blueprints.cpp +++ b/searchlib/src/vespa/searchlib/queryeval/intermediate_blueprints.cpp @@ -318,6 +318,11 @@ OrBlueprint::calculate_flow_stats(uint32_t) const { OrFlow::cost_of(get_children(), true) + flow::heap_cost(est, get_children().size())}; } +double +OrBlueprint::estimate_self_cost(InFlow in_flow) const noexcept { + return in_flow.strict() ? flow::heap_cost(estimate(), get_children().size()) : 0.0; +} + Blueprint::HitEstimate OrBlueprint::combine(const std::vector<HitEstimate> &data) const { @@ -431,6 +436,11 @@ WeakAndBlueprint::calculate_flow_stats(uint32_t docid_limit) const { OrFlow::cost_of(get_children(), true) + flow::heap_cost(est, get_children().size())}; } +double +WeakAndBlueprint::estimate_self_cost(InFlow in_flow) const noexcept { + return in_flow.strict() ? flow::heap_cost(estimate(), get_children().size()) : 0.0; +} + Blueprint::HitEstimate WeakAndBlueprint::combine(const std::vector<HitEstimate> &data) const { @@ -507,6 +517,11 @@ NearBlueprint::calculate_flow_stats(uint32_t) const { AndFlow::cost_of(get_children(), true) + childCnt() * est}; } +double +NearBlueprint::estimate_self_cost(InFlow) const noexcept { + return childCnt() * estimate(); +} + Blueprint::HitEstimate NearBlueprint::combine(const std::vector<HitEstimate> &data) const { @@ -572,6 +587,11 @@ ONearBlueprint::calculate_flow_stats(uint32_t) const { AndFlow::cost_of(get_children(), true) + childCnt() * est}; } +double +ONearBlueprint::estimate_self_cost(InFlow) const noexcept { + return childCnt() * estimate(); +} + Blueprint::HitEstimate ONearBlueprint::combine(const std::vector<HitEstimate> &data) const { diff --git a/searchlib/src/vespa/searchlib/queryeval/intermediate_blueprints.h b/searchlib/src/vespa/searchlib/queryeval/intermediate_blueprints.h index dfed40f4d1b..ade4c9318e4 100644 --- a/searchlib/src/vespa/searchlib/queryeval/intermediate_blueprints.h +++ b/searchlib/src/vespa/searchlib/queryeval/intermediate_blueprints.h @@ -67,6 +67,7 @@ public: ~OrBlueprint() override; bool supports_termwise_children() const override { return true; } FlowStats calculate_flow_stats(uint32_t docid_limit) const final; + double estimate_self_cost(InFlow in_flow) const noexcept override; HitEstimate combine(const std::vector<HitEstimate> &data) const override; FieldSpecBaseList exposeFields() const override; void optimize_self(OptimizePass pass) override; @@ -94,6 +95,7 @@ private: AnyFlow my_flow(InFlow in_flow) const override; public: FlowStats calculate_flow_stats(uint32_t docid_limit) const final; + double estimate_self_cost(InFlow in_flow) const noexcept override; HitEstimate combine(const std::vector<HitEstimate> &data) const override; FieldSpecBaseList exposeFields() const override; Blueprint::UP get_replacement() override; @@ -125,6 +127,7 @@ private: AnyFlow my_flow(InFlow in_flow) const override; public: FlowStats calculate_flow_stats(uint32_t docid_limit) const final; + double estimate_self_cost(InFlow in_flow) const noexcept override; HitEstimate combine(const std::vector<HitEstimate> &data) const override; FieldSpecBaseList exposeFields() const override; void sort(Children &children, InFlow in_flow) const override; @@ -147,6 +150,7 @@ private: AnyFlow my_flow(InFlow in_flow) const override; public: FlowStats calculate_flow_stats(uint32_t docid_limit) const final; + double estimate_self_cost(InFlow in_flow) const noexcept override; HitEstimate combine(const std::vector<HitEstimate> &data) const override; FieldSpecBaseList exposeFields() const override; void sort(Children &children, InFlow in_flow) const override; |