Przechowywanie listy do ponownego zamówienia w bazie danych

54

Pracuję nad systemem list życzeń, w którym użytkownicy mogą dodawać elementy do różnych list życzeń, i zamierzam umożliwić użytkownikom ponowne zamówienie elementów w późniejszym terminie. Nie jestem do końca pewien, jak najlepiej przechować to w bazie danych, jednocześnie zachowując szybkość i nie zmieniając się w bałagan (ta aplikacja będzie używana przez dość dużą bazę użytkowników, więc nie chcę, aby spadła do czyszczenia rzeczy).

Początkowo próbowałem positionkolumny, ale wydaje się, że byłoby dość nieefektywne zmienianie wartości pozycji każdego innego elementu podczas przenoszenia.

Widziałem ludzi używających odsyłaczy do odniesienia do poprzedniej (lub następnej) wartości, ale znowu wydaje się, że musiałbyś zaktualizować całą masę innych pozycji na liście.

Innym rozwiązaniem, które widziałem, jest używanie liczb dziesiętnych i po prostu umieszczanie przedmiotów w przerwach między nimi, co wydaje się najlepszym rozwiązaniem do tej pory, ale jestem pewien, że musi być lepszy sposób.

Powiedziałbym, że typowa lista zawierałaby do około 20 przedmiotów i prawdopodobnie ograniczę ją do 50. Zmiana kolejności będzie polegała na przeciąganiu i upuszczaniu i prawdopodobnie zostanie wykonana partiami, aby zapobiec warunkom wyścigowym i tym podobne z żądania ajax. Używam postgres (na heroku), jeśli to ma znaczenie.

Czy ktoś ma jakieś pomysły?

Pozdrawiam za wszelką pomoc!

Tom Brunoli
źródło
Czy możesz zrobić trochę benchmarkingu i powiedzieć nam, czy IO czy baza danych będą wąskim gardłem?
rwong
Podobne pytanie dotyczące stackoverflow .
Jordão
Z odniesieniem do siebie, przenosząc element z jednego miejsca na liście do drugiego, musisz zaktualizować tylko 2 elementy. Zobacz en.wikipedia.org/wiki/Linked_list
Pieter B
Hmm, nie jestem pewien, dlaczego listy połączone nie przyciągają uwagi w odpowiedziach.
Christiaan Westerbeek

Odpowiedzi:

32

Po pierwsze, nie próbuj robić niczego sprytnego z liczbami dziesiętnymi, ponieważ będą cię na złość. REALi DOUBLE PRECISIONsą niedokładne i mogą niepoprawnie przedstawiać to, co w nich wkładasz. NUMERICjest dokładne, ale właściwa sekwencja ruchów zabraknie ci precyzji, a twoja implementacja źle się zepsuje.

Ograniczenie ruchów do pojedynczych wzlotów i upadków sprawia, że ​​cała operacja jest bardzo łatwa. Aby uzyskać listę kolejno ponumerowanych elementów, możesz przesunąć element w górę, zmniejszając jego pozycję i zwiększając numer pozycji niezależnie od tego, co wymyślił poprzedni dekrement. (Innymi słowy, poz 5stanie 4i jaki był przedmiot 4staje się 5skutecznie swap jak kretyni opisano w swojej odpowiedzi.) Przesuwając go byłoby odwrotnie. Indeksuj swoją tabelę według tego, co jednoznacznie identyfikuje listę i pozycję, i możesz to zrobić za pomocą dwóch UPDATEsekund w transakcji, która będzie przebiegać bardzo szybko. Chyba że użytkownicy zmieniają swoje listy z nadludzkimi prędkościami, nie spowoduje to dużego obciążenia.

Ruchy metodą „przeciągnij i upuść” (np. Przesuń element, 6aby usiąść między elementami 9i 10) są nieco trudniejsze i muszą być wykonane inaczej w zależności od tego, czy nowa pozycja znajduje się powyżej czy poniżej starej. W powyższym przykładzie musisz otworzyć dziurę, zwiększając wszystkie pozycje większe niż 9, aktualizując pozycję przedmiotu 6, aby była nowa, 10a następnie zmniejszając pozycję wszystkiego większego niż, 6aby wypełnić puste miejsce. Przy takim samym indeksowaniu, jak opisałem wcześniej, będzie to szybkie. Możesz faktycznie sprawić, że pójdzie to trochę szybciej niż to opisałem, minimalizując liczbę wierszy, które dotyka transakcja, ale jest to mikrooptymalizacja, której nie potrzebujesz, dopóki nie udowodnisz, że istnieje wąskie gardło.

Tak czy inaczej, próba prześcignięcia bazy danych za pomocą domowego, zbyt sprytnego rozwiązania na pół nie zwykle kończy się sukcesem. Bazy danych warte swojej soli zostały starannie napisane, aby wykonywać te operacje bardzo, bardzo szybko przez ludzi, którzy są w tym bardzo, bardzo dobrzy.

Blrfl
źródło
Dokładnie tak sobie z tym poradziłem w systemie przygotowywania ofert, który mieliśmy przed milionami lat. Nawet w programie Access aktualizacja była szybko podzielona podobnie.
HLGEM
Dzięki za wyjaśnienie, Blrfl! Próbowałem wykonać tę drugą opcję, ale odkryłem, że jeśli usunę elementy ze środka listy, pozostaną luki na pozycjach (było to dość naiwne wdrożenie). Czy istnieje prosty sposób na uniknięcie tworzenia takich luk, czy też musiałbym to robić ręcznie za każdym razem, gdy coś ponownie zamawiam (jeśli w ogóle muszę to zarządzać)?
Tom Brunoli
2
@TomBrunoli: Musiałbym trochę pomyśleć o implementacji, zanim na pewno to powie, ale możesz być w stanie przeprowadzić większość lub całość automatycznej numeracji za pomocą wyzwalaczy. Na przykład, jeśli usuniesz element 7, wyzwalacz zmniejsza wszystkie wiersze na tej samej liście o numerze większym niż 7 po zakończeniu usuwania. Inserty zrobiłyby to samo (wstawienie elementu 7 zwiększyłoby wszystkie wiersze 7 lub wyższe). Wyzwalacz aktualizacji (np. Przesuń element 3 między 9 a 10) byłby umiarkowanie bardziej złożony, ale z pewnością mieści się w zakresie wykonalności.
Blrfl 19.04.13
Wcześniej nie szukałem wyzwalaczy, ale wydaje się to dobrym sposobem na zrobienie tego.
Tom Brunoli,
1
@TomBrunoli: Przyszło mi do głowy, że użycie do tego celu wyzwalaczy może powodować kaskady. Procedury składowane ze wszystkimi zmianami w transakcji mogą być lepszą drogą do tego.
Blrfl
15

Ta sama odpowiedź tutaj https://stackoverflow.com/a/49956113/10608


Rozwiązanie: zrób indexłańcuch (ponieważ w zasadzie łańcuchy mają nieskończoną „dowolną precyzję”). Lub jeśli używasz int, zwiększaj indexo 100 zamiast 1.

Problem z wydajnością jest następujący: między dwoma posortowanymi elementami nie ma „pośrednich” wartości.

item      index
-----------------
gizmo     1
              <<------ Oh no! no room between 1 and 2.
                       This requires incrementing _every_ item after it
gadget    2
gear      3
toolkit   4
box       5

Zamiast tego zrób tak (lepsze rozwiązanie poniżej):

item      index
-----------------
gizmo     100
              <<------ Sweet :). I can re-order 99 (!) items here
                       without having to change anything else
gadget    200
gear      300
toolkit   400
box       500

Jeszcze lepiej: oto jak Jira rozwiązuje ten problem. Ich „ranga” (tak zwany indeks) jest wartością ciągu, która pozwala tonie oddychać pomiędzy pozycjonowanymi pozycjami.

Oto prawdziwy przykład bazy danych Jira, z którą pracuję

   id    | jira_rank
---------+------------
 AP-2405 | 0|hzztxk:
 ES-213  | 0|hzztxs:
 AP-2660 | 0|hzztzc:
 AP-2688 | 0|hzztzk:
 AP-2643 | 0|hzztzs:
 AP-2208 | 0|hzztzw:
 AP-2700 | 0|hzztzy:
 AP-2702 | 0|hzztzz:
 AP-2411 | 0|hzztzz:i
 AP-2440 | 0|hzztzz:r

Zwróć uwagę na ten przykład hzztzz:i. Zaletą rangi sznurkowej jest to, że zabraknie miejsca między dwoma przedmiotami, nadal nie musisz zmieniać rangi niczego innego. Po prostu zacznij dodawać więcej znaków do ciągu, aby zawęzić fokus.

Alexander Bird
źródło
1
Próbowałem wymyślić jakiś sposób, aby to zrobić, aktualizując tylko jeden rekord, a ta odpowiedź wyjaśnia bardzo dobrze rozwiązanie, o którym myślałem.
NSjonas
13

Widziałem ludzi używających odsyłaczy do odniesienia do poprzedniej (lub następnej) wartości, ale znowu wydaje się, że musiałbyś zaktualizować całą masę innych pozycji na liście.

Dlaczego? Załóżmy, że stosujesz podejście do tabeli z listami połączonymi z kolumnami (listID, itemID, nextItemID).

Wstawienie nowego elementu do listy kosztuje jedną wstawkę i jeden zmodyfikowany wiersz.

Zmiana położenia przedmiotu kosztuje trzy modyfikacje wiersza (przenoszony element, element przed nim i element przed nową lokalizacją).

Usunięcie elementu kosztuje jedno usunięcie i jeden zmodyfikowany wiersz.

Koszty te pozostają takie same, niezależnie od tego, czy lista zawiera 10 pozycji, czy 10 000 pozycji. We wszystkich trzech przypadkach modyfikacja jest mniejsza, jeśli wiersz docelowy jest pierwszym elementem listy. Jeśli częściej operujesz na ostatnim elemencie listy, może być korzystne zapisanie prevItemID zamiast następnego.

sqweek
źródło
10

„ale wydaje się, że byłoby to dość nieefektywne”

Czy mierzyć to? Czy to tylko zgadywanie? Nie rób takich założeń bez żadnego dowodu.

„20 do 50 pozycji na liście”

Szczerze mówiąc, to nie jest „dużo przedmiotów”, dla mnie to brzmi bardzo mało.

Proponuję trzymać się zasady „kolumny pozycji” (jeśli jest to najprostsza implementacja dla Ciebie). W przypadku tak małych list nie zaczynaj niepotrzebnej optymalizacji przed wystąpieniem prawdziwych problemów z wydajnością

Doktor Brown
źródło
6

To jest naprawdę kwestia skali i przypadku użycia ..

Ile oczekujesz pozycji na liście? Jeśli miliony, myślę, że gong dziesiętna trasa jest oczywista.

Jeśli 6, to numeracja liczb całkowitych jest oczywistym wyborem. s Również pytania dotyczą tego, w jaki sposób listy zostały uporządkowane. Jeśli używasz strzałek w górę i w dół (poruszanie się w górę lub w dół o jedno miejsce na raz), i użyłbym liczb całkowitych, a następnie zamieniłem się z poprzednim (lub następnym) w ruchu.

Jak często dokonujesz zmian, jeśli użytkownik może wprowadzić 250 zmian, to zatwierdzaj naraz, niż mówię liczby całkowite z ponowną numeracją ...

tl; dr: Potrzebujesz więcej informacji.


Edycja: „Listy życzeń” brzmią jak wiele małych list (założenie, że to może być fałsz). Więc mówię Integer z numeracją. (Każda lista zawiera własną pozycję)

Kretynowie
źródło
Zaktualizuję pytanie o nieco więcej kontekstu
Tom Brunoli,
ułamki dziesiętne nie działają, ponieważ precyzja jest ograniczona, a każdy wstawiony element może zająć 1 bit
njzk2
3

Jeśli celem jest zminimalizowanie liczby operacji bazy danych na operację zmiany kolejności:

Przy założeniu, że

  • Wszystkie elementy zakupów można wyliczyć za pomocą 32-bitowych liczb całkowitych.
  • Istnieje limit maksymalnego rozmiaru listy życzeń użytkownika. (Widziałem, że niektóre popularne witryny wykorzystują 20–40 pozycji jako limit)

Przechowuj posortowaną listę życzeń użytkownika jako spakowaną sekwencję liczb całkowitych (tablic liczb całkowitych) w jednej kolumnie. Za każdym razem, gdy lista życzeń jest zmieniana, cała tablica (pojedynczy wiersz; pojedyncza kolumna) jest aktualizowana - co należy wykonać za pomocą pojedynczej aktualizacji SQL.

https://www.postgresql.org/docs/current/static/arrays.html


Jeśli cel jest inny, trzymaj się podejścia „kolumna pozycji”.


Jeśli chodzi o „szybkość”, należy przeprowadzić analizę porównawczą podejścia do procedury składowanej. Chociaż wydawanie ponad 20 oddzielnych aktualizacji dla jednego losowego losowania listy życzeń może być powolne, może być szybki sposób przy użyciu procedury składowanej.

rwong
źródło
3

OK. Ostatnio mam do czynienia z tym trudnym problemem, a wszystkie odpowiedzi w tym poście zadały wiele inspiracji. Z mojego punktu widzenia każde rozwiązanie ma swoje zalety i wady.

  • Jeśli positionpole musi być sekwencyjne bez luk, wtedy w zasadzie będziesz musiał ponownie uporządkować całą listę. Jest to operacja O (N). Zaletą jest to, że po stronie klienta nie potrzeba żadnej specjalnej logiki, aby uzyskać zamówienie.

  • Jeśli chcemy uniknąć operacji O (N), ALE JESZCZE utrzymujemy dokładną sekwencję, jednym z podejść jest użycie „odniesienia do siebie w odniesieniu do poprzedniej (lub następnej) wartości”. To jest scenariusz z listą powiązaną z podręcznikiem. Z założenia NIE spowoduje to „wielu innych pozycji na liście”. Wymaga to jednak po stronie klienta (usługi sieciowej lub aplikacji mobilnej) wdrożenia logiki przejścia listy powiązanej w celu uzyskania kolejności.

  • Niektóre warianty nie wykorzystują odniesienia, tj. Listy połączonej. Wybierają reprezentowanie całego porządku jako samodzielnego obiektu blob, takiego jak tablica JSON w ciągu [5,2,1,3,...]; taka kolejność będzie następnie przechowywana w oddzielnym miejscu. Takie podejście ma również efekt uboczny polegający na wymaganiu od strony klienta kodu utrzymania tego oddzielnego obiektu blob zamówienia.

  • W wielu przypadkach tak naprawdę nie musimy przechowywać dokładnej kolejności, musimy jedynie utrzymać względną pozycję w każdym rejestrze. Dlatego możemy dopuścić luki między kolejnymi rekordami. Odmiany obejmują: (1) użycie liczb całkowitych z lukami, takimi jak 100, 200, 300 ... ale szybko zabraknie braków, a następnie będziesz potrzebować procesu odzyskiwania; (2) przy użyciu liczb dziesiętnych z naturalnymi lukami, ale musisz zdecydować, czy możesz żyć z ewentualnym ograniczeniem precyzji; (3) używając rangi opartej na łańcuchach, jak opisano w tej odpowiedzi, ale uważaj na trudne pułapki implementacyjne .

  • Prawdziwa odpowiedź może brzmieć „to zależy”. Ponownie sprawdź wymagania biznesowe. Na przykład, jeśli jest to system z listą życzeń, osobiście chętnie skorzystałbym z systemu organizowanego przez zaledwie kilka rang jako „must have”, „good-to-have”, „może-later”, a następnie prezentowałem przedmioty bez szczególnych porządek wewnątrz każdej rangi. Jeśli jest to system dostarczania, możesz bardzo dobrze wykorzystać czas dostawy jako przybliżoną pozycję, która ma naturalną lukę (i naturalne zapobieganie konfliktom, ponieważ żadna dostawa nie nastąpiłaby w tym samym czasie). Twój przebieg może się różnić.

RayLuo
źródło
2

Użyj liczby zmiennoprzecinkowej dla kolumny pozycji.

Następnie możesz zmienić kolejność listy, zmieniając tylko kolumnę pozycji w wierszu „przeniesionym”.

Zasadniczo, jeśli użytkownik chce ustawić „czerwony” po „niebieskim”, ale przed „żółtym”

Musisz po prostu obliczyć

red.position = ((yellow.position - blue.position) / 2) + blue.position

Po kilku milionach zmian pozycji liczby zmiennoprzecinkowe mogą być tak małe, że nie ma „pomiędzy” - ale jest to tak samo prawdopodobne, jak zobaczenie jednorożca.

Możesz to zaimplementować za pomocą pola liczb całkowitych z początkową przerwą, powiedzmy 1000. Tak więc początkowe oreringowanie byłoby 1000-> niebieski, 2000-> Żółty, 3000-> Czerwony. Po „przesunięciu” koloru czerwonego po niebieskim miałbyś 1000-> niebieski, 1500-> czerwony, 2000-> żółty.

Problem polega na tym, że przy pozornie dużej początkowej luce wynoszącej 1000, zaledwie 10 ruchów doprowadzi cię do sytuacji takiej jak 1000-> niebieski, 1001-puce, 1004-> biege ...... gdzie nie będziesz już w stanie wstawić cokolwiek po „niebieskim” bez ponownego numerowania całej listy. Używając liczb zmiennoprzecinkowych, zawsze będzie punkt „w połowie” między dwiema pozycjami.

James Anderson
źródło
4
Indeksowanie i sortowanie w bazie danych opartej na liczbach zmiennoprzecinkowych jest droższe niż ints. Ints są również ładnym typem porządkowym ... nie muszą być wysyłane jako bity, aby można je było sortować na kliencie (różnica między dwiema liczbami, które renderują to samo po wydrukowaniu, ale mają różne wartości bitów).
Ale każdy schemat wykorzystujący ints oznacza, że ​​musisz aktualizować wszystkie / większość wierszy na liście za każdym razem, gdy zmienia się kolejność. Za pomocą liczb zmiennoprzecinkowych aktualizujesz tylko wiersz, który się przesunął. Również „unosi się drożej niż ints” bardzo zależy od implementacji i użytego sprzętu. Z pewnością dodatkowe zaangażowane procesory są nieznaczne w porównaniu z procesorami wymaganymi do aktualizacji wiersza i powiązanych z nim indeksów.
James Anderson
5
Dla naysayers to rozwiązanie jest dokładnie tym, co robi Trello ( trello.com ). Otwórz swój debugger Chrome i zdywersyfikuj dane wyjściowe JSON przed / po zmianie kolejności (przeciągnij / upuść kartę), a otrzymasz - "pos": 1310719, + "pos": 638975.5. Szczerze mówiąc, większość ludzi nie tworzy list trello z 4 milionami wpisów, ale rozmiar i sposób użycia listy Trello jest dość powszechny w przypadku treści, które można sortować. I wszystko, co można sortować przez użytkownika, nie ma w przybliżeniu nic wspólnego z wysoką wydajnością, szybkość sortowania int vs float jest do tego słuszna, szczególnie biorąc pod uwagę, że bazy danych są w większości ograniczone przez wydajność IO.
zelk
1
@PieterB Jeśli chodzi o „dlaczego nie użyć 64-bitowej liczby całkowitej”, powiedziałbym, że jest to głównie ergonomia dla programisty. Dla przeciętnej liczby zmiennoprzecinkowej jest w przybliżeniu tyle samo głębi bitowej <1,0, ile jest> 1,0, więc można domyślnie ustawić kolumnę „pozycja” na 1,0 i wstawić 0,5, 0,25, 0,75 równie łatwo, jak podwojenie. W przypadku liczb całkowitych domyślna wartość to 2 ^ 30, co utrudnia zastanawianie się przy debugowaniu. Czy 4073741824 jest większy niż 496359787? Zacznij liczyć cyfry.
zelk
1
Co więcej, jeśli kiedykolwiek trafisz na przypadek, w którym zabraknie miejsca między liczbami ... nie jest to trudne do naprawienia. Przesuń jeden z nich. Ale ważne jest to, że działa to w najlepszy sposób, który obsługuje wiele jednoczesnych edycji przez różne strony (np. Trello). Możesz podzielić dwie liczby, może nawet posypać trochę losowym hałasem, i voila, nawet jeśli ktoś inny zrobił to samo w tym samym czasie, wciąż istnieje globalne zamówienie i nie trzeba WSTAWIAĆ w transakcji, aby uzyskać tam.
zelk