73.1. Примеры оценки количества строк#
73.1. Примеры оценки количества строк
Приведенные ниже примеры используют таблицы в тестовой базе данных PostgreSQL.
Показанные результаты взяты из версии 8.3.
Поведение более ранних (или более поздних) версий может отличаться.
Также обратите внимание, что поскольку ANALYZE использует случайную выборку при создании статистики, результаты могут незначительно измениться после каждого нового ANALYZE.
Давайте начнем с очень простого запроса:
EXPLAIN SELECT * FROM tenk1;
QUERY PLAN
-------------------------------------------------------------
Seq Scan on tenk1 (cost=0.00..458.00 rows=10000 width=244)
Как планировщик определяет кардинальность tenk1 описано в Раздел 14.2, но повторяется здесь для полноты. Количество страниц и строк ищется в 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(mvf))/(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 непосредственно применяет условие (например, “< 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
Суммируя все MCF, мы также узнаем, что общая доля населения, представленная MCV, составляет 0,03033333, а, следовательно, доля, представленная гистограммой, составляет 0,96966667 (снова, здесь нет нулей, иначе нам пришлось бы исключить их). Мы видим, что значение IAAAAA практически находится в конце третьего интервала гистограммы. Используя некоторые довольно неправдоподобные предположения о частоте различных символов, планировщик приходит к оценке 0,298387 для доли населения гистограммы, которая меньше IAAAAA. Затем мы объединяем оценки для населения MCV и не 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.