[PATCH v5 0/4] box: introduce hint option for memtx tree index

[Kirill Shcherbatov <kshcherbatov@tarantool.org>]

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

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

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

Kirill Shcherbatov (4):
  memtx: rework memtx_tree to store arbitrary nodes
  memtx: introduce tuple compare hint
  box: move offset_slot init to tuple_format_add_field
  box: introduce multikey indexes

 src/box/key_def.c         |  20 ++
 src/box/key_def.h         | 130 ++++++++++
 src/box/memtx_tree.c      | 470 +++++++++++++++++++++++++---------
 src/box/tuple.c           |   8 +-
 src/box/tuple.h           | 130 ++++++++--
 src/box/tuple_compare.cc  | 514 +++++++++++++++++++++++++++++++++++++-
 src/box/tuple_compare.h   |   7 +
 src/box/tuple_format.c    | 210 +++++++++++++---
 src/lib/coll/coll.c       |  33 +++
 src/lib/coll/coll.h       |   4 +
 test/engine/json.result   |  80 +++++-
 test/engine/json.test.lua |  20 ++
 12 files changed, 1446 insertions(+), 180 deletions(-)

-- 
2.21.0