Query Engines and Performance
A SQL query describes the result set but does not specify the particular steps or algorithms used for generating the results. This allows the SQL optimizer to produce the best query plan—at least in theory.
By contrast, most computer languages are procedural. A command that says “sort the data” generally implements a particular algorithm for the sort—bubble sort, merge sort, quicksort, or perhaps some fancy parallel out-of-memory sort. The SQL statement ORDER BY simply says that the result set will be in a particular order. The statement does not specify exactly how that should be done. And, different databases take different approaches. For instance, in SQL Server, if the statement accesses only a single table and the ORDER BY key is the clustered index for the table, then an additional sorting step is generally unnecessary.
This section starts by introducing “order notation” from computer science as a way of characterizing...