* [PATCH v2 01/14] vinyl: remove optimized comparators
2019-03-13 8:52 [PATCH v2 00/14] vinyl: do not fill secondary tuples with nulls Vladimir Davydov
@ 2019-03-13 8:52 ` Vladimir Davydov
2019-03-13 8:55 ` Konstantin Osipov
2019-03-13 8:52 ` [PATCH v2 02/14] vinyl: introduce statement environment Vladimir Davydov
` (13 subsequent siblings)
14 siblings, 1 reply; 34+ messages in thread
From: Vladimir Davydov @ 2019-03-13 8:52 UTC (permalink / raw)
To: kostja; +Cc: tarantool-patches
A vinyl statement (vy_stmt struct) may represent either a tuple or a
key. We differentiate between the two kinds by statement type - we use
SELECT for keys and other types for tuples. This was done that way so
that we could pass both tuples and keys to a read iterator as a search
key. To avoid branching in comparators when the types of compared
statements are known in advance, we provide several comparators, each of
which expects certain statement types, e.g. a tuple and a key. Actually,
such a micro optimization looks like an overkill, because a typical
comparator is called by function pointer and has a lot of comparisons
in the code, see tuple_compare_slowpath for instance. Eliminating one
branch will hardly make the code perform better. At the same time, it
makes the code more difficult to write. Besides, once we remove nils
from statements read from disk (aka surrogate tuples), which will
ease implementation of multikey indexes, the number of places where
types of compared statements are known will diminish drastically.
That said, let's remove optimized comparators and always use
vy_stmt_compare, which checks types of compared statements and calls
the appropriate comparator.
---
src/box/vinyl.c | 8 +--
src/box/vy_cache.c | 8 +--
src/box/vy_cache.h | 2 +-
src/box/vy_lsm.c | 8 +--
src/box/vy_mem.c | 13 +++--
src/box/vy_mem.h | 2 +-
src/box/vy_range.c | 13 +++--
src/box/vy_read_iterator.c | 22 ++++----
src/box/vy_run.c | 36 ++++++-------
src/box/vy_stmt.h | 121 +++++++-------------------------------------
src/box/vy_tx.c | 6 +--
src/box/vy_upsert.c | 2 +-
src/box/vy_write_iterator.c | 2 +-
13 files changed, 76 insertions(+), 167 deletions(-)
diff --git a/src/box/vinyl.c b/src/box/vinyl.c
index 63ceab41..4ffa79bf 100644
--- a/src/box/vinyl.c
+++ b/src/box/vinyl.c
@@ -1305,7 +1305,7 @@ vy_get_by_secondary_tuple(struct vy_lsm *lsm, struct vy_tx *tx,
return -1;
if (*result == NULL ||
- vy_tuple_compare(*result, tuple, lsm->key_def) != 0) {
+ vy_stmt_compare(*result, tuple, lsm->key_def) != 0) {
/*
* If a tuple read from a secondary index doesn't
* match the tuple corresponding to it in the
@@ -1524,7 +1524,7 @@ vy_check_is_unique_secondary(struct vy_tx *tx, const struct vy_read_view **rv,
* fail here.
*/
if (found != NULL && vy_stmt_type(stmt) == IPROTO_REPLACE &&
- vy_tuple_compare(stmt, found, lsm->pk->key_def) == 0) {
+ vy_stmt_compare(stmt, found, lsm->pk->key_def) == 0) {
tuple_unref(found);
return 0;
}
@@ -1729,7 +1729,7 @@ vy_check_update(struct space *space, const struct vy_lsm *pk,
uint64_t column_mask)
{
if (!key_update_can_be_skipped(pk->key_def->column_mask, column_mask) &&
- vy_tuple_compare(old_tuple, new_tuple, pk->key_def) != 0) {
+ vy_stmt_compare(old_tuple, new_tuple, pk->key_def) != 0) {
diag_set(ClientError, ER_CANT_UPDATE_PRIMARY_KEY,
index_name_by_id(space, pk->index_id),
space_name(space));
@@ -3513,7 +3513,7 @@ vy_squash_process(struct vy_squash *squash)
while (!vy_mem_tree_iterator_is_invalid(&mem_itr)) {
const struct tuple *mem_stmt;
mem_stmt = *vy_mem_tree_iterator_get_elem(&mem->tree, &mem_itr);
- if (vy_tuple_compare(result, mem_stmt, lsm->cmp_def) != 0 ||
+ if (vy_stmt_compare(result, mem_stmt, lsm->cmp_def) != 0 ||
vy_stmt_type(mem_stmt) != IPROTO_UPSERT)
break;
assert(vy_stmt_lsn(mem_stmt) >= MAX_LSN);
diff --git a/src/box/vy_cache.c b/src/box/vy_cache.c
index 320ea04d..8354b1c2 100644
--- a/src/box/vy_cache.c
+++ b/src/box/vy_cache.c
@@ -370,8 +370,8 @@ vy_cache_add(struct vy_cache *cache, struct tuple *stmt,
&inserted);
assert(*prev_check_entry != NULL);
struct tuple *prev_check_stmt = (*prev_check_entry)->stmt;
- int cmp = vy_tuple_compare(prev_stmt, prev_check_stmt,
- cache->cmp_def);
+ int cmp = vy_stmt_compare(prev_stmt, prev_check_stmt,
+ cache->cmp_def);
if (entry->flags & flag) {
/* The found entry must be exactly prev_stmt. (2) */
@@ -722,8 +722,8 @@ vy_cache_iterator_skip(struct vy_cache_iterator *itr,
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))
+ vy_stmt_compare(itr->curr_stmt, last_stmt,
+ itr->cache->cmp_def) > 0))
return 0;
*stop = false;
diff --git a/src/box/vy_cache.h b/src/box/vy_cache.h
index 7cb93155..a846622e 100644
--- a/src/box/vy_cache.h
+++ b/src/box/vy_cache.h
@@ -74,7 +74,7 @@ static inline int
vy_cache_tree_cmp(struct vy_cache_entry *a,
struct vy_cache_entry *b, struct key_def *cmp_def)
{
- return vy_tuple_compare(a->stmt, b->stmt, cmp_def);
+ return vy_stmt_compare(a->stmt, b->stmt, cmp_def);
}
/**
diff --git a/src/box/vy_lsm.c b/src/box/vy_lsm.c
index 07da145b..52183799 100644
--- a/src/box/vy_lsm.c
+++ b/src/box/vy_lsm.c
@@ -405,7 +405,7 @@ vy_lsm_recover_slice(struct vy_lsm *lsm, struct vy_range *range,
goto out;
}
if (begin != NULL && end != NULL &&
- vy_key_compare(begin, end, lsm->cmp_def) >= 0) {
+ vy_stmt_compare(begin, end, lsm->cmp_def) >= 0) {
diag_set(ClientError, ER_INVALID_VYLOG_FILE,
tt_sprintf("begin >= end for slice %lld",
(long long)slice_info->id));
@@ -451,7 +451,7 @@ vy_lsm_recover_range(struct vy_lsm *lsm,
goto out;
}
if (begin != NULL && end != NULL &&
- vy_key_compare(begin, end, lsm->cmp_def) >= 0) {
+ vy_stmt_compare(begin, end, lsm->cmp_def) >= 0) {
diag_set(ClientError, ER_INVALID_VYLOG_FILE,
tt_sprintf("begin >= end for range %lld",
(long long)range_info->id));
@@ -632,8 +632,8 @@ vy_lsm_recover(struct vy_lsm *lsm, struct vy_recovery *recovery,
int cmp = 0;
if (prev != NULL &&
(prev->end == NULL || range->begin == NULL ||
- (cmp = vy_key_compare(prev->end, range->begin,
- lsm->cmp_def)) != 0)) {
+ (cmp = vy_stmt_compare(prev->end, range->begin,
+ lsm->cmp_def)) != 0)) {
const char *errmsg = cmp > 0 ?
"Nearby ranges %lld and %lld overlap" :
"Keys between ranges %lld and %lld not spanned";
diff --git a/src/box/vy_mem.c b/src/box/vy_mem.c
index 6bc3859c..c47a3c36 100644
--- a/src/box/vy_mem.c
+++ b/src/box/vy_mem.c
@@ -146,7 +146,7 @@ vy_mem_older_lsn(struct vy_mem *mem, const struct tuple *stmt)
const struct tuple *result;
result = *vy_mem_tree_iterator_get_elem(&mem->tree, &itr);
- if (vy_tuple_compare(result, stmt, mem->cmp_def) != 0)
+ if (vy_stmt_compare(result, stmt, mem->cmp_def) != 0)
return NULL;
return result;
}
@@ -195,7 +195,7 @@ vy_mem_insert_upsert(struct vy_mem *mem, const struct tuple *stmt)
const struct tuple **older = vy_mem_tree_iterator_get_elem(&mem->tree,
&inserted);
if (older == NULL || vy_stmt_type(*older) != IPROTO_UPSERT ||
- vy_tuple_compare(stmt, *older, mem->cmp_def) != 0)
+ vy_stmt_compare(stmt, *older, mem->cmp_def) != 0)
return 0;
uint8_t n_upserts = vy_stmt_n_upserts(*older);
/*
@@ -339,7 +339,7 @@ vy_mem_iterator_find_lsn(struct vy_mem_iterator *itr)
const struct tuple *prev_stmt;
prev_stmt = *vy_mem_tree_iterator_get_elem(&itr->mem->tree, &prev_pos);
if (vy_stmt_lsn(prev_stmt) > (**itr->read_view).vlsn ||
- vy_tuple_compare(itr->curr_stmt, prev_stmt, cmp_def) != 0) {
+ vy_stmt_compare(itr->curr_stmt, prev_stmt, cmp_def) != 0) {
/*
* The next statement is either invisible in
* the read view or for another key.
@@ -488,7 +488,7 @@ vy_mem_iterator_next_key(struct vy_mem_iterator *itr)
* for this key so instead of iterating further we simply
* look up the next key - it's pretty cheap anyway.
*/
- if (vy_tuple_compare(prev_stmt, itr->curr_stmt, cmp_def) == 0)
+ if (vy_stmt_compare(prev_stmt, itr->curr_stmt, cmp_def) == 0)
return vy_mem_iterator_seek(itr, itr->curr_stmt);
if (itr->iterator_type == ITER_EQ &&
@@ -523,7 +523,7 @@ next:
const struct tuple *next_stmt;
next_stmt = *vy_mem_tree_iterator_get_elem(&itr->mem->tree, &next_pos);
- if (vy_tuple_compare(itr->curr_stmt, next_stmt, cmp_def) != 0)
+ if (vy_stmt_compare(itr->curr_stmt, next_stmt, cmp_def) != 0)
return 1;
itr->curr_pos = next_pos;
@@ -577,8 +577,7 @@ vy_mem_iterator_skip(struct vy_mem_iterator *itr,
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))
+ vy_stmt_compare(itr->curr_stmt, last_stmt, itr->mem->cmp_def) > 0))
return 0;
vy_history_cleanup(history);
diff --git a/src/box/vy_mem.h b/src/box/vy_mem.h
index b41c3c0b..39f238b3 100644
--- a/src/box/vy_mem.h
+++ b/src/box/vy_mem.h
@@ -90,7 +90,7 @@ static int
vy_mem_tree_cmp(const struct tuple *a, const struct tuple *b,
struct key_def *cmp_def)
{
- int res = vy_tuple_compare(a, b, cmp_def);
+ int res = vy_stmt_compare(a, b, cmp_def);
if (res)
return res;
int64_t a_lsn = vy_stmt_lsn(a), b_lsn = vy_stmt_lsn(b);
diff --git a/src/box/vy_range.c b/src/box/vy_range.c
index 2a2d2d00..f76615c4 100644
--- a/src/box/vy_range.c
+++ b/src/box/vy_range.c
@@ -63,8 +63,8 @@ vy_range_tree_cmp(struct vy_range *range_a, struct vy_range *range_b)
return 1;
assert(range_a->cmp_def == range_b->cmp_def);
- return vy_key_compare(range_a->begin, range_b->begin,
- range_a->cmp_def);
+ return vy_stmt_compare(range_a->begin, range_b->begin,
+ range_a->cmp_def);
}
int
@@ -73,7 +73,7 @@ vy_range_tree_key_cmp(const struct tuple *stmt, struct vy_range *range)
/* Any key > -inf. */
if (range->begin == NULL)
return 1;
- return vy_stmt_compare_with_key(stmt, range->begin, range->cmp_def);
+ return vy_stmt_compare(stmt, range->begin, range->cmp_def);
}
struct vy_range *
@@ -125,8 +125,7 @@ vy_range_tree_find_by_key(vy_range_tree_t *tree,
/* switch to previous for case (4) */
if (range != NULL && range->begin != NULL &&
!vy_stmt_is_full_key(key, range->cmp_def) &&
- vy_stmt_compare_with_key(key, range->begin,
- range->cmp_def) == 0)
+ vy_stmt_compare(key, range->begin, range->cmp_def) == 0)
range = vy_range_tree_prev(tree, range);
/* for case 5 or subcase of case 4 */
if (range == NULL)
@@ -160,8 +159,8 @@ vy_range_tree_find_by_key(vy_range_tree_t *tree,
if (range != NULL) {
/* fix curr_range for cases 2 and 3 */
if (range->begin != NULL &&
- vy_stmt_compare_with_key(key, range->begin,
- range->cmp_def) != 0) {
+ vy_stmt_compare(key, range->begin,
+ range->cmp_def) != 0) {
struct vy_range *prev;
prev = vy_range_tree_prev(tree, range);
if (prev != NULL)
diff --git a/src/box/vy_read_iterator.c b/src/box/vy_read_iterator.c
index 740ee940..94c5f4b9 100644
--- a/src/box/vy_read_iterator.c
+++ b/src/box/vy_read_iterator.c
@@ -148,17 +148,17 @@ vy_read_iterator_range_is_done(struct vy_read_iterator *itr,
int dir = iterator_direction(itr->iterator_type);
if (dir > 0 && range->end != NULL &&
- (next_key == NULL || vy_tuple_compare_with_key(next_key,
- range->end, cmp_def) >= 0) &&
+ (next_key == NULL || vy_stmt_compare(next_key, range->end,
+ cmp_def) >= 0) &&
(itr->iterator_type != ITER_EQ ||
- vy_stmt_compare_with_key(itr->key, range->end, cmp_def) >= 0))
+ vy_stmt_compare(itr->key, range->end, cmp_def) >= 0))
return true;
if (dir < 0 && range->begin != NULL &&
- (next_key == NULL || vy_tuple_compare_with_key(next_key,
- range->begin, cmp_def) < 0) &&
+ (next_key == NULL || vy_stmt_compare(next_key, range->begin,
+ cmp_def) < 0) &&
(itr->iterator_type != ITER_REQ ||
- vy_stmt_compare_with_key(itr->key, range->begin, cmp_def) <= 0))
+ vy_stmt_compare(itr->key, range->begin, cmp_def) <= 0))
return true;
return false;
@@ -185,7 +185,7 @@ vy_read_iterator_cmp_stmt(struct vy_read_iterator *itr,
if (a == NULL && b == NULL)
return 0;
return iterator_direction(itr->iterator_type) *
- vy_tuple_compare(a, b, itr->lsm->cmp_def);
+ vy_stmt_compare(a, b, itr->lsm->cmp_def);
}
/**
@@ -763,12 +763,12 @@ vy_read_iterator_next_range(struct vy_read_iterator *itr)
* Make sure the next statement falls in the range.
*/
if (dir > 0 && (range->end == NULL ||
- vy_tuple_compare_with_key(itr->last_stmt,
- range->end, cmp_def) < 0))
+ vy_stmt_compare(itr->last_stmt, range->end,
+ cmp_def) < 0))
break;
if (dir < 0 && (range->begin == NULL ||
- vy_tuple_compare_with_key(itr->last_stmt,
- range->begin, cmp_def) > 0))
+ vy_stmt_compare(itr->last_stmt, range->begin,
+ cmp_def) > 0))
break;
}
itr->curr_range = range;
diff --git a/src/box/vy_run.c b/src/box/vy_run.c
index fae123d8..8d40ef00 100644
--- a/src/box/vy_run.c
+++ b/src/box/vy_run.c
@@ -449,21 +449,21 @@ vy_slice_cut(struct vy_slice *slice, int64_t id, struct tuple *begin,
*result = NULL;
if (begin != NULL && slice->end != NULL &&
- vy_key_compare(begin, slice->end, cmp_def) >= 0)
+ vy_stmt_compare(begin, slice->end, cmp_def) >= 0)
return 0; /* no intersection: begin >= slice->end */
if (end != NULL && slice->begin != NULL &&
- vy_key_compare(end, slice->begin, cmp_def) <= 0)
+ vy_stmt_compare(end, slice->begin, cmp_def) <= 0)
return 0; /* no intersection: end <= slice->end */
/* begin = MAX(begin, slice->begin) */
if (slice->begin != NULL &&
- (begin == NULL || vy_key_compare(begin, slice->begin, cmp_def) < 0))
+ (begin == NULL || vy_stmt_compare(begin, slice->begin, cmp_def) < 0))
begin = slice->begin;
/* end = MIN(end, slice->end) */
if (slice->end != NULL &&
- (end == NULL || vy_key_compare(end, slice->end, cmp_def) > 0))
+ (end == NULL || vy_stmt_compare(end, slice->end, cmp_def) > 0))
end = slice->end;
*result = vy_slice_new(id, slice->run, begin, end, cmp_def);
@@ -1206,8 +1206,8 @@ vy_run_iterator_find_lsn(struct vy_run_iterator *itr,
return -1;
if (vy_stmt_lsn(test_stmt) > (**itr->read_view).vlsn ||
vy_stmt_flags(test_stmt) & VY_STMT_SKIP_READ ||
- vy_tuple_compare(itr->curr_stmt, test_stmt,
- cmp_def) != 0) {
+ vy_stmt_compare(itr->curr_stmt, test_stmt,
+ cmp_def) != 0) {
tuple_unref(test_stmt);
break;
}
@@ -1219,8 +1219,7 @@ 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 (slice->begin != NULL &&
- vy_tuple_compare_with_key(itr->curr_stmt, slice->begin,
- cmp_def) < 0) {
+ vy_stmt_compare(itr->curr_stmt, slice->begin, cmp_def) < 0) {
vy_run_iterator_stop(itr);
return 0;
}
@@ -1228,8 +1227,7 @@ vy_run_iterator_find_lsn(struct vy_run_iterator *itr,
assert(iterator_type == ITER_GE || iterator_type == ITER_GT ||
iterator_type == ITER_EQ);
if (slice->end != NULL &&
- vy_tuple_compare_with_key(itr->curr_stmt, slice->end,
- cmp_def) >= 0) {
+ vy_stmt_compare(itr->curr_stmt, slice->end, cmp_def) >= 0) {
vy_run_iterator_stop(itr);
return 0;
}
@@ -1360,7 +1358,7 @@ vy_run_iterator_seek(struct vy_run_iterator *itr,
* | ge | begin | ge |
* | eq | stop |
*/
- cmp = vy_stmt_compare_with_key(key, slice->begin, cmp_def);
+ cmp = vy_stmt_compare(key, slice->begin, cmp_def);
if (cmp < 0 && iterator_type == ITER_EQ) {
vy_run_iterator_stop(itr);
*ret = NULL;
@@ -1387,7 +1385,7 @@ vy_run_iterator_seek(struct vy_run_iterator *itr,
* > end | lt | end | lt |
* | le | end | lt |
*/
- cmp = vy_stmt_compare_with_key(key, slice->end, cmp_def);
+ 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;
@@ -1480,7 +1478,7 @@ vy_run_iterator_next_key(struct vy_run_iterator *itr, struct tuple **ret)
if (vy_run_iterator_read(itr, itr->curr_pos, &next_key) != 0)
return -1;
- } while (vy_tuple_compare(itr->curr_stmt, next_key, itr->cmp_def) == 0);
+ } while (vy_stmt_compare(itr->curr_stmt, next_key, itr->cmp_def) == 0);
tuple_unref(itr->curr_stmt);
itr->curr_stmt = next_key;
@@ -1521,7 +1519,7 @@ next:
if (vy_run_iterator_read(itr, next_pos, &next_key) != 0)
return -1;
- if (vy_tuple_compare(itr->curr_stmt, next_key, itr->cmp_def) != 0) {
+ if (vy_stmt_compare(itr->curr_stmt, next_key, itr->cmp_def) != 0) {
tuple_unref(next_key);
return 0;
}
@@ -1571,8 +1569,7 @@ vy_run_iterator_skip(struct vy_run_iterator *itr,
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))
+ vy_stmt_compare(itr->curr_stmt, last_stmt, itr->cmp_def) > 0))
return 0;
vy_history_cleanup(history);
@@ -2585,8 +2582,8 @@ vy_slice_stream_search(struct vy_stmt_stream *virt_stream)
stream->is_primary);
if (fnd_key == NULL)
return -1;
- int cmp = vy_tuple_compare_with_key(fnd_key,
- stream->slice->begin, stream->cmp_def);
+ int cmp = vy_stmt_compare(fnd_key, stream->slice->begin,
+ stream->cmp_def);
if (cmp < 0)
beg = mid + 1;
else
@@ -2637,8 +2634,7 @@ vy_slice_stream_next(struct vy_stmt_stream *virt_stream, struct tuple **ret)
/* Check that the tuple is not out of slice bounds = */
if (stream->slice->end != NULL &&
stream->page_no >= stream->slice->last_page_no &&
- vy_tuple_compare_with_key(tuple, stream->slice->end,
- stream->cmp_def) >= 0) {
+ vy_stmt_compare(tuple, stream->slice->end, stream->cmp_def) >= 0) {
tuple_unref(tuple);
return 0;
}
diff --git a/src/box/vy_stmt.h b/src/box/vy_stmt.h
index 1dfbe1f7..98c1a2f3 100644
--- a/src/box/vy_stmt.h
+++ b/src/box/vy_stmt.h
@@ -321,94 +321,9 @@ vy_stmt_unref_if_possible(struct tuple *stmt)
}
/**
- * Specialized comparators are faster than general-purpose comparators.
- * For example, vy_stmt_compare - slowest comparator because it in worst case
- * checks all combinations of key and tuple types, but
- * vy_key_compare - fastest comparator, because it shouldn't check statement
- * types.
+ * Compare two vinyl statements taking into account their
+ * formats (key or tuple).
*/
-
-/**
- * Compare SELECT/DELETE statements using the key definition
- * @param a left operand (SELECT/DELETE)
- * @param b right operand (SELECT/DELETE)
- * @param cmp_def key definition, with primary parts
- *
- * @retval 0 if a == b
- * @retval > 0 if a > b
- * @retval < 0 if a < b
- *
- * @sa key_compare()
- */
-static inline int
-vy_key_compare(const struct tuple *a, const struct tuple *b,
- struct key_def *cmp_def)
-{
- assert(vy_stmt_type(a) == IPROTO_SELECT);
- assert(vy_stmt_type(b) == IPROTO_SELECT);
- return key_compare(tuple_data(a), tuple_data(b), cmp_def);
-}
-
-/**
- * Compare REPLACE/UPSERTS statements.
- * @param a left operand (REPLACE/UPSERT)
- * @param b right operand (REPLACE/UPSERT)
- * @param cmp_def key definition with primary parts
- *
- * @retval 0 if a == b
- * @retval > 0 if a > b
- * @retval < 0 if a < b
- *
- * @sa tuple_compare()
- */
-static inline int
-vy_tuple_compare(const struct tuple *a, const struct tuple *b,
- struct key_def *cmp_def)
-{
- enum iproto_type type;
- type = vy_stmt_type(a);
- assert(type == IPROTO_INSERT || type == IPROTO_REPLACE ||
- type == IPROTO_UPSERT || type == IPROTO_DELETE);
- type = vy_stmt_type(b);
- assert(type == IPROTO_INSERT || type == IPROTO_REPLACE ||
- type == IPROTO_UPSERT || type == IPROTO_DELETE);
- (void)type;
- return tuple_compare(a, b, cmp_def);
-}
-
-/**
- * Compare REPLACE/UPSERT with SELECT/DELETE using the key
- * definition
- * @param tuple Left operand (REPLACE/UPSERT)
- * @param key MessagePack array of key fields, right operand.
- *
- * @retval > 0 tuple > key.
- * @retval == 0 tuple == key in all fields
- * @retval == 0 tuple is prefix of key
- * @retval == 0 key is a prefix of tuple
- * @retval < 0 tuple < key.
- *
- * @sa tuple_compare_with_key()
- */
-static inline int
-vy_tuple_compare_with_raw_key(const struct tuple *tuple, const char *key,
- struct key_def *key_def)
-{
- uint32_t part_count = mp_decode_array(&key);
- return tuple_compare_with_key(tuple, key, part_count, key_def);
-}
-
-/** @sa vy_tuple_compare_with_raw_key(). */
-static inline int
-vy_tuple_compare_with_key(const struct tuple *tuple, const struct tuple *key,
- struct key_def *key_def)
-{
- const char *key_mp = tuple_data(key);
- uint32_t part_count = mp_decode_array(&key_mp);
- return tuple_compare_with_key(tuple, key_mp, part_count, key_def);
-}
-
-/** @sa tuple_compare. */
static inline int
vy_stmt_compare(const struct tuple *a, const struct tuple *b,
struct key_def *key_def)
@@ -416,36 +331,36 @@ vy_stmt_compare(const struct tuple *a, const struct tuple *b,
bool a_is_tuple = vy_stmt_type(a) != IPROTO_SELECT;
bool b_is_tuple = vy_stmt_type(b) != IPROTO_SELECT;
if (a_is_tuple && b_is_tuple) {
- return vy_tuple_compare(a, b, key_def);
+ return tuple_compare(a, b, key_def);
} else if (a_is_tuple && !b_is_tuple) {
- return vy_tuple_compare_with_key(a, b, key_def);
+ const char *key = tuple_data(b);
+ uint32_t part_count = mp_decode_array(&key);
+ return tuple_compare_with_key(a, key, part_count, key_def);
} else if (!a_is_tuple && b_is_tuple) {
- return -vy_tuple_compare_with_key(b, a, key_def);
+ const char *key = tuple_data(a);
+ uint32_t part_count = mp_decode_array(&key);
+ return -tuple_compare_with_key(b, key, part_count, key_def);
} else {
assert(!a_is_tuple && !b_is_tuple);
- return vy_key_compare(a, b, key_def);
+ return key_compare(tuple_data(a), tuple_data(b), key_def);
}
}
-/** @sa tuple_compare_with_raw_key. */
+/**
+ * Compare a vinyl statement (key or tuple) with a raw key
+ * (msgpack array).
+ */
static inline int
vy_stmt_compare_with_raw_key(const struct tuple *stmt, const char *key,
struct key_def *key_def)
{
- if (vy_stmt_type(stmt) != IPROTO_SELECT)
- return vy_tuple_compare_with_raw_key(stmt, key, key_def);
+ if (vy_stmt_type(stmt) != IPROTO_SELECT) {
+ uint32_t part_count = mp_decode_array(&key);
+ return tuple_compare_with_key(stmt, key, part_count, key_def);
+ }
return key_compare(tuple_data(stmt), key, key_def);
}
-/** @sa tuple_compare_with_key. */
-static inline int
-vy_stmt_compare_with_key(const struct tuple *stmt, const struct tuple *key,
- struct key_def *key_def)
-{
- assert(vy_stmt_type(key) == IPROTO_SELECT);
- return vy_stmt_compare_with_raw_key(stmt, tuple_data(key), key_def);
-}
-
/**
* Create the SELECT statement from raw MessagePack data.
* @param format Format of an index.
diff --git a/src/box/vy_tx.c b/src/box/vy_tx.c
index a125a4a7..3768b3bd 100644
--- a/src/box/vy_tx.c
+++ b/src/box/vy_tx.c
@@ -68,7 +68,7 @@ write_set_cmp(struct txv *a, struct txv *b)
{
int rc = a->lsm < b->lsm ? -1 : a->lsm > b->lsm;
if (rc == 0)
- return vy_tuple_compare(a->stmt, b->stmt, a->lsm->cmp_def);
+ return vy_stmt_compare(a->stmt, b->stmt, a->lsm->cmp_def);
return rc;
}
@@ -1213,8 +1213,8 @@ vy_txw_iterator_skip(struct vy_txw_iterator *itr,
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))
+ vy_stmt_compare(itr->curr_txv->stmt, last_stmt,
+ itr->lsm->cmp_def) > 0))
return 0;
vy_history_cleanup(history);
diff --git a/src/box/vy_upsert.c b/src/box/vy_upsert.c
index ebea2789..3c5a4abb 100644
--- a/src/box/vy_upsert.c
+++ b/src/box/vy_upsert.c
@@ -205,7 +205,7 @@ check_key:
* Check that key hasn't been changed after applying operations.
*/
if (!key_update_can_be_skipped(cmp_def->column_mask, column_mask) &&
- vy_tuple_compare(old_stmt, result_stmt, cmp_def) != 0) {
+ vy_stmt_compare(old_stmt, result_stmt, cmp_def) != 0) {
/*
* Key has been changed: ignore this UPSERT and
* @retval the old stmt.
diff --git a/src/box/vy_write_iterator.c b/src/box/vy_write_iterator.c
index 365b44bb..0e804ac1 100644
--- a/src/box/vy_write_iterator.c
+++ b/src/box/vy_write_iterator.c
@@ -225,7 +225,7 @@ heap_less(heap_t *heap, struct vy_write_src *src1, struct vy_write_src *src2)
struct vy_write_iterator *stream =
container_of(heap, struct vy_write_iterator, src_heap);
- int cmp = vy_tuple_compare(src1->tuple, src2->tuple, stream->cmp_def);
+ int cmp = vy_stmt_compare(src1->tuple, src2->tuple, stream->cmp_def);
if (cmp != 0)
return cmp < 0;
--
2.11.0
^ permalink raw reply [flat|nested] 34+ messages in thread* Re: [PATCH v2 01/14] vinyl: remove optimized comparators
2019-03-13 8:52 ` [PATCH v2 01/14] vinyl: remove optimized comparators Vladimir Davydov
@ 2019-03-13 8:55 ` Konstantin Osipov
0 siblings, 0 replies; 34+ messages in thread
From: Konstantin Osipov @ 2019-03-13 8:55 UTC (permalink / raw)
To: Vladimir Davydov; +Cc: tarantool-patches
* Vladimir Davydov <vdavydov.dev@gmail.com> [19/03/13 11:53]:
> A vinyl statement (vy_stmt struct) may represent either a tuple or a
> key. We differentiate between the two kinds by statement type - we use
> SELECT for keys and other types for tuples. This was done that way so
> that we could pass both tuples and keys to a read iterator as a search
> key. To avoid branching in comparators when the types of compared
> statements are known in advance, we provide several comparators, each of
> which expects certain statement types, e.g. a tuple and a key. Actually,
> such a micro optimization looks like an overkill, because a typical
> comparator is called by function pointer and has a lot of comparisons
> in the code, see tuple_compare_slowpath for instance. Eliminating one
> branch will hardly make the code perform better. At the same time, it
> makes the code more difficult to write. Besides, once we remove nils
> from statements read from disk (aka surrogate tuples), which will
> ease implementation of multikey indexes, the number of places where
> types of compared statements are known will diminish drastically.
> That said, let's remove optimized comparators and always use
> vy_stmt_compare, which checks types of compared statements and calls
> the appropriate comparator.
OK to push.
--
Konstantin Osipov, Moscow, Russia, +7 903 626 22 32
http://tarantool.io - www.twitter.com/kostja_osipov
^ permalink raw reply [flat|nested] 34+ messages in thread
* [PATCH v2 02/14] vinyl: introduce statement environment
2019-03-13 8:52 [PATCH v2 00/14] vinyl: do not fill secondary tuples with nulls Vladimir Davydov
2019-03-13 8:52 ` [PATCH v2 01/14] vinyl: remove optimized comparators Vladimir Davydov
@ 2019-03-13 8:52 ` Vladimir Davydov
2019-03-13 8:58 ` Konstantin Osipov
2019-03-13 8:52 ` [PATCH v2 03/14] vinyl: rename key stmt construction routine Vladimir Davydov
` (12 subsequent siblings)
14 siblings, 1 reply; 34+ messages in thread
From: Vladimir Davydov @ 2019-03-13 8:52 UTC (permalink / raw)
To: kostja; +Cc: tarantool-patches
Store tuple_format_vtab, max_tuple_size, and key_format there.
This will allow us to determine a statement type (key or tuple)
by checking its format against key_format.
---
src/box/vinyl.c | 29 ++++++++++++++++-------------
src/box/vy_lsm.c | 28 +++++++++++-----------------
src/box/vy_lsm.h | 9 +++++----
src/box/vy_stmt.c | 35 +++++++++++++++++++++++++++++------
src/box/vy_stmt.h | 34 +++++++++++++++++++++++++++-------
test/unit/vy_iterators_helper.c | 21 +++++++--------------
test/unit/vy_iterators_helper.h | 3 +--
test/unit/vy_mem.c | 6 ++----
test/unit/vy_point_lookup.c | 11 +++++------
9 files changed, 103 insertions(+), 73 deletions(-)
diff --git a/src/box/vinyl.c b/src/box/vinyl.c
index 4ffa79bf..7bfc0884 100644
--- a/src/box/vinyl.c
+++ b/src/box/vinyl.c
@@ -104,6 +104,8 @@ struct vy_env {
struct mempool iterator_pool;
/** Memory quota */
struct vy_quota quota;
+ /** Statement environment. */
+ struct vy_stmt_env stmt_env;
/** Common LSM tree environment. */
struct vy_lsm_env lsm_env;
/** Environment for cache subsystem */
@@ -601,6 +603,7 @@ static struct space *
vinyl_engine_create_space(struct engine *engine, struct space_def *def,
struct rlist *key_list)
{
+ struct vy_env *env = vy_env(engine);
struct space *space = malloc(sizeof(*space));
if (space == NULL) {
diag_set(OutOfMemory, sizeof(*space),
@@ -623,11 +626,10 @@ vinyl_engine_create_space(struct engine *engine, struct space_def *def,
rlist_foreach_entry(index_def, key_list, link)
keys[key_count++] = index_def->key_def;
- struct tuple_format *format =
- tuple_format_new(&vy_tuple_format_vtab, NULL, keys, key_count,
- def->fields, def->field_count,
- def->exact_field_count, def->dict, false,
- false);
+ struct tuple_format *format;
+ format = vy_stmt_format_new(&env->stmt_env, keys, key_count,
+ def->fields, def->field_count,
+ def->exact_field_count, def->dict);
if (format == NULL) {
free(space);
return NULL;
@@ -717,9 +719,9 @@ vinyl_space_create_index(struct space *space, struct index_def *index_def)
pk = vy_lsm(space_index(space, 0));
assert(pk != NULL);
}
- struct vy_lsm *lsm = vy_lsm_new(&env->lsm_env, &env->cache_env,
- &env->mem_env, index_def,
- space->format, pk,
+ struct vy_lsm *lsm = vy_lsm_new(&env->lsm_env, &env->stmt_env,
+ &env->cache_env, &env->mem_env,
+ index_def, space->format, pk,
space_group_id(space));
if (lsm == NULL) {
free(index);
@@ -2521,6 +2523,7 @@ vy_env_new(const char *path, size_t memory,
if (e->squash_queue == NULL)
goto error_squash_queue;
+ vy_stmt_env_create(&e->stmt_env);
vy_mem_env_create(&e->mem_env, memory);
vy_scheduler_create(&e->scheduler, write_threads,
vy_env_dump_complete_cb,
@@ -2528,6 +2531,7 @@ vy_env_new(const char *path, size_t memory,
if (vy_lsm_env_create(&e->lsm_env, e->path,
&e->scheduler.generation,
+ e->stmt_env.key_format,
vy_squash_schedule, e) != 0)
goto error_lsm_env;
@@ -2569,6 +2573,7 @@ vy_env_delete(struct vy_env *e)
vy_lsm_env_destroy(&e->lsm_env);
vy_mem_env_destroy(&e->mem_env);
vy_cache_env_destroy(&e->cache_env);
+ vy_stmt_env_destroy(&e->stmt_env);
vy_quota_destroy(&e->quota);
if (e->recovery != NULL)
vy_recovery_delete(e->recovery);
@@ -2641,8 +2646,7 @@ vinyl_engine_set_memory(struct vinyl_engine *vinyl, size_t size)
void
vinyl_engine_set_max_tuple_size(struct vinyl_engine *vinyl, size_t max_size)
{
- (void)vinyl;
- vy_max_tuple_size = max_size;
+ vinyl->env->stmt_env.max_tuple_size = max_size;
}
void
@@ -3057,9 +3061,8 @@ vy_send_lsm(struct vy_join_ctx *ctx, struct vy_lsm_recovery_info *lsm_info)
lsm_info->key_part_count);
if (ctx->key_def == NULL)
goto out;
- ctx->format = tuple_format_new(&vy_tuple_format_vtab, NULL,
- &ctx->key_def, 1, NULL, 0, 0, NULL,
- false, false);
+ ctx->format = vy_stmt_format_new(&ctx->env->stmt_env, &ctx->key_def, 1,
+ NULL, 0, 0, NULL);
if (ctx->format == NULL)
goto out_free_key_def;
tuple_format_ref(ctx->format);
diff --git a/src/box/vy_lsm.c b/src/box/vy_lsm.c
index 52183799..29cd6eab 100644
--- a/src/box/vy_lsm.c
+++ b/src/box/vy_lsm.c
@@ -70,23 +70,17 @@ static const int64_t VY_MAX_RANGE_SIZE = 2LL * 1024 * 1024 * 1024;
int
vy_lsm_env_create(struct vy_lsm_env *env, const char *path,
- int64_t *p_generation,
+ int64_t *p_generation, struct tuple_format *key_format,
vy_upsert_thresh_cb upsert_thresh_cb,
void *upsert_thresh_arg)
{
- env->key_format = tuple_format_new(&vy_tuple_format_vtab, NULL,
- NULL, 0, NULL, 0, 0, NULL, false,
- false);
- if (env->key_format == NULL)
+ env->empty_key = vy_stmt_new_select(key_format, NULL, 0);
+ if (env->empty_key == NULL)
return -1;
- tuple_format_ref(env->key_format);
- env->empty_key = vy_stmt_new_select(env->key_format, NULL, 0);
- if (env->empty_key == NULL) {
- tuple_format_unref(env->key_format);
- return -1;
- }
env->path = path;
env->p_generation = p_generation;
+ env->key_format = key_format;
+ tuple_format_ref(key_format);
env->upsert_thresh_cb = upsert_thresh_cb;
env->upsert_thresh_arg = upsert_thresh_arg;
env->too_long_threshold = TIMEOUT_INFINITY;
@@ -124,9 +118,10 @@ vy_lsm_mem_tree_size(struct vy_lsm *lsm)
}
struct vy_lsm *
-vy_lsm_new(struct vy_lsm_env *lsm_env, struct vy_cache_env *cache_env,
- struct vy_mem_env *mem_env, struct index_def *index_def,
- struct tuple_format *format, struct vy_lsm *pk, uint32_t group_id)
+vy_lsm_new(struct vy_lsm_env *lsm_env, struct vy_stmt_env *stmt_env,
+ struct vy_cache_env *cache_env, struct vy_mem_env *mem_env,
+ struct index_def *index_def, struct tuple_format *format,
+ struct vy_lsm *pk, uint32_t group_id)
{
static int64_t run_buckets[] = {
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 15, 20, 25, 50, 100,
@@ -161,9 +156,8 @@ vy_lsm_new(struct vy_lsm_env *lsm_env, struct vy_cache_env *cache_env,
*/
lsm->disk_format = format;
} else {
- lsm->disk_format = tuple_format_new(&vy_tuple_format_vtab, NULL,
- &cmp_def, 1, NULL, 0, 0,
- NULL, false, false);
+ lsm->disk_format = vy_stmt_format_new(stmt_env, &cmp_def, 1,
+ NULL, 0, 0, NULL);
if (lsm->disk_format == NULL)
goto fail_format;
}
diff --git a/src/box/vy_lsm.h b/src/box/vy_lsm.h
index 1bb447fb..b94e7a43 100644
--- a/src/box/vy_lsm.h
+++ b/src/box/vy_lsm.h
@@ -130,7 +130,7 @@ struct vy_lsm_env {
/** Create a common LSM tree environment. */
int
vy_lsm_env_create(struct vy_lsm_env *env, const char *path,
- int64_t *p_generation,
+ int64_t *p_generation, struct tuple_format *key_format,
vy_upsert_thresh_cb upsert_thresh_cb,
void *upsert_thresh_arg);
@@ -333,9 +333,10 @@ vy_lsm_mem_tree_size(struct vy_lsm *lsm);
/** Allocate a new LSM tree object. */
struct vy_lsm *
-vy_lsm_new(struct vy_lsm_env *lsm_env, struct vy_cache_env *cache_env,
- struct vy_mem_env *mem_env, struct index_def *index_def,
- struct tuple_format *format, struct vy_lsm *pk, uint32_t group_id);
+vy_lsm_new(struct vy_lsm_env *lsm_env, struct vy_stmt_env *stmt_env,
+ struct vy_cache_env *cache_env, struct vy_mem_env *mem_env,
+ struct index_def *index_def, struct tuple_format *format,
+ struct vy_lsm *pk, uint32_t group_id);
/** Free an LSM tree object. */
void
diff --git a/src/box/vy_stmt.c b/src/box/vy_stmt.c
index a75baeb8..91966d8c 100644
--- a/src/box/vy_stmt.c
+++ b/src/box/vy_stmt.c
@@ -112,12 +112,34 @@ vy_tuple_delete(struct tuple_format *format, struct tuple *tuple)
free(tuple);
}
-struct tuple_format_vtab vy_tuple_format_vtab = {
- vy_tuple_delete,
- vy_tuple_new,
-};
+void
+vy_stmt_env_create(struct vy_stmt_env *env)
+{
+ env->tuple_format_vtab.tuple_new = vy_tuple_new;
+ env->tuple_format_vtab.tuple_delete = vy_tuple_delete;
+ env->max_tuple_size = 1024 * 1024;
+ env->key_format = vy_stmt_format_new(env, NULL, 0, NULL, 0, 0, NULL);
+ if (env->key_format == NULL)
+ panic("failed to create vinyl key format");
+ tuple_format_ref(env->key_format);
+}
-size_t vy_max_tuple_size = 1024 * 1024;
+void
+vy_stmt_env_destroy(struct vy_stmt_env *env)
+{
+ tuple_format_unref(env->key_format);
+}
+
+struct tuple_format *
+vy_stmt_format_new(struct vy_stmt_env *env, struct key_def *const *keys,
+ uint16_t key_count, const struct field_def *fields,
+ uint32_t field_count, uint32_t exact_field_count,
+ struct tuple_dictionary *dict)
+{
+ return tuple_format_new(&env->tuple_format_vtab, env, keys, key_count,
+ fields, field_count, exact_field_count, dict,
+ false, false);
+}
/**
* Allocate a vinyl statement object on base of the struct tuple
@@ -132,9 +154,10 @@ size_t vy_max_tuple_size = 1024 * 1024;
static struct tuple *
vy_stmt_alloc(struct tuple_format *format, uint32_t bsize)
{
+ struct vy_stmt_env *env = format->engine;
uint32_t total_size = sizeof(struct vy_stmt) + format->field_map_size +
bsize;
- if (unlikely(total_size > vy_max_tuple_size)) {
+ if (unlikely(total_size > env->max_tuple_size)) {
diag_set(ClientError, ER_VINYL_MAX_TUPLE_SIZE,
(unsigned) total_size);
error_log(diag_last_error(diag_get()));
diff --git a/src/box/vy_stmt.h b/src/box/vy_stmt.h
index 98c1a2f3..0332bbdb 100644
--- a/src/box/vy_stmt.h
+++ b/src/box/vy_stmt.h
@@ -49,6 +49,7 @@ extern "C" {
struct xrow_header;
struct region;
struct tuple_format;
+struct tuple_dictionary;
struct iovec;
#define MAX_LSN (INT64_MAX / 2)
@@ -61,14 +62,33 @@ static_assert(VY_UPSERT_THRESHOLD <= UINT8_MAX, "n_upserts max value");
static_assert(VY_UPSERT_INF == VY_UPSERT_THRESHOLD + 1,
"inf must be threshold + 1");
-/** Vinyl statement vtable. */
-extern struct tuple_format_vtab vy_tuple_format_vtab;
+/** Vinyl statement environment. */
+struct vy_stmt_env {
+ /** Vinyl statement vtable. */
+ struct tuple_format_vtab tuple_format_vtab;
+ /**
+ * Max tuple size
+ * @see box.cfg.vinyl_max_tuple_size
+ */
+ size_t max_tuple_size;
+ /** Tuple format for keys. */
+ struct tuple_format *key_format;
+};
-/**
- * Max tuple size
- * @see box.cfg.vinyl_max_tuple_size
- */
-extern size_t vy_max_tuple_size;
+/** Initialize a vinyl statement environment. */
+void
+vy_stmt_env_create(struct vy_stmt_env *env);
+
+/** Destroy a vinyl statement environment. */
+void
+vy_stmt_env_destroy(struct vy_stmt_env *env);
+
+/** Create a vinyl statement format. */
+struct tuple_format *
+vy_stmt_format_new(struct vy_stmt_env *env, struct key_def *const *keys,
+ uint16_t key_count, const struct field_def *fields,
+ uint32_t field_count, uint32_t exact_field_count,
+ struct tuple_dictionary *dict);
/** Statement flags. */
enum {
diff --git a/test/unit/vy_iterators_helper.c b/test/unit/vy_iterators_helper.c
index 9fd45766..0b0fe4ab 100644
--- a/test/unit/vy_iterators_helper.c
+++ b/test/unit/vy_iterators_helper.c
@@ -6,7 +6,7 @@
struct tt_uuid INSTANCE_UUID;
-struct tuple_format *vy_key_format = NULL;
+struct vy_stmt_env stmt_env;
struct vy_mem_env mem_env;
struct vy_cache_env cache_env;
@@ -19,12 +19,9 @@ vy_iterator_C_test_init(size_t cache_size)
memory_init();
fiber_init(fiber_c_invoke);
tuple_init(NULL);
+ vy_stmt_env_create(&stmt_env);
vy_cache_env_create(&cache_env, cord_slab_cache());
vy_cache_env_set_quota(&cache_env, cache_size);
- vy_key_format = tuple_format_new(&vy_tuple_format_vtab, NULL, NULL, 0,
- NULL, 0, 0, NULL, false, false);
- tuple_format_ref(vy_key_format);
-
size_t mem_size = 64 * 1024 * 1024;
vy_mem_env_create(&mem_env, mem_size);
}
@@ -33,8 +30,8 @@ void
vy_iterator_C_test_finish()
{
vy_mem_env_destroy(&mem_env);
- tuple_format_unref(vy_key_format);
vy_cache_env_destroy(&cache_env);
+ vy_stmt_env_destroy(&stmt_env);
tuple_free();
fiber_free();
memory_free();
@@ -122,7 +119,7 @@ vy_new_simple_stmt(struct tuple_format *format,
case IPROTO_SELECT: {
const char *key = buf;
uint part_count = mp_decode_array(&key);
- ret = vy_stmt_new_select(vy_key_format, key, part_count);
+ ret = vy_stmt_new_select(stmt_env.key_format, key, part_count);
fail_if(ret == NULL);
break;
}
@@ -199,11 +196,8 @@ struct vy_mem *
create_test_mem(struct key_def *def)
{
/* Create format */
- struct key_def * const defs[] = { def };
- struct tuple_format *format =
- tuple_format_new(&vy_tuple_format_vtab, NULL, defs,
- def->part_count, NULL, 0, 0, NULL, false,
- false);
+ struct tuple_format *format;
+ format = vy_stmt_format_new(&stmt_env, &def, 1, NULL, 0, 0, NULL);
fail_if(format == NULL);
/* Create mem */
@@ -220,8 +214,7 @@ create_test_cache(uint32_t *fields, uint32_t *types,
*def = box_key_def_new(fields, types, key_cnt);
assert(*def != NULL);
vy_cache_create(cache, &cache_env, *def, true);
- *format = tuple_format_new(&vy_tuple_format_vtab, NULL, def, 1, NULL, 0,
- 0, NULL, false, false);
+ *format = vy_stmt_format_new(&stmt_env, def, 1, NULL, 0, 0, NULL);
tuple_format_ref(*format);
}
diff --git a/test/unit/vy_iterators_helper.h b/test/unit/vy_iterators_helper.h
index 9690f684..49b4f4fd 100644
--- a/test/unit/vy_iterators_helper.h
+++ b/test/unit/vy_iterators_helper.h
@@ -51,8 +51,7 @@
#define STMT_TEMPLATE_DEFERRED_DELETE(lsn, type, ...) \
STMT_TEMPLATE_FLAGS(lsn, type, VY_STMT_DEFERRED_DELETE, __VA_ARGS__)
-extern struct tuple_format_vtab vy_tuple_format_vtab;
-extern struct tuple_format *vy_key_format;
+extern struct vy_stmt_env stmt_env;
extern struct vy_mem_env mem_env;
extern struct vy_cache_env cache_env;
diff --git a/test/unit/vy_mem.c b/test/unit/vy_mem.c
index b8272eac..0226a62a 100644
--- a/test/unit/vy_mem.c
+++ b/test/unit/vy_mem.c
@@ -76,10 +76,8 @@ test_iterator_restore_after_insertion()
assert(key_def != NULL);
/* Create format */
- struct tuple_format *format = tuple_format_new(&vy_tuple_format_vtab,
- NULL, &key_def, 1, NULL,
- 0, 0, NULL, false,
- false);
+ struct tuple_format *format = vy_stmt_format_new(&stmt_env, &key_def, 1,
+ NULL, 0, 0, NULL);
assert(format != NULL);
tuple_format_ref(format);
diff --git a/test/unit/vy_point_lookup.c b/test/unit/vy_point_lookup.c
index 8ed16f6c..5f20d09b 100644
--- a/test/unit/vy_point_lookup.c
+++ b/test/unit/vy_point_lookup.c
@@ -66,7 +66,8 @@ test_basic()
int rc;
struct vy_lsm_env lsm_env;
- rc = vy_lsm_env_create(&lsm_env, ".", &generation, NULL, NULL);
+ rc = vy_lsm_env_create(&lsm_env, ".", &generation,
+ stmt_env.key_format, NULL, NULL);
is(rc, 0, "vy_lsm_env_create");
struct vy_run_env run_env;
@@ -83,10 +84,8 @@ test_basic()
isnt(key_def, NULL, "key_def is not NULL");
vy_cache_create(&cache, &cache_env, key_def, true);
- struct tuple_format *format = tuple_format_new(&vy_tuple_format_vtab,
- NULL, &key_def, 1, NULL,
- 0, 0, NULL, false,
- false);
+ struct tuple_format *format = vy_stmt_format_new(&stmt_env, &key_def, 1,
+ NULL, 0, 0, NULL);
isnt(format, NULL, "tuple_format_new is not NULL");
tuple_format_ref(format);
@@ -95,7 +94,7 @@ test_basic()
index_def_new(512, 0, "primary", sizeof("primary") - 1, TREE,
&index_opts, key_def, NULL);
- struct vy_lsm *pk = vy_lsm_new(&lsm_env, &cache_env, &mem_env,
+ struct vy_lsm *pk = vy_lsm_new(&lsm_env, &stmt_env, &cache_env, &mem_env,
index_def, format, NULL, 0);
isnt(pk, NULL, "lsm is not NULL")
--
2.11.0
^ permalink raw reply [flat|nested] 34+ messages in thread* Re: [PATCH v2 02/14] vinyl: introduce statement environment
2019-03-13 8:52 ` [PATCH v2 02/14] vinyl: introduce statement environment Vladimir Davydov
@ 2019-03-13 8:58 ` Konstantin Osipov
2019-03-13 9:19 ` Vladimir Davydov
0 siblings, 1 reply; 34+ messages in thread
From: Konstantin Osipov @ 2019-03-13 8:58 UTC (permalink / raw)
To: Vladimir Davydov; +Cc: tarantool-patches
* Vladimir Davydov <vdavydov.dev@gmail.com> [19/03/13 11:53]:
> Store tuple_format_vtab, max_tuple_size, and key_format there.
> This will allow us to determine a statement type (key or tuple)
> by checking its format against key_format.
What exactly is a key format? Is there a single global key format?
Why do you need it and why is it sufficient to have a single key
format? Please explain in the comment for stmt_env->key_format.
> --
--
Konstantin Osipov, Moscow, Russia, +7 903 626 22 32
http://tarantool.io - www.twitter.com/kostja_osipov
^ permalink raw reply [flat|nested] 34+ messages in thread
* Re: [PATCH v2 02/14] vinyl: introduce statement environment
2019-03-13 8:58 ` Konstantin Osipov
@ 2019-03-13 9:19 ` Vladimir Davydov
0 siblings, 0 replies; 34+ messages in thread
From: Vladimir Davydov @ 2019-03-13 9:19 UTC (permalink / raw)
To: Konstantin Osipov; +Cc: tarantool-patches
On Wed, Mar 13, 2019 at 11:58:03AM +0300, Konstantin Osipov wrote:
> * Vladimir Davydov <vdavydov.dev@gmail.com> [19/03/13 11:53]:
> > Store tuple_format_vtab, max_tuple_size, and key_format there.
> > This will allow us to determine a statement type (key or tuple)
> > by checking its format against key_format.
>
> What exactly is a key format?
It's the format we use for creating all key statements. It's kinda
pseudo format, as it imposes no restriction on the tuple and doesn't
setup offset map.
> Is there a single global key format?
Yes. It's a crux: we use to identify key statements.
> Why do you need it and why is it sufficient to have a single key
> format?
> Please explain in the comment for stmt_env->key_format.
OK, will do.
^ permalink raw reply [flat|nested] 34+ messages in thread
* [PATCH v2 03/14] vinyl: rename key stmt construction routine
2019-03-13 8:52 [PATCH v2 00/14] vinyl: do not fill secondary tuples with nulls Vladimir Davydov
2019-03-13 8:52 ` [PATCH v2 01/14] vinyl: remove optimized comparators Vladimir Davydov
2019-03-13 8:52 ` [PATCH v2 02/14] vinyl: introduce statement environment Vladimir Davydov
@ 2019-03-13 8:52 ` Vladimir Davydov
2019-03-13 8:59 ` Konstantin Osipov
2019-03-13 8:52 ` [PATCH v2 04/14] vinyl: don't use IPROTO_SELECT type for key statements Vladimir Davydov
` (11 subsequent siblings)
14 siblings, 1 reply; 34+ messages in thread
From: Vladimir Davydov @ 2019-03-13 8:52 UTC (permalink / raw)
To: kostja; +Cc: tarantool-patches
Currently, it's called vy_stmt_new_select, but soon a key statement will
be allowed to have any type, not just IPROTO_SELECT. So let's rename it
to vy_stmt_new_key. Let's also rename the wrapper vy_key_from_msgpack to
vy_stmt_new_key_from_msgpack to be consistent with vy_stmt_new_key.
---
src/box/vinyl.c | 15 ++++++++-------
src/box/vy_lsm.c | 22 +++++++++++-----------
src/box/vy_scheduler.c | 6 ++++--
src/box/vy_stmt.c | 19 ++++---------------
src/box/vy_stmt.h | 19 +++++++------------
test/unit/vy_iterators_helper.c | 4 +---
test/unit/vy_mem.c | 2 +-
7 files changed, 36 insertions(+), 51 deletions(-)
diff --git a/src/box/vinyl.c b/src/box/vinyl.c
index 7bfc0884..0146f62c 100644
--- a/src/box/vinyl.c
+++ b/src/box/vinyl.c
@@ -1435,8 +1435,8 @@ vy_get_by_raw_key(struct vy_lsm *lsm, struct vy_tx *tx,
const char *key_raw, uint32_t part_count,
struct tuple **result)
{
- struct tuple *key = vy_stmt_new_select(lsm->env->key_format,
- key_raw, part_count);
+ struct tuple *key = vy_stmt_new_key(lsm->env->key_format,
+ key_raw, part_count);
if (key == NULL)
return -1;
int rc = vy_get(lsm, tx, rv, key, result);
@@ -2912,6 +2912,7 @@ vy_prepare_send_slice(struct vy_join_ctx *ctx,
int rc = -1;
struct vy_run *run = NULL;
struct tuple *begin = NULL, *end = NULL;
+ struct tuple_format *key_format = ctx->env->lsm_env.key_format;
run = vy_run_new(&ctx->env->run_env, slice_info->run->id);
if (run == NULL)
@@ -2920,14 +2921,14 @@ vy_prepare_send_slice(struct vy_join_ctx *ctx,
goto out;
if (slice_info->begin != NULL) {
- begin = vy_key_from_msgpack(ctx->env->lsm_env.key_format,
- slice_info->begin);
+ begin = vy_stmt_new_key_from_msgpack(key_format,
+ slice_info->begin);
if (begin == NULL)
goto out;
}
if (slice_info->end != NULL) {
- end = vy_key_from_msgpack(ctx->env->lsm_env.key_format,
- slice_info->end);
+ end = vy_stmt_new_key_from_msgpack(key_format,
+ slice_info->end);
if (end == NULL)
goto out;
}
@@ -3799,7 +3800,7 @@ vinyl_index_create_iterator(struct index *base, enum iterator_type type,
"mempool", "struct vinyl_iterator");
return NULL;
}
- it->key = vy_stmt_new_select(lsm->env->key_format, key, part_count);
+ it->key = vy_stmt_new_key(lsm->env->key_format, key, part_count);
if (it->key == NULL) {
mempool_free(&env->iterator_pool, it);
return NULL;
diff --git a/src/box/vy_lsm.c b/src/box/vy_lsm.c
index 29cd6eab..171664d4 100644
--- a/src/box/vy_lsm.c
+++ b/src/box/vy_lsm.c
@@ -74,7 +74,7 @@ vy_lsm_env_create(struct vy_lsm_env *env, const char *path,
vy_upsert_thresh_cb upsert_thresh_cb,
void *upsert_thresh_arg)
{
- env->empty_key = vy_stmt_new_select(key_format, NULL, 0);
+ env->empty_key = vy_stmt_new_key(key_format, NULL, 0);
if (env->empty_key == NULL)
return -1;
env->path = path;
@@ -387,14 +387,14 @@ vy_lsm_recover_slice(struct vy_lsm *lsm, struct vy_range *range,
struct vy_run *run;
if (slice_info->begin != NULL) {
- begin = vy_key_from_msgpack(lsm->env->key_format,
- slice_info->begin);
+ begin = vy_stmt_new_key_from_msgpack(lsm->env->key_format,
+ slice_info->begin);
if (begin == NULL)
goto out;
}
if (slice_info->end != NULL) {
- end = vy_key_from_msgpack(lsm->env->key_format,
- slice_info->end);
+ end = vy_stmt_new_key_from_msgpack(lsm->env->key_format,
+ slice_info->end);
if (end == NULL)
goto out;
}
@@ -433,14 +433,14 @@ vy_lsm_recover_range(struct vy_lsm *lsm,
struct vy_range *range = NULL;
if (range_info->begin != NULL) {
- begin = vy_key_from_msgpack(lsm->env->key_format,
- range_info->begin);
+ begin = vy_stmt_new_key_from_msgpack(lsm->env->key_format,
+ range_info->begin);
if (begin == NULL)
goto out;
}
if (range_info->end != NULL) {
- end = vy_key_from_msgpack(lsm->env->key_format,
- range_info->end);
+ end = vy_stmt_new_key_from_msgpack(lsm->env->key_format,
+ range_info->end);
if (end == NULL)
goto out;
}
@@ -1068,8 +1068,8 @@ vy_lsm_split_range(struct vy_lsm *lsm, struct vy_range *range)
/*
* Determine new ranges' boundaries.
*/
- struct tuple *split_key = vy_key_from_msgpack(key_format,
- split_key_raw);
+ struct tuple *split_key = vy_stmt_new_key_from_msgpack(key_format,
+ split_key_raw);
if (split_key == NULL)
goto fail;
diff --git a/src/box/vy_scheduler.c b/src/box/vy_scheduler.c
index 92d40780..91cf502b 100644
--- a/src/box/vy_scheduler.c
+++ b/src/box/vy_scheduler.c
@@ -1136,10 +1136,12 @@ vy_task_dump_complete(struct vy_task *task)
* intersecting the run or NULL if the run itersects all
* ranges.
*/
- min_key = vy_key_from_msgpack(key_format, new_run->info.min_key);
+ min_key = vy_stmt_new_key_from_msgpack(key_format,
+ new_run->info.min_key);
if (min_key == NULL)
goto fail;
- max_key = vy_key_from_msgpack(key_format, new_run->info.max_key);
+ max_key = vy_stmt_new_key_from_msgpack(key_format,
+ new_run->info.max_key);
if (max_key == NULL) {
tuple_unref(min_key);
goto fail;
diff --git a/src/box/vy_stmt.c b/src/box/vy_stmt.c
index 91966d8c..e34ff2b6 100644
--- a/src/box/vy_stmt.c
+++ b/src/box/vy_stmt.c
@@ -236,20 +236,9 @@ vy_stmt_dup_lsregion(const struct tuple *stmt, struct lsregion *lsregion,
return mem_stmt;
}
-/**
- * Create the key statement from raw MessagePack data.
- * @param format Format of an index.
- * @param key MessagePack data that contain an array of
- * fields WITHOUT the array header.
- * @param part_count Count of the key fields that will be saved as
- * result.
- *
- * @retval not NULL Success.
- * @retval NULL Memory allocation error.
- */
struct tuple *
-vy_stmt_new_select(struct tuple_format *format, const char *key,
- uint32_t part_count)
+vy_stmt_new_key(struct tuple_format *format, const char *key,
+ uint32_t part_count)
{
assert(part_count == 0 || key != NULL);
/* Key don't have field map */
@@ -649,7 +638,7 @@ vy_stmt_extract_key(const struct tuple *stmt, struct key_def *key_def,
return NULL;
uint32_t part_count = mp_decode_array(&key_raw);
assert(part_count == key_def->part_count);
- struct tuple *key = vy_stmt_new_select(format, key_raw, part_count);
+ struct tuple *key = vy_stmt_new_key(format, key_raw, part_count);
/* Cleanup memory allocated by tuple_extract_key(). */
region_truncate(region, region_svp);
return key;
@@ -668,7 +657,7 @@ vy_stmt_extract_key_raw(const char *data, const char *data_end,
return NULL;
uint32_t part_count = mp_decode_array(&key_raw);
assert(part_count == key_def->part_count);
- struct tuple *key = vy_stmt_new_select(format, key_raw, part_count);
+ struct tuple *key = vy_stmt_new_key(format, key_raw, part_count);
/* Cleanup memory allocated by tuple_extract_key_raw(). */
region_truncate(region, region_svp);
return key;
diff --git a/src/box/vy_stmt.h b/src/box/vy_stmt.h
index 0332bbdb..192f47de 100644
--- a/src/box/vy_stmt.h
+++ b/src/box/vy_stmt.h
@@ -382,7 +382,7 @@ vy_stmt_compare_with_raw_key(const struct tuple *stmt, const char *key,
}
/**
- * Create the SELECT statement from raw MessagePack data.
+ * Create a key statement from raw MessagePack data.
* @param format Format of an index.
* @param key MessagePack data that contain an array of
* fields WITHOUT the array header.
@@ -393,8 +393,8 @@ vy_stmt_compare_with_raw_key(const struct tuple *stmt, const char *key,
* @retval not NULL Success.
*/
struct tuple *
-vy_stmt_new_select(struct tuple_format *format, const char *key,
- uint32_t part_count);
+vy_stmt_new_key(struct tuple_format *format, const char *key,
+ uint32_t part_count);
/**
* Copy the key in a new memory area.
@@ -549,7 +549,7 @@ vy_stmt_upsert_ops(const struct tuple *tuple, uint32_t *mp_size)
}
/**
- * Create the SELECT statement from MessagePack array.
+ * Create a key statement from MessagePack array.
* @param format Format of an index.
* @param key MessagePack array of key fields.
*
@@ -557,15 +557,10 @@ vy_stmt_upsert_ops(const struct tuple *tuple, uint32_t *mp_size)
* @retval NULL Memory error.
*/
static inline struct tuple *
-vy_key_from_msgpack(struct tuple_format *format, const char *key)
+vy_stmt_new_key_from_msgpack(struct tuple_format *format, const char *key)
{
- uint32_t part_count;
- /*
- * The statement already is a key, so simply copy it in
- * the new struct vy_stmt as SELECT.
- */
- part_count = mp_decode_array(&key);
- return vy_stmt_new_select(format, key, part_count);
+ uint32_t part_count = mp_decode_array(&key);
+ return vy_stmt_new_key(format, key, part_count);
}
/**
diff --git a/test/unit/vy_iterators_helper.c b/test/unit/vy_iterators_helper.c
index 0b0fe4ab..9b70ed98 100644
--- a/test/unit/vy_iterators_helper.c
+++ b/test/unit/vy_iterators_helper.c
@@ -117,9 +117,7 @@ vy_new_simple_stmt(struct tuple_format *format,
break;
}
case IPROTO_SELECT: {
- const char *key = buf;
- uint part_count = mp_decode_array(&key);
- ret = vy_stmt_new_select(stmt_env.key_format, key, part_count);
+ ret = vy_stmt_new_key_from_msgpack(stmt_env.key_format, buf);
fail_if(ret == NULL);
break;
}
diff --git a/test/unit/vy_mem.c b/test/unit/vy_mem.c
index 0226a62a..da4117c5 100644
--- a/test/unit/vy_mem.c
+++ b/test/unit/vy_mem.c
@@ -86,7 +86,7 @@ test_iterator_restore_after_insertion()
struct slab_cache *slab_cache = cord_slab_cache();
lsregion_create(&lsregion, slab_cache->arena);
- struct tuple *select_key = vy_stmt_new_select(format, "", 0);
+ struct tuple *select_key = vy_stmt_new_key(format, NULL, 0);
struct mempool history_node_pool;
mempool_create(&history_node_pool, cord_slab_cache(),
--
2.11.0
^ permalink raw reply [flat|nested] 34+ messages in thread* Re: [PATCH v2 03/14] vinyl: rename key stmt construction routine
2019-03-13 8:52 ` [PATCH v2 03/14] vinyl: rename key stmt construction routine Vladimir Davydov
@ 2019-03-13 8:59 ` Konstantin Osipov
0 siblings, 0 replies; 34+ messages in thread
From: Konstantin Osipov @ 2019-03-13 8:59 UTC (permalink / raw)
To: Vladimir Davydov; +Cc: tarantool-patches
* Vladimir Davydov <vdavydov.dev@gmail.com> [19/03/13 11:53]:
> Currently, it's called vy_stmt_new_select, but soon a key statement will
> be allowed to have any type, not just IPROTO_SELECT. So let's rename it
> to vy_stmt_new_key. Let's also rename the wrapper vy_key_from_msgpack to
> vy_stmt_new_key_from_msgpack to be consistent with vy_stmt_new_key.
OK to push. I would call it vy_key_new() and
vy_key_new_from_msgpack, if these names are not used.
--
Konstantin Osipov, Moscow, Russia, +7 903 626 22 32
http://tarantool.io - www.twitter.com/kostja_osipov
^ permalink raw reply [flat|nested] 34+ messages in thread
* [PATCH v2 04/14] vinyl: don't use IPROTO_SELECT type for key statements
2019-03-13 8:52 [PATCH v2 00/14] vinyl: do not fill secondary tuples with nulls Vladimir Davydov
` (2 preceding siblings ...)
2019-03-13 8:52 ` [PATCH v2 03/14] vinyl: rename key stmt construction routine Vladimir Davydov
@ 2019-03-13 8:52 ` Vladimir Davydov
2019-03-13 9:00 ` Konstantin Osipov
2019-03-13 8:52 ` [PATCH v2 05/14] bloom: do not use tuple_common_key_parts when constructing tuple bloom Vladimir Davydov
` (10 subsequent siblings)
14 siblings, 1 reply; 34+ messages in thread
From: Vladimir Davydov @ 2019-03-13 8:52 UTC (permalink / raw)
To: kostja; +Cc: tarantool-patches
To differentiate between key and tuple statements in comparators, we set
IPROTO_SELECT type for key statements. As a result, we can't use key
statements in the run iterator directly although secondary index runs do
store statements in key format. Instead we create surrogate tuples
filling missing fields with NULLs. This won't play nicely with multikey
indexes so we need to teach iterators to deal with statements in key
format. The first step in this direction is dropping IPROTO_SELECT in
favor of identifying key statements by format.
---
src/box/vy_run.c | 2 +-
src/box/vy_stmt.c | 6 +++++-
src/box/vy_stmt.h | 38 +++++++++++++++++++++++++-------------
test/unit/vy_mem.c | 2 +-
4 files changed, 32 insertions(+), 16 deletions(-)
diff --git a/src/box/vy_run.c b/src/box/vy_run.c
index 8d40ef00..3c096b0a 100644
--- a/src/box/vy_run.c
+++ b/src/box/vy_run.c
@@ -1250,7 +1250,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) {
bool need_lookup;
- if (vy_stmt_type(key) == IPROTO_SELECT) {
+ if (vy_stmt_is_key(key)) {
const char *data = tuple_data(key);
uint32_t part_count = mp_decode_array(&data);
need_lookup = tuple_bloom_maybe_has_key(bloom, data,
diff --git a/src/box/vy_stmt.c b/src/box/vy_stmt.c
index e34ff2b6..954ec276 100644
--- a/src/box/vy_stmt.c
+++ b/src/box/vy_stmt.c
@@ -240,6 +240,7 @@ struct tuple *
vy_stmt_new_key(struct tuple_format *format, const char *key,
uint32_t part_count)
{
+ assert(vy_stmt_is_key_format(format));
assert(part_count == 0 || key != NULL);
/* Key don't have field map */
assert(format->field_map_size == 0);
@@ -260,7 +261,6 @@ vy_stmt_new_key(struct tuple_format *format, const char *key,
char *data = mp_encode_array(raw, part_count);
memcpy(data, key, key_size);
assert(data + key_size == raw + bsize);
- vy_stmt_set_type(stmt, IPROTO_SELECT);
return stmt;
}
@@ -859,6 +859,10 @@ vy_stmt_snprint(char *buf, int size, const struct tuple *stmt)
SNPRINT(total, snprintf, buf, size, "<NULL>");
return total;
}
+ if (vy_stmt_type(stmt) == 0) {
+ SNPRINT(total, mp_snprint, buf, size, tuple_data(stmt));
+ return total;
+ }
SNPRINT(total, snprintf, buf, size, "%s(",
iproto_type_name(vy_stmt_type(stmt)));
SNPRINT(total, mp_snprint, buf, size, tuple_data(stmt));
diff --git a/src/box/vy_stmt.h b/src/box/vy_stmt.h
index 192f47de..7c9b3677 100644
--- a/src/box/vy_stmt.h
+++ b/src/box/vy_stmt.h
@@ -133,12 +133,9 @@ enum {
};
/**
- * There are two groups of statements:
+ * A vinyl statement can have either key or tuple format.
*
- * - SELECT is "key" statement.
- * - DELETE, UPSERT and REPLACE are "tuple" statements.
- *
- * REPLACE/UPSERT/DELETE statements structure:
+ * Tuple statement structure:
* data_offset
* ^
* +----------------------------------+
@@ -154,7 +151,7 @@ enum {
* indexed then before MessagePack data are stored offsets only for field 3 and
* field 5.
*
- * SELECT statements structure.
+ * Key statement structure:
* +--------------+-----------------+
* | array header | part1 ... partN | - MessagePack data
* +--------------+-----------------+
@@ -164,7 +161,7 @@ enum {
struct vy_stmt {
struct tuple base;
int64_t lsn;
- uint8_t type; /* IPROTO_SELECT/REPLACE/UPSERT/DELETE */
+ uint8_t type; /* IPROTO_INSERT/REPLACE/UPSERT/DELETE */
uint8_t flags;
/**
* Offsets array concatenated with MessagePack fields
@@ -239,6 +236,21 @@ vy_stmt_set_n_upserts(struct tuple *stmt, uint8_t n)
*((uint8_t *)stmt - 1) = n;
}
+/** Return true if the given format is a key format. */
+static inline bool
+vy_stmt_is_key_format(const struct tuple_format *format)
+{
+ struct vy_stmt_env *env = format->engine;
+ return env->key_format == format;
+}
+
+/** Return true if the vinyl statement has key format. */
+static inline bool
+vy_stmt_is_key(const struct tuple *stmt)
+{
+ return vy_stmt_is_key_format(tuple_format(stmt));
+}
+
/**
* Return the number of key parts defined in the given vinyl
* statement.
@@ -249,7 +261,7 @@ vy_stmt_set_n_upserts(struct tuple *stmt, uint8_t n)
static inline uint32_t
vy_stmt_key_part_count(const struct tuple *stmt, struct key_def *key_def)
{
- if (vy_stmt_type(stmt) == IPROTO_SELECT) {
+ if (vy_stmt_is_key(stmt)) {
uint32_t part_count = tuple_field_count(stmt);
assert(part_count <= key_def->part_count);
return part_count;
@@ -348,8 +360,8 @@ static inline int
vy_stmt_compare(const struct tuple *a, const struct tuple *b,
struct key_def *key_def)
{
- bool a_is_tuple = vy_stmt_type(a) != IPROTO_SELECT;
- bool b_is_tuple = vy_stmt_type(b) != IPROTO_SELECT;
+ bool a_is_tuple = !vy_stmt_is_key(a);
+ bool b_is_tuple = !vy_stmt_is_key(b);
if (a_is_tuple && b_is_tuple) {
return tuple_compare(a, b, key_def);
} else if (a_is_tuple && !b_is_tuple) {
@@ -374,7 +386,7 @@ static inline int
vy_stmt_compare_with_raw_key(const struct tuple *stmt, const char *key,
struct key_def *key_def)
{
- if (vy_stmt_type(stmt) != IPROTO_SELECT) {
+ if (!vy_stmt_is_key(stmt)) {
uint32_t part_count = mp_decode_array(&key);
return tuple_compare_with_key(stmt, key, part_count, key_def);
}
@@ -565,7 +577,7 @@ vy_stmt_new_key_from_msgpack(struct tuple_format *format, const char *key)
/**
* Extract the key from a tuple by the given key definition
- * and store the result in a SELECT statement allocated with
+ * and store the result in a key statement allocated with
* malloc().
*/
struct tuple *
@@ -574,7 +586,7 @@ vy_stmt_extract_key(const struct tuple *stmt, struct key_def *key_def,
/**
* Extract the key from msgpack by the given key definition
- * and store the result in a SELECT statement allocated with
+ * and store the result in a key statement allocated with
* malloc().
*/
struct tuple *
diff --git a/test/unit/vy_mem.c b/test/unit/vy_mem.c
index da4117c5..b672ee91 100644
--- a/test/unit/vy_mem.c
+++ b/test/unit/vy_mem.c
@@ -86,7 +86,7 @@ test_iterator_restore_after_insertion()
struct slab_cache *slab_cache = cord_slab_cache();
lsregion_create(&lsregion, slab_cache->arena);
- struct tuple *select_key = vy_stmt_new_key(format, NULL, 0);
+ struct tuple *select_key = vy_stmt_new_key(stmt_env.key_format, NULL, 0);
struct mempool history_node_pool;
mempool_create(&history_node_pool, cord_slab_cache(),
--
2.11.0
^ permalink raw reply [flat|nested] 34+ messages in thread* Re: [PATCH v2 04/14] vinyl: don't use IPROTO_SELECT type for key statements
2019-03-13 8:52 ` [PATCH v2 04/14] vinyl: don't use IPROTO_SELECT type for key statements Vladimir Davydov
@ 2019-03-13 9:00 ` Konstantin Osipov
0 siblings, 0 replies; 34+ messages in thread
From: Konstantin Osipov @ 2019-03-13 9:00 UTC (permalink / raw)
To: Vladimir Davydov; +Cc: tarantool-patches
* Vladimir Davydov <vdavydov.dev@gmail.com> [19/03/13 11:53]:
> To differentiate between key and tuple statements in comparators, we set
> IPROTO_SELECT type for key statements. As a result, we can't use key
> statements in the run iterator directly although secondary index runs do
> store statements in key format. Instead we create surrogate tuples
> filling missing fields with NULLs. This won't play nicely with multikey
> indexes so we need to teach iterators to deal with statements in key
> format. The first step in this direction is dropping IPROTO_SELECT in
> favor of identifying key statements by format.
OK to push.
--
Konstantin Osipov, Moscow, Russia, +7 903 626 22 32
http://tarantool.io - www.twitter.com/kostja_osipov
^ permalink raw reply [flat|nested] 34+ messages in thread
* [PATCH v2 05/14] bloom: do not use tuple_common_key_parts when constructing tuple bloom
2019-03-13 8:52 [PATCH v2 00/14] vinyl: do not fill secondary tuples with nulls Vladimir Davydov
` (3 preceding siblings ...)
2019-03-13 8:52 ` [PATCH v2 04/14] vinyl: don't use IPROTO_SELECT type for key statements Vladimir Davydov
@ 2019-03-13 8:52 ` Vladimir Davydov
2019-03-13 11:52 ` Konstantin Osipov
2019-03-13 8:52 ` [PATCH v2 06/14] bloom: factor out helper to add tuple hash to bloom builder Vladimir Davydov
` (9 subsequent siblings)
14 siblings, 1 reply; 34+ messages in thread
From: Vladimir Davydov @ 2019-03-13 8:52 UTC (permalink / raw)
To: kostja; +Cc: tarantool-patches
Tuple bloom filter is an array of bloom filters, each of which reflects
lookups by all possible partial keys. To optimize the overall bloom
filter size, we need to know how many unique elements there are for each
partial key. To achieve that, we require the caller to pass the number
of key parts that have been hashed for the given tuple. Here's how it
looks in Vinyl:
uint32_t hashed_parts = writer->last_stmt == NULL ? 0 :
tuple_common_key_parts(stmt, writer->last_stmt,
writer->key_def);
tuple_bloom_builder_add(writer->bloom, stmt,
writer->key_def, hashed_parts);
Actually, there's no need in such a requirement as instead we can
calculate the hash value for the given tuple, compare it with the hash
of the tuple added last time, and add the new hash only if the two
values differ. This should be accurate enough while allowing us to get
rid of the cumbersome tuple_common_key_parts helper. Note, such a check
will only work if tuples are added in the order defined by the key
definition, but that already holds - anyway, one wouldn't be able to
use tuple_common_key_parts either if it wasn't true.
---
src/box/key_def.h | 11 -----------
src/box/tuple_bloom.c | 15 ++++++++-------
src/box/tuple_bloom.h | 8 ++++----
src/box/tuple_compare.cc | 33 ---------------------------------
src/box/vy_run.c | 10 ++--------
5 files changed, 14 insertions(+), 63 deletions(-)
diff --git a/src/box/key_def.h b/src/box/key_def.h
index dd62f6a3..e3a34ce1 100644
--- a/src/box/key_def.h
+++ b/src/box/key_def.h
@@ -512,17 +512,6 @@ tuple_extract_key_raw(const char *data, const char *data_end,
}
/**
- * Return the length of the longest common prefix of two tuples.
- * @param tuple_a first tuple
- * @param tuple_b second tuple
- * @param key_def key defintion
- * @return number of key parts the two tuples have in common
- */
-uint32_t
-tuple_common_key_parts(const struct tuple *tuple_a, const struct tuple *tuple_b,
- struct key_def *key_def);
-
-/**
* Compare keys using the key definition.
* @param key_a key parts with MessagePack array header
* @param part_count_a the number of parts in the key_a
diff --git a/src/box/tuple_bloom.c b/src/box/tuple_bloom.c
index cf887c7b..39d218dc 100644
--- a/src/box/tuple_bloom.c
+++ b/src/box/tuple_bloom.c
@@ -72,8 +72,7 @@ tuple_bloom_builder_delete(struct tuple_bloom_builder *builder)
int
tuple_bloom_builder_add(struct tuple_bloom_builder *builder,
- const struct tuple *tuple, struct key_def *key_def,
- uint32_t hashed_parts)
+ const struct tuple *tuple, struct key_def *key_def)
{
assert(builder->part_count == key_def->part_count);
@@ -82,17 +81,20 @@ tuple_bloom_builder_add(struct tuple_bloom_builder *builder,
uint32_t total_size = 0;
for (uint32_t i = 0; i < key_def->part_count; i++) {
+ struct tuple_hash_array *hash_arr = &builder->parts[i];
total_size += tuple_hash_key_part(&h, &carry, tuple,
&key_def->parts[i]);
- if (i < hashed_parts) {
+ uint32_t hash = PMurHash32_Result(h, carry, total_size);
+ if (hash_arr->count > 0 &&
+ hash_arr->values[hash_arr->count - 1] == hash) {
/*
* This part is already in the bloom, proceed
- * to the next one. Note, we can't skip to
- * hashed_parts, as we need to compute the hash.
+ * to the next one. Note, this check only works
+ * if tuples are added in the order defined by
+ * the key definition.
*/
continue;
}
- struct tuple_hash_array *hash_arr = &builder->parts[i];
if (hash_arr->count >= hash_arr->capacity) {
uint32_t capacity = MAX(hash_arr->capacity * 2, 1024U);
uint32_t *values = realloc(hash_arr->values,
@@ -105,7 +107,6 @@ tuple_bloom_builder_add(struct tuple_bloom_builder *builder,
hash_arr->capacity = capacity;
hash_arr->values = values;
}
- uint32_t hash = PMurHash32_Result(h, carry, total_size);
hash_arr->values[hash_arr->count++] = hash;
}
return 0;
diff --git a/src/box/tuple_bloom.h b/src/box/tuple_bloom.h
index b05fee18..8380801e 100644
--- a/src/box/tuple_bloom.h
+++ b/src/box/tuple_bloom.h
@@ -111,14 +111,14 @@ tuple_bloom_builder_delete(struct tuple_bloom_builder *builder);
* @param builder - bloom filter builder
* @param tuple - tuple to add
* @param key_def - key definition
- * @param hashed_parts - number of key parts that have already
- * been added to the builder
* @return 0 on success, -1 on OOM
+ *
+ * For the bloom size calculation to be accurate, tuples
+ * must be added in the order defined by the key definition.
*/
int
tuple_bloom_builder_add(struct tuple_bloom_builder *builder,
- const struct tuple *tuple, struct key_def *key_def,
- uint32_t hashed_parts);
+ const struct tuple *tuple, struct key_def *key_def);
/**
* Create a new tuple bloom filter.
diff --git a/src/box/tuple_compare.cc b/src/box/tuple_compare.cc
index cf4519cc..dfe30b19 100644
--- a/src/box/tuple_compare.cc
+++ b/src/box/tuple_compare.cc
@@ -425,39 +425,6 @@ tuple_compare_field_with_hint(const char *field_a, enum mp_type a_type,
}
}
-uint32_t
-tuple_common_key_parts(const struct tuple *tuple_a, const struct tuple *tuple_b,
- struct key_def *key_def)
-{
- uint32_t i;
- struct tuple_format *tuple_a_format = tuple_format(tuple_a);
- struct tuple_format *tuple_b_format = tuple_format(tuple_b);
- const char *tuple_a_raw = tuple_data(tuple_a);
- const char *tuple_b_raw = tuple_data(tuple_b);
- const uint32_t *tuple_a_field_map = tuple_field_map(tuple_a);
- const uint32_t *tuple_b_field_map = tuple_field_map(tuple_b);
- for (i = 0; i < key_def->part_count; i++) {
- struct key_part *part = (struct key_part *)&key_def->parts[i];
- const char *field_a =
- tuple_field_raw_by_part(tuple_a_format, tuple_a_raw,
- tuple_a_field_map, part);
- const char *field_b =
- tuple_field_raw_by_part(tuple_b_format, tuple_b_raw,
- tuple_b_field_map, part);
- enum mp_type a_type = field_a != NULL ?
- mp_typeof(*field_a) : MP_NIL;
- enum mp_type b_type = field_b != NULL ?
- mp_typeof(*field_b) : MP_NIL;
- if (a_type == MP_NIL && b_type == MP_NIL)
- continue;
- if (a_type == MP_NIL || b_type == MP_NIL ||
- tuple_compare_field_with_hint(field_a, a_type,
- field_b, b_type, part->type, part->coll) != 0)
- break;
- }
- return i;
-}
-
template<bool is_nullable, bool has_optional_parts, bool has_json_paths>
static inline int
tuple_compare_slowpath(const struct tuple *tuple_a, const struct tuple *tuple_b,
diff --git a/src/box/vy_run.c b/src/box/vy_run.c
index 3c096b0a..e2123fe7 100644
--- a/src/box/vy_run.c
+++ b/src/box/vy_run.c
@@ -2178,11 +2178,8 @@ static int
vy_run_writer_write_to_page(struct vy_run_writer *writer, struct tuple *stmt)
{
if (writer->bloom != NULL) {
- uint32_t hashed_parts = writer->last_stmt == NULL ? 0 :
- tuple_common_key_parts(stmt, writer->last_stmt,
- writer->key_def);
tuple_bloom_builder_add(writer->bloom, stmt,
- writer->key_def, hashed_parts);
+ writer->key_def);
}
if (writer->last_stmt != NULL)
vy_stmt_unref_if_possible(writer->last_stmt);
@@ -2409,11 +2406,8 @@ vy_run_rebuild_index(struct vy_run *run, const char *dir,
if (tuple == NULL)
goto close_err;
if (bloom_builder != NULL) {
- uint32_t hashed_parts = prev_tuple == NULL ? 0 :
- tuple_common_key_parts(prev_tuple,
- tuple, key_def);
tuple_bloom_builder_add(bloom_builder, tuple,
- key_def, hashed_parts);
+ key_def);
}
key = tuple_extract_key(tuple, cmp_def, NULL);
if (prev_tuple != NULL)
--
2.11.0
^ permalink raw reply [flat|nested] 34+ messages in thread* [PATCH v2 06/14] bloom: factor out helper to add tuple hash to bloom builder
2019-03-13 8:52 [PATCH v2 00/14] vinyl: do not fill secondary tuples with nulls Vladimir Davydov
` (4 preceding siblings ...)
2019-03-13 8:52 ` [PATCH v2 05/14] bloom: do not use tuple_common_key_parts when constructing tuple bloom Vladimir Davydov
@ 2019-03-13 8:52 ` Vladimir Davydov
2019-03-13 11:52 ` Konstantin Osipov
2019-03-13 8:52 ` [PATCH v2 07/14] vinyl: add helpers to add/check statement with bloom Vladimir Davydov
` (8 subsequent siblings)
14 siblings, 1 reply; 34+ messages in thread
From: Vladimir Davydov @ 2019-03-13 8:52 UTC (permalink / raw)
To: kostja; +Cc: tarantool-patches
No functional changes, just move a piece of code, so as not to mix it in
the next patch.
---
src/box/tuple_bloom.c | 59 ++++++++++++++++++++++++++++++---------------------
1 file changed, 35 insertions(+), 24 deletions(-)
diff --git a/src/box/tuple_bloom.c b/src/box/tuple_bloom.c
index 39d218dc..367b1faa 100644
--- a/src/box/tuple_bloom.c
+++ b/src/box/tuple_bloom.c
@@ -70,6 +70,39 @@ tuple_bloom_builder_delete(struct tuple_bloom_builder *builder)
free(builder);
}
+/**
+ * Add a tuple hash to a hash array unless it's already there.
+ * Reallocate the array if necessary.
+ */
+static int
+tuple_hash_array_add(struct tuple_hash_array *hash_arr, uint32_t hash)
+{
+ if (hash_arr->count > 0 &&
+ hash_arr->values[hash_arr->count - 1] == hash) {
+ /*
+ * This part is already in the bloom, proceed
+ * to the next one. Note, this check only works
+ * if tuples are added in the order defined by
+ * the key definition.
+ */
+ return 0;
+ }
+ if (hash_arr->count >= hash_arr->capacity) {
+ uint32_t capacity = MAX(hash_arr->capacity * 2, 1024U);
+ uint32_t *values = realloc(hash_arr->values,
+ capacity * sizeof(*values));
+ if (values == NULL) {
+ diag_set(OutOfMemory, capacity * sizeof(*values),
+ "malloc", "tuple hash array");
+ return -1;
+ }
+ hash_arr->capacity = capacity;
+ hash_arr->values = values;
+ }
+ hash_arr->values[hash_arr->count++] = hash;
+ return 0;
+}
+
int
tuple_bloom_builder_add(struct tuple_bloom_builder *builder,
const struct tuple *tuple, struct key_def *key_def)
@@ -81,33 +114,11 @@ tuple_bloom_builder_add(struct tuple_bloom_builder *builder,
uint32_t total_size = 0;
for (uint32_t i = 0; i < key_def->part_count; i++) {
- struct tuple_hash_array *hash_arr = &builder->parts[i];
total_size += tuple_hash_key_part(&h, &carry, tuple,
&key_def->parts[i]);
uint32_t hash = PMurHash32_Result(h, carry, total_size);
- if (hash_arr->count > 0 &&
- hash_arr->values[hash_arr->count - 1] == hash) {
- /*
- * This part is already in the bloom, proceed
- * to the next one. Note, this check only works
- * if tuples are added in the order defined by
- * the key definition.
- */
- continue;
- }
- if (hash_arr->count >= hash_arr->capacity) {
- uint32_t capacity = MAX(hash_arr->capacity * 2, 1024U);
- uint32_t *values = realloc(hash_arr->values,
- capacity * sizeof(*values));
- if (values == NULL) {
- diag_set(OutOfMemory, capacity * sizeof(*values),
- "malloc", "tuple hash array");
- return -1;
- }
- hash_arr->capacity = capacity;
- hash_arr->values = values;
- }
- hash_arr->values[hash_arr->count++] = hash;
+ if (tuple_hash_array_add(&builder->parts[i], hash) != 0)
+ return -1;
}
return 0;
}
--
2.11.0
^ permalink raw reply [flat|nested] 34+ messages in thread* [PATCH v2 07/14] vinyl: add helpers to add/check statement with bloom
2019-03-13 8:52 [PATCH v2 00/14] vinyl: do not fill secondary tuples with nulls Vladimir Davydov
` (5 preceding siblings ...)
2019-03-13 8:52 ` [PATCH v2 06/14] bloom: factor out helper to add tuple hash to bloom builder Vladimir Davydov
@ 2019-03-13 8:52 ` Vladimir Davydov
2019-03-13 11:59 ` Konstantin Osipov
2019-03-13 8:52 ` [PATCH v2 08/14] vinyl: do not pass format to vy_apply_upsert Vladimir Davydov
` (7 subsequent siblings)
14 siblings, 1 reply; 34+ messages in thread
From: Vladimir Davydov @ 2019-03-13 8:52 UTC (permalink / raw)
To: kostja; +Cc: tarantool-patches
A Vinyl statement may be either a key or a tuple. We must use different
functions for the two kinds when working with a bloom filter. Let's
introduce helpers incorporating that logic.
Notes:
- Currently, we never add keys to bloom filters, but after the next
patch we will, so this patch adds tuple_bloom_builder_add_key helper.
- According to the function protocol, tuple_bloom_builder_add may fail
with out-of-memory, but we never checked that. Fix that while we are
at it.
---
src/box/tuple_bloom.c | 23 +++++++++++++++++++++++
src/box/tuple_bloom.h | 15 +++++++++++++++
src/box/vy_run.c | 37 ++++++++++++++-----------------------
src/box/vy_stmt.c | 29 +++++++++++++++++++++++++++++
src/box/vy_stmt.h | 18 ++++++++++++++++++
5 files changed, 99 insertions(+), 23 deletions(-)
diff --git a/src/box/tuple_bloom.c b/src/box/tuple_bloom.c
index 367b1faa..8d918065 100644
--- a/src/box/tuple_bloom.c
+++ b/src/box/tuple_bloom.c
@@ -123,6 +123,29 @@ tuple_bloom_builder_add(struct tuple_bloom_builder *builder,
return 0;
}
+int
+tuple_bloom_builder_add_key(struct tuple_bloom_builder *builder,
+ const char *key, uint32_t part_count,
+ struct key_def *key_def)
+{
+ (void)part_count;
+ assert(part_count >= key_def->part_count);
+ assert(builder->part_count == key_def->part_count);
+
+ uint32_t h = HASH_SEED;
+ uint32_t carry = 0;
+ uint32_t total_size = 0;
+
+ for (uint32_t i = 0; i < key_def->part_count; i++) {
+ total_size += tuple_hash_field(&h, &carry, &key,
+ key_def->parts[i].coll);
+ uint32_t hash = PMurHash32_Result(h, carry, total_size);
+ if (tuple_hash_array_add(&builder->parts[i], hash) != 0)
+ return -1;
+ }
+ return 0;
+}
+
struct tuple_bloom *
tuple_bloom_new(struct tuple_bloom_builder *builder, double fpr)
{
diff --git a/src/box/tuple_bloom.h b/src/box/tuple_bloom.h
index 8380801e..f653c7ed 100644
--- a/src/box/tuple_bloom.h
+++ b/src/box/tuple_bloom.h
@@ -121,6 +121,21 @@ tuple_bloom_builder_add(struct tuple_bloom_builder *builder,
const struct tuple *tuple, struct key_def *key_def);
/**
+ * Add a key hash to a tuple bloom filter builder.
+ * @param builder - bloom filter builder
+ * @param key - key to add
+ * @param part_count - number of parts in the key
+ * @param key_def - key definition
+ * @param hashed_parts - number of key parts that have already
+ * been added to the builder
+ * @return 0 on success, -1 on OOM
+ */
+int
+tuple_bloom_builder_add_key(struct tuple_bloom_builder *builder,
+ const char *key, uint32_t part_count,
+ struct key_def *key_def);
+
+/**
* Create a new tuple bloom filter.
* @param builder - bloom filter builder
* @param fpr - desired false positive rate
diff --git a/src/box/vy_run.c b/src/box/vy_run.c
index e2123fe7..57f62b72 100644
--- a/src/box/vy_run.c
+++ b/src/box/vy_run.c
@@ -1248,22 +1248,11 @@ vy_run_iterator_do_seek(struct vy_run_iterator *itr,
struct tuple_bloom *bloom = run->info.bloom;
struct key_def *key_def = itr->key_def;
- if (iterator_type == ITER_EQ && bloom != NULL) {
- bool need_lookup;
- if (vy_stmt_is_key(key)) {
- const char *data = tuple_data(key);
- uint32_t part_count = mp_decode_array(&data);
- need_lookup = tuple_bloom_maybe_has_key(bloom, data,
- part_count, key_def);
- } else {
- need_lookup = tuple_bloom_maybe_has(bloom, key,
- key_def);
- }
- if (!need_lookup) {
- itr->search_ended = true;
- itr->stat->bloom_hit++;
- return 0;
- }
+ if (iterator_type == ITER_EQ && bloom != NULL &&
+ !vy_stmt_bloom_maybe_has(bloom, key, key_def)) {
+ itr->search_ended = true;
+ itr->stat->bloom_hit++;
+ return 0;
}
itr->stat->lookup++;
@@ -2177,10 +2166,10 @@ vy_run_writer_start_page(struct vy_run_writer *writer,
static int
vy_run_writer_write_to_page(struct vy_run_writer *writer, struct tuple *stmt)
{
- if (writer->bloom != NULL) {
- tuple_bloom_builder_add(writer->bloom, stmt,
- writer->key_def);
- }
+ if (writer->bloom != NULL &&
+ vy_stmt_bloom_builder_add(writer->bloom, stmt,
+ writer->key_def) != 0)
+ return -1;
if (writer->last_stmt != NULL)
vy_stmt_unref_if_possible(writer->last_stmt);
writer->last_stmt = stmt;
@@ -2405,9 +2394,11 @@ vy_run_rebuild_index(struct vy_run *run, const char *dir,
format, iid == 0);
if (tuple == NULL)
goto close_err;
- if (bloom_builder != NULL) {
- tuple_bloom_builder_add(bloom_builder, tuple,
- key_def);
+ if (bloom_builder != NULL &&
+ vy_stmt_bloom_builder_add(bloom_builder, tuple,
+ key_def) != 0) {
+ tuple_unref(tuple);
+ goto close_err;
}
key = tuple_extract_key(tuple, cmp_def, NULL);
if (prev_tuple != NULL)
diff --git a/src/box/vy_stmt.c b/src/box/vy_stmt.c
index 954ec276..229f8b41 100644
--- a/src/box/vy_stmt.c
+++ b/src/box/vy_stmt.c
@@ -41,6 +41,7 @@
#include <small/lsregion.h>
#include "error.h"
+#include "tuple_bloom.h"
#include "tuple_format.h"
#include "xrow.h"
#include "fiber.h"
@@ -663,6 +664,34 @@ vy_stmt_extract_key_raw(const char *data, const char *data_end,
return key;
}
+int
+vy_stmt_bloom_builder_add(struct tuple_bloom_builder *builder,
+ const struct tuple *stmt, struct key_def *key_def)
+{
+ if (vy_stmt_is_key(stmt)) {
+ const char *data = tuple_data(stmt);
+ uint32_t part_count = mp_decode_array(&data);
+ return tuple_bloom_builder_add_key(builder, data,
+ part_count, key_def);
+ } else {
+ return tuple_bloom_builder_add(builder, stmt, key_def);
+ }
+}
+
+bool
+vy_stmt_bloom_maybe_has(const struct tuple_bloom *bloom,
+ const struct tuple *stmt, struct key_def *key_def)
+{
+ if (vy_stmt_is_key(stmt)) {
+ const char *data = tuple_data(stmt);
+ uint32_t part_count = mp_decode_array(&data);
+ return tuple_bloom_maybe_has_key(bloom, data,
+ part_count, key_def);
+ } else {
+ return tuple_bloom_maybe_has(bloom, stmt, key_def);
+ }
+}
+
/**
* Encode the given statement meta data in a request.
* Returns 0 on success, -1 on memory allocation error.
diff --git a/src/box/vy_stmt.h b/src/box/vy_stmt.h
index 7c9b3677..7b93883d 100644
--- a/src/box/vy_stmt.h
+++ b/src/box/vy_stmt.h
@@ -50,6 +50,8 @@ struct xrow_header;
struct region;
struct tuple_format;
struct tuple_dictionary;
+struct tuple_bloom;
+struct tuple_bloom_builder;
struct iovec;
#define MAX_LSN (INT64_MAX / 2)
@@ -595,6 +597,22 @@ vy_stmt_extract_key_raw(const char *data, const char *data_end,
struct tuple_format *format);
/**
+ * Add a statement hash to a bloom filter builder.
+ * See tuple_bloom_builder_add() for more details.
+ */
+int
+vy_stmt_bloom_builder_add(struct tuple_bloom_builder *builder,
+ const struct tuple *stmt, struct key_def *key_def);
+
+/**
+ * Check if a statement hash is present in a bloom filter.
+ * See tuple_bloom_maybe_has() for more details.
+ */
+bool
+vy_stmt_bloom_maybe_has(const struct tuple_bloom *bloom,
+ const struct tuple *stmt, struct key_def *key_def);
+
+/**
* Encode vy_stmt for a primary key as xrow_header
*
* @param value statement to encode
--
2.11.0
^ permalink raw reply [flat|nested] 34+ messages in thread* Re: [PATCH v2 07/14] vinyl: add helpers to add/check statement with bloom
2019-03-13 8:52 ` [PATCH v2 07/14] vinyl: add helpers to add/check statement with bloom Vladimir Davydov
@ 2019-03-13 11:59 ` Konstantin Osipov
2019-03-13 12:25 ` Vladimir Davydov
0 siblings, 1 reply; 34+ messages in thread
From: Konstantin Osipov @ 2019-03-13 11:59 UTC (permalink / raw)
To: Vladimir Davydov; +Cc: tarantool-patches
* Vladimir Davydov <vdavydov.dev@gmail.com> [19/03/13 11:58]:
> A Vinyl statement may be either a key or a tuple. We must use different
> functions for the two kinds when working with a bloom filter. Let's
> introduce helpers incorporating that logic.
While we are at it, tuple_bloom_builder is a cumbersome name. Why
not simply bloom_builder or vy_bloom_builder?
Especially the name is confusing since now we have
tuple_bloom_builder_add(_tuple) and tuple_bloom_builder_add_key.
Besides, tuple_bloom_builder pretends to be generic, not specific
to vinyl engine. I don't think anyone cares (I don't).
> +int
> +tuple_bloom_builder_add_key(struct tuple_bloom_builder *builder,
> + const char *key, uint32_t part_count,
> + struct key_def *key_def)
> +{
> + (void)part_count;
> + assert(part_count >= key_def->part_count);
> + assert(builder->part_count == key_def->part_count);
> +
> + uint32_t h = HASH_SEED;
> + uint32_t carry = 0;
> + uint32_t total_size = 0;
> +
Once again, since we are at it I would appreciate an explanation
about our strategy for building bloom filters for partial keys.
No other LSM I'm aware of is doing it this way, so it would be
nice to see a write down of how it works.
> + for (uint32_t i = 0; i < key_def->part_count; i++) {
> + total_size += tuple_hash_field(&h, &carry, &key,
> + key_def->parts[i].coll);
> + uint32_t hash = PMurHash32_Result(h, carry, total_size);
> + if (tuple_hash_array_add(&builder->parts[i], hash) != 0)
> + return -1;
> + }
> + return 0;
> +}
--
Konstantin Osipov, Moscow, Russia, +7 903 626 22 32
http://tarantool.io - www.twitter.com/kostja_osipov
^ permalink raw reply [flat|nested] 34+ messages in thread* Re: [PATCH v2 07/14] vinyl: add helpers to add/check statement with bloom
2019-03-13 11:59 ` Konstantin Osipov
@ 2019-03-13 12:25 ` Vladimir Davydov
0 siblings, 0 replies; 34+ messages in thread
From: Vladimir Davydov @ 2019-03-13 12:25 UTC (permalink / raw)
To: Konstantin Osipov; +Cc: tarantool-patches
On Wed, Mar 13, 2019 at 02:59:34PM +0300, Konstantin Osipov wrote:
> * Vladimir Davydov <vdavydov.dev@gmail.com> [19/03/13 11:58]:
>
> > A Vinyl statement may be either a key or a tuple. We must use different
> > functions for the two kinds when working with a bloom filter. Let's
> > introduce helpers incorporating that logic.
>
> While we are at it, tuple_bloom_builder is a cumbersome name.
> Why not simply bloom_builder
So as not to consue with generic bloom defined in salad.
> or vy_bloom_builder?
Just in case we want to reuse it. After all, tuple_bloom isn't really
specific to vinyl.
>
> Especially the name is confusing since now we have
> tuple_bloom_builder_add(_tuple) and tuple_bloom_builder_add_key.
>
> Besides, tuple_bloom_builder pretends to be generic, not specific
> to vinyl engine. I don't think anyone cares (I don't).
Well, we can move it to vy_bloom, I guess, but I don't think it's really
necessary now.
>
> > +int
> > +tuple_bloom_builder_add_key(struct tuple_bloom_builder *builder,
> > + const char *key, uint32_t part_count,
> > + struct key_def *key_def)
> > +{
> > + (void)part_count;
> > + assert(part_count >= key_def->part_count);
> > + assert(builder->part_count == key_def->part_count);
> > +
> > + uint32_t h = HASH_SEED;
> > + uint32_t carry = 0;
> > + uint32_t total_size = 0;
> > +
>
> Once again, since we are at it I would appreciate an explanation
> about our strategy for building bloom filters for partial keys.
> No other LSM I'm aware of is doing it this way, so it would be
> nice to see a write down of how it works.
Okay, I'll add a comment to tuple_bloom explaining what's going on in
the builder.
>
>
> > + for (uint32_t i = 0; i < key_def->part_count; i++) {
> > + total_size += tuple_hash_field(&h, &carry, &key,
> > + key_def->parts[i].coll);
> > + uint32_t hash = PMurHash32_Result(h, carry, total_size);
> > + if (tuple_hash_array_add(&builder->parts[i], hash) != 0)
> > + return -1;
> > + }
> > + return 0;
> > +}
^ permalink raw reply [flat|nested] 34+ messages in thread
* [PATCH v2 08/14] vinyl: do not pass format to vy_apply_upsert
2019-03-13 8:52 [PATCH v2 00/14] vinyl: do not fill secondary tuples with nulls Vladimir Davydov
` (6 preceding siblings ...)
2019-03-13 8:52 ` [PATCH v2 07/14] vinyl: add helpers to add/check statement with bloom Vladimir Davydov
@ 2019-03-13 8:52 ` Vladimir Davydov
2019-03-13 12:00 ` Konstantin Osipov
2019-03-13 8:52 ` [PATCH v2 09/14] vinyl: clean up write iterator source destruction Vladimir Davydov
` (6 subsequent siblings)
14 siblings, 1 reply; 34+ messages in thread
From: Vladimir Davydov @ 2019-03-13 8:52 UTC (permalink / raw)
To: kostja; +Cc: tarantool-patches
Use the format of the given statement instead. Passing format is
a legacy from the time when we have a separate format for UPSERTs.
Nowadays it only obfuscates the code.
---
src/box/vinyl.c | 2 +-
src/box/vy_history.c | 5 ++---
src/box/vy_history.h | 3 +--
src/box/vy_lsm.c | 3 +--
src/box/vy_point_lookup.c | 4 ++--
src/box/vy_read_iterator.c | 2 +-
src/box/vy_tx.c | 5 ++---
src/box/vy_upsert.c | 5 +++--
src/box/vy_upsert.h | 4 +---
src/box/vy_write_iterator.c | 4 ++--
10 files changed, 16 insertions(+), 21 deletions(-)
diff --git a/src/box/vinyl.c b/src/box/vinyl.c
index 0146f62c..0e908cc5 100644
--- a/src/box/vinyl.c
+++ b/src/box/vinyl.c
@@ -4069,7 +4069,7 @@ vy_build_recover_stmt(struct vy_lsm *lsm, struct vy_lsm *pk,
return -1;
} else if (type == IPROTO_UPSERT) {
struct tuple *new_tuple = vy_apply_upsert(mem_stmt, old_tuple,
- pk->cmp_def, pk->mem_format, true);
+ pk->cmp_def, true);
if (new_tuple == NULL)
return -1;
uint32_t data_len;
diff --git a/src/box/vy_history.c b/src/box/vy_history.c
index 0f3b7119..b45c6d51 100644
--- a/src/box/vy_history.c
+++ b/src/box/vy_history.c
@@ -74,8 +74,7 @@ vy_history_cleanup(struct vy_history *history)
int
vy_history_apply(struct vy_history *history, struct key_def *cmp_def,
- struct tuple_format *format, bool keep_delete,
- int *upserts_applied, struct tuple **ret)
+ bool keep_delete, int *upserts_applied, struct tuple **ret)
{
*ret = NULL;
*upserts_applied = 0;
@@ -101,7 +100,7 @@ vy_history_apply(struct vy_history *history, struct key_def *cmp_def,
}
while (node != NULL) {
struct tuple *stmt = vy_apply_upsert(node->stmt, curr_stmt,
- cmp_def, format, true);
+ cmp_def, true);
++*upserts_applied;
if (curr_stmt != NULL)
tuple_unref(curr_stmt);
diff --git a/src/box/vy_history.h b/src/box/vy_history.h
index e3c5a19e..458ea749 100644
--- a/src/box/vy_history.h
+++ b/src/box/vy_history.h
@@ -155,8 +155,7 @@ vy_history_cleanup(struct vy_history *history);
*/
int
vy_history_apply(struct vy_history *history, struct key_def *cmp_def,
- struct tuple_format *format, bool keep_delete,
- int *upserts_applied, struct tuple **ret);
+ bool keep_delete, int *upserts_applied, struct tuple **ret);
#if defined(__cplusplus)
} /* extern "C" */
diff --git a/src/box/vy_lsm.c b/src/box/vy_lsm.c
index 171664d4..2dc8f639 100644
--- a/src/box/vy_lsm.c
+++ b/src/box/vy_lsm.c
@@ -977,8 +977,7 @@ vy_lsm_commit_upsert(struct vy_lsm *lsm, struct vy_mem *mem,
older = vy_mem_older_lsn(mem, stmt);
assert(older == NULL || vy_stmt_type(older) != IPROTO_UPSERT);
struct tuple *upserted =
- vy_apply_upsert(stmt, older, lsm->cmp_def,
- lsm->mem_format, false);
+ vy_apply_upsert(stmt, older, lsm->cmp_def, false);
lsm->stat.upsert.applied++;
if (upserted == NULL) {
diff --git a/src/box/vy_point_lookup.c b/src/box/vy_point_lookup.c
index 18d5622b..51226ce8 100644
--- a/src/box/vy_point_lookup.c
+++ b/src/box/vy_point_lookup.c
@@ -272,7 +272,7 @@ done:
if (rc == 0) {
int upserts_applied;
- rc = vy_history_apply(&history, lsm->cmp_def, lsm->mem_format,
+ rc = vy_history_apply(&history, lsm->cmp_def,
false, &upserts_applied, ret);
lsm->stat.upsert.applied += upserts_applied;
}
@@ -319,7 +319,7 @@ vy_point_lookup_mem(struct vy_lsm *lsm, const struct vy_read_view **rv,
done:
if (rc == 0) {
int upserts_applied;
- rc = vy_history_apply(&history, lsm->cmp_def, lsm->mem_format,
+ rc = vy_history_apply(&history, lsm->cmp_def,
true, &upserts_applied, ret);
lsm->stat.upsert.applied += upserts_applied;
}
diff --git a/src/box/vy_read_iterator.c b/src/box/vy_read_iterator.c
index 94c5f4b9..cc884bec 100644
--- a/src/box/vy_read_iterator.c
+++ b/src/box/vy_read_iterator.c
@@ -805,7 +805,7 @@ vy_read_iterator_apply_history(struct vy_read_iterator *itr,
}
int upserts_applied = 0;
- int rc = vy_history_apply(&history, lsm->cmp_def, lsm->mem_format,
+ int rc = vy_history_apply(&history, lsm->cmp_def,
true, &upserts_applied, ret);
lsm->stat.upsert.applied += upserts_applied;
diff --git a/src/box/vy_tx.c b/src/box/vy_tx.c
index 3768b3bd..c4445505 100644
--- a/src/box/vy_tx.c
+++ b/src/box/vy_tx.c
@@ -481,7 +481,7 @@ vy_tx_write(struct vy_lsm *lsm, struct vy_mem *mem,
vy_cache_on_write(&lsm->cache, stmt, &deleted);
if (deleted != NULL) {
struct tuple *applied = vy_apply_upsert(stmt, deleted,
- mem->cmp_def, mem->format, false);
+ mem->cmp_def, false);
tuple_unref(deleted);
if (applied != NULL) {
assert(vy_stmt_type(applied) == IPROTO_REPLACE);
@@ -998,8 +998,7 @@ vy_tx_set_with_colmask(struct vy_tx *tx, struct vy_lsm *lsm,
old_type == IPROTO_DELETE);
(void) old_type;
- applied = vy_apply_upsert(stmt, old->stmt, lsm->cmp_def,
- lsm->mem_format, true);
+ applied = vy_apply_upsert(stmt, old->stmt, lsm->cmp_def, true);
lsm->stat.upsert.applied++;
if (applied == NULL)
return -1;
diff --git a/src/box/vy_upsert.c b/src/box/vy_upsert.c
index 3c5a4abb..8cf0cc19 100644
--- a/src/box/vy_upsert.c
+++ b/src/box/vy_upsert.c
@@ -88,8 +88,7 @@ vy_upsert_try_to_squash(struct tuple_format *format, struct region *region,
struct tuple *
vy_apply_upsert(const struct tuple *new_stmt, const struct tuple *old_stmt,
- struct key_def *cmp_def, struct tuple_format *format,
- bool suppress_error)
+ struct key_def *cmp_def, bool suppress_error)
{
/*
* old_stmt - previous (old) version of stmt
@@ -107,6 +106,8 @@ vy_apply_upsert(const struct tuple *new_stmt, const struct tuple *old_stmt,
return vy_stmt_replace_from_upsert(new_stmt);
}
+ struct tuple_format *format = tuple_format(new_stmt);
+
/*
* Unpack UPSERT operation from the new stmt
*/
diff --git a/src/box/vy_upsert.h b/src/box/vy_upsert.h
index 5649961e..df3413d8 100644
--- a/src/box/vy_upsert.h
+++ b/src/box/vy_upsert.h
@@ -57,7 +57,6 @@ struct tuple_format;
* @param new_stmt An UPSERT statement.
* @param old_stmt An REPLACE/DELETE/UPSERT statement or NULL.
* @param cmp_def Key definition of an index, with primary parts.
- * @param format Format for REPLACE/DELETE tuples.
* @param suppress_error True if ClientErrors must not be written to log.
*
* @retval NULL Memory allocation error.
@@ -65,8 +64,7 @@ struct tuple_format;
*/
struct tuple *
vy_apply_upsert(const struct tuple *new_stmt, const struct tuple *old_stmt,
- struct key_def *cmp_def, struct tuple_format *format,
- bool suppress_error);
+ struct key_def *cmp_def, bool suppress_error);
#if defined(__cplusplus)
} /* extern "C" */
diff --git a/src/box/vy_write_iterator.c b/src/box/vy_write_iterator.c
index 0e804ac1..2c4dbf58 100644
--- a/src/box/vy_write_iterator.c
+++ b/src/box/vy_write_iterator.c
@@ -842,7 +842,7 @@ vy_read_view_merge(struct vy_write_iterator *stream, struct tuple *hint,
assert(!stream->is_last_level || hint == NULL ||
vy_stmt_type(hint) != IPROTO_UPSERT);
struct tuple *applied = vy_apply_upsert(h->tuple, hint,
- stream->cmp_def, stream->format, false);
+ stream->cmp_def, false);
if (applied == NULL)
return -1;
vy_stmt_unref_if_possible(h->tuple);
@@ -856,7 +856,7 @@ vy_read_view_merge(struct vy_write_iterator *stream, struct tuple *hint,
vy_stmt_type(h->tuple) == IPROTO_UPSERT);
assert(result->tuple != NULL);
struct tuple *applied = vy_apply_upsert(h->tuple, result->tuple,
- stream->cmp_def, stream->format, false);
+ stream->cmp_def, false);
if (applied == NULL)
return -1;
vy_stmt_unref_if_possible(result->tuple);
--
2.11.0
^ permalink raw reply [flat|nested] 34+ messages in thread* [PATCH v2 09/14] vinyl: clean up write iterator source destruction
2019-03-13 8:52 [PATCH v2 00/14] vinyl: do not fill secondary tuples with nulls Vladimir Davydov
` (7 preceding siblings ...)
2019-03-13 8:52 ` [PATCH v2 08/14] vinyl: do not pass format to vy_apply_upsert Vladimir Davydov
@ 2019-03-13 8:52 ` Vladimir Davydov
2019-03-13 12:05 ` Konstantin Osipov
2019-03-13 8:52 ` [PATCH v2 10/14] vinyl: zap vy_write_iterator->format Vladimir Davydov
` (5 subsequent siblings)
14 siblings, 1 reply; 34+ messages in thread
From: Vladimir Davydov @ 2019-03-13 8:52 UTC (permalink / raw)
To: kostja; +Cc: tarantool-patches
By convention we have two methods in each write iterator stream
implementation (including the write iterator itself as it implements
the interface too): 'stop' and 'close'. The 'stop' method is called
in a worker thread. It reverses the effect of 'start'. We need it
unreference all tuples referenced during the iteration (we must do
it in the worker thread, where the tuples were referenced in the first
place so as not to unreference tuple formats, see vy_tuple_delete).
The 'close' method is called from the tx thread to unreference tuple
formats if necessary and release memory.
For the write iterator itself we follow this convention. However,
for individual sources, for vy_slice_stream source to be more exact,
we do not - the write iterator calls both 'stop' and 'close' from
its own 'stop method. Let's cleanup this mess and make the write
iterator follow the convention. We'll need it in the next patch.
---
src/box/vy_run.c | 8 +++----
src/box/vy_write_iterator.c | 54 ++++++++++++++++++++++++++-------------------
2 files changed, 35 insertions(+), 27 deletions(-)
diff --git a/src/box/vy_run.c b/src/box/vy_run.c
index 57f62b72..59ae906a 100644
--- a/src/box/vy_run.c
+++ b/src/box/vy_run.c
@@ -2654,9 +2654,9 @@ vy_slice_stream_next(struct vy_stmt_stream *virt_stream, struct tuple **ret)
* Free resources.
*/
static void
-vy_slice_stream_close(struct vy_stmt_stream *virt_stream)
+vy_slice_stream_stop(struct vy_stmt_stream *virt_stream)
{
- assert(virt_stream->iface->close == vy_slice_stream_close);
+ assert(virt_stream->iface->stop == vy_slice_stream_stop);
struct vy_slice_stream *stream = (struct vy_slice_stream *)virt_stream;
if (stream->page != NULL) {
vy_page_delete(stream->page);
@@ -2671,8 +2671,8 @@ vy_slice_stream_close(struct vy_stmt_stream *virt_stream)
static const struct vy_stmt_stream_iface vy_slice_stream_iface = {
.start = vy_slice_stream_search,
.next = vy_slice_stream_next,
- .stop = NULL,
- .close = vy_slice_stream_close
+ .stop = vy_slice_stream_stop,
+ .close = NULL,
};
void
diff --git a/src/box/vy_write_iterator.c b/src/box/vy_write_iterator.c
index 2c4dbf58..8988daa3 100644
--- a/src/box/vy_write_iterator.c
+++ b/src/box/vy_write_iterator.c
@@ -265,6 +265,7 @@ vy_write_iterator_new_src(struct vy_write_iterator *stream)
"malloc", "vinyl write stream");
return NULL;
}
+ heap_node_create(&res->heap_node);
res->is_end_of_key = false;
rlist_add(&stream->src_list, &res->in_src_list);
return res;
@@ -278,8 +279,6 @@ vy_write_iterator_delete_src(struct vy_write_iterator *stream,
{
(void)stream;
assert(!src->is_end_of_key);
- if (src->stream.iface->stop != NULL)
- src->stream.iface->stop(&src->stream);
if (src->stream.iface->close != NULL)
src->stream.iface->close(&src->stream);
rlist_del(&src->in_src_list);
@@ -287,8 +286,8 @@ vy_write_iterator_delete_src(struct vy_write_iterator *stream,
}
/**
- * Add a source to the write iterator heap. The added source
- * must be open.
+ * Start iteration in the given source, retrieve the first tuple,
+ * and add the source to the write iterator heap.
*
* @return 0 - success, not 0 - error.
*/
@@ -298,35 +297,38 @@ vy_write_iterator_add_src(struct vy_write_iterator *stream,
{
if (src->stream.iface->start != NULL) {
int rc = src->stream.iface->start(&src->stream);
- if (rc != 0) {
- vy_write_iterator_delete_src(stream, src);
+ if (rc != 0)
return rc;
- }
}
int rc = src->stream.iface->next(&src->stream, &src->tuple);
- if (rc != 0 || src->tuple == NULL) {
- vy_write_iterator_delete_src(stream, src);
- return rc;
- }
+ if (rc != 0 || src->tuple == NULL)
+ goto stop;
+
rc = vy_source_heap_insert(&stream->src_heap, src);
if (rc != 0) {
diag_set(OutOfMemory, sizeof(void *),
"malloc", "vinyl write stream heap");
- vy_write_iterator_delete_src(stream, src);
- return rc;
+ goto stop;
}
return 0;
+stop:
+ if (src->stream.iface->stop != NULL)
+ src->stream.iface->stop(&src->stream);
+ return rc;
}
/**
- * Remove a source from the heap, destroy and free it.
+ * Remove a source from the heap and stop iteration.
*/
static void
vy_write_iterator_remove_src(struct vy_write_iterator *stream,
struct vy_write_src *src)
{
+ if (heap_node_is_stray(&src->heap_node))
+ return; /* already removed */
vy_source_heap_delete(&stream->src_heap, src);
- vy_write_iterator_delete_src(stream, src);
+ if (src->stream.iface->stop != NULL)
+ src->stream.iface->stop(&src->stream);
}
static const struct vy_stmt_stream_iface vy_slice_stream_iface;
@@ -394,16 +396,20 @@ vy_write_iterator_start(struct vy_stmt_stream *vstream)
{
assert(vstream->iface->start == vy_write_iterator_start);
struct vy_write_iterator *stream = (struct vy_write_iterator *)vstream;
- struct vy_write_src *src, *tmp;
- rlist_foreach_entry_safe(src, &stream->src_list, in_src_list, tmp) {
+ struct vy_write_src *src;
+ rlist_foreach_entry(src, &stream->src_list, in_src_list) {
if (vy_write_iterator_add_src(stream, src) != 0)
- return -1;
+ goto fail;
}
return 0;
+fail:
+ rlist_foreach_entry(src, &stream->src_list, in_src_list)
+ vy_write_iterator_remove_src(stream, src);
+ return -1;
}
/**
- * Free all resources.
+ * Stop iteration in all sources.
*/
static void
vy_write_iterator_stop(struct vy_stmt_stream *vstream)
@@ -412,9 +418,9 @@ vy_write_iterator_stop(struct vy_stmt_stream *vstream)
struct vy_write_iterator *stream = (struct vy_write_iterator *)vstream;
for (int i = 0; i < stream->rv_count; ++i)
vy_read_view_stmt_destroy(&stream->read_views[i]);
- struct vy_write_src *src, *tmp;
- rlist_foreach_entry_safe(src, &stream->src_list, in_src_list, tmp)
- vy_write_iterator_delete_src(stream, src);
+ struct vy_write_src *src;
+ rlist_foreach_entry(src, &stream->src_list, in_src_list)
+ vy_write_iterator_remove_src(stream, src);
if (stream->last_stmt != NULL) {
vy_stmt_unref_if_possible(stream->last_stmt);
stream->last_stmt = NULL;
@@ -439,7 +445,9 @@ vy_write_iterator_close(struct vy_stmt_stream *vstream)
{
assert(vstream->iface->close == vy_write_iterator_close);
struct vy_write_iterator *stream = (struct vy_write_iterator *)vstream;
- vy_write_iterator_stop(vstream);
+ struct vy_write_src *src, *tmp;
+ rlist_foreach_entry_safe(src, &stream->src_list, in_src_list, tmp)
+ vy_write_iterator_delete_src(stream, src);
vy_source_heap_destroy(&stream->src_heap);
tuple_format_unref(stream->format);
free(stream);
--
2.11.0
^ permalink raw reply [flat|nested] 34+ messages in thread* Re: [PATCH v2 09/14] vinyl: clean up write iterator source destruction
2019-03-13 8:52 ` [PATCH v2 09/14] vinyl: clean up write iterator source destruction Vladimir Davydov
@ 2019-03-13 12:05 ` Konstantin Osipov
0 siblings, 0 replies; 34+ messages in thread
From: Konstantin Osipov @ 2019-03-13 12:05 UTC (permalink / raw)
To: Vladimir Davydov; +Cc: tarantool-patches
* Vladimir Davydov <vdavydov.dev@gmail.com> [19/03/13 11:58]:
> By convention we have two methods in each write iterator stream
> implementation (including the write iterator itself as it implements
> the interface too): 'stop' and 'close'. The 'stop' method is called
> in a worker thread. It reverses the effect of 'start'. We need it
> unreference all tuples referenced during the iteration (we must do
> it in the worker thread, where the tuples were referenced in the first
> place so as not to unreference tuple formats, see vy_tuple_delete).
> The 'close' method is called from the tx thread to unreference tuple
> formats if necessary and release memory.
>
> For the write iterator itself we follow this convention. However,
> for individual sources, for vy_slice_stream source to be more exact,
> we do not - the write iterator calls both 'stop' and 'close' from
> its own 'stop method. Let's cleanup this mess and make the write
> iterator follow the convention. We'll need it in the next patch.
OK to push.
--
Konstantin Osipov, Moscow, Russia, +7 903 626 22 32
http://tarantool.io - www.twitter.com/kostja_osipov
^ permalink raw reply [flat|nested] 34+ messages in thread
* [PATCH v2 10/14] vinyl: zap vy_write_iterator->format
2019-03-13 8:52 [PATCH v2 00/14] vinyl: do not fill secondary tuples with nulls Vladimir Davydov
` (8 preceding siblings ...)
2019-03-13 8:52 ` [PATCH v2 09/14] vinyl: clean up write iterator source destruction Vladimir Davydov
@ 2019-03-13 8:52 ` Vladimir Davydov
2019-03-13 12:06 ` Konstantin Osipov
2019-03-13 8:52 ` [PATCH v2 11/14] vinyl: do not fill secondary tuples with nulls when decoded Vladimir Davydov
` (4 subsequent siblings)
14 siblings, 1 reply; 34+ messages in thread
From: Vladimir Davydov @ 2019-03-13 8:52 UTC (permalink / raw)
To: kostja; +Cc: tarantool-patches
It's actually only needed to initialize disk streams so let's pass it
to vy_write_iterator_new_slice() instead.
---
src/box/vinyl.c | 6 +++---
src/box/vy_run.c | 11 ++++++++++-
src/box/vy_scheduler.c | 13 ++++++-------
src/box/vy_write_iterator.c | 25 ++++++++++---------------
src/box/vy_write_iterator.h | 9 ++++-----
test/unit/vy_point_lookup.c | 11 +++++------
test/unit/vy_write_iterator.c | 3 +--
7 files changed, 39 insertions(+), 39 deletions(-)
diff --git a/src/box/vinyl.c b/src/box/vinyl.c
index 0e908cc5..ced0efe5 100644
--- a/src/box/vinyl.c
+++ b/src/box/vinyl.c
@@ -3004,14 +3004,14 @@ vy_send_range(struct vy_join_ctx *ctx,
/* Create a write iterator. */
struct rlist fake_read_views;
rlist_create(&fake_read_views);
- ctx->wi = vy_write_iterator_new(ctx->key_def, ctx->format,
- true, true, &fake_read_views, NULL);
+ ctx->wi = vy_write_iterator_new(ctx->key_def, true, true,
+ &fake_read_views, NULL);
if (ctx->wi == NULL) {
rc = -1;
goto out;
}
rlist_foreach_entry(slice, &ctx->slices, in_join) {
- rc = vy_write_iterator_new_slice(ctx->wi, slice);
+ rc = vy_write_iterator_new_slice(ctx->wi, slice, ctx->format);
if (rc != 0)
goto out_delete_wi;
}
diff --git a/src/box/vy_run.c b/src/box/vy_run.c
index 59ae906a..76b2f94a 100644
--- a/src/box/vy_run.c
+++ b/src/box/vy_run.c
@@ -2668,11 +2668,19 @@ vy_slice_stream_stop(struct vy_stmt_stream *virt_stream)
}
}
+static void
+vy_slice_stream_close(struct vy_stmt_stream *virt_stream)
+{
+ assert(virt_stream->iface->close == vy_slice_stream_close);
+ struct vy_slice_stream *stream = (struct vy_slice_stream *)virt_stream;
+ tuple_format_unref(stream->format);
+}
+
static const struct vy_stmt_stream_iface vy_slice_stream_iface = {
.start = vy_slice_stream_search,
.next = vy_slice_stream_next,
.stop = vy_slice_stream_stop,
- .close = NULL,
+ .close = vy_slice_stream_close,
};
void
@@ -2690,5 +2698,6 @@ vy_slice_stream_open(struct vy_slice_stream *stream, struct vy_slice *slice,
stream->slice = slice;
stream->cmp_def = cmp_def;
stream->format = format;
+ tuple_format_ref(format);
stream->is_primary = is_primary;
}
diff --git a/src/box/vy_scheduler.c b/src/box/vy_scheduler.c
index 91cf502b..437b95ac 100644
--- a/src/box/vy_scheduler.c
+++ b/src/box/vy_scheduler.c
@@ -1395,9 +1395,8 @@ vy_task_dump_new(struct vy_scheduler *scheduler, struct vy_worker *worker,
*/
struct vy_stmt_stream *wi;
bool is_last_level = (lsm->run_count == 0);
- wi = vy_write_iterator_new(task->cmp_def, lsm->disk_format,
- lsm->index_id == 0, is_last_level,
- scheduler->read_views, NULL);
+ wi = vy_write_iterator_new(task->cmp_def, lsm->index_id == 0,
+ is_last_level, scheduler->read_views, NULL);
if (wi == NULL)
goto err_wi;
rlist_foreach_entry(mem, &lsm->sealed, in_sealed) {
@@ -1670,9 +1669,8 @@ vy_task_compaction_new(struct vy_scheduler *scheduler, struct vy_worker *worker,
struct vy_stmt_stream *wi;
bool is_last_level = (range->compaction_priority == range->slice_count);
- wi = vy_write_iterator_new(task->cmp_def, lsm->disk_format,
- lsm->index_id == 0, is_last_level,
- scheduler->read_views,
+ wi = vy_write_iterator_new(task->cmp_def, lsm->index_id == 0,
+ is_last_level, scheduler->read_views,
lsm->index_id > 0 ? NULL :
&task->deferred_delete_handler);
if (wi == NULL)
@@ -1682,7 +1680,8 @@ vy_task_compaction_new(struct vy_scheduler *scheduler, struct vy_worker *worker,
int32_t dump_count = 0;
int n = range->compaction_priority;
rlist_foreach_entry(slice, &range->slices, in_range) {
- if (vy_write_iterator_new_slice(wi, slice) != 0)
+ if (vy_write_iterator_new_slice(wi, slice,
+ lsm->disk_format) != 0)
goto err_wi_sub;
new_run->dump_lsn = MAX(new_run->dump_lsn,
slice->run->dump_lsn);
diff --git a/src/box/vy_write_iterator.c b/src/box/vy_write_iterator.c
index 8988daa3..36e43bc9 100644
--- a/src/box/vy_write_iterator.c
+++ b/src/box/vy_write_iterator.c
@@ -168,8 +168,6 @@ struct vy_write_iterator {
heap_t src_heap;
/** Index key definition used to store statements on disk. */
struct key_def *cmp_def;
- /** Format to allocate new REPLACE and DELETE tuples from vy_run */
- struct tuple_format *format;
/* There is no LSM tree level older than the one we're writing to. */
bool is_last_level;
/**
@@ -339,9 +337,8 @@ static const struct vy_stmt_stream_iface vy_slice_stream_iface;
* @return the iterator or NULL on error (diag is set).
*/
struct vy_stmt_stream *
-vy_write_iterator_new(struct key_def *cmp_def, struct tuple_format *format,
- bool is_primary, bool is_last_level,
- struct rlist *read_views,
+vy_write_iterator_new(struct key_def *cmp_def, bool is_primary,
+ bool is_last_level, struct rlist *read_views,
struct vy_deferred_delete_handler *handler)
{
/*
@@ -378,8 +375,6 @@ vy_write_iterator_new(struct key_def *cmp_def, struct tuple_format *format,
vy_source_heap_create(&stream->src_heap);
rlist_create(&stream->src_list);
stream->cmp_def = cmp_def;
- stream->format = format;
- tuple_format_ref(stream->format);
stream->is_primary = is_primary;
stream->is_last_level = is_last_level;
stream->deferred_delete_handler = handler;
@@ -449,7 +444,6 @@ vy_write_iterator_close(struct vy_stmt_stream *vstream)
rlist_foreach_entry_safe(src, &stream->src_list, in_src_list, tmp)
vy_write_iterator_delete_src(stream, src);
vy_source_heap_destroy(&stream->src_heap);
- tuple_format_unref(stream->format);
free(stream);
}
@@ -474,14 +468,15 @@ vy_write_iterator_new_mem(struct vy_stmt_stream *vstream, struct vy_mem *mem)
*/
NODISCARD int
vy_write_iterator_new_slice(struct vy_stmt_stream *vstream,
- struct vy_slice *slice)
+ struct vy_slice *slice,
+ struct tuple_format *disk_format)
{
struct vy_write_iterator *stream = (struct vy_write_iterator *)vstream;
struct vy_write_src *src = vy_write_iterator_new_src(stream);
if (src == NULL)
return -1;
vy_slice_stream_open(&src->slice_stream, slice, stream->cmp_def,
- stream->format, stream->is_primary);
+ disk_format, stream->is_primary);
return 0;
}
@@ -927,11 +922,11 @@ vy_read_view_merge(struct vy_write_iterator *stream, struct tuple *hint,
* so as not to trigger optimization #5 on the next
* compaction.
*/
- uint32_t size;
- const char *data = tuple_data_range(rv->tuple, &size);
- struct tuple *copy = is_first_insert ?
- vy_stmt_new_insert(stream->format, data, data + size) :
- vy_stmt_new_replace(stream->format, data, data + size);
+ struct tuple *copy = vy_stmt_dup(rv->tuple);
+ if (is_first_insert)
+ vy_stmt_set_type(copy, IPROTO_INSERT);
+ else
+ vy_stmt_set_type(copy, IPROTO_REPLACE);
if (copy == NULL)
return -1;
vy_stmt_set_lsn(copy, vy_stmt_lsn(rv->tuple));
diff --git a/src/box/vy_write_iterator.h b/src/box/vy_write_iterator.h
index 4ae3815d..e217160e 100644
--- a/src/box/vy_write_iterator.h
+++ b/src/box/vy_write_iterator.h
@@ -239,7 +239,6 @@ struct vy_deferred_delete_handler {
* Open an empty write iterator. To add sources to the iterator
* use vy_write_iterator_add_* functions.
* @param cmp_def - key definition for tuple compare.
- * @param format - dormat to allocate new REPLACE and DELETE tuples from vy_run.
* @param LSM tree is_primary - set if this iterator is for a primary index.
* @param is_last_level - there is no older level than the one we're writing to.
* @param read_views - Opened read views.
@@ -249,9 +248,8 @@ struct vy_deferred_delete_handler {
* @return the iterator or NULL on error (diag is set).
*/
struct vy_stmt_stream *
-vy_write_iterator_new(struct key_def *cmp_def, struct tuple_format *format,
- bool is_primary, bool is_last_level,
- struct rlist *read_views,
+vy_write_iterator_new(struct key_def *cmp_def, bool is_primary,
+ bool is_last_level, struct rlist *read_views,
struct vy_deferred_delete_handler *handler);
/**
@@ -267,7 +265,8 @@ vy_write_iterator_new_mem(struct vy_stmt_stream *stream, struct vy_mem *mem);
*/
NODISCARD int
vy_write_iterator_new_slice(struct vy_stmt_stream *stream,
- struct vy_slice *slice);
+ struct vy_slice *slice,
+ struct tuple_format *disk_format);
#endif /* INCLUDES_TARANTOOL_BOX_VY_WRITE_STREAM_H */
diff --git a/test/unit/vy_point_lookup.c b/test/unit/vy_point_lookup.c
index 5f20d09b..38e9f403 100644
--- a/test/unit/vy_point_lookup.c
+++ b/test/unit/vy_point_lookup.c
@@ -191,9 +191,9 @@ test_basic()
tmpl_val.upsert_value = 8;
vy_mem_insert_template(run_mem, &tmpl_val);
}
- struct vy_stmt_stream *write_stream
- = vy_write_iterator_new(pk->cmp_def, pk->disk_format,
- true, true, &read_views, NULL);
+ struct vy_stmt_stream *write_stream;
+ write_stream = vy_write_iterator_new(pk->cmp_def, true, true,
+ &read_views, NULL);
vy_write_iterator_new_mem(write_stream, run_mem);
struct vy_run *run = vy_run_new(&run_env, 1);
isnt(run, NULL, "vy_run_new");
@@ -222,9 +222,8 @@ test_basic()
tmpl_val.upsert_value = 4;
vy_mem_insert_template(run_mem, &tmpl_val);
}
- write_stream
- = vy_write_iterator_new(pk->cmp_def, pk->disk_format,
- true, true, &read_views, NULL);
+ write_stream = vy_write_iterator_new(pk->cmp_def, true, true,
+ &read_views, NULL);
vy_write_iterator_new_mem(write_stream, run_mem);
run = vy_run_new(&run_env, 2);
isnt(run, NULL, "vy_run_new");
diff --git a/test/unit/vy_write_iterator.c b/test/unit/vy_write_iterator.c
index bb0eb8d3..ecbc6281 100644
--- a/test/unit/vy_write_iterator.c
+++ b/test/unit/vy_write_iterator.c
@@ -105,8 +105,7 @@ compare_write_iterator_results(const struct vy_stmt_template *content,
test_handler_create(&handler, mem->format);
struct vy_stmt_stream *wi;
- wi = vy_write_iterator_new(key_def, mem->format, is_primary,
- is_last_level, &rv_list,
+ wi = vy_write_iterator_new(key_def, is_primary, is_last_level, &rv_list,
is_primary ? &handler.base : NULL);
fail_if(wi == NULL);
fail_if(vy_write_iterator_new_mem(wi, mem) != 0);
--
2.11.0
^ permalink raw reply [flat|nested] 34+ messages in thread* [PATCH v2 11/14] vinyl: do not fill secondary tuples with nulls when decoded
2019-03-13 8:52 [PATCH v2 00/14] vinyl: do not fill secondary tuples with nulls Vladimir Davydov
` (9 preceding siblings ...)
2019-03-13 8:52 ` [PATCH v2 10/14] vinyl: zap vy_write_iterator->format Vladimir Davydov
@ 2019-03-13 8:52 ` Vladimir Davydov
2019-03-13 12:25 ` Konstantin Osipov
2019-03-13 8:52 ` [PATCH v2 12/14] vinyl: zap vy_stmt_new_surrogate_from_key Vladimir Davydov
` (3 subsequent siblings)
14 siblings, 1 reply; 34+ messages in thread
From: Vladimir Davydov @ 2019-03-13 8:52 UTC (permalink / raw)
To: kostja; +Cc: tarantool-patches
In contrast to a primary index, which stores full tuples, secondary
indexes only store extended (secondary + primary) keys on disk. To make
them look like tuples, we fill missing fields with nulls (aka tuple
surrogate). This isn't going to work nicely with multikey indexes
though: how would you make a surrogate array from a key? We could
special-case multikey index handling, but that would look cumbersome.
So this patch removes nulls from secondary tuples restored from disk
altogether. To achieve that, it's enough to use key_format for them -
then the comparators will detect that it's actually a key, not a tuple
and use the appropriate primitive.
---
src/box/key_def.c | 36 +++++++++++++++++++++++++++++++++++
src/box/key_def.h | 14 ++++++++++++++
src/box/vinyl.c | 46 +++++++++++++++++++++++++++++++++------------
src/box/vy_lsm.c | 30 ++++++++++++++++++++---------
src/box/vy_lsm.h | 13 +++++++++----
src/box/vy_run.c | 31 ++++++++++++++++++++----------
src/box/vy_stmt.c | 36 +++++++++++++++++------------------
test/unit/vy_point_lookup.c | 2 +-
8 files changed, 154 insertions(+), 54 deletions(-)
diff --git a/src/box/key_def.c b/src/box/key_def.c
index d4c979aa..c8993a06 100644
--- a/src/box/key_def.c
+++ b/src/box/key_def.c
@@ -709,6 +709,42 @@ key_def_merge(const struct key_def *first, const struct key_def *second)
return new_def;
}
+struct key_def *
+key_def_extract(const struct key_def *cmp_def, const struct key_def *pk_def,
+ struct region *region)
+{
+ struct key_def *extracted_def = NULL;
+ size_t region_svp = region_used(region);
+
+ /* First, dump primary key parts as is. */
+ struct key_part_def *parts = region_alloc(region,
+ pk_def->part_count * sizeof(*parts));
+ if (parts == NULL) {
+ diag_set(OutOfMemory, pk_def->part_count * sizeof(*parts),
+ "region", "key def parts");
+ goto out;
+ }
+ if (key_def_dump_parts(pk_def, parts, region) != 0)
+ goto out;
+ /*
+ * Second, update field numbers to match the primary key
+ * parts in a secondary key.
+ */
+ for (uint32_t i = 0; i < pk_def->part_count; i++) {
+ const struct key_part *part = key_def_find(cmp_def,
+ &pk_def->parts[i]);
+ assert(part != NULL);
+ parts[i].fieldno = part - cmp_def->parts;
+ parts[i].path = NULL;
+ }
+
+ /* Finally, allocate the new key definition. */
+ extracted_def = key_def_new(parts, pk_def->part_count);
+out:
+ region_truncate(region, region_svp);
+ return extracted_def;
+}
+
int
key_validate_parts(const struct key_def *key_def, const char *key,
uint32_t part_count, bool allow_nullable)
diff --git a/src/box/key_def.h b/src/box/key_def.h
index e3a34ce1..21119a83 100644
--- a/src/box/key_def.h
+++ b/src/box/key_def.h
@@ -375,6 +375,20 @@ key_def_contains(const struct key_def *first, const struct key_def *second);
struct key_def *
key_def_merge(const struct key_def *first, const struct key_def *second);
+/**
+ * Create a key definition suitable for extracting primary key
+ * parts from an extended secondary key.
+ * @param cmp_def Extended secondary key definition
+ * (must include primary key parts).
+ * @param pk_def Primary key definition.
+ * @param region Region used for temporary allocations.
+ * @retval not NULL Pointer to the extracted key definition.
+ * @retval NULL Memory allocation error.
+ */
+struct key_def *
+key_def_extract(const struct key_def *cmp_def, const struct key_def *pk_def,
+ struct region *region);
+
/*
* Check that parts of the key match with the key definition.
* @param key_def Key definition.
diff --git a/src/box/vinyl.c b/src/box/vinyl.c
index ced0efe5..e9a4ae0d 100644
--- a/src/box/vinyl.c
+++ b/src/box/vinyl.c
@@ -719,10 +719,9 @@ vinyl_space_create_index(struct space *space, struct index_def *index_def)
pk = vy_lsm(space_index(space, 0));
assert(pk != NULL);
}
- struct vy_lsm *lsm = vy_lsm_new(&env->lsm_env, &env->stmt_env,
- &env->cache_env, &env->mem_env,
- index_def, space->format, pk,
- space_group_id(space));
+ struct vy_lsm *lsm = vy_lsm_new(&env->lsm_env, &env->cache_env,
+ &env->mem_env, index_def, space->format,
+ pk, space_group_id(space));
if (lsm == NULL) {
free(index);
return NULL;
@@ -1301,13 +1300,34 @@ 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)
{
+ int rc = 0;
assert(lsm->index_id > 0);
- if (vy_point_lookup(lsm->pk, tx, rv, tuple, result) != 0)
- return -1;
+ /*
+ * Lookup the full tuple by a secondary statement.
+ * There are two cases: the secondary statement may be
+ * a key, in which case we need to extract the primary
+ * key parts from it; or it may be a full tuple, which
+ * we may pass it immediately to the iterator.
+ */
+ struct tuple *key;
+ if (vy_stmt_is_key(tuple)) {
+ key = vy_stmt_extract_key(tuple, lsm->pk_in_cmp_def,
+ lsm->env->key_format);
+ if (key == NULL)
+ return -1;
+ } else {
+ key = tuple;
+ tuple_ref(key);
+ }
+
+ if (vy_point_lookup(lsm->pk, tx, rv, key, result) != 0) {
+ rc = -1;
+ goto out;
+ }
if (*result == NULL ||
- vy_stmt_compare(*result, tuple, lsm->key_def) != 0) {
+ vy_stmt_compare(*result, tuple, lsm->cmp_def) != 0) {
/*
* If a tuple read from a secondary index doesn't
* match the tuple corresponding to it in the
@@ -1327,7 +1347,7 @@ vy_get_by_secondary_tuple(struct vy_lsm *lsm, struct vy_tx *tx,
* the tuple cache implementation.
*/
vy_cache_on_write(&lsm->cache, tuple, NULL);
- return 0;
+ goto out;
}
/*
@@ -1340,13 +1360,15 @@ vy_get_by_secondary_tuple(struct vy_lsm *lsm, struct vy_tx *tx,
*/
if (tx != NULL && vy_tx_track_point(tx, lsm->pk, *result) != 0) {
tuple_unref(*result);
- return -1;
+ rc = -1;
+ goto out;
}
if ((*rv)->vlsn == INT64_MAX)
- vy_cache_add(&lsm->pk->cache, *result, NULL, tuple, ITER_EQ);
-
- return 0;
+ vy_cache_add(&lsm->pk->cache, *result, NULL, key, ITER_EQ);
+out:
+ tuple_unref(key);
+ return rc;
}
/**
diff --git a/src/box/vy_lsm.c b/src/box/vy_lsm.c
index 2dc8f639..28cd487c 100644
--- a/src/box/vy_lsm.c
+++ b/src/box/vy_lsm.c
@@ -118,10 +118,9 @@ vy_lsm_mem_tree_size(struct vy_lsm *lsm)
}
struct vy_lsm *
-vy_lsm_new(struct vy_lsm_env *lsm_env, struct vy_stmt_env *stmt_env,
- struct vy_cache_env *cache_env, struct vy_mem_env *mem_env,
- struct index_def *index_def, struct tuple_format *format,
- struct vy_lsm *pk, uint32_t group_id)
+vy_lsm_new(struct vy_lsm_env *lsm_env, struct vy_cache_env *cache_env,
+ struct vy_mem_env *mem_env, struct index_def *index_def,
+ struct tuple_format *format, struct vy_lsm *pk, uint32_t group_id)
{
static int64_t run_buckets[] = {
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 15, 20, 25, 50, 100,
@@ -156,10 +155,19 @@ vy_lsm_new(struct vy_lsm_env *lsm_env, struct vy_stmt_env *stmt_env,
*/
lsm->disk_format = format;
} else {
- lsm->disk_format = vy_stmt_format_new(stmt_env, &cmp_def, 1,
- NULL, 0, 0, NULL);
- if (lsm->disk_format == NULL)
- goto fail_format;
+ /*
+ * To save disk space, we do not store full tuples
+ * in secondary index runs. Instead we only store
+ * extended keys (i.e. keys consisting of secondary
+ * and primary index parts). This is enough to look
+ * up a full tuple in the primary index.
+ */
+ lsm->disk_format = lsm_env->key_format;
+
+ lsm->pk_in_cmp_def = key_def_extract(lsm->cmp_def, pk->key_def,
+ &fiber()->gc);
+ if (lsm->pk_in_cmp_def == NULL)
+ goto fail_pk_in_cmp_def;
}
tuple_format_ref(lsm->disk_format);
@@ -208,7 +216,9 @@ fail_run_hist:
vy_lsm_stat_destroy(&lsm->stat);
fail_stat:
tuple_format_unref(lsm->disk_format);
-fail_format:
+ if (lsm->pk_in_cmp_def != NULL)
+ key_def_delete(lsm->pk_in_cmp_def);
+fail_pk_in_cmp_def:
key_def_delete(cmp_def);
fail_cmp_def:
key_def_delete(key_def);
@@ -262,6 +272,8 @@ vy_lsm_delete(struct vy_lsm *lsm)
tuple_format_unref(lsm->disk_format);
key_def_delete(lsm->cmp_def);
key_def_delete(lsm->key_def);
+ if (lsm->pk_in_cmp_def != NULL)
+ key_def_delete(lsm->pk_in_cmp_def);
histogram_delete(lsm->run_hist);
vy_lsm_stat_destroy(&lsm->stat);
vy_cache_destroy(&lsm->cache);
diff --git a/src/box/vy_lsm.h b/src/box/vy_lsm.h
index b94e7a43..e969e45c 100644
--- a/src/box/vy_lsm.h
+++ b/src/box/vy_lsm.h
@@ -200,6 +200,12 @@ struct vy_lsm {
/** Key definition passed by the user. */
struct key_def *key_def;
/**
+ * Key definition to extract primary key parts from
+ * a secondary key. NULL if this LSM tree corresponds
+ * to a primary index.
+ */
+ struct key_def *pk_in_cmp_def;
+ /**
* If the following flag is set, the index this LSM tree
* is created for is unique and it must be checked for
* duplicates on INSERT. Otherwise, the check can be skipped,
@@ -333,10 +339,9 @@ vy_lsm_mem_tree_size(struct vy_lsm *lsm);
/** Allocate a new LSM tree object. */
struct vy_lsm *
-vy_lsm_new(struct vy_lsm_env *lsm_env, struct vy_stmt_env *stmt_env,
- struct vy_cache_env *cache_env, struct vy_mem_env *mem_env,
- struct index_def *index_def, struct tuple_format *format,
- struct vy_lsm *pk, uint32_t group_id);
+vy_lsm_new(struct vy_lsm_env *lsm_env, struct vy_cache_env *cache_env,
+ struct vy_mem_env *mem_env, struct index_def *index_def,
+ struct tuple_format *format, struct vy_lsm *pk, uint32_t group_id);
/** Free an LSM tree object. */
void
diff --git a/src/box/vy_run.c b/src/box/vy_run.c
index 76b2f94a..928ca57f 100644
--- a/src/box/vy_run.c
+++ b/src/box/vy_run.c
@@ -2139,7 +2139,8 @@ vy_run_writer_start_page(struct vy_run_writer *writer,
if (run->info.page_count >= writer->page_info_capacity &&
vy_run_alloc_page_info(run, &writer->page_info_capacity) != 0)
return -1;
- const char *key = tuple_extract_key(first_stmt, writer->cmp_def, NULL);
+ const char *key = vy_stmt_is_key(first_stmt) ? tuple_data(first_stmt) :
+ tuple_extract_key(first_stmt, writer->cmp_def, NULL);
if (key == NULL)
return -1;
if (run->info.page_count == 0) {
@@ -2289,7 +2290,9 @@ vy_run_writer_commit(struct vy_run_writer *writer)
}
assert(writer->last_stmt != NULL);
- const char *key = tuple_extract_key(writer->last_stmt,
+ const char *key = vy_stmt_is_key(writer->last_stmt) ?
+ tuple_data(writer->last_stmt) :
+ tuple_extract_key(writer->last_stmt,
writer->cmp_def, NULL);
if (key == NULL)
goto out;
@@ -2360,6 +2363,7 @@ vy_run_rebuild_index(struct vy_run *run, const char *dir,
int64_t max_lsn = 0;
int64_t min_lsn = INT64_MAX;
struct tuple *prev_tuple = NULL;
+ char *page_min_key = NULL;
struct tuple_bloom_builder *bloom_builder = NULL;
if (opts->bloom_fpr < 1) {
@@ -2377,7 +2381,6 @@ vy_run_rebuild_index(struct vy_run *run, const char *dir,
if (run->info.page_count == page_info_capacity &&
vy_run_alloc_page_info(run, &page_info_capacity) != 0)
goto close_err;
- const char *page_min_key = NULL;
uint32_t page_row_count = 0;
uint64_t page_row_index_offset = 0;
uint64_t row_offset = xlog_cursor_tx_pos(&cursor);
@@ -2400,7 +2403,8 @@ vy_run_rebuild_index(struct vy_run *run, const char *dir,
tuple_unref(tuple);
goto close_err;
}
- key = tuple_extract_key(tuple, cmp_def, NULL);
+ key = vy_stmt_is_key(tuple) ? tuple_data(tuple) :
+ tuple_extract_key(tuple, cmp_def, NULL);
if (prev_tuple != NULL)
tuple_unref(prev_tuple);
prev_tuple = tuple;
@@ -2411,8 +2415,11 @@ vy_run_rebuild_index(struct vy_run *run, const char *dir,
if (run->info.min_key == NULL)
goto close_err;
}
- if (page_min_key == NULL)
- page_min_key = key;
+ if (page_min_key == NULL) {
+ page_min_key = vy_key_dup(key);
+ if (page_min_key == NULL)
+ goto close_err;
+ }
if (xrow.lsn > max_lsn)
max_lsn = xrow.lsn;
if (xrow.lsn < min_lsn)
@@ -2429,11 +2436,9 @@ vy_run_rebuild_index(struct vy_run *run, const char *dir,
info->row_index_offset = page_row_index_offset;
++run->info.page_count;
vy_run_acct_page(run, info);
- }
- if (prev_tuple != NULL) {
- tuple_unref(prev_tuple);
- prev_tuple = NULL;
+ free(page_min_key);
+ page_min_key = NULL;
}
if (key != NULL) {
@@ -2444,6 +2449,10 @@ vy_run_rebuild_index(struct vy_run *run, const char *dir,
run->info.max_lsn = max_lsn;
run->info.min_lsn = min_lsn;
+ if (prev_tuple != NULL) {
+ tuple_unref(prev_tuple);
+ prev_tuple = NULL;
+ }
region_truncate(region, mem_used);
run->fd = cursor.fd;
xlog_cursor_close(&cursor, true);
@@ -2473,6 +2482,8 @@ close_err:
region_truncate(region, mem_used);
if (prev_tuple != NULL)
tuple_unref(prev_tuple);
+ if (page_min_key != NULL)
+ free(page_min_key);
if (bloom_builder != NULL)
tuple_bloom_builder_delete(bloom_builder);
if (xlog_cursor_is_open(&cursor))
diff --git a/src/box/vy_stmt.c b/src/box/vy_stmt.c
index 229f8b41..fd7850cc 100644
--- a/src/box/vy_stmt.c
+++ b/src/box/vy_stmt.c
@@ -748,6 +748,8 @@ int
vy_stmt_encode_primary(const struct tuple *value, struct key_def *key_def,
uint32_t space_id, struct xrow_header *xrow)
{
+ assert(!vy_stmt_is_key(value));
+
memset(xrow, 0, sizeof(*xrow));
enum iproto_type type = vy_stmt_type(value);
xrow->type = type;
@@ -804,7 +806,9 @@ vy_stmt_encode_secondary(const struct tuple *value, struct key_def *cmp_def,
memset(&request, 0, sizeof(request));
request.type = type;
uint32_t size;
- const char *extracted = tuple_extract_key(value, cmp_def, &size);
+ const char *extracted = vy_stmt_is_key(value) ?
+ tuple_data_range(value, &size) :
+ tuple_extract_key(value, cmp_def, &size);
if (extracted == NULL)
return -1;
if (type == IPROTO_REPLACE || type == IPROTO_INSERT) {
@@ -834,27 +838,23 @@ vy_stmt_decode(struct xrow_header *xrow, const struct key_def *key_def,
if (xrow_decode_dml(xrow, &request, key_map) != 0)
return NULL;
struct tuple *stmt = NULL;
- const char *key;
- (void) key;
struct iovec ops;
switch (request.type) {
case IPROTO_DELETE:
- /* extract key */
- stmt = vy_stmt_new_surrogate_from_key(request.key,
- IPROTO_DELETE,
- key_def, format);
- break;
- case IPROTO_INSERT:
- case IPROTO_REPLACE:
- if (is_primary) {
- stmt = vy_stmt_new_with_ops(format, request.tuple,
- request.tuple_end,
- NULL, 0, request.type);
- } else {
- stmt = vy_stmt_new_surrogate_from_key(request.tuple,
- request.type,
+ if (is_primary)
+ stmt = vy_stmt_new_surrogate_from_key(request.key,
+ IPROTO_DELETE,
key_def, format);
- }
+ else
+ stmt = vy_stmt_new_with_ops(format, request.key,
+ request.key_end,
+ NULL, 0, IPROTO_DELETE);
+ break;
+ case IPROTO_INSERT:
+ case IPROTO_REPLACE:
+ stmt = vy_stmt_new_with_ops(format, request.tuple,
+ request.tuple_end,
+ NULL, 0, request.type);
break;
case IPROTO_UPSERT:
ops.iov_base = (char *)request.ops;
diff --git a/test/unit/vy_point_lookup.c b/test/unit/vy_point_lookup.c
index 38e9f403..f3cd84d4 100644
--- a/test/unit/vy_point_lookup.c
+++ b/test/unit/vy_point_lookup.c
@@ -94,7 +94,7 @@ test_basic()
index_def_new(512, 0, "primary", sizeof("primary") - 1, TREE,
&index_opts, key_def, NULL);
- struct vy_lsm *pk = vy_lsm_new(&lsm_env, &stmt_env, &cache_env, &mem_env,
+ struct vy_lsm *pk = vy_lsm_new(&lsm_env, &cache_env, &mem_env,
index_def, format, NULL, 0);
isnt(pk, NULL, "lsm is not NULL")
--
2.11.0
^ permalink raw reply [flat|nested] 34+ messages in thread* Re: [PATCH v2 11/14] vinyl: do not fill secondary tuples with nulls when decoded
2019-03-13 8:52 ` [PATCH v2 11/14] vinyl: do not fill secondary tuples with nulls when decoded Vladimir Davydov
@ 2019-03-13 12:25 ` Konstantin Osipov
2019-03-13 12:45 ` Vladimir Davydov
0 siblings, 1 reply; 34+ messages in thread
From: Konstantin Osipov @ 2019-03-13 12:25 UTC (permalink / raw)
To: Vladimir Davydov; +Cc: tarantool-patches
* Vladimir Davydov <vdavydov.dev@gmail.com> [19/03/13 11:58]:
> +struct key_def *
> +key_def_extract(const struct key_def *cmp_def, const struct key_def *pk_def,
> + struct region *region)
The name is not very telling :(
It also looks like a standalone function, not a key_def method. So
we could name it build_pk_def_for_cmp_def or
find_primary_key_parts() or something like it.
> if (lsm == NULL) {
> free(index);
> return NULL;
> @@ -1301,13 +1300,34 @@ 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)
> {
> + int rc = 0;
> assert(lsm->index_id > 0);
>
> - if (vy_point_lookup(lsm->pk, tx, rv, tuple, result) != 0)
> - return -1;
> + /*
> + * Lookup the full tuple by a secondary statement.
> + * There are two cases: the secondary statement may be
> + * a key, in which case we need to extract the primary
Please explain:
may be a key, if we got this tuple from disk ... or may be a full
tuple if we got this tuple from the tuple cache or level 0,
> + * key parts from it; or it may be a full tuple, which
> + * we may pass it immediately to the iterator.
> + */
> + struct tuple *key;
> + /*
> + * To save disk space, we do not store full tuples
> + * in secondary index runs. Instead we only store
> + * extended keys (i.e. keys consisting of secondary
> + * and primary index parts). This is enough to look
> + * up a full tuple in the primary index.
> + */
> + lsm->disk_format = lsm_env->key_format;
Nice.
> +
> + lsm->pk_in_cmp_def = key_def_extract(lsm->cmp_def, pk->key_def,
Oh. Shall we call the function find_pk_in_cmp_def()?
> + if (is_primary)
> + stmt = vy_stmt_new_surrogate_from_key(request.key,
Shouldn't this be renamed?
> + IPROTO_DELETE,
> key_def, format);
--
Konstantin Osipov, Moscow, Russia, +7 903 626 22 32
http://tarantool.io - www.twitter.com/kostja_osipov
^ permalink raw reply [flat|nested] 34+ messages in thread* Re: [PATCH v2 11/14] vinyl: do not fill secondary tuples with nulls when decoded
2019-03-13 12:25 ` Konstantin Osipov
@ 2019-03-13 12:45 ` Vladimir Davydov
2019-03-13 12:56 ` Konstantin Osipov
0 siblings, 1 reply; 34+ messages in thread
From: Vladimir Davydov @ 2019-03-13 12:45 UTC (permalink / raw)
To: Konstantin Osipov; +Cc: tarantool-patches
On Wed, Mar 13, 2019 at 03:25:59PM +0300, Konstantin Osipov wrote:
> * Vladimir Davydov <vdavydov.dev@gmail.com> [19/03/13 11:58]:
> > +struct key_def *
> > +key_def_extract(const struct key_def *cmp_def, const struct key_def *pk_def,
> > + struct region *region)
>
> The name is not very telling :(
>
> It also looks like a standalone function, not a key_def method. So
> we could name it build_pk_def_for_cmp_def or
> find_primary_key_parts() or something like it.
Well, key_def_merge is also not a key_def method in this regard.
I think of key_def_ more like as of a namespace.
>
> > if (lsm == NULL) {
> > free(index);
> > return NULL;
> > @@ -1301,13 +1300,34 @@ 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)
> > {
> > + int rc = 0;
> > assert(lsm->index_id > 0);
> >
> > - if (vy_point_lookup(lsm->pk, tx, rv, tuple, result) != 0)
> > - return -1;
> > + /*
> > + * Lookup the full tuple by a secondary statement.
> > + * There are two cases: the secondary statement may be
> > + * a key, in which case we need to extract the primary
> Please explain:
>
> may be a key, if we got this tuple from disk ... or may be a full
> tuple if we got this tuple from the tuple cache or level 0,
Okay.
>
> > + * key parts from it; or it may be a full tuple, which
> > + * we may pass it immediately to the iterator.
> > + */
> > + struct tuple *key;
> > + /*
> > + * To save disk space, we do not store full tuples
> > + * in secondary index runs. Instead we only store
> > + * extended keys (i.e. keys consisting of secondary
> > + * and primary index parts). This is enough to look
> > + * up a full tuple in the primary index.
> > + */
> > + lsm->disk_format = lsm_env->key_format;
>
> Nice.
>
> > +
> > + lsm->pk_in_cmp_def = key_def_extract(lsm->cmp_def, pk->key_def,
>
> Oh. Shall we call the function find_pk_in_cmp_def()?
The name's fine. Well, at least one can figure out what the function
does, but I don't quite like that there's no key_def_ prefix.
> > + if (is_primary)
> > + stmt = vy_stmt_new_surrogate_from_key(request.key,
>
> Shouldn't this be renamed?
The next patch removes this function altogether.
^ permalink raw reply [flat|nested] 34+ messages in thread* Re: [PATCH v2 11/14] vinyl: do not fill secondary tuples with nulls when decoded
2019-03-13 12:45 ` Vladimir Davydov
@ 2019-03-13 12:56 ` Konstantin Osipov
0 siblings, 0 replies; 34+ messages in thread
From: Konstantin Osipov @ 2019-03-13 12:56 UTC (permalink / raw)
To: Vladimir Davydov; +Cc: tarantool-patches
* Vladimir Davydov <vdavydov.dev@gmail.com> [19/03/13 15:47]:
> > Oh. Shall we call the function find_pk_in_cmp_def()?
>
> The name's fine. Well, at least one can figure out what the function
> does, but I don't quite like that there's no key_def_ prefix.
OK, let it be key_def_find_pk_in_cmp_def().
--
Konstantin Osipov, Moscow, Russia, +7 903 626 22 32
http://tarantool.io - www.twitter.com/kostja_osipov
^ permalink raw reply [flat|nested] 34+ messages in thread
* [PATCH v2 12/14] vinyl: zap vy_stmt_new_surrogate_from_key
2019-03-13 8:52 [PATCH v2 00/14] vinyl: do not fill secondary tuples with nulls Vladimir Davydov
` (10 preceding siblings ...)
2019-03-13 8:52 ` [PATCH v2 11/14] vinyl: do not fill secondary tuples with nulls when decoded Vladimir Davydov
@ 2019-03-13 8:52 ` Vladimir Davydov
2019-03-13 12:27 ` Konstantin Osipov
2019-03-13 8:52 ` [PATCH v2 13/14] vinyl: don't use vy_stmt_new_surrogate_delete if not necessary Vladimir Davydov
` (2 subsequent siblings)
14 siblings, 1 reply; 34+ messages in thread
From: Vladimir Davydov @ 2019-03-13 8:52 UTC (permalink / raw)
To: kostja; +Cc: tarantool-patches
This heavy function isn't needed anymore, as we can now insert key
statements into the memory level.
---
src/box/vinyl.c | 4 +-
src/box/vy_lsm.c | 3 +-
src/box/vy_mem.c | 3 +-
src/box/vy_point_lookup.c | 2 +-
src/box/vy_read_iterator.c | 3 +-
src/box/vy_run.c | 31 +++-------
src/box/vy_run.h | 9 +--
src/box/vy_stmt.c | 147 +++++---------------------------------------
src/box/vy_stmt.h | 38 +++++-------
src/box/vy_write_iterator.c | 2 +-
test/vinyl/stat.result | 2 +-
11 files changed, 53 insertions(+), 191 deletions(-)
diff --git a/src/box/vinyl.c b/src/box/vinyl.c
index e9a4ae0d..f2d9ab55 100644
--- a/src/box/vinyl.c
+++ b/src/box/vinyl.c
@@ -1719,8 +1719,8 @@ vy_delete(struct vy_env *env, struct vy_tx *tx, struct txn_stmt *stmt,
}
} else {
assert(lsm->index_id == 0);
- delete = vy_stmt_new_surrogate_delete_from_key(request->key,
- pk->key_def, pk->mem_format);
+ delete = vy_stmt_new_delete(pk->env->key_format,
+ request->key, request->key_end);
if (delete == NULL)
return -1;
if (space->index_count > 1)
diff --git a/src/box/vy_lsm.c b/src/box/vy_lsm.c
index 28cd487c..a5e92887 100644
--- a/src/box/vy_lsm.c
+++ b/src/box/vy_lsm.c
@@ -898,7 +898,8 @@ vy_lsm_set(struct vy_lsm *lsm, struct vy_mem *mem,
lsm->stat.memory.count.bytes += tuple_size(stmt);
/* Abort transaction if format was changed by DDL */
- if (format_id != tuple_format_id(mem->format)) {
+ if (!vy_stmt_is_key(stmt) &&
+ format_id != tuple_format_id(mem->format)) {
diag_set(ClientError, ER_TRANSACTION_CONFLICT);
return -1;
}
diff --git a/src/box/vy_mem.c b/src/box/vy_mem.c
index c47a3c36..7fa90cbd 100644
--- a/src/box/vy_mem.c
+++ b/src/box/vy_mem.c
@@ -215,7 +215,8 @@ vy_mem_insert(struct vy_mem *mem, const struct tuple *stmt)
{
assert(vy_stmt_type(stmt) != IPROTO_UPSERT);
/* Check if the statement can be inserted in the vy_mem. */
- assert(stmt->format_id == tuple_format_id(mem->format));
+ assert(vy_stmt_is_key(stmt) ||
+ stmt->format_id == tuple_format_id(mem->format));
/* The statement must be from a lsregion. */
assert(!vy_stmt_is_refable(stmt));
size_t size = tuple_size(stmt);
diff --git a/src/box/vy_point_lookup.c b/src/box/vy_point_lookup.c
index 51226ce8..9f7796eb 100644
--- a/src/box/vy_point_lookup.c
+++ b/src/box/vy_point_lookup.c
@@ -144,7 +144,7 @@ vy_point_lookup_scan_slice(struct vy_lsm *lsm, struct vy_slice *slice,
struct vy_run_iterator run_itr;
vy_run_iterator_open(&run_itr, &lsm->stat.disk.iterator, slice,
ITER_EQ, key, rv, lsm->cmp_def, lsm->key_def,
- lsm->disk_format, lsm->index_id == 0);
+ lsm->disk_format);
struct vy_history slice_history;
vy_history_create(&slice_history, &lsm->env->history_node_pool);
int rc = vy_run_iterator_next(&run_itr, &slice_history);
diff --git a/src/box/vy_read_iterator.c b/src/box/vy_read_iterator.c
index cc884bec..2864a280 100644
--- a/src/box/vy_read_iterator.c
+++ b/src/box/vy_read_iterator.c
@@ -622,8 +622,7 @@ vy_read_iterator_add_disk(struct vy_read_iterator *itr)
&lsm->stat.disk.iterator, slice,
iterator_type, itr->key,
itr->read_view, lsm->cmp_def,
- lsm->key_def, lsm->disk_format,
- lsm->index_id == 0);
+ lsm->key_def, lsm->disk_format);
}
}
diff --git a/src/box/vy_run.c b/src/box/vy_run.c
index 928ca57f..699941a8 100644
--- a/src/box/vy_run.c
+++ b/src/box/vy_run.c
@@ -707,22 +707,19 @@ vy_page_xrow(struct vy_page *page, uint32_t stmt_no,
* Read raw stmt data from the page
* @param page Page.
* @param stmt_no Statement position in the page.
- * @param cmp_def Key definition, including primary key parts.
* @param format Format for REPLACE/DELETE tuples.
- * @param is_primary True if the index is primary.
*
* @retval not NULL Statement read from page.
* @retval NULL Memory error.
*/
static struct tuple *
vy_page_stmt(struct vy_page *page, uint32_t stmt_no,
- const struct key_def *cmp_def, struct tuple_format *format,
- bool is_primary)
+ struct tuple_format *format)
{
struct xrow_header xrow;
if (vy_page_xrow(page, stmt_no, &xrow) != 0)
return NULL;
- return vy_stmt_decode(&xrow, cmp_def, format, is_primary);
+ return vy_stmt_decode(&xrow, format);
}
/**
@@ -1025,8 +1022,7 @@ vy_run_iterator_read(struct vy_run_iterator *itr,
int rc = vy_run_iterator_load_page(itr, pos.page_no, &page);
if (rc != 0)
return rc;
- *stmt = vy_page_stmt(page, pos.pos_in_page, itr->cmp_def,
- itr->format, itr->is_primary);
+ *stmt = vy_page_stmt(page, pos.pos_in_page, itr->format);
if (*stmt == NULL)
return -1;
return 0;
@@ -1052,9 +1048,7 @@ vy_run_iterator_search_in_page(struct vy_run_iterator *itr,
iterator_type == ITER_LE ? -1 : 0);
while (beg != end) {
uint32_t mid = beg + (end - beg) / 2;
- struct tuple *fnd_key = vy_page_stmt(page, mid, itr->cmp_def,
- itr->format,
- itr->is_primary);
+ struct tuple *fnd_key = vy_page_stmt(page, mid, itr->format);
if (fnd_key == NULL)
return end;
int cmp = vy_stmt_compare(fnd_key, key, itr->cmp_def);
@@ -1402,14 +1396,12 @@ vy_run_iterator_open(struct vy_run_iterator *itr,
struct vy_slice *slice, enum iterator_type iterator_type,
const struct tuple *key, const struct vy_read_view **rv,
struct key_def *cmp_def, struct key_def *key_def,
- struct tuple_format *format,
- bool is_primary)
+ struct tuple_format *format)
{
itr->stat = stat;
itr->cmp_def = cmp_def;
itr->key_def = key_def;
itr->format = format;
- itr->is_primary = is_primary;
itr->slice = slice;
itr->iterator_type = iterator_type;
@@ -2393,8 +2385,7 @@ vy_run_rebuild_index(struct vy_run *run, const char *dir,
continue;
}
++page_row_count;
- struct tuple *tuple = vy_stmt_decode(&xrow, cmp_def,
- format, iid == 0);
+ struct tuple *tuple = vy_stmt_decode(&xrow, format);
if (tuple == NULL)
goto close_err;
if (bloom_builder != NULL &&
@@ -2574,8 +2565,7 @@ vy_slice_stream_search(struct vy_stmt_stream *virt_stream)
while (beg != end) {
uint32_t mid = beg + (end - beg) / 2;
struct tuple *fnd_key = vy_page_stmt(stream->page, mid,
- stream->cmp_def, stream->format,
- stream->is_primary);
+ stream->format);
if (fnd_key == NULL)
return -1;
int cmp = vy_stmt_compare(fnd_key, stream->slice->begin,
@@ -2622,8 +2612,7 @@ vy_slice_stream_next(struct vy_stmt_stream *virt_stream, struct tuple **ret)
/* Read current tuple from the page */
struct tuple *tuple = vy_page_stmt(stream->page, stream->pos_in_page,
- stream->cmp_def, stream->format,
- stream->is_primary);
+ stream->format);
if (tuple == NULL) /* Read or memory error */
return -1;
@@ -2696,8 +2685,7 @@ static const struct vy_stmt_stream_iface vy_slice_stream_iface = {
void
vy_slice_stream_open(struct vy_slice_stream *stream, struct vy_slice *slice,
- struct key_def *cmp_def, struct tuple_format *format,
- bool is_primary)
+ struct key_def *cmp_def, struct tuple_format *format)
{
stream->base.iface = &vy_slice_stream_iface;
@@ -2710,5 +2698,4 @@ vy_slice_stream_open(struct vy_slice_stream *stream, struct vy_slice *slice,
stream->cmp_def = cmp_def;
stream->format = format;
tuple_format_ref(format);
- stream->is_primary = is_primary;
}
diff --git a/src/box/vy_run.h b/src/box/vy_run.h
index 18ca1729..beb87b78 100644
--- a/src/box/vy_run.h
+++ b/src/box/vy_run.h
@@ -248,8 +248,6 @@ struct vy_run_iterator {
* pages.
*/
struct tuple_format *format;
- /** Set if this iterator is for a primary index. */
- bool is_primary;
/** The run slice to iterate. */
struct vy_slice *slice;
@@ -523,7 +521,7 @@ vy_run_iterator_open(struct vy_run_iterator *itr,
struct vy_slice *slice, enum iterator_type iterator_type,
const struct tuple *key, const struct vy_read_view **rv,
struct key_def *cmp_def, struct key_def *key_def,
- struct tuple_format *format, bool is_primary);
+ struct tuple_format *format);
/**
* Advance a run iterator to the next key.
@@ -575,8 +573,6 @@ struct vy_slice_stream {
struct key_def *cmp_def;
/** Format for allocating REPLACE and DELETE tuples read from pages. */
struct tuple_format *format;
- /** Set if this iterator is for a primary index. */
- bool is_primary;
};
/**
@@ -584,8 +580,7 @@ struct vy_slice_stream {
*/
void
vy_slice_stream_open(struct vy_slice_stream *stream, struct vy_slice *slice,
- struct key_def *cmp_def, struct tuple_format *format,
- bool is_primary);
+ struct key_def *cmp_def, struct tuple_format *format);
/**
* Run_writer fills a created run with statements one by one,
diff --git a/src/box/vy_stmt.c b/src/box/vy_stmt.c
index fd7850cc..2e26e843 100644
--- a/src/box/vy_stmt.c
+++ b/src/box/vy_stmt.c
@@ -371,6 +371,14 @@ vy_stmt_new_insert(struct tuple_format *format, const char *tuple_begin,
}
struct tuple *
+vy_stmt_new_delete(struct tuple_format *format, const char *tuple_begin,
+ const char *tuple_end)
+{
+ return vy_stmt_new_with_ops(format, tuple_begin, tuple_end,
+ NULL, 0, IPROTO_DELETE);
+}
+
+struct tuple *
vy_stmt_replace_from_upsert(const struct tuple *upsert)
{
assert(vy_stmt_type(upsert) == IPROTO_UPSERT);
@@ -393,122 +401,6 @@ vy_stmt_replace_from_upsert(const struct tuple *upsert)
return replace;
}
-static struct tuple *
-vy_stmt_new_surrogate_from_key(const char *key, enum iproto_type type,
- const struct key_def *cmp_def,
- struct tuple_format *format)
-{
- /* UPSERT can't be surrogate. */
- assert(type != IPROTO_UPSERT);
- struct region *region = &fiber()->gc;
- size_t region_svp = region_used(region);
-
- uint32_t field_count = format->index_field_count;
- uint32_t iov_sz = sizeof(struct iovec) * format->total_field_count;
- struct iovec *iov = region_alloc(region, iov_sz);
- if (iov == NULL) {
- diag_set(OutOfMemory, iov_sz, "region",
- "iov for surrogate key");
- return NULL;
- }
- memset(iov, 0, iov_sz);
- uint32_t part_count = mp_decode_array(&key);
- assert(part_count == cmp_def->part_count);
- assert(part_count <= format->total_field_count);
- /**
- * Calculate bsize using format::min_tuple_size tuple
- * where parts_count nulls replaced with extracted keys.
- */
- uint32_t bsize = format->min_tuple_size - mp_sizeof_nil() * part_count;
- for (uint32_t i = 0; i < part_count; ++i) {
- const struct key_part *part = &cmp_def->parts[i];
- assert(part->fieldno < field_count);
- struct tuple_field *field =
- tuple_format_field_by_path(format, part->fieldno,
- part->path, part->path_len);
- assert(field != NULL);
- const char *svp = key;
- iov[field->id].iov_base = (char *) key;
- mp_next(&key);
- iov[field->id].iov_len = key - svp;
- bsize += key - svp;
- }
-
- struct tuple *stmt = vy_stmt_alloc(format, bsize);
- if (stmt == NULL)
- goto out;
-
- char *raw = (char *) tuple_data(stmt);
- uint32_t *field_map = (uint32_t *) raw;
- memset((char *)field_map - format->field_map_size, 0,
- format->field_map_size);
- char *wpos = mp_encode_array(raw, field_count);
- struct tuple_field *field;
- json_tree_foreach_entry_preorder(field, &format->fields.root,
- struct tuple_field, token) {
- /*
- * Do not restore fields not involved in index
- * (except gaps in the mp array that may be filled
- * with nils later).
- */
- if (!field->is_key_part)
- continue;
- if (field->token.type == JSON_TOKEN_NUM) {
- /*
- * Write nil istead of omitted array
- * members.
- */
- struct json_token **neighbors =
- field->token.parent->children;
- for (int i = field->token.sibling_idx - 1; i >= 0; i--) {
- if (neighbors[i] != NULL &&
- json_tree_entry(neighbors[i],
- struct tuple_field,
- token)->is_key_part)
- break;
- wpos = mp_encode_nil(wpos);
- }
- } else {
- /* Write a key string for map member. */
- assert(field->token.type == JSON_TOKEN_STR);
- const char *str = field->token.str;
- uint32_t len = field->token.len;
- wpos = mp_encode_str(wpos, str, len);
- }
- int max_child_idx = field->token.max_child_idx;
- if (json_token_is_leaf(&field->token)) {
- if (iov[field->id].iov_len == 0) {
- wpos = mp_encode_nil(wpos);
- } else {
- memcpy(wpos, iov[field->id].iov_base,
- iov[field->id].iov_len);
- uint32_t data_offset = wpos - raw;
- int32_t slot = field->offset_slot;
- if (slot != TUPLE_OFFSET_SLOT_NIL)
- field_map[slot] = data_offset;
- wpos += iov[field->id].iov_len;
- }
- } else if (field->type == FIELD_TYPE_ARRAY) {
- wpos = mp_encode_array(wpos, max_child_idx + 1);
- } else if (field->type == FIELD_TYPE_MAP) {
- wpos = mp_encode_map(wpos, max_child_idx + 1);
- }
- }
- assert(wpos == raw + bsize);
- vy_stmt_set_type(stmt, type);
-out:
- region_truncate(region, region_svp);
- return stmt;
-}
-
-struct tuple *
-vy_stmt_new_surrogate_delete_from_key(const char *key, struct key_def *cmp_def,
- struct tuple_format *format)
-{
- return vy_stmt_new_surrogate_from_key(key, IPROTO_DELETE,
- cmp_def, format);
-}
-
struct tuple *
vy_stmt_new_surrogate_delete_raw(struct tuple_format *format,
const char *src_data, const char *src_data_end)
@@ -748,8 +640,6 @@ int
vy_stmt_encode_primary(const struct tuple *value, struct key_def *key_def,
uint32_t space_id, struct xrow_header *xrow)
{
- assert(!vy_stmt_is_key(value));
-
memset(xrow, 0, sizeof(*xrow));
enum iproto_type type = vy_stmt_type(value);
xrow->type = type;
@@ -763,8 +653,9 @@ vy_stmt_encode_primary(const struct tuple *value, struct key_def *key_def,
const char *extracted = NULL;
switch (type) {
case IPROTO_DELETE:
- /* extract key */
- extracted = tuple_extract_key(value, key_def, &size);
+ extracted = vy_stmt_is_key(value) ?
+ tuple_data_range(value, &size) :
+ tuple_extract_key(value, key_def, &size);
if (extracted == NULL)
return -1;
request.key = extracted;
@@ -829,9 +720,9 @@ vy_stmt_encode_secondary(const struct tuple *value, struct key_def *cmp_def,
}
struct tuple *
-vy_stmt_decode(struct xrow_header *xrow, const struct key_def *key_def,
- struct tuple_format *format, bool is_primary)
+vy_stmt_decode(struct xrow_header *xrow, struct tuple_format *format)
{
+ struct vy_stmt_env *env = format->engine;
struct request request;
uint64_t key_map = dml_request_key_map(xrow->type);
key_map &= ~(1ULL << IPROTO_SPACE_ID); /* space_id is optional */
@@ -841,14 +732,10 @@ vy_stmt_decode(struct xrow_header *xrow, const struct key_def *key_def,
struct iovec ops;
switch (request.type) {
case IPROTO_DELETE:
- if (is_primary)
- stmt = vy_stmt_new_surrogate_from_key(request.key,
- IPROTO_DELETE,
- key_def, format);
- else
- stmt = vy_stmt_new_with_ops(format, request.key,
- request.key_end,
- NULL, 0, IPROTO_DELETE);
+ /* Always use key format for DELETE statements. */
+ stmt = vy_stmt_new_with_ops(env->key_format,
+ request.key, request.key_end,
+ NULL, 0, IPROTO_DELETE);
break;
case IPROTO_INSERT:
case IPROTO_REPLACE:
diff --git a/src/box/vy_stmt.h b/src/box/vy_stmt.h
index 7b93883d..187aa8dd 100644
--- a/src/box/vy_stmt.h
+++ b/src/box/vy_stmt.h
@@ -419,27 +419,6 @@ char *
vy_key_dup(const char *key);
/**
- * Create a new surrogate DELETE from @a key using format.
- *
- * Example:
- * key: {a3, a5}
- * key_def: { 3, 5 }
- * result: {nil, nil, a3, nil, a5}
- *
- * @param key MessagePack array with key fields.
- * @param cmp_def Key definition of the result statement (incudes
- * primary key parts).
- * @param format Target tuple format.
- *
- * @retval not NULL Success.
- * @retval NULL Memory or format error.
- */
-struct tuple *
-vy_stmt_new_surrogate_delete_from_key(const char *key,
- struct key_def *cmp_def,
- struct tuple_format *format);
-
-/**
* Create a new surrogate DELETE from @a tuple using @a format.
* A surrogate tuple has format->field_count fields from the source
* with all unindexed fields replaced with MessagePack NIL.
@@ -497,6 +476,20 @@ struct tuple *
vy_stmt_new_insert(struct tuple_format *format, const char *tuple_begin,
const char *tuple_end);
+/**
+ * Create the DELETE statement from raw MessagePack data.
+ * @param format Format of a tuple for offsets generating.
+ * @param tuple_begin MessagePack data that contain an array of fields WITH the
+ * array header.
+ * @param tuple_end End of the array that begins from @param tuple_begin.
+ *
+ * @retval NULL Memory allocation error.
+ * @retval not NULL Success.
+ */
+struct tuple *
+vy_stmt_new_delete(struct tuple_format *format, const char *tuple_begin,
+ const char *tuple_end);
+
/**
* Create the UPSERT statement from raw MessagePack data.
* @param tuple_begin MessagePack data that contain an array of fields WITH the
@@ -649,8 +642,7 @@ vy_stmt_encode_secondary(const struct tuple *value, struct key_def *cmp_def,
* @retval NULL on error
*/
struct tuple *
-vy_stmt_decode(struct xrow_header *xrow, const struct key_def *key_def,
- struct tuple_format *format, bool is_primary);
+vy_stmt_decode(struct xrow_header *xrow, struct tuple_format *format);
/**
* Format a statement into string.
diff --git a/src/box/vy_write_iterator.c b/src/box/vy_write_iterator.c
index 36e43bc9..ee2cb7ae 100644
--- a/src/box/vy_write_iterator.c
+++ b/src/box/vy_write_iterator.c
@@ -476,7 +476,7 @@ vy_write_iterator_new_slice(struct vy_stmt_stream *vstream,
if (src == NULL)
return -1;
vy_slice_stream_open(&src->slice_stream, slice, stream->cmp_def,
- disk_format, stream->is_primary);
+ disk_format);
return 0;
}
diff --git a/test/vinyl/stat.result b/test/vinyl/stat.result
index 01da5f14..08da1658 100644
--- a/test/vinyl/stat.result
+++ b/test/vinyl/stat.result
@@ -1391,7 +1391,7 @@ st2 = i2:stat()
...
s:bsize()
---
-- 107449
+- 107199
...
i1:len(), i2:len()
---
--
2.11.0
^ permalink raw reply [flat|nested] 34+ messages in thread* [PATCH v2 13/14] vinyl: don't use vy_stmt_new_surrogate_delete if not necessary
2019-03-13 8:52 [PATCH v2 00/14] vinyl: do not fill secondary tuples with nulls Vladimir Davydov
` (11 preceding siblings ...)
2019-03-13 8:52 ` [PATCH v2 12/14] vinyl: zap vy_stmt_new_surrogate_from_key Vladimir Davydov
@ 2019-03-13 8:52 ` Vladimir Davydov
2019-03-13 12:28 ` Konstantin Osipov
2019-03-13 8:53 ` [PATCH v2 14/14] tuple_format: zap min_tuple_size Vladimir Davydov
2019-03-13 15:54 ` [PATCH v2 00/14] vinyl: do not fill secondary tuples with nulls Vladimir Davydov
14 siblings, 1 reply; 34+ messages in thread
From: Vladimir Davydov @ 2019-03-13 8:52 UTC (permalink / raw)
To: kostja; +Cc: tarantool-patches
There are three places where we use this expensive functions while we
could get along with a cheaper one:
- Deferred DELETE space on_replace trigger. Here we can use simple
vy_stmt_new_delete, because the trigger is already passed a surrogate
DELETE statement.
- Secondary index build on_replace trigger. Here we can extract the
secondary key, set its type to DELETE and insert it into the index.
We don't need all the other indexed fields.
- Secondary index build recovery procedure. Similarly to the previous
case, we can use extracted here rather than building a surrogate
DELETE statement.
---
src/box/vinyl.c | 14 ++++++++------
1 file changed, 8 insertions(+), 6 deletions(-)
diff --git a/src/box/vinyl.c b/src/box/vinyl.c
index f2d9ab55..80296269 100644
--- a/src/box/vinyl.c
+++ b/src/box/vinyl.c
@@ -3935,10 +3935,11 @@ vy_build_on_replace(struct trigger *trigger, void *event)
/* Forward the statement to the new LSM tree. */
if (stmt->old_tuple != NULL) {
- struct tuple *delete = vy_stmt_new_surrogate_delete(format,
- stmt->old_tuple);
+ struct tuple *delete = vy_stmt_extract_key(stmt->old_tuple,
+ lsm->cmp_def, lsm->env->key_format);
if (delete == NULL)
goto err;
+ vy_stmt_set_type(delete, IPROTO_DELETE);
int rc = vy_tx_set(tx, lsm, delete);
tuple_unref(delete);
if (rc != 0)
@@ -4076,10 +4077,11 @@ vy_build_recover_stmt(struct vy_lsm *lsm, struct vy_lsm *pk,
struct tuple *delete = NULL;
struct tuple *insert = NULL;
if (old_tuple != NULL) {
- delete = vy_stmt_new_surrogate_delete(lsm->mem_format,
- old_tuple);
+ delete = vy_stmt_extract_key(old_tuple, lsm->cmp_def,
+ lsm->env->key_format);
if (delete == NULL)
return -1;
+ vy_stmt_set_type(delete, IPROTO_DELETE);
}
enum iproto_type type = vy_stmt_type(mem_stmt);
if (type == IPROTO_REPLACE || type == IPROTO_INSERT) {
@@ -4387,8 +4389,8 @@ vy_deferred_delete_on_replace(struct trigger *trigger, void *event)
/* Create the deferred DELETE statement. */
struct vy_lsm *pk = vy_lsm(space->index[0]);
- struct tuple *delete = vy_stmt_new_surrogate_delete_raw(pk->mem_format,
- delete_data, delete_data_end);
+ struct tuple *delete = vy_stmt_new_delete(pk->mem_format, delete_data,
+ delete_data_end);
if (delete == NULL)
diag_raise();
/*
--
2.11.0
^ permalink raw reply [flat|nested] 34+ messages in thread* [PATCH v2 14/14] tuple_format: zap min_tuple_size
2019-03-13 8:52 [PATCH v2 00/14] vinyl: do not fill secondary tuples with nulls Vladimir Davydov
` (12 preceding siblings ...)
2019-03-13 8:52 ` [PATCH v2 13/14] vinyl: don't use vy_stmt_new_surrogate_delete if not necessary Vladimir Davydov
@ 2019-03-13 8:53 ` Vladimir Davydov
2019-03-13 12:28 ` Konstantin Osipov
2019-03-13 15:54 ` [PATCH v2 00/14] vinyl: do not fill secondary tuples with nulls Vladimir Davydov
14 siblings, 1 reply; 34+ messages in thread
From: Vladimir Davydov @ 2019-03-13 8:53 UTC (permalink / raw)
To: kostja; +Cc: tarantool-patches
It had been used only in Vinyl's vy_stmt_new_surrogate_from_key, which
was deleted by the previous patches, so we can drop it as well.
---
src/box/tuple_format.c | 40 ----------------------------------------
src/box/tuple_format.h | 5 -----
2 files changed, 45 deletions(-)
diff --git a/src/box/tuple_format.c b/src/box/tuple_format.c
index 4439ce3e..22a84af8 100644
--- a/src/box/tuple_format.c
+++ b/src/box/tuple_format.c
@@ -441,7 +441,6 @@ tuple_format_create(struct tuple_format *format, struct key_def * const *keys,
"malloc", "required field bitmap");
return -1;
}
- format->min_tuple_size = mp_sizeof_array(format->index_field_count);
struct tuple_field *field;
json_tree_foreach_entry_preorder(field, &format->fields.root,
struct tuple_field, token) {
@@ -453,44 +452,6 @@ tuple_format_create(struct tuple_format *format, struct key_def * const *keys,
if (json_token_is_leaf(&field->token) &&
!tuple_field_is_nullable(field))
bit_set(format->required_fields, field->id);
-
- /*
- * Update format::min_tuple_size by field.
- * Skip fields not involved in index.
- */
- if (!field->is_key_part)
- continue;
- if (field->token.type == JSON_TOKEN_NUM) {
- /*
- * Account a gap between omitted array
- * items.
- */
- struct json_token **neighbors =
- field->token.parent->children;
- for (int i = field->token.sibling_idx - 1; i >= 0; i--) {
- if (neighbors[i] != NULL &&
- json_tree_entry(neighbors[i],
- struct tuple_field,
- token)->is_key_part)
- break;
- format->min_tuple_size += mp_sizeof_nil();
- }
- } else {
- /* Account a key string for map member. */
- assert(field->token.type == JSON_TOKEN_STR);
- format->min_tuple_size +=
- mp_sizeof_str(field->token.len);
- }
- int max_child_idx = field->token.max_child_idx;
- if (json_token_is_leaf(&field->token)) {
- format->min_tuple_size += mp_sizeof_nil();
- } else if (field->type == FIELD_TYPE_ARRAY) {
- format->min_tuple_size +=
- mp_sizeof_array(max_child_idx + 1);
- } else if (field->type == FIELD_TYPE_MAP) {
- format->min_tuple_size +=
- mp_sizeof_map(max_child_idx + 1);
- }
}
format->hash = tuple_format_hash(format);
return 0;
@@ -623,7 +584,6 @@ tuple_format_alloc(struct key_def * const *keys, uint16_t key_count,
format->total_field_count = field_count;
format->required_fields = NULL;
format->fields_depth = 1;
- format->min_tuple_size = 0;
format->refs = 0;
format->id = FORMAT_ID_NIL;
format->index_field_count = index_field_count;
diff --git a/src/box/tuple_format.h b/src/box/tuple_format.h
index 5c5fdbd3..22a0fb23 100644
--- a/src/box/tuple_format.h
+++ b/src/box/tuple_format.h
@@ -203,11 +203,6 @@ struct tuple_format {
*/
struct tuple_dictionary *dict;
/**
- * The size of a minimal tuple conforming to the format
- * and filled with nils.
- */
- uint32_t min_tuple_size;
- /**
* A maximum depth of format::fields subtree.
*/
uint32_t fields_depth;
--
2.11.0
^ permalink raw reply [flat|nested] 34+ messages in thread* Re: [PATCH v2 00/14] vinyl: do not fill secondary tuples with nulls
2019-03-13 8:52 [PATCH v2 00/14] vinyl: do not fill secondary tuples with nulls Vladimir Davydov
` (13 preceding siblings ...)
2019-03-13 8:53 ` [PATCH v2 14/14] tuple_format: zap min_tuple_size Vladimir Davydov
@ 2019-03-13 15:54 ` Vladimir Davydov
14 siblings, 0 replies; 34+ messages in thread
From: Vladimir Davydov @ 2019-03-13 15:54 UTC (permalink / raw)
To: kostja; +Cc: tarantool-patches
On Wed, Mar 13, 2019 at 11:52:46AM +0300, Vladimir Davydov wrote:
> Vladimir Davydov (14):
> vinyl: remove optimized comparators
> vinyl: introduce statement environment
> vinyl: rename key stmt construction routine
> vinyl: don't use IPROTO_SELECT type for key statements
> bloom: do not use tuple_common_key_parts when constructing tuple bloom
> bloom: factor out helper to add tuple hash to bloom builder
> vinyl: add helpers to add/check statement with bloom
> vinyl: do not pass format to vy_apply_upsert
> vinyl: clean up write iterator source destruction
> vinyl: zap vy_write_iterator->format
> vinyl: do not fill secondary tuples with nulls when decoded
> vinyl: zap vy_stmt_new_surrogate_from_key
> vinyl: don't use vy_stmt_new_surrogate_delete if not necessary
> tuple_format: zap min_tuple_size
Pushed to 2.1 with fixes according to review by Kostja.
^ permalink raw reply [flat|nested] 34+ messages in thread