diff options
author | Geir Storli <geirst@yahooinc.com> | 2024-02-13 13:04:13 +0100 |
---|---|---|
committer | GitHub <noreply@github.com> | 2024-02-13 13:04:13 +0100 |
commit | 0df446a4fcb16f6f1358de971762570af239bad8 (patch) | |
tree | 72eb1142632804d5abffdedd09b50c88b2002c0a | |
parent | 45b56e769811a58807a6c59e534473cd5f4be180 (diff) | |
parent | 64990b4bb6fd3cba16275f431a24212fe4c1abf7 (diff) |
Merge pull request #30243 from vespa-engine/havardpe/better-or-flow-stats
account for heap cost in strict OR
5 files changed, 166 insertions, 121 deletions
diff --git a/searchlib/src/tests/queryeval/blueprint/intermediate_blueprints_test.cpp b/searchlib/src/tests/queryeval/blueprint/intermediate_blueprints_test.cpp index aed6f6e60f2..510c6be4bf3 100644 --- a/searchlib/src/tests/queryeval/blueprint/intermediate_blueprints_test.cpp +++ b/searchlib/src/tests/queryeval/blueprint/intermediate_blueprints_test.cpp @@ -5,6 +5,7 @@ #include <vespa/searchlib/queryeval/isourceselector.h> #include <vespa/searchlib/queryeval/blueprint.h> #include <vespa/searchlib/queryeval/flow.h> +#include <vespa/searchlib/queryeval/flow_tuning.h> #include <vespa/searchlib/queryeval/intermediate_blueprints.h> #include <vespa/searchlib/queryeval/leaf_blueprints.h> #include <vespa/searchlib/queryeval/equiv_blueprint.h> @@ -1332,26 +1333,20 @@ void verify_cost(make &&mk, double expect, double expect_strict) { EXPECT_EQUAL(bp->strict_cost(), expect_strict); } -double calc_cost(std::vector<std::pair<double,double>> list) { - double flow = 1.0; - double cost = 0.0; - for (auto [sub_cost,pass_through]: list) { - cost += flow * sub_cost; - flow *= pass_through; - } - return cost; -} +std::vector<FlowStats> child_stats({{0.2, 1.1, 0.2*1.1}, + {0.3, 1.2, 0.3*1.2}, + {0.5, 1.3, 1.3}}); TEST("cost for OR") { verify_cost(make::OR(), - calc_cost({{1.3, 0.5},{1.2, 0.7},{1.1, 0.8}}), - 0.2*1.1 + 0.3*1.2 + 1.3); + OrFlow::cost_of(child_stats, false), + OrFlow::cost_of(child_stats, true) + flow::heap_cost(OrFlow::estimate_of(child_stats), 3)); } TEST("cost for AND") { verify_cost(make::AND(), - calc_cost({{1.1, 0.2},{1.2, 0.3},{1.3, 0.5}}), - calc_cost({{0.2*1.1, 0.2},{1.2, 0.3},{1.3, 0.5}})); + AndFlow::cost_of(child_stats, false), + AndFlow::cost_of(child_stats, true)); } TEST("cost for RANK") { @@ -1360,8 +1355,8 @@ TEST("cost for RANK") { TEST("cost for ANDNOT") { verify_cost(make::ANDNOT(), - calc_cost({{1.1, 0.2},{1.3, 0.5},{1.2, 0.7}}), - calc_cost({{0.2*1.1, 0.2},{1.3, 0.5},{1.2, 0.7}})); + AndNotFlow::cost_of(child_stats, false), + AndNotFlow::cost_of(child_stats, true)); } TEST("cost for SB") { @@ -1371,20 +1366,20 @@ TEST("cost for SB") { TEST("cost for NEAR") { verify_cost(make::NEAR(1), - 0.2*0.3*0.5 * 3 + calc_cost({{1.1, 0.2},{1.2, 0.3},{1.3, 0.5}}), - 0.2*0.3*0.5 * 3 + calc_cost({{0.2*1.1, 0.2},{1.2, 0.3},{1.3, 0.5}})); + AndFlow::cost_of(child_stats, false) + AndFlow::estimate_of(child_stats) * 3, + AndFlow::cost_of(child_stats, true) + AndFlow::estimate_of(child_stats) * 3); } TEST("cost for ONEAR") { verify_cost(make::ONEAR(1), - 0.2*0.3*0.5 * 3 + calc_cost({{1.1, 0.2},{1.2, 0.3},{1.3, 0.5}}), - 0.2*0.3*0.5 * 3 + calc_cost({{0.2*1.1, 0.2},{1.2, 0.3},{1.3, 0.5}})); + AndFlow::cost_of(child_stats, false) + AndFlow::estimate_of(child_stats) * 3, + AndFlow::cost_of(child_stats, true) + AndFlow::estimate_of(child_stats) * 3); } TEST("cost for WEAKAND") { verify_cost(make::WEAKAND(1000), - calc_cost({{1.3, 0.5},{1.2, 0.7},{1.1, 0.8}}), - 0.2*1.1 + 0.3*1.2 + 1.3); + OrFlow::cost_of(child_stats, false), + OrFlow::cost_of(child_stats, true)); } TEST_MAIN() { TEST_DEBUG("lhs.out", "rhs.out"); TEST_RUN_ALL(); } diff --git a/searchlib/src/tests/queryeval/flow/queryeval_flow_test.cpp b/searchlib/src/tests/queryeval/flow/queryeval_flow_test.cpp index ec3e0066134..7a3950dbf1c 100644 --- a/searchlib/src/tests/queryeval/flow/queryeval_flow_test.cpp +++ b/searchlib/src/tests/queryeval/flow/queryeval_flow_test.cpp @@ -9,42 +9,20 @@ constexpr size_t loop_cnt = 64; using namespace search::queryeval; -struct ItemAdapter { - double estimate(const auto &child) const noexcept { return child.rel_est; } - double cost(const auto &child) const noexcept { return child.cost; } - double strict_cost(const auto &child) const noexcept { return child.strict_cost; } -}; - -struct Item { - double rel_est; - double cost; - double strict_cost; - Item(double rel_est_in, double cost_in, double strict_cost_in) noexcept - : rel_est(rel_est_in), cost(cost_in), strict_cost(strict_cost_in) {} - template <typename FLOW> static double estimate_of(std::vector<Item> &data) { - return FLOW::estimate_of(ItemAdapter(), data); - } - template <typename FLOW> static void sort(std::vector<Item> &data, bool strict) { - FLOW::sort(ItemAdapter(), data, strict); - } - template <typename FLOW> static double cost_of(const std::vector<Item> &data, bool strict) { - return FLOW::cost_of(ItemAdapter(), data, strict); - } - template <typename FLOW> static double ordered_cost_of(const std::vector<Item> &data, bool strict) { - return flow::ordered_cost_of(ItemAdapter(), data, FLOW(1.0, strict)); - } - auto operator <=>(const Item &rhs) const noexcept = default; -}; +template <typename FLOW> +double ordered_cost_of(const std::vector<FlowStats> &data, bool strict) { + return flow::ordered_cost_of(flow::DirectAdapter(), data, FLOW(strict)); +} -std::vector<Item> gen_data(size_t size) { +std::vector<FlowStats> gen_data(size_t size) { static std::mt19937 gen; - static std::uniform_real_distribution<double> rel_est(0.1, 0.9); + static std::uniform_real_distribution<double> estimate(0.1, 0.9); static std::uniform_real_distribution<double> cost(1.0, 10.0); static std::uniform_real_distribution<double> strict_cost(0.1, 5.0); - std::vector<Item> result; + std::vector<FlowStats> result; result.reserve(size); for (size_t i = 0; i < size; ++i) { - result.emplace_back(rel_est(gen), cost(gen), strict_cost(gen)); + result.emplace_back(estimate(gen), cost(gen), strict_cost(gen)); } return result; } @@ -84,7 +62,7 @@ TEST(FlowTest, perm_test) { template <template <typename> typename ORDER> void verify_ordering_is_strict_weak() { - auto cmp = ORDER(ItemAdapter()); + auto cmp = ORDER(flow::DirectAdapter()); auto input = gen_data(7); input.emplace_back(0.5, 1.5, 0.5); input.emplace_back(0.5, 1.5, 0.5); @@ -97,13 +75,13 @@ void verify_ordering_is_strict_weak() { input.emplace_back(0.5, 1.5, 0.0); input.emplace_back(0.0, 0.0, 0.0); input.emplace_back(0.0, 0.0, 0.0); - std::vector<Item> output; - for (const Item &in: input) { + std::vector<FlowStats> output; + for (const FlowStats &in: input) { EXPECT_FALSE(cmp(in, in)); // Irreflexivity size_t out_idx = 0; bool lower = false; bool upper = false; - for (const Item &out: output) { + for (const FlowStats &out: output) { if (cmp(out, in)) { EXPECT_FALSE(cmp(in, out)); // Antisymmetry EXPECT_FALSE(lower); // Transitivity @@ -148,66 +126,90 @@ void verify_flow(auto flow, const std::vector<double> &est_list, const std::vect } } -TEST(FlowTest, basic_and_flow) { +TEST(FlowTest, full_and_flow) { + for (bool strict: {false, true}) { + verify_flow(AndFlow(strict), {0.4, 0.7, 0.2}, + {{1.0, 0.0, strict}, + {0.4, 0.4, false}, + {0.4*0.7, 0.4*0.7, false}, + {0.4*0.7*0.2, 0.4*0.7*0.2, false}}); + } +} + +TEST(FlowTest, partial_and_flow) { for (double in: {1.0, 0.5, 0.25}) { - for (bool strict: {false, true}) { - verify_flow(AndFlow(in, strict), {0.4, 0.7, 0.2}, - {{in, 0.0, strict}, - {in*0.4, in*0.4, false}, - {in*0.4*0.7, in*0.4*0.7, false}, - {in*0.4*0.7*0.2, in*0.4*0.7*0.2, false}}); - } + verify_flow(AndFlow(in), {0.4, 0.7, 0.2}, + {{in, 0.0, false}, + {in*0.4, in*0.4, false}, + {in*0.4*0.7, in*0.4*0.7, false}, + {in*0.4*0.7*0.2, in*0.4*0.7*0.2, false}}); } } -TEST(FlowTest, basic_or_flow) { +TEST(FlowTest, full_or_flow) { + verify_flow(OrFlow(false), {0.4, 0.7, 0.2}, + {{1.0, 0.0, false}, + {0.6, 1.0-0.6, false}, + {0.6*0.3, 1.0-0.6*0.3, false}, + {0.6*0.3*0.8, 1.0-0.6*0.3*0.8, false}}); + verify_flow(OrFlow(true), {0.4, 0.7, 0.2}, + {{1.0, 0.0, true}, + {1.0, 1.0-0.6, true}, + {1.0, 1.0-0.6*0.3, true}, + {1.0, 1.0-0.6*0.3*0.8, true}}); +} + +TEST(FlowTest, partial_or_flow) { for (double in: {1.0, 0.5, 0.25}) { - verify_flow(OrFlow(in, false), {0.4, 0.7, 0.2}, + verify_flow(OrFlow(in), {0.4, 0.7, 0.2}, {{in, 0.0, false}, {in*0.6, 1.0-in*0.6, false}, {in*0.6*0.3, 1.0-in*0.6*0.3, false}, {in*0.6*0.3*0.8, 1.0-in*0.6*0.3*0.8, false}}); - verify_flow(OrFlow(in, true), {0.4, 0.7, 0.2}, - {{in, 0.0, true}, - {in, 1.0-in*0.6, true}, - {in, 1.0-in*0.6*0.3, true}, - {in, 1.0-in*0.6*0.3*0.8, true}}); } } -TEST(FlowTest, basic_and_not_flow) { +TEST(FlowTest, full_and_not_flow) { + for (bool strict: {false, true}) { + verify_flow(AndNotFlow(strict), {0.4, 0.7, 0.2}, + {{1.0, 0.0, strict}, + {0.4, 0.4, false}, + {0.4*0.3, 0.4*0.3, false}, + {0.4*0.3*0.8, 0.4*0.3*0.8, false}}); + } +} + +TEST(FlowTest, partial_and_not_flow) { for (double in: {1.0, 0.5, 0.25}) { - for (bool strict: {false, true}) { - verify_flow(AndNotFlow(in, strict), {0.4, 0.7, 0.2}, - {{in, 0.0, strict}, - {in*0.4, in*0.4, false}, - {in*0.4*0.3, in*0.4*0.3, false}, - {in*0.4*0.3*0.8, in*0.4*0.3*0.8, false}}); - } + verify_flow(AndNotFlow(in), {0.4, 0.7, 0.2}, + {{in, 0.0, false}, + {in*0.4, in*0.4, false}, + {in*0.4*0.3, in*0.4*0.3, false}, + {in*0.4*0.3*0.8, in*0.4*0.3*0.8, false}}); } } TEST(FlowTest, flow_cost) { - std::vector<Item> data = {{0.4, 1.1, 0.6}, {0.7, 1.2, 0.5}, {0.2, 1.3, 0.4}}; - EXPECT_DOUBLE_EQ(Item::ordered_cost_of<AndFlow>(data, false), 1.1 + 0.4*1.2 + 0.4*0.7*1.3); - EXPECT_DOUBLE_EQ(Item::ordered_cost_of<AndFlow>(data, true), 0.6 + 0.4*1.2 + 0.4*0.7*1.3); - EXPECT_DOUBLE_EQ(Item::ordered_cost_of<OrFlow>(data, false), 1.1 + 0.6*1.2 + 0.6*0.3*1.3); - EXPECT_DOUBLE_EQ(Item::ordered_cost_of<OrFlow>(data, true), 0.6 + 0.5 + 0.4); - EXPECT_DOUBLE_EQ(Item::ordered_cost_of<AndNotFlow>(data, false), 1.1 + 0.4*1.2 + 0.4*0.3*1.3); - EXPECT_DOUBLE_EQ(Item::ordered_cost_of<AndNotFlow>(data, true), 0.6 + 0.4*1.2 + 0.4*0.3*1.3); + std::vector<FlowStats> data = {{0.4, 1.1, 0.6}, {0.7, 1.2, 0.5}, {0.2, 1.3, 0.4}}; + EXPECT_DOUBLE_EQ(ordered_cost_of<AndFlow>(data, false), 1.1 + 0.4*1.2 + 0.4*0.7*1.3); + EXPECT_DOUBLE_EQ(ordered_cost_of<AndFlow>(data, true), 0.6 + 0.4*1.2 + 0.4*0.7*1.3); + EXPECT_DOUBLE_EQ(ordered_cost_of<OrFlow>(data, false), 1.1 + 0.6*1.2 + 0.6*0.3*1.3); + EXPECT_DOUBLE_EQ(ordered_cost_of<OrFlow>(data, true), 0.6 + 0.5 + 0.4); + EXPECT_DOUBLE_EQ(ordered_cost_of<AndNotFlow>(data, false), 1.1 + 0.4*1.2 + 0.4*0.3*1.3); + EXPECT_DOUBLE_EQ(ordered_cost_of<AndNotFlow>(data, true), 0.6 + 0.4*1.2 + 0.4*0.3*1.3); } TEST(FlowTest, optimal_and_flow) { for (size_t i = 0; i < loop_cnt; ++i) { for (bool strict: {false, true}) { auto data = gen_data(7); - double ref_est = Item::estimate_of<AndFlow>(data); - double min_cost = Item::cost_of<AndFlow>(data, strict); + double ref_est = AndFlow::estimate_of(data); + double min_cost = AndFlow::cost_of(data, strict); double max_cost = 0.0; - Item::sort<AndFlow>(data, strict); - EXPECT_EQ(Item::ordered_cost_of<AndFlow>(data, strict), min_cost); - auto check = [&](const std::vector<Item> &my_data) noexcept { - double my_cost = Item::ordered_cost_of<AndFlow>(my_data, strict); + AndFlow::sort(data, strict); + EXPECT_EQ(ordered_cost_of<AndFlow>(data, strict), min_cost); + auto check = [&](const std::vector<FlowStats> &my_data) noexcept { + double my_cost = ordered_cost_of<AndFlow>(my_data, strict); EXPECT_LE(min_cost, my_cost); max_cost = std::max(max_cost, my_cost); }; @@ -216,7 +218,7 @@ TEST(FlowTest, optimal_and_flow) { fprintf(stderr, " AND cost(%zu,%s): min: %g, max: %g, factor: %g\n", i, strict ? "strict" : "non-strict", min_cost, max_cost, max_cost / min_cost); } - EXPECT_NEAR(ref_est, Item::estimate_of<AndFlow>(data), 1e-9); + EXPECT_NEAR(ref_est, AndFlow::estimate_of(data), 1e-9); } } } @@ -225,12 +227,12 @@ TEST(FlowTest, optimal_or_flow) { for (size_t i = 0; i < loop_cnt; ++i) { for (bool strict: {false, true}) { auto data = gen_data(7); - double min_cost = Item::cost_of<OrFlow>(data, strict); + double min_cost = OrFlow::cost_of(data, strict); double max_cost = 0.0; - Item::sort<OrFlow>(data, strict); - EXPECT_EQ(Item::ordered_cost_of<OrFlow>(data, strict), min_cost); - auto check = [&](const std::vector<Item> &my_data) noexcept { - double my_cost = Item::ordered_cost_of<OrFlow>(my_data, strict); + OrFlow::sort(data, strict); + EXPECT_EQ(ordered_cost_of<OrFlow>(data, strict), min_cost); + auto check = [&](const std::vector<FlowStats> &my_data) noexcept { + double my_cost = ordered_cost_of<OrFlow>(my_data, strict); EXPECT_LE(min_cost, my_cost + 1e-9); max_cost = std::max(max_cost, my_cost); }; @@ -247,15 +249,15 @@ TEST(FlowTest, optimal_and_not_flow) { for (size_t i = 0; i < loop_cnt; ++i) { for (bool strict: {false, true}) { auto data = gen_data(7); - Item first = data[0]; - double min_cost = Item::cost_of<AndNotFlow>(data, strict); + FlowStats first = data[0]; + double min_cost = AndNotFlow::cost_of(data, strict); double max_cost = 0.0; - Item::sort<AndNotFlow>(data, strict); + AndNotFlow::sort(data, strict); EXPECT_EQ(data[0], first); - EXPECT_EQ(Item::ordered_cost_of<AndNotFlow>(data, strict), min_cost); - auto check = [&](const std::vector<Item> &my_data) noexcept { + EXPECT_EQ(ordered_cost_of<AndNotFlow>(data, strict), min_cost); + auto check = [&](const std::vector<FlowStats> &my_data) noexcept { if (my_data[0] == first) { - double my_cost = Item::ordered_cost_of<AndNotFlow>(my_data, strict); + double my_cost = ordered_cost_of<AndNotFlow>(my_data, strict); EXPECT_LE(min_cost, my_cost); max_cost = std::max(max_cost, my_cost); } diff --git a/searchlib/src/vespa/searchlib/queryeval/flow.h b/searchlib/src/vespa/searchlib/queryeval/flow.h index 1dc6e6aef55..cfbb28b190f 100644 --- a/searchlib/src/vespa/searchlib/queryeval/flow.h +++ b/searchlib/src/vespa/searchlib/queryeval/flow.h @@ -1,9 +1,10 @@ // Copyright Vespa.ai. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. #pragma once +#include <vespa/vespalib/util/small_vector.h> #include <cstddef> #include <algorithm> -#include <vespa/vespalib/util/small_vector.h> +#include <cmath> // Model how boolean result decisions flow through intermediate nodes // of different types based on relative estimates for sub-expressions @@ -16,6 +17,7 @@ struct FlowStats { double strict_cost; constexpr FlowStats(double estimate_in, double cost_in, double strict_cost_in) noexcept : estimate(estimate_in), cost(cost_in), strict_cost(strict_cost_in) {} + auto operator <=>(const FlowStats &rhs) const noexcept = default; }; namespace flow { @@ -28,6 +30,38 @@ struct DefaultAdapter { double strict_cost(const auto &child) const noexcept { return child->strict_cost(); } }; +template <typename T> +concept DefaultAdaptable = requires(const T &t) { + { t->estimate() } -> std::same_as<double>; + { t->cost() } -> std::same_as<double>; + { t->strict_cost() } -> std::same_as<double>; +}; + +// adapter making it possible to use FlowStats directly for testing +struct DirectAdapter { + double estimate(const auto &child) const noexcept { return child.estimate; } + double cost(const auto &child) const noexcept { return child.cost; } + double strict_cost(const auto &child) const noexcept { return child.strict_cost; } +}; + +template <typename T> +concept DirectAdaptable = requires(const T &t) { + { t.estimate } -> std::same_as<const double &>; + { t.cost } -> std::same_as<const double &>; + { t.strict_cost } -> std::same_as<const double &>; +}; + +auto make_adapter(const auto &children) { + using type = std::remove_cvref_t<decltype(children)>::value_type; + if constexpr (DefaultAdaptable<type>) { + return DefaultAdapter(); + } else if constexpr (DirectAdaptable<type>) { + return DirectAdapter(); + } else { + static_assert(false, "unable to resolve children adapter"); + } +} + template <typename ADAPTER, typename T> struct IndirectAdapter { const T &data; @@ -133,19 +167,19 @@ size_t select_strict_and_child(ADAPTER adapter, const T &children) { template <typename FLOW> struct FlowMixin { static double estimate_of(auto adapter, const auto &children) { - return flow::estimate_of(adapter, children, FLOW(1.0, false)); + return flow::estimate_of(adapter, children, FLOW(false)); } static double estimate_of(const auto &children) { - return estimate_of(flow::DefaultAdapter(), children); + return estimate_of(flow::make_adapter(children), children); } static double cost_of(auto adapter, const auto &children, bool strict) { auto my_adapter = flow::IndirectAdapter(adapter, children); auto order = flow::make_index(children.size()); FLOW::sort(my_adapter, order, strict); - return flow::ordered_cost_of(my_adapter, order, FLOW(1.0, strict)); + return flow::ordered_cost_of(my_adapter, order, FLOW(strict)); } static double cost_of(const auto &children, bool strict) { - return cost_of(flow::DefaultAdapter(), children, strict); + return cost_of(flow::make_adapter(children), children, strict); } }; @@ -155,8 +189,8 @@ private: bool _strict; bool _first; public: - AndFlow(double in, bool strict) noexcept - : _flow(in), _strict(strict), _first(true) {} + AndFlow(bool strict) noexcept : _flow(1.0), _strict(strict), _first(true) {} + AndFlow(double in) noexcept : _flow(in), _strict(false), _first(true) {} void add(double est) noexcept { _flow *= est; _first = false; @@ -182,25 +216,24 @@ public: } } static void sort(auto &children, bool strict) { - sort(flow::DefaultAdapter(), children, strict); + sort(flow::make_adapter(children), children, strict); } }; class OrFlow : public FlowMixin<OrFlow>{ private: - double _full; double _flow; bool _strict; bool _first; public: - OrFlow(double in, bool strict) noexcept - : _full(in), _flow(in), _strict(strict), _first(true) {} + OrFlow(bool strict) noexcept : _flow(1.0), _strict(strict), _first(true) {} + OrFlow(double in) noexcept : _flow(in), _strict(false), _first(true) {} void add(double est) noexcept { _flow *= (1.0 - est); _first = false; } double flow() const noexcept { - return _strict ? _full : _flow; + return _strict ? 1.0 : _flow; } bool strict() const noexcept { return _strict; @@ -214,7 +247,7 @@ public: } } static void sort(auto &children, bool strict) { - sort(flow::DefaultAdapter(), children, strict); + sort(flow::make_adapter(children), children, strict); } }; @@ -224,8 +257,8 @@ private: bool _strict; bool _first; public: - AndNotFlow(double in, bool strict) noexcept - : _flow(in), _strict(strict), _first(true) {} + AndNotFlow(bool strict) noexcept : _flow(1.0), _strict(strict), _first(true) {} + AndNotFlow(double in) noexcept : _flow(in), _strict(false), _first(true) {} void add(double est) noexcept { _flow *= _first ? est : (1.0 - est); _first = false; @@ -243,7 +276,7 @@ public: flow::sort_partial<flow::MinOrCost>(adapter, children, 1); } static void sort(auto &children, bool strict) { - sort(flow::DefaultAdapter(), children, strict); + sort(flow::make_adapter(children), children, strict); } }; diff --git a/searchlib/src/vespa/searchlib/queryeval/flow_tuning.h b/searchlib/src/vespa/searchlib/queryeval/flow_tuning.h new file mode 100644 index 00000000000..ab0381fa12c --- /dev/null +++ b/searchlib/src/vespa/searchlib/queryeval/flow_tuning.h @@ -0,0 +1,13 @@ +// Copyright Vespa.ai. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. + +#pragma once +#include <cmath> +#include <cstddef> + +namespace search::queryeval::flow { + +inline double heap_cost(double my_est, size_t num_children) { + return my_est * std::log2(std::max(size_t(1),num_children)); +} + +} diff --git a/searchlib/src/vespa/searchlib/queryeval/intermediate_blueprints.cpp b/searchlib/src/vespa/searchlib/queryeval/intermediate_blueprints.cpp index 089351b4ae5..938044c0c19 100644 --- a/searchlib/src/vespa/searchlib/queryeval/intermediate_blueprints.cpp +++ b/searchlib/src/vespa/searchlib/queryeval/intermediate_blueprints.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 "intermediate_blueprints.h" +#include "flow_tuning.h" #include "andnotsearch.h" #include "andsearch.h" #include "orsearch.h" @@ -315,9 +316,10 @@ OrBlueprint::~OrBlueprint() = default; FlowStats OrBlueprint::calculate_flow_stats(uint32_t) const { - return {OrFlow::estimate_of(get_children()), + double est = OrFlow::estimate_of(get_children()); + return {est, OrFlow::cost_of(get_children(), false), - OrFlow::cost_of(get_children(), true)}; + OrFlow::cost_of(get_children(), true) + flow::heap_cost(est, get_children().size())}; } Blueprint::HitEstimate |