Is it REALLY possible that the order will not be guaranteed for this particular redundant derived table?

Question

I stumbled upon this question on a Twitter conversation with Lukas Eder.

Although the correct behavior would be to apply the ORDER BY clause on the outermost query, because, here, we are not using DISTINCT, GROUP BY, JOIN or any other WHERE clause in the outermost query, why wouldn't a RDBMS just pass the incoming data as it was sorted by the inner query?

SELECT * 
FROM (
    SELECT * FROM table ORDER BY time DESC
) AS t

When running this example on PostgreSQL, at least, you get the same Execution Plan for both the inner query and this derived table example, as well as the same result set.

So, I would assume that the Planner will simply discard the outermost query because it's redundant or simply pass through the results from the inner table.

Does anyone think this might not be the case?

Answer 1

Most databases are quite clear about the fact that an ORDER BY in a subquery is either:

• Not allowed: E.g. SQL Server, Sybase SQL Anywhere (unless complemented with TOP or OFFSET .. FETCH)
• Meaningless: E.g. PostgreSQL, DB2 (again, unless complemented with OFFSET .. FETCH or LIMIT)

Here's an example from the DB2 LUW manual (emphasis mine)

An ORDER BY clause in a subselect does not affect the order of the rows returned by a query. An ORDER BY clause only affects the order of the rows returned if it is specified in the outermost fullselect.

The wording is quite explicit, just like PostgreSQL's:

If sorting is not chosen, the rows will be returned in an unspecified order. The actual order in that case will depend on the scan and join plan types and the order on disk, but it must not be relied on. A particular output ordering can only be guaranteed if the sort step is explicitly chosen.

From this specification, it can be followed that any ordering resulting from the ORDER BY clause in a derived table is merely accidental and may coincidentally match your expected ordering (which it does in most databases in your trivial example), but it would be unwise to rely on this.

Side note on DB2:

In particular, DB2 has a lesser known feature called ORDER BY ORDER OF <table-designator>, which can be used as follows:

SELECT C1 FROM
   (SELECT C1 FROM T1
      UNION
    SELECT C1 FROM T2
    ORDER BY C1 ) AS UTABLE
ORDER BY ORDER OF UTABLE

In this particular case, the ordering of the derived table can be explicitly re-used in the outer most SELECT

Side note on Oracle:

For years it has been a practice in Oracle to implement OFFSET pagination using ROWNUM, which can be reasonably calculated only after ordering a derived table:

SELECT *
FROM (
  SELECT rownum AS rn, t.* -- ROWNUM here depends on the derived table's ordering
  FROM (
    SELECT * FROM table ORDER BY time DESC
  ) t
) t
WHERE rn BETWEEN 10 AND 20

It can be reasonably expected that at least in the presence of ROWNUM in a query, future Oracle versions will not break this behaviour in order not to break pretty much all the legacy Oracle SQL out there, which has not yet migrated to the much more desireable and readable SQL standard OFFSET .. FETCH syntax:

SELECT * FROM table ORDER BY time DESC OFFSET 10 ROWS FETCH NEXT 10 ROWS ONLY

Answer 2

Yes. Without an ORDER BY clause the output order is undefined and the query planner is well within its purview to assume that you know and understand this.

It may decide that because the outer query doesn't specify an order it can drop the ordering in the inner query to avoid a sort operation, especially if there is no clustered index or no index at all to support the ordering. If it doesn't now it may do in future versions.

Never rely on undefined behaviour. If you need a specific ordering, give an ORDER BY clause in the appropriate place.

Answer 3

Its the very problem with undefined behaviour - works for you, works for me, reformats the HDD in prod ;)

We can take a step back and say that in one sense you're right - theres no earthly reason why any sane RDBMS would rearrange the rows in the inner select. But its not guaranteed - meaning that there may in future be a reason, and vendors are free to do so. Meaning that any code that relies on this behaviour is at the mercy of a change that a vendor could make which they would be under no obligation to publicise, as it isnt a breaking change from an API POV.

Answer 4

Is it REALLY possible that the order will not be guaranteed for this particular redundant derived table?

The answer for all currently existing Postgres (which you were testing) versions is: No. For the given query, sort order is guaranteed.

SQL server people will be uncomfortable with this since Microsoft does not even allow ORDER BY in subqueries. Sort order is guaranteed for this simple query in Postgres nonetheless. ORDER BY is applied in the subquery, and the outer query does not do anything that might change the order.

The manual even hints as much in the chapter Aggregate Functions:

Alternatively, supplying the input values from a sorted subquery will usually work.

Note this is only true while outer query levels don't add operations that might change the order. So it's only "guaranteed" for the simple case, and that's not backed by the SQL standard. Postgres is free to reorder if it's opportune for additional operations. In case of doubt add another ORDER BY to the outer SELECT. (In which case the inner ORDER BY would be redundant noise for this simple query.)