Struttura dati per la memorizzazione di un campo di ordinamento per consentire modifiche efficienti

Question

Uso Django e PostgreSQL, ma non sono assolutamente legato all'ORM Django se esiste un modo migliore per farlo con operazioni SQL o database specifiche.

Ho un modello che richiede un ordinamento sequenziale. Le operazioni di ricerca in genere recuperano l'intero elenco in ordine. L'operazione più comune su questi dati è quello di spostare una riga alla fine di un elenco, con un sottoinsieme degli elementi intermedi gorgogliare in sostituzione di quello precedente in questo modo:

 
(operation on A, with subset B, C, E) 

A -> B 
B -> C 
C -> E 
D -> D 
E -> A 

Notice how D does not move. 

In generale, il sottoinsieme di articoli non saranno più di circa 50 voci, ma l'elenco di base potrebbe crescere fino a decine di migliaia di voci.

Il modo più ovvio di implementare questo è con un campo di ordine intero semplice. Questo sembra non ottimale. Richiede il compromesso di rendere la colonna degli ordini di posizione non univoca, laddove la non unicità è richiesta solo per la durata di un'operazione di modifica. Per vedere questo, immaginare l'operazione minima utilizzando A con sottoinsieme B:

oldpos = B.pos 
B.pos = A.pos 
A.pos = oldpos 

Anche se hai memorizzato la posizione, in seconda linea che hai violato il vincolo di unicità. Inoltre, questo metodo rende problematica l'atomicità: l'operazione di lettura deve essere eseguita prima della scrittura, durante la quale i record potrebbero cambiare. La documentazione di default per la gestione delle transazioni di Django non risolve questo problema, anche se so che dovrebbe essere possibile in SQL usando il livello "REPEATABLE READ" del blocco delle transazioni.

Sto cercando strutture di dati alternative che si adattino meglio a questo schema di utilizzo. Ho esaminato lo this question per le idee.

Una proposta v'è la soluzione stile decimale Dewey, che rende le operazioni di inserimento verificano numericamente tra valori esistenti, quindi inserendo A tra B e C risultati in:

 
A=1 -> B=2 
B=2 -> A=2.5 
C=3 -> C=3 

Questo risolve colonna problema unicità, ma introduce il problema che la colonna deve essere un float di un numero specificato di decimali. O sovrastimolo e immagazzino più dati di quanti ne abbia bisogno, oppure il sistema diventa limitato dalla lunghezza decimale arbitraria che impongo. Inoltre, non mi aspetto che l'uso sia anche oltre il database: alcune chiavi verranno spostate molto più spesso di altre, rendendo questa soluzione il più presto possibile. Potrei risolvere questo problema periodicamente ri-numerando il database, ma sembra che una buona struttura dati dovrebbe evitare di averne bisogno.

Un'altra struttura che ho considerato è la lista collegata (e le varianti). Questo ha il vantaggio di rendere le modifiche semplici, ma non sono sicuro delle sue proprietà rispetto a SQL - ordinare un elenco di questo tipo nella query SQL sembra come sarebbe doloroso, e l'estrazione di un sottoinsieme non sequenziale della lista ha terribili proprietà di recupero.

Oltre questo, ci sono alberi B, vari alberi binari e così via. Cosa consiglia per questa struttura dati? Esiste una struttura dati standard per questa soluzione in SQL? L'idea iniziale di andare con interi sequenziali avrà davvero problemi di ridimensionamento, o vedrò problemi dove non ce ne sono?

Answer 1

soluzioni preferita:

Un linked list sarebbe il solito modo per raggiungere questo obiettivo. Una query per restituire gli articoli in ordine è trivial in Oracle, ma non sono sicuro di come lo faresti in PostreSQL.

Un'altra opzione sarebbe quella di implementare questo utilizzando il ltree module for postgresql.

meno aggraziati (e scrivere-pesante) Soluzione: transazione Start. "seleziona per aggiornamento" nell'ambito dei blocchi a livello di riga. Sposta il record target in posizione 0, aggiorna i record futuri successivi a +1 dove la loro posizione è superiore alla posizione originale dei bersagli (o viceversa) e quindi aggiorna il target nella nuova posizione - una singola scrittura aggiuntiva rispetto a quella necessaria senza un vincolo unico.Commit: D

soluzione semplice (ma ancora write-pesante) se si può aspettare per PostgreSQL 8.5 (Alpha è disponibile) :)

avvolgerla in una transazione, selezionare per l'aggiornamento nel campo di applicazione, e l'uso un vincolo posticipato (postgresql 8.5 has support for deferred unique constraints come Oracle).

Answer 2

Mi sembra che il tuo vero problema sia la necessità di bloccare una tabella per la durata di una transazione. Non vedo immediatamente un buon modo per risolvere questo problema in una singola operazione, quindi la necessità di bloccare.

Quindi la domanda è se è possibile farlo in un "modo Django" anziché utilizzare l'SQL diretto.Cercando "django lock table" abbiamo trovato alcuni link interessanti, tra cui this snippet, ce ne sono molti altri che implementano un comportamento simile.

Una soluzione di stile elenco lineare SQL collegato è disponibile in questo stack overflow post, mi sembra logico e succinto, ma ancora una volta sono due operazioni.

Sono molto curioso di sapere come si presenta e quale sia la soluzione finale, assicurati di tenerci aggiornati!

Answer 3

È possibile risolvere il problema di rinumerazione eseguendo la colonna dell'ordine come un numero intero sempre uguale. Quando ci si sposta i dati, si modifica il campo per il nuovo valore di ordinamento + 1 e poi fare un rapido aggiornamento per convertire tutti i campi di ordine dispari a pari:

update table set sort_order = bitand(sort_order, '0xFFFFFFFE') 
where sort_order <> bitand(sort_order, '0xFFFFFFFE') 

questo modo è possibile mantenere l'unicità di sort_order come vincolo

MODIFICA: Ok, guardando di nuovo la domanda, ho iniziato una nuova risposta.

Answer 4

Perché non eseguire un campo di caratteri semplice di una certa lunghezza come un massimo di 16 (o 255) inizialmente.

Inizia inizialmente con l'etichettatura cose aaa tramite zzz (che dovrebbe essere 17576 voci). (È inoltre possibile aggiungere 0-9 e le lettere maiuscole e i simboli per un'ottimizzazione.)

All'aggiunta di elementi, possono andare alla fine fino al massimo consentito per gli 'orari finali' aggiuntivi (zzza, zzzaa, zzzaaa, zzzaab, zzzaac, zzzaad, ecc.)

Questo dovrebbe essere abbastanza semplice da programmare ed è molto simile al sistema Dewey Decimal.

Sì, sarà necessario riequilibrarlo occasionalmente, ma dovrebbe essere una semplice operazione. L'approccio più semplice è due passaggi, il passaggio 1 sarebbe quello di impostare il nuovo tag di ordinamento su '0' (o qualsiasi carattere prima del primo carattere) seguito dal nuovo tag della lunghezza appropriata, e il passaggio 2 sarebbe quello di rimuovere il ' 0 dalla parte anteriore.

Ovviamente, si potrebbe fare la stessa cosa con i galleggianti, e riequilibrandolo regolarmente, questa è solo una variazione su questo. L'unico vantaggio è che la maggior parte dei database ti consentirà di impostare una dimensione massima ridicolmente grande per il campo del personaggio, abbastanza grande da rendere molto, molto, molto improbabile che si verrebbero a mancare le cifre per fare l'ordine, e anche renderlo improbabile che avresti mai dovuto modificare lo schema, senza sprecare molto spazio.

Answer 5

Una tabella temporanea e una transazione devono mantenere l'atomicità e il vincolo univoco sull'ordinamento. Riprendendo il problema, vuoi andare da:

A 10 to B 10 
B 25  C 25 
C 26  E 26 
E 34  A 34 

Dove non ci può essere un qualsiasi numero di elementi tra ogni fila. Quindi, prima leggi i record e crea un elenco [['A',10],['B',25],['C',26],['E',34]]. Attraverso qualche magia divinatorio si sposta gli identificatori intorno ed inserire in una tabella temporanea:

create temporary table reorder (
    id varchar(20), -- whatever 
    sort_order number, 
    primary key (id)); 

Ora per l'aggiornamento:

update table XYZ 
set sort_order = (select sort_order from reorder where xyz.id = reorder.id) 
where id in (select id from reorder) 

sto solo supponendo pgsql in grado di gestire quella query. Se può, sarà atomico.

Se lo si desidera, creare la tabella REORDER come tabella permanente e la transazione assicurerà che i tentativi di riordinare lo stesso record due volte verranno serializzati.

---

MODIFICA: ci sono alcuni problemi di transazione. Potrebbe essere necessario implementare entrambe le mie idee. Se due processi vogliono entrambi aggiornare l'elemento B (per esempio), ci possono essere problemi. Quindi, assumere tutti i valori di ordine sono anche:

1. iniziare la transazione
2. Incremento tutti gli ordini in uso da 1. Questo mette livello di riga blocchi di scrittura su tutte le righe che si sta per aggiornare.
3. Selezionare i dati appena aggiornati, se qualche campo sort_order è anche qualche altro processo ha aggiunto un record che corrisponde ai criteri. È possibile interrompere la transazione e riavviare oppure è possibile rilasciare il record e completare l'operazione utilizzando solo i record che sono stati aggiornati nel passaggio 2. La cosa "giusta" da eseguire dipende da ciò che è necessario eseguire questo codice.
4. Riempi la tabella di riordino temporanea come sopra utilizzando gli ordinamenti di ordinamento pari pari.
5. Aggiorna la tabella principale come sopra.
6. Eliminare la tabella temporanea.
7. commit della transazione

Fase 2 assicura che se due liste si sovrappongono, solo il primo avrà accesso alla fila in questione fino al completamento della transazione:

update XYZ set sort_order = sort_order + 1 
where -- whatever your select criteria are 

select * from XYZ 
where -- same select criteria 
order by sort_order 

In alternativa, è possibile aggiungi un campo di controllo alla tabella per ottenere lo stesso effetto e quindi non è necessario giocare con il campo sort_order. Il vantaggio dell'uso del campo sort_order è indicizzato da un campo BIT o da un campo LOCK_BY_USERID quando il campo è solitamente nullo e tende a presentare scarse prestazioni poiché l'indice 99% delle volte non ha senso. Ai motori SQL non piacciono gli indici che trascorrono la maggior parte del tempo a vuoto.