ASA SQL User's Guide
Query Optimization and Execution
Query execution algorithms
Sorting and unions
The sort operator reads its input into memory, sorts it in memory, and then outputs the sorted results. If the input does not completely fit into memory, then several sorted runs are created and then merged together. Sort does not return any rows until it has read all of the input rows. Sort locks its input rows.
If the merge sort algorithm executes in an environment where there is very little cache memory available, it may not be able to complete. In this case, the merge sort orders the remainder of the input using an indexed-based sort method. Input rows are read and inserted into a work table, and an index is built on the ordering columns of the work table. In this case, rows are read from the work table using a complex index scan. This indexed-based strategy is significantly slower than other join methods. The optimizer avoids generating access plans using a merge sort algorithm if it detects that a low memory situation may occur during query execution. When the index-based strategy is needed due to low memory, a performance counter is incremented; you can read this monitor with the QueryLowMemoryStrategy property, or in the "Query: Low Memory Strategies" counter in Windows Performance Monitor.
Sort performance is affected by the size of the sort key, the row size, and the total size of the input. For large rows, it may be cheaper to use a VALUES SENSITIVE cursor. In that case, columns in the SELECT list are not copied into the work tables used by the sort. While the sort does not write output rows to a work table, the results of the wort must be materialized before rows are returned to the application. If necessary, the optimizer adds a work table to ensure this.