Data

Pagination and Search System Design

Returning a slice of a large table with a total, a sort, a filter and a search box, without the query getting slower as the table grows.

internal/paginateinternal/services

1.Problem statement

Every list endpoint in the application is the same endpoint. Give me page three of the orders, sorted by date, filtered to the ones that are unpaid, matching the text someone typed, and tell me how many there are in total so I can draw the page numbers.

Written by hand per resource, that becomes forty slightly different implementations. Some validate the sort column and some interpolate it into the SQL. Some cap the page size and some let a caller ask for a million rows. Some count with the filters applied and some count the whole table, which makes the page count wrong. The variations are invisible until one of them is the one with the injection.

There is also a limit nobody hits until they do. Offset pagination asks the database to produce and discard every row before the one you want, so page five thousand reads five thousand pages worth of rows to return twenty. The fix is keyset pagination, which is strictly better for scrolling and cannot produce page numbers, so both have to exist and the choice has to be per request.

The system has to be able to:

Bind page, size, sort, order, search and filters from the query string once, for every resource.
Validate the sort and filter columns against a whitelist, never interpolate what a caller sent.
Cap the page size, so no request can ask for the whole table.
Return the total and the page count, computed over the same filters as the page.
Offer keyset pagination for deep lists, where offset stops being viable.
Answer the extra counts a dashboard needs on the same request rather than one request per card.
Search across the columns the resource says are searchable.

2.System requirements

Functional requirements

Default page 1, default size 20, maximum size 100.
Default sort created_at descending, overridable per resource.
Sort column checked against the resource whitelist; anything else falls back to the default.
Filters from query parameters, applied only for whitelisted columns.
An IN filter for id columns, opted into per column rather than inferred.
Date range filtering on a named column.
Full text search across declared columns.
Cursor mode, requested explicitly or implied by sending a cursor.
Extra counts, a time series and a per-value breakdown, all on the list request.

Non-functional requirements

No interpolation, ever. a sort column is the one place a list endpoint cannot use a bound parameter, which makes it the one place a whitelist is mandatory rather than advisable.
Bounded by construction. the maximum page size is enforced in the binder, not asked of each handler. A handler cannot forget it.
Consistent envelope. every list returns data and meta in the same shape, so one client-side hook works for every resource.
Zero is an answer. the counts are serialised without omitempty. An empty table reporting no total at all leaves every client doing arithmetic on undefined.
Honest about mode. a cursor response says so, because total, page and pages are all zero in cursor mode and a client cannot otherwise distinguish that from an empty table.

3.Capacity estimation

Numbers for a mid-sized deployment. They are here to size the thing, not to predict your traffic: change an assumption and the sums below move with it.

Assumptions

Parameter	Value
List requests per second	~550 at peak
Default page size	20
Rows in a large table	10,000,000
Indexed sort column	created_at
Share of requests on page 1	~85%

Offset cost by depth

page 1: LIMIT 20 OFFSET 0, reads 20 rows

page 100: LIMIT 20 OFFSET 1,980, reads 2,000 rows

page 10,000: LIMIT 20 OFFSET 199,980, reads 200,000 rows

The cost is linear in the page number. Fine for an admin table nobody pages past thirty, fatal for an export loop or an infinite scroll.

Keyset cost by depth

WHERE (created_at, id) < (?, ?) ORDER BY created_at DESC, id DESC LIMIT 20

an index seek plus 20 rows, at any depth

page 10,000 costs what page 1 costs

The count is the expensive part

COUNT(*) with filters on 10,000,000 rows: hundreds of milliseconds

the page itself: single-digit milliseconds on an indexed sort

so the total, not the page, dominates a list request

Which is why cursor mode does not count unless asked, and why the dashboard counts are opt-in per request rather than always computed.

Payload

20 rows x ~1.5 KB = 30 KB per page

550 requests/s x 30 KB = ~16 MB/s before compression

with gzip, roughly 4 MB/s

4.High level design

One binder turns the query string into a validated structure. One list function turns that structure plus a whitelist into a query and an envelope.

Core components

Params. the normalised query state. Produced from the request once, with everything already clamped to its limits.
Config. what this resource allows: which columns are sortable, filterable and searchable, and what the default sort is. The whitelist lives with the resource, not in the binder.
Query builder. applies search, filters, the date range and the sort, then either an offset and a limit or a keyset predicate.
Counter. the total over the same filters as the page, plus whatever extra counts were asked for.
Cursor codec. encodes the sort value and the id of the last row as an opaque token, so pages stay stable when rows are inserted mid-pagination.
Meta. the envelope. Page and pages in offset mode, next cursor and has-more in cursor mode, and the mode itself so the client can tell.

Request flow

A list request, from query string to envelope

1A list request arrives with page, size, sort, order, search and whatever filters the interface offers.
2Everything is bound and clamped. A size of 5,000 becomes 100, a page of minus one becomes 1, and the reserved words are separated from the arbitrary query parameters so the whitelist can be applied to the arbitrary ones and only those.
3The resource config says what is allowed. A sort column not on the list is not an error, it is the default sort, because a stale bookmark should return rows rather than a 400.
4The query is assembled: the search across the searchable columns, the whitelisted filters, the date range, the validated sort.
5The ownership scope is applied last, by the same code the single-record read uses. A list is the easiest place to leak another tenant’s rows, so this is not something the list builder is trusted to remember.
6The page is read. In offset mode that is a limit and an offset; in cursor mode a keyset predicate on the sort value and the id.
7The total is counted over the same filters, and any extra counts, series or breakdowns the request asked for are computed alongside it rather than as separate requests.
8The envelope is assembled. Offset mode gets page and pages, cursor mode gets a next cursor and has-more and says that it is cursor mode, and both get the data under the same key.

Data flow

The count uses the same filters and search as the page. Counting the unfiltered table is the commonest way to get a page count wrong, and it is wrong in the direction that shows empty pages.
The cursor encodes the sort value and the id together, because a sort value is not unique and a cursor on the value alone either skips or repeats rows.
Search is applied to declared columns only. Searching everything means searching columns with indexes nobody built.
The IN filter splits on commas and is therefore only enabled for id columns, where a comma never appears in a value. For anything a person types, "Smith, John" is one value.

5.Technology stack

Component	What it is
Binder	one function, every list endpoint
Defaults	page 1, size 20, maximum 100, sort created_at desc
Modes	offset by default, keyset on request
Safety	column whitelists per resource, bound parameters everywhere else
Envelope	data plus meta, identical across resources
Extras	counts, series and breakdown on the same request

6.API design

The list surface, identical for every resource

Method	Endpoint	What it does
GET	/api/v1/orders?page=2&page_size=50	Offset pagination, capped at 100
GET	/api/v1/orders?sort_by=total&sort_order=asc	Sort, validated against the whitelist
GET	/api/v1/orders?search=invoice	Search across the declared columns
GET	/api/v1/orders?status=unpaid	Filter, whitelisted per column
GET	/api/v1/orders?mode=cursor	Keyset pagination, flat cost at any depth
GET	/api/v1/orders?counts=created_7d	Extra totals beside the page

An offset response

{
  "data": [ { "id": "01a1...", "total": 1250 } ],
  "meta": {
    "total": 4821,
    "page": 2,
    "page_size": 50,
    "pages": 97,
    "counts": { "created_7d": 112 }
  }
}

A cursor response, which has no page numbers on purpose

{
  "data": [ { "id": "01a1...", "total": 1250 } ],
  "meta": {
    "total": 0,
    "page": 0,
    "page_size": 20,
    "pages": 0,
    "mode": "cursor",
    "next_cursor": "eyJ2IjoiMjAyNi0xMC0wOSIsImkiOiIwMWEx...",
    "has_more": true
  }
}

7.Low level design

Core types

paginate.Paramsinternal/paginate/paginate.go

The bound query state. Reserved words are parsed into fields; everything else goes into a separate map so the whitelist applies to untrusted input and only to untrusted input.

paginate.Config

Per resource: sortable, filterable, searchable, the defaults, and whether cursor mode and the total are available.

paginate.List

Generic over the row type. Takes a query, params and config, returns the typed result and the meta.

List

paginate.Meta

The envelope. The counts have no omitempty, deliberately: a missing total is worse than a zero one.

Design principles applied

Validate in one place. forty handlers each checking a sort column means thirty-nine chances to get it right and one not to.
Fall back rather than refuse. an unknown sort column returns the default order. A 400 for a stale bookmark is correct and useless.
Make the expensive thing opt-in. the count dominates the request, so cursor mode does not count and the dashboard extras are asked for explicitly.
Say which mode answered. the zeroes in a cursor response are indistinguishable from an empty table without it.

Patterns

Pattern	Where it is used
Offset pagination	page numbers and a total, linear cost in depth
Keyset pagination	an opaque cursor, flat cost, no page numbers
Whitelist validation	for the one input that cannot be a bound parameter
Query object	one normalised structure instead of a dozen request fields

8.Scalability and performance

An indexed sort column is the single thing that makes a list endpoint fast. Without one, every page is a sort of the whole filtered set.
Offset cost grows with the page number. That is acceptable for a human browsing and unacceptable for a loop, which is what cursor mode is for.
The count is usually the slowest part of a list request, so the cheapest optimisation available is not computing it when nobody is showing it.
The composite index that matters is the sort column plus the id, which is exactly what the keyset predicate uses.
Capping the page size at 100 bounds the worst request anybody can send, which bounds memory and bandwidth per request by construction.
List responses cache well because they are read far more than written, and prefix invalidation on write keeps them honest.

9.Bottlenecks and improvements

What breaks first

Deep offset. page five thousand reads a hundred thousand rows to return twenty, and an export loop walks every page.
Counting on every request. a filtered count on a large table can cost more than the page by an order of magnitude, on every single request.
Unstable pages. rows inserted while somebody pages through offset results shift everything, so a row can be seen twice or missed.
Search without an index. a leading-wildcard LIKE across several columns is a full scan, and it looks fine on a thousand rows.

What to do about it

Cursor mode for anything that walks. exports, infinite scroll, sync. Flat cost and stable pages, at the price of page numbers nobody was showing.
Cache or skip the total. an approximate total from statistics, a cached total on a short lifetime, or no total at all where the interface does not show one.
Index the sort key with the id. the composite index serves both the offset sort and the keyset predicate, and makes the tie-break deterministic.
Move search to the engine built for it. a Postgres full text index on a generated column, or a dedicated search service once the table is large enough that LIKE is the bottleneck.