arangodb · gnusi · Sep 10, 2021 · Sep 3, 2021 · Sep 6, 2021 · Sep 6, 2021
diff --git a/CHANGELOG b/CHANGELOG
@@ -1,6 +1,10 @@
 devel
 -----
 
+* Added ArangoSearch condition optimization: STARTS_WITH is merged 
+  with LEVENSHTEIN_MATCH if used in the same AND node and field name and prefix
+  matches.
+
 * Added multidimensional indexes which can be used to efficiently intersect
   multiple range queries. They are currently limited to IEEE-754 double values.
   Given documents of the form {x: 12.9, y: -284.0, z: 0.02} one can define a

diff --git a/arangod/Aql/IResearchViewExecutor.cpp b/arangod/Aql/IResearchViewExecutor.cpp
@@ -150,7 +150,8 @@ IResearchViewExecutorInfos::IResearchViewExecutorInfos(
     IResearchViewStoredValues const& storedValues, ExecutionPlan const& plan,
     Variable const& outVariable, aql::AstNode const& filterCondition,
     std::pair<bool, bool> volatility, IResearchViewExecutorInfos::VarInfoMap const& varInfoMap,
-    int depth, IResearchViewNode::ViewValuesRegisters&& outNonMaterializedViewRegs, iresearch::CountApproximate countApproximate)
+    int depth, IResearchViewNode::ViewValuesRegisters&& outNonMaterializedViewRegs,
+    iresearch::CountApproximate countApproximate, iresearch::FilterOptimization filterOptimization)
     : _scoreRegisters(std::move(scoreRegisters)),
       _reader(std::move(reader)),
       _query(query),
@@ -167,7 +168,8 @@ IResearchViewExecutorInfos::IResearchViewExecutorInfos(
       _depth(depth),
       _outNonMaterializedViewRegs(std::move(outNonMaterializedViewRegs)),
       _countApproximate(countApproximate),
-      _filterConditionIsEmpty(::filterConditionIsEmpty(&_filterCondition)) {
+      _filterConditionIsEmpty(::filterConditionIsEmpty(&_filterCondition)),
+      _filterOptimization(filterOptimization) {
   TRI_ASSERT(_reader != nullptr);
   std::tie(_documentOutReg, _collectionPointerReg) = std::visit(
       overload{[&](aql::IResearchViewExecutorInfos::MaterializeRegisters regs) {
@@ -599,7 +601,8 @@ void IResearchViewExecutorBase<Impl, Traits>::reset() {
 
   ExecutionPlan const* plan = &infos().plan();
   iresearch::QueryContext const queryCtx = { &_trx, plan, plan->getAst(),
-                                            &_ctx, _reader.get(), &infos().outVariable()};
+                                            &_ctx, _reader.get(), &infos().outVariable(),
+                                            infos().filterOptimization()};
 
   if (infos().volatileFilter() || !_isInitialized) {  // `_volatileSort` implies `_volatileFilter`
     irs::Or root;

diff --git a/arangod/Aql/IResearchViewExecutor.h b/arangod/Aql/IResearchViewExecutor.h
@@ -90,7 +90,7 @@ class IResearchViewExecutorInfos {
       Variable const& outVariable, aql::AstNode const& filterCondition,
       std::pair<bool, bool> volatility, VarInfoMap const& varInfoMap, int depth,
       iresearch::IResearchViewNode::ViewValuesRegisters&& outNonMaterializedViewRegs,
-      iresearch::CountApproximate);
+      iresearch::CountApproximate, iresearch::FilterOptimization);
 
   auto getDocumentRegister() const noexcept -> RegisterId;
   auto getCollectionRegister() const noexcept -> RegisterId;
@@ -111,6 +111,7 @@ class IResearchViewExecutorInfos {
   bool volatileSort() const noexcept;
   bool volatileFilter() const noexcept;
   iresearch::CountApproximate countApproximate() const noexcept { return _countApproximate; }
+  iresearch::FilterOptimization filterOptimization() const noexcept { return _filterOptimization; }
 
   // first - sort
   // second - number of sort conditions to take into account
@@ -137,6 +138,7 @@ class IResearchViewExecutorInfos {
   iresearch::IResearchViewNode::ViewValuesRegisters _outNonMaterializedViewRegs;
   iresearch::CountApproximate _countApproximate;
   bool _filterConditionIsEmpty;
+  iresearch::FilterOptimization _filterOptimization;
 };  // IResearchViewExecutorInfos
 
 class IResearchViewStats {

diff --git a/arangod/Aql/IResearchViewNode.cpp b/arangod/Aql/IResearchViewNode.cpp
@@ -179,6 +179,10 @@ void toVelocyPack(velocypack::Builder& builder, IResearchViewNode::Options const
       }
     }
   }
+
+  if (options.filterOptimization != arangodb::iresearch::FilterOptimization::MAX) {
+    builder.add("filterOptimization", VPackValue(static_cast<int64_t>(options.filterOptimization)));
+  }
 }
 
 bool fromVelocyPack(velocypack::Slice optionsSlice, IResearchViewNode::Options& options) {
@@ -284,6 +288,19 @@ bool fromVelocyPack(velocypack::Slice optionsSlice, IResearchViewNode::Options&
     }
   }
 
+  // filterOptimization
+  {
+    auto const optionSlice = optionsSlice.get("filterOptimization");
+    if (!optionSlice.isNone()) {
+      // 'filterOptimization' is optional. Missing means MAX
+      if (!optionSlice.isNumber()) {
+        return false;
+      }
+      options.filterOptimization =
+        static_cast<arangodb::iresearch::FilterOptimization>(optionSlice.getNumber<int>());
+    }
+  }
+
   return true;
 }
 
@@ -438,6 +455,18 @@ bool parseOptions(aql::QueryContext& query, LogicalView const& view, aql::AstNod
          }
          options.conditionOptimization = conditionTypeIt->second;
          return true;
+       }},
+       // cppcheck-suppress constStatement
+       {"filterOptimization", [](aql::QueryContext& /*query*/, LogicalView const& /*view*/,
+                                  aql::AstNode const& value,
+                                  IResearchViewNode::Options& options, std::string& error) {
+         if (!value.isValueType(aql::VALUE_TYPE_INT)) {
+           error = "int value expected for option 'filterOptimization'";
+           return false;
+         }
+         options.filterOptimization =
+           static_cast<arangodb::iresearch::FilterOptimization>(value.getIntValue());
+         return true;
        }}};
 
   if (!optionsNode) {
@@ -1660,7 +1689,8 @@ std::unique_ptr<aql::ExecutionBlock> IResearchViewNode::createBlock(
                                         getRegisterPlan()->varInfo,   // ??? do we need this?
                                         getDepth(),
                                         std::move(outNonMaterializedViewRegs),
-                                        _options.countApproximate};
+                                        _options.countApproximate,
+                                        filterOptimization()};
 
     return std::make_tuple(materializeType, std::move(executorInfos), std::move(registerInfos));
   };

diff --git a/arangod/Aql/IResearchViewNode.h b/arangod/Aql/IResearchViewNode.h
@@ -29,6 +29,7 @@
 #include "Aql/ExecutionNodeId.h"
 #include "Aql/LateMaterializedOptimizerRulesCommon.h"
 #include "Aql/types.h"
+#include "IResearch/IResearchFilterOptimization.h"
 #include "IResearch/IResearchOrderFactory.h"
 #include "IResearch/IResearchViewSort.h"
 #include "IResearch/IResearchViewStoredValues.h"
@@ -90,6 +91,9 @@ class IResearchViewNode final : public arangodb::aql::ExecutionNode {
 
     /// @brief skipAll method for view
     CountApproximate countApproximate{CountApproximate::Exact};
+
+    /// @brief iresearch filters optimization level
+    FilterOptimization filterOptimization {FilterOptimization::MAX};
   };  // Options
 
   IResearchViewNode(aql::ExecutionPlan& plan, aql::ExecutionNodeId id, TRI_vocbase_t& vocbase,
@@ -151,6 +155,15 @@ class IResearchViewNode final : public arangodb::aql::ExecutionNode {
   /// @brief return the scorers to pass to the view
   std::vector<Scorer> const& scorers() const noexcept { return _scorers; }
 
+  // we could merge if it is allowed in general and there are no scores - as changing
+  // filters will affect score and we will lose backward compatibility
+  FilterOptimization filterOptimization() const noexcept {
+    if (!_scorers.empty()) {
+      return FilterOptimization::NONE;
+    }
+    return _options.filterOptimization;
+  }
+
   /// @brief set the scorers to pass to the view
   void scorers(std::vector<Scorer>&& scorers) noexcept {
     _scorers = std::move(scorers);

diff --git a/arangod/Aql/IResearchViewOptimizerRules.cpp b/arangod/Aql/IResearchViewOptimizerRules.cpp
@@ -24,6 +24,7 @@
 
 #include "IResearchViewOptimizerRules.h"
 
+#include "Aql/AqlFunctionFeature.h"
 #include "Aql/CalculationNodeVarFinder.h"
 #include "Aql/ClusterNodes.h"
 #include "Aql/Condition.h"
@@ -77,6 +78,50 @@ inline IResearchViewStoredValues const& storedValues(arangodb::LogicalView const
   return viewImpl.storedValues();
 }
 
+/// @brief Moves all FCALLs in every AND node to the bottom of the AND node
+/// @param condition SEARCH condition node
+/// @param starts_with Function to push
+void pushFuncToBack(arangodb::aql::AstNode& condition, arangodb::aql::Function const* starts_with) {
+  auto numMembers = condition.numMembers();
+  for (size_t memberIdx = 0; memberIdx < numMembers; ++memberIdx) {
+    auto current = condition.getMemberUnchecked(memberIdx);
+    TRI_ASSERT(current);
+    auto const numAndMembers = current->numMembers();
+    if (current->type == arangodb::aql::AstNodeType::NODE_TYPE_OPERATOR_NARY_AND &&
+        numAndMembers > 1) {
+      size_t movePoint = numAndMembers - 1;
+      do {
+        auto candidate = current->getMemberUnchecked(movePoint);
+        if (candidate->type != arangodb::aql::AstNodeType::NODE_TYPE_FCALL ||
+            static_cast<arangodb::aql::Function const*>(candidate->getData()) != starts_with) {
+          break;
+        }
+      } while ((--movePoint) != 0);
+      for (size_t andMemberIdx = 0; andMemberIdx < movePoint; ++andMemberIdx) {
+        auto andMember = current->getMemberUnchecked(andMemberIdx);
+        if (andMember->type == arangodb::aql::AstNodeType::NODE_TYPE_FCALL &&
+            static_cast<arangodb::aql::Function const*>(andMember->getData()) == starts_with) {
+          TEMPORARILY_UNLOCK_NODE(current);
+          auto tmp = current->getMemberUnchecked(movePoint);
+          current->changeMember(movePoint--, andMember);
+          current->changeMember(andMemberIdx, tmp);
+          while (movePoint > andMemberIdx &&
+                 current->getMemberUnchecked(movePoint)->type ==
+                     arangodb::aql::AstNodeType::NODE_TYPE_FCALL &&
+                 static_cast<arangodb::aql::Function const*>(
+                     current->getMemberUnchecked(movePoint)->getData()) == starts_with) {
+            --movePoint;
+          }
+        } else {
+          pushFuncToBack(*andMember, starts_with);
+        }
+      }
+    } else {
+      pushFuncToBack(*current, starts_with);
+    }
+  }
+}
+
 bool addView(arangodb::LogicalView const& view, arangodb::aql::QueryContext& query) {
   auto& collections = query.collections();
 
@@ -132,6 +177,13 @@ bool optimizeSearchCondition(IResearchViewNode& viewNode, arangodb::aql::QueryCo
 
  // check filter condition if present
   if (searchCondition.root()) {
+    if (viewNode.filterOptimization() != arangodb::iresearch::FilterOptimization::NONE) {
+      // we could benefit from merging STARTS_WITH and LEVENSHTEIN_MATCH
+      auto& server = plan.getAst()->query().vocbase().server();
+      auto starts_with = server.getFeature<AqlFunctionFeature>().byName("STARTS_WITH");
+      TRI_ASSERT(starts_with);
+      pushFuncToBack(*searchCondition.root(), starts_with);
+    }
     auto filterCreated = FilterFactory::filter(
       nullptr,
       { &query.trxForOptimization(), nullptr, nullptr, nullptr, nullptr, &viewNode.outVariable() },
@@ -728,14 +780,14 @@ void handleViewsRule(Optimizer* opt,
       modified |= optimizeSort(viewNode, plan.get());
     }
 
-    if (!optimizeSearchCondition(viewNode, query, *plan)) {
-      continue;
-    }
-
     // find scorers that have to be evaluated by a view
     scorerReplacer.extract(viewNode.outVariable(), scorers);
     viewNode.scorers(std::move(scorers));
 
+    if (!optimizeSearchCondition(viewNode, query, *plan)) {
+      continue;
+    }
+
     modified = true;
   }
   keepReplacementViewVariables(calcNodes, viewNodes);

diff --git a/arangod/CMakeLists.txt b/arangod/CMakeLists.txt
@@ -66,6 +66,7 @@ add_library(arango_iresearch
   IResearch/IResearchExpressionContext.cpp IResearch/IResearchExpressionContext.h
   IResearch/IResearchFeature.cpp IResearch/IResearchFeature.h
   IResearch/IResearchFilterFactory.cpp IResearch/IResearchFilterFactory.h
+  IResearch/IResearchFilterOptimization.cpp IResearch/IResearchFilterOptimization.h
   IResearch/IResearchIdentityAnalyzer.cpp IResearch/IResearchIdentityAnalyzer.h
   IResearch/IResearchKludge.cpp IResearch/IResearchKludge.h
   IResearch/IResearchLink.cpp IResearch/IResearchLink.h

diff --git a/arangod/IResearch/AqlHelper.h b/arangod/IResearch/AqlHelper.h
@@ -28,6 +28,7 @@
 #include "Aql/AstNode.h"
 #include "Aql/SortCondition.h"
 #include "VelocyPackHelper.h"
+#include "IResearch/IResearchFilterOptimization.h"
 
 #include "search/sort.hpp"
 #include "utils/noncopyable.hpp"
@@ -241,6 +242,8 @@ struct QueryContext {
   aql::ExpressionContext* ctx;
   irs::index_reader const* index;
   aql::Variable const* ref;
+  /// @brief allow optimize away/modify some conditions during filter building
+  FilterOptimization  filterOptimization {FilterOptimization::MAX};
 };  // QueryContext
 
 ////////////////////////////////////////////////////////////////////////////////

diff --git a/arangod/IResearch/IResearchFilterFactory.cpp b/arangod/IResearch/IResearchFilterFactory.cpp
@@ -65,6 +65,7 @@
 #include "IResearch/IResearchAnalyzerFeature.h"
 #include "IResearch/IResearchCommon.h"
 #include "IResearch/IResearchFeature.h"
+#include "IResearch/IResearchFilterOptimization.h"
 #include "IResearch/IResearchKludge.h"
 #include "IResearch/IResearchPDP.h"
 #include "Logger/LogMacros.h"
@@ -241,7 +242,7 @@ Result malformedNode(aql::AstNodeType type) {
   return {TRI_ERROR_BAD_PARAMETER, message};
 }
 
-} // error
+} // namespace error
 
 bool setupGeoFilter(FieldMeta::Analyzer const& a,
                     S2RegionTermIndexer::Options& opts) {
@@ -403,7 +404,7 @@ Result getAnalyzerByName(
   }
   auto& analyzerFeature = server.getFeature<IResearchAnalyzerFeature>();
 
-  analyzer = analyzerFeature.get(analyzerId, ctx.trx->vocbase(),	
+  analyzer = analyzerFeature.get(analyzerId, ctx.trx->vocbase(),
                                  ctx.trx->state()->analyzersRevision());
 
   if (!analyzer) {
@@ -2084,7 +2085,6 @@ Result fromFuncAnalyzer(
 
     shortName = arangodb::iresearch::IResearchAnalyzerFeature::normalize(  // normalize
       analyzerId, ctx.trx->vocbase().name(), false);  // args
-
   }
 
   FilterContext const subFilterContext(analyzerValue, filterCtx.boost); // override analyzer
@@ -3570,17 +3570,29 @@ Result fromFuncStartsWith(
 
     TRI_ASSERT(filterCtx.analyzer);
     kludge::mangleField(name, filterCtx.analyzer);
-    filter->boost(filterCtx.boost);
+
+    // Try to optimize us away
+    if (!isMultiPrefix && !prefixes.empty() &&
+        ctx.filterOptimization != FilterOptimization::NONE  && 
+        arangodb::iresearch::includeStartsWithInLevenshtein(filter, name,
+                                                            prefixes.back().second)) {
+      return {};
+    }
 
     if (isMultiPrefix) {
       auto& minMatchFilter = filter->add<irs::Or>();
       minMatchFilter.min_match_count(static_cast<size_t>(minMatchCount));
+      minMatchFilter.boost(filterCtx.boost);
       // become a new root
       filter = &minMatchFilter;
     }
 
     for (size_t i = 0, size = prefixes.size(); i < size; ++i) {
       auto& prefixFilter = filter->add<irs::by_prefix>();
+      if (!isMultiPrefix) {
+        TRI_ASSERT(prefixes.size() == 1);
+        prefixFilter.boost(filterCtx.boost);
+      }
       if (i + 1 < size) {
         *prefixFilter.mutable_field() = name;
       } else {

diff --git a/arangod/IResearch/IResearchFilterFactory.h b/arangod/IResearch/IResearchFilterFactory.h
@@ -24,6 +24,8 @@
 
 #pragma once
 
+#include "IResearchFilterOptimization.h"
+
 #include "VocBase/voc-types.h"
 
 #include "search/filter.hpp"