[PATCH v4 0/3] box: introduce hint option for memtx tree index
Kirill Shcherbatov
kshcherbatov at tarantool.org
Thu Feb 28 16:38:46 MSK 2019
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 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
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
Alexandr Lyapunov (1):
memtx: introduce tuple compare hint
Kirill Shcherbatov (2):
memtx: renamed memtx_tree.c to memtx_tree.cc
memtx: rework memtx_tree to store arbitrary nodes
src/box/CMakeLists.txt | 3 +-
src/box/key_def.c | 2 +
src/box/key_def.h | 44 +++
src/box/{memtx_tree.c => memtx_tree.cc} | 406 ++++++++++++++++--------
src/box/tuple_hint.cc | 301 ++++++++++++++++++
src/box/tuple_hint.h | 60 ++++
src/lib/coll/coll.c | 33 ++
src/lib/coll/coll.h | 4 +
8 files changed, 725 insertions(+), 128 deletions(-)
rename src/box/{memtx_tree.c => memtx_tree.cc} (68%)
create mode 100644 src/box/tuple_hint.cc
create mode 100644 src/box/tuple_hint.h
--
2.21.0
More information about the Tarantool-patches
mailing list