[PATCH v9 5/6] box: introduce offset_slot cache in key_part

[Kirill Shcherbatov <kshcherbatov@tarantool.org>]

tuple_field_by_part looks up the tuple_field corresponding to the
given key part in tuple_format in order to quickly retrieve the offset
of indexed data from the tuple field map. For regular indexes this
operation is blazing fast, however of JSON indexes it is not as we
have to parse the path to data and then do multiple lookups in a JSON
tree. Since tuple_field_by_part is used by comparators, we should
strive to make this routine as fast as possible for all kinds of
indexes.

This patch introduces an optimization that is supposed to make
tuple_field_by_part for JSON indexes as fast as it is for regular
indexes in most cases. We do that by caching the offset slot right in
key_part. There's a catch here however - we create a new format
whenever an index is dropped or created and we don't reindex old
tuples. As a result, there may be several generations of tuples in the
same space, all using different formats while there's the only key_def
used for comparison.

To overcome this problem, we introduce the notion of tuple_format
epoch. This is a counter incremented each time a new format is
created. We store it in tuple_format and key_def, and we only use
the offset slot cached in a key_def if it's epoch coincides with the
epoch of the tuple format. If they don't, we look up a tuple_field as
before, and then update the cached value provided the epoch of the
tuple format.

Part of #1012
---
 src/box/key_def.c      | 15 ++++++++++-----
 src/box/key_def.h      | 14 ++++++++++++++
 src/box/tuple.h        |  2 +-
 src/box/tuple_format.c |  6 +++++-
 src/box/tuple_format.h | 41 +++++++++++++++++++++++++++++++++++------
 5 files changed, 65 insertions(+), 13 deletions(-)

diff --git a/src/box/key_def.c b/src/box/key_def.c
index 1b00945ca..9411ade39 100644
--- a/src/box/key_def.c
+++ b/src/box/key_def.c
@@ -142,7 +142,8 @@ key_def_set_part(struct key_def *def, uint32_t part_no, uint32_t fieldno,
 		 enum field_type type, enum on_conflict_action nullable_action,
 		 struct coll *coll, uint32_t coll_id,
 		 enum sort_order sort_order, const char *path,
-		 uint32_t path_len, char **path_pool)
+		 uint32_t path_len, char **path_pool, int32_t offset_slot,
+		 uint64_t format_epoch)
 {
 	assert(part_no < def->part_count);
 	assert(type < field_type_MAX);
@@ -154,6 +155,8 @@ key_def_set_part(struct key_def *def, uint32_t part_no, uint32_t fieldno,
 	def->parts[part_no].coll = coll;
 	def->parts[part_no].coll_id = coll_id;
 	def->parts[part_no].sort_order = sort_order;
+	def->parts[part_no].offset_slot_cache = offset_slot;
+	def->parts[part_no].format_epoch = format_epoch;
 	if (path != NULL) {
 		assert(path_pool != NULL);
 		def->parts[part_no].path = *path_pool;
@@ -202,7 +205,7 @@ key_def_new(const struct key_part_def *parts, uint32_t part_count)
 		key_def_set_part(def, i, part->fieldno, part->type,
 				 part->nullable_action, coll, part->coll_id,
 				 part->sort_order, part->path, path_len,
-				 &path_pool);
+				 &path_pool, TUPLE_OFFSET_SLOT_NIL, 0);
 	}
 	assert(path_pool == (char *)def + sz);
 	key_def_set_cmp(def);
@@ -256,7 +259,7 @@ box_key_def_new(uint32_t *fields, uint32_t *types, uint32_t part_count)
 				 (enum field_type)types[item],
 				 ON_CONFLICT_ACTION_DEFAULT,
 				 NULL, COLL_NONE, SORT_ORDER_ASC, NULL, 0,
-				 NULL);
+				 NULL, TUPLE_OFFSET_SLOT_NIL, 0);
 	}
 	key_def_set_cmp(key_def);
 	return key_def;
@@ -666,7 +669,8 @@ key_def_merge(const struct key_def *first, const struct key_def *second)
 		key_def_set_part(new_def, pos++, part->fieldno, part->type,
 				 part->nullable_action, part->coll,
 				 part->coll_id, part->sort_order, part->path,
-				 part->path_len, &path_pool);
+				 part->path_len, &path_pool,
+				 part->offset_slot_cache, part->format_epoch);
 	}
 
 	/* Set-append second key def's part to the new key def. */
@@ -678,7 +682,8 @@ key_def_merge(const struct key_def *first, const struct key_def *second)
 		key_def_set_part(new_def, pos++, part->fieldno, part->type,
 				 part->nullable_action, part->coll,
 				 part->coll_id, part->sort_order, part->path,
-				 part->path_len, &path_pool);
+				 part->path_len, &path_pool,
+				 part->offset_slot_cache, part->format_epoch);
 	}
 	assert(path_pool == (char *)new_def + sz);
 	key_def_set_cmp(new_def);
diff --git a/src/box/key_def.h b/src/box/key_def.h
index 678d1f070..85bed92bb 100644
--- a/src/box/key_def.h
+++ b/src/box/key_def.h
@@ -97,6 +97,20 @@ struct key_part {
 	char *path;
 	/** The length of JSON path. */
 	uint32_t path_len;
+	/**
+	 * Epoch of the tuple format the offset slot cached in
+	 * this part is valid for, see tuple_format::epoch.
+	 */
+	uint64_t format_epoch;
+	/**
+	 * Cached value of the offset slot corresponding to
+	 * the indexed field (tuple_field::offset_slot).
+	 * Valid only if key_part::format_epoch equals the epoch
+	 * of the tuple format. This value is updated in
+	 * tuple_field_by_part_raw to always store the
+	 * offset corresponding to the last used tuple format.
+	 */
+	int32_t offset_slot_cache;
 };
 
 struct key_def;
diff --git a/src/box/tuple.h b/src/box/tuple.h
index c3cd689fd..d2da26713 100644
--- a/src/box/tuple.h
+++ b/src/box/tuple.h
@@ -528,7 +528,7 @@ tuple_field_by_path(const struct tuple *tuple, uint32_t fieldno,
 {
 	return tuple_field_raw_by_path(tuple_format(tuple), tuple_data(tuple),
 				       tuple_field_map(tuple), fieldno,
-				       path, path_len);
+				       path, path_len, NULL);
 }
 
 /**
diff --git a/src/box/tuple_format.c b/src/box/tuple_format.c
index d9c408495..fc152cbbc 100644
--- a/src/box/tuple_format.c
+++ b/src/box/tuple_format.c
@@ -41,6 +41,7 @@ struct tuple_format **tuple_formats;
 static intptr_t recycled_format_ids = FORMAT_ID_NIL;
 
 static uint32_t formats_size = 0, formats_capacity = 0;
+static uint64_t formats_epoch = 0;
 
 /**
  * Find in format1::fields the field by format2_field's JSON path.
@@ -623,6 +624,7 @@ tuple_format_alloc(struct key_def * const *keys, uint16_t key_count,
 	format->index_field_count = index_field_count;
 	format->exact_field_count = 0;
 	format->min_field_count = 0;
+	format->epoch = 0;
 	return format;
 error:
 	tuple_format_destroy_fields(format);
@@ -672,6 +674,7 @@ tuple_format_reuse(struct tuple_format **p_format)
 		tuple_format_destroy(format);
 		free(format);
 		*p_format = *entry;
+		(*p_format)->epoch = ++formats_epoch;
 		return true;
 	}
 	return false;
@@ -740,6 +743,7 @@ tuple_format_new(struct tuple_format_vtab *vtab, void *engine,
 		goto err;
 	if (tuple_format_reuse(&format))
 		return format;
+	format->epoch = ++formats_epoch;
 	if (tuple_format_register(format) < 0)
 		goto err;
 	if (tuple_format_add_to_hash(format) < 0) {
@@ -1205,5 +1209,5 @@ 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);
+				       path_len - lexer.offset, NULL);
 }
diff --git a/src/box/tuple_format.h b/src/box/tuple_format.h
index d4b53195b..aedd3e915 100644
--- a/src/box/tuple_format.h
+++ b/src/box/tuple_format.h
@@ -137,6 +137,12 @@ tuple_field_is_nullable(struct tuple_field *tuple_field)
  * Tuple format describes how tuple is stored and information about its fields
  */
 struct tuple_format {
+	/**
+	 * Counter that grows incrementally on space rebuild
+	 * used for caching offset slot in key_part, for more
+	 * details see key_part::offset_slot_cache.
+	 */
+	uint64_t epoch;
 	/** Virtual function table */
 	struct tuple_format_vtab vtab;
 	/** Pointer to engine-specific data. */
@@ -421,26 +427,43 @@ tuple_field_go_to_path(const char **data, const char *path, uint32_t path_len);
  * @param field_map Tuple field map.
  * @param path Relative JSON path to field.
  * @param path_len Length of @a path.
+ * @param offset_slot_hint The pointer to a variable that contains
+ *                         an offset slot. May be NULL.
+ *                         If specified AND value by pointer is
+ *                         not TUPLE_OFFSET_SLOT_NIL is used to
+ *                         access data in a single operation.
+ *                         Else it is initialized with offset_slot
+ *                         of format field by path.
  */
 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)
+			const char *path, uint32_t path_len,
+			int32_t *offset_slot_hint)
 {
+	int32_t offset_slot;
+	if (offset_slot_hint != NULL &&
+	    *offset_slot_hint != TUPLE_OFFSET_SLOT_NIL) {
+		offset_slot = *offset_slot_hint;
+		goto offset_slot_access;
+	}
 	if (likely(fieldno < format->index_field_count)) {
+		struct tuple_field *field;
 		if (path == NULL && fieldno == 0) {
 			mp_decode_array(&tuple);
 			return tuple;
 		}
-		struct tuple_field *field =
-			tuple_format_field_by_path(format, fieldno, path,
+		field = tuple_format_field_by_path(format, fieldno, path,
 						   path_len);
 		assert(field != NULL || path != NULL);
 		if (path != NULL && field == NULL)
 			goto parse;
-		int32_t offset_slot = field->offset_slot;
+		offset_slot = field->offset_slot;
 		if (offset_slot == TUPLE_OFFSET_SLOT_NIL)
 			goto parse;
+		if (offset_slot_hint != NULL)
+			*offset_slot_hint = offset_slot;
+offset_slot_access:
 		/* Indexed field */
 		if (field_map[offset_slot] == 0)
 			return NULL;
@@ -478,7 +501,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, 0, NULL);
 }
 
 /**
@@ -513,8 +536,14 @@ static inline const char *
 tuple_field_by_part_raw(struct tuple_format *format, const char *data,
 			const uint32_t *field_map, struct key_part *part)
 {
+	if (unlikely(part->format_epoch != format->epoch)) {
+		assert(format->epoch != 0);
+		part->format_epoch = format->epoch;
+		part->offset_slot_cache = TUPLE_OFFSET_SLOT_NIL;
+	}
 	return tuple_field_raw_by_path(format, data, field_map, part->fieldno,
-				       part->path, part->path_len);
+				       part->path, part->path_len,
+				       &part->offset_slot_cache);
 }
 
 /**
-- 
2.20.1