I am using a Key-value datastore with the base functionality of
put(String bucketName, String, byte[] value);
byte[] get(String bucketName, String key);
List<String> getKeys(String bucketName, String prefix, int maxKeys);
delete(String bucketName, String key);
And for the sake of argument, let's assume that these API calls directly interfaces to object storage that can store millions of values, get value using keys fast, get keys (by prefix only, no suffix no regex capability), and delete a value using a key. All these can be done efficiently and very optimal, what it cannot do is search by value nor search by a key suffix, regex, or any query for that matter. There's also no transactions, meaning we can't do "all-or-not-at-all" batch operations, each operation is on its own. Furthermore, there is no way for me to modify the behavior of the server, our library can only interface to it through that API performing such operations, and also create collections/buckets. That's about it.
My question here is being a Key-value datastore, how would you implement a query functionality on top of this limited datastore operations? For what I understand, for example, Google BigTable is also a Key-value store and can't also search/query keys and values inside keys, so how it is possible for such datastore to be used with queries, especially that it is used as the underlying storage of Google App Engine datastore? What is the key concept there?
What can be layered on top of this API as such it will be possible to do queries?
My initial idea is I would need to create an "index" collection/bucket to achieve this, but, I would like to know from datastore experts.