Сравнительный и практический анализ

Я представляю вам не слишком известный, но лично для меня (и для других специалистов) очень важный журнал, издаваемый техническим комитетом IEEE Computer Society по инженерии данных. Почему мне нравится этот журнал? Во-первых, он не выпендривается. Нормальный технический журнал, не претендующий на высокую науку (я ничего против нее не имею, но не вижу ее в своей области - инженеры мы, а не ученые). Во-вторых, мне нравятся авторы журнала, большинство из них известные специалисты в области баз данных. В третьих, мне нравится главный редактор журнала Дэвид Ломет, с приходом которого в Microsoft Research в корпорации Microsoft совершенно изменилась ситуация с исследованиями в области баз данных. В четвертых, этот журнал один из немногих, который выходит только в Internet (www.research.microsoft.com/research/db/debull) и абсолютно свободно доступен всем желающим.

Итак, июньский номер (а журнал выходит четыре раза в год) посвящен адаптивной обработке запросов к базам данных. Приглашенным редактором номера является Алон Леви (Alon Levy) из Вашингтонского университета. (Честно говоря, я не читал его собственных статей по этой тематике. А может быть, редакторам и не стоит писать?) Термин «адаптивная обработка запросов» появился совсем недавно, но по смыслу ничего нового не привнес. Та же самая оптимизация запросов, и конечно, запросов к реляционным базам данных. Но эта область исследований безгранична и очень важна с практической точки зрения.

Первая небольшая статья принадлежит перу Гоц Грейф (Goetz Graefe), который, конечно же, работал в IBM и который, конечно же, теперь работает в Microsoft. (Похоже, скоро все мы там будем.) Статья называется «Dynamic Query Evaluation Plans: Some Course Corrections?» и имеет вводно-постановочный характер. В статье перечисляются темы, в отношении которых все еще уместны исследования. Забавно, но в основном это те же самые темы, которые были актуальны тридцать лет тому назад. Первая тема - это методы оценки стоимости выполнения запросов. Патриция Селинджер написала свою классическую статью по этому поводу в 1976 году. Вторая тема - оптимизация буферизации при выполнении вложенных запросов (помните, как боролся с вложенными запросами Вон Ким?; оказывается, что иногда приводить запросы со вложенными подзапросами к запросам с соединениями невыгодно). Третья, и тоже очень древняя и до сих пор нерешенная задача - это эффективная материализация представлений (и соответствующая индексация). Следующая задача состоит в разумном кэшировании результатов запросов (Oracle пытается делать это начиная с шестой версии). Наконец, несколько последних аспектов статьи касаются вопросов физической оптимизации баз данных. Вполне естественная тема, соответствующая стратегии Microsoft.

Вторая статья номера «Adaptive Query Processing: Technology in Evolution» написана большой группой авторов (Joseph M. Hellerstein, Michael J. Franklin, Sirish Chandrasekaran, Amol Deshpande, Kris Hildrum, Sam Madden, Vijayshankar Raman, Mehul A. Shah). Но статья очень полезная. Хороший технологическтий обзор и анализ методов оптимизации, применяемых в проекте Telegraph Университета Беркли. Приводится определение адаптивной системы обработки запросов с тремя ее характеристиками: (1) система использует информацию своей среды; (2) эта информация определяет поведение системы; (3) имеется обратная связь между средой и системой. Мне кажется, что основной заслугой авторов являются не представленные ими результаты (как обычно, это новые результаты, базирующиеся на статьях 30-летней давности), а очень хороший обзор и перечень нерешенных проблем. Полезная работа. Кстати, очень хороший список библиографии. Рекомендую.

Следующая (третья) статья тоже создана коллективом авторов (Zachary G. Ives, Alon Y. Levy, Daniel S. Weld - Вашингтонский университет, Daniela Florescu - INRIA, Франция, Marc Friedman - совсем молодая компания Viathan, основанная выходцами из Microsoft). Пожалуй, из всей этой кампании в последние годы более всех известна Даниела Флореску, которая активно работает в INRIA над системами баз данных для Internet. Статья называется «Adaptive Query Processing for Internet Applications» и базируется на промежуточных результатах проекта Tukwila Вашингтонского университета. Пожалуй, наиболее интересный результат этой статьи - это стратегии оптимизации запросов к базам данных в Internet, дающим неполные и неточные результаты. Очень важны критерии достаточности таких результатов. Как сейчас принято, весь проект основан на XML. Естественно, авторы ссылаются на Джонотана Руби (ныне работающего в компании Software AG) и прочих живых классиков из Консорциума W3C.

У четвертой статьи два автора - Толга Урбан (Tolga Urban, университет Мэриленда) и Майкл Франклин (Michael J. Franklin, университет Беркли) - и эта статья абсолютно конкретна. Описывается еще один алгоритм реляционного соединения «Xjoin: A Reactivlely-Scheduled Pipelined Join Operator». Основная идея предложенного алгоритма основана на известном методе симметричного соединения на основе хэширования (см. список литературы), но отличие состоит в том, что требуется получить (хотя бы первые) результаты соединения как можно быстрее, преодолевая задержки, свойственные доступу к базам данных в Internet. Среди прочего, в статье показано, что выбранный метод соединений для случая баз данных в Internet работает более эффективно, чем известный подход гибридного соединения на основе хэширования. Планируется реализовать предложенный алгоритм в упоминавшемся выше проекте университета Беркли Telegraph. В статье содержится краткий, но очень качественный и свежий список литературы.

Пятая статья написана Ричардом Коулом (Richard L. Cole) из компании Informix Software и кажется мне очень актуальной, хотя предлагаемые идеи явно еще не реализованы. Если вы помните, начиная с эпохального проекта IBM System R (Патриция Селинджер!!!), в мире реляционных баз данных был принят подход к оценке стоимости выполнения плана запроса во время компиляции. Понятно, что используются эвристические алгоритмы, и понятно, что точность оценок весьма относительна. Коул в своей статье «A Decision Theoretic Cost Model for Dynamic Plans» предлагает другой подход, основанный на динамически используемых эвристиках из области теории принятия решений. Разумная идея, но не возникла ли она слишком поздно? Посмотрим, воспользуется ли этой идеей Informix. А актуальной я считаю статью, поскольку в нашем мире баз данных слишком мало новых идей. Возможно, мысли Ричарда не будут немедленно востребованы, но рано или поздно они пригодятся.

Наконец, последняя статья июньского номера «Бюллетеня» является французско-американской. Ее авторы — Люк Бугамин (Luc Bougamin, Versallis, Франция), Франсуаза Фабре (Francoise Fabret, INRIA), Патрик Вальдурец (Patrick Valduriez, INRIA) и К. Мохан (C. Mohan), который теперь не только работает на IBM, но и сотрудничает с INRIA. Видимо, это статья с наиболее знаменитыми авторами: Вальдурец и Мохан имеют мировую известность. Название статьи :»A Dynamic Query Processing Architecture for Data Integration Systems» относится к старой и нерешенной проблемы оптимизации запросов для интегрированных систем баз данных. Отмечаются проблемы, связанные с использованием традиционных методов оптимизации запросов в подобной среде. Предлагается стратегия динамической оптимизации и выполнения запросов. Не знаю, насколько этот подход важен сегодня практически, но давно хотелось увидеть что-нибудь подобное.

Честно говоря, прочитав журнал, я испытал чувство праздника. Не так уж часто удается издавать отдельные номера журналов, посвященные достаточно узкой тематике. Пятнадцать лет назад оптимизация запросов была моей любимой темой. С тех пор актуальность этого исследовательского и индустриального направления только возросла. Помните статью Чаутхари в третьем, «майкрософтовском» номере СУБД за 1998 год? И в России нужны такие специалисты. Кстати, для работы в технических комитетах Computer Society не требуется даже членство в сообществе (см. www.computer.org.ru), хотя по-прежнему рекомендую к нам присоединяться. Надеюсь, что вы помните мои координаты.

Электронная почта - kuzloc@ispras.ru, телефон — (095) 912-4614.