add get-range queries

[stevelr]

Signed-off-by: stevelr steve@cosmonic.com

[stevelr]

I wasn't able to test the syntax with the latest git version of wit-bindgen since it doesn't currently support the use keyword or some of the other syntax features in this file. Please let me know if there's another parse tool you use.

[stevelr]

Motivation for range support: range support enables a lot of apps that are very hard to implement otherwise. Examples cases:

• simulate "tables" by using table name as a prefix. Delete a table with delete-range. Get all books by querying for prefix("book.")

• implement indexes. If you have a table of books that have keys of the form "book.id" where id is a number or uuid, and values are json data about the book, you can have an author lookup by defining "author.Alice.101", "author.Alice.102", and then get all ids of books written by Alice by querying keys beginning with "author.Alice."

• store a time-based log with keys like "2022-01-01-12:00:00.event.open", then you can query for all events for a date range using a range query.

Downside: why wouldn't you want to do this?

• if the kv does not have a means to sort keys. If the KV is backed by Hashtable, you'd have to build and maintain a separate key index. Most KV stores that I know of do have the ability to scan keys though. (If you were building an in-memory kv and supported the range interface, you might use a BTree map instead of hashmap).

[Mossaka]

I wasn't able to test the syntax with the latest git version of wit-bindgen since it doesn't currently support the use keyword or some of the other syntax features in this file. Please let me know if there's another parse tool you use.

I am not using any parse tools. We can assume use syntax and later adapt to the what wit-bindgen has.

[Gearme]

Just my thoughts on the matter as someone who is basically building the same thing rn - why not use bounds rather than those key-ranges?

variant bound {
  inclusive(bytes),
  exclusive(bytes),
  unbounded
}

with

get-range: func(lower: bound, upper: bound)

Maps pretty well to Rust at least.

In addition (as in the example above) I'll be using bytes (list\<u8> for now) rather than strings for keys: There's cases in which I'll need a range over non-strings (such as big endian i64 timestamps).

[stevelr]

@Gearme the get-range query is over keys, so it should be using the same key type as the whole kvstore. I should have used key instead of string. Per a suggestion from the call earlier today, it should even be option<key> to allow for semantics of "all items up to X", or "all items starting at x".

As to whether keys are binary or strings, that's a good point to raise with the overall interface. The current spec uses strings. If you're using binary keys and had to convert them to base64 to store in this kv store, you wouldn't be able to use the get-range query at all.

@Mossaka @danbugs have you heard other feedback on whether keyvalue keys should be strings or bytes?

[danbugs]

As to whether keys are binary or strings, that's a good point to raise with the overall interface. The current spec uses strings. If you're using binary keys and had to convert them to base64 to store in this kv store, you wouldn't be able to use the get-range query at all.

@Mossaka @danbugs have you heard other feedback on whether keyvalue keys should be strings or bytes?

As far as I recall, this hasn't been brought up before. Regardless, I don't think every implementer supports storing binary data as keys — e.g., iirc, Memcached doesn't.

[Mossaka]

@stevelr could you please resolve the conflicts? I'd like to merge this PR in sometime later.

[stevelr]

too out of date - closing this. needs to be re-filed as a new PR