Add in scanLimit() to Map?

[ByronBecker]

The source this map was taken from has a scanLimit() functionality.

Since the Map is balanced and sorted, having a scan allows someone to paginate through the map which is especially useful for larger data sets or in performance restricted environments. It's one of the super powers of the data structure.

If you'd like to modify the API, I'd recommend keeping:

• a start point to iterate from
• an end point (to stop iterating)
• direction (forward/backward) of pagination
• a limit (to force the user to use pagination and think in terms of ICP canister resource limits)

[ByronBecker]

Tagging @rvanasa here to get a sense of what you'd like the API interface to look like (direct port, or port with some modifications).

[Kamirus]

@ByronBecker are these two functions: entriesFrom and reverseEntriesFrom not enough?
The end point could be specified by Iter.takeWhile and the limit by Iter.take. A composition of these functions should be equivalent, or am I wrong?

[ByronBecker]

Hey @Kamirus, thanks for the suggestion!

With pagination, you want to receive a result that's something like

type PaginationResult<K, V> = {
results : [(K, V)]; // or Iter.Iter<(K, V)>
nextKey : ?K;
};

You can definitely compose these functions, but there's a bit of awkwardness in both retrieving the nextKey while preserving the iterator and not needing to iterate through twice.
Map.entriesFrom - gives the start point
Iter.takeWhile - gives the stop point
Iter.take - gives the limit

But there isn't an obvious, non-duplicative way (without going twice through the iterator) to then get the cursor/next page key after the limit (if it exists) without consuming the iterator before turning it into a result array. Especially with how Iter.toArray() uses a linked list under the hood before converting the LL to an array there's a bit more work one would do to implement this efficiently, while retaining the iterator.

I took a page out of Iter.toArray() and implemented forward Map pagination like this https://icp.ninja/i?s=z8MZ6

Ideally, you'd also include the direction in there as well (#asc/#desc variant)

There are some side effects associated with providing a cursor/nextKey, and using a LL to hold results before converting them to an Array using the array tabulate API is non-obvious (not commonly used either).

Pagination is such a common pattern, that if you ask the developer to implement it each time, they might make mistakes or do it sub-optimally (I probably did that in my example 😅), so it's sort of a bummer to not have it in the base library 🤷‍♂ You're then also creating friction on the developer's side to implement a pattern that should be encouraged for the data structure to excel - pagination, with cursor/next key support.

[Kamirus]

Pagination is such a common pattern, that if you ask the developer to implement it each time, they might make mistakes or do it sub-optimally (I probably did that in my example 😅), so it's sort of a bummer to not have it in the base library 🤷‍♂ ...

Definitely! Personally I'd see a place for such common patterns in the base lib, but I'd first focus on providing general building blocks in base.
Ideally IMO the API should be:

• general and reusable for other data structures, e.g. Iter as input so that any data structure without custom pagination function would work good enough (would just need to provide entries/valuesFrom for efficiency).
• simple and familiar to use, possibly mimicking known APIs from other languages.

I understand the need for the nextKey (which is the first key beyond the limit), so that we can construct the next page starting from this key. I see two use cases let me know which is more common in practice:

1. Implement a general chunks function: (Iter<T>, Nat) -> Iter<[T]>

Get an Iter for the whole range. Materializing Iter.take to an array gives results : [(K, V)]. To get the next page, call again Iter.take |> Iter.toArray on the original iterator. No need for the nextKey, the original iterator is lazy, we just consume limit-amount of elements for each page. This transformation could take an iterator over the whole range and return an iterator over pages: (Iter<T>, Nat) -> Iter<[T]> with pages as arrays for simple materialized results. Similar to an already existing function pure/List.chunks.

2.

The scenario above fails when the original iterator over the whole range gets invalid or unavailable. In this case we need to know where to start the next page, so along with the page we expect to get the 'new starting key for the next page'.

A simple solution is to get the last key of a page [(K, V)], plug it into entriesFrom and do Iter.drop(_, 1) to get the input for the chunks function above.

We might consider adding more specialized types like PaginationResult<K, V> and functions like scanLimit/paginate/...

type PaginationResult<K, V> = {
  results : [(K, V)];
  nextKey : ?K;
};

func paginate<K, V>(map: Map.Map<K, V>, compare : (K, K) -> Order.Order, start : K, end: K, limit : Nat) : PaginationResult<K, V> { ... }

The problem there is how to come up with a good API. Just by looking at the type of your paginate function it's not obvious that it returns me a single page with a nextKey that I should plug into the next paginate call.
Someone coming from SQL would expect to provide both LIMIT and OFFSET.
Someone might expect a "cursor" that is send with the next request to get the "next page".
Etc. So maybe it's better to provide basic building blocks first and then users start to use them to build their commonly used functions and we can then pull them into the base package.

---

Especially with how Iter.toArray() uses a linked list under the hood before converting the LL to an array

The implementation of Iter.toArray() is a bit of a detail here. Definitely worth improving in a separate issue. I'd focus on the API (functions, names, types) and general performance bounds.

---

Ideally, you'd also include the direction in there as well (#asc/#desc variant)

Yes this could be considered for the 'specialized scenerio'. In general case just rely on the reverseEntriesFrom to get the other direction.

---

There are some side effects associated with providing a cursor/nextKey, and using a LL to hold results before converting them to an Array using the array tabulate API is non-obvious (not commonly used either).

Yes, this is unfortunate that creating an array is non-obvious. We had discussions about that on the forum and summarized in this issue #280 . A simple solution is to just use src/List (or pure/List or ...). to start from an empty vector and keep adding elements, converting to an array later.

[ByronBecker]

A simple solution is to get the last key of a page [(K, V)], plug it into entriesFrom and do Iter.drop(_, 1) to get the input for the chunks function above.

@Kamirus This is a nice solution, but wouldn't it need to perform a complete iteration just to get the last entry? Asymptotically it's the same, but if I'm doing pagination on 10k items at a time adding another n iterations just to get the last entry makes a difference (especially on the Internet Computer 😅).

If there was an Iter operation that converted the first n items to an array, and then returned the consumed iterator as well that would work nicely as a building block. Something like:

func consume<T>(iter: Iter.Iter<T>, n) : ([T], Iter.Iter<T>)

Then I could do

let (results, restIter) = consume(BTree.fromEntries(map), n;
// and get the cursor/nextKey from `restIter.next()`

I'd use this instead of Iter.takeWhile() because of the array building overhead associated with the side-effect of that function being passed to takeWhile (especially when you don't know the true size of the array beforehand).

Just by looking at the type of your paginate function it's not obvious that it returns me a single page with a nextKey that I should plug into the next paginate call.
Someone coming from SQL would expect to provide both LIMIT and OFFSET.
Someone might expect a "cursor" that is send with the next request to get the "next page".

How about this?

type PaginationResult<K, V> = {
  results : [(K, V)];
  cursor : ?K; // rename to cursor
};

func paginate<K, V>(
  map: Map.Map<K, V>,
  compare : (K, K) -> Order.Order,
  startKey : K, // renamed, could also call this `cursor`, or `startCursor`
  stopKey: K, // could make the stopKey optional
  direction : { #asc; desc }, // alternatives: `{ #fwd; bwd }` or could make this be a boolean condition
  limit : Nat,
) : PaginationResult<K, V> { ... }

[ByronBecker]

@Kamirus
The SQL pattern has WHERE field >= start AND and field <= end, so start/stop are somewhat equivalent.

The main reason why relational databases have OFFSET + LIMIT is that the relational model is row based, not key ordered and doesn't assume a natural sort order unless ORDER BY is included.

OFFSET has some performance issues though, given that in the traditional implementation the DB has to scan through and find through OFFSET rows and discard those result before returning the next page.

BTrees really shine when using lexicographic traversal "start at this key and walk until that key in this direction". It's one of the things that make NoSQL databases like DynamoDB so powerful and scalable.

Having a start key/stop key is slightly harder to use for casual developers, but it scales much better for paginated data retrieval on the IC.

[Kamirus]

This is a nice solution, but wouldn't it need to perform a complete iteration just to get the last entry?

[(K, V)] is an array, so the index access is const time. To get the last entry you just array[array.size() - 1] (we'll add the Array.last function that does that).

---

func consume<T>(iter: Iter.Iter<T>, n) : ([T], Iter.Iter<T>)

The implementation could be simply:

let array = Iter.take(iter, n) |> Iter.toArray(_);
(array, iter);

To iterate over all the batches you can do the following loop:

// iter over the all the entries from range `[startKey, stopKey)`
let iter = Map.entriesFrom(map, compare, startKey)
  |> Iter.takeWhile<(K, V)>(_, func (k, _) = k < stopKey);

loop {
  let batch = Iter.toArray(Iter.take(iter, limit)); // consume limit-elements from iter
  // ... process the batch ...
  if (batch.size < limit) return ...; // all batches finished
}

If you want to process a single batch only and update the 'cursor' startKey for future processing in another message, then you can:

• No need for a loop
• After processing the batch, consume the next element from the iter by iter.next() and use the key to update the startKey
• Note that iter can no longer be used for batch processing because next() consumed one element. On the next message rebuild the iter

---

I'd use this instead of Iter.takeWhile() because of the array building overhead associated with the side-effect of that function being passed to takeWhile (especially when you don't know the true size of the array beforehand).

I understand the concern about the performance. But I suggest we focus on the basic general API first so that we have a baseline. And then we can run a benchmark to compare the performance and see how much of an overhead we are talking about.

---

type PaginationResult<K, V> = {
  results : [(K, V)];
  cursor : ?K; // rename to cursor
};

func paginate<K, V>(
  map: Map.Map<K, V>,
  compare : (K, K) -> Order.Order,
  startKey : K, // renamed, could also call this `cursor`, or `startCursor`
  stopKey: K, // could make the stopKey optional
  direction : { #asc; desc }, // alternatives: `{ #fwd; bwd }` or could make this be a boolean condition
  limit : Nat,
) : PaginationResult<K, V> { ... }

I think this is a nice API but IMO it would fit better as a separate mops package. I think all the necessary building blocks are there so the implementation would not need the access to the internals of the map implementation, right?

[rvanasa]

This seems like a valuable addition to the base library. Because of the inherent API complexity, it could make sense to initially publish this as a Mops package (paginate?) and then integrate into the new base library with potential API improvements based on real-world usage.

[ByronBecker]

I'll think about writing a package. I see the value you're mentioning in refining/standardizing the API before integrating directly into base.