tarantool / tarantool / 15696

83%

master: 88%

push

travis-ci

vinyl: optimize mem iterator for frequently updated keys

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.

(cherry picked from commit 7383b295e)

24 of 24 new or added lines in 1 file covered. (100.0%)

41226 of 50132 relevant lines covered (82.23%)

867612.26 hits per line