Sort V1 und V2

Nachdem ich zuletzt mehrfach über allerlei Effekte im Zusammenhang von Sortierungen geschrieben habe, hier mal ein paar Überlegungen zum (inzwischen nicht mehr ganz so) neuen Sortierverfahren V2. Zum alten Mechanismus insertion sort (V1) hat Jonathan Lewis in seinem cbo-Buch und in seinem Blog allerlei geschrieben. Grundsätzlich wird bei diesem Verfahren intern ein B*Baum gefüllt:

The problem with the V1 sort is that the “sorting” mechanism works by building a balanced binary index as it reads the data. Although the implementation is made a little more complicated by the complexities of dynamic memory allocation the basic mechanism simply stacks your unsorted data at one end of the workarea memory while dynamically maintaining an index into that data at the other end of the workarea.

Über den V2-Mechanismus schreibt Jonathan Lewis auch einiges, aber das dahinter stehende Verfahren ist für mich weniger klar erkennbar. Auch Joze Senegacniks Präsentation zum PGA-Management enthält ein paar Hinweise, aber keine umfassende Erklärung des neuen Verfahrens - aber auch Jonathan Lewis Erklärungen zum V1-Verfahren basierten auf Tests und möglicherweise werden die internen Details von V2 auch durch Tests nicht ganz klar.

Mir genügt an dieser Stelle eine phänomenologische Betrachtung der Verfahren und ihrer Leistungsfähigkeit. Dazu folgender Test:

create table test_sort
as
select rownum rn
     , mod(rownum , 10) col1
     , lpad('*', 50, '*') col2
  from dual
connect by level < 1000000;

exec dbms_stats.gather_table_stats (ownname=>user, tabname=>'test_sort')

create index test_sort_v2_idx on test_sort(col2, col1, rn);

Index wurde erstellt.

-- Abgelaufen: 00:00:08.50

drop index test_sort_v2_idx;

alter session set "_newsort_enabled"=false;

create index test_sort_v1_idx on test_sort(col2, col1, rn);

Index wurde erstellt.

-- Abgelaufen: 00:00:16.50

Mit V2 lief die Indexerzeugung demnach in der halben Zeit. Aber etwas mehr kann man dazu dann vermutlich doch noch sagen. Aus v$sesstat kann ich in diesem Fall nicht besonders viel ableiten:

NAME                                              V2        V1     Diff
-----------------------------------------------------------------------
file io wait time                             187373      9513  -177860
session logical reads                          25270     22605    -2665
sorts (memory)                                    57         5      -52
sorts (rows)                                 1000050   1000002      -48
sorts (disk)                                       0         1        1
workarea executions - onepass                      0         2        2
DB time                                          850      1651      801
physical reads direct temporary tablespace         0      9893     9893
physical writes direct temporary tablespace        0      9893     9893
physical read total bytes                     221184  81043456 80822272
physical write total bytes                  80805888 161849344 81043456

Die Event-Auswahl ist eher willkürlich, deutlich wird nur, dass die V1-Operation (bei sonst gleichen Session-Settings und in einer sonst ungenutzten Instanz) eine Sortierung auf die Platte verschieben muss. Deshalb noch ein 10032-Trace zum Thema:

alter session set events '10032 trace name context forever, level 1'; 

-- V2
---- Sort Statistics ------------------------------
Input records                             999999
Output records                            999999
Total number of comparisons performed     9841519
  Comparisons performed by in-memory sort 9841519
Total amount of memory used               91718656
Uses version 2 sort
---- End of Sort Statistics -----------------------

-- V1
---- Sort Statistics ------------------------------
Initial runs                              4
Number of merges                          1
Input records                             999999
Output records                            999999
Disk blocks 1st pass                      9893
Total disk blocks used                    9895
Total number of comparisons performed     19891137
  Comparisons performed by in-memory sort 18667731
  Comparisons performed during merge      1223406
Temp segments allocated                   1
Extents allocated                         78
Uses version 1 sort
Uses asynchronous IO
    ---- Run Directory Statistics ----
Run directory block reads (buffer cache)  5
Block pins (for run directory)            1
Block repins (for run directory)          4
    ---- Direct Write Statistics -----
Write slot size                           253952
Write slots used during in-memory sort    4
Number of direct writes                   321
Num blocks written (with direct write)    9893
Block pins (for sort records)             9893
Cached block repins (for sort records)    3
Waits for async writes                    301
    ---- Direct Read Statistics ------
Size of read slots for output             57344
Number of read slots for output           21
Number of direct sync reads               266
Number of blocks read synchronously       290
Number of direct async reads              1427
Number of blocks read asynchronously      9603
Waits for async reads                     314
---- End of Sort Statistics -----------------------

Die Statistiken für die V2-Sortierung vergleichsweise übersichtlich - möglicherweise wäre da ein höheres Trace-Level aussagekräftiger. Deutlich wird eigentlich nur, dass V2 deutlich weniger Vergleiche durchführt (10M statt 20M) und dass für V2 in diesem Fall keine onepass-Operation erforderlich ist. Aber in jedem Fall ist V2 offenbar sehr viel effektiver als V1 - und das genügt mir für den Moment...