Множества, логика и математика таблиц

Язык множеств даёт точные слова для того, что происходит при соединении таблиц, и объясняет, почему результат JOIN иногда больше обеих исходных таблиц вместе взятых.

Суть

Множество — это набор различимых объектов, рассматриваемый как одно целое. У множества есть только одно содержательное свойство: про любой объект можно сказать, входит он в множество или нет. Порядок элементов не имеет значения, повторов не бывает. Число элементов конечного множества называют его мощностью и обозначают вертикальными чертами: |A|.

Над множествами определены четыре операции, которых достаточно для описания почти всей работы с таблицами. Объединение A ∪ B — все элементы, входящие хотя бы в одно из множеств. Пересечение A ∩ B — элементы, входящие в оба. Разность A \ B — элементы A, которых нет в B. Декартово произведение A × B — множество всех упорядоченных пар, где первый элемент взят из A, а второй из B. Первые три операции не увеличивают результат сверх суммы размеров, а четвёртая увеличивает: мощность произведения равна произведению мощностей.

Теперь переведём это на таблицы. Строка таблицы — элемент множества, схема таблицы задаёт, из каких пар «колонка — значение» этот элемент составлен. Реляционная модель, которую Эдгар Кодд предложил в 1970 году, строилась именно на этой аналогии: отношение есть подмножество декартова произведения доменов колонок. Отсюда и название «реляционная».

Соединение как произведение с фильтром

Формально JOIN определяется в два шага. Сначала строится декартово произведение двух таблиц: каждая строка левой склеивается с каждой строкой правой. Потом из этого произведения отбираются строки, удовлетворяющие условию ON. Никакой другой механики в соединении нет.

Из такого определения сразу следует несколько вещей. Во-первых, если условие ON опустить или написать в нём 1 = 1, вы получите полное произведение. Соединение витрины заказов на десять миллионов строк со справочником на тысячу строк без условия даст десять миллиардов строк — запрос не завершится, и это будет ошибкой не базы, а автора запроса. Во-вторых, размер результата определяется не размерами таблиц, а тем, сколько пар строк проходят условие. В-третьих, соединение по условию неравенства (ON a.dt BETWEEN b.dt_from AND b.dt_to) — такая же законная операция, но число проходящих пар в ней предсказать сложнее, чем при соединении по равенству ключей.

Виды соединений на языке множеств

Пусть K₁ — множество значений ключа, встречающихся в левой таблице, K₂ — в правой. Тогда INNER JOIN оставляет строки, ключ которых лежит в K₁ ∩ K₂. LEFT JOIN сохраняет все ключи из K₁, дополняя NULL-ами те, что попали в K₁ \ K₂. FULL OUTER JOIN покрывает K₁ ∪ K₂. Конструкция LEFT JOIN … WHERE b.id IS NULL — это разность K₁ \ K₂ в чистом виде, ей часто пользуются, чтобы найти записи без пары.

Отдельно стоят операции над результатами запросов: UNION ALL складывает строки без обработки повторов, UNION дополнительно убирает дубликаты, INTERSECT и EXCEPT дают пересечение и разность. Эти четыре конструкции работают с таблицами как с множествами строк целиком, а не по ключу.

Где аналогия ломается

Таблица в SQL — не множество, а мультимножество: одинаковые строки в ней разрешены и хранятся отдельно. Это отличие лежит в основе большинства ошибок при соединениях. В множестве элемент либо есть, либо нет; в мультимножестве у каждого элемента есть кратность, и соединение эти кратности перемножает. Если в правой таблице ключ встречается трижды, каждая соответствующая строка левой таблицы вернётся в результате три раза. Мощность результата тогда считается не как пересечение, а как сумма произведений кратностей по всем общим ключам.

Второе расхождение — NULL. В теории множеств элемент либо принадлежит множеству, либо нет; в SQL сравнение с NULL даёт третий ответ «неизвестно», и строка с таким результатом условия в соединение не попадает. Об этом отдельная тема далее.

Кардинальность связи предсказывает, во сколько раз вырастет таблица после соединения и почему выручка в отчёте окажется завышенной.

Суть

Кардинальность связи между двумя таблицами описывает, сколько строк одной таблицы может соответствовать одной строке другой. Различают три случая. Один к одному (1:1) — каждому ключу слева соответствует не более одной строки справа: например, заказ и его запись в таблице отмен. Один ко многим (1:N) — одному заказу соответствует несколько позиций, одному клиенту несколько заказов. Многие ко многим (N:M) — например, товары и акции: товар участвует в нескольких акциях, в акции участвует множество товаров.

Точная формула размера результата выводится напрямую. Обозначим через aₖ число строк с ключом k в левой таблице, через bₖ — в правой. Внутри одного ключа соединение даёт полное произведение: aₖ · bₖ строк. Суммируя по всем ключам, получаем общий размер.

Если справа ключ уникален, все bₖ равны единице и сумма сворачивается в число строк слева — соединение размера не меняет. Как только bₖ становится больше единицы, строки слева размножаются. Это явление называют раздуванием, или fan-out.

Почему растёт сумма

Раздувание само по себе не ошибка: оно означает, что вы перешли на более мелкую гранулярность. Ошибка возникает, когда после раздувания вы суммируете колонку, которая была определена на прежнем, крупном уровне. Сумма заказа записана в таблице заказов один раз на заказ. Если заказ размножился на три позиции, SUM по этой колонке сложит одну и ту же величину трижды.

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

Цепочка соединений и перемножение

Отдельный источник раздувания — два независимых соединения 1:N от одной и той же таблицы. Если к заказу присоединить позиции и отдельно платежи, база построит все пары «позиция — платёж». Заказ с тремя позициями и двумя платежами даст 3 · 2 = 6 строк, хотя ни в одной исходной таблице шести строк не было. При добавлении третьего такого соединения множители продолжают перемножаться. Правило: количество измерений в цепочке безопасно наращивать только тогда, когда каждое из них присоединяется по уникальному ключу.

Как чинить

Первый способ — агрегировать до соединения. Свернуть позиции до уровня заказа подзапросом, а потом присоединить результат, ключ которого уже уникален. Это единственный способ, который сохраняет корректность при любых распределениях.

Второй способ — считать на разных гранулярностях по отдельности и соединять уже готовые числа, а не строки. Третий — воспользоваться оконной функцией или конструкцией вида SUM(CASE WHEN row_number = 1 THEN amount END), помечая одну строку на заказ. Способ, который применять не следует, — SUM(DISTINCT amount): он схлопывает не дубликаты заказов, а совпадающие суммы, и два разных заказа по 1 490 рублей превратятся в один.

Гранулярность — это ответ на вопрос «что означает одна строка», и от него зависит, какие метрики вообще можно посчитать из таблицы.

Суть

Гранулярность (зерно таблицы) — набор колонок, комбинация значений которых уникальна и полностью определяет строку. Витрина заказов с зерном «заказ» содержит по одной строке на заказ. Витрина с зерном «заказ × позиция» — по строке на каждую товарную позицию. Лог просмотров объявлений классифайда имеет зерно «просмотр»: пользователь, объявление, момент времени. Одна и та же предметная область описывается таблицами разного зерна, и это нормально; ненормально не знать, с каким зерном вы работаете.

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

Аддитивность мер

Метрики делятся на три класса по тому, как они переносят агрегацию. Аддитивные складываются по любому измерению: выручка, число заказов, количество штук. Их можно суммировать по дням, регионам, категориям в любом порядке, результат совпадёт.

Полуаддитивные складываются по одним измерениям и не складываются по другим. Классический случай — остаток на счёте в таблице транзакций банка. Остатки разных клиентов на одну дату складывать осмысленно: получится совокупный портфель. Остатки одного клиента за тридцать дней складывать нельзя — получится величина без содержания. По времени такие меры агрегируют иначе: берут значение на конец периода или среднее за период. К этому же классу относятся складские остатки и число активных подписок.

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

Среднее по средним

Самая частая ошибка агрегации — усреднение уже усреднённых величин. Среднее средних равно общему среднему только тогда, когда все группы одинакового размера. В реальных данных группы разного размера всегда, поэтому результат отличается — иногда драматически.

Ту же природу имеет и парадокс Симпсона: соотношение, верное внутри каждой группы, может перевернуться при объединении групп, если веса групп сильно различаются. Практический вывод для отчётности: «средняя конверсия по регионам» и «конверсия по всем регионам» — две разные метрики, и в дашборде нужно писать, какая из них показана.

Смена уровня в одном запросе

Часто требуется показать метрику одного уровня рядом с метрикой другого: доля категории в общей выручке, отношение заказа к среднему чеку клиента. Для этого существуют оконные функции — они вычисляют агрегат по группе, не схлопывая строки. Выражение SUM(amount) OVER (PARTITION BY category) даёт итог категории в каждой строке, а деление на SUM(amount) OVER () — долю. Это корректная альтернатива соединению с подзапросом-агрегатом, которая не создаёт риска раздувания.

Уникальные пользователи за период не равны сумме уникальных пользователей по дням, и принцип включения-исключения показывает, чему они равны на самом деле.

Суть

Число элементов объединения двух множеств меньше суммы их мощностей ровно на величину пересечения: элементы, попавшие в оба множества, при сложении посчитаны дважды, и один из двух подсчётов надо снять. Это и есть принцип включения-исключения. Для трёх множеств процедура продолжается: вычитая три попарных пересечения, вы снимаете тройное пересечение трижды, хотя оно было учтено трижды и в сумме мощностей, поэтому его нужно вернуть.

Отсюда следует главный практический вывод: COUNT(DISTINCT …) не аддитивен. Уникальные покупатели за квартал не складываются из уникальных покупателей по месяцам, уникальные посетители сайта не складываются из уникальных по каналам, месячная аудитория не равна сумме дневных. Любая метрика вида «число уникальных сущностей» требует пересчёта на том периоде и в том разрезе, в котором её показывают.

Откуда берутся дубликаты

Дубликаты бывают двух принципиально разных видов, и лечатся они по-разному. Технические дубликаты — следствие сбоя загрузки: пакет данных проехал дважды, ретрай отправил событие повторно, стриминговая доставка гарантирует «хотя бы один раз» и потому иногда доставляет дважды. Такие строки идентичны или различаются только техническим временем загрузки, их следует убирать при подготовке витрины, а не в каждом отчёте.

Смысловые дубликаты — не дубликаты вовсе. Строки различаются, но по тем колонкам, которые вы выбрали, выглядят одинаково: у пользователя две сессии за день, у объявления два просмотра от одного человека, у клиента два продукта. Убирать их через DISTINCT означает молча изменить метрику. Правильный ответ — понять, какое зерно вам нужно, и агрегировать явно.

DISTINCT как диагноз

Конструкция SELECT DISTINCT, добавленная в запрос потому, что «строк получилось многовато», почти всегда маскирует раздувание из предыдущей темы. Она уберёт полностью совпадающие строки, но не восстановит корректность: если заказ размножился на три позиции и суммы позиций различаются, DISTINCT ничего не схлопнет, а если совпадают — схлопнет лишнее и занизит результат. Появление DISTINCT в запросе — повод вернуться к соединению и проверить кардинальность ключей, а не признак того, что проблема решена.

Отдельно стоит помнить о стоимости: COUNT(DISTINCT …) требует хранить все встреченные значения, поэтому на десятках миллионов уникальных ключей он существенно дороже COUNT(*). Об экономичных приближениях — в теме 2.7.

UNION и UNION ALL

Разница между этими операциями — ровно принцип включения-исключения. UNION ALL выдаёт |A| + |B| строк, UNION выдаёт |A ∪ B|, потратив ресурсы на удаление повторов. Если вы точно знаете, что источники не пересекаются (например, объединяете партиции за разные месяцы), UNION ALL и корректнее по смыслу, и дешевле. Если пересечение возможно, а вы взяли UNION ALL, повторы попадут в итог молча.

В SQL условие может быть истинным, ложным и неизвестным, и строки с неизвестным результатом молча выпадают из выборки вместе с частью выручки.

Суть

NULL — не значение и не ноль. Это маркер, означающий «значение отсутствует» или «неизвестно». Отсутствовать значение может по разным причинам: у транзакции нет категории торговой точки, поле не заполнялось на момент загрузки, поле пришло из внешней таблицы через LEFT JOIN и пары не нашлось. Для базы все эти случаи выглядят одинаково.

Раз NULL означает «неизвестно», результат сравнения с ним тоже неизвестен. Условие amount > 1000 при неизвестном amount нельзя объявить ни истинным, ни ложным. Поэтому логика в SQL трёхзначная: TRUE, FALSE и UNKNOWN. Оператор WHERE пропускает дальше только строки со значением TRUE — и FALSE, и UNKNOWN отсекаются одинаково. Это и есть механизм, по которому строки исчезают незаметно.

Отсюда же следует, что NULL = NULL даёт не TRUE, а UNKNOWN: два неизвестных значения не обязаны совпадать. Для проверки отсутствия существуют отдельные операторы IS NULL и IS NOT NULL, возвращающие честные TRUE или FALSE.

Таблицы истинности

Правила комбинирования выведены из смысла UNKNOWN: результат известен, если он не зависит от неизвестного операнда.

Строка «FALSE AND UNKNOWN = FALSE» читается так: если одно условие заведомо ложно, конъюнкция ложна независимо от второго. Аналогично «TRUE OR UNKNOWN = TRUE». Оператор NOT переводит TRUE в FALSE и обратно, а UNKNOWN оставляет UNKNOWN — поэтому отрицание не спасает: NOT (x = 5) при NULL так же не пропустит строку, как и x = 5.

Три ловушки, которые встречаются постоянно

Первая — оператор NOT IN со списком, содержащим NULL. Выражение x NOT IN (1, 2, NULL) разворачивается в x <> 1 AND x <> 2 AND x <> NULL. Последний множитель всегда UNKNOWN, поэтому вся конъюнкция никогда не бывает TRUE, и запрос возвращает ноль строк при любых данных. Особенно коварно, когда список приходит из подзапроса, где NULL появился недавно. Замена на NOT EXISTS устраняет проблему, поскольку там сравнение идёт построчно.

Вторая — фильтр по правой таблице в WHERE после LEFT JOIN. Условие вида WHERE b.status = 'ok' отбрасывает строки, где пары не нашлось и b.status равен NULL, превращая внешнее соединение во внутреннее. Если условие относится к самому соединению, его место в ON; если это фильтр результата — нужно явно дописать OR b.status IS NULL.

Третья — агрегатные функции. Все они, кроме COUNT(*), игнорируют NULL. AVG(x) делит сумму на число непустых значений, а не на число строк. Если пропуски по смыслу означают ноль, надо писать AVG(COALESCE(x, 0)); если означают «неизвестно» — оставлять как есть, но понимать, по какой базе считается среднее. Разница между COUNT(*) и COUNT(column) — самый быстрый способ узнать количество пропусков в колонке.

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

Суть

Вся комбинаторика для аналитической практики выводится из одного правила — правила умножения. Если первый выбор делается n₁ способами, а второй независимо от него n₂ способами, то пара выбирается n₁ · n₂ способами. Отсюда следует всё остальное.

Число подмножеств множества из n элементов равно 2ⁿ: для каждого элемента независимо решается, входит он в подмножество или нет. Число способов выбрать k элементов из n без учёта порядка — биномиальный коэффициент.

Число упорядоченных наборов длины k из n вариантов с повторениями равно n в степени k — это ровно то, что описывает, сколько существует путей пользователя длиной в k шагов при n типах событий.

Сколько ячеек в дашборде

Разрез отчёта — это комбинация значений измерений, и число комбинаций перемножается. Допустим, в витрине маркетплейса есть регион (8 укрупнённых макрорегионов), устройство (3 типа), канал привлечения (5 значений) и сегмент покупателя (4 значения). Полный куб содержит 8 · 3 · 5 · 4 = 480 комбинаций. Если по каждому измерению вы хотите ещё и строку «Всего», у каждого измерения появляется дополнительный уровень, и общее число ячеек равно 9 · 4 · 6 · 5 = 1 080.

Отдельно считается число уровней агрегации. При четырёх измерениях группировать можно по любому подмножеству измерений, то есть существует 2⁴ = 16 разных уровней — от полной детализации до единственной итоговой строки. Именно столько наборов вычисляет конструкция GROUP BY CUBE, и именно поэтому она резко дорожает с добавлением каждого нового измерения: пятое измерение удваивает работу до 32 уровней.

Когорты

Когортная таблица устроена как треугольник: когорта, набранная в месяц i, наблюдается только в месяцы i и позже. Если период набора и период наблюдения составляют по m месяцев, число заполненных ячеек равно m · (m + 1) / 2. При m = 24 это 24 · 25 / 2 = 300 ячеек. Прямоугольник 24 × 24 дал бы 576 ячеек, то есть почти половина сетки останется пустой по построению — пустоту в правом верхнем углу когортной таблицы не следует принимать за потерю данных.

Тот же счёт нужен при планировании выгрузки. Если к когортной сетке добавить разбивку по трём каналам и двум платформам, получится 300 · 3 · 2 = 1 800 строк — это ещё обозримо. Добавление региона с восемью значениями превращает выгрузку в 14 400 строк, где большинство ячеек содержит слишком мало наблюдений, чтобы делать по ним выводы.

Обратная сторона: множественные сравнения

Число срезов определяет, сколько случайных «находок» вы обнаружите. Если проверять каждый срез на значимость с порогом 0,05, то при отсутствии реального эффекта в среднем 5 % срезов дадут значимый результат случайно. На 480 срезах это 480 · 0,05 = 24 ложных сигнала. Вероятность не получить ни одного ложного срабатывания равна 0,95 в степени 480 — величина порядка 10 в минус одиннадцатой степени, то есть при таком количестве проверок ложные находки гарантированы.

Тот же счёт применим к попарным сравнениям. Сравнивая 20 городов между собой, вы делаете C(20, 2) = 20 · 19 / 2 = 190 сравнений, и около 190 · 0,05 ≈ 9–10 из них окажутся «значимыми» при полном отсутствии различий. Практический вывод: формулировать гипотезу о конкретном срезе до просмотра данных, а найденное перебором проверять на новом периоде.

На таблицах в сотни миллионов строк точный подсчёт уникальных стоит дорого, и есть два способа получить ответ с контролируемой погрешностью за долю ресурсов.

Суть

Точный COUNT(DISTINCT user_id) требует хранить каждое встреченное значение, чтобы отличить новое от уже виденного. Память растёт линейно с числом уникальных значений. Допустим, в логе просмотров объявлений классифайда 80 млн уникальных пользователей за месяц; при 16 байтах на элемент структуры это порядка 80 000 000 · 16 = 1 280 000 000 байт, около 1,3 ГБ на один узел. Если ту же метрику надо посчитать в разрезе 480 сегментов, задача перестаёт помещаться в память, и движок уходит в перекладывание данных на диск.

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

Как устроен HyperLogLog

Идея опирается на свойство хеш-функции: хеш равномерно распределён по битам, поэтому вероятность того, что хеш начинается ровно с k нулей, равна 1 / 2 в степени (k + 1). Если среди множества хешей встретился хеш с 10 ведущими нулями, разумно предположить, что различных значений было порядка 2¹⁰ ≈ 1 000. Одно такое наблюдение крайне неустойчиво, поэтому поток разбивают на m независимых частей (по первым битам хеша), в каждой запоминают максимальное число ведущих нулей, а затем усредняют оценки гармоническим средним, что подавляет выбросы.

Относительная погрешность такой конструкции определяется числом регистров.

При m = 16 384 регистрах получаем 1,04 / 128 = 0,0081, то есть около 0,8 %. Каждый регистр хранит небольшое число (до 6 бит), поэтому вся структура занимает 16 384 · 6 / 8 = 12 288 байт, около 12 КБ вместо 1,3 ГБ. Это и есть причина, по которой approx_count_distinct в аналитических движках работает на порядки быстрее точного подсчёта.

Второе свойство HLL важнее скорости: скетчи объединяются. Два скетча складываются покомпонентно взятием максимума, и результат равен скетчу объединённого потока. Это снимает ограничение из темы 2.4: если хранить в суточной витрине не число уникальных, а HLL-скетч, месячную аудиторию можно получить объединением тридцати суточных скетчей без обращения к исходному логу. Точность при этом не деградирует, поскольку объединение точное — приближённой остаётся только оценка мощности.

Сэмплирование

При сэмплировании берётся доля p строк, метрика считается на них и масштабируется на 1 / p. Для долей и средних это работает хорошо: стандартная ошибка оценки доли зависит от размера выборки, а не от размера исходной таблицы.

Для выборки в 1 000 000 строк и доли конверсии около 2 % получаем √(0,02 · 0,98 / 1 000 000) = √0,0000000196 ≈ 0,00014, то есть 0,014 процентного пункта. Интервал в две стандартные ошибки — примерно ±0,03 п. п. Такой точности достаточно почти для любого продуктового решения.

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

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

Где приближения неприменимы

Финансовая сверка, регуляторная отчётность, расчёт выплат партнёрам и любые числа, которые кто-то будет сверять с другой системой, требуют точного подсчёта. Погрешность 0,8 % на обороте — недопустимая величина, а расхождение в одну строку вызовет разбирательство. Приближения уместны в исследовании, мониторинге, оценке размера сегмента перед запуском — везде, где решение не изменится от сдвига на процент.