Preserving order with LINQ

Question

I use LINQ to Objects instructions on an ordered array. Which operations shouldn't I do to be sure the order of the array is not changed?

Incogitant

Answer 1

I examined the methods of System.Linq.Enumerable, discarding any that returned non-IEnumerable results. I checked the remarks of each to determine how the order of the result would differ from order of the source.

Preserves Order Absolutely. You can map a source element by index to a result element

• AsEnumerable
• Cast
• Concat
• Select
• ToArray
• ToList

Preserves Order. Elements are filtered or added, but not re-ordered.

• Distinct
• Except
• Intersect
• OfType
• Prepend (new in .net 4.7.1)
• Skip
• SkipWhile
• Take
• TakeWhile
• Where
• Zip (new in .net 4)

Destroys Order - we don't know what order to expect results in.

• ToDictionary
• ToLookup

Redefines Order Explicitly - use these to change the order of the result

• OrderBy
• OrderByDescending
• Reverse
• ThenBy
• ThenByDescending

Redefines Order according to some rules.

• GroupBy - The IGrouping objects are yielded in an order based on the order of the elements in source that produced the first key of each IGrouping. Elements in a grouping are yielded in the order they appear in source.
• GroupJoin - GroupJoin preserves the order of the elements of outer, and for each element of outer, the order of the matching elements from inner.
• Join - preserves the order of the elements of outer, and for each of these elements, the order of the matching elements of inner.
• SelectMany - for each element of source, selector is invoked and a sequence of values is returned.
• Union - When the object returned by this method is enumerated, Union enumerates first and second in that order and yields each element that has not already been yielded.

---

Edit: I've moved Distinct to Preserving order based on this implementation.

    private static IEnumerable<TSource> DistinctIterator<TSource>
      (IEnumerable<TSource> source, IEqualityComparer<TSource> comparer)
    {
        Set<TSource> set = new Set<TSource>(comparer);
        foreach (TSource element in source)
            if (set.Add(element)) yield return element;
    }

Strasbourg

Actually, I think Distinct preserves original (first found) order - so {1,2,1,3,1,3,4,1,5} would be {1,2,3,4,5} – Gamesome

msdn.microsoft.com/en-us/library/bb348436.aspx The Distinct<(Of <(TSource>)>)(IEnumerable<(Of <(TSource>)>)) method returns an unordered sequence that contains no duplicate values. – Strasbourg

Marc: what you say could be true, but it would be a bad idea to rely on that behavior. – Strasbourg

@Amy B I think it would be unreasonable to implement Distinct (for linq to objects) in a way that doesn't preserve order, since that would perform worse than if it did preserve order. – Disrepair

@Disrepair shrug if you want to defy the documentation, that's up to you. – Strasbourg

@Amy B yes but it doesn't apply to Linq to Objects. In Linq to Sql, distinct() puts the distinct keyword into the generated sql, and ordering from sql is not guaranteed. I'd be interested to see an implementation of distinct for linq to objects that doesn't preserve order and is more efficient that one that does preserve order. For example, you can consume the entire input and put it in a hashset, then yield values by enumerating the hashset (losing order), but that's worse. So yeah, I don't mind defying documentation every now and then :) – Disrepair

@Dan "Found First" destroys order. In that list the 1 is before and after the 4. By making it a distinct list, that ordering is gone. – Mirador

@Mirador - depends on your definition of preserves order. If we go with the FoundFirst for Distinct - one could aruge that elements are filtered and not reordered. The only reason I have for not choosing that option, is the documentation says "unordered". – Strasbourg

@Amy and that's why. Found First isn't the same as Distinct. If there comes a time when someone has a way to do distinct without preserving order that is faster, then by all means, I don't want to hold them back because of an assumption. – Mirador

Maybe the documentation (for Distinct method) just meant to say "unsorted", not "in unpredictable order". I'd say Distinct belongs to the filtering category above, just like Where. – Aegaeon

I'm not sure about select many, as there is no other constructions besides two foreaches. What side effect are you talking about? – Bechuana

@Bechuana I've considered my use of the term "side effect", and decided to edit since it has a meaning in our field. Also, when I'm talking about "preserving order", I'm talking from the perspective of Order Isomorphism. Distinct and SelectMany are not order isomorphic. – Strasbourg

Aren't Except, Intersect Union etc set operations? I wouldnt trust them to return in order. Is it documented? – Womenfolk

@Womenfolk Intersect ( msdn.microsoft.com/en-us/library/vstudio/… ): "Finally, the marked elements are yielded in the order in which they were collected." Except doesn't document this, but its implementation is likely to be very similar. Union ( msdn.microsoft.com/en-us/library/vstudio/… ) : quote is already in the answer. While these operations could be described as set operations, they operate on IEnumerable<T> and it makes sense for their implementations to have a documented order based on the order of the source IEnumerable. – Strasbourg

@Womenfolk also note: this question and answer are about LinqToObjects (the methods of System.Linq.Enumerable). If you are using Linq to anything else (System.Linq.Queryable) - none of this applies. – Strasbourg

@AmyB For ILookup: The IGrouping<TKey, TElement> objects are yielded in an order based on the order of the elements in source that produced the first key of each IGrouping<TKey, TElement>. Elements in a grouping are yielded in the order they appear in source., taken from the GroupBy documentation. Since ILookup has IGroupings, it's guaranteed to preserve order, right? – Ounce

github.com/dotnet/corefx/blob/master/src/System.Linq.Parallel/… ToLookup returns a Lookup. As you can see in the code, Lookup wraps a Dictionary. Because of this, Lookup has the same inconsistent ordering as Dictionary. – Strasbourg

Lookup indeed wraps a dictionary but a special one: it maintains links between the elements to preserve the ordering of group keys, because it has to fulfil the documented ordering of GroupBy. Lookup is the underlying data structure of both GroupBy and ToLookup. Therefore ToLookup preserves ordering just as well as Distinct does: neither is documented, both works (for ≥ 6 years now). – Phenothiazine

But Lookup is backed by a plain Dictionary: _dict = new Dictionary<TKey, IGrouping<TKey, TElement>>(_comparer); Does this mean that Dictionary preserves order? – Strasbourg

@Amy B The plain Dictionary preserves ordering (albeit undocumented) as long as no elements are removed, but it is not used in Lookup. Its internal GetGrouping() method contains a hash table implementation, with the aforementioned .next pointers, to be used in GetEnumerator() (line 3288). – Phenothiazine

@Phenothiazine it looks like ToLookup changes the keys order, but the elements preserve the order of the source enumerable. – Steger

@Steger can you show an example on dotnetfiddle.net? It sounds me impossible. Are you speaking about Linq.Parallel or the normal(serial) one? – Phenothiazine

@Phenothiazine take a look at ToLookup which calls Lookup.Create. It runs serially on the source enumerable and calls Grouping.Add that encapsulate a simple array buffer. – Steger

@Steger This proves that the order of elements is preserved within the groups, which I didn't question. I contradicted with the first half of your claim: “ToLookup changes the keys order”. Lookup.Create calls lookup.GetGrouping() for every item of the source, which creates groups in a manner that preserves the ordering of keys, as I detailed above. – Phenothiazine

You didn't mention Aggregate. Aggregate follows the order because the concept of Aggregate requires that it follows the order. Here's the Reference Source to verify this. I realize that since it's kind of a given, it might not be important enough to mention, but it's not mentioned anywhere on this Q&A. – Mobocracy

@ZachMierzejewski Aggregate was excluded because it does not return an IEnumerable. With no enumerable result, the order of the result does not exist and cannot be defined as preserved or not. It is important to know that Aggregate processes the input in order, same as all the methods which have an IEnumerable source. – Strasbourg

I think it's funny that no one ever asked me to move Union to Preserving Order... it has the same Found First behavior as Distinct. – Strasbourg

So why doesn't, eg, Skip (and other things on the order preserved list) return an IOrderedEnumerable? – Wawro

@Wawro It might be helpful to think about what IOrderedEnumerable<T> is for. Without this interface, we could not call ThenBy. Does it make sense to call customers.Skip(5).ThenBy(c => c.Name) ? Skip does not define an ordering - its implementation doesn't change the order. – Strasbourg

Thanks for the reply! The flipside of this, however, is that IEnumerable doesn't guarantee order, and I wouldn't've assumed I could count on something returning IEnumerable "doesn't change the order". It seems smelly to say that a function that returns an unordered type guarantees that unordered type's order is preserved. Wait, what? ;^) If customers has an internalized idea of how it's ordered (ie, the formula by which it's ordered, which I admit I don't think is the case), then your Skip usage would, in fact, make sense. orderedByCountyCustomers.Skip(5).ThenBy(c => c.Name) – Wawro

Interesting continuation of your point in this answer from Eric Lippert & discussion with Skeet. Still seems weird to pretend an IEnumerable has an order to be preserved when it doesn't guarantee order (ie, is implicitly unordered)... I think it's probably better for me to think that an IEnumerable can be ordered, but doesn't, by itself, guarantee order. IOrderedEnumerable probably isn't the best name for what it's doing either.. IInTheProcessOfBeingOrderedEnumerable? /shrug Thanks again. – Wawro

@Wawro most IEnumerable<T> have an order (for example, array index order). When they do, the order is preserved by the operations. When they don't, there is no order to preserve. All IOrderedEnumerable<T> have a defined order. That defined order is respected and modified by calls to ThenBy. – Strasbourg

I think you were correct to go by the documented behavior of Distinct and not the implementation. Nothing says .Net has to run on a Von Neumann architecture - on a version for a Connection Machine, perhaps not preserving order would be a better implementation. – Vegetal

Great list! But I don't see anything in the Select remarks or anywhere else on the page that states the order is guaranteed to be preserved. – Standford

Hi @Standford , the indexed overload in the Select documentation mentions processing and returning the items in order. learn.microsoft.com/en-us/dotnet/api/… – Strasbourg

Hey @AmyB The only mention of the word "order" on that page says that selector overload can provide the item's index in the "source sequence". But that doesn't indicate what the Select function returns. Can you quote part of where you're seeing a mention of returning the items in order? – Standford

It seems that the old debate about ToLookup was never resolved, but Microsoft's own documentation for multiple versions of ToLookup (e.g. Framework 4.5, .Net 6, etc.) all say for ToLookup() overloads that "The values within each group are in the same order as in source." – Turnabout

Answer 2

Are you actually talking about SQL, or about arrays? To put it another way, are you using LINQ to SQL or LINQ to Objects?

The LINQ to Objects operators don't actually change their original data source - they build sequences which are effectively backed by the data source. The only operations which change the ordering are OrderBy/OrderByDescending/ThenBy/ThenByDescending - and even then, those are stable for equally ordered elements. Of course, many operations will filter out some elements, but the elements which are returned will be in the same order.

If you convert to a different data structure, e.g. with ToLookup or ToDictionary, I don't believe order is preserved at that point - but that's somewhat different anyway. (The order of values mapping to the same key is preserved for lookups though, I believe.)

Pyrene

so because OrderBy is a stable sort, then: seq.OrderBy( _ => _.Key ) will put the elements in to exactly the same order as seq.GroupBy( _ => _.Key ).SelectMany( _ => _ ). Is that correct? – Christianity

@dmg: No, it won't. Just GroupBy followed by SelectMany will give the results grouped by key, but not in ascending key order... it will give them in the order in which the keys originally occurred. – Pyrene

are you saying that LINQ to SQL does not preserver order? – Machree

@symbiont: In many SQL operations there is no well-defined order to start with. Basically I'm trying to only make promises about things I can guarantee - such as LINQ to Objects. – Pyrene

@JonSkeet If I use OrderBy does it guarantee that 'n' objects with the same key will preserve their original sequence except that they are all together. ie.:in list<x> {a b c d e f g} if c,d,e all have the same key then the resulting sequence will contain c,d,e next to each other AND in the order c,d,e. I can't seem to find a categorical MS-based answer. – Corcoran

@Paulustrious: In LINQ to Objects, yes. In other providers, it's implementation-specific. – Pyrene

@JonSkeet You're good. You answered while I was still editing my question – Corcoran

@Paulustrious: From msdn.microsoft.com/en-us/library/bb534966(v=vs.110).aspx: "This method performs a stable sort; that is, if the keys of two elements are equal, the order of the elements is preserved. In contrast, an unstable sort does not preserve the order of elements that have the same key." – Pyrene

Regarding the statement about ToLookup not preserving order, Microsoft's own documentation for multiple versions of ToLookup (e.g. Framework 4.5, .Net 6, etc.) all say for ToLookup() overloads that "The values within each group are in the same order as in source." The keys are not necessary stored in the same order, but enumeration or indexing into the Lookup object does preserve the order. – Turnabout

@CPerkins: Hence "The order of values mapping to the same key is preserved for lookups though, I believe." – Pyrene

Answer 3

If you are working on an array, it sounds like you are using LINQ-to-Objects, not SQL; can you confirm? Most LINQ operations don't re-order anything (the output will be in the same order as the input) - so don't apply another sort (OrderBy[Descending]/ThenBy[Descending]).

[edit: as Jon put more clearly; LINQ generally creates a new sequence, leaving the original data alone]

Note that pushing the data into a Dictionary<,> (ToDictionary) will scramble the data, as dictionary does not respect any particular sort order.

But most common things (Select, Where, Skip, Take) should be fine.

Gamesome

If I'm not mistaken, ToDictionary() merely makes no promises about the order, but in practice maintains the input order (until you remove something from it). I'm not saying to rely on this, but 'scrambling' seems inaccurate. – Codicodices

Answer 4

I found a great answer in a similar question which references official documentation. To quote it:

For Enumerable methods (LINQ to Objects, which applies to List<T>), you can rely on the order of elements returned by Select, Where, or GroupBy. This is not the case for things that are inherently unordered like ToDictionary or Distinct.

From Enumerable.GroupBy documentation:

The IGrouping<TKey, TElement> objects are yielded in an order based on the order of the elements in source that produced the first key of each IGrouping<TKey, TElement>. Elements in a grouping are yielded in the order they appear in source.

This is not necessarily true for IQueryable extension methods (other LINQ providers).

Source: Do LINQ's Enumerable Methods Maintain Relative Order of Elements?

Introspection

Answer 5

Any 'group by' or 'order by' will possibly change the order.

Bake

Answer 6

The question here is specifically referring to LINQ-to-Objects.

If your using LINQ-to-SQL instead there is no order there unless you impose one with something like:

mysqlresult.OrderBy(e=>e.SomeColumn)

If you do not do this with LINQ-to-SQL then the order of results can vary between subsequent queries, even of the same data, which could cause an intermittant bug.

Augustus

Answer 7

For me the issue was determining the default sort order which turned out to be by 2 columns as shown below. After many iterations I was able to find the default sort order and redo it in my LINQ query. To remove duplicates a simple foreach is used to create a new list of strings without duplicates.

//original sorting order lost
var inv2 = db.Inventories
.GroupBy(l => l.VendorFullSKU)
.Select(cl => new Inventory2
{
    VariantID = cl.FirstOrDefault() == null ? 0 : cl.FirstOrDefault().VariantID,
    Quan = cl.Sum(c => c.Quan), 
    Color = cl.FirstOrDefault() == null ? "" : cl.FirstOrDefault().Color    
});


//original sorting order restored
var bl = (from pv in db.ProductVariants
join inv in inv2 on pv.VariantID equals inv.VariantID
orderby inv.VariantID, inv.Color //sort
select inv.Color
).ToList();


//remove duplicates while preserving original sort order
var colorsDistinct = new List<string>();
foreach (var item in bl)
{
    if (!colorsDistinct.Contains(item))
        colorsDistinct.Add(item);
}

Enochenol