Paginación de Base de Datos: Uso de OFFSET y Keyset en N1QL

Lea los antecedentes de la paginación en mi artículo anterior: https://www.couchbase.com/blog/optimizing-database-pagination-using-couchbase-n1ql/

La paginación es la tarea de dividir el resultado potencial en páginas y recuperar las páginas requeridas, una a una bajo demanda. El uso de OFFSET y LIMIT es la forma más sencilla de escribir la paginación en las consultas a bases de datos. Juntos, OFFSET y LIMIT, forman la cláusula de paginación de la sentencia SELECT. La paginación es un trabajo de aplicación común y su implementación tiene un gran impacto en la experiencia del cliente. Veamos los problemas y soluciones con Couchbase N1QL en detalle.

Markus Winand de http://use-the-index-luke.com/ argumenta que puede no ser lo más eficiente. También sugiere, cuando sea posible, utilizar la paginación por conjuntos de teclas en lugar de la paginación OFFSET. Para este artículo, voy a utilizar las consultas de ejemplo modelado en su artículo, http://use-the-index-luke.com/no-offset para mostrar qué optimizaciones OFFSET hemos hecho, cuándo y cómo explotar la paginación de conjuntos de teclas en N1QL.

Dado que Couchbase incluye un conjunto de datos de muestra de viajes, lo utilizaremos para escribir nuestras consultas de paginación.

1. OBTENER LA PRIMERA PÁGINA

Para esta consulta, utilizando el índice ixtopic, el motor de consulta se ejecuta de forma sencilla. El motor de consultas obtiene todas las claves cualificadas del índice, a continuación obtiene todos los documentos, ordena en función de la cláusula ORDER BY y, por último, elimina el número de documentos OFFSET (en este caso cero) y proyecta el número de documentos LIMIT (en este caso 10).

Aquí está el plan que muestra el índice y los vanos.

N1QL elige el índice ixtype e introduce el filtro (type = "hotel") en la exploración del índice. Para aplicar la cláusula ORDER BY, recupera todos los documentos. En la fase de ordenación, reconocemos la cláusula LIMIT 10 y hacemos que la ordenación sea eficiente manteniendo sólo los 10 primeros elementos.

Veamos la eficiencia del operador de escaneo de índices con este índice:

El indizador ha devuelto 917 claves de documento. El motor de consulta obtuvo 917 documentos. A continuación, el operador de clasificación (orden) los ordenó y devolvió los 10 elementos.

2. OBTENER LA SEGUNDA PÁGINA

En este caso, todo es igual que en la consulta1 excepto:

1. El operador de ordenación (ORDER BY) devolverá 20 documentos (offset + limit).
2. El nuevo operador OFFSET se ejecutará después del operador Order y eliminará las 10 primeras filas.

A medida que el OFFSET aumenta, el número de documentos escaneados por la clasificación también aumentará, consumiendo más memoria y CPU.

3. Mejoremos el rendimiento cubriendo las claves de predicado y ordenación con un único índice.

Utiliza el índice adecuado y crea los filtros adecuados (spans) para la exploración del índice.Explain incluye lo siguiente.

Veamos la eficiencia del operador de escaneo de índices con este índice:

Sólo se devuelven las 10 claves de documento necesarias a partir de la exploración del índice. El optimizador N1QL evalúa tanto la cláusula WHERE como la cláusula de paginación (OFFSET, LIMIT). El optimizador de consultas decide enviar la cláusula de paginación al indexador basándose en la cláusula order by de la consulta y en el orden de las claves del índice.  

En este caso, el predicado de la consulta es: type = 'hotel'

La cláusula Order by es: ORDER BY país, ciudad

El orden de las claves del índice es: (tipo, país, ciudad)

Por simple comparación, el orden por cláusula no es exactamente el mismo que el orden por clave del índice. Sin embargo, la clave principal del índice (tipo) tiene un predicado de igualdad (tipo = 'hotel'). Por lo tanto, el optimizador sabe que las claves proyectadas del documento estarán en el orden de (país y ciudad).

**y la cláusula ORDER BY para ver si puede empujar hacia abajo los parámetros de paginación a la exploración del índice. En este caso, hay una coincidencia perfecta.

El optimizador pasa tanto OFFSET como LIMIT en la paginación al escaneo de índice y el escaneo de índice devuelve sólo las 10 claves de documento requeridas sin importar el OFFSET. Por lo tanto, fetch sólo necesita obtener los 10 documentos. El indexador tiene que pasar por el escaneo del índice para evaluar las claves.

Esta consulta se ejecutó en unos 6,81 milisegundos en mi entorno. Vamos a paginar las páginas siguientes para ver el rendimiento:

Si desea paginar en orden descendente, cambie la consulta y el índice por los siguientes. La intercalación de la clave en el índice debe coincidir con la intercalación de la consulta. En este caso, tanto el país como la ciudad están en orden descendente.

Veamos ahora una consulta que no está cubierta por el índice. En la consulta que vimos antes, decidimos recuperar el nombre del hotel junto con el país y la ciudad. El nombre no está en el índice.

En este caso, de nuevo, el índice tiene los datos para cubrir la cláusula WHERE y la cláusula ORDER BY. El escaneo del índice aplicará el predicado. El orden del índice coincide con el orden de la consulta (nota: sólo hay un predicado de igualdad en la clave principal. Por lo tanto, el país y la ciudad se ordenan automáticamente). El índice omite el número OFFSET de claves cualificadas y devuelve el número de claves especificado por la cláusula LIMIT. El motor recupera los documentos para mantener el orden especificado por la cláusula ORDER BY.

Todas estas pequeñas optimizaciones juntas aseguran que el rendimiento de la consulta sea consistente tanto si OFFSET es 10, 100 o 1000. La única sobrecarga entre OFFSET más altos es la exploración del índice omitiendo los elementos adicionales. La evaluación de la clave del índice y la omisión es significativamente más rápida que obtener todos los documentos y ordenarlos.

Consideremos una consulta de larga duración con un potencial de devolución de hasta 24.000 documentos.

create index idxtypeaiaid ON `viajes-muestra`(tipo, aerolinea, airlineid)

Incluso cuando los predicados de consulta de paginación y el orden por están completamente cubiertos por el índice, hay un número limitado de casos en los que el LIMIT y OFFSET de paginación pueden ser empujados al escaneo del índice para hacerlo muy eficiente.

Estas son las reglas generales y los requisitos para enviar OFFSET y LIMIT al indexador. Tenga en cuenta que estas reglas no son exhaustivas ni completas, pero le dan una idea de cuándo se realiza esta optimización.

1. El escaneo de la consulta debe realizarse en un único espacio clave (referencia única en la cláusula FROM sin JOINs.
   1. DESDE viaje-muestra t
   2. DESDE viaje-muestra hotel INNER JOIN viaje-muestra hitos ON KEYS hotel.lmid

El caso (a) cumple los requisitos, y el (b) no.

1. Todos los predicados de la consulta son empujados hacia abajo en el escaneo del índice (spans).
   1. No podemos empujar los predicados (col LIKE "%xyz") al escaneo del índice. Por lo tanto, la paginación no se puede empujar hacia abajo también.
2. Todos los predicados deben estar representados por un único span. Si tenemos que hacer varios escaneos de índice, después del procesamiento del escaneo de índice (por ejemplo, escaneo de unión, escaneo distinto en el explain), no podemos hacer que el indexador evalúe la paginación. La consulta se ejecutará sin enviar la cláusula de paginación al escaneo del índice. A continuación se muestran ejemplos de predicados que generan un único intervalo.
   1. Por ejemplo (a entre 4 y 8 y a 12)
   2. (a = 5 O a = 6)
   3. (a IN [4, 6, 9])
3. Todos los predicados deben ser exactos.
   1. Predicados exactos: (a = 5), (a entre 9,8 y 9,99)
   2. Predicados inexactos: (a > 5 y a > $param)
4. La consulta no puede contener cláusulas de agregación, agrupación, tener. No deben eliminar ningún documento después del escaneo del índice (no hay filtrado/reducción posterior al escaneo del índice).
5. Las claves ORDER BY y el orden de las claves deben coincidir con la clave del índice y el orden de la clave del índice.
   1. CREAR ÍNDICE i1 EN 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;

El caso (2) coincide perfectamente con el pedido.

El caso (3) no coincide perfectamente, pero la clave principal tiene un filtro de igualdad. Por lo tanto, sabemos que los resultados de la exploración estarán en el orden de (b, c). Por lo tanto, la paginación pushdown al índice es posible.

Para el caso (4), la clave principal tiene un predicado de rango (a > 3) y, por lo tanto, no es posible el pushdown de paginación.

En el caso (5), la cláusula ORDER BY coincide perfectamente con las claves del índice. Por lo tanto, podemos enviar la paginación al indexador, incluso si hay un predicado de rango en la clave principal.

Para el caso (f), podemos explotar el orden del índice, pero no podemos presionar OFFSET y LIMIT porque el predicado completo no puede ser evaluado por el escaneo del índice. Dado que obtenemos los resultados en el orden requerido, una vez proyectados el número de documentos OFFSET y LIMIT, finalizamos la exploración del índice.

Para simplificar, he utilizado una sola clave principal. Las afirmaciones son generalizadas y aplicables a múltiples claves principales.

Obviamente, la lógica de este optimizador es compleja. Véase información adicional en el apéndice sobre los requisitos.

OFFSET por encima:

La muestra de viajes inicial tiene unos 900 documentos con (tipo = "hotel"). Para experimentar, simplemente aumento la cantidad de datos volviendo a insertar los mismos datos varias veces utilizando la siguiente consulta:

Ahora, probemos esta consulta:

A medida que aumenta el OFFSET, aumenta el tiempo que tarda el indizador en recorrer los elementos del índice. Esto afecta tanto a la latencia como al rendimiento.  

¿Podemos mejorar esto? La paginación por teclas viene al rescate. Todas las reglas que hemos mencionado para la optimización de la paginación se aplican también en este caso. Además, uno de los predicados tiene que ser UNIQUE para que podamos navegar claramente de una página a otra sin que aparezcan documentos duplicados en varias páginas. Con Couchbase, estamos de suerte. Cada documento de un bucket tiene una clave de documento única. Es referenciada por META().id en la consulta N1QL.

La idea básica es que los clientes suelen querer la página SIGUIENTE en lugar de una página aleatoria del principio del conjunto de resultados. Por lo tanto, cuando obtenga cada página en orden, recuerde el último conjunto (MÁS ALTO/MÁS BAJO dependiendo de la cláusula ORDER BY). A continuación, utilice esa información para establecer los predicados y posicionar el índice para la siguiente búsqueda. Esto evitará el desperdicio de procesamiento de claves durante OFFSET.

Veamos un ejemplo:

CREAR ÍNDICE ixtypectcy EN viaje-muestra (tipo, país, ciudad, META().id);

1. GET La PRIMERA PÁGINA. Fíjate que he añadido META().id a la cláusula index, projection y ORDER BY para que garantice el valor UNIQUE en cada una de ellas.

Resultados:

Esta consulta se ejecutó en 5,14 milisegundos.

2. Ahora, construya la consulta para la página siguiente SIN utilizar OFFSET:

¿Cómo hemos construido esta consulta?

1. Reutilice todos los predicados de la cláusula WHERE. (tipo = "hotel").
2. Ahora, tome las claves del ORDER BY y construya los predicados adicionales. Así, simplemente tome el valor más alto devuelto por la última consulta y añada los nuevos predicados. No añada la clave del documento todavía. En este caso, estamos ordenando en orden ascendente. Por lo tanto, utilice el operador Mayor que O Igual a.

En este caso, es: (país >= "Francia" Y ciudad >= "Aviñón").

Ahora, para asegurar un valor único, añadimos el predicado META().id.

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

Esto se ejecuta en 5 milisegundos con el siguiente plan. A medida que avance por las páginas siguientes, simplemente repita los pasos para construir la siguiente consulta y evitar el OFFSET. ¡Puede continuar hasta el infinito con un tiempo de respuesta similar!

RESUMEN:

Acabas de aprender cómo funciona la paginación. También aprendiste cómo el optimizador N1QL de Couchbase explota el índice para mejorar la eficiencia del rendimiento de la paginación de consultas. Puedes usar las técnicas de paginación keyset para mejorar aún más el rendimiento de OFFSET usando la técnica escrita.

Referencias:

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: Optimizar la consulta con orden, desplazamiento y límite para aprovechar el orden de los índices

La evaluación de la consulta ORDER BY puede explotar el orden del índice con el indexador devolviendo los resultados en el orden requerido y la consulta no tiene que modificar el orden (por ejemplo, hace agrupaciones, uniones). Cuando cambia el orden de los registros, es necesario utilizar datos de ordenación para satisfacer la cláusula ORDER BY.

• No se utilizará el orden de índice cuando la cláusula from contenga agregados.
• El orden del índice no se utilizará cuando esté presente la cláusula GROUP BY.
• El orden del índice no se utilizará cuando se utilicen JOINs, NEST o UNNEST.
• El orden del índice no se utilizará cuando DISTINCT esté presente.
• No se utilizará el orden de índice cuando se utilicen operadores SET. Esto incluye UNION, UNION ALL, INTERSECT, EXCEPT, EXCEPTALL.
• El orden de los índices no se utilizará cuando se trate de una exploración primaria.
• No se utilizará el orden de índice cuando se trate de una exploración de intersección o unión.
• El orden de los índices no se utilizará cuando se trate de índices de matrices.
• El orden del índice no se utilizará cuando la intercalación del orden (ASC, DESC) no coincida con la intercalación del índice.
• El orden de índice no se utilizará cuando algún término de orden no coincida con claves de índice.
• Si la consulta explota el orden del índice, el operador Orden no estará presente en el EXPLAIN de la consulta.

OFFSET y LIMIT pueden ser empujados a IndexScan

• cuando el ORDER BY está presente y es capaz de explotar el orden del índice
• Cuando la consulta ORDER BY no está presente
• Todos los predicados se envían al indizador como parte de los intervalos.
• Los valores de los tramos empujados son exactos
• Basado en intervalos El Indexador no genera falsos positivos
• La consulta no reduce aún más los resultados de la exploración de índices.
• Si el OFFSET es empujado al indexador "offset" aparecerá en la sección IndexScan del EXPLAIN y el Operador Offset no estará presente al final del EXPLAIN.
• Si el límite es empujado al indexador "limit" aparecerá en la sección IndexScan del EXPLAIN.