11

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?

  • 3
    Note that your query will fail in SQL Server because an order by is not allowed inside a derived table. – a_horse_with_no_name Aug 23 '17 at 9:50
  • Why are you so incredulous? Why would you assume anything? When you write a program that leaves you a choice do you expect users to expect things about your choice? Read about logical & physical query optimization/implementation. – philipxy Aug 24 '17 at 1:44
  • 2
    "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." You could just as easily assume that the Planner will discard the ordering clause on the inner query because it's meaningless in context. – Wildcard Aug 24 '17 at 3:08
  • MariaDB, about 2012, discusses the issue. Lack of the inner ORDER BY lead to different optimization for groupwise max . – Rick James Aug 24 '17 at 10:54
  • Actually, you are right for Postgres. – Erwin Brandstetter Sep 13 '17 at 13:49
19

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
  • Meaningless: E.g. PostgreSQL should really be: 'unreliable', because it does mean something. Rows are sorted in the inner query, and that order is kept in outer query levels unless instructed otherwise or reordering is opportune for additional operations. Even if that's just an implementation detail, it's not meaningless. This can be used for sorted input to aggregate functions. The manual even hints as much: Alternatively, supplying the input values from a sorted subquery will usually work. – Erwin Brandstetter Sep 13 '17 at 13:43
  • The quote you added for Postgres actually applies to a different case: queries with no ORDER BY at all. – Erwin Brandstetter Sep 13 '17 at 13:47
  • @ErwinBrandstetter: Feel free to add an answer with those details. I personally disagree that implementation details are meaningful. Just today, I've learned that in the old days, people relied on Oracle always performing a sorted group by operation in Oracle 8i (I believe), when suddenly, a newer version introduced hashed group by, which broke the assumption that some implicit ordering could be relied upon. In other words: I like to put it in bold words. Meaningless, rather than oh if you know the intricate details of version x.y.z, you can actually... – Lukas Eder Sep 14 '17 at 21:21
  • I already added an answer. Whether we chose to ignore non-standard behavior or what other good advice we have is beside the question: Is order guaranteed for the given query? It is for Postgres. It is not (or not even applicable) for other RDBMS. And that applies for all existing versions of Postgres, not just for version x.y.z. It's even documented (with reservations). Your quote is misleading. If we want to ignore non-standard behavior we might start with Oracle making us believe NULL and the empty string are the same. Also orthogonal to the question. – Erwin Brandstetter Sep 15 '17 at 0:39
  • @ErwinBrandstetter: Interesting, thanks for the update. Is this guarantee that you're referring to documented? – Lukas Eder Sep 19 '17 at 8:38
12

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.

  • When testing it on PostgreSQL, the sorting was done after a sequential scan as I didn't have any index on the column used by ORDER BY. Which RDBMS do you think will skip the inner query ORDER BY? – Vlad Mihalcea Aug 23 '17 at 9:52
  • 5
    I can't say I know any what will, just that they any and all are perfectly free to do so if they wish - it would be a perfectly acceptable optimisation according to both the general standards and the product specifications. SQL Server will reject the query outright (unless you include TOP 100% so the current query isn't portable, should that be a priority for your project. Because Postgres obeys the ordering in the inner query now does not imply it always will do in future (or that older versions do, in fact) so you should avoid relying on the behaviour just in case. – David Spillett Aug 23 '17 at 10:04
  • 1
    @VladMihalcea a DBMS that does "optimize away" the redundant ORDER BY is MariaDB: Why is ORDER BY in a FROM Subquery Ignored? – ypercubeᵀᴹ Sep 13 '17 at 16:13
6

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.

  • 2
    The one reason it may optimize the order by out is speed. Returning the rows in a different order may be more efficient. – TomTom Aug 23 '17 at 10:08
  • 2
    In particular, the server may exploit parallelism to read the table. If it does so, and there's no need to enforce an order, you'll get the rows back however the threads read them. (SQL Server actually does this, so that a SELECT with no ORDER BY truly is nondeterministic, and not just in theory or because data changed.) – Jeroen Mostert Aug 23 '17 at 17:54
  • @JeroenMostert: Undefined behavior only gets worse. What happens if it's out of order and the delta was used to index into an array? – Joshua Aug 24 '17 at 4:28
2

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 this particular 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.)

  • Is it true when the "table" is not a simple, base table but a complex view or a partitioned table? Is it true when the plan has parallel execution, too? Is it true in Postgres 10 as well? (I'm only asking, I'm not sure for the answer of any of these questions.) – ypercubeᵀᴹ Sep 13 '17 at 15:07
  • @ypercubeᵀᴹ: I have not tested Postgres 10 for all of these, but I am pretty sure it's true in any case. The order is applied and not changed in the outer query for the simple case. – Erwin Brandstetter Sep 13 '17 at 18:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.