[PATCH 04/13] vinyl: store tuple comparison hints in tx read set

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

This patch incorporates tuple comparison hints into the transaction
read set. Now, beside a statement, each read interval also stores hints
of boundary statements, which are used in all comparison operations.

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_read_set.c | 19 ++++++++++++-------
 src/box/vy_read_set.h | 10 +++++++++-
 src/box/vy_tx.c       | 20 ++++++++++++++------
 3 files changed, 35 insertions(+), 14 deletions(-)

diff --git a/src/box/vy_read_set.c b/src/box/vy_read_set.c
index b95d2e4e..464ff060 100644
--- a/src/box/vy_read_set.c
+++ b/src/box/vy_read_set.c
@@ -46,7 +46,8 @@ vy_read_interval_cmpl(const struct vy_read_interval *a,
 {
 	assert(a->lsm == b->lsm);
 	struct key_def *cmp_def = a->lsm->cmp_def;
-	int cmp = vy_stmt_compare(a->left, b->left, cmp_def);
+	int cmp = vy_stmt_compare_hinted(a->left, a->left_hint,
+					 b->left, b->left_hint, cmp_def);
 	if (cmp != 0)
 		return cmp;
 	if (a->left_belongs && !b->left_belongs)
@@ -67,7 +68,8 @@ vy_read_interval_cmpr(const struct vy_read_interval *a,
 {
 	assert(a->lsm == b->lsm);
 	struct key_def *cmp_def = a->lsm->cmp_def;
-	int cmp = vy_stmt_compare(a->right, b->right, cmp_def);
+	int cmp = vy_stmt_compare_hinted(a->right, a->right_hint,
+					 b->right, b->right_hint, cmp_def);
 	if (cmp != 0)
 		return cmp;
 	if (a->right_belongs && !b->right_belongs)
@@ -89,7 +91,8 @@ vy_read_interval_should_merge(const struct vy_read_interval *l,
 	assert(l->lsm == r->lsm);
 	assert(vy_read_interval_cmpl(l, r) <= 0);
 	struct key_def *cmp_def = l->lsm->cmp_def;
-	int cmp = vy_stmt_compare(l->right, r->left, cmp_def);
+	int cmp = vy_stmt_compare_hinted(l->right, l->right_hint,
+					 r->left, r->left_hint, cmp_def);
 	if (cmp > 0)
 		return true;
 	if (cmp < 0)
@@ -118,7 +121,8 @@ vy_tx_conflict_iterator_next(struct vy_tx_conflict_iterator *it)
 		assert(left == NULL || left->lsm == curr->lsm);
 		assert(right == NULL || right->lsm == curr->lsm);
 
-		int cmp_right = vy_stmt_compare(it->stmt, last->right, cmp_def);
+		int cmp_right = vy_stmt_compare_hinted(it->stmt, it->hint,
+					last->right, last->right_hint, cmp_def);
 		if (cmp_right == 0 && !last->right_belongs)
 			cmp_right = 1;
 
@@ -137,7 +141,8 @@ vy_tx_conflict_iterator_next(struct vy_tx_conflict_iterator *it)
 			/* Optimize comparison out. */
 			cmp_left = cmp_right;
 		} else {
-			cmp_left = vy_stmt_compare(it->stmt, curr->left, cmp_def);
+			cmp_left = vy_stmt_compare_hinted(it->stmt, it->hint,
+					curr->left, curr->left_hint, cmp_def);
 			if (cmp_left == 0 && !curr->left_belongs)
 				cmp_left = -1;
 		}
@@ -164,8 +169,8 @@ vy_tx_conflict_iterator_next(struct vy_tx_conflict_iterator *it)
 			/* Optimize comparison out. */
 			cmp_right = cmp_left;
 		} else if (curr != last) {
-			cmp_right = vy_stmt_compare(it->stmt, curr->right,
-						    cmp_def);
+			cmp_right = vy_stmt_compare_hinted(it->stmt, it->hint,
+					curr->right, curr->right_hint, cmp_def);
 			if (cmp_right == 0 && !curr->right_belongs)
 				cmp_right = 1;
 		}
diff --git a/src/box/vy_read_set.h b/src/box/vy_read_set.h
index 1b139ccf..73d5dd4a 100644
--- a/src/box/vy_read_set.h
+++ b/src/box/vy_read_set.h
@@ -39,6 +39,7 @@
 #define RB_COMPACT 1
 #include <small/rb.h>
 
+#include "key_def.h"
 #include "salad/stailq.h"
 #include "trivia/util.h"
 
@@ -60,8 +61,12 @@ struct vy_read_interval {
 	struct vy_lsm *lsm;
 	/** Left boundary of the interval. */
 	struct tuple *left;
+	/** Left boundary statement hint. */
+	hint_t left_hint;
 	/** Right boundary of the interval. */
 	struct tuple *right;
+	/** Right boundary statement hint. */
+	hint_t right_hint;
 	/** Set if the left boundary belongs to the interval. */
 	bool left_belongs;
 	/** Set if the right boundary belongs to the interval. */
@@ -188,6 +193,8 @@ rb_gen_aug(MAYBE_UNUSED static inline, vy_lsm_read_set_, vy_lsm_read_set_t,
 struct vy_tx_conflict_iterator {
 	/** The statement. */
 	const struct tuple *stmt;
+	/** Statement comparison hint. */
+	hint_t hint;
 	/**
 	 * Iterator over the interval tree checked
 	 * for intersections with the statement.
@@ -203,11 +210,12 @@ struct vy_tx_conflict_iterator {
 static inline void
 vy_tx_conflict_iterator_init(struct vy_tx_conflict_iterator *it,
 			     vy_lsm_read_set_t *read_set,
-			     const struct tuple *stmt)
+			     const struct tuple *stmt, hint_t hint)
 {
 	vy_lsm_read_set_walk_init(&it->tree_walk, read_set);
 	it->tree_dir = 0;
 	it->stmt = stmt;
+	it->hint = hint;
 }
 
 /**
diff --git a/src/box/vy_tx.c b/src/box/vy_tx.c
index 6a464a1e..596c7ed0 100644
--- a/src/box/vy_tx.c
+++ b/src/box/vy_tx.c
@@ -277,8 +277,8 @@ vy_read_interval_unacct(struct vy_read_interval *interval)
 
 static struct vy_read_interval *
 vy_read_interval_new(struct vy_tx *tx, struct vy_lsm *lsm,
-		     struct tuple *left, bool left_belongs,
-		     struct tuple *right, bool right_belongs)
+		     struct tuple *left, hint_t left_hint, bool left_belongs,
+		     struct tuple *right, hint_t right_hint, bool right_belongs)
 {
 	struct tx_manager *xm = tx->xm;
 	struct vy_read_interval *interval;
@@ -293,9 +293,11 @@ vy_read_interval_new(struct vy_tx *tx, struct vy_lsm *lsm,
 	interval->lsm = lsm;
 	tuple_ref(left);
 	interval->left = left;
+	interval->left_hint = left_hint;
 	interval->left_belongs = left_belongs;
 	tuple_ref(right);
 	interval->right = right;
+	interval->right_hint = right_hint;
 	interval->right_belongs = right_belongs;
 	interval->subtree_last = NULL;
 	vy_read_interval_acct(interval);
@@ -392,7 +394,7 @@ static int
 vy_tx_send_to_read_view(struct vy_tx *tx, struct txv *v)
 {
 	struct vy_tx_conflict_iterator it;
-	vy_tx_conflict_iterator_init(&it, &v->lsm->read_set, v->stmt);
+	vy_tx_conflict_iterator_init(&it, &v->lsm->read_set, v->stmt, v->hint);
 	struct vy_tx *abort;
 	while ((abort = vy_tx_conflict_iterator_next(&it)) != NULL) {
 		/* Don't abort self. */
@@ -420,7 +422,7 @@ static void
 vy_tx_abort_readers(struct vy_tx *tx, struct txv *v)
 {
 	struct vy_tx_conflict_iterator it;
-	vy_tx_conflict_iterator_init(&it, &v->lsm->read_set, v->stmt);
+	vy_tx_conflict_iterator_init(&it, &v->lsm->read_set, v->stmt, v->hint);
 	struct vy_tx *abort;
 	while ((abort = vy_tx_conflict_iterator_next(&it)) != NULL) {
 		/* Don't abort self. */
@@ -928,9 +930,13 @@ vy_tx_track(struct vy_tx *tx, struct vy_lsm *lsm,
 		return 0;
 	}
 
+	hint_t left_hint = vy_stmt_hint(left, lsm->cmp_def);
+	hint_t right_hint = vy_stmt_hint(right, lsm->cmp_def);
+
 	struct vy_read_interval *new_interval;
-	new_interval = vy_read_interval_new(tx, lsm, left, left_belongs,
-					    right, right_belongs);
+	new_interval = vy_read_interval_new(tx, lsm, left, left_hint,
+					    left_belongs, right, right_hint,
+					    right_belongs);
 	if (new_interval == NULL)
 		return -1;
 
@@ -978,6 +984,7 @@ vy_tx_track(struct vy_tx *tx, struct vy_lsm *lsm,
 			tuple_ref(interval->left);
 			tuple_unref(new_interval->left);
 			new_interval->left = interval->left;
+			new_interval->left_hint = interval->left_hint;
 			new_interval->left_belongs = interval->left_belongs;
 		}
 		interval = stailq_last_entry(&merge, struct vy_read_interval,
@@ -986,6 +993,7 @@ vy_tx_track(struct vy_tx *tx, struct vy_lsm *lsm,
 			tuple_ref(interval->right);
 			tuple_unref(new_interval->right);
 			new_interval->right = interval->right;
+			new_interval->right_hint = interval->right_hint;
 			new_interval->right_belongs = interval->right_belongs;
 		}
 		struct vy_read_interval *next_interval;
-- 
2.11.0