Normally the key of a map might be a simple address or id, but that doesn’t mean it was limited to those simple things. By understanding how smart contracts’ storage operates and using key permutation, we can achieve a more complex composite key that can be used to index our data in a more enhanced way and make our CosmWasm smart contract experience better.

First, we need to understand how the underlying IAVL+ key-value storage operates.

https://docs.cosmwasm.com/tutorials/storage/key-value-store

The storage of the CosmWasm smart contract is structured with tree modeling. IAVL+ is a kind of self-balancing binary search tree that is used here and has been modified from the original AVL tree to be specially used in smart contract storage.

Imagine each circle is a key, corresponding with a value that is tied to that key. The iteration process can be done through key prefixes. For example, the key JPL has J JP JPL as its prefixes. So looking back range(JP) will contain JPL .

The underlying process of these prefixes is each key has an underlying fixed-length bytes representation. If we let one key length equal to 2 bytes, then one key can contain the value from 0000 to FFFF . For JPL , it will be something like 004A,0050,004C (Comma here is for ease in reading, all bytes are also padded to the left), so we can iterate through range(JP) that will go through 0004,A005,0000 to 004A,0050,FFFF , result in getting JP JPL JPLN JPV JPVS JPVSQ JPVSQ JPVSU JPVX .

As you can see, the iteration is pretty simple (and also limiting). Thus there are many cases where these key iteration is not enough for indexing and do not resonate with state design.

Take a look at the struct below. Let's say each treasure has a unique id and one address can be the owner of multiple treasures.

Treasure Struct And TreasureTy Enum

And if you want to index the treasure by owner and type, you would need 2 distinct maps. One for the owner and one for the type, probably like this.

Mapping

Usage

You can’t do much about this if you want to iterate through all treasures with owner or treasure type as prefixes, but there is a catch.

Using the key pattern above, you can add treasure type to the owner’s composite key to make it indexable by treasure type too.

So the key bytes representation of this map here is like below. (Not representing the real pattern used, just for illustration)** The namespace can/will be neglected from now on.**

Namespace | Address          TreasureTy(u8)   Id(u64)
v         | v                v                v
t_o       | ################ ################ ################

The namespace is the internal top key identifier that will separate your multiple composite key map from each other. The namespace specified can’t be accessed directly through prefix or range . (Although low-level implementation is possible)

There are three options to iterate through the range here.

One is using prefix , prefix will freeze the n — 1 slot of n length composite key and iterate using the last slot as a bound.

Total composite key length = 3Address          TreasureTy(u8)   Id(u64)
(<- Prefix                    ->) (<- Bound    ->)
v                v                v
################ ################ ################

prefix in this case, will be (Addr, TreasureTy) and the bound of that prefix is u64 .

Another method is using sub_prefix , sub_prefix will freeze n — 2 slot of n key. But for normal composite keys that have 2 keys or a single key, this will be a unit type () . For example, Map<Addr, Treasure> and Map<(Addr, u64), Treasure)> will both have a unit() as the sub_prefix .

Total composite key length = 3

Address          TreasureTy(u8)   Id(u64)
(<- Prefix   ->) (<- Bound                     ->)
v                v                v
################ ################ ################

sub_prefix in this case, will be Addr and the bound is (TreasureTy, u64) .

The last option is to create another map accessor to access only the namespace. To put it simply, iterate only through the topnamespace range. Thus return all the values in that namespace.

Total composite key length = 0
Total key's bytes representation length = (Addr,u8,u64).joined_key().len()

Namespace | X                X                X
v         | v                v                v
t_o       | 0000000000000000 0000000000000000 0000000000000000

We can also specify how the struct/enum operates as a storage key too. By implementing PrimaryKey and Prefixes trait, we can fully customize how struct/enum serialize to key bytes representation. And specify how prefix and sub_prefix access the range too.

Using sub_prefix method on treasure_owner to set the address bytes to a specific address, here we will supply a_addr .

Address          TreasureTy(u8)   Id(u64)
v                v                v
0000615F61646472 ################ ################

Then we can use range method chain on Prefix (Helper struct that is the result of prefix and sub_prefix) on accessing the iterator. Note that the bound we used here must be joined key bytes of TreasureTy and u64 as said before.

If we supply None to both bound conditions, it will iterate through all treasures of this address. Equivalent to (u8::min_value(), u64::min_value()) to (u8::max_value(), u64::max_value()) .

Address          TreasureTy(u8)   Id(u64)
v                v                v
0000615F61646472 0000000000000000 0000000000000000

Address          TreasureTy(u8)   Id(u64)
v                v                v
0000615F61646472 00000000000000FF FFFFFFFFFFFFFFFF

If we want to use our own bound, it will have to be in the joined key bytes format of (TreasureTy, u64) .

Suppose that we want to go through this prefix from TreasureTy::Pearl at specific id 3840 to the end of TreasureTy::Coin . A similar representation will be (0,3840) to (1,u64::max_value()) , and the bytes representation will be as below.

Address          TreasureTy(u8)   Id(u64)
v                v                v
0000615F61646472 0000000000000000 0000000000000F00

Address          TreasureTy(u8)   Id(u64)
v                v                v
0000615F61646472 0000000000000001 FFFFFFFFFFFFFFFF

Remarks: if you use this in query function, as the bound that need to be (TreasureTy,u64) your query start_after pagination parameter might need to look like start_after: (TreasureTy, u64) , or start_after: Treasure , or something like that.

Using prefix method on treasure_owner to set the address and treasure type to specific bytes, here we will supply (a_addr, TreasureTy::BankNote) .

Address          TreasureTy(u8)   Id(u64)
v                v                v
0000615F61646472 0000000000000002 ################

Then we can use range method chain on Prefix like normally we do with a composite key with a two key element. (such as initial treasure_owner )

By using the more complex composite key, and use prefix and sub_prefix that follows the key bytes representation, we can bring out a more helpful iterator that can be used to access our data in a specific way in addition to the original way of indexing.