|
21.4. Оптимизация запросов,
управляемая правилами
В лекции 18 мы коротко рассмотрели
проблемы оптимизации запросов,
которые приходится решать в
компиляторах языков баз данных.
Возможно, главным выводом, который
следовало бы сделать на основе
материалов этой лекции, является
то, что оптимизатор запросов - это
наиболее громоздкий, сложный и
критичный компонент СУБД. Все
разработчики систем управления
базами данных согласны с тем, что на
оптимизации запросов экономить
нельзя. Чем большее количество
вариантов выполнения запроса
анализируется и чем более точные
оценки стоимости плана выполнения
запроса применяются, тем более
вероятно, что запрос будет выполнен
эффективно.
Главная неприятность, связанная с
оптимизаторами запросов, состоит в
том, что отсутствует принятая
технология их программирования.
Обычно оптимизатор представляет
собой аморфный набор относительно
независимых процедур, которые
жестко связаны с другими
компонентами компилятора. По этой
причине очень трудно менять
стратегии оптимизации или
качественно их расширять (делать
это приходится, поскольку
оптимизация вообще и оптимизация
запросов, в частности, в принципе
является эмпирической дисциплиной,
а хорошие эмпирические алгоритмы
появляются только со временем).
Каким же образом можно решать эту
проблему? Имеются компромиссные
решения, не выводящие за пределы
традиционной технологии
производства компиляторов. В
основном все они связаны с
применением тех или иных
инструментальных средств,
обеспечивающих автоматизацию
построения компиляторов. Среди них
отметим технологию, примененную
Ричардом Столлманом в его
семействе компиляторов gcc, а также
инструментальный пакет Cocktail,
разработанный в Германском
университете города Карлсруе.
Основным производственным
достоинством gcc является
применение единого языка в
качестве средства внутреннего
представления программы.
Высокоуровневый лиспоподобный
язык RTL используется на всех фазах
компиляции gcc, что позволяет
применять одни и те же
преобразующие процедуры на разных
стадиях оптимизации программы
(вплоть до стадии машинно-зависимых
оптимизаций).
В пакете Cocktail обеспечивается
набор универсальных, настраиваемых
процедур преобразования графов
внутреннего представления
программы. В некотором смысле Cocktail
можно рассматривать как
специализированный язык для
написания компиляторов
(компиляторов любых языков, а не
только процедурных языков
программирования или
декларативных языков баз данных).
Как утверждается, Cocktail позволяет
повысить производительность труда
разработчиков компиляторов в 2-3
раза.
Однако наиболее революционный
подход среди известных автору был
применен в экспериментальной
постреляционной системе компании
IBM Starburst. В некотором смысле этот
подход является развитием идеи
Столлмана, примененной при
реализации широко популярного
редактора Emacs. Напомним, что в
основе этого редактора лежит
интерпретатор расширенного
диалекта языка Common Lisp. Сам этот
интерпретатор написан на языке Си,
а основная часть редактора
написана на языке Лисп. Это
позволяет, среди прочего, добавлять
в редактор новые возможности, не
покидая его среды: вы просто пишете
новый текст на Лиспе и объявляете
соответствующую функцию
подключенной к редактору.
Система Starburst основана на
применении продукционной системы.
Эта система является, по существу,
виртуальной машиной, в которой
выполняются все компоненты СУБД,
начиная от компилятора языка баз
данных (расширенного варианта
языка SQL) и заканчивая подсистемой
непосредственного исполнения
запросов. Сама СУБД представляет
собой набор продукционных правил,
каждое из которых вызывается
продукционной системой при
возникновении соответствующего
события и выполняет некоторое
действие, которое, в свою очередь,
может привести к возникновению
события, активизирующего другое
правило. Правила представляются на
специальном языке. Поддерживается
набор предопределенных правил
низкого уровня, обеспечивающих
интерфейс с подсистемой управления
внешней памятью (конечно, по
соображениям эффективности эта
подсистема написана не на
продукционном языке).
Очевидно, что такая организация
системы обеспечивает максимальную
гибкость. Например, чтобы внедрить
в оптимизатор запросов некоторую
новую стратегию выполнения
(например, расширить применяемый
набор методов выполнения
эквисоединения) достаточно
дополнительно написать одно или
несколько новых правил, связанных с
событием требования выполнить
соединение. Тем самым, Starburst может
использоваться (и реально
используется в
научно-исследовательских
лабораториях компании IBM) как
мощное и гибкое средство
исследования методов оптимизации
запросов. Конечно, сомнительно, что
технология, положенная в основу
Starburst, позволит этой системе
конкурировать с такими
выполненными в традиционной манере
коммерческими СУБД, как DB2, Oracle, Informix
и т.д.
Предыдущая
глава || Оглавление
|| Следующая глава
|
