Tarantool development patches archive
 help / color / mirror / Atom feed
* [PATCH v2 0/4] box: introduce hint option for memtx tree index
@ 2019-02-13  9:32 Kirill Shcherbatov
  2019-02-13  9:32 ` [PATCH v2 1/4] box: move memtx_tree implementation to source file Kirill Shcherbatov
                   ` (3 more replies)
  0 siblings, 4 replies; 13+ messages in thread
From: Kirill Shcherbatov @ 2019-02-13  9:32 UTC (permalink / raw)
  To: tarantool-patches, kostja, vdavydov.dev; +Cc: Kirill Shcherbatov

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

^ permalink raw reply	[flat|nested] 13+ messages in thread

end of thread, other threads:[~2019-02-21 16:06 UTC | newest]

Thread overview: 13+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-02-13  9:32 [PATCH v2 0/4] box: introduce hint option for memtx tree index Kirill Shcherbatov
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

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox