| 1 |
<!-- doc/src/sgml/planstats.sgml --> |
| 2 |
|
| 3 |
<chapter id="planner-stats-details"> |
| 4 |
<title>How the Planner Uses Statistics</title> |
| 5 |
|
| 6 |
<para> |
| 7 |
This chapter builds on the material covered in <xref |
| 8 |
linkend="using-explain"/> and <xref linkend="planner-stats"/> to show some |
| 9 |
additional details about how the planner uses the |
| 10 |
system statistics to estimate the number of rows each part of a query might |
| 11 |
return. This is a significant part of the planning process, |
| 12 |
providing much of the raw material for cost calculation. |
| 13 |
</para> |
| 14 |
|
| 15 |
<para> |
| 16 |
The intent of this chapter is not to document the code in detail, |
| 17 |
but to present an overview of how it works. |
| 18 |
This will perhaps ease the learning curve for someone who subsequently |
| 19 |
wishes to read the code. |
| 20 |
</para> |
| 21 |
|
| 22 |
<sect1 id="row-estimation-examples"> |
| 23 |
<title>Row Estimation Examples</title> |
| 24 |
|
| 25 |
<indexterm zone="row-estimation-examples"> |
| 26 |
<primary>row estimation</primary> |
| 27 |
<secondary>planner</secondary> |
| 28 |
</indexterm> |
| 29 |
|
| 30 |
<para> |
| 31 |
The examples shown below use tables in the <productname>PostgreSQL</productname> |
| 32 |
regression test database. |
| 33 |
Note also that since <command>ANALYZE</command> uses random sampling |
| 34 |
while producing statistics, the results will change slightly after |
| 35 |
any new <command>ANALYZE</command>. |
| 36 |
</para> |
| 37 |
|
| 38 |
<para> |
| 39 |
Let's start with a very simple query: |
| 40 |
|
| 41 |
<programlisting> |
| 42 |
EXPLAIN SELECT * FROM tenk1; |
| 43 |
|
| 44 |
QUERY PLAN |
| 45 |
------------------------------------------------------------- |
| 46 |
Seq Scan on tenk1 (cost=0.00..458.00 rows=10000 width=244) |
| 47 |
</programlisting> |
| 48 |
|
| 49 |
How the planner determines the cardinality of <structname>tenk1</structname> |
| 50 |
is covered in <xref linkend="planner-stats"/>, but is repeated here for |
| 51 |
completeness. The number of pages and rows is looked up in |
| 52 |
<structname>pg_class</structname>: |
| 53 |
|
| 54 |
<programlisting> |
| 55 |
SELECT relpages, reltuples FROM pg_class WHERE relname = 'tenk1'; |
| 56 |
|
| 57 |
relpages | reltuples |
| 58 |
----------+----------- |
| 59 |
358 | 10000 |
| 60 |
</programlisting> |
| 61 |
|
| 62 |
These numbers are current as of the last <command>VACUUM</command> or |
| 63 |
<command>ANALYZE</command> on the table. The planner then fetches the |
| 64 |
actual current number of pages in the table (this is a cheap operation, |
| 65 |
not requiring a table scan). If that is different from |
| 66 |
<structfield>relpages</structfield> then |
| 67 |
<structfield>reltuples</structfield> is scaled accordingly to |
| 68 |
arrive at a current number-of-rows estimate. In the example above, the value of |
| 69 |
<structfield>relpages</structfield> is up-to-date so the rows estimate is |
| 70 |
the same as <structfield>reltuples</structfield>. |
| 71 |
</para> |
| 72 |
|
| 73 |
<para> |
| 74 |
Let's move on to an example with a range condition in its |
| 75 |
<literal>WHERE</literal> clause: |
| 76 |
|
| 77 |
<programlisting> |
| 78 |
EXPLAIN SELECT * FROM tenk1 WHERE unique1 < 1000; |
| 79 |
|
| 80 |
QUERY PLAN |
| 81 |
-------------------------------------------------------------------&zwsp;------------- |
| 82 |
Bitmap Heap Scan on tenk1 (cost=24.06..394.64 rows=1007 width=244) |
| 83 |
Recheck Cond: (unique1 < 1000) |
| 84 |
-> Bitmap Index Scan on tenk1_unique1 (cost=0.00..23.80 rows=1007 width=0) |
| 85 |
Index Cond: (unique1 < 1000) |
| 86 |
</programlisting> |
| 87 |
|
| 88 |
The planner examines the <literal>WHERE</literal> clause condition |
| 89 |
and looks up the selectivity function for the operator |
| 90 |
<literal><</literal> in <structname>pg_operator</structname>. |
| 91 |
This is held in the column <structfield>oprrest</structfield>, |
| 92 |
and the entry in this case is <function>scalarltsel</function>. |
| 93 |
The <function>scalarltsel</function> function retrieves the histogram for |
| 94 |
<structfield>unique1</structfield> from |
| 95 |
<structname>pg_statistic</structname>. For manual queries it is more |
| 96 |
convenient to look in the simpler <structname>pg_stats</structname> |
| 97 |
view: |
| 98 |
|
| 99 |
<programlisting> |
| 100 |
SELECT histogram_bounds FROM pg_stats |
| 101 |
WHERE tablename='tenk1' AND attname='unique1'; |
| 102 |
|
| 103 |
histogram_bounds |
| 104 |
------------------------------------------------------ |
| 105 |
{0,993,1997,3050,4040,5036,5957,7057,8029,9016,9995} |
| 106 |
</programlisting> |
| 107 |
|
| 108 |
Next the fraction of the histogram occupied by <quote>< 1000</quote> |
| 109 |
is worked out. This is the selectivity. The histogram divides the range |
| 110 |
into equal frequency buckets, so all we have to do is locate the bucket |
| 111 |
that our value is in and count <emphasis>part</emphasis> of it and |
| 112 |
<emphasis>all</emphasis> of the ones before. The value 1000 is clearly in |
| 113 |
the second bucket (993–1997). Assuming a linear distribution of |
| 114 |
values inside each bucket, we can calculate the selectivity as: |
| 115 |
|
| 116 |
<programlisting> |
| 117 |
selectivity = (1 + (1000 - bucket[2].min)/(bucket[2].max - bucket[2].min))/num_buckets |
| 118 |
= (1 + (1000 - 993)/(1997 - 993))/10 |
| 119 |
= 0.100697 |
| 120 |
</programlisting> |
| 121 |
|
| 122 |
that is, one whole bucket plus a linear fraction of the second, divided by |
| 123 |
the number of buckets. The estimated number of rows can now be calculated as |
| 124 |
the product of the selectivity and the cardinality of |
| 125 |
<structname>tenk1</structname>: |
| 126 |
|
| 127 |
<programlisting> |
| 128 |
rows = rel_cardinality * selectivity |
| 129 |
= 10000 * 0.100697 |
| 130 |
= 1007 (rounding off) |
| 131 |
</programlisting> |
| 132 |
</para> |
| 133 |
|
| 134 |
<para> |
| 135 |
Next let's consider an example with an equality condition in its |
| 136 |
<literal>WHERE</literal> clause: |
| 137 |
|
| 138 |
<programlisting> |
| 139 |
EXPLAIN SELECT * FROM tenk1 WHERE stringu1 = 'CRAAAA'; |
| 140 |
|
| 141 |
QUERY PLAN |
| 142 |
---------------------------------------------------------- |
| 143 |
Seq Scan on tenk1 (cost=0.00..483.00 rows=30 width=244) |
| 144 |
Filter: (stringu1 = 'CRAAAA'::name) |
| 145 |
</programlisting> |
| 146 |
|
| 147 |
Again the planner examines the <literal>WHERE</literal> clause condition |
| 148 |
and looks up the selectivity function for <literal>=</literal>, which is |
| 149 |
<function>eqsel</function>. For equality estimation the histogram is |
| 150 |
not useful; instead the list of <firstterm>most |
| 151 |
common values</firstterm> (<acronym>MCV</acronym>s) is used to determine the |
| 152 |
selectivity. Let's have a look at the MCVs, with some additional columns |
| 153 |
that will be useful later: |
| 154 |
|
| 155 |
<programlisting> |
| 156 |
SELECT null_frac, n_distinct, most_common_vals, most_common_freqs FROM pg_stats |
| 157 |
WHERE tablename='tenk1' AND attname='stringu1'; |
| 158 |
|
| 159 |
null_frac | 0 |
| 160 |
n_distinct | 676 |
| 161 |
most_common_vals | {EJAAAA,BBAAAA,CRAAAA,FCAAAA,FEAAAA,GSAAAA,&zwsp;JOAAAA,MCAAAA,NAAAAA,WGAAAA} |
| 162 |
most_common_freqs | {0.00333333,0.003,0.003,0.003,0.003,0.003,&zwsp;0.003,0.003,0.003,0.003} |
| 163 |
|
| 164 |
</programlisting> |
| 165 |
|
| 166 |
Since <literal>CRAAAA</literal> appears in the list of MCVs, the selectivity is |
| 167 |
merely the corresponding entry in the list of most common frequencies |
| 168 |
(<acronym>MCF</acronym>s): |
| 169 |
|
| 170 |
<programlisting> |
| 171 |
selectivity = mcf[3] |
| 172 |
= 0.003 |
| 173 |
</programlisting> |
| 174 |
|
| 175 |
As before, the estimated number of rows is just the product of this with the |
| 176 |
cardinality of <structname>tenk1</structname>: |
| 177 |
|
| 178 |
<programlisting> |
| 179 |
rows = 10000 * 0.003 |
| 180 |
= 30 |
| 181 |
</programlisting> |
| 182 |
</para> |
| 183 |
|
| 184 |
<para> |
| 185 |
Now consider the same query, but with a constant that is not in the |
| 186 |
<acronym>MCV</acronym> list: |
| 187 |
|
| 188 |
<programlisting> |
| 189 |
EXPLAIN SELECT * FROM tenk1 WHERE stringu1 = 'xxx'; |
| 190 |
|
| 191 |
QUERY PLAN |
| 192 |
---------------------------------------------------------- |
| 193 |
Seq Scan on tenk1 (cost=0.00..483.00 rows=15 width=244) |
| 194 |
Filter: (stringu1 = 'xxx'::name) |
| 195 |
</programlisting> |
| 196 |
|
| 197 |
This is quite a different problem: how to estimate the selectivity when the |
| 198 |
value is <emphasis>not</emphasis> in the <acronym>MCV</acronym> list. |
| 199 |
The approach is to use the fact that the value is not in the list, |
| 200 |
combined with the knowledge of the frequencies for all of the |
| 201 |
<acronym>MCV</acronym>s: |
| 202 |
|
| 203 |
<programlisting> |
| 204 |
selectivity = (1 - sum(mcv_freqs))/(num_distinct - num_mcv) |
| 205 |
= (1 - (0.00333333 + 0.003 + 0.003 + 0.003 + 0.003 + 0.003 + |
| 206 |
0.003 + 0.003 + 0.003 + 0.003))/(676 - 10) |
| 207 |
= 0.0014559 |
| 208 |
</programlisting> |
| 209 |
|
| 210 |
That is, add up all the frequencies for the <acronym>MCV</acronym>s and |
| 211 |
subtract them from one, then |
| 212 |
divide by the number of <emphasis>other</emphasis> distinct values. |
| 213 |
This amounts to assuming that the fraction of the column that is not any |
| 214 |
of the MCVs is evenly distributed among all the other distinct values. |
| 215 |
Notice that there are no null values so we don't have to worry about those |
| 216 |
(otherwise we'd subtract the null fraction from the numerator as well). |
| 217 |
The estimated number of rows is then calculated as usual: |
| 218 |
|
| 219 |
<programlisting> |
| 220 |
rows = 10000 * 0.0014559 |
| 221 |
= 15 (rounding off) |
| 222 |
</programlisting> |
| 223 |
</para> |
| 224 |
|
| 225 |
<para> |
| 226 |
The previous example with <literal>unique1 < 1000</literal> was an |
| 227 |
oversimplification of what <function>scalarltsel</function> really does; |
| 228 |
now that we have seen an example of the use of MCVs, we can fill in some |
| 229 |
more detail. The example was correct as far as it went, because since |
| 230 |
<structfield>unique1</structfield> is a unique column it has no MCVs (obviously, no |
| 231 |
value is any more common than any other value). For a non-unique |
| 232 |
column, there will normally be both a histogram and an MCV list, and |
| 233 |
<emphasis>the histogram does not include the portion of the column |
| 234 |
population represented by the MCVs</emphasis>. We do things this way because |
| 235 |
it allows more precise estimation. In this situation |
| 236 |
<function>scalarltsel</function> directly applies the condition (e.g., |
| 237 |
<quote>< 1000</quote>) to each value of the MCV list, and adds up the |
| 238 |
frequencies of the MCVs for which the condition is true. This gives |
| 239 |
an exact estimate of the selectivity within the portion of the table |
| 240 |
that is MCVs. The histogram is then used in the same way as above |
| 241 |
to estimate the selectivity in the portion of the table that is not |
| 242 |
MCVs, and then the two numbers are combined to estimate the overall |
| 243 |
selectivity. For example, consider |
| 244 |
|
| 245 |
<programlisting> |
| 246 |
EXPLAIN SELECT * FROM tenk1 WHERE stringu1 < 'IAAAAA'; |
| 247 |
|
| 248 |
QUERY PLAN |
| 249 |
------------------------------------------------------------ |
| 250 |
Seq Scan on tenk1 (cost=0.00..483.00 rows=3077 width=244) |
| 251 |
Filter: (stringu1 < 'IAAAAA'::name) |
| 252 |
</programlisting> |
| 253 |
|
| 254 |
We already saw the MCV information for <structfield>stringu1</structfield>, |
| 255 |
and here is its histogram: |
| 256 |
|
| 257 |
<programlisting> |
| 258 |
SELECT histogram_bounds FROM pg_stats |
| 259 |
WHERE tablename='tenk1' AND attname='stringu1'; |
| 260 |
|
| 261 |
histogram_bounds |
| 262 |
-------------------------------------------------------------------&zwsp;------------- |
| 263 |
{AAAAAA,CQAAAA,FRAAAA,IBAAAA,KRAAAA,NFAAAA,PSAAAA,SGAAAA,VAAAAA,&zwsp;XLAAAA,ZZAAAA} |
| 264 |
</programlisting> |
| 265 |
|
| 266 |
Checking the MCV list, we find that the condition <literal>stringu1 < |
| 267 |
'IAAAAA'</literal> is satisfied by the first six entries and not the last four, |
| 268 |
so the selectivity within the MCV part of the population is |
| 269 |
|
| 270 |
<programlisting> |
| 271 |
selectivity = sum(relevant mvfs) |
| 272 |
= 0.00333333 + 0.003 + 0.003 + 0.003 + 0.003 + 0.003 |
| 273 |
= 0.01833333 |
| 274 |
</programlisting> |
| 275 |
|
| 276 |
Summing all the MCFs also tells us that the total fraction of the |
| 277 |
population represented by MCVs is 0.03033333, and therefore the |
| 278 |
fraction represented by the histogram is 0.96966667 (again, there |
| 279 |
are no nulls, else we'd have to exclude them here). We can see |
| 280 |
that the value <literal>IAAAAA</literal> falls nearly at the end of the |
| 281 |
third histogram bucket. Using some rather cheesy assumptions |
| 282 |
about the frequency of different characters, the planner arrives |
| 283 |
at the estimate 0.298387 for the portion of the histogram population |
| 284 |
that is less than <literal>IAAAAA</literal>. We then combine the estimates |
| 285 |
for the MCV and non-MCV populations: |
| 286 |
|
| 287 |
<programlisting> |
| 288 |
selectivity = mcv_selectivity + histogram_selectivity * histogram_fraction |
| 289 |
= 0.01833333 + 0.298387 * 0.96966667 |
| 290 |
= 0.307669 |
| 291 |
|
| 292 |
rows = 10000 * 0.307669 |
| 293 |
= 3077 (rounding off) |
| 294 |
</programlisting> |
| 295 |
|
| 296 |
In this particular example, the correction from the MCV list is fairly |
| 297 |
small, because the column distribution is actually quite flat (the |
| 298 |
statistics showing these particular values as being more common than |
| 299 |
others are mostly due to sampling error). In a more typical case where |
| 300 |
some values are significantly more common than others, this complicated |
| 301 |
process gives a useful improvement in accuracy because the selectivity |
| 302 |
for the most common values is found exactly. |
| 303 |
</para> |
| 304 |
|
| 305 |
<para> |
| 306 |
Now let's consider a case with more than one |
| 307 |
condition in the <literal>WHERE</literal> clause: |
| 308 |
|
| 309 |
<programlisting> |
| 310 |
EXPLAIN SELECT * FROM tenk1 WHERE unique1 < 1000 AND stringu1 = 'xxx'; |
| 311 |
|
| 312 |
QUERY PLAN |
| 313 |
-------------------------------------------------------------------&zwsp;------------- |
| 314 |
Bitmap Heap Scan on tenk1 (cost=23.80..396.91 rows=1 width=244) |
| 315 |
Recheck Cond: (unique1 < 1000) |
| 316 |
Filter: (stringu1 = 'xxx'::name) |
| 317 |
-> Bitmap Index Scan on tenk1_unique1 (cost=0.00..23.80 rows=1007 width=0) |
| 318 |
Index Cond: (unique1 < 1000) |
| 319 |
</programlisting> |
| 320 |
|
| 321 |
The planner assumes that the two conditions are independent, so that |
| 322 |
the individual selectivities of the clauses can be multiplied together: |
| 323 |
|
| 324 |
<programlisting> |
| 325 |
selectivity = selectivity(unique1 < 1000) * selectivity(stringu1 = 'xxx') |
| 326 |
= 0.100697 * 0.0014559 |
| 327 |
= 0.0001466 |
| 328 |
|
| 329 |
rows = 10000 * 0.0001466 |
| 330 |
= 1 (rounding off) |
| 331 |
</programlisting> |
| 332 |
|
| 333 |
Notice that the number of rows estimated to be returned from the bitmap |
| 334 |
index scan reflects only the condition used with the index; this is |
| 335 |
important since it affects the cost estimate for the subsequent heap |
| 336 |
fetches. |
| 337 |
</para> |
| 338 |
|
| 339 |
<para> |
| 340 |
Finally we will examine a query that involves a join: |
| 341 |
|
| 342 |
<programlisting> |
| 343 |
EXPLAIN SELECT * FROM tenk1 t1, tenk2 t2 |
| 344 |
WHERE t1.unique1 < 50 AND t1.unique2 = t2.unique2; |
| 345 |
|
| 346 |
QUERY PLAN |
| 347 |
-------------------------------------------------------------------&zwsp;------------------- |
| 348 |
Nested Loop (cost=4.64..456.23 rows=50 width=488) |
| 349 |
-> Bitmap Heap Scan on tenk1 t1 (cost=4.64..142.17 rows=50 width=244) |
| 350 |
Recheck Cond: (unique1 < 50) |
| 351 |
-> Bitmap Index Scan on tenk1_unique1 (cost=0.00..4.63 rows=50 width=0) |
| 352 |
Index Cond: (unique1 < 50) |
| 353 |
-> Index Scan using tenk2_unique2 on tenk2 t2 (cost=0.00..6.27 rows=1 width=244) |
| 354 |
Index Cond: (unique2 = t1.unique2) |
| 355 |
</programlisting> |
| 356 |
|
| 357 |
The restriction on <structname>tenk1</structname>, |
| 358 |
<literal>unique1 < 50</literal>, |
| 359 |
is evaluated before the nested-loop join. |
| 360 |
This is handled analogously to the previous range example. This time the |
| 361 |
value 50 falls into the first bucket of the |
| 362 |
<structfield>unique1</structfield> histogram: |
| 363 |
|
| 364 |
<programlisting> |
| 365 |
selectivity = (0 + (50 - bucket[1].min)/(bucket[1].max - bucket[1].min))/num_buckets |
| 366 |
= (0 + (50 - 0)/(993 - 0))/10 |
| 367 |
= 0.005035 |
| 368 |
|
| 369 |
rows = 10000 * 0.005035 |
| 370 |
= 50 (rounding off) |
| 371 |
</programlisting> |
| 372 |
|
| 373 |
The restriction for the join is <literal>t2.unique2 = t1.unique2</literal>. |
| 374 |
The operator is just |
| 375 |
our familiar <literal>=</literal>, however the selectivity function is |
| 376 |
obtained from the <structfield>oprjoin</structfield> column of |
| 377 |
<structname>pg_operator</structname>, and is <function>eqjoinsel</function>. |
| 378 |
<function>eqjoinsel</function> looks up the statistical information for both |
| 379 |
<structname>tenk2</structname> and <structname>tenk1</structname>: |
| 380 |
|
| 381 |
<programlisting> |
| 382 |
SELECT tablename, null_frac,n_distinct, most_common_vals FROM pg_stats |
| 383 |
WHERE tablename IN ('tenk1', 'tenk2') AND attname='unique2'; |
| 384 |
|
| 385 |
tablename | null_frac | n_distinct | most_common_vals |
| 386 |
-----------+-----------+------------+------------------ |
| 387 |
tenk1 | 0 | -1 | |
| 388 |
tenk2 | 0 | -1 | |
| 389 |
</programlisting> |
| 390 |
|
| 391 |
In this case there is no <acronym>MCV</acronym> information for |
| 392 |
<structname>unique2</structname> and all the values appear to be |
| 393 |
unique (n_distinct = -1), so we use an algorithm that relies on the row |
| 394 |
count estimates for both relations (num_rows, not shown, but "tenk") |
| 395 |
together with the column null fractions (zero for both): |
| 396 |
|
| 397 |
<programlisting> |
| 398 |
selectivity = (1 - null_frac1) * (1 - null_frac2) / max(num_rows1, num_rows2) |
| 399 |
= (1 - 0) * (1 - 0) / max(10000, 10000) |
| 400 |
= 0.0001 |
| 401 |
</programlisting> |
| 402 |
|
| 403 |
This is, subtract the null fraction from one for each of the relations, |
| 404 |
and divide by the row count of the larger relation (this value does get |
| 405 |
scaled in the non-unique case). |
| 406 |
The number of rows |
| 407 |
that the join is likely to emit is calculated as the cardinality of the |
| 408 |
Cartesian product of the two inputs, multiplied by the |
| 409 |
selectivity: |
| 410 |
|
| 411 |
<programlisting> |
| 412 |
rows = (outer_cardinality * inner_cardinality) * selectivity |
| 413 |
= (50 * 10000) * 0.0001 |
| 414 |
= 50 |
| 415 |
</programlisting> |
| 416 |
</para> |
| 417 |
|
| 418 |
<para> |
| 419 |
Had there been MCV lists for the two columns, |
| 420 |
<function>eqjoinsel</function> would have used direct comparison of the MCV |
| 421 |
lists to determine the join selectivity within the part of the column |
| 422 |
populations represented by the MCVs. The estimate for the remainder of the |
| 423 |
populations follows the same approach shown here. |
| 424 |
</para> |
| 425 |
|
| 426 |
<para> |
| 427 |
Notice that we showed <literal>inner_cardinality</literal> as 10000, that is, |
| 428 |
the unmodified size of <structname>tenk2</structname>. It might appear from |
| 429 |
inspection of the <command>EXPLAIN</command> output that the estimate of |
| 430 |
join rows comes from 50 * 1, that is, the number of outer rows times |
| 431 |
the estimated number of rows obtained by each inner index scan on |
| 432 |
<structname>tenk2</structname>. But this is not the case: the join relation size |
| 433 |
is estimated before any particular join plan has been considered. If |
| 434 |
everything is working well then the two ways of estimating the join |
| 435 |
size will produce about the same answer, but due to round-off error and |
| 436 |
other factors they sometimes diverge significantly. |
| 437 |
</para> |
| 438 |
|
| 439 |
<para> |
| 440 |
For those interested in further details, estimation of the size of |
| 441 |
a table (before any <literal>WHERE</literal> clauses) is done in |
| 442 |
<filename>src/backend/optimizer/util/plancat.c</filename>. The generic |
| 443 |
logic for clause selectivities is in |
| 444 |
<filename>src/backend/optimizer/path/clausesel.c</filename>. The |
| 445 |
operator-specific selectivity functions are mostly found |
| 446 |
in <filename>src/backend/utils/adt/selfuncs.c</filename>. |
| 447 |
</para> |
| 448 |
</sect1> |
| 449 |
|
| 450 |
<sect1 id="multivariate-statistics-examples"> |
| 451 |
<title>Multivariate Statistics Examples</title> |
| 452 |
|
| 453 |
<indexterm> |
| 454 |
<primary>row estimation</primary> |
| 455 |
<secondary>multivariate</secondary> |
| 456 |
</indexterm> |
| 457 |
|
| 458 |
<sect2 id="functional-dependencies"> |
| 459 |
<title>Functional Dependencies</title> |
| 460 |
|
| 461 |
<para> |
| 462 |
Multivariate correlation can be demonstrated with a very simple data set |
| 463 |
— a table with two columns, both containing the same values: |
| 464 |
|
| 465 |
<programlisting> |
| 466 |
CREATE TABLE t (a INT, b INT); |
| 467 |
INSERT INTO t SELECT i % 100, i % 100 FROM generate_series(1, 10000) s(i); |
| 468 |
ANALYZE t; |
| 469 |
</programlisting> |
| 470 |
|
| 471 |
As explained in <xref linkend="planner-stats"/>, the planner can determine |
| 472 |
cardinality of <structname>t</structname> using the number of pages and |
| 473 |
rows obtained from <structname>pg_class</structname>: |
| 474 |
|
| 475 |
<programlisting> |
| 476 |
SELECT relpages, reltuples FROM pg_class WHERE relname = 't'; |
| 477 |
|
| 478 |
relpages | reltuples |
| 479 |
----------+----------- |
| 480 |
45 | 10000 |
| 481 |
</programlisting> |
| 482 |
|
| 483 |
The data distribution is very simple; there are only 100 distinct values |
| 484 |
in each column, uniformly distributed. |
| 485 |
</para> |
| 486 |
|
| 487 |
<para> |
| 488 |
The following example shows the result of estimating a <literal>WHERE</literal> |
| 489 |
condition on the <structfield>a</structfield> column: |
| 490 |
|
| 491 |
<programlisting> |
| 492 |
EXPLAIN (ANALYZE, TIMING OFF, BUFFERS OFF) SELECT * FROM t WHERE a = 1; |
| 493 |
QUERY PLAN |
| 494 |
-------------------------------------------------------------------&zwsp;------------ |
| 495 |
Seq Scan on t (cost=0.00..170.00 rows=100 width=8) (actual rows=100.00 loops=1) |
| 496 |
Filter: (a = 1) |
| 497 |
Rows Removed by Filter: 9900 |
| 498 |
</programlisting> |
| 499 |
|
| 500 |
The planner examines the condition and determines the selectivity |
| 501 |
of this clause to be 1%. By comparing this estimate and the actual |
| 502 |
number of rows, we see that the estimate is very accurate |
| 503 |
(in fact exact, as the table is very small). Changing the |
| 504 |
<literal>WHERE</literal> condition to use the <structfield>b</structfield> column, an |
| 505 |
identical plan is generated. But observe what happens if we apply the same |
| 506 |
condition on both columns, combining them with <literal>AND</literal>: |
| 507 |
|
| 508 |
<programlisting> |
| 509 |
EXPLAIN (ANALYZE, TIMING OFF, BUFFERS OFF) SELECT * FROM t WHERE a = 1 AND b = 1; |
| 510 |
QUERY PLAN |
| 511 |
-------------------------------------------------------------------&zwsp;---------- |
| 512 |
Seq Scan on t (cost=0.00..195.00 rows=1 width=8) (actual rows=100.00 loops=1) |
| 513 |
Filter: ((a = 1) AND (b = 1)) |
| 514 |
Rows Removed by Filter: 9900 |
| 515 |
</programlisting> |
| 516 |
|
| 517 |
The planner estimates the selectivity for each condition individually, |
| 518 |
arriving at the same 1% estimates as above. Then it assumes that the |
| 519 |
conditions are independent, and so it multiplies their selectivities, |
| 520 |
producing a final selectivity estimate of just 0.01%. |
| 521 |
This is a significant underestimate, as the actual number of rows |
| 522 |
matching the conditions (100) is two orders of magnitude higher. |
| 523 |
</para> |
| 524 |
|
| 525 |
<para> |
| 526 |
This problem can be fixed by creating a statistics object that |
| 527 |
directs <command>ANALYZE</command> to calculate functional-dependency |
| 528 |
multivariate statistics on the two columns: |
| 529 |
|
| 530 |
<programlisting> |
| 531 |
CREATE STATISTICS stts (dependencies) ON a, b FROM t; |
| 532 |
ANALYZE t; |
| 533 |
EXPLAIN (ANALYZE, TIMING OFF, BUFFERS OFF) SELECT * FROM t WHERE a = 1 AND b = 1; |
| 534 |
QUERY PLAN |
| 535 |
-------------------------------------------------------------------&zwsp;------------ |
| 536 |
Seq Scan on t (cost=0.00..195.00 rows=100 width=8) (actual rows=100.00 loops=1) |
| 537 |
Filter: ((a = 1) AND (b = 1)) |
| 538 |
Rows Removed by Filter: 9900 |
| 539 |
</programlisting> |
| 540 |
</para> |
| 541 |
</sect2> |
| 542 |
|
| 543 |
<sect2 id="multivariate-ndistinct-counts"> |
| 544 |
<title>Multivariate N-Distinct Counts</title> |
| 545 |
|
| 546 |
<para> |
| 547 |
A similar problem occurs with estimation of the cardinality of sets of |
| 548 |
multiple columns, such as the number of groups that would be generated by |
| 549 |
a <command>GROUP BY</command> clause. When <command>GROUP BY</command> |
| 550 |
lists a single column, the n-distinct estimate (which is visible as the |
| 551 |
estimated number of rows returned by the HashAggregate node) is very |
| 552 |
accurate: |
| 553 |
<programlisting> |
| 554 |
EXPLAIN (ANALYZE, TIMING OFF, BUFFERS OFF) SELECT COUNT(*) FROM t GROUP BY a; |
| 555 |
QUERY PLAN |
| 556 |
-------------------------------------------------------------------&zwsp;---------------------- |
| 557 |
HashAggregate (cost=195.00..196.00 rows=100 width=12) (actual rows=100.00 loops=1) |
| 558 |
Group Key: a |
| 559 |
-> Seq Scan on t (cost=0.00..145.00 rows=10000 width=4) (actual rows=10000.00 loops=1) |
| 560 |
</programlisting> |
| 561 |
But without multivariate statistics, the estimate for the number of |
| 562 |
groups in a query with two columns in <command>GROUP BY</command>, as |
| 563 |
in the following example, is off by an order of magnitude: |
| 564 |
<programlisting> |
| 565 |
EXPLAIN (ANALYZE, TIMING OFF, BUFFERS OFF) SELECT COUNT(*) FROM t GROUP BY a, b; |
| 566 |
QUERY PLAN |
| 567 |
-------------------------------------------------------------------&zwsp;------------------------- |
| 568 |
HashAggregate (cost=220.00..230.00 rows=1000 width=16) (actual rows=100.00 loops=1) |
| 569 |
Group Key: a, b |
| 570 |
-> Seq Scan on t (cost=0.00..145.00 rows=10000 width=8) (actual rows=10000.00 loops=1) |
| 571 |
</programlisting> |
| 572 |
By redefining the statistics object to include n-distinct counts for the |
| 573 |
two columns, the estimate is much improved: |
| 574 |
<programlisting> |
| 575 |
DROP STATISTICS stts; |
| 576 |
CREATE STATISTICS stts (dependencies, ndistinct) ON a, b FROM t; |
| 577 |
ANALYZE t; |
| 578 |
EXPLAIN (ANALYZE, TIMING OFF, BUFFERS OFF) SELECT COUNT(*) FROM t GROUP BY a, b; |
| 579 |
QUERY PLAN |
| 580 |
-------------------------------------------------------------------&zwsp;------------------------- |
| 581 |
HashAggregate (cost=220.00..221.00 rows=100 width=16) (actual rows=100.00 loops=1) |
| 582 |
Group Key: a, b |
| 583 |
-> Seq Scan on t (cost=0.00..145.00 rows=10000 width=8) (actual rows=10000.00 loops=1) |
| 584 |
</programlisting> |
| 585 |
</para> |
| 586 |
|
| 587 |
</sect2> |
| 588 |
|
| 589 |
<sect2 id="mcv-lists"> |
| 590 |
<title>MCV Lists</title> |
| 591 |
|
| 592 |
<para> |
| 593 |
As explained in <xref linkend="functional-dependencies"/>, functional |
| 594 |
dependencies are very cheap and efficient type of statistics, but their |
| 595 |
main limitation is their global nature (only tracking dependencies at |
| 596 |
the column level, not between individual column values). |
| 597 |
</para> |
| 598 |
|
| 599 |
<para> |
| 600 |
This section introduces multivariate variant of <acronym>MCV</acronym> |
| 601 |
(most-common values) lists, a straightforward extension of the per-column |
| 602 |
statistics described in <xref linkend="row-estimation-examples"/>. These |
| 603 |
statistics address the limitation by storing individual values, but it is |
| 604 |
naturally more expensive, both in terms of building the statistics in |
| 605 |
<command>ANALYZE</command>, storage and planning time. |
| 606 |
</para> |
| 607 |
|
| 608 |
<para> |
| 609 |
Let's look at the query from <xref linkend="functional-dependencies"/> |
| 610 |
again, but this time with a <acronym>MCV</acronym> list created on the |
| 611 |
same set of columns (be sure to drop the functional dependencies, to |
| 612 |
make sure the planner uses the newly created statistics). |
| 613 |
|
| 614 |
<programlisting> |
| 615 |
DROP STATISTICS stts; |
| 616 |
CREATE STATISTICS stts2 (mcv) ON a, b FROM t; |
| 617 |
ANALYZE t; |
| 618 |
EXPLAIN (ANALYZE, TIMING OFF, BUFFERS OFF) SELECT * FROM t WHERE a = 1 AND b = 1; |
| 619 |
QUERY PLAN |
| 620 |
-------------------------------------------------------------------&zwsp;------------ |
| 621 |
Seq Scan on t (cost=0.00..195.00 rows=100 width=8) (actual rows=100.00 loops=1) |
| 622 |
Filter: ((a = 1) AND (b = 1)) |
| 623 |
Rows Removed by Filter: 9900 |
| 624 |
</programlisting> |
| 625 |
|
| 626 |
The estimate is as accurate as with the functional dependencies, mostly |
| 627 |
thanks to the table being fairly small and having a simple distribution |
| 628 |
with a low number of distinct values. Before looking at the second query, |
| 629 |
which was not handled by functional dependencies particularly well, |
| 630 |
let's inspect the <acronym>MCV</acronym> list a bit. |
| 631 |
</para> |
| 632 |
|
| 633 |
<para> |
| 634 |
Inspecting the <acronym>MCV</acronym> list is possible using |
| 635 |
<function>pg_mcv_list_items</function> set-returning function. |
| 636 |
|
| 637 |
<programlisting> |
| 638 |
SELECT m.* FROM pg_statistic_ext join pg_statistic_ext_data on (oid = stxoid), |
| 639 |
pg_mcv_list_items(stxdmcv) m WHERE stxname = 'stts2'; |
| 640 |
index | values | nulls | frequency | base_frequency |
| 641 |
-------+----------+-------+-----------+---------------- |
| 642 |
0 | {0, 0} | {f,f} | 0.01 | 0.0001 |
| 643 |
1 | {1, 1} | {f,f} | 0.01 | 0.0001 |
| 644 |
... |
| 645 |
49 | {49, 49} | {f,f} | 0.01 | 0.0001 |
| 646 |
50 | {50, 50} | {f,f} | 0.01 | 0.0001 |
| 647 |
... |
| 648 |
97 | {97, 97} | {f,f} | 0.01 | 0.0001 |
| 649 |
98 | {98, 98} | {f,f} | 0.01 | 0.0001 |
| 650 |
99 | {99, 99} | {f,f} | 0.01 | 0.0001 |
| 651 |
(100 rows) |
| 652 |
</programlisting> |
| 653 |
|
| 654 |
This confirms there are 100 distinct combinations in the two columns, and |
| 655 |
all of them are about equally likely (1% frequency for each one). The |
| 656 |
base frequency is the frequency computed from per-column statistics, as if |
| 657 |
there were no multi-column statistics. Had there been any null values in |
| 658 |
either of the columns, this would be identified in the |
| 659 |
<structfield>nulls</structfield> column. |
| 660 |
</para> |
| 661 |
|
| 662 |
<para> |
| 663 |
When estimating the selectivity, the planner applies all the conditions |
| 664 |
on items in the <acronym>MCV</acronym> list, and then sums the frequencies |
| 665 |
of the matching ones. See <function>mcv_clauselist_selectivity</function> |
| 666 |
in <filename>src/backend/statistics/mcv.c</filename> for details. |
| 667 |
</para> |
| 668 |
|
| 669 |
<para> |
| 670 |
Compared to functional dependencies, <acronym>MCV</acronym> lists have two |
| 671 |
major advantages. Firstly, the list stores actual values, making it possible |
| 672 |
to decide which combinations are compatible. |
| 673 |
|
| 674 |
<programlisting> |
| 675 |
EXPLAIN (ANALYZE, TIMING OFF, BUFFERS OFF) SELECT * FROM t WHERE a = 1 AND b = 10; |
| 676 |
QUERY PLAN |
| 677 |
-------------------------------------------------------------------&zwsp;-------- |
| 678 |
Seq Scan on t (cost=0.00..195.00 rows=1 width=8) (actual rows=0.00 loops=1) |
| 679 |
Filter: ((a = 1) AND (b = 10)) |
| 680 |
Rows Removed by Filter: 10000 |
| 681 |
</programlisting> |
| 682 |
|
| 683 |
Secondly, <acronym>MCV</acronym> lists handle a wider range of clause types, |
| 684 |
not just equality clauses like functional dependencies. For example, |
| 685 |
consider the following range query for the same table: |
| 686 |
|
| 687 |
<programlisting> |
| 688 |
EXPLAIN (ANALYZE, TIMING OFF, BUFFERS OFF) SELECT * FROM t WHERE a <= 49 AND b > 49; |
| 689 |
QUERY PLAN |
| 690 |
-------------------------------------------------------------------&zwsp;-------- |
| 691 |
Seq Scan on t (cost=0.00..195.00 rows=1 width=8) (actual rows=0.00 loops=1) |
| 692 |
Filter: ((a <= 49) AND (b > 49)) |
| 693 |
Rows Removed by Filter: 10000 |
| 694 |
</programlisting> |
| 695 |
|
| 696 |
</para> |
| 697 |
|
| 698 |
</sect2> |
| 699 |
|
| 700 |
</sect1> |
| 701 |
|
| 702 |
<sect1 id="planner-stats-security"> |
| 703 |
<title>Planner Statistics and Security</title> |
| 704 |
|
| 705 |
<para> |
| 706 |
Access to the table <structname>pg_statistic</structname> is restricted to |
| 707 |
superusers, so that ordinary users cannot learn about the contents of the |
| 708 |
tables of other users from it. Some selectivity estimation functions will |
| 709 |
use a user-provided operator (either the operator appearing in the query or |
| 710 |
a related operator) to analyze the stored statistics. For example, in order |
| 711 |
to determine whether a stored most common value is applicable, the |
| 712 |
selectivity estimator will have to run the appropriate <literal>=</literal> |
| 713 |
operator to compare the constant in the query to the stored value. |
| 714 |
Thus the data in <structname>pg_statistic</structname> is potentially |
| 715 |
passed to user-defined operators. An appropriately crafted operator can |
| 716 |
intentionally leak the passed operands (for example, by logging them |
| 717 |
or writing them to a different table), or accidentally leak them by showing |
| 718 |
their values in error messages, in either case possibly exposing data from |
| 719 |
<structname>pg_statistic</structname> to a user who should not be able to |
| 720 |
see it. |
| 721 |
</para> |
| 722 |
|
| 723 |
<para> |
| 724 |
In order to prevent this, the following applies to all built-in selectivity |
| 725 |
estimation functions. When planning a query, in order to be able to use |
| 726 |
stored statistics, the current user must either |
| 727 |
have <literal>SELECT</literal> privilege on the table or the involved |
| 728 |
columns, or the operator used must be <literal>LEAKPROOF</literal> (more |
| 729 |
accurately, the function that the operator is based on). If not, then the |
| 730 |
selectivity estimator will behave as if no statistics are available, and |
| 731 |
the planner will proceed with default or fall-back assumptions. |
| 732 |
The <xref linkend="app-psql"/> program's |
| 733 |
<command><link linkend="app-psql-meta-command-do-lc">\do+</link></command> |
| 734 |
meta-command is useful to determine which operators are marked as leakproof. |
| 735 |
</para> |
| 736 |
|
| 737 |
<para> |
| 738 |
If a user does not have the required privilege on the table or columns, |
| 739 |
then in many cases the query will ultimately receive a permission-denied |
| 740 |
error, in which case this mechanism is invisible in practice. But if the |
| 741 |
user is reading from a security-barrier view, then the planner might wish |
| 742 |
to check the statistics of an underlying table that is otherwise |
| 743 |
inaccessible to the user. In that case, the operator should be leakproof |
| 744 |
or the statistics will not be used. There is no direct feedback about |
| 745 |
that, except that the plan might be suboptimal. If one suspects that this |
| 746 |
is the case, one could try running the query as a more privileged user, |
| 747 |
to see if a different plan results. |
| 748 |
</para> |
| 749 |
|
| 750 |
<para> |
| 751 |
This restriction applies only to cases where the planner would need to |
| 752 |
execute a user-defined operator on one or more values |
| 753 |
from <structname>pg_statistic</structname>. Thus the planner is permitted |
| 754 |
to use generic statistical information, such as the fraction of null values |
| 755 |
or the number of distinct values in a column, regardless of access |
| 756 |
privileges. |
| 757 |
</para> |
| 758 |
|
| 759 |
<para> |
| 760 |
Selectivity estimation functions contained in third-party extensions that |
| 761 |
potentially operate on statistics with user-defined operators should follow |
| 762 |
the same security rules. Consult the PostgreSQL source code for guidance. |
| 763 |
</para> |
| 764 |
</sect1> |
| 765 |
</chapter> |