Методы оптимизации запросов в реляционных системах
| Вид материала | Документы |
- Решение задач глобальной оптимизации большой размерности на многопроцессорных комплексах, 143.77kb.
- Петербургский Государственный Университет Математико-Механический Факультет Кафедра, 596.99kb.
- Календарный план учебных занятий по дисциплине Компьютерный дизайн оптических наноструктур,, 39.38kb.
- Рабочей программы дисциплины Системы управления базами данных по направлению подготовки, 20.59kb.
- Методы оптимизации энергопотребления в микроэлектронных системах, 490.32kb.
- Конспект лекций по Методам оптимизации для студентов, обучающихся по специальности, 41.05kb.
- Концепция системного подхода при проектировании сапр. Последовательный метод компоновки, 29.25kb.
- Учебной дисциплины «Методы оптимизации» для направления 010400. 62 «Прикладная математика, 40.12kb.
- Рабочая учебная программа по дисциплине «Методы оптимизации» Направление №230100 «Информатика, 129.28kb.
- Рабочая программа учебной дисциплины (модуля) методы оптимизации, 164.09kb.
3.1.1 Статистическая информация о базовых данных
Для каждой таблицы необходимая статистическая информация включает число кортежей в потоке данных, поскольку этот параметр определяет стоимость сканирования данных, соединений и соответствующие требования к памяти. Кроме числа кортежей, важным является число физических страниц, занимаемых таблицей. Представляет интерес статистическая информация о столбцах потоков данных, поскольку эти статистики могут быть использованы для оценки селективности предиката на столбце. Такая информация создается для столбцов, для которых существует один или несколько индексов, хотя по требованиям она может быть создана и для любого другого столбца.
В большом числе систем информация о распределении данных в столбце обеспечивается с помощью гистограмм. В гистограмме значения столбца делятся на k порций. Во многих случаях k является константой и представляет степень точности гистограммы. Однако k определяет также и использование памяти, поскольку при оптимизации запроса подходящие столбцы гистограммы загружаются в основную память. Имеется несколько вариантов разбиения значений на порции. Во многих системах баз данных для представления распределения данных в столбце используются равноглубокие гистограммы (по-другому их называют равновысокими). Если в таблице содержится n записей и гистограмма состоит из k порций, то в равноглубокой гистограмме набор значений этого столбца делится на k диапазонов, в каждом из которых присутствует одно и то же число значений, т. е. n/k. В сжатых гистограммах часто встречающиеся значения помещаются в отдельные порции. Число таких отдельных порций может настраиваться. Как показано в [52], такие гистограммы эффективны для сильно или слабо скошенных распределений данных. Одним из аспектов гистограмм, отноящихся к оптимизации, является предположение о данных внутри одной порции. Например, для равноглубоких гистограмм можно предположить, что данные на границах порций распределены равномерно. Это предположение, так же как и широкая таксономия гистограммного подхода и влияние структуры гистограмм на точность, обсуждаются в [52]. При отсутствии гистограмм может использоваться такая информация, как минимальное и максимальное значения столбца. Однако на практике используются следующее за минимальным и предыдущее максимальному значения, потому что минимум и максимум с большой вероятностью являются отдаленными значениями. Гистограммная информация дополняется информацией о таких параметрах, как число различных значений в данном столбце.
Хотя гистограммы обеспечивают информацию об одном столбце, они не обеспечивают информации о корреляции между столбцами. Для принятия в учет корреляций нам требуется совместное распределение значений. Один из вариантов состоит в использовании двухмерных гистограмм [45, 51]. К сожалению, пространство возможностей очень велико. Во многих системах вместо детального совместного распределения используется только сводная информация, такая как число различных пар значений. Например, статистическая информация, ассоциированная с индексом на нескольких столбцах, может состоять из гистограммы на первом столбце и общего числа различных комбинаций существующих в таблице значений столбцов.
3.1.2 Оценка статистики базовых данных
Базы данных масштаба предприятия часто имеют большую схему и содержат большие объемы данных. Поэтому для наличия гибкости при получении статистики для улучшения точности важно иметь возможность точно и эффективно оценивать статистические параметры. Один из возможных подходов основывается на взятии проб данных. Однако задачей является ограничение ошибки оценки. В [48] Шапиро и Коннелл показывают, что при наличии заданного запроса требуется только небольшая проба, чтобы построить гистограмму, которая с большой вероятностью будет точной для этого запроса. Но этот подход не достигает цели, которая состоит в том, чтобы построить гистограмму, являющуюся достаточно точной для большого класса запросов. Эту проблему затрагивает наша недавняя работа [11]. Мы также показали, что задача оценки различных значений, вероятно, подвержена ошибкам, т. е. для любой схемы оценок существует база данных, для которой ошибка будет существенной. Этот результат объясняет возникавшие в прошлом трудности в оценке числа различных значений [50, 27]. В одной из недавних работ рассматривается также проблема поддержки статистики в инкрементальной манере [18].
3.1.3 Распространение статистической информации
Недостаточно использовать только информацию о базовых данных, поскольку запрос обычно содержит много операций. Поэтому важно иметь возможность распространять статистическую информацию через операции. Простейший случай такой операции - это селекция. Если имеется гистограмма на столбце A, и запрос состоит из единственной селекции на столбце A, то гистограмму можно модифицировать таким образом, чтобы она отражала действие селекции. На этом шаге такие предположения, как равномерное распределение данных внутри порции данных гистограммы, приводят к некоторой неточности. Более того, ключевым источником ошибок является невозможность учета корреляции. В приведенном примере это выражается в том, что не модифицируются распределения значений других атрибутов таблицы (кроме A), а это подвергает значительным ошибкам последующие операции. Подобно этому, если в запросе присутствует несколько предикатов, то принимается предположение об их независимости и общей селективностью условия считается произведение селективностей предикатов. Однако в некоторых системах используется селективность наиболее селективного предиката, и они могут установить наличие потенциальной корреляции [17]. При наличии гистограмм на столбцах, участвующих в предикате соединения, гистограммы могут «соединяться». Однако это порождает вопрос о выравнивании границ соответствующих порций. Наконец, если гистограммная информация недоступна, то для оценки селективности используются специально подобранные константы, как в [55].
3.2 Вычисление стоимости
На шаге оценки стоимости производится попытка определить стоимость операции. Модуль стоимости оценивает время центрального процессора, число операций ввода/вывода и, в случае параллельных или распределенных систем, коммуникационные расходы. В большинстве систем эти параметры комбинируются на основе общей метрики, и эта комбинированная оценка стоимости используется для сравнения возможных планов. Проблема выбора соответствующего набора параметров для определения стоимости заслуживает значительного внимания. В ранних исследованиях [40] было установлено, что в дополнение к учету физических и логических свойств входных потоков данных и вычислению селективности - ключевую роль в точных оценках играет моделирование использования буферизации в основной памяти. Для этого требуется использование разных коэффициентов предпочтительности содержания в буферном пуле в зависимости от уровней индекса, а также регулирование использования буфера за счет учета свойств методов соединения, например, относительно явной локальности ссылок при индексном сканировании в индексном методе соединения с помощью вложенных циклов [17]. В оценочных моделях учитываются уместные аспекты физического проекта, например, относительное расположение страниц данных и индексных страниц. Однако обеспечение возможности произведения действительно точных оценок стоимости и распространения статистической информации потоков данных остаются трудными открытыми вопросами оптимизации запросов.
4. Архитектуры перебора
Алгоритм перебора должен выбрать недорогой план выполнения данного запроса на основе исследования пространства поиска. Алгоритм перебора System R, который мы обсуждали в разделе 3, был разработан в расчете на выбор только оптимального порядка линейных соединений. По соображениям технологии программирования желательно создать такой алгоритм перебора, который мог бы легко приспосабливаться к изменениям пространства поиска по причине добавления новых преобразований, добавления новых физических операций (например, новых реализаций соединений) и к изменениям методов оценки стоимости. Современные архитектуры оптимизации построены на основе этой парадигмы и называются расширяемыми оптимизаторами. Построение расширяемого оптимизатора - это трудная задача, поскольку от него требуется не только наличие улучшенного алгоритма перебора. На самом деле эта технология обеспечивает инфраструктуру для развития техники оптимизации. Однако общность архитектуры должна быть сбалансирована с потребностью эффективного перебора.
Мы сосредоточимся на двух представительных примерах таких расширяемых оптимизаторов: Starburst и Volcano/Cascades. Несмотря на имеющиеся различия, можно выделить некоторые общие характеристики этих оптимизаторов.
a) использование обобщенных стоимостных функций и физических свойств вершин-операций;
b) использование подсистемы обработки правил, дающей возможность изменять выражения запросов или деревья операций. Такие подсистемы обеспечивают также возможность прямого поиска для достижения эффективности;
c) большое количество доступных «кнопок», которые можно использовать для настройки поведения оптимизатора. К сожалению, установка этих кнопок для достижения оптимальной эффективности является пугающей задачей.
4.1 Starburst
Оптимизация запросов в проекте Starburst исследовательского центра Almaden компании IBM начинается со структурного представления SQL-запроса, которое используется в течение всего жизненного цикла оптимизации. Это представление называется графовой моделью запроса (Query Graph Model - QGM). В QGM бокс представляет блок запроса, а помеченные дуги между боксами представляют ссылки на таблицы между блоками. Каждый бокс содержит информацию о структуре предиката, а также о том, упорядочен ли поток данных. На фазе оптимизации переписывания запроса [49] используются правила для преобразования QGM в другую эквивалентную QGM. Правила оформляются как пары произвольных функций. Первая функция проверяет условие применимости, вторая - проводит преобразование. Правилами управляет подсистема, основанная на построении цепочек правил. Правила могут группироваться в классы, и можно настраивать порядок вычисления классов правил для ориентации поиска. Поскольку любое применение правила приводит к допустимой QGM, любой набор применений правил гарантирует эквивалентность (в предположении, что сами правила законны). Фаза переписывания запроса не приводит к появлению информации о стоимости. Это вынуждает модуль переписывания запросов либо оставлять варианты, получаемые при применении правил, либо использовать правила эвристическим образом (и тем самым рисковать оптимальностью).
Вторая фаза оптимизации запроса называется оптимизацией плана. На этой фазе выбирается план выполнения для данной QGM. В Starburst физические операторы (называемые LOLEPOP) могут комбинироваться различными способами для реализации операций более высокого уровня. Такие комбинации выражаются в грамматике языка, похожего на языки продукций [37]. Реализация высокоуровневой операции выражается путем описания ее происхождения в терминах физических операций. При вычислении таких описаний сравнимые планы, обладающие одними и теми же физическими и логическими свойствами, но имеющие более высокую стоимость, удаляются. Для каждого плана имеются реляционное описание, соответствующее представляемому алгебраическому выражению, оценочная стоимость и физические свойства (например, наличие упорядоченности). Эти свойства распространяются по мере построения планов снизу-вверх. Таким образом, с каждой физической операцией ассоциирована функция, которая показывает воздействие физической операции на каждое из указанных свойств. Алгоритм перебора соединений в этой системе похож на схему перебора снизу-вверх System R.
4.2 Volcano/Cascades
Расширяемые архитектуры Volcano [23] и Cascades [21] происходят от Exodus [22]. В этих системах правила используются универсально для представления знаний о пространстве поиска. Применяются два вида правил. Правила преобразования отображают одно алгебраическое выражение в другое. Правила реализации отображают алгебраическое выражение в дерево операций. Правила могут иметь условия применимости. Логические свойства, физические свойства и оценки стоимости ассоциируются с планами. Физические свойства и стоимость зависят от алгоритмов, используемых для реализации операций, и от их входных потоков данных. В целях эффективности в Volcano/Cascades используется динамическое программирование в манере «сверху/вниз» («запоминание»). Сталкиваясь с задачей оптимизации, оптимизатор проверяет, не выполнялась ли уже такая задача, производя поиск ее логических и физических свойств в таблице планов, которые оптимизировались в прошлом. Если этот поиск не приводит к результату, то оптимизатор применяет правила преобразования, правила реализации или насильственно изменяет свойства потока данных. На каждой стадии используется перспектива действия для определения следующего шага. Параметр перспективы является программируемым и отражает параметры стоимости.
Volcano/Cascades отличается от подхода Starburst алгоритмом перебора:
a) не применяются две разные фазы оптимизации, поскольку все преобразования являются алгебраическими и основаны на оценках;
b) отображение алгебраического представления в дерево физических операций выполняется за один шаг;
c) вместо применения правил в манере цепочек, как это происходит на фазе переписывания запросов в Starburst, в Volcano/Cascades применение правил управляется целью.
5. За пределами основ
До сих пор я рассматривал основы программных компонентов оптимизатора. В этом разделе обсуждаются более передовые темы. Каждая из них существенно важна для коммерческих систем.
5.1 Распределенные и параллельные базы данных
Распределенные базы данных вводят в рассмотрение вопросы стоимости коммуникаций и расширения пространства поиска в связи с возможностью при оптимизации запросов учитывать допустимые перемещения данных и выбор узлов для выполнения промежуточных операций. Хотя в некоторых из ранних работ основной упор делался на сокращение стоимости коммуникаций [1, 3] (например, с использованием полусоединений), результаты System R* показывают доминирующую роль локальной обработки [39] (см. обзор в [38]). Со временем архитектуры распределенных баз данных эволюционировали к реплицированным базам данных, в которых поддерживается управление физическим распределением данных, и к параллельным базам данных, основной эффект которых состоит в увеличении масштабируемости. В архитектурах, поддерживающих репликацию, важным вопросом является поддержание согласованности реплик, но это находится за пределами темы данной статьи.
В отличие от распределенных систем параллельные базы данных ведут себя как единая система, но используют множественные процессорные элементы для сокращения времени ответа (В однопроцессорных системах основное внимание уделяется сокращению общего объема работы. При параллельном выполнении стремятся скорее сократить время ответа, а не общую работу. На самом деле, во многих случаях, хотя это не необходимо, параллельное выполнение увеличивает общую работу.) на запросы. Преимущества параллелизма могут быть использованы несколькими способами. Например, физическое распределение данных, когда таблица (в общем случае - поток данных) разделяется или реплицируется между узлами, позволяет процессорам работать над независимыми наборами данных. Параллелизм можно также использовать для выполнения независимых операций или конвейерных операций (путем размещения узла-производителя и узла-потребителя на разных процессорах). Достоинства параллелизма уравновешиваются потребностью в коммуникации процессоров для обмена данными, например, в том случае, когда требуется перераспределение данных после выполнения операции. Кроме того, эффективное планирование выполнения физических операций вносит новое измерение в проблему оптимизации. В проекте XPRS [31, 32] поддерживается двухфазный подход, в котором в первой фазе для генерации плана выполнения используется традиционная однопроцессорная оптимизация. На второй фазе определяется планирование процессоров. В работе над оптимизацией запросов в XPRS не изучались эффекты межпроцессорных коммуникаций. В работе Хасана [28] было показана важность учета расходов на коммуникацию. Хасан оставил двухфазный подход, использовавшийся в XPRS, но включил в первую фазу учет расходов и доходов от разделения данных с целью определения порядка соединений и используемых методов доступа. Атрибут разделения потока данных рассматривался как физическое свойство потока данных. На выходе первой фазы формировалось дерево операций, раскрывающее ограничения предшествования (например, для сортировки) и конвейерность выполнения. Для второй фазы оптимизации он предложил алгоритмы планирования, учитывающие коммуникационные расходы.
5.2 Определяемые пользователями функции
Хранимые процедуры (называемые также определяемыми пользователями функциями) получили широкое распространение в реляционных системах. Хотя в разных продуктах поддержка таких функций производится по-разному, они обеспечивают мощный механизм для сокращения коммуникаций клиентов и серверов и предоставляют средства включения в запросы семантики приложений. Новые вопросы оптимизации возникают в тех случаях, когда вызовы хранимых процедур рассматриваются как полноправные компоненты запросов. Проблема определения стоимостной модели определяемой пользователем функции остается трудной проблемой. Интересные аспекты возникают в контексте алгоритма перебора. Например, рассмотрим случай, когда хранимая процедура действует как определенный пользователем предикат в разделе WHERE запроса. В отличие от других предикатов такие предикаты могут быть дорогостоящими (например, они могут быть предикатами на BLOB, содержащих графический образ), и поэтому для них отсутствует здравая эвристика вычисления предикатов как можно раньше. Проблема оптимизации запросов с определенными пользователями предикатами была поставлена в [12, 29]. Подход, предложенный в [12] заключается в том, что к определенным пользователями предикатам следует относиться как к отношениям с точки зрения динамической оптимизации запросов. В подходах [29, 30] используется следующее наблюдение: если отсутствуют соединения, то дорогостоящие предикаты могут быть эффективно упорядочены в соответствии с их рангами, вычисляемыми на основе селективности предикатов и стоимости их вычисления для одного кортежа. К сожалению, попытки расширить использование рангов для запросов с соединениями могут привести к выбору неоптимальных планов. Этот недостаток был устранен в [8] путем представления определенных пользователем предикатов наподобие физических свойств плана, так что основанный на динамическом программировании алгоритм перебора гарантирует оптимальность. Более того, при использовании реалистических предположений о стоимостной модели было показано, что эта проблема имеет полиномиальную сложность в зависимости от числа определенных пользователями предикатов.
Решение проблемы оптимизации определяемых пользователями предикатов - это только первый шаг в решении более широкой проблемы представления семантики ADT (Abstract Data Type) в системе запросов и оптимизация запросов при наличии абстрактных типов данных. Эта проблема близко соприкасается с областью семантической оптимизации запросов.
5.3 Материализованные представления
Материализованные представления - это результаты представлений (т. е. запросов), кэшируемые подсистемой запросов и прозрачно используемые оптимизатором. Проблема оптимизации формулируется следующим образом. Для заданного набора материализованных представлений и запроса целью является оптимизация запроса с учетом имеющихся материализованных представлений. Эта проблема порождает две фундаментальные задачи. Первая состоит в потребности переформулировки запроса таким образом, чтобы для его выполнения можно было использовать одно или несколько материализованных представлений. Эта задача рассматривалась в [15, 61, 59, 9] в контексте SQL-запросов только с одним блоком, и решение должно быть обобщено для сложных запросов. Вторая задача связана с тем, что подход к решению проблемы оптимизации на основе двухфазового процесса, когда генерируются все логически эквивалентные выражения и затем каждое из них оптимизируется индивидуально, может увеличить стоимость оптимизации, поскольку подвыражения не устраняются способом, основанным на оценках. В [9] мы показали, каким образом могут перекрываться шаги перебора и генерации эквивалентных выражений при наличии материализованных представлений.
5.4 Другие вопросы оптимизации
В этой статье я коснулся только некоторых фундаментальных вопросов оптимизации. Имеется много важных областей, которые я не обсуждал. Одним из интересных направлений является то, в котором допускается отложенная генерация полных планов при условии доступности информации времени выполнения [19, 33]. Кроме того, открытой остается проблема учета других ресурсов (в особенности памяти) при определении планов выполнения. Работа [58] посвящена вопросам оптимизации использования порядка при оптимизации запросов. Технология оптимизации в объектно-ориентированных системах является важной областью, заслуживающей отдельного обсуждения. Кроме того, когда базы данных стали использоваться в контекстах мультимедиа и Web, появилось интересное направление работы в связи с нечеткими (неточными) запросами [14, 10]. Существующее повышенное внимание к системам поддержки принятия решений побудило также проведение работ в области расширений SQL. Такие работы, как CUBE [24], мотивируются не потребностью повышения выразительной мощности, а скорее связаны с поиском таких расширений языка, которые позволили бы оптимизатору лучше оптимизировать запросы систем поддержки принятия решений.
6. Заключение
Оптимизация означает намного больше, чем преобразования и эквивалентность запросов. Существенна инфраструктура оптимизации. Разработка эффективных и корректных преобразований SQL-запросов является трудной задачей, надежные метрики оценок иллюзорны, задача построения расширяемой архитектуры перебора в значительной степени решена. Несмотря на многие годы работы, существенные проблемы остаются открытыми. Однако для того, чтобы внести вклад в области оптимизации запросов, необходимо понимание существующих подходов.