LINQ OrderBy. Всегда ли он возвращает тот же упорядоченный список?

Question

Я пробовал простую инструкцию OrderBy.

Цель данных на заказ является то, что, как показано ниже:

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

Тогда я заказываю детали собственности скорости.

Странно, что если я их «закажу», он «пропускает» некоторые элементы по заданному смещению, а затем «берет» только часть данных.

Например,

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

Результат выглядит отлично подходит для большинства это, но «крайний случай» элемент не возвращается вообще.

Например,

если первый результат вернулся в

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

второй результат возвращается как

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

Item "ID: 19" не был возвращен со вторым запросом. Вместо этого элемент «id: 1» вернулся дважды.

Я полагаю, что оператор SQL OrderBy не производит один и тот же упорядоченный список каждый раз, когда OrderBy заказывает заданное свойство, но точный порядок внутри группы, которая имеет одно и то же свойство, может измениться.

Каков точный механизм под капотом?

Answer 1

Короткий ответ: LINQ to Objects использует устойчивый алгоритм сортировки, поэтому мы можем сказать, что он детерминирован, а LINQ to SQL зависит от реализации базы данных Order By, которая обычно недетерминирована.

Детерминированный алгоритм сортировки - это тот же метод, что и на разных прогонах.

В вашем примере у вас есть дубликаты в предложении OrderBy. Для гарантированного и прогнозируемого сортировки один из предложений заказа или комбинация предложений заказа должен быть уникальным.

В LINQ вы можете достичь этого, добавив еще одно предложение OrderBy, чтобы указать свое уникальное свойство, например, в
items.OrderBy(i => i.Rate).ThenBy(i => i.ID).

Длинный ответ:

LINQ к объектам использует стабильную сортировку, как описано в этой ссылке: MSDN.

В LINQ to SQL это зависит от алгоритма сортировки базовой базы данных, и обычно это нестабильный тип, например, в MS SQL Server (MSDN).

В устойчивой сортировке, если ключи из двух элементов равны, порядок элементов сохраняется.Напротив, нестабильная сортировка не сохраняет порядок элементов, имеющих один и тот же ключ.

Так, LINQ к SQL, сортировка обычно недетерминирован, потому что (реляционная система управления базами данных, как MS SQL Server) RDMS может напрямую использовать алгоритм нестабильную сортировки с случайного выбора поворота или случайность может быть связана с тем, с какой базой данных происходит доступ к первой базе данных в файловой системе.

Например, представьте, что размер страницы в файловой системе может содержать до 4 строк.

страница будет полной, если вы вставите следующие данные:

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

Если вам нужно вставить новую строку, то RDMS имеет два варианта:

1. Создать новую страницу для выделения новой строки.
2. Разделить текущую страницу на две страницы. Таким образом, первая страница будет содержать имена и B и вторая страница будет держать C и D.

Предположим, что RDMS выбирает вариант 1 (для уменьшения фрагментации индекса). Если вставить новую строку с названием C и Value , вы получите:

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

Вероятно, предложение OrderBy в колонке Имя возвратит следующее:

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

Предположим, что RDMS выбирает вариант 2 (чтобы увеличить производительность вставки в системе хранения со многими шпинделями). Если вставить новую строку с названием C и Value , вы получите:

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

Вероятно, предложение OrderBy в колонке Имя возвратит следующее:

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

Относительно вашего примера:

Я считаю, что вы упустили что-то в своем вопросе, потому что вы использовали items.OrderBy(i => i.rate).Skip(2).Take(2);, и первый результат не показывает строку с Rate = 2.Это невозможно, так как Skip игнорирует первые две строки, и они имеют Rate = 1, поэтому ваш вывод должен показывать строку с Rate = 2.

Вы отметили свой вопрос database, поэтому я считаю, что вы используете LINQ to SQL. В этом случае результаты могут быть недетерминирован и вы можете получить следующее:

Результат 1:

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

Результат 2:

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

Если вы использовали items.OrderBy(i => i.rate).ThenBy(i => i.ID).Skip(2).Take(2); тогда единственный возможный результат будет be:

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