Implement skip for ExternalIterator

[webmaster128]

Right now skipping elements decodes the result region which we don't need as the value is dropped. We can just do

        let next_result = unsafe { db_next(self.iterator_id) };
        let kv_region_ptr = next_result as *mut Region;
        let _kv = unsafe { consume_region(kv_region_ptr) };

instead.

This improvement alone is not a game changer but in a follow-up step we can then add a db_skip(self.iterator_id) low import that does not write key and value to Wasm at all.

[ethanfrey]

Huh, you want to override the trait method on the Rust side. Is this called somewhere? (We use limit a lot of places, but I don't think that calls skip. What composition would call this?)

Also seems they recommend overriding nth: https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.skip

[webmaster128]

You need this when doing iteration with offsets (pagination). Right now it just calls next for every skipped element, which is horribly inefficient. Once we have a custom implementation (skip or nth, depending on what makes sense here), we will see that this can be improved by having a db_skip import that does not load the unused key/value into Wasm.

[ethanfrey]

Oh, who uses pagination with numeric offsets? That is always terribly inefficient.
I learned that back in web land when handling large collections backed by PostgreSQL.

Proper way is to provide some cursor like start_after which can be translated to the last key show to efficiently iterate after that. Whoever is doing this other approach should learn better design.

Not saying we can't do this, but it is covering up a problematic design... and they will still call the IAVL tree all those times, with 1000+ gas for every value they skip, even if this doesn't cause contract overhead.

[webmaster128]

Yeah I know, I know. It was just the first example that popped up in my mind. I'll come up with a better use case ...

[webmaster128]

This is implemented in #1838. However, Ethan is right and we should be careful when this is actually used. It indicates a bad storage layout.