How do databases implement SQL "ORDER BY x"?

Question

I wonder how they work under the hood, especially for large result sets. For example, can a database write the original result to disk and then perform an appearance?

I am also wondering how this works with LIMIT ... OFFSET. If the database cannot use the existing index, it seems that the database would have to sort it all out and tear out a subset of the original result set.

Answer 1

Indexes are ordered; if there is a suitable index to be used. Otherwise, they will have to be sorted as you think. The query execution plan (which you can get, for example, EXPLAIN or through the client’s menu , the exact way to get it depends on the DBMS) may contain hints about how the request will be sorted.

Cm:

• MySQL: ORDER optimization
• PostgreSQL: Indexes and ORDER BY
• SQL Server Indexes
• Oracle: Understanding Indexes

Answer 2

You may find this page interesting:

http://dev.mysql.com/doc/refman/5.6/en/order-by-optimization.html

Answer 3

mySQL shows its own order. Optimization on this link

Oracle shows the theoretical order in the algorithmic procedure here

Basically, if you have an index, it is ordered. But when you don't sort, this is O(n log n)

Answer 4

You are pretty much entitled to it. If nothing has been prepared or planned in advance (i.e. indexes or data previously prepared or cached earlier), then yes, all the data that needs to be taken into account to form the proper order should be read, and if the amount of data needs to be worked out, not can fit in available / allocated memory, then it will be necessary to perform disk caching.

This is a non-trivial performance issue, and each RDBMS will have smart ways to address and optimize it so that you use your product, and not that flabby “Brand X” with a knockout.