* [PATCH v2 0/4] box: introduce hint option for memtx tree index
@ 2019-02-13 9:32 Kirill Shcherbatov
2019-02-13 9:32 ` [PATCH v2 1/4] box: move memtx_tree implementation to source file Kirill Shcherbatov
` (3 more replies)
0 siblings, 4 replies; 13+ messages in thread
From: Kirill Shcherbatov @ 2019-02-13 9:32 UTC (permalink / raw)
To: tarantool-patches, kostja, vdavydov.dev; +Cc: Kirill Shcherbatov
Reworked memtx tree to use 'tuple hints'.
Introduced special functions for retrieve 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 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', 'unsigned' or 'integer'
* 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.
Enabled hint option improve performance on average by 15%; Select operations
are significantly accelerated (there are scenarios in which the difference
reaches 200-250%).
Changes in version 2:
-- Splitted patch to parts in other way to decrease diff
-- Hints are not index option anymore, but default where possible
-- Removed hints for numeric types
http://github.com/tarantool/tarantool/tree/kshch/gh-3961-tuple-hints
https://github.com/tarantool/tarantool/issues/3961
Alexandr Lyapunov (1):
box: introduce tuple compare hint for string index
Kirill Shcherbatov (3):
box: move memtx_tree implementation to source file
box: rework memtx_tree to store arbitrary nodes
box: rename memtx_tree.c to memtx_tree_impl.h
src/box/CMakeLists.txt | 2 +-
src/box/key_def.c | 1 +
src/box/key_def.h | 44 ++
src/box/memtx_tree.h | 68 +--
src/box/memtx_tree_decl.c | 207 +++++++++
src/box/{memtx_tree.c => memtx_tree_impl.h} | 490 +++++++++++++++-----
src/box/tuple_compare.cc | 101 ++++
src/box/tuple_compare.h | 7 +
src/coll.c | 45 ++
src/coll.h | 4 +
10 files changed, 787 insertions(+), 182 deletions(-)
create mode 100644 src/box/memtx_tree_decl.c
rename src/box/{memtx_tree.c => memtx_tree_impl.h} (55%)
--
2.20.1
^ permalink raw reply [flat|nested] 13+ messages in thread
* [PATCH v2 1/4] box: move memtx_tree implementation to source file
2019-02-13 9:32 [PATCH v2 0/4] box: introduce hint option for memtx tree index Kirill Shcherbatov
@ 2019-02-13 9:32 ` Kirill Shcherbatov
2019-02-14 13:57 ` [tarantool-patches] " Konstantin Osipov
2019-02-21 13:26 ` Vladimir Davydov
2019-02-13 9:32 ` [PATCH v2 2/4] box: rework memtx_tree to store arbitrary nodes Kirill Shcherbatov
` (2 subsequent siblings)
3 siblings, 2 replies; 13+ messages in thread
From: Kirill Shcherbatov @ 2019-02-13 9:32 UTC (permalink / raw)
To: tarantool-patches, kostja, vdavydov.dev; +Cc: Kirill Shcherbatov
Refactored memtx_tree code so that memtx_tree.h contained only
the signature of the tree object constructor memtx_tree_index_new,
while all implementation details were in memtx_tree.c.
This will further allow to template the implementation details.
Needed for #3961
---
src/box/memtx_tree.c | 62 ++++++++++++++++++++++++++++++++++++++--
src/box/memtx_tree.h | 68 ++------------------------------------------
2 files changed, 63 insertions(+), 67 deletions(-)
diff --git a/src/box/memtx_tree.c b/src/box/memtx_tree.c
index f851fb869..2e8adb682 100644
--- a/src/box/memtx_tree.c
+++ b/src/box/memtx_tree.c
@@ -39,6 +39,64 @@
#include <third_party/qsort_arg.h>
#include <small/mempool.h>
+/**
+ * Struct that is used as a key in BPS tree definition.
+ */
+struct memtx_tree_key_data {
+ /** Sequence of msgpacked search fields. */
+ const char *key;
+ /** Number of msgpacked search fields. */
+ uint32_t 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.
+ */
+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);
+}
+
+#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_arg_t struct key_def *
+
+#include "salad/bps_tree.h"
+
+#undef BPS_TREE_NAME
+#undef BPS_TREE_BLOCK_SIZE
+#undef BPS_TREE_EXTENT_SIZE
+#undef BPS_TREE_COMPARE
+#undef BPS_TREE_COMPARE_KEY
+#undef bps_tree_elem_t
+#undef bps_tree_key_t
+#undef bps_tree_arg_t
+
+struct memtx_tree_index {
+ struct index base;
+ struct memtx_tree tree;
+ struct tuple **build_array;
+ size_t build_array_size, build_array_alloc_size;
+ struct memtx_gc_task gc_task;
+ struct memtx_tree_iterator gc_iterator;
+};
+
/* {{{ Utilities. *************************************************/
static int
@@ -683,7 +741,7 @@ static const struct index_vtab memtx_tree_index_vtab = {
/* .end_build = */ memtx_tree_index_end_build,
};
-struct memtx_tree_index *
+struct index *
memtx_tree_index_new(struct memtx_engine *memtx, struct index_def *def)
{
if (!mempool_is_initialized(&memtx->tree_iterator_pool)) {
@@ -707,5 +765,5 @@ memtx_tree_index_new(struct memtx_engine *memtx, struct index_def *def)
struct key_def *cmp_def = memtx_tree_index_cmp_def(index);
memtx_tree_create(&index->tree, cmp_def, memtx_index_extent_alloc,
memtx_index_extent_free, memtx);
- return index;
+ return &index->base;
}
diff --git a/src/box/memtx_tree.h b/src/box/memtx_tree.h
index bbc8b2419..edeaebab9 100644
--- a/src/box/memtx_tree.h
+++ b/src/box/memtx_tree.h
@@ -30,78 +30,16 @@
* THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*/
-#include <stddef.h>
-#include <stdint.h>
-
-#include "index.h"
-#include "memtx_engine.h"
#if defined(__cplusplus)
extern "C" {
#endif /* defined(__cplusplus) */
+struct index;
+struct index_def;
struct memtx_engine;
-/**
- * Struct that is used as a key in BPS tree definition.
- */
-struct memtx_tree_key_data
-{
- /** Sequence of msgpacked search fields */
- const char *key;
- /** Number of msgpacked search fields */
- uint32_t 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.
- */
-static inline 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);
-}
-
-#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_arg_t struct key_def *
-
-#include "salad/bps_tree.h"
-
-#undef BPS_TREE_NAME
-#undef BPS_TREE_BLOCK_SIZE
-#undef BPS_TREE_EXTENT_SIZE
-#undef BPS_TREE_COMPARE
-#undef BPS_TREE_COMPARE_KEY
-#undef bps_tree_elem_t
-#undef bps_tree_key_t
-#undef bps_tree_arg_t
-
-struct memtx_tree_index {
- struct index base;
- struct memtx_tree tree;
- struct tuple **build_array;
- size_t build_array_size, build_array_alloc_size;
- struct memtx_gc_task gc_task;
- struct memtx_tree_iterator gc_iterator;
-};
-
-struct memtx_tree_index *
+struct index *
memtx_tree_index_new(struct memtx_engine *memtx, struct index_def *def);
#if defined(__cplusplus)
--
2.20.1
^ permalink raw reply [flat|nested] 13+ messages in thread
* [PATCH v2 2/4] box: rework memtx_tree to store arbitrary nodes
2019-02-13 9:32 [PATCH v2 0/4] box: introduce hint option for memtx tree index Kirill Shcherbatov
2019-02-13 9:32 ` [PATCH v2 1/4] box: move memtx_tree implementation to source file Kirill Shcherbatov
@ 2019-02-13 9:32 ` Kirill Shcherbatov
2019-02-21 15:01 ` Vladimir Davydov
2019-02-13 9:32 ` [PATCH v2 3/4] box: rename memtx_tree.c to memtx_tree_impl.h Kirill Shcherbatov
2019-02-13 9:32 ` [PATCH v2 4/4] box: introduce tuple compare hint for string index Kirill Shcherbatov
3 siblings, 1 reply; 13+ messages in thread
From: Kirill Shcherbatov @ 2019-02-13 9:32 UTC (permalink / raw)
To: tarantool-patches, kostja, vdavydov.dev; +Cc: Kirill Shcherbatov
Reworked memtx_tree class to use arbitrary containers as a tree
nodes. This makes possible to implement tuple hints in subsequent
patches.
The memtx_tree.c is currently used in a header manner. This is to
ensure that functional changes in the patch do not mix with
refactoring, that will be finished in the next commit.
Needed for #3961
---
src/box/CMakeLists.txt | 2 +-
src/box/memtx_tree.c | 498 ++++++++++++++++++++++++++------------
src/box/memtx_tree_decl.c | 84 +++++++
3 files changed, 434 insertions(+), 150 deletions(-)
create mode 100644 src/box/memtx_tree_decl.c
diff --git a/src/box/CMakeLists.txt b/src/box/CMakeLists.txt
index 5521e489e..dc8cc2cd5 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_decl.c
memtx_rtree.c
memtx_bitset.c
engine.c
diff --git a/src/box/memtx_tree.c b/src/box/memtx_tree.c
index 2e8adb682..0874b7dc8 100644
--- a/src/box/memtx_tree.c
+++ b/src/box/memtx_tree.c
@@ -1,5 +1,5 @@
/*
- * Copyright 2010-2016, Tarantool AUTHORS, please see AUTHORS file.
+ * 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
@@ -28,72 +28,156 @@
* THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*/
-#include "memtx_tree.h"
-#include "memtx_engine.h"
-#include "space.h"
-#include "schema.h" /* space_cache_find() */
-#include "errinj.h"
-#include "memory.h"
-#include "fiber.h"
-#include "tuple.h"
-#include <third_party/qsort_arg.h>
+
+#if defined(__cplusplus)
+extern "C" {
+#endif /* defined(__cplusplus) */
+
#include <small/mempool.h>
+#include <third_party/qsort_arg.h>
+#include "memtx_engine.h"
+#include "schema.h"
-/**
- * Struct that is used as a key in BPS tree definition.
- */
-struct memtx_tree_key_data {
- /** Sequence of msgpacked search fields. */
- const char *key;
- /** Number of msgpacked search fields. */
- uint32_t part_count;
-};
+#ifndef MEMTX_TREE_NAME
+#error "MEMTX_TREE_NAME must be defined"
+#endif
+
+#ifndef memtx_tree_elem
+#error "memtx_tree_elem must be defined"
+#endif
+
+#ifndef memtx_tree_key
+#error "memtx_tree_key must be defined"
+#endif
+
+#ifndef MEMTX_TREE_ELEM_CMP
+#error "MEMTX_TREE_ELEM_CMP must be defined"
+#endif
+
+#ifndef MEMTX_TREE_ELEM_WITH_KEY_CMP
+#error "MEMTX_TREE_ELEM_WITH_KEY_CMP must be defined"
+#endif
+
+#ifndef MEMTX_TREE_ELEM_SET
+#error "MEMTX_TREE_ELEM_SET must be defined"
+#endif
+
+#ifndef MEMTX_TREE_KEY_SET
+#error "MEMTX_TREE_KEY_SET must be defined"
+#endif
+
+#ifndef MEMTX_TREE_ELEM_GET
+#error "MEMTX_TREE_ELEM_GET must be defined"
+#endif
+
+#ifndef MEMTX_TREE_KEY_GET
+#error "MEMTX_TREE_KEY_GET must be defined"
+#endif
/**
- * 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.
+ * The size of the biggest memtx tree iterator. Used with
+ * mempool_create. This is the size of the block that will be
+ * allocated for each iterator.
*/
-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);
-}
+#define MEMTX_TREE_ITERATOR_SIZE (152)
-#define BPS_TREE_NAME memtx_tree
+#define bps_tree_elem_t memtx_tree_elem
+#define bps_tree_key_t memtx_tree_key *
+#define bps_tree_arg_t struct key_def *
+#define BPS_TREE_NAME CONCAT3(MEMTX_TREE_NAME, _, 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_arg_t struct key_def *
+#define BPS_TREE_COMPARE(a, b, arg) MEMTX_TREE_ELEM_CMP(&a, &b, arg)
+#define BPS_TREE_COMPARE_KEY(a, b, arg) MEMTX_TREE_ELEM_WITH_KEY_CMP(&a, b, arg)
+#define BPS_TREE_NO_DEBUG
#include "salad/bps_tree.h"
+#undef bps_tree_elem_t
+#undef bps_tree_key_t
+#undef bps_tree_arg_t
#undef BPS_TREE_NAME
#undef BPS_TREE_BLOCK_SIZE
#undef BPS_TREE_EXTENT_SIZE
#undef BPS_TREE_COMPARE
#undef BPS_TREE_COMPARE_KEY
-#undef bps_tree_elem_t
-#undef bps_tree_key_t
-#undef bps_tree_arg_t
+#undef BPS_TREE_NO_DEBUG
+
+#define memtx_tree CONCAT3(MEMTX_TREE_NAME, _, tree)
+#define _tree_api_name(postfix) CONCAT5(MEMTX_TREE_NAME, _, tree, _, postfix)
+#define memtx_tree_iterator _tree_api_name(iterator)
+#define memtx_tree_iterator_is_invalid _tree_api_name(iterator_is_invalid)
+#define memtx_tree_iterator_first _tree_api_name(iterator_first)
+#define memtx_tree_iterator_last _tree_api_name(iterator_last)
+#define memtx_tree_iterator_get_elem _tree_api_name(iterator_get_elem)
+#define memtx_tree_iterator_next _tree_api_name(iterator_next)
+#define memtx_tree_iterator_prev _tree_api_name(iterator_prev)
+#define memtx_tree_iterator_freeze _tree_api_name(iterator_freeze)
+#define memtx_tree_iterator_destroy _tree_api_name(iterator_destroy)
+#define memtx_tree_create _tree_api_name(create)
+#define memtx_tree_build _tree_api_name(build)
+#define memtx_tree_destroy _tree_api_name(destroy)
+#define memtx_tree_find _tree_api_name(find)
+#define memtx_tree_insert _tree_api_name(insert)
+#define memtx_tree_delete _tree_api_name(delete)
+#define memtx_tree_size _tree_api_name(size)
+#define memtx_tree_mem_used _tree_api_name(mem_used)
+#define memtx_tree_random _tree_api_name(random)
+#define memtx_tree_invalid_iterator _tree_api_name(invalid_iterator)
+#define memtx_tree_lower_bound _tree_api_name(lower_bound)
+#define memtx_tree_upper_bound _tree_api_name(upper_bound)
+#define memtx_tree_lower_bound_elem _tree_api_name(lower_bound_elem)
+#define memtx_tree_upper_bound_elem _tree_api_name(upper_bound_elem)
+
+#undef _api_name
+#define _api_name(postfix) CONCAT3(MEMTX_TREE_NAME, _, postfix)
+#define memtx_tree_index _api_name(index)
+#define memtx_tree_qcompare _api_name(qcompare)
+#define tree_iterator _api_name(iterator)
+#define tree_iterator_free _api_name(iterator_free)
+#define tree_iterator_cast _api_name(iterator_cast)
+#define tree_iterator_dummie _api_name(iterator_dummie)
+#define tree_iterator_next _api_name(iterator_next)
+#define tree_iterator_prev _api_name(iterator_prev)
+#define tree_iterator_next_equal _api_name(iterator_next_equal)
+#define tree_iterator_prev_equal _api_name(iterator_prev_equal)
+#define tree_iterator_set_next_method _api_name(iterator_set_next_method)
+#define tree_iterator_start _api_name(iterator_start)
+#define memtx_tree_index_cmp_def _api_name(index_cmp_def)
+#define memtx_tree_index_free _api_name(index_free)
+#define memtx_tree_index_gc_run _api_name(index_gc_run)
+#define memtx_tree_index_gc_free _api_name(index_gc_free)
+#define memtx_tree_index_gc_vtab _api_name(index_gc_vtab)
+#define memtx_tree_index_destroy _api_name(index_destroy)
+#define memtx_tree_index_update_def _api_name(index_update_def)
+#define memtx_tree_index_depends_on_pk _api_name(index_depends_on_pk)
+#define memtx_tree_index_size _api_name(index_size)
+#define memtx_tree_index_bsize _api_name(index_bsize)
+#define memtx_tree_index_random _api_name(index_random)
+#define memtx_tree_index_count _api_name(index_count)
+#define memtx_tree_index_get _api_name(index_get)
+#define memtx_tree_index_insert_tuple _api_name(index_insert_tuple)
+#define memtx_tree_index_delete_tuple _api_name(index_delete_tuple)
+#define memtx_tree_index_replace _api_name(index_replace)
+#define memtx_tree_index_create_iterator _api_name(index_create_iterator)
+#define memtx_tree_index_begin_build _api_name(index_begin_build)
+#define memtx_tree_index_build_next _api_name(index_build_next)
+#define memtx_tree_index_reserve _api_name(index_reserve)
+#define memtx_tree_index_end_build _api_name(index_end_build)
+#define tree_snapshot_iterator _api_name(snapshot_iterator)
+#define tree_snapshot_iterator_free _api_name(snapshot_iterator_free)
+#define tree_snapshot_iterator_next _api_name(snapshot_iterator_next)
+#define memtx_tree_index_create_snapshot_iterator\
+ _api_name(index_create_snapshot_iterator)
+#define memtx_tree_index_vtab _api_name(index_vtab)
+#define memtx_tree_index_new _api_name(index_new)
struct memtx_tree_index {
struct index base;
- struct memtx_tree tree;
- struct tuple **build_array;
+ memtx_tree_elem *build_array;
size_t build_array_size, build_array_alloc_size;
struct memtx_gc_task gc_task;
+ struct memtx_tree tree;
struct memtx_tree_iterator gc_iterator;
};
@@ -102,8 +186,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);
+ return MEMTX_TREE_ELEM_CMP((memtx_tree_elem *)a,
+ (memtx_tree_elem *)b, c);
}
/* {{{ MemtxTree Iterators ****************************************/
@@ -113,17 +197,21 @@ 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;
+ memtx_tree_key key_data;
+ memtx_tree_elem current;
/** Memory pool the iterator was allocated from. */
struct mempool *pool;
};
+static_assert(sizeof(struct tree_iterator) <= MEMTX_TREE_ITERATOR_SIZE,
+ "tree_iterator must be less or equal than "
+ "MEMTX_TREE_ITERATOR_SIZE");
+
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;
@@ -132,9 +220,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 = MEMTX_TREE_ELEM_GET(&it->current);
+ if (tuple != NULL)
+ tuple_unref(tuple);
mempool_free(it->pool, it);
}
@@ -149,25 +238,28 @@ 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(MEMTX_TREE_ELEM_GET(&it->current) != NULL);
+ memtx_tree_elem *check =
+ memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
+ if (check == NULL ||
+ MEMTX_TREE_ELEM_GET(check) != MEMTX_TREE_ELEM_GET(&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(MEMTX_TREE_ELEM_GET(&it->current));
+ memtx_tree_elem *res =
+ memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
if (res == NULL) {
iterator->next = tree_iterator_dummie;
+ memset(&it->current, 0, sizeof(it->current));
*ret = NULL;
} else {
- *ret = it->current_tuple = *res;
- tuple_ref(it->current_tuple);
+ *ret = MEMTX_TREE_ELEM_GET(res);
+ tuple_ref(*ret);
+ it->current = *res;
}
return 0;
}
@@ -175,23 +267,27 @@ 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(MEMTX_TREE_ELEM_GET(&it->current) != NULL);
+ memtx_tree_elem *check =
+ memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
+ if (check == NULL ||
+ MEMTX_TREE_ELEM_GET(check) != MEMTX_TREE_ELEM_GET(&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(MEMTX_TREE_ELEM_GET(&it->current));
+ memtx_tree_elem *res =
+ memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
if (!res) {
iterator->next = tree_iterator_dummie;
+ memset(&it->current, 0, sizeof(it->current));
*ret = NULL;
} else {
- *ret = it->current_tuple = *res;
- tuple_ref(it->current_tuple);
+ *ret = MEMTX_TREE_ELEM_GET(res);
+ tuple_ref(*ret);
+ it->current = *res;
}
return 0;
}
@@ -199,28 +295,31 @@ 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(MEMTX_TREE_ELEM_GET(&it->current) != NULL);
+ memtx_tree_elem *check =
+ memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
+ if (check == NULL ||
+ MEMTX_TREE_ELEM_GET(check) != MEMTX_TREE_ELEM_GET(&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(MEMTX_TREE_ELEM_GET(&it->current));
+ memtx_tree_elem *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 ||
+ MEMTX_TREE_ELEM_WITH_KEY_CMP(res, &it->key_data,
+ it->index_def->key_def) != 0) {
iterator->next = tree_iterator_dummie;
+ memset(&it->current, 0, sizeof(it->current));
*ret = NULL;
} else {
- *ret = it->current_tuple = *res;
- tuple_ref(it->current_tuple);
+ *ret = MEMTX_TREE_ELEM_GET(res);
+ tuple_ref(*ret);
+ it->current = *res;
}
return 0;
}
@@ -228,27 +327,30 @@ 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(MEMTX_TREE_ELEM_GET(&it->current) != NULL);
+ memtx_tree_elem *check =
+ memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
+ if (check == NULL ||
+ MEMTX_TREE_ELEM_GET(check) != MEMTX_TREE_ELEM_GET(&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(MEMTX_TREE_ELEM_GET(&it->current));
+ memtx_tree_elem *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 ||
+ MEMTX_TREE_ELEM_WITH_KEY_CMP(res, &it->key_data,
+ it->index_def->key_def) != 0) {
iterator->next = tree_iterator_dummie;
+ memset(&it->current, 0, sizeof(it->current));
*ret = NULL;
} else {
- *ret = it->current_tuple = *res;
- tuple_ref(it->current_tuple);
+ *ret = MEMTX_TREE_ELEM_GET(res);
+ tuple_ref(*ret);
+ it->current = *res;
}
return 0;
}
@@ -256,7 +358,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(MEMTX_TREE_ELEM_GET(&it->current) != NULL);
switch (it->type) {
case ITER_EQ:
it->base.next = tree_iterator_next_equal;
@@ -285,13 +387,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(MEMTX_TREE_ELEM_GET(&it->current) == NULL);
+ uint32_t part_count;
+ const char *key = MEMTX_TREE_KEY_GET(&it->key_data, &part_count);
+ if (key == NULL) {
if (iterator_type_is_reverse(it->type))
it->tree_iterator = memtx_tree_iterator_last(tree);
else
@@ -327,12 +431,13 @@ tree_iterator_start(struct iterator *iterator, struct tuple **ret)
}
}
- struct tuple **res = memtx_tree_iterator_get_elem(it->tree,
- &it->tree_iterator);
+ memtx_tree_elem *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 = MEMTX_TREE_ELEM_GET(res);
+ tuple_ref(*ret);
+ it->current = *res;
tree_iterator_set_next_method(it);
return 0;
}
@@ -386,7 +491,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);
+ memtx_tree_elem *res = memtx_tree_iterator_get_elem(tree, itr);
+ struct tuple *tuple = MEMTX_TREE_ELEM_GET(res);;
memtx_tree_iterator_next(tree, itr);
tuple_unref(tuple);
if (++loops >= YIELD_LOOPS) {
@@ -466,8 +572,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;
+ memtx_tree_elem *res = memtx_tree_random(&index->tree, rnd);
+ *result = res != NULL ? MEMTX_TREE_ELEM_GET(res) : NULL;
return 0;
}
@@ -487,26 +593,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;
+ memtx_tree_key key_data;
+ struct key_def *cmp_def = memtx_tree_index_cmp_def(index);
+ MEMTX_TREE_KEY_SET(&key_data, key, part_count, cmp_def);
+ memtx_tree_elem *res = memtx_tree_find(&index->tree, &key_data);
+ *result = res != NULL ? MEMTX_TREE_ELEM_GET(res) : 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;
+ memtx_tree_elem data;
+ MEMTX_TREE_ELEM_SET(&data, tuple, index->tree.arg);
+ memtx_tree_elem data_replaced;
+ memset(&data_replaced, 0, sizeof(data_replaced));
+ int rc = memtx_tree_insert(&index->tree, data, &data_replaced);
+ if (replaced != NULL)
+ *replaced = MEMTX_TREE_ELEM_GET(&data_replaced);
+ 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;
+ memtx_tree_elem data;
+ MEMTX_TREE_ELEM_SET(&data, 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");
@@ -516,9 +646,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,
@@ -530,9 +660,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;
}
@@ -571,12 +700,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);
+ MEMTX_TREE_KEY_SET(&it->key_data, 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;
+ memset(&it->current, 0, sizeof(it->current));
return (struct iterator *)it;
}
@@ -594,8 +723,8 @@ 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));
+ memtx_tree_elem *tmp =
+ realloc(index->build_array, size_hint * sizeof(*tmp));
if (tmp == NULL) {
diag_set(OutOfMemory, size_hint * sizeof(*tmp),
"memtx_tree_index", "reserve");
@@ -611,20 +740,20 @@ 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 = (memtx_tree_elem *)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 **)
+ memtx_tree_elem *tmp =
realloc(index->build_array,
index->build_array_alloc_size * sizeof(*tmp));
if (tmp == NULL) {
@@ -634,7 +763,8 @@ memtx_tree_index_build_next(struct index *base, struct tuple *tuple)
}
index->build_array = tmp;
}
- index->build_array[index->build_array_size++] = tuple;
+ MEMTX_TREE_ELEM_SET(&index->build_array[index->build_array_size++],
+ tuple, memtx_tree_index_cmp_def(index));
return 0;
}
@@ -644,10 +774,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;
@@ -678,12 +807,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);
+ memtx_tree_elem *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(MEMTX_TREE_ELEM_GET(res), size);
}
/**
@@ -746,7 +875,7 @@ memtx_tree_index_new(struct memtx_engine *memtx, struct index_def *def)
{
if (!mempool_is_initialized(&memtx->tree_iterator_pool)) {
mempool_create(&memtx->tree_iterator_pool, cord_slab_cache(),
- sizeof(struct tree_iterator));
+ MEMTX_TREE_ITERATOR_SIZE);
}
struct memtx_tree_index *index =
@@ -767,3 +896,74 @@ memtx_tree_index_new(struct memtx_engine *memtx, struct index_def *def)
memtx_index_extent_free, memtx);
return &index->base;
}
+
+#undef _tree_api_name
+#undef memtx_tree
+#undef memtx_tree_iterator
+#undef memtx_tree_iterator_is_invalid
+#undef memtx_tree_iterator_first
+#undef memtx_tree_iterator_last
+#undef memtx_tree_iterator_get_elem
+#undef memtx_tree_iterator_next
+#undef memtx_tree_iterator_prev
+#undef memtx_tree_iterator_freeze
+#undef memtx_tree_iterator_destroy
+#undef memtx_tree_create
+#undef memtx_tree_build
+#undef memtx_tree_destroy
+#undef memtx_tree_find
+#undef memtx_tree_insert
+#undef memtx_tree_delete
+#undef memtx_tree_size
+#undef memtx_tree_mem_used
+#undef memtx_tree_random
+#undef memtx_tree_invalid_iterator
+#undef memtx_tree_lower_bound
+#undef memtx_tree_upper_bound
+#undef memtx_tree_lower_bound_elem
+#undef memtx_tree_upper_bound_elem
+
+#undef _api_name
+#undef memtx_tree_index
+#undef memtx_tree_qcompare
+#undef tree_iterator
+#undef tree_iterator_free
+#undef tree_iterator_cast
+#undef tree_iterator_dummie
+#undef tree_iterator_next
+#undef tree_iterator_prev
+#undef tree_iterator_next_equal
+#undef tree_iterator_prev_equal
+#undef tree_iterator_set_next_method
+#undef tree_iterator_start
+#undef memtx_tree_index_cmp_def
+#undef memtx_tree_index_free
+#undef memtx_tree_index_gc_run
+#undef memtx_tree_index_gc_free
+#undef memtx_tree_index_gc_vtab
+#undef memtx_tree_index_destroy
+#undef memtx_tree_index_update_def
+#undef memtx_tree_index_depends_on_pk
+#undef memtx_tree_index_size
+#undef memtx_tree_index_bsize
+#undef memtx_tree_index_random
+#undef memtx_tree_index_count
+#undef memtx_tree_index_get
+#undef memtx_tree_index_insert_tuple
+#undef memtx_tree_index_delete_tuple
+#undef memtx_tree_index_replace
+#undef memtx_tree_index_create_iterator
+#undef memtx_tree_index_begin_build
+#undef memtx_tree_index_build_next
+#undef memtx_tree_index_reserve
+#undef memtx_tree_index_end_build
+#undef tree_snapshot_iterator
+#undef tree_snapshot_iterator_free
+#undef tree_snapshot_iterator_next
+#undef tree_index_create_snapshot_iterator
+#undef memtx_tree_index_vtab
+#undef memtx_tree_index_new
+
+#if defined(__cplusplus)
+} /* extern "C" */
+#endif /* defined(__cplusplus) */
diff --git a/src/box/memtx_tree_decl.c b/src/box/memtx_tree_decl.c
new file mode 100644
index 000000000..03e0e0ed7
--- /dev/null
+++ b/src/box/memtx_tree_decl.c
@@ -0,0 +1,84 @@
+/*
+ * 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 <stdbool.h>
+#include <stdint.h>
+#include "tuple_compare.h"
+#include "memtx_tree.h"
+
+/* {{{ Memtx tree of tuples class. ******************************/
+
+/** Struct that is used as a key in BPS tree definition. */
+struct memtx_tuple_tree_key_data {
+ /** Sequence of msgpacked search fields. */
+ const char *key;
+ /** Number of msgpacked search fields. */
+ uint32_t part_count;
+};
+
+#define MEMTX_TREE_NAME memtx_tuple_tree
+#define memtx_tree_elem struct tuple *
+#define memtx_tree_key struct memtx_tuple_tree_key_data
+#define MEMTX_TREE_ELEM_CMP(elem_a_ptr, elem_b_ptr, key_def) \
+ tuple_compare(*elem_a_ptr, *elem_b_ptr, key_def)
+#define MEMTX_TREE_ELEM_WITH_KEY_CMP(elem_ptr, key_ptr, key_def) \
+ tuple_compare_with_key(*elem_ptr, (key_ptr)->key, \
+ (key_ptr)->part_count, key_def)
+#define MEMTX_TREE_ELEM_SET(elem_ptr, tuple, key_def) \
+ ({(void)key_def; *elem_ptr = tuple;})
+#define MEMTX_TREE_KEY_SET(key_ptr, key_val, part_count_val, key_def) \
+ ({(void)key_def; (key_ptr)->key = key_val; \
+ (key_ptr)->part_count = part_count_val;})
+#define MEMTX_TREE_ELEM_GET(elem_ptr) (*(elem_ptr))
+#define MEMTX_TREE_KEY_GET(key_ptr, part_count_ptr) \
+ ({*part_count_ptr = (key_ptr)->part_count; (key_ptr)->key;})
+
+#include "memtx_tree.c"
+
+#undef memtx_tree_key
+#undef memtx_tree_elem
+#undef MEMTX_TREE_KEY_GET
+#undef MEMTX_TREE_ELEM_GET
+#undef MEMTX_TREE_KEY_SET
+#undef MEMTX_TREE_ELEM_SET
+#undef MEMTX_TREE_ELEM_WITH_KEY_CMP
+#undef MEMTX_TREE_ELEM_CMP
+#undef MEMTX_TREE_ELEM_EQUAL
+#undef memtx_tree_key
+#undef memtx_tree_elem
+#undef MEMTX_TREE_NAME
+
+/* }}} */
+
+struct index *
+memtx_tree_index_new(struct memtx_engine *memtx, struct index_def *def)
+{
+ return memtx_tuple_tree_index_new(memtx, def);
+}
--
2.20.1
^ permalink raw reply [flat|nested] 13+ messages in thread
* [PATCH v2 3/4] box: rename memtx_tree.c to memtx_tree_impl.h
2019-02-13 9:32 [PATCH v2 0/4] box: introduce hint option for memtx tree index Kirill Shcherbatov
2019-02-13 9:32 ` [PATCH v2 1/4] box: move memtx_tree implementation to source file Kirill Shcherbatov
2019-02-13 9:32 ` [PATCH v2 2/4] box: rework memtx_tree to store arbitrary nodes Kirill Shcherbatov
@ 2019-02-13 9:32 ` Kirill Shcherbatov
2019-02-13 9:32 ` [PATCH v2 4/4] box: introduce tuple compare hint for string index Kirill Shcherbatov
3 siblings, 0 replies; 13+ messages in thread
From: Kirill Shcherbatov @ 2019-02-13 9:32 UTC (permalink / raw)
To: tarantool-patches, kostja, vdavydov.dev; +Cc: Kirill Shcherbatov
File meta_tree.c that implements the template class memtx_tree,
renamed to memes_tree_impl.h due to the fact that the inclusion
of code in header files is more common.
Needed for #3961
---
src/box/memtx_tree_decl.c | 2 +-
src/box/{memtx_tree.c => memtx_tree_impl.h} | 0
2 files changed, 1 insertion(+), 1 deletion(-)
rename src/box/{memtx_tree.c => memtx_tree_impl.h} (100%)
diff --git a/src/box/memtx_tree_decl.c b/src/box/memtx_tree_decl.c
index 03e0e0ed7..084a0594f 100644
--- a/src/box/memtx_tree_decl.c
+++ b/src/box/memtx_tree_decl.c
@@ -60,7 +60,7 @@ struct memtx_tuple_tree_key_data {
#define MEMTX_TREE_KEY_GET(key_ptr, part_count_ptr) \
({*part_count_ptr = (key_ptr)->part_count; (key_ptr)->key;})
-#include "memtx_tree.c"
+#include "memtx_tree_impl.h"
#undef memtx_tree_key
#undef memtx_tree_elem
diff --git a/src/box/memtx_tree.c b/src/box/memtx_tree_impl.h
similarity index 100%
rename from src/box/memtx_tree.c
rename to src/box/memtx_tree_impl.h
--
2.20.1
^ permalink raw reply [flat|nested] 13+ messages in thread
* [PATCH v2 4/4] box: introduce tuple compare hint for string index
2019-02-13 9:32 [PATCH v2 0/4] box: introduce hint option for memtx tree index Kirill Shcherbatov
` (2 preceding siblings ...)
2019-02-13 9:32 ` [PATCH v2 3/4] box: rename memtx_tree.c to memtx_tree_impl.h Kirill Shcherbatov
@ 2019-02-13 9:32 ` Kirill Shcherbatov
2019-02-14 14:09 ` [tarantool-patches] " Konstantin Osipov
2019-02-15 18:34 ` Kirill Shcherbatov
3 siblings, 2 replies; 13+ messages in thread
From: Kirill Shcherbatov @ 2019-02-13 9:32 UTC (permalink / raw)
To: tarantool-patches, kostja, vdavydov.dev; +Cc: 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.
Part of #3961
---
src/box/key_def.c | 1 +
src/box/key_def.h | 44 ++++++++++++++
src/box/memtx_tree_decl.c | 123 ++++++++++++++++++++++++++++++++++++++
src/box/tuple_compare.cc | 101 +++++++++++++++++++++++++++++++
src/box/tuple_compare.h | 7 +++
src/coll.c | 45 ++++++++++++++
src/coll.h | 4 ++
7 files changed, 325 insertions(+)
diff --git a/src/box/key_def.c b/src/box/key_def.c
index 9411ade39..ceca1ebee 100644
--- a/src/box/key_def.c
+++ b/src/box/key_def.c
@@ -135,6 +135,7 @@ key_def_set_cmp(struct key_def *def)
def->tuple_compare_with_key = tuple_compare_with_key_create(def);
tuple_hash_func_set(def);
tuple_extract_key_set(def);
+ tuple_hint_set(def);
}
static void
diff --git a/src/box/key_def.h b/src/box/key_def.h
index bf3e63b6d..a2a0bbecb 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
@@ -551,6 +562,39 @@ tuple_compare_with_key(const struct tuple *tuple, const char *key,
return key_def->tuple_compare_with_key(tuple, key, part_count, 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_decl.c b/src/box/memtx_tree_decl.c
index 084a0594f..264241832 100644
--- a/src/box/memtx_tree_decl.c
+++ b/src/box/memtx_tree_decl.c
@@ -77,8 +77,131 @@ struct memtx_tuple_tree_key_data {
/* }}} */
+/* {{{ Memtx hinted and hint_only tree class. *******************/
+
+/**
+ * Struct that is used as a key in BPS tree definition in
+ * memtx_hint_only_tree and memtx_hinted_tree.
+*/
+struct memtx_hinted_tree_key_data {
+ /** Sequence of msgpacked search fields. */
+ const char *key;
+ /** Number of msgpacked search fields. */
+ uint32_t part_count;
+ /**
+ * Compare hint. Is calculated automatically on 'set'
+ * operation with memtx_hinted_tree_key_data_set().
+ */
+ uint64_t hint;
+};
+
+/**
+ * Struct that is used as a key in BPS tree definition in
+ * memtx_hint_only_tree and memtx_hinted_tree.
+ */
+struct memtx_hinted_tree_data {
+ /** Tuple this node is representing. */
+ struct tuple *tuple;
+ /**
+ * Compare hint. Is calculated automatically on 'set'
+ * operation with memtx_hinted_tree_data_set().
+ */
+ uint64_t hint;
+};
+
+/**
+ * Compare memtx_hinted_tree records.
+ */
+static int
+memtx_hinted_tree_data_cmp(struct memtx_hinted_tree_data *a,
+ struct memtx_hinted_tree_data *b,
+ struct key_def *key_def)
+{
+ if (a->hint != b->hint)
+ return a->hint < b->hint ? -1 : 1;
+ return tuple_compare(a->tuple, b->tuple, key_def);
+}
+
+/**
+ * Compare memtx_hinted_tree record with key.
+ */
+static int
+memtx_hinted_tree_data_cmp_with_key(struct memtx_hinted_tree_data *a,
+ struct memtx_hinted_tree_key_data *key,
+ struct key_def *key_def)
+{
+ if (a->hint != key->hint)
+ return a->hint < key->hint ? -1 : 1;
+ return tuple_compare_with_key(a->tuple, key->key, key->part_count,
+ key_def);
+}
+
+/**
+ * Initialize memtx_hinted_tree or memtx_hint_only_tree record
+ * with tuple and recalculate internal hint field.
+ */
+static void
+memtx_hinted_tree_data_set(struct memtx_hinted_tree_data *data,
+ struct tuple *tuple, struct key_def *key_def)
+{
+ data->tuple = tuple;
+ data->hint = tuple != NULL ? tuple_hint(tuple, key_def) : 0;
+}
+
+/**
+ * Initialize memtx_hinted_tree or memtx_hint_only_tree key with
+ * key raw and part count and recalculate internal hint field.
+ */
+static void
+memtx_hinted_tree_key_data_set(struct memtx_hinted_tree_key_data *key_data,
+ const char *key, uint32_t part_count,
+ struct key_def *key_def)
+{
+ key_data->key = key;
+ key_data->part_count = part_count;
+ key_data->hint = key != NULL && part_count > 0 ?
+ key_hint(key, key_def) : 0;
+}
+
+#define MEMTX_TREE_NAME memtx_hinted_tree
+#define memtx_tree_elem struct memtx_hinted_tree_data
+#define memtx_tree_key struct memtx_hinted_tree_key_data
+#define MEMTX_TREE_ELEM_EQUAL(elem_a_ptr, elem_b_ptr) \
+ ((elem_a_ptr)->tuple == (elem_b_ptr)->tuple)
+#define MEMTX_TREE_ELEM_CMP(elem_a_ptr, elem_b_ptr, key_def) \
+ memtx_hinted_tree_data_cmp(elem_a_ptr, elem_b_ptr, key_def)
+#define MEMTX_TREE_ELEM_WITH_KEY_CMP(elem_ptr, key_ptr, key_def) \
+ memtx_hinted_tree_data_cmp_with_key(elem_ptr, key_ptr, key_def)
+#define MEMTX_TREE_ELEM_SET(elem_ptr, tuple, key_def) \
+ memtx_hinted_tree_data_set(elem_ptr, tuple, key_def)
+#define MEMTX_TREE_KEY_SET(key_ptr, key_val, part_count_val, key_def) \
+ memtx_hinted_tree_key_data_set(key_ptr, key_val, part_count_val, \
+ key_def)
+#define MEMTX_TREE_ELEM_GET(elem_ptr) ((elem_ptr)->tuple)
+#define MEMTX_TREE_KEY_GET(key_ptr, part_count_ptr) \
+ ({*part_count_ptr = (key_ptr)->part_count; (key_ptr)->key;})
+
+#include "memtx_tree_impl.h"
+
+#undef memtx_tree_key
+#undef memtx_tree_elem
+#undef MEMTX_TREE_KEY_GET
+#undef MEMTX_TREE_ELEM_GET
+#undef MEMTX_TREE_KEY_SET
+#undef MEMTX_TREE_ELEM_SET
+#undef MEMTX_TREE_ELEM_WITH_KEY_CMP
+#undef MEMTX_TREE_ELEM_CMP
+#undef MEMTX_TREE_ELEM_EQUAL
+#undef memtx_tree_key
+#undef memtx_tree_elem
+#undef MEMTX_TREE_NAME
+
+/* }}} */
+
struct index *
memtx_tree_index_new(struct memtx_engine *memtx, struct index_def *def)
{
+ if (def->cmp_def->parts->type == FIELD_TYPE_STRING)
+ return memtx_hinted_tree_index_new(memtx, def);
return memtx_tuple_tree_index_new(memtx, def);
}
diff --git a/src/box/tuple_compare.cc b/src/box/tuple_compare.cc
index ded802c7d..744901d70 100644
--- a/src/box/tuple_compare.cc
+++ b/src/box/tuple_compare.cc
@@ -1321,4 +1321,105 @@ tuple_compare_with_key_create(const struct key_def *def)
compare_with_key_slowpath_funcs[cmp_func_idx];
}
+static uint64_t
+key_hint_default(const char *key, struct key_def *key_def)
+{
+ (void)key;
+ (void)key_def;
+ return 0;
+}
+
+static uint64_t
+tuple_hint_default(const struct tuple *tuple, struct key_def *key_def)
+{
+ (void)tuple;
+ (void)key_def;
+ return 0;
+}
+
+static uint64_t
+key_hint_string(const char *key, struct key_def *key_def)
+{
+ assert(key != NULL);
+ (void)key_def;
+ assert(key_def->parts->type == FIELD_TYPE_STRING);
+ 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;
+ /*
+ * Map the sequence of characters in the hint's bytes in
+ * the reverse order: the first character will be mapped
+ * in the highest byte of the number, etc.
+ * One additional bit encodes the presence of the next
+ * sign.
+ * 0bCHARBYTEU CHARBYTEU CHARBYTEU ... CHARBYTE0
+ * The sequence constructed in this way provides a
+ * comparison transitivity of strings no longer than 7
+ * bytes.
+ */
+ uint32_t process_len = MIN(len, sizeof(char) - 1);
+ for (uint32_t i = 0; i < process_len; i++) {
+ result <<= CHAR_BIT + 1;
+ result |= UCHAR_MAX + 1;
+ result |= str[i];
+ }
+ /*
+ * If the length of the string is less than the 64-bit
+ * hint can accommodate, the insignificant positions are
+ * filled with 0.
+ */
+ result <<= (CHAR_BIT + 1) * (sizeof(char) - 1 - process_len);
+ return result;
+}
+
+static uint64_t
+tuple_hint_string(const struct tuple *tuple, struct key_def *key_def)
+{
+ const char *field = tuple_field_by_part(tuple, key_def->parts);
+ return field != NULL ? key_hint_string(field, key_def) : 0;
+}
+
+static uint64_t
+key_hint_string_coll(const char *key, struct key_def *key_def)
+{
+ assert(key != NULL);
+ assert(key_def->parts->type == FIELD_TYPE_STRING);
+ assert(mp_typeof(*key) == MP_STR);
+ assert(key_def->parts->coll != NULL);
+ uint32_t len;
+ const char *str = mp_decode_str(&key, &len);
+ return key_def->parts->coll->hint(str, len, key_def->parts->coll);
+}
+
+static uint64_t
+tuple_hint_string_coll(const struct tuple *tuple, struct key_def *key_def)
+{
+ const char *field = tuple_field_by_part(tuple, key_def->parts);
+ return field != NULL ? key_hint_string_coll(field, key_def) : 0;
+}
+
+void
+tuple_hint_set(struct key_def *def)
+{
+ def->key_hint = key_hint_default;
+ def->tuple_hint = tuple_hint_default;
+ if (key_part_is_nullable(def->parts))
+ return;
+ if (def->parts->type == FIELD_TYPE_STRING && def->parts->coll != NULL) {
+ def->key_hint = key_hint_string_coll;
+ def->tuple_hint = tuple_hint_string_coll;
+ return;
+ }
+ switch (def->parts->type) {
+ case FIELD_TYPE_STRING:
+ def->key_hint = key_hint_string;
+ def->tuple_hint = tuple_hint_string;
+ break;
+ default:
+ break;
+ };
+}
+
/* }}} tuple_compare_with_key */
diff --git a/src/box/tuple_compare.h b/src/box/tuple_compare.h
index e3a63204f..405460086 100644
--- a/src/box/tuple_compare.h
+++ b/src/box/tuple_compare.h
@@ -67,6 +67,13 @@ tuple_compare_create(const struct key_def *key_def);
tuple_compare_with_key_t
tuple_compare_with_key_create(const struct key_def *key_def);
+/**
+ * Initialize tuple_hint() and key_hint() functions for the key_def.
+ * @param key_def key definition to set up.
+ */
+void
+tuple_hint_set(struct key_def *key_def);
+
#if defined(__cplusplus)
} /* extern "C" */
#endif /* defined(__cplusplus) */
diff --git a/src/coll.c b/src/coll.c
index 6d9c44dbf..5bb46a94f 100644
--- a/src/coll.c
+++ b/src/coll.c
@@ -33,6 +33,7 @@
#include "third_party/PMurHash.h"
#include "diag.h"
#include "assoc.h"
+#include "limits.h"
#include <unicode/ucol.h>
#include <trivia/config.h>
@@ -133,6 +134,48 @@ 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 string using ICU collation. */
+static uint64_t
+coll_icu_hint(const char *s, size_t s_len, struct coll *coll)
+{
+ UCharIterator itr;
+ uiter_setUTF8(&itr, s, s_len);
+ uint8_t buf[7];
+ 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 <= 7);
+ uint64_t result = 0;
+ for (int32_t i = 0; i < got; i++) {
+ result <<= 9;
+ result |= 0x100;
+ result |= buf[i];
+ }
+ result <<= 9 * (7 - got);
+ return result;
+}
+
+/**
+ * Get a compare hint of a string using BINARY collation.
+ * Works similar to key_hint_string, read it's comment for more
+ * details.
+ */
+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, sizeof(char) - 1);
+ for (uint32_t i = 0; i < process_len; i++) {
+ result <<= CHAR_BIT;
+ result |= UCHAR_MAX + 1;
+ result |= s[i];
+ }
+ result <<= (CHAR_BIT + 1) * (sizeof(char) - 1 - process_len);
+ return result;
+}
+
/**
* Set up ICU collator and init cmp and hash members of collation.
* @param coll Collation to set up.
@@ -242,6 +285,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 +376,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/coll.h b/src/coll.h
index 9c725712a..53133dae3 100644
--- a/src/coll.h
+++ b/src/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.20.1
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [tarantool-patches] [PATCH v2 1/4] box: move memtx_tree implementation to source file
2019-02-13 9:32 ` [PATCH v2 1/4] box: move memtx_tree implementation to source file Kirill Shcherbatov
@ 2019-02-14 13:57 ` Konstantin Osipov
2019-02-21 13:26 ` Vladimir Davydov
1 sibling, 0 replies; 13+ messages in thread
From: Konstantin Osipov @ 2019-02-14 13:57 UTC (permalink / raw)
To: tarantool-patches; +Cc: vdavydov.dev, Kirill Shcherbatov
* Kirill Shcherbatov <kshcherbatov@tarantool.org> [19/02/13 13:03]:
> Refactored memtx_tree code so that memtx_tree.h contained only
> the signature of the tree object constructor memtx_tree_index_new,
> while all implementation details were in memtx_tree.c.
> This will further allow to template the implementation details.
>
> Needed for #3961
This patch is OK to push.
I am not sure if any of the following patches will be in, but
hiding more details in the implementation is always a good thing.
--
Konstantin Osipov, Moscow, Russia, +7 903 626 22 32
http://tarantool.io - www.twitter.com/kostja_osipov
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [tarantool-patches] [PATCH v2 4/4] box: introduce tuple compare hint for string index
2019-02-13 9:32 ` [PATCH v2 4/4] box: introduce tuple compare hint for string index Kirill Shcherbatov
@ 2019-02-14 14:09 ` Konstantin Osipov
2019-02-15 18:34 ` Kirill Shcherbatov
1 sibling, 0 replies; 13+ messages in thread
From: Konstantin Osipov @ 2019-02-14 14:09 UTC (permalink / raw)
To: tarantool-patches; +Cc: vdavydov.dev, Alexandr Lyapunov
* Kirill Shcherbatov <kshcherbatov@tarantool.org> [19/02/13 13:03]:
> From: Alexandr Lyapunov <aleks@tarantool.org>
> diff --git a/src/box/key_def.c b/src/box/key_def.c
> index 9411ade39..ceca1ebee 100644
> --- a/src/box/key_def.c
> +++ b/src/box/key_def.c
> @@ -135,6 +135,7 @@ key_def_set_cmp(struct key_def *def)
> def->tuple_compare_with_key = tuple_compare_with_key_create(def);
> tuple_hash_func_set(def);
> tuple_extract_key_set(def);
> + tuple_hint_set(def);
I think the name of the function is confusing. The name suggests
that it says a tuple hint, whereas it sets a function which
evaluates the hint. Please prepare a separate patch which renames
existing functions tuple_hash_func_set and tuple_extract_key_set
to
key_def_set_{tuple_extract_key_func|tuple_hash_func|tuple_hint_func}.
> +/** @copydoc tuple_hint() */
> +typedef uint64_t (*tuple_hint_t)(const struct tuple *tuple,
> + struct key_def *key_def);
The func typedef should end with _f not with _t.
> +
> +/** @copydoc key_hint() */
> +typedef uint64_t (*key_hint_t)(const char *key, struct key_def *key_def);
Same here.
> +static int
> +memtx_hinted_tree_data_cmp(struct memtx_hinted_tree_data *a,
> + struct memtx_hinted_tree_data *b,
> + struct key_def *key_def)
> +{
> + if (a->hint != b->hint)
> + return a->hint < b->hint ? -1 : 1;
> + return tuple_compare(a->tuple, b->tuple, key_def);
> +}
Looks like we need null-aware hints as well, to preserve online null ->
not null alter semantics.
--
Konstantin Osipov, Moscow, Russia, +7 903 626 22 32
http://tarantool.io - www.twitter.com/kostja_osipov
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [tarantool-patches] [PATCH v2 4/4] box: introduce tuple compare hint for string index
2019-02-13 9:32 ` [PATCH v2 4/4] box: introduce tuple compare hint for string index Kirill Shcherbatov
2019-02-14 14:09 ` [tarantool-patches] " Konstantin Osipov
@ 2019-02-15 18:34 ` Kirill Shcherbatov
2019-02-19 15:01 ` [tarantool-patches] " Konstantin Osipov
2019-02-19 15:02 ` Kirill Shcherbatov
1 sibling, 2 replies; 13+ messages in thread
From: Kirill Shcherbatov @ 2019-02-15 18:34 UTC (permalink / raw)
To: tarantool-patches, kostja, vdavydov.dev; +Cc: Alexandr Lyapunov
Hi! I've implemented Kostya's concepts for compatible hints for UINT/INT.
Also fixed nullability troubles. Now alter looks fine for me.
I've thought about number/integer convertions, but such alter would not pass,
I guess.
=========================================
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.
Part of #3961
---
src/box/key_def.c | 1 +
src/box/key_def.h | 44 +++++++++
src/box/memtx_tree_decl.c | 125 ++++++++++++++++++++++++++
src/box/tuple_compare.cc | 182 ++++++++++++++++++++++++++++++++++++++
src/box/tuple_compare.h | 7 ++
src/coll.c | 45 ++++++++++
src/coll.h | 4 +
7 files changed, 408 insertions(+)
diff --git a/src/box/key_def.c b/src/box/key_def.c
index 9411ade39..ceca1ebee 100644
--- a/src/box/key_def.c
+++ b/src/box/key_def.c
@@ -135,6 +135,7 @@ key_def_set_cmp(struct key_def *def)
def->tuple_compare_with_key = tuple_compare_with_key_create(def);
tuple_hash_func_set(def);
tuple_extract_key_set(def);
+ tuple_hint_set(def);
}
static void
diff --git a/src/box/key_def.h b/src/box/key_def.h
index bf3e63b6d..a2a0bbecb 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
@@ -551,6 +562,39 @@ tuple_compare_with_key(const struct tuple *tuple, const char *key,
return key_def->tuple_compare_with_key(tuple, key, part_count, 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_decl.c b/src/box/memtx_tree_decl.c
index 084a0594f..55016148b 100644
--- a/src/box/memtx_tree_decl.c
+++ b/src/box/memtx_tree_decl.c
@@ -77,8 +77,133 @@ struct memtx_tuple_tree_key_data {
/* }}} */
+/* {{{ Memtx hinted and hint_only tree class. *******************/
+
+/**
+ * Struct that is used as a key in BPS tree definition in
+ * memtx_hint_only_tree and memtx_hinted_tree.
+*/
+struct memtx_hinted_tree_key_data {
+ /** Sequence of msgpacked search fields. */
+ const char *key;
+ /** Number of msgpacked search fields. */
+ uint32_t part_count;
+ /**
+ * Compare hint. Is calculated automatically on 'set'
+ * operation with memtx_hinted_tree_key_data_set().
+ */
+ uint64_t hint;
+};
+
+/**
+ * Struct that is used as a key in BPS tree definition in
+ * memtx_hint_only_tree and memtx_hinted_tree.
+ */
+struct memtx_hinted_tree_data {
+ /** Tuple this node is representing. */
+ struct tuple *tuple;
+ /**
+ * Compare hint. Is calculated automatically on 'set'
+ * operation with memtx_hinted_tree_data_set().
+ */
+ uint64_t hint;
+};
+
+/**
+ * Compare memtx_hinted_tree records.
+ */
+static int
+memtx_hinted_tree_data_cmp(struct memtx_hinted_tree_data *a,
+ struct memtx_hinted_tree_data *b,
+ struct key_def *key_def)
+{
+ if (a->hint != b->hint)
+ return a->hint < b->hint ? -1 : 1;
+ return tuple_compare(a->tuple, b->tuple, key_def);
+}
+
+/**
+ * Compare memtx_hinted_tree record with key.
+ */
+static int
+memtx_hinted_tree_data_cmp_with_key(struct memtx_hinted_tree_data *a,
+ struct memtx_hinted_tree_key_data *key,
+ struct key_def *key_def)
+{
+ if (a->hint != key->hint)
+ return a->hint < key->hint ? -1 : 1;
+ return tuple_compare_with_key(a->tuple, key->key, key->part_count,
+ key_def);
+}
+
+/**
+ * Initialize memtx_hinted_tree or memtx_hint_only_tree record
+ * with tuple and recalculate internal hint field.
+ */
+static void
+memtx_hinted_tree_data_set(struct memtx_hinted_tree_data *data,
+ struct tuple *tuple, struct key_def *key_def)
+{
+ data->tuple = tuple;
+ data->hint = tuple_hint(tuple, key_def);
+}
+
+/**
+ * Initialize memtx_hinted_tree or memtx_hint_only_tree key with
+ * key raw and part count and recalculate internal hint field.
+ */
+static void
+memtx_hinted_tree_key_data_set(struct memtx_hinted_tree_key_data *key_data,
+ const char *key, uint32_t part_count,
+ struct key_def *key_def)
+{
+ key_data->key = key;
+ key_data->part_count = part_count;
+ key_data->hint = key != NULL && part_count > 0 ?
+ key_hint(key, key_def) : 0;
+}
+
+#define MEMTX_TREE_NAME memtx_hinted_tree
+#define memtx_tree_elem struct memtx_hinted_tree_data
+#define memtx_tree_key struct memtx_hinted_tree_key_data
+#define MEMTX_TREE_ELEM_EQUAL(elem_a_ptr, elem_b_ptr) \
+ ((elem_a_ptr)->tuple == (elem_b_ptr)->tuple)
+#define MEMTX_TREE_ELEM_CMP(elem_a_ptr, elem_b_ptr, key_def) \
+ memtx_hinted_tree_data_cmp(elem_a_ptr, elem_b_ptr, key_def)
+#define MEMTX_TREE_ELEM_WITH_KEY_CMP(elem_ptr, key_ptr, key_def) \
+ memtx_hinted_tree_data_cmp_with_key(elem_ptr, key_ptr, key_def)
+#define MEMTX_TREE_ELEM_SET(elem_ptr, tuple, key_def) \
+ memtx_hinted_tree_data_set(elem_ptr, tuple, key_def)
+#define MEMTX_TREE_KEY_SET(key_ptr, key_val, part_count_val, key_def) \
+ memtx_hinted_tree_key_data_set(key_ptr, key_val, part_count_val, \
+ key_def)
+#define MEMTX_TREE_ELEM_GET(elem_ptr) ((elem_ptr)->tuple)
+#define MEMTX_TREE_KEY_GET(key_ptr, part_count_ptr) \
+ ({*part_count_ptr = (key_ptr)->part_count; (key_ptr)->key;})
+
+#include "memtx_tree_impl.h"
+
+#undef memtx_tree_key
+#undef memtx_tree_elem
+#undef MEMTX_TREE_KEY_GET
+#undef MEMTX_TREE_ELEM_GET
+#undef MEMTX_TREE_KEY_SET
+#undef MEMTX_TREE_ELEM_SET
+#undef MEMTX_TREE_ELEM_WITH_KEY_CMP
+#undef MEMTX_TREE_ELEM_CMP
+#undef MEMTX_TREE_ELEM_EQUAL
+#undef memtx_tree_key
+#undef memtx_tree_elem
+#undef MEMTX_TREE_NAME
+
+/* }}} */
+
struct index *
memtx_tree_index_new(struct memtx_engine *memtx, struct index_def *def)
{
+ if (def->cmp_def->parts->type == FIELD_TYPE_STRING ||
+ def->cmp_def->parts->type == FIELD_TYPE_UNSIGNED ||
+ def->cmp_def->parts->type == FIELD_TYPE_INTEGER)
+ return memtx_hinted_tree_index_new(memtx, def);
return memtx_tuple_tree_index_new(memtx, def);
}
diff --git a/src/box/tuple_compare.cc b/src/box/tuple_compare.cc
index ded802c7d..6ebf625a4 100644
--- a/src/box/tuple_compare.cc
+++ b/src/box/tuple_compare.cc
@@ -1321,4 +1321,186 @@ tuple_compare_with_key_create(const struct key_def *def)
compare_with_key_slowpath_funcs[cmp_func_idx];
}
+static uint64_t
+key_hint_default(const char *key, struct key_def *key_def)
+{
+ (void)key;
+ (void)key_def;
+ return 0;
+}
+
+static uint64_t
+tuple_hint_default(const struct tuple *tuple, struct key_def *key_def)
+{
+ (void)tuple;
+ (void)key_def;
+ return 0;
+}
+
+template<bool is_nullable>
+static uint64_t
+key_hint_uint(const char *key, struct key_def *key_def)
+{
+ assert(key_part_is_nullable(key_def->parts) == is_nullable);
+ if (is_nullable && mp_typeof(*key) == MP_NIL)
+ return 0;
+ assert(mp_typeof(*key) == MP_UINT);
+ uint64_t val = mp_decode_uint(&key);
+ if (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);
+ 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);
+ if (is_nullable && mp_typeof(*key) == MP_NIL)
+ return 0;
+ if (mp_typeof(*key) == MP_UINT) {
+ return key_hint_uint<is_nullable>(key, key_def);
+ } else {
+ assert(key_def->parts->type == FIELD_TYPE_INTEGER);
+ 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);
+ 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_string(const char *key, struct key_def *key_def)
+{
+ assert(key_part_is_nullable(key_def->parts) == is_nullable);
+ if (is_nullable && mp_typeof(*key) == MP_NIL)
+ return 0;
+ assert(key_def->parts->type == FIELD_TYPE_STRING);
+ 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;
+ /*
+ * Map the sequence of characters in the hint's bytes in
+ * the reverse order: the first character will be mapped
+ * in the highest byte of the number, etc.
+ * One additional bit encodes the presence of the next
+ * sign.
+ * 0bCHARBYTEU CHARBYTEU CHARBYTEU ... CHARBYTE0
+ * The sequence constructed in this way provides a
+ * comparison transitivity of strings no longer than 7
+ * bytes.
+ */
+ uint32_t process_len = MIN(len, 7);
+ for (uint32_t i = 0; i < process_len; i++) {
+ result <<= 9;
+ result |= 0x100;
+ result |= str[i];
+ }
+ /*
+ * If the length of the string is less than the 64-bit
+ * hint can accommodate, the insignificant positions are
+ * filled with 0.
+ */
+ result <<= 9 * (7 - 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);
+ 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);
+ if (is_nullable && mp_typeof(*key) == MP_NIL)
+ return 0;
+ assert(key_def->parts->type == FIELD_TYPE_STRING);
+ assert(mp_typeof(*key) == MP_STR);
+ assert(key_def->parts->coll != NULL);
+ 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);
+ 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
+tuple_hint_set(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;
+ default:
+ break;
+ };
+}
+
/* }}} tuple_compare_with_key */
diff --git a/src/box/tuple_compare.h b/src/box/tuple_compare.h
index e3a63204f..405460086 100644
--- a/src/box/tuple_compare.h
+++ b/src/box/tuple_compare.h
@@ -67,6 +67,13 @@ tuple_compare_create(const struct key_def *key_def);
tuple_compare_with_key_t
tuple_compare_with_key_create(const struct key_def *key_def);
+/**
+ * Initialize tuple_hint() and key_hint() functions for the key_def.
+ * @param key_def key definition to set up.
+ */
+void
+tuple_hint_set(struct key_def *key_def);
+
#if defined(__cplusplus)
} /* extern "C" */
#endif /* defined(__cplusplus) */
diff --git a/src/coll.c b/src/coll.c
index 6d9c44dbf..0e7c8ec92 100644
--- a/src/coll.c
+++ b/src/coll.c
@@ -33,6 +33,7 @@
#include "third_party/PMurHash.h"
#include "diag.h"
#include "assoc.h"
+#include "limits.h"
#include <unicode/ucol.h>
#include <trivia/config.h>
@@ -133,6 +134,48 @@ 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 string using ICU collation. */
+static uint64_t
+coll_icu_hint(const char *s, size_t s_len, struct coll *coll)
+{
+ UCharIterator itr;
+ uiter_setUTF8(&itr, s, s_len);
+ uint8_t buf[7];
+ 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 <= 7);
+ uint64_t result = 0;
+ for (int32_t i = 0; i < got; i++) {
+ result <<= 9;
+ result |= 0x100;
+ result |= buf[i];
+ }
+ result <<= 9 * (7 - got);
+ return result;
+}
+
+/**
+ * Get a compare hint of a string using BINARY collation.
+ * Works similar to key_hint_string, read it's comment for more
+ * details.
+ */
+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, 7);
+ for (uint32_t i = 0; i < process_len; i++) {
+ result <<= 9;
+ result |= 0x100;
+ result |= s[i];
+ }
+ result <<= 9 * (7 - process_len);
+ return result;
+}
+
/**
* Set up ICU collator and init cmp and hash members of collation.
* @param coll Collation to set up.
@@ -242,6 +285,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 +376,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/coll.h b/src/coll.h
index 9c725712a..53133dae3 100644
--- a/src/coll.h
+++ b/src/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.20.1
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [tarantool-patches] Re: [PATCH v2 4/4] box: introduce tuple compare hint for string index
2019-02-15 18:34 ` Kirill Shcherbatov
@ 2019-02-19 15:01 ` Konstantin Osipov
2019-02-19 15:02 ` Kirill Shcherbatov
1 sibling, 0 replies; 13+ messages in thread
From: Konstantin Osipov @ 2019-02-19 15:01 UTC (permalink / raw)
To: tarantool-patches; +Cc: vdavydov.dev, Alexandr Lyapunov
* Kirill Shcherbatov <kshcherbatov@tarantool.org> [19/02/15 21:36]:
> Hi! I've implemented Kostya's concepts for compatible hints for UINT/INT.
> Also fixed nullability troubles. Now alter looks fine for me.
> I've thought about number/integer convertions, but such alter would not pass,
> I guess.
>
Do you have tests for this or have you checked that specific tests
exist? E.g. when tuple hint is used *and* we change nullability
back and forth.
BTW, have you checked changes in collation, do they work?
--
Konstantin Osipov, Moscow, Russia, +7 903 626 22 32
http://tarantool.io - www.twitter.com/kostja_osipov
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [tarantool-patches] Re: [PATCH v2 4/4] box: introduce tuple compare hint for string index
2019-02-15 18:34 ` Kirill Shcherbatov
2019-02-19 15:01 ` [tarantool-patches] " Konstantin Osipov
@ 2019-02-19 15:02 ` Kirill Shcherbatov
2019-02-21 16:06 ` Vladimir Davydov
1 sibling, 1 reply; 13+ messages in thread
From: Kirill Shcherbatov @ 2019-02-19 15:02 UTC (permalink / raw)
To: tarantool-patches, Vladimir Davydov
Hm, it looks like introduced before collation hint for binary collation is a not working.
(I've dropped icu_bin_hint for now)
This is a particular case in which there is no collator object, so we can do without
hints at all in this case.
====================================================
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.
Closes #3961
---
src/box/key_def.c | 1 +
src/box/key_def.h | 44 +++++++++
src/box/memtx_tree_decl.c | 125 ++++++++++++++++++++++++++
src/box/tuple_compare.cc | 185 ++++++++++++++++++++++++++++++++++++++
src/box/tuple_compare.h | 7 ++
src/coll.c | 24 +++++
src/coll.h | 4 +
7 files changed, 390 insertions(+)
diff --git a/src/box/key_def.c b/src/box/key_def.c
index 9411ade39..ceca1ebee 100644
--- a/src/box/key_def.c
+++ b/src/box/key_def.c
@@ -135,6 +135,7 @@ key_def_set_cmp(struct key_def *def)
def->tuple_compare_with_key = tuple_compare_with_key_create(def);
tuple_hash_func_set(def);
tuple_extract_key_set(def);
+ tuple_hint_set(def);
}
static void
diff --git a/src/box/key_def.h b/src/box/key_def.h
index bf3e63b6d..a2a0bbecb 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
@@ -551,6 +562,39 @@ tuple_compare_with_key(const struct tuple *tuple, const char *key,
return key_def->tuple_compare_with_key(tuple, key, part_count, 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_decl.c b/src/box/memtx_tree_decl.c
index 084a0594f..55016148b 100644
--- a/src/box/memtx_tree_decl.c
+++ b/src/box/memtx_tree_decl.c
@@ -77,8 +77,133 @@ struct memtx_tuple_tree_key_data {
/* }}} */
+/* {{{ Memtx hinted and hint_only tree class. *******************/
+
+/**
+ * Struct that is used as a key in BPS tree definition in
+ * memtx_hint_only_tree and memtx_hinted_tree.
+*/
+struct memtx_hinted_tree_key_data {
+ /** Sequence of msgpacked search fields. */
+ const char *key;
+ /** Number of msgpacked search fields. */
+ uint32_t part_count;
+ /**
+ * Compare hint. Is calculated automatically on 'set'
+ * operation with memtx_hinted_tree_key_data_set().
+ */
+ uint64_t hint;
+};
+
+/**
+ * Struct that is used as a key in BPS tree definition in
+ * memtx_hint_only_tree and memtx_hinted_tree.
+ */
+struct memtx_hinted_tree_data {
+ /** Tuple this node is representing. */
+ struct tuple *tuple;
+ /**
+ * Compare hint. Is calculated automatically on 'set'
+ * operation with memtx_hinted_tree_data_set().
+ */
+ uint64_t hint;
+};
+
+/**
+ * Compare memtx_hinted_tree records.
+ */
+static int
+memtx_hinted_tree_data_cmp(struct memtx_hinted_tree_data *a,
+ struct memtx_hinted_tree_data *b,
+ struct key_def *key_def)
+{
+ if (a->hint != b->hint)
+ return a->hint < b->hint ? -1 : 1;
+ return tuple_compare(a->tuple, b->tuple, key_def);
+}
+
+/**
+ * Compare memtx_hinted_tree record with key.
+ */
+static int
+memtx_hinted_tree_data_cmp_with_key(struct memtx_hinted_tree_data *a,
+ struct memtx_hinted_tree_key_data *key,
+ struct key_def *key_def)
+{
+ if (a->hint != key->hint)
+ return a->hint < key->hint ? -1 : 1;
+ return tuple_compare_with_key(a->tuple, key->key, key->part_count,
+ key_def);
+}
+
+/**
+ * Initialize memtx_hinted_tree or memtx_hint_only_tree record
+ * with tuple and recalculate internal hint field.
+ */
+static void
+memtx_hinted_tree_data_set(struct memtx_hinted_tree_data *data,
+ struct tuple *tuple, struct key_def *key_def)
+{
+ data->tuple = tuple;
+ data->hint = tuple_hint(tuple, key_def);
+}
+
+/**
+ * Initialize memtx_hinted_tree or memtx_hint_only_tree key with
+ * key raw and part count and recalculate internal hint field.
+ */
+static void
+memtx_hinted_tree_key_data_set(struct memtx_hinted_tree_key_data *key_data,
+ const char *key, uint32_t part_count,
+ struct key_def *key_def)
+{
+ key_data->key = key;
+ key_data->part_count = part_count;
+ key_data->hint = key != NULL && part_count > 0 ?
+ key_hint(key, key_def) : 0;
+}
+
+#define MEMTX_TREE_NAME memtx_hinted_tree
+#define memtx_tree_elem struct memtx_hinted_tree_data
+#define memtx_tree_key struct memtx_hinted_tree_key_data
+#define MEMTX_TREE_ELEM_EQUAL(elem_a_ptr, elem_b_ptr) \
+ ((elem_a_ptr)->tuple == (elem_b_ptr)->tuple)
+#define MEMTX_TREE_ELEM_CMP(elem_a_ptr, elem_b_ptr, key_def) \
+ memtx_hinted_tree_data_cmp(elem_a_ptr, elem_b_ptr, key_def)
+#define MEMTX_TREE_ELEM_WITH_KEY_CMP(elem_ptr, key_ptr, key_def) \
+ memtx_hinted_tree_data_cmp_with_key(elem_ptr, key_ptr, key_def)
+#define MEMTX_TREE_ELEM_SET(elem_ptr, tuple, key_def) \
+ memtx_hinted_tree_data_set(elem_ptr, tuple, key_def)
+#define MEMTX_TREE_KEY_SET(key_ptr, key_val, part_count_val, key_def) \
+ memtx_hinted_tree_key_data_set(key_ptr, key_val, part_count_val, \
+ key_def)
+#define MEMTX_TREE_ELEM_GET(elem_ptr) ((elem_ptr)->tuple)
+#define MEMTX_TREE_KEY_GET(key_ptr, part_count_ptr) \
+ ({*part_count_ptr = (key_ptr)->part_count; (key_ptr)->key;})
+
+#include "memtx_tree_impl.h"
+
+#undef memtx_tree_key
+#undef memtx_tree_elem
+#undef MEMTX_TREE_KEY_GET
+#undef MEMTX_TREE_ELEM_GET
+#undef MEMTX_TREE_KEY_SET
+#undef MEMTX_TREE_ELEM_SET
+#undef MEMTX_TREE_ELEM_WITH_KEY_CMP
+#undef MEMTX_TREE_ELEM_CMP
+#undef MEMTX_TREE_ELEM_EQUAL
+#undef memtx_tree_key
+#undef memtx_tree_elem
+#undef MEMTX_TREE_NAME
+
+/* }}} */
+
struct index *
memtx_tree_index_new(struct memtx_engine *memtx, struct index_def *def)
{
+ if (def->cmp_def->parts->type == FIELD_TYPE_STRING ||
+ def->cmp_def->parts->type == FIELD_TYPE_UNSIGNED ||
+ def->cmp_def->parts->type == FIELD_TYPE_INTEGER)
+ return memtx_hinted_tree_index_new(memtx, def);
return memtx_tuple_tree_index_new(memtx, def);
}
diff --git a/src/box/tuple_compare.cc b/src/box/tuple_compare.cc
index ded802c7d..5845235ff 100644
--- a/src/box/tuple_compare.cc
+++ b/src/box/tuple_compare.cc
@@ -1321,4 +1321,189 @@ tuple_compare_with_key_create(const struct key_def *def)
compare_with_key_slowpath_funcs[cmp_func_idx];
}
+static uint64_t
+key_hint_default(const char *key, struct key_def *key_def)
+{
+ (void)key;
+ (void)key_def;
+ return 0;
+}
+
+static uint64_t
+tuple_hint_default(const struct tuple *tuple, struct key_def *key_def)
+{
+ (void)tuple;
+ (void)key_def;
+ return 0;
+}
+
+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);
+ if (is_nullable && mp_typeof(*key) == MP_NIL)
+ return 0;
+ assert(mp_typeof(*key) == MP_UINT);
+ uint64_t val = mp_decode_uint(&key);
+ if (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);
+ 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);
+ if (is_nullable && mp_typeof(*key) == MP_NIL)
+ return 0;
+ if (mp_typeof(*key) == MP_UINT) {
+ return key_hint_uint<is_nullable>(key, key_def);
+ } else {
+ assert(key_def->parts->type == FIELD_TYPE_INTEGER);
+ 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);
+ 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_string(const char *key, struct key_def *key_def)
+{
+ (void)key_def;
+ assert(key_part_is_nullable(key_def->parts) == is_nullable);
+ if (is_nullable && mp_typeof(*key) == MP_NIL)
+ return 0;
+ assert(key_def->parts->type == FIELD_TYPE_STRING);
+ 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;
+ /*
+ * Map the sequence of characters in the hint's bytes in
+ * the reverse order: the first character will be mapped
+ * in the highest byte of the number, etc.
+ * One additional bit encodes the presence of the next
+ * sign.
+ * 0bCHARBYTEU CHARBYTEU CHARBYTEU ... CHARBYTE0
+ * The sequence constructed in this way provides a
+ * comparison transitivity of strings no longer than 7
+ * bytes.
+ */
+ uint32_t process_len = MIN(len, 7);
+ for (uint32_t i = 0; i < process_len; i++) {
+ result <<= 9;
+ result |= 0x100;
+ result |= str[i];
+ }
+ /*
+ * If the length of the string is less than the 64-bit
+ * hint can accommodate, the insignificant positions are
+ * filled with 0.
+ */
+ result <<= 9 * (7 - 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);
+ 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);
+ if (is_nullable && mp_typeof(*key) == MP_NIL)
+ return 0;
+ assert(key_def->parts->type == FIELD_TYPE_STRING);
+ assert(mp_typeof(*key) == MP_STR);
+ assert(key_def->parts->coll != NULL);
+ 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);
+ 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
+tuple_hint_set(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->parts->coll->type != COLL_TYPE_BINARY) {
+ 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;
+ default:
+ break;
+ };
+}
+
/* }}} tuple_compare_with_key */
diff --git a/src/box/tuple_compare.h b/src/box/tuple_compare.h
index e3a63204f..405460086 100644
--- a/src/box/tuple_compare.h
+++ b/src/box/tuple_compare.h
@@ -67,6 +67,13 @@ tuple_compare_create(const struct key_def *key_def);
tuple_compare_with_key_t
tuple_compare_with_key_create(const struct key_def *key_def);
+/**
+ * Initialize tuple_hint() and key_hint() functions for the key_def.
+ * @param key_def key definition to set up.
+ */
+void
+tuple_hint_set(struct key_def *key_def);
+
#if defined(__cplusplus)
} /* extern "C" */
#endif /* defined(__cplusplus) */
diff --git a/src/coll.c b/src/coll.c
index 6d9c44dbf..922f03944 100644
--- a/src/coll.c
+++ b/src/coll.c
@@ -133,6 +133,28 @@ 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 string using ICU collation. */
+static uint64_t
+coll_icu_hint(const char *s, size_t s_len, struct coll *coll)
+{
+ UCharIterator itr;
+ uiter_setUTF8(&itr, s, s_len);
+ uint8_t buf[7];
+ 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 <= 7);
+ uint64_t result = 0;
+ for (int32_t i = 0; i < got; i++) {
+ result <<= 9;
+ result |= 0x100;
+ result |= buf[i];
+ }
+ result <<= 9 * (7 - got);
+ return result;
+}
+
/**
* Set up ICU collator and init cmp and hash members of collation.
* @param coll Collation to set up.
@@ -242,6 +264,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 +355,7 @@ coll_new(const struct coll_def *def)
coll->collator = NULL;
coll->cmp = coll_bin_cmp;
coll->hash = coll_bin_hash;
+ coll->hint = NULL;
break;
default:
unreachable();
diff --git a/src/coll.h b/src/coll.h
index 9c725712a..53133dae3 100644
--- a/src/coll.h
+++ b/src/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.20.1
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [PATCH v2 1/4] box: move memtx_tree implementation to source file
2019-02-13 9:32 ` [PATCH v2 1/4] box: move memtx_tree implementation to source file Kirill Shcherbatov
2019-02-14 13:57 ` [tarantool-patches] " Konstantin Osipov
@ 2019-02-21 13:26 ` Vladimir Davydov
1 sibling, 0 replies; 13+ messages in thread
From: Vladimir Davydov @ 2019-02-21 13:26 UTC (permalink / raw)
To: Kirill Shcherbatov; +Cc: tarantool-patches, kostja
The subject line prefix should be 'memtx:' I think.
On Wed, Feb 13, 2019 at 12:32:25PM +0300, Kirill Shcherbatov wrote:
> Refactored memtx_tree code so that memtx_tree.h contained only
> the signature of the tree object constructor memtx_tree_index_new,
> while all implementation details were in memtx_tree.c.
> This will further allow to template the implementation details.
>
> Needed for #3961
> ---
> src/box/memtx_tree.c | 62 ++++++++++++++++++++++++++++++++++++++--
> src/box/memtx_tree.h | 68 ++------------------------------------------
> 2 files changed, 63 insertions(+), 67 deletions(-)
The patch is good, but I think we shouldn't stop at memtx_tree and do
the same for other memtx indexes - hash, bitset, rtree. Please do it in
the scope of this patch.
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [PATCH v2 2/4] box: rework memtx_tree to store arbitrary nodes
2019-02-13 9:32 ` [PATCH v2 2/4] box: rework memtx_tree to store arbitrary nodes Kirill Shcherbatov
@ 2019-02-21 15:01 ` Vladimir Davydov
0 siblings, 0 replies; 13+ messages in thread
From: Vladimir Davydov @ 2019-02-21 15:01 UTC (permalink / raw)
To: Kirill Shcherbatov; +Cc: tarantool-patches, kostja
On Wed, Feb 13, 2019 at 12:32:26PM +0300, Kirill Shcherbatov wrote:
> Reworked memtx_tree class to use arbitrary containers as a tree
> nodes. This makes possible to implement tuple hints in subsequent
> patches.
>
> The memtx_tree.c is currently used in a header manner. This is to
> ensure that functional changes in the patch do not mix with
> refactoring, that will be finished in the next commit.
>
> Needed for #3961
> ---
> src/box/CMakeLists.txt | 2 +-
> src/box/memtx_tree.c | 498 ++++++++++++++++++++++++++------------
> src/box/memtx_tree_decl.c | 84 +++++++
> 3 files changed, 434 insertions(+), 150 deletions(-)
> create mode 100644 src/box/memtx_tree_decl.c
>
> diff --git a/src/box/CMakeLists.txt b/src/box/CMakeLists.txt
> index 5521e489e..dc8cc2cd5 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_decl.c
> memtx_rtree.c
> memtx_bitset.c
> engine.c
> diff --git a/src/box/memtx_tree.c b/src/box/memtx_tree.c
> index 2e8adb682..0874b7dc8 100644
> --- a/src/box/memtx_tree.c
> +++ b/src/box/memtx_tree.c
> @@ -1,5 +1,5 @@
> /*
> - * Copyright 2010-2016, Tarantool AUTHORS, please see AUTHORS file.
> + * 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
> @@ -28,72 +28,156 @@
> * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
> * SUCH DAMAGE.
> */
> -#include "memtx_tree.h"
> -#include "memtx_engine.h"
> -#include "space.h"
> -#include "schema.h" /* space_cache_find() */
> -#include "errinj.h"
> -#include "memory.h"
> -#include "fiber.h"
> -#include "tuple.h"
> -#include <third_party/qsort_arg.h>
Why touch header inclusions?
> +
> +#if defined(__cplusplus)
> +extern "C" {
> +#endif /* defined(__cplusplus) */
> +
This isn't needed in a header like this.
> #include <small/mempool.h>
> +#include <third_party/qsort_arg.h>
> +#include "memtx_engine.h"
> +#include "schema.h"
>
> -/**
> - * Struct that is used as a key in BPS tree definition.
> - */
> -struct memtx_tree_key_data {
> - /** Sequence of msgpacked search fields. */
> - const char *key;
> - /** Number of msgpacked search fields. */
> - uint32_t part_count;
> -};
> +#ifndef MEMTX_TREE_NAME
> +#error "MEMTX_TREE_NAME must be defined"
> +#endif
> +
> +#ifndef memtx_tree_elem
> +#error "memtx_tree_elem must be defined"
> +#endif
> +
> +#ifndef memtx_tree_key
> +#error "memtx_tree_key must be defined"
> +#endif
Let's please use _t suffix for types (memtx_tree_elem_t,
memtx_tree_key_t).
> +
> +#ifndef MEMTX_TREE_ELEM_CMP
> +#error "MEMTX_TREE_ELEM_CMP must be defined"
> +#endif
> +
> +#ifndef MEMTX_TREE_ELEM_WITH_KEY_CMP
> +#error "MEMTX_TREE_ELEM_WITH_KEY_CMP must be defined"
> +#endif
May be, call these MEMTX_TREE_COMPARE and MEMTX_TREE_COMPARE_KEY to
match BPS tree macros?
> +
> +#ifndef MEMTX_TREE_ELEM_SET
> +#error "MEMTX_TREE_ELEM_SET must be defined"
> +#endif
> +
> +#ifndef MEMTX_TREE_KEY_SET
> +#error "MEMTX_TREE_KEY_SET must be defined"
> +#endif
> +
> +#ifndef MEMTX_TREE_ELEM_GET
> +#error "MEMTX_TREE_ELEM_GET must be defined"
> +#endif
> +
> +#ifndef MEMTX_TREE_KEY_GET
> +#error "MEMTX_TREE_KEY_GET must be defined"
> +#endif
Please add a comment to each of the macros describing what it is
supposed to do.
>
> /**
> - * 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.
> + * The size of the biggest memtx tree iterator. Used with
> + * mempool_create. This is the size of the block that will be
> + * allocated for each iterator.
> */
> -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);
> -}
> +#define MEMTX_TREE_ITERATOR_SIZE (152)
Take a look at struct memtx_engine:
/** Memory pool for tree index iterator. */
struct mempool tree_iterator_pool;
/** Memory pool for rtree index iterator. */
struct mempool rtree_iterator_pool;
/** Memory pool for hash index iterator. */
struct mempool hash_iterator_pool;
/** Memory pool for bitset index iterator. */
struct mempool bitset_iterator_pool;
This looks ugly. Let's use this trick with static iterator size for all
index types. Please do it in a separate patch.
>
> -#define BPS_TREE_NAME memtx_tree
> +#define bps_tree_elem_t memtx_tree_elem
> +#define bps_tree_key_t memtx_tree_key *
> +#define bps_tree_arg_t struct key_def *
> +#define BPS_TREE_NAME CONCAT3(MEMTX_TREE_NAME, _, 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_arg_t struct key_def *
> +#define BPS_TREE_COMPARE(a, b, arg) MEMTX_TREE_ELEM_CMP(&a, &b, arg)
> +#define BPS_TREE_COMPARE_KEY(a, b, arg) MEMTX_TREE_ELEM_WITH_KEY_CMP(&a, b, arg)
> +#define BPS_TREE_NO_DEBUG
>
> #include "salad/bps_tree.h"
>
> +#undef bps_tree_elem_t
> +#undef bps_tree_key_t
> +#undef bps_tree_arg_t
> #undef BPS_TREE_NAME
> #undef BPS_TREE_BLOCK_SIZE
> #undef BPS_TREE_EXTENT_SIZE
> #undef BPS_TREE_COMPARE
> #undef BPS_TREE_COMPARE_KEY
> -#undef bps_tree_elem_t
> -#undef bps_tree_key_t
> -#undef bps_tree_arg_t
> +#undef BPS_TREE_NO_DEBUG
> +
> +#define memtx_tree CONCAT3(MEMTX_TREE_NAME, _, tree)
> +#define _tree_api_name(postfix) CONCAT5(MEMTX_TREE_NAME, _, tree, _, postfix)
Why not _api_name?
> +#define memtx_tree_iterator _tree_api_name(iterator)
> +#define memtx_tree_iterator_is_invalid _tree_api_name(iterator_is_invalid)
> +#define memtx_tree_iterator_first _tree_api_name(iterator_first)
> +#define memtx_tree_iterator_last _tree_api_name(iterator_last)
> +#define memtx_tree_iterator_get_elem _tree_api_name(iterator_get_elem)
> +#define memtx_tree_iterator_next _tree_api_name(iterator_next)
> +#define memtx_tree_iterator_prev _tree_api_name(iterator_prev)
> +#define memtx_tree_iterator_freeze _tree_api_name(iterator_freeze)
> +#define memtx_tree_iterator_destroy _tree_api_name(iterator_destroy)
> +#define memtx_tree_create _tree_api_name(create)
> +#define memtx_tree_build _tree_api_name(build)
> +#define memtx_tree_destroy _tree_api_name(destroy)
> +#define memtx_tree_find _tree_api_name(find)
> +#define memtx_tree_insert _tree_api_name(insert)
> +#define memtx_tree_delete _tree_api_name(delete)
> +#define memtx_tree_size _tree_api_name(size)
> +#define memtx_tree_mem_used _tree_api_name(mem_used)
> +#define memtx_tree_random _tree_api_name(random)
> +#define memtx_tree_invalid_iterator _tree_api_name(invalid_iterator)
> +#define memtx_tree_lower_bound _tree_api_name(lower_bound)
> +#define memtx_tree_upper_bound _tree_api_name(upper_bound)
> +#define memtx_tree_lower_bound_elem _tree_api_name(lower_bound_elem)
> +#define memtx_tree_upper_bound_elem _tree_api_name(upper_bound_elem)
> +
> +#undef _api_name
BPS tree should undef all macros it defines on its own. Please fix it in
a separate patch.
> +#define _api_name(postfix) CONCAT3(MEMTX_TREE_NAME, _, postfix)
> +#define memtx_tree_index _api_name(index)
> +#define memtx_tree_qcompare _api_name(qcompare)
> +#define tree_iterator _api_name(iterator)
> +#define tree_iterator_free _api_name(iterator_free)
> +#define tree_iterator_cast _api_name(iterator_cast)
> +#define tree_iterator_dummie _api_name(iterator_dummie)
> +#define tree_iterator_next _api_name(iterator_next)
> +#define tree_iterator_prev _api_name(iterator_prev)
> +#define tree_iterator_next_equal _api_name(iterator_next_equal)
> +#define tree_iterator_prev_equal _api_name(iterator_prev_equal)
> +#define tree_iterator_set_next_method _api_name(iterator_set_next_method)
> +#define tree_iterator_start _api_name(iterator_start)
> +#define memtx_tree_index_cmp_def _api_name(index_cmp_def)
> +#define memtx_tree_index_free _api_name(index_free)
> +#define memtx_tree_index_gc_run _api_name(index_gc_run)
> +#define memtx_tree_index_gc_free _api_name(index_gc_free)
> +#define memtx_tree_index_gc_vtab _api_name(index_gc_vtab)
> +#define memtx_tree_index_destroy _api_name(index_destroy)
> +#define memtx_tree_index_update_def _api_name(index_update_def)
> +#define memtx_tree_index_depends_on_pk _api_name(index_depends_on_pk)
> +#define memtx_tree_index_size _api_name(index_size)
> +#define memtx_tree_index_bsize _api_name(index_bsize)
> +#define memtx_tree_index_random _api_name(index_random)
> +#define memtx_tree_index_count _api_name(index_count)
> +#define memtx_tree_index_get _api_name(index_get)
> +#define memtx_tree_index_insert_tuple _api_name(index_insert_tuple)
> +#define memtx_tree_index_delete_tuple _api_name(index_delete_tuple)
> +#define memtx_tree_index_replace _api_name(index_replace)
> +#define memtx_tree_index_create_iterator _api_name(index_create_iterator)
> +#define memtx_tree_index_begin_build _api_name(index_begin_build)
> +#define memtx_tree_index_build_next _api_name(index_build_next)
> +#define memtx_tree_index_reserve _api_name(index_reserve)
> +#define memtx_tree_index_end_build _api_name(index_end_build)
> +#define tree_snapshot_iterator _api_name(snapshot_iterator)
> +#define tree_snapshot_iterator_free _api_name(snapshot_iterator_free)
> +#define tree_snapshot_iterator_next _api_name(snapshot_iterator_next)
> +#define memtx_tree_index_create_snapshot_iterator\
> + _api_name(index_create_snapshot_iterator)
> +#define memtx_tree_index_vtab _api_name(index_vtab)
> +#define memtx_tree_index_new _api_name(index_new)
I'd undef _api_name right here, because we don't need it anywhere else.
>
> struct memtx_tree_index {
> struct index base;
> - struct memtx_tree tree;
> - struct tuple **build_array;
> + memtx_tree_elem *build_array;
> size_t build_array_size, build_array_alloc_size;
> struct memtx_gc_task gc_task;
> + struct memtx_tree tree;
Nit: pointless change (moving 'tree' member).
> struct memtx_tree_iterator gc_iterator;
> };
>
> @@ -102,8 +186,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);
> + return MEMTX_TREE_ELEM_CMP((memtx_tree_elem *)a,
> + (memtx_tree_elem *)b, c);
> }
>
> /* {{{ MemtxTree Iterators ****************************************/
> @@ -113,17 +197,21 @@ 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;
> + memtx_tree_key key_data;
> + memtx_tree_elem current;
> /** Memory pool the iterator was allocated from. */
> struct mempool *pool;
> };
>
> +static_assert(sizeof(struct tree_iterator) <= MEMTX_TREE_ITERATOR_SIZE,
> + "tree_iterator must be less or equal than "
> + "MEMTX_TREE_ITERATOR_SIZE");
> +
> 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;
> @@ -132,9 +220,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 = MEMTX_TREE_ELEM_GET(&it->current);
> + if (tuple != NULL)
> + tuple_unref(tuple);
> mempool_free(it->pool, it);
> }
>
> @@ -149,25 +238,28 @@ 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(MEMTX_TREE_ELEM_GET(&it->current) != NULL);
> + memtx_tree_elem *check =
> + memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
> + if (check == NULL ||
> + MEMTX_TREE_ELEM_GET(check) != MEMTX_TREE_ELEM_GET(&it->current)) {
AFAIU this check isn't quite correct: we want to make sure that
it->current and check refer to the same tree element. So in case
of a multikey index it isn't enough to just check the tuples they
refer to - you also need to check the key offsets.
> diff --git a/src/box/memtx_tree_decl.c b/src/box/memtx_tree_decl.c
> new file mode 100644
> index 000000000..03e0e0ed7
> --- /dev/null
> +++ b/src/box/memtx_tree_decl.c
> @@ -0,0 +1,84 @@
> +/*
> + * 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 <stdbool.h>
> +#include <stdint.h>
> +#include "tuple_compare.h"
> +#include "memtx_tree.h"
> +
> +/* {{{ Memtx tree of tuples class. ******************************/
> +
> +/** Struct that is used as a key in BPS tree definition. */
> +struct memtx_tuple_tree_key_data {
> + /** Sequence of msgpacked search fields. */
> + const char *key;
> + /** Number of msgpacked search fields. */
> + uint32_t part_count;
> +};
> +
> +#define MEMTX_TREE_NAME memtx_tuple_tree
I don't quite like the name, because all memtx indexes store tuples,
eventually. May be, memtx_simple_tree or memtx_basic_tree?
> +#define memtx_tree_elem struct tuple *
> +#define memtx_tree_key struct memtx_tuple_tree_key_data
> +#define MEMTX_TREE_ELEM_CMP(elem_a_ptr, elem_b_ptr, key_def) \
> + tuple_compare(*elem_a_ptr, *elem_b_ptr, key_def)
> +#define MEMTX_TREE_ELEM_WITH_KEY_CMP(elem_ptr, key_ptr, key_def) \
> + tuple_compare_with_key(*elem_ptr, (key_ptr)->key, \
> + (key_ptr)->part_count, key_def)
> +#define MEMTX_TREE_ELEM_SET(elem_ptr, tuple, key_def) \
> + ({(void)key_def; *elem_ptr = tuple;})
> +#define MEMTX_TREE_KEY_SET(key_ptr, key_val, part_count_val, key_def) \
> + ({(void)key_def; (key_ptr)->key = key_val; \
> + (key_ptr)->part_count = part_count_val;})
> +#define MEMTX_TREE_ELEM_GET(elem_ptr) (*(elem_ptr))
> +#define MEMTX_TREE_KEY_GET(key_ptr, part_count_ptr) \
> + ({*part_count_ptr = (key_ptr)->part_count; (key_ptr)->key;})
> +
> +#include "memtx_tree.c"
> +
> +#undef memtx_tree_key
> +#undef memtx_tree_elem
> +#undef MEMTX_TREE_KEY_GET
> +#undef MEMTX_TREE_ELEM_GET
> +#undef MEMTX_TREE_KEY_SET
> +#undef MEMTX_TREE_ELEM_SET
> +#undef MEMTX_TREE_ELEM_WITH_KEY_CMP
> +#undef MEMTX_TREE_ELEM_CMP
> +#undef MEMTX_TREE_ELEM_EQUAL
This one is never defined.
> +#undef memtx_tree_key
> +#undef memtx_tree_elem
You undef those twice.
> +#undef MEMTX_TREE_NAME
> +
> +/* }}} */
> +
> +struct index *
> +memtx_tree_index_new(struct memtx_engine *memtx, struct index_def *def)
> +{
> + return memtx_tuple_tree_index_new(memtx, def);
> +}
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [tarantool-patches] Re: [PATCH v2 4/4] box: introduce tuple compare hint for string index
2019-02-19 15:02 ` Kirill Shcherbatov
@ 2019-02-21 16:06 ` Vladimir Davydov
0 siblings, 0 replies; 13+ messages in thread
From: Vladimir Davydov @ 2019-02-21 16:06 UTC (permalink / raw)
To: Kirill Shcherbatov; +Cc: tarantool-patches
On Tue, Feb 19, 2019 at 06:02:55PM +0300, Kirill Shcherbatov wrote:
> diff --git a/src/box/memtx_tree_decl.c b/src/box/memtx_tree_decl.c
> index 084a0594f..55016148b 100644
> --- a/src/box/memtx_tree_decl.c
> +++ b/src/box/memtx_tree_decl.c
> @@ -77,8 +77,133 @@ struct memtx_tuple_tree_key_data {
>
> /* }}} */
>
> +/* {{{ Memtx hinted and hint_only tree class. *******************/
There's no hint_only tree anymore. Please update the comments.
> +
> +/**
> + * Struct that is used as a key in BPS tree definition in
> + * memtx_hint_only_tree and memtx_hinted_tree.
> +*/
> +struct memtx_hinted_tree_key_data {
> + /** Sequence of msgpacked search fields. */
> + const char *key;
> + /** Number of msgpacked search fields. */
> + uint32_t part_count;
> + /**
> + * Compare hint. Is calculated automatically on 'set'
Comparison hint. 'Is' isn't necessary - could be simply Calculated ...
> + * operation with memtx_hinted_tree_key_data_set().
> + */
> + uint64_t hint;
> +};
> +
> +/**
> + * Struct that is used as a key in BPS tree definition in
> + * memtx_hint_only_tree and memtx_hinted_tree.
> + */
> +struct memtx_hinted_tree_data {
> + /** Tuple this node is representing. */
represents
> + struct tuple *tuple;
> + /**
> + * Compare hint. Is calculated automatically on 'set'
> + * operation with memtx_hinted_tree_data_set().
> + */
> + uint64_t hint;
> +};
> +
> +/**
> + * Compare memtx_hinted_tree records.
> + */
> +static int
> +memtx_hinted_tree_data_cmp(struct memtx_hinted_tree_data *a,
> + struct memtx_hinted_tree_data *b,
> + struct key_def *key_def)
> +{
> + if (a->hint != b->hint)
> + return a->hint < b->hint ? -1 : 1;
> + return tuple_compare(a->tuple, b->tuple, key_def);
> +}
> +
> +/**
> + * Compare memtx_hinted_tree record with key.
> + */
> +static int
> +memtx_hinted_tree_data_cmp_with_key(struct memtx_hinted_tree_data *a,
> + struct memtx_hinted_tree_key_data *key,
> + struct key_def *key_def)
> +{
> + if (a->hint != key->hint)
> + return a->hint < key->hint ? -1 : 1;
> + return tuple_compare_with_key(a->tuple, key->key, key->part_count,
> + key_def);
> +}
> +
> +/**
> + * Initialize memtx_hinted_tree or memtx_hint_only_tree record
> + * with tuple and recalculate internal hint field.
> + */
> +static void
> +memtx_hinted_tree_data_set(struct memtx_hinted_tree_data *data,
> + struct tuple *tuple, struct key_def *key_def)
> +{
> + data->tuple = tuple;
> + data->hint = tuple_hint(tuple, key_def);
> +}
> +
> +/**
> + * Initialize memtx_hinted_tree or memtx_hint_only_tree key with
> + * key raw and part count and recalculate internal hint field.
> + */
> +static void
> +memtx_hinted_tree_key_data_set(struct memtx_hinted_tree_key_data *key_data,
> + const char *key, uint32_t part_count,
> + struct key_def *key_def)
All these functions aren't used anywhere except in MEMTX_TREE_ macros,
and they're pretty short. Worth inlining them there?
> +{
> + key_data->key = key;
> + key_data->part_count = part_count;
> + key_data->hint = key != NULL && part_count > 0 ?
No need to check both part_count and key. Either of them is enough.
> + key_hint(key, key_def) : 0;
> +}
> +
> +#define MEMTX_TREE_NAME memtx_hinted_tree
> +#define memtx_tree_elem struct memtx_hinted_tree_data
> +#define memtx_tree_key struct memtx_hinted_tree_key_data
> +#define MEMTX_TREE_ELEM_EQUAL(elem_a_ptr, elem_b_ptr) \
> + ((elem_a_ptr)->tuple == (elem_b_ptr)->tuple)
This macro isn't required as far as I recall.
> +#define MEMTX_TREE_ELEM_CMP(elem_a_ptr, elem_b_ptr, key_def) \
> + memtx_hinted_tree_data_cmp(elem_a_ptr, elem_b_ptr, key_def)
> +#define MEMTX_TREE_ELEM_WITH_KEY_CMP(elem_ptr, key_ptr, key_def) \
> + memtx_hinted_tree_data_cmp_with_key(elem_ptr, key_ptr, key_def)
> +#define MEMTX_TREE_ELEM_SET(elem_ptr, tuple, key_def) \
> + memtx_hinted_tree_data_set(elem_ptr, tuple, key_def)
> +#define MEMTX_TREE_KEY_SET(key_ptr, key_val, part_count_val, key_def) \
> + memtx_hinted_tree_key_data_set(key_ptr, key_val, part_count_val, \
> + key_def)
> +#define MEMTX_TREE_ELEM_GET(elem_ptr) ((elem_ptr)->tuple)
> +#define MEMTX_TREE_KEY_GET(key_ptr, part_count_ptr) \
> + ({*part_count_ptr = (key_ptr)->part_count; (key_ptr)->key;})
> +
> +#include "memtx_tree_impl.h"
> +
> +#undef memtx_tree_key
> +#undef memtx_tree_elem
> +#undef MEMTX_TREE_KEY_GET
> +#undef MEMTX_TREE_ELEM_GET
> +#undef MEMTX_TREE_KEY_SET
> +#undef MEMTX_TREE_ELEM_SET
> +#undef MEMTX_TREE_ELEM_WITH_KEY_CMP
> +#undef MEMTX_TREE_ELEM_CMP
> +#undef MEMTX_TREE_ELEM_EQUAL
> +#undef memtx_tree_key
> +#undef memtx_tree_elem
> +#undef MEMTX_TREE_NAME
> +
> +/* }}} */
> +
> struct index *
> memtx_tree_index_new(struct memtx_engine *memtx, struct index_def *def)
> {
> + if (def->cmp_def->parts->type == FIELD_TYPE_STRING ||
> + def->cmp_def->parts->type == FIELD_TYPE_UNSIGNED ||
> + def->cmp_def->parts->type == FIELD_TYPE_INTEGER)
> + return memtx_hinted_tree_index_new(memtx, def);
> return memtx_tuple_tree_index_new(memtx, def);
> }
> diff --git a/src/box/tuple_compare.cc b/src/box/tuple_compare.cc
> index ded802c7d..5845235ff 100644
> --- a/src/box/tuple_compare.cc
> +++ b/src/box/tuple_compare.cc
> @@ -1321,4 +1321,189 @@ tuple_compare_with_key_create(const struct key_def *def)
> compare_with_key_slowpath_funcs[cmp_func_idx];
> }
I think all the hints should be defined in new files tuple_hint.{h,cc}
>
> +static uint64_t
> +key_hint_default(const char *key, struct key_def *key_def)
> +{
> + (void)key;
> + (void)key_def;
> + return 0;
> +}
> +
> +static uint64_t
> +tuple_hint_default(const struct tuple *tuple, struct key_def *key_def)
> +{
> + (void)tuple;
> + (void)key_def;
> + return 0;
> +}
> +
> +template<bool is_nullable>
I doubt we need to use templates here, but OK, let them be.
> +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);
> + if (is_nullable && mp_typeof(*key) == MP_NIL)
> + return 0;
> + assert(mp_typeof(*key) == MP_UINT);
> + uint64_t val = mp_decode_uint(&key);
> + if (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);
> + 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);
> + if (is_nullable && mp_typeof(*key) == MP_NIL)
> + return 0;
> + if (mp_typeof(*key) == MP_UINT) {
> + return key_hint_uint<is_nullable>(key, key_def);
> + } else {
> + assert(key_def->parts->type == FIELD_TYPE_INTEGER);
This assertion should be in the beginning of this function, no?
Please also add assertions checking part->type to other hint functions.
> + 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);
> + 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_string(const char *key, struct key_def *key_def)
> +{
> + (void)key_def;
> + assert(key_part_is_nullable(key_def->parts) == is_nullable);
> + if (is_nullable && mp_typeof(*key) == MP_NIL)
> + return 0;
> + assert(key_def->parts->type == FIELD_TYPE_STRING);
> + 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;
> + /*
> + * Map the sequence of characters in the hint's bytes in
> + * the reverse order: the first character will be mapped
> + * in the highest byte of the number, etc.
> + * One additional bit encodes the presence of the next
> + * sign.
> + * 0bCHARBYTEU CHARBYTEU CHARBYTEU ... CHARBYTE0
> + * The sequence constructed in this way provides a
> + * comparison transitivity of strings no longer than 7
> + * bytes.
Still I don't understand why we need this transformation and why simply
using a sequence of bytes constituting the string isn't enough. Could
you give an example?
> + */
> + uint32_t process_len = MIN(len, 7);
> + for (uint32_t i = 0; i < process_len; i++) {
> + result <<= 9;
> + result |= 0x100;
> + result |= str[i];
> + }
> + /*
> + * If the length of the string is less than the 64-bit
> + * hint can accommodate, the insignificant positions are
> + * filled with 0.
> + */
> + result <<= 9 * (7 - 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);
> + 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);
> + if (is_nullable && mp_typeof(*key) == MP_NIL)
> + return 0;
> + assert(key_def->parts->type == FIELD_TYPE_STRING);
> + assert(mp_typeof(*key) == MP_STR);
> + assert(key_def->parts->coll != NULL);
> + 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);
> + 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
> +tuple_hint_set(struct key_def *def)
Should be called key_def_set_hint_func. Please rename.
> +{
> + 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->parts->coll->type != COLL_TYPE_BINARY) {
> + 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;
> + default:
> + break;
> + };
> +}
^ permalink raw reply [flat|nested] 13+ messages in thread
end of thread, other threads:[~2019-02-21 16:06 UTC | newest]
Thread overview: 13+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-02-13 9:32 [PATCH v2 0/4] box: introduce hint option for memtx tree index Kirill Shcherbatov
2019-02-13 9:32 ` [PATCH v2 1/4] box: move memtx_tree implementation to source file Kirill Shcherbatov
2019-02-14 13:57 ` [tarantool-patches] " Konstantin Osipov
2019-02-21 13:26 ` Vladimir Davydov
2019-02-13 9:32 ` [PATCH v2 2/4] box: rework memtx_tree to store arbitrary nodes Kirill Shcherbatov
2019-02-21 15:01 ` Vladimir Davydov
2019-02-13 9:32 ` [PATCH v2 3/4] box: rename memtx_tree.c to memtx_tree_impl.h Kirill Shcherbatov
2019-02-13 9:32 ` [PATCH v2 4/4] box: introduce tuple compare hint for string index Kirill Shcherbatov
2019-02-14 14:09 ` [tarantool-patches] " Konstantin Osipov
2019-02-15 18:34 ` Kirill Shcherbatov
2019-02-19 15:01 ` [tarantool-patches] " Konstantin Osipov
2019-02-19 15:02 ` Kirill Shcherbatov
2019-02-21 16:06 ` Vladimir Davydov
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox