Zamówienie LINQ. Czy zawsze zwraca tę samą uporządkowaną listę?

Question

Próbowałem wypróbować proste polecenie OrderBy.

Docelowa dane zamówienie jest coś takiego jak poniżej:

[ 
    {"id":40, "description":"aaa", "rate":1}, 
    {"id":1, "description":"bbb", "rate":1}, 
    {"id":4, "description":"ccc", "rate":2}, 
    {"id":19, "description":"aaa", "rate":1} 
] 

Potem zamówić elementy przez właściwość stopy.

Dziwne jest to, że jeśli "zamówię" je, "przeskakuje" niektóre elementy o dane przesunięcie, a następnie "bierze" tylko część danych.

Na przykład

var result = items.OrderBy(i => i.rate); 
var result = result.Skip(2); 
var result = result.Take(2); 

Rezultat wygląda dobrze dla większości z nich, ale „sprawa krawędzi” pozycja nie jest zwracana w ogóle.

Na przykład

jeżeli pierwszy wynik wrócił jako

[{"id":40, "description":"aaa", "rate":1}, {"id":1, "description":"bbb", "rate":1}] 

drugi wynik wraca jak

[{"id":1, "description":"bbb", "rate":1}, {"id":4, "description":"ccc", "rate":2}] 

Element "ID: 19" nie został zwrócony z drugim wywołaniem zapytania. Zamiast tego element "id: 1" powrócił dwukrotnie.

Domyślam się, że instrukcja SQL OrderBy nie generuje tej samej listy zamówień za każdym razem, gdy zamówienia OrderBy dotyczą danej nieruchomości, ale dokładna kolejność w grupie, która ma tę samą właściwość, może ulec zmianie.

Jaki jest dokładny mechanizm pod maską?

Answer 1

Krótka odpowiedź: LINQ to Objects wykorzystuje stabilne algorytm sortowania, więc możemy powiedzieć, że jest deterministyczny i LINQ to SQL zależy od implementacji bazy danych Zamów przez to zwykle niedeterministyczny.

Algorytm sortowania deterministycznego to taki, który ma zawsze takie samo zachowanie na różnych przebiegach.

W twoim przykładzie masz duplikaty w swojej klauzuli OrderBy. W przypadku gwarantowanego i przewidywanego sortowania jedna z klauzul zamówienia lub kombinacja klauzul zamówienia musi być unikalna.

W LINQ można to osiągnąć, dodając kolejną klauzulę OrderBy, aby wskazać unikatową właściwość, np.
items.OrderBy(i => i.Rate).ThenBy(i => i.ID).

Długa odpowiedź:

LINQ to Objects używa stabilnego rodzaju, co zostało udokumentowane w ten link: MSDN.

W LINQ do SQL zależy to od algorytmu sortowania bazowej bazy danych i zazwyczaj jest to niestabilny sortowanie, np. W MS SQL Server (MSDN).

W sortowaniu stabilnym, jeśli klucze dwóch elementów są równe, kolejność elementów zostaje zachowana.W przeciwieństwie do tego, niestabilny sort nie zachowuje porządku elementów, które mają ten sam klucz.

Więc dla LINQ to SQL, sortowanie jest zwykle niedeterministyczny ponieważ (system zarządzania bazami danych relacyjne, jak MS SQL Server) RDMS może bezpośrednio użyć algorytmu sortowania niestabilnego z losowego doboru obrotu lub losowość może być związana z tym wierszem, w którym baza danych uzyskuje dostęp do pierwszego w systemie plików.

Na przykład wyobraź sobie, że rozmiar strony w systemie plików może wynosić maksymalnie 4 wiersze.

strona będzie pełna, jeśli wstawić następujące dane:

 Page 1 
| Name | Value | 
|------|-------| 
| A | 1 | 
| B | 2 | 
| C | 3 | 
| D | 4 | 

Jeśli trzeba wstawić nowy wiersz, RDMS posiada dwie opcje:

1. utworzyć nową stronę przydzielić nowy wiersz.
2. Podziel bieżącą stronę na dwie strony. Tak więc pierwsza strona będzie trzymać Nazwy i B a druga strona będzie posiadać C i D.

Załóżmy, że RDMS wybiera opcję 1 (w celu zmniejszenia fragmentacji indeksu). Jeśli wstawić nowy wiersz z nazwy C i warto , dostaniesz:

 Page 1    Page 2 
| Name | Value | | Name | Value | 
|------|-------| |------|-------| 
| A | 1 | | C | 9 | 
| B | 2 | |  |  | 
| C | 3 | |  |  | 
| D | 4 | |  |  | 

Prawdopodobnie klauzula OrderBy w kolumnie Nazwa powróci następujące:

| Name | Value | 
|------|-------| 
| A | 1 | 
| B | 2 | 
| C | 3 | 
| C | 9 | -- Value 9 appears after because it was at another page 
| D | 4 | 

Teraz załóżmy, że RDMS wybiera opcję 2 (w celu zwiększenia wydajności wkładki w systemie pamięci masowej z wieloma wrzecionami). Jeśli wstawić nowy wiersz z nazwy C i warto , dostaniesz:

 Page 1    Page 2 
| Name | Value | | Name | Value | 
|------|-------| |------|-------| 
| A | 1 | | C | 3 | 
| B | 2 | | D | 4 | 
| C | 9 | |  |  | 
|  |  | |  |  | 

Prawdopodobnie klauzula OrderBy w kolumnie Nazwa powróci następujące:

| Name | Value | 
|------|-------| 
| A | 1 | 
| B | 2 | 
| C | 9 | -- Value 9 appears before because it was at the first page 
| C | 3 | 
| D | 4 | 

Odnosząc się do twojego przykładu:

Uważam, że błędnie wpisałeś coś w swoim pytaniu, ponieważ użyłeś items.OrderBy(i => i.rate).Skip(2).Take(2);, a pierwszy wynik nie pokazuje wiersza z Rate = 2.Nie jest to możliwe, ponieważ Skip zignoruje pierwsze dwa wiersze i ma wartość Rate = 1, więc wynik musi zawierać wiersz z Rate = 2.

Oznaczyłeś swoje pytanie na database, więc uważam, że używasz LINQ do SQL. W tym przypadku wyniki mogą być niedeterministyczny i można uzyskać następujące:

Wynik 1:

[{"id":40, "description":"aaa", "rate":1}, 
{"id":4, "description":"ccc", "rate":2}] 

Wynik 2:

[{"id":1, "description":"bbb", "rate":1}, 
{"id":4, "description":"ccc", "rate":2}] 

Jeśli użył items.OrderBy(i => i.rate).ThenBy(i => i.ID).Skip(2).Take(2); wówczas jedynym możliwym wynikiem będzie być:

[{"id":40, "description":"aaa", "rate":1}, 
{"id":4, "description":"ccc", "rate":2}]