[PATCH 10/13] vinyl: forward tuple comparison hints to cache tree
Vladimir Davydov
vdavydov.dev at gmail.com
Tue Apr 2 20:33:47 MSK 2019
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 <stdbool.h>
+#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
More information about the Tarantool-patches
mailing list