Almacenar una lista reordenable en una base de datos

Estoy trabajando en un sistema de lista de deseos, donde los usuarios pueden agregar elementos a sus diversas listas de deseos, y planeo permitir que los usuarios vuelvan a ordenar los elementos más adelante. No estoy realmente seguro de cuál es la mejor manera de almacenar esto en una base de datos mientras permanezco rápido y no se convierte en un desastre (esta aplicación será utilizada por una base de usuarios bastante grande, por lo que no quiero que se caiga para limpiar cosas).

Inicialmente probé una positioncolumna, pero parece que sería bastante ineficiente tener que cambiar el valor de posición de cada otro elemento cuando los mueves.

He visto a personas que usan una autorreferencia para referirse al valor anterior (o siguiente), pero nuevamente, parece que tendría que actualizar una gran cantidad de otros elementos en la lista.

Otra solución que he visto es usar números decimales y simplemente pegar elementos en los espacios entre ellos, lo que parece ser la mejor solución hasta ahora, pero estoy seguro de que tiene que haber una mejor manera.

Yo diría que una lista típica contendría hasta unos 20 elementos, y probablemente la limitaré a 50. El reordenamiento sería arrastrar y soltar y probablemente se realice en lotes para evitar condiciones de carrera y demás. solicitudes ajax. Estoy usando postgres (en heroku) si es importante.

¿Alguien tiene alguna idea?

Saludos por cualquier ayuda!

Primero, no intentes hacer nada inteligente con los números decimales, porque te molestarán. REALy DOUBLE PRECISIONson inexactos y pueden no representar adecuadamente lo que pones en ellos. NUMERICes exacto, pero la secuencia correcta de movimientos te hará perder precisión y tu implementación se romperá gravemente.

Limitar los movimientos a altibajos simples hace que toda la operación sea muy fácil. Para obtener una lista de elementos numerados secuencialmente, puede mover un elemento hacia arriba disminuyendo su posición e incrementando el número de posición de cualquier resultado anterior. (En otras palabras, el tema 5se convertiría 4y lo que era tema 4se convierte 5, efectivamente un intercambio como Imbéciles describe en su respuesta.) Mover hacia abajo sería lo contrario. Indice su tabla por lo que identifique de forma única una lista y una posición, y puede hacerlo con dos UPDATEs dentro de una transacción que se ejecutará muy rápidamente. A menos que sus usuarios reorganicen sus listas a velocidades sobrehumanas, esto no causará mucha carga.

Los movimientos de arrastrar y soltar (p. Ej., Mover elementos 6para sentarse entre los elementos 9y 10) son un poco más complicados y tienen que hacerse de manera diferente dependiendo de si la nueva posición está por encima o por debajo de la anterior. En el ejemplo anterior, debe abrir un agujero incrementando todas las posiciones más que 9, actualizando 6la posición del elemento para que sea el nuevo 10y luego disminuyendo la posición de todo lo que sea mayor que 6llenar el lugar desocupado. Con la misma indexación que describí antes, esto será rápido. En realidad, puede hacer que esto vaya un poco más rápido de lo que describí minimizando el número de filas que toca la transacción, pero esa es una microoptimización que no necesita hasta que pueda demostrar que hay un cuello de botella.

De cualquier manera, tratar de superar la base de datos con una solución casera, demasiado inteligente a la mitad, generalmente no conduce al éxito. Las bases de datos que valen la pena han sido escritas cuidadosamente para hacer estas operaciones muy, muy rápidamente por personas que son muy, muy buenas en eso.

Misma respuesta desde aquí https://stackoverflow.com/a/49956113/10608

Solución: haga indexuna cadena (porque las cadenas, en esencia, tienen una "precisión arbitraria" infinita). O si usa un int, incremente indexen 100 en lugar de 1.

El problema de rendimiento es este: no hay valores "intermedios" entre dos elementos ordenados.

item      index
-----------------
gizmo     1
              <<------ Oh no! no room between 1 and 2.
                       This requires incrementing _every_ item after it
gadget    2
gear      3
toolkit   4
box       5

En cambio, haz esto (mejor solución a continuación):

item      index
-----------------
gizmo     100
              <<------ Sweet :). I can re-order 99 (!) items here
                       without having to change anything else
gadget    200
gear      300
toolkit   400
box       500

Aún mejor: así es como Jira resuelve este problema. Su "rango" (lo que llama índice) es un valor de cadena que permite un montón de espacio para respirar entre los elementos clasificados.

Aquí hay un ejemplo real de una base de datos jira con la que trabajo

   id    | jira_rank
---------+------------
 AP-2405 | 0|hzztxk:
 ES-213  | 0|hzztxs:
 AP-2660 | 0|hzztzc:
 AP-2688 | 0|hzztzk:
 AP-2643 | 0|hzztzs:
 AP-2208 | 0|hzztzw:
 AP-2700 | 0|hzztzy:
 AP-2702 | 0|hzztzz:
 AP-2411 | 0|hzztzz:i
 AP-2440 | 0|hzztzz:r

Note este ejemplo hzztzz:i. La ventaja de un rango de cadena es que te quedas sin espacio entre dos elementos, todavía no tienes que volver a clasificar nada más. Simplemente comienza a agregar más caracteres a la cadena para reducir el enfoque.

He visto a personas que usan una autorreferencia para referirse al valor anterior (o siguiente), pero nuevamente, parece que tendría que actualizar una gran cantidad de otros elementos en la lista.

¿Por qué? Supongamos que adopta un enfoque de tabla de lista vinculada con columnas (listID, itemID, nextItemID).

Insertar un nuevo elemento en una lista cuesta una inserción y una fila modificada.

Reposicionar un artículo cuesta tres modificaciones de fila (el artículo que se mueve, el artículo anterior y el artículo anterior a su nueva ubicación).

Eliminar un artículo cuesta una eliminación y una fila modificada.

Estos costos siguen siendo los mismos independientemente de si la lista tiene 10 artículos o 10,000 artículos. En los tres casos, hay una modificación menos si la fila de destino es el primer elemento de la lista. Si opera con más frecuencia en el último elemento de la lista, puede ser beneficioso almacenar prevItemID en lugar de siguiente.

"pero parece que eso sería bastante ineficiente"

¿ Mediste eso? ¿O es solo una suposición? No haga tales suposiciones sin ninguna prueba.

"20 a 50 artículos por lista"

Honestamente, eso no es "una gran cantidad de elementos", para mí eso suena muy pocos.

Le sugiero que se adhiera al enfoque de "columna de posición" (si esa es la implementación más simple para usted). Para tamaños de lista tan pequeños, no comience una optimización innecesaria antes de experimentar problemas de rendimiento reales

Esto es realmente una cuestión de escala y caso de uso.

¿Cuántos artículos esperas en una lista? Si son millones, creo que la ruta decimal es la obvia.

Si 6, entonces la numeración de enteros es la opción obvia. s También la pregunta es cómo se reorganizaron las listas. Si usa flechas hacia arriba y hacia abajo (moviéndose hacia arriba o hacia abajo una ranura a la vez), usaría enteros y luego cambiaría con el anterior (o siguiente) en movimiento.

Además, ¿con qué frecuencia se compromete? Si el usuario puede realizar 250 cambios, confirme de una vez, de lo que digo números enteros con una nueva numeración ...

tl; dr: Necesito más información.

Editar: "Listas de deseos" suena como muchas listas pequeñas (suposición, esto puede ser falso) .. Entonces digo Integer con renumeración. (Cada lista contiene su propia posición)

Si el objetivo es minimizar el número de operaciones de la base de datos por operación de reordenamiento:

Asumiendo que

• Todos los artículos de compra se pueden enumerar con enteros de 32 bits.
• Hay un límite de tamaño máximo para la lista de deseos de un usuario. (Vi que algunos sitios web populares usan 20-40 elementos como límite)

Almacene la lista de deseos ordenada del usuario como una secuencia empaquetada de enteros (matrices de enteros) en una columna. Cada vez que se reordena la lista de deseos, se actualiza toda la matriz (una sola fila; una sola columna), que se realizará con una única actualización de SQL.

https://www.postgresql.org/docs/current/static/arrays.html

Si el objetivo es diferente, quédese con el enfoque de "columna de posición".

Con respecto a la "velocidad", asegúrese de comparar el enfoque del procedimiento almacenado. Si bien la emisión de más de 20 actualizaciones separadas para una lista de deseos aleatoria puede ser lenta, puede haber una forma rápida de usar el procedimiento almacenado.

OK, recientemente me enfrenté a este complicado problema, y ​​todas las respuestas en esta publicación de preguntas y respuestas me dieron mucha inspiración. A mi modo de ver, cada solución tiene sus pros y sus contras.

• Si el positioncampo tiene que ser secuencial sin espacios, básicamente necesitará reordenar la lista completa. Esta es una operación O (N). La ventaja es que el lado del cliente no necesitaría ninguna lógica especial para obtener el pedido.

• Si queremos evitar la operación O (N) PERO TODAVÍA mantenemos una secuencia precisa, uno de los enfoques es usar "autorreferencia para referirnos al valor anterior (o siguiente)". Este es un escenario de lista enlazada de libros de texto. Por diseño, NO incurrirá en "una gran cantidad de otros elementos en la lista". Sin embargo, esto requiere que el lado del cliente (un servicio web o tal vez una aplicación móvil) implemente la lógica de recorrido de la lista vinculada para derivar el orden.

• Algunas variaciones no usan referencia, es decir, lista vinculada. Eligen representar todo el orden como un blob autocontenido, como un JSON-array-in-a-string [5,2,1,3,...]; dicho pedido se almacenará en un lugar separado. Este enfoque también tiene el efecto secundario de requerir que el código del lado del cliente mantenga ese blob de orden separado.

• En muchos casos, realmente no necesitamos almacenar el orden exacto, solo necesitamos mantener un rango relativo entre cada registro. Por lo tanto, podemos permitir brechas entre registros secuenciales. Las variaciones incluyen: (1) usar un número entero con espacios como 100, 200, 300 ... pero rápidamente se quedará sin espacios y luego necesitará el proceso de recuperación; (2) usar el decimal que viene con espacios naturales, pero deberá decidir si puede vivir con la limitación de precisión eventual; (3) usar el rango basado en cadenas como se describe en esta respuesta, pero tenga cuidado con las trampas de implementación difíciles .

• La verdadera respuesta puede ser "depende". Revise sus requisitos comerciales. Por ejemplo, si se trata de un sistema de lista de deseos, personalmente usaría un sistema organizado por unos pocos rangos como "must-have", "good-to-have", "maybe-later", y luego presentar elementos sin particular orden dentro de cada rango. Si se trata de un sistema de entrega, puede utilizar el tiempo de entrega como un rango aproximado que viene con una brecha natural (y prevención de conflictos naturales ya que no ocurriría ninguna entrega al mismo tiempo). Su experiencia puede ser diferente.

Use un número de coma flotante para la columna de posición.

Luego puede reordenar la lista cambiando solo la columna de posición en la fila "movida".

Básicamente, si su usuario quiere posicionar "rojo" después de "azul" pero antes de "amarillo"

Entonces solo necesitas calcular

red.position = ((yellow.position - blue.position) / 2) + blue.position

Después de algunos millones de reubicaciones, puede obtener números de coma flotante tan pequeños que no haya "entre", pero esto es casi tan probable como ver un unicornio.

Puede implementar esto usando un campo entero con un espacio inicial de, digamos, 1000. Entonces, su orientación inicial sería 1000-> azul, 2000-> Amarillo, 3000-> Rojo. Después de "mover" el rojo después del azul, tendría 1000-> azul, 1500-> rojo, 2000-> amarillo.

El problema es que con una brecha inicial aparentemente grande de 1000, tan solo 10 movimientos lo llevarán a una situación como 1000-> azul, 1001-puce, 1004-> biege ...... donde ya no podrá para insertar cualquier cosa después de "azul" sin volver a numerar la lista completa. Usando números de coma flotante siempre habrá un punto "intermedio" entre las dos posiciones.

Si bien el OP se refirió brevemente a la noción de usar una Lista Vinculada para almacenar el orden de clasificación, tiene muchas ventajas para los casos en que los artículos se reordenarán con frecuencia.

He visto a personas que usan una autorreferencia para referirse al valor anterior (o siguiente), pero nuevamente, parece que tendría que actualizar una gran cantidad de otros elementos en la lista.

La cosa es que no . Cuando se utiliza una lista enlazada, la inserción, la eliminación y el reordenamiento son O(1)operaciones, y la integridad referencial impuesta por la base de datos garantiza que no haya referencias rotas, registros huérfanos o bucles.

Aquí hay un ejemplo:

CREATE TABLE Wishlists (
  WishlistId int           NOT NULL IDENTITY(1,1) PRIMARY KEY,
  [Name]     nvarchar(200) NOT NULL
);

CREATE TABLE WishlistItems (
  ItemId     int           NOT NULL IDENTITY(1,1),
  WishlistId int           NOT NULL,
  Text       nvarchar(200) NOT NULL,
  SortAfter  int               NULL,

  CONSTRAINT PK_WishlistItem PRIMARY KEY ( ItemId, WishlistId ),
  CONSTRAINT FK_Wishlist_WishlistItem FOREIGN KEY ( WishlistId ) REFERENCES Wishlists ( WishlistId ),
  CONSTRAINT FK_Sorting FOREIGN KEY ( SortAfter, WishlistId ) REFERENCES WishlistItems ( ItemId, WishlistId )
);

CREATE UNIQUE INDEX UX_Sorting ON WishlistItems ( SortAfter, WishlistId );

 -----

SET IDENTITY_INSERT Wishlists ON;

INSERT INTO Wishlists ( WishlistId, [Name] ) VALUES
  ( 1, 'Wishlist 1' ),
  ( 2, 'Wishlist 2' );

SET IDENTITY_INSERT Wishlists OFF;

SET IDENTITY_INSERT WishlistItems ON;

INSERT INTO WishlistItems ( ItemId, WishlistId, [Text], SortAfter ) VALUES
( 1, 1, 'One', NULL ),
( 2, 1, 'Two', 1 ),
( 3, 1, 'Three', 2 ),
( 4, 1, 'Four', 3 ),
( 5, 1, 'Five', 4 ),
( 6, 1, 'Six', 5 ),
( 7, 1, 'Seven', 6 ),
( 8, 1, 'Eight', 7 );

SET IDENTITY_INSERT WishlistItems OFF;

Tenga en cuenta lo siguiente:

• Usar una clave principal compuesta y una clave externa FK_Sortingpara evitar que los elementos se refieran accidentalmente al elemento primario incorrecto
• El UNIQUE INDEX UX_Sortingrealiza dos roles:
  • Como permite un solo NULLvalor, cada lista puede tener solo 1 elemento "principal".
  • Impide que dos o más elementos afirmen estar en el mismo lugar de clasificación (al evitar SortAftervalores duplicados ).

Las principales ventajas de este enfoque:

• Nunca requiere reequilibrio o mantenimiento, como ocurre con las órdenes de clasificación basadas en into realque eventualmente se quedan sin espacio entre los artículos después de un pedido frecuente.
• Solo los artículos que se reordenan (y sus hermanos) deben actualizarse.

Sin embargo, este enfoque tiene desventajas:

• Solo puede ordenar esta lista en SQL utilizando un CTE recursivo porque no puede hacer una tarea sencilla ORDER BY.
  • Como solución alternativa, puede crear un contenedor VIEWo TVF que use un CTE para agregar un derivado que contenga un orden de clasificación incremental, pero sería costoso usarlo en operaciones grandes.
• Debe cargar la lista completa en su programa para poder visualizarla; no puede operar en un subconjunto de filas porque la SortAftercolumna se referirá a elementos que no están cargados en su programa.
  • Sin embargo, cargar todos los elementos para una lista es fácil debido a la clave primaria compuesta (es decir, simplemente hacer SELECT * FROM WishlistItems WHERE WishlistId = @wishlistToLoad).
• La realización de cualquier operación mientras UX_Sortingestá habilitada requiere soporte DBMS para restricciones diferidas.
  • es decir, la implementación ideal de este enfoque no funcionará en SQL Server hasta que agreguen soporte para restricciones e índices diferibles.
  • Una solución alternativa es hacer que el índice único sea un índice filtrado que permita múltiples NULLvalores en la columna, lo que desafortunadamente significa que una lista podría tener múltiples elementos HEAD.
    • Una solución alternativa para esta solución consiste en agregar una tercera columna, Stateque es un indicador simple para declarar si un elemento de la lista está "activo" o no, y el índice exclusivo ignora los elementos inactivos.
  • Esto es algo que SQL Server solía admitir en la década de 1990 y luego eliminaron inexplicablemente el soporte para ello.

Solución 1: necesita capacidad para realizar un trivial ORDER BY.

Aquí hay una VISIÓN utilizando un CTE recursivo que agrega una SortOrdercolumna:

CREATE VIEW OrderableWishlistItems AS 

    WITH c ( ItemId, WishlistId, [Text], SortAfter, SortOrder )
    AS
    (
        SELECT
              ItemId, WishlistId, [Text], SortAfter, 1 AS SortOrder
        FROM
              WishlistItems
        WHERE
              SortAfter IS NULL

        UNION ALL

        SELECT
              i.ItemId, i.WishlistId, i.[Text], i.SortAfter, c.SortOrder + 1
        FROM
              WishlistItems AS i
              INNER JOIN c ON
                  i.WishlistId = c.WishlistId
                  AND
                  i.SortAfter = c.ItemId
    )
    SELECT
        ItemId, WishlistId, [Text], SortAfter, SortOrder
    FROM
        c;

Puede usar esta VISTA en otras consultas en las que necesite ordenar valores usando ORDER BY:

Query:

    SELECT * FROM OrderableWishlistItems

Results:

    ItemId  WishlistId  Text        SortAfter   SortOrder
    1       1           One         (null)      1
    2       1           Two             1       2
    3       1           Three           2       3
    4       1           Four            3       4
    5       1           Five            4       5
    6       1           Six             5       6
    7       1           Seven           6       7
    8       1           Eight           7       8

Solución 2: Prevención de UNIQUE INDEXrestricciones de violación al realizar operaciones:

Agregue una Statecolumna a la WishlistItemstabla. La columna está marcada como HIDDENasí que la mayoría de las herramientas ORM (como Entity Framework) no la incluirán al generar modelos, por ejemplo.

CREATE TABLE WishlistItems (
  ItemId     int           NOT NULL IDENTITY(1,1),
  WishlistId int           NOT NULL,
  Text       nvarchar(200) NOT NULL,
  SortAfter  int               NULL,
  [State]    bit           NOT NULL HIDDEN,

  CONSTRAINT PK_WishlistItem PRIMARY KEY ( ItemId, WishlistId ),
  CONSTRAINT FK_Wishlist_WishlistItem FOREIGN KEY ( WishlistId ) REFERENCES Wishlists ( WishlistId ),
  CONSTRAINT FK_Sorting FOREIGN KEY ( SortAfter, WishlistId ) REFERENCES WishlistItems ( ItemId, WishlistId )
);

CREATE UNIQUE INDEX UX_Sorting ON WishlistItems ( SortAfter, WishlistId ) WHERE [State] = 1;

Operaciones:

Agregar un nuevo elemento al final de la lista:

1. Cargue la lista primero para determinar el ItemIdúltimo elemento actual de la lista y guárdelo @tailItemId, o úselo SELECT MAX( SortOrder ) FROM OrderableWishlistItems WHERE WishlistId = @listId.
2. INSERT INTO WishlistItems ( WishlistId, [Text], SortAfter ) VALUES ( @listId, @text, @tailItemId ).

Reordenar el elemento 4 por debajo del elemento 7

BEGIN TRANSACTION

    DECLARE @itemIdToMove int = 4
    DECLARE @itemIdToMoveAfter int = 7

    DECLARE @prev int = ( SELECT SortAfter FROM WishlistItems WHERE ItemId = @itemIdToMove )

    UPDATE WishlistItems SET [State] = 0 WHERE ItemId IN ( @itemIdToMove , @itemIdToMoveAfter )

    UPDATE WishlistItems SET [SortAfter] = @itemIdToMove WHERE ItemId = @itemIdToMoveAfter 

    UPDATE WishlistItems SET [SortAfter] = @prev WHERE SortAfter = @itemIdToMove 

    UPDATE WishlistItems SET [State] = 1 WHERE ItemId IN ( @itemIdToMove, @itemIdToMoveAfter )

COMMIT;

Eliminando el elemento 4 del medio de la lista:

Si un elemento está al final de la lista (es decir, dónde NOT EXISTS ( SELECT 1 FROM WishlistItems WHERE SortAfter = @itemId )), puede hacer uno solo DELETE.

Si un elemento tiene un elemento ordenado después de él, realiza los mismos pasos que reordenar un elemento, excepto que DELETElo haga después en lugar de configurarlo State = 1;.

BEGIN TRANSACTION

    DECLARE @itemIdToRemove int = 4

    DECLARE @prev int = ( SELECT SortAfter FROM WishlistItems WHERE ItemId = @itemIdToRemove )

    UPDATE WishlistItems SET [State] = 0 WHERE ItemId = @itemIdToRemove

    UPDATE WishlistItems SET [SortAfter] = @prev WHERE SortAfter = @itemIdToRemove

    DELETE FROM WishlistItems WHERE ItemId = @itemIdToRemove

COMMIT;