Oracle的排序

[English]

作者： fuyuncat

来源： www.HelloDBA.com

日期： 2010-03-18 03:17:15

分享到 

排序(sort)算法        在Oracle的排序过程中，首先将获取到的数据放入一块私有内存区（Sort Area）中进行排序。如果需要排序的数据太大，无法一次在Sort Area中完成全部数据的排序，就会将Sort Area中排好序的数据直接写入（Direct Write，数据不被cache）临时空间作为一个数据集存在。当所有数据都在内存中排过序并写入了磁盘后，就会将磁盘上的数据集进行合并排序（Merge Sort）。合并排序是一个递归过程，直到所有数据集都被合入一个数据集，排序才算完成。   初始化运行（Initial Runs）     数据最初在Sort Area中排序的过程被称为初始化运行。Sort Area的80~90%的空间需要被用于读缓冲，其他空间则被用于写缓冲。如果我们知道有多少数据（可以通过需要排序的记录数、记录平均长度已经数据块大小估算出来）需要进行排序，那么就可以用下面的公式来估算初始化运行的次数（也就是会产生多少个初始数据集），     Initial Runs = CEIL(SORT_DATA_BLOKCS/ROUND(0.8*SORT_AREA_SIZE/BLOCK_SIZE)) 合并（Merges）     在进行合并时，可以同时合并2个或2个以上的数据集。一次合并多少个数据集就称为合并宽度（Merge Width）。合并也是在Sort Area中完成的，进行合并之前，需要将数据从磁盘直接读入（Direct Read）内存中。和全表扫描的多数据块读（MBRC）类似，对排序数据块的读取也可以是多个的，由sort_multiblock_read_count（SMRC，这个参数在9i后是隐含参数）控制一次读取的数据块数。不过，请注意，这个参数控制的是一次能读取的最大数据块数，而实际上一次能读取的数据块数是由sort_area_size、数据块大小等数据计算得来的。要进行合并操作，最少需要夺取2个数据集；如果使用了异步IO（disk_asynch_io=TRUE），需要有2块读缓冲。因此实际的SMRC可以按照以下公式计算：     SMRC = MIN(ROUND(SORT_AREA_SIZE/(2*2*BLOCK_SIZE))-1, _sort_multiblock_read_count)     有了SMRC，合并宽度也可以计算出来了，     merge width = ROUND(SORT_AREA_SIZE/(2*SMRC*BLOCK_SIZE))-1    合并是个递归过程，直到所有数据集被合为一个数据集。每一轮合并过程中，如果还有少于合并宽度的数据集没有被合并，则会在下一轮中再进行合并。我们创建了以下函数来计算合并次数。     注意：除最后一次合并外，所有合并都被称为中间运行（Intermediate run）。 SQL代码 HELLODBA.COM>create or replace function sort_merges(init_runs number, width number)      2  return number      3  as     4   i number:=init_runs;      5   n number:=0;      6  begin     7    while i>width loop      8      n := n+floor(i/width);      9      i := floor(i/width)+ mod(i,width);     10    end loop;     11    if i > 0 then    12      n := n+1;     13    end if;     14    return n;     15  end;     16  /       Function created.        我们来看一个例子：sort area大小为64k，估算到有721个数据块需要进行排序，数据块大小为8K。通过以下查询语句，我们就可以得到这次排序的相关统计数据。 SQL代码 HELLODBA.COM>select init_runs,SMRC,merge_width,sort_merges(init_runs,merge_width) merges from     2  (select init_runs,      3         SMRC,      4         round(sort_area_size / (2 * SMRC * block_size), 0) - 1 as merge_width      5    from (select sort_blocks, sort_area_size, block_size, ceil(sort_blocks / round(0.8 * sort_area_size / block_size, 0)) init_runs,      6                 round(sort_area_size / (2 * 2 * block_size), 0) - 1 SMRC      7            from (select 721 as sort_blocks, 65536 as sort_area_size, 8192 as block_size from dual)));        INIT_RUNS       SMRC MERGE_WIDTH     MERGES    ---------- ---------- ----------- ----------           121          1           3         60       1 row selected.    新的排序算法     从10gR2之后，oracle引入了新的排序算法以减少排序时内存和CPU的消耗。新算法由参数"_new_sort"控制，默认为TRUE。新算法在以下几个方面进行了改进。   *内存排序     对于那些仅需要在内存中就可以完成的小数据集的排序，新算法需要更少的内存   *合并排序     初始化运行完成后，会保存初始数据集的键值到内存中，在进行数据集进行合并时，会根据键值来选择数据集。从trace文件中可以看到一条新的统计数据：        Comparisons while searching for key in-memory 120     新算法过程中，合并过程中用到的临时数据块更容易被重用，节省磁盘空间 Trace     我们可以通过10031, 10032, 10033事件对排序过程进行跟踪，跟踪内容可以帮助我们更好的理解排序过程及其性能。下面的跟踪文件就是我们之前例子的产生的。 SQL代码 Recording run at 401ca9 for 6 blocks    Recording run at 401cb0 for 6 blocks    Recording run at 401cb6 for 6 blocks    Recording run at 401d3c for 6 blocks    Recording run at 401d42 for 6 blocks    Recording run at 401d48 for 6 blocks    ...    ---- Sort Parameters ------------------------------    sort_area_size                    65536    sort_area_retained_size           65536    sort_multiblock_read_count        1    max intermediate merge width      3    Merging run at 401d1a for 1 blocks    Merging run at 401c3a for 6 blocks    Total number of blocks to read: 7 blocks    Recording run at 401d1b for 7 blocks    Merging run at 401c40 for 6 blocks    Merging run at 401c46 for 6 blocks    Merging run at 401c5c for 6 blocks    Total number of blocks to read: 18 blocks    Recording run at 401d22 for 17 blocks    ...    ---- Sort Statistics ------------------------------    Initial runs                              121    Intermediate runs                         59    Number of merges                          60    Input records                             47582    Output records                            47582    Disk blocks 1st pass                      721    Total disk blocks used                    896    Total number of comparisons performed     651813      Comparisons performed by in-memory sort 320660      Comparisons performed during merge      331033      Comparisons while searching for key in-memory 120    Temp segments allocated                   1    Extents allocated                         56    Uses version 2 sort    Uses asynchronous IO        ---- Run Directory Statistics ----    Run directory block reads (buffer cache)  240    Block pins (for run directory)            1    Block repins (for run directory)          239        ---- Direct Write Statistics -----    Write slot size                           8192    Write slots used during in-memory sort    2    Number of direct writes                   2884    Num blocks written (with direct write)    2884    Block pins (for sort records)             2884    Waits for async writes                    1731        ---- Direct Read Statistics ------    Size of read slots for merge phase        8192    Number of read slots for merge phase      6    Size of read slots for output             8192    Number of read slots for output           8    Number of direct sync reads               1498    Number of blocks read synchronously       1498    Number of direct async reads              1386    Number of blocks read asynchronously      1386    Waits for async reads                     347    ---- End of Sort Statistics -----------------------       --- Fuyuncat ---