Como armazenar informações solicitadas em um banco de dados relacional

20

Estou tentando entender como armazenar corretamente as informações solicitadas em um banco de dados relacional.

Um exemplo:

Digamos que eu tenha uma lista de reprodução, composta por músicas. Dentro do meu banco de dados relacional, tenho uma tabela Playlistscontendo alguns metadados (nome, criador, etc.). Eu também tenho uma tabela chamada Songs, contendo informações sobre a playlist_idmúsica e também sobre a música (nome, artista, duração etc.).

Por padrão, quando uma nova música é adicionada a uma lista de reprodução, ela é anexada ao final. Ao fazer o pedido no ID da música (crescente), a ordem será a ordem de adição. Mas e se um usuário conseguir reordenar músicas na lista de reprodução?

Eu vim com algumas idéias, cada uma com suas vantagens e desvantagens:

  1. Uma coluna chamada order, que é um número inteiro . Quando uma música é movida, a ordem de todas as músicas entre a antiga e a nova posição é alterada, para refletir a alteração. A desvantagem disso é que muitas consultas precisam ser feitas toda vez que uma música é movida, e o algoritmo de movimentação não é tão trivial quanto nas outras opções.
  2. Uma coluna chamada order, que é um decimal ( NUMERIC). Quando uma música é movida, é atribuído o valor do ponto flutuante entre os dois números adjacentes. Desvantagem: os campos decimais ocupam mais espaço e pode ser possível ficar sem precisão, a menos que seja tomado o cuidado de redistribuir o intervalo após algumas alterações.
  3. Outra maneira seria ter previousum nextcampo e que faça referência a outras músicas. (ou são NULL no caso da primeira e da última música da lista de reprodução no momento; basicamente, você cria uma lista vinculada ). Desvantagem: consultas como 'encontrar a décima música na lista' não são mais de tempo constante, mas sim de tempo linear.

Qual desses procedimentos é mais frequentemente usado na prática? Qual desses procedimentos é mais rápido em bancos de dados de médio a grande porte? Existem outras maneiras de arquivar isso?

EDIT: Por uma questão de simplicidade, no exemplo, uma música pertence apenas a uma lista de reprodução (um relacionamento muitos-para-um). Obviamente, também é possível usar uma Junction Table para que a lista de músicas seja uma relação de muitos para muitos (e aplique uma das estratégias acima nessa tabela).

Qqwy
fonte
1
Você pode usar a opção um (faça o pedido como Inteiro) com 100 etapas. Então você não precisa reordenar se mover uma música, basta ter um valor entre as 100. De vez em quando, você pode precisar de uma nova renumeração para obter novamente intervalos entre as músicas.
Knut
4
"A desvantagem disso é que muitas consultas precisam ser feitas sempre que uma música é movida"?! - update songorder set order = order - 1 where order >= 12 & order <= 42; update songorder set order = 42 where id = 123;- são duas atualizações - não trinta. Três, se você quiser colocar uma restrição exclusiva em ordem.
2
Use a opção um, a menos que saiba de fato que precisa de outra coisa. Um problema que os programadores novatos em bancos de dados encontram não é entender que os bancos de dados são muito, muito bons nesse tipo de coisa. Não tenha medo de colocar seu banco de dados para trabalhar.
GrandmasterB
1
Queries like 'find the Xth Song in the list' are no longer constant-timetambém é válido para a opção 2.
Doc Brown
2
@ MikeNakis: Parece caro, mas todo o trabalho está sendo feito no servidor, que é (geralmente) otimizado para esse tipo de trabalho. Eu não usaria essa técnica em uma tabela com milhões de linhas, mas não a descontaria em uma tabela com apenas alguns milhares.
TMN

Respostas:

29

Os bancos de dados são otimizados para certas coisas. A atualização rápida de muitas linhas é uma delas. Isso se torna especialmente verdadeiro quando você deixa o banco de dados fazer seu trabalho.

Considerar:

order song
1     Happy Birthday
2     Beat It
3     Never Gonna Give You Up
4     Safety Dance
5     Imperial March

E você quer ir Beat Itpara o final, você teria duas consultas:

update table 
  set order = order - 1
  where order >= 2 and order <= 5;

update table
  set order = 5
  where song = 'Beat It'

E é isso. Isso aumenta muito bem com números muito grandes. Tente colocar alguns milhares de músicas em uma lista de reprodução hipotética em seu banco de dados e veja quanto tempo leva para mover uma música de um local para outro. Como estes têm formas muito padronizadas:

update table 
  set order = order - 1
  where order >= ? and order <= ?;

update table
  set order = ?
  where song = ?

Você tem duas instruções preparadas que podem ser reutilizadas com muita eficiência.

Isso fornece algumas vantagens significativas - a ordem da tabela é algo que você pode pensar. A terceira música tem um orderde 3, sempre. A única maneira de garantir isso é usar números inteiros consecutivos como a ordem. O uso de listas pseudo-vinculadas ou números decimais ou números inteiros com lacunas não permitirá garantir essa propriedade; nesses casos, a única maneira de obter a enésima música é ordenar a tabela inteira e obter o enésimo registro.

E realmente, isso é muito mais fácil do que você pensa. É simples descobrir o que você deseja fazer, gerar as duas instruções de atualização e outras pessoas olharem para essas duas instruções de atualização e perceberem o que está sendo feito.

vedante
fonte
2
Estou começando a gostar dessa abordagem.
Mike Nakis
2
@ MikeNakis funciona bem. Há também uma árvore binária baseada em uma idéia semelhante - a árvore de pré-encomenda modificada . Demora um pouco mais para entender, mas permite fazer algumas consultas muito agradáveis ​​para dados hierárquicos. Nunca tive problemas de desempenho, mesmo em árvores grandes. Ser capaz de raciocinar sobre o código é algo que enfatizo até que seja mostrado que o código simples não possui o desempenho necessário (e isso ocorreu apenas em situações extremas).
Haverá problemas com o uso de orderuma vez que order byé uma palavra-chave?
kojow7
@ kojow7, se seus campos tiverem nomes conflitantes com palavras-chave, você deverá colocá-los entre as marcas "` ".
Andri
Essa abordagem faz sentido, mas qual é a melhor maneira de obter ordervalor ao adicionar uma nova música a uma lista de reprodução. Digamos que seja a 9ª música, existe uma maneira melhor de inserir 9 do orderque fazer COUNTantes de adicionar o disco?
delashum 15/10
3

Primeiro, não está claro em sua descrição o que você fez, mas você precisa de uma PlaylistSongstabela que contenha a PlaylistIde a SongId, descrevendo quais músicas pertencem a quais listas de reprodução.

É nesta tabela que você precisa adicionar informações sobre pedidos.

Meu mecanismo favorito é com números reais. Eu o implementei recentemente e funcionou como um encanto. Quando você deseja mover uma música para uma posição específica, calcula seu novo Orderingvalor como a média dos Orderingvalores da música anterior e da próxima música. Se você usar um número real de 64 bits, ficará sem precisão quase ao mesmo tempo em que o inferno congelará, mas se estiver realmente escrevendo seu software para a posteridade, considere reatribuir bons Orderingvalores inteiros arredondados a todas as músicas em cada lista de reprodução de vez em quando.

Como um bônus adicional, aqui está o código que eu escrevi que implementa isso. É claro que você não pode usá-lo como está, e agora seria muito trabalhoso higienizá-lo para você, por isso estou postando apenas para que você possa ter idéias.

A classe é ParameterTemplate(seja o que for, não pergunte!) O método obtém a lista de modelos de parâmetros aos quais esse modelo pertence do pai ActivityTemplate. (Seja como for, não pergunte!) O código contém alguma proteção contra a falta de precisão. O divisor é usado para teste: o teste de unidade usa um divisor grande para ficar sem precisão rapidamente e, assim, acionar o código de proteção de precisão. O segundo método é público e "apenas para uso interno; não invoque" para que o código de teste possa invocá-lo. (Não pode ser privado de pacote porque meu código de teste não está no mesmo pacote que o código que ele testa.) O campo que controla a ordem é chamado Ordering, acessado por meio de getOrdering()e setOrdering(). Você não vê nenhum SQL porque estou usando o Mapeamento Relacional a Objetos via Hibernate.

/**
 * Moves this {@link ParameterTemplate} to the given index in the list of {@link ParameterTemplate}s of the parent {@link ActivityTemplate}.
 *
 * The index must be greater than or equal to zero, and less than or equal to the number of entries in the list.  Specifying an index of zero will move this item to the top of
 * the list. Specifying an index which is equal to the number of entries will move this item to the end of the list.  Any other index will move this item to the position
 * specified, also moving other items in the list as necessary. The given index cannot be equal to the current index of the item, nor can it be equal to the current index plus
 * one.  If the given index is below the current index of the item, then the item will be moved so that its new index will be equal to the given index.  If the given index is
 * above the current index, then the new index of the item will be the given index minus one.
 *
 * NOTE: this method flushes the persistor and refreshes the parent node so as to guarantee that the changes will be immediately visible in the list of {@link
 * ParameterTemplate}s of the parent {@link ActivityTemplate}.
 *
 * @param toIndex the desired new index of this {@link ParameterTemplate} in the list of {@link ParameterTemplate}s of the parent {@link ActivityTemplate}.
 */
public void moveAt( int toIndex )
{
    moveAt( toIndex, 2.0 );
}

/**
 * For internal use only; do not invoke.
 */
public boolean moveAt( int toIndex, double divisor )
{
    MutableList<ParameterTemplate<?>> parameterTemplates = getLogicDomain().getMutableCollections().newArrayList();
    parameterTemplates.addAll( getParentActivityTemplate().getParameterTemplates() );
    assert parameterTemplates.getLength() >= 1; //guaranteed since at the very least, this parameter template must be in the list.
    int fromIndex = parameterTemplates.indexOf( this );
    assert 0 <= toIndex;
    assert toIndex <= parameterTemplates.getLength();
    assert 0 <= fromIndex;
    assert fromIndex < parameterTemplates.getLength();
    assert fromIndex != toIndex;
    assert fromIndex != toIndex - 1;

    double order;
    if( toIndex == 0 )
    {
        order = parameterTemplates.fetchFirstElement().getOrdering() - 1.0;
    }
    else if( toIndex == parameterTemplates.getLength() )
    {
        order = parameterTemplates.fetchLastElement().getOrdering() + 1.0;
    }
    else
    {
        double prevOrder = parameterTemplates.get( toIndex - 1 ).getOrdering();
        parameterTemplates.moveAt( fromIndex, toIndex );
        double nextOrder = parameterTemplates.get( toIndex + (toIndex > fromIndex ? 0 : 1) ).getOrdering();
        assert prevOrder <= nextOrder;
        order = (prevOrder + nextOrder) / divisor;
        if( order <= prevOrder || order >= nextOrder ) //if the accuracy of the double has been exceeded
        {
            parameterTemplates.clear();
            parameterTemplates.addAll( getParentActivityTemplate().getParameterTemplates() );
            for( int i = 0; i < parameterTemplates.getLength(); i++ )
                parameterTemplates.get( i ).setOrdering( i * 1.0 );
            rocs3dDomain.getPersistor().flush();
            rocs3dDomain.getPersistor().refresh( getParentActivityTemplate() );
            moveAt( toIndex );
            return true;
        }
    }
    setOrdering( order );
    rocs3dDomain.getPersistor().flush();
    rocs3dDomain.getPersistor().refresh( getParentActivityTemplate() );
    assert getParentActivityTemplate().getParameterTemplates().indexOf( this ) == (toIndex > fromIndex ? toIndex - 1 : toIndex);
    return false;
}
Mike Nakis
fonte
Eu usaria uma ordem inteira e, se considerasse a reordenação muito cara, reduziria o número de reordenações, fazendo com que cada uma delas saltasse com X, onde X é a quantidade necessária para reduzir a reordenação, digamos 20, que deve estar bem como iniciante.
Warren P
1
@ WarrenP Sim, eu sei, isso também pode ser feito dessa maneira, é por isso que chamei essa abordagem de "meu favorito" em vez de "melhor" ou "único".
Mike Nakis
0

O que funcionou para mim, para uma pequena lista da ordem de 100 itens, foi usar uma abordagem híbrida:

  1. Decimal SortOrder, mas com precisão suficiente para armazenar 0,5 diferenças (isto é, decimal (8,2) ou algo assim).
  2. Ao classificar, pegue as PKs da linha acima e abaixo de onde a linha atual foi movida, se elas existirem. (Você não terá uma linha acima se mover o item para a primeira posição, por exemplo)
  3. Poste as PKs da linha atual, anterior e seguinte no servidor para executar a classificação.
  4. Se você tiver uma linha anterior, defina a posição da linha atual como anterior + 0,5. Se você tiver apenas uma próxima, defina a posição da linha atual para a próxima - 0,5.
  5. Em seguida, tenho um processo Stored que atualiza todas as posições usando a função Row_Number do SQL Server, ordenando pela nova ordem de classificação. Isso transformará a ordem de 1,1,5,2,3,4,6 para 1,2,3,4,5,6, pois a função row_number fornece ordinais inteiros.

Então, você acaba com uma ordem inteira sem intervalos, armazenada em uma coluna decimal. É bastante limpo, eu sinto. Mas isso pode não aumentar muito bem quando você tiver centenas de milhares de linhas que precisam atualizar, tudo de uma vez. Mas se sim, por que você está usando uma classificação definida pelo usuário em primeiro lugar? (Nota: se você tiver uma tabela grande com milhões de usuários, mas cada usuário tiver apenas algumas centenas de itens para classificar, poderá usar a abordagem acima muito bem, pois você usará uma cláusula where para limitar as alterações a apenas um usuário )

John
fonte