arangodb · maierlars · Jan 5, 2022 · Mar 3, 2021 · Mar 4, 2021 · Mar 4, 2021
diff --git a/arangod/Aql/ConditionFinder.cpp b/arangod/Aql/ConditionFinder.cpp
@@ -152,6 +152,7 @@ bool ConditionFinder::before(ExecutionNode* en) {
         // will clear out usedIndexes
         IndexIteratorOptions opts;
         opts.ascending = !descending;
+        opts.lookahead = node->hint().getLookahead();
         TRI_IF_FAILURE("ConditionFinder::insertIndexNode") {
           THROW_ARANGO_EXCEPTION(TRI_ERROR_DEBUG);
         }

diff --git a/arangod/Aql/IndexHint.cpp b/arangod/Aql/IndexHint.cpp
@@ -103,6 +103,15 @@ IndexHint::IndexHint(QueryContext& query, AstNode const* node) : IndexHint() {
             _forced = value->value.value._bool;
             handled = true;
           }
+        } else if (name == "lookahead") {
+          TRI_ASSERT(child->numMembers() > 0);
+          AstNode const* value = child->getMember(0);
+
+          if (value->type == AstNodeType::NODE_TYPE_VALUE &&
+              value->value.type == AstNodeValueType::VALUE_TYPE_INT) {
+            _lookahead = value->value.value._int;
+            handled = true;
+          }
         }
 
         if (!handled) {

diff --git a/arangod/Aql/IndexHint.h b/arangod/Aql/IndexHint.h
@@ -56,9 +56,12 @@ class IndexHint {
   std::string typeName() const;
   std::string toString() const;
 
+  size_t getLookahead() const noexcept { return _lookahead; }
+
  private:
   HintType _type;
   bool _forced;
+  size_t _lookahead = 1;
 
   // actual hint is a recursive structure, with the data type determined by the
   // _type above; in the case of a nested IndexHint, the value of isForced() is

diff --git a/arangod/Indexes/IndexIterator.h b/arangod/Indexes/IndexIterator.h
@@ -308,6 +308,9 @@ struct IndexIteratorOptions {
   bool evaluateFCalls = true;
   /// @brief enable caching
   bool enableCache = true;
+  /// @brief number of lookahead elements considered before computing the next
+  /// intersection of the Z-curve with the search range
+  size_t lookahead = 1;
 };
 
 /// index estimate map, defined here because it was convenient

diff --git a/arangod/RocksDBEngine/RocksDBZkdIndex.cpp b/arangod/RocksDBEngine/RocksDBZkdIndex.cpp
@@ -61,13 +61,15 @@ class RocksDBZkdIndexIterator final : public IndexIterator {
   RocksDBZkdIndexIterator(LogicalCollection* collection,
                           RocksDBZkdIndexBase* index, transaction::Methods* trx,
                           zkd::byte_string min, zkd::byte_string max,
-                          std::size_t dim, ReadOwnWrites readOwnWrites)
+                          std::size_t dim, ReadOwnWrites readOwnWrites,
+                          size_t lookahead)
       : IndexIterator(collection, trx, readOwnWrites),
         _bound(RocksDBKeyBounds::ZkdIndex(index->objectId())),
         _min(std::move(min)),
         _max(std::move(max)),
         _dim(dim),
-        _index(index) {
+        _index(index),
+        _lookahead(lookahead) {
     _cur = _min;
     _upperBound = _bound.end();
 
@@ -85,6 +87,12 @@ class RocksDBZkdIndexIterator final : public IndexIterator {
   char const* typeName() const override { return "rocksdb-zkd-index-iterator"; }
 
  protected:
+  size_t numNextTries()
+      const noexcept {  // may depend on the number of dimensions
+                        // and the limits of the query
+    return _lookahead;
+  }

   bool nextImpl(LocalDocumentIdCallback const& callback,
                 size_t limit) override {
     for (auto i = size_t{0}; i < limit;) {
@@ -105,7 +113,26 @@ class RocksDBZkdIndexIterator final : public IndexIterator {
         case IterState::CHECK_CURRENT_ITER: {
           auto const rocksKey = _iter->key();
           auto const byteStringKey = RocksDBKey::zkdIndexValue(rocksKey);
-          if (!zkd::testInBox(byteStringKey, _min, _max, _dim)) {
+
+          bool foundNextZValueInBox =
+              zkd::testInBox(byteStringKey, _min, _max, _dim);
+          for (size_t numTried = 0;
+               !foundNextZValueInBox && numTried < numNextTries(); ++numTried) {
+            _iter->Next();
+            if (!_iter->Valid()) {
+              arangodb::rocksutils::checkIteratorStatus(_iter.get());
+              _iterState = IterState::DONE;
+              break;  // for loop
+            }
+            foundNextZValueInBox =
+                zkd::testInBox(byteStringKey, _min, _max, _dim);
+          }
+
+          if (_iterState == IterState::DONE) {
+            break;  // case CHECK_CURRENT_ITER
+          }
+
+          if (!foundNextZValueInBox) {
             _cur = byteStringKey;
 
             zkd::compareWithBoxInto(_cur, _min, _max, _dim, _compareResult);
@@ -164,6 +191,8 @@ class RocksDBZkdIndexIterator final : public IndexIterator {
   std::unique_ptr<rocksdb::Iterator> _iter;
   RocksDBZkdIndexBase* _index = nullptr;
 
+  const size_t _lookahead;
+
   std::vector<zkd::CompareResult> _compareResult;
 };
 
@@ -526,7 +555,7 @@ arangodb::RocksDBZkdIndexBase::iteratorForCondition(
 
   return std::make_unique<RocksDBZkdIndexIterator<false>>(
       &_collection, this, trx, std::move(min), std::move(max), fields().size(),
-      readOwnWrites);
+      readOwnWrites, opts.lookahead);
 }
 
 std::unique_ptr<IndexIterator>
@@ -538,7 +567,7 @@ arangodb::RocksDBUniqueZkdIndex::iteratorForCondition(
 
   return std::make_unique<RocksDBZkdIndexIterator<true>>(
       &_collection, this, trx, std::move(min), std::move(max), fields().size(),
-      readOwnWrites);
+      readOwnWrites, opts.lookahead);
 }
 
 arangodb::Result arangodb::RocksDBUniqueZkdIndex::insert(

diff --git a/tests/js/server/aql/aql-optimizer-zkdindex-multi.js b/tests/js/server/aql/aql-optimizer-zkdindex-multi.js
@@ -122,33 +122,34 @@ function optimizerRuleZkd2dIndexTestSuite() {
                     if (x === "none" && y === "none" && z === "none" && w === "none") {
                         continue; // does not use the index
                     }
-
-                    testObject[["testCase", x, y, z, w].join("_")] = function () {
-                        const query = `
-                            FOR d IN ${colName}
+                    for (let addLookahead of ["", " OPTIONS {lookahead: 32}"]) {
+                        testObject[["testCase", x, y, z, w].join("_")] = function () {
                            const query = `
+                            FOR d IN ${colName} ${addLookahead}
                               FILTER ${conditionForVariable(x, "d.x")}
                               FILTER ${conditionForVariable(y, "d.y")}
                               FILTER ${conditionForVariable(z, "d.z")}
                               FILTER ${conditionForVariable(w, "d.a.w")}
                               RETURN [d.x, d.y, d.z, d.a.w]
                           `;
-                        const explainRes = AQL_EXPLAIN(query);
-                        const appliedRules = explainRes.plan.rules;
-                        const nodeTypes = explainRes.plan.nodes.map(n => n.type).filter(n => !["GatherNode", "RemoteNode"].includes(n));
-                        assertEqual(["SingletonNode", "IndexNode", "CalculationNode", "ReturnNode"], nodeTypes);
-                        assertTrue(appliedRules.includes(useIndexes));
-
-                        const conds = [x, y, z, w];
-                        if (!conds.includes("lt") && !conds.includes("gt") && !conds.includes("legt")) {
-                            assertTrue(appliedRules.includes(removeFilterCoveredByIndex));
-                        }
-                        const executeRes = AQL_EXECUTE(query);
-                        const res = executeRes.json;
-                        const expected = productSet(x, y, z, w);
-                        res.sort();
-                        expected.sort();
-                        assertEqual(expected, res, JSON.stringify({query}));
-                    };
+                            const explainRes = AQL_EXPLAIN(query);
+                            const appliedRules = explainRes.plan.rules;
+                            const nodeTypes = explainRes.plan.nodes.map(n => n.type).filter(n => !["GatherNode", "RemoteNode"].includes(n));
+                            assertEqual(["SingletonNode", "IndexNode", "CalculationNode", "ReturnNode"], nodeTypes);
+                            assertTrue(appliedRules.includes(useIndexes));
+
+                            const conds = [x, y, z, w];
+                            if (!conds.includes("lt") && !conds.includes("gt") && !conds.includes("legt")) {
+                                assertTrue(appliedRules.includes(removeFilterCoveredByIndex));
+                            }
+                            const executeRes = AQL_EXECUTE(query);
+                            const res = executeRes.json;
+                            const expected = productSet(x, y, z, w);
+                            res.sort();
+                            expected.sort();
+                            assertEqual(expected, res, JSON.stringify({query}));
+                        };
+                    }
                 }
             }
         }