查询计划中的笛卡尔积

日期： 2009-02-07 14:53:41

分享到

今天遇到一个性能问题，经过定位，最终确定问题的根本原因是一个查询中存在笛卡尔乘积（Cartesian）。在这里，我们先讲一下什么叫笛卡尔乘积以及查询计划中笛卡尔乘积的来由。

首先，我们要知道在查询计划中产生笛卡尔乘积的一个先决条件：笛卡尔乘积只出现在CBO中。

1、没有join条件导致笛卡尔乘积

学过线性代数的人都知道，笛卡尔乘积通俗的说，就是两个集合中的每一个成员，都与对方集合中的任意一个成员有关联。可以想象，在SQL查询中，如果对两张表join查询而没有join条件时，就会产生笛卡尔乘积。这就是我们的笛卡尔乘积导致的性能问题中最常见的案例：开发人员在写代码时遗漏了join条件。
SQL> create table t_test1 as select * from all_objects;
 
Table created.
 
SQL> create table t_test2 as select * from all_tables;
 
Table created.
 
SQL> set autot trace
SQL> select count(1) from t_test1, t_test2;
 
Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT Optimizer=CHOOSE
   1    0   SORT (AGGREGATE)
   2    1     NESTED LOOPS
   3    2       TABLE ACCESS (FULL) OF 'T_TEST2'
   4    2       TABLE ACCESS (FULL) OF 'T_TEST1'
 
 
SQL> analyze table t_test1 compute statistics;
 
Table analyzed.
 
SQL> analyze table t_test2 compute statistics;
 
Table analyzed.
 
SQL>
SQL> select count(1) from t_test1, t_test2;
 
Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT Optimizer=CHOOSE (Cost=4169 Card=1)
   1    0   SORT (AGGREGATE)
   2    1     MERGE JOIN (CARTESIAN) (Cost=4169 Card=2585632)
   3    2       TABLE ACCESS (FULL) OF 'T_TEST2' (Cost=4 Card=833)
   4    2       BUFFER (SORT) (Cost=4165 Card=3104)
   5    4         TABLE ACCESS (FULL) OF 'T_TEST1' (Cost=5 Card=3104)
 
从以上的例子中我们可以看到，只有在CBO中才会产生笛卡尔乘积。

2、优化器代价计算结果，采用笛卡尔积最优

一种情形就是：2个小的结果集分别与一个大的结果集join时，如果代价计算结果中小的结果集的cardinality值都很小（1），则会先让小结果集做笛卡尔积后再和大结果集join。实际上，如果统计数据正确，这种结果是优化器根据代价估算得出的正确结论：2个小结果集本身做笛卡尔积后再和大结果集循环比较所付出的代价是低于大结果集分别和两个结果集做循环的代价更低。
SQL> create table t_test4 as select * from all_users;
Table created.
 
SQL> create index t_test4_idx1 on t_test4(username) compute statistics;
Index created.
 
SQL> create index t_test4_idx2 on t_test4(created) compute statistics;
Index created.
 
SQL> analyze table t_test4 compute statistics for table for all columns for all indexes;
 
Table analyzed.
 
SQL> create table t_test5 as select * from all_users where username='SYS';
Table created.
 
SQL> analyze table t_test2 compute statistics;
 
Table analyzed.
 
SQL> set autot trace
 
SQL> select a.*
  2  from t_test1 a, t_test4 b, t_test5 c
  3  where a.owner = b.username
  4  and a.owner = c.username;
 
13144 rows selected.
 
 
Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT Optimizer=CHOOSE (Cost=50 Card=1917 Bytes=1
          87866)
   1    0   HASH JOIN (Cost=50 Card=1917 Bytes=187866)
   2    1     MERGE JOIN (CARTESIAN) (Cost=4 Card=45 Bytes=540)
   3    2       TABLE ACCESS (FULL) OF 'T_TEST5' (Cost=2 Card=1 Bytes=        3)
   4    2       BUFFER (SORT) (Cost=2 Card=45 Bytes=405)
   5    4         INDEX (FULL SCAN) OF 'T_TEST4_IDX1' (NON-UNIQUE) (Cost=1 Card=45 Bytes=405)
   6    1     TABLE ACCESS (FULL) OF 'T_TEST1' (Cost=42 Card=30670 Byt
          es=2637620)
 
 
SQL> select a.*
  2  from t_test1 a, t_test4 b, t_test5 c
  3  where a.owner = b.username
  4  and a.owner = c.username
  5  and b.created = sysdate;
 
no rows selected
 
 
Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT Optimizer=CHOOSE (Cost=50 Card=60 Bytes=6300)
   1    0   HASH JOIN (Cost=50 Card=60 Bytes=6300)
   2    1     MERGE JOIN (CARTESIAN) (Cost=4 Card=1 Bytes=19)
   3    2       TABLE ACCESS (BY INDEX ROWID) OF 'T_TEST4' (Cost=2 Card=1 Bytes=16)
   4    3         INDEX (RANGE SCAN) OF 'T_TEST4_IDX2' (NON-UNIQUE) (Cost=1 Card=1)
   5    2       BUFFER (SORT) (Cost=2 Card=1 Bytes=3)
   6    5         TABLE ACCESS (FULL) OF 'T_TEST5' (Cost=2 Card=1 Bytes=3)
   7    1     TABLE ACCESS (FULL) OF 'T_TEST1' (Cost=42 Card=30670 Bytes=2637620)
 
在有join条件的情况下，由优化器计算出使用cartesian merge join的查询计划不止这一种情形。对于这样的情况，如果统计数据正确，那么这样的查询计划效率也是已优化的，如果语句本身的性能可以接受，那么这样的查询计划也是可以接受的，无需再优化。

3、10gR2的新特性——条件传递会使有join条件的查询产生笛卡尔积

10gR2中，可以设置在多表join查询时，查询条件通过join条件进行传递。这是什么意思呢？举例说明，看以下查询语句：
SQL> select count(*)
  2  from t_test1 a, t_test2 b
  3  where a.owner = 'OUTLN'
  4  and b.owner = a.owner;
从逻辑上分析，b.owner = a.owner = 'OUTLN' => b.owner = 'OUTLN'，通过条件传递，以上语句就成了：
SQL> select count(*)
  2  from t_test1 a, t_test2 b
  3  where a.owner = 'OUTLN'
  4  and b.owner = 'OUTLN';
根据笛卡尔乘积产生的条件，上述语句也就会产生笛卡尔乘积了。

10gR2中是否进行条件传递，是通过隐含参数_optimizer_transitivity_retain来控制的。默认为true，即不进行传递。看以下示例：
SQL> create table t_test1 as select * from all_objects;
 
Table created.
 
SQL> create table t_test2 as select * from all_tables;
 
Table created.