From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: From: Vladimir Davydov Subject: [PATCH 09/12] vinyl: consolidate skip optimization checks in read iterator Date: Sun, 15 Apr 2018 22:55:22 +0300 Message-Id: <5ff19cf39854cc565022683b6dce48aeda904d2f.1523820298.git.vdavydov.dev@gmail.com> In-Reply-To: References: In-Reply-To: References: To: kostja@tarantool.org Cc: tarantool-patches@freelists.org List-ID: 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