Try to resolve slow iterator seek with preifx in some condition

Issues Badger
1

When I was trying to change the db engine to badgerdb in some of my projects, I found the iterator Seek with prefix was pretty slow in the following situation:

  • lots of keys we were seeking with prefix didn’t exist
  • lots of keys have lots of versions

Then I use pprof to found out the iterator was still running parseItem even if the current key was not match the prefix.
image

So I fix this by skipping the parseItem process when the current key is not match the prefix.

pr : Improve Iterator Performance of Seeking with Prefix by zzyalbert · Pull Request #1719 · dgraph-io/badger · GitHub

What version of Go are you using (go version)?

go1.16.4

What operating system are you using?

ubuntu

What version of Badger are you using?

3.2103

Does this issue reproduce with the latest master?

yes

Steps to Reproduce the issue

when keys in badger has lots of versions, then iterator.Seek a prefix that didn’t exist.
It was quite slow in compare with leveldb, even in minuts total when seeking 30000 non-existent prefix

What Badger options were set?

default

What did you do?

What did you expect to see?

What did you see instead?