[PATCH 2/2] vinyl: optimize mem iterator for frequently updated keys

Vladimir Davydov vdavydov.dev at gmail.com
Thu Feb 28 14:09:24 MSK 2019

On Thu, Feb 28, 2019 at 12:37:20AM +0300, Vladimir Davydov wrote:
> If a key is frequently updated, iteration to the next key stored in the
> memory level can take quite a while, because:
>  - In case of GE/GT iterator, vy_mem_iterator_next_key will have to
>    iterate the tree from left to right to skip older key versions.
>  - In case of LE/LT iterator, vy_mem_iterator_find_lsn will have to
>    iterate the tree from right to left to find the newest key version
>    visible in the read view.
> To avoid that, let's fall back on key lookup if we failed to find an
> appropriate statement after one iteration, because in this case there's
> a good chance that there's more statements for this key. This should be
> fine since a lookup in a memory tree is pretty cheap.
> ---
> https://github.com/tarantool/tarantool/commits/dv/vy-optimize-next-key
>  src/box/vy_mem.c | 80 ++++++++++++++++++++++++++++++++++++++++----------------
>  1 file changed, 57 insertions(+), 23 deletions(-)

Pushed to 2.1. Will backport to 1.10 once stability test passes.

More information about the Tarantool-patches mailing list