[PATCH v5 0/4] box: introduce multikey indexes in memtx

[Kirill Shcherbatov]

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 5:
    - new tuple_format_iterator interface
    - simplified multikey_required_fields and
      memtx_tree_index_build_array_deduplicate routines
      (O^2(n) -> O(n))
    - new memtx_tree_delete_identical method in bps tree to
      simplify memtx_tree_index_replace_multikey
    - decreased memtx_tree_index_build_array_append diff
    - new example in commit message

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

v4: https://www.freelists.org/post/tarantool-patches/PATCH-v4-03-box-introduce-multikey-indexes-in-memtx
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 (4):
  box: introduce tuple_format_iterator class
  box: introduce field_map_builder class
  salad: introduce bps_tree_delete_identical routine
  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           | 250 +++++++++++
 src/box/index_def.c           |   5 +
 src/box/key_def.c             | 142 ++++--
 src/box/key_def.h             |  34 ++
 src/box/memtx_engine.c        |  10 +-
 src/box/memtx_space.c         |  18 +
 src/box/memtx_tree.c          | 240 ++++++++++-
 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        | 561 +++++++++++++++---------
 src/box/tuple_format.h        | 167 ++++++-
 src/box/vinyl.c               |   7 +
 src/box/vy_cache.h            |   4 +-
 src/box/vy_mem.h              |   4 +-
 src/box/vy_stmt.c             | 126 ++----
 src/lib/salad/bps_tree.h      |  35 ++
 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 +++++++++
 test/unit/bps_tree.cc         |  60 +++
 test/unit/bps_tree.result     |   2 +
 31 files changed, 2705 insertions(+), 404 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