SQL и MapReduce: новые возможности или латание старых дыр?

Сергей Кузнецов

Эта заметка возникла в связи с переводом статьи Эрика Фридмана (Eric Friedman) и др. «SQL/MapReduce: практический подход к поддержке самоописываемых, полиморфных и параллелизуемых функций, определяемых пользователями». Сначала я, как обычно, хотел написать небольшое предисловие к своему переводу статьи, но затем у меня возникло сильное желание прокомментировать один из ее подразделов, а размер этого комментария явно превышал допустимые размеры комментариев, которые уместно помещать в сносках. Поэтому я решил сделать отдельную заметку, а на нее уже сослаться из текста перевода.

Сначала я коротко расскажу о том, почему я решил перевести статью Эрика Фридмана и др., и что я в ней считаю особенно интересным. На самом деле, желание разобраться с подходом компании Asterdata к интеграции подходов SQL и MapReduce для управления аналитическими базами данных возникло у меня после знакомства с подходом компании Greenplum, переводом статьи Джеффри Коэна (Jeffrey Cohen) и др. «МОГучие способности: новые приемы анализа больших данных», нескольких выступлений на семинарах и конференциях и написания собственной статьи «Год эпохи перемен в технологии баз данных».

Напомню, что в Greenplum подход MapReduce интегрируется в среду массивно-параллельной SQL-ориентированной системы баз данных, прежде всего, для того, чтобы у аналитиков имелась возможность в процедурном стиле создавать на стороне сервера баз данных новые параллельные аналитические приложения на разных языках программирования. Насколько я понимаю, в случае Greenplum в руки разработчиков серверных аналитических приложений даются средства MapReduce в чистом виде, а сами эти средства реализуются за счет использования механизмов расширения функциональности СУБД Postgres. Следует отметить, что при этом одной из проблем своей параллельной СУБД разработчики Greenplum считают трудности распараллеливания определяемых пользователями функций (user-defined function, UDF) среды SQL.

Авторы статьи «SQL/MapReduce: практический подход к поддержке самоописываемых, полиморфных и параллелизуемых функций, определяемых пользователями», как, собственно, следует из ее названия, подходят к делу с другой стороны. На основе применения духа (а не буквы) парадигмы MapReduce они предлагают механизм реализации определяемых пользователями функций (более точно, табличных функций, т.е. функций, основным аргументом и значением которых являются таблицы), параллельность выполнения которых предполагается по умолчанию.

Не буду здесь распространяться об интересных особенностях самоописания и динамического полиморфизма SQL/MR-функций. Чтобы с этим разобраться, нужно внимательно читать основную статью. Замечу лишь, что эти особенности способствуют повторному использованию UDF, допускают динамическую оптимизацию запросов, в которых используются вызовы таких функций, и т.д.

Авторы демонстрируют ряд практических задач, решение которых средствами чистого SQL затруднительно (или вообще невозможно), а применение SQL/MR-функций упрощает решение и приводит к существенному выигрышу в производительности.

В статье все хорошо и убедительно говорится вплоть до подраздела 6.2, который убедительным мне не кажется, и по поводу которого и затеяна эта заметка. Кратко перескажу суть задачи, обсуждаемой в этом подразделе. Имеется таблица Clicks(user_id int, page_id int), каждая строка которой соответствует обращению пользователя с идентификатором user_id к Web-странице с идентификтором page_id. Задается n множеств идетификаторов страниц SET1,..., SETn (в статье они называется поисковыми наборами). Требуется найти идентификаторы всех пользователей, которые обращались ко всем страницам, идентификаторы которых содержатся хотя бы в одном из множеств SETi (1 ≤ i ≤ n).

Авторы не приводят текст своего SQL-запроса, решающего эту задачу, поскольку у них он получился слишком объемным, но приводят его основую идею (которая мне кажется ужасной!). Пусть имеется только один поисковый набор SET1, и пусть он содержит k₁ идентификаторов страниц. Тогда в запросе сначала выполняется k₁ соединений таблицы Clicks по user_id, а полученные кортежи сравниваются с кортежем, представляющим (в некотором порядке) все идентификаторы страниц из SET1.

Понятно, что такой запрос выдаст правильный результат, но сначала будет произведено множество лишних кортежей, а затем выполнено множество лишних сравнений. Конечно, такой запрос будет выполняться очень долго и примет совсем страшный вид, если задается несколько поисковых наборов разного размера. Поэтому сравнивать время выполнения такого запроса со временем выполнения разумно написанной SQL/MR-функции, как минимум, некорректно.

Хотя авторы считают свой запрос "наиболее оптимизированным", мне достаточно быстро пришла в голову формулировка (с небольшими вольностями), которая, совершенно очевидно, может привести к существенному убыстрению времени выполнения. Вот она:

(SELECT 'SET1', user_id
FROM Clicks
WHERE page_id IN SET1
GROUP BY user_id
HAVING COUNT(DISTINCT page_id) = k1)
UNION
...
UNION
(SELECT 'SETn', user_id
FROM Clicks
WHERE page_id IN SETn
GROUP BY user_id
HAVING COUNT(DISTINCT page_id) = kn)

Это тоже не очень хороший запрос, поскольку при наличии n поисковых наборов потребуется n раз выполнять однотипные действия над таблицей Clicks. Но здесь, по крайней мере, нет соединений, и каждый подзапрос может быть выполнен достаточно эффективно. (Кстати, в качестве дополнительного преимущества приведенный запрос для каждого результирующего user_id выдает номер поискового набора, которому он удовлетворяет.)

Почему же не удается написать SQL-запрос, при выполнении которого выполнялись бы такие же естественные действия, которые выполяются при наличии определяемой авторами SQL/MR-функции? Ответ очень прост: это связано с тем, что в современном стандарте SQL нет условия, проверяющего вхождение одного множества в другое. Можно многими способами проверить вхождение в таблицу некоторой строки, а проверить вхождение одной таблицы в другую – нельзя.

Самое смешное, что на заре SQL в середине 1970-х гг. такая возможность имелась (см. например, статью Дона Чемберлина (D.D. Chamberlin) и др. «SEQUEL 2: унифицированный подход к определению, манипулированию и контролю данных». В этом варианте SQL имелся предикат CONTAINS, служащий именно для проверки вхождения одного множества кортежей в другое множество (или мультимножество). С использованием этого предиката (и операции SET, позволяющей образовать множество значений заданного столбца в группе строк таблицы) нужный нам запрос можно было бы сформулировать (немного неформально) следующим лаконочным образом:

SELECT user_id
FROM Clicks
GROUP BY user_id
HAVING SET(page_id) CONTAINS SET1
    OR SET(page_id) CONTAINS SET2
    ...
    OR SET(page_id) CONTAINS SETn;

Легко заметить, что естественным способом обработки такого запроса в массивно-параллельной среде было бы разделение таблицы Clicks по значениям столбца user_id и выполнение за один проход всех проверок, т.е. ровно то же, что делается при выполнении SQL/MR-функции из подраздела 6.2 статьи «SQL/MapReduce: практический подход к поддержке самоописываемых, полиморфных и параллелизуемых функций, определяемых пользователями». Кроме того, развитый оптимизатор запросов оценил бы и другие возможные способы выполнения этого запроса и выбрал бы из них действительно оптимальный способ при текущем состоянии базы данных, а не тот, который почему-то нравится (или навязывается?) пользователю.

Мораль моей заметки в том, что, безусловно, сообщество баз данных должно смотреть по сторонам и заимствовать полезные подходы, возникшие в смежных областях. Однако стоит ли использовать чужие идеи для латания известных технологических дыр, с которыми можно справиться собственными силами?