Tarantool development patches archive
 help / color / mirror / Atom feed
From: Vladimir Davydov <vdavydov.dev@gmail.com>
To: Konstantin Osipov <kostja@tarantool.org>
Cc: tarantool-patches@freelists.org
Subject: Re: [PATCH v2 07/14] vinyl: add helpers to add/check statement with bloom
Date: Wed, 13 Mar 2019 15:25:05 +0300	[thread overview]
Message-ID: <20190313122505.f3atkaws5hneulzr@esperanza> (raw)
In-Reply-To: <20190313115934.GG25066@chai>

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

  reply	other threads:[~2019-03-13 12:25 UTC|newest]

Thread overview: 34+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
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:55   ` Konstantin Osipov
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
2019-03-13  8:52 ` [PATCH v2 03/14] vinyl: rename key stmt construction routine 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
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
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
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
2019-03-13 11:59   ` Konstantin Osipov
2019-03-13 12:25     ` Vladimir Davydov [this message]
2019-03-13  8:52 ` [PATCH v2 08/14] vinyl: do not pass format to vy_apply_upsert 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
2019-03-13 12:05   ` Konstantin Osipov
2019-03-13  8:52 ` [PATCH v2 10/14] vinyl: zap vy_write_iterator->format 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
2019-03-13 12:25   ` Konstantin Osipov
2019-03-13 12:45     ` Vladimir Davydov
2019-03-13 12:56       ` Konstantin Osipov
2019-03-13  8:52 ` [PATCH v2 12/14] vinyl: zap vy_stmt_new_surrogate_from_key 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
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 12:28   ` Konstantin Osipov
2019-03-13 15:54 ` [PATCH v2 00/14] vinyl: do not fill secondary tuples with nulls Vladimir Davydov

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20190313122505.f3atkaws5hneulzr@esperanza \
    --to=vdavydov.dev@gmail.com \
    --cc=kostja@tarantool.org \
    --cc=tarantool-patches@freelists.org \
    --subject='Re: [PATCH v2 07/14] vinyl: add helpers to add/check statement with bloom' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox