blob: 9c596f9294d69c366e24a6f1bc8e94c887d5928e [file] [log] [blame]
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<!-- NewPage -->
<html lang="zh">
<head>
<!-- Generated by javadoc -->
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>org.apache.calcite.plan.volcano (Apache Calcite calcite API)</title>
<link rel="stylesheet" type="text/css" href="../../../../../stylesheet.css" title="Style">
<script type="text/javascript" src="../../../../../script.js"></script>
</head>
<body>
<script type="text/javascript"><!--
try {
if (location.href.indexOf('is-external=true') == -1) {
parent.document.title="org.apache.calcite.plan.volcano (Apache Calcite calcite API)";
}
}
catch(err) {
}
//-->
</script>
<noscript>
<div>您的浏览器已禁用 JavaScript。</div>
</noscript>
<!-- ========= START OF TOP NAVBAR ======= -->
<div class="topNav"><a name="navbar.top">
<!-- -->
</a>
<div class="skipNav"><a href="#skip.navbar.top" title="跳过导航链接">跳过导航链接</a></div>
<a name="navbar.top.firstrow">
<!-- -->
</a>
<ul class="navList" title="导航">
<li><a href="../../../../../overview-summary.html">概览</a></li>
<li class="navBarCell1Rev">程序包</li>
<li></li>
<li><a href="package-tree.html"></a></li>
<li><a href="../../../../../deprecated-list.html">已过时</a></li>
<li><a href="../../../../../index-all.html">索引</a></li>
<li><a href="../../../../../help-doc.html">帮助</a></li>
</ul>
<div class="aboutLanguage"><b>Apache Calcite</b></div>
</div>
<div class="subNav">
<ul class="navList">
<li><a href="../../../../../org/apache/calcite/plan/hep/package-summary.html">上一个程序包</a></li>
<li><a href="../../../../../org/apache/calcite/prepare/package-summary.html">下一个程序包</a></li>
</ul>
<ul class="navList">
<li><a href="../../../../../index.html?org/apache/calcite/plan/volcano/package-summary.html" target="_top">框架</a></li>
<li><a href="package-summary.html" target="_top">无框架</a></li>
</ul>
<ul class="navList" id="allclasses_navbar_top">
<li><a href="../../../../../allclasses-noframe.html">所有类</a></li>
</ul>
<div>
<script type="text/javascript"><!--
allClassesLink = document.getElementById("allclasses_navbar_top");
if(window==top) {
allClassesLink.style.display = "block";
}
else {
allClassesLink.style.display = "none";
}
//-->
</script>
</div>
<a name="skip.navbar.top">
<!-- -->
</a></div>
<!-- ========= END OF TOP NAVBAR ========= -->
<div class="header">
<h1 title="程序包" class="title">程序包&nbsp;org.apache.calcite.plan.volcano</h1>
<div class="docSummary">
<div class="block">Optimizes relational expressions.</div>
</div>
<p>请参阅:&nbsp;<a href="#package.description">说明</a></p>
</div>
<div class="contentContainer">
<ul class="blockList">
<li class="blockList">
<table class="typeSummary" border="0" cellpadding="3" cellspacing="0" summary="接口概要表, 列表接口和解释">
<caption><span>接口概要</span><span class="tabEnd">&nbsp;</span></caption>
<tr>
<th class="colFirst" scope="col">接口</th>
<th class="colLast" scope="col">说明</th>
</tr>
<tbody>
<tr class="altColor">
<td class="colFirst"><a href="../../../../../org/apache/calcite/plan/volcano/VolcanoPlannerPhaseRuleMappingInitializer.html" title="org.apache.calcite.plan.volcano中的接口">VolcanoPlannerPhaseRuleMappingInitializer</a></td>
<td class="colLast">
<div class="block">VolcanoPlannerPhaseRuleMappingInitializer describes an interface for
initializing the mapping of <a href="../../../../../org/apache/calcite/plan/volcano/VolcanoPlannerPhase.html" title="org.apache.calcite.plan.volcano中的枚举"><code>VolcanoPlannerPhase</code></a>s to sets of rule
descriptions.</div>
</td>
</tr>
</tbody>
</table>
</li>
<li class="blockList">
<table class="typeSummary" border="0" cellpadding="3" cellspacing="0" summary="类概要表, 列表类和解释">
<caption><span>类概要</span><span class="tabEnd">&nbsp;</span></caption>
<tr>
<th class="colFirst" scope="col"></th>
<th class="colLast" scope="col">说明</th>
</tr>
<tbody>
<tr class="altColor">
<td class="colFirst"><a href="../../../../../org/apache/calcite/plan/volcano/AbstractConverter.html" title="org.apache.calcite.plan.volcano中的类">AbstractConverter</a></td>
<td class="colLast">
<div class="block">Converts a relational expression to any given output convention.</div>
</td>
</tr>
<tr class="rowColor">
<td class="colFirst"><a href="../../../../../org/apache/calcite/plan/volcano/AbstractConverter.ExpandConversionRule.html" title="org.apache.calcite.plan.volcano中的类">AbstractConverter.ExpandConversionRule</a></td>
<td class="colLast">
<div class="block">Rule which converts an <a href="../../../../../org/apache/calcite/plan/volcano/AbstractConverter.html" title="org.apache.calcite.plan.volcano中的类"><code>AbstractConverter</code></a> into a chain of
converters from the source relation to the target traits.</div>
</td>
</tr>
<tr class="altColor">
<td class="colFirst"><a href="../../../../../org/apache/calcite/plan/volcano/ChainedPhaseRuleMappingInitializer.html" title="org.apache.calcite.plan.volcano中的类">ChainedPhaseRuleMappingInitializer</a></td>
<td class="colLast">
<div class="block">ChainedPhaseRuleMappingInitializer is an abstract implementation of
<a href="../../../../../org/apache/calcite/plan/volcano/VolcanoPlannerPhaseRuleMappingInitializer.html" title="org.apache.calcite.plan.volcano中的接口"><code>VolcanoPlannerPhaseRuleMappingInitializer</code></a> that allows additional
rules to be layered on top of those configured by a subordinate
<a href="../../../../../org/apache/calcite/plan/volcano/VolcanoPlannerPhaseRuleMappingInitializer.html" title="org.apache.calcite.plan.volcano中的接口"><code>VolcanoPlannerPhaseRuleMappingInitializer</code></a>.</div>
</td>
</tr>
<tr class="rowColor">
<td class="colFirst"><a href="../../../../../org/apache/calcite/plan/volcano/RelSubset.html" title="org.apache.calcite.plan.volcano中的类">RelSubset</a></td>
<td class="colLast">
<div class="block">Subset of an equivalence class where all relational expressions have the
same physical properties.</div>
</td>
</tr>
<tr class="altColor">
<td class="colFirst"><a href="../../../../../org/apache/calcite/plan/volcano/VolcanoPlanner.html" title="org.apache.calcite.plan.volcano中的类">VolcanoPlanner</a></td>
<td class="colLast">
<div class="block">VolcanoPlanner optimizes queries by transforming expressions selectively
according to a dynamic programming algorithm.</div>
</td>
</tr>
<tr class="rowColor">
<td class="colFirst"><a href="../../../../../org/apache/calcite/plan/volcano/VolcanoRelMetadataProvider.html" title="org.apache.calcite.plan.volcano中的类">VolcanoRelMetadataProvider</a></td>
<td class="colLast">
<div class="block">VolcanoRelMetadataProvider implements the <a href="../../../../../org/apache/calcite/rel/metadata/RelMetadataProvider.html" title="org.apache.calcite.rel.metadata中的接口"><code>RelMetadataProvider</code></a>
interface by combining metadata from the rels making up an equivalence class.</div>
</td>
</tr>
<tr class="altColor">
<td class="colFirst"><a href="../../../../../org/apache/calcite/plan/volcano/VolcanoRuleCall.html" title="org.apache.calcite.plan.volcano中的类">VolcanoRuleCall</a></td>
<td class="colLast">
<div class="block"><code>VolcanoRuleCall</code> implements the <a href="../../../../../org/apache/calcite/plan/RelOptRuleCall.html" title="org.apache.calcite.plan中的类"><code>RelOptRuleCall</code></a> interface
for VolcanoPlanner.</div>
</td>
</tr>
</tbody>
</table>
</li>
<li class="blockList">
<table class="typeSummary" border="0" cellpadding="3" cellspacing="0" summary="枚举概要表, 列表枚举和解释">
<caption><span>枚举概要</span><span class="tabEnd">&nbsp;</span></caption>
<tr>
<th class="colFirst" scope="col">枚举</th>
<th class="colLast" scope="col">说明</th>
</tr>
<tbody>
<tr class="altColor">
<td class="colFirst"><a href="../../../../../org/apache/calcite/plan/volcano/VolcanoPlannerPhase.html" title="org.apache.calcite.plan.volcano中的枚举">VolcanoPlannerPhase</a></td>
<td class="colLast">
<div class="block">VolcanoPlannerPhase represents the phases of operation that the
<a href="../../../../../org/apache/calcite/plan/volcano/VolcanoPlanner.html" title="org.apache.calcite.plan.volcano中的类"><code>VolcanoPlanner</code></a> passes through during optimization of a tree of
<a href="../../../../../org/apache/calcite/rel/RelNode.html" title="org.apache.calcite.rel中的接口"><code>RelNode</code></a> objects.</div>
</td>
</tr>
</tbody>
</table>
</li>
</ul>
<a name="package.description">
<!-- -->
</a>
<h2 title="程序包org.apache.calcite.plan.volcano的说明">程序包org.apache.calcite.plan.volcano的说明</h2>
<div class="block">Optimizes relational expressions.<p>&nbsp;</p>
<h2>Overview</h2>
<p>A <dfn>planner</dfn> (also known as an <dfn>optimizer</dfn>) finds the
most efficient implementation of a
<a href="../../../../../org/apache/calcite/rel/RelNode.html" title="org.apache.calcite.rel中的接口"><code>relational expression</code></a>.</p>
<p>Interface <a href="../../../../../org/apache/calcite/plan/RelOptPlanner.html" title="org.apache.calcite.plan中的接口"><code>RelOptPlanner</code></a> defines a planner,
and class <a href="../../../../../org/apache/calcite/plan/volcano/VolcanoPlanner.html" title="org.apache.calcite.plan.volcano中的类"><code>VolcanoPlanner</code></a> is an
implementation which uses a dynamic programming technique. It is based upon
the Volcano optimizer [<a href="#graefe93">1</a>].</p>
<p>Interface <a href="../../../../../org/apache/calcite/plan/RelOptCost.html" title="org.apache.calcite.plan中的接口"><code>RelOptCost</code></a> defines a cost
model; class <code>VolcanoCost</code> is
the implementation for a <code>VolcanoPlanner</code>.</p>
<p>A <code>RelSet</code> is a set of equivalent
relational expressions. They are equivalent because they will produce the
same result for any set of input data. It is an equivalence class: two
expressions are in the same set if and only if they are in the same
<code>RelSet</code>.</p>
<p>One of the unique features of the optimizer is that expressions can take
on a variety of physical traits. Each relational expression has a set of
traits. Each trait is described by an implementation of
<a href="../../../../../org/apache/calcite/plan/RelTraitDef.html" title="org.apache.calcite.plan中的类"><code>RelTraitDef</code></a>. Manifestations of the trait
implement <a href="../../../../../org/apache/calcite/plan/RelTrait.html" title="org.apache.calcite.plan中的接口"><code>RelTrait</code></a>. The most common example
of a trait is calling convention: the protocol used to receive and transmit
data. <a href="../../../../../org/apache/calcite/plan/ConventionTraitDef.html" title="org.apache.calcite.plan中的类"><code>ConventionTraitDef</code></a> defines the trait
and <a href="../../../../../org/apache/calcite/plan/Convention.html" title="org.apache.calcite.plan中的接口"><code>Convention</code></a> enumerates the
protocols. Every relational expression has a single calling convention by
which it returns its results. Some examples:</p>
<ul>
<li><a href="../../../../../org/apache/calcite/adapter/jdbc/JdbcConvention.html" title="org.apache.calcite.adapter.jdbc中的类"><code>JdbcConvention</code></a> is a fairly
conventional convention; the results are rows from a
<a href="https://docs.oracle.com/javase/8/docs/api/java/sql/ResultSet.html?is-external=true" title="java.sql中的类或接口"><code>JDBC result set</code></a>.
</li>
<li><a href="../../../../../org/apache/calcite/plan/Convention.html#NONE"><code>Convention.NONE</code></a> means that a
relational
expression cannot be implemented; typically there are rules which can
transform it to equivalent, implementable expressions.
</li>
<li><a href="../../../../../org/apache/calcite/adapter/enumerable/EnumerableConvention.html" title="org.apache.calcite.adapter.enumerable中的枚举"><code>EnumerableConvention</code></a>
implements the expression by
generating Java code. The code places the current row in a Java
variable, then
calls the piece of code which implements the consuming relational
expression.
For example, a Java array reader of the <code>names</code> array
would generate the following code:
<blockquote>
<pre>String[] names;
for (int i = 0; i &lt; names.length; i++) {
String name = names[i];
// ... code for consuming relational expression ...
}</pre>
</blockquote>
</li>
</ul>
<p>New traits are added to the planner in one of two ways:</p>
<ol>
<li>If the new trait is integral to Calcite, then each and every
implementation of <a href="../../../../../org/apache/calcite/rel/RelNode.html" title="org.apache.calcite.rel中的接口"><code>RelNode</code></a> should include
its manifestation of the trait as part of the
<a href="../../../../../org/apache/calcite/plan/RelTraitSet.html" title="org.apache.calcite.plan中的类"><code>RelTraitSet</code></a> passed to
<a href="../../../../../org/apache/calcite/rel/AbstractRelNode.html" title="org.apache.calcite.rel中的类"><code>AbstractRelNode</code></a>'s constructor. It may be
useful to provide alternate <code>AbstractRelNode</code> constructors
if most relational expressions use a single manifestation of the
trait.</li>
<li>If the new trait describes some aspect of a Farrago extension, then
the RelNodes passed to
<a href="../../../../../org/apache/calcite/plan/volcano/VolcanoPlanner.html#setRoot-org.apache.calcite.rel.RelNode-"><code>VolcanoPlanner.setRoot(org.apache.calcite.rel.RelNode)</code></a>
should have their trait sets expanded before the
<code>setRoot(RelNode)</code> call.</li>
</ol>
<p>The second trait extension mechanism requires that implementations of
<a href="https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html?is-external=true#clone--" title="java.lang中的类或接口"><code>Object.clone()</code></a> must not assume the
type and quantity of traits in their trait set. In either case, the new
<code>RelTraitDef</code> implementation must be
<a href="../../../../../org/apache/calcite/plan/volcano/VolcanoPlanner.html#addRelTraitDef-org.apache.calcite.plan.RelTraitDef-"><code>VolcanoPlanner.addRelTraitDef(org.apache.calcite.plan.RelTraitDef)</code></a>
registered with the planner.</p>
<p>A <a href="../../../../../org/apache/calcite/plan/volcano/RelSubset.html" title="org.apache.calcite.plan.volcano中的类"><code>RelSubset</code></a> is a subset of a
<code>RelSet</code> containing expressions which are equivalent and which
have the same <code>Convention</code>. Like <code>RelSet</code>, it is an
equivalence class.</p>
<h2>Related packages</h2>
<ul>
<li><code>&lt;a href="../rel/package-summary.html"&gt;org.apache.calcite.rel&lt;/a&gt;</code>
defines <a href="../../../../../org/apache/calcite/rel/RelNode.html" title="org.apache.calcite.rel中的接口"><code>relational expressions</code></a>.
</li>
</ul>
<h2>Details</h2>
<p>...</p>
<p>Sets merge when the result of a rule already exists in another set. This
implies that all of the expressions are equivalent. The RelSets are
merged, and so are the contained RelSubsets.</p>
<p>Expression registration.</p>
<ul>
<li>Expression is added to a set. We may find that an equivalent
expression already exists. Otherwise, this is the moment when an
expression becomes public, and fixed. Its digest is assigned, which
allows us to quickly find identical expressions.</li>
<li>We match operands, figure out which rules are applicable, and
generate rule calls. The rule calls are placed on a queue, and the
important ones are called later.</li>
<li>RuleCalls allow us to defer the invocation of rules. When an
expression is registered </li>
</ul>
<p>Algorithm</p>
<p>To optimize a relational expression R:</p>
<p>1. Register R.</p>
<p>2. Create rule-calls for all applicable rules.</p>
<p>3. Rank the rule calls by importance.</p>
<p>4. Call the most important rule</p>
<p>5. Repeat.</p>
<p><b>Importance</b>. A rule-call is important if it is likely to produce
better implementation of a relexp on the plan's critical path. Hence (a)
it produces a member of an important RelSubset, (b) its children are
cheap.</p>
<p>Conversion. Conversions are difficult because we have to work backwards
from the goal.</p>
<p><b>Rule triggering</b></p>
<p>The rules are:</p>
<ol>
<li><code>PushFilterThroughProjectRule</code>. Operands:
<blockquote>
<pre>Filter
Project</pre>
</blockquote>
</li>
<li><code>CombineProjectsRule</code>. Operands:
<blockquote>
<pre>Project
Project</pre>
</blockquote>
</li>
</ol>
<p>A rule can be triggered by a change to any of its operands. Consider the
rule to combine two filters into one. It would have operands [Filter
[Filter]]. If I register a new Filter, it will trigger the rule in 2
places. Consider:</p>
<blockquote>
<pre>Project (deptno) [exp 1, subset A]
Filter (gender='F') [exp 2, subset B]
Project (deptno, gender, empno) [exp 3, subset C]
Project (deptno, gender, empno, salary) [exp 4, subset D]
TableScan (emp) [exp 0, subset X]</pre>
</blockquote>
<p>Apply <code>PushFilterThroughProjectRule</code> to [exp 2, exp 3]:</p>
<blockquote>
<pre>Project (deptno) [exp 1, subset A]
Project (deptno, gender, empno) [exp 5, subset B]
Filter (gender='F') [exp 6, subset E]
Project (deptno, gender, empno, salary) [exp 4, subset D]
TableScan (emp) [exp 0, subset X]</pre>
</blockquote>
<p>Two new expressions are created. Expression 5 is in subset B (because it
is equivalent to expression 2), and expression 6 is in a new equivalence
class, subset E.</p>
<p>The products of a applying a rule can trigger a cascade of rules. Even in
this simple system (2 rules and 4 initial expressions), two more rules
are triggered:</p>
<ul>
<li>Registering exp 5 triggers <code>CombineProjectsRule</code>(exp 1,
exp 5), which creates
<blockquote>
<pre>Project (deptno) [exp 7, subset A]
Filter (gender='F') [exp 6, subset E]
Project (deptno, gender, empno, salary) [exp 4, subset D]
TableScan (emp) [exp 0, subset X]</pre>
</blockquote>
</li>
<li>Registering exp 6 triggers
<code>PushFilterThroughProjectRule</code>(exp 6, exp 4), which
creates
<blockquote>
<pre>Project (deptno) [exp 1, subset A]
Project (deptno, gender, empno) [exp 5, subset B]
Project (deptno, gender, empno, salary) [exp 8, subset E]
Filter (gender='F') [exp 9, subset F]
TableScan (emp) [exp 0, subset X]</pre>
</blockquote>
</li>
</ul>
<p>Each rule application adds additional members to existing subsets. The
non-singleton subsets are now A {1, 7}, B {2, 5} and E {6, 8}, and new
combinations are possible. For example,
<code>CombineProjectsRule</code>(exp 7, exp 8) further reduces the depth
of the tree to:</p>
<blockquote>
<pre>Project (deptno) [exp 10, subset A]
Filter (gender='F') [exp 9, subset F]
TableScan (emp) [exp 0, subset X]</pre>
</blockquote>
<p>Todo: show how rules can cause subsets to merge.</p>
<p>Conclusion:</p>
<ol>
<li>A rule can be triggered by any of its operands.</li>
<li>If a subset is a child of more than one parent, it can trigger rule
matches for any of its parents.
</li>
<li>Registering one relexp can trigger several rules (and even the same
rule several times).</li>
<li>Firing rules can cause subsets to merge.</li>
</ol>
<h2>References</h2>
<p>1. <a id="graefe93" href="http://citeseer.nj.nec.com/graefe93volcano.html">The
Volcano Optimizer
Generator: Extensibility and Efficient Search - Goetz Graefe, William J.
McKenna
(1993)</a>.</p></div>
</div>
<!-- ======= START OF BOTTOM NAVBAR ====== -->
<div class="bottomNav"><a name="navbar.bottom">
<!-- -->
</a>
<div class="skipNav"><a href="#skip.navbar.bottom" title="跳过导航链接">跳过导航链接</a></div>
<a name="navbar.bottom.firstrow">
<!-- -->
</a>
<ul class="navList" title="导航">
<li><a href="../../../../../overview-summary.html">概览</a></li>
<li class="navBarCell1Rev">程序包</li>
<li></li>
<li><a href="package-tree.html"></a></li>
<li><a href="../../../../../deprecated-list.html">已过时</a></li>
<li><a href="../../../../../index-all.html">索引</a></li>
<li><a href="../../../../../help-doc.html">帮助</a></li>
</ul>
<div class="aboutLanguage"><b>Apache Calcite</b></div>
</div>
<div class="subNav">
<ul class="navList">
<li><a href="../../../../../org/apache/calcite/plan/hep/package-summary.html">上一个程序包</a></li>
<li><a href="../../../../../org/apache/calcite/prepare/package-summary.html">下一个程序包</a></li>
</ul>
<ul class="navList">
<li><a href="../../../../../index.html?org/apache/calcite/plan/volcano/package-summary.html" target="_top">框架</a></li>
<li><a href="package-summary.html" target="_top">无框架</a></li>
</ul>
<ul class="navList" id="allclasses_navbar_bottom">
<li><a href="../../../../../allclasses-noframe.html">所有类</a></li>
</ul>
<div>
<script type="text/javascript"><!--
allClassesLink = document.getElementById("allclasses_navbar_bottom");
if(window==top) {
allClassesLink.style.display = "block";
}
else {
allClassesLink.style.display = "none";
}
//-->
</script>
</div>
<a name="skip.navbar.bottom">
<!-- -->
</a></div>
<!-- ======== END OF BOTTOM NAVBAR ======= -->
<p class="legalCopy"><small>Copyright &copy; 2012-2020 Apache Software Foundation. All Rights Reserved.</small></p>
</body>
</html>