Про разные варианты одного запроса

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

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

Нам предстоит работать с таблицей person из примерно 300 тысяч строк следующего вида:

id	first_name	middle_name	last_name	mother_id	father_id
Уникальный идентификатор человека	Имя	Отчество	Фамилия	Ссылка на id матери в этой же таблице (person)	Ссылка на id отца в этой же таблице (person)

Задача довольно тривиальная — необходимо подсчитать количество детей у каждого человека. То есть на выходе требуется таблица вида:

id	first_name	middle_name	last_name	child_cnt
Уникальный идентификатор человека	Имя	Отчество	Фамилия	Количество детей у указанного человека

Самый тривиальный вариант, который обычно пишут новички в SQL содержит подзапрос в списке столбцов:

1. SELECT p.id,
2.        p.last_name,
3.        p.first_name,
4.        p.middle_name,
5.        (
6.            SELECT COUNT(*) AS child_cnt
7.            FROM dbo.person pp
8.            WHERE pp.father_id = p.id
9.                  OR pp.mother_id = p.id
10.        ) AS child_cnt
11. FROM dbo.person p
12. ORDER BY p.id;

Надеюсь, вы понимаете в чём проблема этого запроса. Для каждой(!) строки результирующей выборки (а их 300 тысяч) будет выполнен подзапрос с подсчётом количества детей. Суммарная стоимость этого варианта составляет 178230. Что касается времени выполнения, то я так и не дождался результата, поэтому условно будем считать час (на самом деле намного больше).

Казалось бы очевидным улучшением является подсчёт количества детей с помощью соединения таблицы с собой:

1. SELECT p.id,
2.        COUNT(p2.father_id)+COUNT(p2.mother_id) AS child_cnt
3. FROM dbo.person p
4.     LEFT JOIN dbo.person p2
5.         ON p2.father_id = p.id
6.            OR p2.mother_id = p.id
7. GROUP BY p.id;

Но оптимизатор так не считает. Оценка этого варианта 455435, а в плане виден ненавистный спулинг.

Тем не менее если мы заменим left join на inner join, мы получим список только тех людей, у кого есть хотя бы один ребёнок, но зато с оценкой в ~64.

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

1. SELECT p.id,
2.        p.last_name,
3.        p.first_name,
4.        p.middle_name,
5.        COALESCE(r.child_cnt, 0) AS child_cnt
6. FROM dbo.person p
7.     LEFT JOIN
8.     (
9.         SELECT p.id,
10.                COUNT(*) AS child_cnt
11.         FROM dbo.person p
12.             INNER JOIN dbo.person p2
13.                 ON p2.father_id = p.id
14.                    OR p2.mother_id = p.id
15.         GROUP BY p.id
16.     ) r
17.         ON p.id = r.id;

Время выполнения этого запроса девять секунд. В принципе, на этом можно было бы остановиться, но ради спортивного интереса продолжим.

Очевидно, что идея подсчитать количество детей для тех, у кого они есть, а потом дополнить этот список оставшимися людьми довольно эффективная. Так как «обёртка»-дополнение во всех случаях будет одинаковой , сосредоточимся на подсчёте детей у тех, у кого они есть.

1. SELECT p.id,
2.        COUNT(*) AS child_cnt
3. FROM dbo.person p
4.     INNER JOIN dbo.person p2
5.         ON p2.father_id = p.id
6. GROUP BY p.id
7. UNION ALL
8. SELECT p.id,
9.        COUNT(*) AS child_cnt
10. FROM dbo.person p
11.     INNER JOIN dbo.person p2
12.         ON p2.mother_id = p.id
13. GROUP BY p.id;

В этом варианте запроса с оценкой ~15, мы избавляемся от сложного оператора OR в join. Вместо этого мы подсчитываем у скольких людей конкретная персона является отцом, аналогично считаем у скольких людей она является матерью, а результаты просто объединяем.

Но на самом деле можно поступить ещё проще. Нам нет необходимости проверять каждую персону на наличие детей. Мы можем просто посчитать сколько раз каждый человек появлялся в столбцах mother_id / father_id и таким образом получить искомое количество детей.

1. SELECT r.parent_id,
2.        COUNT(*) AS child_cnt
3. FROM
4. (
5.     SELECT mother_id AS parent_id
6.     FROM dbo.person
7.     WHERE (1 = 1)
8.           AND (mother_id IS NOT NULL)
9.     UNION ALL
10.     SELECT father_id
11.     FROM dbo.person
12.     WHERE (1 = 1)
13.           AND (father_id IS NOT NULL)
14. ) r
15. GROUP BY r.parent_id;

С оценкой ~5 мы считаем требуемые данные всего за одну секунду.

Разумеется, как я сказал ещё в самом начале, гораздо проще было бы ускорить этот запрос, просто добавив индекс. Но разве не здорово просто переформулировав то, что ты хочешь получить от сервера, добиться ускорения в сотни раз?

—

Уже после публикации этой записи мне пришла в голову ещё одна идея. Очевидно, что использование OR в подзапросе существенно замедляет его. Что если оставить подзапрос в SELECT, но при этом разбить его на две части?

1. SELECT p.id,
2.        p.last_name,
3.        p.first_name,
4.        p.middle_name,
5.        (
6.            SELECT COUNT(*) AS child_cnt
7.            FROM dbo.person pp
8.            WHERE pp.father_id = p.id
9.        ) +
10.        (
11.            SELECT COUNT(*) AS child_cnt
12.            FROM dbo.person pp
13.            WHERE pp.mother_id = p.id
14.        ) AS child_cnt
15. FROM dbo.person p
16. ORDER BY p.id;

Мы видим, что при таком запросе оптимизатор догадался сначала сгруппировать данные по матерям и отцам, а потом собрать итоговую таблицу используя быстрый MERGE JOIN.

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