Pagination, Part 3: Range Walks and the Truncation Anchor

This is part three of our Pagination series. Part 1 covered slices by position, Part 2 slices by key. This part covers the most common shape for time series, candles, funding rates, fills: a request bounded on both sides, start and end, that returns at most $s$ rows from between them.

Two bounds, one cap

The request names a closed range $[a, b]$ and the server returns the rows inside it, capped at $s$ :

f (a, b, s) = [x : a \leq k (x) \leq b]_{capped at s}

The whole difficulty hides in the word capped. When more than $s$ rows fall in $[a, b]$ , the server keeps the $s$ adjacent to one end. Call that end the anchor:

f_{start} (a, b, s) = the s smallest keys in [a, b] f_{end} (a, b, s) = the s largest keys in [a, b]

The anchor is a property of the endpoint, not of the request. The client cannot choose it, usually cannot read it in the documentation, and gets no error when it guesses wrong.

One request, f(a, b, s = 4), over a range holding twelve rows. Which four come back is a property of the endpoint, and nothing in the response says which it was.

Walking a range

A range walk is Part 2's key cursor with the far bound held fixed. On an end-anchored endpoint the client keeps $a$ and moves $b$ down to the smallest key of each full page; on a start-anchored one it keeps $b$ and moves $a$ up to the largest. The boundary row comes back and is dropped, a short page means the range is exhausted, a full page all at one key cannot be advanced past.

pos ← b; far ← a                          # end-anchored: move b down towards a
C ← ∅
loop:
  rows ← f(far, pos, s)
  yield rows − C
  if |rows| < cap:               stop     # everything left in [far, pos] came back
  m ← min k(x) for x in rows
  if m = pos:                    raise    # full page, one key: unreachable rest
  pos ← m; C ← { x ∈ rows : k(x) = m }

The walk never requests outside $[a, b]$ and never needs to know how many rows fit in a span of time. The width of each request is whatever the data makes it.

Walking an end-anchored endpoint the right way: the end bound follows the smallest key of each full page, the boundary row comes back and is dropped by key, and nothing outside [a, b] is ever requested.

Walking the wrong way

Now run the ascending walk against an end-anchored endpoint. The first request asks for $[a, b]$ and gets the $s$ newest rows. The walk moves $a$ to the largest key, which is already at $b$ , requests $[b, b]$ , gets back the one row it has already seen, and stops. It has yielded $s$ rows of the range and considers itself done.

Nothing in that sequence is an error. Every response was well-formed and every stop condition was legitimately met. A client of ours did exactly this: it asked a venue that keeps the newest rows for six hours of one-minute candles, about 360 rows, received five, and reported success. The direction had been chosen from the order rows appear in on a page, and that order has nothing to do with which end of the range the server fills from. Wire order is presentation. The anchor decides the walk.

The same endpoint walked ascending: the first page is the newest four rows, the moving bound jumps straight to the far end, and the walk finishes with four rows of twelve. Every response was valid.

Measuring the anchor

Since the anchor is rarely stated, measure it: request a range far wider than one page with the smallest size the endpoint accepts, and see which end the rows cluster at. Use a range safely in the past, since a range near the live edge looks start-anchored simply because the newest rows do not exist yet. Across the venues we maintain clients for the split is close to even, and a venue is not always consistent with itself across endpoints, so there is no safe default.

Venues that refuse

Some servers reject a wide range instead of truncating it: Coinbase's candle endpoint errors on any range holding more than 350 candles. The anchor-driven walk cannot even start, because its first request is the widest one. The client then bounds each request's width itself with a span $w$ and moves span by span, keeping the full-page check from before so that a span denser than expected narrows instead of dropping rows:

pos ← b; far ← a
loop:
  edge ← max(pos − w, far)
  rows ← f(edge, pos, s)
  yield rows − C
  if |rows| ≥ cap:    pos ← min k(x); C ← rows at that key      # narrow, as before
  else if edge ≤ far: stop
  else:               pos ← edge; C ← { x ∈ rows : k(x) = edge }

The awkward part is $w$ : 350 one-minute candles is six hours, 350 daily candles is a year, so it depends on the data's density and has to be a parameter the caller can set.

Spans: the caller bounds each request's width with w, moves span by span towards a, and falls back to the narrow-and-carry step whenever a span holds more rows than the cap.

Closing

Three facts fully determine a range walk: the anchor, the cap, and whether the venue truncates or refuses. None of them is reliably documented, and two are cheap to measure. Part 4 turns all of this into recommendations, for the people designing these endpoints and for the people walking them.