Мы разрабатываем базу данных. Однажны к нам обратилась компания, которая столкнулась со следующей задачей:
Есть некоторое множество объектов, и некоторое множество тегов. Каждый объект может содержать несколько тегов. Какие-то теги очень редкие, а какие-то встречаются часто. Одному объекту один тег может быть сопоставлен несколько раз.
Новые объекты, теги и связи между ними непрерывно добавляются.
Задача — очень быстро отвечать на вопросы вида: «сколько есть объектов, у которых есть тег А или 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 секунд.
