[tarantool-patches] [PATCH v1 2/5] box: introduce slot_cache in key_part

[Kirill Shcherbatov <kshcherbatov@tarantool.org>]

Same key_part could be used in different formats multiple
times, so different field->offset_slot would be allocated.
In most scenarios we work with series of tuples of same
format, and (in general) format lookup for field would be
expensive operation for JSON-paths defined in key_part.
New slot_cache field in key_part structure and epoch-based
mechanism to validate it actuality should be effective
approach to improve performance.
New routine tuple_field_by_part use tuple and key_part
to access field that allows to rework and speedup all
scenarios of access tuple data by index.
This also allows to work with JSON-path key_parts later.

Part of #1012.
---
 src/box/key_def.c            |  2 ++
 src/box/key_def.h            |  4 ++++
 src/box/memtx_bitset.c       |  4 ++--
 src/box/memtx_rtree.c        |  2 +-
 src/box/tuple_bloom.c        |  8 ++++----
 src/box/tuple_compare.cc     | 48 +++++++++++++++++---------------------------
 src/box/tuple_extract_key.cc | 13 +++---------
 src/box/tuple_format.c       | 43 +++++++++++++++++++++++++++++++++++++++
 src/box/tuple_format.h       | 15 ++++++++++++++
 src/box/tuple_hash.cc        | 28 ++++++++++++--------------
 src/box/tuple_hash.h         |  5 +++--
 src/box/vy_stmt.h            |  2 +-
 12 files changed, 109 insertions(+), 65 deletions(-)

diff --git a/src/box/key_def.c b/src/box/key_def.c
index ee09dc9..8a4262b 100644
--- a/src/box/key_def.c
+++ b/src/box/key_def.c
@@ -258,6 +258,8 @@ key_def_set_part(struct key_def *def, uint32_t part_no, uint32_t fieldno,
 	def->parts[part_no].type = type;
 	def->parts[part_no].coll = coll;
 	def->parts[part_no].coll_id = coll_id;
+	def->parts[part_no].slot_cache = TUPLE_OFFSET_SLOT_NIL;
+	def->parts[part_no].format_epoch = 0;
 	column_mask_set_fieldno(&def->column_mask, fieldno);
 	/**
 	 * When all parts are set, initialize the tuple
diff --git a/src/box/key_def.h b/src/box/key_def.h
index aecbe03..42c054c 100644
--- a/src/box/key_def.h
+++ b/src/box/key_def.h
@@ -74,6 +74,10 @@ struct key_part {
 	struct coll *coll;
 	/** True if a part can store NULLs. */
 	bool is_nullable;
+	/** Format epoch for slot_cache. */
+	uint64_t format_epoch;
+	/** Cache for corresponding tuple_format slot_offset. */
+	int32_t slot_cache;
 };
 
 struct key_def;
diff --git a/src/box/memtx_bitset.c b/src/box/memtx_bitset.c
index a665f1a..e9b5f6a 100644
--- a/src/box/memtx_bitset.c
+++ b/src/box/memtx_bitset.c
@@ -283,8 +283,8 @@ memtx_bitset_index_replace(struct index *base, struct tuple *old_tuple,
 	}
 
 	if (new_tuple != NULL) {
-		const char *field;
-		field = tuple_field(new_tuple, base->def->key_def->parts[0].fieldno);
+		const char *field =
+			tuple_field_by_part(new_tuple, base->def->key_def, 0);
 		uint32_t key_len;
 		const void *key = make_key(field, &key_len);
 #ifndef OLD_GOOD_BITSET
diff --git a/src/box/memtx_rtree.c b/src/box/memtx_rtree.c
index 0b12cda..fd6334f 100644
--- a/src/box/memtx_rtree.c
+++ b/src/box/memtx_rtree.c
@@ -112,7 +112,7 @@ extract_rectangle(struct rtree_rect *rect, const struct tuple *tuple,
 		  struct index_def *index_def)
 {
 	assert(index_def->key_def->part_count == 1);
-	const char *elems = tuple_field(tuple, index_def->key_def->parts[0].fieldno);
+	const char *elems = tuple_field_by_part(tuple, index_def->key_def, 0);
 	unsigned dimension = index_def->opts.dimension;
 	uint32_t count = mp_decode_array(&elems);
 	return mp_decode_rect(rect, dimension, elems, count, "Field");
diff --git a/src/box/tuple_bloom.c b/src/box/tuple_bloom.c
index ffad151..3de83bc 100644
--- a/src/box/tuple_bloom.c
+++ b/src/box/tuple_bloom.c
@@ -85,8 +85,8 @@ tuple_bloom_builder_add(struct tuple_bloom_builder *builder,
 	uint32_t total_size = 0;
 
 	for (uint32_t i = 0; i < key_def->part_count; i++) {
-		total_size += tuple_hash_key_part(&h, &carry, tuple,
-						  &key_def->parts[i]);
+		total_size +=
+			tuple_hash_key_part(&h, &carry, tuple, key_def, i);
 		if (i < hashed_parts) {
 			/*
 			 * This part is already in the bloom, proceed
@@ -183,8 +183,8 @@ tuple_bloom_maybe_has(const struct tuple_bloom *bloom,
 	uint32_t total_size = 0;
 
 	for (uint32_t i = 0; i < key_def->part_count; i++) {
-		total_size += tuple_hash_key_part(&h, &carry, tuple,
-						  &key_def->parts[i]);
+		total_size +=
+			tuple_hash_key_part(&h, &carry, tuple, key_def, i);
 		uint32_t hash = PMurHash32_Result(h, carry, total_size);
 		if (!bloom_maybe_has(&bloom->parts[i], hash))
 			return false;
diff --git a/src/box/tuple_compare.cc b/src/box/tuple_compare.cc
index e53afba..6d34c60 100644
--- a/src/box/tuple_compare.cc
+++ b/src/box/tuple_compare.cc
@@ -432,9 +432,8 @@ tuple_common_key_parts(const struct tuple *tuple_a,
 {
 	uint32_t i;
 	for (i = 0; i < key_def->part_count; i++) {
-		const struct key_part *part = &key_def->parts[i];
-		const char *field_a = tuple_field(tuple_a, part->fieldno);
-		const char *field_b = tuple_field(tuple_b, part->fieldno);
+		const char *field_a = tuple_field_by_part(tuple_a, key_def, i);
+		const char *field_b = tuple_field_by_part(tuple_b, key_def, i);
 		enum mp_type a_type = field_a != NULL ?
 				      mp_typeof(*field_a) : MP_NIL;
 		enum mp_type b_type = field_b != NULL ?
@@ -442,8 +441,9 @@ tuple_common_key_parts(const struct tuple *tuple_a,
 		if (a_type == MP_NIL && b_type == MP_NIL)
 			continue;
 		if (a_type == MP_NIL || b_type == MP_NIL ||
-		    tuple_compare_field_with_hint(field_a, a_type,
-				field_b, b_type, part->type, part->coll) != 0)
+		    tuple_compare_field_with_hint(field_a, a_type, field_b,
+						  b_type, key_def->parts[i].type,
+						  key_def->parts[i].coll) != 0)
 			break;
 	}
 	return i;
@@ -457,7 +457,7 @@ tuple_compare_slowpath(const struct tuple *tuple_a, const struct tuple *tuple_b,
 	assert(!has_optional_parts || is_nullable);
 	assert(is_nullable == key_def->is_nullable);
 	assert(has_optional_parts == key_def->has_optional_parts);
-	const struct key_part *part = key_def->parts;
+	struct key_part *part = (struct key_part *)key_def->parts;
 	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) {
@@ -484,10 +484,6 @@ tuple_compare_slowpath(const struct tuple *tuple_a, const struct tuple *tuple_b,
 	}
 
 	bool was_null_met = false;
-	const struct tuple_format *format_a = tuple_format(tuple_a);
-	const struct tuple_format *format_b = tuple_format(tuple_b);
-	const uint32_t *field_map_a = tuple_field_map(tuple_a);
-	const uint32_t *field_map_b = tuple_field_map(tuple_b);
 	const struct key_part *end;
 	const char *field_a, *field_b;
 	enum mp_type a_type, b_type;
@@ -497,11 +493,10 @@ tuple_compare_slowpath(const struct tuple *tuple_a, const struct tuple *tuple_b,
 	else
 		end = part + key_def->part_count;
 
-	for (; part < end; part++) {
-		field_a = tuple_field_raw(format_a, tuple_a_raw, field_map_a,
-					  part->fieldno);
-		field_b = tuple_field_raw(format_b, tuple_b_raw, field_map_b,
-					  part->fieldno);
+	uint32_t i = 0;
+	for (; part < end; part++, i++) {
+		field_a = tuple_field_by_part(tuple_a, key_def, i);
+		field_b = tuple_field_by_part(tuple_b, key_def, i);
 		assert(has_optional_parts ||
 		       (field_a != NULL && field_b != NULL));
 		if (! is_nullable) {
@@ -547,11 +542,9 @@ tuple_compare_slowpath(const struct tuple *tuple_a, const struct tuple *tuple_b,
 	 * extended parts only.
 	 */
 	end = key_def->parts + key_def->part_count;
-	for (; part < end; ++part) {
-		field_a = tuple_field_raw(format_a, tuple_a_raw, field_map_a,
-					  part->fieldno);
-		field_b = tuple_field_raw(format_b, tuple_b_raw, field_map_b,
-					  part->fieldno);
+	for (; part < end; ++part, ++i) {
+		field_a = tuple_field_by_part(tuple_a, key_def, i);
+		field_b = tuple_field_by_part(tuple_b, key_def, i);
 		/*
 		 * Extended parts are primary, and they can not
 		 * be absent or be NULLs.
@@ -576,15 +569,11 @@ tuple_compare_with_key_slowpath(const struct tuple *tuple, const char *key,
 	assert(has_optional_parts == key_def->has_optional_parts);
 	assert(key != NULL || part_count == 0);
 	assert(part_count <= key_def->part_count);
-	const struct key_part *part = key_def->parts;
-	const struct tuple_format *format = tuple_format(tuple);
-	const char *tuple_raw = tuple_data(tuple);
-	const uint32_t *field_map = tuple_field_map(tuple);
+	struct key_part *part = (struct key_part *)key_def->parts;
 	enum mp_type a_type, b_type;
+	uint32_t i = 0;
 	if (likely(part_count == 1)) {
-		const char *field;
-		field = tuple_field_raw(format, tuple_raw, field_map,
-					part->fieldno);
+		const char *field = tuple_field_by_part(tuple, key_def, i);
 		if (! is_nullable) {
 			return tuple_compare_field(field, key, part->type,
 						   part->coll);
@@ -607,10 +596,9 @@ tuple_compare_with_key_slowpath(const struct tuple *tuple, const char *key,
 
 	const struct key_part *end = part + part_count;
 	int rc;
-	for (; part < end; ++part, mp_next(&key)) {
+	for (; part < end; ++i, ++part, mp_next(&key)) {
 		const char *field;
-		field = tuple_field_raw(format, tuple_raw, field_map,
-					part->fieldno);
+		field = tuple_field_by_part(tuple, key_def, i);
 		if (! is_nullable) {
 			rc = tuple_compare_field(field, key, part->type,
 						 part->coll);
diff --git a/src/box/tuple_extract_key.cc b/src/box/tuple_extract_key.cc
index 880abb6..bbd87f5 100644
--- a/src/box/tuple_extract_key.cc
+++ b/src/box/tuple_extract_key.cc
@@ -101,18 +101,13 @@ tuple_extract_key_slowpath(const struct tuple *tuple,
 	assert(contains_sequential_parts ==
 	       key_def_contains_sequential_parts(key_def));
 	assert(mp_sizeof_nil() == 1);
-	const char *data = tuple_data(tuple);
 	uint32_t part_count = key_def->part_count;
 	uint32_t bsize = mp_sizeof_array(part_count);
-	const struct tuple_format *format = tuple_format(tuple);
-	const uint32_t *field_map = tuple_field_map(tuple);
-	const char *tuple_end = data + tuple->bsize;
+	const char *tuple_end = tuple_data(tuple) + tuple->bsize;
 
 	/* Calculate the key size. */
 	for (uint32_t i = 0; i < part_count; ++i) {
-		const char *field =
-			tuple_field_raw(format, data, field_map,
-					key_def->parts[i].fieldno);
+		const char *field = tuple_field_by_part(tuple, key_def, i);
 		if (has_optional_parts && field == NULL) {
 			bsize += mp_sizeof_nil();
 			continue;
@@ -152,9 +147,7 @@ tuple_extract_key_slowpath(const struct tuple *tuple,
 	}
 	char *key_buf = mp_encode_array(key, part_count);
 	for (uint32_t i = 0; i < part_count; ++i) {
-		const char *field =
-			tuple_field_raw(format, data, field_map,
-					key_def->parts[i].fieldno);
+		const char *field = tuple_field_by_part(tuple, key_def, i);
 		if (has_optional_parts && field == NULL) {
 			key_buf = mp_encode_nil(key_buf);
 			continue;
diff --git a/src/box/tuple_format.c b/src/box/tuple_format.c
index 2e19d2e..40cd48a 100644
--- a/src/box/tuple_format.c
+++ b/src/box/tuple_format.c
@@ -29,12 +29,15 @@
  * SUCH DAMAGE.
  */
 #include "json/path.h"
+#include "tuple.h"
 #include "tuple_format.h"
 
 /** Global table of tuple formats */
 struct tuple_format **tuple_formats;
 static intptr_t recycled_format_ids = FORMAT_ID_NIL;
 
+static uint64_t format_epoch = 1;
+
 static uint32_t formats_size = 0, formats_capacity = 0;
 
 static const struct tuple_field tuple_field_default = {
@@ -69,6 +72,7 @@ tuple_format_create(struct tuple_format *format, struct key_def * const *keys,
 		format->fields[i] = tuple_field_default;
 
 	int current_slot = 0;
+	bool format_epoch_changed = false;
 
 	/* extract field type info */
 	for (uint16_t key_no = 0; key_no < key_count; ++key_no) {
@@ -135,6 +139,8 @@ tuple_format_create(struct tuple_format *format, struct key_def * const *keys,
 			    is_sequential == false && part->fieldno > 0) {
 
 				field->offset_slot = --current_slot;
+				if (part->slot_cache != field->offset_slot)
+					format_epoch_changed = true;
 			}
 		}
 	}
@@ -148,6 +154,8 @@ tuple_format_create(struct tuple_format *format, struct key_def * const *keys,
 		return -1;
 	}
 	format->field_map_size = field_map_size;
+	if (format_epoch_changed)
+		format->epoch = ++format_epoch;
 	return 0;
 }
 
@@ -233,6 +241,7 @@ tuple_format_alloc(struct key_def * const *keys, uint16_t key_count,
 		format->dict = dict;
 		tuple_dictionary_ref(dict);
 	}
+	format->epoch = format_epoch;
 	format->refs = 0;
 	format->id = FORMAT_ID_NIL;
 	format->field_count = field_count;
@@ -542,6 +551,40 @@ tuple_field_go_to_key(const char **field, const char *key, int len)
 	return -1;
 }
 
+const char *
+tuple_field_by_part(const struct tuple *tuple, const struct key_def *def,
+		    uint32_t idx)
+{
+	struct key_part *part = (struct key_part *)&def->parts[idx];
+	const struct tuple_format *format = tuple_format(tuple);
+	const char *data = tuple_data(tuple);
+	const uint32_t *field_map = tuple_field_map(tuple);
+
+	uint32_t field_no = part->fieldno;
+	if (likely(field_no < format->index_field_count)) {
+		assert(format->epoch > 0);
+		int32_t offset_slot = TUPLE_OFFSET_SLOT_NIL;
+		if (part->format_epoch != format->epoch) {
+			offset_slot = format->fields[field_no].offset_slot;
+			if (format->epoch > part->format_epoch) {
+				part->slot_cache = offset_slot;
+				part->format_epoch = format->epoch;
+			}
+		}
+		if (offset_slot != TUPLE_OFFSET_SLOT_NIL) {
+			return field_map[offset_slot] != 0 ?
+			       data + field_map[offset_slot] : NULL;
+		}
+	}
+	ERROR_INJECT(ERRINJ_TUPLE_FIELD, return NULL);
+	uint32_t field_count = mp_decode_array(&data);
+	if (unlikely(field_no >= field_count))
+		return NULL;
+	for (uint32_t k = 0; k < field_no; k++)
+		mp_next(&data);
+	return data;
+}
+
 int
 tuple_field_raw_by_path(struct tuple_format *format, const char *tuple,
                         const uint32_t *field_map, const char *path,
diff --git a/src/box/tuple_format.h b/src/box/tuple_format.h
index c7dc48f..3cb1284 100644
--- a/src/box/tuple_format.h
+++ b/src/box/tuple_format.h
@@ -115,6 +115,8 @@ struct tuple_field {
  * Tuple format describes how tuple is stored and information about its fields
  */
 struct tuple_format {
+	/** Tuple format epoch. */
+	uint64_t epoch;
 	/** Virtual function table */
 	struct tuple_format_vtab vtab;
 	/** Pointer to engine-specific data. */
@@ -324,6 +326,19 @@ tuple_init_field_map(const struct tuple_format *format, uint32_t *field_map,
 		     const char *tuple);
 
 /**
+ * Get a field refereed by multipart index @def part @idx in
+ * @tuple.
+ *
+ * @param tuple object containing data to lookup.
+ * @param key_def multipart index to use.
+ * @param idx index of part to use.
+ * @retval field data if field exists or NULL
+ */
+const char *
+tuple_field_by_part(const struct tuple *tuple, const struct key_def *def,
+		    uint32_t idx);
+
+/**
  * Get a field at the specific position in this MessagePack array.
  * Returns a pointer to MessagePack data.
  * @param format tuple format
diff --git a/src/box/tuple_hash.cc b/src/box/tuple_hash.cc
index dee9be3..7e4f3e6 100644
--- a/src/box/tuple_hash.cc
+++ b/src/box/tuple_hash.cc
@@ -157,7 +157,7 @@ struct TupleHash
 		uint32_t h = HASH_SEED;
 		uint32_t carry = 0;
 		uint32_t total_size = 0;
-		const char *field = tuple_field(tuple, key_def->parts->fieldno);
+		const char *field = tuple_field_by_part(tuple, key_def, 0);
 		TupleFieldHash<TYPE, MORE_TYPES...>::
 			hash(&field, &h, &carry, &total_size);
 		return PMurHash32_Result(h, carry, total_size);
@@ -169,7 +169,7 @@ struct TupleHash<FIELD_TYPE_UNSIGNED> {
 	static uint32_t	hash(const struct tuple *tuple,
 			     const struct key_def *key_def)
 	{
-		const char *field = tuple_field(tuple, key_def->parts->fieldno);
+		const char *field = tuple_field_by_part(tuple, key_def, 0);
 		uint64_t val = mp_decode_uint(&field);
 		if (likely(val <= UINT32_MAX))
 			return val;
@@ -310,12 +310,12 @@ tuple_hash_null(uint32_t *ph1, uint32_t *pcarry)
 uint32_t
 tuple_hash_key_part(uint32_t *ph1, uint32_t *pcarry,
 		    const struct tuple *tuple,
-		    const struct key_part *part)
+		    const struct key_def *key_def, uint32_t i)
 {
-	const char *field = tuple_field(tuple, part->fieldno);
+	const char *field = tuple_field_by_part(tuple, key_def, i);
 	if (field == NULL)
 		return tuple_hash_null(ph1, pcarry);
-	return tuple_hash_field(ph1, pcarry, &field, part->coll);
+	return tuple_hash_field(ph1, pcarry, &field, key_def->parts[i].coll);
 }
 
 template <bool has_optional_parts>
@@ -326,31 +326,29 @@ tuple_hash_slowpath(const struct tuple *tuple, const struct key_def *key_def)
 	uint32_t h = HASH_SEED;
 	uint32_t carry = 0;
 	uint32_t total_size = 0;
-	uint32_t prev_fieldno = key_def->parts[0].fieldno;
-	const char *field = tuple_field(tuple, key_def->parts[0].fieldno);
+	const struct key_part *part = &key_def->parts[0];
+	uint32_t prev_fieldno = part->fieldno;
+	const char *field = tuple_field_by_part(tuple, key_def, 0);
 	const char *end = (char *)tuple + tuple_size(tuple);
 	if (has_optional_parts && field == NULL) {
 		total_size += tuple_hash_null(&h, &carry);
 	} else {
-		total_size += tuple_hash_field(&h, &carry, &field,
-					       key_def->parts[0].coll);
+		total_size += tuple_hash_field(&h, &carry, &field, part->coll);
 	}
 	for (uint32_t part_id = 1; part_id < key_def->part_count; part_id++) {
 		/* If parts of key_def are not sequential we need to call
 		 * tuple_field. Otherwise, tuple is hashed sequentially without
 		 * need of tuple_field
 		 */
-		if (prev_fieldno + 1 != key_def->parts[part_id].fieldno) {
-			field = tuple_field(tuple, key_def->parts[part_id].fieldno);
-		}
+		if (prev_fieldno + 1 != part->fieldno)
+			field = tuple_field_by_part(tuple, key_def, part_id);
 		if (has_optional_parts && (field == NULL || field >= end)) {
 			total_size += tuple_hash_null(&h, &carry);
 		} else {
 			total_size +=
-				tuple_hash_field(&h, &carry, &field,
-						 key_def->parts[part_id].coll);
+				tuple_hash_field(&h, &carry, &field, part->coll);
 		}
-		prev_fieldno = key_def->parts[part_id].fieldno;
+		prev_fieldno = part->fieldno;
 	}
 
 	return PMurHash32_Result(h, carry, total_size);
diff --git a/src/box/tuple_hash.h b/src/box/tuple_hash.h
index aab8f54..90f80a8 100644
--- a/src/box/tuple_hash.h
+++ b/src/box/tuple_hash.h
@@ -64,7 +64,8 @@ tuple_hash_field(uint32_t *ph1, uint32_t *pcarry, const char **field,
  * @param ph1 - pointer to running hash
  * @param pcarry - pointer to carry
  * @param tuple - tuple to hash
- * @param part - key part
+ * @param key_def - key definition
+ * @param i - index of part to hash
  * @return size of processed data
  *
  * This function updates @ph1 and @pcarry.
@@ -72,7 +73,7 @@ tuple_hash_field(uint32_t *ph1, uint32_t *pcarry, const char **field,
 uint32_t
 tuple_hash_key_part(uint32_t *ph1, uint32_t *pcarry,
 		    const struct tuple *tuple,
-		    const struct key_part *part);
+		    const struct key_def *key_def, uint32_t i);
 
 /**
  * Calculates a common hash value for a tuple
diff --git a/src/box/vy_stmt.h b/src/box/vy_stmt.h
index e53f98c..0b485ad 100644
--- a/src/box/vy_stmt.h
+++ b/src/box/vy_stmt.h
@@ -665,7 +665,7 @@ static inline bool
 vy_tuple_key_contains_null(const struct tuple *tuple, const struct key_def *def)
 {
 	for (uint32_t i = 0; i < def->part_count; ++i) {
-		const char *field = tuple_field(tuple, def->parts[i].fieldno);
+		const char *field = tuple_field_by_part(tuple, def, i);
 		if (field == NULL || mp_typeof(*field) == MP_NIL)
 			return true;
 	}
-- 
2.7.4