From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp45.i.mail.ru (smtp45.i.mail.ru [94.100.177.105]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by dev.tarantool.org (Postfix) with ESMTPS id 2139D44643A for ; Wed, 21 Oct 2020 13:23:47 +0300 (MSK) From: Aleksandr Lyapunov Date: Wed, 21 Oct 2020 13:23:32 +0300 Message-Id: <1603275812-32375-3-git-send-email-alyapunov@tarantool.org> In-Reply-To: <1603275812-32375-1-git-send-email-alyapunov@tarantool.org> References: <1603275812-32375-1-git-send-email-alyapunov@tarantool.org> MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 8bit Subject: [Tarantool-patches] [PATCH v2 2/2] memtx: make tuple compare hints optional List-Id: Tarantool development patches List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: tarantool-patches@dev.tarantool.org, Nikita Pettik , Ilya Kosarev Since 9fba29abb4e05babb9b23b4413bd8083f0fba933 (memtx: introduce tuple compare hint) memtx tree key data (indexes) started to contain extra 8 bytes as a hint. Now it is optional and can be turned off in an index options with "hint = false" entry. Closes #4927 @TarantoolBot document Title: memtx: optional tuple compare hints Update the documentation for an index creation to reflect that there is now an option to turn off hints for the index. --- src/box/index_def.c | 2 + src/box/index_def.h | 6 + src/box/lua/schema.lua | 53 ++++ src/box/lua/space.cc | 7 + src/box/memtx_engine.c | 2 + src/box/memtx_tree.cc | 606 ++++++++++++++++++++++++------------ src/lib/salad/bps_tree.h | 19 ++ test/box/alter.result | 103 +++++- test/box/alter.test.lua | 34 ++ test/box/errinj.result | 3 +- test/box/tree_pk.result | 314 +++++++++++++++++++ test/box/tree_pk.test.lua | 115 +++++++ test/box/tree_pk_multipart.result | 153 +++++++++ test/box/tree_pk_multipart.test.lua | 64 ++++ 14 files changed, 1274 insertions(+), 207 deletions(-) diff --git a/src/box/index_def.c b/src/box/index_def.c index 9802961..79394b8 100644 --- a/src/box/index_def.c +++ b/src/box/index_def.c @@ -51,6 +51,7 @@ const struct index_opts index_opts_default = { /* .lsn = */ 0, /* .stat = */ NULL, /* .func = */ 0, + /* .hint = */ true, }; const struct opt_def index_opts_reg[] = { @@ -66,6 +67,7 @@ const struct opt_def index_opts_reg[] = { OPT_DEF("lsn", OPT_INT64, struct index_opts, lsn), OPT_DEF("func", OPT_UINT32, struct index_opts, func_id), OPT_DEF_LEGACY("sql"), + OPT_DEF("hint", OPT_BOOL, struct index_opts, hint), OPT_END, }; diff --git a/src/box/index_def.h b/src/box/index_def.h index d928b23..2180a69 100644 --- a/src/box/index_def.h +++ b/src/box/index_def.h @@ -165,6 +165,10 @@ struct index_opts { struct index_stat *stat; /** Identifier of the functional index function. */ uint32_t func_id; + /** + * Use hint optimization for tree index. + */ + bool hint; }; extern const struct index_opts index_opts_default; @@ -211,6 +215,8 @@ index_opts_cmp(const struct index_opts *o1, const struct index_opts *o2) return o1->bloom_fpr < o2->bloom_fpr ? -1 : 1; if (o1->func_id != o2->func_id) return o1->func_id - o2->func_id; + if (o1->hint != o2->hint) + return o1->hint - o2->hint; return 0; } diff --git a/src/box/lua/schema.lua b/src/box/lua/schema.lua index 1131af7..9cc1289 100644 --- a/src/box/lua/schema.lua +++ b/src/box/lua/schema.lua @@ -1000,8 +1000,31 @@ local index_options = { page_size = 'number', bloom_fpr = 'number', func = 'number, string', + hint = 'boolean', } +local function jsonpaths_from_idx_parts(parts) + local paths = {} + + for _, part in pairs(parts) do + if type(part.path) == 'string' then + table.insert(paths, part.path) + end + end + + return paths +end + +local function is_multikey_index(parts) + for _, path in pairs(jsonpaths_from_idx_parts(parts)) do + if path:find('[*]', 1, true) then + return true + end + end + + return false +end + -- -- check_param_table() template for alter index, -- includes all index options. @@ -1076,6 +1099,15 @@ box.schema.index.create = function(space_id, name, options) options_defaults = {} end options = update_param_table(options, options_defaults) + if options.hint and + (options.type ~= 'tree' or box.space[space_id].engine ~= 'memtx') then + box.error(box.error.MODIFY_INDEX, name, space.name, + "hint is only reasonable with memtx tree index") + end + if options.hint and options.func then + box.error(box.error.MODIFY_INDEX, name, space.name, + "functional index can't use hints") + end local _index = box.space[box.schema.INDEX_ID] local _vindex = box.space[box.schema.VINDEX_ID] @@ -1115,6 +1147,7 @@ box.schema.index.create = function(space_id, name, options) run_size_ratio = options.run_size_ratio, bloom_fpr = options.bloom_fpr, func = options.func, + hint = options.hint, } local field_type_aliases = { num = 'unsigned'; -- Deprecated since 1.7.2 @@ -1135,6 +1168,10 @@ box.schema.index.create = function(space_id, name, options) if parts_can_be_simplified then parts = simplify_index_parts(parts) end + if options.hint and is_multikey_index(parts) then + box.error(box.error.MODIFY_INDEX, name, space.name, + "multikey index can't use hints") + end if index_opts.func ~= nil and type(index_opts.func) == 'string' then index_opts.func = func_id_by_name(index_opts.func) end @@ -1253,6 +1290,17 @@ box.schema.index.alter = function(space_id, index_id, options) index_opts[k] = options[k] end end + if options.hint and + (options.type ~= 'tree' or box.space[space_id].engine ~= 'memtx') then + box.error(box.error.MODIFY_INDEX, space.index[index_id].name, + space.name, + "hint is only reasonable with memtx tree index") + end + if options.hint and options.func then + box.error(box.error.MODIFY_INDEX, space.index[index_id].name, + space.name, + "functional index can't use hints") + end if options.parts then local parts_can_be_simplified parts, parts_can_be_simplified = @@ -1262,6 +1310,11 @@ box.schema.index.alter = function(space_id, index_id, options) parts = simplify_index_parts(parts) end end + if options.hint and is_multikey_index(parts) then + box.error(box.error.MODIFY_INDEX, space.index[index_id].name, + space.name, + "multikey index can't use hints") + end if index_opts.func ~= nil and type(index_opts.func) == 'string' then index_opts.func = func_id_by_name(index_opts.func) end diff --git a/src/box/lua/space.cc b/src/box/lua/space.cc index 177c588..1ea993c 100644 --- a/src/box/lua/space.cc +++ b/src/box/lua/space.cc @@ -344,6 +344,13 @@ lbox_fillspace(struct lua_State *L, struct space *space, int i) lua_pushnumber(L, index_opts->dimension); lua_setfield(L, -2, "dimension"); } + if (space_is_memtx(space) && index_def->type == TREE) { + lua_pushboolean(L, index_opts->hint); + lua_setfield(L, -2, "hint"); + } else { + lua_pushnil(L); + lua_setfield(L, -2, "hint"); + } if (index_opts->func_id > 0) { lua_pushstring(L, "func"); diff --git a/src/box/memtx_engine.c b/src/box/memtx_engine.c index 8147557..43000ba 100644 --- a/src/box/memtx_engine.c +++ b/src/box/memtx_engine.c @@ -1398,6 +1398,8 @@ memtx_index_def_change_requires_rebuild(struct index *index, return true; if (old_def->opts.func_id != new_def->opts.func_id) return true; + if (old_def->opts.hint != new_def->opts.hint) + return true; const struct key_def *old_cmp_def, *new_cmp_def; if (index_depends_on_pk(index)) { diff --git a/src/box/memtx_tree.cc b/src/box/memtx_tree.cc index d3b993b..44bdc86 100644 --- a/src/box/memtx_tree.cc +++ b/src/box/memtx_tree.cc @@ -45,23 +45,51 @@ /** * Struct that is used as a key in BPS tree definition. */ -struct memtx_tree_key_data { +struct memtx_tree_key_data_common { /** Sequence of msgpacked search fields. */ const char *key; /** Number of msgpacked search fields. */ uint32_t part_count; +}; + +template +struct memtx_tree_key_data; + +template <> +struct memtx_tree_key_data : memtx_tree_key_data_common { + static constexpr hint_t hint = HINT_NONE; + void set_hint(hint_t) { assert(false); } +}; + +template <> +struct memtx_tree_key_data : memtx_tree_key_data_common { /** Comparison hint, see tuple_hint(). */ hint_t hint; + void set_hint(hint_t h) { hint = h; } }; /** * Struct that is used as a elem in BPS tree definition. */ -struct memtx_tree_data { +struct memtx_tree_data_common { /* Tuple that this node is represents. */ struct tuple *tuple; +}; + +template +struct memtx_tree_data; + +template <> +struct memtx_tree_data : memtx_tree_data_common { + static constexpr hint_t hint = HINT_NONE; + void set_hint(hint_t) { assert(false); } +}; + +template <> +struct memtx_tree_data : memtx_tree_data { /** Comparison hint, see key_hint(). */ hint_t hint; + void set_hint(hint_t h) { hint = h; } }; /** @@ -73,8 +101,8 @@ struct memtx_tree_data { * @retval false - Otherwise. */ static bool -memtx_tree_data_is_equal(const struct memtx_tree_data *a, - const struct memtx_tree_data *b) +memtx_tree_data_is_equal(const struct memtx_tree_data_common *a, + const struct memtx_tree_data_common *b) { return a->tuple == b->tuple; } @@ -89,12 +117,28 @@ memtx_tree_data_is_equal(const struct memtx_tree_data *a, (b)->part_count, (b)->hint, arg) #define BPS_TREE_IS_IDENTICAL(a, b) memtx_tree_data_is_equal(&a, &b) #define BPS_TREE_NO_DEBUG 1 -#define bps_tree_elem_t struct memtx_tree_data -#define bps_tree_key_t struct memtx_tree_key_data * #define bps_tree_arg_t struct key_def * +#define BPS_TREE_NAMESPACE NS_NO_HINT +#define bps_tree_elem_t struct memtx_tree_data +#define bps_tree_key_t struct memtx_tree_key_data * + #include "salad/bps_tree.h" +#undef BPS_TREE_NAMESPACE +#undef bps_tree_elem_t +#undef bps_tree_key_t + +#define BPS_TREE_NAMESPACE NS_USE_HINT +#define bps_tree_elem_t struct memtx_tree_data +#define bps_tree_key_t struct memtx_tree_key_data * + +#include "salad/bps_tree.h" + +#undef BPS_TREE_NAMESPACE +#undef bps_tree_elem_t +#undef bps_tree_key_t + #undef BPS_TREE_NAME #undef BPS_TREE_BLOCK_SIZE #undef BPS_TREE_EXTENT_SIZE @@ -102,66 +146,119 @@ memtx_tree_data_is_equal(const struct memtx_tree_data *a, #undef BPS_TREE_COMPARE_KEY #undef BPS_TREE_IS_IDENTICAL #undef BPS_TREE_NO_DEBUG -#undef bps_tree_elem_t -#undef bps_tree_key_t #undef bps_tree_arg_t +using namespace NS_NO_HINT; +using namespace NS_USE_HINT; + +template +struct memtx_tree_selector; + +template <> +struct memtx_tree_selector : NS_NO_HINT::memtx_tree {}; + +template <> +struct memtx_tree_selector : NS_USE_HINT::memtx_tree {}; + +template +using memtx_tree_t = struct memtx_tree_selector; + +template +struct memtx_tree_iterator_selector; + +template <> +struct memtx_tree_iterator_selector { + using type = NS_NO_HINT::memtx_tree_iterator; +}; + +template <> +struct memtx_tree_iterator_selector { + using type = NS_USE_HINT::memtx_tree_iterator; +}; + +template +using memtx_tree_iterator_t = typename memtx_tree_iterator_selector::type; + +static void +invalidate_tree_iterator(NS_NO_HINT::memtx_tree_iterator *itr) +{ + *itr = NS_NO_HINT::memtx_tree_invalid_iterator(); +} + +static void +invalidate_tree_iterator(NS_USE_HINT::memtx_tree_iterator *itr) +{ + *itr = NS_USE_HINT::memtx_tree_invalid_iterator(); +} + +template struct memtx_tree_index { struct index base; - struct memtx_tree tree; - struct memtx_tree_data *build_array; + memtx_tree_t tree; + struct memtx_tree_data *build_array; size_t build_array_size, build_array_alloc_size; struct memtx_gc_task gc_task; - struct memtx_tree_iterator gc_iterator; + memtx_tree_iterator_t gc_iterator; }; /* {{{ Utilities. *************************************************/ +template static inline struct key_def * -memtx_tree_cmp_def(struct memtx_tree *tree) +memtx_tree_cmp_def(TREE *tree) { return tree->arg; } +template static int memtx_tree_qcompare(const void* a, const void *b, void *c) { - const struct memtx_tree_data *data_a = (struct memtx_tree_data *)a; - const struct memtx_tree_data *data_b = (struct memtx_tree_data *)b; + const struct memtx_tree_data *data_a = + (struct memtx_tree_data *)a; + const struct memtx_tree_data *data_b = + (struct memtx_tree_data *)b; struct key_def *key_def = (struct key_def *)c; return tuple_compare(data_a->tuple, data_a->hint, data_b->tuple, data_b->hint, key_def); } /* {{{ MemtxTree Iterators ****************************************/ +template struct tree_iterator { struct iterator base; - struct memtx_tree_iterator tree_iterator; + memtx_tree_iterator_t tree_iterator; enum iterator_type type; - struct memtx_tree_key_data key_data; - struct memtx_tree_data current; + struct memtx_tree_key_data key_data; + struct memtx_tree_data current; /** Memory pool the iterator was allocated from. */ struct mempool *pool; }; -static_assert(sizeof(struct tree_iterator) <= MEMTX_ITERATOR_SIZE, - "sizeof(struct tree_iterator) must be less than or equal " +static_assert(sizeof(struct tree_iterator) <= MEMTX_ITERATOR_SIZE, + "sizeof(struct tree_iterator) must be less than or equal " + "to MEMTX_ITERATOR_SIZE"); +static_assert(sizeof(struct tree_iterator) <= MEMTX_ITERATOR_SIZE, + "sizeof(struct tree_iterator) must be less than or equal " "to MEMTX_ITERATOR_SIZE"); +template static void tree_iterator_free(struct iterator *iterator); -static inline struct tree_iterator * -tree_iterator(struct iterator *it) +template +static inline struct tree_iterator * +get_tree_iterator(struct iterator *it) { - assert(it->free == tree_iterator_free); - return (struct tree_iterator *) it; + assert(it->free == &tree_iterator_free); + return (struct tree_iterator *) it; } +template static void tree_iterator_free(struct iterator *iterator) { - struct tree_iterator *it = tree_iterator(iterator); + struct tree_iterator *it = get_tree_iterator(iterator); struct tuple *tuple = it->current.tuple; if (tuple != NULL) tuple_unref(tuple); @@ -176,14 +273,15 @@ tree_iterator_dummie(struct iterator *iterator, struct tuple **ret) return 0; } +template static int tree_iterator_next_base(struct iterator *iterator, struct tuple **ret) { - struct memtx_tree_index *index = - (struct memtx_tree_index *)iterator->index; - struct tree_iterator *it = tree_iterator(iterator); + struct memtx_tree_index *index = + (struct memtx_tree_index *)iterator->index; + struct tree_iterator *it = get_tree_iterator(iterator); assert(it->current.tuple != NULL); - struct memtx_tree_data *check = + struct memtx_tree_data *check = memtx_tree_iterator_get_elem(&index->tree, &it->tree_iterator); if (check == NULL || !memtx_tree_data_is_equal(check, &it->current)) { it->tree_iterator = memtx_tree_upper_bound_elem(&index->tree, @@ -192,7 +290,7 @@ tree_iterator_next_base(struct iterator *iterator, struct tuple **ret) memtx_tree_iterator_next(&index->tree, &it->tree_iterator); } tuple_unref(it->current.tuple); - struct memtx_tree_data *res = + struct memtx_tree_data *res = memtx_tree_iterator_get_elem(&index->tree, &it->tree_iterator); if (res == NULL) { iterator->next = tree_iterator_dummie; @@ -206,14 +304,15 @@ tree_iterator_next_base(struct iterator *iterator, struct tuple **ret) return 0; } +template static int tree_iterator_prev_base(struct iterator *iterator, struct tuple **ret) { - struct memtx_tree_index *index = - (struct memtx_tree_index *)iterator->index; - struct tree_iterator *it = tree_iterator(iterator); + struct memtx_tree_index *index = + (struct memtx_tree_index *)iterator->index; + struct tree_iterator *it = get_tree_iterator(iterator); assert(it->current.tuple != NULL); - struct memtx_tree_data *check = + struct memtx_tree_data *check = memtx_tree_iterator_get_elem(&index->tree, &it->tree_iterator); if (check == NULL || !memtx_tree_data_is_equal(check, &it->current)) { it->tree_iterator = memtx_tree_lower_bound_elem(&index->tree, @@ -221,7 +320,7 @@ tree_iterator_prev_base(struct iterator *iterator, struct tuple **ret) } memtx_tree_iterator_prev(&index->tree, &it->tree_iterator); tuple_unref(it->current.tuple); - struct memtx_tree_data *res = + struct memtx_tree_data *res = memtx_tree_iterator_get_elem(&index->tree, &it->tree_iterator); if (!res) { iterator->next = tree_iterator_dummie; @@ -235,14 +334,15 @@ tree_iterator_prev_base(struct iterator *iterator, struct tuple **ret) return 0; } +template static int tree_iterator_next_equal_base(struct iterator *iterator, struct tuple **ret) { - struct memtx_tree_index *index = - (struct memtx_tree_index *)iterator->index; - struct tree_iterator *it = tree_iterator(iterator); + struct memtx_tree_index *index = + (struct memtx_tree_index *)iterator->index; + struct tree_iterator *it = get_tree_iterator(iterator); assert(it->current.tuple != NULL); - struct memtx_tree_data *check = + struct memtx_tree_data *check = memtx_tree_iterator_get_elem(&index->tree, &it->tree_iterator); if (check == NULL || !memtx_tree_data_is_equal(check, &it->current)) { it->tree_iterator = memtx_tree_upper_bound_elem(&index->tree, @@ -251,7 +351,7 @@ tree_iterator_next_equal_base(struct iterator *iterator, struct tuple **ret) memtx_tree_iterator_next(&index->tree, &it->tree_iterator); } tuple_unref(it->current.tuple); - struct memtx_tree_data *res = + struct memtx_tree_data *res = memtx_tree_iterator_get_elem(&index->tree, &it->tree_iterator); /* Use user key def to save a few loops. */ if (res == NULL || @@ -271,14 +371,15 @@ tree_iterator_next_equal_base(struct iterator *iterator, struct tuple **ret) return 0; } +template static int tree_iterator_prev_equal_base(struct iterator *iterator, struct tuple **ret) { - struct memtx_tree_index *index = - (struct memtx_tree_index *)iterator->index; - struct tree_iterator *it = tree_iterator(iterator); + struct memtx_tree_index *index = + (struct memtx_tree_index *)iterator->index; + struct tree_iterator *it = get_tree_iterator(iterator); assert(it->current.tuple != NULL); - struct memtx_tree_data *check = + struct memtx_tree_data *check = memtx_tree_iterator_get_elem(&index->tree, &it->tree_iterator); if (check == NULL || !memtx_tree_data_is_equal(check, &it->current)) { it->tree_iterator = memtx_tree_lower_bound_elem(&index->tree, @@ -286,7 +387,7 @@ tree_iterator_prev_equal_base(struct iterator *iterator, struct tuple **ret) } memtx_tree_iterator_prev(&index->tree, &it->tree_iterator); tuple_unref(it->current.tuple); - struct memtx_tree_data *res = + struct memtx_tree_data *res = memtx_tree_iterator_get_elem(&index->tree, &it->tree_iterator); /* Use user key def to save a few loops. */ if (res == NULL || @@ -307,28 +408,30 @@ tree_iterator_prev_equal_base(struct iterator *iterator, struct tuple **ret) } #define WRAP_ITERATOR_METHOD(name) \ +template \ static int \ name(struct iterator *iterator, struct tuple **ret) \ { \ - struct memtx_tree *tree = \ - &((struct memtx_tree_index *)iterator->index)->tree; \ - struct tree_iterator *it = tree_iterator(iterator); \ - struct memtx_tree_iterator *ti = &it->tree_iterator; \ + memtx_tree_t *tree = \ + &((struct memtx_tree_index *)iterator->index)->tree; \ + struct tree_iterator *it = \ + get_tree_iterator(iterator); \ + memtx_tree_iterator_t *ti = &it->tree_iterator; \ uint32_t iid = iterator->index->def->iid; \ bool is_multikey = iterator->index->def->key_def->is_multikey; \ struct txn *txn = in_txn(); \ struct space *space = space_by_id(iterator->space_id); \ bool is_rw = txn != NULL; \ do { \ - int rc = name##_base(iterator, ret); \ + int rc = name##_base(iterator, ret); \ if (rc != 0 || *ret == NULL) \ return rc; \ uint32_t mk_index = 0; \ if (is_multikey) { \ - struct memtx_tree_data *check = \ + struct memtx_tree_data *check = \ memtx_tree_iterator_get_elem(tree, ti); \ assert(check != NULL); \ - mk_index = check->hint; \ + mk_index = (uint32_t)check->hint; \ } \ *ret = memtx_tx_tuple_clarify(txn, space, *ret, \ iid, mk_index, is_rw); \ @@ -347,27 +450,28 @@ WRAP_ITERATOR_METHOD(tree_iterator_prev_equal); #undef WRAP_ITERATOR_METHOD +template static void -tree_iterator_set_next_method(struct tree_iterator *it) +tree_iterator_set_next_method(struct tree_iterator *it) { assert(it->current.tuple != NULL); switch (it->type) { case ITER_EQ: - it->base.next = tree_iterator_next_equal; + it->base.next = tree_iterator_next_equal; break; case ITER_REQ: - it->base.next = tree_iterator_prev_equal; + it->base.next = tree_iterator_prev_equal; break; case ITER_ALL: - it->base.next = tree_iterator_next; + it->base.next = tree_iterator_next; break; case ITER_LT: case ITER_LE: - it->base.next = tree_iterator_prev; + it->base.next = tree_iterator_prev; break; case ITER_GE: case ITER_GT: - it->base.next = tree_iterator_next; + it->base.next = tree_iterator_next; break; default: /* The type was checked in initIterator */ @@ -375,15 +479,16 @@ tree_iterator_set_next_method(struct tree_iterator *it) } } +template static int tree_iterator_start(struct iterator *iterator, struct tuple **ret) { *ret = NULL; - struct memtx_tree_index *index = - (struct memtx_tree_index *)iterator->index; - struct tree_iterator *it = tree_iterator(iterator); + struct memtx_tree_index *index = + (struct memtx_tree_index *)iterator->index; + struct tree_iterator *it = get_tree_iterator(iterator); it->base.next = tree_iterator_dummie; - struct memtx_tree *tree = &index->tree; + memtx_tree_t *tree = &index->tree; enum iterator_type type = it->type; bool exact = false; assert(it->current.tuple == NULL); @@ -423,8 +528,8 @@ tree_iterator_start(struct iterator *iterator, struct tuple **ret) } } - struct memtx_tree_data *res = memtx_tree_iterator_get_elem(tree, - &it->tree_iterator); + struct memtx_tree_data *res = + memtx_tree_iterator_get_elem(tree, &it->tree_iterator); if (!res) return 0; *ret = res->tuple; @@ -437,7 +542,7 @@ tree_iterator_start(struct iterator *iterator, struct tuple **ret) struct txn *txn = in_txn(); struct space *space = space_by_id(iterator->space_id); bool is_rw = txn != NULL; - uint32_t mk_index = is_multikey ? res->hint : 0; + uint32_t mk_index = is_multikey ? (uint32_t)res->hint : 0; *ret = memtx_tx_tuple_clarify(txn, space, *ret, iid, mk_index, is_rw); if (*ret == NULL) { return iterator->next(iterator, ret); @@ -454,14 +559,16 @@ tree_iterator_start(struct iterator *iterator, struct tuple **ret) /* {{{ MemtxTree **********************************************************/ +template static void -memtx_tree_index_free(struct memtx_tree_index *index) +memtx_tree_index_free(struct memtx_tree_index *index) { memtx_tree_destroy(&index->tree); free(index->build_array); free(index); } +template static void memtx_tree_index_gc_run(struct memtx_gc_task *task, bool *done) { @@ -475,14 +582,14 @@ memtx_tree_index_gc_run(struct memtx_gc_task *task, bool *done) enum { YIELD_LOOPS = 10 }; #endif - struct memtx_tree_index *index = container_of(task, - struct memtx_tree_index, gc_task); - struct memtx_tree *tree = &index->tree; - struct memtx_tree_iterator *itr = &index->gc_iterator; + struct memtx_tree_index *index = container_of(task, + struct memtx_tree_index, gc_task); + memtx_tree_t *tree = &index->tree; + memtx_tree_iterator_t *itr = &index->gc_iterator; unsigned int loops = 0; while (!memtx_tree_iterator_is_invalid(itr)) { - struct memtx_tree_data *res = + struct memtx_tree_data *res = memtx_tree_iterator_get_elem(tree, itr); memtx_tree_iterator_next(tree, itr); tuple_unref(res->tuple); @@ -494,23 +601,32 @@ memtx_tree_index_gc_run(struct memtx_gc_task *task, bool *done) *done = true; } +template static void memtx_tree_index_gc_free(struct memtx_gc_task *task) { - struct memtx_tree_index *index = container_of(task, - struct memtx_tree_index, gc_task); + struct memtx_tree_index *index = container_of(task, + struct memtx_tree_index, gc_task); memtx_tree_index_free(index); } -static const struct memtx_gc_task_vtab memtx_tree_index_gc_vtab = { - .run = memtx_tree_index_gc_run, - .free = memtx_tree_index_gc_free, +template +static struct memtx_gc_task_vtab * get_memtx_tree_index_gc_vtab() +{ + static memtx_gc_task_vtab tab = + { + .run = memtx_tree_index_gc_run, + .free = memtx_tree_index_gc_free, + }; + return &tab; }; +template static void memtx_tree_index_destroy(struct index *base) { - struct memtx_tree_index *index = (struct memtx_tree_index *)base; + struct memtx_tree_index *index = + (struct memtx_tree_index *)base; struct memtx_engine *memtx = (struct memtx_engine *)base->engine; if (base->def->iid == 0) { /* @@ -518,7 +634,7 @@ memtx_tree_index_destroy(struct index *base) * in the index, which may take a while. Schedule a * background task in order not to block tx thread. */ - index->gc_task.vtab = &memtx_tree_index_gc_vtab; + index->gc_task.vtab = get_memtx_tree_index_gc_vtab(); index->gc_iterator = memtx_tree_iterator_first(&index->tree); memtx_engine_schedule_gc(memtx, &index->gc_task); } else { @@ -530,10 +646,12 @@ memtx_tree_index_destroy(struct index *base) } } +template static void memtx_tree_index_update_def(struct index *base) { - struct memtx_tree_index *index = (struct memtx_tree_index *)base; + struct memtx_tree_index *index = + (struct memtx_tree_index *)base; struct index_def *def = base->def; /* * We use extended key def for non-unique and nullable @@ -553,51 +671,62 @@ memtx_tree_index_depends_on_pk(struct index *base) return !def->opts.is_unique || def->key_def->is_nullable; } +template static ssize_t memtx_tree_index_size(struct index *base) { - struct memtx_tree_index *index = (struct memtx_tree_index *)base; + struct memtx_tree_index *index = + (struct memtx_tree_index *)base; return memtx_tree_size(&index->tree); } +template static ssize_t memtx_tree_index_bsize(struct index *base) { - struct memtx_tree_index *index = (struct memtx_tree_index *)base; + struct memtx_tree_index *index = + (struct memtx_tree_index *)base; return memtx_tree_mem_used(&index->tree); } +template 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 memtx_tree_data *res = memtx_tree_random(&index->tree, rnd); + struct memtx_tree_index *index = + (struct memtx_tree_index *)base; + struct memtx_tree_data *res = memtx_tree_random(&index->tree, rnd); *result = res != NULL ? res->tuple : NULL; return 0; } +template static ssize_t memtx_tree_index_count(struct index *base, enum iterator_type type, const char *key, uint32_t part_count) { if (type == ITER_ALL) - return memtx_tree_index_size(base); /* optimization */ + return memtx_tree_index_size(base); /* optimization */ return generic_index_count(base, type, key, part_count); } +template static int memtx_tree_index_get(struct index *base, const char *key, uint32_t part_count, struct tuple **result) { 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_index *index = + (struct memtx_tree_index *)base; struct key_def *cmp_def = memtx_tree_cmp_def(&index->tree); - struct memtx_tree_key_data key_data; + struct memtx_tree_key_data key_data; key_data.key = key; key_data.part_count = part_count; - key_data.hint = key_hint(key, part_count, cmp_def); - struct memtx_tree_data *res = memtx_tree_find(&index->tree, &key_data); + if (USE_HINT) + key_data.set_hint(key_hint(key, part_count, cmp_def)); + struct memtx_tree_data *res = + memtx_tree_find(&index->tree, &key_data); if (res == NULL) { *result = NULL; return 0; @@ -605,24 +734,28 @@ memtx_tree_index_get(struct index *base, const char *key, struct txn *txn = in_txn(); struct space *space = space_by_id(base->def->space_id); bool is_rw = txn != NULL; - uint32_t mk_index = base->def->key_def->is_multikey ? res->hint : 0; + bool is_multikey = base->def->key_def->is_multikey; + uint32_t mk_index = is_multikey ? (uint32_t)res->hint : 0; *result = memtx_tx_tuple_clarify(txn, space, res->tuple, base->def->iid, mk_index, is_rw); return 0; } +template 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; + struct memtx_tree_index *index = + (struct memtx_tree_index *)base; struct key_def *cmp_def = memtx_tree_cmp_def(&index->tree); if (new_tuple) { - struct memtx_tree_data new_data; + struct memtx_tree_data new_data; new_data.tuple = new_tuple; - new_data.hint = tuple_hint(new_tuple, cmp_def); - struct memtx_tree_data dup_data; + if (USE_HINT) + new_data.set_hint(tuple_hint(new_tuple, cmp_def)); + struct memtx_tree_data dup_data; dup_data.tuple = NULL; /* Try to optimistically replace the new_tuple. */ @@ -652,9 +785,10 @@ memtx_tree_index_replace(struct index *base, struct tuple *old_tuple, } } if (old_tuple) { - struct memtx_tree_data old_data; + struct memtx_tree_data old_data; old_data.tuple = old_tuple; - old_data.hint = tuple_hint(old_tuple, cmp_def); + if (USE_HINT) + old_data.set_hint(tuple_hint(old_tuple, cmp_def)); memtx_tree_delete(&index->tree, old_data); } *result = old_tuple; @@ -667,13 +801,13 @@ memtx_tree_index_replace(struct index *base, struct tuple *old_tuple, * by all it's multikey indexes. */ static int -memtx_tree_index_replace_multikey_one(struct memtx_tree_index *index, +memtx_tree_index_replace_multikey_one(struct memtx_tree_index *index, struct tuple *old_tuple, struct tuple *new_tuple, enum dup_replace_mode mode, hint_t hint, - struct memtx_tree_data *replaced_data, + struct memtx_tree_data *replaced_data, bool *is_multikey_conflict) { - struct memtx_tree_data new_data, dup_data; + struct memtx_tree_data new_data, dup_data; new_data.tuple = new_tuple; new_data.hint = hint; dup_data.tuple = NULL; @@ -720,11 +854,11 @@ memtx_tree_index_replace_multikey_one(struct memtx_tree_index *index, * delete operation is fault-tolerant. */ static void -memtx_tree_index_replace_multikey_rollback(struct memtx_tree_index *index, +memtx_tree_index_replace_multikey_rollback(struct memtx_tree_index *index, struct tuple *new_tuple, struct tuple *replaced_tuple, int err_multikey_idx) { - struct memtx_tree_data data; + struct memtx_tree_data data; if (replaced_tuple != NULL) { /* Restore replaced tuple index occurrences. */ struct key_def *cmp_def = memtx_tree_cmp_def(&index->tree); @@ -798,7 +932,8 @@ memtx_tree_index_replace_multikey(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; + struct memtx_tree_index *index = + (struct memtx_tree_index *)base; struct key_def *cmp_def = memtx_tree_cmp_def(&index->tree); *result = NULL; if (new_tuple != NULL) { @@ -808,7 +943,7 @@ memtx_tree_index_replace_multikey(struct index *base, struct tuple *old_tuple, for (; (uint32_t) multikey_idx < multikey_count; multikey_idx++) { bool is_multikey_conflict; - struct memtx_tree_data replaced_data; + struct memtx_tree_data replaced_data; err = memtx_tree_index_replace_multikey_one(index, old_tuple, new_tuple, mode, multikey_idx, &replaced_data, @@ -833,7 +968,7 @@ memtx_tree_index_replace_multikey(struct index *base, struct tuple *old_tuple, } } if (old_tuple != NULL) { - struct memtx_tree_data data; + struct memtx_tree_data data; data.tuple = old_tuple; uint32_t multikey_count = tuple_multikey_count(old_tuple, cmp_def); @@ -865,7 +1000,7 @@ struct func_key_undo { /** A link to organize entries in list. */ struct rlist link; /** An inserted record copy. */ - struct memtx_tree_data key; + struct memtx_tree_data key; }; /** Allocate a new func_key_undo on given region. */ @@ -888,7 +1023,7 @@ func_key_undo_new(struct region *region) * return a given index object in it's original state. */ static void -memtx_tree_func_index_replace_rollback(struct memtx_tree_index *index, +memtx_tree_func_index_replace_rollback(struct memtx_tree_index *index, struct rlist *old_keys, struct rlist *new_keys) { @@ -919,7 +1054,8 @@ memtx_tree_func_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; + struct memtx_tree_index *index = + (struct memtx_tree_index *)base; struct index_def *index_def = index->base.def; assert(index_def->key_def->for_func_index); @@ -952,7 +1088,7 @@ memtx_tree_func_index_replace(struct index *base, struct tuple *old_tuple, undo->key.hint = (hint_t)key; rlist_add(&new_keys, &undo->link); bool is_multikey_conflict; - struct memtx_tree_data old_data; + struct memtx_tree_data old_data; old_data.tuple = NULL; err = memtx_tree_index_replace_multikey_one(index, old_tuple, new_tuple, @@ -1015,7 +1151,7 @@ memtx_tree_func_index_replace(struct index *base, struct tuple *old_tuple, if (key_list_iterator_create(&it, old_tuple, index_def, false, func_index_key_dummy_alloc) != 0) goto end; - struct memtx_tree_data data, deleted_data; + struct memtx_tree_data data, deleted_data; data.tuple = old_tuple; const char *key; while (key_list_iterator_next(&it, &key) == 0 && key != NULL) { @@ -1040,11 +1176,13 @@ end: return rc; } +template static struct iterator * memtx_tree_index_create_iterator(struct index *base, enum iterator_type type, const char *key, uint32_t part_count) { - struct memtx_tree_index *index = (struct memtx_tree_index *)base; + struct memtx_tree_index *index = + (struct memtx_tree_index *)base; struct memtx_engine *memtx = (struct memtx_engine *)base->engine; struct key_def *cmp_def = memtx_tree_cmp_def(&index->tree); @@ -1064,42 +1202,47 @@ memtx_tree_index_create_iterator(struct index *base, enum iterator_type type, key = NULL; } - struct tree_iterator *it = (struct tree_iterator *) + struct tree_iterator *it = (struct tree_iterator *) mempool_alloc(&memtx->iterator_pool); if (it == NULL) { - diag_set(OutOfMemory, sizeof(struct tree_iterator), + diag_set(OutOfMemory, sizeof(struct tree_iterator), "memtx_tree_index", "iterator"); return NULL; } iterator_create(&it->base, base); it->pool = &memtx->iterator_pool; - it->base.next = tree_iterator_start; - it->base.free = tree_iterator_free; + 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; - it->key_data.hint = key_hint(key, part_count, cmp_def); - it->tree_iterator = memtx_tree_invalid_iterator(); + if (USE_HINT) + it->key_data.set_hint(key_hint(key, part_count, cmp_def)); + invalidate_tree_iterator(&it->tree_iterator); it->current.tuple = NULL; return (struct iterator *)it; } +template static void memtx_tree_index_begin_build(struct index *base) { - struct memtx_tree_index *index = (struct memtx_tree_index *)base; + struct memtx_tree_index *index = + (struct memtx_tree_index *)base; assert(memtx_tree_size(&index->tree) == 0); (void)index; } +template static int memtx_tree_index_reserve(struct index *base, uint32_t size_hint) { - struct memtx_tree_index *index = (struct memtx_tree_index *)base; + struct memtx_tree_index *index = + (struct memtx_tree_index *)base; if (size_hint < index->build_array_alloc_size) return 0; - struct memtx_tree_data *tmp = - (struct memtx_tree_data *) + struct memtx_tree_data *tmp = + (struct memtx_tree_data *) realloc(index->build_array, size_hint * sizeof(*tmp)); if (tmp == NULL) { diag_set(OutOfMemory, size_hint * sizeof(*tmp), @@ -1111,14 +1254,15 @@ memtx_tree_index_reserve(struct index *base, uint32_t size_hint) return 0; } +template /** Initialize the next element of the index build_array. */ static int -memtx_tree_index_build_array_append(struct memtx_tree_index *index, +memtx_tree_index_build_array_append(struct memtx_tree_index *index, struct tuple *tuple, hint_t hint) { if (index->build_array == NULL) { index->build_array = - (struct memtx_tree_data *)malloc(MEMTX_EXTENT_SIZE); + (struct memtx_tree_data *)malloc(MEMTX_EXTENT_SIZE); if (index->build_array == NULL) { diag_set(OutOfMemory, MEMTX_EXTENT_SIZE, "memtx_tree_index", "build_next"); @@ -1131,8 +1275,8 @@ memtx_tree_index_build_array_append(struct memtx_tree_index *index, if (index->build_array_size == index->build_array_alloc_size) { index->build_array_alloc_size = index->build_array_alloc_size + DIV_ROUND_UP(index->build_array_alloc_size, 2); - struct memtx_tree_data *tmp = - (struct memtx_tree_data *)realloc(index->build_array, + struct memtx_tree_data *tmp = + (struct memtx_tree_data *)realloc(index->build_array, index->build_array_alloc_size * sizeof(*tmp)); if (tmp == NULL) { diag_set(OutOfMemory, index->build_array_alloc_size * @@ -1141,17 +1285,20 @@ memtx_tree_index_build_array_append(struct memtx_tree_index *index, } index->build_array = tmp; } - struct memtx_tree_data *elem = + struct memtx_tree_data *elem = &index->build_array[index->build_array_size++]; elem->tuple = tuple; - elem->hint = hint; + if (USE_HINT) + elem->set_hint(hint); return 0; } +template static int memtx_tree_index_build_next(struct index *base, struct tuple *tuple) { - struct memtx_tree_index *index = (struct memtx_tree_index *)base; + struct memtx_tree_index *index = + (struct memtx_tree_index *)base; struct key_def *cmp_def = memtx_tree_cmp_def(&index->tree); return memtx_tree_index_build_array_append(index, tuple, tuple_hint(tuple, cmp_def)); @@ -1160,7 +1307,7 @@ memtx_tree_index_build_next(struct index *base, struct tuple *tuple) static int memtx_tree_index_build_next_multikey(struct index *base, struct tuple *tuple) { - struct memtx_tree_index *index = (struct memtx_tree_index *)base; + struct memtx_tree_index *index = (struct memtx_tree_index *)base; struct key_def *cmp_def = memtx_tree_cmp_def(&index->tree); uint32_t multikey_count = tuple_multikey_count(tuple, cmp_def); for (uint32_t multikey_idx = 0; multikey_idx < multikey_count; @@ -1175,7 +1322,7 @@ memtx_tree_index_build_next_multikey(struct index *base, struct tuple *tuple) static int memtx_tree_func_index_build_next(struct index *base, struct tuple *tuple) { - struct memtx_tree_index *index = (struct memtx_tree_index *)base; + struct memtx_tree_index *index = (struct memtx_tree_index *)base; struct index_def *index_def = index->base.def; assert(index_def->key_def->for_func_index); @@ -1211,8 +1358,9 @@ error: * of equal tuples (in terms of index's cmp_def and have same * tuple pointer). The build_array is expected to be sorted. */ +template static void -memtx_tree_index_build_array_deduplicate(struct memtx_tree_index *index, +memtx_tree_index_build_array_deduplicate(struct memtx_tree_index *index, void (*destroy)(struct tuple *tuple, const char *hint)) { if (index->build_array_size == 0) @@ -1246,13 +1394,16 @@ memtx_tree_index_build_array_deduplicate(struct memtx_tree_index *index, index->build_array_size = w_idx + 1; } +template static void memtx_tree_index_end_build(struct index *base) { - struct memtx_tree_index *index = (struct memtx_tree_index *)base; + struct memtx_tree_index *index = + (struct memtx_tree_index *)base; struct key_def *cmp_def = memtx_tree_cmp_def(&index->tree); qsort_arg(index->build_array, index->build_array_size, - sizeof(index->build_array[0]), memtx_tree_qcompare, cmp_def); + sizeof(index->build_array[0]), + memtx_tree_qcompare, cmp_def); if (cmp_def->is_multikey) { /* * Multikey index may have equal(in terms of @@ -1261,9 +1412,9 @@ memtx_tree_index_end_build(struct index *base) * the following memtx_tree_build assumes that * all keys are unique. */ - memtx_tree_index_build_array_deduplicate(index, NULL); + memtx_tree_index_build_array_deduplicate(index, NULL); } else if (cmp_def->for_func_index) { - memtx_tree_index_build_array_deduplicate(index, + memtx_tree_index_build_array_deduplicate(index, tuple_chunk_delete); } memtx_tree_build(&index->tree, index->build_array, @@ -1275,19 +1426,21 @@ memtx_tree_index_end_build(struct index *base) index->build_array_alloc_size = 0; } +template struct tree_snapshot_iterator { struct snapshot_iterator base; - struct memtx_tree_index *index; - struct memtx_tree_iterator tree_iterator; + struct memtx_tree_index *index; + memtx_tree_iterator_t tree_iterator; struct memtx_tx_snapshot_cleaner cleaner; }; +template static void tree_snapshot_iterator_free(struct snapshot_iterator *iterator) { - assert(iterator->free == tree_snapshot_iterator_free); - struct tree_snapshot_iterator *it = - (struct tree_snapshot_iterator *)iterator; + assert(iterator->free == &tree_snapshot_iterator_free); + struct tree_snapshot_iterator *it = + (struct tree_snapshot_iterator *)iterator; memtx_leave_delayed_free_mode((struct memtx_engine *) it->index->base.engine); memtx_tree_iterator_destroy(&it->index->tree, &it->tree_iterator); @@ -1296,17 +1449,18 @@ tree_snapshot_iterator_free(struct snapshot_iterator *iterator) free(iterator); } +template static int tree_snapshot_iterator_next(struct snapshot_iterator *iterator, const char **data, uint32_t *size) { - assert(iterator->free == tree_snapshot_iterator_free); - struct tree_snapshot_iterator *it = - (struct tree_snapshot_iterator *)iterator; - struct memtx_tree *tree = &it->index->tree; + assert(iterator->free == &tree_snapshot_iterator_free); + struct tree_snapshot_iterator *it = + (struct tree_snapshot_iterator *)iterator; + memtx_tree_t *tree = &it->index->tree; while (true) { - struct memtx_tree_data *res = + struct memtx_tree_data *res = memtx_tree_iterator_get_elem(tree, &it->tree_iterator); if (res == NULL) { @@ -1333,14 +1487,18 @@ tree_snapshot_iterator_next(struct snapshot_iterator *iterator, * index modifications will not affect the iteration results. * Must be destroyed by iterator->free after usage. */ +template static struct snapshot_iterator * memtx_tree_index_create_snapshot_iterator(struct index *base) { - struct memtx_tree_index *index = (struct memtx_tree_index *)base; - struct tree_snapshot_iterator *it = - (struct tree_snapshot_iterator *) calloc(1, sizeof(*it)); + struct memtx_tree_index *index = + (struct memtx_tree_index *)base; + struct tree_snapshot_iterator *it = + (struct tree_snapshot_iterator *) + calloc(1, sizeof(*it)); if (it == NULL) { - diag_set(OutOfMemory, sizeof(struct tree_snapshot_iterator), + diag_set(OutOfMemory, + sizeof(struct tree_snapshot_iterator), "memtx_tree_index", "create_snapshot_iterator"); return NULL; } @@ -1352,8 +1510,8 @@ memtx_tree_index_create_snapshot_iterator(struct index *base) return NULL; } - it->base.free = tree_snapshot_iterator_free; - it->base.next = tree_snapshot_iterator_next; + it->base.free = tree_snapshot_iterator_free; + it->base.next = tree_snapshot_iterator_next; it->index = index; index_ref(base); it->tree_iterator = memtx_tree_iterator_first(&index->tree); @@ -1362,94 +1520,124 @@ memtx_tree_index_create_snapshot_iterator(struct index *base) return (struct snapshot_iterator *) it; } -static const struct index_vtab memtx_tree_index_vtab = { - /* .destroy = */ memtx_tree_index_destroy, +static const struct index_vtab memtx_tree_no_hint_index_vtab = { + /* .destroy = */ memtx_tree_index_destroy, /* .commit_create = */ generic_index_commit_create, /* .abort_create = */ generic_index_abort_create, /* .commit_modify = */ generic_index_commit_modify, /* .commit_drop = */ generic_index_commit_drop, - /* .update_def = */ memtx_tree_index_update_def, + /* .update_def = */ memtx_tree_index_update_def, /* .depends_on_pk = */ memtx_tree_index_depends_on_pk, /* .def_change_requires_rebuild = */ memtx_index_def_change_requires_rebuild, - /* .size = */ memtx_tree_index_size, - /* .bsize = */ memtx_tree_index_bsize, + /* .size = */ memtx_tree_index_size, + /* .bsize = */ memtx_tree_index_bsize, /* .min = */ generic_index_min, /* .max = */ generic_index_max, - /* .random = */ memtx_tree_index_random, - /* .count = */ memtx_tree_index_count, - /* .get = */ memtx_tree_index_get, - /* .replace = */ memtx_tree_index_replace, - /* .create_iterator = */ memtx_tree_index_create_iterator, + /* .random = */ memtx_tree_index_random, + /* .count = */ memtx_tree_index_count, + /* .get = */ memtx_tree_index_get, + /* .replace = */ memtx_tree_index_replace, + /* .create_iterator = */ memtx_tree_index_create_iterator, /* .create_snapshot_iterator = */ - memtx_tree_index_create_snapshot_iterator, + memtx_tree_index_create_snapshot_iterator, /* .stat = */ generic_index_stat, /* .compact = */ generic_index_compact, /* .reset_stat = */ generic_index_reset_stat, - /* .begin_build = */ memtx_tree_index_begin_build, - /* .reserve = */ memtx_tree_index_reserve, - /* .build_next = */ memtx_tree_index_build_next, - /* .end_build = */ memtx_tree_index_end_build, + /* .begin_build = */ memtx_tree_index_begin_build, + /* .reserve = */ memtx_tree_index_reserve, + /* .build_next = */ memtx_tree_index_build_next, + /* .end_build = */ memtx_tree_index_end_build, +}; + +static const struct index_vtab memtx_tree_use_hint_index_vtab = { + /* .destroy = */ memtx_tree_index_destroy, + /* .commit_create = */ generic_index_commit_create, + /* .abort_create = */ generic_index_abort_create, + /* .commit_modify = */ generic_index_commit_modify, + /* .commit_drop = */ generic_index_commit_drop, + /* .update_def = */ memtx_tree_index_update_def, + /* .depends_on_pk = */ memtx_tree_index_depends_on_pk, + /* .def_change_requires_rebuild = */ + memtx_index_def_change_requires_rebuild, + /* .size = */ memtx_tree_index_size, + /* .bsize = */ memtx_tree_index_bsize, + /* .min = */ generic_index_min, + /* .max = */ generic_index_max, + /* .random = */ memtx_tree_index_random, + /* .count = */ memtx_tree_index_count, + /* .get = */ memtx_tree_index_get, + /* .replace = */ memtx_tree_index_replace, + /* .create_iterator = */ memtx_tree_index_create_iterator, + /* .create_snapshot_iterator = */ + memtx_tree_index_create_snapshot_iterator, + /* .stat = */ generic_index_stat, + /* .compact = */ generic_index_compact, + /* .reset_stat = */ generic_index_reset_stat, + /* .begin_build = */ memtx_tree_index_begin_build, + /* .reserve = */ memtx_tree_index_reserve, + /* .build_next = */ memtx_tree_index_build_next, + /* .end_build = */ memtx_tree_index_end_build, }; static const struct index_vtab memtx_tree_index_multikey_vtab = { - /* .destroy = */ memtx_tree_index_destroy, + /* .destroy = */ memtx_tree_index_destroy, /* .commit_create = */ generic_index_commit_create, /* .abort_create = */ generic_index_abort_create, /* .commit_modify = */ generic_index_commit_modify, /* .commit_drop = */ generic_index_commit_drop, - /* .update_def = */ memtx_tree_index_update_def, + /* .update_def = */ memtx_tree_index_update_def, /* .depends_on_pk = */ memtx_tree_index_depends_on_pk, /* .def_change_requires_rebuild = */ memtx_index_def_change_requires_rebuild, - /* .size = */ memtx_tree_index_size, - /* .bsize = */ memtx_tree_index_bsize, + /* .size = */ memtx_tree_index_size, + /* .bsize = */ memtx_tree_index_bsize, /* .min = */ generic_index_min, /* .max = */ generic_index_max, - /* .random = */ memtx_tree_index_random, - /* .count = */ memtx_tree_index_count, - /* .get = */ memtx_tree_index_get, + /* .random = */ memtx_tree_index_random, + /* .count = */ memtx_tree_index_count, + /* .get = */ memtx_tree_index_get, /* .replace = */ memtx_tree_index_replace_multikey, - /* .create_iterator = */ memtx_tree_index_create_iterator, + /* .create_iterator = */ memtx_tree_index_create_iterator, /* .create_snapshot_iterator = */ - memtx_tree_index_create_snapshot_iterator, + memtx_tree_index_create_snapshot_iterator, /* .stat = */ generic_index_stat, /* .compact = */ generic_index_compact, /* .reset_stat = */ generic_index_reset_stat, - /* .begin_build = */ memtx_tree_index_begin_build, - /* .reserve = */ memtx_tree_index_reserve, + /* .begin_build = */ memtx_tree_index_begin_build, + /* .reserve = */ memtx_tree_index_reserve, /* .build_next = */ memtx_tree_index_build_next_multikey, - /* .end_build = */ memtx_tree_index_end_build, + /* .end_build = */ memtx_tree_index_end_build, }; static const struct index_vtab memtx_tree_func_index_vtab = { - /* .destroy = */ memtx_tree_index_destroy, + /* .destroy = */ memtx_tree_index_destroy, /* .commit_create = */ generic_index_commit_create, /* .abort_create = */ generic_index_abort_create, /* .commit_modify = */ generic_index_commit_modify, /* .commit_drop = */ generic_index_commit_drop, - /* .update_def = */ memtx_tree_index_update_def, + /* .update_def = */ memtx_tree_index_update_def, /* .depends_on_pk = */ memtx_tree_index_depends_on_pk, /* .def_change_requires_rebuild = */ memtx_index_def_change_requires_rebuild, - /* .size = */ memtx_tree_index_size, - /* .bsize = */ memtx_tree_index_bsize, + /* .size = */ memtx_tree_index_size, + /* .bsize = */ memtx_tree_index_bsize, /* .min = */ generic_index_min, /* .max = */ generic_index_max, - /* .random = */ memtx_tree_index_random, - /* .count = */ memtx_tree_index_count, - /* .get = */ memtx_tree_index_get, + /* .random = */ memtx_tree_index_random, + /* .count = */ memtx_tree_index_count, + /* .get = */ memtx_tree_index_get, /* .replace = */ memtx_tree_func_index_replace, - /* .create_iterator = */ memtx_tree_index_create_iterator, + /* .create_iterator = */ memtx_tree_index_create_iterator, /* .create_snapshot_iterator = */ - memtx_tree_index_create_snapshot_iterator, + memtx_tree_index_create_snapshot_iterator, /* .stat = */ generic_index_stat, /* .compact = */ generic_index_compact, /* .reset_stat = */ generic_index_reset_stat, - /* .begin_build = */ memtx_tree_index_begin_build, - /* .reserve = */ memtx_tree_index_reserve, + /* .begin_build = */ memtx_tree_index_begin_build, + /* .reserve = */ memtx_tree_index_reserve, /* .build_next = */ memtx_tree_func_index_build_next, - /* .end_build = */ memtx_tree_index_end_build, + /* .end_build = */ memtx_tree_index_end_build, }; /** @@ -1459,7 +1647,7 @@ static const struct index_vtab memtx_tree_func_index_vtab = { * key defintion is not completely initialized at that moment). */ static const struct index_vtab memtx_tree_disabled_index_vtab = { - /* .destroy = */ memtx_tree_index_destroy, + /* .destroy = */ memtx_tree_index_destroy, /* .commit_create = */ generic_index_commit_create, /* .abort_create = */ generic_index_abort_create, /* .commit_modify = */ generic_index_commit_modify, @@ -1488,27 +1676,19 @@ static const struct index_vtab memtx_tree_disabled_index_vtab = { /* .end_build = */ generic_index_end_build, }; -struct index * -memtx_tree_index_new(struct memtx_engine *memtx, struct index_def *def) +template +static struct index * +memtx_tree_index_new_tpl(struct memtx_engine *memtx, struct index_def *def, + const struct index_vtab *vtab) { - struct memtx_tree_index *index = - (struct memtx_tree_index *)calloc(1, sizeof(*index)); + struct memtx_tree_index *index = + (struct memtx_tree_index *) + calloc(1, sizeof(*index)); if (index == NULL) { diag_set(OutOfMemory, sizeof(*index), "malloc", "struct memtx_tree_index"); return NULL; } - const struct index_vtab *vtab; - if (def->key_def->for_func_index) { - if (def->key_def->func_index_func == NULL) - vtab = &memtx_tree_disabled_index_vtab; - else - vtab = &memtx_tree_func_index_vtab; - } else if (def->key_def->is_multikey) { - vtab = &memtx_tree_index_multikey_vtab; - } else { - vtab = &memtx_tree_index_vtab; - } if (index_create(&index->base, (struct engine *)memtx, vtab, def) != 0) { free(index); @@ -1524,3 +1704,23 @@ memtx_tree_index_new(struct memtx_engine *memtx, struct index_def *def) memtx_index_extent_free, memtx); return &index->base; } + +struct index * +memtx_tree_index_new(struct memtx_engine *memtx, struct index_def *def) +{ + const struct index_vtab *vtab; + if (def->key_def->for_func_index) { + if (def->key_def->func_index_func == NULL) + vtab = &memtx_tree_disabled_index_vtab; + else + vtab = &memtx_tree_func_index_vtab; + } else if (def->key_def->is_multikey) { + vtab = &memtx_tree_index_multikey_vtab; + } else if (def->opts.hint) { + vtab = &memtx_tree_use_hint_index_vtab; + } else { + vtab = &memtx_tree_no_hint_index_vtab; + return memtx_tree_index_new_tpl(memtx, def, vtab); + } + return memtx_tree_index_new_tpl(memtx, def, vtab); +} diff --git a/src/lib/salad/bps_tree.h b/src/lib/salad/bps_tree.h index ef5ae3d..0bb803a 100644 --- a/src/lib/salad/bps_tree.h +++ b/src/lib/salad/bps_tree.h @@ -168,6 +168,17 @@ /* {{{ BPS-tree interface settings */ /** + * Optional namespace for structs and functions. + * Is set, struct and functions will have BPS_TREE_NAMESPACE:: prefix. + * For example one can #define BPS_TREE_NAMESPACE my along with + * #define BPS_TREE_NAME _test, and use then + * struct my::bps_tree_test my_tree; + * my::bps_tree_test_create(&my_tree, ...); + * + * #define BPS_TREE_NAMESPACE + */ + +/** * Custom name for structs and functions. * Struct and functions will have bps_tree##BPS_TREE_NAME name or prefix. * For example one can #define BPS_TREE_NAME _test, and use then @@ -300,6 +311,10 @@ /* }}} */ +#ifdef BPS_TREE_NAMESPACE +namespace BPS_TREE_NAMESPACE { +#endif + /* {{{ BPS-tree internal settings */ typedef int16_t bps_tree_pos_t; typedef uint32_t bps_tree_block_id_t; @@ -6188,3 +6203,7 @@ bps_tree_debug_check_internal_functions(bool assertme) #undef bps_tree_debug_check_insert_and_move_to_left_inner /* }}} */ + +#ifdef BPS_TREE_NAMESPACE +} /* namespace BPS_TREE_NAMESPACE { */ +#endif diff --git a/test/box/alter.result b/test/box/alter.result index 237c2d8..5b412a7 100644 --- a/test/box/alter.result +++ b/test/box/alter.result @@ -680,8 +680,9 @@ s.index.pk - type: unsigned is_nullable: false fieldno: 2 - type: TREE + hint: true id: 0 + type: TREE space_id: 731 name: pk ... @@ -710,9 +711,10 @@ s.index.pk - type: unsigned is_nullable: false fieldno: 1 - space_id: 731 + hint: true id: 0 type: TREE + space_id: 731 name: pk ... s.index.secondary @@ -722,8 +724,9 @@ s.index.secondary - type: unsigned is_nullable: false fieldno: 2 - type: TREE + hint: true id: 1 + type: TREE space_id: 731 name: secondary ... @@ -1559,3 +1562,97 @@ assert(err:match('does not exist') ~= nil) --- - true ... +-- hint +s = box.schema.create_space('test'); +--- +... +s:create_index('test1', {type='tree', parts={{1, 'uint'}}}).hint +--- +- true +... +s:create_index('test2', {type='tree', parts={{2, 'uint'}}, hint = true}).hint +--- +- true +... +s:create_index('test3', {type='tree', parts={{3, 'uint'}}, hint = false}).hint +--- +- false +... +s:create_index('test4', {type='tree', parts={{4, 'string'}}, hint = false}).hint +--- +- false +... +s.index.test1.hint +--- +- true +... +s.index.test2.hint +--- +- true +... +s.index.test3.hint +--- +- false +... +s.index.test4.hint +--- +- false +... +N = 1000 box.begin() for i = 1,N do s:replace{i, i, i, '' .. i} end box.commit() +--- +... +s.index.test1:bsize() == s.index.test2:bsize() +--- +- true +... +s.index.test1:bsize() > s.index.test3:bsize() +--- +- true +... +s.index.test1:bsize() > s.index.test4:bsize() +--- +- true +... +s.index.test1:alter{hint=false} +--- +... +s.index.test2:alter{hint=true} +--- +... +s.index.test3:alter{name='test33', hint=false} +--- +... +s.index.test4:alter{hint=true} +--- +... +s.index.test1.hint +--- +- false +... +s.index.test2.hint +--- +- true +... +s.index.test33.hint +--- +- false +... +s.index.test4.hint +--- +- true +... +s.index.test1:bsize() < s.index.test2:bsize() +--- +- true +... +s.index.test1:bsize() == s.index.test33:bsize() +--- +- true +... +s.index.test1:bsize() < s.index.test4:bsize() +--- +- true +... +s:drop() +--- +... diff --git a/test/box/alter.test.lua b/test/box/alter.test.lua index abd08e2..2114186 100644 --- a/test/box/alter.test.lua +++ b/test/box/alter.test.lua @@ -620,3 +620,37 @@ s:drop() s:alter({}) ok, err = pcall(box.schema.space.alter, s.id, {}) assert(err:match('does not exist') ~= nil) + +-- hint +s = box.schema.create_space('test'); +s:create_index('test1', {type='tree', parts={{1, 'uint'}}}).hint +s:create_index('test2', {type='tree', parts={{2, 'uint'}}, hint = true}).hint +s:create_index('test3', {type='tree', parts={{3, 'uint'}}, hint = false}).hint +s:create_index('test4', {type='tree', parts={{4, 'string'}}, hint = false}).hint + +s.index.test1.hint +s.index.test2.hint +s.index.test3.hint +s.index.test4.hint + +N = 1000 box.begin() for i = 1,N do s:replace{i, i, i, '' .. i} end box.commit() + +s.index.test1:bsize() == s.index.test2:bsize() +s.index.test1:bsize() > s.index.test3:bsize() +s.index.test1:bsize() > s.index.test4:bsize() + +s.index.test1:alter{hint=false} +s.index.test2:alter{hint=true} +s.index.test3:alter{name='test33', hint=false} +s.index.test4:alter{hint=true} + +s.index.test1.hint +s.index.test2.hint +s.index.test33.hint +s.index.test4.hint + +s.index.test1:bsize() < s.index.test2:bsize() +s.index.test1:bsize() == s.index.test33:bsize() +s.index.test1:bsize() < s.index.test4:bsize() + +s:drop() \ No newline at end of file diff --git a/test/box/errinj.result b/test/box/errinj.result index 613d22c..b8c2476 100644 --- a/test/box/errinj.result +++ b/test/box/errinj.result @@ -1774,9 +1774,10 @@ rtreespace:create_index('pk', {if_not_exists = true}) - type: unsigned is_nullable: false fieldno: 1 + hint: true id: 0 - space_id: 512 type: TREE + space_id: 512 name: pk ... rtreespace:create_index('target', {type='rtree', dimension = 3, parts={2, 'array'},unique = false, if_not_exists = true,}) diff --git a/test/box/tree_pk.result b/test/box/tree_pk.result index df3c78b..18cb607 100644 --- a/test/box/tree_pk.result +++ b/test/box/tree_pk.result @@ -852,3 +852,317 @@ box.internal.collation.drop('test') box.internal.collation.drop('test-ci') --- ... +-- hints +s = box.schema.space.create('test') +--- +... +s:create_index('test', {type = 'tree', hint = 'true'} ) +--- +- error: Illegal parameters, options parameter 'hint' should be of type boolean +... +s:create_index('test', {type = 'hash', hint = true} ) +--- +- error: 'Can''t create or modify index ''test'' in space ''test'': hint is only reasonable + with memtx tree index' +... +s:create_index('test', {type = 'hash'}):alter({hint = true}) +--- +- error: 'Can''t create or modify index ''test'' in space ''test'': hint is only reasonable + with memtx tree index' +... +s:create_index('multikey', {hint = true, parts = {{2, 'int', path = '[*]'}}}) +--- +- error: 'Can''t create or modify index ''multikey'' in space ''test'': multikey index + can''t use hints' +... +s:create_index('multikey', {parts = {{2, 'int', path = '[*]'}}}):alter({hint = true}) +--- +- error: 'Can''t create or modify index ''multikey'' in space ''test'': multikey index + can''t use hints' +... +lua_code = [[function(tuple) return {tuple[1] + tuple[2]} end]] +--- +... +box.schema.func.create('s', {body = lua_code, is_deterministic = true, is_sandboxed = true}) +--- +... +s:create_index('func', {hint = true, func = box.func.s.id, parts = {{1, 'unsigned'}}}) +--- +- error: 'Can''t create or modify index ''func'' in space ''test'': functional index + can''t use hints' +... +s:drop() +--- +... +s = box.schema.space.create('test', {engine = 'vinyl'}) +--- +... +s:create_index('test', {type = 'tree', hint = true} ) +--- +- error: 'Can''t create or modify index ''test'' in space ''test'': hint is only reasonable + with memtx tree index' +... +s:drop() +--- +... +-- numeric hints +s1 = box.schema.space.create('test1') +--- +... +s1:create_index('test', {type = 'tree', hint = false}).hint +--- +- false +... +s2 = box.schema.space.create('test2') +--- +... +s2:create_index('test', {type = 'tree'}).hint +--- +- true +... +N = 2000 +--- +... +box.begin() for i = 1,N do local v = math.random(10 * N) s1:replace{v} s2:replace{v} end box.commit() +--- +... +s1:count() == s2:count() +--- +- true +... +good = true r1 = s1:select{} r2 = s2:select{} +--- +... +if #r1 ~= #r2 then good = false end +--- +... +for k,v in pairs(r1) do if r2[k][1] ~= v[1] then good = false end end +--- +... +good +--- +- true +... +r1 = nil r2 = nil +--- +... +function diff(t1, t2) if t1 then return t1[1] ~= t2[1] else return t2 ~= nil end end +--- +... +for i = 1, N * 10 do if diff(s1:get{i}, s2:get{i}) then good = false end end +--- +... +good +--- +- true +... +s1.index[0]:bsize() < s2.index[0]:bsize() +--- +- true +... +s1.index[0]:alter{hint=true} +--- +... +s1.index[0]:bsize() == s2.index[0]:bsize() +--- +- true +... +s2.index[0]:alter{hint=false} +--- +... +s1.index[0]:bsize() > s2.index[0]:bsize() +--- +- true +... +s1.index[0]:alter{hint=false} +--- +... +s1.index[0]:bsize() == s2.index[0]:bsize() +--- +- true +... +s1:drop() +--- +... +s2:drop() +--- +... +-- string hints +s1 = box.schema.space.create('test1') +--- +... +s1:create_index('test', {type = 'tree', parts = {1, 'str'}, hint = false}).hint +--- +- false +... +s2 = box.schema.space.create('test2') +--- +... +s2:create_index('test', {type = 'tree', parts = {1, 'str'}}).hint +--- +- true +... +N = 1000 +--- +... +box.begin() for i = 1,N do local v = ''..math.random(10 * N) s1:replace{v} s2:replace{v} end box.commit() +--- +... +s1:count() == s2:count() +--- +- true +... +good = true r1 = s1:select{} r2 = s2:select{} +--- +... +if #r1 ~= #r2 then good = false end +--- +... +for k,v in pairs(r1) do if r2[k][1] ~= v[1] then good = false end end +--- +... +good +--- +- true +... +r1 = nil r2 = nil +--- +... +function diff(t1, t2) if t1 then return t1[1] ~= t2[1] else return t2 ~= nil end end +--- +... +for i = 1, N * 10 do v = ''..i if diff(s1:get{v}, s2:get{v}) then good = false end end +--- +... +good +--- +- true +... +s1.index[0]:bsize() < s2.index[0]:bsize() +--- +- true +... +s1.index[0]:alter{hint=true} +--- +... +s1.index[0]:bsize() == s2.index[0]:bsize() +--- +- true +... +s2.index[0]:alter{hint=false} +--- +... +s1.index[0]:bsize() > s2.index[0]:bsize() +--- +- true +... +s1.index[0]:alter{hint=false} +--- +... +s1.index[0]:bsize() == s2.index[0]:bsize() +--- +- true +... +s1:drop() +--- +... +s2:drop() +--- +... +-- string with collation hints +s1 = box.schema.space.create('test1') +--- +... +s1:create_index('test', {type = 'tree', parts = {{1, 'str', collation = 'Unicode'}}, hint = false}).hint +--- +- false +... +s2 = box.schema.space.create('test2') +--- +... +s2:create_index('test', {type = 'tree', parts = {{1, 'str', collation = 'Unicode'}}}).hint +--- +- true +... +N = 1000 +--- +... +syms = {'a', 'B', 'c', 'D', 'ж', 'Ё', '~', '1', '%', '2'} +--- +... +syms_size = #syms +--- +... +len = 20 +--- +... +vals = {} +--- +... +for i = 1,2*N do str = '' for j=1,len do str = str .. syms[math.random(syms_size)] end vals[i] = str end +--- +... +for i = 1,N do local v = vals[i] s1:replace{v} s2:replace{v} end +--- +... +s1:count() == s2:count() +--- +- true +... +good = true r1 = s1:select{} r2 = s2:select{} +--- +... +if #r1 ~= #r2 then good = false end +--- +... +for k,v in pairs(r1) do if r2[k][1] ~= v[1] then good = false end end +--- +... +good +--- +- true +... +r1 = nil r2 = nil +--- +... +function diff(t1, t2) if t1 then return t1[1] ~= t2[1] else return t2 ~= nil end end +--- +... +for i = 1, N * 2 do v = vals[i] if diff(s1:get{v}, s2:get{v}) then good = false end end +--- +... +good +--- +- true +... +s1.index[0]:bsize() < s2.index[0]:bsize() +--- +- true +... +s1.index[0]:alter{hint=true} +--- +... +s1.index[0]:bsize() == s2.index[0]:bsize() +--- +- true +... +s2.index[0]:alter{hint=false} +--- +... +s1.index[0]:bsize() > s2.index[0]:bsize() +--- +- true +... +s1.index[0]:alter{hint=false} +--- +... +s1.index[0]:bsize() == s2.index[0]:bsize() +--- +- true +... +s1:drop() +--- +... +s2:drop() +--- +... diff --git a/test/box/tree_pk.test.lua b/test/box/tree_pk.test.lua index 1190ab4..2f22ed9 100644 --- a/test/box/tree_pk.test.lua +++ b/test/box/tree_pk.test.lua @@ -301,3 +301,118 @@ s:drop() box.internal.collation.drop('test') box.internal.collation.drop('test-ci') + +-- hints +s = box.schema.space.create('test') +s:create_index('test', {type = 'tree', hint = 'true'} ) +s:create_index('test', {type = 'hash', hint = true} ) +s:create_index('test', {type = 'hash'}):alter({hint = true}) +s:create_index('multikey', {hint = true, parts = {{2, 'int', path = '[*]'}}}) +s:create_index('multikey', {parts = {{2, 'int', path = '[*]'}}}):alter({hint = true}) +lua_code = [[function(tuple) return {tuple[1] + tuple[2]} end]] +box.schema.func.create('s', {body = lua_code, is_deterministic = true, is_sandboxed = true}) +s:create_index('func', {hint = true, func = box.func.s.id, parts = {{1, 'unsigned'}}}) +s:drop() + +s = box.schema.space.create('test', {engine = 'vinyl'}) +s:create_index('test', {type = 'tree', hint = true} ) +s:drop() + +-- numeric hints +s1 = box.schema.space.create('test1') +s1:create_index('test', {type = 'tree', hint = false}).hint +s2 = box.schema.space.create('test2') +s2:create_index('test', {type = 'tree'}).hint + +N = 2000 +box.begin() for i = 1,N do local v = math.random(10 * N) s1:replace{v} s2:replace{v} end box.commit() +s1:count() == s2:count() + +good = true r1 = s1:select{} r2 = s2:select{} +if #r1 ~= #r2 then good = false end +for k,v in pairs(r1) do if r2[k][1] ~= v[1] then good = false end end +good +r1 = nil r2 = nil + +function diff(t1, t2) if t1 then return t1[1] ~= t2[1] else return t2 ~= nil end end +for i = 1, N * 10 do if diff(s1:get{i}, s2:get{i}) then good = false end end +good + +s1.index[0]:bsize() < s2.index[0]:bsize() +s1.index[0]:alter{hint=true} +s1.index[0]:bsize() == s2.index[0]:bsize() +s2.index[0]:alter{hint=false} +s1.index[0]:bsize() > s2.index[0]:bsize() +s1.index[0]:alter{hint=false} +s1.index[0]:bsize() == s2.index[0]:bsize() + +s1:drop() +s2:drop() + +-- string hints +s1 = box.schema.space.create('test1') +s1:create_index('test', {type = 'tree', parts = {1, 'str'}, hint = false}).hint +s2 = box.schema.space.create('test2') +s2:create_index('test', {type = 'tree', parts = {1, 'str'}}).hint + +N = 1000 +box.begin() for i = 1,N do local v = ''..math.random(10 * N) s1:replace{v} s2:replace{v} end box.commit() +s1:count() == s2:count() + +good = true r1 = s1:select{} r2 = s2:select{} +if #r1 ~= #r2 then good = false end +for k,v in pairs(r1) do if r2[k][1] ~= v[1] then good = false end end +good +r1 = nil r2 = nil + +function diff(t1, t2) if t1 then return t1[1] ~= t2[1] else return t2 ~= nil end end +for i = 1, N * 10 do v = ''..i if diff(s1:get{v}, s2:get{v}) then good = false end end +good + +s1.index[0]:bsize() < s2.index[0]:bsize() +s1.index[0]:alter{hint=true} +s1.index[0]:bsize() == s2.index[0]:bsize() +s2.index[0]:alter{hint=false} +s1.index[0]:bsize() > s2.index[0]:bsize() +s1.index[0]:alter{hint=false} +s1.index[0]:bsize() == s2.index[0]:bsize() + +s1:drop() +s2:drop() + +-- string with collation hints +s1 = box.schema.space.create('test1') +s1:create_index('test', {type = 'tree', parts = {{1, 'str', collation = 'Unicode'}}, hint = false}).hint +s2 = box.schema.space.create('test2') +s2:create_index('test', {type = 'tree', parts = {{1, 'str', collation = 'Unicode'}}}).hint + +N = 1000 +syms = {'a', 'B', 'c', 'D', 'ж', 'Ё', '~', '1', '%', '2'} +syms_size = #syms +len = 20 +vals = {} +for i = 1,2*N do str = '' for j=1,len do str = str .. syms[math.random(syms_size)] end vals[i] = str end + +for i = 1,N do local v = vals[i] s1:replace{v} s2:replace{v} end +s1:count() == s2:count() + +good = true r1 = s1:select{} r2 = s2:select{} +if #r1 ~= #r2 then good = false end +for k,v in pairs(r1) do if r2[k][1] ~= v[1] then good = false end end +good +r1 = nil r2 = nil + +function diff(t1, t2) if t1 then return t1[1] ~= t2[1] else return t2 ~= nil end end +for i = 1, N * 2 do v = vals[i] if diff(s1:get{v}, s2:get{v}) then good = false end end +good + +s1.index[0]:bsize() < s2.index[0]:bsize() +s1.index[0]:alter{hint=true} +s1.index[0]:bsize() == s2.index[0]:bsize() +s2.index[0]:alter{hint=false} +s1.index[0]:bsize() > s2.index[0]:bsize() +s1.index[0]:alter{hint=false} +s1.index[0]:bsize() == s2.index[0]:bsize() + +s1:drop() +s2:drop() diff --git a/test/box/tree_pk_multipart.result b/test/box/tree_pk_multipart.result index 93219f6..3f6bb94 100644 --- a/test/box/tree_pk_multipart.result +++ b/test/box/tree_pk_multipart.result @@ -542,3 +542,156 @@ space:drop() space = nil --- ... +-- hints +test_run:cmd("setopt delimiter ';'") +--- +- true +... +function equal(res1, res2) + if #res1 ~= #res2 then + return false + end + for k,v in pairs(res1) do + if res2[k][1] ~= v[1] or res2[k][2] ~= v[2] then + return false + end + end + return true +end +test_run:cmd("setopt delimiter ''"); +--- +... +-- num num +N1 = 100 +--- +... +t1 = {} +--- +... +for i = 1,N1*2 do t1[i] = math.random(10000) * 10000 + i end +--- +... +N2 = 5 +--- +... +t2 = {} +--- +... +for i = 1,N2*2 do t2[i] = math.random(1000000) end +--- +... +s1 = box.schema.space.create('test1') +--- +... +s1:create_index('test', {type = 'tree', parts = {{1, 'num'}, {2, 'num'}}, hint = false}).hint +--- +- false +... +s2 = box.schema.space.create('test2') +--- +... +s2:create_index('test', {type = 'tree', parts = {{1, 'num'}, {2, 'num'}}, hint = true}).hint +--- +- true +... +for j = 1,N2 do for i = 1,N1 do s1:replace{t1[i], t2[j]} s2:replace{t1[i], t2[j]} end end +--- +... +s1:count() == s2:count() +--- +- true +... +equal(s1:select{}, s2:select{}) +--- +- true +... +good = true +--- +... +for i = 1,N1*2 do good = good and equal(s1:select{t1[i]}, s2:select{t1[i]}) end +--- +... +good +--- +- true +... +for i = 1,N1*2 do for j=1,N2*2 do good = good and equal(s1:select{t1[i], t2[j]}, s2:select{t1[i], t2[j]}) end end +--- +... +good +--- +- true +... +s1:drop() +--- +... +s2:drop() +--- +... +-- str num +N1 = 100 +--- +... +t1 = {} +--- +... +for i = 1,N1*2 do t1[i] = ''..(math.random(10000) * 10000 + i) end +--- +... +N2 = 5 +--- +... +t2 = {} +--- +... +for i = 1,N2*2 do t2[i] = math.random(1000000) end +--- +... +s1 = box.schema.space.create('test1') +--- +... +s1:create_index('test', {type = 'tree', parts = {{1, 'str'}, {2, 'num'}}, hint = false}).hint +--- +- false +... +s2 = box.schema.space.create('test2') +--- +... +s2:create_index('test', {type = 'tree', parts = {{1, 'str'}, {2, 'num'}}, hint = true}).hint +--- +- true +... +for j = 1,N2 do for i = 1,N1 do s1:replace{t1[i], t2[j]} s2:replace{t1[i], t2[j]} end end +--- +... +s1:count() == s2:count() +--- +- true +... +equal(s1:select{}, s2:select{}) +--- +- true +... +good = true +--- +... +for i = 1,N1*2 do good = good and equal(s1:select{t1[i]}, s2:select{t1[i]}) end +--- +... +good +--- +- true +... +for i = 1,N1*2 do for j=1,N2*2 do good = good and equal(s1:select{t1[i], t2[j]}, s2:select{t1[i], t2[j]}) end end +--- +... +good +--- +- true +... +s1:drop() +--- +... +s2:drop() +--- +... diff --git a/test/box/tree_pk_multipart.test.lua b/test/box/tree_pk_multipart.test.lua index 7d3405f..cba3a98 100644 --- a/test/box/tree_pk_multipart.test.lua +++ b/test/box/tree_pk_multipart.test.lua @@ -194,3 +194,67 @@ test_run:cmd("setopt delimiter ''"); space:drop() space = nil + + +-- hints +test_run:cmd("setopt delimiter ';'") +function equal(res1, res2) + if #res1 ~= #res2 then + return false + end + for k,v in pairs(res1) do + if res2[k][1] ~= v[1] or res2[k][2] ~= v[2] then + return false + end + end + return true +end +test_run:cmd("setopt delimiter ''"); + +-- num num +N1 = 100 +t1 = {} +for i = 1,N1*2 do t1[i] = math.random(10000) * 10000 + i end +N2 = 5 +t2 = {} +for i = 1,N2*2 do t2[i] = math.random(1000000) end + +s1 = box.schema.space.create('test1') +s1:create_index('test', {type = 'tree', parts = {{1, 'num'}, {2, 'num'}}, hint = false}).hint +s2 = box.schema.space.create('test2') +s2:create_index('test', {type = 'tree', parts = {{1, 'num'}, {2, 'num'}}, hint = true}).hint +for j = 1,N2 do for i = 1,N1 do s1:replace{t1[i], t2[j]} s2:replace{t1[i], t2[j]} end end +s1:count() == s2:count() +equal(s1:select{}, s2:select{}) +good = true +for i = 1,N1*2 do good = good and equal(s1:select{t1[i]}, s2:select{t1[i]}) end +good +for i = 1,N1*2 do for j=1,N2*2 do good = good and equal(s1:select{t1[i], t2[j]}, s2:select{t1[i], t2[j]}) end end +good + +s1:drop() +s2:drop() + +-- str num +N1 = 100 +t1 = {} +for i = 1,N1*2 do t1[i] = ''..(math.random(10000) * 10000 + i) end +N2 = 5 +t2 = {} +for i = 1,N2*2 do t2[i] = math.random(1000000) end + +s1 = box.schema.space.create('test1') +s1:create_index('test', {type = 'tree', parts = {{1, 'str'}, {2, 'num'}}, hint = false}).hint +s2 = box.schema.space.create('test2') +s2:create_index('test', {type = 'tree', parts = {{1, 'str'}, {2, 'num'}}, hint = true}).hint +for j = 1,N2 do for i = 1,N1 do s1:replace{t1[i], t2[j]} s2:replace{t1[i], t2[j]} end end +s1:count() == s2:count() +equal(s1:select{}, s2:select{}) +good = true +for i = 1,N1*2 do good = good and equal(s1:select{t1[i]}, s2:select{t1[i]}) end +good +for i = 1,N1*2 do for j=1,N2*2 do good = good and equal(s1:select{t1[i], t2[j]}, s2:select{t1[i], t2[j]}) end end +good + +s1:drop() +s2:drop() -- 2.7.4