Complexity of StorageDoubleMap::remove_prefix

Question

The official documentation of StorageMaps states

An implementation of a map with a two keys.

It provides an important ability to efficiently remove all entries that have a common first key.

https://docs.substrate.io/rustdocs/latest/frame_support/storage/trait.StorageDoubleMap.html

This reference to efficiency suggests that remove_prefix would not require the naive O(N) database operations, where N is the number of mappings under the given first key, but rather something sublinear, like O(1) or O(log N).

However, I have also asked around about this, and received, the opposite information, I would just love to get a conclusive answer.

1. What is the running time in terms of number of mappings under the key to be removed.
2. If the time is just O(N), in what sense is this efficient?

Answer 1

Efficiently here is probably a poor choice of words, and I think simply refers to the ease of calling the API. I will make a PR to update the wording here.

There is no magic that can happen with adding or removing keys from the database, you must write and update the merkle trie, which involves removing all of the database entries for those storage values and the subsequent trie nodes that are generated. This where all the complexity comes from.

remove_prefix still behaves O(N), and the underlying implementation just uses an iterator.

If you plan to use remove_prefix, you should consider whether you should be using a BoundedVec, where removal of all items is a single storage operation.

Otherwise, you should use the second parameter to remove_prefix:

pub fn remove_prefix<KArg1: ?Sized>(
    k1: KArg1,
    limit: Option<u32>
) -> KillStorageResult

limit allows you to put an upper limit to the number of items that remove_prefix will do at once, and you can schedule a removal over multiple blocks to keep your runtime logic bounded.