[PATCH v3 0/7] box: introduce hint option for memtx tree index

[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 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

v2: https://www.freelists.org/post/tarantool-patches/PATCH-v2-04-box-introduce-hint-option-for-memtx-tree-index

Branch: http://github.com/tarantool/tarantool/tree/kshch/gh-3961-tuple-hints
Issue: https://github.com/tarantool/tarantool/issues/3961

Alexandr Lyapunov (1):
  memtx: introduce tuple compare hint

Kirill Shcherbatov (6):
  memtx: introduce universal iterator_pool
  lib: fix undef _api_name in bps_tree header
  lib: introduce BPS_TREE_IDENTICAL custom comparator
  memtx: hide index implementation details from header
  memtx: rework memtx_tree to store arbitrary nodes
  memtx: rename memtx_tree.c to memtx_tree_impl.h

 src/box/CMakeLists.txt                      |   3 +-
 src/box/key_def.c                           |   2 +
 src/box/key_def.h                           |  44 ++
 src/box/memtx_bitset.c                      |  33 +-
 src/box/memtx_bitset.h                      |  26 +-
 src/box/memtx_engine.c                      |  10 +-
 src/box/memtx_engine.h                      |  17 +-
 src/box/memtx_hash.c                        |  58 ++-
 src/box/memtx_hash.h                        |  44 +-
 src/box/memtx_rtree.c                       |  26 +-
 src/box/memtx_rtree.h                       |  16 +-
 src/box/memtx_space.c                       |  16 +-
 src/box/memtx_tree.h                        |  68 +--
 src/box/memtx_tree_decl.c                   | 173 +++++++
 src/box/{memtx_tree.c => memtx_tree_impl.h} | 531 ++++++++++++++++----
 src/box/tuple_hint.cc                       | 210 ++++++++
 src/box/tuple_hint.h                        |  51 ++
 src/coll.c                                  |  33 ++
 src/coll.h                                  |   4 +
 src/lib/salad/bps_tree.h                    |  83 ++-
 test/unit/bps_tree_iterator.cc              |  16 +-
 21 files changed, 1134 insertions(+), 330 deletions(-)
 create mode 100644 src/box/memtx_tree_decl.c
 rename src/box/{memtx_tree.c => memtx_tree_impl.h} (52%)
 create mode 100644 src/box/tuple_hint.cc
 create mode 100644 src/box/tuple_hint.h

-- 
2.20.1