Tarantool development patches archive
 help / color / mirror / Atom feed
From: Kirill Shcherbatov <kshcherbatov@tarantool.org>
To: tarantool-patches@freelists.org, vdavydov.dev@gmail.com
Cc: Kirill Shcherbatov <kshcherbatov@tarantool.org>
Subject: [PATCH v1 0/4] box: introduce hint option for memtx tree index
Date: Tue,  5 Feb 2019 14:58:35 +0300	[thread overview]
Message-ID: <cover.1549367041.git.kshcherbatov@tarantool.org> (raw)

Reworked memtx tree to use 'tuple hints'.
Introduced special functions for retrieve tuple hints for a particular key_def.
Hint is an integer that can be used for tuple comparison optimization:
if a hint of one tuple is less than a hint of another then the first
tuple is definitely less than the second; only if hints are equal
tuple_compare must be called for getting comparison result.

Hints are only useful when:

* they are precalculated and stored along with the tuple;
  calculation is not cheap (cheaper than tuple_compare btw) but
  precalculated hints allow to compare tuples without even fetching
  tuple data.
* first part of key_def is 'string', 'unsigned' or 'integer'
* since hint is calculated using only the first part of key_def
  (and only first several characters if it is a string) this part
  must be different with high probability for every tuple pair.

Enabled hint option improve performance on average by 15%; Select operations
are significantly accelerated (there are scenarios in which the difference
reaches 200-250%).

http://github.com/tarantool/tarantool/tree/kshch/gh-3961-tuple-hints
https://github.com/tarantool/tarantool/issues/3961

Kirill Shcherbatov (3):
  lib: introduce BPS_TREE_EQUAL custom comparator
  box: rework memtx_tree class to be reusable
  box: introduce hint option for memtx tree index

Alexandr Lyapunov (1):
  box: introduce tuple compare hint

 src/box/index_def.c                 |   2 +
 src/box/index_def.h                 |   6 +
 src/box/key_def.c                   |   1 +
 src/box/key_def.h                   |  11 +
 src/box/lua/schema.lua              |  12 +
 src/box/lua/space.cc                |   5 +
 src/box/memtx_tree.c                | 851 ++++++------------------
 src/box/memtx_tree.h                |  68 +-
 src/box/memtx_tree_impl.h           | 960 ++++++++++++++++++++++++++++
 src/box/tuple_compare.cc            | 131 ++++
 src/box/tuple_compare.h             |  40 ++
 src/coll.c                          |  23 +
 src/coll.h                          |   3 +
 src/lib/salad/bps_tree.h            |  74 ++-
 test/box/tree_pk.result             | 220 +++++++
 test/box/tree_pk.test.lua           |  88 +++
 test/box/tree_pk_multipart.result   | 155 +++++
 test/box/tree_pk_multipart.test.lua |  65 ++
 test/unit/bps_tree_iterator.cc      |  15 +-
 19 files changed, 1989 insertions(+), 741 deletions(-)
 create mode 100644 src/box/memtx_tree_impl.h

-- 
2.20.1

             reply	other threads:[~2019-02-05 11:58 UTC|newest]

Thread overview: 9+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-02-05 11:58 Kirill Shcherbatov [this message]
2019-02-05 11:58 ` [PATCH v1 1/4] lib: introduce BPS_TREE_EQUAL custom comparator Kirill Shcherbatov
2019-02-11 15:46   ` Vladimir Davydov
2019-02-05 11:58 ` [PATCH v1 2/4] box: rework memtx_tree class to be reusable Kirill Shcherbatov
2019-02-11 15:49   ` Vladimir Davydov
2019-02-05 11:58 ` [PATCH v1 3/4] box: introduce tuple compare hint Kirill Shcherbatov
2019-02-11 15:57   ` Vladimir Davydov
2019-02-05 11:58 ` [PATCH v1 4/4] box: introduce hint option for memtx tree index Kirill Shcherbatov
2019-02-11 16:12   ` 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.1549367041.git.kshcherbatov@tarantool.org \
    --to=kshcherbatov@tarantool.org \
    --cc=tarantool-patches@freelists.org \
    --cc=vdavydov.dev@gmail.com \
    --subject='Re: [PATCH v1 0/4] box: introduce hint option for memtx tree index' \
    /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