Struktura danych do przechowywania pola sortowania w celu wydajnego wprowadzania modyfikacji

Question

Używam Django i PostgreSQL, ale nie jestem absolutnie związany z ORM Django, jeśli jest lepszy sposób na zrobienie tego z surowymi operacjami SQL lub bazami danych.

Mam model, który wymaga porządkowania sekwencyjnego. Operacje wyszukiwania będą zazwyczaj pobierać całą listę w kolejności. Najczęstszym operacji na tych danych jest, aby przenieść wiersz do końca listy, z podzbioru interweniujących elementów propagacji się zastąpić poprzedni element takiego:

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

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

Notice how D does not move. 

w ogóle, podzbiór przedmiotów nie będzie więcej niż około 50 pozycji, ale lista podstawowa może wzrosnąć do dziesiątków tysięcy wpisów.

Najbardziej oczywistym sposobem realizacji tego jest użycie prostego pola liczby całkowitej. Wydaje się to nieoptymalne. Wymaga kompromisu polegającego na tym, że kolumna zamawiania pozycji jest nieunikalna, gdzie nieunikalność jest wymagana tylko podczas trwania operacji modyfikacji. Aby to zobaczyć, wyobrazić sobie pracę przy użyciu minimalnej z podzbioru B:

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

Chociaż już zapisany pozycję, w drugiej linii masz naruszył unikatowości. Dodatkowo, ta metoda powoduje, że atomowość jest problematyczna - twoja operacja odczytu musi nastąpić przed napisaniem, podczas której twoje zapisy mogą się zmienić. Domyślna dokumentacja obsługi transakcji Django nie rozwiązuje tego problemu, chociaż wiem, że powinna być możliwa w SQL przy użyciu poziomu blokowania transakcji "REPEATABLE READ".

Poszukuję alternatywnych struktur danych, które będą bardziej pasować do tego wzoru użycia. Przyjrzałem się pomysłom na this question.

Jedną z propozycji nie jest Dewey rozwiązanie styl dziesiętny, który sprawia, że ​​operacje wstawiania wystąpić numerycznie między istniejącymi wartościami, więc wkładając między B i C powoduje:

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

rozwiązuje ten kolumnie wyjątkowość problemu, ale wprowadza problem polegający na tym, że kolumna musi być zmienną o określonej liczbie miejsc po przecinku. Albo przeszacowuję i przechowuję więcej danych, niż potrzebuję, albo system staje się ograniczony przez dowolną dziesiętną długość, którą narzucam. Ponadto nie spodziewam się, że użycie będzie równomierne w stosunku do bazy danych - niektóre klucze będą przenoszone znacznie częściej niż inne, dzięki czemu rozwiązanie to szybciej osiągnie granicę. Mógłbym rozwiązać ten problem, okresowo zmieniając numerację bazy danych, ale wydaje się, że dobra struktura danych powinna tego uniknąć.

Inną strukturą, którą rozważałem, jest połączona lista (i warianty). Ma to tę zaletę, że czyni modyfikację prostą, ale nie jestem pewien jej właściwości w odniesieniu do SQL - porządkowanie takiej listy w zapytaniu SQL wydaje się być bolesne, a wyodrębnianie niesekwencyjnego podzbioru listy jest okropne właściwości pobierania.

Poza tym są B-drzewa, różne drzewa binarne i tak dalej. Co zalecamy dla tej struktury danych? Czy istnieje standardowa struktura danych dla tego rozwiązania w SQL? Czy początkowy pomysł na sekwencyjne liczby całkowite rzeczywiście będzie miał problemy ze skalowaniem, czy też widzę problemy tam, gdzie ich nie ma?

Answer 1

Zalecany rozwiązania:

linked list byłby zwykły sposób, aby osiągnąć ten cel. Zapytanie, które zwraca te elementy w kolejności, to trivial in Oracle, ale nie jestem pewien, jak by to zrobić w PostreSQL.

Innym rozwiązaniem byłoby zaimplementować to za pomocą ltree module for postgresql.

Mniej wdzięku (i pisać ciężki) rozwiązanie: transakcję Start. "wybierz do aktualizacji" w zakresie blokad na poziomie wiersza. Przenieś rekord docelowy do pozycji 0, zaktualizuj docelowe przyszłe rekordy do +1, gdzie ich pozycja jest wyższa niż pierwotna pozycja celu (lub odwrotnie), a następnie zaktualizuj cel do nowej pozycji - dodatkowy dodatkowy zapis wymagany bez wyjątkowe ograniczenie.Popełnić: D

Simple (jeszcze ciągle pisać ciężki) rozwiązanie, jeśli można poczekać PostgreSQL 8.5 (alfa jest dostępny) :)

owinąć go w transakcji, wybierz dla aktualizacji zakresu i stosowanie odroczone ograniczenie (postgresql 8.5 has support for deferred unique constraints podobnie jak Oracle).

Answer 2

Wydaje mi się, że Twoim prawdziwym problemem jest konieczność zablokowania tabeli na czas trwania transakcji. Nie widzę od razu dobrego rozwiązania tego problemu w pojedynczej operacji, stąd potrzeba blokowania.

Pytanie więc, czy można to zrobić w "sposób Django" w przeciwieństwie do prostego kodu SQL.Szukając "tabeli blokowania django" pojawiły się interesujące linki, w tym this snippet, jest wiele innych, które implementują podobne zachowanie.

Proste rozwiązanie w postaci listy połączonych list SQL można znaleźć w tym stack overflow post, wydawało mi się logiczne i zwięzłe, ale znowu to dwie operacje.

Jestem bardzo ciekawa, jak to się skończyło i jakie jest twoje ostateczne rozwiązanie, pamiętaj, abyśmy byli na bieżąco!

Answer 3

Możesz rozwiązać problem zmiany numeracji, wykonując kolumnę zamówienia jako liczbę całkowitą, która jest zawsze liczbą parzystą. Podczas przenoszenia danych, pole kolejności zmienić na nową wartość sortowania + 1, a następnie zrobić szybką aktualizację, aby przekształcić wszystkie nieparzyste pola rzędu nawet:

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

ten sposób można zachować wyjątkowość porządek_sortowania jako ograniczenie

EDYCJA: Okay, ponownie patrząc na pytanie, zacząłem nową odpowiedź.

Answer 4

Dlaczego nie zrobić proste pole znakowe o pewnej długości, na przykład maksymalnie 16 (lub 255) początkowo.

Zacznij od oznaczania rzeczy od aaa przez zzz (powinno być 17576 wpisów). (Można również dodać 0-9 oraz wielkie litery i symbole do optymalizacji.)

Po dodaniu pozycji mogą one przejść do końca, aż do maksymalnego dopuszczalnego czasu dodatkowego "(zzza, zzzaa, zzzaaa, zzzaab, zzzaac, zzzaad, itp.)

Powinno to być rozsądnie proste do zaprogramowania i bardzo podobne do systemu dziesiętnego Deweya.

Tak, trzeba będzie zrównoważyć to od czasu do czasu, ale to powinna być prosta operacja. Najprostszym podejściem są dwa podania, przejście 1 oznacza ustawienie nowego znacznika porządkującego na "0" (lub dowolny znak wcześniejszy niż pierwszy znak), a następnie nowy znacznik o odpowiedniej długości, a krok 2 oznaczałby usunięcie " 0 z przodu.

Podobno można zrobić to samo z pływakami i przywracać je regularnie, jest to tylko wariacja. Jedyną zaletą jest to, że większość baz danych pozwoli ci ustawić absurdalnie duży maksymalny rozmiar pola postaci, wystarczająco duży, aby uczynić go bardzo, bardzo, bardzo mało prawdopodobnym, że skończyłoby Ci się cyfry, by zrobić zamawianie, a także uczynić go mało prawdopodobnym że kiedykolwiek będziesz musiał zmodyfikować schemat, nie marnując dużo miejsca.

Answer 5

Tabela tymczasowa i transakcja powinny zachować atomowość i unikalne ograniczenie w porządku sortowania. Wracając do problemu, chcesz przejść od:

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

Gdzie między każdym rzędem może znajdować się dowolna liczba elementów. Najpierw czytaj w zapisach i stwórz listę: [['A',10],['B',25],['C',26],['E',34]]. Przez jakiś pythonic magii zmieniasz identyfikatory wokół i wstawić je do tabeli temp:

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

Teraz po aktualizacji:

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

Ja tylko zakładając pgsql może obsłużyć tego zapytania. Jeśli to możliwe, będzie atomowa.

Opcjonalnie utwórz tabelę REORDER jako stałą tabelę, a transakcja zapewni, że próby ponownego uporządkowania tego samego rekordu dwa razy będą serializowane.

---

EDYCJA: Istnieją pewne problemy z transakcjami. Być może będziesz musiał wdrożyć oba moje pomysły. Jeśli dwa procesy chcą zaktualizować element B (na przykład), mogą wystąpić problemy. Więc przyjmijmy, że wszystkie wartości rzędu są jeszcze:

1. rozpocząć transakcji
2. Increment wszystkie zlecenia są wykorzystywane przez 1. To stawia rząd poziomu blokady zapisu na wszystkich wierszy masz zamiar zaktualizować.
3. Wybierz właśnie zaktualizowane dane, jeśli jakiekolwiek pola sort_order są nawet jakimś innym procesem dodawały rekord, który pasuje do twoich kryteriów. Możesz albo przerwać transakcję i zrestartować, albo możesz po prostu upuścić rekord i zakończyć operację, używając tylko tych rekordów, które zostały zaktualizowane w kroku 2. "Właściwa" czynność zależy od tego, czego potrzebujesz do wykonania tego kodu.
4. Wypełnij tymczasową tabelę zmian w sposób opisany powyżej, używając prawidłowych, równych danych sort_orders.
5. Zaktualizuj główną tabelę jak powyżej.
6. Upuść tabelę tymczasową.
7. zatwierdzania transakcji

Krok 2 zapewnia, że ​​jeśli dwie listy zachodzą na siebie, tylko pierwszy z nich będzie miał dostęp do wiersza w pytaniu dopóki transakcja uzupełnia:

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 

Alternatywnie, można dodaj pole kontrolne do tabeli, aby uzyskać ten sam efekt, a następnie nie musisz grać z polem sort_order. Zaletą korzystania z pola sort_order jest indeksowanie za pomocą pola BIT lub pola LOCK_BY_USERID, gdy pole ma zwykle zerową tendencję do słabej wydajności, ponieważ wskaźnik 99% czasu jest bez znaczenia. Silniki SQL nie lubią indeksów, które większość czasu spędzają puste.