Share via


Order Preservation in PLINQ

In PLINQ, the goal is to maximize performance while maintaining correctness. A query should run as fast as possible but still produce the correct results. In some cases, correctness requires the order of the source sequence to be preserved; however, ordering can be computationally expensive. Therefore, by default, PLINQ does not preserve the order of the source sequence. In this regard, PLINQ resembles LINQ to SQL, but is unlike LINQ to Objects, which does preserve ordering.

To override the default behavior, you can turn on order-preservation by using the AsOrdered operator on the source sequence. You can then turn off order preservation later in the query by using the AsUnordered<TSource> method. With both methods, the query is processed based on the heuristics that determine whether to execute the query as parallel or as sequential. For more information, see Understanding Speedup in PLINQ.

The following example shows an unordered parallel query that filters for all the elements that match a condition, without trying to order the results in any way.

Dim cityQuery = From city In cities.AsParallel()
               Where City.Population > 10000
               Take (1000)
var cityQuery = (from city in cities.AsParallel()
                 where city.Population > 10000
                 select city)
                   .Take(1000);

This query does not necessarily produce the first 1000 cities in the source sequence that meet the condition, but rather some set of 1000 cities that meet the condition. PLINQ query operators partition the source sequence into multiple subsequences that are processed as concurrent tasks. If order preservation is not specified, the results from each partition are handed off to the next stage of the query in an arbitrary order. Also, a partition may yield a subset of its results before it continues to process the remaining elements. The resulting order may be different every time. Your application cannot control this because it depends on how the operating system schedules the threads.

The following example overrides the default behavior by using the AsOrdered operator on the source sequence. This ensures that the Take<TSource> method returns the first 10 cities in the source sequence that meet the condition.

Dim orderedCities = From city In cities.AsParallel().AsOrdered()
                    Where City.Population > 10000
                    Take (1000)
            var orderedCities = (from city in cities.AsParallel().AsOrdered()
                                 where city.Population > 10000
                                 select city)
                                .Take(1000);

However, this query probably does not run as fast as the unordered version because it must keep track of the original ordering throughout the partitions and at merge time ensure that the ordering is consistent. Therefore, we recommend that you use AsOrdered only when it is required, and only for those parts of the query that require it. When order preservation is no longer required, use AsUnordered<TSource> to turn it off. The following example achieves this by composing two queries.

        Dim orderedCities2 = From city In cities.AsParallel().AsOrdered()
                             Where city.Population > 10000
                             Select city
                             Take (1000)

        Dim finalResult = From city In orderedCities2.AsUnordered()
                            Join p In people.AsParallel() On city.Name Equals p.CityName
                            Select New With {.Name = city.Name, .Pop = city.Population, .Mayor = city.Mayor}

        For Each city In finalResult
            Console.WriteLine(city.Name & ":" & city.Pop & ":" & city.Mayor)
        Next

var orderedCities2 = (from city in cities.AsParallel().AsOrdered()
                      where city.Population > 10000
                      select city)
                        .Take(1000);


var finalResult = from city in orderedCities2.AsUnordered()
                  join p in people.AsParallel() on city.Name equals p.CityName into details
                  from c in details
                  select new { Name = city.Name, Pop = city.Population, Mayor = c.Mayor };

foreach (var city in finalResult) { /*...*/ }

Note that PLINQ preserves the ordering of a sequence produced by order-imposing operators for the rest of the query. In other words, operators such as OrderBy and ThenBy are treated as if they were followed by a call to AsOrdered.

Query Operators and Ordering

The following query operators introduce order preservation into all subsequent operations in a query, or until AsUnordered<TSource> is called:

The following PLINQ query operators may in some cases require ordered source sequences to produce correct results:

Some PLINQ query operators behave differently, depending on whether their source sequence is ordered or unordered. The following table lists these operators.

Operator

Result when the source sequence is ordered

Result when the source sequence is unordered

Aggregate

Nondeterministic output for nonassociative or noncommutative operations

Nondeterministic output for nonassociative or noncommutative operations

All<TSource>

Not applicable

Not applicable

Any

Not applicable

Not applicable

AsEnumerable<TSource>

Not applicable

Not applicable

Average

Nondeterministic output for nonassociative or noncommutative operations

Nondeterministic output for nonassociative or noncommutative operations

Cast<TResult>

Ordered results

Unordered results

Concat

Ordered results

Unordered results

Count

Not applicable

Not applicable

DefaultIfEmpty

Not applicable

Not applicable

Distinct

Ordered results

Unordered results

ElementAt<TSource>

Return specified element

Arbitrary element

ElementAtOrDefault<TSource>

Return specified element

Arbitrary element

Except

Unordered results

Unordered results

First

Return specified element

Arbitrary element

FirstOrDefault

Return specified element

Arbitrary element

ForAll<TSource>

Executes nondeterministically in parallel

Executes nondeterministically in parallel

GroupBy

Ordered results

Unordered results

GroupJoin

Ordered results

Unordered results

Intersect

Ordered results

Unordered results

Join

Ordered results

Unordered results

Last

Return specified element

Arbitrary element

LastOrDefault

Return specified element

Arbitrary element

LongCount

Not applicable

Not applicable

Min

Not applicable

Not applicable

OrderBy

Reorders the sequence

Starts new ordered section

OrderByDescending

Reorders the sequence

Starts new ordered section

Range

Not applicable (same default as AsParallel )

Not applicable

Repeat<TResult>

Not applicable (same default as AsParallel)

Not applicable

Reverse<TSource>

Reverses

Does nothing

Select

Ordered results

Unordered results

Select (indexed)

Ordered results

Unordered results.

SelectMany

Ordered results.

Unordered results

SelectMany (indexed)

Ordered results.

Unordered results.

SequenceEqual

Ordered comparison

Unordered comparison

Single

Not applicable

Not applicable

SingleOrDefault

Not applicable

Not applicable

Skip<TSource>

Skips first n elements

Skips any n elements

SkipWhile

Ordered results.

Nondeterministic. Performs SkipWhile on the current arbitrary order

Sum

Nondeterministic output for nonassociative or noncommutative operations

Nondeterministic output for nonassociative or noncommutative operations

Take<TSource>

Takes first n elements

Takes any n elements

TakeWhile

Ordered results

Nondeterministic. Performs TakeWhile on the current arbitrary order

ThenBy

Supplements OrderBy

Supplements OrderBy

ThenByDescending

Supplements OrderBy

Supplements OrderBy

ToTSource[]

Ordered results

Unordered results

ToDictionary

Not applicable

Not applicable

ToList<TSource>

Ordered results

Unordered results

ToLookup

Ordered results

Unordered results

Union

Ordered results

Unordered results

Where

Ordered results

Unordered results

Where (indexed)

Ordered results

Unordered results

Zip

Ordered results

Unordered results

Unordered results are not actively shuffled; they simply do not have any special ordering logic applied to them. In some cases, an unordered query may retain the ordering of the source sequence. For queries that use the indexed Select operator, PLINQ guarantees that the output elements will come out in the order of increasing indices, but makes no guarantees about which indices will be assigned to which elements.

See Also

Concepts

Parallel LINQ (PLINQ)

Other Resources

Parallel Programming in the .NET Framework