codekingpro/portable-devtools
115k
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 < 1000;49 50 QUERY PLAN51--------------------------------------------------------------------------------52 Bitmap Heap Scan on tenk1 (cost=24.06..394.64 rows=1007 width=244)53 Recheck Cond: (unique1 < 1000)54 -> Bitmap Index Scan on tenk1_unique1 (cost=0.00..23.80 rows=1007 width=0)55 Index Cond: (unique1 < 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"><</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">< 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 < 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">< 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 < 'IAAAAA';211 212 QUERY PLAN213------------------------------------------------------------214 Seq Scan on tenk1 (cost=0.00..483.00 rows=3077 width=244)215 Filter: (stringu1 < '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 <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 < 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 < 1000)278 Filter: (stringu1 = 'xxx'::name)279 -> Bitmap Index Scan on tenk1_unique1 (cost=0.00..23.80 rows=1007 width=0)280 Index Cond: (unique1 < 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 < 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 < 50 AND t1.unique2 = t2.unique2;305 306 QUERY PLAN307--------------------------------------------------------------------------------------308 Nested Loop (cost=4.64..456.23 rows=50 width=488)309 -> Bitmap Heap Scan on tenk1 t1 (cost=4.64..142.17 rows=50 width=244)310 Recheck Cond: (unique1 < 50)311 -> Bitmap Index Scan on tenk1_unique1 (cost=0.00..4.63 rows=50 width=0)312 Index Cond: (unique1 < 50)313 -> 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 < 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>