[PATCH 06/13] vinyl: store tuple comparison hints in page index

[Vladimir Davydov <vdavydov.dev@gmail.com>]

This patch incorporates tuple comparison hints into the run iterator
implementation. Now, every page in a page index stores not only the min
key, but also a comparison hint corresponding to the key. We also store
comparison hints for vy_slice->begin and ->end. This should speed up
page index lookups and hence the overall run iterator performance.

It isn't strictly necessary to incorporate hints deep down the run
iterator implementation, since runs can only store keys. However,
we will need to look up a statement in a run by a hinted tuple to
support multikey indexes. Storing hints in runs should make the code
look more consistent then.
---
 src/box/vinyl.c             |   8 +-
 src/box/vy_lsm.c            |  16 ++--
 src/box/vy_run.c            | 207 +++++++++++++++++++++++++++++---------------
 src/box/vy_run.h            |  23 +++--
 src/box/vy_scheduler.c      |   6 +-
 src/box/vy_stmt.h           |  11 ++-
 test/unit/vy_point_lookup.c |   6 +-
 test/vinyl/stat.result      |  22 ++---
 8 files changed, 197 insertions(+), 102 deletions(-)

diff --git a/src/box/vinyl.c b/src/box/vinyl.c
index 77bacd77..80b6aecd 100644
--- a/src/box/vinyl.c
+++ b/src/box/vinyl.c
@@ -2955,11 +2955,13 @@ vy_prepare_send_slice(struct vy_join_ctx *ctx,
 	int rc = -1;
 	struct vy_run *run = NULL;
 	struct tuple *begin = NULL, *end = NULL;
+	hint_t begin_hint = HINT_NONE, end_hint = HINT_NONE;
 
 	run = vy_run_new(&ctx->env->run_env, slice_info->run->id);
 	if (run == NULL)
 		goto out;
-	if (vy_run_recover(run, ctx->env->path, ctx->space_id, 0) != 0)
+	if (vy_run_recover(run, ctx->env->path, ctx->space_id, 0,
+			   ctx->key_def) != 0)
 		goto out;
 
 	if (slice_info->begin != NULL) {
@@ -2967,16 +2969,18 @@ vy_prepare_send_slice(struct vy_join_ctx *ctx,
 					    slice_info->begin);
 		if (begin == NULL)
 			goto out;
+		begin_hint = vy_stmt_hint(begin, ctx->key_def);
 	}
 	if (slice_info->end != NULL) {
 		end = vy_key_from_msgpack(ctx->env->lsm_env.key_format,
 					  slice_info->end);
 		if (end == NULL)
 			goto out;
+		end_hint = vy_stmt_hint(end, ctx->key_def);
 	}
 
 	struct vy_slice *slice = vy_slice_new(slice_info->id, run,
-					      begin, end, ctx->key_def);
+			begin, begin_hint, end, end_hint, ctx->key_def);
 	if (slice == NULL)
 		goto out;
 
diff --git a/src/box/vy_lsm.c b/src/box/vy_lsm.c
index 44973a3a..52fd429d 100644
--- a/src/box/vy_lsm.c
+++ b/src/box/vy_lsm.c
@@ -365,8 +365,8 @@ vy_lsm_recover_run(struct vy_lsm *lsm, struct vy_run_recovery_info *run_info,
 
 	run->dump_lsn = run_info->dump_lsn;
 	run->dump_count = run_info->dump_count;
-	if (vy_run_recover(run, lsm->env->path,
-			   lsm->space_id, lsm->index_id) != 0 &&
+	if (vy_run_recover(run, lsm->env->path, lsm->space_id,
+			   lsm->index_id, lsm->cmp_def) != 0 &&
 	    (!force_recovery ||
 	     vy_run_rebuild_index(run, lsm->env->path,
 				  lsm->space_id, lsm->index_id,
@@ -396,6 +396,7 @@ vy_lsm_recover_slice(struct vy_lsm *lsm, struct vy_range *range,
 		     struct vy_run_env *run_env, bool force_recovery)
 {
 	struct tuple *begin = NULL, *end = NULL;
+	hint_t begin_hint = HINT_NONE, end_hint = HINT_NONE;
 	struct vy_slice *slice = NULL;
 	struct vy_run *run;
 
@@ -404,15 +405,18 @@ vy_lsm_recover_slice(struct vy_lsm *lsm, struct vy_range *range,
 					    slice_info->begin);
 		if (begin == NULL)
 			goto out;
+		begin_hint = vy_stmt_hint(begin, lsm->cmp_def);
 	}
 	if (slice_info->end != NULL) {
 		end = vy_key_from_msgpack(lsm->env->key_format,
 					  slice_info->end);
 		if (end == NULL)
 			goto out;
+		end_hint = vy_stmt_hint(end, lsm->cmp_def);
 	}
 	if (begin != NULL && end != NULL &&
-	    vy_stmt_compare(begin, end, lsm->cmp_def) >= 0) {
+	    vy_stmt_compare_hinted(begin, begin_hint, end, end_hint,
+				   lsm->cmp_def) >= 0) {
 		diag_set(ClientError, ER_INVALID_VYLOG_FILE,
 			 tt_sprintf("begin >= end for slice %lld",
 				    (long long)slice_info->id));
@@ -424,7 +428,8 @@ vy_lsm_recover_slice(struct vy_lsm *lsm, struct vy_range *range,
 	if (run == NULL)
 		goto out;
 
-	slice = vy_slice_new(slice_info->id, run, begin, end, lsm->cmp_def);
+	slice = vy_slice_new(slice_info->id, run, begin, begin_hint,
+			     end, end_hint, lsm->cmp_def);
 	if (slice == NULL)
 		goto out;
 
@@ -1151,7 +1156,8 @@ vy_lsm_split_range(struct vy_lsm *lsm, struct vy_range *range)
 		 */
 		rlist_foreach_entry_reverse(slice, &range->slices, in_range) {
 			if (vy_slice_cut(slice, vy_log_next_id(), part->begin,
-					 part->end, lsm->cmp_def,
+					 part->begin_hint, part->end,
+					 part->end_hint, lsm->cmp_def,
 					 &new_slice) != 0)
 				goto fail;
 			if (new_slice != NULL)
diff --git a/src/box/vy_run.c b/src/box/vy_run.c
index 818d0cf3..9608e207 100644
--- a/src/box/vy_run.c
+++ b/src/box/vy_run.c
@@ -201,13 +201,17 @@ vy_run_env_enable_coio(struct vy_run_env *env)
  */
 static int
 vy_page_info_create(struct vy_page_info *page_info, uint64_t offset,
-		    const char *min_key)
+		    const char *min_key, struct key_def *cmp_def)
 {
 	memset(page_info, 0, sizeof(*page_info));
 	page_info->offset = offset;
 	page_info->unpacked_size = 0;
 	page_info->min_key = vy_key_dup(min_key);
-	return page_info->min_key == NULL ? -1 : 0;
+	if (page_info->min_key == NULL)
+		return -1;
+	uint32_t part_count = mp_decode_array(&min_key);
+	page_info->hint = key_hint(min_key, part_count, cmp_def);
+	return 0;
 }
 
 /**
@@ -288,18 +292,19 @@ vy_run_bloom_size(struct vy_run *run)
  *  must be started from the beginning of the next page.
  *
  * @param run - run
- * @param key - key to find
- * @param key_def - key_def for comparison
  * @param itype - iterator type (see above)
+ * @param key - key to find
+ * @param hint - comparison hint of the key
+ * @param cmp_def - key_def for comparison
  * @param equal_key: *equal_key is set to true if there is a page
  *  with min_key equal to the given key.
  * @return offset of the page in page index OR run->info.page_count if
  *  there no pages fulfilling the conditions.
  */
 static uint32_t
-vy_page_index_find_page(struct vy_run *run, const struct tuple *key,
-			struct key_def *cmp_def, enum iterator_type itype,
-			bool *equal_key)
+vy_page_index_find_page(struct vy_run *run, enum iterator_type itype,
+			const struct tuple *key, hint_t hint,
+			struct key_def *cmp_def, bool *equal_key)
 {
 	if (itype == ITER_EQ)
 		itype = ITER_GE; /* One day it'll become obsolete */
@@ -338,8 +343,8 @@ vy_page_index_find_page(struct vy_run *run, const struct tuple *key,
 	do {
 		int32_t mid = range[0] + (range[1] - range[0]) / 2;
 		struct vy_page_info *info = vy_run_page_info(run, mid);
-		int cmp = vy_stmt_compare_with_raw_key(key, info->min_key,
-						       cmp_def);
+		int cmp = vy_stmt_compare_with_raw_key_hinted(key, hint,
+					info->min_key, info->hint, cmp_def);
 		if (is_lower_bound)
 			range[cmp <= 0] = mid;
 		else
@@ -362,7 +367,8 @@ vy_page_index_find_page(struct vy_run *run, const struct tuple *key,
 
 struct vy_slice *
 vy_slice_new(int64_t id, struct vy_run *run, struct tuple *begin,
-	     struct tuple *end, struct key_def *cmp_def)
+	     hint_t begin_hint, struct tuple *end, hint_t end_hint,
+	     struct key_def *cmp_def)
 {
 	struct vy_slice *slice = malloc(sizeof(*slice));
 	if (slice == NULL) {
@@ -379,9 +385,11 @@ vy_slice_new(int64_t id, struct vy_run *run, struct tuple *begin,
 	if (begin != NULL)
 		tuple_ref(begin);
 	slice->begin = begin;
+	slice->begin_hint = begin_hint;
 	if (end != NULL)
 		tuple_ref(end);
 	slice->end = end;
+	slice->end_hint = end_hint;
 	rlist_create(&slice->in_range);
 	fiber_cond_create(&slice->pin_cond);
 	if (run->info.page_count == 0) {
@@ -394,16 +402,18 @@ vy_slice_new(int64_t id, struct vy_run *run, struct tuple *begin,
 		slice->first_page_no = 0;
 	} else {
 		slice->first_page_no =
-			vy_page_index_find_page(run, slice->begin, cmp_def,
-						ITER_GE, &unused);
+			vy_page_index_find_page(run, ITER_GE, slice->begin,
+						slice->begin_hint, cmp_def,
+						&unused);
 		assert(slice->first_page_no < run->info.page_count);
 	}
 	if (slice->end == NULL) {
 		slice->last_page_no = run->info.page_count - 1;
 	} else {
 		slice->last_page_no =
-			vy_page_index_find_page(run, slice->end, cmp_def,
-						ITER_LT, &unused);
+			vy_page_index_find_page(run, ITER_LT, slice->end,
+						slice->end_hint, cmp_def,
+						&unused);
 		if (slice->last_page_no == run->info.page_count) {
 			/* It's an empty slice */
 			slice->first_page_no = 0;
@@ -443,30 +453,35 @@ vy_slice_delete(struct vy_slice *slice)
 
 int
 vy_slice_cut(struct vy_slice *slice, int64_t id, struct tuple *begin,
-	     struct tuple *end, struct key_def *cmp_def,
-	     struct vy_slice **result)
+	     hint_t begin_hint, struct tuple *end, hint_t end_hint,
+	     struct key_def *cmp_def, struct vy_slice **result)
 {
 	*result = NULL;
 
 	if (begin != NULL && slice->end != NULL &&
-	    vy_stmt_compare(begin, slice->end, cmp_def) >= 0)
+	    vy_stmt_compare_hinted(begin, begin_hint, slice->end,
+				   slice->end_hint, cmp_def) >= 0)
 		return 0; /* no intersection: begin >= slice->end */
 
 	if (end != NULL && slice->begin != NULL &&
-	    vy_stmt_compare(end, slice->begin, cmp_def) <= 0)
+	    vy_stmt_compare_hinted(end, end_hint, slice->begin,
+				   slice->begin_hint, cmp_def) <= 0)
 		return 0; /* no intersection: end <= slice->end */
 
 	/* begin = MAX(begin, slice->begin) */
 	if (slice->begin != NULL &&
-	    (begin == NULL || vy_stmt_compare(begin, slice->begin, cmp_def) < 0))
+	    (begin == NULL || vy_stmt_compare_hinted(begin, begin_hint,
+			slice->begin, slice->begin_hint, cmp_def) < 0))
 		begin = slice->begin;
 
 	/* end = MIN(end, slice->end) */
 	if (slice->end != NULL &&
-	    (end == NULL || vy_stmt_compare(end, slice->end, cmp_def) > 0))
+	    (end == NULL || vy_stmt_compare_hinted(end, end_hint,
+			slice->end, slice->end_hint, cmp_def) > 0))
 		end = slice->end;
 
-	*result = vy_slice_new(id, slice->run, begin, end, cmp_def);
+	*result = vy_slice_new(id, slice->run, begin, begin_hint,
+			       end, end_hint, cmp_def);
 	if (*result == NULL)
 		return -1; /* OOM */
 
@@ -478,6 +493,7 @@ vy_slice_cut(struct vy_slice *slice, int64_t id, struct tuple *begin,
  *
  * @param[out] page Page information.
  * @param xrow      Xrow to decode.
+ * @param cmp_def   Definition of keys stored in the page.
  * @param filename  Filename for error reporting.
  *
  * @retval  0 Success.
@@ -485,7 +501,7 @@ vy_slice_cut(struct vy_slice *slice, int64_t id, struct tuple *begin,
  */
 static int
 vy_page_info_decode(struct vy_page_info *page, const struct xrow_header *xrow,
-		    const char *filename)
+		    struct key_def *cmp_def, const char *filename)
 {
 	assert(xrow->type == VY_INDEX_PAGE_INFO);
 	const char *pos = xrow->body->iov_base;
@@ -494,6 +510,7 @@ vy_page_info_decode(struct vy_page_info *page, const struct xrow_header *xrow,
 	uint32_t map_size = mp_decode_map(&pos);
 	uint32_t map_item;
 	const char *key_beg;
+	uint32_t part_count;
 	for (map_item = 0; map_item < map_size; ++map_item) {
 		uint32_t key = mp_decode_uint(&pos);
 		key_map &= ~(1ULL << key);
@@ -513,6 +530,8 @@ vy_page_info_decode(struct vy_page_info *page, const struct xrow_header *xrow,
 			page->min_key = vy_key_dup(key_beg);
 			if (page->min_key == NULL)
 				return -1;
+			part_count = mp_decode_array(&key_beg);
+			page->hint = key_hint(key_beg, part_count, cmp_def);
 			break;
 		case VY_PAGE_INFO_UNPACKED_SIZE:
 			page->unpacked_size = mp_decode_uint(&pos);
@@ -707,19 +726,24 @@ vy_page_xrow(struct vy_page *page, uint32_t stmt_no,
  * Read raw stmt data from the page
  * @param page          Page.
  * @param stmt_no       Statement position in the page.
+ * @param cmp_def       Definition of keys stored in the page.
  * @param format        Format for REPLACE/DELETE tuples.
+ * @param[out] hint     Comparison hint of the loaded statement.
  *
  * @retval not NULL Statement read from page.
  * @retval     NULL Memory error.
  */
 static struct tuple *
-vy_page_stmt(struct vy_page *page, uint32_t stmt_no,
-	     struct tuple_format *format)
+vy_page_stmt(struct vy_page *page, uint32_t stmt_no, struct key_def *cmp_def,
+	     struct tuple_format *format, hint_t *hint)
 {
 	struct xrow_header xrow;
 	if (vy_page_xrow(page, stmt_no, &xrow) != 0)
 		return NULL;
-	return vy_stmt_decode(&xrow, format);
+	struct tuple *stmt = vy_stmt_decode(&xrow, format);
+	if (stmt != NULL)
+		*hint = vy_stmt_hint(stmt, cmp_def);
+	return stmt;
 }
 
 /**
@@ -731,6 +755,7 @@ vy_run_iterator_stop(struct vy_run_iterator *itr)
 	if (itr->curr_stmt != NULL) {
 		tuple_unref(itr->curr_stmt);
 		itr->curr_stmt = NULL;
+		itr->curr_hint = HINT_NONE;
 	}
 	if (itr->curr_page != NULL) {
 		vy_page_delete(itr->curr_page);
@@ -1015,13 +1040,14 @@ vy_run_iterator_load_page(struct vy_run_iterator *itr, uint32_t page_no,
 static NODISCARD int
 vy_run_iterator_read(struct vy_run_iterator *itr,
 		     struct vy_run_iterator_pos pos,
-		     struct tuple **stmt)
+		     struct tuple **stmt, hint_t *hint)
 {
 	struct vy_page *page;
 	int rc = vy_run_iterator_load_page(itr, pos.page_no, &page);
 	if (rc != 0)
 		return rc;
-	*stmt = vy_page_stmt(page, pos.pos_in_page, itr->format);
+	*stmt = vy_page_stmt(page, pos.pos_in_page, itr->cmp_def,
+			     itr->format, hint);
 	if (*stmt == NULL)
 		return -1;
 	return 0;
@@ -1037,7 +1063,7 @@ vy_run_iterator_read(struct vy_run_iterator *itr,
 static uint32_t
 vy_run_iterator_search_in_page(struct vy_run_iterator *itr,
 			       enum iterator_type iterator_type,
-			       const struct tuple *key,
+			       const struct tuple *key, hint_t hint,
 			       struct vy_page *page, bool *equal_key)
 {
 	uint32_t beg = 0;
@@ -1047,10 +1073,13 @@ vy_run_iterator_search_in_page(struct vy_run_iterator *itr,
 			iterator_type == ITER_LE ? -1 : 0);
 	while (beg != end) {
 		uint32_t mid = beg + (end - beg) / 2;
-		struct tuple *fnd_key = vy_page_stmt(page, mid, itr->format);
+		hint_t fnd_hint;
+		struct tuple *fnd_key = vy_page_stmt(page, mid, itr->cmp_def,
+						     itr->format, &fnd_hint);
 		if (fnd_key == NULL)
 			return end;
-		int cmp = vy_stmt_compare(fnd_key, key, itr->cmp_def);
+		int cmp = vy_stmt_compare_hinted(fnd_key, fnd_hint,
+						 key, hint, itr->cmp_def);
 		cmp = cmp ? cmp : zero_cmp;
 		*equal_key = *equal_key || cmp == 0;
 		if (cmp < 0)
@@ -1076,12 +1105,11 @@ vy_run_iterator_search_in_page(struct vy_run_iterator *itr,
 static NODISCARD int
 vy_run_iterator_search(struct vy_run_iterator *itr,
 		       enum iterator_type iterator_type,
-		       const struct tuple *key,
+		       const struct tuple *key, hint_t hint,
 		       struct vy_run_iterator_pos *pos, bool *equal_key)
 {
-	pos->page_no = vy_page_index_find_page(itr->slice->run, key,
-					       itr->cmp_def, iterator_type,
-					       equal_key);
+	pos->page_no = vy_page_index_find_page(itr->slice->run, iterator_type,
+					       key, hint, itr->cmp_def, equal_key);
 	if (pos->page_no == itr->slice->run->info.page_count)
 		return 1;
 	struct vy_page *page;
@@ -1090,7 +1118,7 @@ vy_run_iterator_search(struct vy_run_iterator *itr,
 		return rc;
 	bool equal_in_page = false;
 	pos->pos_in_page = vy_run_iterator_search_in_page(itr, iterator_type,
-							  key, page,
+							  key, hint, page,
 							  &equal_in_page);
 	if (pos->pos_in_page == page->row_count) {
 		pos->page_no++;
@@ -1176,11 +1204,12 @@ vy_run_iterator_find_lsn(struct vy_run_iterator *itr, struct tuple **ret)
 		}
 		tuple_unref(itr->curr_stmt);
 		itr->curr_stmt = NULL;
-		if (vy_run_iterator_read(itr, itr->curr_pos,
-					 &itr->curr_stmt) != 0)
+		if (vy_run_iterator_read(itr, itr->curr_pos, &itr->curr_stmt,
+					 &itr->curr_hint) != 0)
 			return -1;
 		if (itr->iterator_type == ITER_EQ &&
-		    vy_stmt_compare(itr->curr_stmt, itr->key, cmp_def) != 0) {
+		    vy_stmt_compare_hinted(itr->curr_stmt, itr->curr_hint,
+					   itr->key, itr->hint, cmp_def) != 0) {
 			vy_run_iterator_stop(itr);
 			return 0;
 		}
@@ -1189,26 +1218,32 @@ vy_run_iterator_find_lsn(struct vy_run_iterator *itr, struct tuple **ret)
 		struct vy_run_iterator_pos test_pos;
 		while (vy_run_iterator_next_pos(itr, itr->iterator_type,
 						&test_pos) == 0) {
+			hint_t test_hint;
 			struct tuple *test_stmt;
-			if (vy_run_iterator_read(itr, test_pos,
-						 &test_stmt) != 0)
+			if (vy_run_iterator_read(itr, test_pos, &test_stmt,
+						 &test_hint) != 0)
 				return -1;
 			if (vy_stmt_lsn(test_stmt) > (**itr->read_view).vlsn ||
 			    vy_stmt_flags(test_stmt) & VY_STMT_SKIP_READ ||
-			    vy_stmt_compare(itr->curr_stmt, test_stmt,
-					    cmp_def) != 0) {
+			    vy_stmt_compare_hinted(itr->curr_stmt,
+						   itr->curr_hint,
+						   test_stmt, test_hint,
+						   cmp_def) != 0) {
 				tuple_unref(test_stmt);
 				break;
 			}
 			tuple_unref(itr->curr_stmt);
 			itr->curr_stmt = test_stmt;
+			itr->curr_hint = test_hint;
 			itr->curr_pos = test_pos;
 		}
 	}
 	/* Check if the result is within the slice boundaries. */
 	if (itr->iterator_type == ITER_LE || itr->iterator_type == ITER_LT) {
 		if (slice->begin != NULL &&
-		    vy_stmt_compare(itr->curr_stmt, slice->begin, cmp_def) < 0) {
+		    vy_stmt_compare_hinted(itr->curr_stmt, itr->curr_hint,
+					   slice->begin, slice->begin_hint,
+					   cmp_def) < 0) {
 			vy_run_iterator_stop(itr);
 			return 0;
 		}
@@ -1217,7 +1252,9 @@ vy_run_iterator_find_lsn(struct vy_run_iterator *itr, struct tuple **ret)
 		       itr->iterator_type == ITER_GT ||
 		       itr->iterator_type == ITER_EQ);
 		if (slice->end != NULL &&
-		    vy_stmt_compare(itr->curr_stmt, slice->end, cmp_def) >= 0) {
+		    vy_stmt_compare_hinted(itr->curr_stmt, itr->curr_hint,
+					   slice->end, slice->end_hint,
+					   cmp_def) >= 0) {
 			vy_run_iterator_stop(itr);
 			return 0;
 		}
@@ -1243,13 +1280,13 @@ vy_run_iterator_find_lsn(struct vy_run_iterator *itr, struct tuple **ret)
 static NODISCARD int
 vy_run_iterator_do_seek(struct vy_run_iterator *itr,
 			enum iterator_type iterator_type,
-			const struct tuple *key)
+			const struct tuple *key, hint_t hint)
 {
 	struct vy_run *run = itr->slice->run;
 	struct vy_run_iterator_pos end_pos = {run->info.page_count, 0};
 	bool equal_found = false;
 	if (!vy_stmt_is_empty_key(key)) {
-		int rc = vy_run_iterator_search(itr, iterator_type, key,
+		int rc = vy_run_iterator_search(itr, iterator_type, key, hint,
 						&itr->curr_pos, &equal_found);
 		if (rc != 0)
 			return rc;
@@ -1296,12 +1333,13 @@ vy_run_iterator_do_seek(struct vy_run_iterator *itr,
  */
 static NODISCARD int
 vy_run_iterator_seek(struct vy_run_iterator *itr, const struct tuple *last_key,
-		     struct tuple **ret)
+		     hint_t last_hint, struct tuple **ret)
 {
 	struct key_def *cmp_def = itr->cmp_def;
 	struct vy_slice *slice = itr->slice;
 	struct tuple_bloom *bloom = slice->run->info.bloom;
 	const struct tuple *key = itr->key;
+	hint_t hint = itr->hint;
 	enum iterator_type iterator_type = itr->iterator_type;
 
 	*ret = NULL;
@@ -1334,6 +1372,7 @@ vy_run_iterator_seek(struct vy_run_iterator *itr, const struct tuple *last_key,
 		iterator_type = iterator_direction(iterator_type) > 0 ?
 				ITER_GT : ITER_LT;
 		key = last_key;
+		hint = last_hint;
 	}
 
 	/* Take slice boundaries into account. */
@@ -1353,7 +1392,8 @@ vy_run_iterator_seek(struct vy_run_iterator *itr, const struct tuple *last_key,
 		 *         | ge  | begin | ge  |
 		 *         | eq  |    stop     |
 		 */
-		int cmp = vy_stmt_compare(key, slice->begin, cmp_def);
+		int cmp = vy_stmt_compare_hinted(key, hint, slice->begin,
+						 slice->begin_hint, cmp_def);
 		if (cmp < 0 && iterator_type == ITER_EQ) {
 			vy_run_iterator_stop(itr);
 			return 0;
@@ -1363,6 +1403,7 @@ vy_run_iterator_seek(struct vy_run_iterator *itr, const struct tuple *last_key,
 				check_eq = true;
 			iterator_type = ITER_GE;
 			key = slice->begin;
+			hint = slice->begin_hint;
 		}
 	}
 	if (slice->end != NULL &&
@@ -1378,16 +1419,18 @@ vy_run_iterator_seek(struct vy_run_iterator *itr, const struct tuple *last_key,
 		 * > end   | lt  | end   | lt  |
 		 *         | le  | end   | lt  |
 		 */
-		int cmp = vy_stmt_compare(key, slice->end, cmp_def);
+		int cmp = vy_stmt_compare_hinted(key, hint, slice->end,
+						 slice->end_hint, cmp_def);
 		if (cmp > 0 || (cmp == 0 && iterator_type != ITER_LT)) {
 			iterator_type = ITER_LT;
 			key = slice->end;
+			hint = slice->end_hint;
 		}
 	}
 
 	/* Perform a lookup in the run. */
 	itr->stat->lookup++;
-	int rc = vy_run_iterator_do_seek(itr, iterator_type, key);
+	int rc = vy_run_iterator_do_seek(itr, iterator_type, key, hint);
 	if (rc < 0)
 		return -1;
 	if (rc > 0)
@@ -1397,13 +1440,15 @@ vy_run_iterator_seek(struct vy_run_iterator *itr, const struct tuple *last_key,
 	if (itr->curr_stmt != NULL) {
 		tuple_unref(itr->curr_stmt);
 		itr->curr_stmt = NULL;
+		itr->curr_hint = HINT_NONE;
 	}
-	if (vy_run_iterator_read(itr, itr->curr_pos, &itr->curr_stmt) != 0)
+	if (vy_run_iterator_read(itr, itr->curr_pos, &itr->curr_stmt,
+				 &itr->curr_hint) != 0)
 		return -1;
 
 	/* Check EQ constraint if necessary. */
-	if (check_eq && vy_stmt_compare(itr->curr_stmt, itr->key,
-					itr->cmp_def) != 0)
+	if (check_eq && vy_stmt_compare_hinted(itr->curr_stmt, itr->curr_hint,
+					itr->key, itr->hint, itr->cmp_def) != 0)
 		goto not_found;
 
 	/* Skip statements invisible from the iterator read view. */
@@ -1436,9 +1481,11 @@ vy_run_iterator_open(struct vy_run_iterator *itr,
 
 	itr->iterator_type = iterator_type;
 	itr->key = key;
+	itr->hint = vy_stmt_hint(key, cmp_def);
 	itr->read_view = rv;
 
 	itr->curr_stmt = NULL;
+	itr->curr_hint = HINT_NONE;
 	itr->curr_pos.page_no = slice->run->info.page_count;
 	itr->curr_page = NULL;
 	itr->prev_page = NULL;
@@ -1467,13 +1514,14 @@ vy_run_iterator_next_key(struct vy_run_iterator *itr, struct tuple **ret)
 
 	if (!itr->search_started) {
 		itr->search_started = true;
-		return vy_run_iterator_seek(itr, NULL, ret);
+		return vy_run_iterator_seek(itr, NULL, HINT_NONE, ret);
 	}
 	if (itr->curr_stmt == NULL)
 		return 0;
 
 	assert(itr->curr_pos.page_no < itr->slice->run->info.page_count);
 
+	hint_t next_hint = HINT_NONE;
 	struct tuple *next_key = NULL;
 	do {
 		if (next_key != NULL)
@@ -1484,15 +1532,19 @@ vy_run_iterator_next_key(struct vy_run_iterator *itr, struct tuple **ret)
 			return 0;
 		}
 
-		if (vy_run_iterator_read(itr, itr->curr_pos, &next_key) != 0)
+		if (vy_run_iterator_read(itr, itr->curr_pos,
+					 &next_key, &next_hint) != 0)
 			return -1;
-	} while (vy_stmt_compare(itr->curr_stmt, next_key, itr->cmp_def) == 0);
+	} while (vy_stmt_compare_hinted(itr->curr_stmt, itr->curr_hint,
+					next_key, next_hint, itr->cmp_def) == 0);
 
 	tuple_unref(itr->curr_stmt);
 	itr->curr_stmt = next_key;
+	itr->curr_hint = next_hint;
 
 	if (itr->iterator_type == ITER_EQ &&
-	    vy_stmt_compare(next_key, itr->key, itr->cmp_def) != 0) {
+	    vy_stmt_compare_hinted(next_key, next_hint, itr->key, itr->hint,
+				   itr->cmp_def) != 0) {
 		vy_run_iterator_stop(itr);
 		return 0;
 	}
@@ -1520,17 +1572,20 @@ next:
 		return 0;
 	}
 
+	hint_t next_hint;
 	struct tuple *next_key;
-	if (vy_run_iterator_read(itr, next_pos, &next_key) != 0)
+	if (vy_run_iterator_read(itr, next_pos, &next_key, &next_hint) != 0)
 		return -1;
 
-	if (vy_stmt_compare(itr->curr_stmt, next_key, itr->cmp_def) != 0) {
+	if (vy_stmt_compare_hinted(itr->curr_stmt, itr->curr_hint,
+				   next_key, next_hint, itr->cmp_def) != 0) {
 		tuple_unref(next_key);
 		return 0;
 	}
 
 	tuple_unref(itr->curr_stmt);
 	itr->curr_stmt = next_key;
+	itr->curr_hint = next_hint;
 	itr->curr_pos = next_pos;
 	if (vy_stmt_flags(itr->curr_stmt) & VY_STMT_SKIP_READ)
 		goto next;
@@ -1564,6 +1619,8 @@ vy_run_iterator_skip(struct vy_run_iterator *itr,
 		     const struct tuple *last_stmt,
 		     struct vy_history *history)
 {
+	hint_t last_hint = last_stmt == NULL ? HINT_NONE :
+			   vy_stmt_hint(last_stmt, itr->cmp_def);
 	/*
 	 * Check if the iterator is already positioned
 	 * at the statement following last_stmt.
@@ -1571,14 +1628,15 @@ vy_run_iterator_skip(struct vy_run_iterator *itr,
 	if (itr->search_started &&
 	    (itr->curr_stmt == NULL || last_stmt == NULL ||
 	     iterator_direction(itr->iterator_type) *
-	     vy_stmt_compare(itr->curr_stmt, last_stmt, itr->cmp_def) > 0))
+	     vy_stmt_compare_hinted(itr->curr_stmt, itr->curr_hint,
+				    last_stmt, last_hint, itr->cmp_def) > 0))
 		return 0;
 
 	vy_history_cleanup(history);
 
 	itr->search_started = true;
 	struct tuple *stmt;
-	if (vy_run_iterator_seek(itr, last_stmt, &stmt) != 0)
+	if (vy_run_iterator_seek(itr, last_stmt, last_hint, &stmt) != 0)
 		return -1;
 
 	while (stmt != NULL) {
@@ -1617,8 +1675,8 @@ vy_run_acct_page(struct vy_run *run, struct vy_page_info *page)
 }
 
 int
-vy_run_recover(struct vy_run *run, const char *dir,
-	       uint32_t space_id, uint32_t iid)
+vy_run_recover(struct vy_run *run, const char *dir, uint32_t space_id,
+	       uint32_t iid, struct key_def *cmp_def)
 {
 	char path[PATH_MAX];
 	vy_run_snprint_path(path, sizeof(path), dir,
@@ -1704,7 +1762,7 @@ vy_run_recover(struct vy_run *run, const char *dir,
 			goto fail_close;
 		}
 		struct vy_page_info *page = run->page_info + page_no;
-		if (vy_page_info_decode(page, &xrow, path) < 0) {
+		if (vy_page_info_decode(page, &xrow, cmp_def, path) < 0) {
 			/**
 			 * Limit the count of pages to successfully
 			 * created pages
@@ -2148,7 +2206,8 @@ vy_run_writer_start_page(struct vy_run_writer *writer,
 			return -1;
 	}
 	struct vy_page_info *page = run->page_info + run->info.page_count;
-	if (vy_page_info_create(page, writer->data_xlog.offset, key) != 0)
+	if (vy_page_info_create(page, writer->data_xlog.offset,
+				key, writer->cmp_def) != 0)
 		return -1;
 	xlog_tx_begin(&writer->data_xlog);
 	return 0;
@@ -2425,7 +2484,8 @@ vy_run_rebuild_index(struct vy_run *run, const char *dir,
 		}
 		struct vy_page_info *info;
 		info = run->page_info + run->info.page_count;
-		if (vy_page_info_create(info, page_offset, page_min_key) != 0)
+		if (vy_page_info_create(info, page_offset,
+					page_min_key, cmp_def) != 0)
 			goto close_err;
 		info->row_count = page_row_count;
 		info->size = next_page_offset - page_offset;
@@ -2570,12 +2630,15 @@ vy_slice_stream_search(struct vy_stmt_stream *virt_stream)
 	uint32_t end = stream->page->row_count;
 	while (beg != end) {
 		uint32_t mid = beg + (end - beg) / 2;
+		hint_t fnd_hint;
 		struct tuple *fnd_key = vy_page_stmt(stream->page, mid,
-						     stream->format);
+				stream->cmp_def, stream->format, &fnd_hint);
 		if (fnd_key == NULL)
 			return -1;
-		int cmp = vy_stmt_compare(fnd_key, stream->slice->begin,
-					  stream->cmp_def);
+		int cmp = vy_stmt_compare_hinted(fnd_key, fnd_hint,
+						 stream->slice->begin,
+						 stream->slice->begin_hint,
+						 stream->cmp_def);
 		if (cmp < 0)
 			beg = mid + 1;
 		else
@@ -2617,15 +2680,17 @@ vy_slice_stream_next(struct vy_stmt_stream *virt_stream, struct tuple **ret)
 		return -1;
 
 	/* Read current tuple from the page */
+	hint_t hint;
 	struct tuple *tuple = vy_page_stmt(stream->page, stream->pos_in_page,
-					   stream->format);
+					stream->cmp_def, stream->format, &hint);
 	if (tuple == NULL) /* Read or memory error */
 		return -1;
 
 	/* Check that the tuple is not out of slice bounds = */
 	if (stream->slice->end != NULL &&
 	    stream->page_no >= stream->slice->last_page_no &&
-	    vy_stmt_compare(tuple, stream->slice->end, stream->cmp_def) >= 0) {
+	    vy_stmt_compare_hinted(tuple, hint, stream->slice->end,
+			stream->slice->end_hint, stream->cmp_def) >= 0) {
 		tuple_unref(tuple);
 		return 0;
 	}
diff --git a/src/box/vy_run.h b/src/box/vy_run.h
index cbc51c50..369221ff 100644
--- a/src/box/vy_run.h
+++ b/src/box/vy_run.h
@@ -105,6 +105,8 @@ struct vy_page_info {
 	uint32_t row_count;
 	/** Minimal key stored in the page. */
 	char *min_key;
+	/** Comparison hint of @min_key. */
+	hint_t hint;
 	/** Offset of the row index in the page. */
 	uint32_t row_index_offset;
 };
@@ -185,6 +187,11 @@ struct vy_slice {
 	struct tuple *begin;
 	struct tuple *end;
 	/**
+	 * Comparison hints of @begin and @end tuples.
+	 */
+	hint_t begin_hint;
+	hint_t end_hint;
+	/**
 	 * Random seed used for compaction randomization.
 	 * Lays in range [0, RAND_MAX].
 	 */
@@ -260,6 +267,8 @@ struct vy_run_iterator {
 	enum iterator_type iterator_type;
 	/** Key to search. */
 	const struct tuple *key;
+	/** Comparison hint of the search key. */
+	hint_t hint;
 	/* LSN visibility, iterator shows values with lsn <= vlsn */
 	const struct vy_read_view **read_view;
 
@@ -268,6 +277,8 @@ struct vy_run_iterator {
 	struct vy_run_iterator_pos curr_pos;
 	/** Statement at curr_pos. */
 	struct tuple *curr_stmt;
+	/** Comparison hint of the current statement. */
+	hint_t curr_hint;
 	/**
 	 * Last two pages read by the iterator. We keep two pages
 	 * rather than just one, because we often probe a page for
@@ -374,11 +385,12 @@ vy_run_unref(struct vy_run *run)
  * @param dir - path to the vinyl directory
  * @param space_id - space id
  * @param iid - index id
+ * @param cmp_def - definition of keys stored in the run
  * @return - 0 on sucess, -1 on fail
  */
 int
-vy_run_recover(struct vy_run *run, const char *dir,
-	       uint32_t space_id, uint32_t iid);
+vy_run_recover(struct vy_run *run, const char *dir, uint32_t space_id,
+	       uint32_t iid, struct key_def *cmp_def);
 
 /**
  * Rebuild run index
@@ -453,7 +465,8 @@ vy_run_remove_files(const char *dir, uint32_t space_id,
  */
 struct vy_slice *
 vy_slice_new(int64_t id, struct vy_run *run, struct tuple *begin,
-	     struct tuple *end, struct key_def *cmp_def);
+	     hint_t begin_hint, struct tuple *end, hint_t end_hint,
+	     struct key_def *cmp_def);
 
 /**
  * Free a run slice.
@@ -504,8 +517,8 @@ vy_slice_wait_pinned(struct vy_slice *slice)
  */
 int
 vy_slice_cut(struct vy_slice *slice, int64_t id, struct tuple *begin,
-	     struct tuple *end, struct key_def *cmp_def,
-	     struct vy_slice **result);
+	     hint_t begin_hint, struct tuple *end, hint_t end_hint,
+	     struct key_def *cmp_def, struct vy_slice **result);
 
 /**
  * Open an iterator over on-disk run.
diff --git a/src/box/vy_scheduler.c b/src/box/vy_scheduler.c
index aaae1a89..723bc9ee 100644
--- a/src/box/vy_scheduler.c
+++ b/src/box/vy_scheduler.c
@@ -1147,7 +1147,8 @@ vy_task_dump_complete(struct vy_task *task)
 	for (range = begin_range, i = 0; range != end_range;
 	     range = vy_range_tree_next(&lsm->range_tree, range), i++) {
 		slice = vy_slice_new(vy_log_next_id(), new_run,
-				     range->begin, range->end, lsm->cmp_def);
+				     range->begin, range->begin_hint,
+				     range->end, range->end_hint, lsm->cmp_def);
 		if (slice == NULL)
 			goto fail_free_slices;
 
@@ -1458,7 +1459,8 @@ vy_task_compaction_complete(struct vy_task *task)
 	 */
 	if (!vy_run_is_empty(new_run)) {
 		new_slice = vy_slice_new(vy_log_next_id(), new_run,
-					 NULL, NULL, lsm->cmp_def);
+					 NULL, HINT_NONE, NULL, HINT_NONE,
+					 lsm->cmp_def);
 		if (new_slice == NULL)
 			return -1;
 	}
diff --git a/src/box/vy_stmt.h b/src/box/vy_stmt.h
index 928ae348..8467c2d7 100644
--- a/src/box/vy_stmt.h
+++ b/src/box/vy_stmt.h
@@ -438,14 +438,17 @@ vy_stmt_compare_hinted(const struct tuple *a, hint_t a_hint,
  * (msgpack array).
  */
 static inline int
-vy_stmt_compare_with_raw_key(const struct tuple *stmt, const char *key,
-			     struct key_def *key_def)
+vy_stmt_compare_with_raw_key_hinted(const struct tuple *stmt, hint_t stmt_hint,
+				    const char *key, hint_t key_hint,
+				    struct key_def *key_def)
 {
 	if (!vy_stmt_is_key(stmt)) {
 		uint32_t part_count = mp_decode_array(&key);
-		return tuple_compare_with_key(stmt, key, part_count, key_def);
+		return tuple_compare_with_key_hinted(stmt, stmt_hint, key,
+						part_count, key_hint, key_def);
 	}
-	return key_compare(tuple_data(stmt), key, key_def);
+	return key_compare_hinted(tuple_data(stmt), stmt_hint,
+				  key, key_hint, key_def);
 }
 
 /**
diff --git a/test/unit/vy_point_lookup.c b/test/unit/vy_point_lookup.c
index 8fb1a8d1..bb9798a9 100644
--- a/test/unit/vy_point_lookup.c
+++ b/test/unit/vy_point_lookup.c
@@ -206,7 +206,8 @@ test_basic()
 	vy_mem_delete(run_mem);
 
 	vy_lsm_add_run(pk, run);
-	struct vy_slice *slice = vy_slice_new(1, run, NULL, NULL, pk->cmp_def);
+	struct vy_slice *slice = vy_slice_new(1, run, NULL, HINT_NONE,
+					      NULL, HINT_NONE, pk->cmp_def);
 	vy_range_add_slice(range, slice);
 	vy_run_unref(run);
 
@@ -236,7 +237,8 @@ test_basic()
 	vy_mem_delete(run_mem);
 
 	vy_lsm_add_run(pk, run);
-	slice = vy_slice_new(1, run, NULL, NULL, pk->cmp_def);
+	slice = vy_slice_new(1, run, NULL, HINT_NONE,
+			     NULL, HINT_NONE, pk->cmp_def);
 	vy_range_add_slice(range, slice);
 	vy_run_unref(run);
 
diff --git a/test/vinyl/stat.result b/test/vinyl/stat.result
index 934e0807..f49394f7 100644
--- a/test/vinyl/stat.result
+++ b/test/vinyl/stat.result
@@ -323,7 +323,7 @@ stat_diff(istat(), st)
         bytes_compressed: <bytes_compressed>
         rows: 25
     bytes: 26049
-    index_size: 294
+    index_size: 350
     pages: 7
     bytes_compressed: <bytes_compressed>
     bloom_size: 70
@@ -370,7 +370,7 @@ stat_diff(istat(), st)
         bytes_compressed: <bytes_compressed>
         rows: 50
     bytes: 26042
-    index_size: 252
+    index_size: 300
     pages: 6
     bytes_compressed: <bytes_compressed>
     compaction:
@@ -1046,7 +1046,7 @@ istat()
         bytes: 0
       count: 0
     bloom_size: 140
-    index_size: 1050
+    index_size: 1250
     iterator:
       read:
         bytes_compressed: <bytes_compressed>
@@ -1125,12 +1125,12 @@ gstat()
     tuple_cache: 14417
     tx: 0
     level0: 262583
-    page_index: 1050
+    page_index: 1250
     bloom_filter: 140
   disk:
     data_compacted: 104300
     data: 104300
-    index: 1190
+    index: 1390
   scheduler:
     tasks_inprogress: 0
     dump_output: 0
@@ -1338,8 +1338,8 @@ i1:len(), i2:len()
 ...
 i1:bsize(), i2:bsize()
 ---
-- 364
-- 920
+- 420
+- 928
 ...
 s:bsize() == st1.disk.bytes
 ---
@@ -1400,8 +1400,8 @@ i1:len(), i2:len()
 ...
 i1:bsize(), i2:bsize()
 ---
-- 49516
-- 50072
+- 49572
+- 50080
 ...
 s:bsize() == st1.memory.bytes + st1.disk.bytes
 ---
@@ -1465,8 +1465,8 @@ i1:len(), i2:len()
 ...
 i1:bsize(), i2:bsize()
 ---
-- 364
-- 920
+- 420
+- 928
 ...
 s:bsize() == st1.disk.bytes
 ---
-- 
2.11.0