Oracle 10g Sorting

[Moozik: The Mission - Naked and Savage]

You can never really guarantee the order in which your results will return to you unless you use an order by clause. Nothing earth shattering there. Except that in versions prior to 10.2, Oracle was quite happy to let you get away with just a group by. 10.2 changed all that as a new sorting algorithm was introduced.

Oracle introduced a new sorting algorithm (sometimes known as the Version 2 sort, which is how it is labelled in the 10032 trace) in 10.2.

The previous algorithm was effectively building an in-memory index on the incoming data using a balanced binary tree and seeking to the right (i.e. optimised towards data that appeared in the correct order and keeping such data in the order of appearance - hence the apparent sorting of rowids in our example in 9i).

The CPU and memory overheads for this algorithm are a bit fierce for large sorts, so the new algorithm does something completely different (possibly based on a variant of the heapsort, though it isn’t actually a heapsort) which is more efficient on memory and CPU. It has the side-effect though, of re-ordering incoming rows even when the data is not arriving out of order.