NOLOCK hint changes order of records returned

There is a clustered index on a table Client field LastName.

When I simply dump all records from the table, they appear in the alphabetical order unless (nolock) hint is used as in the query in question. That hint changes the order of records. Should it?. I am positive that no other session has an open transaction with the changes to that table (at least sp_who2 is not showing me any).

How can the difference in the order be explained?

Additional information pulled from comments:

-
There is no order by. Should non clustered index enforce the order?

-
The queries still return different order even when using an index hint specifying a clustered index. Should they? I am wondering why nolock changes the order of returned records without a visible change of the plans.

-
I did a WinDiff on them - same except for [the] (nolock) [query hint].

The appearance of an ordered result set, without an ORDER BY clause, often results from a scan retrieving rows in index order. One reason why an index-order scan is generally chosen under the default READ COMMITTED isolation level is that it reduces the chances of unwanted concurrency anomalies such as encountering the same row multiple times, or entirely skipping some rows. This is detailed in several places, including in this series of articles about isolation levels.

With a NOLOCK table hint, this behavior is relaxed, and access to the table is performed under the more tolerant READ UNCOMMITTED isolation level, which may scan data in allocation order instead of index order. As described in that link, the decision about whether to use an allocation-order or index-order scan is left up to the storage engine. This choice may change between executions without a change in query plan.

This may sound very abstract, but can be more easily demonstrated with some queries using undocumented functions against the AdventureWorks2012 database.

USE AdventureWorks2012;
GO
-- Appears to be ordered by BusinessEntityID
-- File:Page:Slot goes up and down several times
-- Show physical locations with sys.fn_PhysLocFormatter (undocumented)
SELECT
    P.BusinessEntityID,
    [(File:Page:Slot)] =
        sys.fn_PhysLocFormatter(%%physloc%%)
FROM Person.Person AS P;

-- Same query with TABLOCK or NOLOCK
-- Allocation-order (IAM) scan
-- Now appears to be ordered by File:Page:Slot instead of BusinessEntityID
SELECT P.BusinessEntityID,
    [(File:Page:Slot)] =
        sys.fn_PhysLocFormatter(%%physloc%%)
FROM Person.Person AS P WITH (NOLOCK);

The queries are borrowed with slight modification from Paul White.

Finally, just to be clear, this answer is about the appearance of an ordered result set. There is no guaranteed presentation order without a top-level ORDER BY.

An allocation-order scan can occur in a variety of other circumstances, such as when a table-level lock is acquired, or the database is in read-only mode. Parallelism can also influence the order the data is returned in. The key point is that without ORDER BY, the order data is returned in can vary over time by design.

StackExchange Database Administrators Q#112881, answer score: 48