From: Kirill Shcherbatov <kshcherbatov@tarantool.org>
To: tarantool-patches@freelists.org, vdavydov.dev@gmail.com
Cc: Kirill Shcherbatov <kshcherbatov@tarantool.org>
Subject: [PATCH v5 0/4] box: introduce multikey indexes in memtx
Date: Mon, 6 May 2019 14:57:37 +0300 [thread overview]
Message-ID: <cover.1557142159.git.kshcherbatov@tarantool.org> (raw)
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
next reply other threads:[~2019-05-06 11:57 UTC|newest]
Thread overview: 17+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-05-06 11:57 Kirill Shcherbatov [this message]
2019-05-06 11:57 ` [PATCH v5 1/4] box: introduce tuple_format_iterator class Kirill Shcherbatov
2019-05-06 13:55 ` Vladimir Davydov
2019-05-06 14:32 ` [tarantool-patches] " Kirill Shcherbatov
2019-05-06 11:57 ` [PATCH v5 2/4] box: introduce field_map_builder class Kirill Shcherbatov
2019-05-06 14:22 ` Vladimir Davydov
2019-05-06 11:57 ` [PATCH v5 3/4] salad: introduce bps_tree_delete_identical routine Kirill Shcherbatov
2019-05-06 14:34 ` Vladimir Davydov
2019-05-06 14:55 ` [tarantool-patches] " Kirill Shcherbatov
2019-05-06 11:57 ` [PATCH v5 4/4] box: introduce multikey indexes in memtx Kirill Shcherbatov
2019-05-06 15:46 ` Vladimir Davydov
2019-05-06 16:35 ` [tarantool-patches] " Kirill Shcherbatov
2019-05-07 8:11 ` Vladimir Davydov
2019-05-07 8:28 ` Kirill Shcherbatov
2019-05-07 11:30 ` Vladimir Davydov
2019-05-07 13:13 ` Vladimir Davydov
2019-05-06 15:52 ` [PATCH v5 0/4] " Vladimir Davydov
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=cover.1557142159.git.kshcherbatov@tarantool.org \
--to=kshcherbatov@tarantool.org \
--cc=tarantool-patches@freelists.org \
--cc=vdavydov.dev@gmail.com \
--subject='Re: [PATCH v5 0/4] box: introduce multikey indexes in memtx' \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox