From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: From: Vladimir Davydov Subject: [PATCH 10/13] vinyl: forward tuple comparison hints to cache tree Date: Tue, 2 Apr 2019 20:33:47 +0300 Message-Id: <38fae51f79640eff1f2b31f7d41e479386534c5f.1554225074.git.vdavydov.dev@gmail.com> In-Reply-To: References: In-Reply-To: References: To: kostja.osipov@gmail.com Cc: tarantool-patches@freelists.org List-ID: Instead of computing a statement comparison hint in a vy_cache method, forward it from the read iterator, which already has it computed. Apart from eliminating extra calls to vy_stmt_hint, this is also a prerequisite for multikey indexes, which will reuse hints to store offsets of indexed array entries and thus make hints impossible to be computed in an arbitrary place in code. --- src/box/vinyl.c | 56 +++++++++++++++++++++++++---------------- src/box/vy_cache.c | 14 +++-------- src/box/vy_cache.h | 11 +++++--- src/box/vy_lsm.c | 4 +-- src/box/vy_point_lookup.c | 8 +++--- src/box/vy_point_lookup.h | 5 ++-- src/box/vy_read_iterator.c | 14 ++++++++--- src/box/vy_read_iterator.h | 12 +++++++-- src/box/vy_tx.c | 4 +-- test/unit/vy_iterators_helper.c | 11 ++++++-- test/unit/vy_point_lookup.c | 3 ++- 11 files changed, 87 insertions(+), 55 deletions(-) diff --git a/src/box/vinyl.c b/src/box/vinyl.c index 3e96f5f5..8832db2c 100644 --- a/src/box/vinyl.c +++ b/src/box/vinyl.c @@ -1142,8 +1142,9 @@ vinyl_space_check_format(struct space *space, struct tuple_format *format) &env->xm->p_committed_read_view); int rc; int loops = 0; + hint_t hint; struct tuple *tuple; - while ((rc = vy_read_iterator_next(&itr, &tuple)) == 0) { + while ((rc = vy_read_iterator_next(&itr, &tuple, &hint)) == 0) { /* * Read iterator yields only when it reads runs. * Yield periodically in order not to stall the @@ -1309,6 +1310,7 @@ vy_is_committed(struct vy_env *env, struct space *space) * @param tx Current transaction. * @param rv Read view. * @param tuple Tuple read from a secondary index. + * @param hint Comparison hint of the secondary tuple. * @param[out] result The found tuple is stored here. Must be * unreferenced after usage. * @@ -1318,7 +1320,8 @@ vy_is_committed(struct vy_env *env, struct space *space) static int vy_get_by_secondary_tuple(struct vy_lsm *lsm, struct vy_tx *tx, const struct vy_read_view **rv, - struct tuple *tuple, struct tuple **result) + struct tuple *tuple, hint_t hint, + struct tuple **result) { int rc = 0; assert(lsm->index_id > 0); @@ -1343,7 +1346,9 @@ vy_get_by_secondary_tuple(struct vy_lsm *lsm, struct vy_tx *tx, tuple_ref(key); } - if (vy_point_lookup(lsm->pk, tx, rv, key, result) != 0) { + hint_t primary_hint; + if (vy_point_lookup(lsm->pk, tx, rv, key, result, + &primary_hint) != 0) { rc = -1; goto out; } @@ -1368,7 +1373,7 @@ vy_get_by_secondary_tuple(struct vy_lsm *lsm, struct vy_tx *tx, * chain intersections, which are not tolerated by * the tuple cache implementation. */ - vy_cache_on_write(&lsm->cache, tuple, NULL); + vy_cache_on_write(&lsm->cache, tuple, hint, NULL); goto out; } @@ -1387,7 +1392,8 @@ vy_get_by_secondary_tuple(struct vy_lsm *lsm, struct vy_tx *tx, } if ((*rv)->vlsn == INT64_MAX) - vy_cache_add(&lsm->pk->cache, *result, NULL, key, ITER_EQ); + vy_cache_add(&lsm->pk->cache, *result, primary_hint, + NULL, HINT_NONE, key, ITER_EQ); out: tuple_unref(key); return rc; @@ -1417,6 +1423,7 @@ vy_get(struct vy_lsm *lsm, struct vy_tx *tx, assert(tx == NULL || tx->state == VINYL_TX_READY); int rc; + hint_t hint; struct tuple *tuple; if (vy_stmt_is_full_key(key, lsm->cmp_def)) { @@ -1425,11 +1432,11 @@ vy_get(struct vy_lsm *lsm, struct vy_tx *tx, */ if (tx != NULL && vy_tx_track_point(tx, lsm, key) != 0) return -1; - if (vy_point_lookup(lsm, tx, rv, key, &tuple) != 0) + if (vy_point_lookup(lsm, tx, rv, key, &tuple, &hint) != 0) return -1; if (lsm->index_id > 0 && tuple != NULL) { rc = vy_get_by_secondary_tuple(lsm, tx, rv, - tuple, result); + tuple, hint, result); tuple_unref(tuple); if (rc != 0) return -1; @@ -1437,25 +1444,27 @@ vy_get(struct vy_lsm *lsm, struct vy_tx *tx, *result = tuple; } if ((*rv)->vlsn == INT64_MAX) - vy_cache_add(&lsm->cache, *result, NULL, key, ITER_EQ); + vy_cache_add(&lsm->cache, *result, hint, + NULL, HINT_NONE, key, ITER_EQ); return 0; } struct vy_read_iterator itr; vy_read_iterator_open(&itr, lsm, tx, ITER_EQ, key, rv); - while ((rc = vy_read_iterator_next(&itr, &tuple)) == 0) { + while ((rc = vy_read_iterator_next(&itr, &tuple, &hint)) == 0) { if (lsm->index_id == 0 || tuple == NULL) { *result = tuple; if (tuple != NULL) tuple_ref(tuple); break; } - rc = vy_get_by_secondary_tuple(lsm, tx, rv, tuple, result); + rc = vy_get_by_secondary_tuple(lsm, tx, rv, tuple, hint, + result); if (rc != 0 || *result != NULL) break; } if (rc == 0) - vy_read_iterator_cache_add(&itr, *result); + vy_read_iterator_cache_add(&itr, *result, hint); vy_read_iterator_close(&itr); return rc; } @@ -3530,15 +3539,14 @@ vy_squash_process(struct vy_squash *squash) * Use the committed read view to avoid squashing * prepared, but not committed statements. */ + hint_t hint; struct tuple *result; if (vy_point_lookup(lsm, NULL, &env->xm->p_committed_read_view, - squash->stmt, &result) != 0) + squash->stmt, &result, &hint) != 0) return -1; if (result == NULL) return 0; - hint_t hint = vy_stmt_hint(result, lsm->cmp_def); - /* * While we were reading on-disk runs, new statements could * have been prepared for the squashed key. We mustn't apply @@ -3758,9 +3766,10 @@ vinyl_iterator_primary_next(struct iterator *base, struct tuple **ret) if (vinyl_iterator_check_tx(it) != 0) goto fail; - if (vy_read_iterator_next(&it->iterator, ret) != 0) + hint_t hint; + if (vy_read_iterator_next(&it->iterator, ret, &hint) != 0) goto fail; - vy_read_iterator_cache_add(&it->iterator, *ret); + vy_read_iterator_cache_add(&it->iterator, *ret, hint); if (*ret == NULL) { /* EOF. Close the iterator immediately. */ vinyl_iterator_close(it); @@ -3780,17 +3789,18 @@ vinyl_iterator_secondary_next(struct iterator *base, struct tuple **ret) struct vinyl_iterator *it = (struct vinyl_iterator *)base; assert(it->lsm->index_id > 0); struct tuple *tuple; + hint_t hint; next: if (vinyl_iterator_check_tx(it) != 0) goto fail; - if (vy_read_iterator_next(&it->iterator, &tuple) != 0) + if (vy_read_iterator_next(&it->iterator, &tuple, &hint) != 0) goto fail; if (tuple == NULL) { /* EOF. Close the iterator immediately. */ - vy_read_iterator_cache_add(&it->iterator, NULL); + vy_read_iterator_cache_add(&it->iterator, NULL, HINT_NONE); vinyl_iterator_close(it); *ret = NULL; return 0; @@ -3806,11 +3816,11 @@ next: /* Get the full tuple from the primary index. */ if (vy_get_by_secondary_tuple(it->lsm, it->tx, vy_tx_read_view(it->tx), - tuple, ret) != 0) + tuple, hint, ret) != 0) goto fail; if (*ret == NULL) goto next; - vy_read_iterator_cache_add(&it->iterator, *ret); + vy_read_iterator_cache_add(&it->iterator, *ret, hint); tuple_bless(*ret); tuple_unref(*ret); return 0; @@ -4102,9 +4112,10 @@ vy_build_recover_stmt(struct vy_lsm *lsm, struct vy_lsm *pk, /* Lookup the tuple that was affected by this statement. */ const struct vy_read_view rv = { .vlsn = lsn - 1 }; const struct vy_read_view *p_rv = &rv; + hint_t hint; struct tuple *old_tuple; if (vy_point_lookup(pk, NULL, &p_rv, (struct tuple *)mem_stmt, - &old_tuple) != 0) + &old_tuple, &hint) != 0) return -1; /* * Create DELETE + INSERT statements corresponding to @@ -4263,9 +4274,10 @@ vinyl_space_build_index(struct space *src_space, struct index *new_index, &env->xm->p_committed_read_view); int rc; int loops = 0; + hint_t hint; struct tuple *tuple; int64_t build_lsn = env->xm->lsn; - while ((rc = vy_read_iterator_next(&itr, &tuple)) == 0) { + while ((rc = vy_read_iterator_next(&itr, &tuple, &hint)) == 0) { if (tuple == NULL) break; /* diff --git a/src/box/vy_cache.c b/src/box/vy_cache.c index a4a767bc..ee3581f3 100644 --- a/src/box/vy_cache.c +++ b/src/box/vy_cache.c @@ -229,9 +229,9 @@ vy_cache_env_set_quota(struct vy_cache_env *env, size_t quota) } void -vy_cache_add(struct vy_cache *cache, struct tuple *stmt, - struct tuple *prev_stmt, const struct tuple *key, - enum iterator_type order) +vy_cache_add(struct vy_cache *cache, struct tuple *stmt, hint_t hint, + struct tuple *prev_stmt, hint_t prev_hint, + const struct tuple *key, enum iterator_type order) { if (cache->env->mem_quota == 0) { /* Cache is disabled. */ @@ -259,11 +259,6 @@ vy_cache_add(struct vy_cache *cache, struct tuple *stmt, return; } - hint_t hint = stmt == NULL ? HINT_NONE : - vy_stmt_hint(stmt, cache->cmp_def); - hint_t prev_hint = prev_stmt == NULL ? HINT_NONE : - vy_stmt_hint(prev_stmt, cache->cmp_def); - int direction = iterator_direction(order); /** * Let's determine boundary_level (left/right) of the new record @@ -446,11 +441,10 @@ vy_cache_get(struct vy_cache *cache, const struct tuple *key, void vy_cache_on_write(struct vy_cache *cache, const struct tuple *stmt, - struct tuple **deleted) + hint_t hint, struct tuple **deleted) { vy_cache_gc(cache->env); bool exact = false; - hint_t hint = vy_stmt_hint(stmt, cache->cmp_def); struct vy_cache_tree_key tree_key; tree_key = vy_cache_tree_key(stmt, hint); struct vy_cache_tree_iterator itr; diff --git a/src/box/vy_cache.h b/src/box/vy_cache.h index d256f32c..9be2fe68 100644 --- a/src/box/vy_cache.h +++ b/src/box/vy_cache.h @@ -213,15 +213,17 @@ vy_cache_destroy(struct vy_cache *cache); * @param cache - pointer to tuple cache. * @param stmt - statement that was recently read and should be added to the * cache. + * @param hint - statement comparison hint. * @param prev_stmt - previous statement that was read by the reader in one * sequence (by one iterator). + * @param prev_hint - previous statement comparison hint. * @param direction - direction in which the reader (iterator) observes data, * +1 - forward, -1 - backward. */ void -vy_cache_add(struct vy_cache *cache, struct tuple *stmt, - struct tuple *prev_stmt, const struct tuple *key, - enum iterator_type order); +vy_cache_add(struct vy_cache *cache, struct tuple *stmt, hint_t hint, + struct tuple *prev_stmt, hint_t prev_hint, + const struct tuple *key, enum iterator_type order); /** * Find value in cache. @@ -235,12 +237,13 @@ vy_cache_get(struct vy_cache *cache, const struct tuple *key, * Invalidate possibly cached value due to its overwriting * @param cache - pointer to tuple cache. * @param stmt - overwritten statement. + * @param hint - statement comparison hint. * @param[out] deleted - If not NULL, then is set to deleted * statement. */ void vy_cache_on_write(struct vy_cache *cache, const struct tuple *stmt, - struct tuple **deleted); + hint_t hint, struct tuple **deleted); /** diff --git a/src/box/vy_lsm.c b/src/box/vy_lsm.c index 4065f711..8230410d 100644 --- a/src/box/vy_lsm.c +++ b/src/box/vy_lsm.c @@ -1066,7 +1066,7 @@ vy_lsm_commit_stmt(struct vy_lsm *lsm, struct vy_mem *mem, vy_stmt_counter_acct_tuple(&lsm->stat.put, stmt); /* Invalidate cache element. */ - vy_cache_on_write(&lsm->cache, stmt, NULL); + vy_cache_on_write(&lsm->cache, stmt, hint, NULL); } void @@ -1076,7 +1076,7 @@ vy_lsm_rollback_stmt(struct vy_lsm *lsm, struct vy_mem *mem, vy_mem_rollback_stmt(mem, stmt, hint); /* Invalidate cache element. */ - vy_cache_on_write(&lsm->cache, stmt, NULL); + vy_cache_on_write(&lsm->cache, stmt, hint, NULL); } int diff --git a/src/box/vy_point_lookup.c b/src/box/vy_point_lookup.c index 25125662..bac6db2b 100644 --- a/src/box/vy_point_lookup.c +++ b/src/box/vy_point_lookup.c @@ -197,14 +197,15 @@ vy_point_lookup_scan_slices(struct vy_lsm *lsm, const struct vy_read_view **rv, int vy_point_lookup(struct vy_lsm *lsm, struct vy_tx *tx, - const struct vy_read_view **rv, - struct tuple *key, struct tuple **ret) + const struct vy_read_view **rv, struct tuple *key, + struct tuple **ret, hint_t *ret_hint) { /* All key parts must be set for a point lookup. */ assert(vy_stmt_is_full_key(key, lsm->cmp_def)); assert(tx == NULL || tx->state == VINYL_TX_READY); *ret = NULL; + *ret_hint = HINT_NONE; double start_time = ev_monotonic_now(loop()); int rc = 0; @@ -291,10 +292,9 @@ done: vy_history_splice(&history, &disk_history); if (rc == 0) { - hint_t unused; int upserts_applied; rc = vy_history_apply(&history, lsm->cmp_def, false, - &upserts_applied, ret, &unused); + &upserts_applied, ret, ret_hint); lsm->stat.upsert.applied += upserts_applied; } vy_history_cleanup(&history); diff --git a/src/box/vy_point_lookup.h b/src/box/vy_point_lookup.h index 6d77ce9c..a0e23ecb 100644 --- a/src/box/vy_point_lookup.h +++ b/src/box/vy_point_lookup.h @@ -46,6 +46,7 @@ */ #include +#include "key_def.h" #if defined(__cplusplus) extern "C" { @@ -68,8 +69,8 @@ struct tuple; */ int vy_point_lookup(struct vy_lsm *lsm, struct vy_tx *tx, - const struct vy_read_view **rv, - struct tuple *key, struct tuple **ret); + const struct vy_read_view **rv, struct tuple *key, + struct tuple **ret, hint_t *ret_hint); /** * Look up a tuple by key in memory. diff --git a/src/box/vy_read_iterator.c b/src/box/vy_read_iterator.c index b96a5d19..d0b25610 100644 --- a/src/box/vy_read_iterator.c +++ b/src/box/vy_read_iterator.c @@ -715,6 +715,7 @@ vy_read_iterator_open(struct vy_read_iterator *itr, struct vy_lsm *lsm, itr->hint = vy_stmt_hint(key, lsm->cmp_def); itr->read_view = rv; itr->last_hint = HINT_NONE; + itr->last_cached_hint = HINT_NONE; if (vy_stmt_is_empty_key(key)) { /* @@ -893,7 +894,8 @@ vy_read_iterator_track_read(struct vy_read_iterator *itr, struct tuple *stmt) } NODISCARD int -vy_read_iterator_next(struct vy_read_iterator *itr, struct tuple **result) +vy_read_iterator_next(struct vy_read_iterator *itr, + struct tuple **result, hint_t *result_hint) { assert(itr->tx == NULL || itr->tx->state == VINYL_TX_READY); @@ -930,6 +932,7 @@ next_key: if (itr->last_cached_stmt != NULL) tuple_unref(itr->last_cached_stmt); itr->last_cached_stmt = NULL; + itr->last_cached_hint = HINT_NONE; } goto next_key; } @@ -952,11 +955,13 @@ next_key: } *result = stmt; + *result_hint = hint; return 0; } void -vy_read_iterator_cache_add(struct vy_read_iterator *itr, struct tuple *stmt) +vy_read_iterator_cache_add(struct vy_read_iterator *itr, + struct tuple *stmt, hint_t hint) { if ((**itr->read_view).vlsn != INT64_MAX) { if (itr->last_cached_stmt != NULL) @@ -964,13 +969,14 @@ vy_read_iterator_cache_add(struct vy_read_iterator *itr, struct tuple *stmt) itr->last_cached_stmt = NULL; return; } - vy_cache_add(&itr->lsm->cache, stmt, itr->last_cached_stmt, - itr->key, itr->iterator_type); + vy_cache_add(&itr->lsm->cache, stmt, hint, itr->last_cached_stmt, + itr->last_cached_hint, itr->key, itr->iterator_type); if (stmt != NULL) tuple_ref(stmt); if (itr->last_cached_stmt != NULL) tuple_unref(itr->last_cached_stmt); itr->last_cached_stmt = stmt; + itr->last_cached_hint = hint; } /** diff --git a/src/box/vy_read_iterator.h b/src/box/vy_read_iterator.h index d8251372..fd876fcc 100644 --- a/src/box/vy_read_iterator.h +++ b/src/box/vy_read_iterator.h @@ -75,6 +75,10 @@ struct vy_read_iterator { */ struct tuple *last_cached_stmt; /** + * Comparison hint of the last cached statement. + */ + hint_t last_cached_hint; + /** * Copy of lsm->range_tree_version. * Used for detecting range tree changes. */ @@ -144,17 +148,20 @@ vy_read_iterator_open(struct vy_read_iterator *itr, struct vy_lsm *lsm, * if it wasn't started. * @param itr Read iterator. * @param[out] result Found statement is stored here. + * @param[out] hint Comparison hint of the found statement. * * @retval 0 Success. * @retval -1 Read error. */ NODISCARD int -vy_read_iterator_next(struct vy_read_iterator *itr, struct tuple **result); +vy_read_iterator_next(struct vy_read_iterator *itr, + struct tuple **result, hint_t *hint); /** * Add the last tuple returned by the read iterator to the cache. * @param itr Read iterator * @param stmt Last tuple returned by the iterator. + * @param hint Comparison hint of the last statement. * * We use a separate function for populating the cache rather than * doing that right in vy_read_iterator_next() so that we can store @@ -168,7 +175,8 @@ vy_read_iterator_next(struct vy_read_iterator *itr, struct tuple **result); * the result to the cache. */ void -vy_read_iterator_cache_add(struct vy_read_iterator *itr, struct tuple *stmt); +vy_read_iterator_cache_add(struct vy_read_iterator *itr, + struct tuple *stmt, hint_t hint); /** * Close the iterator and free resources. diff --git a/src/box/vy_tx.c b/src/box/vy_tx.c index fd8822a1..5ded9637 100644 --- a/src/box/vy_tx.c +++ b/src/box/vy_tx.c @@ -515,7 +515,7 @@ vy_tx_write(struct vy_lsm *lsm, struct vy_mem *mem, if (vy_stmt_type(stmt) == IPROTO_UPSERT) { struct tuple *deleted = NULL; /* Invalidate cache element. */ - vy_cache_on_write(&lsm->cache, stmt, &deleted); + vy_cache_on_write(&lsm->cache, stmt, hint, &deleted); if (deleted != NULL) { struct tuple *applied = vy_apply_upsert(stmt, deleted, mem->cmp_def, false); @@ -534,7 +534,7 @@ vy_tx_write(struct vy_lsm *lsm, struct vy_mem *mem, } } else { /* Invalidate cache element. */ - vy_cache_on_write(&lsm->cache, stmt, NULL); + vy_cache_on_write(&lsm->cache, stmt, hint, NULL); } return vy_lsm_set(lsm, mem, stmt, hint, region_stmt); } diff --git a/test/unit/vy_iterators_helper.c b/test/unit/vy_iterators_helper.c index d2ac21a0..1f895840 100644 --- a/test/unit/vy_iterators_helper.c +++ b/test/unit/vy_iterators_helper.c @@ -156,15 +156,21 @@ vy_cache_insert_templates_chain(struct vy_cache *cache, { struct tuple *key = vy_new_simple_stmt(format, key_templ); struct tuple *prev_stmt = NULL; + hint_t prev_hint = HINT_NONE; struct tuple *stmt = NULL; + hint_t hint = HINT_NONE; for (uint i = 0; i < length; ++i) { stmt = vy_new_simple_stmt(format, &chain[i]); - vy_cache_add(cache, stmt, prev_stmt, key, order); + hint = vy_stmt_hint(stmt, cache->cmp_def); + vy_cache_add(cache, stmt, hint, prev_stmt, prev_hint, + key, order); if (i != 0) tuple_unref(prev_stmt); prev_stmt = stmt; + prev_hint = hint; stmt = NULL; + hint = HINT_NONE; } tuple_unref(key); if (prev_stmt != NULL) @@ -176,7 +182,8 @@ vy_cache_on_write_template(struct vy_cache *cache, struct tuple_format *format, const struct vy_stmt_template *templ) { struct tuple *written = vy_new_simple_stmt(format, templ); - vy_cache_on_write(cache, written, NULL); + hint_t hint = vy_stmt_hint(written, cache->cmp_def); + vy_cache_on_write(cache, written, hint, NULL); tuple_unref(written); } diff --git a/test/unit/vy_point_lookup.c b/test/unit/vy_point_lookup.c index eef50c30..93841c0a 100644 --- a/test/unit/vy_point_lookup.c +++ b/test/unit/vy_point_lookup.c @@ -275,8 +275,9 @@ test_basic() STMT_TEMPLATE(0, SELECT, i); struct tuple *key = vy_new_simple_stmt(format, &tmpl_key); + hint_t hint; struct tuple *res; - rc = vy_point_lookup(pk, NULL, &prv, key, &res); + rc = vy_point_lookup(pk, NULL, &prv, key, &res, &hint); tuple_unref(key); if (rc != 0) { has_errors = true; -- 2.11.0