You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datafusion.apache.org by gi...@apache.org on 2025/02/28 01:56:00 UTC

(datafusion) branch asf-site updated: Publish built docs triggered by 58330b6b9b5e74762a5cd0e9de3d29c3e8636a1c

This is an automated email from the ASF dual-hosted git repository.

github-bot pushed a commit to branch asf-site
in repository https://gitbox.apache.org/repos/asf/datafusion.git


The following commit(s) were added to refs/heads/asf-site by this push:
     new 53d2d2d66f Publish built docs triggered by 58330b6b9b5e74762a5cd0e9de3d29c3e8636a1c
53d2d2d66f is described below

commit 53d2d2d66f89efb9aac852ebb0343be91a1cd086
Author: github-actions[bot] <gi...@users.noreply.github.com>
AuthorDate: Fri Feb 28 01:55:57 2025 +0000

    Publish built docs triggered by 58330b6b9b5e74762a5cd0e9de3d29c3e8636a1c
---
 _sources/library-user-guide/query-optimizer.md.txt | 107 ++++++++++++++
 library-user-guide/query-optimizer.html            | 155 +++++++++++++++++++++
 searchindex.js                                     |   2 +-
 3 files changed, 263 insertions(+), 1 deletion(-)

diff --git a/_sources/library-user-guide/query-optimizer.md.txt b/_sources/library-user-guide/query-optimizer.md.txt
index d2c688d383..5883fae7b8 100644
--- a/_sources/library-user-guide/query-optimizer.md.txt
+++ b/_sources/library-user-guide/query-optimizer.md.txt
@@ -346,3 +346,110 @@ In the following example, the `type_coercion` and `simplify_expressions` passes
 ```
 
 [df]: https://crates.io/crates/datafusion
+
+## Thinking about Query Optimization
+
+Query optimization in DataFusion uses a cost based model. The cost based model
+relies on table and column level statistics to estimate selectivity; selectivity
+estimates are an important piece in cost analysis for filters and projections
+as they allow estimating the cost of joins and filters.
+
+An important piece of building these estimates is _boundary analysis_ which uses
+interval arithmetic to take an expression such as `a > 2500 AND a <= 5000` and
+build an accurate selectivity estimate that can then be used to find more efficient
+plans.
+
+#### `AnalysisContext` API
+
+The `AnalysisContext` serves as a shared knowledge base during expression evaluation
+and boundary analysis. Think of it as a dynamic repository that maintains information about:
+
+1. Current known boundaries for columns and expressions
+2. Statistics that have been gathered or inferred
+3. A mutable state that can be updated as analysis progresses
+
+What makes `AnalysisContext` particularly powerful is its ability to propagate information
+through the expression tree. As each node in the expression tree is analyzed, it can both
+read from and write to this shared context, allowing for sophisticated boundary analysis and inference.
+
+#### `ColumnStatistics` for Cardinality Estimation
+
+Column statistics form the foundation of optimization decisions. Rather than just tracking
+simple metrics, DataFusion's `ColumnStatistics` provides a rich set of information including:
+
+- Null value counts
+- Maximum and minimum values
+- Value sums (for numeric columns)
+- Distinct value counts
+
+Each of these statistics is wrapped in a `Precision` type that indicates whether the value is
+exact or estimated, allowing the optimizer to make informed decisions about the reliability
+of its cardinality estimates.
+
+### Boundary Analaysis Flow
+
+The boundary analysis process flows through several stages, with each stage building
+upon the information gathered in previous stages. The `AnalysisContext` is continuously
+updated as the analysis progresses through the expression tree.
+
+#### Expression Boundary Analysis
+
+When analyzing expressions, DataFusion runs boundary analysis using interval arithmetic.
+Consider a simple predicate like age > 18 AND age <= 25. The analysis flows as follows:
+
+1. Context Initialization
+
+   - Begin with known column statistics
+   - Set up initial boundaries based on column constraints
+   - Initialize the shared analysis context
+
+2. Expression Tree Walk
+
+   - Analyze each node in the expression tree
+   - Propagate boundary information upward
+   - Allow child nodes to influence parent boundaries
+
+3. Boundary Updates
+   - Each expression can update the shared context
+   - Changes flow through the entire expression tree
+   - Final boundaries inform optimization decisions
+
+### Working with the analysis API
+
+The following example shows how you can run an analysis pass on a physical expression
+to infer the selectivity of the expression and the space of possible values it can
+take.
+
+```rust
+fn analyze_filter_example() -> Result<()> {
+    // Create a schema with an 'age' column
+    let age = Field::new("age", DataType::Int64, false);
+    let schema = Arc::new(Schema::new(vec![age]));
+
+    // Define column statistics
+    let column_stats = ColumnStatistics {
+        null_count: Precision::Exact(0),
+        max_value: Precision::Exact(ScalarValue::Int64(Some(79))),
+        min_value: Precision::Exact(ScalarValue::Int64(Some(14))),
+        distinct_count: Precision::Absent,
+        sum_value: Precision::Absent,
+    };
+
+    // Create expression: age > 18 AND age <= 25
+    let expr = col("age")
+        .gt(lit(18i64))
+        .and(col("age").lt_eq(lit(25i64)));
+
+    // Initialize analysis context
+    let initial_boundaries = vec![ExprBoundaries::try_from_column(
+        &schema, &column_stats, 0)?];
+    let context = AnalysisContext::new(initial_boundaries);
+
+    // Analyze expression
+    let df_schema = DFSchema::try_from(schema)?;
+    let physical_expr = SessionContext::new().create_physical_expr(expr, &df_schema)?;
+    let analysis = analyze(&physical_expr, context, df_schema.as_ref())?;
+
+    Ok(())
+}
+```
diff --git a/library-user-guide/query-optimizer.html b/library-user-guide/query-optimizer.html
index ada46bd91e..5b4815f3af 100644
--- a/library-user-guide/query-optimizer.html
+++ b/library-user-guide/query-optimizer.html
@@ -580,6 +580,50 @@
    </li>
   </ul>
  </li>
+ <li class="toc-h2 nav-item toc-entry">
+  <a class="reference internal nav-link" href="#thinking-about-query-optimization">
+   Thinking about Query Optimization
+  </a>
+  <ul class="nav section-nav flex-column">
+   <li class="toc-h3 nav-item toc-entry">
+    <a class="reference internal nav-link" href="#analysiscontext-api">
+     <code class="docutils literal notranslate">
+      <span class="pre">
+       AnalysisContext
+      </span>
+     </code>
+     API
+    </a>
+   </li>
+   <li class="toc-h3 nav-item toc-entry">
+    <a class="reference internal nav-link" href="#columnstatistics-for-cardinality-estimation">
+     <code class="docutils literal notranslate">
+      <span class="pre">
+       ColumnStatistics
+      </span>
+     </code>
+     for Cardinality Estimation
+    </a>
+   </li>
+   <li class="toc-h3 nav-item toc-entry">
+    <a class="reference internal nav-link" href="#boundary-analaysis-flow">
+     Boundary Analaysis Flow
+    </a>
+    <ul class="nav section-nav flex-column">
+     <li class="toc-h4 nav-item toc-entry">
+      <a class="reference internal nav-link" href="#expression-boundary-analysis">
+       Expression Boundary Analysis
+      </a>
+     </li>
+    </ul>
+   </li>
+   <li class="toc-h3 nav-item toc-entry">
+    <a class="reference internal nav-link" href="#working-with-the-analysis-api">
+     Working with the analysis API
+    </a>
+   </li>
+  </ul>
+ </li>
 </ul>
 
 </nav>
@@ -918,6 +962,117 @@ in isolation (without any other rule being applied).</p>
 </div>
 </section>
 </section>
+<section id="thinking-about-query-optimization">
+<h2>Thinking about Query Optimization<a class="headerlink" href="#thinking-about-query-optimization" title="Link to this heading">¶</a></h2>
+<p>Query optimization in DataFusion uses a cost based model. The cost based model
+relies on table and column level statistics to estimate selectivity; selectivity
+estimates are an important piece in cost analysis for filters and projections
+as they allow estimating the cost of joins and filters.</p>
+<p>An important piece of building these estimates is <em>boundary analysis</em> which uses
+interval arithmetic to take an expression such as <code class="docutils literal notranslate"><span class="pre">a</span> <span class="pre">&gt;</span> <span class="pre">2500</span> <span class="pre">AND</span> <span class="pre">a</span> <span class="pre">&lt;=</span> <span class="pre">5000</span></code> and
+build an accurate selectivity estimate that can then be used to find more efficient
+plans.</p>
+<section id="analysiscontext-api">
+<h3><code class="docutils literal notranslate"><span class="pre">AnalysisContext</span></code> API<a class="headerlink" href="#analysiscontext-api" title="Link to this heading">¶</a></h3>
+<p>The <code class="docutils literal notranslate"><span class="pre">AnalysisContext</span></code> serves as a shared knowledge base during expression evaluation
+and boundary analysis. Think of it as a dynamic repository that maintains information about:</p>
+<ol class="arabic simple">
+<li><p>Current known boundaries for columns and expressions</p></li>
+<li><p>Statistics that have been gathered or inferred</p></li>
+<li><p>A mutable state that can be updated as analysis progresses</p></li>
+</ol>
+<p>What makes <code class="docutils literal notranslate"><span class="pre">AnalysisContext</span></code> particularly powerful is its ability to propagate information
+through the expression tree. As each node in the expression tree is analyzed, it can both
+read from and write to this shared context, allowing for sophisticated boundary analysis and inference.</p>
+</section>
+<section id="columnstatistics-for-cardinality-estimation">
+<h3><code class="docutils literal notranslate"><span class="pre">ColumnStatistics</span></code> for Cardinality Estimation<a class="headerlink" href="#columnstatistics-for-cardinality-estimation" title="Link to this heading">¶</a></h3>
+<p>Column statistics form the foundation of optimization decisions. Rather than just tracking
+simple metrics, DataFusion’s <code class="docutils literal notranslate"><span class="pre">ColumnStatistics</span></code> provides a rich set of information including:</p>
+<ul class="simple">
+<li><p>Null value counts</p></li>
+<li><p>Maximum and minimum values</p></li>
+<li><p>Value sums (for numeric columns)</p></li>
+<li><p>Distinct value counts</p></li>
+</ul>
+<p>Each of these statistics is wrapped in a <code class="docutils literal notranslate"><span class="pre">Precision</span></code> type that indicates whether the value is
+exact or estimated, allowing the optimizer to make informed decisions about the reliability
+of its cardinality estimates.</p>
+</section>
+<section id="boundary-analaysis-flow">
+<h3>Boundary Analaysis Flow<a class="headerlink" href="#boundary-analaysis-flow" title="Link to this heading">¶</a></h3>
+<p>The boundary analysis process flows through several stages, with each stage building
+upon the information gathered in previous stages. The <code class="docutils literal notranslate"><span class="pre">AnalysisContext</span></code> is continuously
+updated as the analysis progresses through the expression tree.</p>
+<section id="expression-boundary-analysis">
+<h4>Expression Boundary Analysis<a class="headerlink" href="#expression-boundary-analysis" title="Link to this heading">¶</a></h4>
+<p>When analyzing expressions, DataFusion runs boundary analysis using interval arithmetic.
+Consider a simple predicate like age &gt; 18 AND age &lt;= 25. The analysis flows as follows:</p>
+<ol class="arabic simple">
+<li><p>Context Initialization</p>
+<ul class="simple">
+<li><p>Begin with known column statistics</p></li>
+<li><p>Set up initial boundaries based on column constraints</p></li>
+<li><p>Initialize the shared analysis context</p></li>
+</ul>
+</li>
+<li><p>Expression Tree Walk</p>
+<ul class="simple">
+<li><p>Analyze each node in the expression tree</p></li>
+<li><p>Propagate boundary information upward</p></li>
+<li><p>Allow child nodes to influence parent boundaries</p></li>
+</ul>
+</li>
+<li><p>Boundary Updates</p>
+<ul class="simple">
+<li><p>Each expression can update the shared context</p></li>
+<li><p>Changes flow through the entire expression tree</p></li>
+<li><p>Final boundaries inform optimization decisions</p></li>
+</ul>
+</li>
+</ol>
+</section>
+</section>
+<section id="working-with-the-analysis-api">
+<h3>Working with the analysis API<a class="headerlink" href="#working-with-the-analysis-api" title="Link to this heading">¶</a></h3>
+<p>The following example shows how you can run an analysis pass on a physical expression
+to infer the selectivity of the expression and the space of possible values it can
+take.</p>
+<div class="highlight-rust notranslate"><div class="highlight"><pre><span></span><span class="k">fn</span><span class="w"> </span><span class="nf">analyze_filter_example</span><span class="p">()</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="nb">Result</span><span class="o">&lt;</span><span class="p">()</span><span class="o">&gt;</span><span class="w"> </span><span class="p">{</span>
+<span class="w">    </span><span class="c1">// Create a schema with an &#39;age&#39; column</span>
+<span class="w">    </span><span class="kd">let</span><span class="w"> </span><span class="n">age</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">Field</span><span class="p">::</span><span class="n">new</span><span class="p">(</span><span class="s">&quot;age&quot;</span><span class="p">,</span><span class="w"> </span><span class="n">DataType</span><span class="p">::</span><span class="n">Int64</span><span class="p">,</span><span class="w"> </ [...]
+<span class="w">    </span><span class="kd">let</span><span class="w"> </span><span class="n">schema</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">Arc</span><span class="p">::</span><span class="n">new</span><span class="p">(</span><span class="n">Schema</span><span class="p">::</span><span class="n">new</span><span class="p">(</span><span class="fm">vec!</span><span class="p">[</span><span class="n">age</span><span class="p">]));</span>
+
+<span class="w">    </span><span class="c1">// Define column statistics</span>
+<span class="w">    </span><span class="kd">let</span><span class="w"> </span><span class="n">column_stats</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">ColumnStatistics</span><span class="w"> </span><span class="p">{</span>
+<span class="w">        </span><span class="n">null_count</span><span class="p">:</span><span class="w"> </span><span class="nc">Precision</span><span class="p">::</span><span class="n">Exact</span><span class="p">(</span><span class="mi">0</span><span class="p">),</span>
+<span class="w">        </span><span class="n">max_value</span><span class="p">:</span><span class="w"> </span><span class="nc">Precision</span><span class="p">::</span><span class="n">Exact</span><span class="p">(</span><span class="n">ScalarValue</span><span class="p">::</span><span class="n">Int64</span><span class="p">(</span><span class="nb">Some</span><span class="p">(</span><span class="mi">79</span><span class="p">))),</span>
+<span class="w">        </span><span class="n">min_value</span><span class="p">:</span><span class="w"> </span><span class="nc">Precision</span><span class="p">::</span><span class="n">Exact</span><span class="p">(</span><span class="n">ScalarValue</span><span class="p">::</span><span class="n">Int64</span><span class="p">(</span><span class="nb">Some</span><span class="p">(</span><span class="mi">14</span><span class="p">))),</span>
+<span class="w">        </span><span class="n">distinct_count</span><span class="p">:</span><span class="w"> </span><span class="nc">Precision</span><span class="p">::</span><span class="n">Absent</span><span class="p">,</span>
+<span class="w">        </span><span class="n">sum_value</span><span class="p">:</span><span class="w"> </span><span class="nc">Precision</span><span class="p">::</span><span class="n">Absent</span><span class="p">,</span>
+<span class="w">    </span><span class="p">};</span>
+
+<span class="w">    </span><span class="c1">// Create expression: age &gt; 18 AND age &lt;= 25</span>
+<span class="w">    </span><span class="kd">let</span><span class="w"> </span><span class="n">expr</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">col</span><span class="p">(</span><span class="s">&quot;age&quot;</span><span class="p">)</span>
+<span class="w">        </span><span class="p">.</span><span class="n">gt</span><span class="p">(</span><span class="n">lit</span><span class="p">(</span><span class="mi">18</span><span class="k">i64</span><span class="p">))</span>
+<span class="w">        </span><span class="p">.</span><span class="n">and</span><span class="p">(</span><span class="n">col</span><span class="p">(</span><span class="s">&quot;age&quot;</span><span class="p">).</span><span class="n">lt_eq</span><span class="p">(</span><span class="n">lit</span><span class="p">(</span><span class="mi">25</span><span class="k">i64</span><span class="p">)));</span>
+
+<span class="w">    </span><span class="c1">// Initialize analysis context</span>
+<span class="w">    </span><span class="kd">let</span><span class="w"> </span><span class="n">initial_boundaries</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="fm">vec!</span><span class="p">[</span><span class="n">ExprBoundaries</span><span class="p">::</span><span class="n">try_from_column</span><span class="p">(</span>
+<span class="w">        </span><span class="o">&amp;</span><span class="n">schema</span><span class="p">,</span><span class="w"> </span><span class="o">&amp;</span><span class="n">column_stats</span><span class="p">,</span><span class="w"> </span><span class="mi">0</span><span class="p">)</span><span class="o">?</span><span class="p">];</span>
+<span class="w">    </span><span class="kd">let</span><span class="w"> </span><span class="n">context</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">AnalysisContext</span><span class="p">::</span><span class="n">new</span><span class="p">(</span><span class="n">initial_boundaries</span><span class="p">);</span>
+
+<span class="w">    </span><span class="c1">// Analyze expression</span>
+<span class="w">    </span><span class="kd">let</span><span class="w"> </span><span class="n">df_schema</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">DFSchema</span><span class="p">::</span><span class="n">try_from</span><span class="p">(</span><span class="n">schema</span><span class="p">)</span><span class="o">?</span><span class="p">;</span>
+<span class="w">    </span><span class="kd">let</span><span class="w"> </span><span class="n">physical_expr</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">SessionContext</span><span class="p">::</span><span class="n">new</span><span class="p">().</span><span class="n">create_physical_expr</span><span class="p">(</span><span class="n">expr</span><span class="p">,</span><span class="w"> </span><span class="o">&amp;</span><span class="n">df_sch [...]
+<span class="w">    </span><span class="kd">let</span><span class="w"> </span><span class="n">analysis</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">analyze</span><span class="p">(</span><span class="o">&amp;</span><span class="n">physical_expr</span><span class="p">,</span><span class="w"> </span><span class="n">context</span><span class="p">,</span><span class="w"> </span><span class="n">df_schema</span><span class="p">.</span><span class [...]
+
+<span class="w">    </span><span class="nb">Ok</span><span class="p">(())</span>
+<span class="p">}</span>
+</pre></div>
+</div>
+</section>
+</section>
 </section>
 
 
diff --git a/searchindex.js b/searchindex.js
index f3cacfbf35..49aa9a8e92 100644
--- a/searchindex.js
+++ b/searchindex.js
@@ -1 +1 @@
-Search.setIndex({"alltitles":{"!=":[[51,"op-neq"]],"!~":[[51,"op-re-not-match"]],"!~*":[[51,"op-re-not-match-i"]],"!~~":[[51,"id19"]],"!~~*":[[51,"id20"]],"#":[[51,"op-bit-xor"]],"%":[[51,"op-modulo"]],"&":[[51,"op-bit-and"]],"(relation, name) tuples in logical fields and logical columns are unique":[[11,"relation-name-tuples-in-logical-fields-and-logical-columns-are-unique"]],"*":[[51,"op-multiply"]],"+":[[51,"op-plus"]],"-":[[51,"op-minus"]],"/":[[51,"op-divide"]],"2022 Q2":[[9,"q2"]], [...]
\ No newline at end of file
+Search.setIndex({"alltitles":{"!=":[[51,"op-neq"]],"!~":[[51,"op-re-not-match"]],"!~*":[[51,"op-re-not-match-i"]],"!~~":[[51,"id19"]],"!~~*":[[51,"id20"]],"#":[[51,"op-bit-xor"]],"%":[[51,"op-modulo"]],"&":[[51,"op-bit-and"]],"(relation, name) tuples in logical fields and logical columns are unique":[[11,"relation-name-tuples-in-logical-fields-and-logical-columns-are-unique"]],"*":[[51,"op-multiply"]],"+":[[51,"op-plus"]],"-":[[51,"op-minus"]],"/":[[51,"op-divide"]],"2022 Q2":[[9,"q2"]], [...]
\ No newline at end of file


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org