database - tutorial - the django project

¿Qué esquemas de paginación pueden manejar listas de contenido que cambian rápidamente?

Question

La paginación es difícil cuando las clasificaciones de contenido pueden cambiar rápidamente, y aún más cuando esas clasificaciones difieren por usuario. (Consideremos el desplazamiento infinito como un tipo de paginación donde los enlaces son invisibles). Hay dos problemas difíciles: contenido recién agregado en la parte superior y contenido reintegrado.

Olvidémonos del contenido recién agregado y aceptemos que tendrá que actualizar la página 1 para verlo. También pretendamos que estamos haciendo una ORDER BY position ; si ordena por otra cosa, es posible que deba usar funciones de ventana. Nuestras páginas tienen 4 filas de animales por página. Comienzan:

+----+----------+-----------+
| id | position^|  animal   |
+----+----------+-----------+
|  1 |        1 | Alpacas   |
|  2 |        2 | Bats      |
|  3 |        3 | Cows      |
|  4 |        4 | Dogs      |
|  5 |        5 | Elephants |
|  6 |        6 | Foxes     |
|  7 |        7 | Giraffes  |
|  8 |        8 | Horses    |
+----+----------+-----------+

Después de buscar la página 1, y antes de ir a la página 2, se mueven muchos elementos. El DB ahora es:

+----+----------+-----------+
| id | position^|  animal   |
+----+----------+-----------+
|  4 |        1 | Dogs      |
|  2 |        2 | Bats      |
|  1 |        3 | Alpacas   |
|  5 |        4 | Elephants |
|  6 |        5 | Foxes     |
|  7 |        6 | Giraffes  |
|  3 |        7 | Cows      |
|  8 |        8 | Horses    |
+----+----------+-----------+

Hay tres enfoques comunes:

Enfoque de desplazamiento / límite

Este es el enfoque ingenuo típico; en Rails, es cómo will_paginate y Kaminari funcionan. Si quiero buscar la página 2, lo haré

SELECT * FROM animals
ORDER BY animals.position
OFFSET ((:page_num - 1) * :page_size) 
LIMIT :page_size;

que obtiene las filas 5-8. Nunca veré elefantes, y veré vacas dos veces.

Último enfoque de identificación visto

Reddit toma un enfoque diferente. En lugar de calcular la primera fila según el tamaño de la página, el cliente rastrea la identificación del último elemento que ha visto, como un marcador. Cuando presiona "siguiente", comienzan a mirar desde ese marcador en adelante:

SELECT * FROM animals
WHERE position > (
  SELECT position FROM animals 
  WHERE id = :last_seen_id
) 
ORDER BY position
LIMIT :page_size;

En algunos casos, esto funciona mejor que la página / desplazamiento. Pero en nuestro caso, Dogs, la publicación vista por última vez, se amplió a la derecha hasta el n. ° 1. Entonces, el cliente envía ?last_seen_id=4 , y mi página 2 es Murciélagos, Alpacas, Elefantes y Zorros. No me he perdido ningún animal, pero vi dos veces Murciélagos y Alpacas.

Estado del lado del servidor

HackerNews (y nuestro sitio, ahora mismo) resuelve esto con continuaciones del lado del servidor; almacenan el conjunto de resultados completo para usted (¿o al menos varias páginas de antemano?) y el enlace "Más" hace referencia a esa continuación. Cuando busco la página 2, pido la "página 2 de mi consulta original". Utiliza el mismo cálculo de compensación / límite, pero como va en contra de la consulta original, simplemente no me importa que las cosas se hayan movido ahora. Veo Elefantes, Zorros, Jirafas y Caballos. Sin dups, sin artículos perdidos.

La desventaja es que tenemos que almacenar mucho estado en el servidor. En HN, eso está almacenado en la RAM, y en realidad esas continuaciones a menudo caducan antes de que puedas presionar el botón "Más", forzándote a volver a la página 1 para encontrar un enlace válido. En la mayoría de las aplicaciones, puede almacenar eso en memcached, o incluso en la base de datos en sí (usando su propia tabla, o en Oracle o PostgreSQL, usando cursores que se pueden usar). Dependiendo de su aplicación, puede haber un golpe de rendimiento; en PostgreSQL, al menos, debe encontrar la forma de volver a conectar correctamente la conexión de base de datos correcta, lo que requiere una gran cantidad de enrutamiento de estado sólido o de algún back-end inteligente.

¿Son estos los únicos tres enfoques posibles? Si no, ¿hay conceptos de ciencias de la computación que me darían Google juice para leer sobre esto? ¿Hay formas de aproximar el enfoque de continuación sin almacenar todo el conjunto de resultados? A largo plazo, hay sistemas complejos de transmisión de eventos / punto en el tiempo, donde "el resultado establecido a partir del momento en que tomé la página 1" es siempre derivable. Corto de eso ...?

Answer 1

Oracle maneja esto muy bien. Siempre que el cursor esté abierto, puede buscar tantas veces como sea necesario y sus resultados siempre reflejarán el momento en que se abrió el cursor. Utiliza datos de los registros de deshacer para deshacer prácticamente los cambios que se cometieron después de que se abrió el cursor.

Funcionará siempre que los datos de reversión necesarios aún estén disponibles. Finalmente, los registros se reciclan y los datos de reversión ya no están disponibles, por lo que existe un límite, dependiendo del espacio de registro, la actividad del sistema, etc.

Desafortunadamente (IMO), no conozco ningún otro DB que funcione así. Las otras bases de datos con las que he trabajado utilizan bloqueos para garantizar la coherencia de lectura, lo cual es problemático si se desea una coherencia de lectura de más de muy corta duración.

Answer 2

Vamos con el enfoque de estado del lado del servidor por ahora, almacenando en caché todo el resultado en la primera consulta, por lo que siempre devolvemos una lista coherente. Esto funcionará siempre que nuestra consulta ya devuelva todas las filas; eventualmente necesitaremos usar un enfoque de vecino más cercano y eso no funcionará.

Pero creo que hay una cuarta posibilidad, que se escala muy bien, siempre y cuando:

1. No necesita una garantía de no duplicados, solo una alta probabilidad
2. Estás de acuerdo con perder algo de contenido durante los rollos, siempre y cuando evites los duplicados

La solución es una variante de la solución de "última identificación": haga que el cliente no conserve uno, sino 5 o 10 o 20 marcadores, lo suficiente como para poder almacenarlos de manera eficiente. La consulta termina pareciéndose a:

SELECT * FROM posts
WHERE id > :bookmark_1
AND id > :bookmark_2
...
ORDER BY id

A medida que el número de marcadores crece, las probabilidades de que (a) comiences en algún momento después de todos los n marcadores, pero (b) que vean el contenido duplicado de todas maneras, se reducen rápidamente, ya que todos fueron reinterpretados.

Si hay agujeros, o mejores respuestas en el futuro, felizmente no aceptaré esta respuesta.

Answer 3

Solución 1: " la solución hacky "

Una solución podría consistir en que su cliente realice un seguimiento del contenido ya visto, una lista de ID, por ejemplo. Cada vez que necesita otra página, agrega esta lista de ID a los parámetros de su llamada al servidor. Su servidor puede ordenar el contenido, eliminar el contenido ya visto y aplicar el desplazamiento para obtener la página correcta.

Aunque no lo recomendaría e insisto en hacky . Simplemente lo escribo aquí porque es rápido y podría ajustarse a algunas necesidades. aquí están las cosas malas que puedo pensar:

1) Necesita algo de trabajo en el lado del cliente para hacerlo bien (lo que significa "ya visto" en mi frase anterior, ¿qué pasa si voy a una página anterior?)

2) El orden resultante no refleja su verdadera política de pedidos. Se podría mostrar un contenido en la página 2, aunque la política debería haberlo puesto en la página 1. Podría llevar a un malentendido del usuario. Tomemos el ejemplo del desbordamiento de pila con su anterior política de pedidos, que significa la mayoría de las respuestas subidas primero. Podríamos tener una pregunta con 6 votaciones ascendentes en la página 2, mientras que una pregunta con 4 votos ascendentes estaría en la página 1. Esto sucede cuando las 2 o más votaciones ascendentes ocurrieron mientras el usuario todavía estaba en la página 1. -> puede ser sorprendente para el usuario .

Solución 2 : " la solución del cliente"

Básicamente es la solución equivalente del lado del cliente a la que usted llama "estado del lado del servidor". Entonces es útil solo si no es lo suficientemente conveniente hacer un seguimiento de la orden completa en el lado del servidor. Funciona si la lista de elementos no es infinita.

• Llame a su servidor para obtener la lista completa (finita) de pedidos + la cantidad de elementos / página
• Guárdelo en el lado del cliente
• Recupere elementos directamente a través de los identificadores de su contenido.

Answer 4

Muy tarde para la fiesta, pero aquí hay algo con lo que experimentamos. Estamos utilizando carga continua, no páginas que el usuario podría ir y venir entre ellas.

El cliente crea una lista de todos los ID que ha mostrado, por lo que después del primer conjunto podría ser: 4,7,19,2,1,72,3

Cuando cargamos más contenido hacemos la misma consulta con el mismo tipo pero le agregamos esto: DONDE no está IN (4,7,19,2,1,72,3)

La lista NOT IN puede crecer bastante rápido. Para nosotros esto no es un problema ya que nuestra herramienta interna generalmente no tiene muchos resultados.

Quiero agregar otra idea. Tal vez una adición al lado del servidor podría aplicarse a esto. Cuando el usuario busca, agregue todos los ID que obtuvo a una tabla con un enlace a su búsqueda. Cuando el cliente quiere más, solo tiene que proporcionar el ID de búsqueda (o usar el estado del lado del servidor) y la consulta puede unirse a sus datos de búsqueda.