[PATCH v1 0/4] box: introduce hint option for memtx tree index
Kirill Shcherbatov
kshcherbatov at tarantool.org
Tue Feb 5 14:58:35 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%).
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
More information about the Tarantool-patches
mailing list