Team Ai
Datasetpublic

codekingpro/portable-devtools

sourceHugging Faceupdated 5mo agoView on Hugging Face
1likes15kdownloads
row-estimation-examples.html399 linesDownload Raw Back to html
1<?xml version="1.0" encoding="UTF-8" standalone="no"?>2<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>76.1. Row Estimation Examples</title><link rel="stylesheet" type="text/css" href="stylesheet.css" /><link rev="made" href="pgsql-docs@lists.postgresql.org" /><meta name="generator" content="DocBook XSL Stylesheets Vsnapshot" /><link rel="prev" href="planner-stats-details.html" title="Chapter 76. How the Planner Uses Statistics" /><link rel="next" href="multivariate-statistics-examples.html" title="76.2. Multivariate Statistics Examples" /></head><body id="docContent" class="container-fluid col-10"><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="5" align="center">76.1. Row Estimation Examples</th></tr><tr><td width="10%" align="left"><a accesskey="p" href="planner-stats-details.html" title="Chapter 76. How the Planner Uses Statistics">Prev</a> </td><td width="10%" align="left"><a accesskey="u" href="planner-stats-details.html" title="Chapter 76. How the Planner Uses Statistics">Up</a></td><th width="60%" align="center">Chapter 76. How the Planner Uses Statistics</th><td width="10%" align="right"><a accesskey="h" href="index.html" title="PostgreSQL 16.3 Documentation">Home</a></td><td width="10%" align="right"> <a accesskey="n" href="multivariate-statistics-examples.html" title="76.2. Multivariate Statistics Examples">Next</a></td></tr></table><hr /></div><div class="sect1" id="ROW-ESTIMATION-EXAMPLES"><div class="titlepage"><div><div><h2 class="title" style="clear: both">76.1. Row Estimation Examples <a href="#ROW-ESTIMATION-EXAMPLES" class="id_link">#</a></h2></div></div></div><a id="id-1.10.27.4.2" class="indexterm"></a><p>3   The examples shown below use tables in the <span class="productname">PostgreSQL</span>4   regression test database.5   The outputs shown are taken from version 8.3.6   The behavior of earlier (or later) versions might vary.7   Note also that since <code class="command">ANALYZE</code> uses random sampling8   while producing statistics, the results will change slightly after9   any new <code class="command">ANALYZE</code>.10  </p><p>11   Let's start with a very simple query:12 13</p><pre class="programlisting">14EXPLAIN SELECT * FROM tenk1;15 16                         QUERY PLAN17-------------------------------------------------------------18 Seq Scan on tenk1  (cost=0.00..458.00 rows=10000 width=244)19</pre><p>20 21   How the planner determines the cardinality of <code class="structname">tenk1</code>22   is covered in <a class="xref" href="planner-stats.html" title="14.2. Statistics Used by the Planner">Section 14.2</a>, but is repeated here for23   completeness. The number of pages and rows is looked up in24   <code class="structname">pg_class</code>:25 26</p><pre class="programlisting">27SELECT relpages, reltuples FROM pg_class WHERE relname = 'tenk1';28 29 relpages | reltuples30----------+-----------31      358 |     1000032</pre><p>33 34    These numbers are current as of the last <code class="command">VACUUM</code> or35    <code class="command">ANALYZE</code> on the table.  The planner then fetches the36    actual current number of pages in the table (this is a cheap operation,37    not requiring a table scan).  If that is different from38    <code class="structfield">relpages</code> then39    <code class="structfield">reltuples</code> is scaled accordingly to40    arrive at a current number-of-rows estimate.  In the example above, the value of41    <code class="structfield">relpages</code> is up-to-date so the rows estimate is42    the same as <code class="structfield">reltuples</code>.43  </p><p>44   Let's move on to an example with a range condition in its45   <code class="literal">WHERE</code> clause:46 47</p><pre class="programlisting">48EXPLAIN SELECT * FROM tenk1 WHERE unique1 &lt; 1000;49 50                                   QUERY PLAN51-------------------------------------------------------------------​-------------52 Bitmap Heap Scan on tenk1  (cost=24.06..394.64 rows=1007 width=244)53   Recheck Cond: (unique1 &lt; 1000)54   -&gt;  Bitmap Index Scan on tenk1_unique1  (cost=0.00..23.80 rows=1007 width=0)55         Index Cond: (unique1 &lt; 1000)56</pre><p>57 58   The planner examines the <code class="literal">WHERE</code> clause condition59   and looks up the selectivity function for the operator60   <code class="literal">&lt;</code> in <code class="structname">pg_operator</code>.61   This is held in the column <code class="structfield">oprrest</code>,62   and the entry in this case is <code class="function">scalarltsel</code>.63   The <code class="function">scalarltsel</code> function retrieves the histogram for64   <code class="structfield">unique1</code> from65   <code class="structname">pg_statistic</code>.  For manual queries it is more66   convenient to look in the simpler <code class="structname">pg_stats</code>67   view:68 69</p><pre class="programlisting">70SELECT histogram_bounds FROM pg_stats71WHERE tablename='tenk1' AND attname='unique1';72 73                   histogram_bounds74------------------------------------------------------75 {0,993,1997,3050,4040,5036,5957,7057,8029,9016,9995}76</pre><p>77 78   Next the fraction of the histogram occupied by <span class="quote">“<span class="quote">&lt; 1000</span>”</span>79   is worked out. This is the selectivity. The histogram divides the range80   into equal frequency buckets, so all we have to do is locate the bucket81   that our value is in and count <span class="emphasis"><em>part</em></span> of it and82   <span class="emphasis"><em>all</em></span> of the ones before. The value 1000 is clearly in83   the second bucket (993–1997).  Assuming a linear distribution of84   values inside each bucket, we can calculate the selectivity as:85 86</p><pre class="programlisting">87selectivity = (1 + (1000 - bucket[2].min)/(bucket[2].max - bucket[2].min))/num_buckets88            = (1 + (1000 - 993)/(1997 - 993))/1089            = 0.10069790</pre><p>91 92   that is, one whole bucket plus a linear fraction of the second, divided by93   the number of buckets. The estimated number of rows can now be calculated as94   the product of the selectivity and the cardinality of95   <code class="structname">tenk1</code>:96 97</p><pre class="programlisting">98rows = rel_cardinality * selectivity99     = 10000 * 0.100697100     = 1007  (rounding off)101</pre><p>102  </p><p>103   Next let's consider an example with an equality condition in its104   <code class="literal">WHERE</code> clause:105 106</p><pre class="programlisting">107EXPLAIN SELECT * FROM tenk1 WHERE stringu1 = 'CRAAAA';108 109                        QUERY PLAN110----------------------------------------------------------111 Seq Scan on tenk1  (cost=0.00..483.00 rows=30 width=244)112   Filter: (stringu1 = 'CRAAAA'::name)113</pre><p>114 115   Again the planner examines the <code class="literal">WHERE</code> clause condition116   and looks up the selectivity function for <code class="literal">=</code>, which is117   <code class="function">eqsel</code>.  For equality estimation the histogram is118   not useful; instead the list of <em class="firstterm">most119   common values</em> (<acronym class="acronym">MCV</acronym>s) is used to determine the120   selectivity. Let's have a look at the MCVs, with some additional columns121   that will be useful later:122 123</p><pre class="programlisting">124SELECT null_frac, n_distinct, most_common_vals, most_common_freqs FROM pg_stats125WHERE tablename='tenk1' AND attname='stringu1';126 127null_frac         | 0128n_distinct        | 676129most_common_vals  | {EJAAAA,BBAAAA,CRAAAA,FCAAAA,FEAAAA,GSAAAA,​JOAAAA,MCAAAA,NAAAAA,WGAAAA}130most_common_freqs | {0.00333333,0.003,0.003,0.003,0.003,0.003,​0.003,0.003,0.003,0.003}131 132</pre><p>133 134   Since <code class="literal">CRAAAA</code> appears in the list of MCVs, the selectivity is135   merely the corresponding entry in the list of most common frequencies136   (<acronym class="acronym">MCF</acronym>s):137 138</p><pre class="programlisting">139selectivity = mcf[3]140            = 0.003141</pre><p>142 143   As before, the estimated number of rows is just the product of this with the144   cardinality of <code class="structname">tenk1</code>:145 146</p><pre class="programlisting">147rows = 10000 * 0.003148     = 30149</pre><p>150  </p><p>151   Now consider the same query, but with a constant that is not in the152   <acronym class="acronym">MCV</acronym> list:153 154</p><pre class="programlisting">155EXPLAIN SELECT * FROM tenk1 WHERE stringu1 = 'xxx';156 157                        QUERY PLAN158----------------------------------------------------------159 Seq Scan on tenk1  (cost=0.00..483.00 rows=15 width=244)160   Filter: (stringu1 = 'xxx'::name)161</pre><p>162 163   This is quite a different problem: how to estimate the selectivity when the164   value is <span class="emphasis"><em>not</em></span> in the <acronym class="acronym">MCV</acronym> list.165   The approach is to use the fact that the value is not in the list,166   combined with the knowledge of the frequencies for all of the167   <acronym class="acronym">MCV</acronym>s:168 169</p><pre class="programlisting">170selectivity = (1 - sum(mcv_freqs))/(num_distinct - num_mcv)171            = (1 - (0.00333333 + 0.003 + 0.003 + 0.003 + 0.003 + 0.003 +172                    0.003 + 0.003 + 0.003 + 0.003))/(676 - 10)173            = 0.0014559174</pre><p>175 176   That is, add up all the frequencies for the <acronym class="acronym">MCV</acronym>s and177   subtract them from one, then178   divide by the number of <span class="emphasis"><em>other</em></span> distinct values.179   This amounts to assuming that the fraction of the column that is not any180   of the MCVs is evenly distributed among all the other distinct values.181   Notice that there are no null values so we don't have to worry about those182   (otherwise we'd subtract the null fraction from the numerator as well).183   The estimated number of rows is then calculated as usual:184 185</p><pre class="programlisting">186rows = 10000 * 0.0014559187     = 15  (rounding off)188</pre><p>189  </p><p>190   The previous example with <code class="literal">unique1 &lt; 1000</code> was an191   oversimplification of what <code class="function">scalarltsel</code> really does;192   now that we have seen an example of the use of MCVs, we can fill in some193   more detail.  The example was correct as far as it went, because since194   <code class="structfield">unique1</code> is a unique column it has no MCVs (obviously, no195   value is any more common than any other value).  For a non-unique196   column, there will normally be both a histogram and an MCV list, and197   <span class="emphasis"><em>the histogram does not include the portion of the column198   population represented by the MCVs</em></span>.  We do things this way because199   it allows more precise estimation.  In this situation200   <code class="function">scalarltsel</code> directly applies the condition (e.g.,201   <span class="quote">“<span class="quote">&lt; 1000</span>”</span>) to each value of the MCV list, and adds up the202   frequencies of the MCVs for which the condition is true.  This gives203   an exact estimate of the selectivity within the portion of the table204   that is MCVs.  The histogram is then used in the same way as above205   to estimate the selectivity in the portion of the table that is not206   MCVs, and then the two numbers are combined to estimate the overall207   selectivity.  For example, consider208 209</p><pre class="programlisting">210EXPLAIN SELECT * FROM tenk1 WHERE stringu1 &lt; 'IAAAAA';211 212                         QUERY PLAN213------------------------------------------------------------214 Seq Scan on tenk1  (cost=0.00..483.00 rows=3077 width=244)215   Filter: (stringu1 &lt; 'IAAAAA'::name)216</pre><p>217 218   We already saw the MCV information for <code class="structfield">stringu1</code>,219   and here is its histogram:220 221</p><pre class="programlisting">222SELECT histogram_bounds FROM pg_stats223WHERE tablename='tenk1' AND attname='stringu1';224 225                                histogram_bounds226-------------------------------------------------------------------​-------------227 {AAAAAA,CQAAAA,FRAAAA,IBAAAA,KRAAAA,NFAAAA,PSAAAA,SGAAAA,VAAAAA,​XLAAAA,ZZAAAA}228</pre><p>229 230   Checking the MCV list, we find that the condition <code class="literal">stringu1 &lt;231   'IAAAAA'</code> is satisfied by the first six entries and not the last four,232   so the selectivity within the MCV part of the population is233 234</p><pre class="programlisting">235selectivity = sum(relevant mvfs)236            = 0.00333333 + 0.003 + 0.003 + 0.003 + 0.003 + 0.003237            = 0.01833333238</pre><p>239 240   Summing all the MCFs also tells us that the total fraction of the241   population represented by MCVs is 0.03033333, and therefore the242   fraction represented by the histogram is 0.96966667 (again, there243   are no nulls, else we'd have to exclude them here).  We can see244   that the value <code class="literal">IAAAAA</code> falls nearly at the end of the245   third histogram bucket.  Using some rather cheesy assumptions246   about the frequency of different characters, the planner arrives247   at the estimate 0.298387 for the portion of the histogram population248   that is less than <code class="literal">IAAAAA</code>.  We then combine the estimates249   for the MCV and non-MCV populations:250 251</p><pre class="programlisting">252selectivity = mcv_selectivity + histogram_selectivity * histogram_fraction253            = 0.01833333 + 0.298387 * 0.96966667254            = 0.307669255 256rows        = 10000 * 0.307669257            = 3077  (rounding off)258</pre><p>259 260   In this particular example, the correction from the MCV list is fairly261   small, because the column distribution is actually quite flat (the262   statistics showing these particular values as being more common than263   others are mostly due to sampling error).  In a more typical case where264   some values are significantly more common than others, this complicated265   process gives a useful improvement in accuracy because the selectivity266   for the most common values is found exactly.267  </p><p>268   Now let's consider a case with more than one269   condition in the <code class="literal">WHERE</code> clause:270 271</p><pre class="programlisting">272EXPLAIN SELECT * FROM tenk1 WHERE unique1 &lt; 1000 AND stringu1 = 'xxx';273 274                                   QUERY PLAN275-------------------------------------------------------------------​-------------276 Bitmap Heap Scan on tenk1  (cost=23.80..396.91 rows=1 width=244)277   Recheck Cond: (unique1 &lt; 1000)278   Filter: (stringu1 = 'xxx'::name)279   -&gt;  Bitmap Index Scan on tenk1_unique1  (cost=0.00..23.80 rows=1007 width=0)280         Index Cond: (unique1 &lt; 1000)281</pre><p>282 283   The planner assumes that the two conditions are independent, so that284   the individual selectivities of the clauses can be multiplied together:285 286</p><pre class="programlisting">287selectivity = selectivity(unique1 &lt; 1000) * selectivity(stringu1 = 'xxx')288            = 0.100697 * 0.0014559289            = 0.0001466290 291rows        = 10000 * 0.0001466292            = 1  (rounding off)293</pre><p>294 295   Notice that the number of rows estimated to be returned from the bitmap296   index scan reflects only the condition used with the index; this is297   important since it affects the cost estimate for the subsequent heap298   fetches.299  </p><p>300   Finally we will examine a query that involves a join:301 302</p><pre class="programlisting">303EXPLAIN SELECT * FROM tenk1 t1, tenk2 t2304WHERE t1.unique1 &lt; 50 AND t1.unique2 = t2.unique2;305 306                                      QUERY PLAN307-------------------------------------------------------------------​-------------------308 Nested Loop  (cost=4.64..456.23 rows=50 width=488)309   -&gt;  Bitmap Heap Scan on tenk1 t1  (cost=4.64..142.17 rows=50 width=244)310         Recheck Cond: (unique1 &lt; 50)311         -&gt;  Bitmap Index Scan on tenk1_unique1  (cost=0.00..4.63 rows=50 width=0)312               Index Cond: (unique1 &lt; 50)313   -&gt;  Index Scan using tenk2_unique2 on tenk2 t2  (cost=0.00..6.27 rows=1 width=244)314         Index Cond: (unique2 = t1.unique2)315</pre><p>316 317   The restriction on <code class="structname">tenk1</code>,318   <code class="literal">unique1 &lt; 50</code>,319   is evaluated before the nested-loop join.320   This is handled analogously to the previous range example.  This time the321   value 50 falls into the first bucket of the322   <code class="structfield">unique1</code> histogram:323 324</p><pre class="programlisting">325selectivity = (0 + (50 - bucket[1].min)/(bucket[1].max - bucket[1].min))/num_buckets326            = (0 + (50 - 0)/(993 - 0))/10327            = 0.005035328 329rows        = 10000 * 0.005035330            = 50  (rounding off)331</pre><p>332 333   The restriction for the join is <code class="literal">t2.unique2 = t1.unique2</code>.334   The operator is just335   our familiar <code class="literal">=</code>, however the selectivity function is336   obtained from the <code class="structfield">oprjoin</code> column of337   <code class="structname">pg_operator</code>, and is <code class="function">eqjoinsel</code>.338   <code class="function">eqjoinsel</code> looks up the statistical information for both339   <code class="structname">tenk2</code> and <code class="structname">tenk1</code>:340 341</p><pre class="programlisting">342SELECT tablename, null_frac,n_distinct, most_common_vals FROM pg_stats343WHERE tablename IN ('tenk1', 'tenk2') AND attname='unique2';344 345tablename  | null_frac | n_distinct | most_common_vals346-----------+-----------+------------+------------------347 tenk1     |         0 |         -1 |348 tenk2     |         0 |         -1 |349</pre><p>350 351   In this case there is no <acronym class="acronym">MCV</acronym> information for352   <code class="structfield">unique2</code> because all the values appear to be353   unique, so we use an algorithm that relies only on the number of354   distinct values for both relations together with their null fractions:355 356</p><pre class="programlisting">357selectivity = (1 - null_frac1) * (1 - null_frac2) * min(1/num_distinct1, 1/num_distinct2)358            = (1 - 0) * (1 - 0) / max(10000, 10000)359            = 0.0001360</pre><p>361 362   This is, subtract the null fraction from one for each of the relations,363   and divide by the maximum of the numbers of distinct values.364   The number of rows365   that the join is likely to emit is calculated as the cardinality of the366   Cartesian product of the two inputs, multiplied by the367   selectivity:368 369</p><pre class="programlisting">370rows = (outer_cardinality * inner_cardinality) * selectivity371     = (50 * 10000) * 0.0001372     = 50373</pre><p>374  </p><p>375   Had there been MCV lists for the two columns,376   <code class="function">eqjoinsel</code> would have used direct comparison of the MCV377   lists to determine the join selectivity within the part of the column378   populations represented by the MCVs.  The estimate for the remainder of the379   populations follows the same approach shown here.380  </p><p>381   Notice that we showed <code class="literal">inner_cardinality</code> as 10000, that is,382   the unmodified size of <code class="structname">tenk2</code>.  It might appear from383   inspection of the <code class="command">EXPLAIN</code> output that the estimate of384   join rows comes from 50 * 1, that is, the number of outer rows times385   the estimated number of rows obtained by each inner index scan on386   <code class="structname">tenk2</code>.  But this is not the case: the join relation size387   is estimated before any particular join plan has been considered.  If388   everything is working well then the two ways of estimating the join389   size will produce about the same answer, but due to round-off error and390   other factors they sometimes diverge significantly.391  </p><p>392   For those interested in further details, estimation of the size of393   a table (before any <code class="literal">WHERE</code> clauses) is done in394   <code class="filename">src/backend/optimizer/util/plancat.c</code>. The generic395   logic for clause selectivities is in396   <code class="filename">src/backend/optimizer/path/clausesel.c</code>.  The397   operator-specific selectivity functions are mostly found398   in <code class="filename">src/backend/utils/adt/selfuncs.c</code>.399  </p></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="planner-stats-details.html" title="Chapter 76. How the Planner Uses Statistics">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="planner-stats-details.html" title="Chapter 76. How the Planner Uses Statistics">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="multivariate-statistics-examples.html" title="76.2. Multivariate Statistics Examples">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Chapter 76. How the Planner Uses Statistics </td><td width="20%" align="center"><a accesskey="h" href="index.html" title="PostgreSQL 16.3 Documentation">Home</a></td><td width="40%" align="right" valign="top"> 76.2. Multivariate Statistics Examples</td></tr></table></div></body></html>
codekingpro/portable-devtools · Team Ai