[PATCH v2 00/14] vinyl: do not fill secondary tuples with nulls

[Vladimir Davydov]

Currently, we require all tuples read from a source iterator (mem, run)
conform to the space format. Since statements read from secondary index
runs don't have all necessary fields, we fill them with nulls (so called
surrogate tuples). This operation is pretty heavy, but it's not really
necessary, as nothing prevents us from comparing keys with tuples
directly. Besides, it's unclear how to befriend this with upcoming
multikey indexes without turning the code into a convoluted mess (How
would we create a multikey surrogate tuple? Create a fake one-element
array and put the indexed key there? Or don't use array at all and
simply insert a single key instead of an array mandated by the space
format? But this would be inconsistent with the key definition...)

So this patch removes nulls from secondary index statements and treats
them as key statements instead. Note, this doesn't allow us to get rid
of surrogate tuples altogether - we still need them to save memory when
inserting a DELETE into the memory level (we don't need to include all
fields into a DELETE statements, only indexed ones). Although this
change is primarily targeted at facilitating implementation of multikey
indexes in Vinyl, it's worthwhile on its own as
vy_stmt_new_surrogate_from_key became way too heavy after json support
was introduced to be called on each run read.

https://github.com/tarantool/tarantool/commits/dv/vy-dont-store-nulls-in-sk

Changes in v2:
 - Drop patches that have already been applied or rejected and rebase on
   top of latest 2.1. Patches 1-4 remained from the previous version.
   They were approved by Kostja, but we decided not to apply them until
   the rest of the series is ready to be committed.
 - Simplify tuple bloom filter construction (patch 5). This allowed to
   get rid of tuple_common_key_parts and key_common_parts helpers and
   hence simplify the main patch of the series.
 - Factor out preliminary changes: tuple bloom filter refactoring
   (patches 6 and 7), removal of the disk format from the write iterator
   (patches 8, 9, and 10). All in all, this should make the main patch
   of the series (patch 11) much easier for review.
 - Remove vy_stmt_new_surrogate_delete_from_key (patch 12), as we now
   can insert key statements into the memory level.
 - Don't use expensive vy_stmt_new_surrogate_delete where we don't need
   to (patch 13).
 - Zap tuple_format->min_tuple_size, as we don't need it anymore.
 - Rename vy_lsm->pk_extractor to pk_in_cmp_def.
 - Rename vy_stmt_new_from_array to vy_stmt_new_from_msgpack.

v1: https://www.freelists.org/post/tarantool-patches/PATCH-0012-vinyl-do-not-fill-secondary-tuples-with-nulls

Vladimir Davydov (14):
  vinyl: remove optimized comparators
  vinyl: introduce statement environment
  vinyl: rename key stmt construction routine
  vinyl: don't use IPROTO_SELECT type for key statements
  bloom: do not use tuple_common_key_parts when constructing tuple bloom
  bloom: factor out helper to add tuple hash to bloom builder
  vinyl: add helpers to add/check statement with bloom
  vinyl: do not pass format to vy_apply_upsert
  vinyl: clean up write iterator source destruction
  vinyl: zap vy_write_iterator->format
  vinyl: do not fill secondary tuples with nulls when decoded
  vinyl: zap vy_stmt_new_surrogate_from_key
  vinyl: don't use vy_stmt_new_surrogate_delete if not necessary
  tuple_format: zap min_tuple_size

 src/box/key_def.c               |  36 ++++++
 src/box/key_def.h               |  25 ++--
 src/box/tuple_bloom.c           |  83 +++++++++----
 src/box/tuple_bloom.h           |  21 +++-
 src/box/tuple_compare.cc        |  33 -----
 src/box/tuple_format.c          |  40 ------
 src/box/tuple_format.h          |   5 -
 src/box/vinyl.c                 | 114 ++++++++++-------
 src/box/vy_cache.c              |   8 +-
 src/box/vy_cache.h              |   2 +-
 src/box/vy_history.c            |   5 +-
 src/box/vy_history.h            |   3 +-
 src/box/vy_lsm.c                |  74 ++++++-----
 src/box/vy_lsm.h                |   8 +-
 src/box/vy_mem.c                |  16 +--
 src/box/vy_mem.h                |   2 +-
 src/box/vy_point_lookup.c       |   6 +-
 src/box/vy_range.c              |  13 +-
 src/box/vy_read_iterator.c      |  27 ++--
 src/box/vy_run.c                | 158 +++++++++++-------------
 src/box/vy_run.h                |   9 +-
 src/box/vy_scheduler.c          |  19 +--
 src/box/vy_stmt.c               | 248 ++++++++++++++-----------------------
 src/box/vy_stmt.h               | 266 ++++++++++++++++------------------------
 src/box/vy_tx.c                 |  11 +-
 src/box/vy_upsert.c             |   7 +-
 src/box/vy_upsert.h             |   4 +-
 src/box/vy_write_iterator.c     |  85 ++++++-------
 src/box/vy_write_iterator.h     |   9 +-
 test/unit/vy_iterators_helper.c |  23 ++--
 test/unit/vy_iterators_helper.h |   3 +-
 test/unit/vy_mem.c              |   8 +-
 test/unit/vy_point_lookup.c     |  20 ++-
 test/unit/vy_write_iterator.c   |   3 +-
 test/vinyl/stat.result          |   2 +-
 35 files changed, 648 insertions(+), 748 deletions(-)

-- 
2.11.0