arangodb · maierlars · Mar 11, 2021 · Mar 10, 2021 · Mar 11, 2021
diff --git a/arangod/ClusterEngine/ClusterIndex.cpp b/arangod/ClusterEngine/ClusterIndex.cpp
@@ -27,6 +27,7 @@
 #include "ClusterIndex.h"
 #include "Indexes/SimpleAttributeEqualityMatcher.h"
 #include "Indexes/SortedIndexAttributeMatcher.h"
+#include "RocksDBEngine/RocksDBZkdIndex.h"
 #include "StorageEngine/EngineSelectorFeature.h"
 #include "VocBase/LogicalCollection.h"
 #include "VocBase/ticks.h"
@@ -268,8 +269,7 @@ Index::FilterCosts ClusterIndex::supportsFilterCondition(
     }
 
     case TRI_IDX_TYPE_ZKD_INDEX:
-      TRI_ASSERT(false);
-      THROW_ARANGO_EXCEPTION(TRI_ERROR_NOT_IMPLEMENTED);
+      return zkd::supportsFilterCondition(this, allIndexes, node, reference, itemsInIndex);
 
     case TRI_IDX_TYPE_UNKNOWN:
       break;
@@ -359,8 +359,7 @@ aql::AstNode* ClusterIndex::specializeCondition(aql::AstNode* node,
     }
 
     case TRI_IDX_TYPE_ZKD_INDEX:
-      TRI_ASSERT(false);
-      THROW_ARANGO_EXCEPTION(TRI_ERROR_NOT_IMPLEMENTED);
+      return zkd::specializeCondition(this, node, reference);
 
     case TRI_IDX_TYPE_UNKNOWN:
       break;

diff --git a/arangod/ClusterEngine/ClusterIndexFactory.cpp b/arangod/ClusterEngine/ClusterIndexFactory.cpp
@@ -166,6 +166,7 @@ ClusterIndexFactory::ClusterIndexFactory(application_features::ApplicationServer
   static const PrimaryIndexFactory primaryIndexFactory(server, "primary");
   static const DefaultIndexFactory skiplistIndexFactory(server, "skiplist");
   static const DefaultIndexFactory ttlIndexFactory(server, "ttl");
+  static const DefaultIndexFactory zkdIndexFactory(server, "zkd");
 
   emplace(edgeIndexFactory._type, edgeIndexFactory);
   emplace(fulltextIndexFactory._type, fulltextIndexFactory);
@@ -177,6 +178,7 @@ ClusterIndexFactory::ClusterIndexFactory(application_features::ApplicationServer
   emplace(primaryIndexFactory._type, primaryIndexFactory);
   emplace(skiplistIndexFactory._type, skiplistIndexFactory);
   emplace(ttlIndexFactory._type, ttlIndexFactory);
+  emplace(zkdIndexFactory._type, zkdIndexFactory);
 }
 
 /// @brief index name aliases (e.g. "persistent" => "hash", "skiplist" =>

diff --git a/arangod/Indexes/IndexFactory.cpp b/arangod/Indexes/IndexFactory.cpp
@@ -300,8 +300,9 @@ std::shared_ptr<Index> IndexFactory::prepareIndexFromSlice(velocypack::Slice def
 
 /// same for both storage engines
 std::vector<std::string> IndexFactory::supportedIndexes() const {
-  return std::vector<std::string>{"primary", "edge",       "hash", "skiplist",
-                                  "ttl",     "persistent", "geo",  "fulltext"};
+  return std::vector<std::string>{"primary",  "edge",     "hash",
+                                  "skiplist", "ttl",      "persistent",
+                                  "geo",      "fulltext", "zkd"};
 }
 
 std::unordered_map<std::string, std::string> IndexFactory::indexAliases() const {

diff --git a/arangod/RocksDBEngine/RocksDBZkdIndex.cpp b/arangod/RocksDBEngine/RocksDBZkdIndex.cpp
@@ -190,20 +190,11 @@ auto readDocumentKey(VPackSlice doc,
   return zkd::interleave(v);
 }
 
-struct ExpressionBounds {
-  struct Bound {
-    aql::AstNode const* op_node = nullptr;
-    aql::AstNode const* bounded_expr = nullptr;
-    aql::AstNode const* bound_value = nullptr;
-    bool isStrict = false;
-  };
+}  // namespace
 
-  Bound lower;
-  Bound upper;
-};
 
-void extractBoundsFromCondition(
-    RocksDBZkdIndex const* index,
+void zkd::extractBoundsFromCondition(
+    arangodb::Index const* index,
     const arangodb::aql::AstNode* condition, const arangodb::aql::Variable* reference,
     std::unordered_map<size_t, ExpressionBounds>& extractedBounds,
     std::unordered_set<aql::AstNode const*>& unusedExpressions) {
@@ -308,7 +299,72 @@ void extractBoundsFromCondition(
   }
 }
 
-}  // namespace
+auto zkd::supportsFilterCondition(
+    arangodb::Index const* index,const std::vector<std::shared_ptr<arangodb::Index>>& allIndexes,
+                             const arangodb::aql::AstNode* node,
+                             const arangodb::aql::Variable* reference,
+                             size_t itemsInIndex) -> Index::FilterCosts {
+
+  TRI_ASSERT(node->type == arangodb::aql::NODE_TYPE_OPERATOR_NARY_AND);
+
+  std::unordered_map<size_t, ExpressionBounds> extractedBounds;
+  std::unordered_set<aql::AstNode const*> unusedExpressions;
+  extractBoundsFromCondition(index, node, reference, extractedBounds, unusedExpressions);
+
+  if (extractedBounds.empty()) {
+    return Index::FilterCosts();
+  }
+
+  // TODO -- actually return costs
+  return Index::FilterCosts::zeroCosts();
+}
+
+auto zkd::specializeCondition(arangodb::Index const* index, arangodb::aql::AstNode* condition,
+                         const arangodb::aql::Variable* reference) -> aql::AstNode* {
+  std::unordered_map<size_t, ExpressionBounds> extractedBounds;
+  std::unordered_set<aql::AstNode const*> unusedExpressions;
+  extractBoundsFromCondition(index, condition, reference, extractedBounds, unusedExpressions);
+
+  std::vector<arangodb::aql::AstNode const*> children;
+
+  for (size_t i = 0; i < condition->numMembers(); ++i) {
+    auto op = condition->getMemberUnchecked(i);
+
+    if (unusedExpressions.find(op) == unusedExpressions.end()) {
+      switch (op->type) {
+        case arangodb::aql::NODE_TYPE_OPERATOR_BINARY_EQ:
+        case arangodb::aql::NODE_TYPE_OPERATOR_BINARY_LE:
+        case arangodb::aql::NODE_TYPE_OPERATOR_BINARY_GE:
+          children.emplace_back(op);
+          break;
+        case arangodb::aql::NODE_TYPE_OPERATOR_BINARY_LT:
+          op->type = aql::NODE_TYPE_OPERATOR_BINARY_LE;
+          children.emplace_back(op);
+          break;
+        case arangodb::aql::NODE_TYPE_OPERATOR_BINARY_GT:
+          op->type = aql::NODE_TYPE_OPERATOR_BINARY_GE;
+          children.emplace_back(op);
+          break;
+        default:
+          break;
+      }
+    }
+  }
+
+  // must edit in place, no access to AST; TODO change so we can replace with
+  // copy
+  TEMPORARILY_UNLOCK_NODE(condition);
+  condition->clearMembers();
+
+  for (auto& it : children) {
+    TRI_ASSERT(it->type != arangodb::aql::NODE_TYPE_OPERATOR_BINARY_NE);
+    condition->addMember(it);
+  }
+
+
+  return condition;
+
+}
 
 arangodb::Result arangodb::RocksDBZkdIndex::insert(
     arangodb::transaction::Methods& trx, arangodb::RocksDBMethods* methods,
@@ -375,63 +431,12 @@ arangodb::Index::FilterCosts arangodb::RocksDBZkdIndex::supportsFilterCondition(
     const arangodb::aql::AstNode* node,
     const arangodb::aql::Variable* reference, size_t itemsInIndex) const {
 
-  TRI_ASSERT(node->type == arangodb::aql::NODE_TYPE_OPERATOR_NARY_AND);
-
-  std::unordered_map<size_t, ExpressionBounds> extractedBounds;
-  std::unordered_set<aql::AstNode const*> unusedExpressions;
-  extractBoundsFromCondition(this, node, reference, extractedBounds, unusedExpressions);
-
-  if (extractedBounds.empty()) {
-    return FilterCosts();
-  }
-
-  // TODO -- actually return costs
-  return FilterCosts::zeroCosts();
+  return zkd::supportsFilterCondition(this, allIndexes, node, reference, itemsInIndex);
 }
+
 arangodb::aql::AstNode* arangodb::RocksDBZkdIndex::specializeCondition(
     arangodb::aql::AstNode* condition, const arangodb::aql::Variable* reference) const {
-  std::unordered_map<size_t, ExpressionBounds> extractedBounds;
-  std::unordered_set<aql::AstNode const*> unusedExpressions;
-  extractBoundsFromCondition(this, condition, reference, extractedBounds, unusedExpressions);
-
-  std::vector<arangodb::aql::AstNode const*> children;
-
-  for (size_t i = 0; i < condition->numMembers(); ++i) {
-    auto op = condition->getMemberUnchecked(i);
-
-    if (unusedExpressions.find(op) == unusedExpressions.end()) {
-      switch (op->type) {
-        case arangodb::aql::NODE_TYPE_OPERATOR_BINARY_EQ:
-        case arangodb::aql::NODE_TYPE_OPERATOR_BINARY_LE:
-        case arangodb::aql::NODE_TYPE_OPERATOR_BINARY_GE:
-          children.emplace_back(op);
-          break;
-        case arangodb::aql::NODE_TYPE_OPERATOR_BINARY_LT:
-          op->type = aql::NODE_TYPE_OPERATOR_BINARY_LE;
-          children.emplace_back(op);
-          break;
-        case arangodb::aql::NODE_TYPE_OPERATOR_BINARY_GT:
-          op->type = aql::NODE_TYPE_OPERATOR_BINARY_GE;
-          children.emplace_back(op);
-          break;
-        default:
-          break;
-      }
-    }
-  }
-
-  // must edit in place, no access to AST; TODO change so we can replace with
-  // copy
-  TEMPORARILY_UNLOCK_NODE(condition);
-  condition->clearMembers();
-
-  for (auto& it : children) {
-    TRI_ASSERT(it->type != arangodb::aql::NODE_TYPE_OPERATOR_BINARY_NE);
-    condition->addMember(it);
-  }
-
-
-  return condition;
+  return zkd::specializeCondition(this, condition, reference);
 }
 
 std::unique_ptr<IndexIterator> arangodb::RocksDBZkdIndex::iteratorForCondition(
@@ -440,7 +445,7 @@ std::unique_ptr<IndexIterator> arangodb::RocksDBZkdIndex::iteratorForCondition(
 
   TRI_ASSERT(node->type == arangodb::aql::NODE_TYPE_OPERATOR_NARY_AND);
 
-  std::unordered_map<size_t, ExpressionBounds> extractedBounds;
+  std::unordered_map<size_t, zkd::ExpressionBounds> extractedBounds;
   std::unordered_set<aql::AstNode const*> unusedExpressions;
   extractBoundsFromCondition(this, node, reference, extractedBounds, unusedExpressions);
 

diff --git a/arangod/RocksDBEngine/RocksDBZkdIndex.h b/arangod/RocksDBEngine/RocksDBZkdIndex.h
@@ -61,6 +61,36 @@ class RocksDBZkdIndex final : public RocksDBIndex {
                                                       const IndexIteratorOptions& opts) override;
 };
 
+namespace zkd {
+
+struct ExpressionBounds {
+  struct Bound {
+    aql::AstNode const* op_node = nullptr;
+    aql::AstNode const* bounded_expr = nullptr;
+    aql::AstNode const* bound_value = nullptr;
+    bool isStrict = false;
+  };
+
+  Bound lower;
+  Bound upper;
+};
+
+void extractBoundsFromCondition(arangodb::Index const* index,
+                                const arangodb::aql::AstNode* condition,
+                                const arangodb::aql::Variable* reference,
+                                std::unordered_map<size_t, ExpressionBounds>& extractedBounds,
+                                std::unordered_set<aql::AstNode const*>& unusedExpressions);
+
+auto supportsFilterCondition(arangodb::Index const* index,
+                             const std::vector<std::shared_ptr<arangodb::Index>>& allIndexes,
+                             const arangodb::aql::AstNode* node,
+                             const arangodb::aql::Variable* reference,
+                             size_t itemsInIndex) -> Index::FilterCosts;
+
+auto specializeCondition(arangodb::Index const* index, arangodb::aql::AstNode* condition,
+                         const arangodb::aql::Variable* reference) -> aql::AstNode*;
+}
+
 }
 
 #endif  // ARANGOD_ROCKSDB_ZKD_INDEX_H
diff --git a/arangod/Zkd/ZkdHelper.cpp b/arangod/Zkd/ZkdHelper.cpp
@@ -9,7 +9,8 @@
 #include <iostream>
 #include <optional>
 
-using namespace zkd;
+using namespace arangodb;
+using namespace arangodb::zkd;
 
 zkd::byte_string zkd::operator"" _bs(const char* const str, std::size_t len) {
   using namespace std::string_literals;

diff --git a/arangod/Zkd/ZkdHelper.h b/arangod/Zkd/ZkdHelper.h
@@ -2,16 +2,16 @@
 #define ZKD_TREE_LIBRARY_H
 
 #include <cstddef>
+#include <iosfwd>
 #include <limits>
 #include <optional>
 #include <string>
 #include <vector>
-#include <iosfwd>
 
-namespace zkd {
+namespace arangodb::zkd {
 
 inline static std::byte operator"" _b(unsigned long long b) {
-  return std::byte{(unsigned char) b};
+  return std::byte{(unsigned char)b};
 }
 /*
 struct byte_string : public std::basic_string<std::byte> {
@@ -49,32 +49,30 @@ struct CompareResult {
 
 std::ostream& operator<<(std::ostream& ostream, CompareResult const& string);
 
-auto compareWithBox(byte_string_view cur, byte_string_view min, byte_string_view max, std::size_t dimensions)
--> std::vector<CompareResult>;
-auto testInBox(byte_string_view cur, byte_string_view min, byte_string_view max, std::size_t dimensions)
--> bool;
+auto compareWithBox(byte_string_view cur, byte_string_view min, byte_string_view max,
+                    std::size_t dimensions) -> std::vector<CompareResult>;
+auto testInBox(byte_string_view cur, byte_string_view min, byte_string_view max,
+               std::size_t dimensions) -> bool;
 
-auto getNextZValue(byte_string_view cur, byte_string_view min, byte_string_view max, std::vector<CompareResult>& cmpResult)
--> std::optional<byte_string>;
+auto getNextZValue(byte_string_view cur, byte_string_view min, byte_string_view max,
+                   std::vector<CompareResult>& cmpResult) -> std::optional<byte_string>;
 
-template<typename T>
+template <typename T>
 auto to_byte_string_fixed_length(T) -> zkd::byte_string;
-template<typename T>
+template <typename T>
 auto from_byte_string_fixed_length(byte_string_view) -> T;
-template<>
+template <>
 byte_string to_byte_string_fixed_length<double>(double x);
 
-enum class Bit {
-  ZERO = 0,
-  ONE = 1
-};
+enum class Bit { ZERO = 0, ONE = 1 };
 
 class BitReader {
  public:
   using iterator = typename byte_string_view::const_iterator;
 
   explicit BitReader(iterator begin, iterator end);
-  explicit BitReader(byte_string const& str) : BitReader(byte_string_view{str}) {}
+  explicit BitReader(byte_string const& str)
+      : BitReader(byte_string_view{str}) {}
   explicit BitReader(byte_string_view v) : BitReader(v.cbegin(), v.cend()) {}
 
   auto next() -> std::optional<Bit>;
@@ -117,7 +115,6 @@ class BitWriter {
   byte_string _buffer;
 };
 
-
 struct RandomBitReader {
   explicit RandomBitReader(byte_string_view ref);
 
@@ -138,10 +135,9 @@ struct RandomBitManipulator {
   byte_string& ref;
 };
 
-
-template<typename T>
+template <typename T>
 void into_bit_writer_fixed_length(BitWriter&, T);
-template<typename T>
+template <typename T>
 auto from_bit_reader_fixed_length(BitReader&) -> T;
 
 struct floating_point {
@@ -156,9 +152,9 @@ auto construct_double(floating_point const& fp) -> double;
 
 std::ostream& operator<<(std::ostream& os, struct floating_point const& fp);
 
-} // namespace zkd
+}  // namespace arangodb::zkd
 
-std::ostream& operator<<(std::ostream& ostream, zkd::byte_string const& string);
-std::ostream& operator<<(std::ostream& ostream, zkd::byte_string_view string);
+std::ostream& operator<<(std::ostream& ostream, arangodb::zkd::byte_string const& string);
+std::ostream& operator<<(std::ostream& ostream, arangodb::zkd::byte_string_view string);
 
-#endif //ZKD_TREE_LIBRARY_H
+#endif  // ZKD_TREE_LIBRARY_H
diff --git a/tests/Zkd/Conversion.cpp b/tests/Zkd/Conversion.cpp
@@ -2,7 +2,8 @@
 
 #include "gtest/gtest.h"
 
-using namespace zkd;
+using namespace arangodb;
+using namespace arangodb::zkd;
 
 TEST(Zkd_byte_string_conversion, uint64) {
   auto tests = {std::pair{uint64_t{12}, byte_string{0_b, 0_b, 0_b, 0_b, 0_b, 0_b, 0_b, 12_b}},

diff --git a/tests/Zkd/Library.cpp b/tests/Zkd/Library.cpp
@@ -8,6 +8,8 @@
 #include <rocksdb/comparator.h>
 #include <rocksdb/slice.h>
 
+using namespace arangodb;
+
 static std::ostream& operator<<(std::ostream& os, std::vector<zkd::byte_string> const& bsvec) {
   os << "{";
   if (!bsvec.empty()) {