Я уже пару раз рассказывал про конфигурационный параметр default_statistics_target: PostgreSQL. default_statistics_target и PostgreSQL. default_statistics_target. Эксперименты.

Во второй из этих статей я написал следующее:

Относительно последнего пункта — видимо, эта константа 300 забита где-то в исходном коде. Можно будет поискать, но не сейчас. Поэтому этот пункт трогать не буду.

И вот — время для поисков пришло!

Историческая сводка

Некоторое время назад я искал информацию про генетические алгоритмы и оптимизацию запросов и наткнулся на информацию о том, что гистограммы, используемые в т.ч. и в PostgreSQL для сохранения информации о распределении значений в столбцах были предложены Григорием Пятецким-Шапиро (он выпускник МГУ). Эти гистограммы строились на основе выборки из таблицы. На английском можно про это почитать в статье Пятецкого-Шапиро и Чарльза Коннелли: Accurate estimation of the number of tuples satisfying a condition.

Не всё было понятно для меня в этой статье. Но в ней в запросах были указаны конкретные условия и для этих условий производилась выборка из таблицы. А что же делать если условия будут самые разные?

Я стал дальше искать, и каким-то образом натолкнулся на статью 1998 года, которая продолжила исследование Пятецкого-Шапиро: Random Sampling for Histogram Construction: How much is enough? Авторы этой статьи уже не привязывались к каким-то конкретным условиям в запросе, рассчитывают ошибки в зависимости от размера выборки и некоторых других параметров.

И вот уже там было что-то похожее на то, что я и искал (но тоже некоторые детали мог упустить).

Исходный код

После прочтения я всё-же соизволил заглянуть в исходный код PostgreSQL и там довольно быстро нашел то место, куда надо было сразу и заглянуть:

postgres/src/backend/commands/analyze.c (строка номер 1891).

Там есть большой комментарий с отсылкой на статью 1998 года, указан конкретный пункт той статьи, который далее в коде используется, приведена формула из статьи:

r = 4 * k * ln(2*n/gamma) / f^2
Taking f = 0.5, gamma = 0.01, n = 10^6 rows, we obtain r = 305.82 * k

где:

• r — минимальный размер выборки из таблицы;
• n — размер таблицы;
• k — размер гистограммы (т. е. размер default_statistics_target);
• f — максимальная относительная погрешность в корзине;
• gamma — вероятность ошибки.

В статье то же самое:

И там же, в статье, есть вот такой абзац:

First of all, observe that the sample size required grows linearly in k and inversely with the squared deviation, but is essentially independent of n since the logarithmic dependence is negligible.

Прежде всего, обратите внимание, что требуемый размер выборки линейно увеличивается в k раз и обратно пропорционален квадрату отклонения, но по существу не зависит от n, поскольку логарифмическая зависимость пренебрежимо мала.

В исходном коде примерно то же самое:

Note that because of the log function, the dependence on n is quite weak; even at n = 10^12, a 300*k sample gives <= 0.66 bin size error with probability 0.99. So there’s no real need to scale for n.

Обратите внимание, что из-за логарифмической функции зависимость от n довольно слабая; даже при n = 10^12 выборка 300 * k дает погрешность в корзине <= 0,66 с вероятностью 0,99. Таким образом, нет реальной необходимости масштабировать n.

Как понимаю — от увеличения размера таблицы ошибка в выборке не особо возрастает.

Проверка

Я посчитал это в wolframalpha.com:

Если подставить размер выборки 10^12 и ошибку f в 0.66 — то общее значение остается примерно как в прошлый раз:

Наверное, это можно как увеличив в несколько раз размер таблицы, ошибка не очень сильно увеличилась.

Итог

Так что в исходном коде и взяли эту константу — 300 для выбранных параметров:

stats->minrows = 300 * attr→attstattarget;

attstattarget — это как раз и есть размер default_statistics_target (строка номер 1865). Либо attstattarget равен 100 (значение по умолчанию), либо пользовательскому значению, либо статистика не собирается.

Поэтому, получается что выборка из любой большой таблицы (по умолчанию) равна 300 * default_statistics_target = 30 000. Если таблица очень большая (миллиарды записей), то размер выборки всё равно будет такой же и ошибка в распределении приемлемой.

Надеюсь что правильно понял 🙂

А с attstattarget можно будет поэкспериментировать отдельно.