Как заставить PostgreSQL считать быстрее
Все умеют считать, но не все умеют считать быстро. В этой статье мы подробно рассмотрим методы оптимизации count в PostgreSQL. Существуют приемы, которые могут позволить ускорить подсчет количества строк на порядки.
Если подходить к вопросу со всей серьезностью, необходимо выделить несколько вариантов count, у каждого из которых есть собственные методы. С чем нужно будет определиться:
Мы проанализируем решения для каждой конкретной ситуации, а также сравним их скорость и потребление ресурсов. Разобрав ситуацию с централизованной БД, мы воспользуемся Citus, чтобы продемонстрировать параллельное выполнение count в распределенной базе данных.
Содержание
Подготовка БД
Для тестов мы будем использовать базу данных под названием count, для которой инициализирован pgbench:
Создадим тестовую таблицу:
Count с дубликатами
Точный подсчет
Pgbench — удобный инструмент для многократного выполнения запроса и сбора статистики о производительности.
Предыдущий тест с count(1) выдал следующие результаты:
На scan приходится 88% стоимости запроса. Если удвоить размер таблицы, то и время выполнения запроса увеличится примерно в два раза при пропорциональном росте стоимости scan и aggregate.
| Количество строк | Среднее время |
|---|---|
| 1 млн | 85 мс |
| 2 млн | 161 мс |
| 4 млн | 343 мс |
Как это ускорить? Есть два варианта: решить, что нам достаточно оценочного значения, либо самостоятельно помещать в кеш количество строк. Во втором случае нам придется отдельно хранить значения для каждой таблицы и каждого выражения WHERE, для которых мы хотим быстро выполнять count.
Давайте рассмотрим пример ручного кеширования значения count(*) для таблицы items целиком. Следующее основанное на триггерах решение является адаптацией метода, предложенного A. Elein Mustain. Механизм MVCC PostgreSQL будет поддерживать согласованность между items и таблицей, содержащей значения количества строк.
Скорость чтения и обновления кешированных значений в этом случае не зависит от размера таблицы, и получение значения количества строк выполняется очень быстро. Однако эта техника увеличивает накладные расходы на операции вставки и удаления. Без триггера следующая команда выполняется 4,7 секунды, когда как вставка с триггером в пятьдесят раз медленнее:
Оценка
Оценка по всей таблице
Подход, при котором мы кешируем количество строк таблицы, замедляет операции вставки. Если вместо точного числа мы готовы довольствоваться оценочным значением, то есть возможность получить быстрые операции чтения без ухудшения времени работы вставки. Для этого мы можем использовать собираемые PostgreSQL служебные данные. Их источниками являются stats collector и autovacuum daemon.
Варианты получения оценочных значений:
Но есть и более надежный источник, данные в котором обновляются чаще. Andrew Gierth (RhodiumToad) советует:
Помните: планировщик на самом деле не использует reltuples; он умножает отношение reltuples/relpages на текущее количество страниц.
Логика здесь следующая: по мере увеличения объема данных в таблице среднее количество строк, умещающихся в физическую страницу, в общем случае будет меняться не так сильно, как их общее количество. Чтобы получить более точную оценку текущего количества строк, мы можем умножить среднее количество строк на актуальную информацию о текущем количестве занимаемых таблицей страниц.
Оценка для выборки
В предыдущем разделе мы рассмотрели получение оценочного количества строк для целой таблицы, а можно ли сделать то же самое, но только для подходящих под условие WHERE строк? Michael Fuhr придумал интересный способ: запустить EXPLAIN для запроса и проанализировать полученный результат.
Эту функцию можно использовать следующим образом:
Distinct сount (без дубликатов)
Точный подсчет
Поведение по умолчанию при нехватке памяти
Count с дубликатами может выполняться медленно, но count distinct намного хуже. С ограниченной рабочей памятью и без индексов PostgreSQL не способна выполнять оптимизацию эффективно. В конфигурации по умолчанию СУБД накладывает жесткий лимит на каждый параллельный запрос ( work_mem ). На компьютере, который я использую для разработки, это значение по умолчанию было установлено в 4 мегабайта.
Запуск EXPLAIN показывает, что большая часть времени выполнения запроса ушла на агрегирование. Также отметим, что подсчет количества строк по колонке типа text ведется намного медленнее, чем по целочисленной:
Специализированное агрегирование
Для подсчета количества уникальных значений Thomas Vondra создал специализированный метод агрегирования, работающий с типами ограниченной длины (не должна превышать 64 бита). Этот способ даже без увеличения рабочей памяти или создания индексов оказывается быстрее используемого по умолчанию метода, основанного на сортировке. Для установки выполните следующие шаги:
В этой статье Томас объясняет, как работает агрегирование. Коротко скажу лишь, что его метод создает в памяти отсортированный массив уникальных элементов, уплотняя его в процессе.
Это работает быстрее стандартного count distinct, который на наших тестовых данных выполняется в среднем 742 мс. Следует учитывать, что написанные на C расширения, такие как count_distinct, не ограничены параметром work_mem, поэтому созданный в процессе массив может занять больше памяти в расчете на соединение, чем вы изначально планировали.
HashAggregate
Если все пересчитываемые столбцы умещаются в work_mem, для получения уникальных значений PostgreSQL применит хеш-таблицу:
Будьте осторожны: установка высокого лимита рабочей памяти может привести к неприятным последствиям, так как work_mem относится к каждому параллельному запросу. Кроме того, мы можем придумать и кое-что получше.
Index-Only Scan
Эта возможность появилась в PostgreSQL 9.2. Если индекс содержит все необходимые для запроса данные, система может использовать только его, не трогая саму таблицу (“the heap”). Тип индекса должен поддерживать index-only scan (например, btree). Индексы GiST и SP-GiST поддерживают index-only scan лишь для некоторых классов операторов.
Создадим по btree-индексу для колонок n и s :
Для выбора уникальных значений из этих колонок теперь используется другая стратегия:
Но тут мы наталкиваемся на странную проблему: SELECT COUNT(DISTINCT n) FROM items не станет использовать индекс, несмотря на то что SELECT DISTINCT n делает это по умолчанию. Следуя советам в блогах («Трюк, который ускорит ваш postgres в 50x раз!»), можно дать подсказку планировщику, переписав count distinct в виде count по подзапросу:
Симметричный (in-order) обход бинарного дерева выполняется быстро. Этот запрос занимает в среднем 177 мс (270 мс для колонки s ).
Оценка
HyperLogLog
Рассмотренные ранее методы зависят от индексов, хеш-таблиц, отсортированных массивов в памяти либо обращаются к статистическим таблицам централизованной базы данных. Когда данных становится по-настоящему много и/или они разделяются между несколькими узлами распределенной базы данных, эти методы перестают нас устраивать.
В этом случае на помощь приходят вероятностные структуры данных, которые способны давать быстрые приблизительные оценки и хорошо распараллеливаются. Давайте испытаем одну из таких структур на count distinct. Рассмотрим механизм оценки количества элементов (cardinality estimator) под названием HyperLogLog (HLL). Для представления набора элементов он использует небольшое количество памяти. Операция объединения в этом механизме работает без потерь, что позволяет объединять произвольные значения HLL, не теряя точности оценки количества.
HLL использует свойства «хороших» хеш-функций, в частности дистанцию между хешированными значениями. Функция, равномерно распределяющая значения, стремится разносить их на максимально возможное расстояние. По мере добавления новых хешей свободного места становится меньше, и элементы начинают прижиматься друг к другу. Анализируя наименьшие расстояния между хешированными значениями, алгоритм может оценить наиболее вероятное количество исходных элементов.
Давайте измерим скорость. Сначала установим расширение для PostgreSQL.
HLL выполняет быстрое агрегирование данных при последовательном сканировании таблиц (sequential scan):
Распараллеливание
Приложения, собирающие аналитику в реальном времени, такие как, например, Google Analytics, активно используют count, и эта операция хорошо распараллеливается. В этом разделе мы измерим производительность нескольких методов подсчета количества строк на базе небольшого кластера Citus, развернутого в Citus Cloud.
Идея в том, чтобы развернуть узлы распределенной базы данных на нескольких машинах. На узлах будет одинаковая схема, и каждый из них будет содержать часть общего набора данных (shard). Подсчет количества строк будет выполняться параллельно, т. е. одновременно на разных машинах.
Настройка кластера
Для теста мы сделаем лишь небольшой кластер, поскольку наша цель — оценить сравнительную производительность, а не получить максимальную скорость.
В Citus Cloud я сделал кластер из восьми машин, выбрав для каждой из них самую слабую из возможных конфигураций. При желании воспроизвести этот пример самостоятельно зарегистрируйтесь вот здесь.
После создания кластера я подключаюсь к координирующей ноде для выполнения SQL-запросов. Первым делом создадим таблицу.
В данный момент таблица существует только в БД координатора. Нам нужно разбить таблицу и разместить ее части на рабочих узлах. Citus приписывает каждую строку к определенному сегменту (shard) путем обработки значений в выбранной нами колонке для распределения (distribution column). В примере ниже мы ставим ему задачу распределить будущие строки в таблице items, используя хеши значений в колонке n для определения принадлежности к тому или иному сегменту.
С помощью координирующей ноды мы загрузим случайные данные в сегменты БД. (Citus также поддерживает MX, режим «без мастера» (masterless mode), который используется для быстрой загрузки данных, но сейчас он нас не интересует).
После получения URL базы данных координатора кластера выполните следующий код на компьютере с быстрым сетевым соединением. (Все генерируемые данные будут передаваться по сети с этой машины, поэтому нужна хорошая скорость.)
В примере с централизованной базой данных мы использовали миллион строк. На этот раз давайте возьмем сто миллионов.
Точный подсчет
С дубликатами
Обычный count (без дубликатов) проблем не доставляет. Координатор выполняет запрос на всех узлах, а затем суммирует результаты. Вывод EXPLAIN показывает план, выбранный на одном из рабочих узлов (“Distributed Query”), и план, выбранный на координаторе (“Master Query”).
Для справки: на нашем кластере этот запрос выполняется 1,2 секунды. Distinct count представляет более серьезную проблему при работе с распределенной БД.
Distinct (без дубликатов)
Трудность в подсчете уникальных значений колонки в распределенной базе данных заключается в том, что дубликаты надо искать на разных узлах. Однако это проблема, если считать значения в колонке для распределения (distribution column). Строки с одинаковыми значениями в этой колонке попадут в один сегмент, что позволит избежать межсегментного дублирования.
Citus знает, что для подсчета уникальных значений в колонке распределения (distribution column) нужно выполнить запрос count distinct на каждом узле и сложить результаты. Наш кластер выполняет эту задачу за 3,4 секунды.
Найти количество уникальных значений в обычной колонке (non-distribution) оказывается более сложной задачей. Логически можно выделить две возможности:
Первый вариант ничем не лучше подсчета в централизованной БД. Фактически это в точности то же самое плюс значительные накладные расходы на передачу данных по сети.
Второй вариант называется «перераспределение» (repartitioning). Идея заключается в том, чтобы, используя колонку для распределения, создать на рабочих узлах временные таблицы. Рабочие узлы посылают друг другу строки для записи во временные таблицы, выполняют запрос и удаляют эти таблицы. У каждой СУБД своя логика реализации перераспределения. Детали этой системы в Citus выходят за рамки данной статьи, поэтому мы не будем в них углубляться.
Оценка без дубликатов
Механизмы оценки мощности, такие как HLL, незаменимы в распределенных базах данных. Они позволяют выполнять подсчет уникальных значений даже по обычным колонкам (non-distribution), создавая при этом лишь небольшую дополнительную нагрузку на сеть. Тип данных HLL имеет небольшой размер в байтах и может быстро пересылаться от рабочих узлов координатору. Поскольку операция объединения в HLL выполняется без потерь, нет необходимости волноваться, что количество сегментов базы может повлиять на точность.
В Citus нет необходимости явно вызывать функции postgresql-hll. Просто установите citus.count_distinct_error_rate в ненулевое значение, и Citus перепишет планы запросов для count distinct с использованием HLL. Например:
Итоги
| Метод | Время/1 млн строк | Точные | Фильтруемые | Уникальные |
|---|---|---|---|---|
| PG Stats | 0,3 мс | — | — | — |
| Парсинг EXPLAIN | 0,3 мс | — | + | — |
| Ручное кеширование | 2 мс (но медленная вставка) | + | — | — |
| count(*) | 85 мс | + | + | — |
| count(1) | 99 мс | + | + | — |
| Index Only Scan | 177 мс | + | + | + |
| HLL | 239 мс | — | + | + |
| HashAgg | 372 мс | + | + | + |
| Custom Agg | 435 мс (колонка 64-bit) | + | + | + |
| Mergesort | 742 мс | + | + | + |
Немного проигрывая index-only scan в централизованной базе данных на таблице с миллионом строк, HyperLogLog (HLL) вырывается вперед на больших объемах данных (> 100 Гб). Этот метод также незаменим в распределенных БД, позволяя получить оценку количества уникальных элементов (distinct count) в реальном времени на огромных объемах данных.
Хитрости count() в SQL
Допустим, есть таблица usr с платежами клиентов, хранящая идентификаторы клинтов и суммы платежей:
ID PRICE 1 1 1 2 1 3 2 1 2 2 2 3
Нужно посчитать, сколько платежей выполнил каждый клиент.
Решение этой задачи очевидно:
ID COUNT 1 3 2 3
Теперь усложним задачу. Помимо количества платежей вообще, посчитаем, сколько было платежей, имеющих некий отличительный признак.
Отличительным признаком может быть что угодно. Допустим, это будет размер платежа. Посчитаем, сколько было платежей, размер которых превышает 1 рубль.
Вот тут решение становится уже не таким очевидным.
Понятно, что тут нам нужна все та же функция count, только считающая не все строки в группе, а те, которые удовлетворяют условию price>1.
Т.е. запрос должен быть типа такого:
Конечно, в таком виде запрос не сработает. Хотя выражение price>1, переданное функции count(), само по себе будет вычислено правильно, на функцию count() результат этого вычисления никак не повлияет.
Дело в том, что count() просто не понимает булевых выражений. Вместо этого функция count() понимает значения NULL.
В общем виде запрос будет выглядеть так:
Напишем это выражение:
Теперь напишем весь запрос целиком:
SELECT id, count(*), count(CASE
WHEN price>1 THEN 1
ELSE NULL
END)
FROM usr
GROUP BY id
COUNT(*)
У меня есть подборка простеньких вопросов, которые я люблю задавать при собеседовании. Например, как посчитать общее число записей к таблице? Вроде бы ничего сложного, но если копнуть глубже, то можно много интересных нюансов рассказать собеседнику.
Давайте начнем с простого… Эти запросы отличаются чем-то друг от друга с точки зрения конечного результата?
Большинство отвечали: «Нет».
Реже старались долее детально формировать ответ: «Запросы вернут идентичный результат, но COUNT вернет значение типа INT, а COUNT_BIG – тип BIGINT».
Если проанализировать план выполнения, то можно заметить различия, которые многие упускают из вида. При использовании COUNT на плане будет операция Compute Scalar:
Если посмотреть в свойства оператора, то мы увидим там:
Это происходит потому, что при вызове COUNT неявно используется COUNT_BIG после чего результат преобразуется в INT.
Не сказал бы, что существенно, но преобразования типов увеличивает нагрузку на процессор. Многие, конечно, могут сказать, что этот оператор ничего не стоит при выполнении, но нужно отметить простой факт – SQL Server очень часто недооценивает Compute Scalar операторы.
Еще я знаю людей, которые любят использовать SUM вместо COUNT:
Такой вариант примерно равнозначен COUNT. Мы также получим лишний Compute Scalar на плане выполнения:
Теперь более детально затронем вопросы производительности.…
Если использовать запросы выше, то чтобы посчитать количество записей SQL Server необходимо выполнить Full Index Scan (или Full Table Scan если таблица является кучей). В любом случае, эти операции далеко не самые быстрые. Лучше всего для получения количества записей использовать системные представления: sys.dm_db_partition_stats или sys.partitions (есть еще sysindexes, но оставлен для обратной совместимости с SQL Server 2000).
Если сравнить планы выполнения, то доступ к системным представлениям менее затратный:
На AdventureWorks преимущество от применения системных представлений явно не проявляется:
Время выполнения на секционированной таблице с 30 миллионами записей:
В случае если нужно проверить наличие записей в таблице, то использование метаданных как было показано выше не даст особых преимуществ…
И на практике будет даже капельку медленнее, поскольку SQL Server генерирует более сложный план выполнения для выборки из метаданных.
Еще интереснее становиться, когда нужно посчитать количество записей по всем таблицам сразу. На практике встречал несколько вариантов, которые можно обобщить.
Вариант #1 с применением недокументированной процедуры, которая курсором обходит все пользовательские таблицы:
Вариант #2 – динамический SQL которые генерирует запросы SELECT COUNT(*):
Вариант #3 – быстрый вариант на каждый день:
Уж очень много я выдал дифирамбов, что системные представления такие хорошие. Однако, при работе с ними нас могут подстерегать «приятные» неожиданности.
Помнится, был такой веселый баг, когда при миграции с SQL Server 2000 на 2005 некоторые системные представления некорректно обновлялись. Особо везучим людям, в таком случае, из метаданных возвращались неверные значения о количестве записей в таблицах. Лечилось это все командой DBCC UPDATEUSAGE.
Вместе с SQL Server 2005 SP1 этот баг исправили и все бы ничего… Но подобную ситуацию я наблюдал еще один раз, когда восстановил бекап с SQL Server 2005 SP4 на SQL Server 2012 SP2. Воспроизвести проблему на реальном окружении увы не смогу, поэтому немного обманув оптимизатор:
расскажу на простом примере.
Самый безобидный запрос начал выполняться дольше чем обычно:
Посмотрел на план запроса и увидел там явно неадекватное значение Estimated number of rows:
Заглянул в статистику по кластерному индексу:
Но в системных представления о которых мы говорили ранее:
В запросе не было предикатов для фильтрации и оптимизатор выбрал Full Index Scan. При Full Index/Table Scan ожидаемое количество строк оптимизатор не берет из статистики, а обращается к метаданным (точно не уверен всегда ли это происходит).
Не секрет, что на основе Estimated number of rows SQL Server генерирует план выполнения и вычисляет сколько нужно памяти чтобы его выполнить. Если оценка будет неверной, то может быть выделено больше памяти на выполнение запроса, чем нужно на самом деле.
Вот к чему приводит неверная оценка количества строк:
Проблема решилась достаточно просто:
После рекомпиляции запроса все пришло в норму:
Если системные представления уже не кажутся «спасительной палочкой», то какие варианты у нас остаются? Можно делать все по-старинке:
Но при интенсивной вставке в таблицу я бы не доверял результатам. «Волшебный» хинт NOLOCK тем более не гарантирует правильного значения:
По сути, чтобы получить правильное значение количества строк в таблице, нужно выполнять запрос под уровнем изоляции SERIALIZABLE либо используя хинт TABLOCKX:
И что мы получаем в итоге… монопольную блокировку таблицы на период выполнении запроса. И тут каждый должен решать сам, что ему лучше использовать. Мой выбор — метаданные.
Еще интереснее, когда нужно быстро подсчитать число строк по условию:
Если в таблице не происходят частые операции вставки-удаления, то можно создать индексированное представление:
Для этих запросов оптимизатор будет генерировать идентичный план на основе кластерного индекса вьюхи:
План выполнения с индексным представлением и без:
Этим постом я хотел показать, что идеальных решений на все случаи жизни не бывает. И в каждом конкретной ситуации нужно действовать с индивидуальным подходом.
Все тестировалось на SQL Server 2012 SP3 (11.00.6020).
В качестве выводов… Когда нужно подсчитать общее число строк по таблице, то я использую метаданные — это самый быстрый способ. И пусть Вас не пугает ситуация с старым багом, который я привел выше.
Если нужно быстро подсчитать количество строк в разрезе какого-то поля или по условию — то я стараюсь использовать индексированные представления либо фильтрованные индексы. Все зависит от ситуации.
Когда таблица маленькая или вопросы с производительностью не стоят так остро, то проще уж действительно по-старинке написать SELECT COUNT(*)…
Если хотите поделиться этой статьей с англоязычной аудиторией:
What is the fastest way to calculate the record COUNT?