Seek iterator with Reverse doesn't work

[brk0v]

Code:

package main

import (
	"fmt"
	"io/ioutil"
	"log"
	"os"

	"github.com/dgraph-io/badger"
)

func main() {
	dir, err := ioutil.TempDir("", "badger")
	if err != nil {
		log.Fatal(err)
	}
	defer os.RemoveAll(dir)

	opts := badger.DefaultOptions
	opts.Dir = dir
	opts.ValueDir = dir

	db, err := badger.Open(opts)
	if err != nil {
		log.Fatal(err)
	}
	defer db.Close()

	bkey := func(i int) []byte {
		return []byte(fmt.Sprintf("%09d", i))
	}
	bval := func(i int) []byte {
		return []byte(fmt.Sprintf("%025d", i))
	}

	txn := db.NewTransaction(true)

	// Fill in 1000 items
	n := 1000
	for i := 0; i < n; i++ {
		err := txn.Set(bkey(i), bval(i))
		if err != nil {
			log.Fatal(err)
		}
	}

	err = txn.Commit(nil)
	if err != nil {
		log.Fatal(err)
	}

	opt := badger.DefaultIteratorOptions
	opt.PrefetchSize = 10
	opt.Reverse = true

	// Iterate over 1000 items
	var count int
	err = db.View(func(txn *badger.Txn) error {
		it := txn.NewIterator(opt)
		for it.Seek([]byte("0")); it.ValidForPrefix([]byte("0")); it.Next() {
			count++
		}
		return nil
	})
	if err != nil {
		log.Fatal(err)
	}
	fmt.Printf("Counted %d elements", count)
}

This code returns 0 elements in reverse mode and 1000 elements with reverse = false

[janardhan1993]

@brk0v That's the expected behaviour. Seek searches for a key greater than or equal to the specifed key. Say you have the following keys "00" ,"01", "02". When you seek for "01" in reverse mode the iteration would start at "00".
Similarly in your case since you are seeking for "0" it will go past all the values and you won't find anything.

[brk0v]

Ok. Got it.
My case is to emulate some kind of buckets inside badger db. I was adding a prefix to keys. This prefix is a bucket. But with current iterator logic I can't find the last item in my "bucket".

[manishrjain]

You still can. You just need to choose the seek key wisely. Following from @janardhan1993's example, if you have [00, 01, 02], and you want to start from 01, then you can use 01~ (with tilde character). That way, the seek would stop just before 01, and it the first item would be 01.

[rebootcode]

He wanted to get the last item in the bucket, not the first, @manishrjain - I think, you misunderstood his statement.

Getting the reverse latest data from badgerdb is still Pain IA.

[manishrjain]

It's all about the choice of seek key. If you want the first data from reverse, you can just call Rewind after setting Reverse option.

[rebootcode]

There is no way to seek reverse and rewind based on prefix.

[manishrjain]

You can set reverse and then Seek to prefix + 0xFF byte. That'd bring you to prefix.

[AlexMackowiak]

@manishrjain I realize this comment is going on 3 years old, but it's subtly incorrect, and reverse iterating over a prefix with badger is still very difficult to get right.

The method suggested in this issue: to find the last key with prefix [0x1, 0x2], set reverse=true and then Seek to [0x1, 0x2, 0xFF]
But this doesn't quite solve the problem when data exists with both the prefix and the 0xFF byte, as in the following example DB:

0x1 0x2 0x3
0x1 0x2 0x4
0x1 0x2 0xFF <----- reverse-Seek([0x1, 0x2, 0xFF])
0x1 0x2 0xFF 0x1
0x1 0x2 0xFF 0x2
0x1 0x3
0x1 0x3 0x1

I believe the solution that accounts for all cases is much more involved.

1. You need to compute the first key lexicographically greater than [prefix, 0xFF, 0xFF, ..., 0xFF], call this increment(prefix)
   a. increment([0x1, 0x2]) = [0x1, 0x3]
   b. increment([0x1, 0xFF, 0xFF]) = [0x2]
   c. increment([0xFF, 0xFF, 0xFF]) = nil, will need to call it.Rewind() instead
   i. ^ it.Rewind() does NOT work with a prefix AND reverse=True, will need to append one more 0xFF byte than the key length
   ii. So one special case when all bytes are 0xFF: increment([0xFF, 0xFF, 0xFF]) = [0xFF, 0xFF, 0xFF, 0xFF]
2. Then reverse-Seek on increment(prefix)
3. Finally, adjust by calling it.Next() if you arrive at a valid key that doesn't match the prefix. In this case, you have overshot the last key with the prefix by exactly one.

DB without exact match on incremented key:

0x1 0x2 0x3
0x1 0x2 0x4
0x1 0x2 0xFF 
0x1 0x2 0xFF 0x1
0x1 0x2 0xFF 0x2 <--- reverse-Seek([0x1, 0x3]), it.Valid() == true, arrive at the correct final key for the prefix [0x1, 0x2]
0x1 0x3 0x1

DB with exact match on incremented key:

0x1 0x2 0x3
0x1 0x2 0x4
0x1 0x2 0xFF 
0x1 0x2 0xFF 0x1
0x1 0x2 0xFF 0x2 <--- after it.Next(), arrive at the correct final key for the prefix [0x1, 0x2]
0x1 0x3 <----- reverse-Seek([0x1, 0x3]), it.Valid() == false, it.Item() != nil
0x1 0x3 0x1

[msackman]

@AlexMackowiak I don't think what you have will work correctly for case 1c. I've tried ... it doesn't play ball. If your prefix is 0xFF and you want to iterate in reverse, without prior knowledge of the key length, I think it's impossible. It's almost like there's no choice but to reserve part of your key space for "impossible" values so that you can seek to them.
Therefore, IMO, the API / semantics for reverse iteration is quite bad, and needs overhauling.

[AlexMackowiak]

@msackman Yeah you're actually right, I stumbled across this myself in some tests about a week later and I guess I forgot to follow up here. it.Rewind() does not work with a prefix and reverse=true how I expected it should, and I even filed an issue on the forum: https://discuss.dgraph.io/t/iterator-rewind-invalid-with-reverse-true-and-prefix-option-set/15518 but as far as I can tell this is the expected behavior?

I believe the actual case 1c that I ended up writing in my code was just to append as many 0xFF values as (key length +1), and just hope that case doesn't come up much if ever in practice (which is a reasonable assumption for my application).