empty case optimization

arangodb · gnusi · Sep 10, 2021 · Sep 3, 2021 · Sep 6, 2021 · Sep 6, 2021
commit 17ea36a45fa3640c542688f4d912d0d6dc3aeaf7
diff --git a/arangod/IResearch/IResearchFilterFactory.cpp b/arangod/IResearch/IResearchFilterFactory.cpp
@@ -3600,7 +3600,7 @@ Result fromFuncStartsWith(
                   return {};
                 }
                } else {
-                // maybe we could enlarge prefix to cover us?
+                 // maybe we could enlarge prefix to cover us?
                  if (std::memcmp(options->prefix.data(), startsWith.c_str(),
                                  options->prefix.size()) == 0) {
                    // looks promising - beginning of the levenshtein prefix is ok
@@ -3616,12 +3616,17 @@ Result fromFuncStartsWith(
                      return {};
                    }
                  }
-               // FIXME: if levenshtein term.size() + prefix.size() + max_distance < startsWith.size()
-               //        this is impossible condition so we could replace whole conjunction with an empty
-               //        filter. But current API does not allow filters removal
-               //        Also we could check if there is a contradiction in prefixes and make an empty filter.
               }
             }
+            if ((options->term.size() +
+                 options->prefix.size() +
+                 options->max_distance) < startsWith.size()) {
+                     // last optimization effort - we can't fulfill this conjunction.
+                     // make it empty
+                     filter->clear();
+                     filter->add<irs::empty>();
+                     return {};
+            }
           }
         }
       }

diff --git a/tests/IResearch/IResearchQueryOptimization-test.cpp b/tests/IResearch/IResearchQueryOptimization-test.cpp
@@ -12139,6 +12139,28 @@ TEST_P(IResearchQueryOptimizationTest, mergeLevenshteinStartsWith) {
       "RETURN d",
       expected);
   }
+  // make it empty with prefix
+  {
+    irs::Or expected;
+    auto& andFilter =  expected.add<irs::And>().add<irs::empty>();
+    assertFilterOptimized(
+      vocbase(),
+      "FOR d IN testView SEARCH STARTS_WITH(d.name, 'foobar12345')"
+      "AND LEVENSHTEIN_MATCH(d.name, 'bar', 2, false, 63, 'foo')"
+      "RETURN d",
+      expected);
+  }
+  // make it empty
+  {
+    irs::Or expected;
+    auto& andFilter =  expected.add<irs::And>().add<irs::empty>();
+    assertFilterOptimized(
+      vocbase(),
+      "FOR d IN testView SEARCH STARTS_WITH(d.name, 'foobar12345')"
+      "AND LEVENSHTEIN_MATCH(d.name, 'foobar', 2, false, 63)"
+      "RETURN d",
+      expected);
+  }
   // empty prefix case - not match
   {
     irs::Or expected;

diff --git a/tests/IResearch/common.cpp b/tests/IResearch/common.cpp
@@ -143,6 +143,11 @@ namespace iresearch {
     return os;
   }
 
+  std::ostream& operator<<(std::ostream& os, empty const&) {
+    os << "EMPTY[]";
+    return os;
+  }
+
   std::ostream& operator<<(std::ostream& os, by_edit_distance const& lev) {
     os << "LEVENSHTEIN_MATCH[";
     os << lev.field() << ", '";
@@ -180,6 +185,8 @@ namespace iresearch {
       return os << static_cast<by_edit_distance const&>(filter);
     } else if (type == irs::type<by_prefix>::id()) {
       return os << static_cast<by_prefix const&>(filter);
+    } else if (type == irs::type<empty>::id()) {
+      return os << static_cast<empty const&>(filter);
     } else {
       return os << "[Unknown filter]";
     }