[Tarantool-patches] [PATCH 2/2] memtx: make tuple compare hints optional

[Aleksandr Lyapunov <alyapunov@tarantool.org>]

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               | 599 ++++++++++++++++++++++++------------
 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, 1269 insertions(+), 205 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..17d58c5 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 <int USE_HINT>
+struct memtx_tree_key_data;
+
+template <>
+struct memtx_tree_key_data<0> : 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<1> : 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 <int USE_HINT>
+struct memtx_tree_data;
+
+template <>
+struct memtx_tree_data<0> : memtx_tree_data_common {
+	static constexpr hint_t hint = HINT_NONE;
+	void set_hint(hint_t) { assert(false); }
+};
+
+template <>
+struct memtx_tree_data<1> :  memtx_tree_data<0> {
 	/** 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<0>
+#define bps_tree_key_t struct memtx_tree_key_data<0> *
+
 #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<1>
+#define bps_tree_key_t struct memtx_tree_key_data<1> *
+
+#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 <int USE_HINT>
+struct memtx_tree_selector;
+
+template <>
+struct memtx_tree_selector<0> : NS_NO_HINT::memtx_tree {};
+
+template <>
+struct memtx_tree_selector<1> : NS_USE_HINT::memtx_tree {};
+
+template <int USE_HINT>
+using memtx_tree_t = struct memtx_tree_selector<USE_HINT>;
+
+template <int USE_HINT>
+struct memtx_tree_iterator_selector;
+
+template <>
+struct memtx_tree_iterator_selector<0> {
+	using type = NS_NO_HINT::memtx_tree_iterator;
+};
+
+template <>
+struct memtx_tree_iterator_selector<1> {
+	using type = NS_USE_HINT::memtx_tree_iterator;
+};
+
+template <int USE_HINT>
+using memtx_tree_iterator_t = typename memtx_tree_iterator_selector<USE_HINT>::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 <int USE_HINT>
 struct memtx_tree_index {
 	struct index base;
-	struct memtx_tree tree;
-	struct memtx_tree_data *build_array;
+	memtx_tree_t<USE_HINT> tree;
+	struct memtx_tree_data<USE_HINT> *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<USE_HINT> gc_iterator;
 };
 
 /* {{{ Utilities. *************************************************/
 
+template <class TREE>
 static inline struct key_def *
-memtx_tree_cmp_def(struct memtx_tree *tree)
+memtx_tree_cmp_def(TREE *tree)
 {
 	return tree->arg;
 }
 
+template <int USE_HINT>
 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<USE_HINT> *data_a =
+		(struct memtx_tree_data<USE_HINT> *)a;
+	const struct memtx_tree_data<USE_HINT> *data_b =
+		(struct memtx_tree_data<USE_HINT> *)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 <int USE_HINT>
 struct tree_iterator {
 	struct iterator base;
-	struct memtx_tree_iterator tree_iterator;
+	memtx_tree_iterator_t<USE_HINT> tree_iterator;
 	enum iterator_type type;
-	struct memtx_tree_key_data key_data;
-	struct memtx_tree_data current;
+	struct memtx_tree_key_data<USE_HINT> key_data;
+	struct memtx_tree_data<USE_HINT> 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<0>) <= MEMTX_ITERATOR_SIZE,
+	      "sizeof(struct tree_iterator<0>) must be less than or equal "
+	      "to MEMTX_ITERATOR_SIZE");
+static_assert(sizeof(struct tree_iterator<1>) <= MEMTX_ITERATOR_SIZE,
+	      "sizeof(struct tree_iterator<1>) must be less than or equal "
 	      "to MEMTX_ITERATOR_SIZE");
 
+template <int USE_HINT>
 static void
 tree_iterator_free(struct iterator *iterator);
 
-static inline struct tree_iterator *
-tree_iterator(struct iterator *it)
+template <int USE_HINT>
+static inline struct tree_iterator<USE_HINT> *
+get_tree_iterator(struct iterator *it)
 {
-	assert(it->free == tree_iterator_free);
-	return (struct tree_iterator *) it;
+	assert(it->free == &tree_iterator_free<USE_HINT>);
+	return (struct tree_iterator<USE_HINT> *) it;
 }
 
+template <int USE_HINT>
 static void
 tree_iterator_free(struct iterator *iterator)
 {
-	struct tree_iterator *it = tree_iterator(iterator);
+	struct tree_iterator<USE_HINT> *it = get_tree_iterator<USE_HINT>(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 <int USE_HINT>
 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<USE_HINT> *index =
+		(struct memtx_tree_index<USE_HINT> *)iterator->index;
+	struct tree_iterator<USE_HINT> *it = get_tree_iterator<USE_HINT>(iterator);
 	assert(it->current.tuple != NULL);
-	struct memtx_tree_data *check =
+	struct memtx_tree_data<USE_HINT> *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<USE_HINT> *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 <int USE_HINT>
 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<USE_HINT> *index =
+		(struct memtx_tree_index<USE_HINT> *)iterator->index;
+	struct tree_iterator<USE_HINT> *it = get_tree_iterator<USE_HINT>(iterator);
 	assert(it->current.tuple != NULL);
-	struct memtx_tree_data *check =
+	struct memtx_tree_data<USE_HINT> *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<USE_HINT> *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 <int USE_HINT>
 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<USE_HINT> *index =
+		(struct memtx_tree_index<USE_HINT> *)iterator->index;
+	struct tree_iterator<USE_HINT> *it = get_tree_iterator<USE_HINT>(iterator);
 	assert(it->current.tuple != NULL);
-	struct memtx_tree_data *check =
+	struct memtx_tree_data<USE_HINT> *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<USE_HINT> *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 <int USE_HINT>
 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<USE_HINT> *index =
+		(struct memtx_tree_index<USE_HINT> *)iterator->index;
+	struct tree_iterator<USE_HINT> *it = get_tree_iterator<USE_HINT>(iterator);
 	assert(it->current.tuple != NULL);
-	struct memtx_tree_data *check =
+	struct memtx_tree_data<USE_HINT> *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<USE_HINT> *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 <int USE_HINT>								\
 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<USE_HINT> *tree =						\
+		&((struct memtx_tree_index<USE_HINT> *)iterator->index)->tree;	\
+	struct tree_iterator<USE_HINT> *it =   					\
+		get_tree_iterator<USE_HINT>(iterator);				\
+	memtx_tree_iterator_t<USE_HINT> *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<USE_HINT>(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<USE_HINT> *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 <int USE_HINT>
 static void
-tree_iterator_set_next_method(struct tree_iterator *it)
+tree_iterator_set_next_method(struct tree_iterator<USE_HINT> *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<USE_HINT>;
 		break;
 	case ITER_REQ:
-		it->base.next = tree_iterator_prev_equal;
+		it->base.next = tree_iterator_prev_equal<USE_HINT>;
 		break;
 	case ITER_ALL:
-		it->base.next = tree_iterator_next;
+		it->base.next = tree_iterator_next<USE_HINT>;
 		break;
 	case ITER_LT:
 	case ITER_LE:
-		it->base.next = tree_iterator_prev;
+		it->base.next = tree_iterator_prev<USE_HINT>;
 		break;
 	case ITER_GE:
 	case ITER_GT:
-		it->base.next = tree_iterator_next;
+		it->base.next = tree_iterator_next<USE_HINT>;
 		break;
 	default:
 		/* The type was checked in initIterator */
@@ -375,15 +479,16 @@ tree_iterator_set_next_method(struct tree_iterator *it)
 	}
 }
 
+template <int USE_HINT>
 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<USE_HINT> *index =
+		(struct memtx_tree_index<USE_HINT> *)iterator->index;
+	struct tree_iterator<USE_HINT> *it = get_tree_iterator<USE_HINT>(iterator);
 	it->base.next = tree_iterator_dummie;
-	struct memtx_tree *tree = &index->tree;
+	memtx_tree_t<USE_HINT> *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<USE_HINT> *res =
+		memtx_tree_iterator_get_elem(tree, &it->tree_iterator);
 	if (!res)
 		return 0;
 	*ret = res->tuple;
@@ -454,14 +559,16 @@ tree_iterator_start(struct iterator *iterator, struct tuple **ret)
 
 /* {{{ MemtxTree  **********************************************************/
 
+template <int USE_HINT>
 static void
-memtx_tree_index_free(struct memtx_tree_index *index)
+memtx_tree_index_free(struct memtx_tree_index<USE_HINT> *index)
 {
 	memtx_tree_destroy(&index->tree);
 	free(index->build_array);
 	free(index);
 }
 
+template <int USE_HINT>
 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<USE_HINT> *index = container_of(task,
+			struct memtx_tree_index<USE_HINT>, gc_task);
+	memtx_tree_t<USE_HINT> *tree = &index->tree;
+	memtx_tree_iterator_t<USE_HINT> *itr = &index->gc_iterator;
 
 	unsigned int loops = 0;
 	while (!memtx_tree_iterator_is_invalid(itr)) {
-		struct memtx_tree_data *res =
+		struct memtx_tree_data<USE_HINT> *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 <int USE_HINT>
 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<USE_HINT> *index = container_of(task,
+			struct memtx_tree_index<USE_HINT>, 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 <int USE_HINT>
+static struct memtx_gc_task_vtab * get_memtx_tree_index_gc_vtab()
+{
+	static memtx_gc_task_vtab tab =
+	{
+		.run = memtx_tree_index_gc_run<USE_HINT>,
+		.free = memtx_tree_index_gc_free<USE_HINT>,
+	};
+	return &tab;
 };
 
+template <int USE_HINT>
 static void
 memtx_tree_index_destroy(struct index *base)
 {
-	struct memtx_tree_index *index = (struct memtx_tree_index *)base;
+	struct memtx_tree_index<USE_HINT> *index =
+		(struct memtx_tree_index<USE_HINT> *)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<USE_HINT>();
 		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 <int USE_HINT>
 static void
 memtx_tree_index_update_def(struct index *base)
 {
-	struct memtx_tree_index *index = (struct memtx_tree_index *)base;
+	struct memtx_tree_index<USE_HINT> *index =
+		(struct memtx_tree_index<USE_HINT> *)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 <int USE_HINT>
 static ssize_t
 memtx_tree_index_size(struct index *base)
 {
-	struct memtx_tree_index *index = (struct memtx_tree_index *)base;
+	struct memtx_tree_index<USE_HINT> *index =
+		(struct memtx_tree_index<USE_HINT> *)base;
 	return memtx_tree_size(&index->tree);
 }
 
+template <int USE_HINT>
 static ssize_t
 memtx_tree_index_bsize(struct index *base)
 {
-	struct memtx_tree_index *index = (struct memtx_tree_index *)base;
+	struct memtx_tree_index<USE_HINT> *index =
+		(struct memtx_tree_index<USE_HINT> *)base;
 	return memtx_tree_mem_used(&index->tree);
 }
 
+template <int USE_HINT>
 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<USE_HINT> *index =
+		(struct memtx_tree_index<USE_HINT> *)base;
+	struct memtx_tree_data<USE_HINT> *res = memtx_tree_random(&index->tree, rnd);
 	*result = res != NULL ? res->tuple : NULL;
 	return 0;
 }
 
+template <int USE_HINT>
 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<USE_HINT>(base); /* optimization */
 	return generic_index_count(base, type, key, part_count);
 }
 
+template <int USE_HINT>
 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<USE_HINT> *index =
+		(struct memtx_tree_index<USE_HINT> *)base;
 	struct key_def *cmp_def = memtx_tree_cmp_def(&index->tree);
-	struct memtx_tree_key_data key_data;
+	struct memtx_tree_key_data<USE_HINT> 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<USE_HINT> *res =
+		memtx_tree_find(&index->tree, &key_data);
 	if (res == NULL) {
 		*result = NULL;
 		return 0;
@@ -611,18 +740,21 @@ memtx_tree_index_get(struct index *base, const char *key,
 	return 0;
 }
 
+template <int USE_HINT>
 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<USE_HINT> *index =
+		(struct memtx_tree_index<USE_HINT> *)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<USE_HINT> 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<USE_HINT> dup_data;
 		dup_data.tuple = NULL;
 
 		/* Try to optimistically replace the new_tuple. */
@@ -652,9 +784,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<USE_HINT> 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 +800,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<1> *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<1> *replaced_data,
 			bool *is_multikey_conflict)
 {
-	struct memtx_tree_data new_data, dup_data;
+	struct memtx_tree_data<1> new_data, dup_data;
 	new_data.tuple = new_tuple;
 	new_data.hint = hint;
 	dup_data.tuple = NULL;
@@ -720,11 +853,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<1> *index,
 			struct tuple *new_tuple, struct tuple *replaced_tuple,
 			int err_multikey_idx)
 {
-	struct memtx_tree_data data;
+	struct memtx_tree_data<1> data;
 	if (replaced_tuple != NULL) {
 		/* Restore replaced tuple index occurrences. */
 		struct key_def *cmp_def = memtx_tree_cmp_def(&index->tree);
@@ -798,7 +931,7 @@ 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<1> *index = (struct memtx_tree_index<1> *)base;
 	struct key_def *cmp_def = memtx_tree_cmp_def(&index->tree);
 	*result = NULL;
 	if (new_tuple != NULL) {
@@ -808,7 +941,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<1> replaced_data;
 			err = memtx_tree_index_replace_multikey_one(index,
 						old_tuple, new_tuple, mode,
 						multikey_idx, &replaced_data,
@@ -833,7 +966,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<1> data;
 		data.tuple = old_tuple;
 		uint32_t multikey_count =
 			tuple_multikey_count(old_tuple, cmp_def);
@@ -865,7 +998,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<1> key;
 };
 
 /** Allocate a new func_key_undo on given region. */
@@ -888,7 +1021,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<1> *index,
 				       struct rlist *old_keys,
 				       struct rlist *new_keys)
 {
@@ -919,7 +1052,7 @@ 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<1> *index = (struct memtx_tree_index<1> *)base;
 	struct index_def *index_def = index->base.def;
 	assert(index_def->key_def->for_func_index);
 
@@ -952,7 +1085,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<1> old_data;
 			old_data.tuple = NULL;
 			err = memtx_tree_index_replace_multikey_one(index,
 						old_tuple, new_tuple,
@@ -1015,7 +1148,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<1> data, deleted_data;
 		data.tuple = old_tuple;
 		const char *key;
 		while (key_list_iterator_next(&it, &key) == 0 && key != NULL) {
@@ -1040,11 +1173,13 @@ end:
 	return rc;
 }
 
+template <int USE_HINT>
 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<USE_HINT> *index =
+		(struct memtx_tree_index<USE_HINT> *)base;
 	struct memtx_engine *memtx = (struct memtx_engine *)base->engine;
 	struct key_def *cmp_def = memtx_tree_cmp_def(&index->tree);
 
@@ -1064,42 +1199,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<USE_HINT> *it = (struct tree_iterator<USE_HINT> *)
 		mempool_alloc(&memtx->iterator_pool);
 	if (it == NULL) {
-		diag_set(OutOfMemory, sizeof(struct tree_iterator),
+		diag_set(OutOfMemory, sizeof(struct tree_iterator<USE_HINT>),
 			 "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<USE_HINT>;
+	it->base.free = tree_iterator_free<USE_HINT>;
 	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 <int USE_HINT>
 static void
 memtx_tree_index_begin_build(struct index *base)
 {
-	struct memtx_tree_index *index = (struct memtx_tree_index *)base;
+	struct memtx_tree_index<USE_HINT> *index =
+		(struct memtx_tree_index<USE_HINT> *)base;
 	assert(memtx_tree_size(&index->tree) == 0);
 	(void)index;
 }
 
+template <int USE_HINT>
 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<USE_HINT> *index =
+		(struct memtx_tree_index<USE_HINT> *)base;
 	if (size_hint < index->build_array_alloc_size)
 		return 0;
-	struct memtx_tree_data *tmp =
-		(struct memtx_tree_data *)
+	struct memtx_tree_data<USE_HINT> *tmp =
+		(struct memtx_tree_data<USE_HINT> *)
 			realloc(index->build_array, size_hint * sizeof(*tmp));
 	if (tmp == NULL) {
 		diag_set(OutOfMemory, size_hint * sizeof(*tmp),
@@ -1111,14 +1251,15 @@ memtx_tree_index_reserve(struct index *base, uint32_t size_hint)
 	return 0;
 }
 
+template <int USE_HINT>
 /** 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<USE_HINT> *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<USE_HINT> *)malloc(MEMTX_EXTENT_SIZE);
 		if (index->build_array == NULL) {
 			diag_set(OutOfMemory, MEMTX_EXTENT_SIZE,
 				 "memtx_tree_index", "build_next");
@@ -1131,8 +1272,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<USE_HINT> *tmp =
+			(struct memtx_tree_data<USE_HINT> *)realloc(index->build_array,
 				index->build_array_alloc_size * sizeof(*tmp));
 		if (tmp == NULL) {
 			diag_set(OutOfMemory, index->build_array_alloc_size *
@@ -1141,17 +1282,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<USE_HINT> *elem =
 		&index->build_array[index->build_array_size++];
 	elem->tuple = tuple;
-	elem->hint = hint;
+	if (USE_HINT)
+		elem->set_hint(hint);
 	return 0;
 }
 
+template <int USE_HINT>
 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<USE_HINT> *index =
+		(struct memtx_tree_index<USE_HINT> *)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 +1304,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<1> *index = (struct memtx_tree_index<1> *)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 +1319,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<1> *index = (struct memtx_tree_index<1> *)base;
 	struct index_def *index_def = index->base.def;
 	assert(index_def->key_def->for_func_index);
 
@@ -1211,8 +1355,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 <int USE_HINT>
 static void
-memtx_tree_index_build_array_deduplicate(struct memtx_tree_index *index,
+memtx_tree_index_build_array_deduplicate(struct memtx_tree_index<USE_HINT> *index,
 			void (*destroy)(struct tuple *tuple, const char *hint))
 {
 	if (index->build_array_size == 0)
@@ -1246,13 +1391,16 @@ memtx_tree_index_build_array_deduplicate(struct memtx_tree_index *index,
 	index->build_array_size = w_idx + 1;
 }
 
+template <int USE_HINT>
 static void
 memtx_tree_index_end_build(struct index *base)
 {
-	struct memtx_tree_index *index = (struct memtx_tree_index *)base;
+	struct memtx_tree_index<USE_HINT> *index =
+		(struct memtx_tree_index<USE_HINT> *)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<USE_HINT>, cmp_def);
 	if (cmp_def->is_multikey) {
 		/*
 		 * Multikey index may have equal(in terms of
@@ -1261,9 +1409,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<USE_HINT>(index, NULL);
 	} else if (cmp_def->for_func_index) {
-		memtx_tree_index_build_array_deduplicate(index,
+		memtx_tree_index_build_array_deduplicate<USE_HINT>(index,
 							 tuple_chunk_delete);
 	}
 	memtx_tree_build(&index->tree, index->build_array,
@@ -1275,19 +1423,21 @@ memtx_tree_index_end_build(struct index *base)
 	index->build_array_alloc_size = 0;
 }
 
+template <int USE_HINT>
 struct tree_snapshot_iterator {
 	struct snapshot_iterator base;
-	struct memtx_tree_index *index;
-	struct memtx_tree_iterator tree_iterator;
+	struct memtx_tree_index<USE_HINT> *index;
+	memtx_tree_iterator_t<USE_HINT> tree_iterator;
 	struct memtx_tx_snapshot_cleaner cleaner;
 };
 
+template <int USE_HINT>
 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<USE_HINT>);
+	struct tree_snapshot_iterator<USE_HINT> *it =
+		(struct tree_snapshot_iterator<USE_HINT> *)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 +1446,18 @@ tree_snapshot_iterator_free(struct snapshot_iterator *iterator)
 	free(iterator);
 }
 
+template <int USE_HINT>
 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<USE_HINT>);
+	struct tree_snapshot_iterator<USE_HINT> *it =
+		(struct tree_snapshot_iterator<USE_HINT> *)iterator;
+	memtx_tree_t<USE_HINT> *tree = &it->index->tree;
 
 	while (true) {
-		struct memtx_tree_data *res =
+		struct memtx_tree_data<USE_HINT> *res =
 			memtx_tree_iterator_get_elem(tree, &it->tree_iterator);
 
 		if (res == NULL) {
@@ -1333,14 +1484,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 <int USE_HINT>
 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<USE_HINT> *index =
+		(struct memtx_tree_index<USE_HINT> *)base;
+	struct tree_snapshot_iterator<USE_HINT> *it =
+		(struct tree_snapshot_iterator<USE_HINT> *)
+		calloc(1, sizeof(*it));
 	if (it == NULL) {
-		diag_set(OutOfMemory, sizeof(struct tree_snapshot_iterator),
+		diag_set(OutOfMemory,
+			 sizeof(struct tree_snapshot_iterator<USE_HINT>),
 			 "memtx_tree_index", "create_snapshot_iterator");
 		return NULL;
 	}
@@ -1352,8 +1507,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<USE_HINT>;
+	it->base.next = tree_snapshot_iterator_next<USE_HINT>;
 	it->index = index;
 	index_ref(base);
 	it->tree_iterator = memtx_tree_iterator_first(&index->tree);
@@ -1362,94 +1517,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<0>,
 	/* .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<0>,
 	/* .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<0>,
+	/* .bsize = */ memtx_tree_index_bsize<0>,
 	/* .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<0>,
+	/* .count = */ memtx_tree_index_count<0>,
+	/* .get = */ memtx_tree_index_get<0>,
+	/* .replace = */ memtx_tree_index_replace<0>,
+	/* .create_iterator = */ memtx_tree_index_create_iterator<0>,
 	/* .create_snapshot_iterator = */
-		memtx_tree_index_create_snapshot_iterator,
+		memtx_tree_index_create_snapshot_iterator<0>,
 	/* .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<0>,
+	/* .reserve = */ memtx_tree_index_reserve<0>,
+	/* .build_next = */ memtx_tree_index_build_next<0>,
+	/* .end_build = */ memtx_tree_index_end_build<0>,
+};
+
+static const struct index_vtab memtx_tree_use_hint_index_vtab = {
+	/* .destroy = */ memtx_tree_index_destroy<1>,
+	/* .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<1>,
+	/* .depends_on_pk = */ memtx_tree_index_depends_on_pk,
+	/* .def_change_requires_rebuild = */
+		memtx_index_def_change_requires_rebuild,
+	/* .size = */ memtx_tree_index_size<1>,
+	/* .bsize = */ memtx_tree_index_bsize<1>,
+	/* .min = */ generic_index_min,
+	/* .max = */ generic_index_max,
+	/* .random = */ memtx_tree_index_random<1>,
+	/* .count = */ memtx_tree_index_count<1>,
+	/* .get = */ memtx_tree_index_get<1>,
+	/* .replace = */ memtx_tree_index_replace<1>,
+	/* .create_iterator = */ memtx_tree_index_create_iterator<1>,
+	/* .create_snapshot_iterator = */
+		memtx_tree_index_create_snapshot_iterator<1>,
+	/* .stat = */ generic_index_stat,
+	/* .compact = */ generic_index_compact,
+	/* .reset_stat = */ generic_index_reset_stat,
+	/* .begin_build = */ memtx_tree_index_begin_build<1>,
+	/* .reserve = */ memtx_tree_index_reserve<1>,
+	/* .build_next = */ memtx_tree_index_build_next<1>,
+	/* .end_build = */ memtx_tree_index_end_build<1>,
 };
 
 static const struct index_vtab memtx_tree_index_multikey_vtab = {
-	/* .destroy = */ memtx_tree_index_destroy,
+	/* .destroy = */ memtx_tree_index_destroy<1>,
 	/* .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<1>,
 	/* .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<1>,
+	/* .bsize = */ memtx_tree_index_bsize<1>,
 	/* .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<1>,
+	/* .count = */ memtx_tree_index_count<1>,
+	/* .get = */ memtx_tree_index_get<1>,
 	/* .replace = */ memtx_tree_index_replace_multikey,
-	/* .create_iterator = */ memtx_tree_index_create_iterator,
+	/* .create_iterator = */ memtx_tree_index_create_iterator<1>,
 	/* .create_snapshot_iterator = */
-		memtx_tree_index_create_snapshot_iterator,
+		memtx_tree_index_create_snapshot_iterator<1>,
 	/* .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<1>,
+	/* .reserve = */ memtx_tree_index_reserve<1>,
 	/* .build_next = */ memtx_tree_index_build_next_multikey,
-	/* .end_build = */ memtx_tree_index_end_build,
+	/* .end_build = */ memtx_tree_index_end_build<1>,
 };
 
 static const struct index_vtab memtx_tree_func_index_vtab = {
-	/* .destroy = */ memtx_tree_index_destroy,
+	/* .destroy = */ memtx_tree_index_destroy<1>,
 	/* .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<1>,
 	/* .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<1>,
+	/* .bsize = */ memtx_tree_index_bsize<1>,
 	/* .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<1>,
+	/* .count = */ memtx_tree_index_count<1>,
+	/* .get = */ memtx_tree_index_get<1>,
 	/* .replace = */ memtx_tree_func_index_replace,
-	/* .create_iterator = */ memtx_tree_index_create_iterator,
+	/* .create_iterator = */ memtx_tree_index_create_iterator<1>,
 	/* .create_snapshot_iterator = */
-		memtx_tree_index_create_snapshot_iterator,
+		memtx_tree_index_create_snapshot_iterator<1>,
 	/* .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<1>,
+	/* .reserve = */ memtx_tree_index_reserve<1>,
 	/* .build_next = */ memtx_tree_func_index_build_next,
-	/* .end_build = */ memtx_tree_index_end_build,
+	/* .end_build = */ memtx_tree_index_end_build<1>,
 };
 
 /**
@@ -1459,7 +1644,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<1>,
 	/* .commit_create = */ generic_index_commit_create,
 	/* .abort_create = */ generic_index_abort_create,
 	/* .commit_modify = */ generic_index_commit_modify,
@@ -1488,27 +1673,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 <int USE_HINT>
+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<USE_HINT> *index =
+		(struct memtx_tree_index<USE_HINT> *)
+		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 +1701,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<0>(memtx, def, vtab);
+	}
+	return memtx_tree_index_new_tpl<1>(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