From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: From: Kirill Shcherbatov Subject: [PATCH v6 0/3] box: introduce hint option for memtx tree index Date: Wed, 13 Mar 2019 15:15:36 +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%). Also appended multikey index prototype. I am going to try to rework field_map initialization and resend last letter a bit later. Changes in version 6: -- Changed hint format: now the first two bytes are reserved for type -- Hints for SCALAR type -- All compare routins now have two versions: hinted and non-hinted Changes in version 5: -- Code rewritten without classes and macro definitions using vtabs. -- Appended multikey index prototype. Changes in version 4: -- Code rewritten in C++ with classes. This perform a better maintainability in future. -- New hints for number and boolean types. Memtx Tree is always hinted now. -- INVALID_HINT marker. We need it because double have strange types NaN and so on that musn't be a problem of hints business. -- After part of code was merged, rebased patch. Changes in version 3: -- Better-structured code -- Refactored all memtx indexes to use shared mempool of default size -- Refactored all memtx indexes to hide implementation details from headers -- Moved all hints-related code to corresponding module -- Better types names, better comments -- Fixed potential bug with iterators: introduce MEMTX_TREE_IDENTICAL macro -- Fix inaccurate MEMTX_TREE_ELEM_SET usage in memtx_tree_index_build_next -- Changed approach to calculate string hints -- Introduce separate hint for binary collation type 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 v5: https://www.freelists.org/post/tarantool-patches/PATCH-v5-04-box-introduce-hint-option-for-memtx-tree-index v4: https://www.freelists.org/post/tarantool-patches/PATCH-v4-07-box-introduce-hint-option-for-memtx-tree-index v3: https://www.freelists.org/post/tarantool-patches/PATCH-v3-07-box-introduce-hint-option-for-memtx-tree-index v2: https://www.freelists.org/post/tarantool-patches/PATCH-v2-04-box-introduce-hint-option-for-memtx-tree-index v1: https://www.freelists.org/post/tarantool-patches/PATCH-v1-04-box-introduce-hint-option-for-memtx-tree-index http://github.com/tarantool/tarantool/tree/kshch/gh-3961-tuple-hints https://github.com/tarantool/tarantool/issues/3961 Kirill Shcherbatov (3): box: refactor key_def_set_compare_func routine memtx: introduce tuple compare hint box: introduce multikey indexes src/box/key_def.c | 15 + src/box/key_def.h | 100 ++++++ src/box/memtx_tree.c | 217 +++++++++++- src/box/tuple.c | 8 +- src/box/tuple.h | 122 ++++++- src/box/tuple_compare.cc | 705 +++++++++++++++++++++++++++++++++++--- src/box/tuple_format.c | 120 +++++-- src/lib/coll/coll.c | 33 ++ src/lib/coll/coll.h | 4 + test/engine/json.result | 80 ++++- test/engine/json.test.lua | 20 ++ 11 files changed, 1330 insertions(+), 94 deletions(-) -- 2.21.0