From: Vladimir Davydov <vdavydov.dev@gmail.com> To: Kirill Shcherbatov <kshcherbatov@tarantool.org> Cc: tarantool-patches@freelists.org Subject: Re: [PATCH v1 4/4] box: introduce hint option for memtx tree index Date: Mon, 11 Feb 2019 19:12:06 +0300 [thread overview] Message-ID: <20190211161206.jtu2narfch42v3xm@esperanza> (raw) In-Reply-To: <d0e74f975be244ea05663275e3f9835e7400e010.1549367041.git.kshcherbatov@tarantool.org> 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; > +};
prev parent reply other threads:[~2019-02-11 16:12 UTC|newest] Thread overview: 9+ messages / expand[flat|nested] mbox.gz Atom feed top 2019-02-05 11:58 [PATCH v1 0/4] " Kirill Shcherbatov 2019-02-05 11:58 ` [PATCH v1 1/4] lib: introduce BPS_TREE_EQUAL custom comparator Kirill Shcherbatov 2019-02-11 15:46 ` Vladimir Davydov 2019-02-05 11:58 ` [PATCH v1 2/4] box: rework memtx_tree class to be reusable Kirill Shcherbatov 2019-02-11 15:49 ` Vladimir Davydov 2019-02-05 11:58 ` [PATCH v1 3/4] box: introduce tuple compare hint Kirill Shcherbatov 2019-02-11 15:57 ` Vladimir Davydov 2019-02-05 11:58 ` [PATCH v1 4/4] box: introduce hint option for memtx tree index Kirill Shcherbatov 2019-02-11 16:12 ` Vladimir Davydov [this message]
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=20190211161206.jtu2narfch42v3xm@esperanza \ --to=vdavydov.dev@gmail.com \ --cc=kshcherbatov@tarantool.org \ --cc=tarantool-patches@freelists.org \ --subject='Re: [PATCH v1 4/4] box: introduce hint option for memtx tree index' \ /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