Iterator Rewind() invalid with reverse=true and prefix option set

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

$ go version
go version go1.16 linux/amd64

What operating system are you using?

WSL on Windows

What version of Badger are you using?

v3.2103.0

Does this issue reproduce with the latest master?

Haven’t tested, but I don’t see any fixes in the changelog

Steps to Reproduce the issue

func TestBadgerPrefixRewind(t *testing.T) {
	db, err := badger.Open(badger.DefaultOptions("").WithInMemory(true))
	assert.NoError(t, err)
	err = db.Update(func(txn *badger.Txn) error {
		testMapping := map[string]byte{
			"test1/abc": 0x1,
			"test1/def": 0x2,
			"test2/abc": 0x3,
			"test2/def": 0x4,
			"test3/abc": 0x5,
			"test3/def": 0x6,
		}
		for key, value := range testMapping {
			if err := txn.Set([]byte(key), []byte{value}); err != nil {
				return err
			}
		}
		return nil
	})
	assert.NoError(t, err)

	options := badger.DefaultIteratorOptions
	options.Prefix = []byte("test2/")
	for _, reverse := range []bool{false, true} {
		options.Reverse = reverse

		_ = db.View(func(txn *badger.Txn) error {
			it := txn.NewIterator(options)
			defer it.Close()
			it.Rewind()

			fmt.Printf("reverse=%v\n", reverse)
			fmt.Println("Starting item valid:", it.Valid())
			if it.Item() != nil {
				fmt.Println("Starting item key:", string(it.Item().Key()))
			}
			fmt.Println("All iterated keys:")
			for ; it.Valid(); it.Next() {
				fmt.Println(string(it.Item().Key()))
			}
			fmt.Println()
			return nil
		})
	}
}

What Badger options were set?

Default options, in-memory (although problem exists with on-disk mode as well)

What did you do?

Set both reverse=true and a prefix on an iterator, then called Rewind()

What did you expect to see?

With reverse=false, it.Rewind() seeks to the smallest key matching the prefix (“test2/” in this case).
I would have expected reverse=true + it.Rewind() to seek to the largest key matching the prefix.

What did you see instead?

Test output:

reverse=false
Starting item valid: true
Starting item key: test2/abc
All iterated keys:
test2/abc
test2/def

reverse=true
Starting item valid: false
Starting item key: test1/def
All iterated keys:

it.Rewind() with reverse=true seeks to the largest key just before the start of the prefix. This means it.Valid() is false and it.Next() would only go backwards further past the prefix.

Hi @AlexMackowiak , please check this out https://dgraph.io/docs/badger/faq/#reverse-iteration-doesn-t-give-me-the-right-results

So basically Rewind() just shouldn’t be used at all with a prefix and reverse=true?

I think there are two cases here, and both of them result in Valid() == false:

  1. prefix="test2/" → as shown above we overshoot the range and Next() only takes us further backward.
  2. prefix="test2/0xFF" → in this case, we do arrive at the last key with the prefix "test2/", but because of the 0xFF byte our prefix doesn’t actually match the first key it seeked to and so still Valid() == false

If this is the expected behavior, then so be it, but it doesn’t feel particularly intuitive to me.