Concevoir une API paginée qui tient la charge

Un endpoint de liste, c’est le premier morceau d’API qu’on écrit et le dernier auquel on repense.

GET /transactions?page=1&size=20, un ORDER BY created_at DESC, un OFFSET calculé à partir du numéro de page. Ça marche.

Ça marche sur les 10 000 lignes du jeu de test, ça marche sur les 200 000 lignes de la première année de prod, et ça continue de marcher longtemps parce que personne ne va jamais à la page 250 000.

Puis un client branche un connecteur pour rapatrier l’historique complet, et la page 250 000 devient une requête comme les autres.

On se basera sur une table de 10 millions de transactions pour regarder ce qui se passe puis on ira voir ce que des grands de la tech telle que Zalando, Google, Uber et Netflix ont rédigé sur ce sujet dans leurs guidelines respectives.

🎯 Ce que la pagination protège vraiment

La pagination permet de maitriser la consommation mémoire.

Le jour où une requête ramène 4 millions de lignes, votre process les matérialise, les sérialise en JSON, et l’OOM killer tranche le débat. Paginer, c’est poser un plafond connu à l’avance sur ce que peut coûter un appel.

La pagination par offset répond correctement au premier, mais échoue sur le second, et pas seulement pour des raisons de performance.

🐌 OFFSET : ce que la base fait pendant que vous attendez

Le protocole de mesure : PostgreSQL 18.4, une table de 10 millions de transactions, un index qui correspond exactement au tri demandé. Tout est reproductible dans un conteneur jetable.

docker run -d --name pg-pagination \
  --shm-size=1g \
  -e POSTGRES_PASSWORD=pagination \
  -e POSTGRES_DB=pagination \
  -p 5432:5432 \
  postgres:18.4

docker exec -it pg-pagination psql -U postgres -d pagination

Je n’ai touché aucun paramètre de configuration. shared_buffers reste à ses 128 Mo par défaut, très en dessous de la taille de la table, si bien que le cache déborde en permanence. C’est une situation réaliste, et c’est elle qui rend visible le written du plan un peu plus bas. Sur une machine réglée pour la charge, tous les temps absolus seront plus bas, mais les écarts entre profondeurs resteront du même ordre.

Le --shm-size=1g mérite un mot, parce qu’il évite une erreur pénible à diagnostiquer. Docker limite /dev/shm à 64 Mo, or c’est là que les requêtes parallèles allouent la mémoire qu’elles partagent entre workers. Sans ce réglage, le COUNT(*) de la fin de section échoue sur un could not resize shared memory segment.

CREATE TABLE transactions (
  id           bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
  account_id   bigint NOT NULL,
  amount_cents bigint NOT NULL,
  label        text   NOT NULL,
  created_at   timestamptz NOT NULL
);

CREATE INDEX idx_txn_created_id ON transactions (created_at DESC, id DESC);

Reste le jeu de données sur lequel nous allons nous baser :

SELECT setseed(0.42);

INSERT INTO transactions (account_id, amount_cents, label, created_at)
SELECT
  1 + floor(random() * 2000)::bigint,
  floor(random() * 500000)::bigint - 250000,
  (ARRAY['CARTE','VIREMENT','PRELEVEMENT','CHEQUE','RETRAIT'])[1 + floor(random() * 5)::int]
    || ' ' || to_char(i, 'FM00000000'),
  timestamptz '2015-01-01 00:00:00+00' + i * interval '20 seconds'
FROM generate_series(1, 10000000) AS i;

VACUUM ANALYZE transactions;

Quelques choix de ce script méritent d’être explicités.

Les dates avancent de 20 secondes par ligne, du 1ᵉʳ janvier 2015 au 3 mai 2021, donc created_at progresse exactement comme l’id. C’est ce qu’on observe en production, où les lignes s’insèrent dans l’ordre du temps.

Les comptes sont tirés au hasard parmi 2 000, ce qui donne autour de 5 000 lignes chacun. C’est de là que viennent les 4 958 lignes du compte utilisé plus loin, dans la section sur le filtrage par tenant.

Le setseed appelé avant le premier random() fixe la graine du générateur : en rejouant le script sur la même version de PostgreSQL, vous obtiendrez les mêmes comptes et les mêmes montants que moi.

Quant au VACUUM ANALYZE final, il joue deux rôles. Il met à jour les statistiques dont le planificateur se sert pour choisir un plan, et il remplit la carte de visibilité. Sans cette dernière, PostgreSQL doit aller vérifier chaque ligne dans la table et ne peut jamais choisir un Index Only Scan, celui qu’on verra apparaître plus loin.

L’index correspond exactement au tri demandé. Voyons ce que donne la même requête à trois profondeurs.

EXPLAIN (ANALYZE, BUFFERS, COSTS OFF, TIMING OFF)
SELECT id, account_id, amount_cents, created_at
FROM transactions
ORDER BY created_at DESC, id DESC
LIMIT 20 OFFSET 5000000;

Le plan d’exécution montre où part le temps :

Limit (actual rows=20.00 loops=1)
  Buffers: shared hit=6592 read=59298 written=9482
  ->  Index Scan using idx_txn_created_id on transactions (actual rows=5000020.00 loops=1)

actual rows=5000020 sous un LIMIT 20. L’index a été parcouru, ligne par ligne, sur cinq millions d’entrées, pour que le nœud du dessus en jette 5 000 000 et en garde 20.

OFFSET est souvent vu comme une instruction de positionnement. C’est piégeux car il correspond plus à une instruction de rejet, puisqu’il n’existe aucun moyen, dans un B-tree, de « sauter directement à la cinq-millionième feuille » : l’arbre est indexé par valeur, pas par rang. Alors la base lit tout ce qui précède et le met à la poubelle.

Le coût d’une page en OFFSET est proportionnel à sa profondeur, pas à sa taille.

Notez aussi le written=9482 de la deuxième ligne. Notre requête n’écrit rien, elle lit : ce compteur mesure des pages qu’elle a dû évincer du cache, et écrire sur disque avant de libérer la place. Une pagination profonde ne se contente donc pas d’être lente pour celui qui la lance, elle vide le cache des requêtes qui tournent en même temps.

Le vrai problème, la dérive

La performance se contourne, on y vient. La correction, non.

Un client parcourt votre dataset trié par date décroissante. Il lit la page 1 (OFFSET 0), et pendant qu’il la traite, trois transactions sont créées.

Les trois nouvelles lignes se placent en tête. Tout le dataset glisse de trois rangs. Quand le client demande OFFSET 20, il reçoit les lignes qui étaient en position 17, 18 et 19 lors de son premier appel : il les voit deux fois.

Dans l’autre sens (un tri ascendant, ou des suppressions), le décalage joue à l’envers et le client saute des lignes sans jamais le savoir.

Et le compteur total ?

Le total que vous renvoyez pour afficher « page 3 sur 12 458 » coûte plus cher que la page elle-même.

Finalize Aggregate (actual rows=1.00 loops=1)
  ->  Gather (actual rows=3.00 loops=1)
        ->  Parallel Seq Scan on transactions (actual rows=3333333.33 loops=3)
Execution Time: 101.134 ms

101 ms et 93 457 blocs, avec trois workers parallèles, pour produire un entier. La première page coûte 0,025 ms. Le compteur coûte donc 4 000 fois la donnée qu’il accompagne.

C’est exactement pour ça que les guidelines Zalando recommande de ne pas renvoyer de total (règle #254 « SHOULD avoid a total result count »), voir plus bas 👇.

🔑 Le keyset : arrêter de compter, commencer à pointer

L’idée tient en une phrase : au lieu de dire à la base « saute les 5 000 000 premières », on lui dit où on s’est arrêté.

SELECT id, account_id, amount_cents, created_at
FROM transactions
WHERE (created_at, id) < ($1, $2)
ORDER BY created_at DESC, id DESC
LIMIT 20;

(created_at, id) < ($1, $2) est une comparaison de n-uplets, et tout le mécanisme tient là-dedans.

⚠️ Attention au faux ami : l’expression ne se développe pas en created_at < $1 AND id < $2, qui donnerait un faux résultat.
Elle définit un ordre lexicographique, « strictement avant cette date, ou à cette date exacte mais avec un id plus petit ».

C’est l’ordre de l’index, exprimé comme une borne.

En valeurs réelles, le mécanisme se voit mieux.
La première page n’a pas de curseur, donc pas de WHERE. Je prends trois lignes plutôt que vingt, pour que la sortie tienne à l’écran :

SELECT id, created_at FROM transactions
ORDER BY created_at DESC, id DESC
LIMIT 3;

    id    |       created_at
----------+------------------------
 10000000 | 2021-05-03 19:33:20+00
  9999999 | 2021-05-03 19:33:00+00
  9999998 | 2021-05-03 19:32:40+00

La dernière ligne rendue sert de curseur. On recopie ses deux valeurs dans la borne, et on redemande la suite :

SELECT id, created_at FROM transactions
WHERE (created_at, id) < (timestamptz '2021-05-03 19:32:40+00', 9999998)
ORDER BY created_at DESC, id DESC
LIMIT 3;

   id    |       created_at
---------+------------------------
 9999997 | 2021-05-03 19:32:20+00
 9999996 | 2021-05-03 19:32:00+00
 9999995 | 2021-05-03 19:31:40+00

On enchaîne sur 9999997 sans trou ni doublon.

Remarquez surtout qu’aucune des deux requêtes ne mentionne de numéro de page : la seconde ignore qu’elle est « la page 2 », elle sait seulement à partir de quelle position lire. C’est là que se joue la différence avec OFFSET, obligé de compter depuis le début pour retrouver son point de reprise.

PostgreSQL peut donc descendre l’arbre directement sur cette borne. La ligne « profondeur 500 000 » du tableau ci-dessous correspond à cette requête, avec le curseur de la 500 000ᵉ ligne :

EXPLAIN (ANALYZE, BUFFERS, COSTS OFF, TIMING OFF)
SELECT id, account_id, amount_cents, created_at
FROM transactions
WHERE (created_at, id) < (timestamptz '2021-01-08 01:47:00+00', 9500001)
ORDER BY created_at DESC, id DESC
LIMIT 20;

Limit (actual rows=20.00 loops=1)
  Buffers: shared hit=4 read=1
  ->  Index Scan using idx_txn_created_id on transactions (actual rows=20.00 loops=1)
        Index Cond: (ROW(created_at, id) < ROW('2021-01-08 01:47:00+00'::timestamp with time zone, 9500001))
        Index Searches: 1

La ligne à regarder est Index Cond. Quand la borne apparaît à cet endroit, l’index s’en sert pour se positionner avant de lire quoi que ce soit. Si elle apparaissait sous Filter, la base lirait les lignes puis les écarterait une par une, et on retomberait sur le comportement de l’OFFSET : nous verrons plus loin une requête qui bascule justement dans ce cas. D’où le actual rows=20 sous le nœud, contre 5 000 020 pour l’OFFSET de même profondeur.

Pour la profondeur 5 000 000, c’est la même requête avec le curseur (timestamptz '2018-03-03 09:47:00+00', 5000001).

Quatre blocs. Le coût de la page ne dépend plus de sa profondeur : c’est une descente dans le B-tree, puis vingt lignes lues à la suite.
Le même prix à la page 1 et à la page 250 000.

Au passage, la dérive disparaît elle aussi. Le curseur désigne une position dans l’ordre de tri, pas un rang dans un ensemble. Les insertions en tête ne le déplacent pas.

📝 Le tie-breaker n’est pas optionnel

created_at n’est pas unique. Deux transactions à la même microseconde, et l’ordre entre elles n’est pas défini, donc pas stable d’un appel à l’autre. Une page peut en renvoyer une, la suivante renvoyer l’autre… ou aucune des deux.

D’où le id dans la clé de tri et dans le curseur.

La clé de pagination doit se terminer par une colonne unique et NOT NULL.
Sans elle, votre tri est ambigu et votre curseur pointe dans le flou.

🗂️ L’index doit correspondre au tri, pas seulement le contenir

Le keyset ne tient que si l’index permet la descente directe.
Trois pièges concrets, mesurés :

1. Le sens de l’index compte moins qu’on ne croit.
Un index déclaré en ascendant sert un tri descendant, PostgreSQL le parcourt à l’envers :

Index Only Scan Backward using idx_txn_asc on transactions (actual rows=20.00 loops=1)
Execution Time: 0.036 ms

Peu importe le sens déclaré, ce qui compte, c’est que toutes les colonnes aillent dans le même sens.

2. Un tri mixte casse la comparaison de n-uplets.
Si vous voulez ORDER BY created_at DESC, id ASC, l’écriture (created_at, id) < ($1, $2) devient fausse, car la comparaison de n-uplets n’a qu’un sens pour tout le tuple. Il faut développer à la main :

WHERE created_at < $1 OR (created_at = $1 AND id > $2)

C’est faisable, mais c’est aussi une bonne raison de ne pas proposer de tris mixtes dans votre API.

Autrement, il faut accepter le coût d’un index supplémentaire reproduisant ce mélange : (created_at DESC, id ASC)

3. NULL empoisonne la comparaison.
Comme NULL < x vaut NULLet pas false, une colonne de tri nullable rend le prédicat de curseur imprévisible.
Il fait donc varier la position des lignes selon NULLS FIRST/NULLS LAST.

Les colonnes qui composent la clé de pagination doivent être déclarées NOT NULL.

Enfin quand la liste est filtrée par tenant, ce qui est presque toujours le cas, le filtre passe devant dans l’index :

CREATE INDEX idx_txn_acct ON transactions (account_id, created_at DESC, id DESC);

🐛 Le piège du « un seul SQL pour la première page et les suivantes »

Celui-ci mérite sa propre section, parce qu’il annule silencieusement tout le bénéfice et que je suis tombé dedans avant de le comprendre.

La première page n’a pas de curseur.

La tentation est d’écrire une seule requête qui gère les deux cas :

WHERE account_id = $1
  AND ($2::timestamptz IS NULL OR (created_at, id) < ($2, $3))
ORDER BY created_at DESC, id DESC
LIMIT $4;

Tant que PostgreSQL construit un plan custom (paramètres connus à la planification), il simplifie le IS NULL et tout va bien : 0,030 ms, 5 blocs.

Mais un PREPARE réutilisé, le comportement normal de la plupart des drivers dont pgx après quelques exécutions, bascule sur un plan générique, où $2 est inconnu au moment de la planification.
Le prédicat ne peut plus servir de borne d’index et devient un filtre :

Index Only Scan using idx_txn_acct on transactions (actual rows=20.00 loops=1)
  Filter: (($2 IS NULL) OR (ROW(created_at, id) < ROW($2, $3)))
  Rows Removed by Filter: 2508
Execution Time: 0.235 ms

Rows Removed by Filter: 2508 👉 la base est repartie du haut de la partition du compte et a jeté 2 508 lignes avant d’atteindre la page. Ici le compte ne contient que 4 958 lignes, donc les dégâts sont plafonnés. Sur un tenant qui en détient deux millions, vous venez de réinventer OFFSET, avec la syntaxe du keyset en prime.

La parade tient en deux requêtes distinctes, une pour la première page et une pour les suivantes.

🧾 Le curseur opaque

Le client ne doit jamais voir created_at et id.

Pas par coquetterie, mais parce qu’un curseur lisible est un curseur que les clients vont construire eux-mêmes, et le jour où vous changez la clé de tri, vous cassez des intégrations dont vous ignoriez l’existence.

Un curseur opaque est une frontière de contrat. Ce qu’il y a dedans vous appartient.

Ce qu’on y met :

• les valeurs de la clé de tri (la position),
• le sens du tri, pour rejeter un curseur rejoué à l’envers,
• une empreinte des filtres, pour rejeter un curseur rejoué sur une autre requête,
• un numéro de version, pour pouvoir changer le format sans casser les curseurs en circulation.

Et on le signe. Sans signature, un client peut forger une position. Au mieux il obtient des résultats incohérents, au pire il contourne un filtre de sécurité qui vivait dans le curseur.

type Cursor struct {
	Version    int       `json:"v"`
	CreatedAt  time.Time `json:"c"`
	ID         int64     `json:"i"`
	Descending bool      `json:"d"`
	Filters    string    `json:"f"`
}

// Encode sérialise le curseur et le préfixe d'un HMAC : un client ne peut ni forger
// une position, ni rejouer sur une requête un curseur émis pour d'autres filtres.
func Encode(c Cursor, key []byte) (string, error) {
	payload, err := json.Marshal(c)
	if err != nil {
		return "", err
	}
	mac := hmac.New(sha256.New, key)
	mac.Write(payload)
	return base64.RawURLEncoding.EncodeToString(append(mac.Sum(nil), payload...)), nil
}

func Decode(token string, key []byte) (Cursor, error) {
	raw, err := base64.RawURLEncoding.DecodeString(token)
	if err != nil || len(raw) < sha256.Size {
		return Cursor{}, ErrInvalidCursor
	}
	sig, payload := raw[:sha256.Size], raw[sha256.Size:]
	mac := hmac.New(sha256.New, key)
	mac.Write(payload)
	if !hmac.Equal(sig, mac.Sum(nil)) {
		return Cursor{}, ErrInvalidCursor
	}
	var c Cursor
	if err := json.Unmarshal(payload, &c); err != nil || c.Version != cursorVersion {
		return Cursor{}, ErrInvalidCursor
	}
	return c, nil
}

L’empreinte des filtres est une simple somme de contrôle de la requête qui a produit le curseur :

func filterFingerprint(q ListQuery) string {
	sum := sha256.Sum256([]byte(fmt.Sprintf("%d|%s|%s", q.AccountID, q.Status, q.Sort)))
	return base64.RawURLEncoding.EncodeToString(sum[:8])
}

Le handler compare l’empreinte du curseur reçu à celle de la requête courante. Si elles diffèrent, le client a changé de filtre en cours de parcours : c’est un 400, pas une page de résultats incohérents.

🔁 Savoir s’il reste des pages, sans compter

Le client a besoin d’une chose : « y a-t-il une suite ? ». Pas d’un total.

On demande une ligne de plus que la page, et on la jette :

const pageSize = 20

rows, err := repo.List(ctx, q, cursor, pageSize+1)
if err != nil {
	return err
}

hasMore := len(rows) > pageSize
if hasMore {
	rows = rows[:pageSize]
}

Coût : une ligne. À comparer aux 101 ms du COUNT(*).

Le corollaire, c’est que next doit être la seule autorité sur la fin du parcours.

🏛️ Ce que font les autres

Regardons ce que certains géants de la tech font à travers leurs standards d’API.
Elles ne disent pas toutes la même chose :

Uber fait exactement l’inverse de Zalando, et pour de bonnes raisons.

Zalando, les guidelines les plus explicites

Zalando publie ses RESTful API Guidelines en open source, et la section pagination est numérotée règle par règle :

• MUST support pagination (#159)
• SHOULD prefer cursor-based pagination, avoid offset-based pagination (#160)
• SHOULD use pagination response page object (#248)
• SHOULD use pagination links (#161)
• SHOULD avoid a total result count (#254)

Le curseur y est défini comme « an opaque pointer to a page, never to be inspected or constructed by clients », et la réponse expose des liens self, first, prev, next, last. C’est la formulation la plus nette de tout ce qui précède, et c’est la référence à citer en revue d’architecture quand quelqu’un tient à son ?page=.

Google, AIP-158, le vocabulaire de référence

L’AIP-158 fixe trois champs et leur sémantique, et c’est probablement le nommage le plus repris de l’industrie :

• page_size en requête : le serveur choisit un défaut, plafonne les valeurs trop grandes plutôt que de les refuser, et rejette les négatives en INVALID_ARGUMENT.
• page_token en requête, next_page_token en réponse. Vide en fin de collection, jamais absent-mais-non-vide.
• Les tokens sont « opaque (but URL-safe) strings, and must not be user-parseable ». Le texte précise que le base64 seul ne suffit pas comme obfuscation.
• Un token peut expirer (trois jours est la durée suggérée) pour ne pas obliger le service à conserver indéfiniment un état.
• total_size existe, mais reste optionnel et explicitement autorisé à être une estimation.

Deux règles qu’on oublie souvent : le serveur doit honorer un changement de page_size en cours de parcours, mais refuser un changement des autres paramètres. Et ajouter la pagination à une méthode qui n’en avait pas est une rupture de compatibilité, pas une amélioration.

Netflix, la pagination Relay côté GraphQL

Netflix a poussé son API vers GraphQL fédéré, et son framework DGS implémente la spécification Relay Connections. On annote un type avec @connection et le framework génère Connection, Edge et PageInfo :

type MessageConnection {
  edges: [MessageEdge]
  pageInfo: PageInfo
}

type MessageEdge {
  cursor: String
  node: Message
}

type PageInfo {
  hasNextPage: Boolean!
  hasPreviousPage: Boolean!
  startCursor: String
  endCursor: String
}

C’est le même keyset, avec deux différences de conception qui valent d’être notées. Le curseur est porté par chaque élément (edge.cursor), pas seulement par la page : un client peut reprendre depuis n’importe quelle ligne, ce qui est précieux quand il traite les éléments un par un et veut reprendre après un crash. Et PageInfo déclare explicitement la navigation dans les deux sens (hasNextPage, hasPreviousPage), là où beaucoup d’API REST n’exposent qu’un next.

Uber, le contre-exemple utile

Uber, lui, fait de l’offset. Sa Riders API l’assume : « Paginated endpoints follow a standard interface that accepts two query parameters, limit and offset », avec une sémantique explicitement empruntée à PostgreSQL.

Ce n’est pas de la négligence, et c’est la nuance la plus utile de cet article : la taille du dataset qui compte n’est pas celle de la table, c’est celle qui reste après filtrage par le tenant. L’historique de courses d’un utilisateur, c’est quelques centaines de lignes, quelques milliers pour un gros utilisateur. OFFSET 300 sur 800 lignes ne pose aucun problème de performance, et la dérive reste marginale sur un historique qui bouge de deux lignes par semaine.

Le keyset devient nécessaire quand une seule requête cliente peut atteindre une profondeur importante. Si votre endpoint le plus chargé sert 800 lignes par utilisateur, OFFSET restera correct pendant très longtemps, et c’est une décision d’architecture parfaitement défendable.

Et les autres, en une ligne chacun

Ce sont les convergences qui frappent. Presque tout le monde a abandonné le total. Presque tout le monde plafonne le limit côté serveur au lieu de faire confiance au client. Et presque tout le monde a rendu le curseur opaque. Stripe fait exception en connaissance de cause, avec un starting_after qui est simplement l’ID du dernier objet, car chez eux les IDs sont déjà l’ordre de tri et la question ne se pose pas dans les mêmes termes.

📐 Le contrat que je recommande

Reste à trancher, et la réponse dépend moins de la taille de la table que de qui consomme l’endpoint. Les deux usages présentés en ouverture n’appellent pas le même contrat : c’est en cela qu’Uber a raison d’assumer son offset.

Sur un écran de recherche, dans la majorité des cas, KEYSET est toujours à privilégier, surtout qu’aujourd’hui les écrans prônent l’infinite scroll, particulièrement adapté à ce type de pagination.
En revanche, utiliser une pagination par OFFSET reste facile et valide à implémenter lorsqu’ elle est numérotée. L’utilisateur restera le plus souvent sur les premières pages tant que l’interface gêne un maximum la navigation vers les pages les plus profondes.

Sur une API de listing filtrée, consommée par un connecteur, un ETL ou un client qui rapatrie son historique, personne ne demandera jamais la page 12. Le besoin est de rendre chaque ligne une fois et une seule, sur un dataset qui bouge pendant le parcours. Une pagination KEYSET est donc indispensable.

Le contrat détaillé ci-dessous est celui du second cas.

Requête

GET /v1/transactions?account_id=42&limit=50&cursor=A7lWwp1PIljnuvc6o-L43tjU8SUsUs3-7uU1iG_V...

• limit : optionnel, défaut 20, plafonné à 100 côté serveur. On plafonne, on ne rejette pas.
• cursor : optionnel, opaque, signé. Absent = première page.
• Les filtres et le tri sont interdits de changement en cours de parcours : leur empreinte est dans le curseur.

Réponse

{
  "data": [ { "id": "9500000", "amount_cents": 212190, "created_at": "2021-01-08T01:46:40Z" } ],
  "page": {
    "next": "XpQF28PoX3CTQl3hKrIqSdr-SCaQJpMk4jUxxT1-...",
    "has_more": true
  }
}

• Pas de total. Si un client en a vraiment besoin, exposez-le sur un endpoint séparé, en estimation assumée.
• next absent (ou null) est le seul signal de fin.
• has_more est redondant avec next, et c’est volontaire : il rend le contrat lisible sans documentation.

Erreurs

Le 410 Gone sur curseur expiré vaut mieux qu’un 400 : il dit au client que sa demande était bien formée mais que la position n’existe plus, ce qui est exactement l’information dont il a besoin pour décider de repartir du début.

Côté base

• Un index qui couvre (filtres…, clé de tri…, tie-breaker), dans cet ordre.
• Toutes les colonnes de la clé de tri en NOT NULL.
• Deux requêtes distinctes : première page, pages suivantes.
• LIMIT n+1 pour has_more.

En résumé

• OFFSET coûte proportionnellement à la profondeur, pas à la taille de la page : 321 ms et 65 890 blocs pour rendre 20 lignes à 5 millions de profondeur, contre 0,009 ms et 4 blocs en keyset.
• Et la lenteur n’est même pas le pire. Sur un dataset qui bouge, un parcours complet en OFFSET renvoie des doublons et saute des lignes, sans jamais lever d’erreur : c’est la dérive.
• Le keyset repose sur une comparaison de n-uplets alignée sur un index, et sur une clé de tri qui se termine par une colonne unique et NOT NULL.
• Le curseur est opaque et signé : c’est la frontière qui vous laisse changer d’implémentation sans casser vos clients.
• Le COUNT(*) coûte 4 000 fois la page qu’il accompagne. Zalando le déconseille, Stripe et Slack ne le renvoient pas.
• OFFSET reste défendable quand la profondeur atteignable après filtrage par tenant est faible, et il devient carrément le bon choix dès qu’une pagination numérotée doit permettre de sauter à la page N : le keyset, lui, n’atteint qu’un rang arbitraire en le parcourant. C’est le choix d’Uber, et il se défend très bien.

Pour conclure, on finira sur ce petit dicton 👇

Paginer, c’est promettre un parcours qui ne coûte rien tant que personne ne va au-delà de la page 20. Le jour où c’est le cas, il ne reste que le keyset pour tenir cette promesse.

Retrouvez un exemple de code d’implémentation en Go et Java sur github

Crédits & Ressources

• Designing a Pagination API That Scales to 1M Records — le retour d’expérience qui a inspiré cet article : un endpoint de transactions qui tenait à 10 000 lignes et s’écroule à 11 millions
• Zalando RESTful API Guidelines — Pagination — les règles #159 à #254, la référence à citer en revue d’architecture
• Google AIP-158 — Pagination — le vocabulaire page_size / page_token / next_page_token et sa sémantique exacte
• Relay GraphQL Cursor Connections Specification — la spécification derrière Connection, Edge et PageInfo
• Netflix DGS — Relay Pagination — l’implémentation Netflix de cette spécification
• Uber Riders API Reference — le contre-exemple assumé, en limit / offset
• No-Offset — Markus Winand — la référence historique sur le keyset et les plans d’exécution associés
• Choisir sa clé primaire dans PostgreSQL — pourquoi un UUIDv4 vous coûte votre curseur de parcours complet
• Gérer ses transactions en base de données — ce que coûte une transaction longue, et pourquoi on ne pagine pas dedans