{"id":390384,"date":"2024-06-29T09:12:58","date_gmt":"2024-06-29T09:12:58","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=390384"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=390384","title":{"rendered":"<span>Queries in PostgreSQL. Statistics<\/span>"},"content":{"rendered":"<div><!--[--><!--]--><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<h2><\/h2>\n<p>In the last article we reviewed the <a href=\"https:\/\/habr.com\/en\/company\/postgrespro\/blog\/649499\/\">stages of query execution<\/a>. Before we move on to plan node operations (data access and join methods), let&#8217;s discuss the bread and butter of the cost optimizer: statistics.<\/p>\n<p>As usual, I use the <a href=\"https:\/\/postgrespro.com\/education\/demodb\">demo database<\/a> for all my examples. You can download it and follow along.<\/p>\n<p>You will see a lot of execution plans here today. We will discuss how the plans work in more detail in later articles. For now just pay attention to the numbers that you see in the first line of each plan, next to the word <em>rows<\/em>. These are row number estimates, or <em>cardinality<\/em>.<\/p>\n<h2>Basic statistics<\/h2>\n<p>Basic relation-level statistics are stored in the table <code>pg_class<\/code> in the system catalog. The statistics include the following data:<\/p>\n<ul>\n<li>\n<p>Relation&#8217;s row count (<code>reltuples<\/code>).<\/p>\n<\/li>\n<li>\n<p>Relation&#8217;s size in pages (<code>relpages<\/code>).<\/p>\n<\/li>\n<li>\n<p>Number of pages marked in the relation&#8217;s visibility map (<code>relallvisible<\/code>).<\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"sql\">SELECT reltuples, relpages, relallvisible FROM pg_class WHERE relname = 'flights';  reltuples | relpages | relallvisible \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212+\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212+\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212     214867 |     2624 |         2624 (1 row)<\/code><\/pre>\n<p>For queries with no conditions (filters), the cardinality estimate will equal <code>reltuples<\/code>:<\/p>\n<pre><code class=\"sql\">EXPLAIN SELECT * FROM flights;                            QUERY PLAN \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212  Seq Scan on flights  (cost=0.00..4772.67 rows=214867 width=63) (1 row)<\/code><\/pre>\n<p>Statistics are collected during automatic or manual analysis. Basic statistics, being vital information, are also calculated when some operations are performed, such as <code>VACUUM FULL<\/code> and <code>CLUSTER<\/code> or <code>CREATE INDEX<\/code> and <code>REINDEX<\/code>. The system also updates statistics during vacuuming.<\/p>\n<p>To collect statistics, the analyzer randomly selects 300 \u00d7 <em>default_statistics_target<\/em> rows (the default value is 100, so 30,000 rows in total). Table sizes are not taken into account here because overall dataset size has little effect on what sample size would be considered sufficient for accurate statistics.<\/p>\n<p>Random rows are selected from 300 \u00d7 <em>default_statistics_target<\/em> random pages. If a table is smaller than the desired sample size, the analyzer just reads the whole table.<\/p>\n<p>In large tables, statistics will be imprecise because the analyzer does not scan every single row. Even if it did, the statistics would always be somewhat outdated, because table data keeps changing. We don&#8217;t need the statistics to be all that precise anyway: variations up to an order of magnitude are still accurate enough to produce an adequate plan.<\/p>\n<p>Let&#8217;s create a copy of the <code>flights<\/code> table with autovacuuming disabled, so we can control when analysis happens.<\/p>\n<pre><code class=\"sql\">CREATE TABLE flights_copy(LIKE flights) WITH (autovacuum_enabled = false);<\/code><\/pre>\n<p> There are no statistics for the new table yet:<\/p>\n<pre><code class=\"sql\">SELECT reltuples, relpages, relallvisible FROM pg_class WHERE relname = 'flights_copy';  reltuples | relpages | relallvisible \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212+\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212+\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212         \u22121 |        0 |             0 (1 row)<\/code><\/pre>\n<p>The value <code>reltuples<\/code> = \u22121 (in PostgreSQL 14 and higher) helps us distinguish between a table that has never had statistics collected for it and a table that just doesn&#8217;t have any rows.<\/p>\n<p>More often than not, a newly created table is populated right away. The planner does not know anything about the new table, so it assumes the table to be 10 pages long by default:<\/p>\n<pre><code class=\"sql\">EXPLAIN SELECT * FROM flights_copy;                            QUERY PLAN \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212  Seq Scan on flights_copy  (cost=0.00..14.10 rows=410 width=170) (1 row)<\/code><\/pre>\n<p>The planner calculates the row count based on the width of a single row. The width is usually an average value that&#8217;s calculated during analysis. This time, however, there is no analysis data, so the system approximates the width based on column data types.<\/p>\n<p>Let&#8217;s copy the data from <code>flights<\/code> into the new table and run the analyzer:<\/p>\n<pre><code class=\"sql\">INSERT INTO flights_copy SELECT * FROM flights; INSERT 0 214867 ANALYZE flights_copy;<\/code><\/pre>\n<p>Now the statistics match the actual row count. The table is compact enough for the analyzer to run through every row:<\/p>\n<pre><code class=\"sql\">SELECT reltuples, relpages, relallvisible FROM pg_class WHERE relname = 'flights_copy';  reltuples | relpages | relallvisible \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212+\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212+\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212     214867 |     2624 |             0 (1 row)<\/code><\/pre>\n<p>The <code>relallvisible<\/code> value updates after vacuuming:<\/p>\n<pre><code class=\"sql\">VACUUM flights_copy; SELECT relallvisible FROM pg_class WHERE relname = 'flights_copy';  relallvisible \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212           2624 (1 row) <\/code><\/pre>\n<p>This value is used when estimating index-only scan cost.<\/p>\n<p>Let&#8217;s double the number of rows while keeping the old statistics and see what cardinality the planner comes up with:<\/p>\n<pre><code class=\"sql\">INSERT INTO flights_copy SELECT * FROM flights; SELECT count(*) FROM flights_copy;  count \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212  429734 (1 row) EXPLAIN SELECT * FROM flights_copy;                              QUERY PLAN \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212  Seq Scan on flights_copy  (cost=0.00..9545.34 rows=429734 width=63) (1 row)<\/code><\/pre>\n<p>The estimate is accurate, despite the outdated <code>pg_class<\/code> data:<\/p>\n<pre><code class=\"sql\">SELECT reltuples, relpages FROM pg_class WHERE relname = 'flights_copy';  reltuples | relpages \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212+\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212     214867 |     2624 (1 row)<\/code><\/pre>\n<p>The planner notices that the size of the data file no longer matches the old <code>relpages<\/code> value, so it scales <code>reltuples<\/code> appropriately in an attempt to increase accuracy. The file size has doubled, so the number of rows is adjusted accordingly (data density is presumed constant):<\/p>\n<pre><code class=\"sql\">SELECT reltuples *   (pg_relation_size('flights_copy') \/ 8192) \/ relpages FROM pg_class WHERE relname = 'flights_copy';  ?column? \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212    429734 (1 row)<\/code><\/pre>\n<p>This adjustment doesn&#8217;t always work (for example, you can delete several rows, and the estimate will not change), but when big changes are made, this approach allows the statistics to hold on until the analyzer comes around.<\/p>\n<h2>NULL values<\/h2>\n<p>While looked down upon by purists, NULL values serve as a convenient representation of values that are unknown or nonexistent.<\/p>\n<p>But special values require special treatment. There are practical considerations to keep in mind when working with NULL values. Boolean logic turns into ternary, and the <code>NOT IN<\/code> construction starts behaving <em>weirdly<\/em>. It&#8217;s unclear whether NULL values are to be considered lower or higher than conventional values (special clauses <code>NULLS FIRST<\/code> and <code>NULLS LAST<\/code> help out with that). The use of NULL values in aggregate functions is sketchy, too. Because NULL values are, in fact, not values at all, the planner needs extra data to accommodate them.<\/p>\n<p>In addition to basic relation-level statistics, the analyzer also collects statistics for each column in a relation. This data is stored in the <code>pg_statistic<\/code> table in the system catalog and can be conveniently displayed using the <code>pg_stats<\/code> view.<\/p>\n<p><em>Fraction of null values<\/em> is column-level statistics. It&#8217;s designated as <code>null_frac<\/code> in <code>pg_stats<\/code>. In this example some planes haven&#8217;t departed yet, so their time of departure is undefined:<\/p>\n<pre><code class=\"sql\">EXPLAIN SELECT * FROM flights WHERE actual_departure IS NULL;                           QUERY PLAN \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212  Seq Scan on flights  (cost=0.00..4772.67 rows=16036 width=63)    Filter: (actual_departure IS NULL) (2 rows)<\/code><\/pre>\n<p>The optimizer multiplies the total row count by the NULL fraction:<\/p>\n<pre><code class=\"sql\">SELECT round(reltuples * s.null_frac) AS rows FROM pg_class   JOIN pg_stats s ON s.tablename = relname WHERE s.tablename = 'flights'   AND s.attname = 'actual_departure';  rows \u2212\u2212\u2212\u2212\u2212\u2212\u2212  16036 (1 row)<\/code><\/pre>\n<p>This is close enough to the true value of 16348.<\/p>\n<h2>Distinct values<\/h2>\n<p>The number of distinct values in a column is stored in the <code>n_distinct<\/code> field in <code>pg_stats<\/code>.<\/p>\n<p>If <code>n_distinct<\/code> is negative, its absolute value instead represents the fraction of values that are distinct. For example, the value of \u22121 means that every item in the column is unique. When the number of distinct values reaches 10% of the number of rows or more, the analyzer switches to the fraction mode. It is assumed at this point that the proportion will generally remain the same when the data is modified.<\/p>\n<p>If the number of distinct values is calculated incorrectly (because the sample happened to be unrepresentative), you can set this value manually:<\/p>\n<pre><code class=\"sql\">ALTER TABLE ... ALTER COLUMN ... SET (n_distinct = ...);<\/code><\/pre>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/bd6\/359\/79e\/bd635979e7d00525768de0086a069948.png\" width=\"1530\" height=\"804\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/bd6\/359\/79e\/bd635979e7d00525768de0086a069948.png\"\/><figcaption><\/figcaption><\/figure>\n<p>The number of distinct values is useful in cases where data is distributed uniformly. Consider this cardinality estimation of a &#171;<em>column<\/em> = <em>expression<\/em>&#187; clause. If the value of <em>expression<\/em> is unknown at the planning stage, the planner assumes that <em>expression<\/em> is equally likely to return any value from the column.<\/p>\n<pre><code class=\"sql\">EXPLAIN SELECT * FROM flights WHERE departure_airport = (   SELECT airport_code FROM airports WHERE city = 'Saint Petersburg' ); QUERY PLAN \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212  Seq Scan on flights  (cost=30.56..5340.40 rows=2066 width=63)    Filter: (departure_airport = $0)    InitPlan 1 (returns $0)      \u2212> Seq Scan on airports_data ml  (cost=0.00..30.56 rows=1 wi...          Filter: ((city \u2212>> lang()) = 'Saint Petersburg'::text) (5 rows) <\/code><\/pre>\n<p>The InitPlan node is executed only once, and the value is then used instead of $0 in the main plan.<\/p>\n<pre><code class=\"sql\">SELECT round(reltuples \/ s.n_distinct) AS rows FROM pg_class   JOIN pg_stats s ON s.tablename = relname WHERE s.tablename = 'flights'   AND s.attname = 'departure_airport';  rows \u2212\u2212\u2212\u2212\u2212\u2212  2066 (1 row)<\/code><\/pre>\n<p>If all data is distributed uniformly, these statistics (together with min and max values) would be sufficient for an accurate estimation. Unfortunately, this estimation does not work as well for nonuniform distributions, which are much more common:<\/p>\n<pre><code class=\"sql\">SELECT min(cnt), round(avg(cnt)) avg, max(cnt) FROM (   SELECT departure_airport, count(*) cnt   FROM flights GROUP BY departure_airport ) t;  min | avg  |  max \u2212\u2212\u2212\u2212\u2212+\u2212\u2212\u2212\u2212\u2212\u2212+\u2212\u2212\u2212\u2212\u2212\u2212\u2212  113 | 2066 | 20875 (1 row) <\/code><\/pre>\n<h2>Most common values<\/h2>\n<p>To improve estimation accuracy for non-uniform distributions, the analyzer collects statistics on most common values (MCVs) and their frequency. These values are stored in <code>pg_stats<\/code> as <code>most_common_vals<\/code> and <code>most_common_freqs<\/code>.<\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/c07\/ec2\/6c0\/c07ec26c002aca1b3ea7440d1b7b1432.png\" width=\"1530\" height=\"936\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c07\/ec2\/6c0\/c07ec26c002aca1b3ea7440d1b7b1432.png\"\/><figcaption><\/figcaption><\/figure>\n<p>Here&#8217;s an example of such statistics for the most common aircraft types:<\/p>\n<pre><code class=\"sql\">SELECT most_common_vals AS mcv,   left(most_common_freqs::text,60) || '...' AS mcf FROM pg_stats WHERE tablename = 'flights' AND attname = 'aircraft_code' \\ gx \u2212[ RECORD 1 ]\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212 mcv | {CN1,CR2,SU9,321,763,733,319,773} mcf | {0.2783,0.27473333,0.25816667,0.059233334,0.038533334,0.0370... <\/code><\/pre>\n<p>Estimating selectivity of &#171;<em>column <\/em>= <em>expression<\/em>&#187; is extremely straightforward: the planner just takes a value from the <code>most_common_vals<\/code> array and multiplies it by the frequency from the same position in the <code>most_common_freqs<\/code> array.<\/p>\n<pre><code class=\"sql\">EXPLAIN SELECT * FROM flights WHERE aircraft_code = '733';                           QUERY PLAN \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212  Seq Scan on flights  (cost=0.00..5309.84 rows=7957 width=63)    Filter: (aircraft_code = '733'::bpchar) (2 rows) SELECT round(reltuples * s.most_common_freqs[   array_position((s.most_common_vals::text::text[]),'733') ]) FROM pg_class   JOIN pg_stats s ON s.tablename = relname WHERE s.tablename = 'flights'   AND s.attname = 'aircraft_code';  round \u2212\u2212\u2212\u2212\u2212\u2212\u2212   7957 (1 row) <\/code><\/pre>\n<p>This estimate will be close to the true value of 8263.<\/p>\n<p>MCV lists are also used for selectivity estimations of inequalities: to find the selectivity of &#171;<em>column <\/em>&lt; <em>value<\/em>&#171;, the planner searches <code>most_common_vals<\/code> for all the values lower than the given value, and then adds together their frequencies from <code>most_common_freqs<\/code>.<\/p>\n<p>Common value statistics work best when the number of distinct values is low. The maximum size of the MCV arrays is defined by <em>default_statistics_target<\/em>, the same parameter that governs row sample size during analysis.<\/p>\n<p>In some cases increasing the value (and thus the array size) beyond the default value will provide more accurate estimations. You can set this value per column:<\/p>\n<pre><code class=\"sql\">ALTER TABLE ... ALTER COLUMN ... SET STATISTICS ...;<\/code><\/pre>\n<p>The row sample size will increase as well, but only for the table.<\/p>\n<p>The common values array stores the values themselves and, depending on the values, could take up a lot of space. This is why values over 1 kB in size are excluded from analysis and statistics. It keeps <code>pg_statistic<\/code> size under control and does not overload the planner. Values this large are usually distinct anyway and wouldn&#8217;t get included in <code>most_common_vals<\/code>.<\/p>\n<h2>Histogram<\/h2>\n<p>When the number of distinct values grows too large to store them all in an array, the system starts using the histogram representation. A histogram employs several <em>buckets<\/em> to store values in. The number of buckets is limited by the same <em>default_statistics_target<\/em> parameter.<\/p>\n<p>The width of each bucket is selected in such a way as to distribute the values evenly across them (as indicated by the rectangles on the image having approximately the same area). This representation enables the system to store only histogram bounds, not wasting space for storing the frequency of each bucket. Histograms do not include values from MCV lists.<\/p>\n<p>The bounds are stored in the <code>histogram_bounds<\/code> field in <code>pg_stats<\/code>. The summary frequency of values in any bucket equals 1 \/ <em>number of buckets<\/em>.<\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/e8e\/a86\/d89\/e8ea86d89136b0c42f8a1e19f2ede191.png\" width=\"1530\" height=\"972\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e8e\/a86\/d89\/e8ea86d89136b0c42f8a1e19f2ede191.png\"\/><figcaption><\/figcaption><\/figure>\n<p>A histogram is stored as an array of bucket bounds:<\/p>\n<pre><code class=\"sql\">SELECT left(histogram_bounds::text,60) || '...' AS histogram_bounds FROM pg_stats s WHERE s.tablename = 'boarding_passes' AND s.attname = 'seat_no';                         histogram_bounds \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212  {10B,10D,10D,10F,11B,11C,11H,12H,13B,14B,14H,15H,16D,16D,16H... (1 row)<\/code><\/pre>\n<p>Among other things, histograms are used to estimate selectivity of &#171;greater than&#187; and &#171;less than&#187; operations together with MCV lists.<\/p>\n<p>Example: calculating the number of boarding passes issued for seats in the back.<\/p>\n<pre><code class=\"sql\">EXPLAIN SELECT * FROM boarding_passes WHERE seat_no > '30C';                              QUERY PLAN \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212  Seq Scan on boarding_passes  (cost=0.00..157353.30 rows=2943394 ...    Filter: ((seat_no)::text > '30C'::text) (2 rows)<\/code><\/pre>\n<p>The cutoff seat number is selected specifically to be on the edge between two buckets.<\/p>\n<p>The selectivity of this condition is <em>N \/ number of buckets<\/em>, where <em>N<\/em> is the number of buckets with matching values (to the right of the cutoff point). Remember that histograms don&#8217;t take into account most common values and undefined values.<\/p>\n<p>Let&#8217;s look at the fraction of matching most common values first:<\/p>\n<pre><code class=\"sql\">SELECT sum(s.most_common_freqs[   array_position((s.most_common_vals::text::text[]),v) ]) FROM pg_stats s, unnest(s.most_common_vals::text::text[]) v WHERE s.tablename = 'boarding_passes' AND s.attname = 'seat_no' AND v > '30C';   sum \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212  0.2127 (1 row)<\/code><\/pre>\n<p>Now let&#8217;s look at the fraction of most common values (excluded from the histogram):<\/p>\n<pre><code class=\"sql\">SELECT sum(s.most_common_freqs[   array_position((s.most_common_vals::text::text[]),v) ]) FROM pg_stats s, unnest(s.most_common_vals::text::text[]) v WHERE s.tablename = 'boarding_passes' AND s.attname = 'seat_no';   sum \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212  0.6762 (1 row)<\/code><\/pre>\n<p>There are no NULL values in the <code>seat_no<\/code> column:<\/p>\n<pre><code class=\"sql\">SELECT s.null_frac FROM pg_stats s WHERE s.tablename = 'boarding_passes' AND s.attname = 'seat_no';  null_frac \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212          0 (1 row)<\/code><\/pre>\n<p>The interval covers exactly 49 buckets (out of 100 total). The resulting estimate:<\/p>\n<pre><code class=\"sql\">SELECT round( reltuples * (    0.2127 -- from most common values  + (1 - 0.6762 - 0) * (49 \/ 100.0) -- from histogram )) FROM pg_class WHERE relname = 'boarding_passes';   round \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212  2943394 (1 row)<\/code><\/pre>\n<p>The true value is 2986429.<\/p>\n<p>When the cutoff value isn&#8217;t at the edge of a bucket, the matching fraction of that bucket is calculated using linear interpolation.<\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/61f\/118\/443\/61f1184435d77bf72b67c6e86dfee634.png\" width=\"1530\" height=\"930\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/61f\/118\/443\/61f1184435d77bf72b67c6e86dfee634.png\"\/><figcaption><\/figcaption><\/figure>\n<p>Higher <em>default_statistics_target<\/em> value may improve estimate accuracy, but the histogram together with the MCV list already produce a good result, even with a high number of distinct values:<\/p>\n<pre><code class=\"sql\">SELECT n_distinct FROM pg_stats WHERE tablename = 'boarding_passes' AND attname = 'seat_no';  n_distinct \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212         461 (1 row)<\/code><\/pre>\n<p>Higher estimate accuracy is beneficial only as long as it improves planning quality. Increasing <em>default_statistics_target<\/em> without a valid reason may slow analysis and planning while having no effect on optimization.<\/p>\n<p>On the other hand, lowering the parameter (all the way down to zero) may increase analysis and planning speed, but may also result in low-quality plans, so this &#171;time save&#187; is rarely justified.<\/p>\n<h2>Statistics for nonscalar data types<\/h2>\n<p>Statistics for nonscalar data types may include distribution data not only for the nonscalar values themselves, but for their comprising elements as well. This allows for more accurate planning when columns in forms other than the first normal form are queried.<\/p>\n<ul>\n<li>\n<p>The arrays <code>most_common_elems<\/code> and <code>most_common_elem_freqs<\/code> contain <em>most common elements<\/em> and their frequencies, respectively. <\/p>\n<p>These statistics are collected and used to estimate selectivity of arrays and <code>tsvector<\/code> data.<\/p>\n<\/li>\n<li>\n<p><code>elem_count_histogram<\/code> array is a histogram of <em>the number of distinct elements<\/em> in a value.<\/p>\n<p>These statistics are collected and used to estimate selectivity of arrays only.<\/p>\n<\/li>\n<li>\n<p>For range data types, histograms are used to represent the distribution of range length and distributions of its lower and upper bounds. These histograms then help estimate selectivity for various operations with these data types. They are not shown in <code>pg_stats<\/code>.<\/p>\n<p>These statistics are also used for multirange data types introduced in PostgreSQL 14.<\/p>\n<\/li>\n<\/ul>\n<h2>Average field width<\/h2>\n<p>The <code>avg_width<\/code> field in <code>pg_stats<\/code> represents the average filed width in a column. Field width for data types such as <code>integer<\/code> or <code>char(3)<\/code> is obviously fixed, but when it comes to data types with no set width, such as text, the value may differ significantly column to column:<\/p>\n<pre><code class=\"sql\">SELECT attname, avg_width FROM pg_stats WHERE (tablename, attname) IN ( VALUES   ('tickets', 'passenger_name'), ('ticket_flights','fare_conditions') );      attname     | avg_width \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212+\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212  fare_conditions |         8  passenger_name  |        16 (2 rows)<\/code><\/pre>\n<p>These statistics help estimate memory usage for operations like sorting or hashing.<\/p>\n<h2>Correlation<\/h2>\n<p>The field <code>correlation<\/code> in <code>pg_stats<\/code> represents correlation between physical row ordering on disk and logical ordering (&#171;greater than&#187; or &#171;less than&#187;) of the column values, ranging from -1 to +1. If the values are stored in order, correlation will be close to +1. If they are stored in reverse order, then correlation will be closer to -1. The more chaotically the data is distributed on the disk, the closer the value will be to zero.<\/p>\n<pre><code class=\"sql\">SELECT attname, correlation FROM pg_stats WHERE tablename = 'airports_data' ORDER BY abs(correlation) DESC; attname    | correlation \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212+\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212 coordinates  | airport_code | \u22120.21120238 city         |  \u22120.1970127 airport_name | \u22120.18223621 timezone     |  0.17961165 (5 rows)<\/code><\/pre>\n<p>The statistics for the <code>coordinates<\/code> column can&#8217;t be collected, because comparison operations (&#171;less than&#187; and &#171;greater than&#187;) are not defined for the point data type.<\/p>\n<p>Correlation is used for index scan cost estimation.<\/p>\n<h2>Expression statistics <\/h2>\n<p>Generally speaking, column statistics are only used when an operation calls for the column itself, not for an expression with the column as a parameter. The planner doesn&#8217;t know how a function will affect column statistics, so conditions like &#171;<em>function-call<\/em> = <em>constant<\/em>&#187; are always estimated at 0.5%:<\/p>\n<pre><code class=\"sql\">EXPLAIN SELECT * FROM flights WHERE extract(   month FROM scheduled_departure AT TIME ZONE 'Europe\/Moscow' ) = 1;                              QUERY PLAN \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212  Seq Scan on flights  (cost=0.00..6384.17 rows=1074 width=63)    Filter: (EXTRACT(month FROM (scheduled_departure AT TIME ZONE ... (2 rows) SELECT round(reltuples * 0.005) FROM pg_class WHERE relname = 'flights';  round \u2212\u2212\u2212\u2212\u2212\u2212\u2212   1074 (1 row)  <\/code><\/pre>\n<p>The planner can&#8217;t process even standard functions, while to us it&#8217;s obvious that the fraction of flights in January will be around 1\/12 of total flights:<\/p>\n<pre><code class=\"sql\">SELECT count(*) AS total,   count(*) FILTER (WHERE extract(     month FROM scheduled_departure AT TIME ZONE 'Europe\/Moscow'   ) = 1) AS january FROM flights;  total  | january \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212+\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212  214867 |   16831 (1 row)<\/code><\/pre>\n<p>This is where expression statistics come in.<\/p>\n<h2>Extended expression statistics<\/h2>\n<p>PostgreSQL 14 introduced a feature known as <em>extended expression statistics<\/em>. Extended expression statistics aren&#8217;t collected automatically. To collect them manually, use the <code>CREATE STATISTICS<\/code> command to create an extended statistics database object.<\/p>\n<pre><code class=\"sql\">CREATE STATISTICS flights_expr ON (extract(   month FROM scheduled_departure AT TIME ZONE 'Europe\/Moscow' )) FROM flights;<\/code><\/pre>\n<p>The new statistics will improve the estimate:<\/p>\n<pre><code class=\"sql\">ANALYZE flights; EXPLAIN SELECT * FROM flights WHERE extract(   month FROM scheduled_departure AT TIME ZONE 'Europe\/Moscow' ) = 1;                              QUERY PLAN \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212  Seq Scan on flights  (cost=0.00..6384.17 rows=16222 width=63)    Filter: (EXTRACT(month FROM (scheduled_departure AT TIME ZONE ... (2 rows)<\/code><\/pre>\n<p>For the statistics to work, the expression in the statistics generation command must be identical to the one in the original query.<\/p>\n<p>Extended statistics metadata is stored in the <code>pg_statistic_ext<\/code> table in the system catalog, while the statistics data itself is stored in a separate table <code>pg_statistic_ext_data<\/code> (in PostgreSQL 12 and higher). It is stored separately from the metadata to restrict user access to sensitive information, if necessary.<\/p>\n<p>There are views that display collected statistics in a user-friendly form. Extended expression statistics can be displayed with the following command:<\/p>\n<pre><code class=\"sql\">SELECT left(expr,50) || '...' AS expr,   null_frac, avg_width, n_distinct,   most_common_vals AS mcv,   left(most_common_freqs::text,50) || '...' AS mcf,   correlation FROM pg_stats_ext_exprs WHERE statistics_name = 'flights_expr' \\gx -[ RECORD 1 ]\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212 expr        | EXTRACT(month FROM (scheduled_departure AT TIME ZO... null_frac   | 0 avg_width   | 8 n_distinct  | 12 mcv         | {8,9,3,5,12,4,10,7,11,1,6,2} mcf         | {0.12526667,0.11016667,0.07903333,0.07903333,0.078.. correlation | 0.095407926<\/code><\/pre>\n<p>The amount of collected statistics data can be altered with the <code>ALTER STATISTICS<\/code> command:<\/p>\n<pre><code class=\"sql\">ALTER STATISTICS flights_expr SET STATISTICS 42;<\/code><\/pre>\n<h2>Expression index statistics<\/h2>\n<p>When an expression index is built, the system collects its statistics, just like with a regular table. The planner can use these statistics too. It&#8217;s convenient, but only if we actually care about the index.<\/p>\n<pre><code class=\"sql\">DROP STATISTICS flights_expr; CREATE INDEX ON flights(extract(   month FROM scheduled_departure AT TIME ZONE 'Europe\/Moscow' )); => ANALYZE flights; EXPLAIN SELECT * FROM flights WHERE extract(   month FROM scheduled_departure AT TIME ZONE 'Europe\/Moscow' ) = 1;                              QUERY PLAN \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212  Bitmap Heap Scan on flights  (cost=318.42..3235.96 rows=16774 wi...    Recheck Cond: (EXTRACT(month FROM (scheduled_departure AT TIME...    \u2212> Bitmap Index Scan on flights_extract_idx  (cost=0.00..314.2...        Index Cond: (EXTRACT(month FROM (scheduled_departure AT TI... (4 rows)<\/code><\/pre>\n<p>Expression index statistics are stored in the same way table statistics are. For example, this is the number of distinct values:<\/p>\n<pre><code class=\"sql\">SELECT n_distinct FROM pg_stats WHERE tablename = 'flights_extract_idx';  n_distinct \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212          12 (1 row)<\/code><\/pre>\n<p>In PostgreSQL 11 and higher, the accuracy of index statistics can be changed with the <code>ALTER INDEX<\/code> command. You might need the name of the column that references the expression. Example:<\/p>\n<pre><code class=\"sql\">SELECT attname FROM pg_attribute WHERE attrelid = 'flights_extract_idx'::regclass;  attname \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212  extract (1 row) ALTER INDEX flights_extract_idx   ALTER COLUMN extract SET STATISTICS 42;<\/code><\/pre>\n<h2>Multivariate statistics<\/h2>\n<p>PostgreSQL 10 introduced the ability to collect statistics from several columns simultaneously, also known as <em>multivariate statistics<\/em>. This requires generating the necessary extended statistics manually.<\/p>\n<p>There are three types of multivariate statistics.<\/p>\n<p><strong>Functional dependencies between columns<\/strong><\/p>\n<p>When values in one column are determined (fully or partially) by values in another column, and there are conditions referencing both columns in a query, the resulting cardinality will be underestimated.<\/p>\n<p>Here&#8217;s an example with two conditions:<\/p>\n<pre><code class=\"sql\">SELECT count(*) FROM flights WHERE flight_no = 'PG0007' AND departure_airport = 'VKO';  count \u2212\u2212\u2212\u2212\u2212\u2212\u2212    396 (1 row)<\/code><\/pre>\n<p>The estimate is significantly lower than it should be, at just 26 rows:<\/p>\n<pre><code class=\"sql\">EXPLAIN SELECT * FROM flights WHERE flight_no = 'PG0007' AND departure_airport = 'VKO';                              QUERY PLAN \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212  Bitmap Heap Scan on flights  (cost=12.03..1238.70 rows=26 width=63)    Recheck Cond: (flight_no = 'PG0007'::bpchar)    Filter: (departure_airport = 'VKO'::bpchar)    \u2212> Bitmap Index Scan on flights_flight_no_scheduled_departure_key        (cost=0.00..12.02 rows=480 width=0)        Index Cond: (flight_no = 'PG0007'::bpchar) (6 rows)<\/code><\/pre>\n<p>This is the infamous <em>correlated predicates problem<\/em>. The planner expects the predicates to be independent and calculates the resulting selectivity as the product of selectivities of the conditions, combined with <code>AND<\/code>. The Bitmap Index Scan estimate, calculated for the <em>flight_no<\/em> condition, drops significantly after the <em>departure_airport<\/em> condition in Bitmap Heap Scan is applied.<\/p>\n<p>Naturally, a flight number already unambiguously defines the departure airport, so the second condition is actually redundant. This is where extended functional dependencies statistics can help improve the estimate.<\/p>\n<p>Let&#8217;s create extended functional dependencies statistics for the two columns:<\/p>\n<pre><code class=\"sql\">CREATE STATISTICS flights_dep(dependencies) ON flight_no, departure_airport FROM flights;<\/code><\/pre>\n<p>Analyze again, now with the new statistics, and the estimate improves:<\/p>\n<pre><code class=\"sql\">ANALYZE flights; EXPLAIN SELECT * FROM flights WHERE flight_no = 'PG0007' AND departure_airport = 'VKO';                              QUERY PLAN \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212  Bitmap Heap Scan on flights  (cost=10.56..816.91 rows=276 width=63)    Recheck Cond: (flight_no = 'PG0007'::bpchar)    Filter: (departure_airport = 'VKO'::bpchar)    \u2212> Bitmap Index Scan on flights_flight_no_scheduled_departure_key        (cost=0.00..10.49 rows=276 width=0)        Index Cond: (flight_no = 'PG0007'::bpchar) (6 rows)<\/code><\/pre>\n<p>The statistics are stored in the system catalog and can be displayed with this command:<\/p>\n<pre><code class=\"sql\">SELECT dependencies FROM pg_stats_ext WHERE statistics_name = 'flights_dep';                dependencies \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212  {\"2 => 5\": 1.000000, \"5 => 2\": 0.010567} (1 row)<\/code><\/pre>\n<p>The numbers 2 and 5 are the table column numbers from <code>pg_attribute<\/code>. The values next to them represent the degree of functional dependency, from 0 (independent) to 1 (values in the second column are entirely defined by values in the first one).<\/p>\n<p><strong>Multivariate number of distinct values<\/strong><\/p>\n<p>Statistics on the number of distinct combinations of values from several columns will significantly improve the cardinality of a <code>GROUP BY<\/code> operation over multiple columns.<\/p>\n<p>In this example, the planner estimates the number of possible pairs of departure and arrival airports as the total number of airports squared. The true number of pairs is significantly lower, however, because not every two airports are connected by direct flights:<\/p>\n<pre><code class=\"sql\">SELECT count(*) FROM (   SELECT DISTINCT departure_airport, arrival_airport FROM flights ) t;  count \u2212\u2212\u2212\u2212\u2212\u2212\u2212    618 (1 row) EXPLAIN SELECT DISTINCT departure_airport, arrival_airport FROM flights;                              QUERY PLAN \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212  HashAggregate  (cost=5847.01..5955.16 rows=10816 width=8)    Group Key: departure_airport, arrival_airport    \u2212> Seq Scan on flights  (cost=0.00..4772.67 rows=214867 width=8) (3 rows)<\/code><\/pre>\n<p>Let&#8217;s create an extended statistics for the number of distinct values:<\/p>\n<pre><code class=\"sql\">CREATE STATISTICS flights_nd(ndistinct) ON departure_airport, arrival_airport FROM flights; ANALYZE flights; EXPLAIN SELECT DISTINCT departure_airport, arrival_airport FROM flights;                              QUERY PLAN \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212  HashAggregate (cost=5847.01..5853.19 rows=618 width=8)    Group Key: departure_airport, arrival_airport    \u2212> Seq Scan on flights  (cost=0.00..4772.67 rows=214867 width=8) (3 rows)<\/code><\/pre>\n<p>The statistics are stored in the system catalog:<\/p>\n<pre><code class=\"sql\">SELECT n_distinct FROM pg_stats_ext WHERE statistics_name = 'flights_nd';   n_distinct \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212  {\"5, 6\": 618} (1 row)<\/code><\/pre>\n<p><strong>Multivariate most common values lists<\/strong><\/p>\n<p>When values are distributed non-uniformly, functional dependency data alone may not suffice, as the estimate will vary significantly depending on specific pairs of values. Consider this example, where the planner inaccurately estimates the number of flights from Sheremetyevo airport made by Boeing 737:<\/p>\n<pre><code class=\"sql\">SELECT count(*) FROM flights WHERE departure_airport = 'SVO' AND aircraft_code = '733'  count \u2212\u2212\u2212\u2212\u2212\u2212\u2212   2037 (1 row) EXPLAIN SELECT * FROM flights WHERE departure_airport = 'SVO' AND aircraft_code = '733';                              QUERY PLAN \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212  Seq Scan on flights  (cost=0.00..5847.00 rows=733 width=63)    Filter: ((departure_airport = 'SVO'::bpchar) AND (aircraft_cod... (2 rows)<\/code><\/pre>\n<p>We can improve the estimate with multivariate MCV list statistics:<\/p>\n<pre><code class=\"sql\">CREATE STATISTICS flights_mcv(mcv) ON departure_airport, aircraft_code FROM flights; ANALYZE flights; EXPLAIN SELECT * FROM flights WHERE departure_airport = 'SVO' AND aircraft_code = '733';                              QUERY PLAN \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212  Seq Scan on flights  (cost=0.00..5847.00 rows=2077 width=63)    Filter: ((departure_airport = 'SVO'::bpchar) AND (aircraft_cod... (2 rows)<\/code><\/pre>\n<p>Now there is frequency data in the system catalog for the planner to use:<\/p>\n<pre><code class=\"sql\">SELECT values, frequency FROM pg_statistic_ext stx   JOIN pg_statistic_ext_data stxd ON stx.oid = stxd.stxoid,   pg_mcv_list_items(stxdmcv) m WHERE stxname = 'flights_mcv' AND values = '{SVO,773}';   values   |      frequency \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212+\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212  {SVO,773} | 0.005733333333333333 (1 row)<\/code><\/pre>\n<p>A multivariate most common values list stores <em>default_statistics_target<\/em> values, just like a regular MCV list. If the parameter is defined at the column level, the highest value is used.<\/p>\n<p>As with extended expression statistics, you can change the list size (in PostgreSQL 13 and higher):<\/p>\n<pre><code class=\"sql\">ALTER STATISTICS ... SET STATISTICS ...;<\/code><\/pre>\n<p>In these examples, multivariate statistics are collected for only two columns, but you can collect them for as many columns as you want.<\/p>\n<p>You can also collect different types of statistics into a single extended statistics object. To do this, just list required statistics types separated by commas when creating an object. If no specific statistics types are defined, the system will collect all available statistics at once.<\/p>\n<p>PostgreSQL 14 also allows you to use not just column names, but arbitrary expressions when making multivariate and expression statistics.<\/p>\n<p>To be continued.<\/p>\n<\/div>\n<\/div>\n<\/div>\n<p><!----><!----><\/div>\n<p><!----><!----><br \/> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/articles\/652971\/\"> https:\/\/habr.com\/ru\/articles\/652971\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<div><!--[--><!--]--><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<h2><\/h2>\n<p>In the last article we reviewed the <a href=\"https:\/\/habr.com\/en\/company\/postgrespro\/blog\/649499\/\">stages of query execution<\/a>. Before we move on to plan node operations (data access and join methods), let&#8217;s discuss the bread and butter of the cost optimizer: statistics.<\/p>\n<p>As usual, I use the <a href=\"https:\/\/postgrespro.com\/education\/demodb\">demo database<\/a> for all my examples. You can download it and follow along.<\/p>\n<p>You will see a lot of execution plans here today. We will discuss how the plans work in more detail in later articles. For now just pay attention to the numbers that you see in the first line of each plan, next to the word <em>rows<\/em>. These are row number estimates, or <em>cardinality<\/em>.<\/p>\n<h2>Basic statistics<\/h2>\n<p>Basic relation-level statistics are stored in the table <code>pg_class<\/code> in the system catalog. The statistics include the following data:<\/p>\n<ul>\n<li>\n<p>Relation&#8217;s row count (<code>reltuples<\/code>).<\/p>\n<\/li>\n<li>\n<p>Relation&#8217;s size in pages (<code>relpages<\/code>).<\/p>\n<\/li>\n<li>\n<p>Number of pages marked in the relation&#8217;s visibility map (<code>relallvisible<\/code>).<\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"sql\">SELECT reltuples, relpages, relallvisible FROM pg_class WHERE relname = 'flights';  reltuples | relpages | relallvisible \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212+\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212+\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212     214867 |     2624 |         2624 (1 row)<\/code><\/pre>\n<p>For queries with no conditions (filters), the cardinality estimate will equal <code>reltuples<\/code>:<\/p>\n<pre><code class=\"sql\">EXPLAIN SELECT * FROM flights;                            QUERY PLAN \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212  Seq Scan on flights  (cost=0.00..4772.67 rows=214867 width=63) (1 row)<\/code><\/pre>\n<p>Statistics are collected during automatic or manual analysis. Basic statistics, being vital information, are also calculated when some operations are performed, such as <code>VACUUM FULL<\/code> and <code>CLUSTER<\/code> or <code>CREATE INDEX<\/code> and <code>REINDEX<\/code>. The system also updates statistics during vacuuming.<\/p>\n<p>To collect statistics, the analyzer randomly selects 300 \u00d7 <em>default_statistics_target<\/em> rows (the default value is 100, so 30,000 rows in total). Table sizes are not taken into account here because overall dataset size has little effect on what sample size would be considered sufficient for accurate statistics.<\/p>\n<p>Random rows are selected from 300 \u00d7 <em>default_statistics_target<\/em> random pages. If a table is smaller than the desired sample size, the analyzer just reads the whole table.<\/p>\n<p>In large tables, statistics will be imprecise because the analyzer does not scan every single row. Even if it did, the statistics would always be somewhat outdated, because table data keeps changing. We don&#8217;t need the statistics to be all that precise anyway: variations up to an order of magnitude are still accurate enough to produce an adequate plan.<\/p>\n<p>Let&#8217;s create a copy of the <code>flights<\/code> table with autovacuuming disabled, so we can control when analysis happens.<\/p>\n<pre><code class=\"sql\">CREATE TABLE flights_copy(LIKE flights) WITH (autovacuum_enabled = false);<\/code><\/pre>\n<p> There are no statistics for the new table yet:<\/p>\n<pre><code class=\"sql\">SELECT reltuples, relpages, relallvisible FROM pg_class WHERE relname = 'flights_copy';  reltuples | relpages | relallvisible \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212+\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212+\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212         \u22121 |        0 |             0 (1 row)<\/code><\/pre>\n<p>The value <code>reltuples<\/code> = \u22121 (in PostgreSQL 14 and higher) helps us distinguish between a table that has never had statistics collected for it and a table that just doesn&#8217;t have any rows.<\/p>\n<p>More often than not, a newly created table is populated right away. The planner does not know anything about the new table, so it assumes the table to be 10 pages long by default:<\/p>\n<pre><code class=\"sql\">EXPLAIN SELECT * FROM flights_copy;                            QUERY PLAN \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212  Seq Scan on flights_copy  (cost=0.00..14.10 rows=410 width=170) (1 row)<\/code><\/pre>\n<p>The planner calculates the row count based on the width of a single row. The width is usually an average value that&#8217;s calculated during analysis. This time, however, there is no analysis data, so the system approximates the width based on column data types.<\/p>\n<p>Let&#8217;s copy the data from <code>flights<\/code> into the new table and run the analyzer:<\/p>\n<pre><code class=\"sql\">INSERT INTO flights_copy SELECT * FROM flights; INSERT 0 214867 ANALYZE flights_copy;<\/code><\/pre>\n<p>Now the statistics match the actual row count. The table is compact enough for the analyzer to run through every row:<\/p>\n<pre><code class=\"sql\">SELECT reltuples, relpages, relallvisible FROM pg_class WHERE relname = 'flights_copy';  reltuples | relpages | relallvisible \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212+\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212+\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212     214867 |     2624 |             0 (1 row)<\/code><\/pre>\n<p>The <code>relallvisible<\/code> value updates after vacuuming:<\/p>\n<pre><code class=\"sql\">VACUUM flights_copy; SELECT relallvisible FROM pg_class WHERE relname = 'flights_copy';  relallvisible \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212           2624 (1 row) <\/code><\/pre>\n<p>This value is used when estimating index-only scan cost.<\/p>\n<p>Let&#8217;s double the number of rows while keeping the old statistics and see what cardinality the planner comes up with:<\/p>\n<pre><code class=\"sql\">INSERT INTO flights_copy SELECT * FROM flights; SELECT count(*) FROM flights_copy;  count \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212  429734 (1 row) EXPLAIN SELECT * FROM flights_copy;                              QUERY PLAN \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212  Seq Scan on flights_copy  (cost=0.00..9545.34 rows=429734 width=63) (1 row)<\/code><\/pre>\n<p>The estimate is accurate, despite the outdated <code>pg_class<\/code> data:<\/p>\n<pre><code class=\"sql\">SELECT reltuples, relpages FROM pg_class WHERE relname = 'flights_copy';  reltuples | relpages \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212+\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212     214867 |     2624 (1 row)<\/code><\/pre>\n<p>The planner notices that the size of the data file no longer matches the old <code>relpages<\/code> value, so it scales <code>reltuples<\/code> appropriately in an attempt to increase accuracy. The file size has doubled, so the number of rows is adjusted accordingly (data density is presumed constant):<\/p>\n<pre><code class=\"sql\">SELECT reltuples *   (pg_relation_size('flights_copy') \/ 8192) \/ relpages FROM pg_class WHERE relname = 'flights_copy';  ?column? \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212    429734 (1 row)<\/code><\/pre>\n<p>This adjustment doesn&#8217;t always work (for example, you can delete several rows, and the estimate will not change), but when big changes are made, this approach allows the statistics to hold on until the analyzer comes around.<\/p>\n<h2>NULL values<\/h2>\n<p>While looked down upon by purists, NULL values serve as a convenient representation of values that are unknown or nonexistent.<\/p>\n<p>But special values require special treatment. There are practical considerations to keep in mind when working with NULL values. Boolean logic turns into ternary, and the <code>NOT IN<\/code> construction starts behaving <em>weirdly<\/em>. It&#8217;s unclear whether NULL values are to be considered lower or higher than conventional values (special clauses <code>NULLS FIRST<\/code> and <code>NULLS LAST<\/code> help out with that). The use of NULL values in aggregate functions is sketchy, too. Because NULL values are, in fact, not values at all, the planner needs extra data to accommodate them.<\/p>\n<p>In addition to basic relation-level statistics, the analyzer also collects statistics for each column in a relation. This data is stored in the <code>pg_statistic<\/code> table in the system catalog and can be conveniently displayed using the <code>pg_stats<\/code> view.<\/p>\n<p><em>Fraction of null values<\/em> is column-level statistics. It&#8217;s designated as <code>null_frac<\/code> in <code>pg_stats<\/code>. In this example some planes haven&#8217;t departed yet, so their time of departure is undefined:<\/p>\n<pre><code class=\"sql\">EXPLAIN SELECT * FROM flights WHERE actual_departure IS NULL;                           QUERY PLAN \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212  Seq Scan on flights  (cost=0.00..4772.67 rows=16036 width=63)    Filter: (actual_departure IS NULL) (2 rows)<\/code><\/pre>\n<p>The optimizer multiplies the total row count by the NULL fraction:<\/p>\n<pre><code class=\"sql\">SELECT round(reltuples * s.null_frac) AS rows FROM pg_class   JOIN pg_stats s ON s.tablename = relname WHERE s.tablename = 'flights'   AND s.attname = 'actual_departure';  rows \u2212\u2212\u2212\u2212\u2212\u2212\u2212  16036 (1 row)<\/code><\/pre>\n<p>This is close enough to the true value of 16348.<\/p>\n<h2>Distinct values<\/h2>\n<p>The number of distinct values in a column is stored in the <code>n_distinct<\/code> field in <code>pg_stats<\/code>.<\/p>\n<p>If <code>n_distinct<\/code> is negative, its absolute value instead represents the fraction of values that are distinct. For example, the value of \u22121 means that every item in the column is unique. When the number of distinct values reaches 10% of the number of rows or more, the analyzer switches to the fraction mode. It is assumed at this point that the proportion will generally remain the same when the data is modified.<\/p>\n<p>If the number of distinct values is calculated incorrectly (because the sample happened to be unrepresentative), you can set this value manually:<\/p>\n<pre><code class=\"sql\">ALTER TABLE ... ALTER COLUMN ... SET (n_distinct = ...);<\/code><\/pre>\n<figure class=\"full-width\"><figcaption><\/figcaption><\/figure>\n<p>The number of distinct values is useful in cases where data is distributed uniformly. Consider this cardinality estimation of a &#171;<em>column<\/em> = <em>expression<\/em>&#187; clause. If the value of <em>expression<\/em> is unknown at the planning stage, the planner assumes that <em>expression<\/em> is equally likely to return any value from the column.<\/p>\n<pre><code class=\"sql\">EXPLAIN SELECT * FROM flights WHERE departure_airport = (   SELECT airport_code FROM airports WHERE city = 'Saint Petersburg' ); QUERY PLAN \u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212\u2212  Seq Scan on flights  (cost=30.56..5340.40 rows=2066 width=63)    Filter: (departure_airport = $0)    InitPlan 1 (returns $0)      \u2212> Seq Scan on airports_data ml  (cost=0.00..30.56 rows=1 wi...          Filter: ((city \u2212>> lang()) = 'Saint Petersburg'::text) (5 rows) <\/code><\/pre>\n<p>The InitPlan node is executed only once, and the value is then used instead of $0 in the main plan.<\/p>\n<pre><code class=\"sql\">SELECT round(reltuples \/ s.n_distinct) AS rows FROM pg_class   JOIN pg_stats s ON s.tablename = relname WHERE s.tablename = 'flights'   AND s.attname = 'departure_airport';  rows \u2212\u2212\u2212\u2212\u2212\u2212  2066 (1 row)<\/code><\/pre>\n<p>If all data is distributed uniformly, these statistics (together with min and max values) would be sufficient for an accurate estimation. Unfortunately, this estimation does not work as well for nonuniform distributions, which are much more common:<\/p>\n<pre><code class=\"sql\">SELECT min(cnt), round(avg(cnt)) avg, max(cnt) FROM (   SELECT departure_airport, count(*) cnt   FROM flights GROUP BY departure_airport ) t;  min | avg  |  max \u2212\u2212\u2212\u2212\u2212+\u2212\u2212\u2212\u2212\u2212\u2212+\u2212\u2212\u2212\u2212\u2212\u2212\u2212  113 | 2066 | 20875 (1 row) <\/code><\/pre>\n<h2>Most common values<\/h2>\n<p>To improve estimation accuracy for non-uniform distributions, the analyzer collects statistics on most common values (MCVs) and their frequency. These values are stored in <code>pg_stats<\/code> as <code>most_common_vals<\/code> and <code>most_common_freqs<\/code>.<\/p>\n<figure class=\"full-width\"><figcaption><\/figcaption><\/figure>\n<p>Here&#8217;s an<\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-390384","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/390384","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=390384"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/390384\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=390384"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=390384"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=390384"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}