Buffer Sorts

In an earlier article I mentioned the buffer sort in a footnote; I thought I would expand a little more on what I think it does and why it appears as a buffer sort in an execution plan rather than the more traditional sort (join).

Consider the trivial script:

execute dbms_random.seed(0)          

create table t1
as
select	trunc(dbms_random.value(1,4))	n1
from	all_objects
where	rownum <= 10
;         

--  gather table stats at this point         

alter session set events '10032 trace name context forever';         

select
	ta.n1, tb.n1
from
	t1	ta,
	t1	tb
;         

alter session set events '10032 trace name context off'         

--------------------------------------------------------------------
| Id  | Operation            |  Name       | Rows  | Bytes | Cost  |
--------------------------------------------------------------------
|   0 | SELECT STATEMENT     |             |   100 |   600 |    22 |
|   1 |  MERGE JOIN CARTESIAN|             |   100 |   600 |    22 |
|   2 |   TABLE ACCESS FULL  | T1          |    10 |    30 |     2 |
|   3 |   BUFFER SORT        |             |    10 |    30 |    20 |
|   4 |    TABLE ACCESS FULL | T1          |    10 |    30 |     2 |
--------------------------------------------------------------------         

If you run the query you will find that the generated data is a random collection of 1s, 2s, and 3s – and there is no obvious sorted order in the output. Despite an apparent “sort” in the execution plan, the 100 rows generated by the Cartesian (everything to everything) join have not been sorted in any way.

I believe the operation at line 3 is labelled a buffer sort to give you a clue that it’s using the buffering mechanism of a traditional sort but not really doing a sort. And, of course, you don’t actually need a sort as you are simply buffering the data to avoid multiple tablescans against real data blocks.

You can confirm that there is no real sort by using the 10032 trace (one of the sort traces) as I have done. The output is shown below:

---- Sort Statistics ------------------------------
Input records                             10
Output records                            10
Total number of comparisons performed     9
  Comparisons performed by in-memory sort 9
Total amount of memory used               8192

The indications from the 10032 trace for this example are that Oracle is “comparing” rows as it reads them. But when you examine the output it isn’t doing anything with those comparison – the data doesn’t get ordered. Moreover, if you simply select the 10 rows from t1, you can see that it would take more than 9 comparisons to sort the rows into order.

So buffer sort is using the buffering mechanism of a sort but not doing the entire sort itself.

Footnote: if you run this test on 8i, you would see a sort (join) in the execution plan – but the 10032 shows that even in 8i, the sort isn’t really sorting.

Addendum (Aug 2008)

The execution plan shown above is from 9i, and the cost of 20 in the buffer sort line comes from multiplying the cost of doing the sort once by 10 – because of the cardinality of 10 reported for the first table. This is an arithmetic error that has been fixed in 10g – which means you are much more likely to see plans in 10g that make use of this buffer sort / merge strategy.

[More on Buffer Sorts]