[PATCH 09/12] vinyl: consolidate skip optimization checks in read iterator

Vladimir Davydov vdavydov.dev at gmail.com
Sun Apr 15 22:55:22 MSK 2018


Each kind of source iterator has 'skip' method, which is called to
position the iterator to a specified key. It is used to advance
sources that were skipped on the previous iteration (e.g. because
the result was found in the cache). The method has an optimization:
it avoids a lookup in the index if it is already positioned at a
statement following the specified key. This optimization makes the
method difficult to use if we want to keep a key history in each
source instead of a single statement, as we don't know whether 'skip'
changed the position or not and hence whether we need to rebuild key
history or not. Let's move the optimization to the read iterator and
make 'skip' plain and simple: let it always reposition the iterator
to the first statement following a given key.
---
 src/box/vy_cache.c         | 19 -------------------
 src/box/vy_mem.c           | 14 --------------
 src/box/vy_read_iterator.c | 23 ++++++++++++++++++++---
 src/box/vy_run.c           | 13 -------------
 src/box/vy_tx.c            | 14 --------------
 5 files changed, 20 insertions(+), 63 deletions(-)

diff --git a/src/box/vy_cache.c b/src/box/vy_cache.c
index 1c3e3692..d4cdcdff 100644
--- a/src/box/vy_cache.c
+++ b/src/box/vy_cache.c
@@ -703,25 +703,6 @@ vy_cache_iterator_skip(struct vy_cache_iterator *itr,
 
 	assert(!itr->search_started || itr->version == itr->cache->version);
 
-	/*
-	 * Check if the iterator is already positioned
-	 * at the statement following last_stmt.
-	 */
-	if (itr->search_started &&
-	    (itr->curr_stmt == NULL || last_stmt == NULL ||
-	     iterator_direction(itr->iterator_type) *
-	     vy_tuple_compare(itr->curr_stmt, last_stmt,
-			      itr->cache->cmp_def) > 0)) {
-		if (itr->curr_stmt == NULL)
-			return;
-		struct vy_cache_tree *tree = &itr->cache->cache_tree;
-		struct vy_cache_entry *entry =
-			*vy_cache_tree_iterator_get_elem(tree, &itr->curr_pos);
-		*ret = itr->curr_stmt;
-		*stop = vy_cache_iterator_is_stop(itr, entry);
-		return;
-	}
-
 	itr->search_started = true;
 	itr->version = itr->cache->version;
 	if (itr->curr_stmt != NULL)
diff --git a/src/box/vy_mem.c b/src/box/vy_mem.c
index 22cd33fa..9d40f76e 100644
--- a/src/box/vy_mem.c
+++ b/src/box/vy_mem.c
@@ -544,20 +544,6 @@ vy_mem_iterator_skip(struct vy_mem_iterator *itr,
 	*ret = NULL;
 	assert(!itr->search_started || itr->version == itr->mem->version);
 
-	/*
-	 * Check if the iterator is already positioned
-	 * at the statement following last_stmt.
-	 */
-	if (itr->search_started &&
-	    (itr->curr_stmt == NULL || last_stmt == NULL ||
-	     iterator_direction(itr->iterator_type) *
-	     vy_tuple_compare(itr->curr_stmt, last_stmt,
-			      itr->mem->cmp_def) > 0)) {
-		if (itr->curr_stmt != NULL)
-			*ret = itr->last_stmt;
-		return 0;
-	}
-
 	const struct tuple *key = itr->key;
 	enum iterator_type iterator_type = itr->iterator_type;
 	if (last_stmt != NULL) {
diff --git a/src/box/vy_read_iterator.c b/src/box/vy_read_iterator.c
index 2cad2337..548cf234 100644
--- a/src/box/vy_read_iterator.c
+++ b/src/box/vy_read_iterator.c
@@ -242,6 +242,23 @@ vy_read_iterator_evaluate_src(struct vy_read_iterator *itr,
 	}
 }
 
+/**
+ * Check if a read iterator source is behind the current read
+ * iterator position and hence needs to be fast-forwarded.
+ */
+static inline bool
+vy_read_src_is_behind(struct vy_read_iterator *itr, struct vy_read_src *src)
+{
+	uint32_t src_id = src - itr->src;
+	if (!src->is_started)
+		return true;
+	if (src_id < itr->skipped_src)
+		return false;
+	if (vy_read_iterator_cmp_stmt(itr, src->stmt, itr->last_stmt) > 0)
+		return false;
+	return true;
+}
+
 /*
  * Each of the functions from the vy_read_iterator_scan_* family
  * is used by vy_read_iterator_next_key() to:
@@ -300,7 +317,7 @@ vy_read_iterator_scan_cache(struct vy_read_iterator *itr, bool *stop)
 	int rc = vy_cache_iterator_restore(src_itr, itr->last_stmt,
 					   &src->stmt, &is_interval);
 	if (rc == 0) {
-		if (!src->is_started || itr->cache_src >= itr->skipped_src) {
+		if (vy_read_src_is_behind(itr, src)) {
 			vy_cache_iterator_skip(src_itr, itr->last_stmt,
 					       &src->stmt, &is_interval);
 		} else if (src->front_id == itr->prev_front_id) {
@@ -329,7 +346,7 @@ vy_read_iterator_scan_mem(struct vy_read_iterator *itr,
 
 	rc = vy_mem_iterator_restore(src_itr, itr->last_stmt, &src->stmt);
 	if (rc == 0) {
-		if (!src->is_started || mem_src >= itr->skipped_src) {
+		if (vy_read_src_is_behind(itr, src)) {
 			rc = vy_mem_iterator_skip(src_itr, itr->last_stmt,
 						  &src->stmt);
 		} else if (src->front_id == itr->prev_front_id) {
@@ -354,7 +371,7 @@ vy_read_iterator_scan_disk(struct vy_read_iterator *itr,
 
 	assert(disk_src >= itr->disk_src && disk_src < itr->src_count);
 
-	if (!src->is_started || disk_src >= itr->skipped_src)
+	if (vy_read_src_is_behind(itr, src))
 		rc = vy_run_iterator_skip(src_itr, itr->last_stmt, &src->stmt);
 	else if (src->front_id == itr->prev_front_id)
 		rc = vy_run_iterator_next_key(src_itr, &src->stmt);
diff --git a/src/box/vy_run.c b/src/box/vy_run.c
index 49caa341..fa5670d3 100644
--- a/src/box/vy_run.c
+++ b/src/box/vy_run.c
@@ -1485,19 +1485,6 @@ vy_run_iterator_skip(struct vy_run_iterator *itr,
 	if (itr->search_ended)
 		return 0;
 
-	/*
-	 * Check if the iterator is already positioned
-	 * at the statement following last_stmt.
-	 */
-	if (itr->search_started &&
-	    (itr->curr_stmt == NULL || last_stmt == NULL ||
-	     iterator_direction(itr->iterator_type) *
-	     vy_tuple_compare(itr->curr_stmt, last_stmt,
-			      itr->cmp_def) > 0)) {
-		*ret = itr->curr_stmt;
-		return 0;
-	}
-
 	const struct tuple *key = itr->key;
 	enum iterator_type iterator_type = itr->iterator_type;
 	if (last_stmt != NULL) {
diff --git a/src/box/vy_tx.c b/src/box/vy_tx.c
index 285af8a6..4812b794 100644
--- a/src/box/vy_tx.c
+++ b/src/box/vy_tx.c
@@ -979,20 +979,6 @@ vy_txw_iterator_skip(struct vy_txw_iterator *itr,
 	assert(!itr->search_started ||
 	       itr->version == itr->tx->write_set_version);
 
-	/*
-	 * Check if the iterator is already positioned
-	 * at the statement following last_stmt.
-	 */
-	if (itr->search_started &&
-	    (itr->curr_txv == NULL || last_stmt == NULL ||
-	     iterator_direction(itr->iterator_type) *
-	     vy_tuple_compare(itr->curr_txv->stmt, last_stmt,
-			      itr->lsm->cmp_def) > 0)) {
-		if (itr->curr_txv != NULL)
-			*ret = itr->curr_txv->stmt;
-		return;
-	}
-
 	const struct tuple *key = itr->key;
 	enum iterator_type iterator_type = itr->iterator_type;
 	if (last_stmt != NULL) {
-- 
2.11.0




More information about the Tarantool-patches mailing list