Range query of composite keys

[bestbeforetoday]

Initially raised by @aklenik on Discord.

As I see, the functionality of the range query is limited across all chaincode SDKs to simple keys. However, behind the scenes, the range query methods of the SDKs call the same backing function as the partial query functions, which don't have the same limitations. That means that the reason for the limitation is not technical, since a range CAN be queried using composite keys.

I can't really wrap my head around the why. Using composite keys is the recommended approach for defining structured and robust key spaces. While range query is a strong update-compatible API feature for efficiently traversing well-designed key spaces. The combination of the two is so evident that I was really surprised to see it fail.

[bestbeforetoday]

For reference, a related discussion that I dug out of the old Jira data:

When we do range query on simple keys, it does return composite key as well. For example, the following range query on marble02 chaincode example returns both simple key such as marble2, marble3, and composite key such as colornamebluemarble2, colornamebluemarble2 where it should have returned only marble2 and marble3.

$ peer chaincode query -n mycc1 -v 0 -c {"Args":["getMarblesByRange","a","z"]} -o 127.0.0.1:7050 -C ch1
Query Result: [

{"Key":"color~namebluemarble3", "Record":} \{"Key":"color~nameredmarble2", "Record":}

{"Key":"marble2", "Record":\{"docType":"marble","name":"marble2","color":"red","size":50,"owner":"tom"}},
{"Key":"marble3", "Record":\{"docType":"marble","name":"marble3","color":"blue","size":70,"owner":"tom"}}

How fabric can differentiate between a simple or composite so that GetStateByRange() can return only simple keys?

Approach-1 Ledger adds a null character 0x00 as a first character in simple key.
The constructCompositeKey(namespace, key) in ledger check whether the key contains \x00. If it does not contain \x00, then the key is a simple key and add a \x00 in the front of the key. The splitCompositeKey() removes the added \x00 in the front of the key if exist. For this approach to work, we shouldn't allow 0x00 in original simple key. Still, this approach will not work as PutState() cannot be used for both simple key and composite key when we want to allow \x00 in composite key (added by CreateCompositeKey) but not in simplekey.

Approach-2: Ledger adds a null character 0x00 as a first character in simple key
This approach is an extension to approach-1. Expose a new chaincode API named PutCompositeState(objectType, attributes, value). Internally, we can call createCompositeKey() instead of exposing an API for that followed by handlePutState(). We have done a similar thing in GetStateByPartialCompositeKey(objectType, attributes). This would simplify the chaincode as well. We can then let chaincode use PutState() API only for simple key and do not allow \x00. At ledger side, we use the approach-1 .

Approach-3: Add a separate namespace for simple and composite key.
Expose two new chaincode APIs named GetCompositeState() and PutCompositeState(). In front to the composite key, chaincode APIs adds c to denote that the key is composite. Similarly, chaincode APIs such as GetState(), PutState(), GetStateByRange() adds ‘s’ in the front of simple key. At ledger side, Next() of each result iterator removes ‘c’ or ‘s’ from the front of each key.

Approach-4 Add separate namespace for simple and composite key.
Instead of adding ‘c’ and ‘s’ from chaincode APIs, we can add these namespace in ledger side. For this, we need to expose two new chaincode APIs and ledger APIs named GetCompositeState() and PutCompositeState(). Now, the ledger API adds ‘s’ and ‘c’ and Next() of each result iterator removes ‘c’ or ‘s’ from the front of each key.

Approach-5 Chaincode API CreateCompositeKey adds a null character 0x00 as a first character in composite key.
In current implementation of GetStateByRange(), we are not concatenating anything with startKey and endKey. In GetStateByPartialCompositeKey(), we concatenate U+10FFFF with the endKey. Hence, prepending 0x00 on composite key will not induce a collision. For this approach to work, we shouldn’t allow 0x00 as first character in simple key. Still, this approach will not work as PutState() cannot be used for both simple key and composite key when we want to allow \x00 as first character in composite key (added by CreateCompositeKey) but not in simplekey.

If startKey of a range query is empty (for an open ended search), current implementation treats the startKey as 0x00 (null). Hence, we replace the empty startKey with 0x01 to avoid collision. Now, there is no collision when chaincode issues open-ended search like (i) startKey="" endKey="", (ii) startKey="a" endKey="z".

TODO: we need to document somewhere that a simpleKey cannot start with a null (0x00) as we cannot introduce a new chaincode API PutCompositeState() at this time.

---

Composite keys (ck) have an objectType prefix. Each part of composite key is delimited by null character, for example (spaces included for visual clarity only):

chaincodeid 0x00 objectType 0x00 ck1 0x00 ck2 0x00// composite key

This design ensures that various composite key types have an objectType namespace to guarantee no collisions across types. For example range queries and partial composite key queries will never overlap.

Issue: Simple keys (sk) and composite key objectType are in the same namespace. Range queries on simple keys will pick up composite keys in an objectType scope. They should be in different scopes to ensure no collisions. To illustrate the issue, note that simple key and composite key objectType are in the same namespace / level:

chaincodeid 0x00 sk                   // simple key 
chaincodeid 0x00 objectType 0x00 ck1 0x00 ck2 0x00   // composite key

Solution
Automatically put simple keys in a reserved namespace, for example the empty “” object space.

Note the simple key and composite key distinct namespaces now (spaces added for visual clarity):

chaincodeid 0x00                    0x00 sk         // simple key
chaincodeid 0x00 objectType 0x00 ck1 0x00 ck2 0x00// composite key 

A range query from a to z on a simple key would look like:

chaincodeid 0x00 0x00 a  TO   chaincodeid 0x00 0x00 z

---

Approach 2,3,4 are out assuming we do not allow chaincode API changes.

Can approach 1 and approach 5 work, if we document (but don't validate in code) that simple keys, or any part of a composite key, should not contain 0x00?

---

Yes, both approach would work for that assumption. Currently, we are checking for 0x00 in attributes of composite key and return error if exist. We only need to document for simple keys.

Approach 1 requires change only in ledger side whereas Approach 5 requires change only in chaincode shim.

---

After discussion with Senthil it was decided to proceed with Approach 5. [~Senthil1] Please add any more details to the Approach 5 Description above, for example the unbounded range query impact and anything else you find during imlementation. Also note the typo ""CreateCompositeCreate"" :-)

---

Before this change, it was possible to specify composite keys as parameters to getStateByRange(), now it is not possible. Was this intended?

---

Yes, it was intended. Now, getStateByRange() returns only simple keys and getStateByPartialCompositeKey() returns only composite keys. We have different namespaces for simple keys and composite keys to avoid collisions.

---

Let me be devil's advocate and propose relaxing the validation constraint...

If we allowed getStateByRange() to accept composite keys, I can see there would be collisions on the open-ended range queries.

But if we allowed it when both startKey and endKey were included, I think there would be value without issues.

Using the marbles02 example, say I want to query for blue marble1 through blue marble9, where <color,id> is the composite key. Wouldn't it be safe to query on <blue,marble1> to <blue,marble9>?

So perhaps instead of rejecting all range queries with composite keys, we could relax it and instead validate that the first parts of the composite keys are the same in startKey and endKey. I believe this would protect against the concerns, while allowing range queries within a composite key space. What do you think?

[bestbeforetoday]

Response from @aklenik (on Discord):

Thank you for digging this up, I completely forgot about the Jira era 😅

Accepting that the above behavior won't change, I'd still like to add the following notes:

1. The underlying lexicographical ordering of keys and the ability to compose keys from attribute values in a specific order are together powerful tools for KV stores to design complex key spaces.
2. The referenced Jira issue shows an overly simplified (and definitely not robust or representative) query for a barely designed key space (at least, I wouldn't call it production-ready). Which is fine for an example chaincode. But then a powerful Fabric feature was pulled down to its level, and I think that was a questionable choice at least.
3. The last comment makes a reasonable compromise by introducing composite key overloads for the range query (the partial query already has similar overloads for different key types).
4. The underlying KV storages don't have the notion of simple and composite keys (as far as I know), and the CreateCompositeKey function also returns a raw string in most SDK APIs (the Java SDK has an explicit class for it, but at the end it's also toStringed). The "simple key" notion also doesn't appear in the API functions. So from my point of view, the simple vs composite key differentiation is artificially introduced between layers that don't expect it. If a data modeler knows that the underlying storage is lexicographically ordered KV pairs (supporting range and prefix queries) and the CRUD functions expect a simple string as a key, then they rightfully assume that that is all there is to string keys. Until they see the range query error about supporting only "simple" keys. And that's not intuitive at all.

I'd welcome any input on this from anyone, it's possible I only see a partial picture. In the meantime, our team will probably need to duplicate the composite key structure in the "simple" namespace (although that means losing partial query support...)

[pfi79]

My claims is with the Range query:

• For some calls (like GetStateByRange), the iterator when Next is called, each call sends a message to the peer. This is very slow, and expensive.
• For other calls (for example GetStateByRangeWithPagination) all values are immediately returned to the chaincode and during the enumeration we don't send messages to the peer. But the returned array doesn't check the size. But the size of the message may suddenly exceed the grpc window size
• GetStateByRangeWithPagination is not allowed to be used when changing data - this is fine. You can use GetStateByRange when changing data, but this call has a limit on the number of returned values. For non-composite keys, I can get around this limitation by using multiple calls to GetStateByRange. But for composite keys I can't, so I don't recommend using them for now.