From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: From: Kirill Shcherbatov Subject: [PATCH v1 0/4] box: introduce hint option for memtx tree index Date: Tue, 5 Feb 2019 14:58:35 +0300 Message-Id: MIME-Version: 1.0 Content-Transfer-Encoding: 8bit To: tarantool-patches@freelists.org, vdavydov.dev@gmail.com Cc: Kirill Shcherbatov List-ID: 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%). http://github.com/tarantool/tarantool/tree/kshch/gh-3961-tuple-hints https://github.com/tarantool/tarantool/issues/3961 Kirill Shcherbatov (3): lib: introduce BPS_TREE_EQUAL custom comparator box: rework memtx_tree class to be reusable box: introduce hint option for memtx tree index Alexandr Lyapunov (1): box: introduce tuple compare hint src/box/index_def.c | 2 + src/box/index_def.h | 6 + src/box/key_def.c | 1 + src/box/key_def.h | 11 + src/box/lua/schema.lua | 12 + src/box/lua/space.cc | 5 + src/box/memtx_tree.c | 851 ++++++------------------ src/box/memtx_tree.h | 68 +- src/box/memtx_tree_impl.h | 960 ++++++++++++++++++++++++++++ src/box/tuple_compare.cc | 131 ++++ src/box/tuple_compare.h | 40 ++ src/coll.c | 23 + src/coll.h | 3 + src/lib/salad/bps_tree.h | 74 ++- 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 ++ test/unit/bps_tree_iterator.cc | 15 +- 19 files changed, 1989 insertions(+), 741 deletions(-) create mode 100644 src/box/memtx_tree_impl.h -- 2.20.1