Как мы запрос в 100 раз ускоряли, или не все хеш-функции одинаково плохи
4 мин
Мы разрабатываем базу данных. Однажны к нам обратилась компания, которая столкнулась со следующей задачей:
Есть некоторое множество объектов, и некоторое множество тегов. Каждый объект может содержать несколько тегов. Какие-то теги очень редкие, а какие-то встречаются часто. Одному объекту один тег может быть сопоставлен несколько раз.
Новые объекты, теги и связи между ними непрерывно добавляются.
Задача — очень быстро отвечать на вопросы вида: «сколько есть объектов, у которых есть тег А или B, но нету тега С» и похожие. На такие запросы хотелось бы отвечать за десятые доли секунды, при этом не останавливая загрузку данных.
Мы получили от них их данные вплоть до сегодняшнего дня, развернули тестовый кластер из четырех машин, и начали думать, как правильно распределить данные и как правильно представить задачу в виде SQL-запроса, чтобы получить максимальную производительность. В итоге решили, что запрос может иметь вид:
Чтобы такой запрос выполнялся быстро, мы разбили данные между серверами кластера по object_id, а внутри каждого сервера отсортировали их по тегам. Таким образом сервер, выполняющий запрос, может отправить запрос без изменений на все сервера с данными, а затем просто сложить их результаты. На каждом сервере с данными для выполнения запроса достаточно найти строки для тегов A, B и C (а так как данные по тегу отсортированы, это быстрая операция), после чего выполнить запрос за один проход по этим строкам. Худший тег имеет несколько десятков миллионов объектов, несколько десятков миллионов строк обработать за десятые доли секунды видится возможным.
Стоит отметить, что подзапрос содержит GROUP BY object_id. GROUP BY в данной ситуации можно выполнить несколькими способами, например, если данные после тега отсортированы по object_id, то можно выполнить что-то похожее на merge sort. В данной ситуации, однако, мы данные по object_id не отсортировали, и оптимизатор разумно решил, что для выполнения GROUP BY надо построить хеш-таблицу.
Мы загрузили все данные в кластер, и запустили запрос. Запрос занял 25 секунд.
Есть некоторое множество объектов, и некоторое множество тегов. Каждый объект может содержать несколько тегов. Какие-то теги очень редкие, а какие-то встречаются часто. Одному объекту один тег может быть сопоставлен несколько раз.
Новые объекты, теги и связи между ними непрерывно добавляются.
Задача — очень быстро отвечать на вопросы вида: «сколько есть объектов, у которых есть тег А или B, но нету тега С» и похожие. На такие запросы хотелось бы отвечать за десятые доли секунды, при этом не останавливая загрузку данных.
Мы получили от них их данные вплоть до сегодняшнего дня, развернули тестовый кластер из четырех машин, и начали думать, как правильно распределить данные и как правильно представить задачу в виде SQL-запроса, чтобы получить максимальную производительность. В итоге решили, что запрос может иметь вид:
SELECT
COUNT(*)
FROM (
SELECT
object_id,
(MAX(tag == A) OR MAX(tag == B)) AND MIN(tag != C) AS good
FROM tags
WHERE tag IN (A, B, C)
GROUP BY object_id
) WHERE good == 1;
Чтобы такой запрос выполнялся быстро, мы разбили данные между серверами кластера по object_id, а внутри каждого сервера отсортировали их по тегам. Таким образом сервер, выполняющий запрос, может отправить запрос без изменений на все сервера с данными, а затем просто сложить их результаты. На каждом сервере с данными для выполнения запроса достаточно найти строки для тегов A, B и C (а так как данные по тегу отсортированы, это быстрая операция), после чего выполнить запрос за один проход по этим строкам. Худший тег имеет несколько десятков миллионов объектов, несколько десятков миллионов строк обработать за десятые доли секунды видится возможным.
Стоит отметить, что подзапрос содержит GROUP BY object_id. GROUP BY в данной ситуации можно выполнить несколькими способами, например, если данные после тега отсортированы по object_id, то можно выполнить что-то похожее на merge sort. В данной ситуации, однако, мы данные по object_id не отсортировали, и оптимизатор разумно решил, что для выполнения GROUP BY надо построить хеш-таблицу.
Мы загрузили все данные в кластер, и запустили запрос. Запрос занял 25 секунд.
В обязанности администратора баз данных входит много разных задач, которые, в основном, направлены на поддержку работоспособности и целостности базы данных. И если целостность данных можно проверить через команду CHECKDB, то с поиском невалидных объектов в схеме не все так гладко.
Иногда в своих проектах мне хотелось прикрутить некоторую географическую базу, с помощью которой я бы разделял пользователей ресурса по их месту пребывания. Но постоянная занятость делами насущными никак не давала реализовать идею с базой регионов и мало-мальски удобным интерфейсом для ее визуализации.
В данном топике хотелось бы поговорить о повышении производительности при работе с таблицами.
В предыдущем посте была 
Основная цель, преследуемая в ходе разработки физической модели данных, — создание таких объектов для конкретной платформы/СУБД, которые позволят достигнуть максимальной производительности запросов/приложений, создающих основную нагрузку, сведя при этом дополнительные затраты, такие как необходимость поддерживать дополнительные индексы, выполнять материализацию производных данных и т. п., к минимуму.