[tarantool-patches] Re: [PATCH v6 2/3] memtx: introduce tuple compare hint
Kirill Shcherbatov
kshcherbatov at tarantool.org
Fri Mar 15 13:20:09 MSK 2019
> Please refresh the comment. It isn't quite correct.
I've stripped it a bit.
> On the second thought, we might want to reduce the hint size or increase
> it in future. Would it be better to introduce a helper type for hints so
> that we could easily do this if we need to?
>
> typedef uint64_t tuple_hint_t;
>
> What do you think? Would it be worthwhile? Would it look OK?
>
> Sorry, I asked you to use uint64_t before. Looks to me now that
> I was wrong... :-(
tuple_hint_t name is not really good, I believe.
At first, tuple_hint() is a routine that calculates such hint for tuple.
I prefer hint_t type that would be ok even later with multikey index intriduction.
> Hmm, (&a)->tuple is equivalent to (a).tuple, isn't it?
I don't understand why, by it doesn't work in such way.
> Accessing index->tree.arg looks ugly - it violates encapsulation.
> Besides, right above you use index_def_cmp_def instead. I think we
> better introduce a helper function for accessing index->tree.arg
> and use it everywhere:
>
> memtx_tree_cmp_def(&index->tree)
Now I use memtx_tree_index_cmp_def() routine that already present in code
and works fine in such scenario.
==============================================================
Implement functions for retrieving tuple hints for a particular
key_def. Hint is an integer that can be used for tuple comparison
optimization: if a hint of one tuple is less than a hint of another
then the first tuple is definitely less than the second; only if
hints are equal tuple_compare must be called for getting comparison
result. Hints are calculated using only the first part of key_def.
Close #3961
---
src/box/key_def.h | 128 +++++++++++++
src/box/memtx_tree.c | 40 +++-
src/box/tuple_compare.cc | 394 +++++++++++++++++++++++++++++++++++++--
src/lib/coll/coll.c | 29 +++
src/lib/coll/coll.h | 5 +
test/engine/ddl.result | 180 ++++++++++++++++++
test/engine/ddl.test.lua | 49 +++++
7 files changed, 800 insertions(+), 25 deletions(-)
diff --git a/src/box/key_def.h b/src/box/key_def.h
index 7c9f8c6b5..174790f72 100644
--- a/src/box/key_def.h
+++ b/src/box/key_def.h
@@ -116,6 +116,41 @@ struct key_part {
struct key_def;
struct tuple;
+/**
+ * Tuple comparison hint h(t) is such a function of tuple t that
+ * the following conditions always hold for any pair of tuples
+ * t1 and t2:
+ * if h(t1) < h(t2) then t1 < t2;
+ * if h(t1) > h(t2) then t1 > t2;
+ * if h(t1) == h(t2) then t1 may or may not be equal to t2.
+ * These rules mean that instead of direct tuple vs tuple
+ * (or tuple vs key) comparison one may compare theirs
+ * hints first; and only if theirs hints equal compare
+ * the tuples themselves.
+ *
+ * The comparison hint has the following structure:
+ * uint64_t: [ HINT_TYPE | HINT_VALUE ]
+ * 64 60 0 bit
+ *
+ * To make the values of hints for numeric types(unsigned,
+ * integer, float, double) compatible, define a linear mapping
+ * of the segment f(x) = k*x + b = x + max + 1:
+ * f([-max - 1, max]) = [0, 2 * max + 1].
+ * It is easy to make sure that there is a < b <=> f (a) < f(b).
+ * The max value is determined by the number of bits allocated
+ * for storage of HINT_VALUE.
+ */
+typedef uint64_t hint_t;
+
+#define HINT_VALUE_BITS 60
+#define HINT_MAX (((int64_t)1 << (HINT_VALUE_BITS - 1)) - 1)
+#define HINT_MIN (-HINT_MAX - 1)
+
+/**
+ * The reserved value to use when comparison hint is undefined.
+ */
+#define HINT_NONE ((hint_t)UINT64_MAX)
+
/**
* Get is_nullable property of key_part.
* @param key_part for which attribute is being fetched
@@ -137,6 +172,19 @@ typedef int (*tuple_compare_with_key_t)(const struct tuple *tuple_a,
typedef int (*tuple_compare_t)(const struct tuple *tuple_a,
const struct tuple *tuple_b,
struct key_def *key_def);
+/** @copydoc tuple_compare_with_key_hinted() */
+typedef int (*tuple_compare_with_key_hinted_t)(const struct tuple *tuple,
+ hint_t tuple_hint,
+ const char *key,
+ uint32_t part_count,
+ hint_t key_hint,
+ struct key_def *key_def);
+/** @copydoc tuple_compare_hinted() */
+typedef int (*tuple_compare_hinted_t)(const struct tuple *tuple_a,
+ hint_t tuple_a_hint,
+ const struct tuple *tuple_b,
+ hint_t tuple_b_hint,
+ struct key_def *key_def);
/** @copydoc tuple_extract_key() */
typedef char *(*tuple_extract_key_t)(const struct tuple *tuple,
struct key_def *key_def,
@@ -152,6 +200,11 @@ typedef uint32_t (*tuple_hash_t)(const struct tuple *tuple,
/** @copydoc key_hash() */
typedef uint32_t (*key_hash_t)(const char *key,
struct key_def *key_def);
+/** @copydoc tuple_hint() */
+typedef hint_t (*tuple_hint_t)(const struct tuple *tuple,
+ struct key_def *key_def);
+/** @copydoc key_hint() */
+typedef hint_t (*key_hint_t)(const char *key, struct key_def *key_def);
/* Definition of a multipart key. */
struct key_def {
@@ -159,6 +212,10 @@ struct key_def {
tuple_compare_t tuple_compare;
/** @see tuple_compare_with_key() */
tuple_compare_with_key_t tuple_compare_with_key;
+ /** @see tuple_compare_with_key_hinted() */
+ tuple_compare_with_key_hinted_t tuple_compare_with_key_hinted;
+ /** @see tuple_compare_hinted() */
+ tuple_compare_hinted_t tuple_compare_hinted;
/** @see tuple_extract_key() */
tuple_extract_key_t tuple_extract_key;
/** @see tuple_extract_key_raw() */
@@ -167,6 +224,10 @@ struct key_def {
tuple_hash_t tuple_hash;
/** @see key_hash() */
key_hash_t key_hash;
+ /** @see tuple_hint() */
+ tuple_hint_t tuple_hint;
+ /** @see key_hint() */
+ key_hint_t key_hint;
/**
* Minimal part count which always is unique. For example,
* if a secondary index is unique, then
@@ -575,6 +636,49 @@ tuple_compare_with_key(const struct tuple *tuple, const char *key,
return key_def->tuple_compare_with_key(tuple, key, part_count, key_def);
}
+/**
+ * Compare tuples using the key definition and comparison hints.
+ * @param tuple_a First tuple.
+ * @param tuple_a_hint Comparison hint of @a tuple_a.
+ * @param tuple_b Second tuple.
+ * @param tuple_b_hint Comparison hint of @a tuple_b.
+ * @param key_def Key definition.
+ * @retval 0 if key_fields(tuple_a) == key_fields(tuple_b).
+ * @retval <0 if key_fields(tuple_a) < key_fields(tuple_b).
+ * @retval >0 if key_fields(tuple_a) > key_fields(tuple_b).
+ */
+static inline int
+tuple_compare_hinted(const struct tuple *tuple_a, hint_t tuple_a_hint,
+ const struct tuple *tuple_b, hint_t tuple_b_hint,
+ struct key_def *key_def)
+{
+ return key_def->tuple_compare_hinted(tuple_a, tuple_a_hint, tuple_b,
+ tuple_b_hint, key_def);
+}
+
+/**
+ * Compare tuple with key using the key definition and
+ * comparison hints.
+ * @param tuple Tuple.
+ * @param tuple_hint Comparison hint of @a tuple.
+ * @param key Key parts without MessagePack array header.
+ * @param part_count The number of parts in @a key.
+ * @param key_hint t Comparison hint of @a key.
+ * @param key_def Key definition.
+ * @retval 0 if key_fields(tuple) == parts(key).
+ * @retval <0 if key_fields(tuple) < parts(key).
+ * @retval >0 if key_fields(tuple) > parts(key).
+ */
+static inline int
+tuple_compare_with_key_hinted(const struct tuple *tuple, hint_t tuple_hint,
+ const char *key, uint32_t part_count,
+ hint_t key_hint, struct key_def *key_def)
+{
+ return key_def->tuple_compare_with_key_hinted(tuple, tuple_hint, key,
+ part_count, key_hint,
+ key_def);
+}
+
/**
* Compute hash of a tuple field.
* @param ph1 - pointer to running hash
@@ -628,6 +732,30 @@ key_hash(const char *key, struct key_def *key_def)
return key_def->key_hash(key, key_def);
}
+ /*
+ * Get comparison hint for a @a tuple.
+ * @param tuple Tuple to compute the hint for.
+ * @param key_def Key definition used for tuple comparison.
+ * @return The hint.
+ */
+static inline hint_t
+tuple_hint(const struct tuple *tuple, struct key_def *key_def)
+{
+ return key_def->tuple_hint(tuple, key_def);
+}
+
+/**
+ * Get a comparison hint of a @a key.
+ * @param key Key to compute the hint for.
+ * @param key_def Key definition used for tuple comparison.
+ * @return The hint.
+ */
+static inline hint_t
+key_hint(const char *key, struct key_def *key_def)
+{
+ return key_def->key_hint(key, key_def);
+}
+
#if defined(__cplusplus)
} /* extern "C" */
#endif /* defined(__cplusplus) */
diff --git a/src/box/memtx_tree.c b/src/box/memtx_tree.c
index d5b42efb6..c2c8a19e7 100644
--- a/src/box/memtx_tree.c
+++ b/src/box/memtx_tree.c
@@ -47,6 +47,8 @@ struct memtx_tree_key_data {
const char *key;
/** Number of msgpacked search fields. */
uint32_t part_count;
+ /** Comparison hint, see tuple_hint(). */
+ hint_t hint;
};
/**
@@ -55,6 +57,8 @@ struct memtx_tree_key_data {
struct memtx_tree_data {
/* Tuple that this node is represents. */
struct tuple *tuple;
+ /** Comparison hint, see key_hint(). */
+ hint_t hint;
};
/**
@@ -69,16 +73,18 @@ static bool
memtx_tree_data_identical(const struct memtx_tree_data *a,
const struct memtx_tree_data *b)
{
- return a->tuple == b->tuple;
+ return a->tuple == b->tuple && a->hint == b->hint;
}
#define BPS_TREE_NAME memtx_tree
#define BPS_TREE_BLOCK_SIZE (512)
#define BPS_TREE_EXTENT_SIZE MEMTX_EXTENT_SIZE
#define BPS_TREE_COMPARE(a, b, arg)\
- tuple_compare((&a)->tuple, (&b)->tuple, arg)
+ tuple_compare_hinted((&a)->tuple, (&a)->hint, (&b)->tuple,\
+ (&b)->hint, arg)
#define BPS_TREE_COMPARE_KEY(a, b, arg)\
- tuple_compare_with_key((&a)->tuple, (b)->key, (b)->part_count, arg)
+ tuple_compare_with_key_hinted((&a)->tuple, (&a)->hint, (b)->key,\
+ (b)->part_count, (b)->hint, arg)
#define BPS_TREE_IDENTICAL(a, b) memtx_tree_data_identical(&a, &b)
#define bps_tree_elem_t struct memtx_tree_data
#define bps_tree_key_t struct memtx_tree_key_data *
@@ -113,7 +119,8 @@ memtx_tree_qcompare(const void* a, const void *b, void *c)
const struct memtx_tree_data *data_a = a;
const struct memtx_tree_data *data_b = b;
struct key_def *key_def = c;
- return tuple_compare(data_a->tuple, data_b->tuple, key_def);
+ return tuple_compare_hinted(data_a->tuple, data_a->hint, data_b->tuple,
+ data_b->hint, key_def);
}
/* {{{ MemtxTree Iterators ****************************************/
@@ -235,9 +242,11 @@ tree_iterator_next_equal(struct iterator *iterator, struct tuple **ret)
memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
/* Use user key def to save a few loops. */
if (res == NULL ||
- tuple_compare_with_key(res->tuple, it->key_data.key,
- it->key_data.part_count,
- it->index_def->key_def) != 0) {
+ tuple_compare_with_key_hinted(res->tuple, res->hint,
+ it->key_data.key,
+ it->key_data.part_count,
+ it->key_data.hint,
+ it->index_def->key_def) != 0) {
iterator->next = tree_iterator_dummie;
it->current.tuple = NULL;
*ret = NULL;
@@ -266,9 +275,11 @@ tree_iterator_prev_equal(struct iterator *iterator, struct tuple **ret)
memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
/* Use user key def to save a few loops. */
if (res == NULL ||
- tuple_compare_with_key(res->tuple, it->key_data.key,
- it->key_data.part_count,
- it->index_def->key_def) != 0) {
+ tuple_compare_with_key_hinted(res->tuple, res->hint,
+ it->key_data.key,
+ it->key_data.part_count,
+ it->key_data.hint,
+ it->index_def->key_def) != 0) {
iterator->next = tree_iterator_dummie;
it->current.tuple = NULL;
*ret = NULL;
@@ -516,9 +527,11 @@ memtx_tree_index_get(struct index *base, const char *key,
assert(base->def->opts.is_unique &&
part_count == base->def->key_def->part_count);
struct memtx_tree_index *index = (struct memtx_tree_index *)base;
+ struct key_def *cmp_def = memtx_tree_index_cmp_def(index);
struct memtx_tree_key_data key_data;
key_data.key = key;
key_data.part_count = part_count;
+ key_data.hint = key_hint(key, cmp_def);
struct memtx_tree_data *res = memtx_tree_find(&index->tree, &key_data);
*result = res != NULL ? res->tuple : NULL;
return 0;
@@ -530,9 +543,11 @@ memtx_tree_index_replace(struct index *base, struct tuple *old_tuple,
struct tuple **result)
{
struct memtx_tree_index *index = (struct memtx_tree_index *)base;
+ struct key_def *key_def = memtx_tree_index_cmp_def(index);
if (new_tuple) {
struct memtx_tree_data new_data;
new_data.tuple = new_tuple;
+ new_data.hint = tuple_hint(new_tuple, key_def);
struct memtx_tree_data dup_data;
dup_data.tuple = NULL;
@@ -565,6 +580,7 @@ memtx_tree_index_replace(struct index *base, struct tuple *old_tuple,
if (old_tuple) {
struct memtx_tree_data old_data;
old_data.tuple = old_tuple;
+ old_data.hint = tuple_hint(old_tuple, key_def);
memtx_tree_delete(&index->tree, old_data);
}
*result = old_tuple;
@@ -607,6 +623,8 @@ memtx_tree_index_create_iterator(struct index *base, enum iterator_type type,
it->type = type;
it->key_data.key = key;
it->key_data.part_count = part_count;
+ struct key_def *cmp_def = memtx_tree_index_cmp_def(index);
+ it->key_data.hint = key_hint(key, cmp_def);
it->index_def = base->def;
it->tree = &index->tree;
it->tree_iterator = memtx_tree_invalid_iterator();
@@ -671,6 +689,8 @@ memtx_tree_index_build_next(struct index *base, struct tuple *tuple)
struct memtx_tree_data *elem =
&index->build_array[index->build_array_size++];
elem->tuple = tuple;
+ struct key_def *key_def = memtx_tree_index_cmp_def(index);
+ elem->hint = tuple_hint(tuple, key_def);
return 0;
}
diff --git a/src/box/tuple_compare.cc b/src/box/tuple_compare.cc
index 7fe1766a8..54a977926 100644
--- a/src/box/tuple_compare.cc
+++ b/src/box/tuple_compare.cc
@@ -34,6 +34,14 @@
#include "trivia/util.h" /* NOINLINE */
#include <math.h>
+/**
+ * Perform hints comparison according hint_t definition.
+ * Returns 1 when hint_a > hint_b, -1 when hint_b > hint_a;
+ * When tuple_hints are incompatible or equal, return 0.
+ */
+static int
+hint_cmp(hint_t hint_a, hint_t hint_b);
+
/* {{{ tuple_compare */
/*
@@ -427,13 +435,17 @@ tuple_compare_field_with_hint(const char *field_a, enum mp_type a_type,
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,
- struct key_def *key_def)
+tuple_compare_slowpath_hinted(const struct tuple *tuple_a,
+ hint_t tuple_a_hint, const struct tuple *tuple_b,
+ hint_t tuple_b_hint, struct key_def *key_def)
{
assert(has_json_paths == key_def->has_json_paths);
assert(!has_optional_parts || is_nullable);
assert(is_nullable == key_def->is_nullable);
assert(has_optional_parts == key_def->has_optional_parts);
+ int rc = 0;
+ if ((rc = hint_cmp(tuple_a_hint, tuple_b_hint)) != 0)
+ return rc;
struct key_part *part = key_def->parts;
const char *tuple_a_raw = tuple_data(tuple_a);
const char *tuple_b_raw = tuple_data(tuple_b);
@@ -469,7 +481,6 @@ tuple_compare_slowpath(const struct tuple *tuple_a, const struct tuple *tuple_b,
struct key_part *end;
const char *field_a, *field_b;
enum mp_type a_type, b_type;
- int rc;
if (is_nullable)
end = part + key_def->unique_part_count;
else
@@ -559,8 +570,19 @@ tuple_compare_slowpath(const struct tuple *tuple_a, const struct tuple *tuple_b,
template<bool is_nullable, bool has_optional_parts, bool has_json_paths>
static inline int
-tuple_compare_with_key_slowpath(const struct tuple *tuple, const char *key,
- uint32_t part_count, struct key_def *key_def)
+tuple_compare_slowpath(const struct tuple *tuple_a, const struct tuple *tuple_b,
+ struct key_def *key_def)
+{
+ return tuple_compare_slowpath_hinted<is_nullable, has_optional_parts,
+ has_json_paths>(tuple_a, HINT_NONE, tuple_b, HINT_NONE,
+ key_def);
+}
+
+template<bool is_nullable, bool has_optional_parts, bool has_json_paths>
+static inline int
+tuple_compare_with_key_slowpath_hinted(const struct tuple *tuple,
+ hint_t tuple_hint, const char *key, uint32_t part_count,
+ hint_t key_hint, struct key_def *key_def)
{
assert(has_json_paths == key_def->has_json_paths);
assert(!has_optional_parts || is_nullable);
@@ -568,6 +590,9 @@ tuple_compare_with_key_slowpath(const struct tuple *tuple, const char *key,
assert(has_optional_parts == key_def->has_optional_parts);
assert(key != NULL || part_count == 0);
assert(part_count <= key_def->part_count);
+ int rc = 0;
+ if ((rc = hint_cmp(tuple_hint, key_hint)) != 0)
+ return rc;
struct key_part *part = key_def->parts;
struct tuple_format *format = tuple_format(tuple);
const char *tuple_raw = tuple_data(tuple);
@@ -603,7 +628,6 @@ tuple_compare_with_key_slowpath(const struct tuple *tuple, const char *key,
}
struct key_part *end = part + part_count;
- int rc;
for (; part < end; ++part, mp_next(&key)) {
const char *field;
if (has_json_paths) {
@@ -642,6 +666,17 @@ tuple_compare_with_key_slowpath(const struct tuple *tuple, const char *key,
return 0;
}
+template<bool is_nullable, bool has_optional_parts, bool has_json_paths>
+static inline int
+tuple_compare_with_key_slowpath(const struct tuple *tuple, const char *key,
+ uint32_t part_count, struct key_def *key_def)
+{
+ return tuple_compare_with_key_slowpath_hinted<is_nullable,
+ has_optional_parts, has_json_paths>(tuple,
+ HINT_NONE, key, part_count,
+ HINT_NONE, key_def);
+}
+
template<bool is_nullable>
static inline int
key_compare_parts(const char *key_a, const char *key_b, uint32_t part_count,
@@ -700,13 +735,17 @@ key_compare_parts(const char *key_a, const char *key_b, uint32_t part_count,
template<bool is_nullable, bool has_optional_parts>
static inline int
-tuple_compare_with_key_sequential(const struct tuple *tuple, const char *key,
- uint32_t part_count, struct key_def *key_def)
+tuple_compare_with_key_sequential_hinted(const struct tuple *tuple,
+ hint_t tuple_hint, const char *key, uint32_t part_count,
+ hint_t key_hint, struct key_def *key_def)
{
assert(!has_optional_parts || is_nullable);
assert(key_def_is_sequential(key_def));
assert(is_nullable == key_def->is_nullable);
assert(has_optional_parts == key_def->has_optional_parts);
+ int rc = hint_cmp(tuple_hint, key_hint);
+ if (rc != 0)
+ return rc;
const char *tuple_key = tuple_data(tuple);
uint32_t field_count = mp_decode_array(&tuple_key);
uint32_t cmp_part_count;
@@ -716,8 +755,8 @@ tuple_compare_with_key_sequential(const struct tuple *tuple, const char *key,
assert(field_count >= part_count);
cmp_part_count = part_count;
}
- int rc = key_compare_parts<is_nullable>(tuple_key, key, cmp_part_count,
- key_def);
+ rc = key_compare_parts<is_nullable>(tuple_key, key, cmp_part_count,
+ key_def);
if (!has_optional_parts || rc != 0)
return rc;
/*
@@ -739,6 +778,16 @@ tuple_compare_with_key_sequential(const struct tuple *tuple, const char *key,
return 0;
}
+template<bool is_nullable, bool has_optional_parts>
+static inline int
+tuple_compare_with_key_sequential(const struct tuple *tuple, const char *key,
+ uint32_t part_count, struct key_def *key_def)
+{
+ return tuple_compare_with_key_sequential_hinted<is_nullable,
+ has_optional_parts>(tuple, HINT_NONE, key,
+ part_count, HINT_NONE, key_def);
+}
+
int
key_compare(const char *key_a, const char *key_b, struct key_def *key_def)
{
@@ -759,13 +808,17 @@ key_compare(const char *key_a, const char *key_b, struct key_def *key_def)
template <bool is_nullable, bool has_optional_parts>
static int
-tuple_compare_sequential(const struct tuple *tuple_a,
- const struct tuple *tuple_b, key_def *key_def)
+tuple_compare_sequential_hinted(const struct tuple *tuple_a,
+ hint_t tuple_a_hint, const struct tuple *tuple_b,
+ hint_t tuple_b_hint, key_def *key_def)
{
assert(!has_optional_parts || is_nullable);
assert(has_optional_parts == key_def->has_optional_parts);
assert(key_def_is_sequential(key_def));
assert(is_nullable == key_def->is_nullable);
+ int rc = hint_cmp(tuple_a_hint, tuple_b_hint);
+ if (rc != 0)
+ return rc;
const char *key_a = tuple_data(tuple_a);
uint32_t fc_a = mp_decode_array(&key_a);
const char *key_b = tuple_data(tuple_b);
@@ -779,7 +832,6 @@ tuple_compare_sequential(const struct tuple *tuple_a,
bool was_null_met = false;
struct key_part *part = key_def->parts;
struct key_part *end = part + key_def->unique_part_count;
- int rc;
uint32_t i = 0;
for (; part < end; ++part, ++i) {
enum mp_type a_type, b_type;
@@ -826,6 +878,16 @@ tuple_compare_sequential(const struct tuple *tuple_a,
return 0;
}
+template <bool is_nullable, bool has_optional_parts>
+static int
+tuple_compare_sequential(const struct tuple *tuple_a,
+ const struct tuple *tuple_b, key_def *key_def)
+{
+ return tuple_compare_sequential_hinted<is_nullable,
+ has_optional_parts>(tuple_a, HINT_NONE, tuple_b,
+ HINT_NONE, key_def);
+}
+
template <int TYPE>
static inline int
field_compare(const char **field_a, const char **field_b);
@@ -956,6 +1018,18 @@ struct TupleCompare
compare(tuple_a, tuple_b, format_a,
format_b, field_a, field_b);
}
+
+ static int compare_hinted(const struct tuple *tuple_a,
+ hint_t tuple_a_hint,
+ const struct tuple *tuple_b,
+ hint_t tuple_b_hint,
+ struct key_def *key_def)
+ {
+ int rc = hint_cmp(tuple_a_hint, tuple_b_hint);
+ if (rc != 0)
+ return rc;
+ return compare(tuple_a, tuple_b, key_def);
+ }
};
template <int TYPE, int ...MORE_TYPES>
@@ -973,15 +1047,30 @@ struct TupleCompare<0, TYPE, MORE_TYPES...> {
return FieldCompare<0, TYPE, MORE_TYPES...>::compare(tuple_a, tuple_b,
format_a, format_b, field_a, field_b);
}
+
+ static int compare_hinted(const struct tuple *tuple_a,
+ hint_t tuple_a_hint,
+ const struct tuple *tuple_b,
+ hint_t tuple_b_hint,
+ struct key_def *key_def)
+ {
+ int rc = hint_cmp(tuple_a_hint, tuple_b_hint);
+ if (rc != 0)
+ return rc;
+ return compare(tuple_a, tuple_b, key_def);
+ }
};
} /* end of anonymous namespace */
struct comparator_signature {
tuple_compare_t f;
+ tuple_compare_hinted_t f_hinted;
uint32_t p[64];
};
#define COMPARATOR(...) \
- { TupleCompare<__VA_ARGS__>::compare, { __VA_ARGS__, UINT32_MAX } },
+ { TupleCompare<__VA_ARGS__>::compare, \
+ TupleCompare<__VA_ARGS__>::compare_hinted, \
+ { __VA_ARGS__, UINT32_MAX } },
/**
* field1 no, field1 type, field2 no, field2 type, ...
@@ -1133,6 +1222,17 @@ struct TupleCompareWithKey
compare(tuple, key, part_count,
key_def, format, field);
}
+
+ static int
+ compare_hinted(const struct tuple *tuple, hint_t tuple_hint,
+ const char *key, uint32_t part_count, hint_t key_hint,
+ struct key_def *key_def)
+ {
+ int rc = hint_cmp(tuple_hint, key_hint);
+ if (rc != 0)
+ return rc;
+ return compare(tuple, key, part_count, key_def);
+ }
};
template <int TYPE, int ...MORE_TYPES>
@@ -1153,6 +1253,17 @@ struct TupleCompareWithKey<0, 0, TYPE, MORE_TYPES...>
compare(tuple, key, part_count,
key_def, format, field);
}
+
+ static int
+ compare_hinted(const struct tuple *tuple, hint_t tuple_hint,
+ const char *key, uint32_t part_count, hint_t key_hint,
+ struct key_def *key_def)
+ {
+ int rc = hint_cmp(tuple_hint, key_hint);
+ if (rc != 0)
+ return rc;
+ return compare(tuple, key, part_count, key_def);
+ }
};
} /* end of anonymous namespace */
@@ -1160,11 +1271,14 @@ struct TupleCompareWithKey<0, 0, TYPE, MORE_TYPES...>
struct comparator_with_key_signature
{
tuple_compare_with_key_t f;
+ tuple_compare_with_key_hinted_t f_hinted;
uint32_t p[64];
};
#define KEY_COMPARATOR(...) \
- { TupleCompareWithKey<0, __VA_ARGS__>::compare, { __VA_ARGS__ } },
+ { TupleCompareWithKey<0, __VA_ARGS__>::compare, \
+ TupleCompareWithKey<0, __VA_ARGS__>::compare_hinted, \
+ { __VA_ARGS__ } },
static const comparator_with_key_signature precompiled_cmp_wk_arr[] = {
KEY_COMPARATOR(0, FIELD_TYPE_UNSIGNED, 1, FIELD_TYPE_UNSIGNED, 2, FIELD_TYPE_UNSIGNED)
@@ -1187,16 +1301,22 @@ static const comparator_with_key_signature precompiled_cmp_wk_arr[] = {
#define COMPARE_SLOWPATH(...) \
{tuple_compare_slowpath<__VA_ARGS__>, \
tuple_compare_with_key_slowpath<__VA_ARGS__>, \
+ tuple_compare_slowpath_hinted<__VA_ARGS__>, \
+ tuple_compare_with_key_slowpath_hinted<__VA_ARGS__>, \
__VA_ARGS__, false}
#define COMPARE_SEQUENTIAL(...) \
{tuple_compare_sequential<__VA_ARGS__>, \
tuple_compare_with_key_sequential<__VA_ARGS__>, \
+ tuple_compare_sequential_hinted<__VA_ARGS__>, \
+ tuple_compare_with_key_sequential_hinted<__VA_ARGS__>, \
__VA_ARGS__, false, true}
static struct {
tuple_compare_t tuple_compare;
tuple_compare_with_key_t tuple_compare_with_key;
+ tuple_compare_hinted_t tuple_compare_hinted;
+ tuple_compare_with_key_hinted_t tuple_compare_with_key_hinted;
bool is_nullable;
bool has_optional_parts;
bool has_json_paths;
@@ -1221,11 +1341,236 @@ static struct {
/* }}} tuple_compare_with_key */
+static inline hint_t
+tuple_hint_new(enum mp_class type, uint64_t val)
+{
+ assert(((uint64_t)type >> (sizeof(hint_t) * CHAR_BIT - HINT_VALUE_BITS)) == 0);
+ assert(val >> HINT_VALUE_BITS == 0);
+ return (hint_t)(((uint64_t)type << HINT_VALUE_BITS) | val);
+}
+
+static int
+hint_cmp(hint_t hint_a, hint_t hint_b)
+{
+ if (hint_a != HINT_NONE && hint_b != HINT_NONE && hint_a != hint_b)
+ return hint_a < hint_b ? -1 : 1;
+ else
+ return 0;
+}
+
+static hint_t
+field_hint_unsigned(const char *field)
+{
+ assert(mp_typeof(*field) == MP_UINT);
+ uint64_t val = mp_decode_uint(&field);
+ if (val > HINT_MAX)
+ val = HINT_MAX;
+ uint64_t ret = val - (uint64_t)HINT_MIN;
+ return tuple_hint_new(MP_CLASS_NUMBER, ret);
+}
+
+static hint_t
+field_hint_integer(const char *field)
+{
+ switch (mp_typeof(*field)) {
+ case MP_INT: {
+ int64_t val = mp_decode_int(&field);
+ if (val > HINT_MAX)
+ val = HINT_MAX;
+ else if (val < HINT_MIN)
+ val = HINT_MIN;
+ uint64_t ret = (uint64_t)val - (uint64_t)HINT_MIN;
+ return tuple_hint_new(MP_CLASS_NUMBER, ret);
+ }
+ case MP_UINT:
+ return field_hint_unsigned(field);
+ default:
+ unreachable();
+ }
+ return HINT_NONE;
+}
+
+static hint_t
+field_hint_number(const char *field)
+{
+ enum mp_type type = mp_typeof(*field);
+ switch (type) {
+ case MP_FLOAT:
+ case MP_DOUBLE: {
+ double f = type == MP_FLOAT ?
+ mp_decode_float(&field) : mp_decode_double(&field);
+ if (!isfinite(f))
+ return HINT_NONE;
+ uint64_t ret;
+ if (f > exp2(HINT_VALUE_BITS - 1))
+ ret = (uint64_t)HINT_MAX - (uint64_t)HINT_MIN;
+ else if (f < -exp2(HINT_VALUE_BITS - 1))
+ ret = 0;
+ else {
+ double val;
+ (void)modf(f, &val);
+ ret = (uint64_t)val - (uint64_t)HINT_MIN;
+ }
+ return tuple_hint_new(MP_CLASS_NUMBER, ret);
+ }
+ case MP_UINT:
+ return field_hint_unsigned(field);
+ case MP_INT:
+ return field_hint_integer(field);
+ default:
+ unreachable();
+ }
+ return HINT_NONE;
+}
+
+static hint_t
+field_hint_boolean(const char *field)
+{
+ assert(mp_typeof(*field) == MP_BOOL);
+ return tuple_hint_new(MP_CLASS_BOOL, mp_decode_bool(&field) ? 1 : 0);
+}
+
+static uint64_t
+memory_buffer_hint_val(const unsigned char *raw, uint32_t size)
+{
+ int process_len = MIN((int)size, 7);
+ uint64_t result = 0;
+ for (int i = 0; i < process_len; i++) {
+ result <<= CHAR_BIT;
+ result |= raw[i];
+ }
+ result <<= CHAR_BIT * (7 - process_len);
+ return result;
+}
+
+template <bool has_collation>
+static hint_t
+field_hint_string(const char *field, struct coll *coll)
+{
+ assert(has_collation == (coll != NULL));
+ assert(mp_typeof(*field) == MP_STR);
+ char buff[7];
+ uint32_t len;
+ const char *str = mp_decode_str(&field, &len);
+ if (has_collation) {
+ len = coll->get_sort_key(str, len, buff, sizeof(buff), coll);
+ str = buff;
+ }
+ uint64_t ret = memory_buffer_hint_val((const unsigned char *)str, len);
+ return tuple_hint_new(MP_CLASS_STR, ret);
+}
+
+template <bool has_collation>
+static hint_t
+field_hint_scalar(const char *field, struct coll *coll)
+{
+ switch (mp_classof(mp_typeof(*field))) {
+ case MP_CLASS_NUMBER:
+ return field_hint_number(field);
+ case MP_CLASS_BOOL:
+ return field_hint_boolean(field);
+ case MP_CLASS_STR:
+ return field_hint_string<has_collation>(field, coll);
+ case MP_CLASS_BIN: {
+ assert(coll == NULL);
+ uint32_t size;
+ const unsigned char *raw =
+ (const unsigned char *)mp_decode_bin(&field, &size);
+ uint64_t ret = memory_buffer_hint_val(raw, size);
+ return tuple_hint_new(MP_CLASS_BIN, ret);
+ }
+ default:
+ unreachable();
+ }
+ return HINT_NONE;
+}
+
+template <enum field_type type, bool is_nullable, bool has_collation>
+static hint_t
+field_hint(const char *field, struct key_def *key_def)
+{
+ assert(type == key_def->parts->type);
+ assert(key_part_is_nullable(key_def->parts) == is_nullable);
+ assert(has_collation == (key_def->parts->coll != NULL));
+ switch (type) {
+ case FIELD_TYPE_UNSIGNED:
+ return field_hint_unsigned(field);
+ case FIELD_TYPE_INTEGER:
+ return field_hint_integer(field);
+ case FIELD_TYPE_NUMBER:
+ return field_hint_number(field);
+ case FIELD_TYPE_BOOLEAN:
+ return field_hint_boolean(field);
+ case FIELD_TYPE_STRING:
+ return field_hint_string<has_collation>(field,
+ key_def->parts->coll);
+ case FIELD_TYPE_SCALAR:
+ return field_hint_scalar<has_collation>(field,
+ key_def->parts->coll);
+ default:
+ unreachable();
+ }
+ return HINT_NONE;
+}
+
+template <enum field_type type, bool is_nullable, bool has_collation>
+static hint_t
+key_hint(const char *key, struct key_def *key_def)
+{
+ if (key == NULL || (is_nullable && mp_typeof(*key) == MP_NIL))
+ return tuple_hint_new(MP_CLASS_NIL, 0);
+ return field_hint<type, is_nullable, has_collation>(key, key_def);
+}
+
+template <enum field_type type, bool is_nullable, bool has_collation>
+static hint_t
+tuple_hint(const struct tuple *tuple, struct key_def *key_def)
+{
+ const char *field = tuple_field_by_part(tuple, key_def->parts);
+ if (is_nullable && (field == NULL || mp_typeof(*field) == MP_NIL))
+ return tuple_hint_new(MP_CLASS_NIL, 0);
+ return field_hint<type, is_nullable, has_collation>(field, key_def);
+}
+
+#define HINT(...) { \
+ tuple_hint<__VA_ARGS__>, key_hint<__VA_ARGS__>, __VA_ARGS__ }
+
+static const struct {
+ tuple_hint_t tuple_hint;
+ key_hint_t key_hint;
+ enum field_type type;
+ bool is_nullable;
+ bool has_collation;
+} hint_arr[] = {
+ HINT(FIELD_TYPE_UNSIGNED, false, false),
+ HINT(FIELD_TYPE_STRING, false, false),
+ HINT(FIELD_TYPE_NUMBER, false, false),
+ HINT(FIELD_TYPE_INTEGER, false, false),
+ HINT(FIELD_TYPE_BOOLEAN, false, false),
+ HINT(FIELD_TYPE_SCALAR, false, false),
+ HINT(FIELD_TYPE_UNSIGNED, true, false),
+ HINT(FIELD_TYPE_STRING, true, false),
+ HINT(FIELD_TYPE_NUMBER, true, false),
+ HINT(FIELD_TYPE_INTEGER, true, false),
+ HINT(FIELD_TYPE_BOOLEAN, true, false),
+ HINT(FIELD_TYPE_SCALAR, true, false),
+ HINT(FIELD_TYPE_STRING, false, true),
+ HINT(FIELD_TYPE_SCALAR, false, true),
+ HINT(FIELD_TYPE_STRING, true, true),
+ HINT(FIELD_TYPE_SCALAR, true, true)
+};
+
+#undef HINT
+
void
key_def_set_compare_func(struct key_def *def)
{
def->tuple_compare = NULL;
def->tuple_compare_with_key = NULL;
+ def->tuple_compare_hinted = NULL;
+ def->tuple_compare_with_key_hinted = NULL;
+ def->key_hint = NULL;
+ def->tuple_hint = NULL;
if (!def->is_nullable && !key_def_has_collation(def) &&
!def->has_json_paths) {
/* Precalculated comparators don't use collation */
@@ -1242,6 +1587,8 @@ key_def_set_compare_func(struct key_def *def)
if (i == def->part_count &&
precompiled_cmp_arr[k].p[i * 2] == UINT32_MAX) {
def->tuple_compare = precompiled_cmp_arr[k].f;
+ def->tuple_compare_hinted =
+ precompiled_cmp_arr[k].f_hinted;
break;
}
}
@@ -1258,6 +1605,8 @@ key_def_set_compare_func(struct key_def *def)
if (i == def->part_count) {
def->tuple_compare_with_key =
precompiled_cmp_wk_arr[k].f;
+ def->tuple_compare_with_key_hinted =
+ precompiled_cmp_wk_arr[k].f_hinted;
break;
}
}
@@ -1274,11 +1623,16 @@ key_def_set_compare_func(struct key_def *def)
if (def->tuple_compare == NULL) {
def->tuple_compare =
cmp_arr[k].tuple_compare;
+ def->tuple_compare_hinted =
+ cmp_arr[k].tuple_compare_hinted;
}
if (def->tuple_compare_with_key == NULL) {
def->tuple_compare_with_key =
cmp_arr[k].
tuple_compare_with_key;
+ def->tuple_compare_with_key_hinted =
+ cmp_arr[k].
+ tuple_compare_with_key_hinted;
}
break;
}
@@ -1286,4 +1640,14 @@ key_def_set_compare_func(struct key_def *def)
}
assert(def->tuple_compare != NULL &&
def->tuple_compare_with_key != NULL);
+ for (uint32_t k = 0; k < sizeof(hint_arr) / sizeof(hint_arr[0]); k++) {
+ if (def->parts->type == hint_arr[k].type &&
+ key_part_is_nullable(def->parts) ==
+ hint_arr[k].is_nullable &&
+ (def->parts->coll != NULL) == hint_arr[k].has_collation) {
+ def->key_hint = hint_arr[k].key_hint;
+ def->tuple_hint = hint_arr[k].tuple_hint;
+ break;
+ }
+ }
}
diff --git a/src/lib/coll/coll.c b/src/lib/coll/coll.c
index afc15e809..d110b156b 100644
--- a/src/lib/coll/coll.c
+++ b/src/lib/coll/coll.c
@@ -133,6 +133,33 @@ coll_bin_hash(const char *s, size_t s_len, uint32_t *ph, uint32_t *pcarry,
return s_len;
}
+int
+coll_icu_get_sort_key(const char *s, size_t s_len, char *buff, size_t buff_len,
+ struct coll *coll)
+{
+ assert(coll->type == COLL_TYPE_ICU);
+ UCharIterator itr;
+ uiter_setUTF8(&itr, s, s_len);
+ uint32_t state[2] = {0, 0};
+ UErrorCode status = U_ZERO_ERROR;
+ int32_t got = ucol_nextSortKeyPart(coll->collator, &itr, state,
+ (uint8_t *)buff, buff_len, &status);
+ assert(got >= 0 && (size_t)got <= buff_len);
+ assert(U_SUCCESS(status));
+ return got;
+}
+
+int
+coll_bin_get_sort_key(const char *s, size_t s_len, char *buff, size_t buff_len,
+ struct coll *coll)
+{
+ (void)coll;
+ assert(coll->type == COLL_TYPE_BINARY);
+ int to_copy = (int)MIN(s_len, buff_len);
+ memcpy(buff, s, to_copy);
+ return to_copy;
+}
+
/**
* Set up ICU collator and init cmp and hash members of collation.
* @param coll Collation to set up.
@@ -242,6 +269,7 @@ coll_icu_init_cmp(struct coll *coll, const struct coll_def *def)
}
coll->cmp = coll_icu_cmp;
coll->hash = coll_icu_hash;
+ coll->get_sort_key = coll_icu_get_sort_key;
return 0;
}
@@ -356,6 +384,7 @@ coll_new(const struct coll_def *def)
coll->collator = NULL;
coll->cmp = coll_bin_cmp;
coll->hash = coll_bin_hash;
+ coll->get_sort_key = coll_bin_get_sort_key;
break;
default:
unreachable();
diff --git a/src/lib/coll/coll.h b/src/lib/coll/coll.h
index 8c9f94293..a68668ec5 100644
--- a/src/lib/coll/coll.h
+++ b/src/lib/coll/coll.h
@@ -48,6 +48,9 @@ typedef int (*coll_cmp_f)(const char *s, size_t s_len, const char *t,
typedef uint32_t (*coll_hash_f)(const char *s, size_t s_len, uint32_t *ph,
uint32_t *pcarry, struct coll *coll);
+typedef int (*coll_get_sort_key_f)(const char *s, size_t s_len, char *buff,
+ size_t buff_len, struct coll *coll);
+
struct UCollator;
/**
@@ -62,6 +65,8 @@ struct coll {
/** String comparator. */
coll_cmp_f cmp;
coll_hash_f hash;
+ /** Fill memory buffer with data. */
+ coll_get_sort_key_f get_sort_key;
/** Reference counter. */
int refs;
/**
diff --git a/test/engine/ddl.result b/test/engine/ddl.result
index 8d34d5ef4..1791138c6 100644
--- a/test/engine/ddl.result
+++ b/test/engine/ddl.result
@@ -1935,6 +1935,186 @@ s:drop()
---
...
--
+-- gh-3961: Introduce tuple comparison hints
+--
+s = box.schema.space.create('test', {engine = engine})
+---
+...
+pk = s:create_index('pk')
+---
+...
+i1 = s:create_index('i1', {unique = true, parts = {2, 'scalar'}})
+---
+...
+bdbl = (2.1)^62;
+---
+...
+nbdbl = -bdbl
+---
+...
+_ = s:insert{0, bdbl}
+---
+...
+_ = s:insert{1, nbdbl}
+---
+...
+_ = s:insert{2, -2.3}
+---
+...
+_ = s:insert{3, -2}
+---
+...
+_ = s:insert{4, -1.3}
+---
+...
+_ = s:insert{5, -1}
+---
+...
+_ = s:insert{6, 0}
+---
+...
+_ = s:insert{7, 1}
+---
+...
+_ = s:insert{8, 1.3}
+---
+...
+_ = s:insert{9, 2}
+---
+...
+_ = s:insert{10, 2.3}
+---
+...
+i1:select()
+---
+- - [1, -9.4972150816945e+19]
+ - [2, -2.3]
+ - [3, -2]
+ - [4, -1.3]
+ - [5, -1]
+ - [6, 0]
+ - [7, 1]
+ - [8, 1.3]
+ - [9, 2]
+ - [10, 2.3]
+ - [0, 9.4972150816945e+19]
+...
+i1:alter{parts = {2, 'number'}}
+---
+...
+_ = s:insert{11, -1.2}
+---
+...
+_ = s:insert{12, 1.2}
+---
+...
+_ = s:insert{13, -5}
+---
+...
+_ = s:insert{14, 5}
+---
+...
+i1:select()
+---
+- - [1, -9.4972150816945e+19]
+ - [13, -5]
+ - [2, -2.3]
+ - [3, -2]
+ - [4, -1.3]
+ - [11, -1.2]
+ - [5, -1]
+ - [6, 0]
+ - [7, 1]
+ - [12, 1.2]
+ - [8, 1.3]
+ - [9, 2]
+ - [10, 2.3]
+ - [14, 5]
+ - [0, 9.4972150816945e+19]
+...
+_ = i1:delete({-2.3})
+---
+...
+_ = i1:delete({-1.3})
+---
+...
+_ = i1:delete({1.3})
+---
+...
+_ = i1:delete({2.3})
+---
+...
+_ = i1:delete({-1.2})
+---
+...
+_ = i1:delete({1.2})
+---
+...
+_ = i1:delete({bdbl})
+---
+...
+_ = i1:delete({nbdbl})
+---
+...
+i1:alter{parts = {2, 'integer'}}
+---
+...
+_ = s:insert{15, -4}
+---
+...
+_ = s:insert{16, 4}
+---
+...
+i1:select()
+---
+- - [13, -5]
+ - [15, -4]
+ - [3, -2]
+ - [5, -1]
+ - [6, 0]
+ - [7, 1]
+ - [9, 2]
+ - [16, 4]
+ - [14, 5]
+...
+_ = i1:delete({-5})
+---
+...
+_ = i1:delete({-4})
+---
+...
+_ = i1:delete({-2})
+---
+...
+_ = i1:delete({-1})
+---
+...
+i1:alter{parts = {2, 'unsigned'}}
+---
+...
+_ = s:insert({17, 10})
+---
+...
+i1:alter{parts = {2, 'scalar'}}
+---
+...
+_ = s:insert({18, 1.1})
+---
+...
+i1:select()
+---
+- - [6, 0]
+ - [7, 1]
+ - [18, 1.1]
+ - [9, 2]
+ - [16, 4]
+ - [14, 5]
+ - [17, 10]
+...
+s:drop()
+---
+...
+--
-- Creating/altering a secondary index of a non-empty space.
--
s = box.schema.space.create('test', {engine = engine})
diff --git a/test/engine/ddl.test.lua b/test/engine/ddl.test.lua
index cdaf7a5bf..a73075498 100644
--- a/test/engine/ddl.test.lua
+++ b/test/engine/ddl.test.lua
@@ -710,6 +710,55 @@ _ = s:create_index('sk', {parts = {2, 'unsigned'}})
c:get()
s:drop()
+--
+-- gh-3961: Introduce tuple comparison hints
+--
+s = box.schema.space.create('test', {engine = engine})
+pk = s:create_index('pk')
+i1 = s:create_index('i1', {unique = true, parts = {2, 'scalar'}})
+bdbl = (2.1)^62;
+nbdbl = -bdbl
+_ = s:insert{0, bdbl}
+_ = s:insert{1, nbdbl}
+_ = s:insert{2, -2.3}
+_ = s:insert{3, -2}
+_ = s:insert{4, -1.3}
+_ = s:insert{5, -1}
+_ = s:insert{6, 0}
+_ = s:insert{7, 1}
+_ = s:insert{8, 1.3}
+_ = s:insert{9, 2}
+_ = s:insert{10, 2.3}
+i1:select()
+i1:alter{parts = {2, 'number'}}
+_ = s:insert{11, -1.2}
+_ = s:insert{12, 1.2}
+_ = s:insert{13, -5}
+_ = s:insert{14, 5}
+i1:select()
+_ = i1:delete({-2.3})
+_ = i1:delete({-1.3})
+_ = i1:delete({1.3})
+_ = i1:delete({2.3})
+_ = i1:delete({-1.2})
+_ = i1:delete({1.2})
+_ = i1:delete({bdbl})
+_ = i1:delete({nbdbl})
+i1:alter{parts = {2, 'integer'}}
+_ = s:insert{15, -4}
+_ = s:insert{16, 4}
+i1:select()
+_ = i1:delete({-5})
+_ = i1:delete({-4})
+_ = i1:delete({-2})
+_ = i1:delete({-1})
+i1:alter{parts = {2, 'unsigned'}}
+_ = s:insert({17, 10})
+i1:alter{parts = {2, 'scalar'}}
+_ = s:insert({18, 1.1})
+i1:select()
+s:drop()
+
--
-- Creating/altering a secondary index of a non-empty space.
--
--
2.21.0
More information about the Tarantool-patches
mailing list