SQL Server 2008 R2 stored procedure output results in different order when executing multiple times

Question

Just encountered an odd behavior during our regression with a stored procedure which output thousands of records:

The stored procedure could output the results in different orders with same parameters if it's being called more than 20 times in a short while.

Anyone got any idea about this behavior?

For some reason, we are not able to specify the order explicitly in the stored procedure.

Answer 1

A parallel query plan sounds a likely culprit ( or different query plans being used on different runs).

If you are not explicitly ordering with an ORDER BY, then no order is guaranteed.

Can you post the Stored Procedure and a query plan?