Статистика таблиц: row count, NDV, nulls fraction

Один и тот же SQL-запрос можно исполнить десятками способов: в каком порядке джойнить таблицы, какую сторону джойна разослать на все ноды, что протолкнуть в источник. Способы различаются по стоимости на порядки. Выбирает один из них Cost-Based Optimizer (CBO) — оптимизатор на основе стоимости. Но чтобы оценить стоимость плана, оптимизатору нужно представлять, сколько данных пройдёт через каждый его шаг. А для этого нужны числа о самих данных — статистика таблиц.

Этот модуль — про внутренности CBO. Открывает его урок про фундамент: какую именно статистику CBO собирает и хранит, что каждая метрика означает и как из них выводится оценка объёма данных на каждом шаге плана.

Зачем оптимизатору числа о данных

Представьте join таблицы заказов с таблицей клиентов. Оптимизатор должен решить, какую таблицу сделать build-стороной (по ней строится хэш-таблица в памяти), а какую — probe-стороной (по ней идёт поиск). Если build-сторона мала, её можно разослать на все ноды целиком — быстрый broadcast join. Если велика — придётся перераспределять обе таблицы по хэшу, дорогой partitioned join.

Чтобы выбрать, оптимизатор обязан знать: сколько строк в каждой таблице, сколько они весят. Без этого знания он выбирает вслепую. Может разослать на все ноды таблицу в миллиард строк, думая, что она маленькая, — и каждая нода захлебнётся. Может выстроить join пяти таблиц в порядке, где промежуточный результат раздувается до триллиона строк, тогда как другой порядок дал бы тысячу.

Альтернатива CBO — оптимизация по правилам (rule-based): «всегда делай так». Она не смотрит на данные и потому промахивается, как только данные не вписываются в зашитое правило. CBO смотрит на статистику и выбирает план под конкретные таблицы. Качество его решений ровно настолько хорошо, насколько точна статистика. Нет статистики — CBO деградирует к эвристикам.

Пять метрик статистики

CBO Trino опирается на компактный набор метрик. Они делятся на два уровня: статистика уровня таблицы и статистика уровня столбца.

На уровне таблицы — одна метрика:

• Row count — общее число строк в таблице. Базовая величина: с неё начинается любая оценка объёма.

На уровне столбца — четыре метрики, каждая для конкретного столбца:

• Data size — размер данных столбца. Для столбцов переменной длины (VARCHAR) особенно важен: оценка памяти и сети зависит не только от числа строк, но и от того, насколько строки в столбце «толстые».
• Nulls fraction — доля NULL-значений в столбце, число от 0 до 1. Влияет на оценку: NULL обычно не проходит join по равенству и фильтруется предикатами, поэтому доля NULL корректирует, сколько строк реально дойдёт до результата.
• NDV (number of distinct values) — число различных (уникальных) значений в столбце. Самая важная для джойнов метрика; разберём её отдельно ниже.
• Min / max — минимальное и максимальное значение столбца. Нужны для оценки селективности диапазонных предикатов: WHERE x > 100 при известных min и max позволяет прикинуть, какая доля строк пройдёт.

NDV и оценка кардинальности

NDV заслуживает отдельного разбора, потому что это центральная метрика для предсказания результата join.

Кардинальность — это оценочное число строк, которое CBO ожидает на выходе шага плана. Для join’а двух таблиц по столбцу x грубая идея такая: если в левой таблице x принимает NDV_L различных значений, в правой — NDV_R, то совпадать смогут лишь общие значения, и плотность совпадений тем выше, чем меньше уникальных значений. Equi-join по столбцу с малым NDV (например, country — десятки значений) даёт много совпадений на каждое значение и крупный результат; join по столбцу с огромным NDV, близким к числу строк (например, order_id), — почти один к одному.

Простой пример с фильтром. Запрос WHERE status = 'shipped'. Если CBO знает, что у столбца status NDV равен 5, он оценивает: предикат равенства по одному из 5 значений пропустит примерно 1/5 строк. Это и есть оценка селективности. Она прикидочная — реальное распределение может быть перекошено, — но без NDV у оптимизатора не было бы и такой опоры.

Почему NDV — это «до железа» важно. Ошибка в NDV каскадом портит весь план. Оценил CBO результат join’а в тысячу строк, а реально миллион — он мог выбрать broadcast этой «тысячи» строк, а по факту разослал миллион на каждую ноду. Дальше этот неверно оценённый результат — вход следующего join’а, и ошибка только растёт. Точность NDV особенно критична в многотабличных запросах, где каждый join опирается на оценку предыдущего.

Откуда NDV берётся: HyperLogLog

Точно посчитать NDV столбца на миллиард строк дорого: пришлось бы держать в памяти множество всех уникальных значений. Поэтому NDV в статистике — приближённое число, и считается оно структурой HyperLogLog.

HyperLogLog — это вероятностная структура для оценки кардинальности (числа уникальных значений) в фиксированной, очень небольшой памяти — килобайты вместо потенциальных гигабайт. Идея: хэшировать каждое значение и по статистике хэшей оценивать, сколько уникальных значений могло такие хэши породить. Точное множество значений не хранится — хранится компактная сводка. Цена — небольшая, ограниченная погрешность оценки; выигрыш — постоянная память независимо от объёма данных.

То же самое доступно в SQL напрямую — функция approx_distinct(column) оценивает NDV через HyperLogLog. Когда CBO собирает статистику, под капотом работает та же механика.

Статистика всегда оценочна — и это нормально

Зафиксируем общий принцип, к которому вернёмся в следующих уроках. Вся статистика, которой оперирует CBO, — оценочная и в той или иной мере устаревшая. NDV приближён HyperLogLog’ом. Распределение значений предполагается равномерным, хотя в реальных данных оно перекошено (значение country = 'US' может занимать половину таблицы при NDV в сотни стран). Статистика отражает состояние данных на момент её сбора, а данные с тех пор могли измениться.

Из этого не следует, что статистика бесполезна, — следует, что CBO работает с приближениями и его задача не «вычислить точную стоимость», а выбрать разумный план среди вариантов. Для этого хватает оценок верного порядка. Проблемы начинаются, когда статистики нет вовсе или она грубо устарела: тогда оценки расходятся с реальностью не в разы, а на порядки, и CBO выбирает плохой план. Именно поэтому следующий урок — про то, как статистику собирать и поддерживать актуальной командой ANALYZE.

Попробуй сам

На песочнице курса (Trino 481):

1. Выполните SHOW STATS FOR tpch.sf1.orders;. В выводе найдите столбцы distinct_values_count (это NDV), nulls_fraction, data_size и строку с общим row_count. Для столбца orderstatus запишите NDV — сравните его с тем, что даёт SELECT count(DISTINCT orderstatus) FROM tpch.sf1.orders;.

2. Рассуждение. У таблицы orders столбец orderkey — это ключ заказа, а orderstatus — статус из небольшого набора. У какого столбца NDV будет огромным, близким к row count, а у какого — крошечным? Объясните, как это влияет на оценку результата equi-join: по какому из этих столбцов join даст результат «почти один к одному», а по какому — много совпадений на каждое значение.

3. Выполните SELECT approx_distinct(orderkey), count(DISTINCT orderkey) FROM tpch.sf1.orders;. Сравните два числа. Объясните, почему они близки, но могут не совпадать точно, и как это связано с тем, что NDV в статистике считается через HyperLogLog.