Estratégias de paginação em bancos de dados com cursor baseado em keyset

1. Fundamentos da paginação tradicional e seus limites

A paginação tradicional baseada em OFFSET e LIMIT é a abordagem mais conhecida por desenvolvedores iniciantes. Sua simplicidade esconde problemas graves em sistemas com grandes volumes de dados.

-- Paginação tradicional (problemática em larga escala)
SELECT * FROM pedidos
ORDER BY criado_em DESC
LIMIT 20 OFFSET 10000;

Problemas identificados:

  1. Degradação de performance: O banco de dados precisa ler e descartar registros até atingir o OFFSET desejado. Em uma tabela com 10 milhões de registros, OFFSET 500000 exige a leitura de meio milhão de linhas.

  2. Inconsistência de dados: Se novos registros são inseridos entre requisições de páginas consecutivas, o usuário pode ver o mesmo registro duas vezes ou pular registros. Em sistemas de feed de notícias ou logs de eventos, isso é inaceitável.

  3. Falta de escalabilidade horizontal: Em sistemas distribuídos, manter a consistência do OFFSET entre nós é praticamente impossível.

2. Conceito de keyset pagination (cursor-based pagination)

O cursor baseado em keyset utiliza valores reais das colunas como referência para navegação, em vez de posições numéricas abstratas.

Princípio fundamental: Em vez de "pule 100 registros e pegue os próximos 20", a abordagem diz "pegue os 20 registros após o último ID que você já viu".

-- Paginação baseada em cursor (keyset)
SELECT * FROM pedidos
WHERE id > 1500
ORDER BY id ASC
LIMIT 20;

Diferenças cruciais:
- Posição vs. Valor: OFFSET usa posição volátil; keyset usa valor estável
- Consistência: Keyset não é afetado por inserções ou remoções de registros anteriores
- Performance: Keyset sempre utiliza índices de forma eficiente, independentemente da profundidade

3. Implementação básica com chave única (PK)

A implementação mais simples utiliza a chave primária como cursor. Este é o padrão mais comum e eficiente.

-- Primeira requisição (sem cursor)
SELECT id, nome, email, criado_em
FROM usuarios
ORDER BY id ASC
LIMIT 50;

-- Requisições subsequentes (com cursor)
SELECT id, nome, email, criado_em
FROM usuarios
WHERE id > 250  -- último ID retornado
ORDER BY id ASC
LIMIT 50;

Tratamento do primeiro carregamento:

-- Função genérica para paginação com keyset
function fetchPage(cursor, pageSize = 50) {
    let query = 'SELECT * FROM usuarios';

    if (cursor) {
        query += ` WHERE id > ${cursor}`;
    }

    query += ' ORDER BY id ASC LIMIT ' + pageSize;
    return executeQuery(query);
}

4. Paginação com chaves compostas e ordenação customizada

Quando a ordenação envolve colunas não únicas, como datas ou nomes, é necessário usar chaves compostas para garantir a estabilidade.

-- Ordenação por data de criação (pode ter valores duplicados)
SELECT id, nome, criado_em
FROM usuarios
ORDER BY criado_em DESC, id DESC
LIMIT 20;

-- Paginação com chave composta
SELECT id, nome, criado_em
FROM usuarios
WHERE (criado_em, id) < ('2024-01-15 10:30:00', 1500)
ORDER BY criado_em DESC, id DESC
LIMIT 20;

Estratégia para colunas não únicas:

-- Quando ordenamos por nome (valores duplicados possíveis)
SELECT id, nome, email
FROM usuarios
WHERE (nome, id) > ('Silva', 3200)
ORDER BY nome ASC, id ASC
LIMIT 20;

5. Paginação reversa e navegação bidirecional

Para suportar navegação "anterior" e "próximo", precisamos inverter a lógica de ordenação.

-- Navegação para frente
SELECT id, nome, criado_em
FROM usuarios
WHERE (criado_em, id) > ('2024-01-10', 500)
ORDER BY criado_em ASC, id ASC
LIMIT 20;

-- Navegação para trás
SELECT id, nome, criado_em
FROM usuarios
WHERE (criado_em, id) < ('2024-01-10', 500)
ORDER BY criado_em DESC, id DESC
LIMIT 20;
-- (depois inverte-se a ordem dos resultados na aplicação)

Índices necessários para navegação bidirecional:

-- Índice composto que suporta ambas direções
CREATE INDEX idx_usuarios_data_id ON usuarios (criado_em DESC, id DESC);

6. Otimização com índices e performance

A chave do sucesso do keyset está nos índices. Um índice bem projetado elimina a necessidade de scans sequenciais.

-- Índice ideal para a query de paginação
CREATE INDEX idx_pedidos_data_id ON pedidos (data_pedido DESC, id DESC);

-- Verificação do plano de execução
EXPLAIN ANALYZE
SELECT * FROM pedidos
WHERE (data_pedido, id) < ('2024-06-01', 85000)
ORDER BY data_pedido DESC, id DESC
LIMIT 50;

Comparação de performance (10 milhões de registros):

-- OFFSET 500000 (lento)
-- Tempo: ~2.3 segundos, 500k linhas lidas

-- Keyset com cursor na posição equivalente (rápido)
-- Tempo: ~0.003 segundos, 50 linhas lidas

7. Desafios e casos especiais

Tratamento de valores nulos:

-- Valores nulos na coluna de ordenação
SELECT id, nome, data_ultimo_acesso
FROM usuarios
WHERE (data_ultimo_acesso IS NOT NULL AND 
       (data_ultimo_acesso, id) > ('2024-03-01', 200))
   OR (data_ultimo_acesso IS NULL AND id > 500)
ORDER BY data_ultimo_acesso NULLS LAST, id ASC
LIMIT 20;

Empates na ordenação:

-- Se houver empates em created_at, use id como desempate
WHERE (created_at, id) > ($last_date, $last_id)
ORDER BY created_at ASC, id ASC

Migração de OFFSET para keyset:

-- Estratégia híbrida durante migração
-- 1. Adicione índices compostos
-- 2. Modifique queries para usar WHERE com cursor
-- 3. Mantenha OFFSET como fallback para clientes antigos
-- 4. Remova OFFSET gradualmente

8. Boas práticas e implementação em APIs REST/GraphQL

Formato de resposta padronizado:

// Resposta da API REST
{
  "data": [
    { "id": 501, "nome": "João", "email": "joao@email.com" },
    { "id": 502, "nome": "Maria", "email": "maria@email.com" }
  ],
  "next_cursor": "NTAx",
  "has_more": true
}

Codificação segura do cursor:

// Codificação base64 para evitar parsing incorreto
function encodeCursor(value) {
    return Buffer.from(String(value)).toString('base64');
}

function decodeCursor(cursor) {
    return Buffer.from(cursor, 'base64').toString('utf-8');
}

Validação de cursor expirado:

// Tratamento de cursor inválido ou expirado
function handlePageRequest(cursor) {
    if (!cursor) {
        return fetchFirstPage();
    }

    const decodedCursor = decodeCursor(cursor);

    // Verificar se o cursor ainda existe no banco
    const exists = checkCursorExists(decodedCursor);

    if (!exists) {
        return {
            error: true,
            message: "Cursor expirado. Faça uma nova consulta.",
            reset_cursor: true
        };
    }

    return fetchPage(decodedCursor);
}

Limitação de tamanho de página:

// Garantir que o tamanho da página não seja abusivo
const MAX_PAGE_SIZE = 100;
const DEFAULT_PAGE_SIZE = 20;

function getPageSize(requestedSize) {
    if (!requestedSize || requestedSize < 1) {
        return DEFAULT_PAGE_SIZE;
    }
    return Math.min(requestedSize, MAX_PAGE_SIZE);
}

Referências