CBO全表扫描代价计算公式推导(1)

[English]

作者： fuyuncat

来源： www.HelloDBA.com

日期： 2009-08-01 15:03:37

分享到 

1.   前言 CBO是一种相对更加精确的优化器，它在选择访问路径时能够更多的考虑一些客观因素，得出更加合理的查询计划。但是，Oracle并没有给出完整的代价计算公式，所以我们并不清楚这些因素在整个代价中到底产生多大的影响，或者在尝试调整一些参数时，也没有可依靠的理论公式。不过，Oracle提供了对CBO的Trace方法和输出。这对于我们来说相当于是个“黑盒子”，我们可以向黑盒子输入一些数据，黑盒子会输出结果。 很多人可能都做过一些IQ测试题，其中一种很典型的题型就是给出一组数字，但是中间缺1、2个，让你通过观察出这一组数字的规律来补充出缺少的数字。比如，一组数字1、2、？、5、8、？、21，通过观察，可以对这组数字得出一个这样的规律Xn = Xn-1 + Xn-2，根据这个规律，可以得出两个缺失的数字分别是3、13。 那么我们是否可以由黑盒子的输入、输出来尝试推导出黑盒子里到底如何运算的呢？ 2.   背景 Oracle的CBO是基于代价的，因此、查询计划的代价计算就是CBO的核心。通过Oracle Concept以及很多相关文档，我们了解到查询计划的代价和许多因素相关。例如hwm下的数据块数量、表的记录数、字段的唯一值数、索引的高度、主机的CPU处理能力等等。在Metalink上，我们也能找到Oracle给出的一个COST计算公式：       Cost = (                #SRds * sreadtim +                #MRds * mreadtim +                #CPUCycles / cpuspeed           ) / sreadtim   对其中因子的解释是： #SRDS：单数据块读的次数； #MRDS：多数据块读的次数； SREADTIM：一次单数据块读的时间； MREADTIM：一次多数据块读的时间； #CPUCYCLES：完成查询所需要发出的CPU指令数 CPUSPEED：CPU的处理速度   但是，这个公式还不足以帮助我们计算出一个查询计划的代价，因为你可以发现，除了CPUSPEED是一个可以直接获得的数据（由System Statistics获取或者有CPU主频乘以数量算出）外，其它几个因子还需要更多的信息和计算公式才能计算得出（在workload模式下，SREADTIM、MREADTIM会有系统统计得出，但是在noworkload模式下，这两个数据仍然需要通过计算得出）。   幸好，还是有人对上述公式再次作出了详细解释。Jonathan Lewis在他的书中阐述了对#SRDS、#MRDS的计算方法，以及noworkload模式下SREADTIM和MREADTIM的计算： #SRDS = BLEVEL + INDLEAFBLKS*INDSEL + TABSEL*CLUF (索引扫描) #MRDS = TABBLKS/MBRC (全表扫描、快速索引全扫描) SREADTIM = IOSEEKTIM + BLKSIZ/IOTFRSPEED MREADTIM = IOSEEKTIM + MBRC * BLKSIZ/IOTFRSPEED   其中， BLEVEL：索引高度； INDLEAFBLKS：索引叶子数据块数； INDSEL：索引选择性； TABSEL：表选择性； TABBLKS：表在HWM下的数据块数； MBRC：多数据块读的一次读取的数据块数，Multi_Block_Read_Count； BLKSIZ：数据块大小； IOSEEKTIM：IO寻址时间，System Statistics中给出，默认为10ms； IOTFRSPEED：IO传输速度，System Statistics中给出，默认为4096字节/ms。   可以看到，除了INDSEL和TABSEL外，所有数据都是可以直接获取的数据（关于INDSEL和TABSEL的计算，Oracle也有公式给出，但是并不完整，我会在另外一篇文章中尝试推测更加完整的公式）。这样，之前的的代价公式中的所有因子除#CPUCYCLE外，基本都有了出处。很遗憾，在Oracle文档中和Jonathan Lewis的书中，我们都没有发现#CPUCYCLE到底是如何计算得出的。我们这里要做的工作就是尝试推导出#CPUCYCLE的计算公式。如果能成功推导出#CPUCYCLE的计算公式，其它公式就能以类似方法进行深入推导。 注：根据由简入繁的原则，我在这里推导是在系统统计信息为noworkload模式下、使用绑定变量的全表扫描中#CPUCYCLE的公式。在推导出此公式的前提下，可以再继续推导其他访问路径的公式。我的数据库环境是10gR2。   好在Oracle可以通过10053事件做CBO的trace，让我们有可能推导出计算公式的更多内容。在10053的Trace文件中，记录了优化器生成最优（代价最低）查询计划的整个过程，包括相关基础信息、查询重写、代价计算中相关因子的计算结果、查询计划代价等。以下trace文件的内容是我们感兴趣的东西：   优化器相关参数： *************************************** PARAMETERS USED BY THE OPTIMIZER ********************************   *************************************   PARAMETERS WITH ALTERED VALUES   ******************************   parallel_execution_enabled          = false   pga_aggregate_target                = 0 KB   optimizer_mode                      = choose   optimizer_index_cost_adj            = 60   *************************************   PARAMETERS WITH DEFAULT VALUES   ******************************   optimizer_mode_hinted               = false   optimizer_features_hinted           = 0.0.0 … … 系统统计信息： ***************************** SYSTEM STATISTICS INFORMATION *****************************   Using NOWORKLOAD Stats   CPUSPEED: 1000 millions instruction/sec   IOTFRSPEED: 4096 bytes per millisecond (default is 4096)   IOSEEKTIM: 10 milliseconds (default is 10) 对象（表、索引、字段）的基本统计信息 *************************************** BASE STATISTICAL INFORMATION *********************** Table Stats::   Table: T_TEST1  Alias: T_TEST1     #Rows: 47582  #Blks:  673  AvgRowLen:  93.00 Index Stats::   Index: T_TEST1_IDX1  Col#: 1     LVLS: 1  #LB: 109  #DK: 22  LB/K: 4.00  DB/K: 58.00  CLUF: 1277.00   Index: T_TEST1_IDX2  Col#: 2 1 … … 各种访问路径的代价计算： *************************************** SINGLE TABLE ACCESS PATH   Table: T_TEST1  Alias: T_TEST1         Card: Original: 47582  Rounded: 47582  Computed: 47582.00  Non Adjusted: 47582.00   Access Path: TableScan     Cost:  150.95  Resp: 150.95  Degree: 0       Cost_io: 149.00  Cost_cpu: 23349709       Resp_io: 149.00  Resp_cpu: 23349709 … …   这些信息相当全面，足以帮助我们由这些结果推导出产生这些结果的公式！ 先看第一部分，这一部分记录了优化器相关参数的数值，这些数值能够影响查询重写和代价计算。这里，我们感兴趣的是代价计算部分。在接下来的推导过程中需要证明部分参数值在公式中的作用。 在第二部分中，是系统收集的系统统计信息，包括我们之前提到的IOSEEKTIM、CPUSPEED、IOTFRSPEED、IOSEEKTIM。系统统计信息有2中模式，一种是workload模式，需要我们手工调用dbms_stat的过程，让系统自动收集到更加全面的统计数据，除了之前4个数据，还有MREADTIM、SREADTIM、MBRC等数据；另外一种模式就是noworkload模式，当没有或系统数据不全或不正确时，就会采用noworkload模式。Trace文件这部分也会提示我们当前采用的是哪种模式。我们可以通过sys.aux_stats$查询这些数据。这些数据还能通过dbms_stat来进行手工设置，在接下来的推导过程中，我会修改这些数据来推导其在公式中的作用。 在第三部分中，是相关对象的统计信息。其中缩写的意思可以在Trace文件的头部找到，以下是相关解释： 表部分 #Rows：表的记录数； #Blks：表的HWM以下的数据块数； AvgRowLen：表记录的平均长度 索引部分 Col#：索引中字段在表中的位置； LVLS：索引高度，即BLevel； #LB：索引叶子节点数据块数； LB/K：平均每个键值的叶子节点数据块数； DB/K：平均每个键值的表数据块数； CLUF：聚簇因子（Clustering Factor） 字段部分 (#n)：字段位置； A(VARCHAR2)：字段名称和数据类型； AvgLen：字段平均长度； NDV：字段中唯一值数量； Nulls：字段中空值数量； Density：字段密度； 第四部分是访问路径的代价计算的过程及结果。我们需要关注到的就是COST_CPU，也就是#CPUCYCLES。我们的推导方法也就是通过修改前面三个部分中的数据，观察这个数据的变化，以推导出它们之间的关系。 根据数学归纳法，我们可以通过2个步骤完成一个公式的论证：证明x=1时，f(x)成立；假设f(n)成立，证明f(n+1)也成立。但是，由于输入、输出过程是一个黑盒过程，无法完成第二步的证明，我在这里采取一种并不十分可靠的方法来代替：通过多个随机数据的输入获取输出，如果出现与公式结果不一直的数，则说明公式错误或者假设不成立，否则，我们就认为公式或假设成立。 在司法上，有2种定罪方法，一种叫无罪推断，一种叫有罪推断。无罪推断就是假定嫌疑人是无罪的，控方需要找出充分的证据证明嫌疑人有罪，嫌疑人的罪名才能成立；而有罪推断就是控方在掌握了不充分的证据的情况下认定嫌疑人有罪，而嫌疑人必须找出证据来证明自己无罪，否则就会被认定有罪。尽管有罪推断的公正性不如无罪推断，但我们这里采用的方法就类似于对推导出的公式最有罪推断。 3.   推导 下面，我们就开始这个漫长的推导吧。为了推导方便、便于观察，尽量减少取整对结果的影响，我首先尽量将数据设置成整数： SQL> create table t_peeking11 (a varchar2(50), b varchar2(50), c varchar2(50), d varchar2(80), e varchar2(50));   表已创建。   SQL> begin   2   dbms_stats.set_system_stats(pname => 'CPUSPEEDNW',pvalue => 1000);   3   dbms_stats.set_system_stats(pname => 'IOSEEKTIM',pvalue => 10);   4   dbms_stats.set_system_stats(pname => 'IOTFRSPEED',pvalue => 4096);   5   dbms_stats.set_table_stats(ownname => 'DEMO', tabname => 'T_PEEKING11',   6                              numrows => 1000000, numblks => 1000, avgrlen => 100);   7   dbms_stats.set_column_stats(ownname => 'DEMO', tabname => 'T_PEEKING11', colname => 'A',   8                               distcnt => 1600, density => null, nullcnt => 0, avgclen=> 50);   9   dbms_stats.set_column_stats(ownname => 'DEMO', tabname => 'T_PEEKING11', colname => 'B', 10                               distcnt => 1600, density => null, nullcnt => 0, avgclen=> 50); 11   dbms_stats.set_column_stats(ownname => 'DEMO', tabname => 'T_PEEKING11', colname => 'C', 12                               distcnt => 1600, density => null, nullcnt => 0, avgclen=> 50); 13   dbms_stats.set_column_stats(ownname => 'DEMO', tabname => 'T_PEEKING11', colname => 'D', 14                               distcnt => 1600, density => null, nullcnt => 0, avgclen=> 50); 15   dbms_stats.set_column_stats(ownname => 'DEMO', tabname => 'T_PEEKING11', colname => 'E', 16                               distcnt => 1600, density => null, nullcnt => 0, avgclen=> 50); 17  end; 18  /   PL/SQL 过程已成功完成。   然后生成一个Trace文件作为基线： SQL> alter session set events '10053 trace name context forever,level 1';   会话已更改。   SQL> explain plan for select /*+full(a)*/* from T_PEEKING11 a where a > :v1;   已解释。   SQL> alter session set events '10053 trace name context off';   会话已更改。   注意：在随后过程中，由于对比的需要，我还创建了多张测试表做基线对某些因子进行推导，其具体数据和这里可能有一些不一致（如字段数、记录数等），但并不影响公式的推导。 注：以下的推导顺序并不是我的实际推导顺序。我在尝试推导某些因子时，如_optimizer_block_size，并没有发现它们的直接影响，直到推导出其他因子时，回头再推导出这些因子的。下面的顺序是我整理过的，便于读者理解。