* [PATCH v4 1/3] memtx: renamed memtx_tree.c to memtx_tree.cc
2019-02-28 13:38 [PATCH v4 0/3] box: introduce hint option for memtx tree index Kirill Shcherbatov
@ 2019-02-28 13:38 ` Kirill Shcherbatov
2019-02-28 13:38 ` [PATCH v4 2/3] memtx: rework memtx_tree to store arbitrary nodes Kirill Shcherbatov
` (2 subsequent siblings)
3 siblings, 0 replies; 5+ messages in thread
From: Kirill Shcherbatov @ 2019-02-28 13:38 UTC (permalink / raw)
To: tarantool-patches, vdavydov.dev; +Cc: kostja, Kirill Shcherbatov
Changed memtx_tree source extension to use C++ compiler. We need
it as we going to use templates and class methods in further
patches.
Needed for #3961
---
src/box/CMakeLists.txt | 2 +-
src/box/{memtx_tree.c => memtx_tree.cc} | 3 ++-
2 files changed, 3 insertions(+), 2 deletions(-)
rename src/box/{memtx_tree.c => memtx_tree.cc} (99%)
diff --git a/src/box/CMakeLists.txt b/src/box/CMakeLists.txt
index 59e91b65a..d4d9b7aeb 100644
--- a/src/box/CMakeLists.txt
+++ b/src/box/CMakeLists.txt
@@ -64,7 +64,7 @@ add_library(box STATIC
index_def.c
iterator_type.c
memtx_hash.c
- memtx_tree.c
+ memtx_tree.cc
memtx_rtree.c
memtx_bitset.c
engine.c
diff --git a/src/box/memtx_tree.c b/src/box/memtx_tree.cc
similarity index 99%
rename from src/box/memtx_tree.c
rename to src/box/memtx_tree.cc
index 250df7f2d..9c2bcbf8e 100644
--- a/src/box/memtx_tree.c
+++ b/src/box/memtx_tree.cc
@@ -564,7 +564,8 @@ memtx_tree_index_create_iterator(struct index *base, enum iterator_type type,
key = NULL;
}
- struct tree_iterator *it = mempool_alloc(&memtx->iterator_pool);
+ struct tree_iterator *it =
+ (struct tree_iterator *)mempool_alloc(&memtx->iterator_pool);
if (it == NULL) {
diag_set(OutOfMemory, sizeof(struct tree_iterator),
"memtx_tree_index", "iterator");
--
2.21.0
^ permalink raw reply [flat|nested] 5+ messages in thread* [PATCH v4 2/3] memtx: rework memtx_tree to store arbitrary nodes
2019-02-28 13:38 [PATCH v4 0/3] box: introduce hint option for memtx tree index Kirill Shcherbatov
2019-02-28 13:38 ` [PATCH v4 1/3] memtx: renamed memtx_tree.c to memtx_tree.cc Kirill Shcherbatov
@ 2019-02-28 13:38 ` Kirill Shcherbatov
2019-02-28 13:38 ` [PATCH v4 3/3] memtx: introduce tuple compare hint Kirill Shcherbatov
2019-03-06 9:41 ` [PATCH v4 0/3] box: introduce hint option for memtx tree index Vladimir Davydov
3 siblings, 0 replies; 5+ messages in thread
From: Kirill Shcherbatov @ 2019-02-28 13:38 UTC (permalink / raw)
To: tarantool-patches, vdavydov.dev; +Cc: kostja, Kirill Shcherbatov
Reworked memtx_tree to use class MemtxTreeData as a tree node.
The code has been rewritten to use methods of this class instead
of direct data operations. This makes possible to implement tuple
hints in subsequent patches.
Needed for #3961
---
src/box/memtx_tree.cc | 368 +++++++++++++++++++++++++++---------------
1 file changed, 242 insertions(+), 126 deletions(-)
diff --git a/src/box/memtx_tree.cc b/src/box/memtx_tree.cc
index 9c2bcbf8e..346585dea 100644
--- a/src/box/memtx_tree.cc
+++ b/src/box/memtx_tree.cc
@@ -42,39 +42,116 @@
/**
* Struct that is used as a key in BPS tree definition.
*/
-struct memtx_tree_key_data {
+class MemtxTreeKeyData {
/** Sequence of msgpacked search fields. */
const char *key;
/** Number of msgpacked search fields. */
uint32_t part_count;
+public:
+ /**
+ * Return "payload" data that this object stores:
+ * key and part_count.
+ */
+ const char *
+ get(uint32_t *part_count) const
+ {
+ *part_count = this->part_count;
+ return this->key;
+ }
+
+ /**
+ * Perform this MemtxTreeKeyData object
+ * initialization.
+ */
+ void
+ set(const char *key, uint32_t part_count, struct key_def *key_def)
+ {
+ (void)key_def;
+ this->key = key;
+ this->part_count = part_count;
+ }
};
/**
- * BPS tree element vs key comparator.
- * Defined in header in order to allow compiler to inline it.
- * @param tuple - tuple to compare.
- * @param key_data - key to compare with.
- * @param def - key definition.
- * @retval 0 if tuple == key in terms of def.
- * @retval <0 if tuple < key in terms of def.
- * @retval >0 if tuple > key in terms of def.
+ * Struct that is used as a node in BPS tree definition.
*/
-static int
-memtx_tree_compare_key(const struct tuple *tuple,
- const struct memtx_tree_key_data *key_data,
- struct key_def *def)
-{
- return tuple_compare_with_key(tuple, key_data->key,
- key_data->part_count, def);
-}
+class MemtxTreeData {
+ /** Data tuple pointer. */
+ struct tuple *tuple;
+public:
+ /**
+ * Return "payload" data that this object stores:
+ * tuple.
+ */
+ struct tuple *
+ get(void) const
+ {
+ return tuple;
+ }
+
+ /** Perform this MemtxTreeData object initialization. */
+ void
+ set(struct tuple *tuple, struct key_def *key_def)
+ {
+ (void)key_def;
+ this->tuple = tuple;
+ }
+
+ /** Clear this MemtxTreeData object. */
+ void
+ clear(void)
+ {
+ this->tuple = NULL;
+ }
+
+ /**
+ * Test if this MemtxTreeData and elem MemtxTreeData
+ * represent exactly the same data.
+ * While MemtxTreeData::compare performs binary data
+ * comparison, this helper checks if the elements are
+ * identical, i.e. initialized with the same arguments.
+ */
+ bool
+ is_identical(const MemtxTreeData *elem) const
+ {
+ return this->tuple == elem->tuple;
+ }
+
+ /**
+ * Compare this MemtxTreeData object with other elem
+ * MemtxTreeData using the key definition is specified.
+ */
+ int
+ compare(const MemtxTreeData *elem, struct key_def *key_def) const
+ {
+ return tuple_compare(this->tuple, elem->tuple, key_def);
+ }
+
+ /**
+ * Compare this MemtxTreeData object with key
+ * MemtxTreeKeyData using the key definition is specified.
+ */
+ int
+ compare_with_key(const MemtxTreeKeyData *key,
+ struct key_def *key_def) const
+ {
+ uint32_t part_count;
+ const char *key_data = key->get(&part_count);
+ return tuple_compare_with_key(this->tuple, key_data, part_count,
+ key_def);
+ }
+};
#define BPS_TREE_NAME memtx_tree
#define BPS_TREE_BLOCK_SIZE (512)
#define BPS_TREE_EXTENT_SIZE MEMTX_EXTENT_SIZE
-#define BPS_TREE_COMPARE(a, b, arg) tuple_compare(a, b, arg)
-#define BPS_TREE_COMPARE_KEY(a, b, arg) memtx_tree_compare_key(a, b, arg)
-#define bps_tree_elem_t struct tuple *
-#define bps_tree_key_t struct memtx_tree_key_data *
+#define BPS_TREE_COMPARE(elem_a, elem_b, key_def) \
+ (&elem_a)->compare(&elem_b, key_def)
+#define BPS_TREE_COMPARE_KEY(elem, key_ptr, key_def) \
+ (&elem)->compare_with_key(key_ptr, key_def)
+#define BPS_TREE_IDENTICAL(elem_a, elem_b) (&elem_a)->is_identical(&elem_b)
+#define bps_tree_elem_t MemtxTreeData
+#define bps_tree_key_t MemtxTreeKeyData *
#define bps_tree_arg_t struct key_def *
#include "salad/bps_tree.h"
@@ -84,6 +161,7 @@ memtx_tree_compare_key(const struct tuple *tuple,
#undef BPS_TREE_EXTENT_SIZE
#undef BPS_TREE_COMPARE
#undef BPS_TREE_COMPARE_KEY
+#undef BPS_TREE_IDENTICAL
#undef bps_tree_elem_t
#undef bps_tree_key_t
#undef bps_tree_arg_t
@@ -91,7 +169,7 @@ memtx_tree_compare_key(const struct tuple *tuple,
struct memtx_tree_index {
struct index base;
struct memtx_tree tree;
- struct tuple **build_array;
+ MemtxTreeData *build_array;
size_t build_array_size, build_array_alloc_size;
struct memtx_gc_task gc_task;
struct memtx_tree_iterator gc_iterator;
@@ -102,8 +180,8 @@ struct memtx_tree_index {
static int
memtx_tree_qcompare(const void* a, const void *b, void *c)
{
- return tuple_compare(*(struct tuple **)a,
- *(struct tuple **)b, (struct key_def *)c);
+ MemtxTreeData *elem_a = (MemtxTreeData *)a;
+ return elem_a->compare((MemtxTreeData *)b, (struct key_def *)c);
}
/* {{{ MemtxTree Iterators ****************************************/
@@ -113,8 +191,8 @@ struct tree_iterator {
struct index_def *index_def;
struct memtx_tree_iterator tree_iterator;
enum iterator_type type;
- struct memtx_tree_key_data key_data;
- struct tuple *current_tuple;
+ MemtxTreeKeyData key_data;
+ MemtxTreeData current;
/** Memory pool the iterator was allocated from. */
struct mempool *pool;
};
@@ -127,7 +205,7 @@ static void
tree_iterator_free(struct iterator *iterator);
static inline struct tree_iterator *
-tree_iterator(struct iterator *it)
+tree_iterator_cast(struct iterator *it)
{
assert(it->free == tree_iterator_free);
return (struct tree_iterator *) it;
@@ -136,9 +214,10 @@ tree_iterator(struct iterator *it)
static void
tree_iterator_free(struct iterator *iterator)
{
- struct tree_iterator *it = tree_iterator(iterator);
- if (it->current_tuple != NULL)
- tuple_unref(it->current_tuple);
+ struct tree_iterator *it = tree_iterator_cast(iterator);
+ struct tuple *tuple = it->current.get();
+ if (tuple != NULL)
+ tuple_unref(tuple);
mempool_free(it->pool, it);
}
@@ -153,25 +232,27 @@ tree_iterator_dummie(struct iterator *iterator, struct tuple **ret)
static int
tree_iterator_next(struct iterator *iterator, struct tuple **ret)
{
- struct tuple **res;
- struct tree_iterator *it = tree_iterator(iterator);
- assert(it->current_tuple != NULL);
- struct tuple **check = memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
- if (check == NULL || *check != it->current_tuple)
+ struct tree_iterator *it = tree_iterator_cast(iterator);
+ assert(it->current.get() != NULL);
+ MemtxTreeData *check =
+ memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
+ if (check == NULL || !check->is_identical(&it->current)) {
it->tree_iterator =
- memtx_tree_upper_bound_elem(it->tree, it->current_tuple,
- NULL);
- else
+ memtx_tree_upper_bound_elem(it->tree, it->current, NULL);
+ } else {
memtx_tree_iterator_next(it->tree, &it->tree_iterator);
- tuple_unref(it->current_tuple);
- it->current_tuple = NULL;
- res = memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
+ }
+ tuple_unref(it->current.get());
+ MemtxTreeData *res =
+ memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
if (res == NULL) {
iterator->next = tree_iterator_dummie;
+ it->current.clear();
*ret = NULL;
} else {
- *ret = it->current_tuple = *res;
- tuple_ref(it->current_tuple);
+ *ret = res->get();
+ tuple_ref(*ret);
+ it->current = *res;
}
return 0;
}
@@ -179,23 +260,26 @@ tree_iterator_next(struct iterator *iterator, struct tuple **ret)
static int
tree_iterator_prev(struct iterator *iterator, struct tuple **ret)
{
- struct tree_iterator *it = tree_iterator(iterator);
- assert(it->current_tuple != NULL);
- struct tuple **check = memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
- if (check == NULL || *check != it->current_tuple)
+ struct tree_iterator *it = tree_iterator_cast(iterator);
+ assert(it->current.get() != NULL);
+ MemtxTreeData *check =
+ memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
+ if (check == NULL || !check->is_identical(&it->current)) {
it->tree_iterator =
- memtx_tree_lower_bound_elem(it->tree, it->current_tuple,
- NULL);
+ memtx_tree_lower_bound_elem(it->tree, it->current, NULL);
+ }
memtx_tree_iterator_prev(it->tree, &it->tree_iterator);
- tuple_unref(it->current_tuple);
- it->current_tuple = NULL;
- struct tuple **res = memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
+ tuple_unref(it->current.get());
+ MemtxTreeData *res =
+ memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
if (!res) {
iterator->next = tree_iterator_dummie;
+ it->current.clear();
*ret = NULL;
} else {
- *ret = it->current_tuple = *res;
- tuple_ref(it->current_tuple);
+ *ret = res->get();
+ tuple_ref(*ret);
+ it->current = *res;
}
return 0;
}
@@ -203,28 +287,29 @@ tree_iterator_prev(struct iterator *iterator, struct tuple **ret)
static int
tree_iterator_next_equal(struct iterator *iterator, struct tuple **ret)
{
- struct tree_iterator *it = tree_iterator(iterator);
- assert(it->current_tuple != NULL);
- struct tuple **check = memtx_tree_iterator_get_elem(it->tree,
- &it->tree_iterator);
- if (check == NULL || *check != it->current_tuple)
+ struct tree_iterator *it = tree_iterator_cast(iterator);
+ assert(it->current.get() != NULL);
+ MemtxTreeData *check =
+ memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
+ if (check == NULL || !check->is_identical(&it->current)) {
it->tree_iterator =
- memtx_tree_upper_bound_elem(it->tree, it->current_tuple,
- NULL);
- else
+ memtx_tree_upper_bound_elem(it->tree, it->current, NULL);
+ } else {
memtx_tree_iterator_next(it->tree, &it->tree_iterator);
- tuple_unref(it->current_tuple);
- it->current_tuple = NULL;
- struct tuple **res = memtx_tree_iterator_get_elem(it->tree,
- &it->tree_iterator);
+ }
+ tuple_unref(it->current.get());
+ MemtxTreeData *res =
+ memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
/* Use user key def to save a few loops. */
- if (!res || memtx_tree_compare_key(*res, &it->key_data,
- it->index_def->key_def) != 0) {
+ if (res == NULL ||
+ res->compare_with_key(&it->key_data, it->index_def->key_def) != 0) {
iterator->next = tree_iterator_dummie;
+ it->current.clear();
*ret = NULL;
} else {
- *ret = it->current_tuple = *res;
- tuple_ref(it->current_tuple);
+ *ret = res->get();
+ tuple_ref(*ret);
+ it->current = *res;
}
return 0;
}
@@ -232,27 +317,28 @@ tree_iterator_next_equal(struct iterator *iterator, struct tuple **ret)
static int
tree_iterator_prev_equal(struct iterator *iterator, struct tuple **ret)
{
- struct tree_iterator *it = tree_iterator(iterator);
- assert(it->current_tuple != NULL);
- struct tuple **check = memtx_tree_iterator_get_elem(it->tree,
- &it->tree_iterator);
- if (check == NULL || *check != it->current_tuple)
+ struct tree_iterator *it = tree_iterator_cast(iterator);
+ assert(it->current.get() != NULL);
+ MemtxTreeData *check =
+ memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
+ if (check == NULL || !check->is_identical(&it->current)) {
it->tree_iterator =
- memtx_tree_lower_bound_elem(it->tree, it->current_tuple,
- NULL);
+ memtx_tree_lower_bound_elem(it->tree, it->current, NULL);
+ }
memtx_tree_iterator_prev(it->tree, &it->tree_iterator);
- tuple_unref(it->current_tuple);
- it->current_tuple = NULL;
- struct tuple **res = memtx_tree_iterator_get_elem(it->tree,
- &it->tree_iterator);
+ tuple_unref(it->current.get());
+ MemtxTreeData *res =
+ memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
/* Use user key def to save a few loops. */
- if (!res || memtx_tree_compare_key(*res, &it->key_data,
- it->index_def->key_def) != 0) {
+ if (res == NULL ||
+ res->compare_with_key(&it->key_data, it->index_def->key_def) != 0) {
iterator->next = tree_iterator_dummie;
+ it->current.clear();
*ret = NULL;
} else {
- *ret = it->current_tuple = *res;
- tuple_ref(it->current_tuple);
+ *ret = res->get();
+ tuple_ref(*ret);
+ it->current = *res;
}
return 0;
}
@@ -260,7 +346,7 @@ tree_iterator_prev_equal(struct iterator *iterator, struct tuple **ret)
static void
tree_iterator_set_next_method(struct tree_iterator *it)
{
- assert(it->current_tuple != NULL);
+ assert(it->current.get() != NULL);
switch (it->type) {
case ITER_EQ:
it->base.next = tree_iterator_next_equal;
@@ -289,13 +375,15 @@ static int
tree_iterator_start(struct iterator *iterator, struct tuple **ret)
{
*ret = NULL;
- struct tree_iterator *it = tree_iterator(iterator);
+ struct tree_iterator *it = tree_iterator_cast(iterator);
it->base.next = tree_iterator_dummie;
const struct memtx_tree *tree = it->tree;
enum iterator_type type = it->type;
bool exact = false;
- assert(it->current_tuple == NULL);
- if (it->key_data.key == 0) {
+ assert(it->current.get() == NULL);
+ uint32_t part_count;
+ const char *key = it->key_data.get(&part_count);
+ if (key == NULL) {
if (iterator_type_is_reverse(it->type))
it->tree_iterator = memtx_tree_iterator_last(tree);
else
@@ -331,12 +419,13 @@ tree_iterator_start(struct iterator *iterator, struct tuple **ret)
}
}
- struct tuple **res = memtx_tree_iterator_get_elem(it->tree,
- &it->tree_iterator);
+ MemtxTreeData *res =
+ memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
if (!res)
return 0;
- *ret = it->current_tuple = *res;
- tuple_ref(it->current_tuple);
+ *ret = res->get();
+ tuple_ref(*ret);
+ it->current = *res;
tree_iterator_set_next_method(it);
return 0;
}
@@ -390,7 +479,8 @@ memtx_tree_index_gc_run(struct memtx_gc_task *task, bool *done)
unsigned int loops = 0;
while (!memtx_tree_iterator_is_invalid(itr)) {
- struct tuple *tuple = *memtx_tree_iterator_get_elem(tree, itr);
+ MemtxTreeData *res = memtx_tree_iterator_get_elem(tree, itr);
+ struct tuple *tuple = res->get();
memtx_tree_iterator_next(tree, itr);
tuple_unref(tuple);
if (++loops >= YIELD_LOOPS) {
@@ -470,8 +560,8 @@ static int
memtx_tree_index_random(struct index *base, uint32_t rnd, struct tuple **result)
{
struct memtx_tree_index *index = (struct memtx_tree_index *)base;
- struct tuple **res = memtx_tree_random(&index->tree, rnd);
- *result = res != NULL ? *res : NULL;
+ MemtxTreeData *res = memtx_tree_random(&index->tree, rnd);
+ *result = res != NULL ? res->get() : NULL;
return 0;
}
@@ -491,26 +581,50 @@ memtx_tree_index_get(struct index *base, const char *key,
assert(base->def->opts.is_unique &&
part_count == base->def->key_def->part_count);
struct memtx_tree_index *index = (struct memtx_tree_index *)base;
- struct memtx_tree_key_data key_data;
- key_data.key = key;
- key_data.part_count = part_count;
- struct tuple **res = memtx_tree_find(&index->tree, &key_data);
- *result = res != NULL ? *res : NULL;
+ MemtxTreeKeyData key_data;
+ struct key_def *cmp_def = memtx_tree_index_cmp_def(index);
+ key_data.set(key, part_count, cmp_def);
+ MemtxTreeData *res = memtx_tree_find(&index->tree, &key_data);
+ *result = res != NULL ? res->get() : NULL;
return 0;
}
+static int
+memtx_tree_index_insert_tuple(struct index *base, struct tuple *tuple,
+ struct tuple **replaced)
+{
+ struct memtx_tree_index *index = (struct memtx_tree_index *)base;
+ MemtxTreeData data;
+ data.set(tuple, index->tree.arg);
+ MemtxTreeData data_replaced;
+ data_replaced.clear();
+ int rc = memtx_tree_insert(&index->tree, data, &data_replaced);
+ if (replaced != NULL)
+ *replaced = data_replaced.get();
+ return rc;
+}
+
+static void
+memtx_tree_index_delete_tuple(struct index *base, struct tuple *tuple)
+{
+ struct memtx_tree_index *index = (struct memtx_tree_index *)base;
+ MemtxTreeData data;
+ data.set(tuple, index->tree.arg);
+ memtx_tree_delete(&index->tree, data);
+}
+
static int
memtx_tree_index_replace(struct index *base, struct tuple *old_tuple,
struct tuple *new_tuple, enum dup_replace_mode mode,
struct tuple **result)
{
- struct memtx_tree_index *index = (struct memtx_tree_index *)base;
if (new_tuple) {
struct tuple *dup_tuple = NULL;
/* Try to optimistically replace the new_tuple. */
- int tree_res = memtx_tree_insert(&index->tree,
- new_tuple, &dup_tuple);
+ int tree_res =
+ memtx_tree_index_insert_tuple(base, new_tuple,
+ &dup_tuple);
if (tree_res) {
diag_set(OutOfMemory, MEMTX_EXTENT_SIZE,
"memtx_tree_index", "replace");
@@ -520,9 +634,9 @@ memtx_tree_index_replace(struct index *base, struct tuple *old_tuple,
uint32_t errcode = replace_check_dup(old_tuple,
dup_tuple, mode);
if (errcode) {
- memtx_tree_delete(&index->tree, new_tuple);
+ memtx_tree_index_delete_tuple(base, new_tuple);
if (dup_tuple)
- memtx_tree_insert(&index->tree, dup_tuple, 0);
+ memtx_tree_index_insert_tuple(base, dup_tuple, 0);
struct space *sp = space_cache_find(base->def->space_id);
if (sp != NULL)
diag_set(ClientError, errcode, base->def->name,
@@ -534,9 +648,8 @@ memtx_tree_index_replace(struct index *base, struct tuple *old_tuple,
return 0;
}
}
- if (old_tuple) {
- memtx_tree_delete(&index->tree, old_tuple);
- }
+ if (old_tuple)
+ memtx_tree_index_delete_tuple(base, old_tuple);
*result = old_tuple;
return 0;
}
@@ -576,12 +689,12 @@ memtx_tree_index_create_iterator(struct index *base, enum iterator_type type,
it->base.next = tree_iterator_start;
it->base.free = tree_iterator_free;
it->type = type;
- it->key_data.key = key;
- it->key_data.part_count = part_count;
+ struct key_def *cmp_def = memtx_tree_index_cmp_def(index);
+ it->key_data.set(key, part_count, cmp_def);
it->index_def = base->def;
it->tree = &index->tree;
it->tree_iterator = memtx_tree_invalid_iterator();
- it->current_tuple = NULL;
+ it->current.clear();
return (struct iterator *)it;
}
@@ -599,8 +712,9 @@ memtx_tree_index_reserve(struct index *base, uint32_t size_hint)
struct memtx_tree_index *index = (struct memtx_tree_index *)base;
if (size_hint < index->build_array_alloc_size)
return 0;
- struct tuple **tmp = (struct tuple **)realloc(index->build_array,
- size_hint * sizeof(*tmp));
+ MemtxTreeData *tmp =
+ (MemtxTreeData *)realloc(index->build_array,
+ size_hint * sizeof(*tmp));
if (tmp == NULL) {
diag_set(OutOfMemory, size_hint * sizeof(*tmp),
"memtx_tree_index", "reserve");
@@ -616,22 +730,23 @@ memtx_tree_index_build_next(struct index *base, struct tuple *tuple)
{
struct memtx_tree_index *index = (struct memtx_tree_index *)base;
if (index->build_array == NULL) {
- index->build_array = (struct tuple **)malloc(MEMTX_EXTENT_SIZE);
+ index->build_array =
+ (MemtxTreeData *)malloc(MEMTX_EXTENT_SIZE);
if (index->build_array == NULL) {
diag_set(OutOfMemory, MEMTX_EXTENT_SIZE,
"memtx_tree_index", "build_next");
return -1;
}
index->build_array_alloc_size =
- MEMTX_EXTENT_SIZE / sizeof(struct tuple*);
+ MEMTX_EXTENT_SIZE / sizeof(index->build_array[0]);
}
assert(index->build_array_size <= index->build_array_alloc_size);
if (index->build_array_size == index->build_array_alloc_size) {
index->build_array_alloc_size = index->build_array_alloc_size +
index->build_array_alloc_size / 2;
- struct tuple **tmp = (struct tuple **)
- realloc(index->build_array,
- index->build_array_alloc_size * sizeof(*tmp));
+ MemtxTreeData *tmp =
+ (MemtxTreeData *)realloc(index->build_array,
+ index->build_array_alloc_size * sizeof(*tmp));
if (tmp == NULL) {
diag_set(OutOfMemory, index->build_array_alloc_size *
sizeof(*tmp), "memtx_tree_index", "build_next");
@@ -639,7 +754,9 @@ memtx_tree_index_build_next(struct index *base, struct tuple *tuple)
}
index->build_array = tmp;
}
- index->build_array[index->build_array_size++] = tuple;
+ MemtxTreeData *elem =
+ &index->build_array[index->build_array_size++];
+ elem->set(tuple, memtx_tree_index_cmp_def(index));
return 0;
}
@@ -649,10 +766,9 @@ memtx_tree_index_end_build(struct index *base)
struct memtx_tree_index *index = (struct memtx_tree_index *)base;
struct key_def *cmp_def = memtx_tree_index_cmp_def(index);
qsort_arg(index->build_array, index->build_array_size,
- sizeof(struct tuple *),
- memtx_tree_qcompare, cmp_def);
+ sizeof(index->build_array[0]), memtx_tree_qcompare, cmp_def);
memtx_tree_build(&index->tree, index->build_array,
- index->build_array_size);
+ index->build_array_size);
free(index->build_array);
index->build_array = NULL;
@@ -683,12 +799,12 @@ tree_snapshot_iterator_next(struct snapshot_iterator *iterator, uint32_t *size)
assert(iterator->free == tree_snapshot_iterator_free);
struct tree_snapshot_iterator *it =
(struct tree_snapshot_iterator *)iterator;
- struct tuple **res = memtx_tree_iterator_get_elem(it->tree,
- &it->tree_iterator);
+ MemtxTreeData *res =
+ memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
if (res == NULL)
return NULL;
memtx_tree_iterator_next(it->tree, &it->tree_iterator);
- return tuple_data_range(*res, size);
+ return tuple_data_range(res->get(), size);
}
/**
--
2.21.0
^ permalink raw reply [flat|nested] 5+ messages in thread* [PATCH v4 3/3] memtx: introduce tuple compare hint
2019-02-28 13:38 [PATCH v4 0/3] box: introduce hint option for memtx tree index Kirill Shcherbatov
2019-02-28 13:38 ` [PATCH v4 1/3] memtx: renamed memtx_tree.c to memtx_tree.cc Kirill Shcherbatov
2019-02-28 13:38 ` [PATCH v4 2/3] memtx: rework memtx_tree to store arbitrary nodes Kirill Shcherbatov
@ 2019-02-28 13:38 ` Kirill Shcherbatov
2019-03-06 9:41 ` [PATCH v4 0/3] box: introduce hint option for memtx tree index Vladimir Davydov
3 siblings, 0 replies; 5+ messages in thread
From: Kirill Shcherbatov @ 2019-02-28 13:38 UTC (permalink / raw)
To: tarantool-patches, vdavydov.dev; +Cc: kostja, Alexandr Lyapunov
From: Alexandr Lyapunov <aleks@tarantool.org>
Implement functions for retrieving tuple hints for a particular
key_def. Hint is an integer that can be used for tuple comparison
optimization: if a hint of one tuple is less than a hint of another
then the first tuple is definitely less than the second; only if
hints are equal tuple_compare must be called for getting comparison
result.
Hints are calculated using only the first part of key_def.
Hints are only useful when:
* they are precalculated and stored along with the tuple;
calculation is not cheap (cheaper than tuple_compare btw) but
precalculated hints allow to compare tuples without even fetching
tuple data.
* first part of key_def is 'string'(for now)
* since hint is calculated using only the first part of key_def
(and only first several characters if it is a string) this part
must be different with high probability for every tuple pair.
@kshcherbatov: massive refactoring, new hints for number,
boolean, binary collation.
Closes #3961
---
src/box/CMakeLists.txt | 1 +
src/box/key_def.c | 2 +
src/box/key_def.h | 44 ++++++
src/box/memtx_tree.cc | 43 +++++-
src/box/tuple_hint.cc | 301 +++++++++++++++++++++++++++++++++++++++++
src/box/tuple_hint.h | 60 ++++++++
src/lib/coll/coll.c | 33 +++++
src/lib/coll/coll.h | 4 +
8 files changed, 484 insertions(+), 4 deletions(-)
create mode 100644 src/box/tuple_hint.cc
create mode 100644 src/box/tuple_hint.h
diff --git a/src/box/CMakeLists.txt b/src/box/CMakeLists.txt
index d4d9b7aeb..f0c508c02 100644
--- a/src/box/CMakeLists.txt
+++ b/src/box/CMakeLists.txt
@@ -38,6 +38,7 @@ add_library(tuple STATIC
tuple_format.c
tuple_update.c
tuple_compare.cc
+ tuple_hint.cc
tuple_extract_key.cc
tuple_hash.cc
tuple_bloom.c
diff --git a/src/box/key_def.c b/src/box/key_def.c
index 432b72a97..ced5b0580 100644
--- a/src/box/key_def.c
+++ b/src/box/key_def.c
@@ -34,6 +34,7 @@
#include "tuple_compare.h"
#include "tuple_extract_key.h"
#include "tuple_hash.h"
+#include "tuple_hint.h"
#include "column_mask.h"
#include "schema_def.h"
#include "coll_id_cache.h"
@@ -135,6 +136,7 @@ key_def_set_func(struct key_def *def)
key_def_set_compare_func(def);
key_def_set_hash_func(def);
key_def_set_extract_func(def);
+ key_def_set_hint_func(def);
}
static void
diff --git a/src/box/key_def.h b/src/box/key_def.h
index dd62f6a35..00775368f 100644
--- a/src/box/key_def.h
+++ b/src/box/key_def.h
@@ -153,6 +153,13 @@ typedef uint32_t (*tuple_hash_t)(const struct tuple *tuple,
typedef uint32_t (*key_hash_t)(const char *key,
struct key_def *key_def);
+/** @copydoc tuple_hint() */
+typedef uint64_t (*tuple_hint_t)(const struct tuple *tuple,
+ struct key_def *key_def);
+
+/** @copydoc key_hint() */
+typedef uint64_t (*key_hint_t)(const char *key, struct key_def *key_def);
+
/* Definition of a multipart key. */
struct key_def {
/** @see tuple_compare() */
@@ -167,6 +174,10 @@ struct key_def {
tuple_hash_t tuple_hash;
/** @see key_hash() */
key_hash_t key_hash;
+ /** @see tuple_hint() */
+ tuple_hint_t tuple_hint;
+ /** @see key_hint() */
+ key_hint_t key_hint;
/**
* Minimal part count which always is unique. For example,
* if a secondary index is unique, then
@@ -624,6 +635,39 @@ key_hash(const char *key, struct key_def *key_def)
return key_def->key_hash(key, key_def);
}
+ /*
+ * Get a comparison hint of a tuple.
+ * Hint is such a function h(tuple) in terms of particular key_def that
+ * has follows rules:
+ * if h(t1) < h(t2) then t1 < t2;
+ * if h(t1) > h(t2) then t1 > t2;
+ * if t1 == t2 then h(t1) == h(t2);
+ * These rules means that instead of direct tuple vs tuple (or tuple vs key)
+ * comparison one may compare theirs hints first; and only if theirs hints
+ * are equal compare the tuples themselves.
+ * @param tuple - tuple to get hint of.
+ * @param key_def - key_def that defines which comparison is used.
+ * @return the hint.
+ */
+static inline uint64_t
+tuple_hint(const struct tuple *tuple, struct key_def *key_def)
+{
+ return key_def->tuple_hint(tuple, key_def);
+}
+
+/**
+ * Get a comparison hint of a key.
+ * @See tuple_hint for hint term definition.
+ * @param key - key to get hint of.
+ * @param key_def - key_def that defines which comparison is used.
+ * @return the hint.
+ */
+static inline uint64_t
+key_hint(const char *key, struct key_def *key_def)
+{
+ return key_def->key_hint(key, key_def);
+}
+
#if defined(__cplusplus)
} /* extern "C" */
#endif /* defined(__cplusplus) */
diff --git a/src/box/memtx_tree.cc b/src/box/memtx_tree.cc
index 346585dea..2b8a07f00 100644
--- a/src/box/memtx_tree.cc
+++ b/src/box/memtx_tree.cc
@@ -36,6 +36,7 @@
#include "memory.h"
#include "fiber.h"
#include "tuple.h"
+#include "tuple_hint.h"
#include <third_party/qsort_arg.h>
#include <small/mempool.h>
@@ -47,6 +48,11 @@ class MemtxTreeKeyData {
const char *key;
/** Number of msgpacked search fields. */
uint32_t part_count;
+ /**
+ * Comparison hint. Calculated automatically on method
+ * MemtxTreeKeyData::set.
+ */
+ uint64_t hint;
public:
/**
* Return "payload" data that this object stores:
@@ -59,6 +65,16 @@ public:
return this->key;
}
+ /**
+ * Return comparasion hint is calculated before "payload"
+ * store on MemtxTreeKeyData::set call.
+ */
+ uint64_t
+ get_hint(void) const
+ {
+ return this->hint;
+ }
+
/**
* Perform this MemtxTreeKeyData object
* initialization.
@@ -66,9 +82,9 @@ public:
void
set(const char *key, uint32_t part_count, struct key_def *key_def)
{
- (void)key_def;
this->key = key;
this->part_count = part_count;
+ this->hint = part_count > 0 ? key_hint(key, key_def) : 0;
}
};
@@ -78,6 +94,11 @@ public:
class MemtxTreeData {
/** Data tuple pointer. */
struct tuple *tuple;
+ /**
+ * Comparison hint. Calculated automatically on method
+ * MemtxTreeData::set.
+ */
+ uint64_t hint;
public:
/**
* Return "payload" data that this object stores:
@@ -95,6 +116,7 @@ public:
{
(void)key_def;
this->tuple = tuple;
+ this->hint = tuple_hint(tuple, key_def);
}
/** Clear this MemtxTreeData object. */
@@ -124,7 +146,13 @@ public:
int
compare(const MemtxTreeData *elem, struct key_def *key_def) const
{
- return tuple_compare(this->tuple, elem->tuple, key_def);
+ if (likely(this->hint != elem->hint &&
+ this->hint != INVALID_HINT &&
+ elem->hint != INVALID_HINT)) {
+ return this->hint < elem->hint ? -1 : 1;
+ } else {
+ return tuple_compare(this->tuple, elem->tuple, key_def);
+ }
}
/**
@@ -137,8 +165,15 @@ public:
{
uint32_t part_count;
const char *key_data = key->get(&part_count);
- return tuple_compare_with_key(this->tuple, key_data, part_count,
- key_def);
+ uint64_t key_hint = key->get_hint();
+ if (likely(this->hint != key_hint &&
+ this->hint != INVALID_HINT &&
+ key_hint != INVALID_HINT)) {
+ return this->hint < key_hint ? -1 : 1;
+ } else {
+ return tuple_compare_with_key(this->tuple, key_data,
+ part_count, key_def);
+ }
}
};
diff --git a/src/box/tuple_hint.cc b/src/box/tuple_hint.cc
new file mode 100644
index 000000000..5acabc985
--- /dev/null
+++ b/src/box/tuple_hint.cc
@@ -0,0 +1,301 @@
+/*
+ * Copyright 2010-2019, Tarantool AUTHORS, please see AUTHORS file.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above
+ * copyright notice, this list of conditions and the
+ * following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above
+ * copyright notice, this list of conditions and the following
+ * disclaimer in the documentation and/or other materials
+ * provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY <COPYRIGHT HOLDER> ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
+ * <COPYRIGHT HOLDER> OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
+ * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
+ * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+#include "tuple.h"
+#include "tuple_hint.h"
+#include "lib/coll/coll.h"
+#include <math.h>
+
+static uint64_t
+key_hint_default(const char *key, struct key_def *key_def)
+{
+ (void)key;
+ (void)key_def;
+ return INVALID_HINT;
+}
+
+static uint64_t
+tuple_hint_default(const struct tuple *tuple, struct key_def *key_def)
+{
+ (void)tuple;
+ (void)key_def;
+ return INVALID_HINT;
+}
+
+template<bool is_nullable>
+static uint64_t
+key_hint_uint(const char *key, struct key_def *key_def)
+{
+ (void)key_def;
+ assert(key_part_is_nullable(key_def->parts) == is_nullable);
+ assert(key_def->parts->type == FIELD_TYPE_UNSIGNED);
+ if (is_nullable && mp_typeof(*key) == MP_NIL)
+ return 0;
+ assert(mp_typeof(*key) == MP_UINT);
+ uint64_t val = mp_decode_uint(&key);
+ if (unlikely(val > INT64_MAX))
+ return INT64_MAX;
+ return val - (uint64_t)INT64_MIN;
+}
+
+template<bool is_nullable>
+static uint64_t
+tuple_hint_uint(const struct tuple *tuple, struct key_def *key_def)
+{
+ assert(key_part_is_nullable(key_def->parts) == is_nullable);
+ assert(key_def->parts->type == FIELD_TYPE_UNSIGNED);
+ const char *field = tuple_field_by_part(tuple, key_def->parts);
+ if (is_nullable && field == NULL)
+ return 0;
+ return key_hint_uint<is_nullable>(field, key_def);
+}
+
+template<bool is_nullable>
+static uint64_t
+key_hint_int(const char *key, struct key_def *key_def)
+{
+ assert(key_part_is_nullable(key_def->parts) == is_nullable);
+ assert(key_def->parts->type == FIELD_TYPE_INTEGER);
+ if (is_nullable && mp_typeof(*key) == MP_NIL)
+ return 0;
+ if (mp_typeof(*key) == MP_UINT) {
+ uint64_t val = mp_decode_uint(&key);
+ if (unlikely(val > INT64_MAX))
+ return INT64_MAX;
+ return val - (uint64_t)INT64_MIN;
+ } else {
+ assert(mp_typeof(*key) == MP_INT);
+ int64_t val = mp_decode_int(&key);
+ return (uint64_t)val - (uint64_t)INT64_MIN;
+ }
+}
+
+template<bool is_nullable>
+static uint64_t
+tuple_hint_int(const struct tuple *tuple, struct key_def *key_def)
+{
+ assert(key_part_is_nullable(key_def->parts) == is_nullable);
+ assert(key_def->parts->type == FIELD_TYPE_INTEGER);
+ const char *field = tuple_field_by_part(tuple, key_def->parts);
+ if (is_nullable && field == NULL)
+ return 0;
+ return key_hint_int<is_nullable>(field, key_def);
+}
+
+template<bool is_nullable>
+static uint64_t
+key_hint_number(const char *key, struct key_def *key_def)
+{
+ assert(key_part_is_nullable(key_def->parts) == is_nullable);
+ assert(key_def->parts->type == FIELD_TYPE_NUMBER);
+ if (is_nullable && mp_typeof(*key) == MP_NIL)
+ return 0;
+ uint64_t val = 0;
+ switch (mp_typeof(*key)) {
+ case MP_FLOAT:
+ case MP_DOUBLE: {
+ double f = mp_typeof(*key) == MP_FLOAT ?
+ mp_decode_float(&key) : mp_decode_double(&key);
+ if (isnan(f) || isinf(f))
+ return INVALID_HINT;
+ double ival;
+ (void)modf(f, &ival);
+ if (unlikely(ival >= (double)INT64_MAX))
+ return INT64_MAX;
+ if (unlikely(ival <= (double)INT64_MIN))
+ return 0;
+ val = (uint64_t)ival;
+ break;
+ }
+ case MP_INT: {
+ val = (uint64_t)mp_decode_int(&key);
+ break;
+ }
+ case MP_UINT: {
+ val = mp_decode_uint(&key);
+ if (val > INT64_MAX)
+ return INT64_MAX;
+ break;
+ }
+ default:
+ unreachable();
+ }
+ return val - (uint64_t)INT64_MIN;
+}
+
+template<bool is_nullable>
+static uint64_t
+tuple_hint_number(const struct tuple *tuple, struct key_def *key_def)
+{
+ assert(key_part_is_nullable(key_def->parts) == is_nullable);
+ assert(key_def->parts->type == FIELD_TYPE_NUMBER);
+ const char *field = tuple_field_by_part(tuple, key_def->parts);
+ if (is_nullable && field == NULL)
+ return 0;
+ return key_hint_number<is_nullable>(field, key_def);
+}
+
+template<bool is_nullable>
+static uint64_t
+key_hint_boolean(const char *key, struct key_def *key_def)
+{
+ assert(key_part_is_nullable(key_def->parts) == is_nullable);
+ assert(key_def->parts->type == FIELD_TYPE_BOOLEAN);
+ if (is_nullable && mp_typeof(*key) == MP_NIL)
+ return 0;
+ bool val = mp_decode_bool(&key);
+ return (uint64_t)val - (uint64_t)INT64_MIN;
+}
+
+template<bool is_nullable>
+static uint64_t
+tuple_hint_boolean(const struct tuple *tuple, struct key_def *key_def)
+{
+ assert(key_part_is_nullable(key_def->parts) == is_nullable);
+ assert(key_def->parts->type == FIELD_TYPE_BOOLEAN);
+ const char *field = tuple_field_by_part(tuple, key_def->parts);
+ if (is_nullable && field == NULL)
+ return 0;
+ return key_hint_boolean<is_nullable>(field, key_def);
+}
+
+template<bool is_nullable>
+static uint64_t
+key_hint_string(const char *key, struct key_def *key_def)
+{
+ (void)key_def;
+ assert(key_part_is_nullable(key_def->parts) == is_nullable);
+ assert(key_def->parts->coll == NULL);
+ assert(key_def->parts->type == FIELD_TYPE_STRING);
+ if (is_nullable && mp_typeof(*key) == MP_NIL)
+ return 0;
+ assert(mp_typeof(*key) == MP_STR);
+ uint32_t len;
+ const unsigned char *str =
+ (const unsigned char *)mp_decode_str(&key, &len);
+ uint64_t result = 0;
+ uint32_t process_len = MIN(len, 8);
+ for (uint32_t i = 0; i < process_len; i++) {
+ result <<= 8;
+ result |= str[i];
+ }
+ result <<= 8 * (8 - process_len);
+ return result;
+}
+
+template<bool is_nullable>
+static uint64_t
+tuple_hint_string(const struct tuple *tuple, struct key_def *key_def)
+{
+ assert(key_part_is_nullable(key_def->parts) == is_nullable);
+ assert(key_def->parts->coll == NULL);
+ assert(key_def->parts->type == FIELD_TYPE_STRING);
+ const char *field = tuple_field_by_part(tuple, key_def->parts);
+ if (is_nullable && field == NULL)
+ return 0;
+ return key_hint_string<is_nullable>(field, key_def);
+}
+
+template<bool is_nullable>
+static uint64_t
+key_hint_string_coll(const char *key, struct key_def *key_def)
+{
+ assert(key_part_is_nullable(key_def->parts) == is_nullable);
+ assert(key_def->parts->type == FIELD_TYPE_STRING &&
+ key_def->parts->coll != NULL);
+ if (is_nullable && mp_typeof(*key) == MP_NIL)
+ return 0;
+ assert(mp_typeof(*key) == MP_STR);
+ uint32_t len;
+ const char *str = mp_decode_str(&key, &len);
+ return key_def->parts->coll->hint(str, len, key_def->parts->coll);
+}
+
+template<bool is_nullable>
+static uint64_t
+tuple_hint_string_coll(const struct tuple *tuple, struct key_def *key_def)
+{
+ assert(key_part_is_nullable(key_def->parts) == is_nullable);
+ assert(key_def->parts->type == FIELD_TYPE_STRING &&
+ key_def->parts->coll != NULL);
+ const char *field = tuple_field_by_part(tuple, key_def->parts);
+ if (is_nullable && field == NULL)
+ return 0;
+ return key_hint_string_coll<is_nullable>(field, key_def);
+}
+
+void
+key_def_set_hint_func(struct key_def *def)
+{
+ def->key_hint = key_hint_default;
+ def->tuple_hint = tuple_hint_default;
+ bool is_nullable = key_part_is_nullable(def->parts);
+ if (def->parts->type == FIELD_TYPE_STRING && def->parts->coll != NULL) {
+ def->key_hint = is_nullable ? key_hint_string_coll<true> :
+ key_hint_string_coll<false>;
+ def->tuple_hint = is_nullable ? tuple_hint_string_coll<true> :
+ tuple_hint_string_coll<false>;
+ return;
+ }
+ switch (def->parts->type) {
+ case FIELD_TYPE_UNSIGNED:
+ def->key_hint = is_nullable ? key_hint_uint<true> :
+ key_hint_uint<false>;
+ def->tuple_hint = is_nullable ? tuple_hint_uint<true> :
+ tuple_hint_uint<false>;
+ break;
+ case FIELD_TYPE_INTEGER:
+ def->key_hint = is_nullable ? key_hint_int<true> :
+ key_hint_int<false>;
+ def->tuple_hint = is_nullable ? tuple_hint_int<true> :
+ tuple_hint_int<false>;
+ break;
+ case FIELD_TYPE_STRING:
+ def->key_hint = is_nullable ? key_hint_string<true> :
+ key_hint_string<false>;
+ def->tuple_hint = is_nullable ? tuple_hint_string<true> :
+ tuple_hint_string<false>;
+ break;
+ case FIELD_TYPE_NUMBER:
+ def->key_hint = is_nullable ? key_hint_number<true> :
+ key_hint_number<false>;
+ def->tuple_hint = is_nullable ? tuple_hint_number<true> :
+ tuple_hint_number<false>;
+ break;
+ case FIELD_TYPE_BOOLEAN:
+ def->key_hint = is_nullable ? key_hint_boolean<true> :
+ key_hint_boolean<false>;
+ def->tuple_hint = is_nullable ? tuple_hint_boolean<true> :
+ tuple_hint_boolean<false>;
+ break;
+ default:
+ break;
+ };
+}
diff --git a/src/box/tuple_hint.h b/src/box/tuple_hint.h
new file mode 100644
index 000000000..19b08dec1
--- /dev/null
+++ b/src/box/tuple_hint.h
@@ -0,0 +1,60 @@
+#ifndef TARANTOOL_BOX_TUPLE_HINT_H_INCLUDED
+#define TARANTOOL_BOX_TUPLE_HINT_H_INCLUDED
+/*
+ * Copyright 2010-2019, Tarantool AUTHORS, please see AUTHORS file.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above
+ * copyright notice, this list of conditions and the
+ * following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above
+ * copyright notice, this list of conditions and the following
+ * disclaimer in the documentation and/or other materials
+ * provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY <COPYRIGHT HOLDER> ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
+ * <COPYRIGHT HOLDER> OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
+ * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
+ * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+#if defined(__cplusplus)
+extern "C" {
+#endif /* defined(__cplusplus) */
+
+#include <stdint.h>
+#include <trivia/util.h>
+
+struct key_def;
+
+/**
+ * If it is impossible to calculate hint, this value is returned.
+ * Such hint must not be used for comparisons.
+ */
+#define INVALID_HINT UINT64_MAX
+
+/**
+ * Initialize tuple_hint() and key_hint() functions for the
+ * key_def.
+ * @param key_def key definition to set up.
+ */
+void
+key_def_set_hint_func(struct key_def *key_def);
+
+#if defined(__cplusplus)
+} /* extern "C" */
+#endif /* defined(__cplusplus) */
+
+#endif /* TARANTOOL_BOX_TUPLE_HINT_H_INCLUDED */
diff --git a/src/lib/coll/coll.c b/src/lib/coll/coll.c
index 6d9c44dbf..fe0ff171f 100644
--- a/src/lib/coll/coll.c
+++ b/src/lib/coll/coll.c
@@ -133,6 +133,37 @@ coll_bin_hash(const char *s, size_t s_len, uint32_t *ph, uint32_t *pcarry,
return s_len;
}
+/** Get a compare hint of a binary collation. */
+static uint64_t
+coll_bin_hint(const char *s, size_t s_len, struct coll *coll)
+{
+ (void)coll;
+ uint64_t result = 0;
+ uint32_t process_len = MIN(s_len, 8);
+ for (uint32_t i = 0; i < process_len; i++) {
+ result <<= 8;
+ result |= ((unsigned char *)s)[i];
+ }
+ result <<= 8 * (8 - process_len);
+ return result;
+}
+
+/** Get a compare hint of a string using ICU collation. */
+static uint64_t
+coll_icu_hint(const char *s, size_t s_len, struct coll *coll)
+{
+ assert(coll->type == COLL_TYPE_ICU);
+ UCharIterator itr;
+ uiter_setUTF8(&itr, s, s_len);
+ uint8_t buf[8];
+ uint32_t state[2] = {0, 0};
+ UErrorCode status = U_ZERO_ERROR;
+ int32_t got = ucol_nextSortKeyPart(coll->collator, &itr, state, buf,
+ sizeof(buf), &status);
+ assert(got >= 0 && got <= 8);
+ return coll_bin_hint((const char *)buf, got, NULL);
+}
+
/**
* Set up ICU collator and init cmp and hash members of collation.
* @param coll Collation to set up.
@@ -242,6 +273,7 @@ coll_icu_init_cmp(struct coll *coll, const struct coll_def *def)
}
coll->cmp = coll_icu_cmp;
coll->hash = coll_icu_hash;
+ coll->hint = coll_icu_hint;
return 0;
}
@@ -332,6 +364,7 @@ coll_new(const struct coll_def *def)
coll->collator = NULL;
coll->cmp = coll_bin_cmp;
coll->hash = coll_bin_hash;
+ coll->hint = coll_bin_hint;
break;
default:
unreachable();
diff --git a/src/lib/coll/coll.h b/src/lib/coll/coll.h
index 9c725712a..53133dae3 100644
--- a/src/lib/coll/coll.h
+++ b/src/lib/coll/coll.h
@@ -47,6 +47,8 @@ typedef int (*coll_cmp_f)(const char *s, size_t s_len, const char *t,
typedef uint32_t (*coll_hash_f)(const char *s, size_t s_len, uint32_t *ph,
uint32_t *pcarry, struct coll *coll);
+typedef uint64_t (*coll_hint_f)(const char *s, size_t s_len, struct coll *coll);
+
struct UCollator;
/**
@@ -61,6 +63,8 @@ struct coll {
/** String comparator. */
coll_cmp_f cmp;
coll_hash_f hash;
+ /** The pointer to routine calculating tuple hint. */
+ coll_hint_f hint;
/** Reference counter. */
int refs;
/**
--
2.21.0
^ permalink raw reply [flat|nested] 5+ messages in thread* Re: [PATCH v4 0/3] box: introduce hint option for memtx tree index
2019-02-28 13:38 [PATCH v4 0/3] box: introduce hint option for memtx tree index Kirill Shcherbatov
` (2 preceding siblings ...)
2019-02-28 13:38 ` [PATCH v4 3/3] memtx: introduce tuple compare hint Kirill Shcherbatov
@ 2019-03-06 9:41 ` Vladimir Davydov
3 siblings, 0 replies; 5+ messages in thread
From: Vladimir Davydov @ 2019-03-06 9:41 UTC (permalink / raw)
To: Kirill Shcherbatov; +Cc: tarantool-patches, kostja
For the record. We've discussed the issue with Kostja and agreed to
try to implement comparison hints / multikey indexes with neither
templates nor macros (both implementations look rather cumbersome).
Something like the code below should do fine, but without 'if' in
memtx_tree_elem_compare (we need to move it to key_def vtab instead).
memtx_tree_index_replace, which differs for multikey and hinted tree
implementations, can be overridden via index vtab.
diff --git a/src/box/memtx_tree.c b/src/box/memtx_tree.c
index 250df7f2..3728728e 100644
--- a/src/box/memtx_tree.c
+++ b/src/box/memtx_tree.c
@@ -40,6 +40,25 @@
#include <small/mempool.h>
/**
+ * Struct that represents a memtrx tree element.
+ */
+struct memtx_tree_elem {
+ struct tuple *tuple;
+ union {
+ /**
+ * Hint to speed up tuple comparisons
+ * (not used for multikey indexes).
+ */
+ uint64_t hint;
+ /**
+ * Offset of the indexed value in
+ * a multikey array.
+ */
+ uint64_t multikey_offset;
+ };
+};
+
+/**
* Struct that is used as a key in BPS tree definition.
*/
struct memtx_tree_key_data {
@@ -47,12 +66,40 @@ struct memtx_tree_key_data {
const char *key;
/** Number of msgpacked search fields. */
uint32_t part_count;
+ /** Hint to speed up comparisons. */
+ uint64_t hint;
};
/**
+ * BPS tree element comparator.
+ * @param elem1 - first element.
+ * @param elem2 - second element.
+ * @param def - key definition.
+ * @retval 0 if elem1 == elem2 in terms of def.
+ * @retval <0 if elem1 < elem2 in terms of def.
+ * @retval >0 if elem1 > elem2 in terms of def.
+ */
+static int
+memtx_tree_compare(const struct memtx_tree_elem elem1,
+ const struct memtx_tree_elem elem2,
+ struct key_def *def)
+{
+ if (!def->has_multikey) {
+ if (elem1.hint != elem2.hint)
+ return elem1.hint - elem2.hint;
+ else
+ return tuple_compare(elem1.tuple, elem2.tuple, def);
+ } else {
+ return tuple_compare_multikey(elem1.tuple, elem1.mutlikey_offset,
+ elem2.tuple, elem2.mutlikey_offset,
+ def);
+ }
+}
+
+/**
* BPS tree element vs key comparator.
* Defined in header in order to allow compiler to inline it.
- * @param tuple - tuple to compare.
+ * @param elem - element to compare.
* @param key_data - key to compare with.
* @param def - key definition.
* @retval 0 if tuple == key in terms of def.
@@ -60,20 +107,29 @@ struct memtx_tree_key_data {
* @retval >0 if tuple > key in terms of def.
*/
static int
-memtx_tree_compare_key(const struct tuple *tuple,
+memtx_tree_compare_key(const struct memtx_tree_elem elem,
const struct memtx_tree_key_data *key_data,
struct key_def *def)
{
- return tuple_compare_with_key(tuple, key_data->key,
- key_data->part_count, def);
+ if (!def->has_multikey) {
+ if (elem.hint != key_data.hint)
+ return elem.hint - key_data.hint;
+ else
+ return tuple_compare_with_key(elem.tuple, key_data->key,
+ key_data->part_count, def);
+ } else {
+ return tuple_compare_with(elem.tuple, elem.multikey_offset,
+ key_data->key, key_data->part_count
+ def);
+ }
}
#define BPS_TREE_NAME memtx_tree
#define BPS_TREE_BLOCK_SIZE (512)
#define BPS_TREE_EXTENT_SIZE MEMTX_EXTENT_SIZE
-#define BPS_TREE_COMPARE(a, b, arg) tuple_compare(a, b, arg)
+#define BPS_TREE_COMPARE(a, b, arg) memtx_tree_compare(a, b, arg)
#define BPS_TREE_COMPARE_KEY(a, b, arg) memtx_tree_compare_key(a, b, arg)
-#define bps_tree_elem_t struct tuple *
+#define bps_tree_elem_t struct memtx_tree_elem
#define bps_tree_key_t struct memtx_tree_key_data *
#define bps_tree_arg_t struct key_def *
^ permalink raw reply [flat|nested] 5+ messages in thread