Armazenando uma lista reordenada em um banco de dados

Estou trabalhando em um sistema de lista de desejos, no qual os usuários podem adicionar itens às suas várias listas de desejos e pretendo permitir que os usuários reordenem os itens posteriormente. Não tenho muita certeza sobre a melhor maneira de armazenar isso em um banco de dados, mantendo-se rápido e sem virar uma bagunça (esse aplicativo será usado por uma base de usuários bastante grande, por isso não quero que ele desça para limpar as coisas).

Inicialmente, tentei uma positioncoluna, mas parece que seria bastante ineficiente ter que alterar o valor da posição de todos os outros itens quando você os move.

Vi pessoas usando uma auto-referência para se referir ao valor anterior (ou próximo), mas, novamente, parece que você precisaria atualizar muitos outros itens da lista.

Outra solução que eu vi é usar números decimais e apenas colocar itens nas lacunas entre eles, o que parece ser a melhor solução até agora, mas tenho certeza de que deve haver uma maneira melhor.

Eu diria que uma lista típica conteria cerca de 20 itens, e provavelmente a limitará a 50. A reordenação usaria o recurso de arrastar e soltar e provavelmente será feita em lotes para evitar condições de corrida e outras coisas. solicitações ajax. Estou usando o postgres (no heroku), se isso importa.

Alguém tem alguma idéia?

Felicidades por qualquer ajuda!

Primeiro, não tente fazer nada inteligente com números decimais, porque eles vão te incomodar. REALe DOUBLE PRECISIONsão inexatos e podem não representar adequadamente o que você coloca neles. NUMERICé exato, mas a sequência correta de movimentos o esgotará com precisão e sua implementação será interrompida.

Limitar movimentos a altos e baixos únicos torna toda a operação muito fácil. Para uma lista de itens numerados seqüencialmente, você pode mover um item para cima, decrementando sua posição e aumentando o número da posição de qualquer que seja o decremento anterior. (Em outras palavras, o item 5se tornaria 4e o que era item 4se tornaria 5, efetivamente uma troca como os idiotas descreveram em sua resposta.) Movê-lo para baixo seria o oposto. Indexe sua tabela de acordo com o que identifica exclusivamente uma lista e posição e você pode fazê-lo com dois UPDATEsegundos em uma transação que será executada muito rapidamente. A menos que seus usuários reorganizem suas listas em velocidades sobre-humanas, isso não causará muita carga.

Movimentos de arrastar e soltar (por exemplo, mover item 6para ficar entre itens 9e 10) são um pouco mais complicados e precisam ser feitos de maneira diferente, dependendo se a nova posição está acima ou abaixo da antiga. No exemplo acima, é necessário abrir um furo incrementando todas as posições maiores que 9, atualizando 6a posição do item para ser o novo 10e diminuindo a posição de tudo maior do 6que preencher o local vazio. Com a mesma indexação descrita anteriormente, isso será rápido. Você pode realmente fazer isso ir um pouco mais rápido do que eu descrevi, minimizando o número de linhas que a transação toca, mas essa é uma micro otimização que você não precisa até que possa provar que há um gargalo.

De qualquer forma, tentar superar o banco de dados com uma solução caseira e inteligente demais pela metade geralmente não leva ao sucesso. Bancos de dados que valem a pena foram cuidadosamente escritos para executar essas operações muito, muito rapidamente por pessoas que são muito, muito boas nisso.

Mesma resposta a partir daqui https://stackoverflow.com/a/49956113/10608

Solução: faça indexuma string (porque as strings, em essência, têm infinita "precisão arbitrária"). Ou, se você usar um int, aumente indexem 100 em vez de 1.

O problema de desempenho é este: não há valores "entre" entre dois itens classificados.

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

Em vez disso, faça o seguinte (melhor solução abaixo):

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

Melhor ainda: eis como Jira resolve esse problema. Sua "classificação" (o que você chama de índice) é um valor de string que permite uma tonelada de espaço para respirar entre os itens classificados.

Aqui está um exemplo real de um banco de dados jira com o qual trabalho

   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

Observe este exemplo hzztzz:i. A vantagem de um ranking de cordas é que você fica sem espaço entre dois itens e ainda não precisa classificar mais nada. Você apenas começa a acrescentar mais caracteres à string para restringir o foco.

Vi pessoas usando uma auto-referência para se referir ao valor anterior (ou próximo), mas, novamente, parece que você precisaria atualizar muitos outros itens da lista.

Por quê? Digamos que você adote uma abordagem de tabela de lista vinculada com colunas (listID, itemID, nextItemID).

Inserir um novo item em uma lista custa uma inserção e uma linha modificada.

Reposicionar um item custa três modificações de linha (o item que está sendo movido, o item antes dele e o item antes de seu novo local).

A remoção de um item custa uma exclusão e uma linha modificada.

Esses custos permanecem os mesmos, independentemente de a lista ter 10 itens ou 10.000 itens. Nos três casos, há uma modificação a menos se a linha de destino for o primeiro item da lista. Se você estiver operando com mais frequência no último item da lista, pode ser benéfico armazenar o prevItemID em vez do próximo.

"mas parece que isso seria bastante ineficiente"

Você mediu isso? Ou isso é apenas um palpite? Não faça tais suposições sem nenhuma prova.

"20 a 50 itens por lista"

Honestamente, isso não é "um monte de itens", para mim isso soa muito pouco.

Sugiro que você se atenha à abordagem "coluna da posição" (se essa for a implementação mais simples para você). Para esses tamanhos de lista pequenos, não inicie a otimização desnecessária antes de ter problemas reais de desempenho

Esta é realmente uma questão de escala e caso de uso.

Quantos itens você espera em uma lista? Se milhões, acho que a rota decimal é a mais óbvia.

Se 6, a renumeração de números inteiros é a escolha óbvia. s Além disso, a questão é como as listas são reorganizadas. Se você estiver usando as setas para cima e para baixo (movendo para cima ou para baixo um slot de cada vez), o i usaria números inteiros e depois trocaria com o anterior (ou o próximo) em movimento.

Também com que frequência você confirma, se o usuário pode fazer 250 alterações e confirmar de uma só vez, do que eu digo números inteiros com renumeração novamente ...

tl; dr: Precisa de mais informações.

Edit: "Wish lists" parece um monte de listas pequenas (suposição, isso pode ser falso) .. Então eu digo Inteiro com renumeração. (Cada lista contém sua própria posição)

Se o objetivo é minimizar o número de operações do banco de dados por operação de reordenação:

Assumindo que

• Todos os itens de compras podem ser enumerados com números inteiros de 32 bits.
• Há um limite máximo de tamanho para a lista de desejos de um usuário. (Vi um site popular usar de 20 a 40 itens como limite)

Armazene a lista de desejos classificada do usuário como uma sequência compactada de números inteiros (matrizes inteiras) em uma coluna. Sempre que a lista de desejos é reordenada, a matriz inteira (linha única; coluna única) é atualizada - o que deve ser executado com uma única atualização SQL.

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

Se o objetivo for diferente, continue com a abordagem "coluna da posição".

Em relação à "velocidade", certifique-se de comparar a abordagem do procedimento armazenado. Embora a emissão de mais de 20 atualizações separadas para um shuffle de uma lista de desejos possa ser lenta, pode haver uma maneira rápida de usar o procedimento armazenado.

OK Enfrento esse problema complicado recentemente, e todas as respostas neste post de perguntas e respostas deram muitas inspirações. Do meu ponto de vista, cada solução tem seus prós e contras.

• Se o positioncampo tiver que ser seqüencial sem intervalos, será necessário reordenar a lista inteira. Esta é uma operação O (N). A vantagem é que o lado do cliente não precisaria de nenhuma lógica especial para obter o pedido.

• Se queremos evitar a operação O (N), MAS AINDA manter uma sequência precisa, uma das abordagens é usar "auto-referência para se referir ao valor anterior (ou próximo)". Este é um cenário de lista vinculada a livros didáticos. Por design, NÃO incorrerá em "muitos outros itens da lista". No entanto, isso requer que o lado do cliente (um serviço da Web ou talvez um aplicativo móvel) implemente a lógica travesal da lista vinculada para derivar o pedido.

• Algumas variações não usam referência, ou seja, lista vinculada. Eles escolhem representar o pedido inteiro como um blob independente, como um JSON-array-in-a-string [5,2,1,3,...]; essa ordem será armazenada em um local separado. Essa abordagem também tem o efeito colateral de exigir que o código do lado do cliente mantenha esse blob de pedido separado.

• Em muitos casos, não precisamos realmente armazenar a ordem exata, apenas precisamos manter uma classificação relativa entre cada registro. Portanto, podemos permitir lacunas entre registros seqüenciais. As variações incluem: (1) usando números inteiros com intervalos como 100, 200, 300 ... mas você ficará rapidamente sem intervalos e precisará do processo de recuperação; (2) usando decimal que vem com lacunas naturais, mas você precisará decidir se pode viver com a eventual limitação de precisão; (3) usando classificação baseada em string, conforme descrito nesta resposta, mas tenha cuidado com as armadilhas de implementação complicadas .

• A resposta real pode ser "depende". Revise seus requisitos de negócios. Por exemplo, se for um sistema de lista de desejos, pessoalmente eu usaria felizmente um sistema organizado por apenas algumas fileiras como "indispensável", "bom de ter", "talvez mais tarde" e, em seguida, apresentaria itens sem particular ordem dentro de cada fila. Se for um sistema de entrega, você pode muito bem usar o tempo de entrega como uma classificação aproximada que vem com uma lacuna natural (e prevenção natural de conflitos, pois nenhuma entrega aconteceria ao mesmo tempo). Sua milhagem pode variar.

Use um número de ponto flutuante para a coluna da posição.

Você pode reordenar a lista alterando apenas a coluna de posição na linha "movida".

Basicamente, se seu usuário deseja posicionar "vermelho" depois de "azul", mas antes de "amarelo"

Então você só precisa calcular

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

Após alguns milhões de reposicionamentos, você pode obter números de ponto flutuante tão pequenos que não há "entre" - mas é quase tão provável quanto avistar um unicórnio.

Você pode implementar isso usando um campo inteiro com um intervalo inicial de, digamos, 1000. Portanto, seu oredring inicial seria 1000-> azul, 2000-> amarelo, 3000-> vermelho. Depois de "mover" o vermelho após o azul, você teria 1000-> azul, 1500-> vermelho, 2000-> amarelo.

O problema é que, com um intervalo inicial aparentemente grande de 1000, apenas 10 movimentos o colocam em uma situação como 1000-> azul, 1001-puce, 1004-> biege ......, onde você não poderá mais para inserir qualquer coisa depois de "azul" sem renumerar a lista inteira. Usando números de ponto flutuante, sempre haverá um ponto "intermediário" entre as duas posições.

Embora o OP tenha abordado brevemente a noção de uso de uma lista vinculada para armazenar a ordem de classificação, ele possui muitas vantagens nos casos em que os itens serão reordenados com frequência.

Vi pessoas usando uma auto-referência para se referir ao valor anterior (ou próximo), mas, novamente, parece que você precisaria atualizar muitos outros itens da lista.

A questão é - você não ! Ao usar uma lista vinculada, inserção, exclusão e reordenação são O(1)operações, e a integridade referencial imposta pelo banco de dados garante que não haja referências quebradas, registros órfãos ou loops.

Aqui está um exemplo:

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;

Observe o seguinte:

• Usando uma chave primária e uma chave estrangeira compostas FK_Sortingpara impedir que os itens se refiram acidentalmente ao item pai errado.
• O UNIQUE INDEX UX_Sortingexecuta duas funções:
  • Como permite um NULLvalor único, cada lista pode ter apenas 1 item "principal".
  • Impede que dois ou mais itens reivindiquem estar no mesmo local de classificação (impedindo SortAftervalores duplicados ).

As principais vantagens dessa abordagem:

• Nunca requer reequilíbrio ou manutenção - como ocorre com as ordens de classificação baseadas intou realque acabam ficando sem espaço entre os itens após reordenamentos frequentes.
• Somente itens reordenados (e seus irmãos) precisam ser atualizados.

Essa abordagem tem desvantagens, no entanto:

• Você só pode classificar essa lista no SQL usando um CTE recursivo porque não pode fazer uma tarefa direta ORDER BY.
  • Como solução alternativa, você pode criar um wrapper VIEWou TVF que use um CTE para adicionar um derivado contendo uma ordem de classificação incremental - mas isso seria caro para uso em grandes operações.
• Você deve carregar a lista inteira no seu programa para exibi-la - você não pode operar em um subconjunto das linhas, porque a SortAftercoluna se referirá aos itens que não foram carregados no seu programa.
  • No entanto, o carregamento de todos os itens para uma lista é fácil devido à chave primária composta (ou seja, basta fazê-lo SELECT * FROM WishlistItems WHERE WishlistId = @wishlistToLoad).
• A execução de qualquer operação enquanto UX_Sortingestiver ativada requer suporte do DBMS para restrições adiadas.
  • ou seja, a implementação ideal dessa abordagem não funcionará no SQL Server até que eles adicionem suporte adicional a restrições e índices adiados.
  • Uma solução alternativa é tornar o Índice Único um Índice Filtrado que permita vários NULLvalores na coluna - o que infelizmente significa que uma Lista pode ter vários itens HEAD.
    • Uma solução alternativa para essa solução alternativa é adicionar uma terceira coluna, Stateque é um sinalizador simples para declarar se um item da lista está "ativo" ou não - e o índice exclusivo ignora itens inativos.
  • Isso é algo que o SQL Server usou para oferecer suporte na década de 1990 e, em seguida, eles inexplicavelmente removeram o suporte.

Solução alternativa 1: precisa da capacidade de executar uma tarefa trivial ORDER BY.

Aqui está uma VIEW usando uma CTE recursiva que adiciona uma SortOrdercoluna:

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;

Você pode usar esse VIEW em outras consultas nas quais você precisa classificar 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

Solução alternativa 2: Evitando UNIQUE INDEXrestrições de violação ao executar operações:

Adicione uma Statecoluna à WishlistItemstabela. A coluna está marcada como HIDDENa maioria das ferramentas ORM (como o Entity Framework) não a inclui ao gerar modelos, por exemplo.

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;

Operações:

Adicionando um novo item ao final da lista:

1. Carregue a lista primeiro para determinar o ItemIdúltimo item atual na lista e armazene @tailItemId- ou use SELECT MAX( SortOrder ) FROM OrderableWishlistItems WHERE WishlistId = @listId.
2. INSERT INTO WishlistItems ( WishlistId, [Text], SortAfter ) VALUES ( @listId, @text, @tailItemId ).

Reordenando o item 4 para ficar abaixo do item 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;

Removendo o item 4 do meio da lista:

Se um item estiver no final da lista (ou seja, onde NOT EXISTS ( SELECT 1 FROM WishlistItems WHERE SortAfter = @itemId )), você poderá fazer um único DELETE.

Se um item tiver um item classificado após ele, execute as mesmas etapas para reordenar um item, exceto você DELETEdepois em vez de definir 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;