Comment stocker les informations commandées dans une base de données relationnelle

20

J'essaie de comprendre comment stocker correctement les informations commandées dans une base de données relationnelle.

Un exemple:

Disons que j'ai une liste de lecture, composée de morceaux. Dans ma base de données relationnelle, j'ai une table de Playlists, contenant des métadonnées (nom, créateur, etc.). J'ai également une table appelée Songs, contenant une information sur la playlist_idchanson, ainsi que sur la chanson (nom, artiste, durée, etc.).

Par défaut, lorsqu'un nouveau morceau est ajouté à une liste de lecture, il est ajouté à la fin. Lors de la commande sur Song-ID (ascendant), l'ordre sera l'ordre d'addition. Mais que se passe-t-il si un utilisateur doit pouvoir réorganiser des chansons dans la liste de lecture?

J'ai proposé quelques idées, chacune avec ses avantages et ses inconvénients:

  1. Une colonne appelée order, qui est un entier . Lorsqu'un morceau est déplacé, l'ordre de tous les morceaux entre son ancienne et sa nouvelle position est modifié pour refléter le changement. L'inconvénient de cela est que de nombreuses requêtes doivent être effectuées chaque fois qu'un morceau est déplacé, et l'algorithme de déplacement n'est pas aussi trivial qu'avec les autres options.
  2. Une colonne appelée order, qui est un décimal ( NUMERIC). Lorsqu'un morceau est déplacé, une valeur à virgule flottante lui est attribuée entre les deux nombres adjacents. Inconvénient: les champs décimaux prennent plus d'espace et il peut être possible de manquer de précision, à moins que l'on prenne soin de redistribuer la plage après quelques modifications.
  3. Une autre façon serait d'avoir un previouset un nextchamp qui référencent d'autres chansons. (ou sont NULL dans le cas de la première ou de la dernière chanson de la liste de lecture en ce moment; Fondamentalement, vous créez une liste liée ). Inconvénient: les requêtes comme «trouver le Xème morceau dans la liste» ne sont plus à temps constant, mais à temps linéaire.

Laquelle de ces procédures est la plus utilisée dans la pratique? Laquelle de ces procédures est la plus rapide sur des bases de données moyennes à grandes? Existe-t-il d'autres moyens de l'archiver?

EDIT: Par souci de simplicité, dans l'exemple, un morceau n'appartient qu'à une liste de lecture (relation plusieurs-à-un). Bien sûr, on pourrait également utiliser une table de jonction, donc song⟷playlist est une relation plusieurs-à-plusieurs (et appliquer l'une des stratégies ci-dessus sur cette table).

Qqwy
la source
1
Vous pouvez utiliser la première option (commander en entier) avec 100 étapes. Ensuite, vous n'avez pas besoin de réorganiser si vous déplacez un morceau, prenez simplement une valeur entre les 100. De temps en temps, vous devrez peut-être une nouvelle renumérotation pour obtenir à nouveau des écarts entre les morceaux.
knut
4
"L'inconvénient est que beaucoup de requêtes doivent être faites à chaque fois qu'une chanson est déplacée"?! - update songorder set order = order - 1 where order >= 12 & order <= 42; update songorder set order = 42 where id = 123;- c'est deux mises à jour - pas trente. Trois si vous voulez mettre de l'ordre dans une contrainte unique.
2
Utilisez la première option, sauf si vous savez pertinemment que vous avez besoin d'autre chose. Un problème rencontré par les programmeurs débutants dans les bases de données est de ne pas comprendre que les bases de données sont très, très bonnes dans ce genre de choses. N'ayez pas peur de mettre votre db au travail.
GrandmasterB
1
Queries like 'find the Xth Song in the list' are no longer constant-timeest également vrai pour l'option 2.
Doc Brown
2
@MikeNakis: Cela semble cher, mais tout le travail se fait sur le serveur, qui est (généralement) optimisé pour ce type de travail. Je n'utiliserais pas cette technique sur une table avec des millions de lignes, mais je ne l'escompterais pas pour une table avec seulement quelques milliers.
TMN

Réponses:

29

Les bases de données sont optimisées pour certaines choses. La mise à jour rapide de nombreuses lignes en fait partie. Cela devient particulièrement vrai lorsque vous laissez la base de données faire son travail.

Considérer:

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

Et vous voulez passer Beat Ità la fin, vous auriez deux requêtes:

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

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

Et c'est tout. Cela évolue très bien avec de très grands nombres. Essayez de mettre quelques milliers de chansons dans une liste de lecture hypothétique dans votre base de données et voyez combien de temps il faut pour déplacer une chanson d'un endroit à un autre. Comme ceux-ci ont des formes très standardisées:

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

update table
  set order = ?
  where song = ?

Vous disposez de deux instructions préparées que vous pouvez réutiliser très efficacement.

Cela offre des avantages importants - l'ordre de la table est quelque chose que vous pouvez raisonner. La troisième chanson a toujours un orderde 3. La seule façon de garantir cela est d'utiliser des entiers consécutifs comme ordre. L'utilisation de listes pseudo-liées ou de nombres décimaux ou d'entiers avec des espaces ne vous permettra pas de garantir cette propriété; dans ces cas, la seule façon d'obtenir le nième morceau est de trier la table entière et d'obtenir le nième enregistrement.

Et vraiment, c'est beaucoup plus facile que vous ne le pensez. Il est simple de comprendre ce que vous voulez faire, de générer les deux instructions de mise à jour et pour que d'autres personnes les regardent et réalisent ce qui est fait.

vedant
la source
2
Je commence à aimer cette approche.
Mike Nakis
2
@MikeNakis ça marche bien. Il existe également un arbre binaire basé sur une idée similaire - l' arbre de précommande modifié . Il faut un peu plus pour obtenir votre tête, mais cela vous permet de faire de très belles requêtes pour les données hiérarchiques. Je n'ai jamais eu de problèmes de performances avec, même dans les grands arbres. Pouvoir raisonner sur le code est quelque chose sur lequel j'insiste beaucoup jusqu'à ce qu'il soit démontré que le code simple n'a pas les performances nécessaires (et cela ne s'est produit que dans des situations extrêmes).
Y aura-t-il des problèmes avec l'utilisation orderpuisque order byc'est un mot clé?
kojow7
@ kojow7, si vos champs ont des noms en conflit avec des mots-clés, vous devez les encapsuler dans les coches "` ".
Andri
Cette approche est logique, mais quelle est la meilleure façon d'obtenir la ordervaleur lors de l'ajout d'une nouvelle chanson à une liste de lecture. Disons que c'est la 9ème chanson, y a-t-il une meilleure façon d'insérer 9 orderque de faire un COUNTavant d'ajouter l'enregistrement?
delashum
3

Tout d'abord, il n'est pas clair d'après votre description de ce que vous avez fait, mais vous avez besoin d'un PlaylistSongstableau qui contient un PlaylistIdet un SongId, décrivant quelles chansons appartiennent à quelles listes de lecture.

C'est dans ce tableau que vous devez ajouter les informations de commande.

Mon mécanisme préféré est avec des nombres réels. Je l'ai implémenté récemment et cela a fonctionné comme un charme. Lorsque vous souhaitez déplacer un morceau vers une position spécifique, vous calculez sa nouvelle Orderingvaleur comme la moyenne des Orderingvaleurs du morceau précédent et du morceau suivant. Si vous utilisez un nombre réel 64 bits, vous manquerez de précision à peu près au même moment où l'enfer gèlera, mais si vous écrivez vraiment votre logiciel pour la postérité, alors envisagez de réaffecter de belles Orderingvaleurs entières arrondies à toutes les chansons de chaque playlist de temps en temps.

En prime, voici le code que j'ai écrit qui implémente cela. Bien sûr, vous ne pouvez pas l'utiliser tel quel, et ce serait trop de travail pour moi en ce moment de le désinfecter pour vous, donc je ne le poste que pour que vous puissiez en tirer des idées.

La classe est ParameterTemplate(peu importe, ne demandez pas!) La méthode obtient la liste des modèles de paramètres auxquels ce modèle appartient de son parent ActivityTemplate. (Quoi qu'il en soit, ne demandez pas!) Le code contient une certaine protection contre le manque de précision. Le diviseur est utilisé pour les tests: le test unitaire utilise un grand diviseur afin de manquer de précision rapidement, et ainsi déclencher le code de garde de précision. La deuxième méthode est publique et "à usage interne uniquement; ne pas invoquer" afin que le code de test puisse l'invoquer. (Il ne peut pas être privé de package car mon code de test n'est pas dans le même package que le code qu'il teste.) Le champ qui contrôle la commande est appelé Ordering, accessible via getOrdering()et setOrdering(). Vous ne voyez aucun SQL car j'utilise le mappage relationnel-objet 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
la source
J'utiliserais un ordre entier et si je pensais que la réorganisation était trop chère, je réduirais simplement le nombre de réordonnances, en faisant sauter chacune par X, où X est le montant dont j'ai besoin pour réduire la réorganisation, disons 20, ce qui devrait être bien en entrée.
Warren P
1
@WarrenP oui, je sais, cela peut aussi se faire de cette façon, c'est pourquoi je viens d'appeler cette approche "ma préférée" au lieu de "la meilleure" ou "la seule" approche.
Mike Nakis
0

Ce qui a fonctionné pour moi, pour une petite liste de l'ordre de 100 articles, c'est d'adopter une approche hybride:

  1. Colonne SortOrder décimale, mais avec une précision suffisante pour stocker une différence de 0,5 (c.-à-d. Decimal (8,2) ou quelque chose).
  2. Lors du tri, saisissez les PK de la ligne au-dessus et au-dessous de l'endroit où la ligne actuelle vient d'être déplacée, s'ils existent. (Vous n'aurez pas de ligne au-dessus si vous déplacez l'élément vers la première position, par exemple)
  3. Publiez les PK de la ligne actuelle, précédente et suivante sur le serveur pour effectuer le tri.
  4. Si vous avez une ligne précédente, définissez la position de la ligne actuelle sur prev + 0,5. Si vous ne disposez que d'un suivant, définissez la position de la ligne actuelle sur le suivant - 0,5.
  5. Ensuite, j'ai un proc stocké qui met à jour toutes les positions à l'aide de la fonction SQL Server Row_Number, trié par le nouvel ordre de tri. Cela transformera l'ordre de 1,1,5,2,3,4,6 en 1,2,3,4,5,6, car la fonction row_number vous donne des ordinaux entiers.

Vous vous retrouvez donc avec un ordre entier sans espace, stocké dans une colonne décimale. C'est assez propre, je pense. Mais il peut ne pas évoluer extrêmement bien une fois que vous avez des centaines de milliers de lignes que vous devez mettre à jour en une seule fois. Mais si vous le faites, pourquoi utilisez-vous un tri défini par l'utilisateur en premier lieu? (Remarque: si vous avez une grande table avec des millions d'utilisateurs mais que chaque utilisateur n'a que quelques centaines d'éléments à trier, vous pouvez très bien utiliser l'approche ci-dessus car vous utiliserez de toute façon une clause where pour limiter les modifications à un seul utilisateur )

John
la source