Примеры оценки строк

В приведенных ниже примерах используются таблицы из базы данных регрессионного тестирования PostgreSQL. Представленные результаты взяты из версии 8.3.. Поведение более ранних (или более поздних) версий может отличаться. Также обратите внимание, что поскольку ANALYZE использует случайную выборку при создании статистики, результаты немного изменятся после любого нового ANALYZE.

Начнем с очень простого запроса:

EXPLAIN SELECT * FROM tenk1;

                         QUERY PLAN
-------------------------------------------------------------
 Seq Scan on tenk1  (cost=0.00..458.00 rows=10000 width=244)

Количество страниц и строк указано в pg_class:

SELECT relpages, reltuples FROM pg_class WHERE relname = 'tenk1';

 relpages | reltuples
----------+-----------
      358 |     10000

Эти числа актуальны на момент последнего VACUUM или ANALYZE в таблице. Затем планировщик получает фактическое текущее количество страниц в таблице (это недорогая операция, не требующая сканирования таблицы). Если это отличается от relpages, то reltuples масштабируется соответствующим образом, чтобы получить текущую оценку количества строк. В приведенном выше примере значение relpages актуально, поэтому количество строк совпадает с reltuples.

Перейдем к примеру с условием диапазона в предложении WHERE:

EXPLAIN SELECT * FROM tenk1 WHERE unique1 < 1000;

                                   QUERY PLAN
--------------------------------------------------------------------------------
 Bitmap Heap Scan on tenk1  (cost=24.06..394.64 rows=1007 width=244)
   Recheck Cond: (unique1 < 1000)
   ->  Bitmap Index Scan on tenk1_unique1  (cost=0.00..23.80 rows=1007 width=0)
         Index Cond: (unique1 < 1000)

Планировщик исследует условие предложения WHERE и ищет функцию селективности для оператора < в pg_operator. Это удерживается в столбце oprrest, и запись в этом случае — scalarltsel. Функция scalarltsel извлекает гистограмму для unique1 из pg_statistic. Для ручных запросов удобнее искать более простое представление pg_stats:

SELECT histogram_bounds FROM pg_stats
WHERE tablename='tenk1' AND attname='unique1';

                   histogram_bounds
------------------------------------------------------
 {0,993,1997,3050,4040,5036,5957,7057,8029,9016,9995}

Затем вычисляется доля гистограммы, занимаемая «< 1000». Это селективность. Гистограмма делит диапазон на равные частотные сегменты, поэтому нужно найти сегмент, содержащий искомое значение, и суммировать его вместе с предыдущими. Значение 1000 явно находится во втором сегменте (993–1997). Предположим линейное распределение значений внутри каждого сегмента, мы можем вычислить селективность следующим образом:

selectivity = (1 + (1000 - bucket[2].min)/(bucket[2].max - bucket[2].min))/num_buckets
            = (1 + (1000 - 993)/(1997 - 993))/10
            = 0.100697

То есть сумма элементов одной целой группы и пропорциональной части элементов второй, деленная на число групп. Теперь примерное число строк может быть рассчитано как произведение избирательности и мощности tenk1:

rows = rel_cardinality * selectivity
     = 10000 * 0.100697
     = 1007  (rounding off)

Далее рассмотрим пример с условием равенства в предложении WHERE:

EXPLAIN SELECT * FROM tenk1 WHERE stringu1 = 'CRAAAA';

                        QUERY PLAN
----------------------------------------------------------
 Seq Scan on tenk1  (cost=0.00..483.00 rows=30 width=244)
   Filter: (stringu1 = 'CRAAAA'::name)

Планировщик исследует условие предложения WHERE и ищет функцию селективности для =, которая является eqsel. Для оценки равенства гистограмма не полезна, вместо этого для определения селективности используется список наиболее распространенных значений (MCV). Давайте рассмотрим MCV с некоторыми дополнительными столбцами, которые будут полезны позже:

SELECT null_frac, n_distinct, most_common_vals, most_common_freqs FROM pg_stats
WHERE tablename='tenk1' AND attname='stringu1';

null_frac         | 0
n_distinct        | 676
most_common_vals  | {EJAAAA,BBAAAA,CRAAAA,FCAAAA,FEAAAA,GSAAAA,​JOAAAA,MCAAAA,NAAAAA,WGAAAA}
most_common_freqs | {0.00333333,0.003,0.003,0.003,0.003,0.003,​0.003,0.003,0.003,0.003}

Поскольку CRAAAA появляется в списке MCV, селективность является лишь соответствующей записью в списке наиболее распространенных частот (MCF):

selectivity = mcf[3]
            = 0.003

Как и раньше, предполагаемое количество строк является только частью этого с мощностью tenk1:

rows = 10000 * 0.003
     = 30

Теперь рассмотрим тот же запрос, но с константой, которой нет в списке MCV:

EXPLAIN SELECT * FROM tenk1 WHERE stringu1 = 'xxx';

                        QUERY PLAN
----------------------------------------------------------
 Seq Scan on tenk1  (cost=0.00..483.00 rows=15 width=244)
   Filter: (stringu1 = 'xxx'::name)

Это совсем другая проблема: как оценить селективность, когда значение не в списке MCV. Подход заключается в использовании того факта, что значение не в списке, в сочетании со знанием частот для всех MCV:

selectivity = (1 - sum(mcv_freqs))/(num_distinct - num_mcv)
            = (1 - (0.00333333 + 0.003 + 0.003 + 0.003 + 0.003 + 0.003 +
                    0.003 + 0.003 + 0.003 + 0.003))/(676 - 10)
            = 0.0014559

То есть сложите все частоты для MCV и вычтите их из одного, затем разделите на число других отличительных значений. Это равнозначно предположению, что доля столбца, который не является ни одним из MCV, равномерно распределена среди всех других отличительных значений. Обратите внимание, что нет нулевых значений, поэтому нам не нужно беспокоиться о них (иначе мы бы также выделили нулевую дробь из числителя). Затем рассчитывается предполагаемое количество строк, как обычно:

rows = 10000 * 0.0014559
     = 15  (rounding off)

Предыдущий пример с unique1 < 1000 был чрезмерным упрощением того, что на самом деле делает scalarltsel; теперь, когда мы видели пример использования MCV, мы можем добавить немного подробностей. Пример был правильным, поскольку unique1 является уникальным столбцом, у него нет MCV (очевидно, ни одно значение не является более распространенным, чем любое другое значение). Для неуникального столбца обычно будет и гистограмма, и список MCV, и гистограмма не включает часть популяции столбцов, представленную MCV. Мы делаем это так, потому что это позволяет получить более точную оценку. В этой ситуации scalarltsel напрямую применяет условие (<HTML0, «< 1000») к каждому значению списка MCV и суммирует частоты MCV, для которых условие является истинным. Это дает точную оценку селективности в той части таблицы, которая является MCV. Затем гистограмма используется так же, как и выше, для оценки селективности в той части таблицы, которая не является MCV, а затем два числа объединяются для оценки общей селективности. Например, рассмотрим:

EXPLAIN SELECT * FROM tenk1 WHERE stringu1 < 'IAAAAA';

                         QUERY PLAN
------------------------------------------------------------
 Seq Scan on tenk1  (cost=0.00..483.00 rows=3077 width=244)
   Filter: (stringu1 < 'IAAAAA'::name)

Мы уже видели информацию о MCV для stringu1, и вот его гистограмма:

SELECT histogram_bounds FROM pg_stats
WHERE tablename='tenk1' AND attname='stringu1';

                                histogram_bounds
-------------------------------------------------------------------​-------------
 {AAAAAA,CQAAAA,FRAAAA,IBAAAA,KRAAAA,NFAAAA,PSAAAA,SGAAAA,VAAAAA,​XLAAAA,ZZAAAA}

Проверяя список MCV, мы обнаруживаем, что условию stringu1 < 'IAAAAA' удовлетворяют первые шесть записей, а не последние четыре, поэтому селективность в части популяции MCV составляет:

selectivity = sum(relevant mvfs)
            = 0.00333333 + 0.003 + 0.003 + 0.003 + 0.003 + 0.003
            = 0.01833333

Основываясь на простых предположениях относительно частоты различных символов, планировщик получает число 0.298387 для части значений, представленных в гистограмме, которые меньше чем IAAAAA. Затем объединяем оценки части значений из списка MCV и значений, не содержащихся в нем:

selectivity = mcv_selectivity + histogram_selectivity * histogram_fraction
            = 0.01833333 + 0.298387 * 0.96966667
            = 0.307669

rows        = 10000 * 0.307669
            = 3077  (rounding off)

В этом конкретном примере коррекция из списка MCV довольно мала, потому что распределение столбцов на самом деле довольно равномерно (статистика, показывающая, что эти конкретные значения являются более распространенными, чем другие, в основном связана с ошибкой выборки). В более типичном случае, когда некоторые значения значительно более распространены, чем другие, этот сложный процесс дает полезное улучшение точности, потому что избирательность для наиболее распространенных значений найдена точно.

Теперь рассмотрим случай с более чем одним условием в предложении WHERE:

EXPLAIN SELECT * FROM tenk1 WHERE unique1 < 1000 AND stringu1 = 'xxx';

                                   QUERY PLAN
-------------------------------------------------------------------​-------------
 Bitmap Heap Scan on tenk1  (cost=23.80..396.91 rows=1 width=244)
   Recheck Cond: (unique1 < 1000)
   Filter: (stringu1 = 'xxx'::name)
   ->  Bitmap Index Scan on tenk1_unique1  (cost=0.00..23.80 rows=1007 width=0)
         Index Cond: (unique1 < 1000)

Планировщик предполагает, что два условия независимы друг от друга, так что отдельные варианты предложений можно умножить вместе:

selectivity = selectivity(unique1 < 1000) * selectivity(stringu1 = 'xxx')
            = 0.100697 * 0.0014559
            = 0.0001466

rows        = 10000 * 0.0001466
            = 1  (rounding off)

Обратите внимание, что количество строк, которые, по оценкам, будут возвращены при сканировании индекса растрового изображения, отражает только условие, используемое с индексом; это важно, поскольку оно влияет на оценку стоимости последующих массивов.

Наконец, рассмотрим запрос, который включает соединение:

EXPLAIN SELECT * FROM tenk1 t1, tenk2 t2
WHERE t1.unique1 < 50 AND t1.unique2 = t2.unique2;

                                      QUERY PLAN
--------------------------------------------------------------------------------------
 Nested Loop  (cost=4.64..456.23 rows=50 width=488)
   ->  Bitmap Heap Scan on tenk1 t1  (cost=4.64..142.17 rows=50 width=244)
         Recheck Cond: (unique1 < 50)
         ->  Bitmap Index Scan on tenk1_unique1  (cost=0.00..4.63 rows=50 width=0)
               Index Cond: (unique1 < 50)
   ->  Index Scan using tenk2_unique2 on tenk2 t2  (cost=0.00..6.27 rows=1 width=244)
         Index Cond: (unique2 = t1.unique2)

Ограничение на tenk1, unique1 < 50, оценивается перед соединением с вложенным циклом. Это обрабатывается аналогично предыдущему примеру диапазона. На этот раз значение 50 попадает в первый блок гистограммы unique1:

selectivity = (0 + (50 - bucket[1].min)/(bucket[1].max - bucket[1].min))/num_buckets
            = (0 + (50 - 0)/(993 - 0))/10
            = 0.005035

rows        = 10000 * 0.005035
            = 50  (rounding off)

Ограничение для соединения t2.unique2 = t1.unique2. Оператор просто знаком =, однако функция выборки получена из столбца oprjoin pg_operator и является eqjoinsel. eqjoinsel ищет статистическую информацию как для tenk2, так и для tenk1:

SELECT tablename, null_frac,n_distinct, most_common_vals FROM pg_stats
WHERE tablename IN ('tenk1', 'tenk2') AND attname='unique2';

tablename  | null_frac | n_distinct | most_common_vals
-----------+-----------+------------+------------------
 tenk1     |         0 |         -1 |
 tenk2     |         0 |         -1 |

В этом случае нет информации MCV для unique2, потому что все значения кажутся уникальными, поэтому мы используем алгоритм, который полагается только на количество различных значений для обоих отношений вместе с их нулевыми дробями:

selectivity = (1 - null_frac1) * (1 - null_frac2) * min(1/num_distinct1, 1/num_distinct2)
            = (1 - 0) * (1 - 0) / max(10000, 10000)
            = 0.0001

То есть вычтите нулевую долю из одной для каждого из отношений и разделите на максимум числа различных значений. Количество строк, которое соединение, вероятно, сгенерирует, вычисляется как мощность декартова произведения двух входных значений, умноженная на избирательность:

rows = (outer_cardinality * inner_cardinality) * selectivity
     = (50 * 10000) * 0.0001
     = 50

Если бы были списки MCV для двух столбцов, eqjoinsel использовал бы прямое сравнение списков MCV для определения выбора соединения в части популяций столбцов, представленных MCV. Оценка для остальных популяций следует тому же подходу, который показан здесь.

Обратите внимание, что мы показали inner_cardinality как 10000, то есть неизмененный размер tenk2. Из проверки выхода EXPLAIN может показаться, что оценка строк соединения исходит из 50 * 1, то есть количество внешних строк умножено на оценочное количество строк, полученных каждым сканированием внутреннего индекса на tenk2. Но это не так: размер отношения объединения оценивается до того, как был рассмотрен какой-либо конкретный план объединения. Если все работает хорошо, два способа оценки размера объединения дадут примерно один и тот же ответ, но из-за ошибки округления и других факторов они иногда значительно расходятся.

Для тех, кто интересуется более подробной информацией, оценка размера таблицы (перед любыми предложениями WHERE) выполняется в src/backend/optimizer/util/plancat.c. Общая логика для селективности предложений находится в src/backend/optimizer/path/clausesel.c. Функции селективности, специфичные для операторов, в основном находятся в src/backend/utils/adt/selfuncs.c.