<commit_before>////////////////////////////////////////////////////////////////////////////////
/// @brief rules for the query optimizer
///
/// @file arangod/Aql/OptimizerRules.cpp
///
/// DISCLAIMER
///
/// Copyright 2010-2014 triagens GmbH, Cologne, Germany
///
/// Licensed under the Apache License, Version 2.0 (the "License");
/// you may not use this file except in compliance with the License.
/// You may obtain a copy of the License at
///
///     http://www.apache.org/licenses/LICENSE-2.0
///
/// Unless required by applicable law or agreed to in writing, software
/// distributed under the License is distributed on an "AS IS" BASIS,
/// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
/// See the License for the specific language governing permissions and
/// limitations under the License.
///
/// Copyright holder is triAGENS GmbH, Cologne, Germany
///
/// @author <NAME>
/// @author Copyright 2014, triagens GmbH, Cologne, Germany
////////////////////////////////////////////////////////////////////////////////

#include "Aql/OptimizerRules.h"
#include "Aql/ExecutionNode.h"
#include "Aql/Indexes.h"
#include "Aql/Variable.h"

using namespace triagens::aql;
using Json = triagens::basics::Json;
using EN   = triagens::aql::ExecutionNode;

// -----------------------------------------------------------------------------
// --SECTION--                                           rules for the optimizer
// -----------------------------------------------------------------------------

////////////////////////////////////////////////////////////////////////////////
/// @brief remove redundant sorts
/// this rule modifies the plan in place:
/// - sorts that are covered by earlier sorts will be removed
////////////////////////////////////////////////////////////////////////////////

int triagens::aql::removeRedundantSorts (Optimizer* opt, 
                                         ExecutionPlan* plan,
                                         Optimizer::Rule const* rule) { 
  std::vector<ExecutionNode*> nodes = plan->findNodesOfType(triagens::aql::ExecutionNode::SORT, true);
  std::unordered_set<ExecutionNode*> toUnlink;
  
  for (auto n : nodes) {
    auto sortInfo = static_cast<SortNode*>(n)->getSortInformation(plan);

    if (sortInfo.isValid && ! sortInfo.criteria.empty()) {
      // we found a sort that we can understand
    
      std::vector<ExecutionNode*> stack;
      for (auto dep : n->getDependencies()) {
        stack.push_back(dep);
      }

      while (! stack.empty()) {
        auto current = stack.back();
        stack.pop_back();

        if (current->getType() == triagens::aql::ExecutionNode::SORT) {
          // we found another sort. now check if they are compatible!
          auto other = static_cast<SortNode*>(current)->getSortInformation(plan);

          if (sortInfo.isCoveredBy(other)) {
            // the sort at the start of the pipeline makes the sort at the end
            // superfluous, so we'll remove it
            toUnlink.insert(n);
            break;
          }
        }

        auto deps = current->getDependencies();
        if (deps.size() != 1) {
          // node either has no or more than one dependency. we don't know what to do and must abort
          // note: this will also handle Singleton nodes
          break;
        }
      
        for (auto dep : deps) {
          stack.push_back(dep);
        }
      }
    }
  }
            
  if (! toUnlink.empty()) {
    plan->unlinkNodes(toUnlink);
    plan->findVarUsage();
  }
  
  opt->addPlan(plan, rule->level, ! toUnlink.empty());

  return TRI_ERROR_NO_ERROR;
}

////////////////////////////////////////////////////////////////////////////////
/// @brief remove all unnecessary filters
/// this rule modifies the plan in place:
/// - filters that are always true are removed completely
/// - filters that are always false will be replaced by a NoResults node
////////////////////////////////////////////////////////////////////////////////

int triagens::aql::removeUnnecessaryFiltersRule (Optimizer* opt, 
                                                 ExecutionPlan* plan, 
                                                 Optimizer::Rule const* rule) {
  bool modified = false;
  std::unordered_set<ExecutionNode*> toUnlink;
  // should we enter subqueries??
  std::vector<ExecutionNode*> nodes = plan->findNodesOfType(triagens::aql::ExecutionNode::FILTER, true);
  
  for (auto n : nodes) {
    // filter nodes always have one input variable
    auto varsUsedHere = n->getVariablesUsedHere();
    TRI_ASSERT(varsUsedHere.size() == 1);

    // now check who introduced our variable
    auto variable = varsUsedHere[0];
    auto setter = plan->getVarSetBy(variable->id);

    if (setter == nullptr || 
        setter->getType() != triagens::aql::ExecutionNode::CALCULATION) {
      // filter variable was not introduced by a calculation. 
      continue;
    }

    // filter variable was introduced a CalculationNode. now check the expression
    auto s = static_cast<CalculationNode*>(setter);
    auto root = s->expression()->node();

    if (! root->isConstant()) {
      // filter expression can only be evaluated at runtime
      continue;
    }

    // filter expression is constant and thus cannot throw
    // we can now evaluate it safely
    TRI_ASSERT(! s->expression()->canThrow());

    if (root->toBoolean()) {
      // filter is always true
      // remove filter node and merge with following node
      toUnlink.insert(n);
      modified = true;
    }
    else {
      // filter is always false
      // now insert a NoResults node below it
      auto noResults = new NoResultsNode(plan->nextId());
      plan->registerNode(noResults);
      plan->replaceNode(n, noResults);
      modified = true;
    }
  }
  
  if (! toUnlink.empty()) {
    plan->unlinkNodes(toUnlink);
    plan->findVarUsage();
  }
  
  opt->addPlan(plan, rule->level, modified);

  return TRI_ERROR_NO_ERROR;
}

////////////////////////////////////////////////////////////////////////////////
/// @brief move calculations up in the plan
/// this rule modifies the plan in place
/// it aims to move up calculations as far up in the plan as possible, to 
/// avoid redundant calculations in inner loops
////////////////////////////////////////////////////////////////////////////////

int triagens::aql::moveCalculationsUpRule (Optimizer* opt, 
                                           ExecutionPlan* plan, 
                                           Optimizer::Rule const* rule) {
  std::vector<ExecutionNode*> nodes = plan->findNodesOfType(triagens::aql::ExecutionNode::CALCULATION, true);
  bool modified = false;
  
  for (auto n : nodes) {
    auto nn = static_cast<CalculationNode*>(n);
    if (nn->expression()->canThrow()) {
      // we will only move expressions up that cannot throw
      continue;
    }

    auto const neededVars = n->getVariablesUsedHere();

    std::vector<ExecutionNode*> stack;
    for (auto dep : n->getDependencies()) {
      stack.push_back(dep);
    }

    while (! stack.empty()) {
      auto current = stack.back();
      stack.pop_back();

      bool found = false;

      auto&& varsSet = current->getVariablesSetHere();
      for (auto v : varsSet) {
        for (auto it = neededVars.begin(); it != neededVars.end(); ++it) {
          if ((*it)->id == v->id) {
            // shared variable, cannot move up any more
            found = true;
            break;
          }
        }
      }

      if (found) {
        // done with optimizing this calculation node
        break;
      }
        
      auto deps = current->getDependencies();
      if (deps.size() != 1) {
        // node either has no or more than one dependency. we don't know what to do and must abort
        // note: this will also handle Singleton nodes
        break;
      }
      
      for (auto dep : deps) {
        stack.push_back(dep);
      }

      // first, unlink the calculation from the plan
      plan->unlinkNode(n);
      // and re-insert into before the current node
      plan->insertDependency(current, n);
      modified = true;
    }

  }
  
  if (modified) {
    plan->findVarUsage();
  }
  
  opt->addPlan(plan, rule->level, modified);

  return TRI_ERROR_NO_ERROR;
}

////////////////////////////////////////////////////////////////////////////////
/// @brief move filters up in the plan
/// this rule modifies the plan in place
/// filters are moved as far up in the plan as possible to make result sets
/// as small as possible as early as possible
/// filters are not pushed beyond limits
////////////////////////////////////////////////////////////////////////////////

int triagens::aql::moveFiltersUpRule (Optimizer* opt, 
                                      ExecutionPlan* plan,
                                      Optimizer::Rule const* rule) {
  std::vector<ExecutionNode*> nodes = plan->findNodesOfType(triagens::aql::ExecutionNode::FILTER, true);
  bool modified = false;
  
  for (auto n : nodes) {
    auto neededVars = n->getVariablesUsedHere();
    TRI_ASSERT(neededVars.size() == 1);

    std::vector<ExecutionNode*> stack;
    for (auto dep : n->getDependencies()) {
      stack.push_back(dep);
    }

    while (! stack.empty()) {
      auto current = stack.back();
      stack.pop_back();

      if (current->getType() == triagens::aql::ExecutionNode::LIMIT) {
        // cannot push a filter beyond a LIMIT node
        break;
      }

      bool found = false;

      auto&& varsSet = current->getVariablesSetHere();
      for (auto v : varsSet) {
        for (auto it = neededVars.begin(); it != neededVars.end(); ++it) {
          if ((*it)->id == v->id) {
            // shared variable, cannot move up any more
            found = true;
            break;
          }
        }
      }

      if (found) {
        // done with optimizing this calculation node
        break;
      }
        
      auto deps = current->getDependencies();
      if (deps.size() != 1) {
        // node either has no or more than one dependency. we don't know what to do and must abort
        // note: this will also handle Singleton nodes
        break;
      }
      
      for (auto dep : deps) {
        stack.push_back(dep);
      }

      // first, unlink the filter from the plan
      plan->unlinkNode(n);
      // and re-insert into plan in front of the current node
      plan->insertDependency(current, n);
      modified = true;
    }

  }
  
  if (modified) {
    plan->findVarUsage();
  }
  
  opt->addPlan(plan, rule->level, modified);

  return TRI_ERROR_NO_ERROR;
}

////////////////////////////////////////////////////////////////////////////////
/// @brief remove CalculationNode(s) that are never needed
/// this modifies an existing plan in place
////////////////////////////////////////////////////////////////////////////////

int triagens::aql::removeUnnecessaryCalculationsRule (Optimizer* opt, 
                                                      ExecutionPlan* plan,
                                                      Optimizer::Rule const* rule) {
  std::vector<ExecutionNode*> nodes
    = plan->findNodesOfType(triagens::aql::ExecutionNode::CALCULATION, true);
  std::unordered_set<ExecutionNode*> toUnlink;
  for (auto n : nodes) {
    auto nn = static_cast<CalculationNode*>(n);

    if (nn->expression()->canThrow() ||
        ! nn->expression()->isDeterministic()) {
      // If this node can throw or is non-deterministic, we must not optimize it away!
      continue;
    }

    auto outvar = n->getVariablesSetHere();
    TRI_ASSERT(outvar.size() == 1);
    auto varsUsedLater = n->getVarsUsedLater();

    if (varsUsedLater.find(outvar[0]) == varsUsedLater.end()) {
      // The variable whose value is calculated here is not used at
      // all further down the pipeline! We remove the whole
      // calculation node, 
      toUnlink.insert(n);
    }
  }

  if (! toUnlink.empty()) {
    plan->unlinkNodes(toUnlink);
    plan->findVarUsage();
  }

  opt->addPlan(plan, rule->level, ! toUnlink.empty());

  return TRI_ERROR_NO_ERROR;
}

////////////////////////////////////////////////////////////////////////////////
/// @brief prefer IndexRange nodes over EnumerateCollection nodes
////////////////////////////////////////////////////////////////////////////////

class FilterToEnumCollFinder : public WalkerWorker<ExecutionNode> {
  RangesInfo* _ranges;
  Optimizer* _opt;
  ExecutionPlan* _plan;
  std::unordered_set<VariableId> _varIds;
  bool _canThrow; 
  int _level;
  
  public:

    FilterToEnumCollFinder (Optimizer* opt, ExecutionPlan* plan, Variable const* var, int level) 
      : _opt(opt),
        _plan(plan), 
        _canThrow(false),
        _level(level) {
      _ranges = new RangesInfo();
      _varIds.insert(var->id);
    };

    ~FilterToEnumCollFinder () {
      delete _ranges;
    }

    bool before (ExecutionNode* en) {
      _canThrow = (_canThrow || en->canThrow()); // can any node walked over throw?

      switch (en->getType()) {
        case EN::ENUMERATE_LIST:
          break;
        case EN::CALCULATION: {
          auto outvar = en->getVariablesSetHere();
          TRI_ASSERT(outvar.size() == 1);
          if (_varIds.find(outvar[0]->id) != _varIds.end()) {
            auto node = static_cast<CalculationNode*>(en);
            std::string attr;
            std::string enumCollVar;
            buildRangeInfo(node->expression()->node(), enumCollVar, attr);
          }
          break;
        }
        case EN::SUBQUERY:        
          break;
        case EN::FILTER:{
          std::vector<Variable const*> inVar = en->getVariablesUsedHere();
          TRI_ASSERT(inVar.size() == 1);
          _varIds.insert(inVar[0]->id);
          break;
        }
        case EN::INTERSECTION:
        case EN::SINGLETON:
        case EN::AGGREGATE:
        case EN::LOOKUP_JOIN:
        case EN::MERGE_JOIN:
        case EN::LOOKUP_INDEX_UNIQUE:
        case EN::LOOKUP_INDEX_RANGE:
        case EN::LOOKUP_FULL_COLLECTION:
        case EN::CONCATENATION:
        case EN::MERGE:
        case EN::REMOTE:
        case EN::INSERT:
        case EN::REMOVE:
        case EN::REPLACE:
        case EN::UPDATE:
        case EN::RETURN:
        case EN::NORESULTS:
        case EN::ILLEGAL:
          break;
        case EN::LIMIT:           
          // if we meet a limit node between a filter and an enumerate collection,
          // we abort . . . 
          return true;
        case EN::SORT:
        case EN::INDEX_RANGE:
          break;
        case EN::ENUMERATE_COLLECTION:{
          auto node = static_cast<EnumerateCollectionNode*>(en);
          auto var = node->getVariablesSetHere()[0];  // should only be 1
          auto map = _ranges->find(var->name);        // check if we have any ranges with this var
          
          if (map != nullptr) {
            // check the first components of <map> against indexes of <node> . . .
            std::unordered_set<std::string> attrs;
            
            bool valid = true;     // are all the range infos valid
            bool equality = true;  // are all the range infos equalities

            for(auto x: *map) {
              valid &= x.second._valid; 
              if (!valid) {
                break;
              }
              equality &= x.second.is1ValueRangeInfo();
              attrs.insert(x.first);
            }

            if (! _canThrow) {
              if (! valid) { // ranges are not valid . . . 
                
                auto newPlan = _plan->clone();
                try {
                  auto parents = newPlan->getNodeById(node->id())->getParents();
                  for (auto x: parents) {
                    auto noRes = new NoResultsNode(newPlan->nextId());
                    newPlan->registerNode(noRes);
                    newPlan->insertDependency(x, noRes);
                    _opt->addPlan(newPlan, _level, true);
                  }
                }
                catch (...) {
                  delete newPlan;
                  throw;
                }
              }
              else {
                std::vector<TRI_index_t*> idxs;
                std::vector<size_t> prefixes;
                // {idxs.at(i)->_fields[0]..idxs.at(i)->_fields[prefixes.at(i)]}
                // is a subset of <attrs>

                node->getIndexesForIndexRangeNode(attrs, idxs, prefixes);

                // make one new plan for every index in <idxs> that replaces the
                // enumerate collection node with a RangeIndexNode . . . 
                
                for (size_t i = 0; i < idxs.size(); i++) {
                  std::vector<std::vector<RangeInfo>> rangeInfo;
                  rangeInfo.push_back(std::vector<RangeInfo>());
                  
                  // ranges must be valid and all comparisons == if hash index or ==
                  // followed by a single <, >, >=, or <= if a skip index in the
                  // order of the fields of the index.
                  auto idx = idxs.at(i);
                  if (idx->_type == TRI_IDX_TYPE_HASH_INDEX && equality) {
                    for (size_t j = 0; j < idx->_fields._length; j++) {
                      auto range = map->find(std::string(idx->_fields._buffer[j]));
                      rangeInfo.at(0).push_back(range->second);
                    }
                  }
                  
                  if (idx->_type == TRI_IDX_TYPE_SKIPLIST_INDEX) {
                    size_t j = 0;
                    auto range = map->find(std::string(idx->_fields._buffer[0]));
                    rangeInfo.at(0).push_back(range->second);
                    equality = range->second.is1ValueRangeInfo();
                    while (++j < prefixes.at(i) && equality){
                      range = map->find(std::string(idx->_fields._buffer[j]));
                      rangeInfo.at(0).push_back(range->second);
                      equality = equality && range->second.is1ValueRangeInfo();
                    }
                  }
                  
                  if (rangeInfo.at(0).size() != 0) {
                    auto newPlan = _plan->clone();
                    try {
                      ExecutionNode* newNode = new IndexRangeNode(newPlan->nextId(), node->vocbase(), 
                        node->collection(), node->outVariable(), idx, rangeInfo);
                      newPlan->registerNode(newNode);
                      newPlan->replaceNode(newPlan->getNodeById(node->id()), newNode);
                      _opt->addPlan(newPlan, _level, true);
                    }
                    catch (...) {
                      delete newPlan;
                      throw;
                    }
                  }
                }
              }
            }
          }
          break;
        }
      }
      return false;
    }

    void buildRangeInfo (AstNode const* node, std::string& enumCollVar, std::string& attr) {
      if (node->type == NODE_TYPE_REFERENCE) {
        auto x = static_cast<Variable*>(node->getData());
        auto setter = _plan->getVarSetBy(x->id);
        if (setter != nullptr && 
            setter->getType() == triagens::aql::ExecutionNode::ENUMERATE_COLLECTION) {
          enumCollVar = x->name;
        }
        return;
      }
      
      if (node->type == NODE_TYPE_ATTRIBUTE_ACCESS) {
        char const* attributeName = node->getStringValue();
        buildRangeInfo(node->getMember(0), enumCollVar, attr);
        if (! enumCollVar.empty()) {
          attr.append(attributeName);
          attr.push_back('.');
        }
        return;
      }
      
      if (node->type == NODE_TYPE_OPERATOR_BINARY_EQ) {
        auto lhs = node->getMember(0);
        auto rhs = node->getMember(1);
        AstNode const* val;
        AstNode const* nextNode;
        if(rhs->type == NODE_TYPE_ATTRIBUTE_ACCESS && lhs->type == NODE_TYPE_VALUE) {
          val = lhs;
          nextNode = rhs;
        }
        else if (lhs->type == NODE_TYPE_ATTRIBUTE_ACCESS && rhs->type == NODE_TYPE_VALUE) {
          val = rhs;
          nextNode = lhs;
        }
        else {
          val = nullptr;
        }
        
        if (val != nullptr) {
          buildRangeInfo(nextNode, enumCollVar, attr);
          if (! enumCollVar.empty()) {
            _ranges->insert(enumCollVar, attr.substr(0, attr.size() - 1), 
                RangeInfoBound(val, true), RangeInfoBound(val, true));
          }
        }
        attr = "";
        enumCollVar = "";
        return;
      }

      if(node->type == NODE_TYPE_OPERATOR_BINARY_LT || 
         node->type == NODE_TYPE_OPERATOR_BINARY_GT ||
         node->type == NODE_TYPE_OPERATOR_BINARY_LE ||
         node->type == NODE_TYPE_OPERATOR_BINARY_GE) {
        
        bool include = (node->type == NODE_TYPE_OPERATOR_BINARY_LE ||
                        node->type == NODE_TYPE_OPERATOR_BINARY_GE);
        
        auto lhs = node->getMember(0);
        auto rhs = node->getMember(1);
        RangeInfoBound low;
        RangeInfoBound high;
        AstNode *nextNode;

        if (rhs->type == NODE_TYPE_ATTRIBUTE_ACCESS && lhs->type == NODE_TYPE_VALUE) {
          if (node->type == NODE_TYPE_OPERATOR_BINARY_GE ||
              node->type == NODE_TYPE_OPERATOR_BINARY_GT) {
            high.assign(lhs, include);
          } 
          else {
            low.assign(lhs, include);
          }
          nextNode = rhs;
        }
        else if (lhs->type == NODE_TYPE_ATTRIBUTE_ACCESS && rhs->type == NODE_TYPE_VALUE) {
          if (node->type == NODE_TYPE_OPERATOR_BINARY_GE ||
              node->type == NODE_TYPE_OPERATOR_BINARY_GT) {
            low.assign(rhs, include);
          } 
          else {
            high.assign(rhs, include);
          }
          nextNode = lhs;
        }

        if (!low._undefined || !high._undefined) {
          buildRangeInfo(nextNode, enumCollVar, attr);
          if (! enumCollVar.empty()) {
            _ranges->insert(enumCollVar, attr.substr(0, attr.size()-1), low, high);
          }
        }
      }
      
      if (node->type == NODE_TYPE_OPERATOR_BINARY_AND) {
        buildRangeInfo(node->getMember(0), enumCollVar, attr);
        buildRangeInfo(node->getMember(1), enumCollVar, attr);
      }
      attr = "";
      enumCollVar = "";
      return;
    }
};

////////////////////////////////////////////////////////////////////////////////
/// @brief useIndexRange, try to use an index for filtering
////////////////////////////////////////////////////////////////////////////////

int triagens::aql::useIndexRange (Optimizer* opt, 
                                  ExecutionPlan* plan, 
                                  Optimizer::Rule const* rule) {
  
  std::vector<ExecutionNode*> nodes
    = plan->findNodesOfType(triagens::aql::ExecutionNode::FILTER, true);
  
  for (auto n : nodes) {
    auto nn = static_cast<FilterNode*>(n);
    auto invars = nn->getVariablesUsedHere();
    TRI_ASSERT(invars.size() == 1);
    FilterToEnumCollFinder finder(opt, plan, invars[0], rule->level);
    nn->walk(&finder);
  }
  opt->addPlan(plan, rule->level, false);

  return TRI_ERROR_NO_ERROR;
}

////////////////////////////////////////////////////////////////////////////////
/// @brief analyse the sortnode and its calculation nodes
////////////////////////////////////////////////////////////////////////////////

class sortAnalysis {
  using ECN = triagens::aql::EnumerateCollectionNode;

  typedef std::pair<ECN::IndexMatchVec, RangeInfoVec> Range_IndexPair;

  struct sortNodeData {
    bool ASC;
    size_t calculationNodeID;
    std::string variableName;
    std::string attributevec;
  };

  std::vector<sortNodeData*> _sortNodeData;

public:
  size_t const sortNodeID;

////////////////////////////////////////////////////////////////////////////////
/// @brief constructor; fetches the referenced calculation nodes and builds 
///   _sortNodeData for later use.
////////////////////////////////////////////////////////////////////////////////
  sortAnalysis (SortNode * node)
  : sortNodeID(node->id())
  {
    auto sortParams = node->getCalcNodePairs();

    for (size_t n = 0; n < sortParams.size(); n++) {
      auto d = new sortNodeData;
      d->ASC = sortParams[n].second;
      d->calculationNodeID = sortParams[n].first->id();

      if (sortParams[n].first->getType() == EN::CALCULATION) {
        auto cn = static_cast<triagens::aql::CalculationNode*>(sortParams[n].first);
        auto oneSortExpression = cn->expression();
        
        if (oneSortExpression->isAttributeAccess()) {
          auto simpleExpression = oneSortExpression->getMultipleAttributes();
          d->variableName = simpleExpression.first;
          d->attributevec = simpleExpression.second;
        }
      }
      _sortNodeData.push_back(d);
    }
  }

  ~sortAnalysis () {
    for (auto x : _sortNodeData){
      delete x;
    }
  }

////////////////////////////////////////////////////////////////////////////////
/// @brief checks the whether we only have simple calculation nodes
////////////////////////////////////////////////////////////////////////////////
  bool isAnalyzeable () {
    if (_sortNodeData.size() == 0) {
      return false;
    }
    size_t j;
    for (j = 0; j < _sortNodeData.size(); j ++) {
      if (_sortNodeData[j]->variableName.length() == 0) {
        return false;
      }
    }

    /*  are we all from one variable? * /
    int j = 0;
    for (; (j < _sortNodeData.size() && 
            sortNodeData[j]->variableName.length() == 0);
         j ++);
    last = sortNodeData[j];
    j ++;
    for (j < _sortNodeData.size(); j++) {
      if (sortNodeData[j]->variableName.length)
      if (last->variableName != sortNodeData[j]->variableName) {
        return false;
      }
      last = sortNodeData[j];
    }
     alle nodes gesetzt, ja.
    */ 
    return true;
  }

////////////////////////////////////////////////////////////////////////////////
/// @brief checks whether our calculation nodes reference variableName; 
/// @returns pair used for further processing with the indices.
////////////////////////////////////////////////////////////////////////////////
  Range_IndexPair getAttrsForVariableName (std::string &variableName) {
    ECN::IndexMatchVec v;
    RangeInfoVec rangeInfo;

    for (size_t j = 0; j < _sortNodeData.size(); j ++) {
      if (_sortNodeData[j]->variableName != variableName) {
        return std::make_pair(v, rangeInfo); // for now, no mixed support.
      }
    }
    for (size_t j = 0; j < _sortNodeData.size(); j ++) {
      v.push_back(std::make_pair(_sortNodeData[j]->attributevec,
                                 _sortNodeData[j]->ASC));
      rangeInfo.push_back(std::vector<RangeInfo>());
    }
    return std::make_pair(v, rangeInfo);
  }

////////////////////////////////////////////////////////////////////////////////
/// @brief removes the sortNode and its referenced Calculationnodes from the plan.
////////////////////////////////////////////////////////////////////////////////
  void removeSortNodeFromPlan (ExecutionPlan *newPlan) {
    newPlan->unlinkNode(newPlan->getNodeById(sortNodeID));

    for (auto idToRemove = _sortNodeData.begin();
         idToRemove != _sortNodeData.end();
         ++idToRemove) {
      newPlan->unlinkNode(newPlan->getNodeById((*idToRemove)->calculationNodeID));
    }
  }
};

class sortToIndexNode : public WalkerWorker<ExecutionNode> {
  using ECN = triagens::aql::EnumerateCollectionNode;<commit_msg>SortIndex: move the unlinking of the sort attributes after unlinking the sort itself<commit_after>////////////////////////////////////////////////////////////////////////////////
/// @brief rules for the query optimizer
///
/// @file arangod/Aql/OptimizerRules.cpp
///
/// DISCLAIMER
///
/// Copyright 2010-2014 triagens GmbH, Cologne, Germany
///
/// Licensed under the Apache License, Version 2.0 (the "License");
/// you may not use this file except in compliance with the License.
/// You may obtain a copy of the License at
///
///     http://www.apache.org/licenses/LICENSE-2.0
///
/// Unless required by applicable law or agreed to in writing, software
/// distributed under the License is distributed on an "AS IS" BASIS,
/// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
/// See the License for the specific language governing permissions and
/// limitations under the License.
///
/// Copyright holder is triAGENS GmbH, Cologne, Germany
///
/// @author <NAME>
/// @author Copyright 2014, triagens GmbH, Cologne, Germany
////////////////////////////////////////////////////////////////////////////////

#include "Aql/OptimizerRules.h"
#include "Aql/ExecutionNode.h"
#include "Aql/Indexes.h"
#include "Aql/Variable.h"

using namespace triagens::aql;
using Json = triagens::basics::Json;
using EN   = triagens::aql::ExecutionNode;

// -----------------------------------------------------------------------------
// --SECTION--                                           rules for the optimizer
// -----------------------------------------------------------------------------

////////////////////////////////////////////////////////////////////////////////
/// @brief remove redundant sorts
/// this rule modifies the plan in place:
/// - sorts that are covered by earlier sorts will be removed
////////////////////////////////////////////////////////////////////////////////

int triagens::aql::removeRedundantSorts (Optimizer* opt, 
                                         ExecutionPlan* plan,
                                         Optimizer::Rule const* rule) { 
  std::vector<ExecutionNode*> nodes = plan->findNodesOfType(triagens::aql::ExecutionNode::SORT, true);
  std::unordered_set<ExecutionNode*> toUnlink;
  
  for (auto n : nodes) {
    auto sortInfo = static_cast<SortNode*>(n)->getSortInformation(plan);

    if (sortInfo.isValid && ! sortInfo.criteria.empty()) {
      // we found a sort that we can understand
    
      std::vector<ExecutionNode*> stack;
      for (auto dep : n->getDependencies()) {
        stack.push_back(dep);
      }

      while (! stack.empty()) {
        auto current = stack.back();
        stack.pop_back();

        if (current->getType() == triagens::aql::ExecutionNode::SORT) {
          // we found another sort. now check if they are compatible!
          auto other = static_cast<SortNode*>(current)->getSortInformation(plan);

          if (sortInfo.isCoveredBy(other)) {
            // the sort at the start of the pipeline makes the sort at the end
            // superfluous, so we'll remove it
            toUnlink.insert(n);
            break;
          }
        }

        auto deps = current->getDependencies();
        if (deps.size() != 1) {
          // node either has no or more than one dependency. we don't know what to do and must abort
          // note: this will also handle Singleton nodes
          break;
        }
      
        for (auto dep : deps) {
          stack.push_back(dep);
        }
      }
    }
  }
            
  if (! toUnlink.empty()) {
    plan->unlinkNodes(toUnlink);
    plan->findVarUsage();
  }
  
  opt->addPlan(plan, rule->level, ! toUnlink.empty());

  return TRI_ERROR_NO_ERROR;
}

////////////////////////////////////////////////////////////////////////////////
/// @brief remove all unnecessary filters
/// this rule modifies the plan in place:
/// - filters that are always true are removed completely
/// - filters that are always false will be replaced by a NoResults node
////////////////////////////////////////////////////////////////////////////////

int triagens::aql::removeUnnecessaryFiltersRule (Optimizer* opt, 
                                                 ExecutionPlan* plan, 
                                                 Optimizer::Rule const* rule) {
  bool modified = false;
  std::unordered_set<ExecutionNode*> toUnlink;
  // should we enter subqueries??
  std::vector<ExecutionNode*> nodes = plan->findNodesOfType(triagens::aql::ExecutionNode::FILTER, true);
  
  for (auto n : nodes) {
    // filter nodes always have one input variable
    auto varsUsedHere = n->getVariablesUsedHere();
    TRI_ASSERT(varsUsedHere.size() == 1);

    // now check who introduced our variable
    auto variable = varsUsedHere[0];
    auto setter = plan->getVarSetBy(variable->id);

    if (setter == nullptr || 
        setter->getType() != triagens::aql::ExecutionNode::CALCULATION) {
      // filter variable was not introduced by a calculation. 
      continue;
    }

    // filter variable was introduced a CalculationNode. now check the expression
    auto s = static_cast<CalculationNode*>(setter);
    auto root = s->expression()->node();

    if (! root->isConstant()) {
      // filter expression can only be evaluated at runtime
      continue;
    }

    // filter expression is constant and thus cannot throw
    // we can now evaluate it safely
    TRI_ASSERT(! s->expression()->canThrow());

    if (root->toBoolean()) {
      // filter is always true
      // remove filter node and merge with following node
      toUnlink.insert(n);
      modified = true;
    }
    else {
      // filter is always false
      // now insert a NoResults node below it
      auto noResults = new NoResultsNode(plan->nextId());
      plan->registerNode(noResults);
      plan->replaceNode(n, noResults);
      modified = true;
    }
  }
  
  if (! toUnlink.empty()) {
    plan->unlinkNodes(toUnlink);
    plan->findVarUsage();
  }
  
  opt->addPlan(plan, rule->level, modified);

  return TRI_ERROR_NO_ERROR;
}

////////////////////////////////////////////////////////////////////////////////
/// @brief move calculations up in the plan
/// this rule modifies the plan in place
/// it aims to move up calculations as far up in the plan as possible, to 
/// avoid redundant calculations in inner loops
////////////////////////////////////////////////////////////////////////////////

int triagens::aql::moveCalculationsUpRule (Optimizer* opt, 
                                           ExecutionPlan* plan, 
                                           Optimizer::Rule const* rule) {
  std::vector<ExecutionNode*> nodes = plan->findNodesOfType(triagens::aql::ExecutionNode::CALCULATION, true);
  bool modified = false;
  
  for (auto n : nodes) {
    auto nn = static_cast<CalculationNode*>(n);
    if (nn->expression()->canThrow()) {
      // we will only move expressions up that cannot throw
      continue;
    }

    auto const neededVars = n->getVariablesUsedHere();

    std::vector<ExecutionNode*> stack;
    for (auto dep : n->getDependencies()) {
      stack.push_back(dep);
    }

    while (! stack.empty()) {
      auto current = stack.back();
      stack.pop_back();

      bool found = false;

      auto&& varsSet = current->getVariablesSetHere();
      for (auto v : varsSet) {
        for (auto it = neededVars.begin(); it != neededVars.end(); ++it) {
          if ((*it)->id == v->id) {
            // shared variable, cannot move up any more
            found = true;
            break;
          }
        }
      }

      if (found) {
        // done with optimizing this calculation node
        break;
      }
        
      auto deps = current->getDependencies();
      if (deps.size() != 1) {
        // node either has no or more than one dependency. we don't know what to do and must abort
        // note: this will also handle Singleton nodes
        break;
      }
      
      for (auto dep : deps) {
        stack.push_back(dep);
      }

      // first, unlink the calculation from the plan
      plan->unlinkNode(n);
      // and re-insert into before the current node
      plan->insertDependency(current, n);
      modified = true;
    }

  }
  
  if (modified) {
    plan->findVarUsage();
  }
  
  opt->addPlan(plan, rule->level, modified);

  return TRI_ERROR_NO_ERROR;
}

////////////////////////////////////////////////////////////////////////////////
/// @brief move filters up in the plan
/// this rule modifies the plan in place
/// filters are moved as far up in the plan as possible to make result sets
/// as small as possible as early as possible
/// filters are not pushed beyond limits
////////////////////////////////////////////////////////////////////////////////

int triagens::aql::moveFiltersUpRule (Optimizer* opt, 
                                      ExecutionPlan* plan,
                                      Optimizer::Rule const* rule) {
  std::vector<ExecutionNode*> nodes = plan->findNodesOfType(triagens::aql::ExecutionNode::FILTER, true);
  bool modified = false;
  
  for (auto n : nodes) {
    auto neededVars = n->getVariablesUsedHere();
    TRI_ASSERT(neededVars.size() == 1);

    std::vector<ExecutionNode*> stack;
    for (auto dep : n->getDependencies()) {
      stack.push_back(dep);
    }

    while (! stack.empty()) {
      auto current = stack.back();
      stack.pop_back();

      if (current->getType() == triagens::aql::ExecutionNode::LIMIT) {
        // cannot push a filter beyond a LIMIT node
        break;
      }

      bool found = false;

      auto&& varsSet = current->getVariablesSetHere();
      for (auto v : varsSet) {
        for (auto it = neededVars.begin(); it != neededVars.end(); ++it) {
          if ((*it)->id == v->id) {
            // shared variable, cannot move up any more
            found = true;
            break;
          }
        }
      }

      if (found) {
        // done with optimizing this calculation node
        break;
      }
        
      auto deps = current->getDependencies();
      if (deps.size() != 1) {
        // node either has no or more than one dependency. we don't know what to do and must abort
        // note: this will also handle Singleton nodes
        break;
      }
      
      for (auto dep : deps) {
        stack.push_back(dep);
      }

      // first, unlink the filter from the plan
      plan->unlinkNode(n);
      // and re-insert into plan in front of the current node
      plan->insertDependency(current, n);
      modified = true;
    }

  }
  
  if (modified) {
    plan->findVarUsage();
  }
  
  opt->addPlan(plan, rule->level, modified);

  return TRI_ERROR_NO_ERROR;
}

////////////////////////////////////////////////////////////////////////////////
/// @brief remove CalculationNode(s) that are never needed
/// this modifies an existing plan in place
////////////////////////////////////////////////////////////////////////////////

int triagens::aql::removeUnnecessaryCalculationsRule (Optimizer* opt, 
                                                      ExecutionPlan* plan,
                                                      Optimizer::Rule const* rule) {
  std::vector<ExecutionNode*> nodes
    = plan->findNodesOfType(triagens::aql::ExecutionNode::CALCULATION, true);
  std::unordered_set<ExecutionNode*> toUnlink;
  for (auto n : nodes) {
    auto nn = static_cast<CalculationNode*>(n);

    if (nn->expression()->canThrow() ||
        ! nn->expression()->isDeterministic()) {
      // If this node can throw or is non-deterministic, we must not optimize it away!
      continue;
    }

    auto outvar = n->getVariablesSetHere();
    TRI_ASSERT(outvar.size() == 1);
    auto varsUsedLater = n->getVarsUsedLater();

    if (varsUsedLater.find(outvar[0]) == varsUsedLater.end()) {
      // The variable whose value is calculated here is not used at
      // all further down the pipeline! We remove the whole
      // calculation node, 
      toUnlink.insert(n);
    }
  }

  if (! toUnlink.empty()) {
    plan->unlinkNodes(toUnlink);
    plan->findVarUsage();
  }

  opt->addPlan(plan, rule->level, ! toUnlink.empty());

  return TRI_ERROR_NO_ERROR;
}

////////////////////////////////////////////////////////////////////////////////
/// @brief prefer IndexRange nodes over EnumerateCollection nodes
////////////////////////////////////////////////////////////////////////////////

class FilterToEnumCollFinder : public WalkerWorker<ExecutionNode> {
  RangesInfo* _ranges;
  Optimizer* _opt;
  ExecutionPlan* _plan;
  std::unordered_set<VariableId> _varIds;
  bool _canThrow; 
  int _level;
  
  public:

    FilterToEnumCollFinder (Optimizer* opt, ExecutionPlan* plan, Variable const* var, int level) 
      : _opt(opt),
        _plan(plan), 
        _canThrow(false),
        _level(level) {
      _ranges = new RangesInfo();
      _varIds.insert(var->id);
    };

    ~FilterToEnumCollFinder () {
      delete _ranges;
    }

    bool before (ExecutionNode* en) {
      _canThrow = (_canThrow || en->canThrow()); // can any node walked over throw?

      switch (en->getType()) {
        case EN::ENUMERATE_LIST:
          break;
        case EN::CALCULATION: {
          auto outvar = en->getVariablesSetHere();
          TRI_ASSERT(outvar.size() == 1);
          if (_varIds.find(outvar[0]->id) != _varIds.end()) {
            auto node = static_cast<CalculationNode*>(en);
            std::string attr;
            std::string enumCollVar;
            buildRangeInfo(node->expression()->node(), enumCollVar, attr);
          }
          break;
        }
        case EN::SUBQUERY:        
          break;
        case EN::FILTER:{
          std::vector<Variable const*> inVar = en->getVariablesUsedHere();
          TRI_ASSERT(inVar.size() == 1);
          _varIds.insert(inVar[0]->id);
          break;
        }
        case EN::INTERSECTION:
        case EN::SINGLETON:
        case EN::AGGREGATE:
        case EN::LOOKUP_JOIN:
        case EN::MERGE_JOIN:
        case EN::LOOKUP_INDEX_UNIQUE:
        case EN::LOOKUP_INDEX_RANGE:
        case EN::LOOKUP_FULL_COLLECTION:
        case EN::CONCATENATION:
        case EN::MERGE:
        case EN::REMOTE:
        case EN::INSERT:
        case EN::REMOVE:
        case EN::REPLACE:
        case EN::UPDATE:
        case EN::RETURN:
        case EN::NORESULTS:
        case EN::ILLEGAL:
          break;
        case EN::LIMIT:           
          // if we meet a limit node between a filter and an enumerate collection,
          // we abort . . . 
          return true;
        case EN::SORT:
        case EN::INDEX_RANGE:
          break;
        case EN::ENUMERATE_COLLECTION:{
          auto node = static_cast<EnumerateCollectionNode*>(en);
          auto var = node->getVariablesSetHere()[0];  // should only be 1
          auto map = _ranges->find(var->name);        // check if we have any ranges with this var
          
          if (map != nullptr) {
            // check the first components of <map> against indexes of <node> . . .
            std::unordered_set<std::string> attrs;
            
            bool valid = true;     // are all the range infos valid
            bool equality = true;  // are all the range infos equalities

            for(auto x: *map) {
              valid &= x.second._valid; 
              if (!valid) {
                break;
              }
              equality &= x.second.is1ValueRangeInfo();
              attrs.insert(x.first);
            }

            if (! _canThrow) {
              if (! valid) { // ranges are not valid . . . 
                
                auto newPlan = _plan->clone();
                try {
                  auto parents = newPlan->getNodeById(node->id())->getParents();
                  for (auto x: parents) {
                    auto noRes = new NoResultsNode(newPlan->nextId());
                    newPlan->registerNode(noRes);
                    newPlan->insertDependency(x, noRes);
                    _opt->addPlan(newPlan, _level, true);
                  }
                }
                catch (...) {
                  delete newPlan;
                  throw;
                }
              }
              else {
                std::vector<TRI_index_t*> idxs;
                std::vector<size_t> prefixes;
                // {idxs.at(i)->_fields[0]..idxs.at(i)->_fields[prefixes.at(i)]}
                // is a subset of <attrs>

                node->getIndexesForIndexRangeNode(attrs, idxs, prefixes);

                // make one new plan for every index in <idxs> that replaces the
                // enumerate collection node with a RangeIndexNode . . . 
                
                for (size_t i = 0; i < idxs.size(); i++) {
                  std::vector<std::vector<RangeInfo>> rangeInfo;
                  rangeInfo.push_back(std::vector<RangeInfo>());
                  
                  // ranges must be valid and all comparisons == if hash index or ==
                  // followed by a single <, >, >=, or <= if a skip index in the
                  // order of the fields of the index.
                  auto idx = idxs.at(i);
                  if (idx->_type == TRI_IDX_TYPE_HASH_INDEX && equality) {
                    for (size_t j = 0; j < idx->_fields._length; j++) {
                      auto range = map->find(std::string(idx->_fields._buffer[j]));
                      rangeInfo.at(0).push_back(range->second);
                    }
                  }
                  
                  if (idx->_type == TRI_IDX_TYPE_SKIPLIST_INDEX) {
                    size_t j = 0;
                    auto range = map->find(std::string(idx->_fields._buffer[0]));
                    rangeInfo.at(0).push_back(range->second);
                    equality = range->second.is1ValueRangeInfo();
                    while (++j < prefixes.at(i) && equality){
                      range = map->find(std::string(idx->_fields._buffer[j]));
                      rangeInfo.at(0).push_back(range->second);
                      equality = equality && range->second.is1ValueRangeInfo();
                    }
                  }
                  
                  if (rangeInfo.at(0).size() != 0) {
                    auto newPlan = _plan->clone();
                    try {
                      ExecutionNode* newNode = new IndexRangeNode(newPlan->nextId(), node->vocbase(), 
                        node->collection(), node->outVariable(), idx, rangeInfo);
                      newPlan->registerNode(newNode);
                      newPlan->replaceNode(newPlan->getNodeById(node->id()), newNode);
                      _opt->addPlan(newPlan, _level, true);
                    }
                    catch (...) {
                      delete newPlan;
                      throw;
                    }
                  }
                }
              }
            }
          }
          break;
        }
      }
      return false;
    }

    void buildRangeInfo (AstNode const* node, std::string& enumCollVar, std::string& attr) {
      if (node->type == NODE_TYPE_REFERENCE) {
        auto x = static_cast<Variable*>(node->getData());
        auto setter = _plan->getVarSetBy(x->id);
        if (setter != nullptr && 
            setter->getType() == triagens::aql::ExecutionNode::ENUMERATE_COLLECTION) {
          enumCollVar = x->name;
        }
        return;
      }
      
      if (node->type == NODE_TYPE_ATTRIBUTE_ACCESS) {
        char const* attributeName = node->getStringValue();
        buildRangeInfo(node->getMember(0), enumCollVar, attr);
        if (! enumCollVar.empty()) {
          attr.append(attributeName);
          attr.push_back('.');
        }
        return;
      }
      
      if (node->type == NODE_TYPE_OPERATOR_BINARY_EQ) {
        auto lhs = node->getMember(0);
        auto rhs = node->getMember(1);
        AstNode const* val;
        AstNode const* nextNode;
        if(rhs->type == NODE_TYPE_ATTRIBUTE_ACCESS && lhs->type == NODE_TYPE_VALUE) {
          val = lhs;
          nextNode = rhs;
        }
        else if (lhs->type == NODE_TYPE_ATTRIBUTE_ACCESS && rhs->type == NODE_TYPE_VALUE) {
          val = rhs;
          nextNode = lhs;
        }
        else {
          val = nullptr;
        }
        
        if (val != nullptr) {
          buildRangeInfo(nextNode, enumCollVar, attr);
          if (! enumCollVar.empty()) {
            _ranges->insert(enumCollVar, attr.substr(0, attr.size() - 1), 
                RangeInfoBound(val, true), RangeInfoBound(val, true));
          }
        }
        attr = "";
        enumCollVar = "";
        return;
      }

      if(node->type == NODE_TYPE_OPERATOR_BINARY_LT || 
         node->type == NODE_TYPE_OPERATOR_BINARY_GT ||
         node->type == NODE_TYPE_OPERATOR_BINARY_LE ||
         node->type == NODE_TYPE_OPERATOR_BINARY_GE) {
        
        bool include = (node->type == NODE_TYPE_OPERATOR_BINARY_LE ||
                        node->type == NODE_TYPE_OPERATOR_BINARY_GE);
        
        auto lhs = node->getMember(0);
        auto rhs = node->getMember(1);
        RangeInfoBound low;
        RangeInfoBound high;
        AstNode *nextNode;

        if (rhs->type == NODE_TYPE_ATTRIBUTE_ACCESS && lhs->type == NODE_TYPE_VALUE) {
          if (node->type == NODE_TYPE_OPERATOR_BINARY_GE ||
              node->type == NODE_TYPE_OPERATOR_BINARY_GT) {
            high.assign(lhs, include);
          } 
          else {
            low.assign(lhs, include);
          }
          nextNode = rhs;
        }
        else if (lhs->type == NODE_TYPE_ATTRIBUTE_ACCESS && rhs->type == NODE_TYPE_VALUE) {
          if (node->type == NODE_TYPE_OPERATOR_BINARY_GE ||
              node->type == NODE_TYPE_OPERATOR_BINARY_GT) {
            low.assign(rhs, include);
          } 
          else {
            high.assign(rhs, include);
          }
          nextNode = lhs;
        }

        if (!low._undefined || !high._undefined) {
          buildRangeInfo(nextNode, enumCollVar, attr);
          if (! enumCollVar.empty()) {
            _ranges->insert(enumCollVar, attr.substr(0, attr.size()-1), low, high);
          }
        }
      }
      
      if (node->type == NODE_TYPE_OPERATOR_BINARY_AND) {
        buildRangeInfo(node->getMember(0), enumCollVar, attr);
        buildRangeInfo(node->getMember(1), enumCollVar, attr);
      }
      attr = "";
      enumCollVar = "";
      return;
    }
};

////////////////////////////////////////////////////////////////////////////////
/// @brief useIndexRange, try to use an index for filtering
////////////////////////////////////////////////////////////////////////////////

int triagens::aql::useIndexRange (Optimizer* opt, 
                                  ExecutionPlan* plan, 
                                  Optimizer::Rule const* rule) {
  
  std::vector<ExecutionNode*> nodes
    = plan->findNodesOfType(triagens::aql::ExecutionNode::FILTER, true);
  
  for (auto n : nodes) {
    auto nn = static_cast<FilterNode*>(n);
    auto invars = nn->getVariablesUsedHere();
    TRI_ASSERT(invars.size() == 1);
    FilterToEnumCollFinder finder(opt, plan, invars[0], rule->level);
    nn->walk(&finder);
  }
  opt->addPlan(plan, rule->level, false);

  return TRI_ERROR_NO_ERROR;
}

////////////////////////////////////////////////////////////////////////////////
/// @brief analyse the sortnode and its calculation nodes
////////////////////////////////////////////////////////////////////////////////

class sortAnalysis {
  using ECN = triagens::aql::EnumerateCollectionNode;

  typedef std::pair<ECN::IndexMatchVec, RangeInfoVec> Range_IndexPair;

  struct sortNodeData {
    bool ASC;
    size_t calculationNodeID;
    std::string variableName;
    std::string attributevec;
  };

  std::vector<sortNodeData*> _sortNodeData;

public:
  size_t const sortNodeID;

////////////////////////////////////////////////////////////////////////////////
/// @brief constructor; fetches the referenced calculation nodes and builds 
///   _sortNodeData for later use.
////////////////////////////////////////////////////////////////////////////////
  sortAnalysis (SortNode * node)
  : sortNodeID(node->id())
  {
    auto sortParams = node->getCalcNodePairs();

    for (size_t n = 0; n < sortParams.size(); n++) {
      auto d = new sortNodeData;
      d->ASC = sortParams[n].second;
      d->calculationNodeID = sortParams[n].first->id();

      if (sortParams[n].first->getType() == EN::CALCULATION) {
        auto cn = static_cast<triagens::aql::CalculationNode*>(sortParams[n].first);
        auto oneSortExpression = cn->expression();
        
        if (oneSortExpression->isAttributeAccess()) {
          auto simpleExpression = oneSortExpression->getMultipleAttributes();
          d->variableName = simpleExpression.first;
          d->attributevec = simpleExpression.second;
        }
      }
      _sortNodeData.push_back(d);
    }
  }

  ~sortAnalysis () {
    for (auto x : _sortNodeData){
      delete x;
    }
  }

////////////////////////////////////////////////////////////////////////////////
/// @brief checks the whether we only have simple calculation nodes
////////////////////////////////////////////////////////////////////////////////
  bool isAnalyzeable () {
    if (_sortNodeData.size() == 0) {
      return false;
    }
    size_t j;
    for (j = 0; j < _sortNodeData.size(); j ++) {
      if (_sortNodeData[j]->variableName.length() == 0) {
        return false;
      }
    }

    /*  are we all from one variable? * /
    int j = 0;
    for (; (j < _sortNodeData.size() && 
            sortNodeData[j]->variableName.length() == 0);
         j ++);
    last = sortNodeData[j];
    j ++;
    for (j < _sortNodeData.size(); j++) {
      if (sortNodeData[j]->variableName.length)
      if (last->variableName != sortNodeData[j]->variableName) {
        return false;
      }
      last = sortNodeData[j];
    }
     alle nodes gesetzt, ja.
    */ 
    return true;
  }

////////////////////////////////////////////////////////////////////////////////
/// @brief checks whether our calculation nodes reference variableName; 
/// @returns pair used for further processing with the indices.
////////////////////////////////////////////////////////////////////////////////
  Range_IndexPair getAttrsForVariableName (std::string &variableName) {
    ECN::IndexMatchVec v;
    RangeInfoVec rangeInfo;

    for (size_t j = 0; j < _sortNodeData.size(); j ++) {
      if (_sortNodeData[j]->variableName != variableName) {
        return std::make_pair(v, rangeInfo); // for now, no mixed support.
      }
    }
    for (size_t j = 0; j < _sortNodeData.size(); j ++) {
      v.push_back(std::make_pair(_sortNodeData[j]->attributevec,
                                 _sortNodeData[j]->ASC));
      rangeInfo.push_back(std::vector<RangeInfo>());
    }
    return std::make_pair(v, rangeInfo);
  }

////////////////////////////////////////////////////////////////////////////////
/// @brief removes the sortNode and its referenced Calculationnodes from the plan.
////////////////////////////////////////////////////////////////////////////////
  void removeSortNodeFromPlan (ExecutionPlan *newPlan) {
    for (auto idToRemove = _sortNodeData.begin();
         idToRemove != _sortNodeData.end();
         ++idToRemove) {
      newPlan->unlinkNode(newPlan->getNodeById((*idToRemove)->calculationNodeID));
    }

    newPlan->unlinkNode(newPlan->getNodeById(sortNodeID));
  }
};

class sortToIndexNode : public WalkerWorker<ExecutionNode> {
  using ECN = triagens::aql::EnumerateCollectionNode;
{'fraction_non_alphanumeric': 0.19174276947657, 'fraction_numerical': 0.0023239347119591858, 'mean_word_length': 1.551772063933287, 'pattern_counts': {'":': 0, '<': 105, '<?xml version=': 0, '>': 447, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 46, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7223644', 'n_tokens_mistral': 14945, 'n_tokens_neox': 14509, 'n_words': 3681}