postgres postgresql pagination offset limit keyset
Paginação é a estratégia de apresentar apenas uma parte dos resultados ao usuário, alimentando com mais dados à medida que ele requisita, por exemplo para um scroll infinito. Quando feito corretamente, isso melhora a experiência de usuário, diminui tempo de carga de dados e reduz o trabalho computacional no front end, backend e banco de dados. Contudo, quando feita incorretamente, causa maior consumo de recursos computacionais, ou seja, desperdício de recursos, aumenta o tempo de espera do usuário por dados e impede a escalabilidade da aplicação.
A implementação mais ineficiente é por LIMIT/OFFSET. O LIMIT não é a causa do problema, mas sim o OFFSET. Quando uma consulta é executada, o banco de dados despende esforço e recursos para gerar linhas que podem ser retornadas à aplicação. O OFFSET N, então, descarta as primeiras N linhas e retorna as linhas seguintes à aplicação. Isso também significa que o esforço para gerar aquelas N linhas foi desperdiçado. Portanto, à medida que o usuário busca as páginas, elas se tornam cada vez mais custosas ao sistema (e normalmente menos relevantes ao usuário final).
É importante entender o custo de gerar uma página, mesmo em um modelo simplificado. Toda consulta tem um custo básico de início (\( C_0 \)), que é baixo em consultas que retornam dados diretos de tabelas (select * from tabela) e alto em consultas que precisam pré-processar grandes volumes antes da primeira linha ser retornada (agregações, ordenações e algumas junções). Ela também tem um custo por linha gerada (\( C_i \)), que pode ser baixo se elas já existirem (buscadas de uma tabela ou de um agrupamento finalizado) ou alto se elas precisarem serem criadas uma a uma (executando funções custosas ou subselects).
Se p é o número de linhas por página, o custo da primeira página é \( C_0 + C_i * p \). O custo da segunda página é \( C_0 + C_i * 2 * p \), o dobro da primeira. O custo da página n é \( C_0 + C_i * n * p \), n vezes o custo da primeira. Adicionalmente, se um usuário abriu a primeira página, pagamos \( C_0 + C_i * p \). Se ele abre a segunda, pagamos mais \( C_0 + C_i * 2 * p \) e assim por diante. Os custos de cada página são adicionados ao total. Após \( N \) páginas, pagamos \( C_0 * N + \frac{N * (N+1)}{2} * Ci * p \), que é um custo quadrático sobre o número de linhas retornadas.
Por exemplo, considerando parâmetros artificiais mas próximos da realidade (\( C_0 = 50 \), \( C_i = 1 \), \( p = 10 \)), se o usuário médio acessa as duas primeiras páginas, pagamos \( 50 + 1 * 10 \) pela primeira página e \( 50 + 1 * 20 \) pela segunda página. Isso produz as primeiras 20 linhas em duas páginas com o custo de 80 linhas em uma página, ou seja, com quatro vezes o custo normal. Essa proporção é pior à medida que o usuário comum acessa mais páginas em média.
Quando usando paginação por OFFSET, deve-se garantir que o usuário médio encontra o que busca na primeira página, mesmo que signifique usar páginas maiores ou fazer requisições para mais dados para não fazer outras requisições. No exemplo acima, o custo de uma requisição com menos de 80 linhas é menor que o custo de duas requisições para as primeiras 20. Se um usuário médio encontraria o que precisa na segunda página (de 10 itens cada), então é mais eficiente usar páginas de 20 (ou maior, até 79 itens); outra opção é manter as páginas visíveis ao usuário com 10 itens, mas fazer requisições de 20 a 79 itens ao backend, guardando os itens em memória e prontos para serem apresentados quando o usuário clicar na próxima página.
Esse desperdício de recursos afeta diretamente a escalabilidade da aplicação. Existem soluções muito mais eficientes que OFFSET para paginação, como keyset pagination, que trazem escalabilidade linear perfeita e devem ser usadas em aplicações escaláveis.
| Usuário | Páginas requisitadas | Custo total |
\( C_0 = 1 \) \( C_i = 1 \) |
\( C_0 = 50 \) \( C_i = 1 \) |
\( C_0 = 1 \) \( C_i = 5 \) |
|---|---|---|---|---|---|
| Satisfeito com a página 1 | P1 | \( = C_0 + C_i*p \) | \( = 1 + 1*p \) | \( = 50 + 1*p \) | \( = 1 + 5*p \) |
| Satisfeito com a página 2 | P1 + P2 |
\( = C_0 + C_i*p \) \( + C_0 + 2*C_i*p \) \( = 2*C_0 + 3*C_i \) |
\( = 1 + 1*p \) \( + 1 + 2*1*p \) \( = 2 + 3*p \) |
\( = 50 + 1*p \) \( + 50 + 2*1*p \) \( = 100 + 3*p \) |
\( = 1 + 5*p \) \( + 1 + 2*5*p \) \( = 2 + 15*p \) |
| Satisfeito com a página 3 | P1 + P2 + P3 |
\( = C_0 + C_i*p \) \( + C_0 + 2*C_i*p \) \( + C_0 + 3*C_i*p \) \( = 3*C_0 + 6*C_i \) |
\( = 1 + 1*p \) \( + 1 + 2*1*p \) \( + 1 + 3*1*p \) \( = 3 + 6*p \) |
\( = 50 + 1*p \) \( + 50 + 2*1*p \) \( + 50 + 3*1*p \) \( = 150 + 6*p \) |
\( = 1 + 5*p \) \( + 1 + 2*5*p \) \( + 1 + 3*5*p \) \( = 3 + 30*p \) |
| … | … | … | … | … | … |
| Satisfeito com a página n | P1 + P2 + P3 + … + Pn |
\( = C_0 + C_i*p \) \( + C_0 + 2*C_i*p \) \( + C_0 + 3*C_i+p \) … \( + C_0 + n*C_i*p \) \( = n*C_0 + \frac{n(n+1)}{2}*C_i*p \) |
\( = 1 + 1*p \) \( + 1 + 2*1*p \) \( + 1 + 3*1*p \) … \( + 1 + n*1*p \) \( = n + \frac{n(n+1)}{2}*1*p \) |
\( = 50 + 1*p \) \( + 50 + 2*1*p \) \( + 50 + 3*1*p \) … \( + 50 + n*1*p \) \( = n*50 + \frac{n(n+1)}{2}*1*p \) |
\( = 1 + 5*p \) \( + 1 + 2*5*p \) \( + 1 + 3*5*p \) … \( + 1 + n*5*p \) \( = n + \frac{n(n+1)}{2}*5*p \) |
TODO: Quebrar a tabela em duas e adicionar um gráfico interativo e parametrizado.
:-)
TODO: Descrever keyset pagination.