[PATCH v4 0/3] box: introduce multikey indexes in memtx

[Kirill Shcherbatov <kshcherbatov@tarantool.org>]

Multikey indexes allows you to automatically index set of documents
by JSON paths having array index placeholder "[*]". Multikey index
cannot be primary as it cannot be unique(by definition).
Multikey index parts must be compatible: only one "[*]" placeholder
is allowed in same position(for all JSON paths in index parts).

Changes in version 4:
    - fixed different results before and after server restart
      (memtx_tree_index_build_array_deduplicate)
    - fixes many troubles with replacement of tuples with
      different count of multikey keys
    - fixed troubles with same multikey keys in tuple
    - fixed troubles with nullable fields:
      here we need to introduce separate field:multikey_required_fields
      and check it leaving multikey index branch in format:fields tree
    - many new tests
    - refactored names and comments

Changes in version 3:
    - introduced tuple_parse_iterator class to encapsulate
      tuple parse details
    - refactored json lib helpers
    - introduced mp_stack_top helper in mspuck library
    - stubs for unused functions
    - refactored tuple_extract set
    - fixed unique multikey index
    - new descriptive comments

Changes in version 2:
    - introduced field_map_builder class to perform field_map
      preparation
    - reworked code: new helpers json_path_is_multikey and
      new flag json_path_cmp(is_weak_cmp = true)
    - rebased to actual tuple hints head
    - new tests

v3: https://www.freelists.org/post/tarantool-patches/PATCH-v3-07-box-introduce-multikey-indexes-in-memtx
v2: https://www.freelists.org/post/tarantool-patches/PATCH-v5-44-box-introduce-multikey-indexes

Branch: http://github.com/tarantool/tarantool/tree/kshch/gh-1257-multikey-indexes
Issue: https://github.com/tarantool/tarantool/issues/1257

Kirill Shcherbatov (3):
  box: introduce tuple_parse_iterator class
  box: introduce field_map_builder class
  box: introduce multikey indexes in memtx

 src/box/CMakeLists.txt        |   1 +
 src/box/errcode.h             |   1 +
 src/box/field_map.c           | 116 +++++
 src/box/field_map.h           | 259 +++++++++++
 src/box/index_def.c           |   5 +
 src/box/key_def.c             | 132 ++++--
 src/box/key_def.h             |  34 ++
 src/box/memtx_engine.c        |  10 +-
 src/box/memtx_space.c         |  18 +
 src/box/memtx_tree.c          | 272 +++++++++++-
 src/box/sql.c                 |   6 +-
 src/box/tuple.c               |  41 +-
 src/box/tuple.h               |  83 +++-
 src/box/tuple_compare.cc      | 152 +++++--
 src/box/tuple_compare.h       |  10 +
 src/box/tuple_extract_key.cc  |   5 +-
 src/box/tuple_format.c        | 398 ++++++++++-------
 src/box/tuple_format.h        | 198 ++++++++-
 src/box/vinyl.c               |   7 +
 src/box/vy_stmt.c             | 121 ++----
 test/box/misc.result          |   1 +
 test/engine/engine.cfg        |   3 +
 test/engine/json.result       |  18 +-
 test/engine/json.test.lua     |  12 +-
 test/engine/multikey.result   | 789 ++++++++++++++++++++++++++++++++++
 test/engine/multikey.test.lua | 206 +++++++++
 26 files changed, 2537 insertions(+), 361 deletions(-)
 create mode 100644 src/box/field_map.c
 create mode 100644 src/box/field_map.h
 create mode 100644 test/engine/multikey.result
 create mode 100644 test/engine/multikey.test.lua

-- 
2.21.0