Storage order vs Result order

Question

This is a spin-off question from Sort order specified in primary key, yet sorting is executed on SELECT.

@Catcall says this on the subject of storage order (clustered index) and the output order

A lot of people believe that a clustered index guarantees a sort order on output. But that's not what it does; it guarantees a storage order on disk. See, for example, this blog post.

I've read the blog post by Hugo Kornelis and understands that an index doesn't guarantee that the sql server reads the records in a specific order. Yet I have a hard time accepting that I can't assume this for my scenario?

CREATE TABLE [dbo].[SensorValues](
  [DeviceId] [int] NOT NULL,
  [SensorId] [int] NOT NULL,
  [SensorValue] [int] NOT NULL,
  [Date] [int] NOT NULL,
CONSTRAINT [PK_SensorValues] PRIMARY KEY CLUSTERED 
(
  [DeviceId] ASC,
  [SensorId] ASC,
  [Date] DESC
) WITH (
    FILLFACTOR=75,
    DATA_COMPRESSION = PAGE,
    PAD_INDEX = OFF,
    STATISTICS_NORECOMPUTE = OFF,
    SORT_IN_TEMPDB = OFF,
    IGNORE_DUP_KEY = OFF,
    ONLINE = OFF,
    ALLOW_ROW_LOCKS = ON,
    ALLOW_PAGE_LOCKS = ON)
  ON [MyPartitioningScheme]([Date])

My original query was this:

SELECT TOP 1 SensorValue
  FROM SensorValues
  WHERE SensorId = 53
    AND DeviceId = 3819
    AND Date < 1339225010
  ORDER BY Date DESC

But I suggest that I could as well use this one (read below for my explanation):

SELECT TOP 1 SensorValue
  FROM SensorValues
  WHERE SensorId = 53
    AND DeviceId = 3819
    AND Date < 1339225010

As you can see, my table rows are small (16bytes) and I've got only one index, a clustered. In my scenario, the table consists of 100.000.000 records at this moment (and this will most likely increase tenfold).

When the database server queries this table it has two ways of finding my rows, either it seeks the primary key and thereby reading and returning my values in desc. order of Date, or it has to do a full table scan. My conclusion is that a full table scan on all those records will be way too slow and the database server will therefore always seek the table via its primary key and thereby returning the values sorted by Date DESC

Answer 1

Let me try to explain why you should not do that, why you should never assume that an SQL-product will return a result set in a specific order, unless you specify so, whatever indices - clustered or non-clustered, B-trees or R-Trees or k-d-trees or fractal-trees or whatever other exotic indices a DBMS is using.

---

Your original query tells to the DBMS to search the SensorValues table, find rows that match the 3 conditions, order those rows by Date descending, keep only the first row from those and - finally - select and return only the SensorValue column.

SELECT TOP 1 SensorValue
  FROM SensorValues
  WHERE SensorId = 53
    AND DeviceId = 3819
    AND Date < 1339225010
  ORDER BY Date DESC ;

These are very specific orders you have given to the DBMS and the result will most probably be the same every time you run the query (there is a chance it might not, if you have more than one row that match the conditions and have the same max Date but different SensorValue but lets assume for the rest of the conversation that no such rows exist in your table).

Does the DBMS have to do this, to run this query, the exact way I describe it above? No, of course not and you know that. It may not read the table but read from an index. Or it may use two indexes if it thinks it's better (faster). Or three. Or it may use a cached result (not SQL Server but other DBMS cache query results). Or it may use parallel execution one time and not the next time it runs. Or ... (add any other feature that affects execution and execution plans).

What is guaranteed though is that it will return the exact same result, every time you run it - as long as no rows are inserted, deleted or updated.

---

Now lets see what your suggestion says:

SELECT TOP 1 SensorValue
  FROM SensorValues
  WHERE SensorId = 53
    AND DeviceId = 3819
    AND Date < 1339225010 ;

This query tells to the DBMS to search the SensorValues table, find rows that match the 3 conditions, order those rows by Date descending,, don't care about the order, keep only one row and - finally - select and return only the SensorValue column.

So, it basically tells the same as the first one, except that it tells that you want one result only that matches the conditions and you don't care which one.

Now, can we assume that it will give always the same result because of the clustered index?
- If it does use this clustered index every time, yes.

But will it use it?
- No.

Why not?
- Beacuse it can. The query optimizer is free to choose a path of execution every time it runs a statement. Whatever path it sees fit at that time for that statement.

But isn't using the clustered index the best/fastest way to get results?
- No, not always. It might be the first time you run the query. The second time, it may use a cached result (if the DBMS has such a feature, not SQL Server^*). The 1000th time the result may have been removed from the cache and another result may exist there. Say, you had executed this query just before:

SELECT TOP 1 SensorValue
  FROM SensorValues
  WHERE SensorId = 53
    AND DeviceId = 3819
    AND Date < 1339225010
  ORDER BY Date ASC ;         --- Notice the `ASC` here

and the cached result (from the above query) is another, different one that still matches your conditions but is not the first in your (wanted) ordering. And you have told the DBMS not to care about the order.

OK, so only cache can affect this?
- No, many other things, too.

• other indexes were considered, at that time by the DBMS as better for this query.
• a developer changed or completely removed this clustered index you had.
• you or some other developer added another index that the optimizer decided it's more efficient to use than the CI.
• you updated to a new version and the new optimizer has a minor bug or a change in how it ranks and chooses execution plans.
• statistics were updated.
• parallel execution was chosen instead.

^{*: SQL Server does not cache query results but the Enterprise Edition does have an Advanced Scanning feature which is kind of similar in that you may get different results because of concurrent queries. Not sure exactly when this kicks in though. (thnx @Martin Smith for the tip.)}

---

I hope you are convinced that you should never rely that an SQL query will return results in a specific order, unless you specify so. And never use TOP (n) without ORDER BY, unless of course you just want n rows in the result and you don't care which ones are returned.