Come memorizzare le informazioni ordinate in un database relazionale

16

Sto cercando di capire come memorizzare correttamente le informazioni ordinate in un database relazionale.

Un esempio:

Dire che ho una playlist, composta da canzoni. All'interno del mio database relazionale, ho una tabella di Playlists , contenente alcuni metadati (nome, creatore, ecc.). Ho anche una tabella chiamata Songs , contenente un playlist_id , oltre a informazioni specifiche sul brano (nome, artista, durata, ecc.).

Per impostazione predefinita, quando una nuova song viene aggiunta a una playlist, viene aggiunta alla fine. Quando si ordina su Song ID (crescente), l'ordine sarà l'ordine di aggiunta. Ma cosa succede se un utente dovrebbe essere in grado di riordinare i brani nella playlist?

Ho trovato un paio di idee, ciascuna con i loro vantaggi e svantaggi:

  1. Una colonna chiamata order , che è un intero . Quando una canzone viene spostata, l'ordine di tutte le canzoni tra la sua posizione vecchia e quella nuova viene cambiato, per riflettere la modifica. Lo svantaggio di questo è che molte query devono essere fatte ogni volta che una canzone viene spostata, e l'algoritmo in movimento non è così banale come con le altre opzioni.
  2. Una colonna chiamata order , che è un decimale ( NUMERIC ). Quando una canzone viene spostata, viene assegnato il valore in virgola mobile tra i due numeri adiacenti. Svantaggio: i campi decimali richiedono più spazio e potrebbe essere possibile eseguire la precisione, a meno che non si prenda cura di ridistribuire l'intervallo dopo ogni modifica.
  3. Un altro modo sarebbe avere un campo previous e un next che facciano riferimento ad altre canzoni. (o sono NULL nel caso del primo brano, o dell'ultimo brano della playlist in questo momento: fondamentalmente si crea una lista collegata ). Svantaggio: le domande come "trova la Xth Song nell'elenco" non sono più costanti, ma al contrario linear-time.

Quale di queste procedure è più spesso utilizzata nella pratica? Quale di queste procedure è più veloce su database di dimensioni medio-grandi? Ci sono altri modi per ottenere questo?

EDIT: per motivi di semplicità, nell'esempio una song appartiene solo a una playlist (una relazione molti-a-uno). Naturalmente, si potrebbe anche usare una tabella di giunzione in modo che la playlist di song sia una relazione molti-a-molti (e applicare una delle strategie sopra indicate su quella tabella).

    
posta Qqwy 08.12.2015 - 22:49
fonte

3 risposte

18

I database sono ottimizzati per determinate cose. L'aggiornamento di molte righe rapidamente è uno di questi. Questo diventa particolarmente vero quando lasci che il database faccia il suo lavoro.

Si consideri:

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

E vuoi spostare Beat It alla fine, avresti due domande:

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

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

E questo è tutto. Questo si adatta molto bene con numeri molto grandi. Prova a mettere alcune migliaia di canzoni in un'ipotetica playlist nel tuo database e vedi quanto tempo ci vuole per spostare una canzone da una posizione all'altra. Poiché hanno forme molto standardizzate:

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

update table
  set order = ?
  where song = ?

Hai due istruzioni preparate che puoi riutilizzare in modo molto efficiente.

Ciò fornisce alcuni vantaggi significativi: l'ordine del tavolo è qualcosa su cui puoi ragionare. La terza canzone ha un id di 3. Sempre. L'unico modo per garantire ciò è utilizzare numeri interi consecutivi come ordine. L'uso di liste pseudo-linked o numeri decimali o interi con gap non consente di garantire questa proprietà; in questi casi l'unico modo per ottenere l'ennesima canzone è ordinare l'intera tabella e ottenere l'ennesimo record.

E davvero, questo è molto più facile di quanto tu pensi che sia. È semplice capire cosa si vuole fare, generare le due dichiarazioni di aggiornamento e per gli altri osservare le due dichiarazioni di aggiornamento e capire cosa si sta facendo.

    
risposta data 08.12.2015 - 23:26
fonte
3

Innanzitutto, non è chiaro dalla descrizione di ciò che hai fatto, ma hai bisogno di una tabella PlaylistSongs che contenga un PlaylistId e un SongId , che descriva quali brani appartengono a quali playlist.

È in questa tabella che devi aggiungere le informazioni per l'ordine.

Il mio meccanismo preferito è con numeri reali. L'ho implementato di recente, e ha funzionato come un fascino. Quando vuoi spostare una canzone in una posizione specifica, calcoli il suo nuovo valore Ordering come media dei valori Ordering della canzone precedente e della canzone successiva. Se si utilizza un numero reale a 64 bit, si esaurirà la precisione all'incirca allo stesso tempo in cui l'inferno si bloccherà, ma se si sta veramente scrivendo il software per i posteri, allora si consideri la riassegnazione di valori interi arrotondati Ordering a tutti canzoni in ogni playlist ogni tanto.

Come bonus aggiuntivo, ecco il codice che ho scritto che implementa questo. Naturalmente non puoi usarlo così com'è, e sarebbe troppo lavoro per me adesso per sanitizzarlo per te, quindi ti sto solo postando per te per ricavarne delle idee.

La classe è ParameterTemplate (qualunque cosa, non chiedere!) Il metodo ottiene l'elenco dei modelli di parametri a cui questo modello appartiene dal suo genitore ActivityTemplate . (Qualunque cosa, non chiedere!) Il codice contiene una guardia contro l'esaurimento della precisione. Il divisore viene utilizzato per il test: il test unitario utilizza un grande divisore in modo da esaurire la precisione rapidamente, e quindi innescare il codice di protezione di precisione. Il secondo metodo è public e "solo per uso interno, non invocare" in modo che il codice di testing possa richiamarlo. (Non può essere package-private perché il mio codice di test non si trova nello stesso pacchetto del codice testato.) Il campo che controlla l'ordine è chiamato Ordering , a cui si accede tramite getOrdering() e setOrdering() . Non vedi SQL perché sto usando Mappatura relazionale di oggetti tramite 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;
}
    
risposta data 08.12.2015 - 22:57
fonte
0

Ciò che ha funzionato per me, per una piccola lista dell'ordine di 100 articoli era di adottare un approccio ibrido:

  1. Colonna SortOrder decimale, ma con una precisione sufficiente per memorizzare 0,5 differenze (vale a dire decimale (8,2) o qualcosa).
  2. Durante l'ordinamento, prendi i PK della riga sopra e sotto dove è stata spostata la riga corrente, se esistono. (Non avrai una riga sopra se sposti l'oggetto nella prima posizione, per esempio)
  3. Pubblica i PK della riga corrente, precedente e successiva sul server per eseguire l'ordinamento.
  4. Se hai una fila precedente, imposta la posizione della riga corrente su prev + 0.5. Se ne hai solo uno successivo, imposta la posizione della riga corrente sul prossimo - 0.5.
  5. Successivamente ho un proc di Stored che aggiorna tutte le posizioni usando la funzione Row_Number di SQL Server, ordinando secondo il nuovo ordinamento. Questo trasformerà l'ordine da 1,1,5,2,3,4,6 a 1,2,3,4,5,6, poiché la funzione row_number ti fornisce numeri interi.

Quindi si finisce con un ordine intero senza spazi vuoti, memorizzato in una colonna decimale. È abbastanza pulito, mi sento. Ma potrebbe non scalare molto bene una volta che hai centinaia di migliaia di file che devi aggiornare, tutto in una volta. Ma se lo fai, perché stai usando un ordinamento definito dall'utente in primo luogo? (Nota: se hai una grande tabella con milioni di utenti, ma ogni utente ha solo poche centinaia di elementi da ordinare, puoi usare l'approccio di sopra bene dato che comunque utilizzerai una clausola where per limitare le modifiche a un solo utente )

    
risposta data 06.09.2016 - 18:59
fonte