How do databases implement SQL 'ORDER BY x'?

I'm wondering how these work under the hood, especially for large result sets. For example, would the DB likely write the raw result to disk and then do an external sort?

I'm also wondering how this works with LIMIT...OFFSET. If the DB can't utilize an existing index it seems like the DB would have to sort the whole thing and pluck the subset of the开发者_开发百科 raw result set.

Indexes are ordered; if there's a suitable index, that will be used. Otherwise, they'll need to sort, as you suppose. The execution plan for a query (which you can get with e.g. EXPLAIN or via client menus; the exact method of getting it varies with the DBMS) may contain hints as to how a query will be sorted.

See:

1. MySQL: ORDER BY Optimization
2. PostgreSQL: Indexes and ORDER BY
3. SQL Server Indexes
4. Oracle: Understanding Indexes

mySQL shows their own Order By optimization on this link

Oracle shows theor own Order By algorithm procedure here

Basically, If you have an index, it is ordered. But when you don't sorting occurs which is O(n log n)

You pretty much have the right of it. If nothing has been prepared or pre-planned (i.e. indexes, or data otherwise previously prepared or cached), then yes, all the data that must be considered in order to generate the proper order must be read, and if the amount of data to be worked over cannot fit in available/allocated memory, then disk caching will need to be done.

It's a non-trivial performance issue, and every RDBMS will have clever ways to address and optimize it, so that you'll use their product and not that shoddy "Brand X" knock-off.