Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 28)

Шаг 2 может применяться итерационно для дерева операций произвольной глубины для определения стоимости каждой из операций. Как только мы имеем оценки стоимости для каждого узла-операции, стоимость плана может быть получена путем комбинирования стоимостей узлов-операций дерева. Важно осознавать различие между природой статистического свойства и стоимостью плана. Статистическое свойство выводного потока данных плана - это то же самое, что статистическое свойство любого другого плана того же запроса, но стоимость этого плана может отличаться от стоимости всех других планов. Другими словами, статистическая сводка - это логическое свойство, а стоимость плана - это свойство физическое.

3.1 Статистические сводки данных

3.1.1 Статистическая информация о базовых данных

Для каждой таблицы необходимая статистическая информация включает число кортежей в потоке данных, поскольку этот параметр определяет стоимость сканирования данных, соединений и соответствующие требования к памяти. Кроме числа кортежей, важным является число физических страниц, занимаемых таблицей. Представляет интерес статистическая информация о столбцах потоков данных, поскольку эти статистики могут быть использованы для оценки селективности предиката на столбце. Такая информация создается для столбцов, для которых существует один или несколько индексов, хотя по требованиям она может быть создана и для любого другого столбца.

В большом числе систем информация о распределении данных в столбце обеспечивается с помощью гистограмм. В гистограмме значения столбца делятся на k порций. Во многих случаях k является константой и представляет степень точности гистограммы. Однако k определяет также и использование памяти, поскольку при оптимизации запроса подходящие столбцы гистограммы загружаются в основную память. Имеется несколько вариантов разбиения значений на порции. Во многих системах баз данных для представления распределения данных в столбце используются равноглубокие гистограммы (по-другому их называют равновысокими). Если в таблице содержится n записей и гистограмма состоит из k порций, то в равноглубокой гистограмме набор значений этого столбца делится на k диапазонов, в каждом из которых присутствует одно и то же число значений, т. е. n/k. В сжатых гистограммах часто встречающиеся значения помещаются в отдельные порции. Число таких отдельных порций может настраиваться. Одним из аспектов гистограмм, отноящихся к оптимизации, является предположение о данных внутри одной порции. Например, для равноглубоких гистограмм можно предположить, что данные на границах порций распределены равномерно. При отсутствии гистограмм может использоваться такая информация, как минимальное и максимальное значения столбца. Однако на практике используются следующее за минимальным и предыдущее максимальному значения, потому что минимум и максимум с большой вероятностью являются отдаленными значениями. Гистограммная информация дополняется информацией о таких параметрах, как число различных значений в данном столбце.

Хотя гистограммы обеспечивают информацию об одном столбце, они не обеспечивают информации о корреляции между столбцами. Для принятия в учет корреляций требуется совместное распределение значений. Один из вариантов состоит в использовании двухмерных гистограмм. К сожалению, пространство возможностей очень велико. Во многих системах вместо детального совместного распределения используется только сводная информация, такая как число различных пар значений. Например, статистическая информация, ассоциированная с индексом на нескольких столбцах, может состоять из гистограммы на первом столбце и общего числа различных комбинаций существующих в таблице значений столбцов.

3.1.2 Оценка статистики базовых данных

Базы данных масштаба предприятия часто имеют большую схему и содержат большие объемы данных. Поэтому для наличия гибкости при получении статистики для улучшения точности важно иметь возможность точно и эффективно оценивать статистические параметры. Один из возможных подходов основывается на взятии проб данных. Однако задачей является ограничение ошибки оценки. В [4] Шапиро и Коннелл показывают, что при наличии заданного запроса требуется только небольшая проба, чтобы построить гистограмму, которая с большой вероятностью будет точной для этого запроса. Но этот подход не достигает цели, которая состоит в том, чтобы построить гистограмму, являющуюся достаточно точной для большого класса запросов.

3.1.3 Распространение статистической информации

Недостаточно использовать только информацию о базовых данных, поскольку запрос обычно содержит много операций. Поэтому важно иметь возможность распространять статистическую информацию через операции. Простейший случай такой операции - это селекция. Если имеется гистограмма на столбце A, и запрос состоит из единственной селекции на столбце A, то гистограмму можно модифицировать таким образом, чтобы она отражала действие селекции. На этом шаге такие предположения, как равномерное распределение данных внутри порции данных гистограммы, приводят к некоторой неточности. Более того, ключевым источником ошибок является невозможность учета корреляции. В приведенном примере это выражается в том, что не модифицируются распределения значений других атрибутов таблицы (кроме A), а это подвергает значительным ошибкам последующие операции. Подобно этому, если в запросе присутствует несколько предикатов, то принимается предположение об их независимости и общей селективностью условия считается произведение селективностей предикатов. Однако в некоторых системах используется селективность наиболее селективного предиката, и они могут установить наличие потенциальной корреляции . При наличии гистограмм на столбцах, участвующих в предикате соединения, гистограммы могут "соединяться". Однако это порождает вопрос о выравнивании границ соответствующих порций. Наконец, если гистограммная информация недоступна, то для оценки селективности используются специально подобранные константы.

3.2 Вычисление стоимости

На шаге оценки стоимости производится попытка определить стоимость операции. Модуль стоимости оценивает время центрального процессора, число операций ввода/вывода и, в случае параллельных или распределенных систем, коммуникационные расходы. В большинстве систем эти параметры комбинируются на основе общей метрики, и эта комбинированная оценка стоимости используется для сравнения возможных планов. Проблема выбора соответствующего набора параметров для определения стоимости заслуживает значительного внимания. Было установлено, что в дополнение к учету физических и логических свойств входных потоков данных и вычислению селективности - ключевую роль в точных оценках играет моделирование использования буферизации в основной памяти. Для этого требуется использование разных коэффициентов предпочтительности содержания в буферном пуле в зависимости от уровней индекса, а также регулирование использования буфера за счет учета свойств методов соединения, например, относительно явной локальности ссылок при индексном сканировании в индексном методе соединения с помощью вложенных циклов . В оценочных моделях учитываются уместные аспекты физического проекта, например, относительное расположение страниц данных и индексных страниц. Однако обеспечение возможности произведения действительно точных оценок стоимости и распространения статистической информации потоков данных остаются трудными открытыми вопросами оптимизации запросов.

4 Другие вопросы оптимизации

В этой статье были рассмотрены только некоторых фундаментальных вопросов оптимизации. Имеется много важных областей, которые не рассматривались. Одним из интересных направлений является то, в котором допускается отложенная генерация полных планов при условии доступности информации времени выполнения . Кроме того, открытой остается проблема учета других ресурсов (в особенности памяти) при определении планов выполнения. Технология оптимизации в объектно-ориентированных системах является важной областью, заслуживающей отдельного обсуждения. Кроме того, когда базы данных стали использоваться в контекстах мультимедиа и Web, появилось интересное направление работы в связи с нечеткими (неточными) запросами.

Существующее повышенное внимание к системам поддержки принятия решений побудило также проведение работ в области расширений SQL.

5. Заключение

Оптимизация означает намного больше, чем преобразования и эквивалентность запросов. Существенна инфраструктура оптимизации. Разработка эффективных и корректных преобразований SQL-запросов является трудной задачей, надежные метрики оценок иллюзорны, задача построения расширяемой архитектуры перебора в значительной степени решена.

6. Литература

1. Rosental A., Galindo-Legaria C. Query Graphs, Implementing Trees, and Freely Reropderable Outerjoins. In Proc. of ACM SIGMOD. Atlantic City, 1990.

2. Kim W. On Optimizing an SQL-like Nested Query. ACM TODS, Vol. 9, No. 3, 1982.

3. Dayal U. Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates and Quantifiers. In Proc. of VLDB, 1987.

4. Piatetsky-Shapiro G., Connel C. Accurate Estimation of the Number of Tuples Satisfying a Condition. In Proc. of ACM SIGMOD, 1984.

5. Кузнецов С.Д. Введение в СУБД. Системы управления базами данных. No 1-4 ,1995.

6. Методы оптимизации запросов в реляционных системах. С. Чаудхари Системы управления базами данных. No 3 ,1998.

Приложение 3. Расчет затрат на создание системы распределенной обработки данных в сети.

2.1. Смета затрат на создание проектного решения интерсети.

2.2. Расчет и обоснование сметы затрат на создание проектного решения интерсети.

2.2.1. Материалы.

К статье затрат на материалы отнесены следующие расходы:

Итого 1700 рублей.

2.2.2. Оборудование.

Затраты по данной статье сводятся к затратам, связанным с использованием вычислительной техники и с учетом ее ремонта.

При разработке использовалось следующее оборудование:

Итого: 26200 рублей.

Затраты на вычислительную технику были определены из того, что при разработке была задействована одна ПЭВМ. Длительность использования оборудования составляет 3 месяца.

При использовании ускоренных сроков амортизации затраты на вычислительную технику вычисляются по формуле:

Характеристики

Список файлов домашнего задания