From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Date: Thu, 28 Feb 2019 14:09:24 +0300 From: Vladimir Davydov Subject: Re: [PATCH 2/2] vinyl: optimize mem iterator for frequently updated keys Message-ID: <20190228110924.jwe4wtfak2rgx64s@esperanza> References: <3295f9b656c0dcb116de25dea7c87b67b647ca37.1551302815.git.vdavydov.dev@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: To: kostja@tarantool.org Cc: tarantool-patches@freelists.org List-ID: 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.