API for string prefix queries within Tuples

Sometimes, there is a need to do string prefix queries inside a tuple element (i.e. all tuples (a, b, str…, …) that start with (a, b, str)). Our current range query does not provide the ability to treat str as a prefix, rather it returns all sub-tuples with str as the last element in the prefix tuple, i.e. (a, b, str, …).

It’s actually somewhat complicated for people to implement this themselves. There are multiple choices for begin key that would determine which of the following keys would be the first included:

1. (a, b, str)
2. (a, b, str, …)
3. (a, b, str…)
4. (a, b, str…, …)

There is no key that separates 3 and 4 in general, but you could draw a line before 1, 2, or 3.

Then there’s the matter of the end key. I believe the strictly correct end key is the encoding of (a, b, sts) with the trailing null byte removed (sts is obtained by running strinc(str)), but we don’t publish strinc in all of our bindings, and even then it only works on byte arrays. Also, it fails if called on a string consisting only of 0 or more \xff characters. It can be used on \xff strings or unicode by packing (a, b, str), removing the trailing null byte, and then passing the result to strinc, but that trick is dependent on our particular encoding, and it’s not at all obvious that it should work.

An API for this could produce the correct end key as well as 1 or more options for the begin key without requiring the user to reason through all of this and risk getting it wrong in subtle ways.

This should work on all Tuple types that one could want to do prefix queries on, the obvious ones being byte strings and Unicode strings. It's possible that this could also apply to nested Tuples.

Start by locating the existing range-query and Tuple APIs across the bindings, then review how strinc and string or byte-string encoding are exposed. Define the supported prefix cases and verify begin and end keys for byte strings, Unicode strings, and any nested Tuples. Done means callers can perform these prefix queries without reproducing encoding logic or missing the stated edge cases.

Written by the indexing model from the issue text.