From: Vladimir Davydov <vdavydov.dev@gmail.com>
To: kostja@tarantool.org
Cc: tarantool-patches@freelists.org
Subject: [PATCH 09/12] vinyl: consolidate skip optimization checks in read iterator
Date: Sun, 15 Apr 2018 22:55:22 +0300 [thread overview]
Message-ID: <5ff19cf39854cc565022683b6dce48aeda904d2f.1523820298.git.vdavydov.dev@gmail.com> (raw)
In-Reply-To: <cover.1523820298.git.vdavydov.dev@gmail.com>
In-Reply-To: <cover.1523820298.git.vdavydov.dev@gmail.com>
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
next prev parent reply other threads:[~2018-04-15 19:55 UTC|newest]
Thread overview: 17+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-04-15 19:55 [PATCH 00/12] vinyl: prepare read iterator for index rebuild Vladimir Davydov
2018-04-15 19:55 ` [PATCH 01/12] vinyl: rename vy_stmt_history to vy_history Vladimir Davydov
2018-04-15 19:55 ` [PATCH 02/12] vinyl: factor out vy_history_apply from vy_point_lookup_apply_history Vladimir Davydov
2018-05-14 18:19 ` [tarantool-patches] " Vladislav Shpilevoy
2018-04-15 19:55 ` [PATCH 03/12] vinyl: add vy_history_append_stmt helper Vladimir Davydov
2018-04-15 19:55 ` [PATCH 04/12] vinyl: zap iterator_src_type enum Vladimir Davydov
2018-04-15 19:55 ` [PATCH 05/12] vinyl: encapsulate key history with struct Vladimir Davydov
2018-04-15 19:55 ` [PATCH 06/12] vinyl: refine vy_history_cleanup Vladimir Davydov
2018-04-15 19:55 ` [PATCH 07/12] vinyl: move vy_history to its own source file Vladimir Davydov
2018-04-15 19:55 ` [PATCH 08/12] vinyl: use mempool for vy_history_node allocations Vladimir Davydov
2018-04-15 19:55 ` Vladimir Davydov [this message]
2018-05-14 18:25 ` [tarantool-patches] Re: [PATCH 09/12] vinyl: consolidate skip optimization checks in read iterator Vladislav Shpilevoy
2018-05-15 15:00 ` Vladimir Davydov
2018-04-15 19:55 ` [PATCH 10/12] vinyl: refactor vy_read_iterator_next Vladimir Davydov
2018-04-15 19:55 ` [PATCH 11/12] vinyl: make read iterator always return newest tuple version Vladimir Davydov
2018-04-15 19:55 ` [PATCH 12/12] vinyl: zap vy_read_iterator::curr_stmt Vladimir Davydov
2018-05-04 18:05 ` [tarantool-patches] Re: [PATCH 00/12] vinyl: prepare read iterator for index rebuild Vladislav Shpilevoy
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=5ff19cf39854cc565022683b6dce48aeda904d2f.1523820298.git.vdavydov.dev@gmail.com \
--to=vdavydov.dev@gmail.com \
--cc=kostja@tarantool.org \
--cc=tarantool-patches@freelists.org \
--subject='Re: [PATCH 09/12] vinyl: consolidate skip optimization checks in read iterator' \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox