javadocAggregate/org/apache/calcite/plan/volcano/package-summary.html - calcite-site - Git at Google

 <!DOCTYPE HTML>
 <html lang="en">
 <head>
 <!-- Generated by javadoc (17) -->
 <title>org.apache.calcite.plan.volcano (Apache Calcite API)</title>
 <meta name="viewport" content="width=device-width, initial-scale=1">
 <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
 <meta name="description" content="declaration: package: org.apache.calcite.plan.volcano">
 <meta name="generator" content="javadoc/PackageWriterImpl">
 <link rel="stylesheet" type="text/css" href="../../../../../stylesheet.css" title="Style">
 <link rel="stylesheet" type="text/css" href="../../../../../script-dir/jquery-ui.min.css" title="Style">
 <link rel="stylesheet" type="text/css" href="../../../../../jquery-ui.overrides.css" title="Style">
 <script type="text/javascript" src="../../../../../script.js"></script>
 <script type="text/javascript" src="../../../../../script-dir/jquery-3.5.1.min.js"></script>
 <script type="text/javascript" src="../../../../../script-dir/jquery-ui.min.js"></script>
 </head>
 <body class="package-declaration-page">
 <script type="text/javascript">var evenRowColor = "even-row-color";
 var oddRowColor = "odd-row-color";
 var tableTab = "table-tab";
 var activeTableTab = "active-table-tab";
 var pathtoroot = "../../../../../";
 loadScripts(document, 'script');</script>
 <noscript>
 <div>JavaScript is disabled on your browser.</div>
 </noscript>
 <div class="flex-box">
 <header role="banner" class="flex-header">
 <nav role="navigation">
 <!-- ========= START OF TOP NAVBAR ======= -->
 <div class="top-nav" id="navbar-top">
 <div class="skip-nav"><a href="#skip-navbar-top" title="Skip navigation links">Skip navigation links</a></div>
 <div class="about-language"><b>Apache Calcite</b></div>
 <ul id="navbar-top-firstrow" class="nav-list" title="Navigation">
 <li><a href="../../../../../index.html">Overview</a></li>
 <li class="nav-bar-cell1-rev">Package</li>
 <li>Class</li>
 <li><a href="package-tree.html">Tree</a></li>
 <li><a href="../../../../../deprecated-list.html">Deprecated</a></li>
 <li><a href="../../../../../index-all.html">Index</a></li>
 <li><a href="../../../../../help-doc.html#package">Help</a></li>
 </ul>
 </div>
 <div class="sub-nav">
 <div>
 <ul class="sub-nav-list">
 <li>Package:&nbsp;</li>
 <li><a href="#package-description">Description</a>&nbsp;|&nbsp;</li>
 <li><a href="#related-package-summary">Related Packages</a>&nbsp;|&nbsp;</li>
 <li><a href="#class-summary">Classes and Interfaces</a></li>
 </ul>
 </div>
 <div class="nav-list-search"><label for="search-input">SEARCH:</label>
 <input type="text" id="search-input" value="search" disabled="disabled">
 <input type="reset" id="reset-button" value="reset" disabled="disabled">
 </div>
 </div>
 <!-- ========= END OF TOP NAVBAR ========= -->
 <span class="skip-nav" id="skip-navbar-top"></span></nav>
 </header>
 <div class="flex-content">
 <main role="main">
 <div class="header">
 <h1 title="Package org.apache.calcite.plan.volcano" class="title">Package org.apache.calcite.plan.volcano</h1>
 </div>
 <hr>
 <div class="package-signature">package <span class="element-name">org.apache.calcite.plan.volcano</span></div>
 <section class="package-description" id="package-description">
 <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="../../rel/RelNode.html" title="interface in org.apache.calcite.rel"><code>relational expression</code></a>.</p>

  <p>Interface <a href="../RelOptPlanner.html" title="interface in org.apache.calcite.plan"><code>RelOptPlanner</code></a> defines a planner,
  and class <a href="VolcanoPlanner.html" title="class in 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="../RelOptCost.html" title="interface in 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="../RelTraitDef.html" title="class in org.apache.calcite.plan"><code>RelTraitDef</code></a>.  Manifestations of the trait
  implement <a href="../RelTrait.html" title="interface in 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="../ConventionTraitDef.html" title="class in org.apache.calcite.plan"><code>ConventionTraitDef</code></a> defines the trait
  and <a href="../Convention.html" title="interface in 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="../../adapter/jdbc/JdbcConvention.html" title="class in 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/en/java/javase/17/docs/api/java.sql/java/sql/ResultSet.html" title="class or interface in java.sql" class="external-link"><code>JDBC result set</code></a>.
      </li>
      <li><a href="../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="../../adapter/enumerable/EnumerableConvention.html" title="enum in 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="../../rel/RelNode.html" title="interface in org.apache.calcite.rel"><code>RelNode</code></a> should include
      its manifestation of the trait as part of the
      <a href="../RelTraitSet.html" title="class in org.apache.calcite.plan"><code>RelTraitSet</code></a> passed to
      <a href="../../rel/AbstractRelNode.html" title="class in 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="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/en/java/javase/17/docs/api/java.base/java/lang/Object.html#clone()" title="class or interface in java.lang" class="external-link"><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="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="RelSubset.html" title="class in 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="../../rel/RelNode.html" title="interface in 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>
 </section>
 <section class="summary">
 <ul class="summary-list">
 <li>
 <div id="related-package-summary">
 <div class="caption"><span>Related Packages</span></div>
 <div class="summary-table two-column-summary">
 <div class="table-header col-first">Package</div>
 <div class="table-header col-last">Description</div>
 <div class="col-first even-row-color"><a href="../package-summary.html">org.apache.calcite.plan</a></div>
 <div class="col-last even-row-color">
 <div class="block">Defines interfaces for constructing rule-based optimizers of
  relational expressions.</div>
 </div>
 <div class="col-first odd-row-color"><a href="../hep/package-summary.html">org.apache.calcite.plan.hep</a></div>
 <div class="col-last odd-row-color">
 <div class="block">Provides a heuristic planner implementation for the interfaces in
  <a href="../package-summary.html"><code>org.apache.calcite.plan</code></a>.</div>
 </div>
 <div class="col-first even-row-color"><a href="../visualizer/package-summary.html">org.apache.calcite.plan.visualizer</a></div>
 <div class="col-last even-row-color">
 <div class="block">A visualizer showing how the rules are applied step-by-step.</div>
 </div>
 </div>
 </div>
 </li>
 <li>
 <div id="class-summary">
 <div class="table-tabs" role="tablist" aria-orientation="horizontal"><button id="class-summary-tab0" role="tab" aria-selected="true" aria-controls="class-summary.tabpanel" tabindex="0" onkeydown="switchTab(event)" onclick="show('class-summary', 'class-summary', 2)" class="active-table-tab">All Classes and Interfaces</button><button id="class-summary-tab1" role="tab" aria-selected="false" aria-controls="class-summary.tabpanel" tabindex="-1" onkeydown="switchTab(event)" onclick="show('class-summary', 'class-summary-tab1', 2)" class="table-tab">Interfaces</button><button id="class-summary-tab2" role="tab" aria-selected="false" aria-controls="class-summary.tabpanel" tabindex="-1" onkeydown="switchTab(event)" onclick="show('class-summary', 'class-summary-tab2', 2)" class="table-tab">Classes</button><button id="class-summary-tab5" role="tab" aria-selected="false" aria-controls="class-summary.tabpanel" tabindex="-1" onkeydown="switchTab(event)" onclick="show('class-summary', 'class-summary-tab5', 2)" class="table-tab">Exceptions</button></div>
 <div id="class-summary.tabpanel" role="tabpanel">
 <div class="summary-table two-column-summary" aria-labelledby="class-summary-tab0">
 <div class="table-header col-first">Class</div>
 <div class="table-header col-last">Description</div>
 <div class="col-first even-row-color class-summary class-summary-tab2"><a href="AbstractConverter.html" title="class in org.apache.calcite.plan.volcano">AbstractConverter</a></div>
 <div class="col-last even-row-color class-summary class-summary-tab2">
 <div class="block">Converts a relational expression to any given output convention.</div>
 </div>
 <div class="col-first odd-row-color class-summary class-summary-tab2"><a href="AbstractConverter.ExpandConversionRule.html" title="class in org.apache.calcite.plan.volcano">AbstractConverter.ExpandConversionRule</a></div>
 <div class="col-last odd-row-color class-summary class-summary-tab2">
 <div class="block">Rule that converts an <a href="AbstractConverter.html" title="class in org.apache.calcite.plan.volcano"><code>AbstractConverter</code></a> into a chain of
  converters from the source relation to the target traits.</div>
 </div>
 <div class="col-first even-row-color class-summary class-summary-tab1"><a href="AbstractConverter.ExpandConversionRule.Config.html" title="interface in org.apache.calcite.plan.volcano">AbstractConverter.ExpandConversionRule.Config</a></div>
 <div class="col-last even-row-color class-summary class-summary-tab1">
 <div class="block">Rule configuration.</div>
 </div>
 <div class="col-first odd-row-color class-summary class-summary-tab2"><a href="RelSubset.html" title="class in org.apache.calcite.plan.volcano">RelSubset</a></div>
 <div class="col-last odd-row-color class-summary class-summary-tab2">
 <div class="block">Subset of an equivalence class where all relational expressions have the
  same physical properties.</div>
 </div>
 <div class="col-first even-row-color class-summary class-summary-tab2"><a href="RuleQueue.html" title="class in org.apache.calcite.plan.volcano">RuleQueue</a></div>
 <div class="col-last even-row-color class-summary class-summary-tab2">
 <div class="block">A data structure that manages rule matches for RuleDriver.</div>
 </div>
 <div class="col-first odd-row-color class-summary class-summary-tab2"><a href="VolcanoPlanner.html" title="class in org.apache.calcite.plan.volcano">VolcanoPlanner</a></div>
 <div class="col-last odd-row-color class-summary class-summary-tab2">
 <div class="block">VolcanoPlanner optimizes queries by transforming expressions selectively
  according to a dynamic programming algorithm.</div>
 </div>
 <div class="col-first even-row-color class-summary class-summary-tab2"><a href="VolcanoRelMetadataProvider.html" title="class in org.apache.calcite.plan.volcano">VolcanoRelMetadataProvider</a></div>
 <div class="col-last even-row-color class-summary class-summary-tab2">Deprecated.</div>
 <div class="col-first odd-row-color class-summary class-summary-tab2"><a href="VolcanoRuleCall.html" title="class in org.apache.calcite.plan.volcano">VolcanoRuleCall</a></div>
 <div class="col-last odd-row-color class-summary class-summary-tab2">
 <div class="block"><code>VolcanoRuleCall</code> implements the <a href="../RelOptRuleCall.html" title="class in org.apache.calcite.plan"><code>RelOptRuleCall</code></a> interface
  for VolcanoPlanner.</div>
 </div>
 <div class="col-first even-row-color class-summary class-summary-tab5"><a href="VolcanoTimeoutException.html" title="class in org.apache.calcite.plan.volcano">VolcanoTimeoutException</a></div>
 <div class="col-last even-row-color class-summary class-summary-tab5">
 <div class="block">Indicates that planning timed out.</div>
 </div>
 </div>
 </div>
 </div>
 </li>
 </ul>
 </section>
 </main>
 <footer role="contentinfo">
 <hr>
 <p class="legal-copy"><small>Copyright &copy; 2012-2023 Apache Software Foundation. All Rights Reserved.</small></p>
 </footer>
 </div>
 </div>
 </body>
 </html>
	<!DOCTYPE HTML>
	<html lang="en">
	<head>
	<!-- Generated by javadoc (17) -->
	<title>org.apache.calcite.plan.volcano (Apache Calcite API)</title>
	<meta name="viewport" content="width=device-width, initial-scale=1">
	<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
	<meta name="description" content="declaration: package: org.apache.calcite.plan.volcano">
	<meta name="generator" content="javadoc/PackageWriterImpl">
	<link rel="stylesheet" type="text/css" href="../../../../../stylesheet.css" title="Style">
	<link rel="stylesheet" type="text/css" href="../../../../../script-dir/jquery-ui.min.css" title="Style">
	<link rel="stylesheet" type="text/css" href="../../../../../jquery-ui.overrides.css" title="Style">
	<script type="text/javascript" src="../../../../../script.js"></script>
	<script type="text/javascript" src="../../../../../script-dir/jquery-3.5.1.min.js"></script>
	<script type="text/javascript" src="../../../../../script-dir/jquery-ui.min.js"></script>
	</head>
	<body class="package-declaration-page">
	<script type="text/javascript">var evenRowColor = "even-row-color";
	var oddRowColor = "odd-row-color";
	var tableTab = "table-tab";
	var activeTableTab = "active-table-tab";
	var pathtoroot = "../../../../../";
	loadScripts(document, 'script');</script>
	<noscript>
	<div>JavaScript is disabled on your browser.</div>
	</noscript>
	<div class="flex-box">
	<header role="banner" class="flex-header">
	<nav role="navigation">
	<!-- ========= START OF TOP NAVBAR ======= -->
	<div class="top-nav" id="navbar-top">
	<div class="skip-nav"><a href="#skip-navbar-top" title="Skip navigation links">Skip navigation links</a></div>
	<div class="about-language"><b>Apache Calcite</b></div>
	<ul id="navbar-top-firstrow" class="nav-list" title="Navigation">
	<li><a href="../../../../../index.html">Overview</a></li>
	<li class="nav-bar-cell1-rev">Package</li>
	<li>Class</li>
	<li><a href="package-tree.html">Tree</a></li>
	<li><a href="../../../../../deprecated-list.html">Deprecated</a></li>
	<li><a href="../../../../../index-all.html">Index</a></li>
	<li><a href="../../../../../help-doc.html#package">Help</a></li>
	</ul>
	</div>
	<div class="sub-nav">
	<div>
	<ul class="sub-nav-list">
	<li>Package: </li>
	<li><a href="#package-description">Description</a> \| </li>
	<li><a href="#related-package-summary">Related Packages</a> \| </li>
	<li><a href="#class-summary">Classes and Interfaces</a></li>
	</ul>
	</div>
	<div class="nav-list-search"><label for="search-input">SEARCH:</label>
	<input type="text" id="search-input" value="search" disabled="disabled">
	<input type="reset" id="reset-button" value="reset" disabled="disabled">
	</div>
	</div>
	<!-- ========= END OF TOP NAVBAR ========= -->
	<span class="skip-nav" id="skip-navbar-top"></span></nav>
	</header>
	<div class="flex-content">
	<main role="main">
	<div class="header">
	<h1 title="Package org.apache.calcite.plan.volcano" class="title">Package org.apache.calcite.plan.volcano</h1>
	</div>
	<hr>
	<div class="package-signature">package <span class="element-name">org.apache.calcite.plan.volcano</span></div>
	<section class="package-description" id="package-description">
	<div class="block">Optimizes relational expressions.<p> </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="../../rel/RelNode.html" title="interface in org.apache.calcite.rel"><code>relational expression</code></a>.</p>

	<p>Interface <a href="../RelOptPlanner.html" title="interface in org.apache.calcite.plan"><code>RelOptPlanner</code></a> defines a planner,
	and class <a href="VolcanoPlanner.html" title="class in 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="../RelOptCost.html" title="interface in 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="../RelTraitDef.html" title="class in org.apache.calcite.plan"><code>RelTraitDef</code></a>. Manifestations of the trait
	implement <a href="../RelTrait.html" title="interface in 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="../ConventionTraitDef.html" title="class in org.apache.calcite.plan"><code>ConventionTraitDef</code></a> defines the trait
	and <a href="../Convention.html" title="interface in 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="../../adapter/jdbc/JdbcConvention.html" title="class in 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/en/java/javase/17/docs/api/java.sql/java/sql/ResultSet.html" title="class or interface in java.sql" class="external-link"><code>JDBC result set</code></a>.
	</li>
	<li><a href="../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="../../adapter/enumerable/EnumerableConvention.html" title="enum in 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 < 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="../../rel/RelNode.html" title="interface in org.apache.calcite.rel"><code>RelNode</code></a> should include
	its manifestation of the trait as part of the
	<a href="../RelTraitSet.html" title="class in org.apache.calcite.plan"><code>RelTraitSet</code></a> passed to
	<a href="../../rel/AbstractRelNode.html" title="class in 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="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/en/java/javase/17/docs/api/java.base/java/lang/Object.html#clone()" title="class or interface in java.lang" class="external-link"><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="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="RelSubset.html" title="class in 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><a href="../rel/package-summary.html">org.apache.calcite.rel</a></code>
	defines <a href="../../rel/RelNode.html" title="interface in 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>
	</section>
	<section class="summary">
	<ul class="summary-list">
	<li>
	<div id="related-package-summary">
	<div class="caption"><span>Related Packages</span></div>
	<div class="summary-table two-column-summary">
	<div class="table-header col-first">Package</div>
	<div class="table-header col-last">Description</div>
	<div class="col-first even-row-color"><a href="../package-summary.html">org.apache.calcite.plan</a></div>
	<div class="col-last even-row-color">
	<div class="block">Defines interfaces for constructing rule-based optimizers of
	relational expressions.</div>
	</div>
	<div class="col-first odd-row-color"><a href="../hep/package-summary.html">org.apache.calcite.plan.hep</a></div>
	<div class="col-last odd-row-color">
	<div class="block">Provides a heuristic planner implementation for the interfaces in
	<a href="../package-summary.html"><code>org.apache.calcite.plan</code></a>.</div>
	</div>
	<div class="col-first even-row-color"><a href="../visualizer/package-summary.html">org.apache.calcite.plan.visualizer</a></div>
	<div class="col-last even-row-color">
	<div class="block">A visualizer showing how the rules are applied step-by-step.</div>
	</div>
	</div>
	</div>
	</li>
	<li>
	<div id="class-summary">
	<div class="table-tabs" role="tablist" aria-orientation="horizontal"><button id="class-summary-tab0" role="tab" aria-selected="true" aria-controls="class-summary.tabpanel" tabindex="0" onkeydown="switchTab(event)" onclick="show('class-summary', 'class-summary', 2)" class="active-table-tab">All Classes and Interfaces</button><button id="class-summary-tab1" role="tab" aria-selected="false" aria-controls="class-summary.tabpanel" tabindex="-1" onkeydown="switchTab(event)" onclick="show('class-summary', 'class-summary-tab1', 2)" class="table-tab">Interfaces</button><button id="class-summary-tab2" role="tab" aria-selected="false" aria-controls="class-summary.tabpanel" tabindex="-1" onkeydown="switchTab(event)" onclick="show('class-summary', 'class-summary-tab2', 2)" class="table-tab">Classes</button><button id="class-summary-tab5" role="tab" aria-selected="false" aria-controls="class-summary.tabpanel" tabindex="-1" onkeydown="switchTab(event)" onclick="show('class-summary', 'class-summary-tab5', 2)" class="table-tab">Exceptions</button></div>
	<div id="class-summary.tabpanel" role="tabpanel">
	<div class="summary-table two-column-summary" aria-labelledby="class-summary-tab0">
	<div class="table-header col-first">Class</div>
	<div class="table-header col-last">Description</div>
	<div class="col-first even-row-color class-summary class-summary-tab2"><a href="AbstractConverter.html" title="class in org.apache.calcite.plan.volcano">AbstractConverter</a></div>
	<div class="col-last even-row-color class-summary class-summary-tab2">
	<div class="block">Converts a relational expression to any given output convention.</div>
	</div>
	<div class="col-first odd-row-color class-summary class-summary-tab2"><a href="AbstractConverter.ExpandConversionRule.html" title="class in org.apache.calcite.plan.volcano">AbstractConverter.ExpandConversionRule</a></div>
	<div class="col-last odd-row-color class-summary class-summary-tab2">
	<div class="block">Rule that converts an <a href="AbstractConverter.html" title="class in org.apache.calcite.plan.volcano"><code>AbstractConverter</code></a> into a chain of
	converters from the source relation to the target traits.</div>
	</div>
	<div class="col-first even-row-color class-summary class-summary-tab1"><a href="AbstractConverter.ExpandConversionRule.Config.html" title="interface in org.apache.calcite.plan.volcano">AbstractConverter.ExpandConversionRule.Config</a></div>
	<div class="col-last even-row-color class-summary class-summary-tab1">
	<div class="block">Rule configuration.</div>
	</div>
	<div class="col-first odd-row-color class-summary class-summary-tab2"><a href="RelSubset.html" title="class in org.apache.calcite.plan.volcano">RelSubset</a></div>
	<div class="col-last odd-row-color class-summary class-summary-tab2">
	<div class="block">Subset of an equivalence class where all relational expressions have the
	same physical properties.</div>
	</div>
	<div class="col-first even-row-color class-summary class-summary-tab2"><a href="RuleQueue.html" title="class in org.apache.calcite.plan.volcano">RuleQueue</a></div>
	<div class="col-last even-row-color class-summary class-summary-tab2">
	<div class="block">A data structure that manages rule matches for RuleDriver.</div>
	</div>
	<div class="col-first odd-row-color class-summary class-summary-tab2"><a href="VolcanoPlanner.html" title="class in org.apache.calcite.plan.volcano">VolcanoPlanner</a></div>
	<div class="col-last odd-row-color class-summary class-summary-tab2">
	<div class="block">VolcanoPlanner optimizes queries by transforming expressions selectively
	according to a dynamic programming algorithm.</div>
	</div>
	<div class="col-first even-row-color class-summary class-summary-tab2"><a href="VolcanoRelMetadataProvider.html" title="class in org.apache.calcite.plan.volcano">VolcanoRelMetadataProvider</a></div>
	<div class="col-last even-row-color class-summary class-summary-tab2">Deprecated.</div>
	<div class="col-first odd-row-color class-summary class-summary-tab2"><a href="VolcanoRuleCall.html" title="class in org.apache.calcite.plan.volcano">VolcanoRuleCall</a></div>
	<div class="col-last odd-row-color class-summary class-summary-tab2">
	<div class="block"><code>VolcanoRuleCall</code> implements the <a href="../RelOptRuleCall.html" title="class in org.apache.calcite.plan"><code>RelOptRuleCall</code></a> interface
	for VolcanoPlanner.</div>
	</div>
	<div class="col-first even-row-color class-summary class-summary-tab5"><a href="VolcanoTimeoutException.html" title="class in org.apache.calcite.plan.volcano">VolcanoTimeoutException</a></div>
	<div class="col-last even-row-color class-summary class-summary-tab5">
	<div class="block">Indicates that planning timed out.</div>
	</div>
	</div>
	</div>
	</div>
	</li>
	</ul>
	</section>
	</main>
	<footer role="contentinfo">
	<hr>
	<p class="legal-copy"><small>Copyright © 2012-2023 Apache Software Foundation. All Rights Reserved.</small></p>
	</footer>
	</div>
	</div>
	</body>
	</html>