本文讨论了oracles的cost-based查询变形，主要包括：

• Oracle中执行的一套启发式和基于成本的转换
• Cost-based查询转换的框架、对这种框架的需求、某些转换之间可能的交互以及用于枚举Cost-based转换的搜索空间的高效搜索算法

它描述了一种将Cost-based转换与传统物理优化器相结合的实用技术，强调了Cost-based转换的一些挑战。经验表明，以Cost-based方式执行某些转换会显著缩短执行时间。

1 INTRODUCTION

在决策支持系统和OLAP中复杂查询变得越来越重要，这类复杂查询通常涉及复杂的嵌套子查询，子查询一般包含以下特点：

• 聚合函数
• union/union-all
• distinct
• 复杂视图（group-by视图）

查询重写（Query rewrite）已被提议作为一种启发式变形（heuristic transformation）来优化此类查询。然而，即使对于简单的 SQL 语句，也可能存在许多可能的transformation变体，涉及到应用哪些transformation以及如何应用这些transformation。当两个或多个transformation相互作用时会增加复杂性。

传统的关系数据库中，查询优化通常由两个处理阶段组成：逻辑优化和物理优化。在逻辑优化阶段，通常基于heuristics或rules将给定的查询重写为等效的更优的查询。传统的物理优化器在单个查询块的范围内工作，该查询块的范围涵盖一组具有限制、投影和联接的基表。在物理优化阶段，选择access methods、join orders和join methods，以便生成高效的执行查询计划。

查询转换通常有两种实现方式：

• 启发式规则驱动的重写系统
• 物理优化器内计划生成的扩展

第一种方法是通用的，但它无法在复杂的商业系统中扩展，而第二种方法不通用。本文的工作主张采用一种新方法——能够系统地提供transformation成本，而无需修改物理优化器。一些启发式规则对于在优化的逻辑阶段应用transformation至关重要。然而，仍然存在一大类transformation，它们不太适合启发式规则，并且如果不以基于成本的方式做出应用这些transformation的决定，则可能会产生次优的执行计划。

2 TRANSFORMATION IN ORACLE

2.1 Heuristic Transformations

传统的heuristic-based transformations的目的包括：

• 对选择和投影进行早期评估
• 裁剪冗余操作
• 最小化查询块

传统的关系优化器仅生成左深（线性）执行树，无法生成bushy-tree等效的计划。然而，人们普遍认为，处理成本低的连接树的很大一部分可以在左深树的空间中找到。一般来说，只要不产生distinct或group by算子的introducing、replicating或re-positioning，最小化查询块的数量就被证明是一个很好的启发式方法。在 Oracle 中，许多transformation都是heuristics驱动的，我们称之为命令式规则（imperative rules），因为如果它们合法的话，它们总是会导致转换的应用。

2.1.1 Subquery Unnesting

使用元组迭代语义（tuple iteration semantics，TIS）对没有进行unnest的子查询进行多次评估，这类似于执行嵌套循环连接，因此无法考虑许多有效的access paths和join orders 。Oracle 优化器可以unnest几乎所有类型的子查询，除了：

• 与非父查询块相关的子查询
• 相关条件出现在析取（or）中
• 包含null值列的multi-item连接条件的 ALL子查询

unnesting有两大类：

• 生成内联视图
• 将子查询合并到其外部查询块中

在Oracle中，前者以基于cost的方式应用，而后者则强制执行。下面是一个例子：

Q2
SELECT d.dept_name, d.budget
FROM departments d
WHERE EXISTS (SELECT 1
 FROM employees e
 WHERE d.dept_id = e.dept_id
 and e.salary > 200000);

该查询被转换为以下等效查询:

Q3
SELECT d.dept_name, d.budget
FROM departments d, employees e
WHERE d.dept_id S= e.dept_id and
 e.salary > 200000;

merge子查询的unnesting方法允许我们在一般情况下考虑额外的连接方法和额外的连接顺序。在此示例中，Oracle 可以使用NLJ以及HJ和SMJ来进行semi-join。Oracle 的anti-join和semi-join实现first-match策略。Oracle执行引擎缓存左表元组的anti-join和semi-join结果，如果左表的连接列中有大量重复项，则此缓存可能非常有用。

semi-join与anti-join和left outer join一样，是一种非交换连接（non-commutative join）。也就是在此示例中，按照连接顺序，departments必须位于employees之前。但是我们可以通过对employees表选择的行应用sort distinct operator，并放宽部分连接顺序限制，将这个semi-join转换为inner- join。这允许优化器考虑连接顺序 ：

• (d semijoin e)
• (distinct(e) join d)

具有non-null连接条件的ALL子查询和 NOT EXISTS 子查询通常可以使用antijoin取消嵌套。Oracle 的下一个版本将有antijoin的另一种变体，即null aware antijoin，它可以处理出现在所有子查询的连接条件中的空值列

2.1.2 Join Elimination

如果表的join列有约束，Join elimination会从查询中remove表，而且不会影响查询结果。考虑以下两个查询 Q4 和 Q5：

Q4
SELECT e.name, e.salary
FROM employees e, departments d
WHERE e.dept_id = d.dept_id;

由于employees中的dept_id是引用departments主键的外键，因此可以从Q4中消除与departments的连接（e.dept_id作为外键保证存在性约束，d.dept_id作为主键保证匹配的唯一性约束，而且不需要输出主表departments的列 ）。

Q5
SELECT e.name, e.salary
FROM employees e left outer join
departments d on e.dept_id = d.dept_id;

在查询Q5中，外连接中右表的join列存在unique约束，由于外连接保留左表的所有元组，并且unique列上的equi-join不会生成重复项，因此可以消除 departments 表。

Q6
SELECT e.name, e.salary
FROM employees e;

在 Q4 和 Q5 上应用JE transformation会产生 Q6。如果在Q4中，e.dept_id可以返回null，则必须在Q6的where子句中添加谓词“e.dept_id is not null”。显然，裁剪冗余join会提高查询的性能，因此如果连接消除有效，Oracle 总是执行连接消除。

2.1.3 Filter Predicate Move Around

Filter Predicate Move Around将廉价的谓词移动到视图查询块中，以便更早地执行过滤。Filter Predicate Move Around是通过命令式heuristics完成的，因为它可以开辟新的access path并减少后续昂贵操作（例如连接和聚合）处理的数据规模大小。

Filter Predicate可以上拉（pulled up）、移动（moved across）和下推（pushed down）到任何级别。一个有趣的扩展是我们能够通过 ANSI 窗口函数和 ANSI 分区外连接的 PARTITION BY 以及 SQL MODEL 子句的 DIMENSION BY 子句push Filter Predicate。Oracle独有的另一种技术是在评估聚合之前通过窗口函数的聚合push谓词。例如下面的语句：

Q7
SELECT acct-id, time, ravg
FROM (SELECT acct-id, time,
 AVG(balance) OVER (PBY acc-id OBY
time
 RANGE BETWEEN UNBOUNDED
PROCEEDING
 AND CURRENT ROW) ravg
 FROM accounts)
WHERE acct-id = ‘ORCL’ AND time <= 12;

在此查询中，可以将有关 acct-id 和time的Predicate push到视图内。在 PARTITION BY (PBY) 子句上push谓词总是可以应用的。通过 ORDER BY (OPBY) 进行推送需要分析窗函数的影响范围。

Q8
SELECT acct-id, time, ravg
FROM (SELECT acct-id, time,
 AVG(balance) OVER (PBY acc-id OBY
 time RANGE BETWEEN UNBOUNDED
 PROCEEDING
 AND CURRENT ROW) ravg
 FROM accounts
 WHERE acct-id = ’ORCL’ AND
time<=12);

2.1.4 Group Pruning

Group pruning是另一种命令式transformation，它从视图中删除外部查询块中不需要的groups。例如，考虑查询 Q9。

Q9
SELECT
sum_sal,country_id,state_id,city_id
FROM (SELECT SUM (e.salary) sum_sal,
      l.country_id, l.state_id, l.city_id
      FROM employees e,departments d, locations l
      WHERE e.dept_id = d.dept_id and d.location_id = l.location_id
      GROUP BY ROLLUP (country_id,state_id,city_id)
WHERE city_id = ’San Francisco’;

在上面的查询中，city_id 上的outer谓词过滤group (country_id) 和 (country_id, state_id)。这种transformation可以基于分组列上的谓词以及分组函数来完成。此转换是在Filter Predicate Move Around后执行的，以将pruning predicates移动到靠近分组查询的位置。

2.2 Cost-Based Transformations

接下来简要讨论 Oracle 以基于代价的方式执行的一些transformation。

2.2.1 Subquery Unnesting

在多表 EXISTS 或 ANY 子查询的情况下，通常不可能简单地将子查询合并到包含的其的查询块中，因为：

• 它可能会出现副作用——生成未变形的查询的查询结果中不存在的行的duplicate
• 子查询中的表的join必须在与外部表的anti-join之前执行

在这些情况下，必须生成包含子查询表的内联视图。包含聚合的相关子查询的Unnesting还需要生成内联分组视图。考虑前面显示的查询 Q1。

Q1
SELECT e1.employee_name, j.job_title
FROM employees e1, job_history j
WHERE e1.emp_id = j.emp_id and
      j.start_date > '19980101' and
      e1.salary >
 (SELECT AVG (e2.salary)
  FROM employees e2
  WHERE e2.dept_id = e1.dept_id
 ) and e1.dept_id IN
 (SELECT dept_id
  FROM departments d, locations l
  WHERE d.loc_id = l.loc_id and
  l.country_id = 'US');

考虑转换后的查询 Q10，其中第一个子查询已通过生成内联视图取消嵌套。

Q10
SELECT e1.employee_name, j.job_title
FROM employees e1, job_history j,
 (SELECT AVG(e2.salary) avg_sal, dept_id
  FROM employees e2
  GROUP BY dept_id) V
WHERE e1.emp_id = j.emp_id and
      j.start_date > '19980101' and
      e1.dept_id = V.dept_id and
      e1.salary > V.avg_sal and
      e1.dept_id IN
 (SELECT dept_id
  FROM departments d, locations l
  WHERE d.loc_id = l.loc_id
  and l.country_id = 'US');

• 如果外部查询块显著过滤了需要计算高于平均工资的员工元组的数量，则未转换的查询 Q1 在 TIS 下可能会表现得更好；此外，如果相关谓词中的本地列（即 e2.dept_id）具有索引，那么 TIS 会非常高效。
• 另一方面，变形后的查询允许考虑不同的连接顺序和连接方法，并且只需要计算一次聚合和分组运算符。

因此，Unnesting此类子查询的决定必须基于cost。Oracle 10g 中引入了cost-based transformation。在 Oracle 10g 之前的版本中，生成内联视图的Unnesting是基于启发式的。该启发式规则的简化版本可以如下给出：如果外部查询中存在过滤谓词，并且子查询关联中的本地列上有索引，则子查询不应Unnesting。

2.2.2 Group-By and Distinct View Merging

Group-by 视图合并（group-by pull-up）允许包含 group-by（或distinct）运算符的视图合并到其外部查询块中。这允许优化器考虑额外的连接顺序和访问路径，并延迟聚合的评估，直到评估连接之后。聚合的延迟评估可能会使性能变得更好或更差，具体取决于数据的特征，例如必须执行聚合的数据集的减少。

• 不转换更好：先执行view中的聚合，再执行与外部表的join。聚合的输入tuples不多，视图输出的tuples数量明显减少(需要与外部表join的行数很少)
• 转换更好：转换后，先与外部表join，再执行聚合。如果join后tuples数量显著减少，则lazy聚合开销能够明显减少

考虑查询 Q11，它是通过合并 Q10 中的分组视图而生成的。

Q11
SELECT e1.employee_name, j.job_title
FROM employees e1, job_history j, employees e2
WHERE e1.emp_id = j.emp_id and
      j.start_date > '19980101' and
      e2.dept_id = e1.dept_id and
      e1.dept_id IN
 (SELECT dept_id
  FROM departments d, locations l
  WHERE d.loc_id = l.loc_id
  and l.country_id = 'US')
GROUP BY e2.dept_id, e1.emp_id, j.rowid, e1.employee_name, j.job_title, e1.salary
HAVING e1.salary > AVG (e2.salary);

未转换的查询 Q10 需要对整个employees表执行聚合。转换后的查询 Q11 执行与 job_history 和两个employees表的联接，并在执行聚合之前应用第二个子查询的过滤。如果连接和filters显著减少了要聚合的数据的大小，则可能会改进执行计划。另一方面，早期聚合会减少连接操作要处理的数据大小，并且可能需要在 group-by 视图中对较小的数据集执行聚合。这些权衡是该决策必须基于cost的原因。在late聚合的查询中，我们还考虑使用group-by placement转换来转换查询以执行early聚合，稍后将对此进行描述。

2.2.3 Join Predicate Pushdown

在此转换中，外层表与view的join谓词被下推到视图内。该transformation对连接表施加偏序，使得视图join的表（通过下推谓词）必须位于视图之前，并且视图必须通过Nested loop连接（lateral derived table）。作为一项附加优化，当join谓词被推入group-by视图时，如果视图在其所有group-by items上具有equi-joins，并且所有这些join谓词对于下推有效，则可以删除group-by运算符。这是因为相等条件上的相关性充当这些列值的分组。类似的优化也可以在不同的视图上进行，如查询 Q13 所示。

Q12
SELECT e1.employee_name, j.job_title, e2.employee_name as mgr_name
FROM employees e1, job_history j, employees e2,
 (SELECT DISTINCT dept_id
  FROM departments d, locations l
  WHERE d.loc_id = l.loc_id and
        l.country_id IN (‘UK’,'US')) V
WHERE e1.emp_id = j.emp_id and
      j.start_date > '19980101' and
      e1.mgr_id = e2.emp_id and
      e1.dept_id = V.dept_id;

查询 Q12 已通过 Join Predicate Pushdown转换为 Q13。这种转换允许我们从视图中删除昂贵的distinct运算符。Inner join在内部转换为semijoin（这不会在查询中显示），这会会导致一个partial join order限制—— e1 必须在 V 之前。

Q13
SELECT e1.employee_name, j.job_title, e2.employee_name as mgr_name
FROM employees e1, job_history j, employees e2,
 (SELECT dept_id
  FROM departments d, locations l
  WHERE d.loc_id = l.loc_id and
        l.country_id IN (‘UK’,'US') and
        e1.dept_id = d.dept_id) V
WHERE e1.emp_id = j.emp_id and
      j.start_date > '19980101' and
      e1.mgr_id = e2.emp_id; 

在Q13中，可以使用nested-loop来join视图V；如果 d.dept_id 有索引并且外部查询中的元组数量相对较小，则这可能非常有效。然而，需要cost-based决策来确定查询 Q12 和 Q13 中的哪一个将产生更优化的执行计划。在 Oracle 中， Join Predicate Pushdown可以应用于可合并（例如，distinct和group by）视图和不可合并（例如，union/union-all、anti-/semi-/outerjoined）视图。

2.2.4 Group-By Placement

group-by下推转换将 group-by 运算符向下推送到查询中的join之前，从而执行 group-by 操作的早期评估。进行早期分组评估可能会导致应用多个分组运算符的行数以及稍后在join中使用的行数显著减少；因此查询的整体性能可能会提高。Group-by placement还可以允许将 group-by 运算符向上拉到join上面，我们称之为 group-by 视图合并。分组查询可以经历不同类型的Group-by placement，具体取决于聚合函数中引用的连接图和表。在 Oracle 中，Group-by placement（group by下推）转换会生成一个或多个group-by views。

Oracle 优化器首先执行 group-by 视图合并（group-by pullup），然后进行 group-by 下推转换，绕过那些经过 group-by 视图合并的查询。

2.2.5 Join Factorization

连接分解（Join Factorization）适用于 UNION/UNION ALL 查询，其中 UNION ALL 的分支包含公共连接表。这些连接表被pull-out到包含的查询块中，并且 UNION ALL 查询块被转换为拉出的表所连接到的视图。这种分解避免了多次访问公共表。使用连接分解，查询 Q14 可以转换为查询 Q15。

Q14
SELECT e.first_name, e.last_name,job_id,d.department_name, l.city
FROM employees e, departments d,locations l
WHERE e.dept_id = d.dept_id and
      d.location_id = l.location_id
UNION ALL
SELECT e.first_name, e.last_name,j.job_id,d.department_name, l.city
 FROM employees e, job_history j,departments d, locations l
WHERE e.emp_id = j.emp_id and
      j.dept_id = d.dept_id and
      d.location_id = l.location_id;

有趣的是，在很多情况下，公共表可以分解出来，但相应的连接谓词却无法分解出来。在这种情况下，连接谓词可以保留在 UNION ALL 视图中，然后通过连接谓词下推部分中描述的技术进行连接。

Q15
SELECT V.first_name, V.last_name, V.job_id, d.department_name, l.city
FROM departments d, locations l,
 (SELECT e.first_name, e.last_name, e.job_id, e.dept_id
  FROM employees e
  UNION ALL
  SELECT e.first_name, e.last_name, j.job_id, j.dept_id
  FROM employees e, job_history j
  WHERE e.emp_id = j.emp_id) V
WHERE d.dept_id = V.dept_id and
      d.location_id = l.location_id;

common table部分为：from d, l where d.location_id = l.location_id

2.2.6 Predicate Pullup

Filter predicate pullup变形将昂贵的过滤谓词从原始视图上拉到包含视图的查询块中。目前，如果谓词包含过程语言函数（procedural language functions）、用户定义的运算符（user-defined operators）或子查询，则该谓词被认为是昂贵的。当前仅当视图的包含查询块中指定 rownum 谓词且视图包含blocking运算符时才考虑predicate pullup转换。考虑以下查询，其中包含一个具有两个昂贵谓词的视图。

Q16
SELECT *
FROM (SELECT document_id
      FROM product_docs
      WHERE contains(summary,'optimizer',1) > 0 AND
            contains(full_text,'execution',2) > 0
      ORDER BY create_date) V
WHERE rownum < 20;

由于视图中有两个昂贵的谓词，因此可以通过三种方式应用谓词上拉变换，其中之一如下所示。

Q17
SELECT *
FROM (SELECT document_id, value(r) AS vr
      FROM product_docs
      WHERE contains(full_text,'execution',2)> 0
      ORDER BY create_date) V
WHERE contains(summary, 'optimizer', 1) > 0 AND rownum < 20;

在某些情况下，对显著减少的数据集进行昂贵的谓词的lazy评估可能会提高查询的性能。如果谓词过滤掉很少的行，那么我们可以避免对完整数据集执行昂贵的谓词。减少来自于包含视图的查询块中存在 rownum 谓词。此转换涉及Filter谓词下推到视图的常见优化技术的逆向操作。因此，在 Oracle 中，pullup谓词的决定是以cost-based方式完成的。

2.2.7 Set Operators Into Join

集合运算符 MINUS 和 INTERSECT 分别转换为antijoin和inner-join/semijoin，从而允许应用各种join methods和join orders。然而，这些集合操作和join之间在语义上存在差异——在 INTERSECT 和 MINUS 中空值匹配，而在join和antijoin中则不匹配。此外，MINUS 和 INTERSECT 是集合运算符，因此它们返回无重复的结果集。必须做出cost-based决定，决定是否应在join的输入或输出处删除重复项；这个问题与distinct placement的问题类似。

2.2.8 Disjunction Into Union All

当Filter或join谓词出现在析取中时，查询可以扩展为 UNION ALL 查询，其中每个分支包含析取中的谓词之一。在没有这种转换的情况下，析取谓词将作为结果的post-filter应用，该结果可能是笛卡尔积。

3 FRAMEWORK FOR COST-BASED TRANSFORMATION

3.1 Basic Components

在cost-based transformation中，逻辑transformation和物理优化相结合，生成最优的执行计划。图 1 对此进行了说明。

逻辑transformation可以被认为具有两个不同的组成部分：基于启发式的转换和基于成本的转换。cost-based transformation框架包括以下内容：

• 转换算法(Transformation algorithms)——将完整或部分查询树转换为语义等效的形式
• 状态空间(State spaces)——各种转换的状态空间
• 状态空间搜索算法(search algorithms)
• 深拷贝(deep copying)查询块及其组成部分的能力
• cost估算技术（物理优化器）
• 转换指令(Transformation directives)和成本注释(cost annotations)

不同的转换适用于查询树的不同元素。例如，unnesting和视图合并分别应用于子查询和视图；group-by placement适用于join graph的节点。predicate pull-up转换适用于昂贵的谓词。

• 优化过程中以自下而上的方式遍历查询树。
• 对查询树中的元素应用一个或多个变换，从而在变换的状态空间中生成不同的状态。
• 在应用特定状态并通过调用物理优化器估计其cost之前，会制作（部分）查询树的深拷贝副本。每个状态的评估通常需要（部分）查询树的不同副本。
• 选择生成最佳计划（即最佳状态）的状态，并将最佳状态的指令传输到原始查询树，原始查询树根据这些指令进行转换。

在 Oracle 中，transformation通常以顺序方式应用；也就是说，每个转换都应用于整个查询树，然后是另一个转换，依此类推。某些transformation遵循的顺序如下：

• common sub-expression factorization
• SPJ view merging
• join elimination
• subquery unnesting
• group-by (distinct) view merging
• group pruning
• predicate move around
• set operator into join conversion
• group-by placement
• predicate pullup
• join factorization
• disjunction into union-all expansion
• star transformation
• join predicate pushdown

然而，在某些情况下，不遵循这种transformation顺序。transformation可以生成constructs，这可能需要重新应用其他transformation。例如，set operator into join conversion可以生成SPJ视图，因此可以再次应用SPJ视图合并和Filter谓词下推。有些transformation相互影响，需要一起考虑，以便做出准确的cost-based决策。

3.2 State Space Search Techniques

与cost-based transformation相关的一个基本问题是：这些transformation是否会导致需要评估的替代方案的组合数量爆炸，以及它们是否会在优化成本和执行成本之间提供权衡。

alternatives的source是各种transformation本身以及每个transformation可能应用的对象集（例如，查询块、表、连接边、谓词等）。如果有 N 个对象可以应用变换 T，则应用 T 可能会生成 2N 种可能的alternatives组合。一般来说，如果有M个变换，T1，T2，...，TM，可以应用于N个对象，则有(1+M)^N种可能的alternatives组合。

例如，在查询 Q1 中，有四种alternatives可供考虑：

Q1
SELECT e1.employee_name, j.job_title
FROM employees e1, job_history j
WHERE e1.emp_id = j.emp_id and
      j.start_date > '19980101' and
      e1.salary >
(SELECT AVG (e2.salary)
 FROM employees e2
 WHERE e2.dept_id = e1.dept_id)
      and e1.dept_id IN
 (SELECT dept_id
  FROM departments d, locations l
  WHERE d.loc_id = l.loc_id and
  l.country_id = 'US');

• no unnesting
• 仅unnesting第一个子查询 (QS1)
• unnesting二个子查询 (QS2)
• unnesting两个子查询

我们将状态表示为bit数组，其中第 n bit表示第 n 个对象（例如子查询）是否已转换（值为 1）或未转换（值为 0）。例如，状态(0,1)指的是仅unnesting第二个子查询。当有 M 个变换应用于 N 个对象时，状态由 MxN 位矩阵表示。

cost-based transformation的复杂性由alternatives组合的数量（状态空间）决定，状态空间随着变换对象的数量呈指数增长。当变换对象的数量较小时，对状态空间进行穷举搜索的枚举变换技术可能是可行的。为了限制优化时间的潜在增加，我们使用几种不同的技术来枚举状态空间：

• Exhaustive.在穷举搜索中，考虑 N 个对象的状态空间的所有可能的 2^N 个状态。
• Iterative.使用迭代改进技术(iterative improvement technique)来修剪搜索空间。该技术的总体思想是——我们从初始状态开始，并使用某种方法移动到下一个相邻状态，通过始终选择向下移动来寻找局部最小值；在下一次迭代中从不同的初始状态开始重复搜索局部最小值。如果没有更多的新状态可找到或已达到某些终止条件（即最大状态数），则算法停止。该技术中枚举的状态数介于 N+1 和 2^N 之间。
• Linear.这种搜索技术的基本思想是基于动态编程方法，它假设对于由多个对象组成的查询，只需考虑这些对象的子集进行转换，然后通过另一个对象的附加转换来扩展它。换句话说，如果 Cost(1,0) 低于 Cost(0,0)，并且 Cost(1,1) 低于 Cost(1,0)，那么可以安全地假设 Cost(1,1) 是所有可能转换的成本中最低的，因此无需评估 Cost(0,1)。该技术考虑 N+1 个状态。当不同元素的转换彼此独立时，线性搜索效果最佳。
• Two-pass. Two-pass是最便宜的搜索技术，我们考虑 2 个状态。我们比较不转换任何对象（即状态 (0,0,…)）的成本与转换所有对象（即状态 (1,1,…)）的成本。

cost-based transformation框架根据查询块中要转换的对象数量、转换的特征以及查询的整体复杂性自动决定使用哪种搜索技术。例如，如果一个查询块包含少量子查询，我们使用穷举搜索来unnesting子查询，但如果数量超过固定阈值，我们使用线性搜索。如果查询中进行转换的元素总数（例如group-by视图、可以unnesting的子查询）超过阈值，则我们对查询中的所有转换使用Two-pass搜索。

3.3 Interaction between Transformations

3.3.1 Interleaving

当两个（或多个）基于成本的transformation应用于同一对象时，其中一个transformation仅在另一个transformation应用后才适用，那么这些转换必须交织在一起，以便优化器确定最佳计划。

例如，在某些情况下，unnesting和视图合并必须交错进行，因为unnesting可能会增加查询的估计成本；然而，当将视图合并变换应用于在unnesting子查询的过程中生成的视图时，可能会产生一个最佳计划，这暗示应该对查询执行unnesting并且必须合并如此生成的视图。在查询 Q10 中，聚合子查询已被unnested到分组视图中。这种转换可能不是最优的。然而，当在 Q10 上应用视图合并时，它会生成 Q11，它可能比 Q1 和 Q10 都代价更低。如果没有视图合并与unnesting的交错，unnesting变换将不会应用于 Q1，并且将选择次优计划。

3.3.2 Juxtaposition

当两个或多个基于成本的转换以precludes their sequential application的方式应用到同一个对象，必须逐一应用它们，以便优化器确定最佳计划。两个或多个基于成本的转换的比较称为Juxtaposition。如果视图合并和连接谓词下推转换可以应用于视图，则它们必须彼此Juxtaposition，并且优化器必须在这三个选项中进行选择。考虑 Q13 中给出的连接谓词下推的示例。Q12 中的不同视图可以合并以生成以下查询：

Q18
SELECT DV.employee_name, DV.job_title, DV.mgr_name
FROM
(SELECT DISTINCT e1.emp_id, e2.emp_id, j.rowid, e1.employee_name, j.job_title, e2.employee_name as mgr_name
 FROM employees e1, job_history j, employees e2, departments d, locations l
 WHERE d.loc_id = l.loc_id and
       l.country_id IN (‘UK’,'US') and
       e1.dept_id = d.dept_id and
       e1.emp_id = j.emp_id and
       j.start_date > '19980101' and
       e1.mgr_id = e2.emp_id) DV;

在view merge中，distinct operator已经pulled up ，外部表的键已添加到新视图中，其中包含原始查询 Q12 的所有表。将估计查询 Q12、Q13 和 Q18 的成本，并且三个中成本最低的一个将确定是否应将这些转换应用于原始查询。

3.3.3 Impact on State Space

Interleaving和juxtaposing变换会导致探索的状态数量增加。我们可能会考虑为每个考虑unnesting的子查询添加一个附加状态。在某些情况下，我们可以考虑的状态是我们稍后会探索的状态，即使没有Interleaving或juxtaposing。

• 如果我们选择子查询unnesting，因为它更便宜，那么就不需要将其与视图合并交错； 我们将考虑以通常的顺序方式合并视图。
• 同样，如果我们选择不进行视图合并，因为它的成本更高，那么就没有必要将其与连接谓词下推并列； 稍后我们将考虑按顺序方式下推连接谓词。

这减轻了由于交错和并置而导致的搜索空间的增加。

3.4 Optimization Performance

我们所描述的基于成本的转换技术在优化时间和优化器内存消耗方面可能都很昂贵。重复复制查询结构会消耗内存，优化每个转换后的查询也会消耗时间。我们讨论了几种减少基于成本的转换对优化性能影响的技术：

• Cost Cut-Off：在评估任何状态期间，如果查询树或其任何组成部分的成本超过迄今为止找到的最佳状态的成本，则该状态的物理优化将中止，优化器将考虑下一个状态。
• Reuse of Query Sub-Tree Cost Annotations：重新优化每个转换后的查询的整体成本很高，而且在许多情况下是不必要的。每个转换都会影响一些已知的查询块，并且只有这些查询块和查询树中包含它们的查询块需要重新优化。换句话说，我们可以重用优化两个等效查询子树的结果，我们将其称为成本注释。对于包含许多子查询或视图的复杂查询，这可以节省大量时间。
• Memory Management：在 Oracle 中，查询结构和优化器成本以及决策结构通常直到优化结束才被释放。基于成本的转换创建许多查询结构副本，并且创建许多优化器结构来优化查询转换变体。因此，我们必须在基于成本的转换框架下更智能地管理内存。当做出每个转换决策时，查询结构和优化器决策结构被释放。请注意，优化器成本注释无法释放，因为它们可以重复使用。
• Caching：某些优化器计算特别昂贵，并且即使查询块已被转换更改，也可以重复使用。例如，Oracle 执行动态采样来估计某些表的单表基数，例如尚未收集优化器统计信息的表，以及具有多个可能相关的过滤谓词的表。这种计算成本很高，并且如果表上的单表谓词没有被转换更改，则可以重用结果。此和其他昂贵的优化器计算通过对优化器的多次调用进行缓存。

CONCLUSION

本文做出了两个主要贡献：

• 首先，提出了一种在cost- based框架内整合各种transformation的可行解决方案。该方案能够对大多数transformation以及它们之间可能的交互进行建模，从而允许优化器选择查询的最佳变体。
• 其次，提出了状态空间搜索算法来处理cost-based transformation的组合爆炸。还讨论了一些文献中尚未讨论的转换（例如，连接谓词下推和连接分解）。

我们发现，对于大量 OLTP 查询，广泛研究的unnesting transformation是一个关键转换。对于受影响的查询，其总运行时间缩短了 387%。通过join谓词下推，运行时间缩短了 23%。通过group-by placement，我们发现运行时间提高了 21%。对于subquery unnesting、group-by view merging和join predicate pushdown，我们的性能实验表明，cost-based transformation比基于启发式的transformation性能高 20%。