8000 [zkd] Cluster support by maierlars · Pull Request #13677 · arangodb/arangodb · GitHub
[go: up one dir, main page]

Skip to content

[zkd] Cluster support #13677

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 2 commits into from
Mar 11, 2021
Merged
Show file tree
Hide file tree
Changes from all commits
Commits
File filter

Filter by extension

Filter by extension

Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
7 changes: 3 additions & 4 deletions arangod/ClusterEngine/ClusterIndex.cpp
Original file line number Diff line number Diff line change
Expand Up @@ -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"
Expand Down Expand Up @@ -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;
Expand Down Expand Up @@ -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;
Expand Down
2 changes: 2 additions & 0 deletions arangod/ClusterEngine/ClusterIndexFactory.cpp
Original file line number Diff line number Diff line change
Expand Up @@ -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);
Expand All @@ -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" =>
Expand Down
5 changes: 3 additions & 2 deletions arangod/Indexes/IndexFactory.cpp
Original file line number Diff line number Diff line change
Expand Up @@ -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 {
Expand Down
141 changes: 73 additions & 68 deletions arangod/RocksDBEngine/RocksDBZkdIndex.cpp
Original file line number Diff line number Diff line change
Expand Up @@ -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) {
Expand Down Expand Up @@ -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,
Expand Down Expand Up @@ -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(
Expand All @@ -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);

Expand Down
30 changes: 30 additions & 0 deletions arangod/RocksDBEngine/RocksDBZkdIndex.h
Original file line number Diff line number Diff line change
Expand Up @@ -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
3 changes: 2 additions & 1 deletion arangod/Zkd/ZkdHelper.cpp
Original file line number Diff line number Diff line change
Expand Up @@ -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;
Expand Down
46 changes: 21 additions & 25 deletions arangod/Zkd/ZkdHelper.h
Original file line number Diff line number Diff line change
Expand Up @@ -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> {
Expand Down Expand Up @@ -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>;
Expand Down Expand Up @@ -117,7 +115,6 @@ class BitWriter {
byte_string _buffer;
};


struct RandomBitReader {
explicit RandomBitReader(byte_string_view ref);

Expand All @@ -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 {
Expand All @@ -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
3 changes: 2 additions & 1 deletion tests/Zkd/Conversion.cpp
Original file line number Diff line number Diff line change
Expand Up @@ -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}},
Expand Down
2 changes: 2 additions & 0 deletions tests/Zkd/Library.cpp
Original file line number Diff line number Diff line change
Expand Up @@ -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()) {
Expand Down
Loading
0