[PATCH v5 2/4] memtx: introduce tuple compare hint
Kirill Shcherbatov
kshcherbatov at tarantool.org
Thu Mar 7 12:44:06 MSK 2019
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.
Hints are only useful when:
* they are precalculated and stored along with the tuple;
calculation is not cheap (cheaper than tuple_compare btw) but
precalculated hints allow to compare tuples without even fetching
tuple data.
* first part of key_def is 'string'(for now)
* since hint is calculated using only the first part of key_def
(and only first several characters if it is a string) this part
must be different with high probability for every tuple pair.
Closes #3961
---
src/box/key_def.c | 1 +
src/box/key_def.h | 119 ++++++++++++
src/box/memtx_tree.c | 32 +++-
src/box/tuple_compare.cc | 381 +++++++++++++++++++++++++++++++++++++++
src/box/tuple_compare.h | 7 +
src/lib/coll/coll.c | 33 ++++
src/lib/coll/coll.h | 4 +
7 files changed, 567 insertions(+), 10 deletions(-)
diff --git a/src/box/key_def.c b/src/box/key_def.c
index d4c979aa1..771c30172 100644
--- a/src/box/key_def.c
+++ b/src/box/key_def.c
@@ -136,6 +136,7 @@ key_def_set_func(struct key_def *def)
key_def_set_compare_func(def);
key_def_set_hash_func(def);
key_def_set_extract_func(def);
+ key_def_set_cmp_aux_func(def);
}
static void
diff --git a/src/box/key_def.h b/src/box/key_def.h
index dd62f6a35..c630e6b43 100644
--- a/src/box/key_def.h
+++ b/src/box/key_def.h
@@ -115,6 +115,28 @@ struct key_part {
struct key_def;
struct tuple;
+/** Comparasion auxiliary information. */
+typedef union {
+ /**
+ * Hint is a value h(t) is calculated for tuple in terms
+ * of particular key_def that has follows rules:
+ * if h(t1) < h(t2) then t1 < t2;
+ * if h(t1) > h(t2) then t1 > t2;
+ * if t1 == t2 then h(t1) == h(t2);
+ * These rules means that instead of direct tuple vs tuple
+ * (or tuple vs key) comparison one may compare theirs
+ * hints first; and only if theirs hints are equal compare
+ * the tuples themselves.
+ */
+ uint64_t hint;
+} cmp_aux_t;
+
+/** Test if cmp_aux_t a and b are equal. */
+static inline bool
+cmp_aux_equal(cmp_aux_t a, cmp_aux_t b)
+{
+ return a.hint == b.hint;
+}
/**
* Get is_nullable property of key_part.
@@ -137,6 +159,18 @@ 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_aux_compare_with_key() */
+typedef int (*tuple_aux_compare_with_key_t)(const struct tuple *tuple,
+ cmp_aux_t tuple_cmp_aux,
+ const char *key, uint32_t part_count,
+ cmp_aux_t key_cmp_aux,
+ struct key_def *key_def);
+/** @copydoc tuple_aux_compare() */
+typedef int (*tuple_aux_compare_t)(const struct tuple *tuple_a,
+ cmp_aux_t tuple_a_cmp_aux,
+ const struct tuple *tuple_b,
+ cmp_aux_t tuple_b_cmp_aux,
+ struct key_def *key_def);
/** @copydoc tuple_extract_key() */
typedef char *(*tuple_extract_key_t)(const struct tuple *tuple,
struct key_def *key_def,
@@ -153,12 +187,23 @@ typedef uint32_t (*tuple_hash_t)(const struct tuple *tuple,
typedef uint32_t (*key_hash_t)(const char *key,
struct key_def *key_def);
+/** @copydoc tuple_cmp_aux() */
+typedef cmp_aux_t (*tuple_cmp_aux_t)(const struct tuple *tuple,
+ struct key_def *key_def);
+
+/** @copydoc key_cmp_aux() */
+typedef cmp_aux_t (*key_cmp_aux_t)(const char *key, struct key_def *key_def);
+
/* Definition of a multipart key. */
struct key_def {
/** @see tuple_compare() */
tuple_compare_t tuple_compare;
/** @see tuple_compare_with_key() */
tuple_compare_with_key_t tuple_compare_with_key;
+ /** @see tuple_aux_compare_with_key() */
+ tuple_aux_compare_with_key_t tuple_aux_compare_with_key;
+ /** @see tuple_aux_compare() */
+ tuple_aux_compare_t tuple_aux_compare;
/** @see tuple_extract_key() */
tuple_extract_key_t tuple_extract_key;
/** @see tuple_extract_key_raw() */
@@ -167,6 +212,10 @@ struct key_def {
tuple_hash_t tuple_hash;
/** @see key_hash() */
key_hash_t key_hash;
+ /** @see tuple_cmp_aux() */
+ tuple_cmp_aux_t tuple_cmp_aux;
+ /** @see key_cmp_aux() */
+ key_cmp_aux_t key_cmp_aux;
/**
* Minimal part count which always is unique. For example,
* if a secondary index is unique, then
@@ -571,6 +620,52 @@ 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 comparasion
+ * auxillary information.
+ * @param tuple_a First tuple.
+ * @param tuple_a_cmp_aux Comparasion auxiliary information
+ * for the tuple_a.
+ * @param tuple_b Second tuple.
+ * @param tuple_b_cmp_aux Comparasion auxilary information
+ * for the 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_aux_compare(const struct tuple *tuple_a, cmp_aux_t tuple_a_cmp_aux,
+ const struct tuple *tuple_b, cmp_aux_t tuple_b_cmp_aux,
+ struct key_def *key_def)
+{
+ return key_def->tuple_aux_compare(tuple_a, tuple_a_cmp_aux, tuple_b,
+ tuple_b_cmp_aux, key_def);
+}
+
+/**
+ * Compare tuple with key using the key definition and
+ * comparasion auxilary information.
+ * @param tuple tuple
+ * @param tuple_cmp_aux tuple compare auxiliary information.
+ * @param key key parts without MessagePack array header
+ * @param part_count the number of parts in @a key
+ * @param key_cmp_aux t Key compare auxiliary information.
+ * @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_aux_compare_with_key(const struct tuple *tuple, cmp_aux_t tuple_cmp_aux,
+ const char *key, uint32_t part_count,
+ cmp_aux_t key_cmp_aux, struct key_def *key_def)
+{
+ return key_def->tuple_aux_compare_with_key(tuple, tuple_cmp_aux, key,
+ part_count, key_cmp_aux,
+ key_def);
+}
+
/**
* Compute hash of a tuple field.
* @param ph1 - pointer to running hash
@@ -624,6 +719,30 @@ key_hash(const char *key, struct key_def *key_def)
return key_def->key_hash(key, key_def);
}
+ /*
+ * Get a comparison auxiliary information for a tuple.
+ * @param tuple - tuple to get cmp_aux_t of.
+ * @param key_def - key_def that defines which comparison is used.
+ * @return the comparison auxiliary information.
+ */
+static inline cmp_aux_t
+tuple_cmp_aux(const struct tuple *tuple, struct key_def *key_def)
+{
+ return key_def->tuple_cmp_aux(tuple, key_def);
+}
+
+/**
+ * Get a comparison hint of a key.
+ * @param key - key to get hint of.
+ * @param key_def - key_def that defines which comparison is used.
+ * @return the comparison auxiliary information.
+ */
+static inline cmp_aux_t
+key_cmp_aux(const char *key, struct key_def *key_def)
+{
+ return key_def->key_cmp_aux(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 688f09597..4b0886bef 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 auxilary information. */
+ cmp_aux_t aux_info;
};
/**
@@ -55,6 +57,8 @@ struct memtx_tree_key_data {
struct memtx_tree_data {
/* Tuple that this node is represents. */
struct tuple *tuple;
+ /** Comparison auxilary information. */
+ cmp_aux_t aux_info;
};
/**
@@ -69,7 +73,7 @@ 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 && cmp_aux_equal(a->aux_info, b->aux_info);
}
/**
@@ -91,6 +95,7 @@ memtx_tree_data_set(struct memtx_tree_data *data, struct tuple *tuple,
{
(void)key_def;
data->tuple = tuple;
+ data->aux_info = tuple_cmp_aux(tuple, key_def);
}
/**
@@ -103,15 +108,18 @@ memtx_tree_key_data_set(struct memtx_tree_key_data *key_data, const char *key,
(void)key_def;
key_data->key = key;
key_data->part_count = part_count;
+ key_data->aux_info = key_cmp_aux(key, key_def);
}
#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_aux_compare((&a)->tuple, (&a)->aux_info, (&b)->tuple,\
+ (&b)->aux_info, arg)
#define BPS_TREE_COMPARE_KEY(a, b, arg)\
- tuple_compare_with_key((&a)->tuple, (b)->key, (b)->part_count, arg)
+ tuple_aux_compare_with_key((&a)->tuple, (&a)->aux_info, (b)->key,\
+ (b)->part_count, (b)->aux_info, 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 *
@@ -146,7 +154,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_aux_compare(data_a->tuple, data_a->aux_info, data_b->tuple,
+ data_b->aux_info, key_def);
}
/* {{{ MemtxTree Iterators ****************************************/
@@ -268,9 +277,10 @@ 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_aux_compare_with_key(res->tuple, res->aux_info,
+ it->key_data.key, it->key_data.part_count,
+ it->key_data.aux_info,
+ it->index_def->key_def) != 0) {
iterator->next = tree_iterator_dummie;
memtx_tree_data_clear(&it->current);
*ret = NULL;
@@ -299,9 +309,10 @@ 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_aux_compare_with_key(res->tuple, res->aux_info,
+ it->key_data.key, it->key_data.part_count,
+ it->key_data.aux_info,
+ it->index_def->key_def) != 0) {
iterator->next = tree_iterator_dummie;
memtx_tree_data_clear(&it->current);
*ret = NULL;
@@ -549,6 +560,7 @@ 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 memtx_tree_key_data key_data;
struct key_def *cmp_def = memtx_tree_index_cmp_def(index);
memtx_tree_key_data_set(&key_data, key, part_count, cmp_def);
diff --git a/src/box/tuple_compare.cc b/src/box/tuple_compare.cc
index cf4519ccb..5b06e06b3 100644
--- a/src/box/tuple_compare.cc
+++ b/src/box/tuple_compare.cc
@@ -1323,9 +1323,390 @@ tuple_compare_with_key_create(const struct key_def *def)
/* }}} tuple_compare_with_key */
+/* {{{ tuple_aux_compare */
+
+#define CMP_HINT_INVALID ((uint64_t)UINT64_MAX)
+
+static int
+tuple_hinted_compare(const struct tuple *tuple_a, cmp_aux_t tuple_a_cmp_aux,
+ const struct tuple *tuple_b, cmp_aux_t tuple_b_cmp_aux,
+ struct key_def *key_def)
+{
+ uint64_t tuple_a_hint = tuple_a_cmp_aux.hint;
+ uint64_t tuple_b_hint = tuple_b_cmp_aux.hint;
+ if (likely(tuple_a_hint != tuple_b_hint &&
+ tuple_a_hint != CMP_HINT_INVALID &&
+ tuple_b_hint != CMP_HINT_INVALID))
+ return tuple_a_hint < tuple_b_hint ? -1 : 1;
+ else
+ return tuple_compare(tuple_a, tuple_b, key_def);
+}
+
+static tuple_aux_compare_t
+tuple_aux_compare_create(const struct key_def *def)
+{
+ (void)def;
+ return tuple_hinted_compare;
+}
+
+/* }}} tuple_aux_compare */
+
+/* {{{ tuple_aux_compare_with_key */
+
+static int
+tuple_hinted_compare_with_key(const struct tuple *tuple, cmp_aux_t tuple_cmp_aux,
+ const char *key, uint32_t part_count,
+ cmp_aux_t key_cmp_aux, struct key_def *key_def)
+{
+ uint64_t tuple_hint = tuple_cmp_aux.hint;
+ uint64_t key_hint = key_cmp_aux.hint;
+ if (likely(tuple_hint != key_hint && tuple_hint != CMP_HINT_INVALID &&
+ key_hint != CMP_HINT_INVALID))
+ return tuple_hint < key_hint ? -1 : 1;
+ else
+ return tuple_compare_with_key(tuple, key, part_count, key_def);
+}
+
+static tuple_aux_compare_with_key_t
+tuple_aux_compare_with_key_create(const struct key_def *def)
+{
+ (void)def;
+ return tuple_hinted_compare_with_key;
+}
+
+/* }}} tuple_aux_compare_with_key */
+
void
key_def_set_compare_func(struct key_def *def)
{
def->tuple_compare = tuple_compare_create(def);
def->tuple_compare_with_key = tuple_compare_with_key_create(def);
+ def->tuple_aux_compare = tuple_aux_compare_create(def);
+ def->tuple_aux_compare_with_key =
+ tuple_aux_compare_with_key_create(def);
+}
+
+/* Tuple hints */
+
+static cmp_aux_t
+key_hint_default(const char *key, struct key_def *key_def)
+{
+ (void)key;
+ (void)key_def;
+ cmp_aux_t ret;
+ ret.hint = CMP_HINT_INVALID;
+ return ret;
+}
+
+static cmp_aux_t
+tuple_hint_default(const struct tuple *tuple, struct key_def *key_def)
+{
+ (void)tuple;
+ (void)key_def;
+ cmp_aux_t ret;
+ ret.hint = CMP_HINT_INVALID;
+ return ret;
+}
+
+template<bool is_nullable>
+static cmp_aux_t
+key_hint_uint(const char *key, struct key_def *key_def)
+{
+ (void)key_def;
+ assert(key_part_is_nullable(key_def->parts) == is_nullable);
+ assert(key_def->parts->type == FIELD_TYPE_UNSIGNED);
+ cmp_aux_t ret;
+ if (key == NULL || (is_nullable && mp_typeof(*key) == MP_NIL)) {
+ ret.hint = 0;
+ return ret;
+ }
+ assert(mp_typeof(*key) == MP_UINT);
+ uint64_t val = mp_decode_uint(&key);
+ ret.hint = unlikely(val > INT64_MAX) ? INT64_MAX :
+ val - (uint64_t)INT64_MIN;;
+ return ret;
+}
+
+template<bool is_nullable>
+static cmp_aux_t
+tuple_hint_uint(const struct tuple *tuple, struct key_def *key_def)
+{
+ assert(key_part_is_nullable(key_def->parts) == is_nullable);
+ assert(key_def->parts->type == FIELD_TYPE_UNSIGNED);
+ cmp_aux_t ret;
+ const char *field = tuple_field_by_part(tuple, key_def->parts);
+ if (is_nullable && field == NULL) {
+ ret.hint = 0;
+ return ret;
+ }
+ return key_hint_uint<is_nullable>(field, key_def);
+}
+
+template<bool is_nullable>
+static cmp_aux_t
+key_hint_int(const char *key, struct key_def *key_def)
+{
+ (void)key_def;
+ assert(key_part_is_nullable(key_def->parts) == is_nullable);
+ assert(key_def->parts->type == FIELD_TYPE_INTEGER);
+ cmp_aux_t ret;
+ if (key == NULL || (is_nullable && mp_typeof(*key) == MP_NIL)) {
+ ret.hint = 0;
+ return ret;
+ }
+ if (mp_typeof(*key) == MP_UINT) {
+ uint64_t val = mp_decode_uint(&key);
+ ret.hint = unlikely(val > INT64_MAX) ? INT64_MAX :
+ val - (uint64_t)INT64_MIN;
+ } else {
+ assert(mp_typeof(*key) == MP_INT);
+ int64_t val = mp_decode_int(&key);
+ ret.hint = (uint64_t)val - (uint64_t)INT64_MIN;
+ }
+ return ret;
+}
+
+template<bool is_nullable>
+static cmp_aux_t
+tuple_hint_int(const struct tuple *tuple, struct key_def *key_def)
+{
+ assert(key_part_is_nullable(key_def->parts) == is_nullable);
+ assert(key_def->parts->type == FIELD_TYPE_INTEGER);
+ cmp_aux_t ret;
+ const char *field = tuple_field_by_part(tuple, key_def->parts);
+ if (is_nullable && field == NULL) {
+ ret.hint = 0;
+ return ret;
+ }
+ return key_hint_int<is_nullable>(field, key_def);
+}
+
+template<bool is_nullable>
+static cmp_aux_t
+key_hint_number(const char *key, struct key_def *key_def)
+{
+ (void)key_def;
+ assert(key_part_is_nullable(key_def->parts) == is_nullable);
+ assert(key_def->parts->type == FIELD_TYPE_NUMBER);
+ cmp_aux_t ret;
+ if (key == NULL || (is_nullable && mp_typeof(*key) == MP_NIL)) {
+ ret.hint = 0;
+ return ret;
+ }
+ uint64_t val = 0;
+ switch (mp_typeof(*key)) {
+ case MP_FLOAT:
+ case MP_DOUBLE: {
+ double f = mp_typeof(*key) == MP_FLOAT ?
+ mp_decode_float(&key) : mp_decode_double(&key);
+ if (isnan(f) || isinf(f)) {
+ ret.hint = CMP_HINT_INVALID;
+ return ret;
+ }
+ double ival;
+ (void)modf(f, &ival);
+ if (unlikely(ival >= (double)INT64_MAX)) {
+ ret.hint = INT64_MAX;
+ return ret;
+ }
+ if (unlikely(ival <= (double)INT64_MIN)) {
+ ret.hint = 0;
+ return ret;
+ }
+ val = (uint64_t)ival;
+ break;
+ }
+ case MP_INT: {
+ val = (uint64_t)mp_decode_int(&key);
+ break;
+ }
+ case MP_UINT: {
+ val = mp_decode_uint(&key);
+ if (val > INT64_MAX) {
+ ret.hint = INT64_MAX;
+ return ret;
+ }
+ break;
+ }
+ default:
+ unreachable();
+ }
+ ret.hint = val - (uint64_t)INT64_MIN;
+ return ret;
+}
+
+template<bool is_nullable>
+static cmp_aux_t
+tuple_hint_number(const struct tuple *tuple, struct key_def *key_def)
+{
+ assert(key_part_is_nullable(key_def->parts) == is_nullable);
+ assert(key_def->parts->type == FIELD_TYPE_NUMBER);
+ cmp_aux_t ret;
+ const char *field = tuple_field_by_part(tuple, key_def->parts);
+ if (is_nullable && field == NULL) {
+ ret.hint = 0;
+ return ret;
+ }
+ return key_hint_number<is_nullable>(field, key_def);
+}
+
+template<bool is_nullable>
+static cmp_aux_t
+key_hint_boolean(const char *key, struct key_def *key_def)
+{
+ (void)key_def;
+ assert(key_part_is_nullable(key_def->parts) == is_nullable);
+ assert(key_def->parts->type == FIELD_TYPE_BOOLEAN);
+ cmp_aux_t ret;
+ if (key == NULL || (is_nullable && mp_typeof(*key) == MP_NIL)) {
+ ret.hint = 0;
+ return ret;
+ }
+ bool val = mp_decode_bool(&key);
+ ret.hint = (uint64_t)val - (uint64_t)INT64_MIN;
+ return ret;
+}
+
+template<bool is_nullable>
+static cmp_aux_t
+tuple_hint_boolean(const struct tuple *tuple, struct key_def *key_def)
+{
+ assert(key_part_is_nullable(key_def->parts) == is_nullable);
+ assert(key_def->parts->type == FIELD_TYPE_BOOLEAN);
+ const char *field = tuple_field_by_part(tuple, key_def->parts);
+ cmp_aux_t ret;
+ if (is_nullable && field == NULL) {
+ ret.hint = 0;
+ return ret;
+ }
+ return key_hint_boolean<is_nullable>(field, key_def);
+}
+
+template<bool is_nullable>
+static cmp_aux_t
+key_hint_string(const char *key, struct key_def *key_def)
+{
+ (void)key_def;
+ assert(key_part_is_nullable(key_def->parts) == is_nullable);
+ assert(key_def->parts->coll == NULL);
+ assert(key_def->parts->type == FIELD_TYPE_STRING);
+ cmp_aux_t ret;
+ if (key == NULL || (is_nullable && mp_typeof(*key) == MP_NIL)) {
+ ret.hint = 0;
+ return ret;
+ }
+ assert(mp_typeof(*key) == MP_STR);
+ uint32_t len;
+ const unsigned char *str =
+ (const unsigned char *)mp_decode_str(&key, &len);
+ uint64_t result = 0;
+ uint32_t process_len = MIN(len, 8);
+ for (uint32_t i = 0; i < process_len; i++) {
+ result <<= 8;
+ result |= str[i];
+ }
+ result <<= 8 * (8 - process_len);
+ ret.hint = result;
+ return ret;
+}
+
+template<bool is_nullable>
+static cmp_aux_t
+tuple_hint_string(const struct tuple *tuple, struct key_def *key_def)
+{
+ assert(key_part_is_nullable(key_def->parts) == is_nullable);
+ assert(key_def->parts->coll == NULL);
+ assert(key_def->parts->type == FIELD_TYPE_STRING);
+ cmp_aux_t ret;
+ const char *field = tuple_field_by_part(tuple, key_def->parts);
+ if (is_nullable && field == NULL) {
+ ret.hint = 0;
+ return ret;
+ }
+ return key_hint_string<is_nullable>(field, key_def);
+}
+
+template<bool is_nullable>
+static cmp_aux_t
+key_hint_string_coll(const char *key, struct key_def *key_def)
+{
+ assert(key_part_is_nullable(key_def->parts) == is_nullable);
+ assert(key_def->parts->type == FIELD_TYPE_STRING &&
+ key_def->parts->coll != NULL);
+ cmp_aux_t ret;
+ if (key == NULL || (is_nullable && mp_typeof(*key) == MP_NIL)) {
+ ret.hint = 0;
+ return ret;
+ }
+ assert(mp_typeof(*key) == MP_STR);
+ uint32_t len;
+ const char *str = mp_decode_str(&key, &len);
+ ret.hint = key_def->parts->coll->hint(str, len, key_def->parts->coll);
+ return ret;
+}
+
+template<bool is_nullable>
+static cmp_aux_t
+tuple_hint_string_coll(const struct tuple *tuple, struct key_def *key_def)
+{
+ assert(key_part_is_nullable(key_def->parts) == is_nullable);
+ assert(key_def->parts->type == FIELD_TYPE_STRING &&
+ key_def->parts->coll != NULL);
+ const char *field = tuple_field_by_part(tuple, key_def->parts);
+ cmp_aux_t ret;
+ if (is_nullable && field == NULL) {
+ ret.hint = 0;
+ return ret;
+ }
+ return key_hint_string_coll<is_nullable>(field, key_def);
+}
+
+void
+key_def_set_cmp_aux_func(struct key_def *def)
+{
+ def->key_cmp_aux = key_hint_default;
+ def->tuple_cmp_aux = tuple_hint_default;
+ bool is_nullable = key_part_is_nullable(def->parts);
+ if (def->parts->type == FIELD_TYPE_STRING && def->parts->coll != NULL) {
+ def->key_cmp_aux = is_nullable ? key_hint_string_coll<true> :
+ key_hint_string_coll<false>;
+ def->tuple_cmp_aux = is_nullable ?
+ tuple_hint_string_coll<true> :
+ tuple_hint_string_coll<false>;
+ return;
+ }
+ switch (def->parts->type) {
+ case FIELD_TYPE_UNSIGNED:
+ def->key_cmp_aux = is_nullable ? key_hint_uint<true> :
+ key_hint_uint<false>;
+ def->tuple_cmp_aux = is_nullable ? tuple_hint_uint<true> :
+ tuple_hint_uint<false>;
+ break;
+ case FIELD_TYPE_INTEGER:
+ def->key_cmp_aux = is_nullable ? key_hint_int<true> :
+ key_hint_int<false>;
+ def->tuple_cmp_aux = is_nullable ? tuple_hint_int<true> :
+ tuple_hint_int<false>;
+ break;
+ case FIELD_TYPE_STRING:
+ def->key_cmp_aux = is_nullable ? key_hint_string<true> :
+ key_hint_string<false>;
+ def->tuple_cmp_aux = is_nullable ? tuple_hint_string<true> :
+ tuple_hint_string<false>;
+ break;
+ case FIELD_TYPE_NUMBER:
+ def->key_cmp_aux = is_nullable ? key_hint_number<true> :
+ key_hint_number<false>;
+ def->tuple_cmp_aux = is_nullable ? tuple_hint_number<true> :
+ tuple_hint_number<false>;
+ break;
+ case FIELD_TYPE_BOOLEAN:
+ def->key_cmp_aux = is_nullable ? key_hint_boolean<true> :
+ key_hint_boolean<false>;
+ def->tuple_cmp_aux = is_nullable ? tuple_hint_boolean<true> :
+ tuple_hint_boolean<false>;
+ break;
+ default:
+ break;
+ };
}
diff --git a/src/box/tuple_compare.h b/src/box/tuple_compare.h
index 6538d5fc0..160135af4 100644
--- a/src/box/tuple_compare.h
+++ b/src/box/tuple_compare.h
@@ -43,6 +43,13 @@ struct key_def;
void
key_def_set_compare_func(struct key_def *def);
+/**
+ * Initialize cmp_aux calculation functions for the key_def.
+ * @param key_def key definition
+ */
+void
+key_def_set_cmp_aux_func(struct key_def *def);
+
#if defined(__cplusplus)
} /* extern "C" */
#endif /* defined(__cplusplus) */
diff --git a/src/lib/coll/coll.c b/src/lib/coll/coll.c
index afc15e809..9c267d384 100644
--- a/src/lib/coll/coll.c
+++ b/src/lib/coll/coll.c
@@ -133,6 +133,37 @@ coll_bin_hash(const char *s, size_t s_len, uint32_t *ph, uint32_t *pcarry,
return s_len;
}
+/** Get a compare hint of a binary collation. */
+static uint64_t
+coll_bin_hint(const char *s, size_t s_len, struct coll *coll)
+{
+ (void)coll;
+ uint64_t result = 0;
+ uint32_t process_len = MIN(s_len, 8);
+ for (uint32_t i = 0; i < process_len; i++) {
+ result <<= 8;
+ result |= ((unsigned char *)s)[i];
+ }
+ result <<= 8 * (8 - process_len);
+ return result;
+}
+
+/** Get a compare hint of a string using ICU collation. */
+static uint64_t
+coll_icu_hint(const char *s, size_t s_len, struct coll *coll)
+{
+ assert(coll->type == COLL_TYPE_ICU);
+ UCharIterator itr;
+ uiter_setUTF8(&itr, s, s_len);
+ uint8_t buf[8];
+ uint32_t state[2] = {0, 0};
+ UErrorCode status = U_ZERO_ERROR;
+ int32_t got = ucol_nextSortKeyPart(coll->collator, &itr, state, buf,
+ sizeof(buf), &status);
+ assert(got >= 0 && got <= 8);
+ return coll_bin_hint((const char *)buf, got, NULL);
+}
+
/**
* Set up ICU collator and init cmp and hash members of collation.
* @param coll Collation to set up.
@@ -242,6 +273,7 @@ coll_icu_init_cmp(struct coll *coll, const struct coll_def *def)
}
coll->cmp = coll_icu_cmp;
coll->hash = coll_icu_hash;
+ coll->hint = coll_icu_hint;
return 0;
}
@@ -356,6 +388,7 @@ coll_new(const struct coll_def *def)
coll->collator = NULL;
coll->cmp = coll_bin_cmp;
coll->hash = coll_bin_hash;
+ coll->hint = coll_bin_hint;
break;
default:
unreachable();
diff --git a/src/lib/coll/coll.h b/src/lib/coll/coll.h
index 8c9f94293..d695a02ad 100644
--- a/src/lib/coll/coll.h
+++ b/src/lib/coll/coll.h
@@ -48,6 +48,8 @@ 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 uint64_t (*coll_hint_f)(const char *s, size_t s_len, struct coll *coll);
+
struct UCollator;
/**
@@ -62,6 +64,8 @@ struct coll {
/** String comparator. */
coll_cmp_f cmp;
coll_hash_f hash;
+ /** The pointer to routine calculating tuple hint. */
+ coll_hint_f hint;
/** Reference counter. */
int refs;
/**
--
2.21.0
More information about the Tarantool-patches
mailing list