arangodb · mchacki · Sep 10, 2021 · Mar 3, 2021 · Mar 4, 2021 · Mar 4, 2021
diff --git a/CHANGELOG b/CHANGELOG
@@ -1,6 +1,23 @@
 devel
 -----
 
+* 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
+  multidimensional index using the new type 'zkd' on the fields ["x", "y", "z"].
+
+  The AQL optimizer will then consider this index when doing queries on multiple
+  ranges, for example:
+
+    FOR p IN points
+        FILTER x0 <= p.x && p.x <= x1
+        FILTER y0 <= p.y && p.y <= y1
+        FILTER z0 <= p.z && p.z <= z1
+        RETURN p
+
+  The index implements the relation <=, == and >= natively. Strict relations are
+  emulated using post filtering. Ranges can be unbounded on one or both sides.
+
 * No runtime limits for shard move and server cleanout jobs, instead
   possibility to cancel them.
 

@@ -0,0 +1,68 @@
+
+@startDocuBlock post_api_index_zkd
+@brief creates a multi-dimensional index
+
+@RESTHEADER{POST /_api/index#multi-dim, Create multi-dimensional index, createIndex#multi-dim}
+
+@RESTQUERYPARAMETERS
+
+@RESTQUERYPARAM{collection,string,required}
+The collection name.
+
+@RESTBODYPARAM{type,string,required,string}
+must be equal to *"zkd"*.
+
+@RESTBODYPARAM{fields,array,required,string}
+an array of attribute names used for each dimension. Array expansions are not allowed.
+
+@RESTBODYPARAM{unique,boolean,required,}
+if *true*, then create a unique index.
+
+@RESTBODYPARAM{fieldValueTypes,string,required,string}
+must be equal to *"double"*. Currently only doubles are supported as values.
+
+@RESTDESCRIPTION
+Creates a multi-dimensional index for the collection *collection-name*, if
+it does not already exist. The call expects an object containing the index
+details.
+
+@RESTRETURNCODES
+
+@RESTRETURNCODE{200}
+If the index already exists, then a *HTTP 200* is
+returned.
+
+@RESTRETURNCODE{201}
+If the index does not already exist and could be created, then a *HTTP 201*
+is returned.
+
+@RESTRETURNCODE{404}
+If the *collection-name* is unknown, then a *HTTP 404* is returned.
+
+@RESTRETURNCODE{400}
+If the index definition is invalid, then a *HTTP 400* is returned.
+
+@EXAMPLES
+
+Creating a multi-dimensional index
+
+@EXAMPLE_ARANGOSH_RUN{RestIndexCreateNewFulltext}
+var cn = "intervals";
+db._drop(cn);
+db._create(cn);
+
+    var url = "/_api/index?collection=" + cn;
+    var body = {
+      type: "zkd",
+      fields: [ "from", "to" ],
+      fieldValueTypes: "double"
+    };
+
+    var response = logCurlRequest('POST', url, body);
+
+    assert(response.code === 201);
+
+    logJsonResponse(response);
+~ db._drop(cn);
+@END_EXAMPLE_ARANGOSH_RUN
+@endDocuBlock
diff --git a/arangod/CMakeLists.txt b/arangod/CMakeLists.txt
@@ -836,6 +836,8 @@ endif()
 include(ClusterEngine/CMakeLists.txt)
 include(RocksDBEngine/CMakeLists.txt)
 
+add_library(arango_zkd STATIC Zkd/ZkdHelper.cpp)
+
 add_library(arango_restart_action STATIC
   RestServer/RestartAction.cpp
 )
@@ -919,6 +921,7 @@ add_library(arango_rocksdb STATIC
   ${ROCKSDB_SOURCES}
   ${ADDITIONAL_LIB_ARANGO_ROCKSDB_SOURCES}
 )
+target_link_libraries(arango_rocksdb arango_zkd)
 
 add_dependencies(arango_rocksdb snappy)
 

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"
@@ -277,6 +278,9 @@ Index::FilterCosts ClusterIndex::supportsFilterCondition(
       return Index::supportsFilterCondition(allIndexes, node, reference, itemsInIndex);
     }
 
+    case TRI_IDX_TYPE_ZKD_INDEX:
+      return zkd::supportsFilterCondition(this, allIndexes, node, reference, itemsInIndex);
+
     case TRI_IDX_TYPE_UNKNOWN:
       break;
   }
@@ -315,6 +319,10 @@ Index::SortCosts ClusterIndex::supportsSortCondition(arangodb::aql::SortConditio
       break;
     }
 
+    case TRI_IDX_TYPE_ZKD_INDEX:
+      // Sorting not supported
+      return Index::SortCosts{};
+
     case TRI_IDX_TYPE_UNKNOWN:
       break;
   }
@@ -359,7 +367,10 @@ aql::AstNode* ClusterIndex::specializeCondition(aql::AstNode* node,
     case TRI_IDX_TYPE_PERSISTENT_INDEX: {
       return SortedIndexAttributeMatcher::specializeCondition(this, node, reference);
     }
-
+
+    case TRI_IDX_TYPE_ZKD_INDEX:
+      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 @@ void ClusterIndexFactory::linkIndexFactories(application_features::ApplicationSe
   static const PrimaryIndexFactory primaryIndexFactory(server, "primary");
   static const DefaultIndexFactory skiplistIndexFactory(server, "skiplist");
   static const DefaultIndexFactory ttlIndexFactory(server, "ttl");
+  static const DefaultIndexFactory zkdIndexFactory(server, "zkd");
 
   factory.emplace(edgeIndexFactory._type, edgeIndexFactory);
   factory.emplace(fulltextIndexFactory._type, fulltextIndexFactory);
@@ -177,6 +178,7 @@ void ClusterIndexFactory::linkIndexFactories(application_features::ApplicationSe
   factory.emplace(primaryIndexFactory._type, primaryIndexFactory);
   factory.emplace(skiplistIndexFactory._type, skiplistIndexFactory);
   factory.emplace(ttlIndexFactory._type, ttlIndexFactory);
+  factory.emplace(zkdIndexFactory._type, zkdIndexFactory);
 }
 
 ClusterIndexFactory::ClusterIndexFactory(application_features::ApplicationServer& server)

diff --git a/arangod/Indexes/Index.cpp b/arangod/Indexes/Index.cpp
@@ -332,6 +332,9 @@ Index::IndexType Index::type(char const* type, size_t len) {
   if (::typeMatch(type, len, "geo2")) {
     return TRI_IDX_TYPE_GEO2_INDEX;
   }
+  if (::typeMatch(type, len, "zkd")) {
+    return TRI_IDX_TYPE_ZKD_INDEX;
+  }
   std::string const& tmp = arangodb::iresearch::DATA_SOURCE_TYPE.name();
   if (::typeMatch(type, len, tmp.c_str())) {
     return TRI_IDX_TYPE_IRESEARCH_LINK;
@@ -374,6 +377,8 @@ char const* Index::oldtypeName(Index::IndexType type) {
       return arangodb::iresearch::DATA_SOURCE_TYPE.name().c_str();
     case TRI_IDX_TYPE_NO_ACCESS_INDEX:
       return "noaccess";
+    case TRI_IDX_TYPE_ZKD_INDEX:
+      return "zkd";
     case TRI_IDX_TYPE_UNKNOWN: {
     }
   }

diff --git a/arangod/Indexes/Index.h b/arangod/Indexes/Index.h
@@ -102,7 +102,8 @@ class Index {
     TRI_IDX_TYPE_TTL_INDEX,
     TRI_IDX_TYPE_PERSISTENT_INDEX,
     TRI_IDX_TYPE_IRESEARCH_LINK,
-    TRI_IDX_TYPE_NO_ACCESS_INDEX
+    TRI_IDX_TYPE_NO_ACCESS_INDEX,
+    TRI_IDX_TYPE_ZKD_INDEX
   };
 
   /// @brief: helper struct returned by index methods that determine the costs

diff --git a/arangod/Indexes/IndexFactory.cpp b/arangod/Indexes/IndexFactory.cpp
@@ -301,8 +301,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 {
@@ -581,4 +582,34 @@ Result IndexFactory::enhanceJsonIndexFulltext(VPackSlice definition,
   return res;
 }
 
+/// @brief enhances the json of a zkd index
+Result IndexFactory::enhanceJsonIndexZkd(VPackSlice definition,
+                                              VPackBuilder& builder, bool create) {
+  if (auto fieldValueTypes = definition.get("fieldValueTypes");
+      !fieldValueTypes.isString() || !fieldValueTypes.isEqualString("double")) {
+    return Result(
+        TRI_ERROR_BAD_PARAMETER,
+        "zkd index requires `fieldValueTypes` to be set to `double` - future "
+        "releases might lift this requirement");
+  }
+
+  builder.add("fieldValueTypes", VPackValue("double"));
+  Result res = processIndexFields(definition, builder, 1, INT_MAX, create, false);
+
+  if (res.ok()) {
+    if (auto isSparse = definition.get(StaticStrings::IndexSparse).isTrue(); isSparse) {
+      return Result(TRI_ERROR_BAD_PARAMETER,
+                    "zkd index does not support sparse property");
+    }
+
+    processIndexUniqueFlag(definition, builder);
+
+    bool bck = basics::VelocyPackHelper::getBooleanValue(definition, StaticStrings::IndexInBackground,
+                                                         false);
+    builder.add(StaticStrings::IndexInBackground, VPackValue(bck));
+  }
+
+  return res;
+}
+
 }  // namespace arangodb
diff --git a/arangod/Indexes/IndexFactory.h b/arangod/Indexes/IndexFactory.h
@@ -158,11 +158,15 @@ class IndexFactory {
   static Result enhanceJsonIndexGeo(velocypack::Slice definition,
                                     velocypack::Builder& builder, bool create,
                                     int minFields, int maxFields);
-  
+
   /// @brief enhances the json of a fulltext index
   static Result enhanceJsonIndexFulltext(velocypack::Slice definition,
                                          velocypack::Builder& builder, bool create);
 
+  /// @brief enhances the json of a zkd index
+  static Result enhanceJsonIndexZkd(arangodb::velocypack::Slice definition,
+                                         arangodb::velocypack::Builder& builder, bool create);
+
  protected:
   /// @brief clear internal factory/normalizer maps
   void clear();

diff --git a/arangod/RocksDBEngine/CMakeLists.txt b/arangod/RocksDBEngine/CMakeLists.txt
@@ -72,9 +72,9 @@ set(ROCKSDB_SOURCES
   RocksDBEngine/RocksDBLogValue.cpp
   RocksDBEngine/RocksDBMetaCollection.cpp
   RocksDBEngine/RocksDBMetadata.cpp
-  RocksDBEngine/RocksDBTransactionMethods.cpp
   RocksDBEngine/RocksDBOptimizerRules.cpp
   RocksDBEngine/RocksDBOptionFeature.cpp
+  RocksDBEngine/RocksDBPersistedLog.cpp
   RocksDBEngine/RocksDBPrimaryIndex.cpp
   RocksDBEngine/RocksDBRecoveryManager.cpp
   RocksDBEngine/RocksDBReplicationCommon.cpp
@@ -90,6 +90,7 @@ set(ROCKSDB_SOURCES
   RocksDBEngine/RocksDBSettingsManager.cpp
   RocksDBEngine/RocksDBSyncThread.cpp
   RocksDBEngine/RocksDBTransactionCollection.cpp
+  RocksDBEngine/RocksDBTransactionMethods.cpp
   RocksDBEngine/RocksDBTransactionState.cpp
   RocksDBEngine/RocksDBTtlIndex.cpp
   RocksDBEngine/RocksDBTypes.cpp
@@ -98,6 +99,6 @@ set(ROCKSDB_SOURCES
   RocksDBEngine/RocksDBVPackIndex.cpp
   RocksDBEngine/RocksDBValue.cpp
   RocksDBEngine/RocksDBWalAccess.cpp
-  RocksDBEngine/RocksDBPersistedLog.cpp
+  RocksDBEngine/RocksDBZkdIndex.cpp
 )
 set(ROCKSDB_SOURCES ${ROCKSDB_SOURCES} PARENT_SCOPE)
diff --git a/arangod/RocksDBEngine/RocksDBColumnFamilyManager.cpp b/arangod/RocksDBEngine/RocksDBColumnFamilyManager.cpp
@@ -30,17 +30,19 @@
 
 namespace arangodb {
 
-std::array<char const*, arangodb::RocksDBColumnFamilyManager::numberOfColumnFamilies>
-    RocksDBColumnFamilyManager::_internalNames = {"default",      "Documents",
-                                                  "PrimaryIndex", "EdgeIndex",
-                                                  "VPackIndex",   "GeoIndex",
-                                                  "FulltextIndex", "ReplicatedLogs"};
+std::array<char const*, arangodb::RocksDBColumnFamilyManager::numberOfColumnFamilies> RocksDBColumnFamilyManager::_internalNames =
+    {"default",       "Documents",      "PrimaryIndex",
+     "EdgeIndex",     "VPackIndex",     "GeoIndex",
+     "FulltextIndex", "ReplicatedLogs", "ZkdIndex"};
+
 std::array<char const*, arangodb::RocksDBColumnFamilyManager::numberOfColumnFamilies> RocksDBColumnFamilyManager::_externalNames =
-    {"definitions", "documents", "primary", "edge", "vpack", "geo", "fulltext", "replicated-logs"};
+    {"definitions", "documents", "primary",         "edge", "vpack",
+     "geo",         "fulltext",  "replicated-logs", "zkd"};
 
 std::array<rocksdb::ColumnFamilyHandle*, RocksDBColumnFamilyManager::numberOfColumnFamilies>
-    RocksDBColumnFamilyManager::_handles = {nullptr, nullptr, nullptr, nullptr,
-                                            nullptr, nullptr, nullptr, nullptr};
+    RocksDBColumnFamilyManager::_handles = {nullptr, nullptr, nullptr,
+                                            nullptr, nullptr, nullptr,
+                                            nullptr, nullptr, nullptr};
 
 rocksdb::ColumnFamilyHandle* RocksDBColumnFamilyManager::_defaultHandle = nullptr;
 

diff --git a/arangod/RocksDBEngine/RocksDBColumnFamilyManager.h b/arangod/RocksDBEngine/RocksDBColumnFamilyManager.h
@@ -46,6 +46,7 @@ struct RocksDBColumnFamilyManager {
     GeoIndex = 5,
     FulltextIndex = 6,
     ReplicatedLogs = 7,
+    ZkdIndex = 8,
 
     Invalid = 1024  // special placeholder
   };
@@ -56,7 +57,7 @@ struct RocksDBColumnFamilyManager {
   };
 
   static constexpr size_t minNumberOfColumnFamilies = 7;
-  static constexpr size_t numberOfColumnFamilies = 8;
+  static constexpr size_t numberOfColumnFamilies = 9;
 
   static void initialize();
 

diff --git a/arangod/RocksDBEngine/RocksDBEngine.cpp b/arangod/RocksDBEngine/RocksDBEngine.cpp
@@ -707,7 +707,7 @@ void RocksDBEngine::start() {
   addFamily(RocksDBColumnFamilyManager::Family::GeoIndex);
   addFamily(RocksDBColumnFamilyManager::Family::FulltextIndex);
   addFamily(RocksDBColumnFamilyManager::Family::ReplicatedLogs);
-
+  addFamily(RocksDBColumnFamilyManager::Family::ZkdIndex);
 
   size_t const minNumberOfColumnFamilies = RocksDBColumnFamilyManager::minNumberOfColumnFamilies;
   bool dbExisted = false;
@@ -746,15 +746,17 @@ void RocksDBEngine::start() {
           << "found existing column families: " << names;
       auto const replicatedLogsName = RocksDBColumnFamilyManager::name(
           RocksDBColumnFamilyManager::Family::ReplicatedLogs);
+      auto const zkdIndexName = RocksDBColumnFamilyManager::name(
+          RocksDBColumnFamilyManager::Family::ReplicatedLogs);
 
       for (auto const& it : cfFamilies) {
         auto it2 = std::find(existingColumnFamilies.begin(),
                              existingColumnFamilies.end(), it.name);
         if (it2 == existingColumnFamilies.end()) {
 
-          if (it.name == replicatedLogsName) {
+          if (it.name == replicatedLogsName || it.name == zkdIndexName) {
             LOG_TOPIC("293c3", INFO, Logger::STARTUP)
-                << "column family " << replicatedLogsName
+                << "column family " << it.name
                 << " is missing and will be created.";
             continue;
           }
@@ -836,6 +838,8 @@ void RocksDBEngine::start() {
                                   cfHandles[6]);
   RocksDBColumnFamilyManager::set(RocksDBColumnFamilyManager::Family::ReplicatedLogs,
                                   cfHandles[7]);
+  RocksDBColumnFamilyManager::set(RocksDBColumnFamilyManager::Family::ZkdIndex,
+                                  cfHandles[8]);
   TRI_ASSERT(RocksDBColumnFamilyManager::get(RocksDBColumnFamilyManager::Family::Definitions)
                  ->GetID() == 0);
 

diff --git a/arangod/RocksDBEngine/RocksDBIndex.cpp b/arangod/RocksDBEngine/RocksDBIndex.cpp
@@ -378,6 +378,8 @@ RocksDBKeyBounds RocksDBIndex::getBounds(Index::IndexType type, uint64_t objectI
       return RocksDBKeyBounds::GeoIndex(objectId);
     case RocksDBIndex::TRI_IDX_TYPE_IRESEARCH_LINK:
       return RocksDBKeyBounds::DatabaseViews(objectId);
+    case RocksDBIndex::TRI_IDX_TYPE_ZKD_INDEX:
+      return RocksDBKeyBounds::ZkdIndex(objectId);
     case RocksDBIndex::TRI_IDX_TYPE_UNKNOWN:
     default:
       THROW_ARANGO_EXCEPTION(TRI_ERROR_NOT_IMPLEMENTED);