From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Date: Mon, 11 Feb 2019 19:12:06 +0300 From: Vladimir Davydov Subject: Re: [PATCH v1 4/4] box: introduce hint option for memtx tree index Message-ID: <20190211161206.jtu2narfch42v3xm@esperanza> References: MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: To: Kirill Shcherbatov Cc: tarantool-patches@freelists.org List-ID: On Tue, Feb 05, 2019 at 02:58:39PM +0300, Kirill Shcherbatov wrote: > If an index has certain option, a compare hint must be calculated > and stored within bps_tree along with struct tuple pointer. This > hint must be used for tuple precomparison in order to avoid memory > fetching and significantly improve tree performance. > > Such a hinted tree will cost twice amount of memory - 20 byte per > tuple on average. > Enabled hint option improve performance on average by 15%; Select > operations are significantly accelerated (there are scenarios in > which the difference reaches 200-250%). > > Test set from original @alyapunov patch. > > Needed for #3961 > --- > src/box/index_def.c | 2 + > src/box/index_def.h | 6 + > src/box/lua/schema.lua | 12 ++ > src/box/lua/space.cc | 5 + > src/box/memtx_tree.c | 192 +++++++++++++++++++++++- > src/box/memtx_tree_impl.h | 2 +- > test/box/tree_pk.result | 220 ++++++++++++++++++++++++++++ > test/box/tree_pk.test.lua | 88 +++++++++++ > test/box/tree_pk_multipart.result | 155 ++++++++++++++++++++ > test/box/tree_pk_multipart.test.lua | 65 ++++++++ > 10 files changed, 745 insertions(+), 2 deletions(-) > > diff --git a/src/box/index_def.c b/src/box/index_def.c > index c52aa38d1..4d3fadc6e 100644 > --- a/src/box/index_def.c > +++ b/src/box/index_def.c > @@ -49,6 +49,7 @@ const struct index_opts index_opts_default = { > /* .bloom_fpr = */ 0.05, > /* .lsn = */ 0, > /* .stat = */ NULL, > + /* .hint = */ false, > }; > > const struct opt_def index_opts_reg[] = { > @@ -62,6 +63,7 @@ const struct opt_def index_opts_reg[] = { > OPT_DEF("run_size_ratio", OPT_FLOAT, struct index_opts, run_size_ratio), > OPT_DEF("bloom_fpr", OPT_FLOAT, struct index_opts, bloom_fpr), > OPT_DEF("lsn", OPT_INT64, struct index_opts, lsn), > + OPT_DEF("hint", OPT_BOOL, struct index_opts, hint), > OPT_END, > }; > > diff --git a/src/box/index_def.h b/src/box/index_def.h > index 7717ecd64..74814bef5 100644 > --- a/src/box/index_def.h > +++ b/src/box/index_def.h > @@ -157,6 +157,10 @@ struct index_opts { > * LSN from the time of index creation. > */ > int64_t lsn; > + /** > + * Use hint optimization for tree index. > + */ > + bool hint; Hints should be enabled unconditionally if possible. Please don't introduce a new index option. The tests won't be necessary then, I guess. > diff --git a/src/box/memtx_tree.c b/src/box/memtx_tree.c > index 6b22883c2..426a11262 100644 > --- a/src/box/memtx_tree.c > +++ b/src/box/memtx_tree.c > @@ -79,8 +79,198 @@ struct memtx_tuple_tree_key_data { > > /* }}} */ > > +/* {{{ Memtx hinted and hint_only tree class. *******************/ Please add a comment somewhere explaining what's the difference. I also have some concerns about struct/function names, but we'll talk about them later, when you make patch 2 review-able. > + > +/** > + * Struct that is used as a key in BPS tree definition in > + * metmx_hint_only_tree and metmx_hinted_tree. > +*/ > +struct memtx_hinted_tree_key_data { > + /** Sequence of msgpacked search fields. */ > + const char *key; > + /** Number of msgpacked search fields. */ > + uint32_t part_count; > + /** > + * Compare hint. Is calculated automatically on 'set' > + * operation with memtx_hinted_tree_key_data_set(). > + */ > + uint64_t hint; > +};