[PATCH 07/13] vinyl: propagate tuple comparison hints to read iterator

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

This patch propagates hints from source iterators (mem, run, txw, cache)
to the read iterator code. Now, source iterators take and return
comparison hints along with statements. The read iterator uses the hints
to speed up tuple comparisons.

Apart from speeding up lookups, this is also needed for multikey index
support, because multikey indexes will reuse hints to store offsets of
indexed array entries.
---
 src/box/vy_cache.c         |  28 ++++----
 src/box/vy_cache.h         |  11 +--
 src/box/vy_history.c       |   9 ++-
 src/box/vy_history.h       |  15 ++--
 src/box/vy_mem.c           |  16 ++---
 src/box/vy_mem.h           |   7 +-
 src/box/vy_point_lookup.c  |  53 ++++++++------
 src/box/vy_read_iterator.c | 170 +++++++++++++++++++++++++++------------------
 src/box/vy_read_iterator.h |   5 ++
 src/box/vy_run.c           |  47 ++++++++-----
 src/box/vy_run.h           |   5 +-
 src/box/vy_tx.c            |  22 +++---
 src/box/vy_tx.h            |   6 +-
 test/unit/vy_cache.c       |  12 ++--
 test/unit/vy_mem.c         |  22 +++---
 15 files changed, 255 insertions(+), 173 deletions(-)

diff --git a/src/box/vy_cache.c b/src/box/vy_cache.c
index 8fafd648..a4a767bc 100644
--- a/src/box/vy_cache.c
+++ b/src/box/vy_cache.c
@@ -431,15 +431,16 @@ vy_cache_add(struct vy_cache *cache, struct tuple *stmt,
 }
 
 struct tuple *
-vy_cache_get(struct vy_cache *cache, const struct tuple *key)
+vy_cache_get(struct vy_cache *cache, const struct tuple *key,
+	     hint_t hint, hint_t *ret_hint)
 {
-	hint_t hint = vy_stmt_hint(key, cache->cmp_def);
 	struct vy_cache_tree_key tree_key;
 	tree_key = vy_cache_tree_key(key, hint);
 	struct vy_cache_entry **entry =
 		vy_cache_tree_find(&cache->cache_tree, &tree_key);
 	if (entry == NULL)
 		return NULL;
+	*ret_hint = (*entry)->hint;
 	return (*entry)->stmt;
 }
 
@@ -732,20 +733,19 @@ vy_cache_iterator_next(struct vy_cache_iterator *itr,
 	if (itr->curr_stmt != NULL) {
 		vy_stmt_counter_acct_tuple(&itr->cache->stat.get,
 					   itr->curr_stmt);
-		return vy_history_append_stmt(history, itr->curr_stmt);
+		return vy_history_append_stmt(history, itr->curr_stmt,
+					      itr->curr_hint);
 	}
 	return 0;
 }
 
 NODISCARD int
 vy_cache_iterator_skip(struct vy_cache_iterator *itr,
-		       const struct tuple *last_stmt,
+		       const struct tuple *last_stmt, hint_t last_hint,
 		       struct vy_history *history, bool *stop)
 {
 	assert(!itr->search_started || itr->version == itr->cache->version);
 
-	hint_t last_hint = last_stmt == NULL ? HINT_NONE :
-			   vy_stmt_hint(last_stmt, itr->cache->cmp_def);
 	/*
 	 * Check if the iterator is already positioned
 	 * at the statement following last_stmt.
@@ -768,22 +768,20 @@ vy_cache_iterator_skip(struct vy_cache_iterator *itr,
 	if (itr->curr_stmt != NULL) {
 		vy_stmt_counter_acct_tuple(&itr->cache->stat.get,
 					   itr->curr_stmt);
-		return vy_history_append_stmt(history, itr->curr_stmt);
+		return vy_history_append_stmt(history, itr->curr_stmt,
+					      itr->curr_hint);
 	}
 	return 0;
 }
 
 NODISCARD int
 vy_cache_iterator_restore(struct vy_cache_iterator *itr,
-			  const struct tuple *last_stmt,
+			  const struct tuple *last_stmt, hint_t last_hint,
 			  struct vy_history *history, bool *stop)
 {
 	if (!itr->search_started || itr->version == itr->cache->version)
 		return 0;
 
-	hint_t last_hint = last_stmt == NULL ? HINT_NONE :
-			   vy_stmt_hint(last_stmt, itr->cache->cmp_def);
-
 	/* Check if the iterator position is still valid. */
 	bool pos_invalid = false;
 	struct vy_cache_tree *tree = &itr->cache->cache_tree;
@@ -865,7 +863,8 @@ vy_cache_iterator_restore(struct vy_cache_iterator *itr,
 	if (itr->curr_stmt != NULL) {
 		vy_stmt_counter_acct_tuple(&itr->cache->stat.get,
 					   itr->curr_stmt);
-		if (vy_history_append_stmt(history, itr->curr_stmt) != 0)
+		if (vy_history_append_stmt(history, itr->curr_stmt,
+					   itr->curr_hint) != 0)
 			return -1;
 	}
 	return 1;
@@ -884,12 +883,13 @@ vy_cache_iterator_close(struct vy_cache_iterator *itr)
 void
 vy_cache_iterator_open(struct vy_cache_iterator *itr, struct vy_cache *cache,
 		       enum iterator_type iterator_type,
-		       const struct tuple *key, const struct vy_read_view **rv)
+		       const struct tuple *key, hint_t hint,
+		       const struct vy_read_view **rv)
 {
 	itr->cache = cache;
 	itr->iterator_type = iterator_type;
 	itr->key = key;
-	itr->hint = vy_stmt_hint(key, cache->cmp_def);
+	itr->hint = hint;
 	itr->read_view = rv;
 
 	itr->curr_stmt = NULL;
diff --git a/src/box/vy_cache.h b/src/box/vy_cache.h
index 4fcdb747..d256f32c 100644
--- a/src/box/vy_cache.h
+++ b/src/box/vy_cache.h
@@ -228,7 +228,8 @@ vy_cache_add(struct vy_cache *cache, struct tuple *stmt,
  * @return A tuple equal to key or NULL if not found.
  */
 struct tuple *
-vy_cache_get(struct vy_cache *cache, const struct tuple *key);
+vy_cache_get(struct vy_cache *cache, const struct tuple *key,
+	     hint_t hint, hint_t *ret_hint);
 
 /**
  * Invalidate possibly cached value due to its overwriting
@@ -282,12 +283,14 @@ struct vy_cache_iterator {
  * @param cache - the cache.
  * @param iterator_type - iterator type (EQ, GT, GE, LT, LE or ALL)
  * @param key - search key data in terms of vinyl, vy_stmt_compare argument
+ * @param hint - comparison hint of the search key
  * @param vlsn - LSN visibility, iterator shows values with lsn <= vlsn
  */
 void
 vy_cache_iterator_open(struct vy_cache_iterator *itr, struct vy_cache *cache,
 		       enum iterator_type iterator_type,
-		       const struct tuple *key, const struct vy_read_view **rv);
+		       const struct tuple *key, hint_t hint,
+		       const struct vy_read_view **rv);
 
 /**
  * Advance a cache iterator to the next key.
@@ -308,7 +311,7 @@ vy_cache_iterator_next(struct vy_cache_iterator *itr,
  */
 NODISCARD int
 vy_cache_iterator_skip(struct vy_cache_iterator *itr,
-		       const struct tuple *last_stmt,
+		       const struct tuple *last_stmt, hint_t last_hint,
 		       struct vy_history *history, bool *stop);
 
 /**
@@ -319,7 +322,7 @@ vy_cache_iterator_skip(struct vy_cache_iterator *itr,
  */
 NODISCARD int
 vy_cache_iterator_restore(struct vy_cache_iterator *itr,
-			  const struct tuple *last_stmt,
+			  const struct tuple *last_stmt, hint_t last_hint,
 			  struct vy_history *history, bool *stop);
 
 /**
diff --git a/src/box/vy_history.c b/src/box/vy_history.c
index b45c6d51..2cbc1695 100644
--- a/src/box/vy_history.c
+++ b/src/box/vy_history.c
@@ -43,7 +43,8 @@
 #include "vy_upsert.h"
 
 int
-vy_history_append_stmt(struct vy_history *history, struct tuple *stmt)
+vy_history_append_stmt(struct vy_history *history,
+		       struct tuple *stmt, hint_t hint)
 {
 	assert(history->pool->objsize == sizeof(struct vy_history_node));
 	struct vy_history_node *node = mempool_alloc(history->pool);
@@ -56,6 +57,7 @@ vy_history_append_stmt(struct vy_history *history, struct tuple *stmt)
 	if (node->is_refable)
 		tuple_ref(stmt);
 	node->stmt = stmt;
+	node->hint = hint;
 	rlist_add_tail_entry(&history->stmts, node, link);
 	return 0;
 }
@@ -74,9 +76,11 @@ vy_history_cleanup(struct vy_history *history)
 
 int
 vy_history_apply(struct vy_history *history, struct key_def *cmp_def,
-		 bool keep_delete, int *upserts_applied, struct tuple **ret)
+		 bool keep_delete, int *upserts_applied,
+		 struct tuple **ret, hint_t *ret_hint)
 {
 	*ret = NULL;
+	*ret_hint = HINT_NONE;
 	*upserts_applied = 0;
 	if (rlist_empty(&history->stmts))
 		return 0;
@@ -84,6 +88,7 @@ vy_history_apply(struct vy_history *history, struct key_def *cmp_def,
 	struct tuple *curr_stmt = NULL;
 	struct vy_history_node *node = rlist_last_entry(&history->stmts,
 					struct vy_history_node, link);
+	*ret_hint = node->hint;
 	if (vy_history_is_terminal(history)) {
 		if (!keep_delete && vy_stmt_type(node->stmt) == IPROTO_DELETE) {
 			/*
diff --git a/src/box/vy_history.h b/src/box/vy_history.h
index 458ea749..94070415 100644
--- a/src/box/vy_history.h
+++ b/src/box/vy_history.h
@@ -64,6 +64,8 @@ struct vy_history_node {
 	struct rlist link;
 	/** History statement. Referenced if @is_refable is set. */
 	struct tuple *stmt;
+	/** Comparison hint of the history statement. */
+	hint_t hint;
 	/**
 	 * Set if the statement stored in this node is refable,
 	 * i.e. has a reference counter that can be incremented
@@ -114,13 +116,16 @@ vy_history_is_terminal(struct vy_history *history)
  * key history or NULL if the history is empty.
  */
 static inline struct tuple *
-vy_history_last_stmt(struct vy_history *history)
+vy_history_last_stmt(struct vy_history *history, hint_t *hint)
 {
-	if (rlist_empty(&history->stmts))
+	if (rlist_empty(&history->stmts)) {
+		*hint = HINT_NONE;
 		return NULL;
+	}
 	/* Newest statement is at the head of the list. */
 	struct vy_history_node *node = rlist_first_entry(&history->stmts,
 					struct vy_history_node, link);
+	*hint = node->hint;
 	return node->stmt;
 }
 
@@ -139,7 +144,8 @@ vy_history_splice(struct vy_history *dst, struct vy_history *src)
  * Returns 0 on success, -1 on memory allocation error.
  */
 int
-vy_history_append_stmt(struct vy_history *history, struct tuple *stmt);
+vy_history_append_stmt(struct vy_history *history,
+		       struct tuple *stmt, hint_t hint);
 
 /**
  * Release all statements stored in the given history and
@@ -155,7 +161,8 @@ vy_history_cleanup(struct vy_history *history);
  */
 int
 vy_history_apply(struct vy_history *history, struct key_def *cmp_def,
-		 bool keep_delete, int *upserts_applied, struct tuple **ret);
+		 bool keep_delete, int *upserts_applied,
+		 struct tuple **ret, hint_t *ret_hint);
 
 #if defined(__cplusplus)
 } /* extern "C" */
diff --git a/src/box/vy_mem.c b/src/box/vy_mem.c
index 220751d4..aea0ecfb 100644
--- a/src/box/vy_mem.c
+++ b/src/box/vy_mem.c
@@ -467,7 +467,8 @@ vy_mem_iterator_seek(struct vy_mem_iterator *itr, const struct tuple *last_key,
 void
 vy_mem_iterator_open(struct vy_mem_iterator *itr, struct vy_mem_iterator_stat *stat,
 		     struct vy_mem *mem, enum iterator_type iterator_type,
-		     const struct tuple *key, const struct vy_read_view **rv)
+		     const struct tuple *key, hint_t hint,
+		     const struct vy_read_view **rv)
 {
 	itr->stat = stat;
 
@@ -476,7 +477,7 @@ vy_mem_iterator_open(struct vy_mem_iterator *itr, struct vy_mem_iterator_stat *s
 
 	itr->iterator_type = iterator_type;
 	itr->key = key;
-	itr->hint = vy_stmt_hint(key, mem->cmp_def);
+	itr->hint = hint;
 	itr->read_view = rv;
 
 	itr->curr_pos = vy_mem_tree_invalid_iterator();
@@ -574,7 +575,7 @@ vy_mem_iterator_get_history(struct vy_mem_iterator *itr,
 	do {
 		struct tuple *stmt = (struct tuple *)itr->curr.stmt;
 		vy_stmt_counter_acct_tuple(&itr->stat->get, stmt);
-		if (vy_history_append_stmt(history, stmt) != 0)
+		if (vy_history_append_stmt(history, stmt, itr->curr.hint) != 0)
 			return -1;
 		if (vy_history_is_terminal(history))
 			break;
@@ -594,14 +595,11 @@ vy_mem_iterator_next(struct vy_mem_iterator *itr,
 
 NODISCARD int
 vy_mem_iterator_skip(struct vy_mem_iterator *itr,
-		     const struct tuple *last_stmt,
+		     const struct tuple *last_stmt, hint_t last_hint,
 		     struct vy_history *history)
 {
 	assert(!itr->search_started || itr->version == itr->mem->version);
 
-	hint_t last_hint = last_stmt == NULL ? HINT_NONE :
-			   vy_stmt_hint(last_stmt, itr->mem->cmp_def);
-
 	/*
 	 * Check if the iterator is already positioned
 	 * at the statement following last_stmt.
@@ -621,14 +619,12 @@ vy_mem_iterator_skip(struct vy_mem_iterator *itr,
 
 NODISCARD int
 vy_mem_iterator_restore(struct vy_mem_iterator *itr,
-			const struct tuple *last_stmt,
+			const struct tuple *last_stmt, hint_t last_hint,
 			struct vy_history *history)
 {
 	if (!itr->search_started || itr->version == itr->mem->version)
 		return 0;
 
-	hint_t last_hint = last_stmt == NULL ? HINT_NONE :
-			   vy_stmt_hint(last_stmt, itr->mem->cmp_def);
 	vy_mem_iterator_seek(itr, last_stmt, last_hint);
 
 	vy_history_cleanup(history);
diff --git a/src/box/vy_mem.h b/src/box/vy_mem.h
index 160bf5e1..f31deaed 100644
--- a/src/box/vy_mem.h
+++ b/src/box/vy_mem.h
@@ -407,7 +407,8 @@ struct vy_mem_iterator {
 void
 vy_mem_iterator_open(struct vy_mem_iterator *itr, struct vy_mem_iterator_stat *stat,
 		     struct vy_mem *mem, enum iterator_type iterator_type,
-		     const struct tuple *key, const struct vy_read_view **rv);
+		     const struct tuple *key, hint_t hint,
+		     const struct vy_read_view **rv);
 
 /**
  * Advance a mem iterator to the next key.
@@ -425,7 +426,7 @@ vy_mem_iterator_next(struct vy_mem_iterator *itr,
  */
 NODISCARD int
 vy_mem_iterator_skip(struct vy_mem_iterator *itr,
-		     const struct tuple *last_stmt,
+		     const struct tuple *last_stmt, hint_t last_hint,
 		     struct vy_history *history);
 
 /**
@@ -436,7 +437,7 @@ vy_mem_iterator_skip(struct vy_mem_iterator *itr,
  */
 NODISCARD int
 vy_mem_iterator_restore(struct vy_mem_iterator *itr,
-			const struct tuple *last_stmt,
+			const struct tuple *last_stmt, hint_t last_hint,
 			struct vy_history *history);
 
 /**
diff --git a/src/box/vy_point_lookup.c b/src/box/vy_point_lookup.c
index aa0625fb..25125662 100644
--- a/src/box/vy_point_lookup.c
+++ b/src/box/vy_point_lookup.c
@@ -65,7 +65,7 @@ vy_point_lookup_scan_txw(struct vy_lsm *lsm, struct vy_tx *tx,
 		return 0;
 	vy_stmt_counter_acct_tuple(&lsm->stat.txw.iterator.get,
 				   txv->stmt);
-	return vy_history_append_stmt(history, txv->stmt);
+	return vy_history_append_stmt(history, txv->stmt, txv->hint);
 }
 
 /**
@@ -74,16 +74,18 @@ vy_point_lookup_scan_txw(struct vy_lsm *lsm, struct vy_tx *tx,
  */
 static int
 vy_point_lookup_scan_cache(struct vy_lsm *lsm, const struct vy_read_view **rv,
-			   struct tuple *key, struct vy_history *history)
+			   struct tuple *key, hint_t hint,
+			   struct vy_history *history)
 {
 	lsm->cache.stat.lookup++;
-	struct tuple *stmt = vy_cache_get(&lsm->cache, key);
+	hint_t stmt_hint;
+	struct tuple *stmt = vy_cache_get(&lsm->cache, key, hint, &stmt_hint);
 
 	if (stmt == NULL || vy_stmt_lsn(stmt) > (*rv)->vlsn)
 		return 0;
 
 	vy_stmt_counter_acct_tuple(&lsm->cache.stat.get, stmt);
-	return vy_history_append_stmt(history, stmt);
+	return vy_history_append_stmt(history, stmt, stmt_hint);
 }
 
 /**
@@ -92,12 +94,12 @@ vy_point_lookup_scan_cache(struct vy_lsm *lsm, const struct vy_read_view **rv,
  */
 static int
 vy_point_lookup_scan_mem(struct vy_lsm *lsm, struct vy_mem *mem,
-			 const struct vy_read_view **rv,
-			 struct tuple *key, struct vy_history *history)
+			 const struct vy_read_view **rv, struct tuple *key,
+			 hint_t hint, struct vy_history *history)
 {
 	struct vy_mem_iterator mem_itr;
 	vy_mem_iterator_open(&mem_itr, &lsm->stat.memory.iterator,
-			     mem, ITER_EQ, key, rv);
+			     mem, ITER_EQ, key, hint, rv);
 	struct vy_history mem_history;
 	vy_history_create(&mem_history, &lsm->env->history_node_pool);
 	int rc = vy_mem_iterator_next(&mem_itr, &mem_history);
@@ -113,16 +115,17 @@ vy_point_lookup_scan_mem(struct vy_lsm *lsm, struct vy_mem *mem,
  */
 static int
 vy_point_lookup_scan_mems(struct vy_lsm *lsm, const struct vy_read_view **rv,
-			  struct tuple *key, struct vy_history *history)
+			  struct tuple *key, hint_t hint,
+			  struct vy_history *history)
 {
 	assert(lsm->mem != NULL);
-	int rc = vy_point_lookup_scan_mem(lsm, lsm->mem, rv, key, history);
+	int rc = vy_point_lookup_scan_mem(lsm, lsm->mem, rv, key, hint, history);
 	struct vy_mem *mem;
 	rlist_foreach_entry(mem, &lsm->sealed, in_sealed) {
 		if (rc != 0 || vy_history_is_terminal(history))
 			return rc;
 
-		rc = vy_point_lookup_scan_mem(lsm, mem, rv, key, history);
+		rc = vy_point_lookup_scan_mem(lsm, mem, rv, key, hint, history);
 	}
 	return 0;
 }
@@ -134,7 +137,7 @@ vy_point_lookup_scan_mems(struct vy_lsm *lsm, const struct vy_read_view **rv,
 static int
 vy_point_lookup_scan_slice(struct vy_lsm *lsm, struct vy_slice *slice,
 			   const struct vy_read_view **rv, struct tuple *key,
-			   struct vy_history *history)
+			   hint_t hint, struct vy_history *history)
 {
 	/*
 	 * The format of the statement must be exactly the space
@@ -143,7 +146,7 @@ vy_point_lookup_scan_slice(struct vy_lsm *lsm, struct vy_slice *slice,
 	 */
 	struct vy_run_iterator run_itr;
 	vy_run_iterator_open(&run_itr, &lsm->stat.disk.iterator, slice,
-			     ITER_EQ, key, rv, lsm->cmp_def, lsm->key_def,
+			     ITER_EQ, key, hint, rv, lsm->cmp_def, lsm->key_def,
 			     lsm->disk_format);
 	struct vy_history slice_history;
 	vy_history_create(&slice_history, &lsm->env->history_node_pool);
@@ -185,8 +188,8 @@ vy_point_lookup_scan_slices(struct vy_lsm *lsm, const struct vy_read_view **rv,
 	int rc = 0;
 	for (i = 0; i < slice_count; i++) {
 		if (rc == 0 && !vy_history_is_terminal(history))
-			rc = vy_point_lookup_scan_slice(lsm, slices[i],
-							rv, key, history);
+			rc = vy_point_lookup_scan_slice(lsm, slices[i], rv,
+							key, hint, history);
 		vy_slice_unpin(slices[i]);
 	}
 	return rc;
@@ -219,12 +222,12 @@ vy_point_lookup(struct vy_lsm *lsm, struct vy_tx *tx,
 	if (rc != 0 || vy_history_is_terminal(&history))
 		goto done;
 
-	rc = vy_point_lookup_scan_cache(lsm, rv, key, &history);
+	rc = vy_point_lookup_scan_cache(lsm, rv, key, hint, &history);
 	if (rc != 0 || vy_history_is_terminal(&history))
 		goto done;
 
 restart:
-	rc = vy_point_lookup_scan_mems(lsm, rv, key, &mem_history);
+	rc = vy_point_lookup_scan_mems(lsm, rv, key, hint, &mem_history);
 	if (rc != 0 || vy_history_is_terminal(&mem_history))
 		goto done;
 
@@ -276,7 +279,7 @@ restart:
 		 * matching the search key.
 		 */
 		vy_history_cleanup(&mem_history);
-		rc = vy_point_lookup_scan_mems(lsm, rv, key, &mem_history);
+		rc = vy_point_lookup_scan_mems(lsm, rv, key, hint, &mem_history);
 		if (rc != 0)
 			goto done;
 		if (vy_history_is_terminal(&mem_history))
@@ -288,9 +291,10 @@ done:
 	vy_history_splice(&history, &disk_history);
 
 	if (rc == 0) {
+		hint_t unused;
 		int upserts_applied;
-		rc = vy_history_apply(&history, lsm->cmp_def,
-				      false, &upserts_applied, ret);
+		rc = vy_history_apply(&history, lsm->cmp_def, false,
+				      &upserts_applied, ret, &unused);
 		lsm->stat.upsert.applied += upserts_applied;
 	}
 	vy_history_cleanup(&history);
@@ -323,11 +327,13 @@ vy_point_lookup_mem(struct vy_lsm *lsm, const struct vy_read_view **rv,
 	struct vy_history history;
 	vy_history_create(&history, &lsm->env->history_node_pool);
 
-	rc = vy_point_lookup_scan_cache(lsm, rv, key, &history);
+	hint_t hint = vy_stmt_hint(key, lsm->cmp_def);
+
+	rc = vy_point_lookup_scan_cache(lsm, rv, key, hint, &history);
 	if (rc != 0 || vy_history_is_terminal(&history))
 		goto done;
 
-	rc = vy_point_lookup_scan_mems(lsm, rv, key, &history);
+	rc = vy_point_lookup_scan_mems(lsm, rv, key, hint, &history);
 	if (rc != 0 || vy_history_is_terminal(&history))
 		goto done;
 
@@ -335,9 +341,10 @@ vy_point_lookup_mem(struct vy_lsm *lsm, const struct vy_read_view **rv,
 	goto out;
 done:
 	if (rc == 0) {
+		hint_t unused;
 		int upserts_applied;
-		rc = vy_history_apply(&history, lsm->cmp_def,
-				      true, &upserts_applied, ret);
+		rc = vy_history_apply(&history, lsm->cmp_def, true,
+				      &upserts_applied, ret, &unused);
 		lsm->stat.upsert.applied += upserts_applied;
 	}
 out:
diff --git a/src/box/vy_read_iterator.c b/src/box/vy_read_iterator.c
index f1d8c8e4..b96a5d19 100644
--- a/src/box/vy_read_iterator.c
+++ b/src/box/vy_read_iterator.c
@@ -141,24 +141,28 @@ vy_read_iterator_unpin_slices(struct vy_read_iterator *itr)
  */
 static bool
 vy_read_iterator_range_is_done(struct vy_read_iterator *itr,
-			       struct tuple *next_key)
+			       struct tuple *next_key, hint_t next_hint)
 {
 	struct vy_range *range = itr->curr_range;
 	struct key_def *cmp_def = itr->lsm->cmp_def;
 	int dir = iterator_direction(itr->iterator_type);
 
 	if (dir > 0 && range->end != NULL &&
-	    (next_key == NULL || vy_stmt_compare(next_key, range->end,
-						 cmp_def) >= 0) &&
+	    (next_key == NULL ||
+	     vy_stmt_compare_hinted(next_key, next_hint, range->end,
+				    range->end_hint, cmp_def) >= 0) &&
 	    (itr->iterator_type != ITER_EQ ||
-	     vy_stmt_compare(itr->key, range->end, cmp_def) >= 0))
+	     vy_stmt_compare_hinted(itr->key, itr->hint, range->end,
+				    range->end_hint, cmp_def) >= 0))
 		return true;
 
 	if (dir < 0 && range->begin != NULL &&
-	    (next_key == NULL || vy_stmt_compare(next_key, range->begin,
-						 cmp_def) < 0) &&
+	    (next_key == NULL ||
+	     vy_stmt_compare_hinted(next_key, next_hint, range->begin,
+				    range->begin_hint, cmp_def) < 0) &&
 	    (itr->iterator_type != ITER_REQ ||
-	     vy_stmt_compare(itr->key, range->begin, cmp_def) <= 0))
+	     vy_stmt_compare_hinted(itr->key, itr->hint, range->begin,
+				    range->begin_hint, cmp_def) <= 0))
 		return true;
 
 	return false;
@@ -176,7 +180,8 @@ vy_read_iterator_range_is_done(struct vy_read_iterator *itr,
  */
 static inline int
 vy_read_iterator_cmp_stmt(struct vy_read_iterator *itr,
-			  const struct tuple *a, const struct tuple *b)
+			  const struct tuple *a, hint_t a_hint,
+			  const struct tuple *b, hint_t b_hint)
 {
 	if (a == NULL && b != NULL)
 		return 1;
@@ -185,7 +190,7 @@ vy_read_iterator_cmp_stmt(struct vy_read_iterator *itr,
 	if (a == NULL && b == NULL)
 		return 0;
 	return iterator_direction(itr->iterator_type) *
-		vy_stmt_compare(a, b, itr->lsm->cmp_def);
+		vy_stmt_compare_hinted(a, a_hint, b, b_hint, itr->lsm->cmp_def);
 }
 
 /**
@@ -194,9 +199,8 @@ vy_read_iterator_cmp_stmt(struct vy_read_iterator *itr,
  */
 static bool
 vy_read_iterator_is_exact_match(struct vy_read_iterator *itr,
-				struct tuple *stmt)
+				struct tuple *stmt, hint_t hint)
 {
-	struct tuple *key = itr->key;
 	enum iterator_type type = itr->iterator_type;
 	struct key_def *cmp_def = itr->lsm->cmp_def;
 
@@ -208,8 +212,9 @@ vy_read_iterator_is_exact_match(struct vy_read_iterator *itr,
 	return itr->last_stmt == NULL && stmt != NULL &&
 		(type == ITER_EQ || type == ITER_REQ ||
 		 type == ITER_GE || type == ITER_LE) &&
-		vy_stmt_is_full_key(key, cmp_def) &&
-		vy_stmt_compare(stmt, key, cmp_def) == 0;
+		vy_stmt_is_full_key(itr->key, cmp_def) &&
+		vy_stmt_compare_hinted(stmt, hint, itr->key,
+				       itr->hint, cmp_def) == 0;
 }
 
 /**
@@ -222,14 +227,18 @@ vy_read_iterator_is_exact_match(struct vy_read_iterator *itr,
 static void
 vy_read_iterator_evaluate_src(struct vy_read_iterator *itr,
 			      struct vy_read_src *src,
-			      struct tuple **next_key, bool *stop)
+			      struct tuple **next_key, hint_t *next_hint,
+			      bool *stop)
 {
 	uint32_t src_id = src - itr->src;
-	struct tuple *stmt = vy_history_last_stmt(&src->history);
-	int cmp = vy_read_iterator_cmp_stmt(itr, stmt, *next_key);
+	hint_t hint;
+	struct tuple *stmt = vy_history_last_stmt(&src->history, &hint);
+	int cmp = vy_read_iterator_cmp_stmt(itr, stmt, hint,
+					    *next_key, *next_hint);
 	if (cmp < 0) {
 		assert(stmt != NULL);
 		*next_key = stmt;
+		*next_hint = hint;
 		itr->front_id++;
 	}
 	if (cmp <= 0)
@@ -238,7 +247,7 @@ vy_read_iterator_evaluate_src(struct vy_read_iterator *itr,
 	itr->skipped_src = MAX(itr->skipped_src, src_id + 1);
 
 	if (cmp < 0 && vy_history_is_terminal(&src->history) &&
-	    vy_read_iterator_is_exact_match(itr, stmt)) {
+	    vy_read_iterator_is_exact_match(itr, stmt, hint)) {
 		itr->skipped_src = src_id + 1;
 		*stop = true;
 	}
@@ -270,7 +279,8 @@ vy_read_iterator_evaluate_src(struct vy_read_iterator *itr,
 
 static NODISCARD int
 vy_read_iterator_scan_txw(struct vy_read_iterator *itr,
-			  struct tuple **next_key, bool *stop)
+			  struct tuple **next_key, hint_t *next_hint,
+			  bool *stop)
 {
 	struct vy_read_src *src = &itr->src[itr->txw_src];
 	struct vy_txw_iterator *src_itr = &src->txw_iterator;
@@ -281,11 +291,11 @@ vy_read_iterator_scan_txw(struct vy_read_iterator *itr,
 	assert(itr->txw_src < itr->skipped_src);
 
 	int rc = vy_txw_iterator_restore(src_itr, itr->last_stmt,
-					 &src->history);
+					 itr->last_hint, &src->history);
 	if (rc == 0) {
 		if (!src->is_started) {
 			rc = vy_txw_iterator_skip(src_itr, itr->last_stmt,
-						  &src->history);
+						  itr->last_hint, &src->history);
 		} else if (src->front_id == itr->prev_front_id) {
 			rc = vy_txw_iterator_next(src_itr, &src->history);
 		}
@@ -294,24 +304,27 @@ vy_read_iterator_scan_txw(struct vy_read_iterator *itr,
 	if (rc < 0)
 		return -1;
 
-	vy_read_iterator_evaluate_src(itr, src, next_key, stop);
+	vy_read_iterator_evaluate_src(itr, src, next_key, next_hint, stop);
 	return 0;
 }
 
 static NODISCARD int
 vy_read_iterator_scan_cache(struct vy_read_iterator *itr,
-			    struct tuple **next_key, bool *stop)
+			    struct tuple **next_key, hint_t *next_hint,
+			    bool *stop)
 {
 	bool is_interval = false;
 	struct vy_read_src *src = &itr->src[itr->cache_src];
 	struct vy_cache_iterator *src_itr = &src->cache_iterator;
 
 	int rc = vy_cache_iterator_restore(src_itr, itr->last_stmt,
-					   &src->history, &is_interval);
+					   itr->last_hint, &src->history,
+					   &is_interval);
 	if (rc == 0) {
 		if (!src->is_started || itr->cache_src >= itr->skipped_src) {
 			rc = vy_cache_iterator_skip(src_itr, itr->last_stmt,
-						&src->history, &is_interval);
+						    itr->last_hint, &src->history,
+						    &is_interval);
 		} else if (src->front_id == itr->prev_front_id) {
 			rc = vy_cache_iterator_next(src_itr, &src->history,
 						    &is_interval);
@@ -321,7 +334,7 @@ vy_read_iterator_scan_cache(struct vy_read_iterator *itr,
 	if (rc < 0)
 		return -1;
 
-	vy_read_iterator_evaluate_src(itr, src, next_key, stop);
+	vy_read_iterator_evaluate_src(itr, src, next_key, next_hint, stop);
 	if (is_interval) {
 		itr->skipped_src = itr->cache_src + 1;
 		*stop = true;
@@ -331,7 +344,8 @@ vy_read_iterator_scan_cache(struct vy_read_iterator *itr,
 
 static NODISCARD int
 vy_read_iterator_scan_mem(struct vy_read_iterator *itr, uint32_t mem_src,
-			  struct tuple **next_key, bool *stop)
+			  struct tuple **next_key, hint_t *next_hint,
+			  bool *stop)
 {
 	int rc;
 	struct vy_read_src *src = &itr->src[mem_src];
@@ -339,11 +353,12 @@ vy_read_iterator_scan_mem(struct vy_read_iterator *itr, uint32_t mem_src,
 
 	assert(mem_src >= itr->mem_src && mem_src < itr->disk_src);
 
-	rc = vy_mem_iterator_restore(src_itr, itr->last_stmt, &src->history);
+	rc = vy_mem_iterator_restore(src_itr, itr->last_stmt, itr->last_hint,
+				     &src->history);
 	if (rc == 0) {
 		if (!src->is_started || mem_src >= itr->skipped_src) {
 			rc = vy_mem_iterator_skip(src_itr, itr->last_stmt,
-						  &src->history);
+						  itr->last_hint, &src->history);
 		} else if (src->front_id == itr->prev_front_id) {
 			rc = vy_mem_iterator_next(src_itr, &src->history);
 		}
@@ -352,13 +367,14 @@ vy_read_iterator_scan_mem(struct vy_read_iterator *itr, uint32_t mem_src,
 	if (rc < 0)
 		return -1;
 
-	vy_read_iterator_evaluate_src(itr, src, next_key, stop);
+	vy_read_iterator_evaluate_src(itr, src, next_key, next_hint, stop);
 	return 0;
 }
 
 static NODISCARD int
 vy_read_iterator_scan_disk(struct vy_read_iterator *itr, uint32_t disk_src,
-			   struct tuple **next_key, bool *stop)
+			   struct tuple **next_key, hint_t *next_hint,
+			   bool *stop)
 {
 	int rc = 0;
 	struct vy_read_src *src = &itr->src[disk_src];
@@ -368,7 +384,7 @@ vy_read_iterator_scan_disk(struct vy_read_iterator *itr, uint32_t disk_src,
 
 	if (!src->is_started || disk_src >= itr->skipped_src)
 		rc = vy_run_iterator_skip(src_itr, itr->last_stmt,
-					  &src->history);
+					  itr->last_hint, &src->history);
 	else if (src->front_id == itr->prev_front_id)
 		rc = vy_run_iterator_next(src_itr, &src->history);
 	src->is_started = true;
@@ -376,7 +392,7 @@ vy_read_iterator_scan_disk(struct vy_read_iterator *itr, uint32_t disk_src,
 	if (rc < 0)
 		return -1;
 
-	vy_read_iterator_evaluate_src(itr, src, next_key, stop);
+	vy_read_iterator_evaluate_src(itr, src, next_key, next_hint, stop);
 	return 0;
 }
 
@@ -387,21 +403,22 @@ vy_read_iterator_scan_disk(struct vy_read_iterator *itr, uint32_t disk_src,
  */
 static NODISCARD int
 vy_read_iterator_restore_mem(struct vy_read_iterator *itr,
-			     struct tuple **next_key)
+			     struct tuple **next_key, hint_t *next_hint)
 {
 	int rc;
 	int cmp;
 	struct vy_read_src *src = &itr->src[itr->mem_src];
 
-	rc = vy_mem_iterator_restore(&src->mem_iterator,
-				     itr->last_stmt, &src->history);
+	rc = vy_mem_iterator_restore(&src->mem_iterator, itr->last_stmt,
+				     itr->last_hint, &src->history);
 	if (rc < 0)
 		return -1; /* memory allocation error */
 	if (rc == 0)
 		return 0; /* nothing changed */
 
-	struct tuple *stmt = vy_history_last_stmt(&src->history);
-	cmp = vy_read_iterator_cmp_stmt(itr, stmt, *next_key);
+	hint_t hint;
+	struct tuple *stmt = vy_history_last_stmt(&src->history, &hint);
+	cmp = vy_read_iterator_cmp_stmt(itr, stmt, hint, *next_key, *next_hint);
 	if (cmp > 0) {
 		/*
 		 * Memory trees are append-only so if the
@@ -417,6 +434,7 @@ vy_read_iterator_restore_mem(struct vy_read_iterator *itr,
 		 * candidate for the next key.
 		 */
 		*next_key = stmt;
+		*next_hint = hint;
 		itr->front_id++;
 	} else {
 		/*
@@ -475,17 +493,19 @@ restart:
 	 */
 	bool stop = false;
 	struct tuple *next_key = NULL;
-	if (vy_read_iterator_scan_txw(itr, &next_key, &stop) != 0)
+	hint_t next_hint = HINT_NONE;
+	if (vy_read_iterator_scan_txw(itr, &next_key, &next_hint, &stop) != 0)
 		return -1;
 	if (stop)
 		goto done;
-	if (vy_read_iterator_scan_cache(itr, &next_key, &stop) != 0)
+	if (vy_read_iterator_scan_cache(itr, &next_key, &next_hint, &stop) != 0)
 		return -1;
 	if (stop)
 		goto done;
 
 	for (uint32_t i = itr->mem_src; i < itr->disk_src; i++) {
-		if (vy_read_iterator_scan_mem(itr, i, &next_key, &stop) != 0)
+		if (vy_read_iterator_scan_mem(itr, i, &next_key, &next_hint,
+					      &stop) != 0)
 			return -1;
 		if (stop)
 			goto done;
@@ -494,7 +514,8 @@ rescan_disk:
 	/* The following code may yield as it needs to access disk. */
 	vy_read_iterator_pin_slices(itr);
 	for (uint32_t i = itr->disk_src; i < itr->src_count; i++) {
-		if (vy_read_iterator_scan_disk(itr, i, &next_key, &stop) != 0) {
+		if (vy_read_iterator_scan_disk(itr, i, &next_key, &next_hint,
+					       &stop) != 0) {
 			vy_read_iterator_unpin_slices(itr);
 			return -1;
 		}
@@ -531,13 +552,13 @@ rescan_disk:
 	 * as it is owned exclusively by the current fiber so the only
 	 * source to check is the active in-memory tree.
 	 */
-	if (vy_read_iterator_restore_mem(itr, &next_key) != 0)
+	if (vy_read_iterator_restore_mem(itr, &next_key, &next_hint) != 0)
 		return -1;
 	/*
 	 * Scan the next range in case we transgressed the current
 	 * range's boundaries.
 	 */
-	if (vy_read_iterator_range_is_done(itr, next_key)) {
+	if (vy_read_iterator_range_is_done(itr, next_key, next_hint)) {
 		vy_read_iterator_next_range(itr);
 		goto rescan_disk;
 	}
@@ -545,8 +566,9 @@ done:
 #ifndef NDEBUG
 	/* Check that the statement meets search criteria. */
 	if (next_key != NULL) {
-		int cmp = vy_stmt_compare(next_key, itr->key,
-					  itr->lsm->cmp_def);
+		int cmp = vy_stmt_compare_hinted(next_key, next_hint,
+						 itr->key, itr->hint,
+						 itr->lsm->cmp_def);
 		cmp *= iterator_direction(itr->iterator_type);
 		if (itr->iterator_type == ITER_GT ||
 		    itr->iterator_type == ITER_LT)
@@ -559,12 +581,13 @@ done:
 	 * and respects statement order.
 	 */
 	if (itr->last_stmt != NULL && next_key != NULL) {
-	       assert(vy_read_iterator_cmp_stmt(itr, next_key,
-						itr->last_stmt) > 0);
+	       assert(vy_read_iterator_cmp_stmt(itr, next_key, next_hint,
+					itr->last_stmt, itr->last_hint) > 0);
 	}
 #endif
 	if (itr->need_check_eq && next_key != NULL &&
-	    vy_stmt_compare(next_key, itr->key, itr->lsm->cmp_def) != 0)
+	    vy_stmt_compare_hinted(next_key, next_hint, itr->key, itr->hint,
+				   itr->lsm->cmp_def) != 0)
 		itr->front_id++;
 	return 0;
 }
@@ -578,7 +601,7 @@ vy_read_iterator_add_tx(struct vy_read_iterator *itr)
 	struct vy_txw_iterator_stat *stat = &itr->lsm->stat.txw.iterator;
 	struct vy_read_src *sub_src = vy_read_iterator_add_src(itr);
 	vy_txw_iterator_open(&sub_src->txw_iterator, stat, itr->tx, itr->lsm,
-			     iterator_type, itr->key);
+			     iterator_type, itr->key, itr->hint);
 }
 
 static void
@@ -589,7 +612,7 @@ vy_read_iterator_add_cache(struct vy_read_iterator *itr)
 	struct vy_read_src *sub_src = vy_read_iterator_add_src(itr);
 	vy_cache_iterator_open(&sub_src->cache_iterator,
 			       &itr->lsm->cache, iterator_type,
-			       itr->key, itr->read_view);
+			       itr->key, itr->hint, itr->read_view);
 }
 
 static void
@@ -604,14 +627,15 @@ vy_read_iterator_add_mem(struct vy_read_iterator *itr)
 	assert(lsm->mem != NULL);
 	sub_src = vy_read_iterator_add_src(itr);
 	vy_mem_iterator_open(&sub_src->mem_iterator, &lsm->stat.memory.iterator,
-			     lsm->mem, iterator_type, itr->key, itr->read_view);
+			     lsm->mem, iterator_type, itr->key, itr->hint,
+			     itr->read_view);
 	/* Add sealed in-memory indexes. */
 	struct vy_mem *mem;
 	rlist_foreach_entry(mem, &lsm->sealed, in_sealed) {
 		sub_src = vy_read_iterator_add_src(itr);
 		vy_mem_iterator_open(&sub_src->mem_iterator,
-				     &lsm->stat.memory.iterator,
-				     mem, iterator_type, itr->key,
+				     &lsm->stat.memory.iterator, mem,
+				     iterator_type, itr->key, itr->hint,
 				     itr->read_view);
 	}
 }
@@ -633,7 +657,7 @@ vy_read_iterator_add_disk(struct vy_read_iterator *itr)
 		struct vy_read_src *sub_src = vy_read_iterator_add_src(itr);
 		vy_run_iterator_open(&sub_src->run_iterator,
 				     &lsm->stat.disk.iterator, slice,
-				     iterator_type, itr->key,
+				     iterator_type, itr->key, itr->hint,
 				     itr->read_view, lsm->cmp_def,
 				     lsm->key_def, lsm->disk_format);
 	}
@@ -688,7 +712,9 @@ vy_read_iterator_open(struct vy_read_iterator *itr, struct vy_lsm *lsm,
 	itr->tx = tx;
 	itr->iterator_type = iterator_type;
 	itr->key = key;
+	itr->hint = vy_stmt_hint(key, lsm->cmp_def);
 	itr->read_view = rv;
+	itr->last_hint = HINT_NONE;
 
 	if (vy_stmt_is_empty_key(key)) {
 		/*
@@ -730,9 +756,15 @@ vy_read_iterator_restore(struct vy_read_iterator *itr)
 {
 	vy_read_iterator_cleanup(itr);
 
-	const struct tuple *key = itr->last_stmt != NULL ?
-				  itr->last_stmt : itr->key;
-	hint_t hint = vy_stmt_hint(key, itr->lsm->cmp_def);
+	hint_t hint;
+	const struct tuple *key;
+	if (itr->last_stmt != NULL) {
+		key = itr->last_stmt;
+		hint = itr->last_hint;
+	} else {
+		key = itr->key;
+		hint = itr->hint;
+	}
 
 	itr->mem_list_version = itr->lsm->mem_list_version;
 	itr->range_tree_version = itr->lsm->range_tree_version;
@@ -778,13 +810,17 @@ vy_read_iterator_next_range(struct vy_read_iterator *itr)
 		 * We could skip an entire range due to the cache.
 		 * Make sure the next statement falls in the range.
 		 */
-		if (dir > 0 && (range->end == NULL ||
-				vy_stmt_compare(itr->last_stmt, range->end,
-						cmp_def) < 0))
+		if (dir > 0 &&
+		    (range->end == NULL ||
+		     vy_stmt_compare_hinted(itr->last_stmt, itr->last_hint,
+					    range->end, range->end_hint,
+					    cmp_def) < 0))
 			break;
-		if (dir < 0 && (range->begin == NULL ||
-				vy_stmt_compare(itr->last_stmt, range->begin,
-						cmp_def) > 0))
+		if (dir < 0 &&
+		    (range->begin == NULL ||
+		     vy_stmt_compare_hinted(itr->last_stmt, itr->last_hint,
+					    range->begin, range->begin_hint,
+					    cmp_def) > 0))
 			break;
 	}
 	itr->curr_range = range;
@@ -805,7 +841,7 @@ vy_read_iterator_next_range(struct vy_read_iterator *itr)
  */
 static NODISCARD int
 vy_read_iterator_apply_history(struct vy_read_iterator *itr,
-			       struct tuple **ret)
+			       struct tuple **ret, hint_t *ret_hint)
 {
 	struct vy_lsm *lsm = itr->lsm;
 	struct vy_history history;
@@ -822,7 +858,7 @@ vy_read_iterator_apply_history(struct vy_read_iterator *itr,
 
 	int upserts_applied = 0;
 	int rc = vy_history_apply(&history, lsm->cmp_def,
-				  true, &upserts_applied, ret);
+				  true, &upserts_applied, ret, ret_hint);
 
 	lsm->stat.upsert.applied += upserts_applied;
 	vy_history_cleanup(&history);
@@ -865,13 +901,14 @@ vy_read_iterator_next(struct vy_read_iterator *itr, struct tuple **result)
 
 	struct vy_lsm *lsm = itr->lsm;
 	struct tuple *stmt;
+	hint_t hint;
 
 	if (itr->last_stmt == NULL)
 		lsm->stat.lookup++; /* first iteration */
 next_key:
 	if (vy_read_iterator_advance(itr) != 0)
 		return -1;
-	if (vy_read_iterator_apply_history(itr, &stmt) != 0)
+	if (vy_read_iterator_apply_history(itr, &stmt, &hint) != 0)
 		return -1;
 	if (vy_read_iterator_track_read(itr, stmt) != 0)
 		return -1;
@@ -879,6 +916,7 @@ next_key:
 	if (itr->last_stmt != NULL)
 		tuple_unref(itr->last_stmt);
 	itr->last_stmt = stmt;
+	itr->last_hint = hint;
 
 	if (stmt != NULL && vy_stmt_type(stmt) == IPROTO_DELETE) {
 		/*
diff --git a/src/box/vy_read_iterator.h b/src/box/vy_read_iterator.h
index baab8859..d8251372 100644
--- a/src/box/vy_read_iterator.h
+++ b/src/box/vy_read_iterator.h
@@ -34,6 +34,7 @@
 #include <stdint.h>
 #include <stdbool.h>
 
+#include "key_def.h"
 #include "iterator_type.h"
 #include "trivia/util.h"
 
@@ -55,6 +56,8 @@ struct vy_read_iterator {
 	enum iterator_type iterator_type;
 	/** Search key. */
 	struct tuple *key;
+	/** Comparison hint of the search key. */
+	hint_t hint;
 	/** Read view the iterator lives in. */
 	const struct vy_read_view **read_view;
 	/**
@@ -64,6 +67,8 @@ struct vy_read_iterator {
 	bool need_check_eq;
 	/** Last statement returned by vy_read_iterator_next(). */
 	struct tuple *last_stmt;
+	/** Comparison hint of the last statement. */
+	hint_t last_hint;
 	/**
 	 * Last statement added to the tuple cache by
 	 * vy_read_iterator_cache_add().
diff --git a/src/box/vy_run.c b/src/box/vy_run.c
index 9608e207..897ece2a 100644
--- a/src/box/vy_run.c
+++ b/src/box/vy_run.c
@@ -1184,12 +1184,14 @@ vy_run_iterator_next_pos(struct vy_run_iterator *itr,
  * Affects: curr_loaded_page, curr_pos
  */
 static NODISCARD int
-vy_run_iterator_find_lsn(struct vy_run_iterator *itr, struct tuple **ret)
+vy_run_iterator_find_lsn(struct vy_run_iterator *itr,
+			 struct tuple **ret, hint_t *ret_hint)
 {
 	struct vy_slice *slice = itr->slice;
 	struct key_def *cmp_def = itr->cmp_def;
 
 	*ret = NULL;
+	*ret_hint = HINT_NONE;
 
 	assert(itr->search_started);
 	assert(itr->curr_stmt != NULL);
@@ -1261,6 +1263,7 @@ vy_run_iterator_find_lsn(struct vy_run_iterator *itr, struct tuple **ret)
 	}
 	vy_stmt_counter_acct_tuple(&itr->stat->get, itr->curr_stmt);
 	*ret = itr->curr_stmt;
+	*ret_hint = itr->curr_hint;
 	return 0;
 }
 
@@ -1333,7 +1336,7 @@ 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,
-		     hint_t last_hint, struct tuple **ret)
+		     hint_t last_hint, struct tuple **ret, hint_t *ret_hint)
 {
 	struct key_def *cmp_def = itr->cmp_def;
 	struct vy_slice *slice = itr->slice;
@@ -1343,6 +1346,7 @@ vy_run_iterator_seek(struct vy_run_iterator *itr, const struct tuple *last_key,
 	enum iterator_type iterator_type = itr->iterator_type;
 
 	*ret = NULL;
+	*ret_hint = HINT_NONE;
 	assert(itr->search_started);
 
 	/* Check the bloom filter on the first iteration. */
@@ -1452,7 +1456,7 @@ vy_run_iterator_seek(struct vy_run_iterator *itr, const struct tuple *last_key,
 		goto not_found;
 
 	/* Skip statements invisible from the iterator read view. */
-	return vy_run_iterator_find_lsn(itr, ret);
+	return vy_run_iterator_find_lsn(itr, ret, ret_hint);
 
 not_found:
 	if (check_bloom)
@@ -1469,7 +1473,8 @@ void
 vy_run_iterator_open(struct vy_run_iterator *itr,
 		     struct vy_run_iterator_stat *stat,
 		     struct vy_slice *slice, enum iterator_type iterator_type,
-		     const struct tuple *key, const struct vy_read_view **rv,
+		     const struct tuple *key, hint_t hint,
+		     const struct vy_read_view **rv,
 		     struct key_def *cmp_def, struct key_def *key_def,
 		     struct tuple_format *format)
 {
@@ -1481,7 +1486,7 @@ 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->hint = hint;
 	itr->read_view = rv;
 
 	itr->curr_stmt = NULL;
@@ -1508,13 +1513,16 @@ vy_run_iterator_open(struct vy_run_iterator *itr,
  * Returns 0 on success, -1 on memory allocation or IO error.
  */
 static NODISCARD int
-vy_run_iterator_next_key(struct vy_run_iterator *itr, struct tuple **ret)
+vy_run_iterator_next_key(struct vy_run_iterator *itr, struct tuple **ret,
+			 hint_t *ret_hint)
 {
 	*ret = NULL;
+	*ret_hint = HINT_NONE;
 
 	if (!itr->search_started) {
 		itr->search_started = true;
-		return vy_run_iterator_seek(itr, NULL, HINT_NONE, ret);
+		return vy_run_iterator_seek(itr, NULL, HINT_NONE,
+					    ret, ret_hint);
 	}
 	if (itr->curr_stmt == NULL)
 		return 0;
@@ -1548,7 +1556,7 @@ vy_run_iterator_next_key(struct vy_run_iterator *itr, struct tuple **ret)
 		vy_run_iterator_stop(itr);
 		return 0;
 	}
-	return vy_run_iterator_find_lsn(itr, ret);
+	return vy_run_iterator_find_lsn(itr, ret, ret_hint);
 }
 
 /**
@@ -1557,9 +1565,11 @@ vy_run_iterator_next_key(struct vy_run_iterator *itr, struct tuple **ret)
  * Returns 0 on success, -1 on memory allocation or IO error.
  */
 static NODISCARD int
-vy_run_iterator_next_lsn(struct vy_run_iterator *itr, struct tuple **ret)
+vy_run_iterator_next_lsn(struct vy_run_iterator *itr, struct tuple **ret,
+			 hint_t *ret_hint)
 {
 	*ret = NULL;
+	*ret_hint = HINT_NONE;
 
 	assert(itr->search_started);
 	assert(itr->curr_stmt != NULL);
@@ -1592,6 +1602,7 @@ next:
 
 	vy_stmt_counter_acct_tuple(&itr->stat->get, itr->curr_stmt);
 	*ret = itr->curr_stmt;
+	*ret_hint = itr->curr_hint;
 	return 0;
 }
 
@@ -1600,15 +1611,16 @@ vy_run_iterator_next(struct vy_run_iterator *itr,
 		     struct vy_history *history)
 {
 	vy_history_cleanup(history);
+	hint_t hint;
 	struct tuple *stmt;
-	if (vy_run_iterator_next_key(itr, &stmt) != 0)
+	if (vy_run_iterator_next_key(itr, &stmt, &hint) != 0)
 		return -1;
 	while (stmt != NULL) {
-		if (vy_history_append_stmt(history, stmt) != 0)
+		if (vy_history_append_stmt(history, stmt, hint) != 0)
 			return -1;
 		if (vy_history_is_terminal(history))
 			break;
-		if (vy_run_iterator_next_lsn(itr, &stmt) != 0)
+		if (vy_run_iterator_next_lsn(itr, &stmt, &hint) != 0)
 			return -1;
 	}
 	return 0;
@@ -1616,11 +1628,9 @@ vy_run_iterator_next(struct vy_run_iterator *itr,
 
 NODISCARD int
 vy_run_iterator_skip(struct vy_run_iterator *itr,
-		     const struct tuple *last_stmt,
+		     const struct tuple *last_stmt, hint_t last_hint,
 		     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.
@@ -1635,16 +1645,17 @@ vy_run_iterator_skip(struct vy_run_iterator *itr,
 	vy_history_cleanup(history);
 
 	itr->search_started = true;
+	hint_t hint;
 	struct tuple *stmt;
-	if (vy_run_iterator_seek(itr, last_stmt, last_hint, &stmt) != 0)
+	if (vy_run_iterator_seek(itr, last_stmt, last_hint, &stmt, &hint) != 0)
 		return -1;
 
 	while (stmt != NULL) {
-		if (vy_history_append_stmt(history, stmt) != 0)
+		if (vy_history_append_stmt(history, stmt, hint) != 0)
 			return -1;
 		if (vy_history_is_terminal(history))
 			break;
-		if (vy_run_iterator_next_lsn(itr, &stmt) != 0)
+		if (vy_run_iterator_next_lsn(itr, &stmt, &hint) != 0)
 			return -1;
 	}
 	return 0;
diff --git a/src/box/vy_run.h b/src/box/vy_run.h
index 369221ff..9f517978 100644
--- a/src/box/vy_run.h
+++ b/src/box/vy_run.h
@@ -530,7 +530,8 @@ void
 vy_run_iterator_open(struct vy_run_iterator *itr,
 		     struct vy_run_iterator_stat *stat,
 		     struct vy_slice *slice, enum iterator_type iterator_type,
-		     const struct tuple *key, const struct vy_read_view **rv,
+		     const struct tuple *key, hint_t hint,
+		     const struct vy_read_view **rv,
 		     struct key_def *cmp_def, struct key_def *key_def,
 		     struct tuple_format *format);
 
@@ -550,7 +551,7 @@ vy_run_iterator_next(struct vy_run_iterator *itr,
  */
 NODISCARD int
 vy_run_iterator_skip(struct vy_run_iterator *itr,
-		     const struct tuple *last_stmt,
+		     const struct tuple *last_stmt, hint_t last_hint,
 		     struct vy_history *history);
 
 /**
diff --git a/src/box/vy_tx.c b/src/box/vy_tx.c
index 596c7ed0..d8d7c905 100644
--- a/src/box/vy_tx.c
+++ b/src/box/vy_tx.c
@@ -1159,14 +1159,14 @@ vy_txw_iterator_open(struct vy_txw_iterator *itr,
 		     struct vy_txw_iterator_stat *stat,
 		     struct vy_tx *tx, struct vy_lsm *lsm,
 		     enum iterator_type iterator_type,
-		     const struct tuple *key)
+		     const struct tuple *key, hint_t hint)
 {
 	itr->stat = stat;
 	itr->tx = tx;
 	itr->lsm = lsm;
 	itr->iterator_type = iterator_type;
 	itr->key = key;
-	itr->hint = vy_stmt_hint(key, lsm->cmp_def);
+	itr->hint = hint;
 	itr->version = UINT32_MAX;
 	itr->curr_txv = NULL;
 	itr->search_started = false;
@@ -1269,21 +1269,20 @@ out:
 	if (itr->curr_txv != NULL) {
 		vy_stmt_counter_acct_tuple(&itr->stat->get,
 					   itr->curr_txv->stmt);
-		return vy_history_append_stmt(history, itr->curr_txv->stmt);
+		return vy_history_append_stmt(history, itr->curr_txv->stmt,
+					      itr->curr_txv->hint);
 	}
 	return 0;
 }
 
 NODISCARD int
 vy_txw_iterator_skip(struct vy_txw_iterator *itr,
-		     const struct tuple *last_stmt,
+		     const struct tuple *last_stmt, hint_t last_hint,
 		     struct vy_history *history)
 {
 	assert(!itr->search_started ||
 	       itr->version == itr->tx->write_set_version);
 
-	hint_t last_hint = last_stmt == NULL ? HINT_NONE :
-			   vy_stmt_hint(last_stmt, itr->lsm->cmp_def);
 	/*
 	 * Check if the iterator is already positioned
 	 * at the statement following last_stmt.
@@ -1305,29 +1304,28 @@ vy_txw_iterator_skip(struct vy_txw_iterator *itr,
 	if (itr->curr_txv != NULL) {
 		vy_stmt_counter_acct_tuple(&itr->stat->get,
 					   itr->curr_txv->stmt);
-		return vy_history_append_stmt(history, itr->curr_txv->stmt);
+		return vy_history_append_stmt(history, itr->curr_txv->stmt,
+					      itr->curr_txv->hint);
 	}
 	return 0;
 }
 
 NODISCARD int
 vy_txw_iterator_restore(struct vy_txw_iterator *itr,
-			const struct tuple *last_stmt,
+			const struct tuple *last_stmt, hint_t last_hint,
 			struct vy_history *history)
 {
 	if (!itr->search_started || itr->version == itr->tx->write_set_version)
 		return 0;
 
-	hint_t last_hint = last_stmt == NULL ? HINT_NONE :
-			   vy_stmt_hint(last_stmt, itr->lsm->cmp_def);
-
 	vy_txw_iterator_seek(itr, last_stmt, last_hint);
 
 	vy_history_cleanup(history);
 	if (itr->curr_txv != NULL) {
 		vy_stmt_counter_acct_tuple(&itr->stat->get,
 					   itr->curr_txv->stmt);
-		if (vy_history_append_stmt(history, itr->curr_txv->stmt) != 0)
+		if (vy_history_append_stmt(history, itr->curr_txv->stmt,
+					   itr->curr_txv->hint) != 0)
 			return -1;
 	}
 	return 1;
diff --git a/src/box/vy_tx.h b/src/box/vy_tx.h
index 907957ae..f3b9eacc 100644
--- a/src/box/vy_tx.h
+++ b/src/box/vy_tx.h
@@ -442,7 +442,7 @@ vy_txw_iterator_open(struct vy_txw_iterator *itr,
 		     struct vy_txw_iterator_stat *stat,
 		     struct vy_tx *tx, struct vy_lsm *lsm,
 		     enum iterator_type iterator_type,
-		     const struct tuple *key);
+		     const struct tuple *key, hint_t hint);
 
 /**
  * Advance a txw iterator to the next key.
@@ -460,7 +460,7 @@ vy_txw_iterator_next(struct vy_txw_iterator *itr,
  */
 NODISCARD int
 vy_txw_iterator_skip(struct vy_txw_iterator *itr,
-		     const struct tuple *last_stmt,
+		     const struct tuple *last_stmt, hint_t last_hint,
 		     struct vy_history *history);
 
 /**
@@ -471,7 +471,7 @@ vy_txw_iterator_skip(struct vy_txw_iterator *itr,
  */
 int
 vy_txw_iterator_restore(struct vy_txw_iterator *itr,
-			const struct tuple *last_stmt,
+			const struct tuple *last_stmt, hint_t last_hint,
 			struct vy_history *history);
 
 /**
diff --git a/test/unit/vy_cache.c b/test/unit/vy_cache.c
index d46d6c3f..d88ffc1a 100644
--- a/test/unit/vy_cache.c
+++ b/test/unit/vy_cache.c
@@ -85,16 +85,18 @@ test_basic()
 	struct vy_read_view rv;
 	rv.vlsn = INT64_MAX;
 	const struct vy_read_view *rv_p = &rv;
-	vy_cache_iterator_open(&itr, &cache, ITER_GE, select_all, &rv_p);
+	vy_cache_iterator_open(&itr, &cache, ITER_GE,
+			       select_all, HINT_NONE, &rv_p);
 
 	/* Start iterator and make several steps. */
+	hint_t hint;
 	struct tuple *ret;
 	bool unused;
 	struct vy_history history;
 	vy_history_create(&history, &history_node_pool);
 	for (int i = 0; i < 4; ++i)
 		vy_cache_iterator_next(&itr, &history, &unused);
-	ret = vy_history_last_stmt(&history);
+	ret = vy_history_last_stmt(&history, &hint);
 	ok(vy_stmt_are_same(ret, &chain1[3], format),
 	   "next_key * 4");
 
@@ -115,9 +117,11 @@ test_basic()
 	 * must be chain1[1].
 	 */
 	struct tuple *last_stmt = vy_new_simple_stmt(format, &chain1[0]);
-	ok(vy_cache_iterator_restore(&itr, last_stmt, &history, &unused) >= 0,
+	hint_t last_hint = vy_stmt_hint(last_stmt, key_def);
+	ok(vy_cache_iterator_restore(&itr, last_stmt, last_hint,
+				     &history, &unused) >= 0,
 	   "restore");
-	ret = vy_history_last_stmt(&history);
+	ret = vy_history_last_stmt(&history, &hint);
 	ok(vy_stmt_are_same(ret, &chain1[1], format),
 	   "restore on position after last");
 	tuple_unref(last_stmt);
diff --git a/test/unit/vy_mem.c b/test/unit/vy_mem.c
index 798c7a99..4453e076 100644
--- a/test/unit/vy_mem.c
+++ b/test/unit/vy_mem.c
@@ -100,11 +100,13 @@ test_iterator_restore_after_insertion()
 	end = mp_encode_uint(end, restore_on_value);
 	struct tuple *restore_on_key = vy_stmt_new_replace(format, data, end);
 	vy_stmt_set_lsn(restore_on_key, 100);
+	hint_t restore_on_hint = vy_stmt_hint(restore_on_key, key_def);
 	end = data;
 	end = mp_encode_array(end, 1);
 	end = mp_encode_uint(end, restore_on_value_reverse);
 	struct tuple *restore_on_key_reverse = vy_stmt_new_replace(format, data, end);
 	vy_stmt_set_lsn(restore_on_key_reverse, 100);
+	hint_t restore_on_hint_reverse = vy_stmt_hint(restore_on_key_reverse, key_def);
 
 	bool wrong_output = false;
 	int i_fail = 0;
@@ -187,13 +189,14 @@ test_iterator_restore_after_insertion()
 		rv.vlsn = 100;
 		const struct vy_read_view *prv = &rv;
 		vy_mem_iterator_open(&itr, &stats, mem,
-				     direct ? ITER_GE : ITER_LE, select_key,
-				     &prv);
+				     direct ? ITER_GE : ITER_LE,
+				     select_key, HINT_NONE, &prv);
+		hint_t hint;
 		struct tuple *t;
 		struct vy_history history;
 		vy_history_create(&history, &history_node_pool);
 		int rc = vy_mem_iterator_next(&itr, &history);
-		t = vy_history_last_stmt(&history);
+		t = vy_history_last_stmt(&history, &hint);
 		assert(rc == 0);
 		size_t j = 0;
 		while (t != NULL) {
@@ -214,7 +217,7 @@ test_iterator_restore_after_insertion()
 			else if(!direct && val <= middle_value)
 				break;
 			int rc = vy_mem_iterator_next(&itr, &history);
-			t = vy_history_last_stmt(&history);
+			t = vy_history_last_stmt(&history, &hint);
 			assert(rc == 0);
 		}
 		if (t == NULL && j != expected_count)
@@ -266,10 +269,13 @@ test_iterator_restore_after_insertion()
 		}
 
 		if (direct)
-			rc = vy_mem_iterator_restore(&itr, restore_on_key, &history);
+			rc = vy_mem_iterator_restore(&itr, restore_on_key,
+						     restore_on_hint, &history);
 		else
-			rc = vy_mem_iterator_restore(&itr, restore_on_key_reverse, &history);
-		t = vy_history_last_stmt(&history);
+			rc = vy_mem_iterator_restore(&itr, restore_on_key_reverse,
+						     restore_on_hint_reverse,
+						     &history);
+		t = vy_history_last_stmt(&history, &hint);
 
 		j = 0;
 		while (t != NULL) {
@@ -286,7 +292,7 @@ test_iterator_restore_after_insertion()
 			}
 			j++;
 			int rc = vy_mem_iterator_next(&itr, &history);
-			t = vy_history_last_stmt(&history);
+			t = vy_history_last_stmt(&history, &hint);
 			assert(rc == 0);
 		}
 		if (j != expected_count)
-- 
2.11.0