From: Kirill Shcherbatov <kshcherbatov@tarantool.org> To: tarantool-patches@freelists.org, kostja@tarantool.org, vdavydov.dev@gmail.com Cc: Kirill Shcherbatov <kshcherbatov@tarantool.org> Subject: [PATCH v2 0/4] box: introduce hint option for memtx tree index Date: Wed, 13 Feb 2019 12:32:24 +0300 [thread overview] Message-ID: <cover.1550050245.git.kshcherbatov@tarantool.org> (raw) Reworked memtx tree to use 'tuple hints'. Introduced special functions for retrieve 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 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', 'unsigned' or 'integer' * 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. Enabled hint option improve performance on average by 15%; Select operations are significantly accelerated (there are scenarios in which the difference reaches 200-250%). Changes in version 2: -- Splitted patch to parts in other way to decrease diff -- Hints are not index option anymore, but default where possible -- Removed hints for numeric types http://github.com/tarantool/tarantool/tree/kshch/gh-3961-tuple-hints https://github.com/tarantool/tarantool/issues/3961 Alexandr Lyapunov (1): box: introduce tuple compare hint for string index Kirill Shcherbatov (3): box: move memtx_tree implementation to source file box: rework memtx_tree to store arbitrary nodes box: rename memtx_tree.c to memtx_tree_impl.h src/box/CMakeLists.txt | 2 +- src/box/key_def.c | 1 + src/box/key_def.h | 44 ++ src/box/memtx_tree.h | 68 +-- src/box/memtx_tree_decl.c | 207 +++++++++ src/box/{memtx_tree.c => memtx_tree_impl.h} | 490 +++++++++++++++----- src/box/tuple_compare.cc | 101 ++++ src/box/tuple_compare.h | 7 + src/coll.c | 45 ++ src/coll.h | 4 + 10 files changed, 787 insertions(+), 182 deletions(-) create mode 100644 src/box/memtx_tree_decl.c rename src/box/{memtx_tree.c => memtx_tree_impl.h} (55%) -- 2.20.1
next reply other threads:[~2019-02-13 9:32 UTC|newest] Thread overview: 13+ messages / expand[flat|nested] mbox.gz Atom feed top 2019-02-13 9:32 Kirill Shcherbatov [this message] 2019-02-13 9:32 ` [PATCH v2 1/4] box: move memtx_tree implementation to source file Kirill Shcherbatov 2019-02-14 13:57 ` [tarantool-patches] " Konstantin Osipov 2019-02-21 13:26 ` Vladimir Davydov 2019-02-13 9:32 ` [PATCH v2 2/4] box: rework memtx_tree to store arbitrary nodes Kirill Shcherbatov 2019-02-21 15:01 ` Vladimir Davydov 2019-02-13 9:32 ` [PATCH v2 3/4] box: rename memtx_tree.c to memtx_tree_impl.h Kirill Shcherbatov 2019-02-13 9:32 ` [PATCH v2 4/4] box: introduce tuple compare hint for string index Kirill Shcherbatov 2019-02-14 14:09 ` [tarantool-patches] " Konstantin Osipov 2019-02-15 18:34 ` Kirill Shcherbatov 2019-02-19 15:01 ` [tarantool-patches] " Konstantin Osipov 2019-02-19 15:02 ` Kirill Shcherbatov 2019-02-21 16:06 ` 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=cover.1550050245.git.kshcherbatov@tarantool.org \ --to=kshcherbatov@tarantool.org \ --cc=kostja@tarantool.org \ --cc=tarantool-patches@freelists.org \ --cc=vdavydov.dev@gmail.com \ --subject='Re: [PATCH v2 0/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