中国 [选择]

首页

产品

服务与解决方案

支持与下载

个性化服务

developerWorks 中国 > Information Management >

DB2 JOIN 基估计

DB2 优化器中针对 JOIN 语句的结果集估计

文档选项

未显示需要 JavaScript 的文档选项

级别：初级

骆洪青 ( hq_l@tom.com), 软件事业部经理, 北京银信长远科技有限公司

2009 年 6 月 11 日

DB2 优化器在为 SQL 语句生成执行计划时，都会对每个步骤产生的结果集大小进行估计，这就是优化器的基估计。在所有 SQL 语句基估计过程中，以 JOIN 语句的计算过程最复杂，而 JOIN 语句恰恰是进行性能优化的重点。本文主要关注 DB2 优化器在进行基估计时采用的计算方法、输入等。

简介

IBM 为社区提供了 DB2 免费版本 DB2 Express-C，它提供了与 DB2 Express Edition 相同的核心数据特性，为构建和部署应用程序奠定了坚实的基础。

优化器是 DB2 的心脏和灵魂（可以把它类比成宝马 730 或波音 747 的发动机引擎一样）。它分析 SQL 语句并确定可以满足每条语句的最有效的存取路径。 DB2 SQL 优化器可以估计每个备选访问计划的执行成本，并根据其估计结果选择一个最佳访问计划。

在优化器在优化一个 SQL 语句的过程中使用到两个非常重要的概念：selectivity 和 cardinality 。 selectivity 是指一个 SQL 操作的得出结果集占原来结果集的百分比，而 cardinality 就是指一个 SQL 操作的得出结果集的行数。

为正确地确定每种访问计划的成本，DB2 优化器都会对每个步骤产生的结果集大小即返回的行数进行估计，这就是优化器的基估计。 DB2 优化器需要准确的基数估计值。基数估计是这样一种过程：在应用了谓词或执行了聚集之后，优化器使用统计信息确定部分查询结果的大小。对于访问计划的每个操作符，优化器将估计该操作符的基数输出。一个或更多谓词的应用可以减少输出流基数。

回页首

JOIN 谓词

当我们在 SQL 里面需要对多个表进行 join 的时候，DB2 会首先选择其中的 2 个表进行 join，并获取到一个中间的结果集，然后 DB2 可能会用这个中间的结果集和第三个表做 join，再次获得中间的结果集（当然也可能是把另外 2 个表做 join，然后把两个中间的结果集进行 join 操作），不管是怎么操作，DB2 一次能够 join 的表的个数肯定是两个。因此当优化器在考虑 Join 如何处理的时候，join 的顺序就是一个很重要的问题，因为我们总是希望能够在最开始就把结果集控制的尽量小。

一个 JOIN 谓词一般描述如下所示：

T1.joincol=T2.joincol

在实际应用过程中，Where 子句中除 JOIN 谓词外，一般都还有本地谓词，形式如下：

T1.joincol=T2.joincol and T1.filter=literal_1 and T2.filter=literal_2

谓词 T1.filter=literal_1 用于对 T1 表进行过来，T2.filter=literal_2 用于多 T2 表进行过滤，然后两个经过过滤的表进行 JOIN 操作。至于 JOIN 采用 hash join 还是 Merge Join 或者 NestLoop Join 取决于 DB2 的优化级别、参数设置以及成本估计。

DB2 Join 谓词选择性计算公式如下：

Selectivity (T1.y = T2.y)= 1/max(colcard(T1. joincol), colcard(T2. joincol))

其中，colcard(T1. joincol) 指 T1 表 joincol 列的不同值的个数，colcard(T2. joincol) 指 T2 表 joincol 列的不同值的个数，两者取较大的一个作为 Join 谓词计算依据。此公式存在两个假设：

包含性，即 T2. joincol 的所有取值都在 T1 joincol 取值范围内，反之也行。
均衡性，即两个连接列上的数据分布均匀。

DB2 Join 谓词基估计计算公式如下：

Join Cardinality =Join Selectivity * 
			 filtered cardinality(t1) * 
			 filtered cardinality(t2)

其中 filtered cardinality(t1) 是在 T1 表上应用本地谓词后获得结果集，filtered cardinality(t2) 是在 T2 表上应用本地谓词后获得结果集。

回页首

示例

创建测试表

我们创建以下测试表：

T1 表拥有 10000 行数据。参加进行 JOIN 操作的列 join1 数据均匀分布，取值范围在 0 ～ 29 之间，没有空值。对 T1 进行过滤的列 filter1 数据也均匀分布，取值在在 0 ～ 24 之间。 V1 列从 0 自然增长到 9999 。
T2 表拥有 10000 行数据。参加进行 JOIN 操作的列 join2 数据均匀分布，取值范围在 0 ～ 29 之间，没有空值。对 T2 进行过滤的列 filte2r 数据也均匀分布，取值在在 0 ～ 24 之间。 V2 列从 0 自然增长到 9999 。

			drop table db2inst1.t1; 
 CREATE TABLE db2inst1.t1 
 ( Filter1 int, join1 int , v1 int, padding1 char(1) 
 ) 
 NOT LOGGED INITIALLY 
 ; 

 INSERT INTO db2inst1.t1 (filter1, join1, v1,padding1) 
 WITH TEMP (COUNTER, filter1, join1, v1,padding1) AS 
 ( VALUES (0, MOD(INT(RAND() * 1000), 25),MOD(INT(RAND() * 1000), 30), 0, 'A') 
 UNION ALL SELECT (COUNTER + 1),MOD(INT(RAND() * 1000), 25),
 MOD(INT(RAND() * 1000), 30), (COUNTER + 1), 'A' FROM TEMP WHERE (COUNTER + 1) < 10000 
 ) 
 SELECT Filter1, join1, v1,padding1 
 FROM TEMP 
 ; 

 drop table db2inst1.t2; 
 CREATE TABLE db2inst1.t2 
 ( Filter2 int, Join2 int , V2 int, Padding2 char(1) 
 ) 
 NOT LOGGED INITIALLY 
 ; 

 INSERT INTO db2inst1.t2 (filter2, join2, v2,padding2) 
 WITH TEMP (COUNTER, filter2, join2, v2,padding2) AS 
 ( VALUES (0, MOD(INT(RAND() * 1000), 50),MOD(INT(RAND() * 1000), 40), 0, 'A') 
 UNION ALL SELECT (COUNTER + 1),MOD(INT(RAND() * 1000), 50),MOD(INT(RAND() * 1000), 40), 
 (COUNTER + 1), 'A' FROM TEMP WHERE (COUNTER + 1) < 10000 
 ) 
 SELECT Filter2, join2, v2,padding2 
 FROM TEMP 
 ;

在表创建完成后，我们收集 T1 和 T2 的统计信息，在收集统计信息是只包括表的基本统计和列的统计信息，不包括列的分布信息。

db2 "runstats on table db2inst1.t1 on all COLUMNS " 
 db2 "runstats on table db2inst1.t2 on all COLUMNS "

使用 db2look 从系统统计视图中提取 T1、T2 的统计信息如下。

表 1. T1 统计信息

统计属性	值	说明
表 CARD	10000	表的行数
表 NPAGES	68	表占用的页面数
列 FILTER1 的 COLCARD	25	列的不同取值个数
列 FILTER1 的 NUMNULLS	0	列的空值行数
列 JOIN1 的 COLCARD	30	列的不同取值个数
列 JOIN1 的 NUMNULLS	0	列的空值行数

表 2. T2 统计信息

统计属性	值	说明
表 CARD	10000	表的行数
表 NPAGES	68	表占用的页面数
列 FILTER2 的 COLCARD	50	列的不同取值个数
列 FILTER2 的 NUMNULLS	0	列的空值行数
列 JOIN2 的 COLCARD	40	列的不同取值个数
列 JOIN2 的 NUMNULLS	0	列的空值行数

测试一

我们首先执行以下查询来验证公式。

select count(*) 
 from ( 
 select 
 t1.v1, t2.v1 
 from 
 t1, 
 t2 
 where 
 t1.filter = 1 
 and t2.join1 = t1.join1 
 and t2.filter = 1 ) 
 as b;

上述查询执行得到的结果是 2002，表示其中的子查询返回 2002 行，我们使用 db2exfmt 获取其执行计划如下。

              Rows 
             RETURN
             (   1)
              Cost 
               I/O 
               |
                1 
             GRPBY 
             (   2)
             165.048 
               136 
               |
              2000 
             HSJOIN
             (   3)
             164.804 
               136 
          /-----+-----\
       400              200 
     TBSCAN           TBSCAN
     (   4)           (   5)
     82.3373          82.3373 
       68               68 
       |                |
      10000            10000 
 TABLE: DB2INST1  TABLE: DB2INST1
       T1               T2

我们观察到操作符 4 的 TBSAN 是对 T1 表的扫描后进行行过滤返回结果是 400 行，操作符 5 的 TBSAN 是对 T2 表的扫描后进行行过滤返回结果是 200 行。

根据本地谓词过滤公式计算得到以下结果，与我们看到的执行计划是一致的。

filtered cardinality(t1) = （t1 table cardinality）
					 *(selectivity of t1.filter) 
				 =10000/25 
				 =400 
 filtered cardinality(t2) = （t2 table cardinality）
					 *(selectivity of t2.filter) 
				 =10000/50 
				 =200

而 JOIN 谓词的选择率计算如下：

Join Selectivity =1/max(colcard(T1. joincol), colcard(T2. joincol)) =1/max(30,40)=1/40 

 Join Cardinality =Join Selectivity * filtered cardinality(t1) 
				 *filtered cardinality(t2) =400*200/40 =2000

这个计算结果与我们在执行计划中看到的操作符 3 （HSJOIN）输出行也是一致的。基估计与实现查询结果误差 2 行，准确性还是比较高的。

测试二

我们继续进行测试，来看看有 null 值的情况。因此我们对 t1，t2 做如下 update，把用来做 join 的列上的一部分值修改为 null：

db2 "update db2inst1.t2 set join2 = null where mod(v1,30) = 0 " 
 db2 "update db2inst1.t2 set join2 = null where mod(v2,30) = 0 "

上述语句中，将使得 t1 表的 join1 列上有 500 个空值，t2 表 join2 上有 334 个空值。重新收集 T1、T2 的统计信息后，得到以下结果。

表 3. T1 统计信息

统计属性	值	说明
表 CARD	10000	表的行数
表 NPAGES	68	表占用的页面数
列 FILTER1 的 COLCARD	25	列的不同取值个数
列 FILTER1 的 NUMNULLS	0	列的空值行数
列 JOIN1 的 COLCARD	31	列的不同取值个数
列 JOIN1 的 NUMNULLS	500	列的空值行数

表 4. T2 统计信息

统计属性	值	说明
表 CARD	10000	表的行数
表 NPAGES	68	表占用的页面数
列 FILTER2 的 COLCARD	50	列的不同取值个数
列 FILTER2 的 NUMNULLS	0	列的空值行数
列 JOIN2 的 COLCARD	41	列的不同取值个数
列 JOIN2 的 NUMNULLS	334	列的空值行数

我们注意到 T1 的 join1 列的基也发生了变化，变成个 31，把空值也考虑在内。同样 T2 的 join1 列的基变成了 41 。 T1、T2 的过滤性不变。

这个我们如果根据公式计算得到 JOIN 基估计如下：

Join Selectivity =1 / max(colcard(T1. joincol), colcard(T2. joincol)) 
				=1/max(31,41)
				=1/41 
 Join Cardinality =Join Selectivity * filtered cardinality(t1) 
					 *filtered cardinality(t2) 
				=400*200/41 
				= 1951.22

我们同样运行上述查询得到结果是 1798，而使用 db2exfmt 观察到其查询计划：

              Rows 
             RETURN
             (   1)
              Cost 
               I/O 
               |
                1 
             GRPBY 
             (   2)
             165.041 
               136 
               |
             1951.22 
             HSJOIN
             (   3)
             164.803 
               136 
          /-----+-----\
       400              200 
     TBSCAN           TBSCAN
     (   4)           (   5)
     82.3373          82.3373 
       68               68 
       |                |
      10000            10000 
 TABLE: DB2INST1  TABLE: DB2INST1
       T1               T2

我们观察到操作符 3 的 HSJOIN 输出与公式是符合的，基估计与实际查询结果差 153.22 行，误差明显高于测试 1 。

测试三

我们把在测试二的基数上把用来做 filter 的列上的一部分值也修改为 null：

update db2inst1.t1 set filter1 = null where mod(v1,50) = 0 
 update db2inst1.t2 set filter2 = null where mod( v2,100) = 0

上述语句中，将使得 t1 表的 filter1 列上有 200 个空值，t2 表 filter2 上有 100 个空值。重新收集 T1、T2 的统计信息后，得到以下结果。

表 5. T1 统计信息

统计属性	值	说明
表 CARD	10000	表的行数
表 NPAGES	68	表占用的页面数
列 FILTER1 的 COLCARD	26	列的不同取值个数
列 FILTER1 的 NUMNULLS	200	列的空值行数
列 JOIN1 的 COLCARD	31	列的不同取值个数
列 JOIN1 的 NUMNULLS	500	列的空值行数

表 6. T2 统计信息

统计属性	值	说明
表 CARD	10000	表的行数
表 NPAGES	68	表占用的页面数
列 FILTER2 的 COLCARD	51	列的不同取值个数
列 FILTER2 的 NUMNULLS	100	列的空值行数
列 JOIN2 的 COLCARD	41	列的不同取值个数
列 JOIN2 的 NUMNULLS	334	列的空值行数

我们注意此时到 T1 的 filter1 列的基也发生了变化，变成个 26，把空值也考虑在内。同样 T2 的 filter2 列的基变成了 51 。

这个我们如果根据公式计算得到 JOIN 基估计如下：

Join Selectivity =1 / max(colcard(T1. joincol), colcard(T2. joincol)) 
				=1/max(31,41)=1/41 
 Join Cardinality =Join Selectivity * filtered cardinality(t1) 
				 *filtered cardinality(t2)
				  =((10000-200)/25)* ((10000-100)/50)/41 
				  =(392* 198)/41 
				  = 1893.07

我们同样运行上述查询得到结果是 1734，而使用 db2exfmt 观察到其查询计划：

             Rows 
             RETURN
             (   1)
              Cost 
               I/O 
               |
                1 
             GRPBY 
             (   2)
             165.031 
               136 
               |
             1893.07 
             HSJOIN
             (   3)
              164.8 
               136 
          /-----+-----\
       392              198 
     TBSCAN           TBSCAN
     (   4)           (   5)
     82.3373          82.3373 
       68               68 
       |                |
      10000            10000 
 TABLE: DB2INST1  TABLE: DB2INST1
       T1               T2

我们观察到对 T1 进行扫描的操作符 4 的输出是 392，对 T2 进行扫描的操作符 5 的输出是 198，操作符 3 的 HSJOIN 输出是 1893.07 都与公式计算吻合。，基估计与实际查询结果差 159.07 行，误差比测试二又高了一些。

NULL 在基估计中的影响

通过上面三个测试，我们发现 NULL 在 DB2 优化器进行基估计是会产生很大影响。在对本地谓词进行过滤时与 JOIN 谓词进行过滤时，NULL 产生的影响不尽相同。

我们考察本地谓词的 NULL 处理公式：

filtered cardinality(t1)= (t1 table cardinality - num_nulls) 
					 /( COLCARD － 1)

在计算基数时把列的空值从列基中扣除了，同时表的基数中也扣除了空行。

我们重新考察 JOIN 基数估计公式：

Selectivity (T1.y = T2.y)= 1/max(colcard(T1. joincol), colcard(T2. joincol)) 

 Join Cardinality =Join Selectivity * filtered cardinality(t1) 
			 *filtered cardinality(t2)

我们发现再计算 JOIN 谓词选择性的时候没有从分母中扣除 NULL 占用的一个基，也没有把 NULL 指示的空行从计算中扣除。如果把 JOIN 谓词的选择性计算方法调整成与本地谓词的选择性计算方法相同，应该计算准确性更高一些。

Selectivity (T1.y = T2.y)= ((Cardinality (t1) - num_nulls(t1.y)) 
						 /Cardinality (t1)) 
				 *(( Cardinality (t2) - num_nulls(t2.y)) 
						 / Cardinality (t2)) 
				 / (max(colcard(T1. y), colcard(T2. y))-1) 
				
 Join Cardinality =Join Selectivity * filtered cardinality(t1) 
					 *filtered cardinality(t2)

我们用上面的公式计算测试二的基估计得到以下结果：

Selectivity (T1.y = T2.y)=((10000 - 500)/ 10000) 
						 *（(10000 - 334)/ 10000) 
						 /(max(31,41)-1) 
				 =0.02295675 

 Join Cardinality =Join Selectivity * filtered cardinality(t1) 
					 *filtered cardinality(t2) 
					 =400*200*0.02295675 
					 = 1836.54

上面的计算结果与查询实际执行结果误差 38.54，要小于测试二的结果。

我们用上面的公式计算测试三的基估计得到以下结果：

Selectivity (T1.y = T2.y)=(10000 - 500) / 10000) 
				 *(10000 - 334) / 10000) 
				 /(max(31,41)-1) 
				 =0.02295675 

 Join Cardinality =Join Selectivity * filtered cardinality(t1) 
				 *filtered cardinality(t2) 
				 =392*198*0.02295675 
				 = 1781.82

上面的计算结果与查询实际执行结果误差 47.811108，要小于测试三的结果。

上面试验告诉我们，NULL 值在 JOIN 基估计中不同的计算方法有不同的影响，我们在分析一个查询的执行计划时一定要仔细研究产生此计划的原因。

回页首

错误假设的影响

我们在执行 JOIN 基数估计时，使用了两个假设：

包含性，即 T2. joincol 的所有取值都在 T1 joincol 取值范围内，反之也行。
均衡性，即两个连接列上的数据分布均匀。

在对两个表做 JOIN 操作时，如果 T1、T2 表是主键、外键关系，上面的假设 1 是能够满足的，而假设二在实际过程中一般很难得到满足，即大部分数据分布不具有均衡性，因此在收集表统计信息时也需要把列分布统计信息一起上来，这样 DB2 优化器能够根据这些统计信息生成更加准确的执行计划。

参考资料

学习

通过访问 DB2 9 技术资源中心 , 查看 DB2 9 相关技术文章和教程的资源。
通过访问 DB2 Express-C 产品专题，了解 DB2 Express-C 相关的产品和文档、教程等技术资源。
Cynthia M. Saracco、Don Chamberlin 和 Rav Ahuja 撰写的 IBM 红皮书 DB2 9 pureXML: Overview and Fast Start 介绍了 DB2 pureXML 的基本知识。
通过理解 DB2 中的列组统计信息，介绍了 DB2 中列组统计信息的相关信息。
通过在 DB2 优化器中使用分布统计信息，了解 DB2 中优化器及分布统计信息的相关信息。
在 developerWorks Information Management 专区学习关于 Information Management 的更多知识。在这里可以找到技术文档、how-to 文章、培训、下载、产品信息等等。
随时关注 developerWorks 技术活动和网络广播。

获得产品和技术

通过 DB2 early access program 体验正在开发的 DB2 技术。
现在可以免费使用 DB2 。下载 DB2 Express-C，这是为社区提供的 DB2 Express Edition 的免费版本，它提供了与 DB2 Express Edition 相同的核心数据特性，为构建和部署应用程序奠定了坚实的基础。
下载 DB2 Enterprise V9.5 试用版，试用本文中描述的特性。
使用可直接从 developerWorks 下载的 IBM 产品评估试用软件构建您的下一个开发项目。

讨论

参与 developerWorks blogs 并加入 developerWorks 社区。

关于作者


		骆洪青，北京银信长远科技有限公司软件事业部经理，主要从事 DB2、数据仓库、ETL、AIX、HACMP 等方面的研究工作，对 DB2 的性能调优有浓厚的兴趣。

对本文的评价

IBM 公司保留在 developerWorks 网站上发表的内容的著作权。未经IBM公司或原始作者的书面明确许可，请勿转载。如果您希望转载，请通过提交转载请求表单联系我们的编辑团队。

关于 IBM

隐私条约

联系 IBM

使用条款