Why does Max() create an order by in the explain plan?

Question

When I attempt to do something like

SELECT Max(ObjectId) FROM Objects;

I see that in the explain-plan that this is performed by doing a sort. Now, sorting (which I guess would require something in the complexity of O(nlogn)) must be much costlier than just scanning each row and remembering the max value (which could be done in O(n)).

Am I missing something here? Is oracle really performing a sort or does the explain-plan just use the description "sort" for describing a simple scan of all values in the ObjectId column? If oracle really does perform a "real sort", is there a good reason for doing this that I am missing?

Thanks in advance!

Answer 1

Hi wasatz,

since you have not posted details about your table Objects we will have to guess. My guess is that you have an index on ObjectId. In that case you will see a INDEX FULL SCAN (MIN/MAX) step in the explain plan, meaning that the data will be retrieved directly from the index. The keys are ordered in an index so reading the first or last key gives you the MIN/MAX.

This is an O(log n) operation (since it depends upon the depth of the index).

Update:

If you don't have an index on ObjectId you will see a SORT AGGREGATE step in the explain plan. This doesn't mean that the entire set will be sorted. In fact the data will be aggregated as it is read. This will likely involve a single comparison for each row, giving you a total O(n) cost.

Also on a related note, Oracle probably uses O(n) algorithms to sort data.