在 Oracle 中，进行排序操作时，会从私有内存（PGA）中分配一块工作区域（Work Area）用于排序操作，这块区域称为排序区（Sort Area）。如果排序区足够大，能容纳所有数据完成排序，那 么这种情况就是优化的（Optimal）排序操作。而如果排序无法容纳所有数据一次性完成排序操作， 那么 Oracle 就要将数据分批放入内存中进行排序，这一过程称为初始化运行（Initial Run）；并将
排序好的数据写入临时空间（Temporary Space）上、以释放内存进行下一批数据的排序；所有数据都被分批写入临时磁盘后，每一批数据本身都是已排序的，接下来就需要将这些已排序的分组数据进行合并排序（Merge Sort），使得所有数据最终成为有序数据。
因此，根据排序操作是否需要通过写入磁盘完成、已经写入次数（或者合并次数）不同，排序
操作的代价估算也不同。
6.8.1 是否需要写入磁盘
判断是否需要写入磁盘的原则实际上比较简单，由排序区大小和需要写入排序区的数据大小决 定：如果排序区大小比排序区的数据量小，就需要写入磁盘；否则不需要。
o 排序区大小（Sort Area Size，SASIZE）和排序区的最大大小（Sort Area Maximum Size， SAMSIZE）
从 10g 开始，Oracle 的私有内存在默认情况下是自动管理，而其中的工作区（包括排序区和哈希区）大小默认也是由 Oracle 自动管理————由参数 workarea_size_policy 决定：AUTO（默认） 为自动管理；MANUAL 为手动管理。
• 自动管理策略下，排序区的大小由隐含参数"_smm_min_size"决定、排序区的最大大小 由隐含参数"_smm_max_size"决定（SMM = SQL Memory Manager）；
提示：这两个参数不仅是优化器进行代价估算时采用的参数，也同时是运行时态的决定参数。
• 手动管理策略下，排序区的大小由参数 sort_area_retained_size 和 sort_area_size 决定， 并且最大大小就是排序区的大小；
o 排序数据大小（Sort Data Size，SDSIZE）
排序数据大小则由需要排序的记录数（Sort Rows Number，SROWNUM）和排序记录长度（Sort Columns Size，SROWSIZE）决定，即：
SDSIZE = SROWNUM*SROWSIZE
o 排序的记录数（SROWNUM）就是由排序的子操作所返回的记录数；
排序记录长度（SROWSIZE）则由所有与排序操作相关的非重复字段（如 SELECT 中的字段和ORDER BY 中的字段）平均长度（Average Column Length，ACL）总和（我们称为原始记录长度， Raw Row Size，RROWSIZE）决定，但是这一长度不能超过表记录的平均长度（Average Row Length， AVGRLEN）；
RROWSIZE = LEAST(AVGRLEN, SUM(ACL1~n))
而当记录被载入内存进行排序时，还需要加上 ROWID（10 字节）和其它额外信息（原始记录长度每增加 10 字节需要增加一个额外字节），因此其计算公式如下：
SROWSIZE = RROWSIZE + 10 + CEIL(RROWSIZE/10)
o 是否写入磁盘的判断
有了排序区大小（SASIZE）和排序数据大小（SDSIZE）后，优化器就很容易判断是否需要写数 据到临时磁盘了：
如果 SDSIZE > SASIZE 则需要写入磁盘。
6.8.2 IO 代价计算
但排序操作是优化的，即无需写入磁盘，则 IO 代价为 0。否则 IO 代价由需要排序的数据块数
（Blocks to Sort，SORTBLKS）、合并传输次数（Merge passes，MERGES）以及每次合并需要读写临时磁盘次数（IO Cost per pass，PASSIO）决定。在 IO 代价模型和 CPU 代价模型下，计算方式稍有不同。
o 排序宽度（Sort Width，SORTWIDTH）
排序宽度也称为合并宽度。在进行合并操作时，需要将两组或者多组已排序数据载入内存，然 后进行合并。而内存可以容纳最大数据组数则成为排序宽度。排序宽度的计算公式如下：
SORTWIDTH = FLOOR((SAMSIZE-((60SAMSIZE/1024/320-40(SAMSIZE/1024/320- 1))+LOG(2,MBDRC)*80)*1024)/((SAMINIO+OPTBLKSIZE)*2.5))
其中，
• SAMSIZE 为排序区的最大大小；
• SAMINIO 为直接读写的最小字节数（由参数"_smm_auto_min_io_size"决定）；
• MBDRC 多数据块直接读写的数据块数，由直接读写的最小字节数和优化器采用的数据块大小（_optimizer_block_size，OPTBLKSIZE）决定。
MBDRC = SAMINIO/OPTBLKSIZE
提示：在 IO 代价模型下，排序宽度需要除以 2：
SORTWIDTH[IO Cost Model] = FLOOR(((SAMSIZE-((60SAMSIZE/320-40(SAMSIZE/320- 1))+LOG(2,MBDRC)*80)*1024)/((SAMINIO+OPTBLKSIZE)*2.5))/2)
o 初始运行次数（Initial Runs，INTRUNS）
数据放入排序区进行排序，就是初始运行。当排序区能够容纳所有数据完成排序操作时，初始化运行次数为 1；否则由排序数据大小（SDSIZE）和排序区最大大小（SAMSIZE）共同决定，并且最少为 2 次：
INTRUNS = GREATEST(CEIL(SDSIZE/SAMSIZE), 2)
记住，初始运行次数也就决定了完成所有初始化运行后，会形成多少组已排序数据。
o 合并传输次数（MERGES）
当数据被分组写入磁盘后，需要被再次读入内存中进行合并排序操作。初始运行次数决定了数据组数；排序宽度则决定了每次最多可以合并多少组数据。因此，合并传输次数的计算就是以排序 宽度为底，对初始运行次数取对数。
MERGES = CEIL(LOG(SORTWIDTH,INIRUNS))
o 排序数据块数（SORTBLKS）
如果数据需要被写入临时空间，则数据会被组织成一个个数据块进行直接读写磁盘。并且，根 据设置，通常是多数据块读写。在数据被组织成数据块时，每个数据块头部都需要有 24 字节的空间存放相关元数据信息。因此，数据块数的估算公式如下：
SORTBLKS = CEIL(SDSIZE/(OPTBLKSIZE-24))
o 磁盘传输 IO 代价（PASSIO）
在将数据写入临时磁盘时，是以多数据块读写的方式进行，每次读写的数据块数（MBDRC）由 最小读写字节数决定，其计算公式在上节已经给出。而每次传输的 IO 代价的估算公式如下：
PASSIO = CEIL(SORTBLKS*(MBDRC*MREADTIM/SREADTIM)/(MBDRC+1)/(MBRC-1))2 +
CEIL(SORTBLKS(MBRC-1-MBDRC)/(MBDRC+1)/(MBRC-1))*2
其中，
• SORTBLKS 为排序数据块数；
• MBDRC 为读数据块直接读写的数据块数；
• MBRC 为多数据块读的数据块数，其计算方式和前面章节中相同：根据系统统计数据及其收集方式不同而不同；
• MREADTIM 为多数据块读时间，其计算方式和前面章节中相同；
• SREADTIM 为单数据块读时间，其计算方式和前面章节中相同。
提示：一次传输包括一次写和一次读，因此在公式中要乘以 2.
o IO 代价计算公式
有了排序数据块数、合并传输次数以及每次传输的 IO 代价后，排序操作的总的 IO 代价就可以用以下公式计算得出：
IOCOST[Sort] = SORTBLKS + (PASSIO * MERGES))
在 IO 代价模型中，IO 代价需要除以 2：
IOCOST[Sort in IO Cost Model] = CEIL((SORTBLKS + (PASSIO * MERGES)))/2)
6.8.3 CPU 代价计算
排序所需要消耗的 CPU 指令，主要包含两个部分：数据块读写和数据记录的比较。
CPUCYCLES[Sort] = BLKCYCLES + ROWCYCLES + SREADTIMCPUSPEED1000
其中，
• BLKCYCLES 为数据块读写指令数，计算公式如下
BLKCYCLES = (1+MERGES) * SORTBLKS * RTBCYCLES
其中 RTBCYCLES 为读取一个临时数据块的 CPU 指令数：
RTBCYCLES = OPTBLKSIZE1.5+ 200(1 - MBDRC/(MBDRC+1))
• ROWCYCLES 数据记录比较的指令数。在 10g 中，Oracle 引入了一种新的排序算法，该算法是快速排序和基数排序的混合算法，其时间复杂度为 NLog(N)。此外，合并排序的时间复杂度也为 NLog(N)。因此，ROWCYCLES 的计算公式如下，
ROWCYCLES = ROUND(CMPCYCLESSROWNUMLOG(10,SROWNUM))
其中 CMPCYCLES 为每次比较所需要消耗的 CPU 指令数：
CMPCYCLES = (1-0.002213)*150 ≈ 149.668
o 临时磁盘空间（TMPSPACE）
当排序需要通过写入临时磁盘来完成时，优化器还需要估算出其占用的临时空间大小。估算公 式如下，
TMPSPACE = ROUND((25000/8192+(CEIL(SROWNUM/ROWSPENTRY)- 1)*2)*OPTBLKSIZE/1000)*1000
其中，
• SROWNUM 为排序记录行数；
• OPTBLKSIZE 为优化器采用的数据块大小；
• ROWSPENTRY 为每个临时数据块中容纳的数据行数：
ROWSPENTRY = ROUND((OPTBLKSIZE-24-8CEIL(ROWWIDTH/4))/(8+ROWWIDTH4))
其中，ROWWIDTH 为数据记录宽度：
ROWWIDTH = (CEIL(GREATEST(RROWSIZE-2,0)/4)-1)+CEIL((COLNUM+1)/2)
6.8.4 排序代价计算演示
我们通过以下语句来演示排序代价的估算：
o 系统参数
首先，我们需要获取相关系统参数设置，以决定代价计算方式已经计算公式中的某些因子的数值：
注意，其中_smm_auto_min_io_size、_smm_min_size 和_smm_max_size 的单位为 K。计算公式中的部分因子数值由上述结果得到：
SASIZE = 204*1024 = 208896
SMASIZE = 409601024 = 41943040 SAMINIO = 561024 = 57344 OPTBLKSIZE = 8192
o 系统统计数据
获取系统统计数据，以便随后计算 IO 代价及 CPU 想 IO 代价的转换关系：
o 对象统计数据
首先获取表的相关统计数据：
还要获取字段的相关统计数据：
o 排序数据大小（Sort Data Size，SDSIZE）
计算排序数据大小需要知道排序的数据记录数（SROWNUM）和排序记录长度（SROWSIZE）：
• 我们这里的查询语句没有增加任何过滤条件，因此排序记录数就是表的记录数；
SROWNUM = 47585
• 语句需要返回表 T_OBJECTS 的所有字段，因此 ORDER BY 子句中的字段为重复字段，不再被计算。而表的所有字段平均长度之和为 129，大于数据记录的平均长度（123），因此原始数据记录长度为：
RROWSIZE = LEAST(AVGRLEN, SUM(ACL1~n))
= LEAST(129, 123)
= 123
• 相应的，排序记录长度为：
SROWSIZE = RROWSIZE + 10 + CEIL(RROWSIZE/10)
= 123 + 10 + CEIL(123/10)
= 146
由上述数据就可以计算得出排序数据大小，即：
SDSIZE = SROWNUM * SROWSIZE
= 47585 * 146
= 6947410
o 是否需要写入磁盘
由于排序区大小（SASIZE）为 208896，小于排序数据大小（6947410），因此，这一排序操作需要将数据写入临时磁盘完成操作。
o 多数据块直接读写数据块数（MBDRC）
多数据块直接读写数据块数由直接读写的最小字节数（SAMINIO）和优化器采用的数据块大小 决定：
MBDRC = SAMINIO/OPTBLKSIZE
= 57344/8192
= 7
o 排序宽度（SORTWIDTH）
排序宽度计算公式中所有因子的数值目前都已获得，因此我们可以计算得出排序宽度为：
SORTWIDTH = FLOOR((SAMSIZE-((60SAMSIZE/1024/320-40(SAMSIZE/1024/320- 1))+LOG(2,MBDRC)*80)1024)/((SAMINIO+OPTBLKSIZE)2.5))
= FLOOR((41943040-((6041943040/1024/320-40(41943040/1024/320- 1))+LOG(2,7)*80)*1024)/((57344+8192)*2.5))
= 238
o 初始运行次数（Initial Runs，INTRUNS）
计算初始运行次数所需的所有因子数值都已获取：
INTRUNS = GREATEST(CEIL(SDSIZE/SAMSIZE), 2)
= GREATEST(CEIL(6947410/41943040), 2)
= 2
o 合并传输次数（MERGES）
有了排序宽度和初始运行次数后，就可以计算出合并传输次数：
MERGES = CEIL(LOG(SORTWIDTH, INIRUNS))
= CEIL(LOG(238, 2))
= 1
o 排序数据块数（SORTBLKS）
排序数据块数由排序数据大小决定：
SORTBLKS = CEIL(SDSIZE/(OPTBLKSIZE-24))
= CEIL(6947410/(8192-24))
= 851
o 磁盘传输 IO 代价（PASSIO）
计算磁盘传输 IO 代价时，需要系统统计数据。根据我们的查询结果，当前的系统统计数据是在负载模式下获得，相应数据可以从系统统计数据种中直接获得：
PASSIO = CEIL(SORTBLKS*(MBDRCMREADTIM/SREADTIM)/(MBDRC+1)/(MBRC-1))2 + CEIL(SORTBLKS(MBRC-1-MBDRC)/(MBDRC+1)/(MBRC-1))2
= CEIL(851(732/8)/(7+1)/(8-1))2 + CEIL(851(8-1-7)/(7+1)/(8-1))2
= 852
o IO 代价计算（IOCOST）
有了上述数据后，排序操作的总的 IO 代价就可以用以下公式计算得出：
IOCOST[Sort] = SORTBLKS + (PASSIO * MERGES))
= 851 + 1852
= 1703
o CPU 总指令数计算
要计算排序的 CPU 总指令数，需要计算出两个部分数据：数据块读写和数据记录的比较。
数据块读写 CPU 指令数
依据数据块读写 CPU 指令数的计算公式，计算出其结果为：
BLKCYCLES = (1+MERGES)SORTBLKS * RTBCYCLES
= (1+MERGES)SORTBLKS * (OPTBLKSIZE1.5+ 200(1 - (SAMINIO/OPTBLKSIZE)/(SAMINIO/OPTBLKSIZE+1)))
= (1+1)851 * (81921.5+200*(1-7/(7+1)))
= 20956726
数据记录比较 CPU 指令数
该数值由排序的时间复杂度决定：
ROWCYCLES = ROUND(CMPCYCLESSROWNUMLOG(10,SROWNUM))
= ROUND((1-0.002213)15047585LOG(10,47585))
= 33312727
总的 CPU 指令数为：
#CPUCYCLES[Sort] = BLKCYCLES + ROWCYCLES + 81000*1000
= 20956726 + 33312727 + 8000000
= 62269453
o 临时磁盘空间（TMPSPACE）
要估算出临时磁盘空间大小，需要先计算出数据记录宽度（ROWWIDTH）和临时数据块中的记 录行数（ROWSPENTRY）。
数据记录宽度的计算：
ROWWIDTH = (CEIL(GREATEST(RROWSIZE-2)/4,1)-1)+CEIL((COLNUM+1)/2)
= (CEIL(GREATEST(123-2,0)/4)-1)+CEIL((15+1)/2)
= 38
临时数据块中的记录行数的计算：
ROWSPENTRY = ROUND((OPTBLKSIZE-24-8CEIL(ROWWIDTH/4))/(8+ROWWIDTH4))
= ROUND((8192-24-8CEIL(38/4))/(8+384))
= 51
由上述数据就可以估算出临时磁盘空间大小：
TMPSPACE = ROUND((25000/8192+(CEIL(SROWNUM/ROWSPENTRY)- 1)*2)*OPTBLKSIZE/1000)*1000
= ROUND((25000/8192+(CEIL(47585/51)-1)*2)*8192/1000)*1000
= 15311000
o 计算结果与实际结果的比较
我们可以从 10053 事件跟踪文件中获得优化器估算出排序代价及相关计算数值。我们依据估算公式计算出的结果与实际结果基本一致：
读者可以参考上例的优化器跟踪文件“06_93_10053_SORT_DEMO.trc”。
