← Back to branch summary

~ubuntu-branches/ubuntu/precise/postgresql-9.1/precise-security

« back to all changes in this revision

Viewing changes to doc/src/sgml/html/row-estimation-examples.html

  • Committer: Bazaar Package Importer
  • Author(s): Martin Pitt
  • Date: 2011-05-11 10:41:53 UTC
  • Revision ID: james.westby@ubuntu.com-20110511104153-psbh2o58553fv1m0
Tags: upstream-9.1~beta1
Import upstream version 9.1~beta1

Show diffs side-by-side

added added

removed removed

Lines of Context:
doc/src/sgml/html/row-estimation-examples.html
 
1
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
 
2
<HTML
 
3
><HEAD
 
4
><TITLE
 
5
>Row Estimation Examples</TITLE
 
6
><META
 
7
NAME="GENERATOR"
 
8
CONTENT="Modular DocBook HTML Stylesheet Version 1.79"><LINK
 
9
REV="MADE"
 
10
HREF="mailto:pgsql-docs@postgresql.org"><LINK
 
11
REL="HOME"
 
12
TITLE="PostgreSQL 9.1beta1 Documentation"
 
13
HREF="index.html"><LINK
 
14
REL="UP"
 
15
TITLE="How the Planner Uses Statistics"
 
16
HREF="planner-stats-details.html"><LINK
 
17
REL="PREVIOUS"
 
18
TITLE="How the Planner Uses Statistics"
 
19
HREF="planner-stats-details.html"><LINK
 
20
REL="NEXT"
 
21
TITLE="Appendixes"
 
22
HREF="appendixes.html"><LINK
 
23
REL="STYLESHEET"
 
24
TYPE="text/css"
 
25
HREF="stylesheet.css"><META
 
26
HTTP-EQUIV="Content-Type"
 
27
CONTENT="text/html; charset=ISO-8859-1"><META
 
28
NAME="creation"
 
29
CONTENT="2011-04-27T21:20:33"></HEAD
 
30
><BODY
 
31
CLASS="SECT1"
 
32
><DIV
 
33
CLASS="NAVHEADER"
 
34
><TABLE
 
35
SUMMARY="Header navigation table"
 
36
WIDTH="100%"
 
37
BORDER="0"
 
38
CELLPADDING="0"
 
39
CELLSPACING="0"
 
40
><TR
 
41
><TH
 
42
COLSPAN="5"
 
43
ALIGN="center"
 
44
VALIGN="bottom"
 
45
><A
 
46
HREF="index.html"
 
47
>PostgreSQL 9.1beta1 Documentation</A
 
48
></TH
 
49
></TR
 
50
><TR
 
51
><TD
 
52
WIDTH="10%"
 
53
ALIGN="left"
 
54
VALIGN="top"
 
55
><A
 
56
TITLE="How the Planner Uses Statistics"
 
57
HREF="planner-stats-details.html"
 
58
ACCESSKEY="P"
 
59
>Prev</A
 
60
></TD
 
61
><TD
 
62
WIDTH="10%"
 
63
ALIGN="left"
 
64
VALIGN="top"
 
65
><A
 
66
TITLE="How the Planner Uses Statistics"
 
67
HREF="planner-stats-details.html"
 
68
>Fast Backward</A
 
69
></TD
 
70
><TD
 
71
WIDTH="60%"
 
72
ALIGN="center"
 
73
VALIGN="bottom"
 
74
>Chapter 57. How the Planner Uses Statistics</TD
 
75
><TD
 
76
WIDTH="10%"
 
77
ALIGN="right"
 
78
VALIGN="top"
 
79
><A
 
80
TITLE="How the Planner Uses Statistics"
 
81
HREF="planner-stats-details.html"
 
82
>Fast Forward</A
 
83
></TD
 
84
><TD
 
85
WIDTH="10%"
 
86
ALIGN="right"
 
87
VALIGN="top"
 
88
><A
 
89
TITLE="Appendixes"
 
90
HREF="appendixes.html"
 
91
ACCESSKEY="N"
 
92
>Next</A
 
93
></TD
 
94
></TR
 
95
></TABLE
 
96
><HR
 
97
ALIGN="LEFT"
 
98
WIDTH="100%"></DIV
 
99
><DIV
 
100
CLASS="SECT1"
 
101
><H1
 
102
CLASS="SECT1"
 
103
><A
 
104
NAME="ROW-ESTIMATION-EXAMPLES"
 
105
>57.1. Row Estimation Examples</A
 
106
></H1
 
107
><P
 
108
>   The examples shown below use tables in the <SPAN
 
109
CLASS="PRODUCTNAME"
 
110
>PostgreSQL</SPAN
 
111
>
 
112
   regression test database.
 
113
   The outputs shown are taken from version 8.3.
 
114
   The behavior of earlier (or later) versions might vary.
 
115
   Note also that since <TT
 
116
CLASS="COMMAND"
 
117
>ANALYZE</TT
 
118
> uses random sampling
 
119
   while producing statistics, the results will change slightly after
 
120
   any new <TT
 
121
CLASS="COMMAND"
 
122
>ANALYZE</TT
 
123
>.
 
124
  </P
 
125
><P
 
126
>   Let's start with a very simple query:
 
127
 
 
128
</P><PRE
 
129
CLASS="PROGRAMLISTING"
 
130
>EXPLAIN SELECT * FROM tenk1;
 
131
 
 
132
                         QUERY PLAN
 
133
-------------------------------------------------------------
 
134
 Seq Scan on tenk1  (cost=0.00..458.00 rows=10000 width=244)</PRE
 
135
><P>
 
136
 
 
137
   How the planner determines the cardinality of <TT
 
138
CLASS="STRUCTNAME"
 
139
>tenk1</TT
 
140
>
 
141
   is covered in <A
 
142
HREF="planner-stats.html"
 
143
>Section 14.2</A
 
144
>, but is repeated here for
 
145
   completeness. The number of pages and rows is looked up in
 
146
   <TT
 
147
CLASS="STRUCTNAME"
 
148
>pg_class</TT
 
149
>:
 
150
 
 
151
</P><PRE
 
152
CLASS="PROGRAMLISTING"
 
153
>SELECT relpages, reltuples FROM pg_class WHERE relname = 'tenk1';
 
154
 
 
155
 relpages | reltuples
 
156
----------+-----------
 
157
      358 |     10000</PRE
 
158
><P>
 
159
 
 
160
    These numbers are current as of the last <TT
 
161
CLASS="COMMAND"
 
162
>VACUUM</TT
 
163
> or
 
164
    <TT
 
165
CLASS="COMMAND"
 
166
>ANALYZE</TT
 
167
> on the table.  The planner then fetches the
 
168
    actual current number of pages in the table (this is a cheap operation,
 
169
    not requiring a table scan).  If that is different from
 
170
    <TT
 
171
CLASS="STRUCTFIELD"
 
172
>relpages</TT
 
173
> then
 
174
    <TT
 
175
CLASS="STRUCTFIELD"
 
176
>reltuples</TT
 
177
> is scaled accordingly to
 
178
    arrive at a current number-of-rows estimate.  In this case the values
 
179
    are correct so the rows estimate is the same as
 
180
    <TT
 
181
CLASS="STRUCTFIELD"
 
182
>reltuples</TT
 
183
>.
 
184
  </P
 
185
><P
 
186
>   Let's move on to an example with a range condition in its
 
187
   <TT
 
188
CLASS="LITERAL"
 
189
>WHERE</TT
 
190
> clause:
 
191
 
 
192
</P><PRE
 
193
CLASS="PROGRAMLISTING"
 
194
>EXPLAIN SELECT * FROM tenk1 WHERE unique1 &lt; 1000;
 
195
 
 
196
                                   QUERY PLAN
 
197
--------------------------------------------------------------------------------
 
198
 Bitmap Heap Scan on tenk1  (cost=24.06..394.64 rows=1007 width=244)
 
199
   Recheck Cond: (unique1 &lt; 1000)
 
200
   -&gt;  Bitmap Index Scan on tenk1_unique1  (cost=0.00..23.80 rows=1007 width=0)
 
201
         Index Cond: (unique1 &lt; 1000)</PRE
 
202
><P>
 
203
 
 
204
   The planner examines the <TT
 
205
CLASS="LITERAL"
 
206
>WHERE</TT
 
207
> clause condition
 
208
   and looks up the selectivity function for the operator
 
209
   <TT
 
210
CLASS="LITERAL"
 
211
>&lt;</TT
 
212
> in <TT
 
213
CLASS="STRUCTNAME"
 
214
>pg_operator</TT
 
215
>.
 
216
   This is held in the column <TT
 
217
CLASS="STRUCTFIELD"
 
218
>oprrest</TT
 
219
>,
 
220
   and the entry in this case is <CODE
 
221
CLASS="FUNCTION"
 
222
>scalarltsel</CODE
 
223
>.
 
224
   The <CODE
 
225
CLASS="FUNCTION"
 
226
>scalarltsel</CODE
 
227
> function retrieves the histogram for
 
228
   <TT
 
229
CLASS="STRUCTFIELD"
 
230
>unique1</TT
 
231
> from
 
232
   <TT
 
233
CLASS="STRUCTNAME"
 
234
>pg_statistics</TT
 
235
>.  For manual queries it is more
 
236
   convenient to look in the simpler <TT
 
237
CLASS="STRUCTNAME"
 
238
>pg_stats</TT
 
239
>
 
240
   view:
 
241
 
 
242
</P><PRE
 
243
CLASS="PROGRAMLISTING"
 
244
>SELECT histogram_bounds FROM pg_stats
 
245
WHERE tablename='tenk1' AND attname='unique1';
 
246
 
 
247
                   histogram_bounds
 
248
------------------------------------------------------
 
249
 {0,993,1997,3050,4040,5036,5957,7057,8029,9016,9995}</PRE
 
250
><P>
 
251
 
 
252
   Next the fraction of the histogram occupied by <SPAN
 
253
CLASS="QUOTE"
 
254
>"&lt; 1000"</SPAN
 
255
>
 
256
   is worked out. This is the selectivity. The histogram divides the range
 
257
   into equal frequency buckets, so all we have to do is locate the bucket
 
258
   that our value is in and count <SPAN
 
259
CLASS="emphasis"
 
260
><I
 
261
CLASS="EMPHASIS"
 
262
>part</I
 
263
></SPAN
 
264
> of it and
 
265
   <SPAN
 
266
CLASS="emphasis"
 
267
><I
 
268
CLASS="EMPHASIS"
 
269
>all</I
 
270
></SPAN
 
271
> of the ones before. The value 1000 is clearly in
 
272
   the second bucket (993-1997).  Assuming a linear distribution of
 
273
   values inside each bucket, we can calculate the selectivity as:
 
274
 
 
275
</P><PRE
 
276
CLASS="PROGRAMLISTING"
 
277
>selectivity = (1 + (1000 - bucket[2].min)/(bucket[2].max - bucket[2].min))/num_buckets
 
278
            = (1 + (1000 - 993)/(1997 - 993))/10
 
279
            = 0.100697</PRE
 
280
><P>
 
281
 
 
282
   that is, one whole bucket plus a linear fraction of the second, divided by
 
283
   the number of buckets. The estimated number of rows can now be calculated as
 
284
   the product of the selectivity and the cardinality of
 
285
   <TT
 
286
CLASS="STRUCTNAME"
 
287
>tenk1</TT
 
288
>:
 
289
 
 
290
</P><PRE
 
291
CLASS="PROGRAMLISTING"
 
292
>rows = rel_cardinality * selectivity
 
293
     = 10000 * 0.100697
 
294
     = 1007  (rounding off)</PRE
 
295
><P>
 
296
  </P
 
297
><P
 
298
>   Next let's consider an example with an equality condition in its
 
299
   <TT
 
300
CLASS="LITERAL"
 
301
>WHERE</TT
 
302
> clause:
 
303
 
 
304
</P><PRE
 
305
CLASS="PROGRAMLISTING"
 
306
>EXPLAIN SELECT * FROM tenk1 WHERE stringu1 = 'CRAAAA';
 
307
 
 
308
                        QUERY PLAN
 
309
----------------------------------------------------------
 
310
 Seq Scan on tenk1  (cost=0.00..483.00 rows=30 width=244)
 
311
   Filter: (stringu1 = 'CRAAAA'::name)</PRE
 
312
><P>
 
313
 
 
314
   Again the planner examines the <TT
 
315
CLASS="LITERAL"
 
316
>WHERE</TT
 
317
> clause condition
 
318
   and looks up the selectivity function for <TT
 
319
CLASS="LITERAL"
 
320
>=</TT
 
321
>, which is
 
322
   <CODE
 
323
CLASS="FUNCTION"
 
324
>eqsel</CODE
 
325
>.  For equality estimation the histogram is
 
326
   not useful; instead the list of <I
 
327
CLASS="FIRSTTERM"
 
328
>most
 
329
   common values</I
 
330
> (<ACRONYM
 
331
CLASS="ACRONYM"
 
332
>MCV</ACRONYM
 
333
>s) is used to determine the
 
334
   selectivity. Let's have a look at the MCVs, with some additional columns
 
335
   that will be useful later:
 
336
 
 
337
</P><PRE
 
338
CLASS="PROGRAMLISTING"
 
339
>SELECT null_frac, n_distinct, most_common_vals, most_common_freqs FROM pg_stats
 
340
WHERE tablename='tenk1' AND attname='stringu1';
 
341
 
 
342
null_frac         | 0
 
343
n_distinct        | 676
 
344
most_common_vals  | {EJAAAA,BBAAAA,CRAAAA,FCAAAA,FEAAAA,GSAAAA,JOAAAA,MCAAAA,NAAAAA,WGAAAA}
 
345
most_common_freqs | {0.00333333,0.003,0.003,0.003,0.003,0.003,0.003,0.003,0.003,0.003}&#13;</PRE
 
346
><P>
 
347
 
 
348
   Since <TT
 
349
CLASS="LITERAL"
 
350
>CRAAAA</TT
 
351
> appears in the list of MCVs, the selectivity is
 
352
   merely the corresponding entry in the list of most common frequencies
 
353
   (<ACRONYM
 
354
CLASS="ACRONYM"
 
355
>MCF</ACRONYM
 
356
>s):
 
357
 
 
358
</P><PRE
 
359
CLASS="PROGRAMLISTING"
 
360
>selectivity = mcf[3]
 
361
            = 0.003</PRE
 
362
><P>
 
363
 
 
364
   As before, the estimated number of rows is just the product of this with the
 
365
   cardinality of <TT
 
366
CLASS="STRUCTNAME"
 
367
>tenk1</TT
 
368
>:
 
369
 
 
370
</P><PRE
 
371
CLASS="PROGRAMLISTING"
 
372
>rows = 10000 * 0.003
 
373
     = 30</PRE
 
374
><P>
 
375
  </P
 
376
><P
 
377
>   Now consider the same query, but with a constant that is not in the
 
378
   <ACRONYM
 
379
CLASS="ACRONYM"
 
380
>MCV</ACRONYM
 
381
> list:
 
382
 
 
383
</P><PRE
 
384
CLASS="PROGRAMLISTING"
 
385
>EXPLAIN SELECT * FROM tenk1 WHERE stringu1 = 'xxx';
 
386
 
 
387
                        QUERY PLAN
 
388
----------------------------------------------------------
 
389
 Seq Scan on tenk1  (cost=0.00..483.00 rows=15 width=244)
 
390
   Filter: (stringu1 = 'xxx'::name)</PRE
 
391
><P>
 
392
 
 
393
   This is quite a different problem: how to estimate the selectivity when the
 
394
   value is <SPAN
 
395
CLASS="emphasis"
 
396
><I
 
397
CLASS="EMPHASIS"
 
398
>not</I
 
399
></SPAN
 
400
> in the <ACRONYM
 
401
CLASS="ACRONYM"
 
402
>MCV</ACRONYM
 
403
> list.
 
404
   The approach is to use the fact that the value is not in the list,
 
405
   combined with the knowledge of the frequencies for all of the
 
406
   <ACRONYM
 
407
CLASS="ACRONYM"
 
408
>MCV</ACRONYM
 
409
>s:
 
410
 
 
411
</P><PRE
 
412
CLASS="PROGRAMLISTING"
 
413
>selectivity = (1 - sum(mvf))/(num_distinct - num_mcv)
 
414
            = (1 - (0.00333333 + 0.003 + 0.003 + 0.003 + 0.003 + 0.003 +
 
415
                    0.003 + 0.003 + 0.003 + 0.003))/(676 - 10)
 
416
            = 0.0014559</PRE
 
417
><P>
 
418
 
 
419
   That is, add up all the frequencies for the <ACRONYM
 
420
CLASS="ACRONYM"
 
421
>MCV</ACRONYM
 
422
>s and
 
423
   subtract them from one, then
 
424
   divide by the number of <SPAN
 
425
CLASS="emphasis"
 
426
><I
 
427
CLASS="EMPHASIS"
 
428
>other</I
 
429
></SPAN
 
430
> distinct values.
 
431
   This amounts to assuming that the fraction of the column that is not any
 
432
   of the MCVs is evenly distributed among all the other distinct values.
 
433
   Notice that there are no null values so we don't have to worry about those
 
434
   (otherwise we'd subtract the null fraction from the numerator as well).
 
435
   The estimated number of rows is then calculated as usual:
 
436
 
 
437
</P><PRE
 
438
CLASS="PROGRAMLISTING"
 
439
>rows = 10000 * 0.0014559
 
440
     = 15  (rounding off)</PRE
 
441
><P>
 
442
  </P
 
443
><P
 
444
>   The previous example with <TT
 
445
CLASS="LITERAL"
 
446
>unique1 &lt; 1000</TT
 
447
> was an
 
448
   oversimplification of what <CODE
 
449
CLASS="FUNCTION"
 
450
>scalarltsel</CODE
 
451
> really does;
 
452
   now that we have seen an example of the use of MCVs, we can fill in some
 
453
   more detail.  The example was correct as far as it went, because since
 
454
   <TT
 
455
CLASS="STRUCTFIELD"
 
456
>unique1</TT
 
457
> is a unique column it has no MCVs (obviously, no
 
458
   value is any more common than any other value).  For a non-unique
 
459
   column, there will normally be both a histogram and an MCV list, and
 
460
   <SPAN
 
461
CLASS="emphasis"
 
462
><I
 
463
CLASS="EMPHASIS"
 
464
>the histogram does not include the portion of the column
 
465
   population represented by the MCVs</I
 
466
></SPAN
 
467
>.  We do things this way because
 
468
   it allows more precise estimation.  In this situation
 
469
   <CODE
 
470
CLASS="FUNCTION"
 
471
>scalarltsel</CODE
 
472
> directly applies the condition (e.g.,
 
473
   <SPAN
 
474
CLASS="QUOTE"
 
475
>"&lt; 1000"</SPAN
 
476
>) to each value of the MCV list, and adds up the
 
477
   frequencies of the MCVs for which the condition is true.  This gives
 
478
   an exact estimate of the selectivity within the portion of the table
 
479
   that is MCVs.  The histogram is then used in the same way as above
 
480
   to estimate the selectivity in the portion of the table that is not
 
481
   MCVs, and then the two numbers are combined to estimate the overall
 
482
   selectivity.  For example, consider
 
483
 
 
484
</P><PRE
 
485
CLASS="PROGRAMLISTING"
 
486
>EXPLAIN SELECT * FROM tenk1 WHERE stringu1 &lt; 'IAAAAA';
 
487
 
 
488
                         QUERY PLAN
 
489
------------------------------------------------------------
 
490
 Seq Scan on tenk1  (cost=0.00..483.00 rows=3077 width=244)
 
491
   Filter: (stringu1 &lt; 'IAAAAA'::name)</PRE
 
492
><P>
 
493
 
 
494
   We already saw the MCV information for <TT
 
495
CLASS="STRUCTFIELD"
 
496
>stringu1</TT
 
497
>,
 
498
   and here is its histogram:
 
499
 
 
500
</P><PRE
 
501
CLASS="PROGRAMLISTING"
 
502
>SELECT histogram_bounds FROM pg_stats
 
503
WHERE tablename='tenk1' AND attname='stringu1';
 
504
 
 
505
                                histogram_bounds
 
506
--------------------------------------------------------------------------------
 
507
 {AAAAAA,CQAAAA,FRAAAA,IBAAAA,KRAAAA,NFAAAA,PSAAAA,SGAAAA,VAAAAA,XLAAAA,ZZAAAA}</PRE
 
508
><P>
 
509
 
 
510
   Checking the MCV list, we find that the condition <TT
 
511
CLASS="LITERAL"
 
512
>stringu1 &lt;
 
513
   'IAAAAA'</TT
 
514
> is satisfied by the first six entries and not the last four,
 
515
   so the selectivity within the MCV part of the population is
 
516
 
 
517
</P><PRE
 
518
CLASS="PROGRAMLISTING"
 
519
>selectivity = sum(relevant mvfs)
 
520
            = 0.00333333 + 0.003 + 0.003 + 0.003 + 0.003 + 0.003
 
521
            = 0.01833333</PRE
 
522
><P>
 
523
 
 
524
   Summing all the MCFs also tells us that the total fraction of the
 
525
   population represented by MCVs is 0.03033333, and therefore the
 
526
   fraction represented by the histogram is 0.96966667 (again, there
 
527
   are no nulls, else we'd have to exclude them here).  We can see
 
528
   that the value <TT
 
529
CLASS="LITERAL"
 
530
>IAAAAA</TT
 
531
> falls nearly at the end of the
 
532
   third histogram bucket.  Using some rather cheesy assumptions
 
533
   about the frequency of different characters, the planner arrives
 
534
   at the estimate 0.298387 for the portion of the histogram population
 
535
   that is less than <TT
 
536
CLASS="LITERAL"
 
537
>IAAAAA</TT
 
538
>.  We then combine the estimates
 
539
   for the MCV and non-MCV populations:
 
540
 
 
541
</P><PRE
 
542
CLASS="PROGRAMLISTING"
 
543
>selectivity = mcv_selectivity + histogram_selectivity * histogram_fraction
 
544
            = 0.01833333 + 0.298387 * 0.96966667
 
545
            = 0.307669
 
546
 
 
547
rows        = 10000 * 0.307669
 
548
            = 3077  (rounding off)</PRE
 
549
><P>
 
550
 
 
551
   In this particular example, the correction from the MCV list is fairly
 
552
   small, because the column distribution is actually quite flat (the
 
553
   statistics showing these particular values as being more common than
 
554
   others are mostly due to sampling error).  In a more typical case where
 
555
   some values are significantly more common than others, this complicated
 
556
   process gives a useful improvement in accuracy because the selectivity
 
557
   for the most common values is found exactly.
 
558
  </P
 
559
><P
 
560
>   Now let's consider a case with more than one
 
561
   condition in the <TT
 
562
CLASS="LITERAL"
 
563
>WHERE</TT
 
564
> clause:
 
565
 
 
566
</P><PRE
 
567
CLASS="PROGRAMLISTING"
 
568
>EXPLAIN SELECT * FROM tenk1 WHERE unique1 &lt; 1000 AND stringu1 = 'xxx';
 
569
 
 
570
                                   QUERY PLAN
 
571
--------------------------------------------------------------------------------
 
572
 Bitmap Heap Scan on tenk1  (cost=23.80..396.91 rows=1 width=244)
 
573
   Recheck Cond: (unique1 &lt; 1000)
 
574
   Filter: (stringu1 = 'xxx'::name)
 
575
   -&gt;  Bitmap Index Scan on tenk1_unique1  (cost=0.00..23.80 rows=1007 width=0)
 
576
         Index Cond: (unique1 &lt; 1000)</PRE
 
577
><P>
 
578
 
 
579
   The planner assumes that the two conditions are independent, so that
 
580
   the individual selectivities of the clauses can be multiplied together:
 
581
 
 
582
</P><PRE
 
583
CLASS="PROGRAMLISTING"
 
584
>selectivity = selectivity(unique1 &lt; 1000) * selectivity(stringu1 = 'xxx')
 
585
            = 0.100697 * 0.0014559
 
586
            = 0.0001466
 
587
 
 
588
rows        = 10000 * 0.0001466
 
589
            = 1  (rounding off)</PRE
 
590
><P>
 
591
 
 
592
   Notice that the number of rows estimated to be returned from the bitmap
 
593
   index scan reflects only the condition used with the index; this is
 
594
   important since it affects the cost estimate for the subsequent heap
 
595
   fetches.
 
596
  </P
 
597
><P
 
598
>   Finally we will examine a query that involves a join:
 
599
 
 
600
</P><PRE
 
601
CLASS="PROGRAMLISTING"
 
602
>EXPLAIN SELECT * FROM tenk1 t1, tenk2 t2
 
603
WHERE t1.unique1 &lt; 50 AND t1.unique2 = t2.unique2;
 
604
 
 
605
                                      QUERY PLAN
 
606
--------------------------------------------------------------------------------------
 
607
 Nested Loop  (cost=4.64..456.23 rows=50 width=488)
 
608
   -&gt;  Bitmap Heap Scan on tenk1 t1  (cost=4.64..142.17 rows=50 width=244)
 
609
         Recheck Cond: (unique1 &lt; 50)
 
610
         -&gt;  Bitmap Index Scan on tenk1_unique1  (cost=0.00..4.63 rows=50 width=0)
 
611
               Index Cond: (unique1 &lt; 50)
 
612
   -&gt;  Index Scan using tenk2_unique2 on tenk2 t2  (cost=0.00..6.27 rows=1 width=244)
 
613
         Index Cond: (unique2 = t1.unique2)</PRE
 
614
><P>
 
615
 
 
616
   The restriction on <TT
 
617
CLASS="STRUCTNAME"
 
618
>tenk1</TT
 
619
>,
 
620
   <TT
 
621
CLASS="LITERAL"
 
622
>unique1 &lt; 50</TT
 
623
>,
 
624
   is evaluated before the nested-loop join.
 
625
   This is handled analogously to the previous range example.  This time the
 
626
   value 50 falls into the first bucket of the
 
627
   <TT
 
628
CLASS="STRUCTFIELD"
 
629
>unique1</TT
 
630
> histogram:
 
631
 
 
632
</P><PRE
 
633
CLASS="PROGRAMLISTING"
 
634
>selectivity = (0 + (50 - bucket[1].min)/(bucket[1].max - bucket[1].min))/num_buckets
 
635
            = (0 + (50 - 0)/(993 - 0))/10
 
636
            = 0.005035
 
637
 
 
638
rows        = 10000 * 0.005035
 
639
            = 50  (rounding off)</PRE
 
640
><P>
 
641
 
 
642
   The restriction for the join is <TT
 
643
CLASS="LITERAL"
 
644
>t2.unique2 = t1.unique2</TT
 
645
>.
 
646
   The operator is just
 
647
   our familiar <TT
 
648
CLASS="LITERAL"
 
649
>=</TT
 
650
>, however the selectivity function is
 
651
   obtained from the <TT
 
652
CLASS="STRUCTFIELD"
 
653
>oprjoin</TT
 
654
> column of
 
655
   <TT
 
656
CLASS="STRUCTNAME"
 
657
>pg_operator</TT
 
658
>, and is <CODE
 
659
CLASS="FUNCTION"
 
660
>eqjoinsel</CODE
 
661
>.
 
662
   <CODE
 
663
CLASS="FUNCTION"
 
664
>eqjoinsel</CODE
 
665
> looks up the statistical information for both
 
666
   <TT
 
667
CLASS="STRUCTNAME"
 
668
>tenk2</TT
 
669
> and <TT
 
670
CLASS="STRUCTNAME"
 
671
>tenk1</TT
 
672
>:
 
673
 
 
674
</P><PRE
 
675
CLASS="PROGRAMLISTING"
 
676
>SELECT tablename, null_frac,n_distinct, most_common_vals FROM pg_stats
 
677
WHERE tablename IN ('tenk1', 'tenk2') AND attname='unique2';
 
678
 
 
679
tablename  | null_frac | n_distinct | most_common_vals
 
680
-----------+-----------+------------+------------------
 
681
 tenk1     |         0 |         -1 |
 
682
 tenk2     |         0 |         -1 |</PRE
 
683
><P>
 
684
 
 
685
   In this case there is no <ACRONYM
 
686
CLASS="ACRONYM"
 
687
>MCV</ACRONYM
 
688
> information for
 
689
   <TT
 
690
CLASS="STRUCTFIELD"
 
691
>unique2</TT
 
692
> because all the values appear to be
 
693
   unique, so we use an algorithm that relies only on the number of
 
694
   distinct values for both relations together with their null fractions:
 
695
 
 
696
</P><PRE
 
697
CLASS="PROGRAMLISTING"
 
698
>selectivity = (1 - null_frac1) * (1 - null_frac2) * min(1/num_distinct1, 1/num_distinct2)
 
699
            = (1 - 0) * (1 - 0) / max(10000, 10000)
 
700
            = 0.0001</PRE
 
701
><P>
 
702
 
 
703
   This is, subtract the null fraction from one for each of the relations,
 
704
   and divide by the maximum of the numbers of distinct values.
 
705
   The number of rows
 
706
   that the join is likely to emit is calculated as the cardinality of the
 
707
   Cartesian product of the two inputs, multiplied by the
 
708
   selectivity:
 
709
 
 
710
</P><PRE
 
711
CLASS="PROGRAMLISTING"
 
712
>rows = (outer_cardinality * inner_cardinality) * selectivity
 
713
     = (50 * 10000) * 0.0001
 
714
     = 50</PRE
 
715
><P>
 
716
  </P
 
717
><P
 
718
>   Had there been MCV lists for the two columns,
 
719
   <CODE
 
720
CLASS="FUNCTION"
 
721
>eqjoinsel</CODE
 
722
> would have used direct comparison of the MCV
 
723
   lists to determine the join selectivity within the part of the column
 
724
   populations represented by the MCVs.  The estimate for the remainder of the
 
725
   populations follows the same approach shown here.
 
726
  </P
 
727
><P
 
728
>   Notice that we showed <TT
 
729
CLASS="LITERAL"
 
730
>inner_cardinality</TT
 
731
> as 10000, that is,
 
732
   the unmodified size of <TT
 
733
CLASS="STRUCTNAME"
 
734
>tenk2</TT
 
735
>.  It might appear from
 
736
   inspection of the <TT
 
737
CLASS="COMMAND"
 
738
>EXPLAIN</TT
 
739
> output that the estimate of
 
740
   join rows comes from 50 * 1, that is, the number of outer rows times
 
741
   the estimated number of rows obtained by each inner index scan on
 
742
   <TT
 
743
CLASS="STRUCTNAME"
 
744
>tenk2</TT
 
745
>.  But this is not the case: the join relation size
 
746
   is estimated before any particular join plan has been considered.  If
 
747
   everything is working well then the two ways of estimating the join
 
748
   size will produce about the same answer, but due to roundoff error and
 
749
   other factors they sometimes diverge significantly.
 
750
  </P
 
751
><P
 
752
>   For those interested in further details, estimation of the size of
 
753
   a table (before any <TT
 
754
CLASS="LITERAL"
 
755
>WHERE</TT
 
756
> clauses) is done in
 
757
   <TT
 
758
CLASS="FILENAME"
 
759
>src/backend/optimizer/util/plancat.c</TT
 
760
>. The generic
 
761
   logic for clause selectivities is in
 
762
   <TT
 
763
CLASS="FILENAME"
 
764
>src/backend/optimizer/path/clausesel.c</TT
 
765
>.  The
 
766
   operator-specific selectivity functions are mostly found
 
767
   in <TT
 
768
CLASS="FILENAME"
 
769
>src/backend/utils/adt/selfuncs.c</TT
 
770
>.
 
771
  </P
 
772
></DIV
 
773
><DIV
 
774
CLASS="NAVFOOTER"
 
775
><HR
 
776
ALIGN="LEFT"
 
777
WIDTH="100%"><TABLE
 
778
SUMMARY="Footer navigation table"
 
779
WIDTH="100%"
 
780
BORDER="0"
 
781
CELLPADDING="0"
 
782
CELLSPACING="0"
 
783
><TR
 
784
><TD
 
785
WIDTH="33%"
 
786
ALIGN="left"
 
787
VALIGN="top"
 
788
><A
 
789
HREF="planner-stats-details.html"
 
790
ACCESSKEY="P"
 
791
>Prev</A
 
792
></TD
 
793
><TD
 
794
WIDTH="34%"
 
795
ALIGN="center"
 
796
VALIGN="top"
 
797
><A
 
798
HREF="index.html"
 
799
ACCESSKEY="H"
 
800
>Home</A
 
801
></TD
 
802
><TD
 
803
WIDTH="33%"
 
804
ALIGN="right"
 
805
VALIGN="top"
 
806
><A
 
807
HREF="appendixes.html"
 
808
ACCESSKEY="N"
 
809
>Next</A
 
810
></TD
 
811
></TR
 
812
><TR
 
813
><TD
 
814
WIDTH="33%"
 
815
ALIGN="left"
 
816
VALIGN="top"
 
817
>How the Planner Uses Statistics</TD
 
818
><TD
 
819
WIDTH="34%"
 
820
ALIGN="center"
 
821
VALIGN="top"
 
822
><A
 
823
HREF="planner-stats-details.html"
 
824
ACCESSKEY="U"
 
825
>Up</A
 
826
></TD
 
827
><TD
 
828
WIDTH="33%"
 
829
ALIGN="right"
 
830
VALIGN="top"
 
831
>Appendixes</TD
 
832
></TR
 
833
></TABLE
 
834
></DIV
 
835
></BODY
 
836
></HTML
 
837
>
 
 
b'\\ No newline at end of file'