From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: From: Kirill Shcherbatov Subject: [PATCH v5 0/4] box: introduce multikey indexes in memtx Date: Mon, 6 May 2019 14:57:37 +0300 Message-Id: MIME-Version: 1.0 Content-Transfer-Encoding: 8bit To: tarantool-patches@freelists.org, vdavydov.dev@gmail.com Cc: Kirill Shcherbatov List-ID: 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