Control the auto-adjustment of targetHits in ANN using post-filtering.

When searching the HNSW index in a post-filtering case,
targetHits is auto-adjusted in an effort to still expose targetHits hits to first-phase ranking after post-filtering.
The following formula is now used to ensure an upper bound of adjustedTargetHits,
avoiding that the search in the HNSW index takes too long.

adjustedTargetHits = min(targetHits / estimatedHitRatio, targetHits * targetHitsMaxAdjustmentFactor).

The target-hits-max-adjustment-factor can be set in a rank profile and overriden per query.
The value is in the range [1.0,inf], with the default being 20.0.

When setting this to 1.0, auto-adjustment of targetHits is effectively disabled.

10 files changed, 78 insertions, 11 deletions

diff --git a/searchlib/src/tests/attribute/tensorattribute/tensorattribute_test.cpp b/searchlib/src/tests/attribute/tensorattribute/tensorattribute_test.cpp
index 6ca7d298ee2..0475f8462fc 100644
--- a/searchlib/src/tests/attribute/tensorattribute/tensorattribute_test.cpp
+++ b/searchlib/src/tests/attribute/tensorattribute/tensorattribute_test.cpp
@@ -1320,15 +1320,16 @@ public:
         return *_query_tensor;
     }
 
-    std::unique_ptr<NearestNeighborBlueprint> make_blueprint(bool approximate = true, double global_filter_lower_limit = 0.05) {
+    std::unique_ptr<NearestNeighborBlueprint> make_blueprint(bool approximate = true,
+                                                             double global_filter_lower_limit = 0.05,
+                                                             double target_hits_max_adjustment_factor = 20.0) {
         search::queryeval::FieldSpec field("foo", 0, 0);
         auto bp = std::make_unique<NearestNeighborBlueprint>(
             field,
             std::make_unique<DistanceCalculator>(this->as_dense_tensor(),
                                                  create_query_tensor(vec_2d(17, 42))),
-            3, approximate, 5,
-            100100.25,
-            global_filter_lower_limit, 1.0, _no_doom.get_doom());
+            3, approximate, 5, 100100.25,
+            global_filter_lower_limit, 1.0, target_hits_max_adjustment_factor, _no_doom.get_doom());
         EXPECT_EQUAL(11u, bp->getState().estimate().estHits);
         EXPECT_EQUAL(100100.25 * 100100.25, bp->get_distance_threshold());
         return bp;
@@ -1362,6 +1363,19 @@ TEST_F("NN blueprint handles empty filter (post-filtering)", NearestNeighborBlue
     EXPECT_EQUAL(NNBA::INDEX_TOP_K, bp->get_algorithm());
 }
 
+TEST_F("NN blueprint adjustment of targetHits is bound (post-filtering)", NearestNeighborBlueprintFixture)
+{
+    auto bp = f.make_blueprint(true, 0.05, 3.5);
+    auto empty_filter = GlobalFilter::create();
+    bp->set_global_filter(*empty_filter, 0.2);
+    // targetHits is adjusted based on the estimated hit ratio of the query,
+    // but bound by target-hits-max-adjustment-factor
+    EXPECT_EQUAL(3u, bp->get_target_hits());
+    EXPECT_EQUAL(10u, bp->get_adjusted_target_hits());
+    EXPECT_EQUAL(10u, bp->getState().estimate().estHits);
+    EXPECT_EQUAL(NNBA::INDEX_TOP_K, bp->get_algorithm());
+}
+
 TEST_F("NN blueprint handles strong filter (pre-filtering)", NearestNeighborBlueprintFixture)
 {
     auto bp = f.make_blueprint();
diff --git a/searchlib/src/tests/ranksetup/ranksetup_test.cpp b/searchlib/src/tests/ranksetup/ranksetup_test.cpp
index 50d9d36f575..f708df0a862 100644
--- a/searchlib/src/tests/ranksetup/ranksetup_test.cpp
+++ b/searchlib/src/tests/ranksetup/ranksetup_test.cpp
@@ -533,6 +533,9 @@ void RankSetupTest::testRankSetup()
     env.getProperties().add(mutate::on_second_phase::Operation::NAME, "=7");
     env.getProperties().add(mutate::on_summary::Attribute::NAME, "c");
     env.getProperties().add(mutate::on_summary::Operation::NAME, "-=2");
+    env.getProperties().add(matching::GlobalFilterLowerLimit::NAME, "0.3");
+    env.getProperties().add(matching::GlobalFilterUpperLimit::NAME, "0.7");
+    env.getProperties().add(matching::TargetHitsMaxAdjustmentFactor::NAME, "5.0");
 
     RankSetup rs(_factory, env);
     EXPECT_FALSE(rs.has_match_features());
@@ -571,7 +574,9 @@ void RankSetupTest::testRankSetup()
     EXPECT_EQUAL(rs.getMutateOnSecondPhase()._operation, "=7");
     EXPECT_EQUAL(rs.getMutateOnSummary()._attribute, "c");
     EXPECT_EQUAL(rs.getMutateOnSummary()._operation, "-=2");
-
+    EXPECT_EQUAL(rs.get_global_filter_lower_limit(), 0.3);
+    EXPECT_EQUAL(rs.get_global_filter_upper_limit(), 0.7);
+    EXPECT_EQUAL(rs.get_target_hits_max_adjustment_factor(), 5.0);
 }
 
 bool
diff --git a/searchlib/src/vespa/searchlib/attribute/attribute_blueprint_factory.cpp b/searchlib/src/vespa/searchlib/attribute/attribute_blueprint_factory.cpp
index be631be6dca..453b7b321b9 100644
--- a/searchlib/src/vespa/searchlib/attribute/attribute_blueprint_factory.cpp
+++ b/searchlib/src/vespa/searchlib/attribute/attribute_blueprint_factory.cpp
@@ -842,14 +842,16 @@ public:
         }
         try {
             auto calc = tensor::DistanceCalculator::make_with_validation(_attr, *query_tensor);
+            const auto& params = getRequestContext().get_attribute_blueprint_params();
             setResult(std::make_unique<queryeval::NearestNeighborBlueprint>(_field,
                                                                             std::move(calc),
                                                                             n.get_target_num_hits(),
                                                                             n.get_allow_approximate(),
                                                                             n.get_explore_additional_hits(),
                                                                             n.get_distance_threshold(),
-                                                                            getRequestContext().get_attribute_blueprint_params().global_filter_lower_limit,
-                                                                            getRequestContext().get_attribute_blueprint_params().global_filter_upper_limit,
+                                                                            params.global_filter_lower_limit,
+                                                                            params.global_filter_upper_limit,
+                                                                            params.target_hits_max_adjustment_factor,
                                                                             getRequestContext().getDoom()));
         } catch (const vespalib::IllegalArgumentException& ex) {
             return fail_nearest_neighbor_term(n, ex.getMessage());
diff --git a/searchlib/src/vespa/searchlib/attribute/attribute_blueprint_params.h b/searchlib/src/vespa/searchlib/attribute/attribute_blueprint_params.h
index 39f58c5382e..64213235c23 100644
--- a/searchlib/src/vespa/searchlib/attribute/attribute_blueprint_params.h
+++ b/searchlib/src/vespa/searchlib/attribute/attribute_blueprint_params.h
@@ -13,17 +13,21 @@ struct AttributeBlueprintParams
 {
     double global_filter_lower_limit;
     double global_filter_upper_limit;
+    double target_hits_max_adjustment_factor;
 
     AttributeBlueprintParams(double global_filter_lower_limit_in,
-                             double global_filter_upper_limit_in)
+                             double global_filter_upper_limit_in,
+                             double target_hits_max_adjustment_factor_in)
         : global_filter_lower_limit(global_filter_lower_limit_in),
-          global_filter_upper_limit(global_filter_upper_limit_in)
+          global_filter_upper_limit(global_filter_upper_limit_in),
+          target_hits_max_adjustment_factor(target_hits_max_adjustment_factor_in)
     {
     }
 
     AttributeBlueprintParams()
         : AttributeBlueprintParams(fef::indexproperties::matching::GlobalFilterLowerLimit::DEFAULT_VALUE,
-                                   fef::indexproperties::matching::GlobalFilterUpperLimit::DEFAULT_VALUE)
+                                   fef::indexproperties::matching::GlobalFilterUpperLimit::DEFAULT_VALUE,
+                                   fef::indexproperties::matching::TargetHitsMaxAdjustmentFactor::DEFAULT_VALUE)
     {
     }
 };
diff --git a/searchlib/src/vespa/searchlib/fef/indexproperties.cpp b/searchlib/src/vespa/searchlib/fef/indexproperties.cpp
index 8be44ce0a0c..7871e66970e 100644
--- a/searchlib/src/vespa/searchlib/fef/indexproperties.cpp
+++ b/searchlib/src/vespa/searchlib/fef/indexproperties.cpp
@@ -422,6 +422,22 @@ GlobalFilterUpperLimit::lookup(const Properties &props, double defaultValue)
     return lookupDouble(props, NAME, defaultValue);
 }
 
+const vespalib::string TargetHitsMaxAdjustmentFactor::NAME("vespa.matching.nns.target_hits_max_adjustment_factor");
+
+const double TargetHitsMaxAdjustmentFactor::DEFAULT_VALUE(20.0);
+
+double
+TargetHitsMaxAdjustmentFactor::lookup(const Properties& props)
+{
+    return lookup(props, DEFAULT_VALUE);
+}
+
+double
+TargetHitsMaxAdjustmentFactor::lookup(const Properties& props, double defaultValue)
+{
+    return lookupDouble(props, NAME, defaultValue);
+}
+
 } // namespace matching
 
 namespace softtimeout {
diff --git a/searchlib/src/vespa/searchlib/fef/indexproperties.h b/searchlib/src/vespa/searchlib/fef/indexproperties.h
index f538e7bef2e..4f38a27d3fe 100644
--- a/searchlib/src/vespa/searchlib/fef/indexproperties.h
+++ b/searchlib/src/vespa/searchlib/fef/indexproperties.h
@@ -313,6 +313,21 @@ namespace matching {
         static double lookup(const Properties &props);
         static double lookup(const Properties &props, double defaultValue);
     };
+
+    /**
+     * Property to control the auto-adjustment of targetHits in a nearestNeighbor search using HNSW index with post-filtering.
+     *
+     * The targetHits is auto-adjusted in an effort to expose targetHits hits to first-phase ranking after post-filtering:
+     * adjustedTargetHits = min(targetHits / estimatedHitRatio, targetHits * targetHitsMaxAdjustmentFactor).
+     *
+     * This property ensures an upper bound of adjustedTargetHits, avoiding that the search in the HNSW index takes too long.
+     **/
+    struct TargetHitsMaxAdjustmentFactor {
+        static const vespalib::string NAME;
+        static const double DEFAULT_VALUE;
+        static double lookup(const Properties &props);
+        static double lookup(const Properties &props, double defaultValue);
+    };
 }
 
 namespace softtimeout {
diff --git a/searchlib/src/vespa/searchlib/fef/ranksetup.cpp b/searchlib/src/vespa/searchlib/fef/ranksetup.cpp
index 823e39199df..9d4e547feef 100644
--- a/searchlib/src/vespa/searchlib/fef/ranksetup.cpp
+++ b/searchlib/src/vespa/searchlib/fef/ranksetup.cpp
@@ -68,6 +68,7 @@ RankSetup::RankSetup(const BlueprintFactory &factory, const IIndexEnvironment &i
       _softTimeoutTailCost(0.1),
       _global_filter_lower_limit(0.0),
       _global_filter_upper_limit(1.0),
+      _target_hits_max_adjustment_factor(20.0),
       _mutateOnMatch(),
       _mutateOnFirstPhase(),
       _mutateOnSecondPhase(),
@@ -121,6 +122,7 @@ RankSetup::configure()
     setSoftTimeoutTailCost(softtimeout::TailCost::lookup(_indexEnv.getProperties()));
     set_global_filter_lower_limit(matching::GlobalFilterLowerLimit::lookup(_indexEnv.getProperties()));
     set_global_filter_upper_limit(matching::GlobalFilterUpperLimit::lookup(_indexEnv.getProperties()));
+    set_target_hits_max_adjustment_factor(matching::TargetHitsMaxAdjustmentFactor::lookup(_indexEnv.getProperties()));
     _mutateOnMatch._attribute = mutate::on_match::Attribute::lookup(_indexEnv.getProperties());
     _mutateOnMatch._operation = mutate::on_match::Operation::lookup(_indexEnv.getProperties());
     _mutateOnFirstPhase._attribute = mutate::on_first_phase::Attribute::lookup(_indexEnv.getProperties());
diff --git a/searchlib/src/vespa/searchlib/fef/ranksetup.h b/searchlib/src/vespa/searchlib/fef/ranksetup.h
index 832b86d042a..72432c2ed8a 100644
--- a/searchlib/src/vespa/searchlib/fef/ranksetup.h
+++ b/searchlib/src/vespa/searchlib/fef/ranksetup.h
@@ -76,6 +76,7 @@ private:
     double                   _softTimeoutTailCost;
     double                   _global_filter_lower_limit;
     double                   _global_filter_upper_limit;
+    double                   _target_hits_max_adjustment_factor;
     MutateOperation          _mutateOnMatch;
     MutateOperation          _mutateOnFirstPhase;
     MutateOperation          _mutateOnSecondPhase;
@@ -393,6 +394,8 @@ public:
     double get_global_filter_lower_limit() const { return _global_filter_lower_limit; }
     void set_global_filter_upper_limit(double v) { _global_filter_upper_limit = v; }
     double get_global_filter_upper_limit() const { return _global_filter_upper_limit; }
+    void set_target_hits_max_adjustment_factor(double v) { _target_hits_max_adjustment_factor = v; }
+    double get_target_hits_max_adjustment_factor() const { return _target_hits_max_adjustment_factor; }
 
     /**
      * This method may be used to indicate that certain features
diff --git a/searchlib/src/vespa/searchlib/queryeval/nearest_neighbor_blueprint.cpp b/searchlib/src/vespa/searchlib/queryeval/nearest_neighbor_blueprint.cpp
index 87ddb8b6edc..32b5148f706 100644
--- a/searchlib/src/vespa/searchlib/queryeval/nearest_neighbor_blueprint.cpp
+++ b/searchlib/src/vespa/searchlib/queryeval/nearest_neighbor_blueprint.cpp
@@ -43,6 +43,7 @@ NearestNeighborBlueprint::NearestNeighborBlueprint(const queryeval::FieldSpec& f
                                                    double distance_threshold,
                                                    double global_filter_lower_limit,
                                                    double global_filter_upper_limit,
+                                                   double target_hits_max_adjustment_factor,
                                                    const vespalib::Doom& doom)
     : ComplexLeafBlueprint(field),
       _distance_calc(std::move(distance_calc)),
@@ -55,6 +56,7 @@ NearestNeighborBlueprint::NearestNeighborBlueprint(const queryeval::FieldSpec& f
       _distance_threshold(std::numeric_limits<double>::max()),
       _global_filter_lower_limit(global_filter_lower_limit),
       _global_filter_upper_limit(global_filter_upper_limit),
+      _target_hits_max_adjustment_factor(target_hits_max_adjustment_factor),
       _distance_heap(target_hits),
       _found_hits(),
       _algorithm(Algorithm::EXACT),
@@ -95,8 +97,10 @@ NearestNeighborBlueprint::set_global_filter(const GlobalFilter &global_filter, d
         } else { // post-filtering case
             // The goal is to expose 'targetHits' hits to first-phase ranking.
             // We try to achieve this by adjusting targetHits based on the estimated hit ratio of the query before post-filtering.
+            // However, this is bound by 'target-hits-max-adjustment-factor' to limit the cost of searching the HNSW index.
             if (estimated_hit_ratio > 0.0) {
-                _adjusted_target_hits = static_cast<double>(_target_hits) / estimated_hit_ratio;
+                _adjusted_target_hits = std::min(static_cast<double>(_target_hits) / estimated_hit_ratio,
+                                                 static_cast<double>(_target_hits) * _target_hits_max_adjustment_factor);
             }
         }
         if (_algorithm != Algorithm::EXACT_FALLBACK) {
diff --git a/searchlib/src/vespa/searchlib/queryeval/nearest_neighbor_blueprint.h b/searchlib/src/vespa/searchlib/queryeval/nearest_neighbor_blueprint.h
index f88cdd5adb1..174f0b23125 100644
--- a/searchlib/src/vespa/searchlib/queryeval/nearest_neighbor_blueprint.h
+++ b/searchlib/src/vespa/searchlib/queryeval/nearest_neighbor_blueprint.h
@@ -38,6 +38,7 @@ private:
     double _distance_threshold;
     double _global_filter_lower_limit;
     double _global_filter_upper_limit;
+    double _target_hits_max_adjustment_factor;
     mutable NearestNeighborDistanceHeap _distance_heap;
     std::vector<search::tensor::NearestNeighborIndex::Neighbor> _found_hits;
     Algorithm _algorithm;
@@ -55,6 +56,7 @@ public:
                              double distance_threshold,
                              double global_filter_lower_limit,
                              double global_filter_upper_limit,
+                             double target_hits_max_adjustment_factor,
                              const vespalib::Doom& doom);
     NearestNeighborBlueprint(const NearestNeighborBlueprint&) = delete;
     NearestNeighborBlueprint& operator=(const NearestNeighborBlueprint&) = delete;