LINQ OrderBy Does it always return the same ordered list?

Question

I tried a simple OrderBy statement.

The target data for the order is something like below:

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

Then I order the elements by the rate property.

The fuzzy thing is that if I “order them”, he “skips” some elements with a given offset, and then “takes” only a part of the data.

For instance,

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

The result looks great for most of them, but the edge register element does not return at all.

For instance,

if the first result returns as

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

the second result is returned as

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

The element "id: 19" was not returned on the second call to the request. Instead, the id: 1 element returned twice.

I assume that the OrderBy SQL statement does not produce the same ordered list every time OrderBy orders a specific property, but the exact order within a group that has the same property may change.

What is the exact mechanism under the hood?

Answer 1

Short answer: LINQ to Objects uses a stable sorting algorithm, so we can say that it is deterministic, and LINQ to SQL depends on the implementation of the Order By database, which is usually non-deterministic. p>

A deterministic sorting algorithm is one that always has the same behavior for different runs.

In your example, you have duplicates in the OrderBy clause. For guaranteed and predictable sorting, one of the order offers or a combination of order offers must be unique.

In LINQ, you can achieve this by adding another OrderBy clause to reference your unique property, for example, in
items.OrderBy(i => i.Rate).ThenBy(i => i.ID) .

Long answer:

LINQ to Objects uses stable sorting as described in this link: MSDN .

In LINQ to SQL, this depends on the sorting algorithm of the base database, and it is usually an unstable type, for example, in MS SQL Server ( MSDN ).

In a stable way, if the keys of two elements are equal, the order of the elements is preserved. In contrast, unstable sorting does not preserve the order of elements that have the same key.

So, for LINQ to SQL, sorting is usually non-deterministic, since RDMS (a relational database management system such as MS SQL Server) can directly use an unstable sorting algorithm with random axis selection or randomness may be related to which database is accessing The first database in the file system.

For example, imagine a page size on a file system can contain up to 4 lines.

The page will be filled if you enter the following data:

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

If you need to insert a new line, RDMS has two options:

• Create a new page to place a new line.
• Divide the current page into two pages. Thus, the first page will contain the names A and B , and the second page will contain C and D.

Suppose RDMS chooses option 1 (to reduce index fragmentation). If you insert a new row with the name C and a value of 9 , you will get:

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

Perhaps the OrderBy clause in the Name column will return the following:

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

Now suppose RDMS chooses option 2 (to increase insert performance in a multi-spindle storage system). If you insert a new row with the name C and a value of 9 , you will get:

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

Perhaps the OrderBy clause in the Name column will return the following:

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

Regarding your example:

I believe you were saddened by something in your question because you used items.OrderBy(i => i.rate).Skip(2).Take(2); , and the first result does not show a line with Rate = 2 . This is not possible, since Skip will ignore the first two lines, and they have Rate = 1 , so your output should show a line with Rate = 2 .

You tagged your question with database , so I believe you are using LINQ to SQL. In this case, the results can be non-deterministic, and you can get the following:

Result 1:

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

Result 2:

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

If you used items.OrderBy(i => i.rate).ThenBy(i => i.ID).Skip(2).Take(2); then the only possible result would be the following:

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