Paginação de banco de dados: Usando OFFSET e Keyset no N1QL

Leia o histórico da paginação em meu artigo anterior: https://www.couchbase.com/blog/optimizing-database-pagination-using-couchbase-n1ql/

A paginação é a tarefa de dividir o resultado potencial em páginas e recuperar as páginas necessárias, uma a uma, sob demanda. Usar OFFSET e LIMIT é a maneira mais fácil de escrever a paginação em consultas de banco de dados. Juntos, OFFSET e LIMIT formam a cláusula de paginação da instrução SELECT. A paginação é um trabalho comum em aplicativos e sua implementação tem um grande impacto na experiência do cliente. Vamos examinar detalhadamente os problemas e as soluções com o Couchbase N1QL.

Markus Winand de http://use-the-index-luke.com/ argumenta que isso pode não ser o mais eficiente. Ele também sugere, quando possível, usar a abordagem de paginação por conjunto de chaves em vez da paginação OFFSET. Para este artigo, usarei as consultas de exemplo modeladas em seu artigo, http://use-the-index-luke.com/no-offset para mostrar as otimizações OFFSET que fizemos, quando e como explorar a paginação do conjunto de chaves no N1QL.

Como o Couchbase vem com um conjunto de dados de amostra de viagens, vamos usá-lo para escrever nossas consultas de paginação.

1. OBTER A PRIMEIRA PÁGINA

Para essa consulta, usando o índice ixtopic, o mecanismo de consulta é executado de forma simples. O mecanismo de consulta obtém todas as chaves qualificadas do índice, depois obtém todos os documentos, classifica com base na cláusula ORDER BY e, em seguida, elimina o número de documentos OFFSET (nesse caso, zero) e projeta o número de documentos LIMIT (nesse caso, 10).

Aqui está o plano que mostra o índice e os vãos.

O N1QL escolhe o ixtype do índice e coloca o filtro (type = "hotel") na varredura do índice. Para implementar a cláusula ORDER BY, ele busca todos os documentos. Na fase de classificação, reconhecemos a cláusula LIMIT 10 e tornamos a classificação eficiente, mantendo apenas os 10 principais itens.

Vamos dar uma olhada na eficiência do operador de varredura de índice com esse índice:

Houve 917 chaves de documentos retornadas pelo indexador. O mecanismo de consulta buscou 917 documentos. Em seguida, o operador de classificação (ordem) os classificou e retornou os 10 itens.

2. OBTER A SEGUNDA PÁGINA

Nesse caso, tudo é igual à consulta1, exceto:

1. O operador Sort (ORDER BY) retornará 20 documentos (deslocamento + limite).
2. O novo operador OFFSET será executado após o operador Order e eliminará as primeiras 10 linhas.

À medida que o OFFSET aumenta, o número de documentos digitalizados pela classificação também aumenta, consumindo mais memória e CPU.

3. Vamos melhorar o desempenho cobrindo o predicado e as chaves de classificação com um único índice.

Ele usa o índice correto e cria os filtros (intervalos) corretos para a varredura do índice.

Vamos dar uma olhada na eficiência do operador de varredura de índice com esse índice:

Somente as 10 chaves de documento necessárias são retornadas da varredura do índice! O otimizador N1QL avalia a cláusula WHERE e a cláusula de paginação (OFFSET, LIMIT). O otimizador de consultas decide enviar a cláusula de paginação para o indexador com base na cláusula order by da consulta e na ordem da chave do índice.  

Nesse caso, o predicado da consulta é: type = 'hotel'

A cláusula Order by é: ORDER BY country, city

A ordem da chave do índice é: (tipo, país, cidade)

Apenas por comparação simples, a ordem por cláusula não é exatamente igual à ordem da chave do índice. Entretanto, a chave principal do índice (type) tem um predicado de igualdade (type = 'hotel'). Portanto, o otimizador sabe que as chaves do documento projetado estarão na ordem ordenada de (país e cidade).

**e a cláusula ORDER BY para ver se ele pode enviar os parâmetros de paginação para a varredura do índice. Nesse caso, há uma correspondência perfeita.

O otimizador empurra o OFFSET e o LIMIT na paginação para a varredura de índice e a varredura de índice retorna apenas as 10 chaves de documento necessárias, independentemente do OFFSET! Portanto, a busca só precisa buscar os 10 documentos. O indexador precisa passar pela varredura de índice para avaliar as chaves.

Essa consulta foi executada em cerca de 6,81 milissegundos em meu ambiente. Vamos paginar para as páginas subsequentes para ver o desempenho:

Se você quiser paginar em ordem decrescente, altere a consulta e o índice para o seguinte. O agrupamento da chave no índice deve corresponder ao agrupamento na consulta. Nesse caso, tanto o país quanto a cidade estão em ordem DESCENDENTE.

Vejamos agora uma consulta que não é coberta pelo índice. Na consulta que vimos anteriormente, decidimos recuperar o nome do hotel junto com o país e a cidade. O nome não está no índice.

Nesse caso, novamente, o índice tem os dados para cobrir a cláusula WHERE e a cláusula ORDER BY. A varredura do índice aplicará o predicado. A ordem do índice corresponde à ordem da consulta (observação: há apenas um predicado de igualdade na chave principal. Portanto, país e cidade estão em ordem automaticamente). O índice ignora o número OFFSET de chaves qualificadas e retorna o número de chaves especificado pela cláusula LIMIT. O mecanismo recupera os documentos para manter a ordem especificada pela cláusula ORDER BY.

Todas essas pequenas otimizações juntas garantem que o desempenho da consulta seja consistente, independentemente de o OFFSET ser 10, 100 ou 1000. A única sobrecarga entre OFFSETs mais altos é a varredura do índice que ignora os itens adicionais. A avaliação e o pulo da chave do índice são significativamente mais rápidos do que a obtenção de todos os documentos e a classificação.

Vamos considerar uma consulta de longa duração com a possibilidade de retornar até 24 mil documentos.

create index idxtypeaiaid ON `travel-sample`(type, airline, airlineid)

Mesmo quando os predicados da consulta de paginação e o order by são completamente cobertos pelo índice, há um número limitado de casos em que o LIMIT e o OFFSET da paginação podem ser transferidos para a varredura do índice para que isso seja muito eficiente.

Aqui estão as regras e os requisitos gerais para enviar OFFSET e LIMIT para o indexador. Observe que essas regras não são exaustivas e completas, mas dão uma ideia de quando essa otimização é feita.

1. A varredura da consulta deve ser feita em um único espaço-chave (referência única na cláusula FROM sem JOINs).
   1. DE amostra de viagem t
   2. DE amostra de viagem hotel INNER JOIN amostra de viagem pontos de referência ON KEYS hotel.lmid

O caso (a) se qualifica, e (b) não.

1. Todos os predicados da consulta são transferidos para a varredura do índice (intervalos).
   1. Não é possível enviar os predicados (col LIKE "%xyz") para a varredura de índice. Portanto, a paginação também não pode ser empurrada para baixo.
2. Todos os predicados devem ser representados por um único intervalo. Se tivermos que fazer várias varreduras de índice, pós-processamento de varredura de índice (por exemplo, varredura de união, varredura distinta na explicação), não poderemos fazer com que o indexador avalie a paginação. A consulta será executada sem empurrar a cláusula de paginação para a varredura de índice. Aqui estão exemplos de predicados que geram um único intervalo.
   1. Por exemplo, (a entre 4 e 8 e a 12)
   2. (a = 5 OU a = 6)
   3. (a IN [4, 6, 9])
3. Todos os predicados precisam ser exatos.
   1. Predicados exatos: (a = 5), (a entre 9,8 e 9,99)
   2. Predicados inexatos: (a > 5 e a > $param)
4. A consulta não pode conter cláusulas de agregação, agrupamento e posse. Elas fazem a redução de documentos após a verificação do índice e não devem eliminar nenhum documento após a verificação do índice (nenhuma filtragem/redução pós-verificação do índice).
5. As chaves ORDER BY e a ordem das chaves devem corresponder à chave do índice e à ordem da chave do índice.
   1. CREATE INDEX i1 ON t(a, b, c);
   2. SELECT * FROM t WHERE a = 1 ORDER BY a, b, c;
   3. SELECT * FROM t WHERE a = 1 ORDER BY b, c;
   4. SELECT * FROM t WHERE a > 3 ORDER BY b, c
   5. SELECT * FROM t WHERE a > 3 ORDER BY a, b, c
   6. SELECT * FROM t WHERE (a LIKE "%xyz") ORDER BY a, b, c OFFSET 10 LIMIT 5;

O caso (2) é uma correspondência perfeita do pedido.

O caso (3) não corresponde perfeitamente, mas a chave principal tem um filtro de igualdade. Portanto, sabemos que os resultados da varredura estarão na ordem de (b, c). Portanto, o pushdown de paginação para o índice é possível.

Para o caso (4), a chave principal tem um predicado de intervalo (a > 3) e, portanto, o pushdown de paginação não é possível.

Para o caso (5), há uma correspondência perfeita da cláusula ORDER BY com as chaves do índice. Portanto, podemos transferir a paginação para o indexador, mesmo que haja um predicado de intervalo na chave principal.

Para o caso (f), podemos explorar a ordem do índice, mas não podemos reduzir o OFFSET e o LIMIT porque o predicado completo não pode ser avaliado pela varredura do índice. Como obtemos os resultados na ordem exigida, depois que o número de documentos OFFSET e LIMIT é projetado, encerramos a varredura do índice.

Para simplificar, usei uma chave principal. As declarações são generalizadas e aplicáveis a várias chaves principais.

Obviamente, essa lógica do otimizador é complexa! Veja informações adicionais no apêndice sobre os requisitos.

OFFSET sobrecarga:

A amostra inicial de viagens tem cerca de 900 documentos com (type = "hotel"). Para fins de experimentação, simplesmente aumentei a quantidade de dados inserindo os mesmos dados novamente algumas vezes usando a seguinte consulta:

Agora, vamos tentar essa consulta:

À medida que o OFFSET aumenta, a quantidade de tempo gasto pelo indexador para percorrer os itens do índice aumenta. Isso afeta a latência e a taxa de transferência.  

Podemos melhorar isso? A paginação de conjunto de chaves vem em socorro. Todas as regras que mencionamos para a otimização da paginação também se aplicam aqui. Além disso, um dos predicados precisa ser UNIQUE para que possamos navegar claramente de uma página para outra sem que documentos duplicados apareçam em várias páginas. Com o Couchbase, estamos com sorte. Cada documento em um bucket tem uma chave de documento exclusiva. Ela é referenciada por META().id na consulta N1QL.

O insight básico é que os clientes normalmente querem a PRÓXIMA página em vez de uma página aleatória do início do conjunto de resultados. Portanto, quando você buscar cada página em ordem, lembre-se do último conjunto (MAIS ALTO/ MENOS ALTO, dependendo da cláusula ORDER BY). Em seguida, use essas informações para definir os predicados e posicionar o índice para a próxima varredura. Isso evitará o desperdício de processamento de chaves durante o OFFSET.

Vamos dar uma olhada em um exemplo:

CREATE INDEX ixtypectcy ON amostra de viagem (tipo, país, cidade, META().id);

1. GET A PRIMEIRA PÁGINA. Observe que adicionei META().id ao índice, à projeção e à cláusula ORDER BY para garantir o valor UNIQUE em cada uma delas.

Resultados:

Essa consulta foi executada em 5,14 milissegundos.

2. Agora, construa a consulta para a próxima página SEM usar o OFFSET:

Como construímos essa consulta?

1. Reutilize todos os predicados na cláusula WHERE. (type = "hotel").
2. Agora, pegue as chaves no ORDER BY e construa os predicados adicionais. Portanto, basta pegar o valor mais alto retornado pela última consulta e adicionar os novos predicados. Não adicione a chave do documento ainda. Nesse caso, estamos classificando em ordem crescente. Portanto, use o operador Greatherthan-OR-Equal-To.

Nesse caso, é: (country >= "France" AND city >= "Avignon").

Agora, para garantir um valor exclusivo, adicionamos o predicado META().id.

(META().id > "038c8a13-e1e7-4848-80ec-8819ff923602")

Isso é executado em 5 milissegundos com o seguinte plano. Ao percorrer as páginas subsequentes, basta repetir as etapas para construir a próxima consulta e evitar o OFFSET. Você pode continuar a percorrer todo o caminho com um tempo de resposta semelhante!

RESUMO:

Você acabou de aprender como funciona a paginação. Você também aprendeu como o otimizador N1QL do Couchbase explora o índice para melhorar a eficiência do desempenho da paginação de consultas. Você pode usar as técnicas de paginação de conjunto de chaves para melhorar ainda mais o desempenho do OFFSET usando a técnica descrita.

Referências:

1. https://www.couchbase.com/blog/optimizing-database-pagination-using-couchbase-n1ql/
2. https://www.slideshare.net/MarkusWinand/p2d2-pagination-done-the-postgresql-way
3. http://use-the-index-luke.com/sql/partial-results/fetch-next-page
4. https://blog.jooq.org/2013/10/26/faster-sql-paging-with-jooq-using-the-seek-method/

Apêndice: Otimizar a consulta com ordem, deslocamento, limite para explorar a ordenação do índice

A avaliação da consulta ORDER BY pode explorar a ordem do índice com o indexador retornando os resultados na ordem necessária e a consulta não precisa modificar a ordem (por exemplo, agrupar, juntar). Sempre que a ordem do registro muda, precisamos usar dados de classificação para satisfazer a cláusula ORDER BY.

• A ordem do índice não será usada quando a cláusula from contiver agregados.
• A ordem do índice não será usada quando a cláusula GROUP BY estiver presente.
• A ordem do índice não será usada quando JOINs, NEST ou UNNEST forem usados.
• A ordem do índice não será usada quando DISTINCT estiver presente.
• A ordem do índice não será usada quando os operadores SET forem usados. Isso inclui UNION, UNION ALL, INTERSECT, EXCEPT, EXCEPTALL.
• A ordem do índice não será usada quando a varredura primária estiver envolvida.
• A ordem do índice não será usada quando a varredura de interseção ou união estiver envolvida.
• A ordem do índice não será usada quando houver índices de matriz envolvidos.
• A ordem do índice não será usada quando o agrupamento da ordem (ASC, DESC) não corresponder ao agrupamento do índice.
• A ordem de índice não será usada quando qualquer termo de ordem não corresponder às chaves de índice.
• Se a consulta explorar a ordem do índice, o operador de ordem não estará presente no EXPLAIN da consulta.

O OFFSET e o LIMIT podem ser enviados para o IndexScan

• quando o ORDER BY está presente e é capaz de explorar a ordem do índice
• Quando a consulta ORDER BY não está presente
• Todos os predicados são enviados ao indexador como parte dos intervalos
• Os valores dos intervalos empurrados são exatos
• Com base em intervalos, o Indexador não gera falsos positivos
• A consulta não reduz ainda mais os resultados da varredura de índice.
• Se o OFFSET for pressionado para o indexador, "offset" aparecerá na seção IndexScan do EXPLAIN e o Offset Operator não estará presente no final do EXPLAIN.
• Se o limite for enviado ao indexador, "limit" aparecerá na seção IndexScan do EXPLAIN.