TABLESAMPLE SYSTEM и LIMIT: выборка, которая не видит конец таблицы

Нам нужно было дёшево оценить, какая доля строк большой таблицы обладает некоторым свойством. В нашем случае свойство — «значение похоже на персональные данные», но задача общая: профилирование данных, проверки качества, любая статистика по колонке. Читать таблицу на миллиард строк целиком ради одной доли дорого, и в PostgreSQL для этого есть TABLESAMPLE SYSTEM: он читает только часть страниц.

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

Рецепт

Хотим около N строк. Оценка числа строк есть в pg_class.reltuples, поэтому процент страниц считается так:

p = 100 × N × c / reltuples

Здесь c — запас. SYSTEM возвращает страницы целиком, и число строк в выборке гуляет, поэтому без запаса часто получается недобор. С запасом строк, наоборот, бывает больше, чем нужно, и лишнее отрезают LIMIT. Для N = 20 000, c = 1,2 и таблицы на миллион строк:

SELECT id, email
FROM big_table TABLESAMPLE SYSTEM (2.4)
LIMIT 20000;

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

Как SYSTEM выбирает страницы

Метод SYSTEM устроен просто (system.c в исходниках PostgreSQL). Он перебирает номера блоков таблицы от нулевого по возрастанию. Для каждого блока считается хеш от номера блока и зерна выборки, и блок берётся, если хеш меньше порога, пропорционального p. Из взятого блока возвращаются все строки.

для блока от 0 до nblocks − 1:

если hash(блок, зерно) < p / 100 × 2³²:

вернуть все строки блока

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

Где ломается LIMIT

LIMIT забирает строки из сканирования выборки, пока не наберёт N, и останавливает его. Блоки идут по возрастанию номера, поэтому до конца файла сканирование не доходит. Выборка с запасом c в среднем содержит c·N строк, и LIMIT N обрывает чтение примерно на доле 1/c таблицы:

В таблице, куда в основном добавляют строки, конец кучи — это самые свежие данные. Выборка, которую писали, чтобы не смотреть на одни старые строки, как делает «первые N строк», теперь систематически не видит новые. После UPDATE и VACUUM новые версии строк попадают и в освободившееся место в середине таблицы, так что «конец кучи» и «свежее» совпадают не всегда, но для таблиц журналов, заказов и событий — почти всегда.

Иногда выборка выходит с недобором, тогда LIMIT не срабатывает и таблица дочитывается до конца. Поэтому смещение не детерминированное: в части запусков хвост всё-таки попадает в выборку, и проблему легко не заметить.

Устаревшая статистика делает хуже

reltuples обновляют VACUUM и ANALYZE. Если таблица выросла с последнего обновления, процент посчитан для старого размера, выборка содержит больше строк, чем нужно, и LIMIT обрывает чтение ещё раньше — примерно на доле 1/(c·g), где g — во сколько раз таблица выросла. Если таблица удвоилась, а запас 1,2, выборка видит около 42% таблицы, то есть всю новую половину не видит вообще.

Сам планировщик PostgreSQL сырой reltuples не использует: он берёт плотность строк на страницу (reltuples / relpages) и умножает на текущее число страниц файла. С PostgreSQL 14 у таблицы, которую ни разу не анализировали, reltuples равен −1, а в более старых версиях — 0. Обе ситуации нужно обрабатывать отдельно, иначе процент получится отрицательным или с делением на ноль.

Эксперимент

PostgreSQL 17.9. Таблица на миллион строк: id, email и строка-заполнитель на 40 символов. Почта заполнена только у последних 10% строк (id > 900000), то есть только в хвосте кучи. После ANALYZE получилось p = 2,4%, N = 20 000. Каждый вариант запускали 200 раз.

CREATE TABLE t (id bigint, email text, pad text) WITH (autovacuum_enabled = false);
INSERT INTO t
SELECT g, CASE WHEN g > 900000 THEN 'user' || g || '@example.com' END, repeat('x', 40)
FROM generate_series(1, 1000000) g;
ANALYZE t;

-- 1. LIMIT поверх выборки
SELECT count(email)::numeric / count(*) AS share, max(id)
FROM (SELECT * FROM t TABLESAMPLE SYSTEM (2.4) LIMIT 20000) s;

-- 2. сначала перемешать, потом LIMIT
SELECT count(email)::numeric / count(*) AS share, max(id)
FROM (SELECT * FROM (SELECT * FROM t TABLESAMPLE SYSTEM (2.4)) x
      ORDER BY random() LIMIT 20000) s;

-- 3. SYSTEM_ROWS из расширения tsm_system_rows
SELECT count(email)::numeric / count(*) AS share, max(id)
FROM (SELECT * FROM t TABLESAMPLE SYSTEM_ROWS (20000)) s;

Истинная доля почты — 10%.

Выборка с LIMIT дочитывает в среднем до 84-го процента таблицы. В 174 запусках из 200 она не нашла ни одной почты, а там, где нашла, почта попала в выборку из-за недобора строк.

Второй сценарий — таблица выросла после ANALYZE. Добавили ещё миллион строк, и у всех новых строк почта заполнена: например, приложение начало её сохранять. Статистику не обновляли (автоочистка на таблице выключена), истинная доля стала 55%. Новые строки с почтой длиннее, поэтому страниц стало в 2,27 раза больше, а не в два.

По старой статистике выборка ни разу не дошла до новой половины таблицы: средний max(id) — около 838 000, то есть чтение обрывалось ещё в старой части.

Как чинить

Перемешать выборку перед LIMIT. Подзапрос читает всю выборку, около c·N строк, сортирует её случайно и отдаёт N:

SELECT *
FROM (SELECT id, email FROM big_table TABLESAMPLE SYSTEM (2.4)) s
ORDER BY random()
LIMIT 20000;

Чтение остаётся тем же — те же c·N строк, — но добавляется сортировка. У нас на таблице в миллион строк (N = 20 000, 20 текстовых колонок, тёплый кеш) запрос вырос с 25–41 до 52–66 мс. При work_mem по умолчанию (4 МБ) и широких строках сортировка уходит на диск — около 16 МБ временного файла на 20 колонок. Помогает выбирать только нужные колонки или поднять work_mem для этой сессии.

Не ставить LIMIT вовсе. Взять всю выборку — около c·N строк с разбросом — и считать доли от фактического числа прочитанных строк. Это самый простой и дешёвый вариант, если коду не нужно ровно N строк.

Использовать SYSTEM_ROWS. Расширение tsm_system_rows добавляет метод, который сам останавливается на N строках, но перебирает блоки не по порядку: начинает со случайного блока и шагает со случайным шагом, взаимно простым с числом блоков. В среднем в нашем эксперименте он не хуже перемешивания, но у него есть оговорки. Нужен CREATE EXTENSION, а при доступе к чужой базе только на чтение это недоступно. REPEATABLE не гарантирует одинаковый результат между запросами. И изредка выборка получается кучной: в наших 200 запусках один раз вышло 0% почты и один раз 100%, когда при неудачном шаге первые блоки легли рядом.

Считать процент от текущего размера таблицы. Как это делает планировщик:

SELECT reltuples / NULLIF(relpages, 0)
* (pg_relation_size(oid) / current_setting('block_size')::int) AS rows_now
FROM pg_class
WHERE oid = 'big_table'::regclass;

pg_relation_size читает размер файла и ничего не стоит. Если reltuples не больше нуля, таблицу не анализировали, и процент считать не из чего: нужен запасной путь, например чтение первых строк с предупреждением или ANALYZE.

SQL Server. Там похожая конструкция — TOP (N) поверх TABLESAMPLE (p PERCENT), и TOP тоже останавливает чтение, как только набрал строки. Мы перемешиваем и там: SELECT TOP (N) … TABLESAMPLE (p PERCENT) ORDER BY NEWID(). Устаревшей статистики там нет: row_count в sys.dm_db_partition_stats поддерживается актуальным.

Как это поймать тестом

Смещение не видно на равномерных данных: если признак размазан по таблице, обрезанная выборка даёт ту же долю. Поэтому тест должен класть признак только в конец кучи и проверять оценку. У нас такой тест (N = 1000) на старом коде падал в обоих сценариях. Когда почта лежала только в последних 20% таблицы, в прочитанных строках её оказалось 2,4% вместо 20%: оценка 115 строк вместо 960. После удвоения таблицы без ANALYZE выборка не нашла ни одной почты.

Отдельно стоит помнить про блочную природу SYSTEM. Строки одной страницы похожи друг на друга, и если редкие значения сгруппированы по страницам — например, загружены одной пачкой, — оценка доли шумит сильнее, чем у построчной выборки того же размера. Запас c от этого не спасает, он только про число строк. Если нужна гарантия, а не оценка, таблицу придётся прочитать целиком.

Итого

• TABLESAMPLE SYSTEM (p) LIMIT N — это не «N случайных строк», а «первые N строк случайного набора страниц в физическом порядке».

• С запасом c такая выборка в среднем не видит последнюю долю 1 − 1/c таблицы, а при устаревшей статистике — ещё больше.

• В таблицах, куда добавляют строки, это самые свежие данные.

• Лечится перемешиванием выборки перед LIMIT, отказом от LIMIT или SYSTEM_ROWS с его оговорками.

• Процент страниц стоит считать от текущего размера файла, как планировщик, а не от сырого reltuples.

• Тест на это смещение — признак только в хвосте таблицы.

Если вы считаете статистику по большим таблицам выборками, проверьте, нет ли у вас LIMIT поверх TABLESAMPLE

Ссылки

• Документация PostgreSQL: SELECT, раздел про TABLESAMPLE

• Исходный код метода SYSTEM: src/backend/access/tablesample/system.c

• Документация tsm_system_rows

• Документация SQL Server: предложение FROM и TABLESAMPLE