* [PATCH 1/6] vinyl: txw iterator: fold eq check in seek method
2019-03-26 15:50 [PATCH 0/6] vinyl: iterator cleanup Vladimir Davydov
@ 2019-03-26 15:50 ` Vladimir Davydov
2019-03-28 14:25 ` [tarantool-patches] " Konstantin Osipov
2019-03-26 15:50 ` [PATCH 2/6] vinyl: cache " Vladimir Davydov
` (5 subsequent siblings)
6 siblings, 1 reply; 17+ messages in thread
From: Vladimir Davydov @ 2019-03-26 15:50 UTC (permalink / raw)
To: tarantool-patches
We substitute iterator_type and key before each call to 'seek'
method and check eq constraint after it. Let's fold it to reduce
code duplication.
---
src/box/vy_tx.c | 53 ++++++++++++++++++-----------------------------------
1 file changed, 18 insertions(+), 35 deletions(-)
diff --git a/src/box/vy_tx.c b/src/box/vy_tx.c
index c4445505..02f5ca27 100644
--- a/src/box/vy_tx.c
+++ b/src/box/vy_tx.c
@@ -1111,17 +1111,24 @@ vy_txw_iterator_open(struct vy_txw_iterator *itr,
/**
* Position the iterator to the first entry in the transaction
- * write set satisfying the search criteria for a given key and
- * direction.
+ * write set satisfying the search criteria and following the
+ * given key (pass NULL to start iteration).
*/
static void
-vy_txw_iterator_seek(struct vy_txw_iterator *itr,
- enum iterator_type iterator_type,
- const struct tuple *key)
+vy_txw_iterator_seek(struct vy_txw_iterator *itr, const struct tuple *last_key)
{
itr->stat->lookup++;
itr->version = itr->tx->write_set_version;
itr->curr_txv = NULL;
+
+ const struct tuple *key = itr->key;
+ enum iterator_type iterator_type = itr->iterator_type;
+ if (last_key != NULL) {
+ key = last_key;
+ iterator_type = iterator_direction(iterator_type) > 0 ?
+ ITER_GT : ITER_LT;
+ }
+
struct vy_lsm *lsm = itr->lsm;
struct write_set_key k = { lsm, key };
struct txv *txv;
@@ -1162,6 +1169,9 @@ vy_txw_iterator_seek(struct vy_txw_iterator *itr,
}
if (txv == NULL || txv->lsm != lsm)
return;
+ if (itr->iterator_type == ITER_EQ && last_key != NULL &&
+ vy_stmt_compare(itr->key, txv->stmt, lsm->cmp_def) != 0)
+ return;
itr->curr_txv = txv;
}
@@ -1172,7 +1182,7 @@ vy_txw_iterator_next(struct vy_txw_iterator *itr,
vy_history_cleanup(history);
if (!itr->search_started) {
itr->search_started = true;
- vy_txw_iterator_seek(itr, itr->iterator_type, itr->key);
+ vy_txw_iterator_seek(itr, NULL);
goto out;
}
assert(itr->version == itr->tx->write_set_version);
@@ -1218,21 +1228,8 @@ vy_txw_iterator_skip(struct vy_txw_iterator *itr,
vy_history_cleanup(history);
- const struct tuple *key = itr->key;
- enum iterator_type iterator_type = itr->iterator_type;
- if (last_stmt != NULL) {
- key = last_stmt;
- iterator_type = iterator_direction(iterator_type) > 0 ?
- ITER_GT : ITER_LT;
- }
-
itr->search_started = true;
- vy_txw_iterator_seek(itr, iterator_type, key);
-
- if (itr->iterator_type == ITER_EQ && last_stmt != NULL &&
- itr->curr_txv != NULL && vy_stmt_compare(itr->key,
- itr->curr_txv->stmt, itr->lsm->cmp_def) != 0)
- itr->curr_txv = NULL;
+ vy_txw_iterator_seek(itr, last_stmt);
if (itr->curr_txv != NULL) {
vy_stmt_counter_acct_tuple(&itr->stat->get,
@@ -1250,22 +1247,8 @@ vy_txw_iterator_restore(struct vy_txw_iterator *itr,
if (!itr->search_started || itr->version == itr->tx->write_set_version)
return 0;
- const struct tuple *key = itr->key;
- enum iterator_type iterator_type = itr->iterator_type;
- if (last_stmt != NULL) {
- key = last_stmt;
- iterator_type = iterator_direction(iterator_type) > 0 ?
- ITER_GT : ITER_LT;
- }
-
struct txv *prev_txv = itr->curr_txv;
- vy_txw_iterator_seek(itr, iterator_type, key);
-
- if (itr->iterator_type == ITER_EQ && itr->curr_txv != NULL &&
- vy_stmt_compare(itr->key, itr->curr_txv->stmt,
- itr->lsm->cmp_def) != 0)
- itr->curr_txv = NULL;
-
+ vy_txw_iterator_seek(itr, last_stmt);
if (prev_txv == itr->curr_txv)
return 0;
--
2.11.0
^ permalink raw reply [flat|nested] 17+ messages in thread* [PATCH 2/6] vinyl: cache iterator: fold eq check in seek method
2019-03-26 15:50 [PATCH 0/6] vinyl: iterator cleanup Vladimir Davydov
2019-03-26 15:50 ` [PATCH 1/6] vinyl: txw iterator: fold eq check in seek method Vladimir Davydov
@ 2019-03-26 15:50 ` Vladimir Davydov
2019-03-28 14:27 ` [tarantool-patches] " Konstantin Osipov
2019-03-26 15:50 ` [PATCH 3/6] vinyl: cache iterator: consolidate curr_stmt updates Vladimir Davydov
` (4 subsequent siblings)
6 siblings, 1 reply; 17+ messages in thread
From: Vladimir Davydov @ 2019-03-26 15:50 UTC (permalink / raw)
To: tarantool-patches
We substitute iterator_type and key before each call to 'seek'
method and check eq constraint after it. Let's fold it to reduce
code duplication.
---
src/box/vy_cache.c | 82 ++++++++++++++++++++++++------------------------------
1 file changed, 37 insertions(+), 45 deletions(-)
diff --git a/src/box/vy_cache.c b/src/box/vy_cache.c
index 8354b1c2..b27e04a5 100644
--- a/src/box/vy_cache.c
+++ b/src/box/vy_cache.c
@@ -635,28 +635,34 @@ vy_cache_iterator_skip_to_read_view(struct vy_cache_iterator *itr, bool *stop)
/**
* Position the iterator to the first cache entry satisfying
- * the search criteria for a given key and direction.
+ * the iterator search criteria and following the given key
+ * (pass NULL to start iteration).
*/
static void
vy_cache_iterator_seek(struct vy_cache_iterator *itr,
- enum iterator_type iterator_type,
- const struct tuple *key,
- struct vy_cache_entry **entry)
+ const struct tuple *last_key,
+ struct vy_cache_entry **ret)
{
struct vy_cache_tree *tree = &itr->cache->cache_tree;
- *entry = NULL;
+ *ret = NULL;
itr->cache->stat.lookup++;
+ const struct tuple *key = itr->key;
+ enum iterator_type iterator_type = itr->iterator_type;
+ if (last_key != NULL) {
+ key = last_key;
+ iterator_type = iterator_direction(itr->iterator_type) > 0 ?
+ ITER_GT : ITER_LT;
+ }
+
+ bool exact;
if (!vy_stmt_is_empty_key(key)) {
- bool exact;
itr->curr_pos = iterator_type == ITER_EQ ||
iterator_type == ITER_GE ||
iterator_type == ITER_LT ?
vy_cache_tree_lower_bound(tree, key, &exact) :
vy_cache_tree_upper_bound(tree, key, &exact);
- if (iterator_type == ITER_EQ && !exact)
- return;
} else if (iterator_type == ITER_LE) {
itr->curr_pos = vy_cache_tree_invalid_iterator();
} else {
@@ -669,7 +675,16 @@ vy_cache_iterator_seek(struct vy_cache_iterator *itr,
if (vy_cache_tree_iterator_is_invalid(&itr->curr_pos))
return;
- *entry = *vy_cache_tree_iterator_get_elem(tree, &itr->curr_pos);
+ struct vy_cache_entry *entry;
+ entry = *vy_cache_tree_iterator_get_elem(tree, &itr->curr_pos);
+
+ if (itr->iterator_type == ITER_EQ &&
+ ((last_key == NULL && !exact) ||
+ (last_key != NULL && vy_stmt_compare(itr->key, entry->stmt,
+ itr->cache->cmp_def) != 0)))
+ return;
+
+ *ret = entry;
}
NODISCARD int
@@ -684,8 +699,7 @@ vy_cache_iterator_next(struct vy_cache_iterator *itr,
itr->search_started = true;
itr->version = itr->cache->version;
struct vy_cache_entry *entry;
- vy_cache_iterator_seek(itr, itr->iterator_type,
- itr->key, &entry);
+ vy_cache_iterator_seek(itr, NULL, &entry);
if (entry == NULL)
return 0;
itr->curr_stmt = entry->stmt;
@@ -735,22 +749,8 @@ vy_cache_iterator_skip(struct vy_cache_iterator *itr,
tuple_unref(itr->curr_stmt);
itr->curr_stmt = NULL;
- const struct tuple *key = itr->key;
- enum iterator_type iterator_type = itr->iterator_type;
- if (last_stmt != NULL) {
- key = last_stmt;
- iterator_type = iterator_direction(iterator_type) > 0 ?
- ITER_GT : ITER_LT;
- }
-
struct vy_cache_entry *entry;
- vy_cache_iterator_seek(itr, iterator_type, key, &entry);
-
- if (itr->iterator_type == ITER_EQ && last_stmt != NULL &&
- entry != NULL && vy_stmt_compare(itr->key, entry->stmt,
- itr->cache->cmp_def) != 0)
- entry = NULL;
-
+ vy_cache_iterator_seek(itr, last_stmt, &entry);
if (entry != NULL) {
*stop = vy_cache_iterator_is_stop(itr, entry);
itr->curr_stmt = entry->stmt;
@@ -771,9 +771,6 @@ vy_cache_iterator_restore(struct vy_cache_iterator *itr,
const struct tuple *last_stmt,
struct vy_history *history, bool *stop)
{
- struct key_def *def = itr->cache->cmp_def;
- int dir = iterator_direction(itr->iterator_type);
-
if (!itr->search_started || itr->version == itr->cache->version)
return 0;
@@ -782,13 +779,6 @@ vy_cache_iterator_restore(struct vy_cache_iterator *itr,
if (prev_stmt != NULL)
tuple_unref(prev_stmt);
- const struct tuple *key = itr->key;
- enum iterator_type iterator_type = itr->iterator_type;
- if (last_stmt != NULL) {
- key = last_stmt;
- iterator_type = dir > 0 ? ITER_GT : ITER_LT;
- }
-
if ((prev_stmt == NULL && itr->iterator_type == ITER_EQ) ||
(prev_stmt != NULL &&
prev_stmt != vy_cache_iterator_curr_stmt(itr))) {
@@ -798,13 +788,8 @@ vy_cache_iterator_restore(struct vy_cache_iterator *itr,
* search.
*/
struct vy_cache_entry *entry;
- vy_cache_iterator_seek(itr, iterator_type, key, &entry);
-
+ vy_cache_iterator_seek(itr, last_stmt, &entry);
itr->curr_stmt = NULL;
- if (entry != NULL && itr->iterator_type == ITER_EQ &&
- vy_stmt_compare(itr->key, entry->stmt, def) != 0)
- entry = NULL;
-
if (entry != NULL) {
*stop = vy_cache_iterator_is_stop(itr, entry);
itr->curr_stmt = entry->stmt;
@@ -817,11 +802,18 @@ vy_cache_iterator_restore(struct vy_cache_iterator *itr,
* and the current statement. Reposition to the
* statement closiest to last_stmt.
*/
+ bool key_belongs = false;
+ const struct tuple *key = last_stmt;
+ if (key == NULL) {
+ key = itr->key;
+ key_belongs = (itr->iterator_type == ITER_EQ ||
+ itr->iterator_type == ITER_GE ||
+ itr->iterator_type == ITER_LE);
+ }
+ int dir = iterator_direction(itr->iterator_type);
+ struct key_def *def = itr->cache->cmp_def;
struct vy_cache_tree *tree = &itr->cache->cache_tree;
struct vy_cache_tree_iterator pos = itr->curr_pos;
- bool key_belongs = (iterator_type == ITER_EQ ||
- iterator_type == ITER_GE ||
- iterator_type == ITER_LE);
if (prev_stmt == NULL)
pos = vy_cache_tree_invalid_iterator();
while (true) {
--
2.11.0
^ permalink raw reply [flat|nested] 17+ messages in thread* [PATCH 3/6] vinyl: cache iterator: consolidate curr_stmt updates
2019-03-26 15:50 [PATCH 0/6] vinyl: iterator cleanup Vladimir Davydov
2019-03-26 15:50 ` [PATCH 1/6] vinyl: txw iterator: fold eq check in seek method Vladimir Davydov
2019-03-26 15:50 ` [PATCH 2/6] vinyl: cache " Vladimir Davydov
@ 2019-03-26 15:50 ` Vladimir Davydov
2019-03-28 14:29 ` [tarantool-patches] " Konstantin Osipov
2019-03-26 15:50 ` [PATCH 4/6] vinyl: run iterator: zap search_ended flag Vladimir Davydov
` (3 subsequent siblings)
6 siblings, 1 reply; 17+ messages in thread
From: Vladimir Davydov @ 2019-03-26 15:50 UTC (permalink / raw)
To: tarantool-patches
Currently, vy_cache_iterator->curr_stmt is updated by top-level iterator
functions - next, skip, restore - which results in code duplication and
spreads core logic among multiple places. To reduce the amount of code
and make it generally easier to follow, this patch moves the updates to
low level functions - step, seek. It also makes the seek method return
the stop flag, which makes it similar to step, thus making the code more
consistent.
---
src/box/vy_cache.c | 87 ++++++++++++++++++++++--------------------------------
1 file changed, 36 insertions(+), 51 deletions(-)
diff --git a/src/box/vy_cache.c b/src/box/vy_cache.c
index b27e04a5..825bfd3b 100644
--- a/src/box/vy_cache.c
+++ b/src/box/vy_cache.c
@@ -581,20 +581,22 @@ vy_cache_iterator_is_end_stop(struct vy_cache_iterator *itr,
* Make one tree's iterator step from the current position.
* Direction of the step depends on the iterator type.
* @param itr Iterator to make step.
- * @param[out] ret Result tuple.
*
- * @retval Must a merge_iterator stop on @a ret?
- * The function is implicitly used by merge_iterator_next_key and
- * return value is used to determine if the merge_iterator can
- * return @a ret to a read_iterator immediately, without lookups
- * in mems and runs. It is possible, when @a ret is a part of
+ * @retval Must a read iterator stop on the cached statement?
+ * The function is implicitly used by vy_read_iterator_next and
+ * return value is used to determine if the read iterator can
+ * return the cached statement without lookups in mems and runs.
+ * It is possible when the cached statement is a part of a
* continuous cached tuples chain. In such a case mems or runs can
* not contain more suitable tuples.
*/
static inline bool
-vy_cache_iterator_step(struct vy_cache_iterator *itr, struct tuple **ret)
+vy_cache_iterator_step(struct vy_cache_iterator *itr)
{
- *ret = NULL;
+ if (itr->curr_stmt != NULL) {
+ tuple_unref(itr->curr_stmt);
+ itr->curr_stmt = NULL;
+ }
struct vy_cache_tree *tree = &itr->cache->cache_tree;
struct vy_cache_entry *prev_entry =
*vy_cache_tree_iterator_get_elem(tree, &itr->curr_pos);
@@ -611,7 +613,8 @@ vy_cache_iterator_step(struct vy_cache_iterator *itr, struct tuple **ret)
vy_stmt_compare(itr->key, entry->stmt, itr->cache->cmp_def)) {
return vy_cache_iterator_is_end_stop(itr, prev_entry);
}
- *ret = entry->stmt;
+ itr->curr_stmt = entry->stmt;
+ tuple_ref(itr->curr_stmt);
return vy_cache_iterator_is_stop(itr, entry);
}
@@ -629,7 +632,7 @@ vy_cache_iterator_skip_to_read_view(struct vy_cache_iterator *itr, bool *stop)
* but there could be older tuples in runs.
*/
*stop = false;
- vy_cache_iterator_step(itr, &itr->curr_stmt);
+ vy_cache_iterator_step(itr);
}
}
@@ -637,15 +640,21 @@ vy_cache_iterator_skip_to_read_view(struct vy_cache_iterator *itr, bool *stop)
* Position the iterator to the first cache entry satisfying
* the iterator search criteria and following the given key
* (pass NULL to start iteration).
+ *
+ * Like vy_cache_iterator_step(), this functions returns true
+ * if the cached statement is a part of a continuous tuple chain
+ * and hence the caller doesn't need to scan mems and runs.
*/
-static void
+static bool
vy_cache_iterator_seek(struct vy_cache_iterator *itr,
- const struct tuple *last_key,
- struct vy_cache_entry **ret)
+ const struct tuple *last_key)
{
struct vy_cache_tree *tree = &itr->cache->cache_tree;
- *ret = NULL;
+ if (itr->curr_stmt != NULL) {
+ tuple_unref(itr->curr_stmt);
+ itr->curr_stmt = NULL;
+ }
itr->cache->stat.lookup++;
const struct tuple *key = itr->key;
@@ -673,7 +682,7 @@ vy_cache_iterator_seek(struct vy_cache_iterator *itr,
if (iterator_type == ITER_LT || iterator_type == ITER_LE)
vy_cache_tree_iterator_prev(tree, &itr->curr_pos);
if (vy_cache_tree_iterator_is_invalid(&itr->curr_pos))
- return;
+ return false;
struct vy_cache_entry *entry;
entry = *vy_cache_tree_iterator_get_elem(tree, &itr->curr_pos);
@@ -682,39 +691,33 @@ vy_cache_iterator_seek(struct vy_cache_iterator *itr,
((last_key == NULL && !exact) ||
(last_key != NULL && vy_stmt_compare(itr->key, entry->stmt,
itr->cache->cmp_def) != 0)))
- return;
+ return false;
- *ret = entry;
+ itr->curr_stmt = entry->stmt;
+ tuple_ref(itr->curr_stmt);
+ return vy_cache_iterator_is_stop(itr, entry);
}
NODISCARD int
vy_cache_iterator_next(struct vy_cache_iterator *itr,
struct vy_history *history, bool *stop)
{
- *stop = false;
vy_history_cleanup(history);
if (!itr->search_started) {
assert(itr->curr_stmt == NULL);
itr->search_started = true;
itr->version = itr->cache->version;
- struct vy_cache_entry *entry;
- vy_cache_iterator_seek(itr, NULL, &entry);
- if (entry == NULL)
- return 0;
- itr->curr_stmt = entry->stmt;
- *stop = vy_cache_iterator_is_stop(itr, entry);
+ *stop = vy_cache_iterator_seek(itr, NULL);
} else {
assert(itr->version == itr->cache->version);
if (itr->curr_stmt == NULL)
return 0;
- tuple_unref(itr->curr_stmt);
- *stop = vy_cache_iterator_step(itr, &itr->curr_stmt);
+ *stop = vy_cache_iterator_step(itr);
}
vy_cache_iterator_skip_to_read_view(itr, stop);
if (itr->curr_stmt != NULL) {
- tuple_ref(itr->curr_stmt);
vy_stmt_counter_acct_tuple(&itr->cache->stat.get,
itr->curr_stmt);
return vy_history_append_stmt(history, itr->curr_stmt);
@@ -740,25 +743,14 @@ vy_cache_iterator_skip(struct vy_cache_iterator *itr,
itr->cache->cmp_def) > 0))
return 0;
- *stop = false;
vy_history_cleanup(history);
itr->search_started = true;
itr->version = itr->cache->version;
- if (itr->curr_stmt != NULL)
- tuple_unref(itr->curr_stmt);
- itr->curr_stmt = NULL;
-
- struct vy_cache_entry *entry;
- vy_cache_iterator_seek(itr, last_stmt, &entry);
- if (entry != NULL) {
- *stop = vy_cache_iterator_is_stop(itr, entry);
- itr->curr_stmt = entry->stmt;
- }
-
+ *stop = vy_cache_iterator_seek(itr, last_stmt);
vy_cache_iterator_skip_to_read_view(itr, stop);
+
if (itr->curr_stmt != NULL) {
- tuple_ref(itr->curr_stmt);
vy_stmt_counter_acct_tuple(&itr->cache->stat.get,
itr->curr_stmt);
return vy_history_append_stmt(history, itr->curr_stmt);
@@ -776,9 +768,6 @@ vy_cache_iterator_restore(struct vy_cache_iterator *itr,
itr->version = itr->cache->version;
struct tuple *prev_stmt = itr->curr_stmt;
- if (prev_stmt != NULL)
- tuple_unref(prev_stmt);
-
if ((prev_stmt == NULL && itr->iterator_type == ITER_EQ) ||
(prev_stmt != NULL &&
prev_stmt != vy_cache_iterator_curr_stmt(itr))) {
@@ -787,13 +776,7 @@ vy_cache_iterator_restore(struct vy_cache_iterator *itr,
* In either case the best we can do is restart the
* search.
*/
- struct vy_cache_entry *entry;
- vy_cache_iterator_seek(itr, last_stmt, &entry);
- itr->curr_stmt = NULL;
- if (entry != NULL) {
- *stop = vy_cache_iterator_is_stop(itr, entry);
- itr->curr_stmt = entry->stmt;
- }
+ *stop = vy_cache_iterator_seek(itr, last_stmt);
vy_cache_iterator_skip_to_read_view(itr, stop);
} else {
/*
@@ -830,7 +813,10 @@ vy_cache_iterator_restore(struct vy_cache_iterator *itr,
break;
if (vy_stmt_lsn(entry->stmt) <= (**itr->read_view).vlsn) {
itr->curr_pos = pos;
+ if (itr->curr_stmt != NULL)
+ tuple_unref(itr->curr_stmt);
itr->curr_stmt = entry->stmt;
+ tuple_ref(itr->curr_stmt);
*stop = vy_cache_iterator_is_stop(itr, entry);
}
if (cmp == 0)
@@ -840,7 +826,6 @@ vy_cache_iterator_restore(struct vy_cache_iterator *itr,
vy_history_cleanup(history);
if (itr->curr_stmt != NULL) {
- tuple_ref(itr->curr_stmt);
vy_stmt_counter_acct_tuple(&itr->cache->stat.get,
itr->curr_stmt);
if (vy_history_append_stmt(history, itr->curr_stmt) != 0)
--
2.11.0
^ permalink raw reply [flat|nested] 17+ messages in thread* [tarantool-patches] Re: [PATCH 3/6] vinyl: cache iterator: consolidate curr_stmt updates
2019-03-26 15:50 ` [PATCH 3/6] vinyl: cache iterator: consolidate curr_stmt updates Vladimir Davydov
@ 2019-03-28 14:29 ` Konstantin Osipov
2019-03-28 14:47 ` Vladimir Davydov
0 siblings, 1 reply; 17+ messages in thread
From: Konstantin Osipov @ 2019-03-28 14:29 UTC (permalink / raw)
To: tarantool-patches
* Vladimir Davydov <vdavydov.dev@gmail.com> [19/03/26 18:56]:
> Currently, vy_cache_iterator->curr_stmt is updated by top-level iterator
> functions - next, skip, restore - which results in code duplication and
> spreads core logic among multiple places. To reduce the amount of code
> and make it generally easier to follow, this patch moves the updates to
> low level functions - step, seek. It also makes the seek method return
> the stop flag, which makes it similar to step, thus making the code more
> consistent.
OK to push. As a nit, I would pass stop as an out parameter, not
in return value. We may want to use the return value to indicate
an error sometime.
--
Konstantin Osipov, Moscow, Russia, +7 903 626 22 32
http://tarantool.io - www.twitter.com/kostja_osipov
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [tarantool-patches] Re: [PATCH 3/6] vinyl: cache iterator: consolidate curr_stmt updates
2019-03-28 14:29 ` [tarantool-patches] " Konstantin Osipov
@ 2019-03-28 14:47 ` Vladimir Davydov
0 siblings, 0 replies; 17+ messages in thread
From: Vladimir Davydov @ 2019-03-28 14:47 UTC (permalink / raw)
To: Konstantin Osipov; +Cc: tarantool-patches
On Thu, Mar 28, 2019 at 05:29:48PM +0300, Konstantin Osipov wrote:
> * Vladimir Davydov <vdavydov.dev@gmail.com> [19/03/26 18:56]:
> > Currently, vy_cache_iterator->curr_stmt is updated by top-level iterator
> > functions - next, skip, restore - which results in code duplication and
> > spreads core logic among multiple places. To reduce the amount of code
> > and make it generally easier to follow, this patch moves the updates to
> > low level functions - step, seek. It also makes the seek method return
> > the stop flag, which makes it similar to step, thus making the code more
> > consistent.
>
> OK to push. As a nit, I would pass stop as an out parameter, not
> in return value. We may want to use the return value to indicate
> an error sometime.
Hmm, I just wanted to make it look like vy_cache_iterator_step,
but I guess you're right - we'd better avoid using retval as stop
indicator. I'll either amend this patch or prepare a separate patch
to clean up retvals across all iterators.
^ permalink raw reply [flat|nested] 17+ messages in thread
* [PATCH 4/6] vinyl: run iterator: zap search_ended flag
2019-03-26 15:50 [PATCH 0/6] vinyl: iterator cleanup Vladimir Davydov
` (2 preceding siblings ...)
2019-03-26 15:50 ` [PATCH 3/6] vinyl: cache iterator: consolidate curr_stmt updates Vladimir Davydov
@ 2019-03-26 15:50 ` Vladimir Davydov
2019-03-28 14:35 ` [tarantool-patches] " Konstantin Osipov
2019-03-26 15:50 ` [PATCH 5/6] vinyl: run iterator: refactor seek method Vladimir Davydov
` (2 subsequent siblings)
6 siblings, 1 reply; 17+ messages in thread
From: Vladimir Davydov @ 2019-03-26 15:50 UTC (permalink / raw)
To: tarantool-patches
It's equivalent to (itr->search_started && itr->curr_stmt == NULL).
---
src/box/vy_run.c | 35 ++++++++++++++---------------------
src/box/vy_run.h | 2 --
2 files changed, 14 insertions(+), 23 deletions(-)
diff --git a/src/box/vy_run.c b/src/box/vy_run.c
index 699941a8..c21e731f 100644
--- a/src/box/vy_run.c
+++ b/src/box/vy_run.c
@@ -738,7 +738,6 @@ vy_run_iterator_stop(struct vy_run_iterator *itr)
vy_page_delete(itr->prev_page);
itr->curr_page = itr->prev_page = NULL;
}
- itr->search_ended = true;
}
static int
@@ -1071,6 +1070,7 @@ vy_run_iterator_search_in_page(struct vy_run_iterator *itr,
* equal to given key (untouched otherwise)
*
* @retval 0 success
+ * @retval 1 EOF
* @retval -1 read or memory error
*/
static NODISCARD int
@@ -1082,10 +1082,8 @@ vy_run_iterator_search(struct vy_run_iterator *itr,
pos->page_no = vy_page_index_find_page(itr->slice->run, key,
itr->cmp_def, iterator_type,
equal_key);
- if (pos->page_no == itr->slice->run->info.page_count) {
- itr->search_ended = true;
- return 0;
- }
+ if (pos->page_no == itr->slice->run->info.page_count)
+ return 1;
struct vy_page *page;
int rc = vy_run_iterator_load_page(itr, pos->page_no, &page);
if (rc != 0)
@@ -1155,7 +1153,7 @@ vy_run_iterator_next_pos(struct vy_run_iterator *itr,
* (i.e. left for GE, right for LE).
* @retval 0 success or EOF (*ret == NULL)
* @retval -1 read or memory error
- * Affects: curr_loaded_page, curr_pos, search_ended
+ * Affects: curr_loaded_page, curr_pos
*/
static NODISCARD int
vy_run_iterator_find_lsn(struct vy_run_iterator *itr,
@@ -1168,7 +1166,6 @@ vy_run_iterator_find_lsn(struct vy_run_iterator *itr,
*ret = NULL;
assert(itr->search_started);
- assert(!itr->search_ended);
assert(itr->curr_stmt != NULL);
assert(itr->curr_pos.page_no < slice->run->info.page_count);
@@ -1244,7 +1241,7 @@ vy_run_iterator_do_seek(struct vy_run_iterator *itr,
struct key_def *key_def = itr->key_def;
if (iterator_type == ITER_EQ && bloom != NULL &&
!vy_stmt_bloom_maybe_has(bloom, key, key_def)) {
- itr->search_ended = true;
+ vy_run_iterator_stop(itr);
itr->stat->bloom_hit++;
return 0;
}
@@ -1257,8 +1254,12 @@ vy_run_iterator_do_seek(struct vy_run_iterator *itr,
if (!vy_stmt_is_empty_key(key)) {
rc = vy_run_iterator_search(itr, iterator_type, key,
&itr->curr_pos, &equal_found);
- if (rc != 0 || itr->search_ended)
- return rc;
+ if (rc < 0)
+ return -1;
+ if (rc > 0) {
+ vy_run_iterator_stop(itr);
+ return 0;
+ }
} else if (iterator_type == ITER_LE) {
itr->curr_pos = end_pos;
} else {
@@ -1412,9 +1413,7 @@ vy_run_iterator_open(struct vy_run_iterator *itr,
itr->curr_pos.page_no = slice->run->info.page_count;
itr->curr_page = NULL;
itr->prev_page = NULL;
-
itr->search_started = false;
- itr->search_ended = false;
/*
* Make sure the format we use to create tuples won't
@@ -1437,14 +1436,14 @@ vy_run_iterator_next_key(struct vy_run_iterator *itr, struct tuple **ret)
{
*ret = NULL;
- if (itr->search_ended)
- return 0;
if (!itr->search_started) {
itr->search_started = true;
return vy_run_iterator_seek(itr, itr->iterator_type,
itr->key, ret);
}
- assert(itr->curr_stmt != NULL);
+ if (itr->curr_stmt == NULL)
+ return 0;
+
assert(itr->curr_pos.page_no < itr->slice->run->info.page_count);
struct tuple *next_key = NULL;
@@ -1483,9 +1482,6 @@ vy_run_iterator_next_lsn(struct vy_run_iterator *itr, struct tuple **ret)
*ret = NULL;
assert(itr->search_started);
- if (itr->search_ended)
- return 0;
-
assert(itr->curr_stmt != NULL);
assert(itr->curr_pos.page_no < itr->slice->run->info.page_count);
@@ -1540,9 +1536,6 @@ vy_run_iterator_skip(struct vy_run_iterator *itr,
const struct tuple *last_stmt,
struct vy_history *history)
{
- if (itr->search_ended)
- return 0;
-
/*
* Check if the iterator is already positioned
* at the statement following last_stmt.
diff --git a/src/box/vy_run.h b/src/box/vy_run.h
index beb87b78..cbc51c50 100644
--- a/src/box/vy_run.h
+++ b/src/box/vy_run.h
@@ -279,8 +279,6 @@ struct vy_run_iterator {
struct vy_page *prev_page;
/** Is false until first .._get or .._next_.. method is called */
bool search_started;
- /** Search is finished, you will not get more values from iterator */
- bool search_ended;
};
/**
--
2.11.0
^ permalink raw reply [flat|nested] 17+ messages in thread* [tarantool-patches] Re: [PATCH 4/6] vinyl: run iterator: zap search_ended flag
2019-03-26 15:50 ` [PATCH 4/6] vinyl: run iterator: zap search_ended flag Vladimir Davydov
@ 2019-03-28 14:35 ` Konstantin Osipov
2019-03-28 14:50 ` Vladimir Davydov
0 siblings, 1 reply; 17+ messages in thread
From: Konstantin Osipov @ 2019-03-28 14:35 UTC (permalink / raw)
To: tarantool-patches
* Vladimir Davydov <vdavydov.dev@gmail.com> [19/03/26 18:56]:
> It's equivalent to (itr->search_started && itr->curr_stmt == NULL).
OK to push, but same as in the previous patch, I would not use the
return value for anything but success/error. We already have a
boolean parameter 'equal found', we could turn it into a enum,
since 'equal found' and 'eof' are mutually exclusive.
--
Konstantin Osipov, Moscow, Russia, +7 903 626 22 32
http://tarantool.io - www.twitter.com/kostja_osipov
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [tarantool-patches] Re: [PATCH 4/6] vinyl: run iterator: zap search_ended flag
2019-03-28 14:35 ` [tarantool-patches] " Konstantin Osipov
@ 2019-03-28 14:50 ` Vladimir Davydov
0 siblings, 0 replies; 17+ messages in thread
From: Vladimir Davydov @ 2019-03-28 14:50 UTC (permalink / raw)
To: Konstantin Osipov; +Cc: tarantool-patches
On Thu, Mar 28, 2019 at 05:35:18PM +0300, Konstantin Osipov wrote:
> * Vladimir Davydov <vdavydov.dev@gmail.com> [19/03/26 18:56]:
> > It's equivalent to (itr->search_started && itr->curr_stmt == NULL).
>
> OK to push, but same as in the previous patch, I would not use the
> return value for anything but success/error. We already have a
> boolean parameter 'equal found', we could turn it into a enum,
> since 'equal found' and 'eof' are mutually exclusive.
Returning 1 is consistent with vy_mem_iterator behavior. Other
vy_run_iterator functions stick to this convention, too. Yeah,
it looks rather awkward, but I think we'd better clean it up in
a separate patch. I'll look what we can do about it.
^ permalink raw reply [flat|nested] 17+ messages in thread
* [PATCH 5/6] vinyl: run iterator: refactor seek method
2019-03-26 15:50 [PATCH 0/6] vinyl: iterator cleanup Vladimir Davydov
` (3 preceding siblings ...)
2019-03-26 15:50 ` [PATCH 4/6] vinyl: run iterator: zap search_ended flag Vladimir Davydov
@ 2019-03-26 15:50 ` Vladimir Davydov
2019-03-28 14:39 ` [tarantool-patches] " Konstantin Osipov
2019-03-26 15:50 ` [PATCH 6/6] vinyl: simplify read iterator restoration behavior Vladimir Davydov
2019-03-28 16:28 ` [PATCH 0/6] vinyl: iterator cleanup Vladimir Davydov
6 siblings, 1 reply; 17+ messages in thread
From: Vladimir Davydov @ 2019-03-26 15:50 UTC (permalink / raw)
To: tarantool-patches
A few changes to make the function more straightforward:
- Move bloom checking and LSN filtering out of 'do_seek' helper. Make
the helper do just one simple task - lookup the first one in a series
of statements matching the given search criteria.
- Fold iterator type and key substitution in 'seek' method, similarly
to how we did it for other iterators.
- Cleanup EQ checks. Use the original iterator type and key where
appropriate to remove extra checks in calling methods. Don't check EQ
in 'seek' method in case it was checked by 'do_seek'.
- Add some comments.
---
src/box/vy_run.c | 199 +++++++++++++++++++++++++++++--------------------------
1 file changed, 106 insertions(+), 93 deletions(-)
diff --git a/src/box/vy_run.c b/src/box/vy_run.c
index c21e731f..818d0cf3 100644
--- a/src/box/vy_run.c
+++ b/src/box/vy_run.c
@@ -1156,9 +1156,7 @@ 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,
- enum iterator_type iterator_type,
- const struct tuple *key, struct tuple **ret)
+vy_run_iterator_find_lsn(struct vy_run_iterator *itr, struct tuple **ret)
{
struct vy_slice *slice = itr->slice;
struct key_def *cmp_def = itr->cmp_def;
@@ -1171,7 +1169,7 @@ vy_run_iterator_find_lsn(struct vy_run_iterator *itr,
while (vy_stmt_lsn(itr->curr_stmt) > (**itr->read_view).vlsn ||
vy_stmt_flags(itr->curr_stmt) & VY_STMT_SKIP_READ) {
- if (vy_run_iterator_next_pos(itr, iterator_type,
+ if (vy_run_iterator_next_pos(itr, itr->iterator_type,
&itr->curr_pos) != 0) {
vy_run_iterator_stop(itr);
return 0;
@@ -1181,15 +1179,15 @@ vy_run_iterator_find_lsn(struct vy_run_iterator *itr,
if (vy_run_iterator_read(itr, itr->curr_pos,
&itr->curr_stmt) != 0)
return -1;
- if (iterator_type == ITER_EQ &&
- vy_stmt_compare(itr->curr_stmt, key, cmp_def) != 0) {
+ if (itr->iterator_type == ITER_EQ &&
+ vy_stmt_compare(itr->curr_stmt, itr->key, cmp_def) != 0) {
vy_run_iterator_stop(itr);
return 0;
}
}
- if (iterator_type == ITER_LE || iterator_type == ITER_LT) {
+ if (itr->iterator_type == ITER_LE || itr->iterator_type == ITER_LT) {
struct vy_run_iterator_pos test_pos;
- while (vy_run_iterator_next_pos(itr, iterator_type,
+ while (vy_run_iterator_next_pos(itr, itr->iterator_type,
&test_pos) == 0) {
struct tuple *test_stmt;
if (vy_run_iterator_read(itr, test_pos,
@@ -1208,15 +1206,16 @@ vy_run_iterator_find_lsn(struct vy_run_iterator *itr,
}
}
/* Check if the result is within the slice boundaries. */
- if (iterator_type == ITER_LE || iterator_type == ITER_LT) {
+ 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_run_iterator_stop(itr);
return 0;
}
} else {
- assert(iterator_type == ITER_GE || iterator_type == ITER_GT ||
- iterator_type == ITER_EQ);
+ assert(itr->iterator_type == ITER_GE ||
+ 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_run_iterator_stop(itr);
@@ -1228,38 +1227,32 @@ vy_run_iterator_find_lsn(struct vy_run_iterator *itr,
return 0;
}
+/**
+ * Helper function for vy_run_iterator_seek().
+ *
+ * Positions the iterator to the beginning (i.e. leftmost for GE,
+ * rightmost for LE) of a series of statements matching the given
+ * search criteria.
+ *
+ * Updates itr->curr_pos. Doesn't affect itr->curr_stmt.
+ *
+ * @retval 0 success
+ * @retval 1 EOF
+ * @retval -1 read or memory error
+ */
static NODISCARD int
vy_run_iterator_do_seek(struct vy_run_iterator *itr,
enum iterator_type iterator_type,
- const struct tuple *key, struct tuple **ret)
+ const struct tuple *key)
{
struct vy_run *run = itr->slice->run;
-
- *ret = NULL;
-
- struct tuple_bloom *bloom = run->info.bloom;
- struct key_def *key_def = itr->key_def;
- if (iterator_type == ITER_EQ && bloom != NULL &&
- !vy_stmt_bloom_maybe_has(bloom, key, key_def)) {
- vy_run_iterator_stop(itr);
- itr->stat->bloom_hit++;
- return 0;
- }
-
- itr->stat->lookup++;
-
struct vy_run_iterator_pos end_pos = {run->info.page_count, 0};
bool equal_found = false;
- int rc;
if (!vy_stmt_is_empty_key(key)) {
- rc = vy_run_iterator_search(itr, iterator_type, key,
- &itr->curr_pos, &equal_found);
- if (rc < 0)
- return -1;
- if (rc > 0) {
- vy_run_iterator_stop(itr);
- return 0;
- }
+ int rc = vy_run_iterator_search(itr, iterator_type, key,
+ &itr->curr_pos, &equal_found);
+ if (rc != 0)
+ return rc;
} else if (iterator_type == ITER_LE) {
itr->curr_pos = end_pos;
} else {
@@ -1267,17 +1260,11 @@ vy_run_iterator_do_seek(struct vy_run_iterator *itr,
itr->curr_pos.page_no = 0;
itr->curr_pos.pos_in_page = 0;
}
- if (iterator_type == ITER_EQ && !equal_found) {
- vy_run_iterator_stop(itr);
- if (bloom != NULL)
- itr->stat->bloom_miss++;
- return 0;
- }
+ if (iterator_type == ITER_EQ && !equal_found)
+ return 1;
if ((iterator_type == ITER_GE || iterator_type == ITER_GT) &&
- itr->curr_pos.page_no == end_pos.page_no) {
- vy_run_iterator_stop(itr);
- return 0;
- }
+ itr->curr_pos.page_no == end_pos.page_no)
+ return 1;
if (iterator_type == ITER_LT || iterator_type == ITER_LE) {
/**
* 1) in case of ITER_LT we now positioned on the value >= than
@@ -1286,11 +1273,8 @@ vy_run_iterator_do_seek(struct vy_run_iterator *itr,
* given (special branch of code in vy_run_iterator_search),
* so we need to make a step on previous key
*/
- if (vy_run_iterator_next_pos(itr, iterator_type,
- &itr->curr_pos) > 0) {
- vy_run_iterator_stop(itr);
- return 0;
- }
+ return vy_run_iterator_next_pos(itr, iterator_type,
+ &itr->curr_pos);
} else {
assert(iterator_type == ITER_GE || iterator_type == ITER_GT ||
iterator_type == ITER_EQ);
@@ -1301,31 +1285,58 @@ vy_run_iterator_do_seek(struct vy_run_iterator *itr,
* 2) in case if ITER_GE or ITER_EQ we now positioned on the
* value >= given, so we need just to find proper lsn
*/
+ return 0;
}
- if (itr->curr_stmt != NULL) {
- tuple_unref(itr->curr_stmt);
- itr->curr_stmt = NULL;
- }
- if (vy_run_iterator_read(itr, itr->curr_pos, &itr->curr_stmt) != 0)
- return -1;
-
- return vy_run_iterator_find_lsn(itr, iterator_type, key, ret);
}
/**
* Position the iterator to the first statement satisfying
- * the search criteria for a given key and direction.
+ * the iterator search criteria and following the given key
+ * (pass NULL to start iteration).
*/
static NODISCARD int
-vy_run_iterator_seek(struct vy_run_iterator *itr,
- enum iterator_type iterator_type,
- const struct tuple *key, struct tuple **ret)
+vy_run_iterator_seek(struct vy_run_iterator *itr, const struct tuple *last_key,
+ struct tuple **ret)
{
struct key_def *cmp_def = itr->cmp_def;
struct vy_slice *slice = itr->slice;
- const struct tuple *check_eq_key = NULL;
- int cmp;
+ struct tuple_bloom *bloom = slice->run->info.bloom;
+ const struct tuple *key = itr->key;
+ enum iterator_type iterator_type = itr->iterator_type;
+ *ret = NULL;
+ assert(itr->search_started);
+
+ /* Check the bloom filter on the first iteration. */
+ bool check_bloom = (itr->iterator_type == ITER_EQ &&
+ itr->curr_stmt == NULL && bloom != NULL);
+ if (check_bloom && !vy_stmt_bloom_maybe_has(bloom, itr->key,
+ itr->key_def)) {
+ vy_run_iterator_stop(itr);
+ itr->stat->bloom_hit++;
+ return 0;
+ }
+
+ /*
+ * vy_run_iterator_do_seek() implements its own EQ check.
+ * We only need to check EQ here if iterator type and key
+ * passed to it differ from the original.
+ */
+ bool check_eq = false;
+
+ /*
+ * Modify iterator type and key so as to position it to
+ * the first statement following the given key.
+ */
+ if (last_key != NULL) {
+ if (iterator_type == ITER_EQ)
+ check_eq = true;
+ iterator_type = iterator_direction(iterator_type) > 0 ?
+ ITER_GT : ITER_LT;
+ key = last_key;
+ }
+
+ /* Take slice boundaries into account. */
if (slice->begin != NULL &&
(iterator_type == ITER_GT || iterator_type == ITER_GE ||
iterator_type == ITER_EQ)) {
@@ -1342,20 +1353,18 @@ vy_run_iterator_seek(struct vy_run_iterator *itr,
* | ge | begin | ge |
* | eq | stop |
*/
- cmp = vy_stmt_compare(key, slice->begin, cmp_def);
+ int cmp = vy_stmt_compare(key, slice->begin, cmp_def);
if (cmp < 0 && iterator_type == ITER_EQ) {
vy_run_iterator_stop(itr);
- *ret = NULL;
return 0;
}
if (cmp < 0 || (cmp == 0 && iterator_type != ITER_GT)) {
if (iterator_type == ITER_EQ)
- check_eq_key = key;
+ check_eq = true;
iterator_type = ITER_GE;
key = slice->begin;
}
}
-
if (slice->end != NULL &&
(iterator_type == ITER_LT || iterator_type == ITER_LE)) {
/*
@@ -1369,21 +1378,41 @@ vy_run_iterator_seek(struct vy_run_iterator *itr,
* > end | lt | end | lt |
* | le | end | lt |
*/
- cmp = vy_stmt_compare(key, slice->end, cmp_def);
+ int cmp = vy_stmt_compare(key, slice->end, cmp_def);
if (cmp > 0 || (cmp == 0 && iterator_type != ITER_LT)) {
iterator_type = ITER_LT;
key = slice->end;
}
}
- if (vy_run_iterator_do_seek(itr, iterator_type, key, ret) != 0)
+ /* Perform a lookup in the run. */
+ itr->stat->lookup++;
+ int rc = vy_run_iterator_do_seek(itr, iterator_type, key);
+ if (rc < 0)
return -1;
+ if (rc > 0)
+ goto not_found;
- if (check_eq_key != NULL && *ret != NULL &&
- vy_stmt_compare(check_eq_key, *ret, cmp_def) != 0) {
- vy_run_iterator_stop(itr);
- *ret = NULL;
+ /* Load the found statement. */
+ if (itr->curr_stmt != NULL) {
+ tuple_unref(itr->curr_stmt);
+ itr->curr_stmt = NULL;
}
+ if (vy_run_iterator_read(itr, itr->curr_pos, &itr->curr_stmt) != 0)
+ return -1;
+
+ /* Check EQ constraint if necessary. */
+ if (check_eq && vy_stmt_compare(itr->curr_stmt, itr->key,
+ itr->cmp_def) != 0)
+ goto not_found;
+
+ /* Skip statements invisible from the iterator read view. */
+ return vy_run_iterator_find_lsn(itr, ret);
+
+not_found:
+ if (check_bloom)
+ itr->stat->bloom_miss++;
+ vy_run_iterator_stop(itr);
return 0;
}
@@ -1438,8 +1467,7 @@ 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, itr->iterator_type,
- itr->key, ret);
+ return vy_run_iterator_seek(itr, NULL, ret);
}
if (itr->curr_stmt == NULL)
return 0;
@@ -1468,7 +1496,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, itr->iterator_type, itr->key, ret);
+ return vy_run_iterator_find_lsn(itr, ret);
}
/**
@@ -1548,26 +1576,11 @@ vy_run_iterator_skip(struct vy_run_iterator *itr,
vy_history_cleanup(history);
- const struct tuple *key = itr->key;
- enum iterator_type iterator_type = itr->iterator_type;
- if (last_stmt != NULL) {
- key = last_stmt;
- iterator_type = iterator_direction(iterator_type) > 0 ?
- ITER_GT : ITER_LT;
- }
-
itr->search_started = true;
struct tuple *stmt;
- if (vy_run_iterator_seek(itr, iterator_type, key, &stmt) != 0)
+ if (vy_run_iterator_seek(itr, last_stmt, &stmt) != 0)
return -1;
- if (itr->iterator_type == ITER_EQ && last_stmt != NULL &&
- stmt != NULL && vy_stmt_compare(itr->key, stmt,
- itr->cmp_def) != 0) {
- vy_run_iterator_stop(itr);
- return 0;
- }
-
while (stmt != NULL) {
if (vy_history_append_stmt(history, stmt) != 0)
return -1;
--
2.11.0
^ permalink raw reply [flat|nested] 17+ messages in thread* [tarantool-patches] Re: [PATCH 5/6] vinyl: run iterator: refactor seek method
2019-03-26 15:50 ` [PATCH 5/6] vinyl: run iterator: refactor seek method Vladimir Davydov
@ 2019-03-28 14:39 ` Konstantin Osipov
2019-03-28 14:58 ` Vladimir Davydov
0 siblings, 1 reply; 17+ messages in thread
From: Konstantin Osipov @ 2019-03-28 14:39 UTC (permalink / raw)
To: tarantool-patches
* Vladimir Davydov <vdavydov.dev@gmail.com> [19/03/26 18:56]:
> A few changes to make the function more straightforward:
>
> - Move bloom checking and LSN filtering out of 'do_seek' helper. Make
> the helper do just one simple task - lookup the first one in a series
> of statements matching the given search criteria.
> - Fold iterator type and key substitution in 'seek' method, similarly
> to how we did it for other iterators.
> - Cleanup EQ checks. Use the original iterator type and key where
> appropriate to remove extra checks in calling methods. Don't check EQ
> in 'seek' method in case it was checked by 'do_seek'.
> - Add some comments.
LGTM (same comment re passing EOF in return value applies).
eq_found looks cumbersome, perhaps you could both kill bool
eq_found and not pass eof in the out parameter of do_seek()?
--
Konstantin Osipov, Moscow, Russia, +7 903 626 22 32
http://tarantool.io - www.twitter.com/kostja_osipov
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [tarantool-patches] Re: [PATCH 5/6] vinyl: run iterator: refactor seek method
2019-03-28 14:39 ` [tarantool-patches] " Konstantin Osipov
@ 2019-03-28 14:58 ` Vladimir Davydov
0 siblings, 0 replies; 17+ messages in thread
From: Vladimir Davydov @ 2019-03-28 14:58 UTC (permalink / raw)
To: Konstantin Osipov; +Cc: tarantool-patches
On Thu, Mar 28, 2019 at 05:39:47PM +0300, Konstantin Osipov wrote:
> * Vladimir Davydov <vdavydov.dev@gmail.com> [19/03/26 18:56]:
> > A few changes to make the function more straightforward:
> >
> > - Move bloom checking and LSN filtering out of 'do_seek' helper. Make
> > the helper do just one simple task - lookup the first one in a series
> > of statements matching the given search criteria.
> > - Fold iterator type and key substitution in 'seek' method, similarly
> > to how we did it for other iterators.
> > - Cleanup EQ checks. Use the original iterator type and key where
> > appropriate to remove extra checks in calling methods. Don't check EQ
> > in 'seek' method in case it was checked by 'do_seek'.
> > - Add some comments.
>
> LGTM (same comment re passing EOF in return value applies).
> eq_found looks cumbersome, perhaps you could both kill bool
> eq_found and not pass eof in the out parameter of do_seek()?
eq_found is an optimization that allows us to save a tuple comparison.
Not that it really matters for the disk iterator, but still I'd rather
keep it.
As I said, I agree that retval conventions look ugly in the iterator
code. I didn't plan on cleaning it up now, because it doesn't really
stand in the way of tuple hints. I'll look into it a bit later.
^ permalink raw reply [flat|nested] 17+ messages in thread
* [PATCH 6/6] vinyl: simplify read iterator restoration behavior
2019-03-26 15:50 [PATCH 0/6] vinyl: iterator cleanup Vladimir Davydov
` (4 preceding siblings ...)
2019-03-26 15:50 ` [PATCH 5/6] vinyl: run iterator: refactor seek method Vladimir Davydov
@ 2019-03-26 15:50 ` Vladimir Davydov
2019-03-28 14:47 ` [tarantool-patches] " Konstantin Osipov
2019-03-28 16:28 ` [PATCH 0/6] vinyl: iterator cleanup Vladimir Davydov
6 siblings, 1 reply; 17+ messages in thread
From: Vladimir Davydov @ 2019-03-26 15:50 UTC (permalink / raw)
To: tarantool-patches
The 'restore' method, which is implemented by txw, cache, and memory
sources, restores an iterator position after a yield in case the source
has changed. It is passed the last key and it is supposed to position
the iterator to the statement following the last key provided it had to
reposition the iterator at all. For all kinds of sources, it first
checks the source version and bails out early if it hasn't changed since
the last time the iterator was used. If it has changed, it either looks
up the statement following the given last key or tries to advance the
iterator statement by statement (in case of a cache iterator, to avoid
extra cache lookups).
Currently, the method returns 1 if the iterator position has actually
changed as a result of the call, 0 otherwise. That is, it returns 0 even
if the version has changed and it had to perform a full lookup, but
landed on the same statement. This is confusing, because in this case
the caller has to check if it has to advance the iterator even though it
doesn't need to, as the iterator is already positioned at the next key -
see vy_read_iterator_scan_* family of functions.
Let's simplify the restoration rules - make the 'restore' method return
1 if it had to restore the iterator position irrespective of whether the
position has actually changed or not. This means that in case the method
returns 1, the caller knows that the iterator is already positioned
properly and doesn't need to be advanced. If it returns 0, it means that
the iterator is positioned at the same statement as before and we need
to check if we need to advance it. This simplifies the iterator code by
removing position checking, which would turn real nasty once multikey
indexes are introduced. Note, comments to 'restore' methods already
conform to this behavior (they weren't quite correct before this patch).
There's a catch though - vy_read_iterator_restore_mem relies on the old
behavior to skip the cache source in case the current key gets updated
during yield. However, it's easy to fix that without introducing any
extra overhead - we just need to check if the cache source is at the
front of the iterator and clear its history if it is. BTW it turned out
that this behavior wasn't covered by tests - when I removed the line
invalidating the cache source from vy_read_iterator_restore_mem, all
tests passed as usual. So while we are at it, let's also add a test case
covering this piece of code.
---
src/box/vy_cache.c | 17 ++++++++++-------
src/box/vy_mem.c | 3 ---
src/box/vy_read_iterator.c | 4 +++-
src/box/vy_tx.c | 3 ---
test/vinyl/stat.result | 4 ++--
test/vinyl/upsert.result | 44 ++++++++++++++++++++++++++++++++++++++++++++
test/vinyl/upsert.test.lua | 18 ++++++++++++++++++
7 files changed, 77 insertions(+), 16 deletions(-)
diff --git a/src/box/vy_cache.c b/src/box/vy_cache.c
index 825bfd3b..e526ab1e 100644
--- a/src/box/vy_cache.c
+++ b/src/box/vy_cache.c
@@ -766,11 +766,11 @@ vy_cache_iterator_restore(struct vy_cache_iterator *itr,
if (!itr->search_started || itr->version == itr->cache->version)
return 0;
+ bool pos_changed = false;
itr->version = itr->cache->version;
- struct tuple *prev_stmt = itr->curr_stmt;
- if ((prev_stmt == NULL && itr->iterator_type == ITER_EQ) ||
- (prev_stmt != NULL &&
- prev_stmt != vy_cache_iterator_curr_stmt(itr))) {
+ if ((itr->curr_stmt == NULL && itr->iterator_type == ITER_EQ) ||
+ (itr->curr_stmt != NULL &&
+ itr->curr_stmt != vy_cache_iterator_curr_stmt(itr))) {
/*
* EQ search ended or the iterator was invalidated.
* In either case the best we can do is restart the
@@ -778,6 +778,7 @@ vy_cache_iterator_restore(struct vy_cache_iterator *itr,
*/
*stop = vy_cache_iterator_seek(itr, last_stmt);
vy_cache_iterator_skip_to_read_view(itr, stop);
+ pos_changed = true;
} else {
/*
* The iterator position is still valid, but new
@@ -797,7 +798,7 @@ vy_cache_iterator_restore(struct vy_cache_iterator *itr,
struct key_def *def = itr->cache->cmp_def;
struct vy_cache_tree *tree = &itr->cache->cache_tree;
struct vy_cache_tree_iterator pos = itr->curr_pos;
- if (prev_stmt == NULL)
+ if (itr->curr_stmt == NULL)
pos = vy_cache_tree_invalid_iterator();
while (true) {
if (dir > 0)
@@ -818,11 +819,14 @@ vy_cache_iterator_restore(struct vy_cache_iterator *itr,
itr->curr_stmt = entry->stmt;
tuple_ref(itr->curr_stmt);
*stop = vy_cache_iterator_is_stop(itr, entry);
+ pos_changed = true;
}
if (cmp == 0)
break;
}
}
+ if (!pos_changed)
+ return 0;
vy_history_cleanup(history);
if (itr->curr_stmt != NULL) {
@@ -830,9 +834,8 @@ vy_cache_iterator_restore(struct vy_cache_iterator *itr,
itr->curr_stmt);
if (vy_history_append_stmt(history, itr->curr_stmt) != 0)
return -1;
- return prev_stmt != itr->curr_stmt;
}
- return 0;
+ return 1;
}
void
diff --git a/src/box/vy_mem.c b/src/box/vy_mem.c
index 7fa90cbd..e3b40083 100644
--- a/src/box/vy_mem.c
+++ b/src/box/vy_mem.c
@@ -595,10 +595,7 @@ vy_mem_iterator_restore(struct vy_mem_iterator *itr,
if (!itr->search_started || itr->version == itr->mem->version)
return 0;
- const struct tuple *prev_stmt = itr->curr_stmt;
vy_mem_iterator_seek(itr, last_stmt);
- if (prev_stmt == itr->curr_stmt)
- return 0;
vy_history_cleanup(history);
if (itr->curr_stmt != NULL &&
diff --git a/src/box/vy_read_iterator.c b/src/box/vy_read_iterator.c
index 2864a280..ac8a410d 100644
--- a/src/box/vy_read_iterator.c
+++ b/src/box/vy_read_iterator.c
@@ -424,7 +424,9 @@ vy_read_iterator_restore_mem(struct vy_read_iterator *itr,
* Make sure we don't read the old value
* from the cache while applying UPSERTs.
*/
- itr->src[itr->cache_src].front_id = 0;
+ struct vy_read_src *cache_src = &itr->src[itr->cache_src];
+ if (cache_src->front_id == itr->front_id)
+ vy_history_cleanup(&cache_src->history);
}
src->front_id = itr->front_id;
return 0;
diff --git a/src/box/vy_tx.c b/src/box/vy_tx.c
index 02f5ca27..bbb41df5 100644
--- a/src/box/vy_tx.c
+++ b/src/box/vy_tx.c
@@ -1247,10 +1247,7 @@ vy_txw_iterator_restore(struct vy_txw_iterator *itr,
if (!itr->search_started || itr->version == itr->tx->write_set_version)
return 0;
- struct txv *prev_txv = itr->curr_txv;
vy_txw_iterator_seek(itr, last_stmt);
- if (prev_txv == itr->curr_txv)
- return 0;
vy_history_cleanup(history);
if (itr->curr_txv != NULL) {
diff --git a/test/vinyl/stat.result b/test/vinyl/stat.result
index 08da1658..ff73d42a 100644
--- a/test/vinyl/stat.result
+++ b/test/vinyl/stat.result
@@ -716,8 +716,8 @@ stat_diff(istat(), st)
rows: 5
bytes: 5305
get:
- rows: 9
- bytes: 9549
+ rows: 5
+ bytes: 5305
txw:
iterator:
lookup: 1
diff --git a/test/vinyl/upsert.result b/test/vinyl/upsert.result
index 6c6d03d6..c807b5b5 100644
--- a/test/vinyl/upsert.result
+++ b/test/vinyl/upsert.result
@@ -791,3 +791,47 @@ s:select({100}, 'GE')
s:drop()
---
...
+--
+-- Check that read iterator ignores a cached statement in case
+-- the current key is updated while it yields on disk read.
+--
+fiber = require('fiber')
+---
+...
+s = box.schema.space.create('test', {engine = 'vinyl'})
+---
+...
+_ = s:create_index('pk')
+---
+...
+s:replace{10, 10}
+---
+- [10, 10]
+...
+box.snapshot()
+---
+- ok
+...
+s:get(10) -- add [10, 10] to the cache
+---
+- [10, 10]
+...
+ch = fiber.channel(1)
+---
+...
+test_run:cmd("setopt delimiter ';'")
+---
+- true
+...
+_ = fiber.create(function() ch:put(s:select()) end)
+s:upsert({10, 10}, {{'+', 2, 10}})
+test_run:cmd("setopt delimiter ''");
+---
+...
+ch:get() -- should see the UPSERT and return [10, 20]
+---
+- - [10, 20]
+...
+s:drop()
+---
+...
diff --git a/test/vinyl/upsert.test.lua b/test/vinyl/upsert.test.lua
index ef83e0f6..cf287360 100644
--- a/test/vinyl/upsert.test.lua
+++ b/test/vinyl/upsert.test.lua
@@ -325,3 +325,21 @@ s:upsert({100}, {{'+', 2, 100}})
s:select({100}, 'GE')
s:drop()
+
+--
+-- Check that read iterator ignores a cached statement in case
+-- the current key is updated while it yields on disk read.
+--
+fiber = require('fiber')
+s = box.schema.space.create('test', {engine = 'vinyl'})
+_ = s:create_index('pk')
+s:replace{10, 10}
+box.snapshot()
+s:get(10) -- add [10, 10] to the cache
+ch = fiber.channel(1)
+test_run:cmd("setopt delimiter ';'")
+_ = fiber.create(function() ch:put(s:select()) end)
+s:upsert({10, 10}, {{'+', 2, 10}})
+test_run:cmd("setopt delimiter ''");
+ch:get() -- should see the UPSERT and return [10, 20]
+s:drop()
--
2.11.0
^ permalink raw reply [flat|nested] 17+ messages in thread* Re: [PATCH 0/6] vinyl: iterator cleanup
2019-03-26 15:50 [PATCH 0/6] vinyl: iterator cleanup Vladimir Davydov
` (5 preceding siblings ...)
2019-03-26 15:50 ` [PATCH 6/6] vinyl: simplify read iterator restoration behavior Vladimir Davydov
@ 2019-03-28 16:28 ` Vladimir Davydov
6 siblings, 0 replies; 17+ messages in thread
From: Vladimir Davydov @ 2019-03-28 16:28 UTC (permalink / raw)
To: tarantool-patches
On Tue, Mar 26, 2019 at 06:50:28PM +0300, Vladimir Davydov wrote:
> vinyl: txw iterator: fold eq check in seek method
> vinyl: cache iterator: fold eq check in seek method
> vinyl: cache iterator: consolidate curr_stmt updates
> vinyl: run iterator: zap search_ended flag
> vinyl: run iterator: refactor seek method
> vinyl: simplify read iterator restoration behavior
After some consideration I decided not to amend these patches with
retval fixes as this is rather an independent change. Pushed to master
as is. Added iterator retval cleanup to my todo list.
^ permalink raw reply [flat|nested] 17+ messages in thread