Re: [commits] [tarantool] 02/04: vinyl: introduce bloom filters for partial key lookups

[Konstantin Osipov <kostja@tarantool.org>]

* Vladimir Davydov <vdavydov.dev@gmail.com> [18/03/21 16:36]:

> commit 5bfb2dc8c91bd9924fc6692006a69b45a532f6da
> Author: Vladimir Davydov <vdavydov.dev@gmail.com>
> AuthorDate: Fri Feb 23 23:01:24 2018 +0300
> 
>     vinyl: introduce bloom filters for partial key lookups
>     
>     Currently, we store and use bloom only for full-key lookups. However,
>     there are use cases when we can also benefit from maintaining bloom
>     filters for partial keys as well - see #3177 for example. So this patch
>     replaces the current full-key bloom filter with a multipart one, which
>     is basically a set of bloom filters, one per each sub-key.

What's a sub-key? I suggest using "partial key" or "prefix of a
full key", this is less ambiguous (remember my initial questions).

> Old bloom
>     filters stored on disk will be silently ignored. This will degrade
>     performance of existing deployments until major compaction is scheduled,
>     but this should be mitigated by #3139 (knob for forcing compaction).

Please fix this.

>     Besides, there are still no vinyl deployments in production as far as we
>     know.

Please remove this statement.

> Anyway, if there are complaints about the performance degradation,
>     we can add some code to load and use the legacy bloom filter if the new
>     one is unavailable.

No, we should not wait for complaints, and it's wrong discussing
this in a commit comment as if it was Kostja's official policy. I
use this weapon very sparingly I hope.
>     
>     When a key or tuple is checked against a multipart bloom filter, we
>     check all its sub-keys to reduce the false positive result. Nevertheless
>     there's no size optimization as per now. E.g. even if the cardinality of
>     a partial key is the same as of the full key, we will still store two
>     full-sized bloom filters although we could probably save some space in
>     this case by assuming that checking against the bloom corresponding to
>     a partial key would reduce the false positive rate of full key lookups.
>     This is addressed later in the series.
>     
>     Before this patch we used a bloom spectrum object to construct a bloom
>     filter. A bloom spectrum is basically a set of bloom filters ranging in
>     size. The point of using a spectrum is that we don't know what the run
>     size will be while we are writing it so we create 10 bloom filters and
>     choose the best of them after we are done. With the default bloom fpr of
>     0.05 it is 10 byte overhead per record, which seems to be OK. However,
>     if we try to optimize other parameters as well, e.g. the number of hash
>     functions, the cost of a spectrum will become prohibitive. Funny thing
>     is a tuple hash is only 4 bytes long, which means if we stored all
>     hashes in an array and built a bloom filter after we'd written a run, we
>     would reduce the memory footprint by more than half! And that would only
>     slightly increase the run write time as scanning a memory map of hashes
>     and constructing a bloom filter is cheap in comparison to mering runs.
>     Putting it all together, we stop using bloom spectrum in this patch,
>     instead we stash all hashes in a new bloom builder object and use them
>     to build a perfect bloom filer after the run has been written and we
>     know the cardinality of each sub key.
>     
>     Closes #3177
> ---
>  src/box/CMakeLists.txt      |   1 +
>  src/box/iproto_constants.c  |   3 +-
>  src/box/iproto_constants.h  |   4 +-
>  src/box/tuple_bloom.c       | 274 ++++++++++++++++++++++++++++++++++++++++++++
>  src/box/tuple_bloom.h       | 191 ++++++++++++++++++++++++++++++
>  src/box/tuple_compare.cc    |  24 ++++
>  src/box/tuple_compare.h     |  12 ++
>  src/box/tuple_hash.cc       |  13 ++-
>  src/box/tuple_hash.h        |  30 +++++
>  src/box/vy_run.c            | 243 +++++++++++++++------------------------
>  src/box/vy_run.h            |  23 ++--
>  src/box/vy_scheduler.c      |  20 +---
>  src/box/xlog.c              |  27 -----
>  src/box/xlog.h              |   9 --
>  test/unit/vy_point_lookup.c |   2 +-
>  test/vinyl/bloom.result     | 157 ++++++++++++++++++++++++-
>  test/vinyl/bloom.test.lua   |  68 ++++++++++-
>  test/vinyl/info.result      |  16 +--
>  18 files changed, 875 insertions(+), 242 deletions(-)
> 
> diff --git a/src/box/CMakeLists.txt b/src/box/CMakeLists.txt
> index ad7f910..cb27db7 100644
> --- a/src/box/CMakeLists.txt
> +++ b/src/box/CMakeLists.txt
> @@ -37,6 +37,7 @@ add_library(tuple STATIC
>      tuple_compare.cc
>      tuple_extract_key.cc
>      tuple_hash.cc
> +    tuple_bloom.c
>      tuple_dictionary.c
>      key_def.cc
>      coll_def.c
> diff --git a/src/box/iproto_constants.c b/src/box/iproto_constants.c
> index cd7b1d0..4a8643c 100644
> --- a/src/box/iproto_constants.c
> +++ b/src/box/iproto_constants.c
> @@ -194,7 +194,8 @@ const char *vy_run_info_key_strs[VY_RUN_INFO_KEY_MAX] = {
>  	"min lsn",
>  	"max lsn",
>  	"page count",
> -	"bloom filter"
> +	"bloom filter legacy",
> +	"bloom filter",
>  };
>  
>  const char *vy_row_index_key_strs[VY_ROW_INDEX_KEY_MAX] = {
> diff --git a/src/box/iproto_constants.h b/src/box/iproto_constants.h
> index 9518424..92534ef 100644
> --- a/src/box/iproto_constants.h
> +++ b/src/box/iproto_constants.h
> @@ -295,8 +295,10 @@ enum vy_run_info_key {
>  	VY_RUN_INFO_MAX_LSN = 4,
>  	/** Number of pages in the run. */
>  	VY_RUN_INFO_PAGE_COUNT = 5,
> +	/** Legacy bloom filter implementation. */
> +	VY_RUN_INFO_BLOOM_LEGACY = 6,
>  	/** Bloom filter for keys. */
> -	VY_RUN_INFO_BLOOM = 6,
> +	VY_RUN_INFO_BLOOM = 7,
>  	/** The last key in this enum + 1 */
>  	VY_RUN_INFO_KEY_MAX
>  };
> diff --git a/src/box/tuple_bloom.c b/src/box/tuple_bloom.c
> new file mode 100644
> index 0000000..65e9827
> --- /dev/null
> +++ b/src/box/tuple_bloom.c
> @@ -0,0 +1,274 @@
> +/*
> + * Copyright 2010-2018, Tarantool AUTHORS, please see AUTHORS file.
> + *
> + * Redistribution and use in source and binary forms, with or
> + * without modification, are permitted provided that the following
> + * conditions are met:
> + *
> + * 1. Redistributions of source code must retain the above
> + *    copyright notice, this list of conditions and the
> + *    following disclaimer.
> + *
> + * 2. Redistributions in binary form must reproduce the above
> + *    copyright notice, this list of conditions and the following
> + *    disclaimer in the documentation and/or other materials
> + *    provided with the distribution.
> + *
> + * THIS SOFTWARE IS PROVIDED BY <COPYRIGHT HOLDER> ``AS IS'' AND
> + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
> + * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
> + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
> + * <COPYRIGHT HOLDER> OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
> + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
> + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
> + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
> + * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
> + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
> + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
> + * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
> + * SUCH DAMAGE.
> + */
> +#include "tuple_bloom.h"
> +
> +#include <assert.h>
> +#include <stdbool.h>
> +#include <stddef.h>
> +#include <stdint.h>
> +#include <stdlib.h>
> +#include <string.h>
> +#include <msgpuck.h>
> +#include "diag.h"
> +#include "errcode.h"
> +#include "memory.h"
> +#include "key_def.h"
> +#include "tuple.h"
> +#include "tuple_hash.h"
> +#include "salad/bloom.h"
> +#include "trivia/util.h"
> +#include "third_party/PMurHash.h"
> +
> +enum { HASH_SEED = 13U };
> +
> +struct tuple_bloom_builder *
> +tuple_bloom_builder_new(uint32_t part_count)
> +{
> +	size_t size = sizeof(struct tuple_bloom_builder) +
> +		part_count * sizeof(struct tuple_hash_array);
> +	struct tuple_bloom_builder *builder = malloc(size);
> +	if (builder == NULL) {
> +		diag_set(OutOfMemory, size, "malloc", "tuple bloom builder");
> +		return NULL;
> +	}
> +	memset(builder, 0, size);
> +	builder->part_count = part_count;
> +	return builder;
> +}
> +
> +void
> +tuple_bloom_builder_delete(struct tuple_bloom_builder *builder)
> +{
> +	for (uint32_t i = 0; i < builder->part_count; i++)
> +		free(builder->parts[i].values);
> +	free(builder);
> +}
> +
> +int
> +tuple_bloom_builder_add(struct tuple_bloom_builder *builder,
> +			const struct tuple *tuple,
> +			const struct key_def *key_def,
> +			uint32_t hashed_parts)
> +{
> +	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_key_part(&h, &carry, tuple,
> +						  &key_def->parts[i]);

Is there a faster way to iterate over key parts?
tuple_hash_key_part() involves tuple_field(). Are you assuming
tuple_field() always has an offset map available?

> +		if (i < hashed_parts)
> +			continue;

Ugh, looks at first glance that we're invoking a hash function
and iterating over key parts only to find out the total size. 
Then I see that you also calculate the hash value and carry as
a side effect. If we can reuse hashed_parts, can't we reuse the
hash of the hashed parts and the total size? Perhaps I'm missing
something.

> +		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,
> +						   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;

Sounds like we need an array data structure after all...
Although I'd use a linked list of 4k blocks - I purposefully do not allow
introducing arrays into the source code to avoid inefficient
applications like this one. 

> +		}
> +		uint32_t hash = PMurHash32_Result(h, carry, total_size);
> +		hash_arr->values[hash_arr->count++] = hash;
> +	}
> +	return 0;
> +}
> +
> +struct tuple_bloom *
> +tuple_bloom_new(struct tuple_bloom_builder *builder, double fpr)
> +{
> +	uint32_t part_count = builder->part_count;
> +	size_t size = sizeof(struct tuple_bloom) +
> +		part_count * sizeof(struct bloom);
> +	struct tuple_bloom *bloom = malloc(size);
> +	if (bloom == NULL) {
> +		diag_set(OutOfMemory, size, "malloc", "tuple bloom");
> +		return NULL;
> +	}
> +	for (uint32_t i = 0; i < part_count; i++) {
> +		struct tuple_hash_array *hash_arr = &builder->parts[i];
> +		uint32_t count = hash_arr->count;
> +		if (bloom_create(&bloom->parts[i], count,
> +				 fpr, runtime.quota) != 0) {
> +			diag_set(OutOfMemory, 0, "bloom_create",
> +				 "tuple bloom part");
> +			for (uint32_t j = 0; j < i; j++)
> +				bloom_destroy(&bloom->parts[j], runtime.quota);
> +			free(bloom);

Why can't use use tuple_bloom_delete() here?
Looks like you need to introduce tuple_bloom_init() function for
that.

> +			return NULL;
> +		}
> +		for (uint32_t k = 0; k < count; k++)
> +			bloom_add(&bloom->parts[i], hash_arr->values[k]);
> +	}
> +	bloom->part_count = part_count;
> +	return bloom;
> +}
> +
> +void
> +tuple_bloom_delete(struct tuple_bloom *bloom)
> +{
> +	for (uint32_t i = 0; i < bloom->part_count; i++)
> +		bloom_destroy(&bloom->parts[i], runtime.quota);
> +	free(bloom);
> +}
> +
> +bool
> +tuple_bloom_possible_has(const struct tuple_bloom *bloom,
> +			 const struct tuple *tuple,
> +			 const struct key_def *key_def)
> +{
> +	assert(bloom->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_key_part(&h, &carry, tuple,
> +						  &key_def->parts[i]);
> +		uint32_t hash = PMurHash32_Result(h, carry, total_size);

> +		if (!bloom_possible_has(&bloom->parts[i], hash))
> +			return false;
> +	}
> +	return true;
> +}
> +
> +bool
> +tuple_bloom_possible_has_key(const struct tuple_bloom *bloom,
> +			     const char *key, uint32_t part_count,
> +			     const struct key_def *key_def)
> +{
> +	assert(part_count <= key_def->part_count);
> +	assert(bloom->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 < 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 (!bloom_possible_has(&bloom->parts[i], hash))
> +			return false;
> +	}
> +	return true;
> +}
> +
> +static size_t
> +tuple_bloom_sizeof_part(const struct bloom *part)
> +{
> +	size_t size = 0;
> +	size += mp_sizeof_array(3);
> +	size += mp_sizeof_uint(part->table_size);
> +	size += mp_sizeof_uint(part->hash_count);
> +	size += mp_sizeof_bin(bloom_store_size(part));
> +	return size;
> +}
> +
> +static char *
> +tuple_bloom_encode_part(const struct bloom *part, char *buf)
> +{
> +	buf = mp_encode_array(buf, 3);
> +	buf = mp_encode_uint(buf, part->table_size);
> +	buf = mp_encode_uint(buf, part->hash_count);
> +	buf = mp_encode_binl(buf, bloom_store_size(part));
> +	buf = bloom_store(part, buf);
> +	return buf;
> +}
> +
> +static int
> +tuple_bloom_decode_part(struct bloom *part, const char **data)
> +{
> +	memset(part, 0, sizeof(*part));
> +	if (mp_decode_array(data) != 3)
> +		unreachable();
> +	part->table_size = mp_decode_uint(data);
> +	part->hash_count = mp_decode_uint(data);
> +	size_t store_size = mp_decode_binl(data);
> +	assert(store_size == bloom_store_size(part));
> +	if (bloom_load_table(part, *data, runtime.quota) != 0) {
> +		diag_set(OutOfMemory, store_size, "bloom_load_table",
> +			 "tuple bloom part");
> +		return -1;
> +	}
> +	*data += store_size;
> +	return 0;
> +}
> +
> +size_t
> +tuple_bloom_size(const struct tuple_bloom *bloom)
> +{
> +	size_t size = 0;
> +	size += mp_sizeof_array(bloom->part_count);
> +	for (uint32_t i = 0; i < bloom->part_count; i++)
> +		size += tuple_bloom_sizeof_part(&bloom->parts[i]);
> +	return size;
> +}
> +
> +char *
> +tuple_bloom_encode(const struct tuple_bloom *bloom, char *buf)
> +{
> +	buf = mp_encode_array(buf, bloom->part_count);
> +	for (uint32_t i = 0; i < bloom->part_count; i++)
> +		buf = tuple_bloom_encode_part(&bloom->parts[i], buf);
> +	return buf;
> +}
> +
> +struct tuple_bloom *
> +tuple_bloom_decode(const char **data)
> +{
> +	uint32_t part_count = mp_decode_array(data);
> +	struct tuple_bloom *bloom = malloc(sizeof(*bloom) +
> +			part_count * sizeof(*bloom->parts));
> +	if (bloom == NULL) {
> +		diag_set(OutOfMemory, sizeof(*bloom) +
> +			 part_count * sizeof(*bloom->parts),
> +			 "malloc", "tuple bloom");
> +		return NULL;
> +	}
> +	for (uint32_t i = 0; i < part_count; i++) {
> +		if (tuple_bloom_decode_part(&bloom->parts[i], data) != 0) {
> +			for (uint32_t j = 0; j < i; j++)
> +				bloom_destroy(&bloom->parts[j], runtime.quota);
> +			free(bloom);
> +			return NULL;
> +		}
> +	}
> +	bloom->part_count = part_count;
> +	return bloom;
> +}
> diff --git a/src/box/tuple_bloom.h b/src/box/tuple_bloom.h
> new file mode 100644
> index 0000000..24a7e1c
> --- /dev/null
> +++ b/src/box/tuple_bloom.h
> @@ -0,0 +1,191 @@
> +#ifndef TARANTOOL_BOX_TUPLE_BLOOM_H_INCLUDED
> +#define TARANTOOL_BOX_TUPLE_BLOOM_H_INCLUDED
> +/*
> + * Copyright 2010-2018, Tarantool AUTHORS, please see AUTHORS file.
> + *
> + * Redistribution and use in source and binary forms, with or
> + * without modification, are permitted provided that the following
> + * conditions are met:
> + *
> + * 1. Redistributions of source code must retain the above
> + *    copyright notice, this list of conditions and the
> + *    following disclaimer.
> + *
> + * 2. Redistributions in binary form must reproduce the above
> + *    copyright notice, this list of conditions and the following
> + *    disclaimer in the documentation and/or other materials
> + *    provided with the distribution.
> + *
> + * THIS SOFTWARE IS PROVIDED BY <COPYRIGHT HOLDER> ``AS IS'' AND
> + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
> + * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
> + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
> + * <COPYRIGHT HOLDER> OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
> + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
> + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
> + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
> + * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
> + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
> + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
> + * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
> + * SUCH DAMAGE.
> + */
> +
> +#include <stdbool.h>
> +#include <stddef.h>
> +#include <stdint.h>
> +#include "salad/bloom.h"
> +
> +#if defined(__cplusplus)
> +extern "C" {
> +#endif /* defined(__cplusplus) */
> +
> +struct tuple;
> +struct key_def;
> +
> +/**
> + * Tuple bloom filter.
> + *
> + * Consists of a set of bloom filters, one per each sub key.

key prefix.

> + * When a key is checked to be hashed in the bloom, all its
> + * sub keys are checked as well, which lowers the probability
> + * of false positive results.
> + */
> +struct tuple_bloom {
> +	/** Number of key parts. */
> +	uint32_t part_count;
> +	/** Array of bloom filters, one per each sub key. */
> +	struct bloom parts[0];
> +};
> +
> +/**
> + * Array of tuple hashes.
> + */
> +struct tuple_hash_array {
> +	/** Number of hashes stored in the array. */
> +	uint32_t count;
> +	/** Capacity of the array of hashes. */
> +	uint32_t capacity;
> +	/** Array of hashes. */
> +	uint32_t *values;
> +};
> +
> +/**
> + * Tuple bloom filter builder.
> + *
> + * Construction of a bloom filter proceeds as follows.
> + * First all tuple hashes are stored in a builder object.
> + * Once all hashes have been stored, a bloom filter of
> + * the optimal size and all the hashes are added to it.
> + */
> +struct tuple_bloom_builder {
> +	/** Number of key parts. */
> +	uint32_t part_count;
> +	/** Hash arrays, one per each sub key. */
> +	struct tuple_hash_array parts[0];
> +};
> +
> +/**
> + * Create a bloom filter builder.
> + * @param part_count - number of key parts
> + * @return bloom builder on success or NULL on OOM
> + */
> +struct tuple_bloom_builder *
> +tuple_bloom_builder_new(uint32_t part_count);
> +
> +/**
> + * Destroy a bloom filter builder.
> + * @param builder - bloom filter builder
> + */
> +void
> +tuple_bloom_builder_delete(struct tuple_bloom_builder *builder);
> +
> +/**
> + * Add a tuple hash to a bloom filter 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
> + */
> +int
> +tuple_bloom_builder_add(struct tuple_bloom_builder *builder,
> +			const struct tuple *tuple,
> +			const struct key_def *key_def,
> +			uint32_t hashed_parts);
> +
> +/**
> + * Create a new bloom filter.

a new tuple bloom filter.

> + * @param builder - bloom filter builder
> + * @param fpr - desired false positive rate
> + * @return bloom filter on success or NULL on OOM
> + */
> +struct tuple_bloom *
> +tuple_bloom_new(struct tuple_bloom_builder *builder, double fpr);
> +
> +/**
> + * Delete a bloom filter.
> + * @param bloom - bloom filter to delete
> + */
> +void
> +tuple_bloom_delete(struct tuple_bloom *bloom);
> +
> +/**
> + * Check if a tuple was stored in a bloom filter.
> + * @param bloom - bloom filter
> + * @param tuple - tuple to check
> + * @param key_def - key definition
> + * @return true if the tuple may have been stored in the bloom,
> + *  false if the tuple is definitely not in the bloom
> + */
> +bool
> +tuple_bloom_possible_has(const struct tuple_bloom *bloom,
> +			 const struct tuple *tuple,
> +			 const struct key_def *key_def);
> +

suggestion: possible -> maybe

> +/**
> + * Check if a tuple matching a key was stored in a bloom filter.
> + * @param bloom - bloom filter
> + * @param key - key to check
> + * @param part_count - number of parts in the key
> + * @param key_def - key definition
> + * @return true if there may be a tuple matching the key stored in
> + *  the bloom, false if there is definitely no such tuple
> + */
> +bool
> +tuple_bloom_possible_has_key(const struct tuple_bloom *bloom,
> +			     const char *key, uint32_t part_count,
> +			     const struct key_def *key_def);
> +
> +/**
> + * Return the size of a bloom filter when encoded.
> + * @param bloom - bloom filter
> + * @return size of the bloom filter, in bytes
> + */
> +size_t
> +tuple_bloom_size(const struct tuple_bloom *bloom);
> +
> +/**
> + * Encode a bloom filter in MsgPack.
> + * @param bloom - bloom filter
> + * @param buf - buffer where to store the bloom filter
> + * @return pointer to the first byte following encoded data
> + */
> +char *
> +tuple_bloom_encode(const struct tuple_bloom *bloom, char *buf);
> +
> +/**
> + * Decode a bloom filter from MsgPack.
> + * @param data - pointer to buffer storing encoded bloom filter;
> + *  on success it is advanced by the number of decoded bytes
> + * @return the decoded bloom on success or NULL on OOM
> + */
> +struct tuple_bloom *
> +tuple_bloom_decode(const char **data);
> +
> +#if defined(__cplusplus)
> +} /* extern "C" */
> +#endif /* defined(__cplusplus) */
> +
> +#endif /* TARANTOOL_BOX_TUPLE_BLOOM_H_INCLUDED */
> diff --git a/src/box/tuple_compare.cc b/src/box/tuple_compare.cc
> index 13ebfc5..cfee004 100644
> --- a/src/box/tuple_compare.cc
> +++ b/src/box/tuple_compare.cc
> @@ -426,6 +426,30 @@ 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,
> +		       const struct key_def *key_def)
> +{
> +	uint32_t i;
> +	for (i = 0; i < key_def->part_count; i++) {
> +		const struct key_part *part = &key_def->parts[i];
> +		const char *field_a = tuple_field(tuple_a, part->fieldno);
> +		const char *field_b = tuple_field(tuple_b, part->fieldno);
> +		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>
>  static inline int
>  tuple_compare_slowpath(const struct tuple *tuple_a, const struct tuple *tuple_b,
> diff --git a/src/box/tuple_compare.h b/src/box/tuple_compare.h
> index 3888bbb..d80e1e7 100644
> --- a/src/box/tuple_compare.h
> +++ b/src/box/tuple_compare.h
> @@ -42,6 +42,18 @@ extern "C" {
>  #endif /* defined(__cplusplus) */
>  
>  /**
> + * 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 parts the two tuples have in common

These are not parts of the tuple, these are parts of the key.
described in the key def.

> + */
> +uint32_t
> +tuple_common_key_parts(const struct tuple *tuple_a,
> +		       const struct tuple *tuple_b,
> +		       const struct key_def *key_def);
> +
> +/**
>   * Create a comparison function for the key_def
>   *
>   * @param key_def key_definition
> diff --git a/src/box/tuple_hash.cc b/src/box/tuple_hash.cc
> index 0f7ba91..0fa8ea5 100644
> --- a/src/box/tuple_hash.cc
> +++ b/src/box/tuple_hash.cc
> @@ -262,7 +262,7 @@ slowpath:
>  	key_def->key_hash = key_hash_slowpath;
>  }
>  
> -static uint32_t
> +uint32_t
>  tuple_hash_field(uint32_t *ph1, uint32_t *pcarry, const char **field,
>  		 struct coll *coll)
>  {
> @@ -308,6 +308,17 @@ tuple_hash_null(uint32_t *ph1, uint32_t *pcarry)
>  	return mp_sizeof_nil();
>  }
>  
> +uint32_t
> +tuple_hash_key_part(uint32_t *ph1, uint32_t *pcarry,
> +		    const struct tuple *tuple,
> +		    const struct key_part *part)
> +{
> +	const char *field = tuple_field(tuple, part->fieldno);
> +	if (field == NULL)
> +		return tuple_hash_null(ph1, pcarry);
> +	return tuple_hash_field(ph1, pcarry, &field, part->coll);
> +}


<snip>

-- 
Konstantin Osipov, Moscow, Russia, +7 903 626 22 32
http://tarantool.io - www.twitter.com/kostja_osipov