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

[Kirill Shcherbatov <kshcherbatov@tarantool.org>]

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