8000 using lookahead in zkd (#14745) · arangodb/arangodb@9013912 · GitHub
[go: up one dir, main page]
Skip to content

Commit 9013912

Browse files
romanatarangomaierlarsgoedderzmchacki
committed
using lookahead in zkd (#14745)
* Bootstrap zkd indexes. Now fill in the details. * Added prototype for condition finder. * Added helper for Range. * Fixed double conversion. * Added wrong but working nextImpl * Extract bounds for iterator. * Fixed extraction logic with reversed operator usage. * Detect equal operator correctly. * Implemented nextImpl * Removed log devel for hot path. * Cleanup * Added support for partially unbounded queries. * Do not use index for full collection scans. * Added tests for ZkdHelper. * Added functional test suite skeleton for zkd index * Some fixes to double conversions * Fixed bug in double to byte_string conversion. * Added support for denormalized doubles and infinity. * Test all interesting double values. * Disallow Nan. * Added more js tests. * Added a lot of tests. * Cleaned up test. * [zkd] Strict comparsion (#13673) * Added support for strict comparsion. * Allow unsupported conditions. Correctly display conditions that are strict in explainer. * Fixed some now broken tests. * Apply suggestions from code review Co-authored-by: Tobias Gödderz <tobias@arangodb.com> Co-authored-by: Tobias Gödderz <tobias@arangodb.com> * [zkd] Cluster support (#13677) * Added support for cluster. * Fixing unit tests namespace using. * Added support for nested fields - excluding expansions. (#13681) * Added support for nested fields - excluding expansions. * Added tests for nested attributes. * [zkd] Unique Constraints (#13691) * Added support for unique constraint. * Added tests for unique constraints. * [zkd] Forward Compat (#13694) * Added required field fieldValueTypes: double. * Refactored index attribute validation. Disallowed attribute expansions. * Added tests for restrictions. * Fixing normalization of zkd index definition. * [zkd] Column Family (#13692) * Added a new column family for the zkd index. * Changed write buffer number to 8 + 2. * Added zkd index docu block. (#13698) * Fixed bug in RocksDBKeyBounds and using default cost estimation * [zkd] testInBox speedup (#13798) * Performance optimized testInBox. * Optimized performance of compareWithBox. * Now actually use the optimized version. * Resize vector before usage. * Clear vector before reusing CompareResults. * Eliminate div operation. * Another div in testInBox. * Count finished dimensions. * Removed unused functions. * Use small vector. * Fixed goto bug and resize short vector properly. * Apply suggestions from code review Co-authored-by: Tobias Gödderz <tobias@arangodb.com> Co-authored-by: Tobias Gödderz <tobias@arangodb.com> * Feature/zkd index speedup getnextzvalue (#13799) * Avoid interleave&transpose in getNextZValue() * Change order of actual/expected in test assertion * Minor improvements * Removed superfluous transpose calls * Updated CHANGELOG. * Fixing iterator. * Added review suggestions. * using lookahead in zkd * added forgotten declaration * added forgotten condering of the new option * Applied suggestions from review. * removed tryNewIndex option, now decided by lookahead==0 * unified default lookaheads for zkd to 1, made one of them const * added testing with lookahead 32 in aql-optimizer-zkdindex-multi.js * Applied clang-format Co-authored-by: maierlars <lars@arangodb.com> Co-authored-by: Tobias Gödderz <tobias@arangodb.com> Co-authored-by: Michael Hackstein <michael@arangodb.com>
1 parent 8c1a975 commit 9013912

File tree

6 files changed

+72
-26
lines changed

6 files changed

+72
-26
lines changed

‎arangod/Aql/ConditionFinder.cpp

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -152,6 +152,7 @@ bool ConditionFinder::before(ExecutionNode* en) {
152152
// will clear out usedIndexes
153153
IndexIteratorOptions opts;
154154
opts.ascending = !descending;
155+
opts.lookahead = node->hint().getLookahead();
155156
TRI_IF_FAILURE("ConditionFinder::insertIndexNode") {
156157
THROW_ARANGO_EXCEPTION(TRI_ERROR_DEBUG);
157158
}

‎arangod/Aql/IndexHint.cpp

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -103,6 +103,15 @@ IndexHint::IndexHint(QueryContext& query, AstNode const* node) : IndexHint() {
103103
_forced = value->value.value._bool;
104104
handled = true;
105105
}
106+
} else if (name == "lookahead") {
107+
TRI_ASSERT(child->numMembers() > 0);
108+
AstNode const* value = child->getMember(0);
109+
110+
if (value->type == AstNodeType::NODE_TYPE_VALUE &&
111+
value->value.type == AstNodeValueType::VALUE_TYPE_INT) {
112+
_lookahead = value->value.value._int;
113+
handled = true;
114+
}
106115
}
107116

108117
if (!handled) {

‎arangod/Aql/IndexHint.h

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -56,9 +56,12 @@ class IndexHint {
5656
std::string typeName() const;
5757
std::string toString() const;
5858

59+
size_t getLookahead() const noexcept { return _lookahead; }
60+
5961
private:
6062
HintType _type;
6163
bool _forced;
64+
size_t _lookahead = 1;
6265

6366
// actual hint is a recursive structure, with the data type determined by the
6467
// _type above; in the case of a nested IndexHint, the value of isForced() is

‎arangod/Indexes/IndexIterator.h

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -308,6 +308,9 @@ struct IndexIteratorOptions {
308308
bool evaluateFCalls = true;
309309
/// @brief enable caching
310310
bool enableCache = true;
311+
/// @brief number of lookahead elements considered before computing the next
312+
/// intersection of the Z-curve with the search range
313+
size_t lookahead = 1;
311314
};
312315

313316
/// index estimate map, defined here because it was convenient

‎arangod/RocksDBEngine/RocksDBZkdIndex.cpp

Lines changed: 34 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -61,13 +61,15 @@ class RocksDBZkdIndexIterator final : public IndexIterator {
6161
RocksDBZkdIndexIterator(LogicalCollection* collection,
6262
RocksDBZkdIndexBase* index, transaction::Methods* trx,
6363
zkd::byte_string min, zkd::byte_string max,
64-
std::size_t dim, ReadOwnWrites readOwnWrites)
64+
std::size_t dim, ReadOwnWrites readOwnWrites,
65+
size_t lookahead)
6566
: IndexIterator(collection, trx, readOwnWrites),
6667
_bound(RocksDBKeyBounds::ZkdIndex(index->objectId())),
6768
_min(std::move(min)),
6869
_max(std::move(max)),
6970
_dim(dim),
70-
_index(index) {
71+
_index(index),
72+
_lookahead(lookahead) {
7173
_cur = _min;
7274
_upperBound = _bound.end();
7375

@@ -85,6 +87,12 @@ class RocksDBZkdIndexIterator final : public IndexIterator {
8587
char const* typeName() const override { return "rocksdb-zkd-index-iterator"; }
8688

8789
protected:
90+
size_t numNextTries()
91+
const noexcept { // may depend on the number of dimensions
92+
// and the limits of the query
93+
return _lookahead;
94+
}
95+
8896
bool nextImpl(LocalDocumentIdCallback const& callback,
8997
size_t limit) override {
9098
for (auto i = size_t{0}; i < limit;) {
@@ -105,7 +113,26 @@ class RocksDBZkdIndexIterator final : public IndexIterator {
105113
case IterState::CHECK_CURRENT_ITER: {
106114
auto const rocksKey = _iter->key();
107115
auto const byteStringKey = RocksDBKey::zkdIndexValue(rocksKey);
108-
if (!zkd::testInBox(byteStringKey, _min, _max, _dim)) {
116+
117+
bool foundNextZValueInBox =
118+
zkd::testInBox(byteStringKey, _min, _max, _dim);
119+
for (size_t numTried = 0;
120+
!foundNextZValueInBox && numTried < numNextTries(); ++numTried) {
121+
_iter->Next();
122+
if (!_iter->Valid()) {
123+
arangodb::rocksutils::checkIteratorStatus(_iter.get());
124+
_iterState = IterState::DONE;
125+
break; // for loop
126+
}
127+
foundNextZValueInBox =
128+
zkd::testInBox(byteStringKey, _min, _max, _dim);
129+
}
130+
131+
if (_iterState == IterState::DONE) {
132+
break; // case CHECK_CURRENT_ITER
133+
}
134+
135+
if (!foundNextZValueInBox) {
109136
_cur = byteStringKey;
110137

111138
zkd::compareWithBoxInto(_cur, _min, _max, _dim, _compareResult);
@@ -164,6 +191,8 @@ class RocksDBZkdIndexIterator final : public IndexIterator {
164191
std::unique_ptr<rocksdb::Iterator> _iter;
165192
RocksDBZkdIndexBase* _index = nullptr;
166193

194+
const size_t _lookahead;
195+
167196
std::vector<zkd::CompareResult> _compareResult;
168197
};
169198

@@ -526,7 +555,7 @@ arangodb::RocksDBZkdIndexBase::iteratorForCondition(
526555

527556
return std::make_unique<RocksDBZkdIndexIterator<false>>(
528557
&_collection, this, trx, std::move(min), std::move(max), fields().size(),
529-
readOwnWrites);
558+
readOwnWrites, opts.lookahead);
530559
}
531560

532561
std::unique_ptr<IndexIterator>
@@ -538,7 +567,7 @@ arangodb::RocksDBUniqueZkdIndex::iteratorForCondition(
538567

539568
return std::make_unique<RocksDBZkdIndexIterator<true>>(
540569
&_collection, this, trx, std::move(min), std::move(max), fields().size(),
541-
readOwnWrites);
570+
readOwnWrites, opts.lookahead);
542571
}
543572

544573
arangodb::Result arangodb::RocksDBUniqueZkdIndex::insert(

‎tests/js/server/aql/aql-optimizer-zkdindex-multi.js

Lines changed: 22 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -122,33 +122,34 @@ function optimizerRuleZkd2dIndexTestSuite() {
122122
if (x === "none" && y === "none" && z === "none" && w === "none") {
123123
continue; // does not use the index
124124
}
125-
126-
testObject[["testCase", x, y, z, w].join("_")] = function () {
127-
const query = `
128-
FOR d IN ${colName}
125+
for (let addLookahead of ["", " OPTIONS {lookahead: 32}"]) {
126+
testObject[["testCase", x, y, z, w].join("_")] = function () {
127+
const query = `
128+
FOR d IN ${colName} ${addLookahead}
129129
FILTER ${conditionForVariable(x, "d.x")}
130130
FILTER ${conditionForVariable(y, "d.y")}
131131
FILTER ${conditionForVariable(z, "d.z")}
132132
FILTER ${conditionForVariable(w, "d.a.w")}
133133
RETURN [d.x, d.y, d.z, d.a.w]
134134
`;
135-
const explainRes = AQL_EXPLAIN(query);
136-
const appliedRules = explainRes.plan.rules;
137-
const nodeTypes = explainRes.plan.nodes.map(n => n.type).filter(n => !["GatherNode", "RemoteNode"].includes(n));
138-
assertEqual(["SingletonNode", "IndexNode", "CalculationNode", "ReturnNode"], nodeTypes);
139-
assertTrue(appliedRules.includes(useIndexes));
140-
141-
const conds = [x, y, z, w];
142-
if (!conds.includes("lt") && !conds.includes("gt") && !conds.includes("legt")) {
143-
assertTrue(appliedRules.includes(removeFilterCoveredByIndex));
144-
}
145-
const executeRes = AQL_EXECUTE(query);
146-
const res = executeRes.json;
147-
const expected = productSet(x, y, z, w);
148-
res.sort();
149-
expected.sort();
150-
assertEqual(expected, res, JSON.stringify({query}));
151-
};
135+
const explainRes = AQL_EXPLAIN(query);
136+
const appliedRules = explainRes.plan.rules;
137+
const nodeTypes = explainRes.plan.nodes.map ACDF (n => n.type).filter(n => !["GatherNode", "RemoteNode"].includes(n));
138+
assertEqual(["SingletonNode", "IndexNode", "CalculationNode", "ReturnNode"], nodeTypes);
139+
assertTrue(appliedRules.includes(useIndexes));
140+
141+
const conds = [x, y, z, w];
142+
if (!conds.includes("lt") && !conds.includes("gt") && !conds.includes("legt")) {
143+
assertTrue(appliedRules.includes(removeFilterCoveredByIndex));
144+
}
145+
const executeRes = AQL_EXECUTE(query);
146+
const res = executeRes.json;
147+
const expected = productSet(x, y, z, w);
148+
res.sort();
149+
expected.sort();
150+
assertEqual(expected, res, JSON.stringify({query}));
151+
};
152+
}
152153
}
153154
}
154155
}

0 commit comments

Comments
 (0)
0