[PATCH v1 4/4] box: introduce hint option for memtx tree index

[Kirill Shcherbatov <kshcherbatov@tarantool.org>]

If an index has certain option, a compare hint must be calculated
and stored within bps_tree along with struct tuple pointer. This
hint must be used for tuple precomparison in order to avoid memory
fetching and significantly improve tree performance.

Such a hinted tree will cost twice amount of memory - 20 byte per
tuple on average.
Enabled hint option improve performance on average by 15%; Select
operations are significantly accelerated (there are scenarios in
which the difference reaches 200-250%).

Test set from original @alyapunov patch.

Needed for #3961
---
 src/box/index_def.c                 |   2 +
 src/box/index_def.h                 |   6 +
 src/box/lua/schema.lua              |  12 ++
 src/box/lua/space.cc                |   5 +
 src/box/memtx_tree.c                | 192 +++++++++++++++++++++++-
 src/box/memtx_tree_impl.h           |   2 +-
 test/box/tree_pk.result             | 220 ++++++++++++++++++++++++++++
 test/box/tree_pk.test.lua           |  88 +++++++++++
 test/box/tree_pk_multipart.result   | 155 ++++++++++++++++++++
 test/box/tree_pk_multipart.test.lua |  65 ++++++++
 10 files changed, 745 insertions(+), 2 deletions(-)

diff --git a/src/box/index_def.c b/src/box/index_def.c
index c52aa38d1..4d3fadc6e 100644
--- a/src/box/index_def.c
+++ b/src/box/index_def.c
@@ -49,6 +49,7 @@ const struct index_opts index_opts_default = {
 	/* .bloom_fpr           = */ 0.05,
 	/* .lsn                 = */ 0,
 	/* .stat                = */ NULL,
+	/* .hint                = */ false,
 };
 
 const struct opt_def index_opts_reg[] = {
@@ -62,6 +63,7 @@ const struct opt_def index_opts_reg[] = {
 	OPT_DEF("run_size_ratio", OPT_FLOAT, struct index_opts, run_size_ratio),
 	OPT_DEF("bloom_fpr", OPT_FLOAT, struct index_opts, bloom_fpr),
 	OPT_DEF("lsn", OPT_INT64, struct index_opts, lsn),
+	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 7717ecd64..74814bef5 100644
--- a/src/box/index_def.h
+++ b/src/box/index_def.h
@@ -157,6 +157,10 @@ struct index_opts {
 	 * LSN from the time of index creation.
 	 */
 	int64_t lsn;
+	/**
+	 * Use hint optimization for tree index.
+	 */
+	bool hint;
 	/**
 	 * SQL specific statistics concerning tuples
 	 * distribution for query planer. It is automatically
@@ -207,6 +211,8 @@ index_opts_cmp(const struct index_opts *o1, const struct index_opts *o2)
 		return o1->run_size_ratio < o2->run_size_ratio ? -1 : 1;
 	if (o1->bloom_fpr != o2->bloom_fpr)
 		return o1->bloom_fpr < o2->bloom_fpr ? -1 : 1;
+	if (o1->hint != o2->hint)
+		return o1->hint < o2->hint ? -1 : 1;
 	return 0;
 }
 
diff --git a/src/box/lua/schema.lua b/src/box/lua/schema.lua
index 0daf484b8..f05d71875 100644
--- a/src/box/lua/schema.lua
+++ b/src/box/lua/schema.lua
@@ -761,6 +761,7 @@ local index_options = {
     range_size = 'number',
     page_size = 'number',
     bloom_fpr = 'number',
+    hint = 'boolean',
 }
 
 --
@@ -828,6 +829,11 @@ 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, box.space[space_id].name,
+            "hint is only reasonable with memtx tree index")
+    end
 
     local _index = box.space[box.schema.INDEX_ID]
     local _vindex = box.space[box.schema.VINDEX_ID]
@@ -866,6 +872,7 @@ box.schema.index.create = function(space_id, name, options)
             run_count_per_level = options.run_count_per_level,
             run_size_ratio = options.run_size_ratio,
             bloom_fpr = options.bloom_fpr,
+            hint = options.hint,
     }
     local field_type_aliases = {
         num = 'unsigned'; -- Deprecated since 1.7.2
@@ -1018,6 +1025,11 @@ 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, options.name, box.space[space_id].name,
+            "hint is only reasonable with memtx tree index")
+    end
     if options.parts then
         local parts_can_be_simplified
         parts, parts_can_be_simplified =
diff --git a/src/box/lua/space.cc b/src/box/lua/space.cc
index 1f152917e..bf6199ced 100644
--- a/src/box/lua/space.cc
+++ b/src/box/lua/space.cc
@@ -269,6 +269,11 @@ lbox_fillspace(struct lua_State *L, struct space *space, int i)
 			lua_setfield(L, -2, "dimension");
 		}
 
+		if (index_def->type == TREE && index_opts->hint) {
+			lua_pushboolean(L, index_opts->hint);
+			lua_setfield(L, -2, "hint");
+		}
+
 		lua_pushstring(L, index_type_strs[index_def->type]);
 		lua_setfield(L, -2, "type");
 
diff --git a/src/box/memtx_tree.c b/src/box/memtx_tree.c
index 6b22883c2..426a11262 100644
--- a/src/box/memtx_tree.c
+++ b/src/box/memtx_tree.c
@@ -79,8 +79,198 @@ struct memtx_tuple_tree_key_data {
 
 /* }}} */
 
+/* {{{ Memtx hinted and hint_only tree class. *******************/
+
+/**
+ * Struct that is used as a key in BPS tree definition in
+ * metmx_hint_only_tree and metmx_hinted_tree.
+*/
+struct memtx_hinted_tree_key_data {
+	/** Sequence of msgpacked search fields. */
+	const char *key;
+	/** Number of msgpacked search fields. */
+	uint32_t part_count;
+	/**
+	 * Compare hint. Is calculated automatically on 'set'
+	 * operation with memtx_hinted_tree_key_data_set().
+	 */
+	uint64_t hint;
+};
+
+/**
+ * Struct that is used as a key in BPS tree definition in
+ * metmx_hint_only_tree and metmx_hinted_tree.
+ */
+struct memtx_hinted_tree_data {
+	/** Tuple this node is representing. */
+	struct tuple *tuple;
+	/**
+	 * Compare hint. Is calculated automatically on 'set'
+	 * operation with memtx_hinted_tree_data_set().
+	 */
+	uint64_t hint;
+};
+
+/**
+ * Compare memtx_hinted_tree records.
+ */
+static int
+memtx_hinted_tree_data_cmp(struct memtx_hinted_tree_data *a,
+			   struct memtx_hinted_tree_data *b,
+			   struct key_def *key_def)
+{
+	if (a->hint != b->hint)
+		return a->hint < b->hint ? -1 : 1;
+	return tuple_compare(a->tuple, b->tuple, key_def);
+}
+
+/**
+ * Compare memtx_hinted_tree record with key.
+ */
+static int
+memtx_hinted_tree_data_cmp_with_key(struct memtx_hinted_tree_data *a,
+				    struct memtx_hinted_tree_key_data *key,
+				    struct key_def *key_def)
+{
+	if (a->hint != key->hint)
+		return a->hint < key->hint ? -1 : 1;
+	return tuple_compare_with_key(a->tuple, key->key, key->part_count,
+				      key_def);
+}
+
+/**
+ * Initialize memtx_hinted_tree or memtx_hint_only_tree record
+ * with tuple and recalculate internal hint field.
+ */
+static void
+memtx_hinted_tree_data_set(struct memtx_hinted_tree_data *data,
+			   struct tuple *tuple, struct key_def *key_def)
+{
+	data->tuple = tuple;
+	data->hint = tuple != NULL ? tuple_hint(tuple, key_def) : 0;
+}
+
+/**
+ * Initialize memtx_hinted_tree or memtx_hint_only_tree key with
+ * key raw and part count and recalculate internal hint field.
+ */
+static void
+memtx_hinted_tree_key_data_set(struct memtx_hinted_tree_key_data *key_data,
+			       const char *key, uint32_t part_count,
+			       struct key_def *key_def)
+{
+	key_data->key = key;
+	key_data->part_count = part_count;
+	key_data->hint = key != NULL && part_count > 0 ?
+			 key_hint(key, key_def) : 0;
+}
+
+#define MEMTX_TREE_NAME metmx_hinted_tree
+#define memtx_tree_elem struct memtx_hinted_tree_data
+#define memtx_tree_key struct memtx_hinted_tree_key_data
+#define MEMTX_TREE_ELEM_EQUAL(elem_a_ptr, elem_b_ptr)				\
+	((elem_a_ptr)->tuple == (elem_b_ptr)->tuple)
+#define MEMTX_TREE_ELEM_CMP(elem_a_ptr, elem_b_ptr, key_def)			\
+	memtx_hinted_tree_data_cmp(elem_a_ptr, elem_b_ptr, key_def)
+#define MEMTX_TREE_ELEM_WITH_KEY_CMP(elem_ptr, key_ptr, key_def)		\
+	memtx_hinted_tree_data_cmp_with_key(elem_ptr, key_ptr, key_def)
+#define MEMTX_TREE_ELEM_SET(elem_ptr, tuple, key_def)				\
+	memtx_hinted_tree_data_set(elem_ptr, tuple, key_def)
+#define MEMTX_TREE_KEY_SET(key_ptr, key_val, part_count_val, key_def)		\
+	memtx_hinted_tree_key_data_set(key_ptr, key_val, part_count_val,	\
+				       key_def)
+#define MEMTX_TREE_ELEM_GET(elem_ptr) ((elem_ptr)->tuple)
+#define MEMTX_TREE_KEY_GET(key_ptr, part_count_ptr)				\
+	({*part_count_ptr = (key_ptr)->part_count; (key_ptr)->key;})
+
+#include "memtx_tree_impl.h"
+
+#undef memtx_tree_key
+#undef memtx_tree_elem
+#undef MEMTX_TREE_KEY_GET
+#undef MEMTX_TREE_ELEM_GET
+#undef MEMTX_TREE_KEY_SET
+#undef MEMTX_TREE_ELEM_SET
+#undef MEMTX_TREE_ELEM_WITH_KEY_CMP
+#undef MEMTX_TREE_ELEM_CMP
+#undef MEMTX_TREE_ELEM_EQUAL
+#undef memtx_tree_key
+#undef memtx_tree_elem
+#undef MEMTX_TREE_NAME
+
+/**
+ * Compare memtx_hinted_tree records.
+ */
+static inline int
+memtx_hint_only_tree_data_cmp(struct memtx_hinted_tree_data *a,
+			      struct memtx_hinted_tree_data *b,
+			      struct key_def *key_def)
+{
+	(void)key_def;
+	assert(key_def->part_count == 1 &&
+	       (key_def->parts->type == FIELD_TYPE_UNSIGNED ||
+	        key_def->parts->type == FIELD_TYPE_INTEGER));
+	return a->hint < b->hint ? -1 : a->hint > b->hint ? 1 : 0;
+}
+
+/**
+ * Compare memtx_hinted_tree record with key.
+ */
+static inline int
+memtx_hint_only_tree_data_cmp_with_key(struct memtx_hinted_tree_data *a,
+				       struct memtx_hinted_tree_key_data *key,
+				       struct key_def *key_def)
+{
+	(void)key_def;
+	assert(key_def->part_count == 1 &&
+	       (key_def->parts->type == FIELD_TYPE_UNSIGNED ||
+	        key_def->parts->type == FIELD_TYPE_INTEGER));
+	return a->hint < key->hint ? -1 : a->hint > key->hint ? 1 : 0;
+}
+
+#define MEMTX_TREE_NAME metmx_hint_only_tree
+#define memtx_tree_elem struct memtx_hinted_tree_data
+#define memtx_tree_key struct memtx_hinted_tree_key_data
+#define MEMTX_TREE_ELEM_EQUAL(elem_a_ptr, elem_b_ptr)				\
+	((elem_a_ptr)->tuple == (elem_b_ptr)->tuple)
+#define MEMTX_TREE_ELEM_CMP(elem_a_ptr, elem_b_ptr, key_def)			\
+	memtx_hint_only_tree_data_cmp(elem_a_ptr, elem_b_ptr, key_def)
+#define MEMTX_TREE_ELEM_WITH_KEY_CMP(elem_ptr, key_ptr, key_def)		\
+	memtx_hint_only_tree_data_cmp_with_key(elem_ptr, key_ptr, key_def)
+#define MEMTX_TREE_ELEM_SET(elem_ptr, tuple, key_def)				\
+	memtx_hinted_tree_data_set(elem_ptr, tuple, key_def)
+#define MEMTX_TREE_KEY_SET(key_ptr, key_val, part_count_val, key_def)		\
+	memtx_hinted_tree_key_data_set(key_ptr, key_val, part_count_val,	\
+				       key_def)
+#define MEMTX_TREE_ELEM_GET(elem_ptr) ((elem_ptr)->tuple)
+#define MEMTX_TREE_KEY_GET(key_ptr, part_count_ptr)				\
+	({*part_count_ptr = (key_ptr)->part_count; (key_ptr)->key;})
+
+#include "memtx_tree_impl.h"
+
+#undef memtx_tree_key
+#undef memtx_tree_elem
+#undef MEMTX_TREE_KEY_GET
+#undef MEMTX_TREE_ELEM_GET
+#undef MEMTX_TREE_KEY_SET
+#undef MEMTX_TREE_ELEM_SET
+#undef MEMTX_TREE_ELEM_WITH_KEY_CMP
+#undef MEMTX_TREE_ELEM_CMP
+#undef MEMTX_TREE_ELEM_EQUAL
+#undef memtx_tree_key
+#undef memtx_tree_elem
+#undef MEMTX_TREE_NAME
+
+/* }}} */
+
 struct index *
 memtx_tree_index_new(struct memtx_engine *memtx, struct index_def *def)
 {
-	return metmx_tuple_tree_index_new(memtx, def);
+	if (!def->opts.hint)
+		return metmx_tuple_tree_index_new(memtx, def);
+	if (def->cmp_def->part_count == 1 &&
+	    (def->cmp_def->parts->type == FIELD_TYPE_UNSIGNED ||
+	     def->cmp_def->parts->type == FIELD_TYPE_INTEGER))
+		return metmx_hint_only_tree_index_new(memtx, def);
+	return metmx_hinted_tree_index_new(memtx, def);
 }
diff --git a/src/box/memtx_tree_impl.h b/src/box/memtx_tree_impl.h
index 20b88ad3b..9a5122bdd 100644
--- a/src/box/memtx_tree_impl.h
+++ b/src/box/memtx_tree_impl.h
@@ -78,7 +78,7 @@
  * mempool_create. This is the size of the block that will be
  * allocated for each iterator.
  */
-#define MEMTX_TREE_ITERATOR_SIZE (136)
+#define MEMTX_TREE_ITERATOR_SIZE (152)
 
 #define bps_tree_elem_t memtx_tree_elem
 #define bps_tree_key_t memtx_tree_key *
diff --git a/test/box/tree_pk.result b/test/box/tree_pk.result
index df3c78bed..7c7aa7f7e 100644
--- a/test/box/tree_pk.result
+++ b/test/box/tree_pk.result
@@ -852,3 +852,223 @@ box.internal.collation.drop('test')
 box.internal.collation.drop('test-ci')
 ---
 ...
+--
+-- gh-3961: Hint option for memtx tree index.
+--
+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: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
+---
+- null
+...
+s2 = box.schema.space.create('test2')
+---
+...
+s2:create_index('test', {type = 'tree', hint = true}).hint
+---
+- true
+...
+N = 2000
+---
+...
+for i = 1,N do local v = math.random(10 * N) 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 * 10 do if diff(s1:get{i}, s2:get{i}) then good = false end end
+---
+...
+good
+---
+- 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
+---
+- null
+...
+s2 = box.schema.space.create('test2')
+---
+...
+s2:create_index('test', {type = 'tree', parts = {1, 'str'}, hint = true}).hint
+---
+- true
+...
+N = 1000
+---
+...
+for i = 1,N do local v = ''..math.random(10 * N) 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 * 10 do v = ''..i if diff(s1:get{v}, s2:get{v}) then good = false end end
+---
+...
+good
+---
+- 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_ci'}}, hint = false}).hint
+---
+- null
+...
+s2 = box.schema.space.create('test2')
+---
+...
+s2:create_index('test', {type = 'tree', parts = {{1, 'str', collation = 'unicode_ci'}}, hint = true}).hint
+---
+- true
+...
+N = 500
+---
+...
+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:drop()
+---
+...
+s2:drop()
+---
+...
diff --git a/test/box/tree_pk.test.lua b/test/box/tree_pk.test.lua
index 1190ab424..3edbdda57 100644
--- a/test/box/tree_pk.test.lua
+++ b/test/box/tree_pk.test.lua
@@ -301,3 +301,91 @@ s:drop()
 
 box.internal.collation.drop('test')
 box.internal.collation.drop('test-ci')
+
+--
+-- gh-3961: Hint option for memtx tree index.
+--
+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: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 = true}).hint
+
+N = 2000
+for i = 1,N do local v = math.random(10 * N) 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 * 10 do if diff(s1:get{i}, s2:get{i}) then good = false end end
+good
+
+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 = true}).hint
+
+N = 1000
+for i = 1,N do local v = ''..math.random(10 * N) 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 * 10 do v = ''..i if diff(s1:get{v}, s2:get{v}) then good = false end end
+good
+
+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_ci'}}, hint = false}).hint
+s2 = box.schema.space.create('test2')
+s2:create_index('test', {type = 'tree', parts = {{1, 'str', collation = 'unicode_ci'}}, hint = true}).hint
+
+N = 500
+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:drop()
+s2:drop()
diff --git a/test/box/tree_pk_multipart.result b/test/box/tree_pk_multipart.result
index 93219f666..e95272feb 100644
--- a/test/box/tree_pk_multipart.result
+++ b/test/box/tree_pk_multipart.result
@@ -542,3 +542,158 @@ space:drop()
 space = nil
 ---
 ...
+--
+-- gh-3961: Hint option for memtx tree index.
+--
+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
+---
+- null
+...
+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
+---
+- null
+...
+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 7d3405ffe..bcb9dc541 100644
--- a/test/box/tree_pk_multipart.test.lua
+++ b/test/box/tree_pk_multipart.test.lua
@@ -194,3 +194,68 @@ test_run:cmd("setopt delimiter ''");
 space:drop()
 
 space = nil
+
+--
+-- gh-3961: Hint option for memtx tree index.
+--
+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.20.1