added Query.SeekPrefix

[drew-512]

[Stebalien]

There should probably be a naive implementation in query_impl.go

[drew-512]

Something like:

type FilterKeySeekPrefix struct {
    SeekPrefix string
}

func (f FilterKeySeekPrefix) Filter(e Entry) bool {
	return e.Key >= f.SeekPrefix
}

and

func NaiveQueryApply(q Query, qr Results) Results {
	if q.Prefix != "" {
		qr = NaiveFilter(qr, FilterKeyPrefix{q.Prefix})
	}
	if q.SeekPrefix != "" {
		qr = NaiveFilter(qr, FilterKeySeekPrefix{q.SeekPrefix})
	}
	...

?

[Stebalien]

That will just act like Prefix. This one will have to skip everything until SeekPrefix. It also needs to be applied after any ordering.

[drew-512]

That will just act like Prefix. This one will have to skip everything until SeekPrefix. It also needs to be applied after any ordering.

Let's say we have entries whose keys are zero-padded time codes for speedy scanning by time: /txn/000009-DEADBEEF /txn/000015-FEEDFACE /txn/000055-BEEFBEEF /txn/000055-B01DFACE /txn/000103-D0D0CACA

.SeekPrefix could be something like /txn/000050 and .Prefix would be /txn/, so the thing I'm seeing is that NaiveQueryApply should look at OrderByKeyDescending (as you described in the other thread) in order to know which way to compare the key with .SeekPrefix:

type FilterKeySeekPrefix struct {
    Ascending bool
    SeekPrefix string
}

func (f FilterKeySeekPrefix) Filter(e Entry) bool {
	if f.Ascending {
		return e.Key >= f.SeekPrefix
	} else {
		return e.Key <= f.SeekPrefix
        }
}

Is the only place NaiveQueryApply is used is in example code? Maybe it was helpful when demoing Datastore way back, but is it likely to ever see production? I would have a sit down w/ someone under me who ever used it, but that's just me. Not that these SeekPrefix changes should drive code to be dropped from ds, but is this candidate code to be dropped? Disclaimer: I'm super OCD about non-production/non-scalable staying around, so feel free to ignore this -- I always like to ask this question. ¯\(ツ)/¯

[Stebalien]

You're right, assuming ordering by key, that should work. Actually, I'm starting to wonder how this should interact with sorting by value. Let's discuss here: https://github.com/ipfs/go-datastore/issues/116#issuecomment-461232579

Is the only place NaiveQueryApply is used is in example code?

We use it in the MapDatastore (in-memory datastore) and many datastores use the component functions (e.g., NaiveFilter).

[drew-512]

Ok cool, thanks for indulging me on that ques and glad you're catching this stuff.

Like that we're gettin through this together and adding a nice feature to ds.

[sanderpick]

This looks pretty stale... does that mean another avenue was chosen? Or key seeking is still not possible?