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

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

[Kirill Shcherbatov]

Reworked memtx tree to use 'tuple hints'.
Introduced special functions for retrieve tuple hints for a particular key_def.
Hint is an integer that can be used for tuple comparison optimization:
if a hint of one tuple is less than a hint of another then the first
tuple is definitely less than the second; only if hints are equal
tuple_compare must be called for getting comparison result.

Hints are only useful when:

* they are precalculated and stored along with the tuple;
  calculation is not cheap (cheaper than tuple_compare btw) but
  precalculated hints allow to compare tuples without even fetching
  tuple data.
* first part of key_def is 'string', 'unsigned' or 'integer'
* since hint is calculated using only the first part of key_def
  (and only first several characters if it is a string) this part
  must be different with high probability for every tuple pair.

Enabled hint option improve performance on average by 15%; Select operations
are significantly accelerated (there are scenarios in which the difference
reaches 200-250%).

Also appended multikey index prototype. I am going to try to rework field_map
initialization and resend last letter a bit later.


Changes in version 5:
  -- Code rewritten without classes and macro definitions using vtabs.
  -- Appended multikey index prototype.

Changes in version 4:
  -- Code rewritten in C++ with classes. This perform a better maintainability
     in future.
  -- New hints for number and boolean types. Memtx Tree is always hinted now.
  -- INVALID_HINT marker. We need it because double have strange types
     NaN and so on that musn't be a problem of hints business.
  -- After part of code was merged, rebased patch.

Changes in version 3:
  -- Better-structured code
  -- Refactored all memtx indexes to use shared mempool of default size
  -- Refactored all memtx indexes to hide implementation details from headers
  -- Moved all hints-related code to corresponding module
  -- Better types names, better comments
  -- Fixed potential bug with iterators: introduce MEMTX_TREE_IDENTICAL macro
  -- Fix inaccurate MEMTX_TREE_ELEM_SET usage in memtx_tree_index_build_next
  -- Changed approach to calculate string hints
  -- Introduce separate hint for binary collation type

Changes in version 2:
  -- Splitted patch to parts in other way to decrease diff
  -- Hints are not index option anymore, but default where possible
  -- Removed hints for numeric types

v4: https://www.freelists.org/post/tarantool-patches/PATCH-v4-07-box-introduce-hint-option-for-memtx-tree-index
v3: https://www.freelists.org/post/tarantool-patches/PATCH-v3-07-box-introduce-hint-option-for-memtx-tree-index
v2: https://www.freelists.org/post/tarantool-patches/PATCH-v2-04-box-introduce-hint-option-for-memtx-tree-index
v1: https://www.freelists.org/post/tarantool-patches/PATCH-v1-04-box-introduce-hint-option-for-memtx-tree-index

https://github.com/tarantool/tarantool/tree/kshch/gh-3961-tuple-hints
https://github.com/tarantool/tarantool/issues/3961

Kirill Shcherbatov (4):
  memtx: rework memtx_tree to store arbitrary nodes
  memtx: introduce tuple compare hint
  box: move offset_slot init to tuple_format_add_field
  box: introduce multikey indexes

 src/box/key_def.c         |  20 ++
 src/box/key_def.h         | 130 ++++++++++
 src/box/memtx_tree.c      | 470 +++++++++++++++++++++++++---------
 src/box/tuple.c           |   8 +-
 src/box/tuple.h           | 130 ++++++++--
 src/box/tuple_compare.cc  | 514 +++++++++++++++++++++++++++++++++++++-
 src/box/tuple_compare.h   |   7 +
 src/box/tuple_format.c    | 210 +++++++++++++---
 src/lib/coll/coll.c       |  33 +++
 src/lib/coll/coll.h       |   4 +
 test/engine/json.result   |  80 +++++-
 test/engine/json.test.lua |  20 ++
 12 files changed, 1446 insertions(+), 180 deletions(-)

-- 
2.21.0

[PATCH v5 1/4] memtx: rework memtx_tree to store arbitrary nodes

[Kirill Shcherbatov]

Reworked memtx_tree class to use arbitrary containers as a tree
nodes. This makes possible to implement tuple hints in subsequent
patches.

Needed for #3961
---
 src/box/memtx_tree.c | 289 ++++++++++++++++++++++++++-----------------
 1 file changed, 178 insertions(+), 111 deletions(-)

diff --git a/src/box/memtx_tree.c b/src/box/memtx_tree.c
index 250df7f2d..688f09597 100644
--- a/src/box/memtx_tree.c
+++ b/src/box/memtx_tree.c
@@ -50,30 +50,70 @@ struct memtx_tree_key_data {
 };
 
 /**
- * BPS tree element vs key comparator.
- * Defined in header in order to allow compiler to inline it.
- * @param tuple - tuple to compare.
- * @param key_data - key to compare with.
- * @param def - key definition.
- * @retval 0  if tuple == key in terms of def.
- * @retval <0 if tuple < key in terms of def.
- * @retval >0 if tuple > key in terms of def.
+ * Struct that is used as a elem in BPS tree definition.
  */
-static int
-memtx_tree_compare_key(const struct tuple *tuple,
-		       const struct memtx_tree_key_data *key_data,
-		       struct key_def *def)
+struct memtx_tree_data {
+	/* Tuple that this node is represents. */
+	struct tuple *tuple;
+};
+
+/**
+ * Test whether BPS tree elements are identical i.e. represents
+ * the same tuple and metadata.
+ * @param a - First BPS tree element to compare.
+ * @param b - Second BPS tree element to compare.
+ * @retval true - When elements a and b are identical.
+ * @retval fa;se - Otherwise.
+ */
+static bool
+memtx_tree_data_identical(const struct memtx_tree_data *a,
+			  const struct memtx_tree_data *b)
 {
-	return tuple_compare_with_key(tuple, key_data->key,
-				      key_data->part_count, def);
+	return a->tuple == b->tuple;
+}
+
+/**
+ * BPS tree element clear.
+ * @param data - BPS tree element to clear.
+ */
+static void
+memtx_tree_data_clear(struct memtx_tree_data *data)
+{
+	data->tuple = NULL;
+}
+
+/**
+ * Initialize BPS tree element.
+ */
+static void
+memtx_tree_data_set(struct memtx_tree_data *data, struct tuple *tuple,
+		    struct key_def *key_def)
+{
+	(void)key_def;
+	data->tuple = tuple;
+}
+
+/**
+ * Initialize BPS tree key element.
+ */
+static void
+memtx_tree_key_data_set(struct memtx_tree_key_data *key_data, const char *key,
+			uint32_t part_count, struct key_def *key_def)
+{
+	(void)key_def;
+	key_data->key = key;
+	key_data->part_count = part_count;
 }
 
 #define BPS_TREE_NAME memtx_tree
 #define BPS_TREE_BLOCK_SIZE (512)
 #define BPS_TREE_EXTENT_SIZE MEMTX_EXTENT_SIZE
-#define BPS_TREE_COMPARE(a, b, arg) tuple_compare(a, b, arg)
-#define BPS_TREE_COMPARE_KEY(a, b, arg) memtx_tree_compare_key(a, b, arg)
-#define bps_tree_elem_t struct tuple *
+#define BPS_TREE_COMPARE(a, b, arg)\
+	tuple_compare((&a)->tuple, (&b)->tuple, arg)
+#define BPS_TREE_COMPARE_KEY(a, b, arg)\
+	tuple_compare_with_key((&a)->tuple, (b)->key, (b)->part_count, arg)
+#define BPS_TREE_IDENTICAL(a, b) memtx_tree_data_identical(&a, &b)
+#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 *
 
@@ -84,6 +124,7 @@ memtx_tree_compare_key(const struct tuple *tuple,
 #undef BPS_TREE_EXTENT_SIZE
 #undef BPS_TREE_COMPARE
 #undef BPS_TREE_COMPARE_KEY
+#undef BPS_TREE_IDENTICAL
 #undef bps_tree_elem_t
 #undef bps_tree_key_t
 #undef bps_tree_arg_t
@@ -91,7 +132,7 @@ memtx_tree_compare_key(const struct tuple *tuple,
 struct memtx_tree_index {
 	struct index base;
 	struct memtx_tree tree;
-	struct tuple **build_array;
+	struct memtx_tree_data *build_array;
 	size_t build_array_size, build_array_alloc_size;
 	struct memtx_gc_task gc_task;
 	struct memtx_tree_iterator gc_iterator;
@@ -102,8 +143,10 @@ struct memtx_tree_index {
 static int
 memtx_tree_qcompare(const void* a, const void *b, void *c)
 {
-	return tuple_compare(*(struct tuple **)a,
-		*(struct tuple **)b, (struct key_def *)c);
+	const struct memtx_tree_data *data_a = a;
+	const struct memtx_tree_data *data_b = b;
+	struct key_def *key_def = c;
+	return tuple_compare(data_a->tuple, data_b->tuple, key_def);
 }
 
 /* {{{ MemtxTree Iterators ****************************************/
@@ -114,7 +157,7 @@ struct tree_iterator {
 	struct memtx_tree_iterator tree_iterator;
 	enum iterator_type type;
 	struct memtx_tree_key_data key_data;
-	struct tuple *current_tuple;
+	struct memtx_tree_data current;
 	/** Memory pool the iterator was allocated from. */
 	struct mempool *pool;
 };
@@ -137,8 +180,9 @@ static void
 tree_iterator_free(struct iterator *iterator)
 {
 	struct tree_iterator *it = tree_iterator(iterator);
-	if (it->current_tuple != NULL)
-		tuple_unref(it->current_tuple);
+	struct tuple *tuple = it->current.tuple;
+	if (tuple != NULL)
+		tuple_unref(tuple);
 	mempool_free(it->pool, it);
 }
 
@@ -153,25 +197,28 @@ tree_iterator_dummie(struct iterator *iterator, struct tuple **ret)
 static int
 tree_iterator_next(struct iterator *iterator, struct tuple **ret)
 {
-	struct tuple **res;
 	struct tree_iterator *it = tree_iterator(iterator);
-	assert(it->current_tuple != NULL);
-	struct tuple **check = memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
-	if (check == NULL || *check != it->current_tuple)
+	assert(it->current.tuple != NULL);
+	struct memtx_tree_data *check =
+		memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
+	if (check == NULL || !memtx_tree_data_identical(check, &it->current)) {
 		it->tree_iterator =
-			memtx_tree_upper_bound_elem(it->tree, it->current_tuple,
+			memtx_tree_upper_bound_elem(it->tree, it->current,
 						    NULL);
-	else
+	} else {
 		memtx_tree_iterator_next(it->tree, &it->tree_iterator);
-	tuple_unref(it->current_tuple);
-	it->current_tuple = NULL;
-	res = memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
+	}
+	tuple_unref(it->current.tuple);
+	struct memtx_tree_data *res =
+		memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
 	if (res == NULL) {
 		iterator->next = tree_iterator_dummie;
+		memtx_tree_data_clear(&it->current);
 		*ret = NULL;
 	} else {
-		*ret = it->current_tuple = *res;
-		tuple_ref(it->current_tuple);
+		*ret = res->tuple;
+		tuple_ref(*ret);
+		it->current = *res;
 	}
 	return 0;
 }
@@ -180,22 +227,25 @@ static int
 tree_iterator_prev(struct iterator *iterator, struct tuple **ret)
 {
 	struct tree_iterator *it = tree_iterator(iterator);
-	assert(it->current_tuple != NULL);
-	struct tuple **check = memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
-	if (check == NULL || *check != it->current_tuple)
+	assert(it->current.tuple != NULL);
+	struct memtx_tree_data *check =
+		memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
+	if (check == NULL || !memtx_tree_data_identical(check, &it->current)) {
 		it->tree_iterator =
-			memtx_tree_lower_bound_elem(it->tree, it->current_tuple,
-						    NULL);
+			memtx_tree_lower_bound_elem(it->tree, it->current, NULL);
+	}
 	memtx_tree_iterator_prev(it->tree, &it->tree_iterator);
-	tuple_unref(it->current_tuple);
-	it->current_tuple = NULL;
-	struct tuple **res = memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
+	tuple_unref(it->current.tuple);
+	struct memtx_tree_data *res =
+		memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
 	if (!res) {
 		iterator->next = tree_iterator_dummie;
+		memtx_tree_data_clear(&it->current);
 		*ret = NULL;
 	} else {
-		*ret = it->current_tuple = *res;
-		tuple_ref(it->current_tuple);
+		*ret = res->tuple;
+		tuple_ref(*ret);
+		it->current = *res;
 	}
 	return 0;
 }
@@ -204,27 +254,30 @@ static int
 tree_iterator_next_equal(struct iterator *iterator, struct tuple **ret)
 {
 	struct tree_iterator *it = tree_iterator(iterator);
-	assert(it->current_tuple != NULL);
-	struct tuple **check = memtx_tree_iterator_get_elem(it->tree,
-						&it->tree_iterator);
-	if (check == NULL || *check != it->current_tuple)
+	assert(it->current.tuple != NULL);
+	struct memtx_tree_data *check =
+		memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
+	if (check == NULL || !memtx_tree_data_identical(check, &it->current)) {
 		it->tree_iterator =
-			memtx_tree_upper_bound_elem(it->tree, it->current_tuple,
-						    NULL);
-	else
+			memtx_tree_upper_bound_elem(it->tree, it->current, NULL);
+	} else {
 		memtx_tree_iterator_next(it->tree, &it->tree_iterator);
-	tuple_unref(it->current_tuple);
-	it->current_tuple = NULL;
-	struct tuple **res = memtx_tree_iterator_get_elem(it->tree,
-						&it->tree_iterator);
+	}
+	tuple_unref(it->current.tuple);
+	struct memtx_tree_data *res =
+		memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
 	/* Use user key def to save a few loops. */
-	if (!res || memtx_tree_compare_key(*res, &it->key_data,
-					   it->index_def->key_def) != 0) {
+	if (res == NULL ||
+	    tuple_compare_with_key(res->tuple, it->key_data.key,
+				   it->key_data.part_count,
+				   it->index_def->key_def) != 0) {
 		iterator->next = tree_iterator_dummie;
+		memtx_tree_data_clear(&it->current);
 		*ret = NULL;
 	} else {
-		*ret = it->current_tuple = *res;
-		tuple_ref(it->current_tuple);
+		*ret = res->tuple;
+		tuple_ref(*ret);
+		it->current = *res;
 	}
 	return 0;
 }
@@ -233,26 +286,29 @@ static int
 tree_iterator_prev_equal(struct iterator *iterator, struct tuple **ret)
 {
 	struct tree_iterator *it = tree_iterator(iterator);
-	assert(it->current_tuple != NULL);
-	struct tuple **check = memtx_tree_iterator_get_elem(it->tree,
-						&it->tree_iterator);
-	if (check == NULL || *check != it->current_tuple)
+	assert(it->current.tuple != NULL);
+	struct memtx_tree_data *check =
+		memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
+	if (check == NULL || !memtx_tree_data_identical(check, &it->current)) {
 		it->tree_iterator =
-			memtx_tree_lower_bound_elem(it->tree, it->current_tuple,
-						    NULL);
+			memtx_tree_lower_bound_elem(it->tree, it->current, NULL);
+	}
 	memtx_tree_iterator_prev(it->tree, &it->tree_iterator);
-	tuple_unref(it->current_tuple);
-	it->current_tuple = NULL;
-	struct tuple **res = memtx_tree_iterator_get_elem(it->tree,
-						&it->tree_iterator);
+	tuple_unref(it->current.tuple);
+	struct memtx_tree_data *res =
+		memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
 	/* Use user key def to save a few loops. */
-	if (!res || memtx_tree_compare_key(*res, &it->key_data,
-					   it->index_def->key_def) != 0) {
+	if (res == NULL ||
+	    tuple_compare_with_key(res->tuple, it->key_data.key,
+				   it->key_data.part_count,
+				   it->index_def->key_def) != 0) {
 		iterator->next = tree_iterator_dummie;
+		memtx_tree_data_clear(&it->current);
 		*ret = NULL;
 	} else {
-		*ret = it->current_tuple = *res;
-		tuple_ref(it->current_tuple);
+		*ret = res->tuple;
+		tuple_ref(*ret);
+		it->current = *res;
 	}
 	return 0;
 }
@@ -260,7 +316,7 @@ tree_iterator_prev_equal(struct iterator *iterator, struct tuple **ret)
 static void
 tree_iterator_set_next_method(struct tree_iterator *it)
 {
-	assert(it->current_tuple != NULL);
+	assert(it->current.tuple != NULL);
 	switch (it->type) {
 	case ITER_EQ:
 		it->base.next = tree_iterator_next_equal;
@@ -294,7 +350,7 @@ tree_iterator_start(struct iterator *iterator, struct tuple **ret)
 	const struct memtx_tree *tree = it->tree;
 	enum iterator_type type = it->type;
 	bool exact = false;
-	assert(it->current_tuple == NULL);
+	assert(it->current.tuple == NULL);
 	if (it->key_data.key == 0) {
 		if (iterator_type_is_reverse(it->type))
 			it->tree_iterator = memtx_tree_iterator_last(tree);
@@ -331,12 +387,13 @@ tree_iterator_start(struct iterator *iterator, struct tuple **ret)
 		}
 	}
 
-	struct tuple **res = memtx_tree_iterator_get_elem(it->tree,
-						&it->tree_iterator);
+	struct memtx_tree_data *res =
+		memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
 	if (!res)
 		return 0;
-	*ret = it->current_tuple = *res;
-	tuple_ref(it->current_tuple);
+	*ret = res->tuple;
+	tuple_ref(*ret);
+	it->current = *res;
 	tree_iterator_set_next_method(it);
 	return 0;
 }
@@ -390,9 +447,10 @@ memtx_tree_index_gc_run(struct memtx_gc_task *task, bool *done)
 
 	unsigned int loops = 0;
 	while (!memtx_tree_iterator_is_invalid(itr)) {
-		struct tuple *tuple = *memtx_tree_iterator_get_elem(tree, itr);
+		struct memtx_tree_data *res =
+			memtx_tree_iterator_get_elem(tree, itr);
 		memtx_tree_iterator_next(tree, itr);
-		tuple_unref(tuple);
+		tuple_unref(res->tuple);
 		if (++loops >= YIELD_LOOPS) {
 			*done = false;
 			return;
@@ -470,8 +528,8 @@ static int
 memtx_tree_index_random(struct index *base, uint32_t rnd, struct tuple **result)
 {
 	struct memtx_tree_index *index = (struct memtx_tree_index *)base;
-	struct tuple **res = memtx_tree_random(&index->tree, rnd);
-	*result = res != NULL ? *res : NULL;
+	struct memtx_tree_data *res = memtx_tree_random(&index->tree, rnd);
+	*result = res != NULL ? res->tuple : NULL;
 	return 0;
 }
 
@@ -492,10 +550,10 @@ memtx_tree_index_get(struct index *base, const char *key,
 	       part_count == base->def->key_def->part_count);
 	struct memtx_tree_index *index = (struct memtx_tree_index *)base;
 	struct memtx_tree_key_data key_data;
-	key_data.key = key;
-	key_data.part_count = part_count;
-	struct tuple **res = memtx_tree_find(&index->tree, &key_data);
-	*result = res != NULL ? *res : NULL;
+	struct key_def *cmp_def = memtx_tree_index_cmp_def(index);
+	memtx_tree_key_data_set(&key_data, key, part_count, cmp_def);
+	struct memtx_tree_data *res = memtx_tree_find(&index->tree, &key_data);
+	*result = res != NULL ? res->tuple : NULL;
 	return 0;
 }
 
@@ -505,12 +563,16 @@ memtx_tree_index_replace(struct index *base, struct tuple *old_tuple,
 			 struct tuple **result)
 {
 	struct memtx_tree_index *index = (struct memtx_tree_index *)base;
+	struct key_def *key_def = index->tree.arg;
 	if (new_tuple) {
-		struct tuple *dup_tuple = NULL;
+		struct memtx_tree_data new_data;
+		memtx_tree_data_set(&new_data, new_tuple, key_def);
+		struct memtx_tree_data dup_data;
+		memtx_tree_data_clear(&dup_data);
 
 		/* Try to optimistically replace the new_tuple. */
-		int tree_res = memtx_tree_insert(&index->tree,
-						 new_tuple, &dup_tuple);
+		int tree_res = memtx_tree_insert(&index->tree, new_data,
+						 &dup_data);
 		if (tree_res) {
 			diag_set(OutOfMemory, MEMTX_EXTENT_SIZE,
 				 "memtx_tree_index", "replace");
@@ -518,24 +580,26 @@ memtx_tree_index_replace(struct index *base, struct tuple *old_tuple,
 		}
 
 		uint32_t errcode = replace_check_dup(old_tuple,
-						     dup_tuple, mode);
+						     dup_data.tuple, mode);
 		if (errcode) {
-			memtx_tree_delete(&index->tree, new_tuple);
-			if (dup_tuple)
-				memtx_tree_insert(&index->tree, dup_tuple, 0);
+			memtx_tree_delete(&index->tree, new_data);
+			if (dup_data.tuple != NULL)
+				memtx_tree_insert(&index->tree, dup_data, NULL);
 			struct space *sp = space_cache_find(base->def->space_id);
 			if (sp != NULL)
 				diag_set(ClientError, errcode, base->def->name,
 					 space_name(sp));
 			return -1;
 		}
-		if (dup_tuple) {
-			*result = dup_tuple;
+		if (dup_data.tuple != NULL) {
+			*result = dup_data.tuple;
 			return 0;
 		}
 	}
 	if (old_tuple) {
-		memtx_tree_delete(&index->tree, old_tuple);
+		struct memtx_tree_data old_data;
+		memtx_tree_data_set(&old_data, old_tuple, key_def);
+		memtx_tree_delete(&index->tree, old_data);
 	}
 	*result = old_tuple;
 	return 0;
@@ -575,12 +639,12 @@ memtx_tree_index_create_iterator(struct index *base, enum iterator_type type,
 	it->base.next = tree_iterator_start;
 	it->base.free = tree_iterator_free;
 	it->type = type;
-	it->key_data.key = key;
-	it->key_data.part_count = part_count;
+	struct key_def *cmp_def = memtx_tree_index_cmp_def(index);
+	memtx_tree_key_data_set(&it->key_data, key, part_count, cmp_def);
 	it->index_def = base->def;
 	it->tree = &index->tree;
 	it->tree_iterator = memtx_tree_invalid_iterator();
-	it->current_tuple = NULL;
+	memtx_tree_data_clear(&it->current);
 	return (struct iterator *)it;
 }
 
@@ -598,8 +662,8 @@ memtx_tree_index_reserve(struct index *base, uint32_t size_hint)
 	struct memtx_tree_index *index = (struct memtx_tree_index *)base;
 	if (size_hint < index->build_array_alloc_size)
 		return 0;
-	struct tuple **tmp = (struct tuple **)realloc(index->build_array,
-						      size_hint * sizeof(*tmp));
+	struct memtx_tree_data *tmp =
+		realloc(index->build_array, size_hint * sizeof(*tmp));
 	if (tmp == NULL) {
 		diag_set(OutOfMemory, size_hint * sizeof(*tmp),
 			 "memtx_tree_index", "reserve");
@@ -614,21 +678,23 @@ static int
 memtx_tree_index_build_next(struct index *base, struct tuple *tuple)
 {
 	struct memtx_tree_index *index = (struct memtx_tree_index *)base;
+	struct key_def *key_def = index->tree.arg;
 	if (index->build_array == NULL) {
-		index->build_array = (struct tuple **)malloc(MEMTX_EXTENT_SIZE);
+		index->build_array =
+			(struct memtx_tree_data *)malloc(MEMTX_EXTENT_SIZE);
 		if (index->build_array == NULL) {
 			diag_set(OutOfMemory, MEMTX_EXTENT_SIZE,
 				 "memtx_tree_index", "build_next");
 			return -1;
 		}
 		index->build_array_alloc_size =
-			MEMTX_EXTENT_SIZE / sizeof(struct tuple*);
+			MEMTX_EXTENT_SIZE / sizeof(index->build_array[0]);
 	}
 	assert(index->build_array_size <= index->build_array_alloc_size);
 	if (index->build_array_size == index->build_array_alloc_size) {
 		index->build_array_alloc_size = index->build_array_alloc_size +
 					index->build_array_alloc_size / 2;
-		struct tuple **tmp = (struct tuple **)
+		struct memtx_tree_data *tmp =
 			realloc(index->build_array,
 				index->build_array_alloc_size * sizeof(*tmp));
 		if (tmp == NULL) {
@@ -638,7 +704,9 @@ memtx_tree_index_build_next(struct index *base, struct tuple *tuple)
 		}
 		index->build_array = tmp;
 	}
-	index->build_array[index->build_array_size++] = tuple;
+	struct memtx_tree_data *elem =
+		&index->build_array[index->build_array_size++];
+	memtx_tree_data_set(elem, tuple, key_def);
 	return 0;
 }
 
@@ -648,8 +716,7 @@ memtx_tree_index_end_build(struct index *base)
 	struct memtx_tree_index *index = (struct memtx_tree_index *)base;
 	struct key_def *cmp_def = memtx_tree_index_cmp_def(index);
 	qsort_arg(index->build_array, index->build_array_size,
-		  sizeof(struct tuple *),
-		  memtx_tree_qcompare, cmp_def);
+		  sizeof(index->build_array[0]), memtx_tree_qcompare, cmp_def);
 	memtx_tree_build(&index->tree, index->build_array,
 			 index->build_array_size);
 
@@ -682,12 +749,12 @@ tree_snapshot_iterator_next(struct snapshot_iterator *iterator, uint32_t *size)
 	assert(iterator->free == tree_snapshot_iterator_free);
 	struct tree_snapshot_iterator *it =
 		(struct tree_snapshot_iterator *)iterator;
-	struct tuple **res = memtx_tree_iterator_get_elem(it->tree,
-						&it->tree_iterator);
+	struct memtx_tree_data *res =
+		memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
 	if (res == NULL)
 		return NULL;
 	memtx_tree_iterator_next(it->tree, &it->tree_iterator);
-	return tuple_data_range(*res, size);
+	return tuple_data_range(res->tuple, size);
 }
 
 /**
-- 
2.21.0

Re: [PATCH v5 1/4] memtx: rework memtx_tree to store arbitrary nodes

[Vladimir Davydov]

On Thu, Mar 07, 2019 at 12:44:05PM +0300, Kirill Shcherbatov wrote:
> Reworked memtx_tree class to use arbitrary containers as a tree
> nodes. This makes possible to implement tuple hints in subsequent
> patches.

The comment and the subject line are confusing: what arbitrary
containers are you talking about? Looks like it's left from the
previous version of the patch that used templates. Please fix.

> 
> Needed for #3961
> ---
>  src/box/memtx_tree.c | 289 ++++++++++++++++++++++++++-----------------
>  1 file changed, 178 insertions(+), 111 deletions(-)
> 
> diff --git a/src/box/memtx_tree.c b/src/box/memtx_tree.c
> index 250df7f2d..688f09597 100644
> --- a/src/box/memtx_tree.c
> +++ b/src/box/memtx_tree.c
> @@ -50,30 +50,70 @@ struct memtx_tree_key_data {
>  };
>  
>  /**
> - * BPS tree element vs key comparator.
> - * Defined in header in order to allow compiler to inline it.
> - * @param tuple - tuple to compare.
> - * @param key_data - key to compare with.
> - * @param def - key definition.
> - * @retval 0  if tuple == key in terms of def.
> - * @retval <0 if tuple < key in terms of def.
> - * @retval >0 if tuple > key in terms of def.
> + * Struct that is used as a elem in BPS tree definition.
>   */
> -static int
> -memtx_tree_compare_key(const struct tuple *tuple,
> -		       const struct memtx_tree_key_data *key_data,
> -		       struct key_def *def)
> +struct memtx_tree_data {
> +	/* Tuple that this node is represents. */
> +	struct tuple *tuple;
> +};
> +
> +/**
> + * Test whether BPS tree elements are identical i.e. represents

s/represents/represent

> + * the same tuple and metadata.

the same tuple at the same position in the tree.

> + * @param a - First BPS tree element to compare.
> + * @param b - Second BPS tree element to compare.
> + * @retval true - When elements a and b are identical.
> + * @retval fa;se - Otherwise.

s/fa;se/false

> + */
> +static bool
> +memtx_tree_data_identical(const struct memtx_tree_data *a,
> +			  const struct memtx_tree_data *b)
>  {
> -	return tuple_compare_with_key(tuple, key_data->key,
> -				      key_data->part_count, def);
> +	return a->tuple == b->tuple;
> +}
> +
> +/**
> + * BPS tree element clear.
> + * @param data - BPS tree element to clear.
> + */
> +static void
> +memtx_tree_data_clear(struct memtx_tree_data *data)
> +{
> +	data->tuple = NULL;
> +}

Please remove this trivial helper function - even after multikey indexes
are introduced, this function will remain the same.

> +
> +/**
> + * Initialize BPS tree element.
> + */
> +static void
> +memtx_tree_data_set(struct memtx_tree_data *data, struct tuple *tuple,
> +		    struct key_def *key_def)
> +{
> +	(void)key_def;
> +	data->tuple = tuple;
> +}

Please remove this trivial helper function as well, as it's only used in
'build_next' and 'replace' index callbacks, which will differ for hinted
and multikey trees anyway.

> +
> +/**
> + * Initialize BPS tree key element.
> + */
> +static void
> +memtx_tree_key_data_set(struct memtx_tree_key_data *key_data, const char *key,
> +			uint32_t part_count, struct key_def *key_def)

This function is only used in 'get' and 'create_iterator' index
callbacks. Rather than using it, you should set different callbacks
for multikey and hinted trees. Please remove it, too.

> +{
> +	(void)key_def;
> +	key_data->key = key;
> +	key_data->part_count = part_count;
>  }

> @@ -614,21 +678,23 @@ static int
>  memtx_tree_index_build_next(struct index *base, struct tuple *tuple)
>  {
>  	struct memtx_tree_index *index = (struct memtx_tree_index *)base;
> +	struct key_def *key_def = index->tree.arg;
>  	if (index->build_array == NULL) {
> -		index->build_array = (struct tuple **)malloc(MEMTX_EXTENT_SIZE);
> +		index->build_array =
> +			(struct memtx_tree_data *)malloc(MEMTX_EXTENT_SIZE);

Nit: pointless type cast, please remove.

Re: [tarantool-patches] Re: [PATCH v5 1/4] memtx: rework memtx_tree to store arbitrary nodes

[Kirill Shcherbatov]

Hi! Thank you for review. I've fixed your comments for this commit and
merge this changes up. Actual patch version is on the branch.

===================================================

Reworked memtx_tree class to use structure memtx_tree_data as a
tree node. This makes possible to extend it with service field
to implement tuple hints and multikey indexes in subsequent
patches.

Needed for #3961
---
 src/box/memtx_tree.c | 245 ++++++++++++++++++++++++-------------------
 1 file changed, 138 insertions(+), 107 deletions(-)

diff --git a/src/box/memtx_tree.c b/src/box/memtx_tree.c
index 250df7f2d..d5b42efb6 100644
--- a/src/box/memtx_tree.c
+++ b/src/box/memtx_tree.c
@@ -50,30 +50,37 @@ struct memtx_tree_key_data {
 };
 
 /**
- * BPS tree element vs key comparator.
- * Defined in header in order to allow compiler to inline it.
- * @param tuple - tuple to compare.
- * @param key_data - key to compare with.
- * @param def - key definition.
- * @retval 0  if tuple == key in terms of def.
- * @retval <0 if tuple < key in terms of def.
- * @retval >0 if tuple > key in terms of def.
+ * Struct that is used as a elem in BPS tree definition.
  */
-static int
-memtx_tree_compare_key(const struct tuple *tuple,
-		       const struct memtx_tree_key_data *key_data,
-		       struct key_def *def)
+struct memtx_tree_data {
+	/* Tuple that this node is represents. */
+	struct tuple *tuple;
+};
+
+/**
+ * Test whether BPS tree elements are identical i.e. represent
+ * the same tuple at the same position in the tree.
+ * @param a - First BPS tree element to compare.
+ * @param b - Second BPS tree element to compare.
+ * @retval true - When elements a and b are identical.
+ * @retval false - Otherwise.
+ */
+static bool
+memtx_tree_data_identical(const struct memtx_tree_data *a,
+			  const struct memtx_tree_data *b)
 {
-	return tuple_compare_with_key(tuple, key_data->key,
-				      key_data->part_count, def);
+	return a->tuple == b->tuple;
 }
 
 #define BPS_TREE_NAME memtx_tree
 #define BPS_TREE_BLOCK_SIZE (512)
 #define BPS_TREE_EXTENT_SIZE MEMTX_EXTENT_SIZE
-#define BPS_TREE_COMPARE(a, b, arg) tuple_compare(a, b, arg)
-#define BPS_TREE_COMPARE_KEY(a, b, arg) memtx_tree_compare_key(a, b, arg)
-#define bps_tree_elem_t struct tuple *
+#define BPS_TREE_COMPARE(a, b, arg)\
+	tuple_compare((&a)->tuple, (&b)->tuple, arg)
+#define BPS_TREE_COMPARE_KEY(a, b, arg)\
+	tuple_compare_with_key((&a)->tuple, (b)->key, (b)->part_count, arg)
+#define BPS_TREE_IDENTICAL(a, b) memtx_tree_data_identical(&a, &b)
+#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 *
 
@@ -84,6 +91,7 @@ memtx_tree_compare_key(const struct tuple *tuple,
 #undef BPS_TREE_EXTENT_SIZE
 #undef BPS_TREE_COMPARE
 #undef BPS_TREE_COMPARE_KEY
+#undef BPS_TREE_IDENTICAL
 #undef bps_tree_elem_t
 #undef bps_tree_key_t
 #undef bps_tree_arg_t
@@ -91,7 +99,7 @@ memtx_tree_compare_key(const struct tuple *tuple,
 struct memtx_tree_index {
 	struct index base;
 	struct memtx_tree tree;
-	struct tuple **build_array;
+	struct memtx_tree_data *build_array;
 	size_t build_array_size, build_array_alloc_size;
 	struct memtx_gc_task gc_task;
 	struct memtx_tree_iterator gc_iterator;
@@ -102,8 +110,10 @@ struct memtx_tree_index {
 static int
 memtx_tree_qcompare(const void* a, const void *b, void *c)
 {
-	return tuple_compare(*(struct tuple **)a,
-		*(struct tuple **)b, (struct key_def *)c);
+	const struct memtx_tree_data *data_a = a;
+	const struct memtx_tree_data *data_b = b;
+	struct key_def *key_def = c;
+	return tuple_compare(data_a->tuple, data_b->tuple, key_def);
 }
 
 /* {{{ MemtxTree Iterators ****************************************/
@@ -114,7 +124,7 @@ struct tree_iterator {
 	struct memtx_tree_iterator tree_iterator;
 	enum iterator_type type;
 	struct memtx_tree_key_data key_data;
-	struct tuple *current_tuple;
+	struct memtx_tree_data current;
 	/** Memory pool the iterator was allocated from. */
 	struct mempool *pool;
 };
@@ -137,8 +147,9 @@ static void
 tree_iterator_free(struct iterator *iterator)
 {
 	struct tree_iterator *it = tree_iterator(iterator);
-	if (it->current_tuple != NULL)
-		tuple_unref(it->current_tuple);
+	struct tuple *tuple = it->current.tuple;
+	if (tuple != NULL)
+		tuple_unref(tuple);
 	mempool_free(it->pool, it);
 }
 
@@ -153,25 +164,28 @@ tree_iterator_dummie(struct iterator *iterator, struct tuple **ret)
 static int
 tree_iterator_next(struct iterator *iterator, struct tuple **ret)
 {
-	struct tuple **res;
 	struct tree_iterator *it = tree_iterator(iterator);
-	assert(it->current_tuple != NULL);
-	struct tuple **check = memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
-	if (check == NULL || *check != it->current_tuple)
+	assert(it->current.tuple != NULL);
+	struct memtx_tree_data *check =
+		memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
+	if (check == NULL || !memtx_tree_data_identical(check, &it->current)) {
 		it->tree_iterator =
-			memtx_tree_upper_bound_elem(it->tree, it->current_tuple,
+			memtx_tree_upper_bound_elem(it->tree, it->current,
 						    NULL);
-	else
+	} else {
 		memtx_tree_iterator_next(it->tree, &it->tree_iterator);
-	tuple_unref(it->current_tuple);
-	it->current_tuple = NULL;
-	res = memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
+	}
+	tuple_unref(it->current.tuple);
+	struct memtx_tree_data *res =
+		memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
 	if (res == NULL) {
 		iterator->next = tree_iterator_dummie;
+		it->current.tuple = NULL;
 		*ret = NULL;
 	} else {
-		*ret = it->current_tuple = *res;
-		tuple_ref(it->current_tuple);
+		*ret = res->tuple;
+		tuple_ref(*ret);
+		it->current = *res;
 	}
 	return 0;
 }
@@ -180,22 +194,25 @@ static int
 tree_iterator_prev(struct iterator *iterator, struct tuple **ret)
 {
 	struct tree_iterator *it = tree_iterator(iterator);
-	assert(it->current_tuple != NULL);
-	struct tuple **check = memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
-	if (check == NULL || *check != it->current_tuple)
+	assert(it->current.tuple != NULL);
+	struct memtx_tree_data *check =
+		memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
+	if (check == NULL || !memtx_tree_data_identical(check, &it->current)) {
 		it->tree_iterator =
-			memtx_tree_lower_bound_elem(it->tree, it->current_tuple,
-						    NULL);
+			memtx_tree_lower_bound_elem(it->tree, it->current, NULL);
+	}
 	memtx_tree_iterator_prev(it->tree, &it->tree_iterator);
-	tuple_unref(it->current_tuple);
-	it->current_tuple = NULL;
-	struct tuple **res = memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
+	tuple_unref(it->current.tuple);
+	struct memtx_tree_data *res =
+		memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
 	if (!res) {
 		iterator->next = tree_iterator_dummie;
+		it->current.tuple = NULL;
 		*ret = NULL;
 	} else {
-		*ret = it->current_tuple = *res;
-		tuple_ref(it->current_tuple);
+		*ret = res->tuple;
+		tuple_ref(*ret);
+		it->current = *res;
 	}
 	return 0;
 }
@@ -204,27 +221,30 @@ static int
 tree_iterator_next_equal(struct iterator *iterator, struct tuple **ret)
 {
 	struct tree_iterator *it = tree_iterator(iterator);
-	assert(it->current_tuple != NULL);
-	struct tuple **check = memtx_tree_iterator_get_elem(it->tree,
-						&it->tree_iterator);
-	if (check == NULL || *check != it->current_tuple)
+	assert(it->current.tuple != NULL);
+	struct memtx_tree_data *check =
+		memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
+	if (check == NULL || !memtx_tree_data_identical(check, &it->current)) {
 		it->tree_iterator =
-			memtx_tree_upper_bound_elem(it->tree, it->current_tuple,
-						    NULL);
-	else
+			memtx_tree_upper_bound_elem(it->tree, it->current, NULL);
+	} else {
 		memtx_tree_iterator_next(it->tree, &it->tree_iterator);
-	tuple_unref(it->current_tuple);
-	it->current_tuple = NULL;
-	struct tuple **res = memtx_tree_iterator_get_elem(it->tree,
-						&it->tree_iterator);
+	}
+	tuple_unref(it->current.tuple);
+	struct memtx_tree_data *res =
+		memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
 	/* Use user key def to save a few loops. */
-	if (!res || memtx_tree_compare_key(*res, &it->key_data,
-					   it->index_def->key_def) != 0) {
+	if (res == NULL ||
+	    tuple_compare_with_key(res->tuple, it->key_data.key,
+				   it->key_data.part_count,
+				   it->index_def->key_def) != 0) {
 		iterator->next = tree_iterator_dummie;
+		it->current.tuple = NULL;
 		*ret = NULL;
 	} else {
-		*ret = it->current_tuple = *res;
-		tuple_ref(it->current_tuple);
+		*ret = res->tuple;
+		tuple_ref(*ret);
+		it->current = *res;
 	}
 	return 0;
 }
@@ -233,26 +253,29 @@ static int
 tree_iterator_prev_equal(struct iterator *iterator, struct tuple **ret)
 {
 	struct tree_iterator *it = tree_iterator(iterator);
-	assert(it->current_tuple != NULL);
-	struct tuple **check = memtx_tree_iterator_get_elem(it->tree,
-						&it->tree_iterator);
-	if (check == NULL || *check != it->current_tuple)
+	assert(it->current.tuple != NULL);
+	struct memtx_tree_data *check =
+		memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
+	if (check == NULL || !memtx_tree_data_identical(check, &it->current)) {
 		it->tree_iterator =
-			memtx_tree_lower_bound_elem(it->tree, it->current_tuple,
-						    NULL);
+			memtx_tree_lower_bound_elem(it->tree, it->current, NULL);
+	}
 	memtx_tree_iterator_prev(it->tree, &it->tree_iterator);
-	tuple_unref(it->current_tuple);
-	it->current_tuple = NULL;
-	struct tuple **res = memtx_tree_iterator_get_elem(it->tree,
-						&it->tree_iterator);
+	tuple_unref(it->current.tuple);
+	struct memtx_tree_data *res =
+		memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
 	/* Use user key def to save a few loops. */
-	if (!res || memtx_tree_compare_key(*res, &it->key_data,
-					   it->index_def->key_def) != 0) {
+	if (res == NULL ||
+	    tuple_compare_with_key(res->tuple, it->key_data.key,
+				   it->key_data.part_count,
+				   it->index_def->key_def) != 0) {
 		iterator->next = tree_iterator_dummie;
+		it->current.tuple = NULL;
 		*ret = NULL;
 	} else {
-		*ret = it->current_tuple = *res;
-		tuple_ref(it->current_tuple);
+		*ret = res->tuple;
+		tuple_ref(*ret);
+		it->current = *res;
 	}
 	return 0;
 }
@@ -260,7 +283,7 @@ tree_iterator_prev_equal(struct iterator *iterator, struct tuple **ret)
 static void
 tree_iterator_set_next_method(struct tree_iterator *it)
 {
-	assert(it->current_tuple != NULL);
+	assert(it->current.tuple != NULL);
 	switch (it->type) {
 	case ITER_EQ:
 		it->base.next = tree_iterator_next_equal;
@@ -294,7 +317,7 @@ tree_iterator_start(struct iterator *iterator, struct tuple **ret)
 	const struct memtx_tree *tree = it->tree;
 	enum iterator_type type = it->type;
 	bool exact = false;
-	assert(it->current_tuple == NULL);
+	assert(it->current.tuple == NULL);
 	if (it->key_data.key == 0) {
 		if (iterator_type_is_reverse(it->type))
 			it->tree_iterator = memtx_tree_iterator_last(tree);
@@ -331,12 +354,13 @@ tree_iterator_start(struct iterator *iterator, struct tuple **ret)
 		}
 	}
 
-	struct tuple **res = memtx_tree_iterator_get_elem(it->tree,
-						&it->tree_iterator);
+	struct memtx_tree_data *res =
+		memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
 	if (!res)
 		return 0;
-	*ret = it->current_tuple = *res;
-	tuple_ref(it->current_tuple);
+	*ret = res->tuple;
+	tuple_ref(*ret);
+	it->current = *res;
 	tree_iterator_set_next_method(it);
 	return 0;
 }
@@ -390,9 +414,10 @@ memtx_tree_index_gc_run(struct memtx_gc_task *task, bool *done)
 
 	unsigned int loops = 0;
 	while (!memtx_tree_iterator_is_invalid(itr)) {
-		struct tuple *tuple = *memtx_tree_iterator_get_elem(tree, itr);
+		struct memtx_tree_data *res =
+			memtx_tree_iterator_get_elem(tree, itr);
 		memtx_tree_iterator_next(tree, itr);
-		tuple_unref(tuple);
+		tuple_unref(res->tuple);
 		if (++loops >= YIELD_LOOPS) {
 			*done = false;
 			return;
@@ -470,8 +495,8 @@ static int
 memtx_tree_index_random(struct index *base, uint32_t rnd, struct tuple **result)
 {
 	struct memtx_tree_index *index = (struct memtx_tree_index *)base;
-	struct tuple **res = memtx_tree_random(&index->tree, rnd);
-	*result = res != NULL ? *res : NULL;
+	struct memtx_tree_data *res = memtx_tree_random(&index->tree, rnd);
+	*result = res != NULL ? res->tuple : NULL;
 	return 0;
 }
 
@@ -494,8 +519,8 @@ memtx_tree_index_get(struct index *base, const char *key,
 	struct memtx_tree_key_data key_data;
 	key_data.key = key;
 	key_data.part_count = part_count;
-	struct tuple **res = memtx_tree_find(&index->tree, &key_data);
-	*result = res != NULL ? *res : NULL;
+	struct memtx_tree_data *res = memtx_tree_find(&index->tree, &key_data);
+	*result = res != NULL ? res->tuple : NULL;
 	return 0;
 }
 
@@ -506,11 +531,14 @@ memtx_tree_index_replace(struct index *base, struct tuple *old_tuple,
 {
 	struct memtx_tree_index *index = (struct memtx_tree_index *)base;
 	if (new_tuple) {
-		struct tuple *dup_tuple = NULL;
+		struct memtx_tree_data new_data;
+		new_data.tuple = new_tuple;
+		struct memtx_tree_data dup_data;
+		dup_data.tuple = NULL;
 
 		/* Try to optimistically replace the new_tuple. */
-		int tree_res = memtx_tree_insert(&index->tree,
-						 new_tuple, &dup_tuple);
+		int tree_res = memtx_tree_insert(&index->tree, new_data,
+						 &dup_data);
 		if (tree_res) {
 			diag_set(OutOfMemory, MEMTX_EXTENT_SIZE,
 				 "memtx_tree_index", "replace");
@@ -518,24 +546,26 @@ memtx_tree_index_replace(struct index *base, struct tuple *old_tuple,
 		}
 
 		uint32_t errcode = replace_check_dup(old_tuple,
-						     dup_tuple, mode);
+						     dup_data.tuple, mode);
 		if (errcode) {
-			memtx_tree_delete(&index->tree, new_tuple);
-			if (dup_tuple)
-				memtx_tree_insert(&index->tree, dup_tuple, 0);
+			memtx_tree_delete(&index->tree, new_data);
+			if (dup_data.tuple != NULL)
+				memtx_tree_insert(&index->tree, dup_data, NULL);
 			struct space *sp = space_cache_find(base->def->space_id);
 			if (sp != NULL)
 				diag_set(ClientError, errcode, base->def->name,
 					 space_name(sp));
 			return -1;
 		}
-		if (dup_tuple) {
-			*result = dup_tuple;
+		if (dup_data.tuple != NULL) {
+			*result = dup_data.tuple;
 			return 0;
 		}
 	}
 	if (old_tuple) {
-		memtx_tree_delete(&index->tree, old_tuple);
+		struct memtx_tree_data old_data;
+		old_data.tuple = old_tuple;
+		memtx_tree_delete(&index->tree, old_data);
 	}
 	*result = old_tuple;
 	return 0;
@@ -580,7 +610,7 @@ memtx_tree_index_create_iterator(struct index *base, enum iterator_type type,
 	it->index_def = base->def;
 	it->tree = &index->tree;
 	it->tree_iterator = memtx_tree_invalid_iterator();
-	it->current_tuple = NULL;
+	it->current.tuple = NULL;
 	return (struct iterator *)it;
 }
 
@@ -598,8 +628,8 @@ memtx_tree_index_reserve(struct index *base, uint32_t size_hint)
 	struct memtx_tree_index *index = (struct memtx_tree_index *)base;
 	if (size_hint < index->build_array_alloc_size)
 		return 0;
-	struct tuple **tmp = (struct tuple **)realloc(index->build_array,
-						      size_hint * sizeof(*tmp));
+	struct memtx_tree_data *tmp =
+		realloc(index->build_array, size_hint * sizeof(*tmp));
 	if (tmp == NULL) {
 		diag_set(OutOfMemory, size_hint * sizeof(*tmp),
 			 "memtx_tree_index", "reserve");
@@ -615,20 +645,20 @@ memtx_tree_index_build_next(struct index *base, struct tuple *tuple)
 {
 	struct memtx_tree_index *index = (struct memtx_tree_index *)base;
 	if (index->build_array == NULL) {
-		index->build_array = (struct tuple **)malloc(MEMTX_EXTENT_SIZE);
+		index->build_array = malloc(MEMTX_EXTENT_SIZE);
 		if (index->build_array == NULL) {
 			diag_set(OutOfMemory, MEMTX_EXTENT_SIZE,
 				 "memtx_tree_index", "build_next");
 			return -1;
 		}
 		index->build_array_alloc_size =
-			MEMTX_EXTENT_SIZE / sizeof(struct tuple*);
+			MEMTX_EXTENT_SIZE / sizeof(index->build_array[0]);
 	}
 	assert(index->build_array_size <= index->build_array_alloc_size);
 	if (index->build_array_size == index->build_array_alloc_size) {
 		index->build_array_alloc_size = index->build_array_alloc_size +
 					index->build_array_alloc_size / 2;
-		struct tuple **tmp = (struct tuple **)
+		struct memtx_tree_data *tmp =
 			realloc(index->build_array,
 				index->build_array_alloc_size * sizeof(*tmp));
 		if (tmp == NULL) {
@@ -638,7 +668,9 @@ memtx_tree_index_build_next(struct index *base, struct tuple *tuple)
 		}
 		index->build_array = tmp;
 	}
-	index->build_array[index->build_array_size++] = tuple;
+	struct memtx_tree_data *elem =
+		&index->build_array[index->build_array_size++];
+	elem->tuple = tuple;
 	return 0;
 }
 
@@ -648,8 +680,7 @@ memtx_tree_index_end_build(struct index *base)
 	struct memtx_tree_index *index = (struct memtx_tree_index *)base;
 	struct key_def *cmp_def = memtx_tree_index_cmp_def(index);
 	qsort_arg(index->build_array, index->build_array_size,
-		  sizeof(struct tuple *),
-		  memtx_tree_qcompare, cmp_def);
+		  sizeof(index->build_array[0]), memtx_tree_qcompare, cmp_def);
 	memtx_tree_build(&index->tree, index->build_array,
 			 index->build_array_size);
 
@@ -682,12 +713,12 @@ tree_snapshot_iterator_next(struct snapshot_iterator *iterator, uint32_t *size)
 	assert(iterator->free == tree_snapshot_iterator_free);
 	struct tree_snapshot_iterator *it =
 		(struct tree_snapshot_iterator *)iterator;
-	struct tuple **res = memtx_tree_iterator_get_elem(it->tree,
-						&it->tree_iterator);
+	struct memtx_tree_data *res =
+		memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
 	if (res == NULL)
 		return NULL;
 	memtx_tree_iterator_next(it->tree, &it->tree_iterator);
-	return tuple_data_range(*res, size);
+	return tuple_data_range(res->tuple, size);
 }
 
 /**
-- 
2.21.0

Re: [tarantool-patches] Re: [PATCH v5 1/4] memtx: rework memtx_tree to store arbitrary nodes

[Vladimir Davydov]

On Mon, Mar 11, 2019 at 07:53:48PM +0300, Kirill Shcherbatov wrote:
> Reworked memtx_tree class to use structure memtx_tree_data as a
> tree node. This makes possible to extend it with service field
> to implement tuple hints and multikey indexes in subsequent
> patches.
> 
> Needed for #3961
> ---
>  src/box/memtx_tree.c | 245 ++++++++++++++++++++++++-------------------
>  1 file changed, 138 insertions(+), 107 deletions(-)

Pushed to 2.1.

[PATCH v5 2/4] memtx: introduce tuple compare hint

[Kirill Shcherbatov]

Implement functions for retrieving tuple hints for a particular
key_def. Hint is an integer that can be used for tuple comparison
optimization: if a hint of one tuple is less than a hint of another
then the first tuple is definitely less than the second; only if
hints are equal tuple_compare must be called for getting comparison
result.

Hints are calculated using only the first part of key_def.

Hints are only useful when:
 * they are precalculated and stored along with the tuple;
calculation is not cheap (cheaper than tuple_compare btw) but
precalculated hints allow to compare tuples without even fetching
tuple data.
 * first part of key_def is 'string'(for now)
 * since hint is calculated using only the first part of key_def
(and only first several characters if it is a string) this part
must be different with high probability for every tuple pair.

Closes #3961
---
 src/box/key_def.c        |   1 +
 src/box/key_def.h        | 119 ++++++++++++
 src/box/memtx_tree.c     |  32 +++-
 src/box/tuple_compare.cc | 381 +++++++++++++++++++++++++++++++++++++++
 src/box/tuple_compare.h  |   7 +
 src/lib/coll/coll.c      |  33 ++++
 src/lib/coll/coll.h      |   4 +
 7 files changed, 567 insertions(+), 10 deletions(-)

diff --git a/src/box/key_def.c b/src/box/key_def.c
index d4c979aa1..771c30172 100644
--- a/src/box/key_def.c
+++ b/src/box/key_def.c
@@ -136,6 +136,7 @@ key_def_set_func(struct key_def *def)
 	key_def_set_compare_func(def);
 	key_def_set_hash_func(def);
 	key_def_set_extract_func(def);
+	key_def_set_cmp_aux_func(def);
 }
 
 static void
diff --git a/src/box/key_def.h b/src/box/key_def.h
index dd62f6a35..c630e6b43 100644
--- a/src/box/key_def.h
+++ b/src/box/key_def.h
@@ -115,6 +115,28 @@ struct key_part {
 
 struct key_def;
 struct tuple;
+/** Comparasion auxiliary information. */
+typedef union {
+	/**
+	 * Hint is a value h(t) is calculated for tuple in terms
+	 * of particular key_def that has follows rules:
+	 * if h(t1) < h(t2) then t1 < t2;
+	 * if h(t1) > h(t2) then t1 > t2;
+	 * if t1 == t2 then h(t1) == h(t2);
+	 * These rules means that instead of direct tuple vs tuple
+	 * (or tuple vs key) comparison one may compare theirs
+	 * hints first; and only if theirs hints are equal compare
+	 * the tuples themselves.
+	 */
+	uint64_t hint;
+} cmp_aux_t;
+
+/** Test if cmp_aux_t a and b are equal. */
+static inline bool
+cmp_aux_equal(cmp_aux_t a, cmp_aux_t b)
+{
+	return a.hint == b.hint;
+}
 
 /**
  * Get is_nullable property of key_part.
@@ -137,6 +159,18 @@ typedef int (*tuple_compare_with_key_t)(const struct tuple *tuple_a,
 typedef int (*tuple_compare_t)(const struct tuple *tuple_a,
 			       const struct tuple *tuple_b,
 			       struct key_def *key_def);
+/** @copydoc tuple_aux_compare_with_key() */
+typedef int (*tuple_aux_compare_with_key_t)(const struct tuple *tuple,
+					    cmp_aux_t tuple_cmp_aux,
+					    const char *key, uint32_t part_count,
+					    cmp_aux_t key_cmp_aux,
+					    struct key_def *key_def);
+/** @copydoc tuple_aux_compare() */
+typedef int (*tuple_aux_compare_t)(const struct tuple *tuple_a,
+				   cmp_aux_t tuple_a_cmp_aux,
+				   const struct tuple *tuple_b,
+				   cmp_aux_t tuple_b_cmp_aux,
+				   struct key_def *key_def);
 /** @copydoc tuple_extract_key() */
 typedef char *(*tuple_extract_key_t)(const struct tuple *tuple,
 				     struct key_def *key_def,
@@ -153,12 +187,23 @@ typedef uint32_t (*tuple_hash_t)(const struct tuple *tuple,
 typedef uint32_t (*key_hash_t)(const char *key,
 				struct key_def *key_def);
 
+/** @copydoc tuple_cmp_aux() */
+typedef cmp_aux_t (*tuple_cmp_aux_t)(const struct tuple *tuple,
+				     struct key_def *key_def);
+
+/** @copydoc key_cmp_aux() */
+typedef cmp_aux_t (*key_cmp_aux_t)(const char *key, struct key_def *key_def);
+
 /* Definition of a multipart key. */
 struct key_def {
 	/** @see tuple_compare() */
 	tuple_compare_t tuple_compare;
 	/** @see tuple_compare_with_key() */
 	tuple_compare_with_key_t tuple_compare_with_key;
+	/** @see tuple_aux_compare_with_key() */
+	tuple_aux_compare_with_key_t tuple_aux_compare_with_key;
+	/** @see tuple_aux_compare() */
+	tuple_aux_compare_t tuple_aux_compare;
 	/** @see tuple_extract_key() */
 	tuple_extract_key_t tuple_extract_key;
 	/** @see tuple_extract_key_raw() */
@@ -167,6 +212,10 @@ struct key_def {
 	tuple_hash_t tuple_hash;
 	/** @see key_hash() */
 	key_hash_t key_hash;
+	/** @see tuple_cmp_aux() */
+	tuple_cmp_aux_t tuple_cmp_aux;
+	/** @see key_cmp_aux() */
+	key_cmp_aux_t key_cmp_aux;
 	/**
 	 * Minimal part count which always is unique. For example,
 	 * if a secondary index is unique, then
@@ -571,6 +620,52 @@ tuple_compare_with_key(const struct tuple *tuple, const char *key,
 	return key_def->tuple_compare_with_key(tuple, key, part_count, key_def);
 }
 
+/**
+ * Compare tuples using the key definition and comparasion
+ * auxillary information.
+ * @param tuple_a First tuple.
+ * @param tuple_a_cmp_aux Comparasion auxiliary information
+ *                        for the tuple_a.
+ * @param tuple_b Second tuple.
+ * @param tuple_b_cmp_aux Comparasion auxilary information
+ *                        for the tuple_b.
+ * @param key_def Key definition.
+ * @retval 0  if key_fields(tuple_a) == key_fields(tuple_b)
+ * @retval <0 if key_fields(tuple_a) < key_fields(tuple_b)
+ * @retval >0 if key_fields(tuple_a) > key_fields(tuple_b)
+ */
+static inline int
+tuple_aux_compare(const struct tuple *tuple_a, cmp_aux_t tuple_a_cmp_aux,
+		  const struct tuple *tuple_b, cmp_aux_t tuple_b_cmp_aux,
+		  struct key_def *key_def)
+{
+	return key_def->tuple_aux_compare(tuple_a, tuple_a_cmp_aux, tuple_b,
+					  tuple_b_cmp_aux, key_def);
+}
+
+/**
+ * Compare tuple with key using the key definition and
+ * comparasion auxilary information.
+ * @param tuple tuple
+ * @param tuple_cmp_aux tuple compare auxiliary information.
+ * @param key key parts without MessagePack array header
+ * @param part_count the number of parts in @a key
+ * @param key_cmp_aux t Key compare auxiliary information.
+ * @param key_def key definition
+ * @retval 0  if key_fields(tuple) == parts(key)
+ * @retval <0 if key_fields(tuple) < parts(key)
+ * @retval >0 if key_fields(tuple) > parts(key)
+ */
+static inline int
+tuple_aux_compare_with_key(const struct tuple *tuple, cmp_aux_t tuple_cmp_aux,
+			   const char *key, uint32_t part_count,
+			   cmp_aux_t key_cmp_aux, struct key_def *key_def)
+{
+	return key_def->tuple_aux_compare_with_key(tuple, tuple_cmp_aux, key,
+						   part_count, key_cmp_aux,
+						   key_def);
+}
+
 /**
  * Compute hash of a tuple field.
  * @param ph1 - pointer to running hash
@@ -624,6 +719,30 @@ key_hash(const char *key, struct key_def *key_def)
 	return key_def->key_hash(key, key_def);
 }
 
+ /*
+ * Get a comparison auxiliary information for a tuple.
+ * @param tuple - tuple to get cmp_aux_t of.
+ * @param key_def - key_def that defines which comparison is used.
+ * @return the comparison auxiliary information.
+ */
+static inline cmp_aux_t
+tuple_cmp_aux(const struct tuple *tuple, struct key_def *key_def)
+{
+	return key_def->tuple_cmp_aux(tuple, key_def);
+}
+
+/**
+ * Get a comparison hint of a key.
+ * @param key - key to get hint of.
+ * @param key_def - key_def that defines which comparison is used.
+ * @return the comparison auxiliary information.
+ */
+static inline cmp_aux_t
+key_cmp_aux(const char *key, struct key_def *key_def)
+{
+	return key_def->key_cmp_aux(key, key_def);
+}
+
 #if defined(__cplusplus)
 } /* extern "C" */
 #endif /* defined(__cplusplus) */
diff --git a/src/box/memtx_tree.c b/src/box/memtx_tree.c
index 688f09597..4b0886bef 100644
--- a/src/box/memtx_tree.c
+++ b/src/box/memtx_tree.c
@@ -47,6 +47,8 @@ struct memtx_tree_key_data {
 	const char *key;
 	/** Number of msgpacked search fields. */
 	uint32_t part_count;
+	/** Comparison auxilary information. */
+	cmp_aux_t aux_info;
 };
 
 /**
@@ -55,6 +57,8 @@ struct memtx_tree_key_data {
 struct memtx_tree_data {
 	/* Tuple that this node is represents. */
 	struct tuple *tuple;
+	/** Comparison auxilary information. */
+	cmp_aux_t aux_info;
 };
 
 /**
@@ -69,7 +73,7 @@ static bool
 memtx_tree_data_identical(const struct memtx_tree_data *a,
 			  const struct memtx_tree_data *b)
 {
-	return a->tuple == b->tuple;
+	return a->tuple == b->tuple && cmp_aux_equal(a->aux_info, b->aux_info);
 }
 
 /**
@@ -91,6 +95,7 @@ memtx_tree_data_set(struct memtx_tree_data *data, struct tuple *tuple,
 {
 	(void)key_def;
 	data->tuple = tuple;
+	data->aux_info = tuple_cmp_aux(tuple, key_def);
 }
 
 /**
@@ -103,15 +108,18 @@ memtx_tree_key_data_set(struct memtx_tree_key_data *key_data, const char *key,
 	(void)key_def;
 	key_data->key = key;
 	key_data->part_count = part_count;
+	key_data->aux_info = key_cmp_aux(key, key_def);
 }
 
 #define BPS_TREE_NAME memtx_tree
 #define BPS_TREE_BLOCK_SIZE (512)
 #define BPS_TREE_EXTENT_SIZE MEMTX_EXTENT_SIZE
 #define BPS_TREE_COMPARE(a, b, arg)\
-	tuple_compare((&a)->tuple, (&b)->tuple, arg)
+	tuple_aux_compare((&a)->tuple, (&a)->aux_info, (&b)->tuple,\
+			  (&b)->aux_info, arg)
 #define BPS_TREE_COMPARE_KEY(a, b, arg)\
-	tuple_compare_with_key((&a)->tuple, (b)->key, (b)->part_count, arg)
+	tuple_aux_compare_with_key((&a)->tuple, (&a)->aux_info, (b)->key,\
+				   (b)->part_count, (b)->aux_info, arg)
 #define BPS_TREE_IDENTICAL(a, b) memtx_tree_data_identical(&a, &b)
 #define bps_tree_elem_t struct memtx_tree_data
 #define bps_tree_key_t struct memtx_tree_key_data *
@@ -146,7 +154,8 @@ memtx_tree_qcompare(const void* a, const void *b, void *c)
 	const struct memtx_tree_data *data_a = a;
 	const struct memtx_tree_data *data_b = b;
 	struct key_def *key_def = c;
-	return tuple_compare(data_a->tuple, data_b->tuple, key_def);
+	return tuple_aux_compare(data_a->tuple, data_a->aux_info, data_b->tuple,
+				 data_b->aux_info, key_def);
 }
 
 /* {{{ MemtxTree Iterators ****************************************/
@@ -268,9 +277,10 @@ tree_iterator_next_equal(struct iterator *iterator, struct tuple **ret)
 		memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
 	/* Use user key def to save a few loops. */
 	if (res == NULL ||
-	    tuple_compare_with_key(res->tuple, it->key_data.key,
-				   it->key_data.part_count,
-				   it->index_def->key_def) != 0) {
+	    tuple_aux_compare_with_key(res->tuple, res->aux_info,
+				       it->key_data.key, it->key_data.part_count,
+				       it->key_data.aux_info,
+				       it->index_def->key_def) != 0) {
 		iterator->next = tree_iterator_dummie;
 		memtx_tree_data_clear(&it->current);
 		*ret = NULL;
@@ -299,9 +309,10 @@ tree_iterator_prev_equal(struct iterator *iterator, struct tuple **ret)
 		memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
 	/* Use user key def to save a few loops. */
 	if (res == NULL ||
-	    tuple_compare_with_key(res->tuple, it->key_data.key,
-				   it->key_data.part_count,
-				   it->index_def->key_def) != 0) {
+	    tuple_aux_compare_with_key(res->tuple, res->aux_info,
+				       it->key_data.key, it->key_data.part_count,
+				       it->key_data.aux_info,
+				       it->index_def->key_def) != 0) {
 		iterator->next = tree_iterator_dummie;
 		memtx_tree_data_clear(&it->current);
 		*ret = NULL;
@@ -549,6 +560,7 @@ memtx_tree_index_get(struct index *base, const char *key,
 	assert(base->def->opts.is_unique &&
 	       part_count == base->def->key_def->part_count);
 	struct memtx_tree_index *index = (struct memtx_tree_index *)base;
+
 	struct memtx_tree_key_data key_data;
 	struct key_def *cmp_def = memtx_tree_index_cmp_def(index);
 	memtx_tree_key_data_set(&key_data, key, part_count, cmp_def);
diff --git a/src/box/tuple_compare.cc b/src/box/tuple_compare.cc
index cf4519ccb..5b06e06b3 100644
--- a/src/box/tuple_compare.cc
+++ b/src/box/tuple_compare.cc
@@ -1323,9 +1323,390 @@ tuple_compare_with_key_create(const struct key_def *def)
 
 /* }}} tuple_compare_with_key */
 
+/* {{{ tuple_aux_compare */
+
+#define CMP_HINT_INVALID ((uint64_t)UINT64_MAX)
+
+static int
+tuple_hinted_compare(const struct tuple *tuple_a, cmp_aux_t tuple_a_cmp_aux,
+		     const struct tuple *tuple_b, cmp_aux_t tuple_b_cmp_aux,
+		     struct key_def *key_def)
+{
+	uint64_t tuple_a_hint = tuple_a_cmp_aux.hint;
+	uint64_t tuple_b_hint = tuple_b_cmp_aux.hint;
+	if (likely(tuple_a_hint != tuple_b_hint &&
+		   tuple_a_hint != CMP_HINT_INVALID &&
+		   tuple_b_hint != CMP_HINT_INVALID))
+		return tuple_a_hint < tuple_b_hint ? -1 : 1;
+	else
+		return tuple_compare(tuple_a, tuple_b, key_def);
+}
+
+static tuple_aux_compare_t
+tuple_aux_compare_create(const struct key_def *def)
+{
+	(void)def;
+	return tuple_hinted_compare;
+}
+
+/* }}} tuple_aux_compare */
+
+/* {{{ tuple_aux_compare_with_key */
+
+static int
+tuple_hinted_compare_with_key(const struct tuple *tuple, cmp_aux_t tuple_cmp_aux,
+			      const char *key, uint32_t part_count,
+			      cmp_aux_t key_cmp_aux, struct key_def *key_def)
+{
+	uint64_t tuple_hint = tuple_cmp_aux.hint;
+	uint64_t key_hint = key_cmp_aux.hint;
+	if (likely(tuple_hint != key_hint && tuple_hint != CMP_HINT_INVALID &&
+		   key_hint != CMP_HINT_INVALID))
+		return tuple_hint < key_hint ? -1 : 1;
+	else
+		return tuple_compare_with_key(tuple, key, part_count, key_def);
+}
+
+static tuple_aux_compare_with_key_t
+tuple_aux_compare_with_key_create(const struct key_def *def)
+{
+	(void)def;
+	return tuple_hinted_compare_with_key;
+}
+
+/* }}} tuple_aux_compare_with_key */
+
 void
 key_def_set_compare_func(struct key_def *def)
 {
 	def->tuple_compare = tuple_compare_create(def);
 	def->tuple_compare_with_key = tuple_compare_with_key_create(def);
+	def->tuple_aux_compare = tuple_aux_compare_create(def);
+	def->tuple_aux_compare_with_key =
+		tuple_aux_compare_with_key_create(def);
+}
+
+/* Tuple hints */
+
+static cmp_aux_t
+key_hint_default(const char *key, struct key_def *key_def)
+{
+	(void)key;
+	(void)key_def;
+	cmp_aux_t ret;
+	ret.hint = CMP_HINT_INVALID;
+	return ret;
+}
+
+static cmp_aux_t
+tuple_hint_default(const struct tuple *tuple, struct key_def *key_def)
+{
+	(void)tuple;
+	(void)key_def;
+	cmp_aux_t ret;
+	ret.hint = CMP_HINT_INVALID;
+	return ret;
+}
+
+template<bool is_nullable>
+static cmp_aux_t
+key_hint_uint(const char *key, struct key_def *key_def)
+{
+	(void)key_def;
+	assert(key_part_is_nullable(key_def->parts) == is_nullable);
+	assert(key_def->parts->type == FIELD_TYPE_UNSIGNED);
+	cmp_aux_t ret;
+	if (key == NULL || (is_nullable && mp_typeof(*key) == MP_NIL)) {
+		ret.hint = 0;
+		return ret;
+	}
+	assert(mp_typeof(*key) == MP_UINT);
+	uint64_t val = mp_decode_uint(&key);
+	ret.hint = unlikely(val > INT64_MAX) ? INT64_MAX :
+		   val - (uint64_t)INT64_MIN;;
+	return ret;
+}
+
+template<bool is_nullable>
+static cmp_aux_t
+tuple_hint_uint(const struct tuple *tuple, struct key_def *key_def)
+{
+	assert(key_part_is_nullable(key_def->parts) == is_nullable);
+	assert(key_def->parts->type == FIELD_TYPE_UNSIGNED);
+	cmp_aux_t ret;
+	const char *field = tuple_field_by_part(tuple, key_def->parts);
+	if (is_nullable && field == NULL) {
+		ret.hint = 0;
+		return ret;
+	}
+	return key_hint_uint<is_nullable>(field, key_def);
+}
+
+template<bool is_nullable>
+static cmp_aux_t
+key_hint_int(const char *key, struct key_def *key_def)
+{
+	(void)key_def;
+	assert(key_part_is_nullable(key_def->parts) == is_nullable);
+	assert(key_def->parts->type == FIELD_TYPE_INTEGER);
+	cmp_aux_t ret;
+	if (key == NULL || (is_nullable && mp_typeof(*key) == MP_NIL)) {
+		ret.hint = 0;
+		return ret;
+	}
+	if (mp_typeof(*key) == MP_UINT) {
+		uint64_t val = mp_decode_uint(&key);
+		ret.hint = unlikely(val > INT64_MAX) ? INT64_MAX :
+			   val - (uint64_t)INT64_MIN;
+	} else {
+		assert(mp_typeof(*key) == MP_INT);
+		int64_t val = mp_decode_int(&key);
+		ret.hint = (uint64_t)val - (uint64_t)INT64_MIN;
+	}
+	return ret;
+}
+
+template<bool is_nullable>
+static cmp_aux_t
+tuple_hint_int(const struct tuple *tuple, struct key_def *key_def)
+{
+	assert(key_part_is_nullable(key_def->parts) == is_nullable);
+	assert(key_def->parts->type == FIELD_TYPE_INTEGER);
+	cmp_aux_t ret;
+	const char *field = tuple_field_by_part(tuple, key_def->parts);
+	if (is_nullable && field == NULL) {
+		ret.hint = 0;
+		return ret;
+	}
+	return key_hint_int<is_nullable>(field, key_def);
+}
+
+template<bool is_nullable>
+static cmp_aux_t
+key_hint_number(const char *key, struct key_def *key_def)
+{
+	(void)key_def;
+	assert(key_part_is_nullable(key_def->parts) == is_nullable);
+	assert(key_def->parts->type == FIELD_TYPE_NUMBER);
+	cmp_aux_t ret;
+	if (key == NULL || (is_nullable && mp_typeof(*key) == MP_NIL)) {
+		ret.hint = 0;
+		return ret;
+	}
+	uint64_t val = 0;
+	switch (mp_typeof(*key)) {
+	case MP_FLOAT:
+	case MP_DOUBLE: {
+		double f = mp_typeof(*key) == MP_FLOAT ?
+			   mp_decode_float(&key) : mp_decode_double(&key);
+		if (isnan(f) || isinf(f)) {
+			ret.hint = CMP_HINT_INVALID;
+			return ret;
+		}
+		double ival;
+		(void)modf(f, &ival);
+		if (unlikely(ival >= (double)INT64_MAX)) {
+			ret.hint = INT64_MAX;
+			return ret;
+		}
+		if (unlikely(ival <= (double)INT64_MIN)) {
+			ret.hint = 0;
+			return ret;
+		}
+		val = (uint64_t)ival;
+		break;
+	}
+	case MP_INT: {
+		val = (uint64_t)mp_decode_int(&key);
+		break;
+	}
+	case MP_UINT: {
+		val = mp_decode_uint(&key);
+		if (val > INT64_MAX) {
+			ret.hint = INT64_MAX;
+			return ret;
+		}
+		break;
+	}
+	default:
+		unreachable();
+	}
+	ret.hint = val - (uint64_t)INT64_MIN;
+	return ret;
+}
+
+template<bool is_nullable>
+static cmp_aux_t
+tuple_hint_number(const struct tuple *tuple, struct key_def *key_def)
+{
+	assert(key_part_is_nullable(key_def->parts) == is_nullable);
+	assert(key_def->parts->type == FIELD_TYPE_NUMBER);
+	cmp_aux_t ret;
+	const char *field = tuple_field_by_part(tuple, key_def->parts);
+	if (is_nullable && field == NULL) {
+		ret.hint = 0;
+		return ret;
+	}
+	return key_hint_number<is_nullable>(field, key_def);
+}
+
+template<bool is_nullable>
+static cmp_aux_t
+key_hint_boolean(const char *key, struct key_def *key_def)
+{
+	(void)key_def;
+	assert(key_part_is_nullable(key_def->parts) == is_nullable);
+	assert(key_def->parts->type == FIELD_TYPE_BOOLEAN);
+	cmp_aux_t ret;
+	if (key == NULL || (is_nullable && mp_typeof(*key) == MP_NIL)) {
+		ret.hint = 0;
+		return ret;
+	}
+	bool val = mp_decode_bool(&key);
+	ret.hint = (uint64_t)val - (uint64_t)INT64_MIN;
+	return ret;
+}
+
+template<bool is_nullable>
+static cmp_aux_t
+tuple_hint_boolean(const struct tuple *tuple, struct key_def *key_def)
+{
+	assert(key_part_is_nullable(key_def->parts) == is_nullable);
+	assert(key_def->parts->type == FIELD_TYPE_BOOLEAN);
+	const char *field = tuple_field_by_part(tuple, key_def->parts);
+	cmp_aux_t ret;
+	if (is_nullable && field == NULL) {
+		ret.hint = 0;
+		return ret;
+	}
+	return key_hint_boolean<is_nullable>(field, key_def);
+}
+
+template<bool is_nullable>
+static cmp_aux_t
+key_hint_string(const char *key, struct key_def *key_def)
+{
+	(void)key_def;
+	assert(key_part_is_nullable(key_def->parts) == is_nullable);
+	assert(key_def->parts->coll == NULL);
+	assert(key_def->parts->type == FIELD_TYPE_STRING);
+	cmp_aux_t ret;
+	if (key == NULL || (is_nullable && mp_typeof(*key) == MP_NIL)) {
+		ret.hint = 0;
+		return ret;
+	}
+	assert(mp_typeof(*key) == MP_STR);
+	uint32_t len;
+	const unsigned char *str =
+		(const unsigned char *)mp_decode_str(&key, &len);
+	uint64_t result = 0;
+	uint32_t process_len = MIN(len, 8);
+	for (uint32_t i = 0; i < process_len; i++) {
+		result <<= 8;
+		result |= str[i];
+	}
+	result <<= 8 * (8 - process_len);
+	ret.hint = result;
+	return ret;
+}
+
+template<bool is_nullable>
+static cmp_aux_t
+tuple_hint_string(const struct tuple *tuple, struct key_def *key_def)
+{
+	assert(key_part_is_nullable(key_def->parts) == is_nullable);
+	assert(key_def->parts->coll == NULL);
+	assert(key_def->parts->type == FIELD_TYPE_STRING);
+	cmp_aux_t ret;
+	const char *field = tuple_field_by_part(tuple, key_def->parts);
+	if (is_nullable && field == NULL) {
+		ret.hint = 0;
+		return ret;
+	}
+	return key_hint_string<is_nullable>(field, key_def);
+}
+
+template<bool is_nullable>
+static cmp_aux_t
+key_hint_string_coll(const char *key, struct key_def *key_def)
+{
+	assert(key_part_is_nullable(key_def->parts) == is_nullable);
+	assert(key_def->parts->type == FIELD_TYPE_STRING &&
+	        key_def->parts->coll != NULL);
+	cmp_aux_t ret;
+	if (key == NULL || (is_nullable && mp_typeof(*key) == MP_NIL)) {
+		ret.hint = 0;
+		return ret;
+	}
+	assert(mp_typeof(*key) == MP_STR);
+	uint32_t len;
+	const char *str = mp_decode_str(&key, &len);
+	ret.hint = key_def->parts->coll->hint(str, len, key_def->parts->coll);
+	return ret;
+}
+
+template<bool is_nullable>
+static cmp_aux_t
+tuple_hint_string_coll(const struct tuple *tuple, struct key_def *key_def)
+{
+	assert(key_part_is_nullable(key_def->parts) == is_nullable);
+	assert(key_def->parts->type == FIELD_TYPE_STRING &&
+	        key_def->parts->coll != NULL);
+	const char *field = tuple_field_by_part(tuple, key_def->parts);
+	cmp_aux_t ret;
+	if (is_nullable && field == NULL) {
+		ret.hint = 0;
+		return ret;
+	}
+	return key_hint_string_coll<is_nullable>(field, key_def);
+}
+
+void
+key_def_set_cmp_aux_func(struct key_def *def)
+{
+	def->key_cmp_aux = key_hint_default;
+	def->tuple_cmp_aux = tuple_hint_default;
+	bool is_nullable = key_part_is_nullable(def->parts);
+	if (def->parts->type == FIELD_TYPE_STRING && def->parts->coll != NULL) {
+		def->key_cmp_aux = is_nullable ? key_hint_string_coll<true> :
+						 key_hint_string_coll<false>;
+		def->tuple_cmp_aux = is_nullable ?
+				     tuple_hint_string_coll<true> :
+				     tuple_hint_string_coll<false>;
+		return;
+	}
+	switch (def->parts->type) {
+	case FIELD_TYPE_UNSIGNED:
+		def->key_cmp_aux = is_nullable ? key_hint_uint<true> :
+						 key_hint_uint<false>;
+		def->tuple_cmp_aux = is_nullable ? tuple_hint_uint<true> :
+						   tuple_hint_uint<false>;
+		break;
+	case FIELD_TYPE_INTEGER:
+		def->key_cmp_aux = is_nullable ? key_hint_int<true> :
+						 key_hint_int<false>;
+		def->tuple_cmp_aux = is_nullable ? tuple_hint_int<true> :
+						   tuple_hint_int<false>;
+		break;
+	case FIELD_TYPE_STRING:
+		def->key_cmp_aux = is_nullable ? key_hint_string<true> :
+						 key_hint_string<false>;
+		def->tuple_cmp_aux = is_nullable ? tuple_hint_string<true> :
+						   tuple_hint_string<false>;
+		break;
+	case FIELD_TYPE_NUMBER:
+		def->key_cmp_aux = is_nullable ? key_hint_number<true> :
+						 key_hint_number<false>;
+		def->tuple_cmp_aux = is_nullable ? tuple_hint_number<true> :
+						   tuple_hint_number<false>;
+		break;
+	case FIELD_TYPE_BOOLEAN:
+		def->key_cmp_aux = is_nullable ? key_hint_boolean<true> :
+						 key_hint_boolean<false>;
+		def->tuple_cmp_aux = is_nullable ? tuple_hint_boolean<true> :
+						   tuple_hint_boolean<false>;
+		break;
+	default:
+		break;
+	};
 }
diff --git a/src/box/tuple_compare.h b/src/box/tuple_compare.h
index 6538d5fc0..160135af4 100644
--- a/src/box/tuple_compare.h
+++ b/src/box/tuple_compare.h
@@ -43,6 +43,13 @@ struct key_def;
 void
 key_def_set_compare_func(struct key_def *def);
 
+/**
+ * Initialize cmp_aux calculation functions for the key_def.
+ * @param key_def key definition
+ */
+void
+key_def_set_cmp_aux_func(struct key_def *def);
+
 #if defined(__cplusplus)
 } /* extern "C" */
 #endif /* defined(__cplusplus) */
diff --git a/src/lib/coll/coll.c b/src/lib/coll/coll.c
index afc15e809..9c267d384 100644
--- a/src/lib/coll/coll.c
+++ b/src/lib/coll/coll.c
@@ -133,6 +133,37 @@ coll_bin_hash(const char *s, size_t s_len, uint32_t *ph, uint32_t *pcarry,
 	return s_len;
 }
 
+/** Get a compare hint of a binary collation. */
+static uint64_t
+coll_bin_hint(const char *s, size_t s_len, struct coll *coll)
+{
+	(void)coll;
+	uint64_t result = 0;
+	uint32_t process_len = MIN(s_len, 8);
+	for (uint32_t i = 0; i < process_len; i++) {
+		result <<= 8;
+		result |= ((unsigned char *)s)[i];
+	}
+	result <<= 8 * (8 - process_len);
+	return result;
+}
+
+/** Get a compare hint of a string using ICU collation. */
+static uint64_t
+coll_icu_hint(const char *s, size_t s_len, struct coll *coll)
+{
+	assert(coll->type == COLL_TYPE_ICU);
+	UCharIterator itr;
+	uiter_setUTF8(&itr, s, s_len);
+	uint8_t buf[8];
+	uint32_t state[2] = {0, 0};
+	UErrorCode status = U_ZERO_ERROR;
+	int32_t got = ucol_nextSortKeyPart(coll->collator, &itr, state, buf,
+					   sizeof(buf), &status);
+	assert(got >= 0 && got <= 8);
+	return coll_bin_hint((const char *)buf, got, NULL);
+}
+
 /**
  * Set up ICU collator and init cmp and hash members of collation.
  * @param coll Collation to set up.
@@ -242,6 +273,7 @@ coll_icu_init_cmp(struct coll *coll, const struct coll_def *def)
 	}
 	coll->cmp = coll_icu_cmp;
 	coll->hash = coll_icu_hash;
+	coll->hint = coll_icu_hint;
 	return 0;
 }
 
@@ -356,6 +388,7 @@ coll_new(const struct coll_def *def)
 		coll->collator = NULL;
 		coll->cmp = coll_bin_cmp;
 		coll->hash = coll_bin_hash;
+		coll->hint = coll_bin_hint;
 		break;
 	default:
 		unreachable();
diff --git a/src/lib/coll/coll.h b/src/lib/coll/coll.h
index 8c9f94293..d695a02ad 100644
--- a/src/lib/coll/coll.h
+++ b/src/lib/coll/coll.h
@@ -48,6 +48,8 @@ typedef int (*coll_cmp_f)(const char *s, size_t s_len, const char *t,
 typedef uint32_t (*coll_hash_f)(const char *s, size_t s_len, uint32_t *ph,
 				uint32_t *pcarry, struct coll *coll);
 
+typedef uint64_t (*coll_hint_f)(const char *s, size_t s_len, struct coll *coll);
+
 struct UCollator;
 
 /**
@@ -62,6 +64,8 @@ struct coll {
 	/** String comparator. */
 	coll_cmp_f cmp;
 	coll_hash_f hash;
+	/** The pointer to routine calculating tuple hint. */
+	coll_hint_f hint;
 	/** Reference counter. */
 	int refs;
 	/**
-- 
2.21.0

Re: [tarantool-patches] [PATCH v5 2/4] memtx: introduce tuple compare hint

[Konstantin Osipov]

* Kirill Shcherbatov <kshcherbatov@tarantool.org> [19/03/07 12:46]:
> Implement functions for retrieving tuple hints for a particular
> key_def. Hint is an integer that can be used for tuple comparison
> optimization: if a hint of one tuple is less than a hint of another
> then the first tuple is definitely less than the second; only if
> hints are equal tuple_compare must be called for getting comparison
> result.

I have a nit on the name: I think the previous name was better.
cmp_hint would be more clear too than cmp_aux_t.

-- 
Konstantin Osipov, Moscow, Russia, +7 903 626 22 32
http://tarantool.io - www.twitter.com/kostja_osipov

Re: [tarantool-patches] [PATCH v5 2/4] memtx: introduce tuple compare hint

[Vladimir Davydov]

On Thu, Mar 07, 2019 at 01:42:21PM +0300, Konstantin Osipov wrote:
> * Kirill Shcherbatov <kshcherbatov@tarantool.org> [19/03/07 12:46]:
> > Implement functions for retrieving tuple hints for a particular
> > key_def. Hint is an integer that can be used for tuple comparison
> > optimization: if a hint of one tuple is less than a hint of another
> > then the first tuple is definitely less than the second; only if
> > hints are equal tuple_compare must be called for getting comparison
> > result.
> 
> I have a nit on the name: I think the previous name was better.
> cmp_hint would be more clear too than cmp_aux_t.

But it's not a hint per se. I mean, for a hinted tree, it is a hint, but
for a multikey it's more than that - without it we can't compare two
tuples. That said, I prefer aux over hint. If you have a better option,
please share.

Re: [PATCH v5 2/4] memtx: introduce tuple compare hint

[Vladimir Davydov]

On Thu, Mar 07, 2019 at 12:44:06PM +0300, Kirill Shcherbatov wrote:
> +void
> +key_def_set_cmp_aux_func(struct key_def *def)
> +{
> +	def->key_cmp_aux = key_hint_default;
> +	def->tuple_cmp_aux = tuple_hint_default;
> +	bool is_nullable = key_part_is_nullable(def->parts);
> +	if (def->parts->type == FIELD_TYPE_STRING && def->parts->coll != NULL) {
> +		def->key_cmp_aux = is_nullable ? key_hint_string_coll<true> :
> +						 key_hint_string_coll<false>;
> +		def->tuple_cmp_aux = is_nullable ?
> +				     tuple_hint_string_coll<true> :
> +				     tuple_hint_string_coll<false>;
> +		return;
> +	}
> +	switch (def->parts->type) {
> +	case FIELD_TYPE_UNSIGNED:
> +		def->key_cmp_aux = is_nullable ? key_hint_uint<true> :
> +						 key_hint_uint<false>;
> +		def->tuple_cmp_aux = is_nullable ? tuple_hint_uint<true> :
> +						   tuple_hint_uint<false>;
> +		break;
> +	case FIELD_TYPE_INTEGER:
> +		def->key_cmp_aux = is_nullable ? key_hint_int<true> :
> +						 key_hint_int<false>;
> +		def->tuple_cmp_aux = is_nullable ? tuple_hint_int<true> :
> +						   tuple_hint_int<false>;
> +		break;
> +	case FIELD_TYPE_STRING:
> +		def->key_cmp_aux = is_nullable ? key_hint_string<true> :
> +						 key_hint_string<false>;
> +		def->tuple_cmp_aux = is_nullable ? tuple_hint_string<true> :
> +						   tuple_hint_string<false>;
> +		break;
> +	case FIELD_TYPE_NUMBER:
> +		def->key_cmp_aux = is_nullable ? key_hint_number<true> :
> +						 key_hint_number<false>;
> +		def->tuple_cmp_aux = is_nullable ? tuple_hint_number<true> :
> +						   tuple_hint_number<false>;
> +		break;
> +	case FIELD_TYPE_BOOLEAN:
> +		def->key_cmp_aux = is_nullable ? key_hint_boolean<true> :
> +						 key_hint_boolean<false>;
> +		def->tuple_cmp_aux = is_nullable ? tuple_hint_boolean<true> :
> +						   tuple_hint_boolean<false>;
> +		break;
> +	default:
> +		break;
> +	};
>  }

I haven't looked into this patch in details yet (expect a separate
email), but at the first glance it looks there's a serious problem we
must address before moving forward - you don't take into account SCALAR
type. The tricky part is SCALAR can be converted to any other basic type
(e.g. INTEGER) without rebuilding the index. So we should either
introduce hints for SCALAR types as well and make them compatible with
basic types or disable hints for SCALAR altogether. Anyway, we need a
test for this.

Re: [PATCH v5 2/4] memtx: introduce tuple compare hint

[Vladimir Davydov]

On Thu, Mar 07, 2019 at 12:44:06PM +0300, Kirill Shcherbatov wrote:
> Implement functions for retrieving tuple hints for a particular
> key_def. Hint is an integer that can be used for tuple comparison
> optimization: if a hint of one tuple is less than a hint of another
> then the first tuple is definitely less than the second; only if
> hints are equal tuple_compare must be called for getting comparison
> result.
> 
> Hints are calculated using only the first part of key_def.
> 
> Hints are only useful when:
>  * they are precalculated and stored along with the tuple;
> calculation is not cheap (cheaper than tuple_compare btw) but
> precalculated hints allow to compare tuples without even fetching
> tuple data.
>  * first part of key_def is 'string'(for now)
>  * since hint is calculated using only the first part of key_def
> (and only first several characters if it is a string) this part
> must be different with high probability for every tuple pair.
> 
> Closes #3961
> ---
>  src/box/key_def.c        |   1 +
>  src/box/key_def.h        | 119 ++++++++++++
>  src/box/memtx_tree.c     |  32 +++-
>  src/box/tuple_compare.cc | 381 +++++++++++++++++++++++++++++++++++++++
>  src/box/tuple_compare.h  |   7 +
>  src/lib/coll/coll.c      |  33 ++++
>  src/lib/coll/coll.h      |   4 +
>  7 files changed, 567 insertions(+), 10 deletions(-)
> 
> diff --git a/src/box/key_def.c b/src/box/key_def.c
> index d4c979aa1..771c30172 100644
> --- a/src/box/key_def.c
> +++ b/src/box/key_def.c
> @@ -136,6 +136,7 @@ key_def_set_func(struct key_def *def)
>  	key_def_set_compare_func(def);
>  	key_def_set_hash_func(def);
>  	key_def_set_extract_func(def);
> +	key_def_set_cmp_aux_func(def);

You can set the extra functions in key_def_set_compare_func, because
they are all defined in tuple_compare.cc.

>  }
>  
>  static void
> diff --git a/src/box/key_def.h b/src/box/key_def.h
> index dd62f6a35..c630e6b43 100644
> --- a/src/box/key_def.h
> +++ b/src/box/key_def.h
> @@ -115,6 +115,28 @@ struct key_part {
>  
>  struct key_def;
>  struct tuple;
> +/** Comparasion auxiliary information. */
> +typedef union {
> +	/**
> +	 * Hint is a value h(t) is calculated for tuple in terms
> +	 * of particular key_def that has follows rules:

s/follows/the following

> +	 * if h(t1) < h(t2) then t1 < t2;
> +	 * if h(t1) > h(t2) then t1 > t2;
> +	 * if t1 == t2 then h(t1) == h(t2);

The last statement isn't true. Please fix.

> +	 * These rules means that instead of direct tuple vs tuple

s/means/mean

> +	 * (or tuple vs key) comparison one may compare theirs
> +	 * hints first; and only if theirs hints are equal compare

s/are equal/equal

> +	 * the tuples themselves.
> +	 */
> +	uint64_t hint;
> +} cmp_aux_t;
> +
> +/** Test if cmp_aux_t a and b are equal. */
> +static inline bool
> +cmp_aux_equal(cmp_aux_t a, cmp_aux_t b)
> +{
> +	return a.hint == b.hint;
> +}

After having pondered the issue for a while, I tend to agree with
Kostja - we better call this auxiliary data 'hint' for both uni-
and multi- key indexes, because cmp_aux sounds awkward and looks
more like a function name, not a type name; it's easy to confuse
with tuple_aux_compare.

That being said, this is how I see it now:

 - There shouldn't be a special type for the auxiliary data. It should
   be of type uint64_t. The members/variables should be called 'hint'.
   Comments should be enough to draw the difference between speeding up
   comparisons and multikey indexing. It shouldn't make the code any
   more difficult to read, because an index implementation will not
   interpret hints anyhow - it will bluntly use 'hinted' key_def
   methods. All the interpretation will be done in a few chosen index
   methods (get, create_iterator replace, build_next index_vtab methods
   in case of memtx).

 - The new key_def virtual functions should be called

   tuple_compare_hinted
   tuple_compare_with_key_hinted
   tuple_hint
   key_hint

   They should all operate with uint64_t hint, the meaning of which will
   depend on the index implementation.

 - We must not define tuple_compare and tuple_compare_with_key as well
   as plain key extractors for multikey indexes (corresponding members
   should be set to NULLs in key_def struct), because they simply don't
   make any sense for them. We must not define key_hint and tuple_hint
   methods either, because those need extra info (multikey offset).
   Passing an offset to those methods explicitly, like you do in the
   next patch, doesn't look good. Instead we should set hints in index
   vtab methods directly, without the use of key_hint/tuple_hint virtual
   methods.

>  
>  /**
>   * Get is_nullable property of key_part.
> @@ -137,6 +159,18 @@ typedef int (*tuple_compare_with_key_t)(const struct tuple *tuple_a,
>  typedef int (*tuple_compare_t)(const struct tuple *tuple_a,
>  			       const struct tuple *tuple_b,
>  			       struct key_def *key_def);
> +/** @copydoc tuple_aux_compare_with_key() */
> +typedef int (*tuple_aux_compare_with_key_t)(const struct tuple *tuple,
> +					    cmp_aux_t tuple_cmp_aux,
> +					    const char *key, uint32_t part_count,
> +					    cmp_aux_t key_cmp_aux,
> +					    struct key_def *key_def);
> +/** @copydoc tuple_aux_compare() */
> +typedef int (*tuple_aux_compare_t)(const struct tuple *tuple_a,
> +				   cmp_aux_t tuple_a_cmp_aux,
> +				   const struct tuple *tuple_b,
> +				   cmp_aux_t tuple_b_cmp_aux,
> +				   struct key_def *key_def);
>  /** @copydoc tuple_extract_key() */
>  typedef char *(*tuple_extract_key_t)(const struct tuple *tuple,
>  				     struct key_def *key_def,
> @@ -153,12 +187,23 @@ typedef uint32_t (*tuple_hash_t)(const struct tuple *tuple,
>  typedef uint32_t (*key_hash_t)(const char *key,
>  				struct key_def *key_def);
>  
> +/** @copydoc tuple_cmp_aux() */
> +typedef cmp_aux_t (*tuple_cmp_aux_t)(const struct tuple *tuple,
> +				     struct key_def *key_def);
> +
> +/** @copydoc key_cmp_aux() */
> +typedef cmp_aux_t (*key_cmp_aux_t)(const char *key, struct key_def *key_def);
> +
>  /* Definition of a multipart key. */
>  struct key_def {
>  	/** @see tuple_compare() */
>  	tuple_compare_t tuple_compare;
>  	/** @see tuple_compare_with_key() */
>  	tuple_compare_with_key_t tuple_compare_with_key;
> +	/** @see tuple_aux_compare_with_key() */
> +	tuple_aux_compare_with_key_t tuple_aux_compare_with_key;
> +	/** @see tuple_aux_compare() */
> +	tuple_aux_compare_t tuple_aux_compare;
>  	/** @see tuple_extract_key() */
>  	tuple_extract_key_t tuple_extract_key;
>  	/** @see tuple_extract_key_raw() */
> @@ -167,6 +212,10 @@ struct key_def {
>  	tuple_hash_t tuple_hash;
>  	/** @see key_hash() */
>  	key_hash_t key_hash;
> +	/** @see tuple_cmp_aux() */
> +	tuple_cmp_aux_t tuple_cmp_aux;
> +	/** @see key_cmp_aux() */
> +	key_cmp_aux_t key_cmp_aux;
>  	/**
>  	 * Minimal part count which always is unique. For example,
>  	 * if a secondary index is unique, then
> @@ -571,6 +620,52 @@ tuple_compare_with_key(const struct tuple *tuple, const char *key,
>  	return key_def->tuple_compare_with_key(tuple, key, part_count, key_def);
>  }
>  
> +/**
> + * Compare tuples using the key definition and comparasion
> + * auxillary information.

Auxillary

> + * @param tuple_a First tuple.
> + * @param tuple_a_cmp_aux Comparasion auxiliary information

Comparasion

> + *                        for the tuple_a.
> + * @param tuple_b Second tuple.
> + * @param tuple_b_cmp_aux Comparasion auxilary information

auxilary

Please enable spell checking already.

> diff --git a/src/box/tuple_compare.cc b/src/box/tuple_compare.cc
> index cf4519ccb..5b06e06b3 100644
> --- a/src/box/tuple_compare.cc
> +++ b/src/box/tuple_compare.cc
> @@ -1323,9 +1323,390 @@ tuple_compare_with_key_create(const struct key_def *def)
>  
>  /* }}} tuple_compare_with_key */
>  
> +/* {{{ tuple_aux_compare */
> +
> +#define CMP_HINT_INVALID ((uint64_t)UINT64_MAX)

Pointless type cast.

> +
> +static int
> +tuple_hinted_compare(const struct tuple *tuple_a, cmp_aux_t tuple_a_cmp_aux,
> +		     const struct tuple *tuple_b, cmp_aux_t tuple_b_cmp_aux,
> +		     struct key_def *key_def)
> +{
> +	uint64_t tuple_a_hint = tuple_a_cmp_aux.hint;
> +	uint64_t tuple_b_hint = tuple_b_cmp_aux.hint;
> +	if (likely(tuple_a_hint != tuple_b_hint &&
> +		   tuple_a_hint != CMP_HINT_INVALID &&
> +		   tuple_b_hint != CMP_HINT_INVALID))
> +		return tuple_a_hint < tuple_b_hint ? -1 : 1;
> +	else
> +		return tuple_compare(tuple_a, tuple_b, key_def);
> +}
> +
> +static tuple_aux_compare_t
> +tuple_aux_compare_create(const struct key_def *def)
> +{
> +	(void)def;
> +	return tuple_hinted_compare;
> +}
> +
> +/* }}} tuple_aux_compare */
> +
> +/* {{{ tuple_aux_compare_with_key */
> +
> +static int
> +tuple_hinted_compare_with_key(const struct tuple *tuple, cmp_aux_t tuple_cmp_aux,
> +			      const char *key, uint32_t part_count,
> +			      cmp_aux_t key_cmp_aux, struct key_def *key_def)
> +{
> +	uint64_t tuple_hint = tuple_cmp_aux.hint;
> +	uint64_t key_hint = key_cmp_aux.hint;
> +	if (likely(tuple_hint != key_hint && tuple_hint != CMP_HINT_INVALID &&

A sane compiler will treat this branch as likely anyways, because the
other branch involves an indirect function call.

> +		   key_hint != CMP_HINT_INVALID))
> +		return tuple_hint < key_hint ? -1 : 1;
> +	else
> +		return tuple_compare_with_key(tuple, key, part_count, key_def);
> +}
> +
> +static tuple_aux_compare_with_key_t
> +tuple_aux_compare_with_key_create(const struct key_def *def)
> +{
> +	(void)def;
> +	return tuple_hinted_compare_with_key;
> +}
> +
> +/* }}} tuple_aux_compare_with_key */
> +
>  void
>  key_def_set_compare_func(struct key_def *def)
>  {
>  	def->tuple_compare = tuple_compare_create(def);
>  	def->tuple_compare_with_key = tuple_compare_with_key_create(def);
> +	def->tuple_aux_compare = tuple_aux_compare_create(def);
> +	def->tuple_aux_compare_with_key =
> +		tuple_aux_compare_with_key_create(def);
> +}
> +
> +/* Tuple hints */
> +
> +static cmp_aux_t
> +key_hint_default(const char *key, struct key_def *key_def)
> +{
> +	(void)key;
> +	(void)key_def;
> +	cmp_aux_t ret;
> +	ret.hint = CMP_HINT_INVALID;
> +	return ret;
> +}
> +
> +static cmp_aux_t
> +tuple_hint_default(const struct tuple *tuple, struct key_def *key_def)
> +{
> +	(void)tuple;
> +	(void)key_def;
> +	cmp_aux_t ret;
> +	ret.hint = CMP_HINT_INVALID;
> +	return ret;
> +}
> +
> +template<bool is_nullable>
> +static cmp_aux_t
> +key_hint_uint(const char *key, struct key_def *key_def)
> +{
> +	(void)key_def;
> +	assert(key_part_is_nullable(key_def->parts) == is_nullable);
> +	assert(key_def->parts->type == FIELD_TYPE_UNSIGNED);
> +	cmp_aux_t ret;
> +	if (key == NULL || (is_nullable && mp_typeof(*key) == MP_NIL)) {
> +		ret.hint = 0;
> +		return ret;
> +	}
> +	assert(mp_typeof(*key) == MP_UINT);
> +	uint64_t val = mp_decode_uint(&key);
> +	ret.hint = unlikely(val > INT64_MAX) ? INT64_MAX :
> +		   val - (uint64_t)INT64_MIN;;

Double semicolon (;) at the end of the string.

> +	return ret;
> +}
> +
> +template<bool is_nullable>
> +static cmp_aux_t
> +tuple_hint_uint(const struct tuple *tuple, struct key_def *key_def)
> +{
> +	assert(key_part_is_nullable(key_def->parts) == is_nullable);
> +	assert(key_def->parts->type == FIELD_TYPE_UNSIGNED);
> +	cmp_aux_t ret;
> +	const char *field = tuple_field_by_part(tuple, key_def->parts);
> +	if (is_nullable && field == NULL) {
> +		ret.hint = 0;
> +		return ret;
> +	}
> +	return key_hint_uint<is_nullable>(field, key_def);
> +}
> +
> +template<bool is_nullable>
> +static cmp_aux_t
> +key_hint_int(const char *key, struct key_def *key_def)
> +{
> +	(void)key_def;
> +	assert(key_part_is_nullable(key_def->parts) == is_nullable);
> +	assert(key_def->parts->type == FIELD_TYPE_INTEGER);
> +	cmp_aux_t ret;
> +	if (key == NULL || (is_nullable && mp_typeof(*key) == MP_NIL)) {
> +		ret.hint = 0;
> +		return ret;
> +	}
> +	if (mp_typeof(*key) == MP_UINT) {
> +		uint64_t val = mp_decode_uint(&key);
> +		ret.hint = unlikely(val > INT64_MAX) ? INT64_MAX :
> +			   val - (uint64_t)INT64_MIN;

Both branches are equally cheap so 'unlikely' is pointless.

Please stop using likely/unlikely without a good reason.

> +	} else {
> +		assert(mp_typeof(*key) == MP_INT);
> +		int64_t val = mp_decode_int(&key);
> +		ret.hint = (uint64_t)val - (uint64_t)INT64_MIN;
> +	}
> +	return ret;
> +}
> +
> +template<bool is_nullable>
> +static cmp_aux_t
> +tuple_hint_int(const struct tuple *tuple, struct key_def *key_def)
> +{
> +	assert(key_part_is_nullable(key_def->parts) == is_nullable);
> +	assert(key_def->parts->type == FIELD_TYPE_INTEGER);
> +	cmp_aux_t ret;
> +	const char *field = tuple_field_by_part(tuple, key_def->parts);
> +	if (is_nullable && field == NULL) {
> +		ret.hint = 0;
> +		return ret;
> +	}
> +	return key_hint_int<is_nullable>(field, key_def);
> +}
> +
> +template<bool is_nullable>
> +static cmp_aux_t
> +key_hint_number(const char *key, struct key_def *key_def)
> +{
> +	(void)key_def;
> +	assert(key_part_is_nullable(key_def->parts) == is_nullable);
> +	assert(key_def->parts->type == FIELD_TYPE_NUMBER);
> +	cmp_aux_t ret;
> +	if (key == NULL || (is_nullable && mp_typeof(*key) == MP_NIL)) {
> +		ret.hint = 0;
> +		return ret;
> +	}
> +	uint64_t val = 0;
> +	switch (mp_typeof(*key)) {
> +	case MP_FLOAT:
> +	case MP_DOUBLE: {

A comment explaining what's going on here would be useful.

> +		double f = mp_typeof(*key) == MP_FLOAT ?
> +			   mp_decode_float(&key) : mp_decode_double(&key);
> +		if (isnan(f) || isinf(f)) {

if (!isfinite(f))

> +			ret.hint = CMP_HINT_INVALID;
> +			return ret;
> +		}
> +		double ival;
> +		(void)modf(f, &ival);
> +		if (unlikely(ival >= (double)INT64_MAX)) {

Again, 'unlikely' is pointless. Better remove all likely/unlikely from
the patch.

> +			ret.hint = INT64_MAX;
> +			return ret;
> +		}
> +		if (unlikely(ival <= (double)INT64_MIN)) {
> +			ret.hint = 0;
> +			return ret;
> +		}
> +		val = (uint64_t)ival;

This check isn't quite correct. Try running the following code:


	#include <stdio.h>
	#include <stdint.h>

	int main()
	{
		double val = INT64_MAX;
		printf("val is %lf\n", val);
		printf("val <= (double)INT64_MAX is %s\n",
		       val <= (double)INT64_MAX ? "true" : "false");
		printf("(int64_t)val is %lld\n", (int64_t)val);
	}

Here's what I get:

	val is 9223372036854775808.000000
	val <= (double)INT64_MAX is true
	(int64_t)val is -9223372036854775808

> +		break;
> +	}
> +	case MP_INT: {
> +		val = (uint64_t)mp_decode_int(&key);
> +		break;
> +	}
> +	case MP_UINT: {
> +		val = mp_decode_uint(&key);
> +		if (val > INT64_MAX) {
> +			ret.hint = INT64_MAX;
> +			return ret;
> +		}
> +		break;
> +	}
> +	default:
> +		unreachable();
> +	}
> +	ret.hint = val - (uint64_t)INT64_MIN;
> +	return ret;
> +}
> +
> +template<bool is_nullable>
> +static cmp_aux_t
> +tuple_hint_number(const struct tuple *tuple, struct key_def *key_def)
> +{
> +	assert(key_part_is_nullable(key_def->parts) == is_nullable);
> +	assert(key_def->parts->type == FIELD_TYPE_NUMBER);
> +	cmp_aux_t ret;
> +	const char *field = tuple_field_by_part(tuple, key_def->parts);
> +	if (is_nullable && field == NULL) {
> +		ret.hint = 0;
> +		return ret;
> +	}
> +	return key_hint_number<is_nullable>(field, key_def);
> +}
> +
> +template<bool is_nullable>
> +static cmp_aux_t
> +key_hint_boolean(const char *key, struct key_def *key_def)
> +{
> +	(void)key_def;
> +	assert(key_part_is_nullable(key_def->parts) == is_nullable);
> +	assert(key_def->parts->type == FIELD_TYPE_BOOLEAN);
> +	cmp_aux_t ret;
> +	if (key == NULL || (is_nullable && mp_typeof(*key) == MP_NIL)) {
> +		ret.hint = 0;
> +		return ret;
> +	}
> +	bool val = mp_decode_bool(&key);
> +	ret.hint = (uint64_t)val - (uint64_t)INT64_MIN;

What's this for?

> +	return ret;
> +}
> +
> +template<bool is_nullable>
> +static cmp_aux_t
> +tuple_hint_boolean(const struct tuple *tuple, struct key_def *key_def)
> +{
> +	assert(key_part_is_nullable(key_def->parts) == is_nullable);
> +	assert(key_def->parts->type == FIELD_TYPE_BOOLEAN);
> +	const char *field = tuple_field_by_part(tuple, key_def->parts);
> +	cmp_aux_t ret;
> +	if (is_nullable && field == NULL) {
> +		ret.hint = 0;
> +		return ret;
> +	}
> +	return key_hint_boolean<is_nullable>(field, key_def);
> +}
> +
> +template<bool is_nullable>
> +static cmp_aux_t
> +key_hint_string(const char *key, struct key_def *key_def)
> +{
> +	(void)key_def;
> +	assert(key_part_is_nullable(key_def->parts) == is_nullable);
> +	assert(key_def->parts->coll == NULL);
> +	assert(key_def->parts->type == FIELD_TYPE_STRING);
> +	cmp_aux_t ret;
> +	if (key == NULL || (is_nullable && mp_typeof(*key) == MP_NIL)) {
> +		ret.hint = 0;
> +		return ret;
> +	}
> +	assert(mp_typeof(*key) == MP_STR);
> +	uint32_t len;
> +	const unsigned char *str =
> +		(const unsigned char *)mp_decode_str(&key, &len);
> +	uint64_t result = 0;
> +	uint32_t process_len = MIN(len, 8);
> +	for (uint32_t i = 0; i < process_len; i++) {
> +		result <<= 8;
> +		result |= str[i];
> +	}
> +	result <<= 8 * (8 - process_len);
> +	ret.hint = result;
> +	return ret;
> +}
> +
> +template<bool is_nullable>
> +static cmp_aux_t
> +tuple_hint_string(const struct tuple *tuple, struct key_def *key_def)
> +{
> +	assert(key_part_is_nullable(key_def->parts) == is_nullable);
> +	assert(key_def->parts->coll == NULL);
> +	assert(key_def->parts->type == FIELD_TYPE_STRING);
> +	cmp_aux_t ret;
> +	const char *field = tuple_field_by_part(tuple, key_def->parts);
> +	if (is_nullable && field == NULL) {
> +		ret.hint = 0;
> +		return ret;
> +	}
> +	return key_hint_string<is_nullable>(field, key_def);
> +}
> +
> +template<bool is_nullable>
> +static cmp_aux_t
> +key_hint_string_coll(const char *key, struct key_def *key_def)
> +{
> +	assert(key_part_is_nullable(key_def->parts) == is_nullable);
> +	assert(key_def->parts->type == FIELD_TYPE_STRING &&
> +	        key_def->parts->coll != NULL);
> +	cmp_aux_t ret;
> +	if (key == NULL || (is_nullable && mp_typeof(*key) == MP_NIL)) {
> +		ret.hint = 0;
> +		return ret;
> +	}
> +	assert(mp_typeof(*key) == MP_STR);
> +	uint32_t len;
> +	const char *str = mp_decode_str(&key, &len);
> +	ret.hint = key_def->parts->coll->hint(str, len, key_def->parts->coll);
> +	return ret;
> +}
> +
> +template<bool is_nullable>
> +static cmp_aux_t
> +tuple_hint_string_coll(const struct tuple *tuple, struct key_def *key_def)
> +{
> +	assert(key_part_is_nullable(key_def->parts) == is_nullable);
> +	assert(key_def->parts->type == FIELD_TYPE_STRING &&
> +	        key_def->parts->coll != NULL);
> +	const char *field = tuple_field_by_part(tuple, key_def->parts);
> +	cmp_aux_t ret;
> +	if (is_nullable && field == NULL) {
> +		ret.hint = 0;
> +		return ret;
> +	}
> +	return key_hint_string_coll<is_nullable>(field, key_def);
> +}
> +
> +void
> +key_def_set_cmp_aux_func(struct key_def *def)
> +{
> +	def->key_cmp_aux = key_hint_default;
> +	def->tuple_cmp_aux = tuple_hint_default;
> +	bool is_nullable = key_part_is_nullable(def->parts);

> +	if (def->parts->type == FIELD_TYPE_STRING && def->parts->coll != NULL) {
> +		def->key_cmp_aux = is_nullable ? key_hint_string_coll<true> :
> +						 key_hint_string_coll<false>;
> +		def->tuple_cmp_aux = is_nullable ?
> +				     tuple_hint_string_coll<true> :
> +				     tuple_hint_string_coll<false>;
> +		return;
> +	}

Please move this to the switch-case below.

> +	switch (def->parts->type) {
> +	case FIELD_TYPE_UNSIGNED:
> +		def->key_cmp_aux = is_nullable ? key_hint_uint<true> :
> +						 key_hint_uint<false>;
> +		def->tuple_cmp_aux = is_nullable ? tuple_hint_uint<true> :
> +						   tuple_hint_uint<false>;
> +		break;
> +	case FIELD_TYPE_INTEGER:
> +		def->key_cmp_aux = is_nullable ? key_hint_int<true> :
> +						 key_hint_int<false>;
> +		def->tuple_cmp_aux = is_nullable ? tuple_hint_int<true> :
> +						   tuple_hint_int<false>;
> +		break;
> +	case FIELD_TYPE_STRING:
> +		def->key_cmp_aux = is_nullable ? key_hint_string<true> :
> +						 key_hint_string<false>;
> +		def->tuple_cmp_aux = is_nullable ? tuple_hint_string<true> :
> +						   tuple_hint_string<false>;
> +		break;
> +	case FIELD_TYPE_NUMBER:
> +		def->key_cmp_aux = is_nullable ? key_hint_number<true> :
> +						 key_hint_number<false>;
> +		def->tuple_cmp_aux = is_nullable ? tuple_hint_number<true> :
> +						   tuple_hint_number<false>;
> +		break;
> +	case FIELD_TYPE_BOOLEAN:
> +		def->key_cmp_aux = is_nullable ? key_hint_boolean<true> :
> +						 key_hint_boolean<false>;
> +		def->tuple_cmp_aux = is_nullable ? tuple_hint_boolean<true> :
> +						   tuple_hint_boolean<false>;
> +		break;
> +	default:
> +		break;
> +	};
>  }

Re: [PATCH v5 2/4] memtx: introduce tuple compare hint

[Vladimir Davydov]

On Thu, Mar 07, 2019 at 12:44:06PM +0300, Kirill Shcherbatov wrote:
> +/* {{{ tuple_aux_compare_with_key */
> +
> +static int
> +tuple_hinted_compare_with_key(const struct tuple *tuple, cmp_aux_t tuple_cmp_aux,
> +			      const char *key, uint32_t part_count,
> +			      cmp_aux_t key_cmp_aux, struct key_def *key_def)
> +{
> +	uint64_t tuple_hint = tuple_cmp_aux.hint;
> +	uint64_t key_hint = key_cmp_aux.hint;
> +	if (likely(tuple_hint != key_hint && tuple_hint != CMP_HINT_INVALID &&
> +		   key_hint != CMP_HINT_INVALID))
> +		return tuple_hint < key_hint ? -1 : 1;
> +	else
> +		return tuple_compare_with_key(tuple, key, part_count, key_def);

This will lead to double indirection - first you call
key_def->tuple_hinted_compare_with_key, which in turn calls
key_def->tuple_compare_with_key. This will introduce some
performance penalty, I guess. Avoid that, please.

[PATCH v5 3/4] box: move offset_slot init to tuple_format_add_field

[Kirill Shcherbatov]

Due to the fact that the allocation of offset_slot in the case of
multikey indexes will become more complicated and will be
necessary for intermediate nodes of the tuple_field tree, let's
move this logic to the tuple_format_add_field.

Needed for #1257
---
 src/box/tuple_format.c | 34 ++++++++++++++++++----------------
 1 file changed, 18 insertions(+), 16 deletions(-)

diff --git a/src/box/tuple_format.c b/src/box/tuple_format.c
index 4439ce3e0..55f4e29e8 100644
--- a/src/box/tuple_format.c
+++ b/src/box/tuple_format.c
@@ -205,13 +205,14 @@ tuple_format_field_by_id(struct tuple_format *format, uint32_t id)
  */
 static struct tuple_field *
 tuple_format_add_field(struct tuple_format *format, uint32_t fieldno,
-		       const char *path, uint32_t path_len, char **path_pool)
+		       const char *path, uint32_t path_len, bool is_sequential,
+		       int *current_slot, char **path_pool)
 {
 	struct tuple_field *field = NULL;
 	struct tuple_field *parent = tuple_format_field(format, fieldno);
 	assert(parent != NULL);
 	if (path == NULL)
-		return parent;
+		goto end;
 	field = tuple_field_new();
 	if (field == NULL)
 		goto fail;
@@ -279,12 +280,23 @@ tuple_format_add_field(struct tuple_format *format, uint32_t fieldno,
 	assert(parent != NULL);
 	/* Update tree depth information. */
 	format->fields_depth = MAX(format->fields_depth, token_count + 1);
-end:
+cleanup:
 	tuple_field_delete(field);
+end:
+	/*
+	 * In the tuple, store only offsets necessary to access
+	 * fields of non-sequential keys. First field is always
+	 * simply accessible, so we don't store an offset for it.
+	 */
+	if (parent != NULL && parent->offset_slot == TUPLE_OFFSET_SLOT_NIL &&
+	    is_sequential == false && (fieldno > 0 || path != NULL)) {
+		*current_slot = *current_slot - 1;
+		parent->offset_slot = *current_slot;
+	}
 	return parent;
 fail:
 	parent = NULL;
-	goto end;
+	goto cleanup;
 }
 
 static int
@@ -295,7 +307,8 @@ tuple_format_use_key_part(struct tuple_format *format, uint32_t field_count,
 	assert(part->fieldno < tuple_format_field_count(format));
 	struct tuple_field *field =
 		tuple_format_add_field(format, part->fieldno, part->path,
-				       part->path_len, path_pool);
+				       part->path_len, is_sequential,
+				       current_slot, path_pool);
 	if (field == NULL)
 		return -1;
 	/*
@@ -350,17 +363,6 @@ tuple_format_use_key_part(struct tuple_format *format, uint32_t field_count,
 		return -1;
 	}
 	field->is_key_part = true;
-	/*
-	 * In the tuple, store only offsets necessary to access
-	 * fields of non-sequential keys. First field is always
-	 * simply accessible, so we don't store an offset for it.
-	 */
-	if (field->offset_slot == TUPLE_OFFSET_SLOT_NIL &&
-	    is_sequential == false &&
-	    (part->fieldno > 0 || part->path != NULL)) {
-		*current_slot = *current_slot - 1;
-		field->offset_slot = *current_slot;
-	}
 	return 0;
 }
 
-- 
2.21.0

Re: [tarantool-patches] [PATCH v5 3/4] box: move offset_slot init to tuple_format_add_field

[Kirill Shcherbatov]

This patch is now. Useless. I've drop it on the branch.

[PATCH v5 4/4] box: introduce multikey indexes

[Kirill Shcherbatov]

With multikey index feature introduction, JSON path may have [*]
placeholder instead of array index: this allows to index
multiple documents by one JSON path automatically.

Example:
s = box.schema.space.create('withdata')
idx = s:create_index('idx', {parts = {{3, 'str', path = '[*].fname'},
				      {3, 'str', path = '[*].sname'}}})
_ = s:insert({1, 1, {{fname='James', sname='Bond'},
		     {fname='Austin', sname='Powers'}}})
idx:get({'Austin', 'Powers'})
---
- [1, 1, [{'fname': 'James', 'sname': 'Bond'}, {'fname': 'Austin',
  'sname': 'Powers'}]]
...

Closes #1257
---
 src/box/key_def.c         |  19 ++++
 src/box/key_def.h         |  17 +++-
 src/box/memtx_tree.c      | 179 ++++++++++++++++++++++++++++++++++++--
 src/box/tuple.c           |   8 +-
 src/box/tuple.h           | 130 +++++++++++++++++++++++----
 src/box/tuple_compare.cc  | 155 ++++++++++++++++++++++++++++-----
 src/box/tuple_format.c    | 178 ++++++++++++++++++++++++++++++++-----
 test/engine/json.result   |  80 ++++++++++++++++-
 test/engine/json.test.lua |  20 +++++
 9 files changed, 713 insertions(+), 73 deletions(-)

diff --git a/src/box/key_def.c b/src/box/key_def.c
index 771c30172..509b09b17 100644
--- a/src/box/key_def.c
+++ b/src/box/key_def.c
@@ -165,9 +165,28 @@ key_def_set_part(struct key_def *def, uint32_t part_no, uint32_t fieldno,
 		*path_pool += path_len;
 		memcpy(def->parts[part_no].path, path, path_len);
 		def->parts[part_no].path_len = path_len;
+
+		int rc;
+		struct json_lexer lexer;
+		uint32_t last_lexer_offset = 0;
+		struct json_token token;
+		json_lexer_create(&lexer, path, path_len, TUPLE_INDEX_BASE);
+		while ((rc = json_lexer_next_token(&lexer, &token)) == 0) {
+			if (token.type == JSON_TOKEN_ANY) {
+				def->has_multikey_parts = true;
+				def->parts[part_no].
+					multikey_path_offset = last_lexer_offset;
+				def->parts[part_no].is_multikey = true;
+				break;
+			} else if (token.type == JSON_TOKEN_END) {
+				break;
+			}
+			last_lexer_offset = lexer.offset;
+		}
 	} else {
 		def->parts[part_no].path = NULL;
 		def->parts[part_no].path_len = 0;
+		def->parts[part_no].is_multikey = false;
 	}
 	column_mask_set_fieldno(&def->column_mask, fieldno);
 }
diff --git a/src/box/key_def.h b/src/box/key_def.h
index c630e6b43..30a4ffcf4 100644
--- a/src/box/key_def.h
+++ b/src/box/key_def.h
@@ -97,6 +97,10 @@ struct key_part {
 	char *path;
 	/** The length of JSON path. */
 	uint32_t path_len;
+	/** The length of JSON path to JSON_TOKEN_ANY or 0. */
+	uint32_t multikey_path_offset;
+	/** True if this is multikey key part. */
+	bool is_multikey;
 	/**
 	 * Epoch of the tuple format the offset slot cached in
 	 * this part is valid for, see tuple_format::epoch.
@@ -129,6 +133,8 @@ typedef union {
 	 * the tuples themselves.
 	 */
 	uint64_t hint;
+	/** Index of item in the array used in multikey index. */
+	uint64_t multikey_idx;
 } cmp_aux_t;
 
 /** Test if cmp_aux_t a and b are equal. */
@@ -189,7 +195,8 @@ typedef uint32_t (*key_hash_t)(const char *key,
 
 /** @copydoc tuple_cmp_aux() */
 typedef cmp_aux_t (*tuple_cmp_aux_t)(const struct tuple *tuple,
-				     struct key_def *key_def);
+				     struct key_def *key_def,
+				     uint64_t multikey_idx);
 
 /** @copydoc key_cmp_aux() */
 typedef cmp_aux_t (*key_cmp_aux_t)(const char *key, struct key_def *key_def);
@@ -228,6 +235,8 @@ struct key_def {
 	bool is_nullable;
 	/** True if some key part has JSON path. */
 	bool has_json_paths;
+	/** True if some part has array index placeholder *. */
+	bool has_multikey_parts;
 	/**
 	 * True, if some key parts can be absent in a tuple. These
 	 * fields assumed to be MP_NIL.
@@ -723,12 +732,14 @@ key_hash(const char *key, struct key_def *key_def)
  * Get a comparison auxiliary information for a tuple.
  * @param tuple - tuple to get cmp_aux_t of.
  * @param key_def - key_def that defines which comparison is used.
+ * @param multikey_idx - index of multikey array item.
  * @return the comparison auxiliary information.
  */
 static inline cmp_aux_t
-tuple_cmp_aux(const struct tuple *tuple, struct key_def *key_def)
+tuple_cmp_aux(const struct tuple *tuple, struct key_def *key_def,
+	      uint64_t multikey_idx)
 {
-	return key_def->tuple_cmp_aux(tuple, key_def);
+	return key_def->tuple_cmp_aux(tuple, key_def, multikey_idx);
 }
 
 /**
diff --git a/src/box/memtx_tree.c b/src/box/memtx_tree.c
index 4b0886bef..78d6970b2 100644
--- a/src/box/memtx_tree.c
+++ b/src/box/memtx_tree.c
@@ -91,11 +91,11 @@ memtx_tree_data_clear(struct memtx_tree_data *data)
  */
 static void
 memtx_tree_data_set(struct memtx_tree_data *data, struct tuple *tuple,
-		    struct key_def *key_def)
+		    struct key_def *key_def, uint64_t multikey_idx)
 {
 	(void)key_def;
 	data->tuple = tuple;
-	data->aux_info = tuple_cmp_aux(tuple, key_def);
+	data->aux_info = tuple_cmp_aux(tuple, key_def, multikey_idx);
 }
 
 /**
@@ -578,7 +578,8 @@ memtx_tree_index_replace(struct index *base, struct tuple *old_tuple,
 	struct key_def *key_def = index->tree.arg;
 	if (new_tuple) {
 		struct memtx_tree_data new_data;
-		memtx_tree_data_set(&new_data, new_tuple, key_def);
+		memtx_tree_data_set(&new_data, new_tuple, key_def,
+				    INVALID_MULTIKEY_INDEX);
 		struct memtx_tree_data dup_data;
 		memtx_tree_data_clear(&dup_data);
 
@@ -610,13 +611,105 @@ memtx_tree_index_replace(struct index *base, struct tuple *old_tuple,
 	}
 	if (old_tuple) {
 		struct memtx_tree_data old_data;
-		memtx_tree_data_set(&old_data, old_tuple, key_def);
+		memtx_tree_data_set(&old_data, old_tuple, key_def,
+				    INVALID_MULTIKEY_INDEX);
 		memtx_tree_delete(&index->tree, old_data);
 	}
 	*result = old_tuple;
 	return 0;
 }
 
+static int
+multikey_get_array_sz(struct tuple *tuple, struct key_def *key_def)
+{
+	assert(key_def->has_multikey_parts);
+	struct key_part *part = key_def->parts;
+	/* FIXME: don't like it... */
+	while (part < key_def->parts + key_def->part_count &&
+	       !part->is_multikey)
+		part++;
+	assert(part->path != NULL && part->is_multikey);
+	const char *field =
+		tuple_field_raw_by_path(tuple_format(tuple), tuple_data(tuple),
+					tuple_field_map(tuple), part->fieldno,
+					part->path, part->multikey_path_offset,
+					0, NULL, INVALID_MULTIKEY_INDEX);
+	assert(mp_typeof(*field) == MP_ARRAY);
+	return mp_decode_array(&field);
+}
+
+int
+memtx_multikey_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 key_def *key_def = index->tree.arg;
+	if (new_tuple != NULL) {
+		int errcode = 0, tree_res = 0;
+		struct tuple *dup_tuple = NULL;
+		int multikey_idx = 0;
+		int sz = multikey_get_array_sz(new_tuple, key_def);
+		for (; multikey_idx < sz; multikey_idx++) {
+			struct memtx_tree_data new_data;
+			memtx_tree_data_set(&new_data, new_tuple, key_def,
+					    multikey_idx);
+			struct memtx_tree_data dup_data;
+			memtx_tree_data_clear(&dup_data);
+			tree_res = memtx_tree_insert(&index->tree, new_data,
+						     &dup_data);
+			if (tree_res != 0) {
+				diag_set(OutOfMemory, MEMTX_EXTENT_SIZE,
+					 "memtx_tree_index", "replace");
+				break;
+			}
+			dup_tuple = dup_data.tuple;
+			errcode = replace_check_dup(old_tuple, dup_tuple, mode);
+			if (errcode != 0) {
+				memtx_tree_delete(&index->tree, new_data);
+				if (dup_tuple != NULL) {
+					memtx_tree_insert(&index->tree,
+							  dup_data, NULL);
+				}
+				struct space *sp =
+					space_cache_find(base->def->space_id);
+				if (sp != NULL) {
+					diag_set(ClientError, errcode,
+						 base->def->name,
+						 space_name(sp));
+				}
+				break;
+			}
+		}
+		if (tree_res != 0 || errcode != 0) {
+			multikey_idx--;
+			for (; multikey_idx >= 0; multikey_idx--) {
+				struct memtx_tree_data data;
+				memtx_tree_data_set(&data, new_tuple, key_def,
+						    multikey_idx);
+				memtx_tree_delete(&index->tree, data);
+			}
+			return -1;
+		}
+		if (dup_tuple != NULL) {
+			*result = dup_tuple;
+			return 0;
+		}
+	}
+	if (old_tuple != NULL) {
+		int sz = multikey_get_array_sz(old_tuple, key_def);
+		for (int multikey_idx = 0; multikey_idx < sz; multikey_idx++) {
+			struct memtx_tree_data old_data;
+			memtx_tree_data_set(&old_data, old_tuple, key_def,
+					    multikey_idx);
+			memtx_tree_delete(&index->tree, old_data);
+		}
+	}
+	*result = old_tuple;
+	return 0;
+}
+
 static struct iterator *
 memtx_tree_index_create_iterator(struct index *base, enum iterator_type type,
 				 const char *key, uint32_t part_count)
@@ -718,7 +811,48 @@ memtx_tree_index_build_next(struct index *base, struct tuple *tuple)
 	}
 	struct memtx_tree_data *elem =
 		&index->build_array[index->build_array_size++];
-	memtx_tree_data_set(elem, tuple, key_def);
+	memtx_tree_data_set(elem, tuple, key_def, INVALID_MULTIKEY_INDEX);
+	return 0;
+}
+
+static int
+memtx_multikey_tree_index_build_next(struct index *base, struct tuple *tuple)
+{
+	struct memtx_tree_index *index = (struct memtx_tree_index *)base;
+	struct key_def *key_def = index->tree.arg;
+	int sz = multikey_get_array_sz(tuple, key_def);
+
+	if (index->build_array == NULL) {
+		index->build_array =
+			(struct memtx_tree_data *)malloc(MEMTX_EXTENT_SIZE);
+		if (index->build_array == NULL) {
+			diag_set(OutOfMemory, MEMTX_EXTENT_SIZE,
+				 "memtx_tree_index", "build_next");
+			return -1;
+		}
+		index->build_array_alloc_size =
+			MEMTX_EXTENT_SIZE / sizeof(index->build_array[0]);
+	}
+	assert(index->build_array_size <= index->build_array_alloc_size);
+	if (index->build_array_size == index->build_array_alloc_size) {
+		index->build_array_alloc_size = index->build_array_alloc_size +
+					index->build_array_alloc_size / 2;
+		struct memtx_tree_data *tmp =
+			realloc(index->build_array,
+				index->build_array_alloc_size * sizeof(*tmp));
+		if (tmp == NULL) {
+			diag_set(OutOfMemory, index->build_array_alloc_size *
+				 sizeof(*tmp), "memtx_tree_index", "build_next");
+			return -1;
+		}
+		index->build_array = tmp;
+	}
+	for (int multikey_idx = 0; multikey_idx < sz; multikey_idx++) {
+		struct memtx_tree_data *elem =
+			&index->build_array[index->build_array_size++];
+		assert(index->build_array_size < index->build_array_alloc_size);
+		memtx_tree_data_set(elem, tuple, key_def, multikey_idx);
+	}
 	return 0;
 }
 
@@ -824,6 +958,36 @@ static const struct index_vtab memtx_tree_index_vtab = {
 	/* .end_build = */ memtx_tree_index_end_build,
 };
 
+static const struct index_vtab memtx_multikey_tree_index_vtab = {
+	/* .destroy = */ memtx_tree_index_destroy,
+	/* .commit_create = */ generic_index_commit_create,
+	/* .abort_create = */ generic_index_abort_create,
+	/* .commit_modify = */ generic_index_commit_modify,
+	/* .commit_drop = */ generic_index_commit_drop,
+	/* .update_def = */ memtx_tree_index_update_def,
+	/* .depends_on_pk = */ memtx_tree_index_depends_on_pk,
+	/* .def_change_requires_rebuild = */
+		memtx_index_def_change_requires_rebuild,
+	/* .size = */ memtx_tree_index_size,
+	/* .bsize = */ memtx_tree_index_bsize,
+	/* .min = */ generic_index_min,
+	/* .max = */ generic_index_max,
+	/* .random = */ memtx_tree_index_random,
+	/* .count = */ memtx_tree_index_count,
+	/* .get = */ memtx_tree_index_get,
+	/* .replace = */ memtx_multikey_tree_index_replace,
+	/* .create_iterator = */ memtx_tree_index_create_iterator,
+	/* .create_snapshot_iterator = */
+		memtx_tree_index_create_snapshot_iterator,
+	/* .stat = */ generic_index_stat,
+	/* .compact = */ generic_index_compact,
+	/* .reset_stat = */ generic_index_reset_stat,
+	/* .begin_build = */ memtx_tree_index_begin_build,
+	/* .reserve = */ memtx_tree_index_reserve,
+	/* .build_next = */ memtx_multikey_tree_index_build_next,
+	/* .end_build = */ memtx_tree_index_end_build,
+};
+
 struct index *
 memtx_tree_index_new(struct memtx_engine *memtx, struct index_def *def)
 {
@@ -834,8 +998,11 @@ memtx_tree_index_new(struct memtx_engine *memtx, struct index_def *def)
 			 "malloc", "struct memtx_tree_index");
 		return NULL;
 	}
+	const struct index_vtab *vtab = def->key_def->has_multikey_parts ?
+					&memtx_multikey_tree_index_vtab :
+					&memtx_tree_index_vtab;
 	if (index_create(&index->base, (struct engine *)memtx,
-			 &memtx_tree_index_vtab, def) != 0) {
+			 vtab, def) != 0) {
 		free(index);
 		return NULL;
 	}
diff --git a/src/box/tuple.c b/src/box/tuple.c
index 7f06d4053..67f4eecf4 100644
--- a/src/box/tuple.c
+++ b/src/box/tuple.c
@@ -455,7 +455,8 @@ tuple_field_go_to_key(const char **field, const char *key, int len)
 }
 
 int
-tuple_go_to_path(const char **data, const char *path, uint32_t path_len)
+tuple_go_to_path_multikey(const char **data, const char *path,
+			  uint32_t path_len, uint64_t multikey_idx)
 {
 	int rc;
 	struct json_lexer lexer;
@@ -463,6 +464,8 @@ tuple_go_to_path(const char **data, const char *path, uint32_t path_len)
 	json_lexer_create(&lexer, path, path_len, TUPLE_INDEX_BASE);
 	while ((rc = json_lexer_next_token(&lexer, &token)) == 0) {
 		switch (token.type) {
+		case JSON_TOKEN_ANY:
+			token.num = (int)multikey_idx;
 		case JSON_TOKEN_NUM:
 			rc = tuple_field_go_to_index(data, token.num);
 			break;
@@ -532,7 +535,8 @@ tuple_field_raw_by_full_path(struct tuple_format *format, const char *tuple,
 	}
 	return tuple_field_raw_by_path(format, tuple, field_map, fieldno,
 				       path + lexer.offset,
-				       path_len - lexer.offset, NULL);
+				       path_len - lexer.offset, 0, NULL,
+				       INVALID_MULTIKEY_INDEX);
 }
 
 /* }}} tuple_field_* getters */
diff --git a/src/box/tuple.h b/src/box/tuple.h
index 8b12fd5a8..16d51920b 100644
--- a/src/box/tuple.h
+++ b/src/box/tuple.h
@@ -45,6 +45,8 @@ struct slab_arena;
 struct quota;
 struct key_part;
 
+#define INVALID_MULTIKEY_INDEX UINT64_MAX
+
 /**
  * A format for standalone tuples allocated on runtime arena.
  * \sa tuple_new().
@@ -508,11 +510,32 @@ tuple_field_count(const struct tuple *tuple)
  *                      with NULL.
  * @param path The path to process.
  * @param path_len The length of the @path.
+ * @param multikey_index The multikey index hint - index of item
+ *                       for JSON_TOKEN_ANY level.
  * @retval 0 On success.
  * @retval -1 In case of error in JSON path.
  */
 int
-tuple_go_to_path(const char **data, const char *path, uint32_t path_len);
+tuple_go_to_path_multikey(const char **data, const char *path,
+			  uint32_t path_len, uint64_t multikey_idx);
+
+/**
+ * Retrieve msgpack data by JSON path.
+ * @param data[in, out] Pointer to msgpack with data.
+ *                      If the field cannot be retrieved be the
+ *                      specified path @path, it is overwritten
+ *                      with NULL.
+ * @param path The path to process.
+ * @param path_len The length of the @path.
+ * @retval 0 On success.
+ * @retval -1 In case of error in JSON path.
+ */
+static inline int
+tuple_go_to_path(const char **data, const char *path, uint32_t path_len)
+{
+	return tuple_go_to_path_multikey(data, path, path_len,
+					 INVALID_MULTIKEY_INDEX);
+}
 
 /**
  * Get tuple field by field index and relative JSON path.
@@ -533,7 +556,8 @@ static inline const char *
 tuple_field_raw_by_path(struct tuple_format *format, const char *tuple,
 			const uint32_t *field_map, uint32_t fieldno,
 			const char *path, uint32_t path_len,
-			int32_t *offset_slot_hint)
+			uint32_t multikey_path_offset,
+			int32_t *offset_slot_hint, uint64_t multikey_idx)
 {
 	int32_t offset_slot;
 	if (offset_slot_hint != NULL &&
@@ -547,17 +571,51 @@ tuple_field_raw_by_path(struct tuple_format *format, const char *tuple,
 			mp_decode_array(&tuple);
 			return tuple;
 		}
-		field = tuple_format_field_by_path(format, fieldno, path,
-						   path_len);
-		assert(field != NULL || path != NULL);
-		if (path != NULL && field == NULL)
-			goto parse;
-		offset_slot = field->offset_slot;
-		if (offset_slot == TUPLE_OFFSET_SLOT_NIL)
-			goto parse;
+		if (multikey_idx == INVALID_MULTIKEY_INDEX) {
+			field = tuple_format_field_by_path(format, fieldno,
+							   path, path_len);
+			assert(field != NULL || path != NULL);
+			if (path != NULL && field == NULL)
+				goto parse;
+			offset_slot = field->offset_slot;
+			if (offset_slot == TUPLE_OFFSET_SLOT_NIL)
+				goto parse;
+		} else {
+			assert(path != NULL);
+			field = tuple_format_field_by_path(format, fieldno,
+							   path,
+							   multikey_path_offset);
+			assert(json_token_is_multikey(&field->token));
+			assert(field->type == FIELD_TYPE_ARRAY);
+
+			struct json_token multikey_token;
+			multikey_token.type = JSON_TOKEN_ANY;
+			struct tuple_field *multikey_field =
+				json_tree_lookup_entry(&format->fields,
+					&field->token, &multikey_token,
+					struct tuple_field, token);
+			assert(multikey_field != NULL);
+			offset_slot = multikey_field->offset_slot;
+		}
 		if (offset_slot_hint != NULL)
 			*offset_slot_hint = offset_slot;
 offset_slot_access:
+		if (multikey_idx != INVALID_MULTIKEY_INDEX) {
+			/* Switch to multikey local field_map. */
+			uint32_t field_map_off =
+				(field_map[offset_slot] >> 4) * sizeof(uint32_t);
+			uint32_t multikey_group_size =
+				field_map[offset_slot] & ((1 << 4) - 1);
+			field_map =
+				(uint32_t *)((char *)field_map - field_map_off);
+
+			field = tuple_format_field_by_path(format, fieldno,
+							   path, path_len);
+			assert(field != NULL);
+			assert(field->offset_slot != TUPLE_OFFSET_SLOT_NIL);
+			offset_slot = field->offset_slot *
+				      multikey_group_size + multikey_idx;
+		}
 		/* Indexed field */
 		if (field_map[offset_slot] == 0)
 			return NULL;
@@ -572,8 +630,8 @@ parse:
 		for (uint32_t k = 0; k < fieldno; k++)
 			mp_next(&tuple);
 		if (path != NULL &&
-		    unlikely(tuple_go_to_path(&tuple, path,
-						    path_len) != 0))
+		    unlikely(tuple_go_to_path_multikey(&tuple, path, path_len,
+						       multikey_idx) != 0))
 			return NULL;
 	}
 	return tuple;
@@ -595,7 +653,8 @@ tuple_field_raw(struct tuple_format *format, const char *tuple,
 		const uint32_t *field_map, uint32_t field_no)
 {
 	return tuple_field_raw_by_path(format, tuple, field_map, field_no,
-				       NULL, 0, NULL);
+				       NULL, 0, 0, NULL,
+				       INVALID_MULTIKEY_INDEX);
 }
 
 /**
@@ -634,16 +693,18 @@ tuple_field_raw_by_full_path(struct tuple_format *format, const char *tuple,
 			     uint32_t path_len, uint32_t path_hash);
 
 /**
- * Get a tuple field pointed to by an index part.
+ * Get a tuple field pointed to by an index part and multikey hint.
  * @param format Tuple format.
  * @param tuple A pointer to MessagePack array.
  * @param field_map A pointer to the LAST element of field map.
+ * @param multikey_idx A multikey hint.
  * @param part Index part to use.
  * @retval Field data if the field exists or NULL.
  */
 static inline const char *
-tuple_field_raw_by_part(struct tuple_format *format, const char *data,
-			const uint32_t *field_map, struct key_part *part)
+tuple_field_raw_by_part_multikey(struct tuple_format *format, const char *data,
+				 const uint32_t *field_map,
+				 struct key_part *part, uint64_t multikey_idx)
 {
 	if (unlikely(part->format_epoch != format->epoch)) {
 		assert(format->epoch != 0);
@@ -656,7 +717,42 @@ tuple_field_raw_by_part(struct tuple_format *format, const char *data,
 	}
 	return tuple_field_raw_by_path(format, data, field_map, part->fieldno,
 				       part->path, part->path_len,
-				       &part->offset_slot_cache);
+				       part->multikey_path_offset,
+				       &part->offset_slot_cache, multikey_idx);
+}
+
+/**
+ * Get a field refereed by index @part and multikey hint in tuple.
+ * @param tuple Tuple to get the field from.
+ * @param part Index part to use.
+ * @param multikey_idx A multikey hint.
+ * @retval Field data if the field exists or NULL.
+ */
+static inline const char *
+tuple_field_by_part_multikey(const struct tuple *tuple, struct key_part *part,
+			     uint64_t multikey_idx)
+{
+	return tuple_field_raw_by_part_multikey(tuple_format(tuple),
+						tuple_data(tuple),
+						tuple_field_map(tuple), part,
+						multikey_idx);
+}
+
+
+/**
+ * Get a tuple field pointed to by an index part.
+ * @param format Tuple format.
+ * @param tuple A pointer to MessagePack array.
+ * @param field_map A pointer to the LAST element of field map.
+ * @param part Index part to use.
+ * @retval Field data if the field exists or NULL.
+ */
+static inline const char *
+tuple_field_raw_by_part(struct tuple_format *format, const char *data,
+			const uint32_t *field_map, struct key_part *part)
+{
+	return tuple_field_raw_by_part_multikey(format, data, field_map,
+						part, INVALID_MULTIKEY_INDEX);
 }
 
 /**
diff --git a/src/box/tuple_compare.cc b/src/box/tuple_compare.cc
index 5b06e06b3..dbf7bb4f6 100644
--- a/src/box/tuple_compare.cc
+++ b/src/box/tuple_compare.cc
@@ -458,10 +458,12 @@ tuple_common_key_parts(const struct tuple *tuple_a, const struct tuple *tuple_b,
 	return i;
 }
 
-template<bool is_nullable, bool has_optional_parts, bool has_json_paths>
+template<bool is_nullable, bool has_optional_parts, bool has_json_paths,
+	 bool is_multikey>
 static inline int
-tuple_compare_slowpath(const struct tuple *tuple_a, const struct tuple *tuple_b,
-		       struct key_def *key_def)
+tuple_compare_slowpath_multikey(const struct tuple *tuple_a,
+		cmp_aux_t tuple_a_cmp_aux, const struct tuple *tuple_b,
+		cmp_aux_t tuple_b_cmp_aux, struct key_def *key_def)
 {
 	assert(has_json_paths == key_def->has_json_paths);
 	assert(!has_optional_parts || is_nullable);
@@ -471,7 +473,7 @@ tuple_compare_slowpath(const struct tuple *tuple_a, const struct tuple *tuple_b,
 	const char *tuple_a_raw = tuple_data(tuple_a);
 	const char *tuple_b_raw = tuple_data(tuple_b);
 	if (key_def->part_count == 1 && part->fieldno == 0 &&
-	    (!has_json_paths || part->path == NULL)) {
+	    (!has_json_paths || part->path == NULL) && !is_multikey) {
 		/*
 		 * First field can not be optional - empty tuples
 		 * can not exist.
@@ -509,7 +511,14 @@ tuple_compare_slowpath(const struct tuple *tuple_a, const struct tuple *tuple_b,
 		end = part + key_def->part_count;
 
 	for (; part < end; part++) {
-		if (has_json_paths) {
+		if (is_multikey) {
+			field_a = tuple_field_raw_by_part_multikey(format_a,
+					tuple_a_raw, field_map_a, part,
+					tuple_a_cmp_aux.multikey_idx);
+			field_b = tuple_field_raw_by_part_multikey(format_b,
+					tuple_b_raw, field_map_b, part,
+					tuple_b_cmp_aux.multikey_idx);
+		} else if (has_json_paths) {
 			field_a = tuple_field_raw_by_part(format_a, tuple_a_raw,
 							  field_map_a, part);
 			field_b = tuple_field_raw_by_part(format_b, tuple_b_raw,
@@ -566,7 +575,14 @@ tuple_compare_slowpath(const struct tuple *tuple_a, const struct tuple *tuple_b,
 	 */
 	end = key_def->parts + key_def->part_count;
 	for (; part < end; ++part) {
-		if (has_json_paths) {
+		if (is_multikey) {
+			field_a = tuple_field_raw_by_part_multikey(format_a,
+					tuple_a_raw, field_map_a, part,
+					tuple_a_cmp_aux.multikey_idx);
+			field_b = tuple_field_raw_by_part_multikey(format_b,
+					tuple_b_raw, field_map_b, part,
+					tuple_b_cmp_aux.multikey_idx);
+		} else if (has_json_paths) {
 			field_a = tuple_field_raw_by_part(format_a, tuple_a_raw,
 							  field_map_a, part);
 			field_b = tuple_field_raw_by_part(format_b, tuple_b_raw,
@@ -592,9 +608,23 @@ tuple_compare_slowpath(const struct tuple *tuple_a, const struct tuple *tuple_b,
 
 template<bool is_nullable, bool has_optional_parts, bool has_json_paths>
 static inline int
-tuple_compare_with_key_slowpath(const struct tuple *tuple, const char *key,
-				uint32_t part_count, struct key_def *key_def)
+tuple_compare_slowpath(const struct tuple *tuple_a, const struct tuple *tuple_b,
+		       struct key_def *key_def)
+{
+	cmp_aux_t dummy;
+	return tuple_compare_slowpath_multikey
+			<is_nullable, has_optional_parts, has_json_paths, false>(
+				tuple_a, dummy, tuple_b, dummy, key_def);
+}
+
+template<bool is_nullable, bool has_optional_parts, bool has_json_paths,
+	 bool is_multikey>
+static inline int
+tuple_compare_with_key_slowpath_multikey(const struct tuple *tuple,
+		cmp_aux_t tuple_cmp_aux, const char *key, uint32_t part_count,
+		cmp_aux_t key_cmp_aux, struct key_def *key_def)
 {
+	(void)key_cmp_aux;
 	assert(has_json_paths == key_def->has_json_paths);
 	assert(!has_optional_parts || is_nullable);
 	assert(is_nullable == key_def->is_nullable);
@@ -608,7 +638,11 @@ tuple_compare_with_key_slowpath(const struct tuple *tuple, const char *key,
 	enum mp_type a_type, b_type;
 	if (likely(part_count == 1)) {
 		const char *field;
-		if (has_json_paths) {
+		if (is_multikey) {
+			field = tuple_field_raw_by_part_multikey(format,
+					tuple_raw, field_map, part,
+					tuple_cmp_aux.multikey_idx);
+		} else if (has_json_paths) {
 			field = tuple_field_raw_by_part(format, tuple_raw,
 							field_map, part);
 		} else {
@@ -639,7 +673,11 @@ tuple_compare_with_key_slowpath(const struct tuple *tuple, const char *key,
 	int rc;
 	for (; part < end; ++part, mp_next(&key)) {
 		const char *field;
-		if (has_json_paths) {
+		if (is_multikey) {
+			field = tuple_field_raw_by_part_multikey(format,
+					tuple_raw, field_map, part,
+					tuple_cmp_aux.multikey_idx);
+		} else if (has_json_paths) {
 			field = tuple_field_raw_by_part(format, tuple_raw,
 							field_map, part);
 		} else {
@@ -675,6 +713,17 @@ tuple_compare_with_key_slowpath(const struct tuple *tuple, const char *key,
 	return 0;
 }
 
+template<bool is_nullable, bool has_optional_parts, bool has_json_paths>
+static inline int
+tuple_compare_with_key_slowpath(const struct tuple *tuple, const char *key,
+				uint32_t part_count, struct key_def *key_def)
+{
+	cmp_aux_t dummy;
+	return tuple_compare_with_key_slowpath_multikey
+		<is_nullable, has_optional_parts, has_json_paths, false>(
+			tuple, dummy, key, part_count, dummy, key_def);
+}
+
 template<bool is_nullable>
 static inline int
 key_compare_parts(const char *key_a, const char *key_b, uint32_t part_count,
@@ -1342,11 +1391,28 @@ tuple_hinted_compare(const struct tuple *tuple_a, cmp_aux_t tuple_a_cmp_aux,
 		return tuple_compare(tuple_a, tuple_b, key_def);
 }
 
+static const tuple_aux_compare_t compare_slowpath_multikey_funcs[] = {
+	tuple_compare_slowpath_multikey<false, false, false, true>,
+	tuple_compare_slowpath_multikey<true, false, false, true>,
+	tuple_compare_slowpath_multikey<false, true, false, true>,
+	tuple_compare_slowpath_multikey<true, true, false, true>,
+	tuple_compare_slowpath_multikey<false, false, true, true>,
+	tuple_compare_slowpath_multikey<true, false, true, true>,
+	tuple_compare_slowpath_multikey<false, true, true, true>,
+	tuple_compare_slowpath_multikey<true, true, true, true>
+};
+
 static tuple_aux_compare_t
 tuple_aux_compare_create(const struct key_def *def)
 {
-	(void)def;
-	return tuple_hinted_compare;
+	if (def->has_multikey_parts) {
+		int cmp_func_idx = (def->is_nullable ? 1 : 0) +
+				   2 * (def->has_optional_parts ? 1 : 0) +
+				   4 * (def->has_json_paths ? 1 : 0);
+		return compare_slowpath_multikey_funcs[cmp_func_idx];
+	} else {
+		return tuple_hinted_compare;
+	}
 }
 
 /* }}} tuple_aux_compare */
@@ -1367,11 +1433,29 @@ tuple_hinted_compare_with_key(const struct tuple *tuple, cmp_aux_t tuple_cmp_aux
 		return tuple_compare_with_key(tuple, key, part_count, key_def);
 }
 
+static const tuple_aux_compare_with_key_t
+		compare_with_key_slowpath_multikey_funcs[] = {
+	tuple_compare_with_key_slowpath_multikey<false, false, false, true>,
+	tuple_compare_with_key_slowpath_multikey<true, false, false, true>,
+	tuple_compare_with_key_slowpath_multikey<false, true, false, true>,
+	tuple_compare_with_key_slowpath_multikey<true, true, false, true>,
+	tuple_compare_with_key_slowpath_multikey<false, false, true, true>,
+	tuple_compare_with_key_slowpath_multikey<true, false, true, true>,
+	tuple_compare_with_key_slowpath_multikey<false, true, true, true>,
+	tuple_compare_with_key_slowpath_multikey<true, true, true, true>
+};
+
 static tuple_aux_compare_with_key_t
 tuple_aux_compare_with_key_create(const struct key_def *def)
 {
-	(void)def;
-	return tuple_hinted_compare_with_key;
+	if (def->has_multikey_parts) {
+		int cmp_func_idx = (def->is_nullable ? 1 : 0) +
+				    2 * (def->has_optional_parts ? 1 : 0) +
+				    4 * (def->has_json_paths ? 1 : 0);
+		return compare_with_key_slowpath_multikey_funcs[cmp_func_idx];
+	} else {
+		return tuple_hinted_compare_with_key;
+	}
 }
 
 /* }}} tuple_aux_compare_with_key */
@@ -1399,10 +1483,12 @@ key_hint_default(const char *key, struct key_def *key_def)
 }
 
 static cmp_aux_t
-tuple_hint_default(const struct tuple *tuple, struct key_def *key_def)
+tuple_hint_default(const struct tuple *tuple, struct key_def *key_def,
+		   uint64_t multikey_idx)
 {
 	(void)tuple;
 	(void)key_def;
+	(void)multikey_idx;
 	cmp_aux_t ret;
 	ret.hint = CMP_HINT_INVALID;
 	return ret;
@@ -1429,8 +1515,10 @@ key_hint_uint(const char *key, struct key_def *key_def)
 
 template<bool is_nullable>
 static cmp_aux_t
-tuple_hint_uint(const struct tuple *tuple, struct key_def *key_def)
+tuple_hint_uint(const struct tuple *tuple, struct key_def *key_def,
+		uint64_t multikey_idx)
 {
+	(void)multikey_idx;
 	assert(key_part_is_nullable(key_def->parts) == is_nullable);
 	assert(key_def->parts->type == FIELD_TYPE_UNSIGNED);
 	cmp_aux_t ret;
@@ -1468,8 +1556,10 @@ key_hint_int(const char *key, struct key_def *key_def)
 
 template<bool is_nullable>
 static cmp_aux_t
-tuple_hint_int(const struct tuple *tuple, struct key_def *key_def)
+tuple_hint_int(const struct tuple *tuple, struct key_def *key_def,
+	       uint64_t multikey_idx)
 {
+	(void)multikey_idx;
 	assert(key_part_is_nullable(key_def->parts) == is_nullable);
 	assert(key_def->parts->type == FIELD_TYPE_INTEGER);
 	cmp_aux_t ret;
@@ -1537,8 +1627,10 @@ key_hint_number(const char *key, struct key_def *key_def)
 
 template<bool is_nullable>
 static cmp_aux_t
-tuple_hint_number(const struct tuple *tuple, struct key_def *key_def)
+tuple_hint_number(const struct tuple *tuple, struct key_def *key_def,
+		  uint64_t multikey_idx)
 {
+	(void)multikey_idx;
 	assert(key_part_is_nullable(key_def->parts) == is_nullable);
 	assert(key_def->parts->type == FIELD_TYPE_NUMBER);
 	cmp_aux_t ret;
@@ -1569,8 +1661,10 @@ key_hint_boolean(const char *key, struct key_def *key_def)
 
 template<bool is_nullable>
 static cmp_aux_t
-tuple_hint_boolean(const struct tuple *tuple, struct key_def *key_def)
+tuple_hint_boolean(const struct tuple *tuple, struct key_def *key_def,
+		   uint64_t multikey_idx)
 {
+	(void)multikey_idx;
 	assert(key_part_is_nullable(key_def->parts) == is_nullable);
 	assert(key_def->parts->type == FIELD_TYPE_BOOLEAN);
 	const char *field = tuple_field_by_part(tuple, key_def->parts);
@@ -1612,8 +1706,10 @@ key_hint_string(const char *key, struct key_def *key_def)
 
 template<bool is_nullable>
 static cmp_aux_t
-tuple_hint_string(const struct tuple *tuple, struct key_def *key_def)
+tuple_hint_string(const struct tuple *tuple, struct key_def *key_def,
+		  uint64_t multikey_idx)
 {
+	(void)multikey_idx;
 	assert(key_part_is_nullable(key_def->parts) == is_nullable);
 	assert(key_def->parts->coll == NULL);
 	assert(key_def->parts->type == FIELD_TYPE_STRING);
@@ -1647,8 +1743,10 @@ key_hint_string_coll(const char *key, struct key_def *key_def)
 
 template<bool is_nullable>
 static cmp_aux_t
-tuple_hint_string_coll(const struct tuple *tuple, struct key_def *key_def)
+tuple_hint_string_coll(const struct tuple *tuple, struct key_def *key_def,
+		       uint64_t multikey_idx)
 {
+	(void)multikey_idx;
 	assert(key_part_is_nullable(key_def->parts) == is_nullable);
 	assert(key_def->parts->type == FIELD_TYPE_STRING &&
 	        key_def->parts->coll != NULL);
@@ -1661,11 +1759,26 @@ tuple_hint_string_coll(const struct tuple *tuple, struct key_def *key_def)
 	return key_hint_string_coll<is_nullable>(field, key_def);
 }
 
+static cmp_aux_t
+tuple_multikey_idx_hint(const struct tuple *tuple, struct key_def *key_def,
+			uint64_t multikey_idx)
+{
+	(void)tuple;
+	(void)key_def;
+	cmp_aux_t ret;
+	ret.multikey_idx = multikey_idx;
+	return ret;
+}
+
 void
 key_def_set_cmp_aux_func(struct key_def *def)
 {
 	def->key_cmp_aux = key_hint_default;
 	def->tuple_cmp_aux = tuple_hint_default;
+	if (def->has_multikey_parts) {
+		def->tuple_cmp_aux = tuple_multikey_idx_hint;
+		return;
+	}
 	bool is_nullable = key_part_is_nullable(def->parts);
 	if (def->parts->type == FIELD_TYPE_STRING && def->parts->coll != NULL) {
 		def->key_cmp_aux = is_nullable ? key_hint_string_coll<true> :
diff --git a/src/box/tuple_format.c b/src/box/tuple_format.c
index 55f4e29e8..ced7e1050 100644
--- a/src/box/tuple_format.c
+++ b/src/box/tuple_format.c
@@ -33,6 +33,7 @@
 #include "json/json.h"
 #include "tuple_format.h"
 #include "coll_id_cache.h"
+#include "tuple.h"
 
 #include "third_party/PMurHash.h"
 
@@ -209,6 +210,7 @@ tuple_format_add_field(struct tuple_format *format, uint32_t fieldno,
 		       int *current_slot, char **path_pool)
 {
 	struct tuple_field *field = NULL;
+	struct tuple_field *multikey_field = NULL;
 	struct tuple_field *parent = tuple_format_field(format, fieldno);
 	assert(parent != NULL);
 	if (path == NULL)
@@ -234,11 +236,6 @@ tuple_format_add_field(struct tuple_format *format, uint32_t fieldno,
 	json_lexer_create(&lexer, path, path_len, TUPLE_INDEX_BASE);
 	while ((rc = json_lexer_next_token(&lexer, &field->token)) == 0 &&
 	       field->token.type != JSON_TOKEN_END) {
-		if (field->token.type == JSON_TOKEN_ANY) {
-			diag_set(ClientError, ER_UNSUPPORTED,
-				"Tarantool", "multikey indexes");
-			goto fail;
-		}
 		enum field_type expected_type =
 			field->token.type == JSON_TOKEN_STR ?
 			FIELD_TYPE_MAP : FIELD_TYPE_ARRAY;
@@ -251,6 +248,17 @@ tuple_format_add_field(struct tuple_format *format, uint32_t fieldno,
 				 field_type_strs[expected_type]);
 			goto fail;
 		}
+		if (field->token.type == JSON_TOKEN_ANY &&
+		    !json_token_is_multikey(&parent->token) &&
+		    !json_token_is_leaf(&parent->token)) {
+			const char *multikey_type =
+				tt_sprintf("multikey %s",
+					   field_type_strs[expected_type]);
+			diag_set(ClientError, ER_INDEX_PART_TYPE_MISMATCH,
+				 tuple_field_path(parent),
+				 field_type_strs[parent->type], multikey_type);
+			goto fail;
+		}
 		struct tuple_field *next =
 			json_tree_lookup_entry(tree, &parent->token,
 					       &field->token,
@@ -268,6 +276,9 @@ tuple_format_add_field(struct tuple_format *format, uint32_t fieldno,
 			if (field == NULL)
 				goto fail;
 		}
+		/* Setup delayed multikey field_map allocation. */
+		if (parent->token.type == JSON_TOKEN_ANY)
+			multikey_field = next;
 		parent->is_key_part = true;
 		parent = next;
 		token_count++;
@@ -291,7 +302,29 @@ end:
 	if (parent != NULL && parent->offset_slot == TUPLE_OFFSET_SLOT_NIL &&
 	    is_sequential == false && (fieldno > 0 || path != NULL)) {
 		*current_slot = *current_slot - 1;
-		parent->offset_slot = *current_slot;
+		if (multikey_field != NULL) {
+			/* Multikey indirection slot. */
+			field = json_tree_entry(multikey_field->token.parent,
+						struct tuple_field, token);
+			assert(field->token.type == JSON_TOKEN_ANY);
+			field->offset_slot = *current_slot;
+			*current_slot = *current_slot - 1;
+
+			/* Multikey parent array slot. */
+			field = json_tree_entry(field->token.parent,
+						struct tuple_field, token);
+			assert(field->type == FIELD_TYPE_ARRAY);
+			field->offset_slot = *current_slot;
+
+			/* Multikey leaf relative offset slot. */
+			assert(parent->offset_slot == TUPLE_OFFSET_SLOT_NIL ||
+			       parent->offset_slot ==
+			       -multikey_field->token.sibling_idx - 1);
+			parent->offset_slot =
+				-multikey_field->token.sibling_idx - 1;
+		} else {
+			parent->offset_slot = *current_slot;
+		}
 	}
 	return parent;
 fail:
@@ -477,9 +510,8 @@ tuple_format_create(struct tuple_format *format, struct key_def * const *keys,
 					break;
 				format->min_tuple_size += mp_sizeof_nil();
 			}
-		} else {
+		} else if (field->token.type == JSON_TOKEN_STR) {
 			/* Account a key string for map member. */
-			assert(field->token.type == JSON_TOKEN_STR);
 			format->min_tuple_size +=
 				mp_sizeof_str(field->token.len);
 		}
@@ -807,6 +839,28 @@ tuple_format1_can_store_format2_tuples(struct tuple_format *format1,
 	return true;
 }
 
+static int
+tuple_field_map_realloc(uint32_t **field_map, uint32_t *field_map_size,
+			uint32_t extent_size, struct region *region)
+{
+	assert(extent_size % sizeof(uint32_t) == 0);
+	uint32_t new_field_map_size = *field_map_size + extent_size;
+	uint32_t *new_field_map = region_alloc(region, new_field_map_size);
+	if (new_field_map == NULL) {
+		diag_set(OutOfMemory, new_field_map_size, "region_alloc",
+			 "new_field_map");
+		return -1;
+	}
+	memset(new_field_map, 0, extent_size);
+	if (*field_map != NULL) {
+		memcpy((char *)new_field_map + extent_size,
+		       (char *)*field_map - *field_map_size, *field_map_size);
+	}
+	*field_map = (uint32_t *)((char *)new_field_map + new_field_map_size);
+	*field_map_size = new_field_map_size;
+	return 0;
+}
+
 /** @sa declaration for details. */
 int
 tuple_field_map_create(struct tuple_format *format, const char *tuple,
@@ -819,14 +873,11 @@ tuple_field_map_create(struct tuple_format *format, const char *tuple,
 		return 0; /* Nothing to initialize */
 	}
 	struct region *region = &fiber()->gc;
-	*field_map_size = format->field_map_size;
-	*field_map = region_alloc(region, *field_map_size);
-	if (*field_map == NULL) {
-		diag_set(OutOfMemory, *field_map_size, "region_alloc",
-			 "field_map");
+	*field_map = NULL;
+	*field_map_size = 0;
+	if (tuple_field_map_realloc(field_map, field_map_size,
+				    format->field_map_size, region) != 0)
 		return -1;
-	}
-	*field_map = (uint32_t *)((char *)*field_map + *field_map_size);
 
 	const char *pos = tuple;
 	int rc = 0;
@@ -866,11 +917,6 @@ tuple_field_map_create(struct tuple_format *format, const char *tuple,
 	uint32_t defined_field_count = MIN(field_count, validate ?
 					   tuple_format_field_count(format) :
 					   format->index_field_count);
-	/*
-	 * Nullify field map to be able to detect by 0,
-	 * which key fields are absent in tuple_field().
-	 */
-	memset((char *)*field_map - *field_map_size, 0, *field_map_size);
 	/*
 	 * Prepare mp stack of the size equal to the maximum depth
 	 * of the indexed field in the format::fields tree
@@ -884,14 +930,25 @@ tuple_field_map_create(struct tuple_format *format, const char *tuple,
 		diag_set(OutOfMemory, frames_sz, "region", "frames");
 		goto error;
 	}
+	uint32_t *full_field_map = *field_map;
 	struct mp_stack stack;
 	mp_stack_create(&stack, format->fields_depth, frames);
 	mp_stack_push(&stack, MP_ARRAY, defined_field_count);
+
+	uint64_t multikey_idx = 0;
+	uint32_t multikey_group_size = 0;
+
 	struct tuple_field *field;
 	struct json_token *parent = &format->fields.root;
 	while (true) {
 		int idx;
-		while ((idx = mp_stack_advance(&stack)) == -1) {
+		while (true) {
+			/* Switch to the next multikey branch. */
+			if (json_token_is_multikey(parent))
+				multikey_idx++;
+			idx = mp_stack_advance(&stack);
+			if (idx != -1)
+				break;
 			/*
 			 * If the elements of the current frame
 			 * are over, pop this frame out of stack
@@ -903,6 +960,17 @@ tuple_field_map_create(struct tuple_format *format, const char *tuple,
 			mp_stack_pop(&stack);
 			if (mp_stack_is_empty(&stack))
 				goto finish;
+			/**
+			 * In case of multikey index, field_map
+			 * was temporary overriden with local
+			 * multikey index field_map. Now original
+			 * field_map pointer must be restored.
+			 */
+			if (json_token_is_multikey(parent)) {
+				*field_map = full_field_map;
+				multikey_idx = 0;
+				multikey_group_size = 0;
+			}
 			parent = parent->parent;
 		}
 		/*
@@ -952,8 +1020,22 @@ tuple_field_map_create(struct tuple_format *format, const char *tuple,
 					 field_type_strs[field->type]);
 				goto error;
 			}
-			if (field->offset_slot != TUPLE_OFFSET_SLOT_NIL)
-				(*field_map)[field->offset_slot] = pos - tuple;
+			if (field->offset_slot != TUPLE_OFFSET_SLOT_NIL) {
+				int32_t offset_slot = field->offset_slot;
+				if (*field_map != full_field_map) {
+					/*
+					 * Need to redefine
+					 * offset slot while
+					 * field_map is "local".
+					 */
+					assert(multikey_group_size > 0);
+					offset_slot = offset_slot *
+						      multikey_group_size +
+						      multikey_idx - 1;
+				}
+				assert(offset_slot < 0);
+				(*field_map)[offset_slot] = pos - tuple;
+			}
 			if (required_fields != NULL)
 				bit_clear(required_fields, field->id);
 		}
@@ -969,12 +1051,62 @@ tuple_field_map_create(struct tuple_format *format, const char *tuple,
 			uint32_t size = type == MP_ARRAY ?
 					mp_decode_array(&pos) :
 					mp_decode_map(&pos);
+			if (json_token_is_multikey(&field->token)) {
+				assert(type == MP_ARRAY);
+				assert(field->offset_slot !=
+				       TUPLE_OFFSET_SLOT_NIL);
+				assert(*field_map == full_field_map);
+
+				struct json_token multikey_token;
+				multikey_token.type = JSON_TOKEN_ANY;
+				struct tuple_field *multikey_field =
+					json_tree_lookup_entry(&format->fields,
+						&field->token, &multikey_token,
+						struct tuple_field, token);
+				assert(multikey_field != NULL);
+				assert(multikey_field->token.type == JSON_TOKEN_ANY);
+
+				/*
+				 * Offset slot for local field_map
+				 * to serve multikey index.
+				 * uin32_t : [LOCAL FIELD MAP OFFSET | SIZE]
+				 */
+				assert(size < (1 << 4));
+				assert(*field_map_size / sizeof(uint32_t) <
+				       (1 << 18));
+				(*field_map)[multikey_field->offset_slot] =
+					(*field_map_size /
+					sizeof(uint32_t)) << 4 | size;
+
+
+				multikey_group_size = size;
+				multikey_idx = 0;
+				uint32_t multikey_group_cnt =
+					multikey_field->token.max_child_idx + 1;
+
+				uint32_t extent_size = multikey_group_cnt *
+						       size * sizeof(uint32_t);
+				if (tuple_field_map_realloc(field_map,
+							    field_map_size,
+							    extent_size,
+							    region) != 0)
+					goto error;
+				full_field_map = *field_map;
+				/*
+				 * Temporary override field_map
+				 * with local multikey field_map
+				 * to initialize multikey index.
+				 */
+				*field_map = (uint32_t *)((char *)*field_map -
+					     *field_map_size + extent_size);
+			}
 			mp_stack_push(&stack, type, size);
 			parent = &field->token;
 		} else {
 			mp_next(&pos);
 		}
 	}
+	assert(*field_map == full_field_map);
 finish:
 	/*
 	 * Check the required field bitmap for missing fields.
diff --git a/test/engine/json.result b/test/engine/json.result
index a790cdfbc..5c7a9b3b3 100644
--- a/test/engine/json.result
+++ b/test/engine/json.result
@@ -691,7 +691,85 @@ s = box.schema.space.create('withdata')
 ...
 idx = s:create_index('idx', {parts = {{3, 'str', path = '[*].fname'}, {3, 'str', path = '[*].sname'}}})
 ---
-- error: Tarantool does not support multikey indexes
+...
+s:insert({1, 1, {{fname='James', sname='Bond'}, {fname='Vasya', sname='Pupkin'}}})
+---
+- [1, 1, [{'fname': 'James', 'sname': 'Bond'}, {'fname': 'Vasya', 'sname': 'Pupkin'}]]
+...
+s:insert({1, 1, {{fname='Ivan', sname='Ivanych'}}})
+---
+- [1, 1, [{'fname': 'Ivan', 'sname': 'Ivanych'}]]
+...
+idx:select({'James', 'Bond'})
+---
+- - [1, 1, [{'fname': 'James', 'sname': 'Bond'}, {'fname': 'Vasya', 'sname': 'Pupkin'}]]
+...
+idx:select({'Kirill', 'Shcherbatov'})
+---
+- []
+...
+idx:select({'Ivan', 'Ivanych'})
+---
+- - [1, 1, [{'fname': 'Ivan', 'sname': 'Ivanych'}]]
+...
+idx:select({'Vasya', 'Pupkin'})
+---
+- - [1, 1, [{'fname': 'James', 'sname': 'Bond'}, {'fname': 'Vasya', 'sname': 'Pupkin'}]]
+...
+idx:select()
+---
+- - [1, 1, [{'fname': 'Ivan', 'sname': 'Ivanych'}]]
+  - [1, 1, [{'fname': 'James', 'sname': 'Bond'}, {'fname': 'Vasya', 'sname': 'Pupkin'}]]
+  - [1, 1, [{'fname': 'James', 'sname': 'Bond'}, {'fname': 'Vasya', 'sname': 'Pupkin'}]]
+...
+s:insert({2, 1, {{fname='Vasya', sname='Pupkin'}}})
+---
+- error: Duplicate key exists in unique index 'idx' in space 'withdata'
+...
+s:insert({2, 1, {{fname='James', sname='Bond'}}})
+---
+- error: Duplicate key exists in unique index 'idx' in space 'withdata'
+...
+idx:select()
+---
+- - [1, 1, [{'fname': 'Ivan', 'sname': 'Ivanych'}]]
+  - [1, 1, [{'fname': 'James', 'sname': 'Bond'}, {'fname': 'Vasya', 'sname': 'Pupkin'}]]
+  - [1, 1, [{'fname': 'James', 'sname': 'Bond'}, {'fname': 'Vasya', 'sname': 'Pupkin'}]]
+...
+idx:delete({'Vasya', 'Pupkin'})
+---
+- [1, 1, [{'fname': 'James', 'sname': 'Bond'}, {'fname': 'Vasya', 'sname': 'Pupkin'}]]
+...
+s:insert({2, 1, {{fname='Vasya', sname='Pupkin'}}})
+---
+- [2, 1, [{'fname': 'Vasya', 'sname': 'Pupkin'}]]
+...
+s:insert({2, 1, {{fname='James', sname='Bond'}}})
+---
+- [2, 1, [{'fname': 'James', 'sname': 'Bond'}]]
+...
+idx:select()
+---
+- - [1, 1, [{'fname': 'Ivan', 'sname': 'Ivanych'}]]
+  - [2, 1, [{'fname': 'James', 'sname': 'Bond'}]]
+  - [2, 1, [{'fname': 'Vasya', 'sname': 'Pupkin'}]]
+...
+s:drop()
+---
+...
+s = box.schema.space.create('withdata')
+---
+...
+pk = s:create_index('pk')
+---
+...
+idx = s:create_index('idx', {parts = {{3, 'str', path = '[*].fname'}, {3, 'str', path = '[*].extra.sname', is_nullable = true}}})
+---
+...
+s:insert({1, 1, {{fname='A1', extra={sname='A2'}}, {fname='B1'}, {fname='C1', extra={sname='C2'}}}})
+---
+- [1, 1, [{'fname': 'A1', 'extra': {'sname': 'A2'}}, {'fname': 'B1'}, {'fname': 'C1',
+      'extra': {'sname': 'C2'}}]]
 ...
 s:drop()
 ---
diff --git a/test/engine/json.test.lua b/test/engine/json.test.lua
index f9a7180b1..dc6016af9 100644
--- a/test/engine/json.test.lua
+++ b/test/engine/json.test.lua
@@ -198,4 +198,24 @@ s:drop()
 --
 s = box.schema.space.create('withdata')
 idx = s:create_index('idx', {parts = {{3, 'str', path = '[*].fname'}, {3, 'str', path = '[*].sname'}}})
+s:insert({1, 1, {{fname='James', sname='Bond'}, {fname='Vasya', sname='Pupkin'}}})
+s:insert({1, 1, {{fname='Ivan', sname='Ivanych'}}})
+idx:select({'James', 'Bond'})
+idx:select({'Kirill', 'Shcherbatov'})
+idx:select({'Ivan', 'Ivanych'})
+idx:select({'Vasya', 'Pupkin'})
+idx:select()
+s:insert({2, 1, {{fname='Vasya', sname='Pupkin'}}})
+s:insert({2, 1, {{fname='James', sname='Bond'}}})
+idx:select()
+idx:delete({'Vasya', 'Pupkin'})
+s:insert({2, 1, {{fname='Vasya', sname='Pupkin'}}})
+s:insert({2, 1, {{fname='James', sname='Bond'}}})
+idx:select()
+s:drop()
+
+s = box.schema.space.create('withdata')
+pk = s:create_index('pk')
+idx = s:create_index('idx', {parts = {{3, 'str', path = '[*].fname'}, {3, 'str', path = '[*].extra.sname', is_nullable = true}}})
+s:insert({1, 1, {{fname='A1', extra={sname='A2'}}, {fname='B1'}, {fname='C1', extra={sname='C2'}}}})
 s:drop()
-- 
2.21.0

Re: [tarantool-patches] [PATCH v5 4/4] box: introduce multikey indexes

[Kirill Shcherbatov]

I've implemented a better version that is easier to understand and works better.
I am going to think, how do not reallocate field map when multikey index was met.
Maybe I'll resend this patch again later.

=======================================================



With multikey index feature introduction, JSON path may have [*]
placeholder instead of array index: this allows to index
multiple documents by one JSON path automatically.

Example:
s = box.schema.space.create('withdata')
idx = s:create_index('idx', {parts = {{3, 'str', path = '[*].fname'},
                                  {3, 'str', path = '[*].sname'}}})
_ = s:insert({1, 1, {{fname='James', sname='Bond'},
                 {fname='Austin', sname='Powers'}}})
idx:get({'Austin', 'Powers'})
---
- [1, 1, [{'fname': 'James', 'sname': 'Bond'}, {'fname': 'Austin',
'sname': 'Powers'}]]
...

Closes #1257
---
 src/box/key_def.c         |  15 ++++
 src/box/key_def.h         |  15 +++-
 src/box/memtx_tree.c      | 180 ++++++++++++++++++++++++++++++++++++--
 src/box/tuple.c           |   8 +-
 src/box/tuple.h           | 122 +++++++++++++++++++++++---
 src/box/tuple_compare.cc  | 155 +++++++++++++++++++++++++++-----
 src/box/tuple_format.c    | 120 ++++++++++++++++++++-----
 test/engine/json.result   |  80 ++++++++++++++++-
 test/engine/json.test.lua |  20 +++++
 9 files changed, 648 insertions(+), 67 deletions(-)

diff --git a/src/box/key_def.c b/src/box/key_def.c
index 771c30172..f6ca461c4 100644
--- a/src/box/key_def.c
+++ b/src/box/key_def.c
@@ -165,9 +165,24 @@ key_def_set_part(struct key_def *def, uint32_t part_no, uint32_t fieldno,
 		*path_pool += path_len;
 		memcpy(def->parts[part_no].path, path, path_len);
 		def->parts[part_no].path_len = path_len;
+
+		int rc;
+		struct json_lexer lexer;
+		struct json_token token;
+		json_lexer_create(&lexer, path, path_len, TUPLE_INDEX_BASE);
+		while ((rc = json_lexer_next_token(&lexer, &token)) == 0) {
+			if (token.type == JSON_TOKEN_ANY) {
+				def->has_multikey_parts = true;
+				def->parts[part_no].is_multikey = true;
+				break;
+			} else if (token.type == JSON_TOKEN_END) {
+				break;
+			}
+		}
 	} else {
 		def->parts[part_no].path = NULL;
 		def->parts[part_no].path_len = 0;
+		def->parts[part_no].is_multikey = false;
 	}
 	column_mask_set_fieldno(&def->column_mask, fieldno);
 }
diff --git a/src/box/key_def.h b/src/box/key_def.h
index c630e6b43..37fae6b52 100644
--- a/src/box/key_def.h
+++ b/src/box/key_def.h
@@ -97,6 +97,8 @@ struct key_part {
 	char *path;
 	/** The length of JSON path. */
 	uint32_t path_len;
+	/** True if this is multikey key part. */
+	bool is_multikey;
 	/**
 	 * Epoch of the tuple format the offset slot cached in
 	 * this part is valid for, see tuple_format::epoch.
@@ -129,6 +131,8 @@ typedef union {
 	 * the tuples themselves.
 	 */
 	uint64_t hint;
+	/** Index of item in the array used in multikey index. */
+	uint64_t multikey_idx;
 } cmp_aux_t;
 
 /** Test if cmp_aux_t a and b are equal. */
@@ -189,7 +193,8 @@ typedef uint32_t (*key_hash_t)(const char *key,
 
 /** @copydoc tuple_cmp_aux() */
 typedef cmp_aux_t (*tuple_cmp_aux_t)(const struct tuple *tuple,
-				     struct key_def *key_def);
+				     struct key_def *key_def,
+				     uint64_t multikey_idx);
 
 /** @copydoc key_cmp_aux() */
 typedef cmp_aux_t (*key_cmp_aux_t)(const char *key, struct key_def *key_def);
@@ -228,6 +233,8 @@ struct key_def {
 	bool is_nullable;
 	/** True if some key part has JSON path. */
 	bool has_json_paths;
+	/** True if some part has array index placeholder *. */
+	bool has_multikey_parts;
 	/**
 	 * True, if some key parts can be absent in a tuple. These
 	 * fields assumed to be MP_NIL.
@@ -723,12 +730,14 @@ key_hash(const char *key, struct key_def *key_def)
  * Get a comparison auxiliary information for a tuple.
  * @param tuple - tuple to get cmp_aux_t of.
  * @param key_def - key_def that defines which comparison is used.
+ * @param multikey_idx - index of multikey array item.
  * @return the comparison auxiliary information.
  */
 static inline cmp_aux_t
-tuple_cmp_aux(const struct tuple *tuple, struct key_def *key_def)
+tuple_cmp_aux(const struct tuple *tuple, struct key_def *key_def,
+	      uint64_t multikey_idx)
 {
-	return key_def->tuple_cmp_aux(tuple, key_def);
+	return key_def->tuple_cmp_aux(tuple, key_def, multikey_idx);
 }
 
 /**
diff --git a/src/box/memtx_tree.c b/src/box/memtx_tree.c
index 4b0886bef..d7f639ca4 100644
--- a/src/box/memtx_tree.c
+++ b/src/box/memtx_tree.c
@@ -91,11 +91,11 @@ memtx_tree_data_clear(struct memtx_tree_data *data)
  */
 static void
 memtx_tree_data_set(struct memtx_tree_data *data, struct tuple *tuple,
-		    struct key_def *key_def)
+		    struct key_def *key_def, uint64_t multikey_idx)
 {
 	(void)key_def;
 	data->tuple = tuple;
-	data->aux_info = tuple_cmp_aux(tuple, key_def);
+	data->aux_info = tuple_cmp_aux(tuple, key_def, multikey_idx);
 }
 
 /**
@@ -578,7 +578,8 @@ memtx_tree_index_replace(struct index *base, struct tuple *old_tuple,
 	struct key_def *key_def = index->tree.arg;
 	if (new_tuple) {
 		struct memtx_tree_data new_data;
-		memtx_tree_data_set(&new_data, new_tuple, key_def);
+		memtx_tree_data_set(&new_data, new_tuple, key_def,
+				    INVALID_MULTIKEY_INDEX);
 		struct memtx_tree_data dup_data;
 		memtx_tree_data_clear(&dup_data);
 
@@ -610,13 +611,106 @@ memtx_tree_index_replace(struct index *base, struct tuple *old_tuple,
 	}
 	if (old_tuple) {
 		struct memtx_tree_data old_data;
-		memtx_tree_data_set(&old_data, old_tuple, key_def);
+		memtx_tree_data_set(&old_data, old_tuple, key_def,
+				    INVALID_MULTIKEY_INDEX);
 		memtx_tree_delete(&index->tree, old_data);
 	}
 	*result = old_tuple;
 	return 0;
 }
 
+static int
+multikey_get_array_sz(struct tuple *tuple, struct key_def *key_def)
+{
+	assert(key_def->has_multikey_parts);
+	struct key_part *part = key_def->parts;
+	/* FIXME: don't like it... */
+	while (part < key_def->parts + key_def->part_count &&
+	       !part->is_multikey)
+		part++;
+	assert(part->path != NULL && part->is_multikey);
+	struct tuple_field *field =
+		tuple_format_field_by_path(tuple_format(tuple), part->fieldno,
+					   part->path, part->path_len);
+	assert(field != NULL);
+	struct field_map_ext *field_map_ext =
+		tuple_field_map_ext((uint32_t *)tuple_field_map(tuple),
+				    field->offset_slot);
+	return field_map_ext->size;
+}
+
+int
+memtx_multikey_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 key_def *key_def = index->tree.arg;
+	if (new_tuple != NULL) {
+		int errcode = 0, tree_res = 0;
+		struct tuple *dup_tuple = NULL;
+		int multikey_idx = 0;
+		int sz = multikey_get_array_sz(new_tuple, key_def);
+		for (; multikey_idx < sz; multikey_idx++) {
+			struct memtx_tree_data new_data;
+			memtx_tree_data_set(&new_data, new_tuple, key_def,
+					    multikey_idx);
+			struct memtx_tree_data dup_data;
+			memtx_tree_data_clear(&dup_data);
+			tree_res = memtx_tree_insert(&index->tree, new_data,
+						     &dup_data);
+			if (tree_res != 0) {
+				diag_set(OutOfMemory, MEMTX_EXTENT_SIZE,
+					 "memtx_tree_index", "replace");
+				break;
+			}
+			dup_tuple = dup_data.tuple;
+			errcode = replace_check_dup(old_tuple, dup_tuple, mode);
+			if (errcode != 0) {
+				memtx_tree_delete(&index->tree, new_data);
+				if (dup_tuple != NULL) {
+					memtx_tree_insert(&index->tree,
+							  dup_data, NULL);
+				}
+				struct space *sp =
+					space_cache_find(base->def->space_id);
+				if (sp != NULL) {
+					diag_set(ClientError, errcode,
+						 base->def->name,
+						 space_name(sp));
+				}
+				break;
+			}
+		}
+		if (tree_res != 0 || errcode != 0) {
+			multikey_idx--;
+			for (; multikey_idx >= 0; multikey_idx--) {
+				struct memtx_tree_data data;
+				memtx_tree_data_set(&data, new_tuple, key_def,
+						    multikey_idx);
+				memtx_tree_delete(&index->tree, data);
+			}
+			return -1;
+		}
+		if (dup_tuple != NULL) {
+			*result = dup_tuple;
+			return 0;
+		}
+	}
+	if (old_tuple != NULL) {
+		int sz = multikey_get_array_sz(old_tuple, key_def);
+		for (int multikey_idx = 0; multikey_idx < sz; multikey_idx++) {
+			struct memtx_tree_data old_data;
+			memtx_tree_data_set(&old_data, old_tuple, key_def,
+					    multikey_idx);
+			memtx_tree_delete(&index->tree, old_data);
+		}
+	}
+	*result = old_tuple;
+	return 0;
+}
+
 static struct iterator *
 memtx_tree_index_create_iterator(struct index *base, enum iterator_type type,
 				 const char *key, uint32_t part_count)
@@ -718,7 +812,48 @@ memtx_tree_index_build_next(struct index *base, struct tuple *tuple)
 	}
 	struct memtx_tree_data *elem =
 		&index->build_array[index->build_array_size++];
-	memtx_tree_data_set(elem, tuple, key_def);
+	memtx_tree_data_set(elem, tuple, key_def, INVALID_MULTIKEY_INDEX);
+	return 0;
+}
+
+static int
+memtx_multikey_tree_index_build_next(struct index *base, struct tuple *tuple)
+{
+	struct memtx_tree_index *index = (struct memtx_tree_index *)base;
+	struct key_def *key_def = index->tree.arg;
+	int sz = multikey_get_array_sz(tuple, key_def);
+
+	if (index->build_array == NULL) {
+		index->build_array =
+			(struct memtx_tree_data *)malloc(MEMTX_EXTENT_SIZE);
+		if (index->build_array == NULL) {
+			diag_set(OutOfMemory, MEMTX_EXTENT_SIZE,
+				 "memtx_tree_index", "build_next");
+			return -1;
+		}
+		index->build_array_alloc_size =
+			MEMTX_EXTENT_SIZE / sizeof(index->build_array[0]);
+	}
+	assert(index->build_array_size <= index->build_array_alloc_size);
+	if (index->build_array_size == index->build_array_alloc_size) {
+		index->build_array_alloc_size = index->build_array_alloc_size +
+					index->build_array_alloc_size / 2;
+		struct memtx_tree_data *tmp =
+			realloc(index->build_array,
+				index->build_array_alloc_size * sizeof(*tmp));
+		if (tmp == NULL) {
+			diag_set(OutOfMemory, index->build_array_alloc_size *
+				 sizeof(*tmp), "memtx_tree_index", "build_next");
+			return -1;
+		}
+		index->build_array = tmp;
+	}
+	for (int multikey_idx = 0; multikey_idx < sz; multikey_idx++) {
+		struct memtx_tree_data *elem =
+			&index->build_array[index->build_array_size++];
+		assert(index->build_array_size < index->build_array_alloc_size);
+		memtx_tree_data_set(elem, tuple, key_def, multikey_idx);
+	}
 	return 0;
 }
 
@@ -824,6 +959,36 @@ static const struct index_vtab memtx_tree_index_vtab = {
 	/* .end_build = */ memtx_tree_index_end_build,
 };
 
+static const struct index_vtab memtx_multikey_tree_index_vtab = {
+	/* .destroy = */ memtx_tree_index_destroy,
+	/* .commit_create = */ generic_index_commit_create,
+	/* .abort_create = */ generic_index_abort_create,
+	/* .commit_modify = */ generic_index_commit_modify,
+	/* .commit_drop = */ generic_index_commit_drop,
+	/* .update_def = */ memtx_tree_index_update_def,
+	/* .depends_on_pk = */ memtx_tree_index_depends_on_pk,
+	/* .def_change_requires_rebuild = */
+		memtx_index_def_change_requires_rebuild,
+	/* .size = */ memtx_tree_index_size,
+	/* .bsize = */ memtx_tree_index_bsize,
+	/* .min = */ generic_index_min,
+	/* .max = */ generic_index_max,
+	/* .random = */ memtx_tree_index_random,
+	/* .count = */ memtx_tree_index_count,
+	/* .get = */ memtx_tree_index_get,
+	/* .replace = */ memtx_multikey_tree_index_replace,
+	/* .create_iterator = */ memtx_tree_index_create_iterator,
+	/* .create_snapshot_iterator = */
+		memtx_tree_index_create_snapshot_iterator,
+	/* .stat = */ generic_index_stat,
+	/* .compact = */ generic_index_compact,
+	/* .reset_stat = */ generic_index_reset_stat,
+	/* .begin_build = */ memtx_tree_index_begin_build,
+	/* .reserve = */ memtx_tree_index_reserve,
+	/* .build_next = */ memtx_multikey_tree_index_build_next,
+	/* .end_build = */ memtx_tree_index_end_build,
+};
+
 struct index *
 memtx_tree_index_new(struct memtx_engine *memtx, struct index_def *def)
 {
@@ -834,8 +999,11 @@ memtx_tree_index_new(struct memtx_engine *memtx, struct index_def *def)
 			 "malloc", "struct memtx_tree_index");
 		return NULL;
 	}
+	const struct index_vtab *vtab = def->key_def->has_multikey_parts ?
+					&memtx_multikey_tree_index_vtab :
+					&memtx_tree_index_vtab;
 	if (index_create(&index->base, (struct engine *)memtx,
-			 &memtx_tree_index_vtab, def) != 0) {
+			 vtab, def) != 0) {
 		free(index);
 		return NULL;
 	}
diff --git a/src/box/tuple.c b/src/box/tuple.c
index 7f06d4053..c8a938c4c 100644
--- a/src/box/tuple.c
+++ b/src/box/tuple.c
@@ -455,7 +455,8 @@ tuple_field_go_to_key(const char **field, const char *key, int len)
 }
 
 int
-tuple_go_to_path(const char **data, const char *path, uint32_t path_len)
+tuple_go_to_path_multikey(const char **data, const char *path,
+			  uint32_t path_len, uint64_t multikey_idx)
 {
 	int rc;
 	struct json_lexer lexer;
@@ -463,6 +464,8 @@ tuple_go_to_path(const char **data, const char *path, uint32_t path_len)
 	json_lexer_create(&lexer, path, path_len, TUPLE_INDEX_BASE);
 	while ((rc = json_lexer_next_token(&lexer, &token)) == 0) {
 		switch (token.type) {
+		case JSON_TOKEN_ANY:
+			token.num = (int)multikey_idx;
 		case JSON_TOKEN_NUM:
 			rc = tuple_field_go_to_index(data, token.num);
 			break;
@@ -532,7 +535,8 @@ tuple_field_raw_by_full_path(struct tuple_format *format, const char *tuple,
 	}
 	return tuple_field_raw_by_path(format, tuple, field_map, fieldno,
 				       path + lexer.offset,
-				       path_len - lexer.offset, NULL);
+				       path_len - lexer.offset, NULL,
+				       INVALID_MULTIKEY_INDEX);
 }
 
 /* }}} tuple_field_* getters */
diff --git a/src/box/tuple.h b/src/box/tuple.h
index 8b12fd5a8..e498e1e41 100644
--- a/src/box/tuple.h
+++ b/src/box/tuple.h
@@ -45,6 +45,8 @@ struct slab_arena;
 struct quota;
 struct key_part;
 
+#define INVALID_MULTIKEY_INDEX UINT64_MAX
+
 /**
  * A format for standalone tuples allocated on runtime arena.
  * \sa tuple_new().
@@ -286,6 +288,7 @@ box_tuple_upsert(const box_tuple_t *tuple, const char *expr, const
 
 /** \endcond public */
 
+
 /**
  * An atom of Tarantool storage. Represents MsgPack Array.
  * Tuple has the following structure:
@@ -296,7 +299,9 @@ box_tuple_upsert(const box_tuple_t *tuple, const char *expr, const
  * |                                            ^
  * +---------------------------------------data_offset
  *
- * Each 'off_i' is the offset to the i-th indexed field.
+ * Each 'off_i' is the offset to the i-th indexed field or field
+ * map extention (described with struct tuple_field_map_ext)
+ * offset (in sizeof(field_map[0]) units).
  */
 struct PACKED tuple
 {
@@ -328,6 +333,26 @@ struct PACKED tuple
 	 */
 };
 
+/**
+ * Tuple field map extent. Is allocated on tuple_field_map_create
+ * call automatically when necessary, when tuple field map must be
+ * reallocated dynamically.
+ */
+struct field_map_ext {
+	/* Sequence of data offset slots. */
+	uint32_t field_map[1];
+	/* The count of field_map items. */
+	uint32_t size;
+};
+
+static inline struct field_map_ext *
+tuple_field_map_ext(uint32_t *field_map, int32_t root_offset_slot)
+{
+	uint32_t slot_off = field_map[root_offset_slot];
+	return (struct field_map_ext *)((char *)field_map -
+		slot_off * sizeof(uint32_t) - sizeof(struct field_map_ext));
+}
+
 /** Size of the tuple including size of struct tuple. */
 static inline size_t
 tuple_size(const struct tuple *tuple)
@@ -508,11 +533,32 @@ tuple_field_count(const struct tuple *tuple)
  *                      with NULL.
  * @param path The path to process.
  * @param path_len The length of the @path.
+ * @param multikey_index The multikey index hint - index of item
+ *                       for JSON_TOKEN_ANY level.
  * @retval 0 On success.
  * @retval -1 In case of error in JSON path.
  */
 int
-tuple_go_to_path(const char **data, const char *path, uint32_t path_len);
+tuple_go_to_path_multikey(const char **data, const char *path,
+			  uint32_t path_len, uint64_t multikey_idx);
+
+/**
+ * Retrieve msgpack data by JSON path.
+ * @param data[in, out] Pointer to msgpack with data.
+ *                      If the field cannot be retrieved be the
+ *                      specified path @path, it is overwritten
+ *                      with NULL.
+ * @param path The path to process.
+ * @param path_len The length of the @path.
+ * @retval 0 On success.
+ * @retval -1 In case of error in JSON path.
+ */
+static inline int
+tuple_go_to_path(const char **data, const char *path, uint32_t path_len)
+{
+	return tuple_go_to_path_multikey(data, path, path_len,
+					 INVALID_MULTIKEY_INDEX);
+}
 
 /**
  * Get tuple field by field index and relative JSON path.
@@ -533,7 +579,7 @@ static inline const char *
 tuple_field_raw_by_path(struct tuple_format *format, const char *tuple,
 			const uint32_t *field_map, uint32_t fieldno,
 			const char *path, uint32_t path_len,
-			int32_t *offset_slot_hint)
+			int32_t *offset_slot_hint, uint64_t multikey_idx)
 {
 	int32_t offset_slot;
 	if (offset_slot_hint != NULL &&
@@ -558,10 +604,22 @@ tuple_field_raw_by_path(struct tuple_format *format, const char *tuple,
 		if (offset_slot_hint != NULL)
 			*offset_slot_hint = offset_slot;
 offset_slot_access:
-		/* Indexed field */
-		if (field_map[offset_slot] == 0)
-			return NULL;
-		tuple += field_map[offset_slot];
+		if (multikey_idx != INVALID_MULTIKEY_INDEX) {
+			struct field_map_ext *field_map_ext =
+				tuple_field_map_ext((uint32_t *)field_map,
+						    offset_slot);
+			if (multikey_idx >= field_map_ext->size)
+				return NULL;
+			uint32_t off = field_map_ext->field_map[-multikey_idx];
+			if (off == 0)
+				return NULL;
+			tuple += off;
+		} else {
+			/* Indexed field */
+			if (field_map[offset_slot] == 0)
+				return NULL;
+			tuple += field_map[offset_slot];
+		}
 	} else {
 		uint32_t field_count;
 parse:
@@ -572,8 +630,8 @@ parse:
 		for (uint32_t k = 0; k < fieldno; k++)
 			mp_next(&tuple);
 		if (path != NULL &&
-		    unlikely(tuple_go_to_path(&tuple, path,
-						    path_len) != 0))
+		    unlikely(tuple_go_to_path_multikey(&tuple, path, path_len,
+						       multikey_idx) != 0))
 			return NULL;
 	}
 	return tuple;
@@ -595,7 +653,7 @@ tuple_field_raw(struct tuple_format *format, const char *tuple,
 		const uint32_t *field_map, uint32_t field_no)
 {
 	return tuple_field_raw_by_path(format, tuple, field_map, field_no,
-				       NULL, 0, NULL);
+				       NULL, 0, NULL, INVALID_MULTIKEY_INDEX);
 }
 
 /**
@@ -634,16 +692,18 @@ tuple_field_raw_by_full_path(struct tuple_format *format, const char *tuple,
 			     uint32_t path_len, uint32_t path_hash);
 
 /**
- * Get a tuple field pointed to by an index part.
+ * Get a tuple field pointed to by an index part and multikey hint.
  * @param format Tuple format.
  * @param tuple A pointer to MessagePack array.
  * @param field_map A pointer to the LAST element of field map.
+ * @param multikey_idx A multikey hint.
  * @param part Index part to use.
  * @retval Field data if the field exists or NULL.
  */
 static inline const char *
-tuple_field_raw_by_part(struct tuple_format *format, const char *data,
-			const uint32_t *field_map, struct key_part *part)
+tuple_field_raw_by_part_multikey(struct tuple_format *format, const char *data,
+				 const uint32_t *field_map,
+				 struct key_part *part, uint64_t multikey_idx)
 {
 	if (unlikely(part->format_epoch != format->epoch)) {
 		assert(format->epoch != 0);
@@ -656,7 +716,41 @@ tuple_field_raw_by_part(struct tuple_format *format, const char *data,
 	}
 	return tuple_field_raw_by_path(format, data, field_map, part->fieldno,
 				       part->path, part->path_len,
-				       &part->offset_slot_cache);
+				       &part->offset_slot_cache, multikey_idx);
+}
+
+/**
+ * Get a field refereed by index @part and multikey hint in tuple.
+ * @param tuple Tuple to get the field from.
+ * @param part Index part to use.
+ * @param multikey_idx A multikey hint.
+ * @retval Field data if the field exists or NULL.
+ */
+static inline const char *
+tuple_field_by_part_multikey(const struct tuple *tuple, struct key_part *part,
+			     uint64_t multikey_idx)
+{
+	return tuple_field_raw_by_part_multikey(tuple_format(tuple),
+						tuple_data(tuple),
+						tuple_field_map(tuple), part,
+						multikey_idx);
+}
+
+
+/**
+ * Get a tuple field pointed to by an index part.
+ * @param format Tuple format.
+ * @param tuple A pointer to MessagePack array.
+ * @param field_map A pointer to the LAST element of field map.
+ * @param part Index part to use.
+ * @retval Field data if the field exists or NULL.
+ */
+static inline const char *
+tuple_field_raw_by_part(struct tuple_format *format, const char *data,
+			const uint32_t *field_map, struct key_part *part)
+{
+	return tuple_field_raw_by_part_multikey(format, data, field_map,
+						part, INVALID_MULTIKEY_INDEX);
 }
 
 /**
diff --git a/src/box/tuple_compare.cc b/src/box/tuple_compare.cc
index 5b06e06b3..dbf7bb4f6 100644
--- a/src/box/tuple_compare.cc
+++ b/src/box/tuple_compare.cc
@@ -458,10 +458,12 @@ tuple_common_key_parts(const struct tuple *tuple_a, const struct tuple *tuple_b,
 	return i;
 }
 
-template<bool is_nullable, bool has_optional_parts, bool has_json_paths>
+template<bool is_nullable, bool has_optional_parts, bool has_json_paths,
+	 bool is_multikey>
 static inline int
-tuple_compare_slowpath(const struct tuple *tuple_a, const struct tuple *tuple_b,
-		       struct key_def *key_def)
+tuple_compare_slowpath_multikey(const struct tuple *tuple_a,
+		cmp_aux_t tuple_a_cmp_aux, const struct tuple *tuple_b,
+		cmp_aux_t tuple_b_cmp_aux, struct key_def *key_def)
 {
 	assert(has_json_paths == key_def->has_json_paths);
 	assert(!has_optional_parts || is_nullable);
@@ -471,7 +473,7 @@ tuple_compare_slowpath(const struct tuple *tuple_a, const struct tuple *tuple_b,
 	const char *tuple_a_raw = tuple_data(tuple_a);
 	const char *tuple_b_raw = tuple_data(tuple_b);
 	if (key_def->part_count == 1 && part->fieldno == 0 &&
-	    (!has_json_paths || part->path == NULL)) {
+	    (!has_json_paths || part->path == NULL) && !is_multikey) {
 		/*
 		 * First field can not be optional - empty tuples
 		 * can not exist.
@@ -509,7 +511,14 @@ tuple_compare_slowpath(const struct tuple *tuple_a, const struct tuple *tuple_b,
 		end = part + key_def->part_count;
 
 	for (; part < end; part++) {
-		if (has_json_paths) {
+		if (is_multikey) {
+			field_a = tuple_field_raw_by_part_multikey(format_a,
+					tuple_a_raw, field_map_a, part,
+					tuple_a_cmp_aux.multikey_idx);
+			field_b = tuple_field_raw_by_part_multikey(format_b,
+					tuple_b_raw, field_map_b, part,
+					tuple_b_cmp_aux.multikey_idx);
+		} else if (has_json_paths) {
 			field_a = tuple_field_raw_by_part(format_a, tuple_a_raw,
 							  field_map_a, part);
 			field_b = tuple_field_raw_by_part(format_b, tuple_b_raw,
@@ -566,7 +575,14 @@ tuple_compare_slowpath(const struct tuple *tuple_a, const struct tuple *tuple_b,
 	 */
 	end = key_def->parts + key_def->part_count;
 	for (; part < end; ++part) {
-		if (has_json_paths) {
+		if (is_multikey) {
+			field_a = tuple_field_raw_by_part_multikey(format_a,
+					tuple_a_raw, field_map_a, part,
+					tuple_a_cmp_aux.multikey_idx);
+			field_b = tuple_field_raw_by_part_multikey(format_b,
+					tuple_b_raw, field_map_b, part,
+					tuple_b_cmp_aux.multikey_idx);
+		} else if (has_json_paths) {
 			field_a = tuple_field_raw_by_part(format_a, tuple_a_raw,
 							  field_map_a, part);
 			field_b = tuple_field_raw_by_part(format_b, tuple_b_raw,
@@ -592,9 +608,23 @@ tuple_compare_slowpath(const struct tuple *tuple_a, const struct tuple *tuple_b,
 
 template<bool is_nullable, bool has_optional_parts, bool has_json_paths>
 static inline int
-tuple_compare_with_key_slowpath(const struct tuple *tuple, const char *key,
-				uint32_t part_count, struct key_def *key_def)
+tuple_compare_slowpath(const struct tuple *tuple_a, const struct tuple *tuple_b,
+		       struct key_def *key_def)
+{
+	cmp_aux_t dummy;
+	return tuple_compare_slowpath_multikey
+			<is_nullable, has_optional_parts, has_json_paths, false>(
+				tuple_a, dummy, tuple_b, dummy, key_def);
+}
+
+template<bool is_nullable, bool has_optional_parts, bool has_json_paths,
+	 bool is_multikey>
+static inline int
+tuple_compare_with_key_slowpath_multikey(const struct tuple *tuple,
+		cmp_aux_t tuple_cmp_aux, const char *key, uint32_t part_count,
+		cmp_aux_t key_cmp_aux, struct key_def *key_def)
 {
+	(void)key_cmp_aux;
 	assert(has_json_paths == key_def->has_json_paths);
 	assert(!has_optional_parts || is_nullable);
 	assert(is_nullable == key_def->is_nullable);
@@ -608,7 +638,11 @@ tuple_compare_with_key_slowpath(const struct tuple *tuple, const char *key,
 	enum mp_type a_type, b_type;
 	if (likely(part_count == 1)) {
 		const char *field;
-		if (has_json_paths) {
+		if (is_multikey) {
+			field = tuple_field_raw_by_part_multikey(format,
+					tuple_raw, field_map, part,
+					tuple_cmp_aux.multikey_idx);
+		} else if (has_json_paths) {
 			field = tuple_field_raw_by_part(format, tuple_raw,
 							field_map, part);
 		} else {
@@ -639,7 +673,11 @@ tuple_compare_with_key_slowpath(const struct tuple *tuple, const char *key,
 	int rc;
 	for (; part < end; ++part, mp_next(&key)) {
 		const char *field;
-		if (has_json_paths) {
+		if (is_multikey) {
+			field = tuple_field_raw_by_part_multikey(format,
+					tuple_raw, field_map, part,
+					tuple_cmp_aux.multikey_idx);
+		} else if (has_json_paths) {
 			field = tuple_field_raw_by_part(format, tuple_raw,
 							field_map, part);
 		} else {
@@ -675,6 +713,17 @@ tuple_compare_with_key_slowpath(const struct tuple *tuple, const char *key,
 	return 0;
 }
 
+template<bool is_nullable, bool has_optional_parts, bool has_json_paths>
+static inline int
+tuple_compare_with_key_slowpath(const struct tuple *tuple, const char *key,
+				uint32_t part_count, struct key_def *key_def)
+{
+	cmp_aux_t dummy;
+	return tuple_compare_with_key_slowpath_multikey
+		<is_nullable, has_optional_parts, has_json_paths, false>(
+			tuple, dummy, key, part_count, dummy, key_def);
+}
+
 template<bool is_nullable>
 static inline int
 key_compare_parts(const char *key_a, const char *key_b, uint32_t part_count,
@@ -1342,11 +1391,28 @@ tuple_hinted_compare(const struct tuple *tuple_a, cmp_aux_t tuple_a_cmp_aux,
 		return tuple_compare(tuple_a, tuple_b, key_def);
 }
 
+static const tuple_aux_compare_t compare_slowpath_multikey_funcs[] = {
+	tuple_compare_slowpath_multikey<false, false, false, true>,
+	tuple_compare_slowpath_multikey<true, false, false, true>,
+	tuple_compare_slowpath_multikey<false, true, false, true>,
+	tuple_compare_slowpath_multikey<true, true, false, true>,
+	tuple_compare_slowpath_multikey<false, false, true, true>,
+	tuple_compare_slowpath_multikey<true, false, true, true>,
+	tuple_compare_slowpath_multikey<false, true, true, true>,
+	tuple_compare_slowpath_multikey<true, true, true, true>
+};
+
 static tuple_aux_compare_t
 tuple_aux_compare_create(const struct key_def *def)
 {
-	(void)def;
-	return tuple_hinted_compare;
+	if (def->has_multikey_parts) {
+		int cmp_func_idx = (def->is_nullable ? 1 : 0) +
+				   2 * (def->has_optional_parts ? 1 : 0) +
+				   4 * (def->has_json_paths ? 1 : 0);
+		return compare_slowpath_multikey_funcs[cmp_func_idx];
+	} else {
+		return tuple_hinted_compare;
+	}
 }
 
 /* }}} tuple_aux_compare */
@@ -1367,11 +1433,29 @@ tuple_hinted_compare_with_key(const struct tuple *tuple, cmp_aux_t tuple_cmp_aux
 		return tuple_compare_with_key(tuple, key, part_count, key_def);
 }
 
+static const tuple_aux_compare_with_key_t
+		compare_with_key_slowpath_multikey_funcs[] = {
+	tuple_compare_with_key_slowpath_multikey<false, false, false, true>,
+	tuple_compare_with_key_slowpath_multikey<true, false, false, true>,
+	tuple_compare_with_key_slowpath_multikey<false, true, false, true>,
+	tuple_compare_with_key_slowpath_multikey<true, true, false, true>,
+	tuple_compare_with_key_slowpath_multikey<false, false, true, true>,
+	tuple_compare_with_key_slowpath_multikey<true, false, true, true>,
+	tuple_compare_with_key_slowpath_multikey<false, true, true, true>,
+	tuple_compare_with_key_slowpath_multikey<true, true, true, true>
+};
+
 static tuple_aux_compare_with_key_t
 tuple_aux_compare_with_key_create(const struct key_def *def)
 {
-	(void)def;
-	return tuple_hinted_compare_with_key;
+	if (def->has_multikey_parts) {
+		int cmp_func_idx = (def->is_nullable ? 1 : 0) +
+				    2 * (def->has_optional_parts ? 1 : 0) +
+				    4 * (def->has_json_paths ? 1 : 0);
+		return compare_with_key_slowpath_multikey_funcs[cmp_func_idx];
+	} else {
+		return tuple_hinted_compare_with_key;
+	}
 }
 
 /* }}} tuple_aux_compare_with_key */
@@ -1399,10 +1483,12 @@ key_hint_default(const char *key, struct key_def *key_def)
 }
 
 static cmp_aux_t
-tuple_hint_default(const struct tuple *tuple, struct key_def *key_def)
+tuple_hint_default(const struct tuple *tuple, struct key_def *key_def,
+		   uint64_t multikey_idx)
 {
 	(void)tuple;
 	(void)key_def;
+	(void)multikey_idx;
 	cmp_aux_t ret;
 	ret.hint = CMP_HINT_INVALID;
 	return ret;
@@ -1429,8 +1515,10 @@ key_hint_uint(const char *key, struct key_def *key_def)
 
 template<bool is_nullable>
 static cmp_aux_t
-tuple_hint_uint(const struct tuple *tuple, struct key_def *key_def)
+tuple_hint_uint(const struct tuple *tuple, struct key_def *key_def,
+		uint64_t multikey_idx)
 {
+	(void)multikey_idx;
 	assert(key_part_is_nullable(key_def->parts) == is_nullable);
 	assert(key_def->parts->type == FIELD_TYPE_UNSIGNED);
 	cmp_aux_t ret;
@@ -1468,8 +1556,10 @@ key_hint_int(const char *key, struct key_def *key_def)
 
 template<bool is_nullable>
 static cmp_aux_t
-tuple_hint_int(const struct tuple *tuple, struct key_def *key_def)
+tuple_hint_int(const struct tuple *tuple, struct key_def *key_def,
+	       uint64_t multikey_idx)
 {
+	(void)multikey_idx;
 	assert(key_part_is_nullable(key_def->parts) == is_nullable);
 	assert(key_def->parts->type == FIELD_TYPE_INTEGER);
 	cmp_aux_t ret;
@@ -1537,8 +1627,10 @@ key_hint_number(const char *key, struct key_def *key_def)
 
 template<bool is_nullable>
 static cmp_aux_t
-tuple_hint_number(const struct tuple *tuple, struct key_def *key_def)
+tuple_hint_number(const struct tuple *tuple, struct key_def *key_def,
+		  uint64_t multikey_idx)
 {
+	(void)multikey_idx;
 	assert(key_part_is_nullable(key_def->parts) == is_nullable);
 	assert(key_def->parts->type == FIELD_TYPE_NUMBER);
 	cmp_aux_t ret;
@@ -1569,8 +1661,10 @@ key_hint_boolean(const char *key, struct key_def *key_def)
 
 template<bool is_nullable>
 static cmp_aux_t
-tuple_hint_boolean(const struct tuple *tuple, struct key_def *key_def)
+tuple_hint_boolean(const struct tuple *tuple, struct key_def *key_def,
+		   uint64_t multikey_idx)
 {
+	(void)multikey_idx;
 	assert(key_part_is_nullable(key_def->parts) == is_nullable);
 	assert(key_def->parts->type == FIELD_TYPE_BOOLEAN);
 	const char *field = tuple_field_by_part(tuple, key_def->parts);
@@ -1612,8 +1706,10 @@ key_hint_string(const char *key, struct key_def *key_def)
 
 template<bool is_nullable>
 static cmp_aux_t
-tuple_hint_string(const struct tuple *tuple, struct key_def *key_def)
+tuple_hint_string(const struct tuple *tuple, struct key_def *key_def,
+		  uint64_t multikey_idx)
 {
+	(void)multikey_idx;
 	assert(key_part_is_nullable(key_def->parts) == is_nullable);
 	assert(key_def->parts->coll == NULL);
 	assert(key_def->parts->type == FIELD_TYPE_STRING);
@@ -1647,8 +1743,10 @@ key_hint_string_coll(const char *key, struct key_def *key_def)
 
 template<bool is_nullable>
 static cmp_aux_t
-tuple_hint_string_coll(const struct tuple *tuple, struct key_def *key_def)
+tuple_hint_string_coll(const struct tuple *tuple, struct key_def *key_def,
+		       uint64_t multikey_idx)
 {
+	(void)multikey_idx;
 	assert(key_part_is_nullable(key_def->parts) == is_nullable);
 	assert(key_def->parts->type == FIELD_TYPE_STRING &&
 	        key_def->parts->coll != NULL);
@@ -1661,11 +1759,26 @@ tuple_hint_string_coll(const struct tuple *tuple, struct key_def *key_def)
 	return key_hint_string_coll<is_nullable>(field, key_def);
 }
 
+static cmp_aux_t
+tuple_multikey_idx_hint(const struct tuple *tuple, struct key_def *key_def,
+			uint64_t multikey_idx)
+{
+	(void)tuple;
+	(void)key_def;
+	cmp_aux_t ret;
+	ret.multikey_idx = multikey_idx;
+	return ret;
+}
+
 void
 key_def_set_cmp_aux_func(struct key_def *def)
 {
 	def->key_cmp_aux = key_hint_default;
 	def->tuple_cmp_aux = tuple_hint_default;
+	if (def->has_multikey_parts) {
+		def->tuple_cmp_aux = tuple_multikey_idx_hint;
+		return;
+	}
 	bool is_nullable = key_part_is_nullable(def->parts);
 	if (def->parts->type == FIELD_TYPE_STRING && def->parts->coll != NULL) {
 		def->key_cmp_aux = is_nullable ? key_hint_string_coll<true> :
diff --git a/src/box/tuple_format.c b/src/box/tuple_format.c
index 4439ce3e0..99b602cd5 100644
--- a/src/box/tuple_format.c
+++ b/src/box/tuple_format.c
@@ -33,6 +33,7 @@
 #include "json/json.h"
 #include "tuple_format.h"
 #include "coll_id_cache.h"
+#include "tuple.h"
 
 #include "third_party/PMurHash.h"
 
@@ -233,14 +234,19 @@ tuple_format_add_field(struct tuple_format *format, uint32_t fieldno,
 	json_lexer_create(&lexer, path, path_len, TUPLE_INDEX_BASE);
 	while ((rc = json_lexer_next_token(&lexer, &field->token)) == 0 &&
 	       field->token.type != JSON_TOKEN_END) {
-		if (field->token.type == JSON_TOKEN_ANY) {
-			diag_set(ClientError, ER_UNSUPPORTED,
-				"Tarantool", "multikey indexes");
-			goto fail;
-		}
 		enum field_type expected_type =
 			field->token.type == JSON_TOKEN_STR ?
 			FIELD_TYPE_MAP : FIELD_TYPE_ARRAY;
+		if (field->token.type == JSON_TOKEN_ANY &&
+		    !json_token_is_multikey(&parent->token) &&
+		    !json_token_is_leaf(&parent->token)) {
+			assert(expected_type == FIELD_TYPE_ARRAY);
+			diag_set(ClientError, ER_INDEX_PART_TYPE_MISMATCH,
+				 tuple_field_path(parent),
+				 field_type_strs[parent->type],
+				 "multikey array");
+			goto fail;
+		}
 		if (field_type1_contains_type2(parent->type, expected_type)) {
 			parent->type = expected_type;
 		} else {
@@ -475,9 +481,8 @@ tuple_format_create(struct tuple_format *format, struct key_def * const *keys,
 					break;
 				format->min_tuple_size += mp_sizeof_nil();
 			}
-		} else {
+		} else if (field->token.type == JSON_TOKEN_STR) {
 			/* Account a key string for map member. */
-			assert(field->token.type == JSON_TOKEN_STR);
 			format->min_tuple_size +=
 				mp_sizeof_str(field->token.len);
 		}
@@ -805,6 +810,59 @@ tuple_format1_can_store_format2_tuples(struct tuple_format *format1,
 	return true;
 }
 
+/**
+ * Grow tuple_field_map allocation left with extent_size
+ * 0 bytes.
+ */
+static int
+tuple_field_map_realloc(uint32_t **field_map, uint32_t *field_map_size,
+			uint32_t extent_size, struct region *region)
+{
+	assert(extent_size % sizeof(uint32_t) == 0);
+	uint32_t new_field_map_size = *field_map_size + extent_size;
+	uint32_t *new_field_map = region_alloc(region, new_field_map_size);
+	if (new_field_map == NULL) {
+		diag_set(OutOfMemory, new_field_map_size, "region_alloc",
+			 "new_field_map");
+		return -1;
+	}
+	memset(new_field_map, 0, extent_size);
+	if (*field_map != NULL) {
+		memcpy((char *)new_field_map + extent_size,
+		       (char *)*field_map - *field_map_size, *field_map_size);
+	}
+	*field_map = (uint32_t *)((char *)new_field_map + new_field_map_size);
+	*field_map_size = new_field_map_size;
+	return 0;
+}
+
+/**
+ * Retrieve tuple field map extent by root_offset_slot, reallocate
+ * memory if required.
+ */
+struct field_map_ext *
+tuple_field_map_ext_retrieve(uint32_t **field_map, uint32_t *field_map_size,
+			     int32_t root_offset_slot, uint32_t extent_items,
+			     struct region *region)
+{
+	uint32_t extent_sz = sizeof(struct field_map_ext) +
+			     extent_items * sizeof(uint32_t);
+	uint32_t slot_off = (*field_map)[root_offset_slot];
+	if (slot_off == 0) {
+		/* Field map extent was not created yet. */
+		slot_off = *field_map_size / sizeof(uint32_t);
+		(*field_map)[root_offset_slot] = slot_off;
+		if (tuple_field_map_realloc(field_map, field_map_size,
+					    extent_sz, region) != 0)
+			return NULL;
+	}
+	struct field_map_ext *field_map_ext =
+		tuple_field_map_ext(*field_map, root_offset_slot);
+	assert(field_map_ext->size == 0 || field_map_ext->size == extent_items);
+	field_map_ext->size = extent_items;
+	return field_map_ext;
+}
+
 /** @sa declaration for details. */
 int
 tuple_field_map_create(struct tuple_format *format, const char *tuple,
@@ -817,14 +875,11 @@ tuple_field_map_create(struct tuple_format *format, const char *tuple,
 		return 0; /* Nothing to initialize */
 	}
 	struct region *region = &fiber()->gc;
-	*field_map_size = format->field_map_size;
-	*field_map = region_alloc(region, *field_map_size);
-	if (*field_map == NULL) {
-		diag_set(OutOfMemory, *field_map_size, "region_alloc",
-			 "field_map");
+	*field_map = NULL;
+	*field_map_size = 0;
+	if (tuple_field_map_realloc(field_map, field_map_size,
+				    format->field_map_size, region) != 0)
 		return -1;
-	}
-	*field_map = (uint32_t *)((char *)*field_map + *field_map_size);
 
 	const char *pos = tuple;
 	int rc = 0;
@@ -864,11 +919,6 @@ tuple_field_map_create(struct tuple_format *format, const char *tuple,
 	uint32_t defined_field_count = MIN(field_count, validate ?
 					   tuple_format_field_count(format) :
 					   format->index_field_count);
-	/*
-	 * Nullify field map to be able to detect by 0,
-	 * which key fields are absent in tuple_field().
-	 */
-	memset((char *)*field_map - *field_map_size, 0, *field_map_size);
 	/*
 	 * Prepare mp stack of the size equal to the maximum depth
 	 * of the indexed field in the format::fields tree
@@ -885,6 +935,12 @@ tuple_field_map_create(struct tuple_format *format, const char *tuple,
 	struct mp_stack stack;
 	mp_stack_create(&stack, format->fields_depth, frames);
 	mp_stack_push(&stack, MP_ARRAY, defined_field_count);
+	/**
+	 * Pointer to the stack entry that represents the multikey
+	 * index root ARRAY entry.
+	 */
+	struct mp_frame *mk_parent_frame = NULL;
+
 	struct tuple_field *field;
 	struct json_token *parent = &format->fields.root;
 	while (true) {
@@ -901,6 +957,10 @@ tuple_field_map_create(struct tuple_format *format, const char *tuple,
 			mp_stack_pop(&stack);
 			if (mp_stack_is_empty(&stack))
 				goto finish;
+			if (json_token_is_multikey(parent)) {
+				/* Leave multikey index branch. */
+				mk_parent_frame = NULL;
+			}
 			parent = parent->parent;
 		}
 		/*
@@ -950,8 +1010,23 @@ tuple_field_map_create(struct tuple_format *format, const char *tuple,
 					 field_type_strs[field->type]);
 				goto error;
 			}
-			if (field->offset_slot != TUPLE_OFFSET_SLOT_NIL)
+			if (field->offset_slot != TUPLE_OFFSET_SLOT_NIL &&
+			    mk_parent_frame == NULL) {
 				(*field_map)[field->offset_slot] = pos - tuple;
+			} else if (field->offset_slot != TUPLE_OFFSET_SLOT_NIL &&
+				   mk_parent_frame != NULL) {
+				uint32_t extent_items = mk_parent_frame->count;
+				struct field_map_ext *field_map_ext =
+					tuple_field_map_ext_retrieve(field_map,
+							field_map_size,
+							field->offset_slot,
+							extent_items, region);
+				if (field_map_ext == NULL)
+					goto error;
+				int multikey_idx = mk_parent_frame->curr;
+				field_map_ext->field_map[
+					-multikey_idx] = pos - tuple;
+			}
 			if (required_fields != NULL)
 				bit_clear(required_fields, field->id);
 		}
@@ -968,6 +1043,11 @@ tuple_field_map_create(struct tuple_format *format, const char *tuple,
 					mp_decode_array(&pos) :
 					mp_decode_map(&pos);
 			mp_stack_push(&stack, type, size);
+			if (json_token_is_multikey(&field->token)) {
+				/* Track multikey entry frame. */
+				assert(type == MP_ARRAY);
+				mk_parent_frame = &frames[stack.used - 1];
+			}
 			parent = &field->token;
 		} else {
 			mp_next(&pos);
diff --git a/test/engine/json.result b/test/engine/json.result
index a790cdfbc..5c7a9b3b3 100644
--- a/test/engine/json.result
+++ b/test/engine/json.result
@@ -691,7 +691,85 @@ s = box.schema.space.create('withdata')
 ...
 idx = s:create_index('idx', {parts = {{3, 'str', path = '[*].fname'}, {3, 'str', path = '[*].sname'}}})
 ---
-- error: Tarantool does not support multikey indexes
+...
+s:insert({1, 1, {{fname='James', sname='Bond'}, {fname='Vasya', sname='Pupkin'}}})
+---
+- [1, 1, [{'fname': 'James', 'sname': 'Bond'}, {'fname': 'Vasya', 'sname': 'Pupkin'}]]
+...
+s:insert({1, 1, {{fname='Ivan', sname='Ivanych'}}})
+---
+- [1, 1, [{'fname': 'Ivan', 'sname': 'Ivanych'}]]
+...
+idx:select({'James', 'Bond'})
+---
+- - [1, 1, [{'fname': 'James', 'sname': 'Bond'}, {'fname': 'Vasya', 'sname': 'Pupkin'}]]
+...
+idx:select({'Kirill', 'Shcherbatov'})
+---
+- []
+...
+idx:select({'Ivan', 'Ivanych'})
+---
+- - [1, 1, [{'fname': 'Ivan', 'sname': 'Ivanych'}]]
+...
+idx:select({'Vasya', 'Pupkin'})
+---
+- - [1, 1, [{'fname': 'James', 'sname': 'Bond'}, {'fname': 'Vasya', 'sname': 'Pupkin'}]]
+...
+idx:select()
+---
+- - [1, 1, [{'fname': 'Ivan', 'sname': 'Ivanych'}]]
+  - [1, 1, [{'fname': 'James', 'sname': 'Bond'}, {'fname': 'Vasya', 'sname': 'Pupkin'}]]
+  - [1, 1, [{'fname': 'James', 'sname': 'Bond'}, {'fname': 'Vasya', 'sname': 'Pupkin'}]]
+...
+s:insert({2, 1, {{fname='Vasya', sname='Pupkin'}}})
+---
+- error: Duplicate key exists in unique index 'idx' in space 'withdata'
+...
+s:insert({2, 1, {{fname='James', sname='Bond'}}})
+---
+- error: Duplicate key exists in unique index 'idx' in space 'withdata'
+...
+idx:select()
+---
+- - [1, 1, [{'fname': 'Ivan', 'sname': 'Ivanych'}]]
+  - [1, 1, [{'fname': 'James', 'sname': 'Bond'}, {'fname': 'Vasya', 'sname': 'Pupkin'}]]
+  - [1, 1, [{'fname': 'James', 'sname': 'Bond'}, {'fname': 'Vasya', 'sname': 'Pupkin'}]]
+...
+idx:delete({'Vasya', 'Pupkin'})
+---
+- [1, 1, [{'fname': 'James', 'sname': 'Bond'}, {'fname': 'Vasya', 'sname': 'Pupkin'}]]
+...
+s:insert({2, 1, {{fname='Vasya', sname='Pupkin'}}})
+---
+- [2, 1, [{'fname': 'Vasya', 'sname': 'Pupkin'}]]
+...
+s:insert({2, 1, {{fname='James', sname='Bond'}}})
+---
+- [2, 1, [{'fname': 'James', 'sname': 'Bond'}]]
+...
+idx:select()
+---
+- - [1, 1, [{'fname': 'Ivan', 'sname': 'Ivanych'}]]
+  - [2, 1, [{'fname': 'James', 'sname': 'Bond'}]]
+  - [2, 1, [{'fname': 'Vasya', 'sname': 'Pupkin'}]]
+...
+s:drop()
+---
+...
+s = box.schema.space.create('withdata')
+---
+...
+pk = s:create_index('pk')
+---
+...
+idx = s:create_index('idx', {parts = {{3, 'str', path = '[*].fname'}, {3, 'str', path = '[*].extra.sname', is_nullable = true}}})
+---
+...
+s:insert({1, 1, {{fname='A1', extra={sname='A2'}}, {fname='B1'}, {fname='C1', extra={sname='C2'}}}})
+---
+- [1, 1, [{'fname': 'A1', 'extra': {'sname': 'A2'}}, {'fname': 'B1'}, {'fname': 'C1',
+      'extra': {'sname': 'C2'}}]]
 ...
 s:drop()
 ---
diff --git a/test/engine/json.test.lua b/test/engine/json.test.lua
index f9a7180b1..dc6016af9 100644
--- a/test/engine/json.test.lua
+++ b/test/engine/json.test.lua
@@ -198,4 +198,24 @@ s:drop()
 --
 s = box.schema.space.create('withdata')
 idx = s:create_index('idx', {parts = {{3, 'str', path = '[*].fname'}, {3, 'str', path = '[*].sname'}}})
+s:insert({1, 1, {{fname='James', sname='Bond'}, {fname='Vasya', sname='Pupkin'}}})
+s:insert({1, 1, {{fname='Ivan', sname='Ivanych'}}})
+idx:select({'James', 'Bond'})
+idx:select({'Kirill', 'Shcherbatov'})
+idx:select({'Ivan', 'Ivanych'})
+idx:select({'Vasya', 'Pupkin'})
+idx:select()
+s:insert({2, 1, {{fname='Vasya', sname='Pupkin'}}})
+s:insert({2, 1, {{fname='James', sname='Bond'}}})
+idx:select()
+idx:delete({'Vasya', 'Pupkin'})
+s:insert({2, 1, {{fname='Vasya', sname='Pupkin'}}})
+s:insert({2, 1, {{fname='James', sname='Bond'}}})
+idx:select()
+s:drop()
+
+s = box.schema.space.create('withdata')
+pk = s:create_index('pk')
+idx = s:create_index('idx', {parts = {{3, 'str', path = '[*].fname'}, {3, 'str', path = '[*].extra.sname', is_nullable = true}}})
+s:insert({1, 1, {{fname='A1', extra={sname='A2'}}, {fname='B1'}, {fname='C1', extra={sname='C2'}}}})
 s:drop()
-- 
2.21.0

Re: [tarantool-patches] [PATCH v5 4/4] box: introduce multikey indexes

[Vladimir Davydov]

On Thu, Mar 07, 2019 at 06:55:09PM +0300, Kirill Shcherbatov wrote:
> diff --git a/src/box/key_def.c b/src/box/key_def.c
> index 771c30172..f6ca461c4 100644
> --- a/src/box/key_def.c
> +++ b/src/box/key_def.c
> @@ -165,9 +165,24 @@ key_def_set_part(struct key_def *def, uint32_t part_no, uint32_t fieldno,
>  		*path_pool += path_len;
>  		memcpy(def->parts[part_no].path, path, path_len);
>  		def->parts[part_no].path_len = path_len;
> +
> +		int rc;
> +		struct json_lexer lexer;
> +		struct json_token token;
> +		json_lexer_create(&lexer, path, path_len, TUPLE_INDEX_BASE);
> +		while ((rc = json_lexer_next_token(&lexer, &token)) == 0) {
> +			if (token.type == JSON_TOKEN_ANY) {
> +				def->has_multikey_parts = true;
> +				def->parts[part_no].is_multikey = true;
> +				break;
> +			} else if (token.type == JSON_TOKEN_END) {
> +				break;
> +			}
> +		}

Better wrap this in a helper in json lib.

>  	} else {
>  		def->parts[part_no].path = NULL;
>  		def->parts[part_no].path_len = 0;
> +		def->parts[part_no].is_multikey = false;
>  	}
>  	column_mask_set_fieldno(&def->column_mask, fieldno);
>  }
> diff --git a/src/box/key_def.h b/src/box/key_def.h
> index c630e6b43..37fae6b52 100644
> --- a/src/box/key_def.h
> +++ b/src/box/key_def.h
> @@ -610,13 +611,106 @@ memtx_tree_index_replace(struct index *base, struct tuple *old_tuple,
>  	}
>  	if (old_tuple) {
>  		struct memtx_tree_data old_data;
> -		memtx_tree_data_set(&old_data, old_tuple, key_def);
> +		memtx_tree_data_set(&old_data, old_tuple, key_def,
> +				    INVALID_MULTIKEY_INDEX);
>  		memtx_tree_delete(&index->tree, old_data);
>  	}
>  	*result = old_tuple;
>  	return 0;
>  }
>  
> +static int
> +multikey_get_array_sz(struct tuple *tuple, struct key_def *key_def)

This function is engine independent. Moreover, we will need it in
Vinyl as well. Please move it to key_def.c.

> +{
> +	assert(key_def->has_multikey_parts);
> +	struct key_part *part = key_def->parts;
> +	/* FIXME: don't like it... */

Me neither. What about storing the path to the first '*' in key_def
instead? You wouldn't need to allocate it - you could simply set it
to point to key_part->path of the first multikey part and store the
length in key_def. Then you wouldn't need to iterate over key parts
here - instead you would simply use the path stored in key_def. You
wouldn't need to add is_multikey and has_multikey_parts flags either.
Instead you could check if the path stored in key_def is not NULL.

This would also allow you to check if multikey parts are compatible
while building a key_def, in key_def_set_part: upon encountering the
first multikey part, you would initialize multikey path in key_def;
then you would check if subsequent multikey paths have the same prefix
(you would need to introduce json_path_ncmp helper for this, I guess).

> +	while (part < key_def->parts + key_def->part_count &&
> +	       !part->is_multikey)
> +		part++;
> +	assert(part->path != NULL && part->is_multikey);
> +	struct tuple_field *field =
> +		tuple_format_field_by_path(tuple_format(tuple), part->fieldno,
> +					   part->path, part->path_len);
> +	assert(field != NULL);

This isn't necessarily true. Just like tuple_field_by_path, this
function must fall back on decoding the msgpack in case the tuple
field isn't indexed in the format.

> +	struct field_map_ext *field_map_ext =
> +		tuple_field_map_ext((uint32_t *)tuple_field_map(tuple),
> +				    field->offset_slot);
> +	return field_map_ext->size;
> +}
> +
> +int
> +memtx_multikey_tree_index_replace(struct index *base, struct tuple *old_tuple,

Nit: memtx_tree_index_ is kinda namespace here so better call it
memtx_tree_index_replace_multikey IMO. The same's fair for other
multikey functions and constants.

> +				  struct tuple *new_tuple,
> +				  enum dup_replace_mode mode,
> +				  struct tuple **result)
> +{
> +	struct memtx_tree_index *index = (struct memtx_tree_index *)base;
> +	struct key_def *key_def = index->tree.arg;
> +	if (new_tuple != NULL) {
> +		int errcode = 0, tree_res = 0;
> +		struct tuple *dup_tuple = NULL;
> +		int multikey_idx = 0;
> +		int sz = multikey_get_array_sz(new_tuple, key_def);
> +		for (; multikey_idx < sz; multikey_idx++) {
> +			struct memtx_tree_data new_data;
> +			memtx_tree_data_set(&new_data, new_tuple, key_def,
> +					    multikey_idx);
> +			struct memtx_tree_data dup_data;
> +			memtx_tree_data_clear(&dup_data);
> +			tree_res = memtx_tree_insert(&index->tree, new_data,
> +						     &dup_data);
> +			if (tree_res != 0) {
> +				diag_set(OutOfMemory, MEMTX_EXTENT_SIZE,
> +					 "memtx_tree_index", "replace");
> +				break;
> +			}
> +			dup_tuple = dup_data.tuple;
> +			errcode = replace_check_dup(old_tuple, dup_tuple, mode);
> +			if (errcode != 0) {
> +				memtx_tree_delete(&index->tree, new_data);
> +				if (dup_tuple != NULL) {
> +					memtx_tree_insert(&index->tree,
> +							  dup_data, NULL);
> +				}
> +				struct space *sp =
> +					space_cache_find(base->def->space_id);
> +				if (sp != NULL) {
> +					diag_set(ClientError, errcode,
> +						 base->def->name,
> +						 space_name(sp));
> +				}
> +				break;
> +			}
> +		}
> +		if (tree_res != 0 || errcode != 0) {
> +			multikey_idx--;
> +			for (; multikey_idx >= 0; multikey_idx--) {
> +				struct memtx_tree_data data;
> +				memtx_tree_data_set(&data, new_tuple, key_def,
> +						    multikey_idx);
> +				memtx_tree_delete(&index->tree, data);
> +			}
> +			return -1;
> +		}
> +		if (dup_tuple != NULL) {
> +			*result = dup_tuple;
> +			return 0;
> +		}
> +	}
> +	if (old_tuple != NULL) {
> +		int sz = multikey_get_array_sz(old_tuple, key_def);
> +		for (int multikey_idx = 0; multikey_idx < sz; multikey_idx++) {
> +			struct memtx_tree_data old_data;
> +			memtx_tree_data_set(&old_data, old_tuple, key_def,
> +					    multikey_idx);
> +			memtx_tree_delete(&index->tree, old_data);
> +		}
> +	}
> +	*result = old_tuple;
> +	return 0;
> +}
> +
>  static struct iterator *
>  memtx_tree_index_create_iterator(struct index *base, enum iterator_type type,
>  				 const char *key, uint32_t part_count)
> @@ -718,7 +812,48 @@ memtx_tree_index_build_next(struct index *base, struct tuple *tuple)
>  	}
>  	struct memtx_tree_data *elem =
>  		&index->build_array[index->build_array_size++];
> -	memtx_tree_data_set(elem, tuple, key_def);
> +	memtx_tree_data_set(elem, tuple, key_def, INVALID_MULTIKEY_INDEX);
> +	return 0;
> +}
> +
> +static int
> +memtx_multikey_tree_index_build_next(struct index *base, struct tuple *tuple)
> +{
> +	struct memtx_tree_index *index = (struct memtx_tree_index *)base;
> +	struct key_def *key_def = index->tree.arg;
> +	int sz = multikey_get_array_sz(tuple, key_def);
> +
> +	if (index->build_array == NULL) {
> +		index->build_array =
> +			(struct memtx_tree_data *)malloc(MEMTX_EXTENT_SIZE);
> +		if (index->build_array == NULL) {
> +			diag_set(OutOfMemory, MEMTX_EXTENT_SIZE,
> +				 "memtx_tree_index", "build_next");
> +			return -1;
> +		}
> +		index->build_array_alloc_size =
> +			MEMTX_EXTENT_SIZE / sizeof(index->build_array[0]);
> +	}
> +	assert(index->build_array_size <= index->build_array_alloc_size);
> +	if (index->build_array_size == index->build_array_alloc_size) {
> +		index->build_array_alloc_size = index->build_array_alloc_size +
> +					index->build_array_alloc_size / 2;
> +		struct memtx_tree_data *tmp =
> +			realloc(index->build_array,
> +				index->build_array_alloc_size * sizeof(*tmp));
> +		if (tmp == NULL) {
> +			diag_set(OutOfMemory, index->build_array_alloc_size *
> +				 sizeof(*tmp), "memtx_tree_index", "build_next");
> +			return -1;
> +		}
> +		index->build_array = tmp;
> +	}

This was copied-n-pasted from memtx_tree_index_build_next.
Better introduce a helper function for that.

> +	for (int multikey_idx = 0; multikey_idx < sz; multikey_idx++) {
> +		struct memtx_tree_data *elem =
> +			&index->build_array[index->build_array_size++];
> +		assert(index->build_array_size < index->build_array_alloc_size);
> +		memtx_tree_data_set(elem, tuple, key_def, multikey_idx);
> +	}
>  	return 0;
>  }
>  
> diff --git a/src/box/tuple.c b/src/box/tuple.c
> index 7f06d4053..c8a938c4c 100644
> --- a/src/box/tuple.c
> +++ b/src/box/tuple.c
> @@ -455,7 +455,8 @@ tuple_field_go_to_key(const char **field, const char *key, int len)
>  }
>  
>  int
> -tuple_go_to_path(const char **data, const char *path, uint32_t path_len)
> +tuple_go_to_path_multikey(const char **data, const char *path,
> +			  uint32_t path_len, uint64_t multikey_idx)
>  {
>  	int rc;
>  	struct json_lexer lexer;
> @@ -463,6 +464,8 @@ tuple_go_to_path(const char **data, const char *path, uint32_t path_len)
>  	json_lexer_create(&lexer, path, path_len, TUPLE_INDEX_BASE);
>  	while ((rc = json_lexer_next_token(&lexer, &token)) == 0) {
>  		switch (token.type) {
> +		case JSON_TOKEN_ANY:
> +			token.num = (int)multikey_idx;

FALLTHROUGH is missing - this code may not compile on certain platforms.

Also, let's use int instead of uint64_t for multikey_idx. And rather
than adding INVALID_MULTIKEY_INDEX contant, simply check if multikey_idx
is non-negative.

Also, an assertion ensuring that if '*' is encountered mutlikey_idx
is set would be welcome here.

>  		case JSON_TOKEN_NUM:
>  			rc = tuple_field_go_to_index(data, token.num);
>  			break;
> @@ -532,7 +535,8 @@ tuple_field_raw_by_full_path(struct tuple_format *format, const char *tuple,
>  	}
>  	return tuple_field_raw_by_path(format, tuple, field_map, fieldno,
>  				       path + lexer.offset,
> -				       path_len - lexer.offset, NULL);
> +				       path_len - lexer.offset, NULL,
> +				       INVALID_MULTIKEY_INDEX);
>  }
>  
>  /* }}} tuple_field_* getters */
> diff --git a/src/box/tuple.h b/src/box/tuple.h
> index 8b12fd5a8..e498e1e41 100644
> --- a/src/box/tuple.h
> +++ b/src/box/tuple.h
> @@ -45,6 +45,8 @@ struct slab_arena;
>  struct quota;
>  struct key_part;
>  
> +#define INVALID_MULTIKEY_INDEX UINT64_MAX
> +
>  /**
>   * A format for standalone tuples allocated on runtime arena.
>   * \sa tuple_new().
> @@ -286,6 +288,7 @@ box_tuple_upsert(const box_tuple_t *tuple, const char *expr, const
>  
>  /** \endcond public */
>  
> +

Nit: extra change.

>  /**
>   * An atom of Tarantool storage. Represents MsgPack Array.
>   * Tuple has the following structure:
> @@ -296,7 +299,9 @@ box_tuple_upsert(const box_tuple_t *tuple, const char *expr, const
>   * |                                            ^
>   * +---------------------------------------data_offset
>   *
> - * Each 'off_i' is the offset to the i-th indexed field.
> + * Each 'off_i' is the offset to the i-th indexed field or field
> + * map extention (described with struct tuple_field_map_ext)
> + * offset (in sizeof(field_map[0]) units).

The comment is bad as it doesn't really explain what a field map
extension looks like, nor in what cases is it created. A diagram
would be helpful here.

>   */
>  struct PACKED tuple
>  {
> @@ -328,6 +333,26 @@ struct PACKED tuple
>  	 */
>  };
>  
> +/**
> + * Tuple field map extent. Is allocated on tuple_field_map_create
> + * call automatically when necessary, when tuple field map must be
> + * reallocated dynamically.
> + */
> +struct field_map_ext {
> +	/* Sequence of data offset slots. */
> +	uint32_t field_map[1];

This looks weird.

> +	/* The count of field_map items. */
> +	uint32_t size;
> +};

I don't think that this deserves a separate structure. I'd rather
you access the offset map array directly.

> +
> +static inline struct field_map_ext *
> +tuple_field_map_ext(uint32_t *field_map, int32_t root_offset_slot)
> +{
> +	uint32_t slot_off = field_map[root_offset_slot];
> +	return (struct field_map_ext *)((char *)field_map -
> +		slot_off * sizeof(uint32_t) - sizeof(struct field_map_ext));
> +}
> +
>  /** Size of the tuple including size of struct tuple. */
>  static inline size_t
>  tuple_size(const struct tuple *tuple)
> @@ -508,11 +533,32 @@ tuple_field_count(const struct tuple *tuple)
>   *                      with NULL.
>   * @param path The path to process.
>   * @param path_len The length of the @path.
> + * @param multikey_index The multikey index hint - index of item

It's multikey_idx.

> + *                       for JSON_TOKEN_ANY level.
>   * @retval 0 On success.
>   * @retval -1 In case of error in JSON path.
>   */
>  int
> -tuple_go_to_path(const char **data, const char *path, uint32_t path_len);
> +tuple_go_to_path_multikey(const char **data, const char *path,
> +			  uint32_t path_len, uint64_t multikey_idx);
> +
> +/**
> + * Retrieve msgpack data by JSON path.
> + * @param data[in, out] Pointer to msgpack with data.
> + *                      If the field cannot be retrieved be the
> + *                      specified path @path, it is overwritten
> + *                      with NULL.
> + * @param path The path to process.
> + * @param path_len The length of the @path.
> + * @retval 0 On success.
> + * @retval -1 In case of error in JSON path.
> + */

Copying-and-pasting is bad, even in case of comments. Please instead
of writing a doxygen-style comment, just say a few words about this
function: what it does, what it expects (the path must not have '*',
I assume).

> +static inline int
> +tuple_go_to_path(const char **data, const char *path, uint32_t path_len)
> +{
> +	return tuple_go_to_path_multikey(data, path, path_len,
> +					 INVALID_MULTIKEY_INDEX);
> +}
>  
>  /**
>   * Get tuple field by field index and relative JSON path.
> @@ -533,7 +579,7 @@ static inline const char *
>  tuple_field_raw_by_path(struct tuple_format *format, const char *tuple,
>  			const uint32_t *field_map, uint32_t fieldno,
>  			const char *path, uint32_t path_len,
> -			int32_t *offset_slot_hint)
> +			int32_t *offset_slot_hint, uint64_t multikey_idx)

Update the comment please.

>  {
>  	int32_t offset_slot;
>  	if (offset_slot_hint != NULL &&
> @@ -558,10 +604,22 @@ tuple_field_raw_by_path(struct tuple_format *format, const char *tuple,
>  		if (offset_slot_hint != NULL)
>  			*offset_slot_hint = offset_slot;
>  offset_slot_access:
> -		/* Indexed field */
> -		if (field_map[offset_slot] == 0)
> -			return NULL;
> -		tuple += field_map[offset_slot];
> +		if (multikey_idx != INVALID_MULTIKEY_INDEX) {
> +			struct field_map_ext *field_map_ext =
> +				tuple_field_map_ext((uint32_t *)field_map,
> +						    offset_slot);
> +			if (multikey_idx >= field_map_ext->size)
> +				return NULL;
> +			uint32_t off = field_map_ext->field_map[-multikey_idx];
> +			if (off == 0)
> +				return NULL;
> +			tuple += off;
> +		} else {
> +			/* Indexed field */

Confused. Both branches are for indexed fields, aren't they?

Anyway, I'd move this whole thing (retrieving offset slot) to a separate
helper function.

> +			if (field_map[offset_slot] == 0)
> +				return NULL;
> +			tuple += field_map[offset_slot];
> +		}
>  	} else {
>  		uint32_t field_count;
>  parse:
> @@ -634,16 +692,18 @@ tuple_field_raw_by_full_path(struct tuple_format *format, const char *tuple,
>  			     uint32_t path_len, uint32_t path_hash);
>  
>  /**
> - * Get a tuple field pointed to by an index part.
> + * Get a tuple field pointed to by an index part and multikey hint.
>   * @param format Tuple format.
>   * @param tuple A pointer to MessagePack array.
>   * @param field_map A pointer to the LAST element of field map.
> + * @param multikey_idx A multikey hint.

What's a multikey hint? Please mention it in the comment.

>   * @param part Index part to use.
>   * @retval Field data if the field exists or NULL.
>   */
>  static inline const char *
> -tuple_field_raw_by_part(struct tuple_format *format, const char *data,
> -			const uint32_t *field_map, struct key_part *part)
> +tuple_field_raw_by_part_multikey(struct tuple_format *format, const char *data,
> +				 const uint32_t *field_map,
> +				 struct key_part *part, uint64_t multikey_idx)
>  {
>  	if (unlikely(part->format_epoch != format->epoch)) {
>  		assert(format->epoch != 0);
> diff --git a/src/box/tuple_compare.cc b/src/box/tuple_compare.cc
> index 5b06e06b3..dbf7bb4f6 100644
> --- a/src/box/tuple_compare.cc
> +++ b/src/box/tuple_compare.cc
> @@ -458,10 +458,12 @@ tuple_common_key_parts(const struct tuple *tuple_a, const struct tuple *tuple_b,
>  	return i;
>  }
>  
> -template<bool is_nullable, bool has_optional_parts, bool has_json_paths>
> +template<bool is_nullable, bool has_optional_parts, bool has_json_paths,
> +	 bool is_multikey>
>  static inline int
> -tuple_compare_slowpath(const struct tuple *tuple_a, const struct tuple *tuple_b,
> -		       struct key_def *key_def)
> +tuple_compare_slowpath_multikey(const struct tuple *tuple_a,

The function has suffix _multikey, but it may be defined with
is_multikey = false template parameter. This is confusing.

> +		cmp_aux_t tuple_a_cmp_aux, const struct tuple *tuple_b,
> +		cmp_aux_t tuple_b_cmp_aux, struct key_def *key_def)
>  {
>  	assert(has_json_paths == key_def->has_json_paths);
>  	assert(!has_optional_parts || is_nullable);

Please add an assertion for is_multikey.

> @@ -471,7 +473,7 @@ tuple_compare_slowpath(const struct tuple *tuple_a, const struct tuple *tuple_b,
>  	const char *tuple_a_raw = tuple_data(tuple_a);
>  	const char *tuple_b_raw = tuple_data(tuple_b);
>  	if (key_def->part_count == 1 && part->fieldno == 0 &&
> -	    (!has_json_paths || part->path == NULL)) {
> +	    (!has_json_paths || part->path == NULL) && !is_multikey) {

I don't understand why you need this: is_multikey can't be set if
there's no json path.

>  		/*
>  		 * First field can not be optional - empty tuples
>  		 * can not exist.
> diff --git a/src/box/tuple_format.c b/src/box/tuple_format.c
> index 4439ce3e0..99b602cd5 100644
> --- a/src/box/tuple_format.c
> +++ b/src/box/tuple_format.c
> @@ -33,6 +33,7 @@
>  #include "json/json.h"
>  #include "tuple_format.h"
>  #include "coll_id_cache.h"
> +#include "tuple.h"
>  
>  #include "third_party/PMurHash.h"
>  
> @@ -233,14 +234,19 @@ tuple_format_add_field(struct tuple_format *format, uint32_t fieldno,
>  	json_lexer_create(&lexer, path, path_len, TUPLE_INDEX_BASE);
>  	while ((rc = json_lexer_next_token(&lexer, &field->token)) == 0 &&
>  	       field->token.type != JSON_TOKEN_END) {
> -		if (field->token.type == JSON_TOKEN_ANY) {
> -			diag_set(ClientError, ER_UNSUPPORTED,
> -				"Tarantool", "multikey indexes");
> -			goto fail;
> -		}
>  		enum field_type expected_type =
>  			field->token.type == JSON_TOKEN_STR ?
>  			FIELD_TYPE_MAP : FIELD_TYPE_ARRAY;
> +		if (field->token.type == JSON_TOKEN_ANY &&
> +		    !json_token_is_multikey(&parent->token) &&
> +		    !json_token_is_leaf(&parent->token)) {
> +			assert(expected_type == FIELD_TYPE_ARRAY);
> +			diag_set(ClientError, ER_INDEX_PART_TYPE_MISMATCH,
> +				 tuple_field_path(parent),
> +				 field_type_strs[parent->type],
> +				 "multikey array");
> +			goto fail;
> +		}

"Field [1].a has type 'array' in one index, but type 'multikey array' in another"

Sounds confusing. IMO better introduce a new error code for this.

BTW, you should also check that there's no multikey parts in Vinyl
indexes. And that there's no two incompatible/unsupported multikey
parts (e.g. a.b[*] and a.c[*], or a.b[*] and a.b[*][*]).

>  		if (field_type1_contains_type2(parent->type, expected_type)) {
>  			parent->type = expected_type;
>  		} else {
> @@ -475,9 +481,8 @@ tuple_format_create(struct tuple_format *format, struct key_def * const *keys,
>  					break;
>  				format->min_tuple_size += mp_sizeof_nil();
>  			}
> -		} else {
> +		} else if (field->token.type == JSON_TOKEN_STR) {
>  			/* Account a key string for map member. */
> -			assert(field->token.type == JSON_TOKEN_STR);
>  			format->min_tuple_size +=
>  				mp_sizeof_str(field->token.len);

Shouldn't we account multikey indexes in min_tuple_size as well?

>  		}
> @@ -805,6 +810,59 @@ tuple_format1_can_store_format2_tuples(struct tuple_format *format1,
>  	return true;
>  }
>  
> +/**
> + * Grow tuple_field_map allocation left with extent_size
> + * 0 bytes.
> + */
> +static int
> +tuple_field_map_realloc(uint32_t **field_map, uint32_t *field_map_size,
> +			uint32_t extent_size, struct region *region)
> +{
> +	assert(extent_size % sizeof(uint32_t) == 0);
> +	uint32_t new_field_map_size = *field_map_size + extent_size;
> +	uint32_t *new_field_map = region_alloc(region, new_field_map_size);
> +	if (new_field_map == NULL) {
> +		diag_set(OutOfMemory, new_field_map_size, "region_alloc",
> +			 "new_field_map");
> +		return -1;
> +	}
> +	memset(new_field_map, 0, extent_size);
> +	if (*field_map != NULL) {
> +		memcpy((char *)new_field_map + extent_size,
> +		       (char *)*field_map - *field_map_size, *field_map_size);
> +	}
> +	*field_map = (uint32_t *)((char *)new_field_map + new_field_map_size);
> +	*field_map_size = new_field_map_size;
> +	return 0;
> +}
> +
> +/**
> + * Retrieve tuple field map extent by root_offset_slot, reallocate
> + * memory if required.
> + */
> +struct field_map_ext *
> +tuple_field_map_ext_retrieve(uint32_t **field_map, uint32_t *field_map_size,
> +			     int32_t root_offset_slot, uint32_t extent_items,
> +			     struct region *region)
> +{
> +	uint32_t extent_sz = sizeof(struct field_map_ext) +
> +			     extent_items * sizeof(uint32_t);
> +	uint32_t slot_off = (*field_map)[root_offset_slot];
> +	if (slot_off == 0) {
> +		/* Field map extent was not created yet. */
> +		slot_off = *field_map_size / sizeof(uint32_t);
> +		(*field_map)[root_offset_slot] = slot_off;
> +		if (tuple_field_map_realloc(field_map, field_map_size,
> +					    extent_sz, region) != 0)
> +			return NULL;
> +	}

I don't like that potentially we have to reallocate the field map
several times if multikey indexes are present. What about introducing
a temporary field map storage which would operate with raw pointers
rather than offsets? We would fill this temporary object rather than
a real field map in tuple_field_map_create, without any relocations.
Once we were done, we would call a special helper method that would
turn this object to a real field map.

> +	struct field_map_ext *field_map_ext =
> +		tuple_field_map_ext(*field_map, root_offset_slot);
> +	assert(field_map_ext->size == 0 || field_map_ext->size == extent_items);
> +	field_map_ext->size = extent_items;
> +	return field_map_ext;
> +}
> +
>  /** @sa declaration for details. */
>  int
>  tuple_field_map_create(struct tuple_format *format, const char *tuple,
> @@ -817,14 +875,11 @@ tuple_field_map_create(struct tuple_format *format, const char *tuple,
>  		return 0; /* Nothing to initialize */
>  	}
>  	struct region *region = &fiber()->gc;
> -	*field_map_size = format->field_map_size;
> -	*field_map = region_alloc(region, *field_map_size);
> -	if (*field_map == NULL) {
> -		diag_set(OutOfMemory, *field_map_size, "region_alloc",
> -			 "field_map");
> +	*field_map = NULL;
> +	*field_map_size = 0;
> +	if (tuple_field_map_realloc(field_map, field_map_size,
> +				    format->field_map_size, region) != 0)
>  		return -1;
> -	}
> -	*field_map = (uint32_t *)((char *)*field_map + *field_map_size);
>  
>  	const char *pos = tuple;
>  	int rc = 0;
> @@ -864,11 +919,6 @@ tuple_field_map_create(struct tuple_format *format, const char *tuple,
>  	uint32_t defined_field_count = MIN(field_count, validate ?
>  					   tuple_format_field_count(format) :
>  					   format->index_field_count);
> -	/*
> -	 * Nullify field map to be able to detect by 0,
> -	 * which key fields are absent in tuple_field().
> -	 */
> -	memset((char *)*field_map - *field_map_size, 0, *field_map_size);
>  	/*
>  	 * Prepare mp stack of the size equal to the maximum depth
>  	 * of the indexed field in the format::fields tree
> @@ -885,6 +935,12 @@ tuple_field_map_create(struct tuple_format *format, const char *tuple,
>  	struct mp_stack stack;
>  	mp_stack_create(&stack, format->fields_depth, frames);
>  	mp_stack_push(&stack, MP_ARRAY, defined_field_count);
> +	/**
> +	 * Pointer to the stack entry that represents the multikey
> +	 * index root ARRAY entry.
> +	 */
> +	struct mp_frame *mk_parent_frame = NULL;
> +
>  	struct tuple_field *field;
>  	struct json_token *parent = &format->fields.root;
>  	while (true) {
> @@ -901,6 +957,10 @@ tuple_field_map_create(struct tuple_format *format, const char *tuple,
>  			mp_stack_pop(&stack);
>  			if (mp_stack_is_empty(&stack))
>  				goto finish;
> +			if (json_token_is_multikey(parent)) {
> +				/* Leave multikey index branch. */
> +				mk_parent_frame = NULL;
> +			}
>  			parent = parent->parent;
>  		}
>  		/*
> @@ -950,8 +1010,23 @@ tuple_field_map_create(struct tuple_format *format, const char *tuple,
>  					 field_type_strs[field->type]);
>  				goto error;
>  			}
> -			if (field->offset_slot != TUPLE_OFFSET_SLOT_NIL)
> +			if (field->offset_slot != TUPLE_OFFSET_SLOT_NIL &&
> +			    mk_parent_frame == NULL) {
>  				(*field_map)[field->offset_slot] = pos - tuple;
> +			} else if (field->offset_slot != TUPLE_OFFSET_SLOT_NIL &&
> +				   mk_parent_frame != NULL) {
> +				uint32_t extent_items = mk_parent_frame->count;
> +				struct field_map_ext *field_map_ext =
> +					tuple_field_map_ext_retrieve(field_map,
> +							field_map_size,
> +							field->offset_slot,
> +							extent_items, region);
> +				if (field_map_ext == NULL)
> +					goto error;
> +				int multikey_idx = mk_parent_frame->curr;
> +				field_map_ext->field_map[
> +					-multikey_idx] = pos - tuple;
> +			}

This function has grown too big for easy reading. It definitely needs to
be split.

>  			if (required_fields != NULL)
>  				bit_clear(required_fields, field->id);
>  		}
> @@ -968,6 +1043,11 @@ tuple_field_map_create(struct tuple_format *format, const char *tuple,
>  					mp_decode_array(&pos) :
>  					mp_decode_map(&pos);
>  			mp_stack_push(&stack, type, size);
> +			if (json_token_is_multikey(&field->token)) {
> +				/* Track multikey entry frame. */
> +				assert(type == MP_ARRAY);
> +				mk_parent_frame = &frames[stack.used - 1];
> +			}
>  			parent = &field->token;
>  		} else {
>  			mp_next(&pos);
> diff --git a/test/engine/json.test.lua b/test/engine/json.test.lua
> index f9a7180b1..dc6016af9 100644
> --- a/test/engine/json.test.lua
> +++ b/test/engine/json.test.lua
> @@ -198,4 +198,24 @@ s:drop()
>  --
>  s = box.schema.space.create('withdata')
>  idx = s:create_index('idx', {parts = {{3, 'str', path = '[*].fname'}, {3, 'str', path = '[*].sname'}}})
> +s:insert({1, 1, {{fname='James', sname='Bond'}, {fname='Vasya', sname='Pupkin'}}})
> +s:insert({1, 1, {{fname='Ivan', sname='Ivanych'}}})
> +idx:select({'James', 'Bond'})
> +idx:select({'Kirill', 'Shcherbatov'})
> +idx:select({'Ivan', 'Ivanych'})
> +idx:select({'Vasya', 'Pupkin'})
> +idx:select()
> +s:insert({2, 1, {{fname='Vasya', sname='Pupkin'}}})
> +s:insert({2, 1, {{fname='James', sname='Bond'}}})
> +idx:select()
> +idx:delete({'Vasya', 'Pupkin'})
> +s:insert({2, 1, {{fname='Vasya', sname='Pupkin'}}})
> +s:insert({2, 1, {{fname='James', sname='Bond'}}})
> +idx:select()
> +s:drop()
> +
> +s = box.schema.space.create('withdata')
> +pk = s:create_index('pk')
> +idx = s:create_index('idx', {parts = {{3, 'str', path = '[*].fname'}, {3, 'str', path = '[*].extra.sname', is_nullable = true}}})
> +s:insert({1, 1, {{fname='A1', extra={sname='A2'}}, {fname='B1'}, {fname='C1', extra={sname='C2'}}}})
>  s:drop()

Please write many more tests to cover all the following cases:

 - snapshot
 - recovery
 - invalid/incompatible paths
 - unique/non-unique indexes
 - duplicates in multikey parts

I guess, it's worth moving this to a separate test file.

Re: [tarantool-patches] [PATCH v5 0/4] box: introduce hint option for memtx tree index

[Konstantin Osipov]

* Kirill Shcherbatov <kshcherbatov@tarantool.org> [19/03/07 12:46]:
> Reworked memtx tree to use 'tuple hints'.
> Introduced special functions for retrieve tuple hints for a particular key_def.
> Hint is an integer that can be used for tuple comparison optimization:
> if a hint of one tuple is less than a hint of another then the first
> tuple is definitely less than the second; only if hints are equal
> tuple_compare must be called for getting comparison result.

I like the design and will not provide a detailed review while on
vacation. Vova, please review, clean up and push this patch set.


-- 
Konstantin Osipov, Moscow, Russia, +7 903 626 22 32
http://tarantool.io - www.twitter.com/kostja_osipov