[an error occurred while processing this directive] [an error occurred while processing this directive]
[an error occurred while processing this directive]
Свободные мысли о свободном софте
[an error occurred while processing this directive]
Logo CitForum CITForum на CD Форумы Газета Море(!) аналитической информации!
[an error occurred while processing this directive]
[an error occurred while processing this directive]
[an error occurred while processing this directive]
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware
[an error occurred while processing this directive] [an error occurred while processing this directive]
[an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive]

15.10.2018

Google
WWW CITForum.ru
[an error occurred while processing this directive]

Новости мира IT:

Архив новостей

[an error occurred while processing this directive] [an error occurred while processing this directive]
[an error occurred while processing this directive]
Пятнадцатая техническая конференция «Корпоративные базы данных-2010»
Москва, 22–23 апреля
С Новым годом!

Генеральный спонсор
Техническая конференция
Корпоративные базы данных – 2008
Москва, 24–25 апреля
При поддержке РФФИ

Спонсор
[an error occurred while processing this directive] [an error occurred while processing this directive]
На правах рекламы
2010 г.

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 ≤ in).

Авторы не приводят текст своего SQL-запроса, решающего эту задачу, поскольку у них он получился слишком объемным, но приводят его основую идею (которая мне кажется ужасной!). Пусть имеется только один поисковый набор SET1, и пусть он содержит k1 идентификаторов страниц. Тогда в запросе сначала выполняется k1 соединений таблицы 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: практический подход к поддержке самоописываемых, полиморфных и параллелизуемых функций, определяемых пользователями». Кроме того, развитый оптимизатор запросов оценил бы и другие возможные способы выполнения этого запроса и выбрал бы из них действительно оптимальный способ при текущем состоянии базы данных, а не тот, который почему-то нравится (или навязывается?) пользователю.

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

[an error occurred while processing this directive]
[an error occurred while processing this directive]
[an error occurred while processing this directive] [an error occurred while processing this directive]

Планирование сроков проекта и вопросы осуществления лидерством проекта рассматриваются на сайте по управлению проектами.

[an error occurred while processing this directive]
[an error occurred while processing this directive]
[an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive]

Размещение рекламы — тел. +7 495 6608306, ICQ 232284597

[an error occurred while processing this directive] [an error occurred while processing this directive]
[an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive]

Редакция рекомендует:

Последние комментарии:

Что мы знаем об iPhone 4G? (7)
16 июля, 20:25

Подписка на новости CITForum.ru

Новые публикации:

7 июля

  • Управление параллелизмом с низкими накладными расходами для разделенных баз данных в основной памяти

  • Рекурсивные запросы в Oracle

  • Жесткий диск WD10EARS с сектором 4 КБ. Подготовка к эксплуатации в Linux.

    Обзоры журнала Computer:

    Газета:

  • Московские пробки - исследование IBM

  • От Osborne до iPad: эволюция портативных компьютеров

    19 мая

  • Прозрачный механизм удаленного обслуживания системных вызовов

  • Система моделирования Grid: реализация и возможности применения

    Газета:

    Майкл Стоунбрейкер:

  • Ошибки в системах баз данных, согласованность "в конечном счете" и теорема CAP

  • Дискуссия по поводу "NoSQL" не имеет никакого отношения к SQL

    29 апреля

  • Материалы конференции "Корпоративные Базы Данных-2010"

  • Разные облики технологии баз данных (отчет о конференции)

    14 апреля

  • MapReduce: внутри, снаружи или сбоку от параллельных СУБД?

  • Научные вызовы технологиям СУБД

    Обзоры журнала Computer:

    31 марта

  • Рационализация согласованности в "облаках": не платите за то, что вам не требуется

  • Взаимные блокировки в Oracle

  • Архитектура среды тестирования на основе моделей, построенная на базе компонентных технологий

  • Объектное представление XML-документов

    Газета:

  • Microsoft для российских разработчиков: практика с элементами фундаментальности

    10 марта

  • HadoopDB: архитектурный гибрид технологий MapReduce и СУБД для аналитических рабочих нагрузок

  • Классификация OLAP-систем вида xOLAP

  • BGP. Три внешних канала. Балансировка исходящего и входящего трафиков

    Газета:

  • Что мы знаем об iPhone 4G?

    17 февраля

  • MapReduce и параллельные СУБД: друзья или враги?

  • Объектно-ориентированное программирование в ограничениях: новый подход на основе декларативных языков моделирования данных

  • Системологический подход к декомпозиции в объектно-ориентированном анализе и проектировании программного обеспечения

    Газета:

  • Эволюция Wine

    3 февраля

  • Дом на песке

  • Реальное переосмысление "формальных методов"

  • Интервью с Найджелом Пендзом

    Газета:

  • iPad. Первый взгляд на долгожданный планшет от Apple

  • Я не верю в iPad [an error occurred while processing this directive]

    20 января

  • SQL/MapReduce: практический подход к поддержке самоописываемых, полиморфных и параллелизуемых функций, определяемых пользователями

  • Данные на лету: как технология потокового SQL помогает преодолеть кризис

    Обзоры журнала Computer:

    2 декабря

  • Сергей Кузнецов. Год эпохи перемен в технологии баз данных

    18 ноября

  • Генерация тестовых программ для подсистемы управления памятью микропроцессора

  • Сравнительный анализ современных технологий разработки тестов для моделей аппаратного обеспечения

    Все публикации >>>


    [an error occurred while processing this directive]
  • [an error occurred while processing this directive] [an error occurred while processing this directive]
    Купить сотовые телефоны в М.Видео
    Отличные цены на сотовые телефоны. Бесплатная доставка. Заказ в интернет-магазине и по телефону (495) 644-28-51
    www.mvideo.ru [an error occurred while processing this directive]

    Регистрация доменов в зонах .ru, .com, .net. Компания Rusonyx.

    IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

    [an error occurred while processing this directive]
    Информация для рекламодателей PR-акции, размещение рекламы — тел. +7 495 6608306, ICQ 232284597 Пресс-релизы — pr@citforum.ru
    Послать комментарий
    Информация для авторов

    Редакция раздаёт котят!

    Rambler's Top100 TopList liveinternet.ru: показано число просмотров за 24 часа, посетителей за 24 часа и за сегодня This Web server launched on February 24, 1997
    Copyright © 1997-2000 CIT, © 2001-2009 CIT Forum
    Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...
    [an error occurred while processing this directive]


    [an error occurred while processing this directive] [an error occurred while processing this directive] реклама:
    Производство и продажа серверов | забронировать гостиницу Санкт Петербурга | платный хостинг | IBM Rational. Аналитика и инструменты
    [an error occurred while processing this directive] [an error occurred while processing this directive]