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