автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Метод анализа плана выполнения SQL-запроса, используя свойства O-большое асимптотик для оценки стоимости

00461536У На правах рукописи

/С-

БОРЧУК Леонид Евгеньевич

МЕТОД АНАЛИЗА ПЛАНА ВЫПОЛНЕНИЯ 8(2Ь-ЗАПРОСА, ИСПОЛЬЗУЯ СВОЙСТВА 0-БОЛЫДОЕ АСИМПТОТИК ДЛЯ ОЦЕНКИ СТОИМОСТИ

Специальность 05.13.11 Математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

-2 дек 2010

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Череповец - 2010

004615369

На правах рукописи

БОРЧУК Леонид Евгеньевич

МЕТОД АНАЛИЗА ПЛАНА ВЫПОЛНЕНИЯ БСЗЬ-ЗАПРОСА, ИСПОЛЬЗУЯ СВОЙСТВА О-БОЛЫИОЕ АСИМПТОТИК ДЛЯ ОЦЕНКИ СТОИМОСТИ

Специальность 05.13.11 Математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Череповец-2010

Диссертационная работа выполнена на кафедре "Математические методы и информационные технологии в экономике" ГОУ ВПО "Череповецкий государственный университет"

Официальные оппоненты: доктор физико-математических наук, профессор

Защита состоится "_í¿" <-¿«a _ 2010г. в 12 час. на заседании

диссертационного совета/Д 2.125.01 при Московском авиационном институте (техническом университете) по адресу: 125993, г. Москва, А-80, ГСП-3, Волоколамское шоссе, д.4.

С диссертацией можно ознакомиться в библиотеке МАИ

Отзывы на автореферат в двух экземплярах, заверенные печатью, просим направлять по адресу: 125993, г.Москва, А-80, ГСП-3, Волоколамское шоссе, д.4., Ученый совет МАИ.

Научный руководитель:

кандидат технических наук, доцент КУЗЬМИН Александр Александрович Заслуженный деятель науки РФ, доктор технических наук, профессор БРЕХОВ Олег Михайлович

Научный консультант:

Ведущая организация:

НОВИКОВ Борис Асенович доктор технических наук, профессор ПАДАЛКО Сергей Николаевич ЗАО "Научно-исследовательский институт "Центрпрограммсистем" (ЗАО НИИ ЦПС)

Автореферат разослан " Í2, " 2010г.

Ученый секретарь

диссертационного совета Д 212.125.01 кандидат технических наук

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы. Выбор плана выполнения SQL-запроса в современной реляционной СУБД производится путем оптимизации его стоимости. Чем меньше стоимость, тем меньше время выполнения запроса. Стоимость вычисляется на основе сложной математической модели, основанной на многих допущениях и параметрах. Допущения выполняются не всегда. Таким образом, если требуется, чтобы запрос выполнялся с заданным временем ответа, необходимо:

1.Обеспечить адекватность оценок стоимости.

2. Обеспечить присутствие хотя бы одного плана выполнения, реализующего требуемое время ответа, в пространстве состояний.

Обеспечение условий для выбора одного из таких планов выполнения составляет задачу настройки реляционной системы баз данных.

Современные СУБД содержат развитую систему средств автоматической настройки своих компонент и структур, реализация которых может различаться (Database Engine Tuning Advisor, DB2 Advisor, Tuning Pack). Существующие средства автоматической настройки позволяют производить выработку рекомендаций для построения индексов и материализованных представлений по известной рабочей нагрузке, производить отбор и воспроизведение рабочей нагрузки, автоматически информировать о проблемах производительности, производить автоматическое управление статистикой, использовать самонастраиваемые гистограммы.

Несмотря на то, что удалось достичь значительных результатов с использованием средств автоматической настройки, исчерпывающе решить задачу настройки, как отмечают в своих работах Волкер Маркл и Сураджит Чаудхури, одними автоматическими средствами на сегодняшний день не

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

В 2006 году Б. Новиков предложил производить настройку с участием администратора системы локальным методом, анализируя SQL -запросы и стоимость их плана выполнения.

На практике сложность настройки на основе существующих методов состоит в том, что:

- по мере развития структура данных и запросы усложняются, что увеличивает как количество операций плана выполнения, так и количество параметров, на них влияющих;

- объемы хранимых данных постоянно увеличиваются, так что недостаточно просто достичь требуемого времени выполнения. Необходимо исследовать динамику поведения системы и убедиться, что время выполнения будет соответствовать требованиям, как минимум, в ближайшей перспективе;

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

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

Таким образом, научная задача состоит в разработке метода анализа плана выполнения, позволяющего повысить оперативность настройки с

обеспечением требуемого качества показателей выполнения БОЬ-запросов пользователей.

Объектом исследования является процесс настройки системы баз

данных.

Предметом исследования является стоимость выполнения запросов пользователей.

Целью диссертационной работы является сокращение сроков настройки системы баз данных на основе разработки метода анализа плана выполнения запроса, позволяющего определить стоимость выполнения запроса от параметров системы.

Исходя из цели работы, в диссертации решались следующие основные задачи:

- обоснование необходимости совершенствования процесса анализа планов выполнения запросов пользователей;

- анализ доступной статистической информации, выделение значимой для достижения цели исследования;

- построение и анализ свойств модели исполнения системы запросов с учетом статистической информации;

- разработка способов обнаружения значимых с точки зрения используемых ресурсов подмножеств запросов или параметров и прогнозирования стоимости при изменении объема данных;

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

Методы исследования. При выполнении работы использованы методы теории асимптотических оценок, теории графов, теории множеств и алгебраических систем, основные положения линейной алгебры и теории информации, методы теории вероятностей и математической статистики,

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

Научная новизна результатов работы состоит в следующем:

- разработан способ построения математической модели на основе свойств О-большое асимптотик стоимости выполнения SQL запросов в зависимости от значимых параметров системы;

- даны рекомендации по реализации и применению предложенной модели стоимости путем преобразования ее к замкнутому виду и использованию гипотезы о стабильности поведения системы.

Практическая ценность диссертационной работы состоит в том, что:

- даны практические рекомендации по определению адекватности математической модели на основе свойств О-болыыое асимптотических оценок и определению границ области изменения параметров, в которых выполняется предположение о стабильности поведения системы;

- разработана методика построения с использованием свойств О-болыпое асимптотик и анализа модели стоимости выполнения SQL запроса и даны практические рекомендации по расчету коэффициентов модели;

- разработаны алгоритмы выбора показателей для анализа математической модели, учитывающие особенности предметной области и цели настройки.

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

ОАО КБ «СЕВЕРГАЗБАНК», а результаты модернизации внедрены в эксплуатацию.

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

Достоверность полученных результатов обеспечивается корректным использованием математического аппарата, а также современных методов и алгоритмов, что подтверждается практическими испытаниями. На примере автоматизированной банковской системы (АБС)

ОАО КБ «СЕВЕРГАЗБАНК» усовершенствован процесс настройки системы баз данных путем модернизации подсистемы тестирования запросов, используя предложенный способ оценки стоимости и гипотезу о стабильности поведения системы. Результаты усовершенствования внедрены в рабочую эксплуатацию в АБС ОАО КБ «СЕВЕРГАЗБАНК».

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на конференциях:

- 143-м семинаре Московской секции ACM SIGMOD (Москва, МГУ, 28 октября 2010 г.)

- 9-й международной конференции "Интеллектуальные системы и компьютерные науки" (Москва, МГУ, 23-27 октября 2006 г.);

- 7-ой международной научно - технической конференции «Кибернетика и высокие технологии XXI века» С&Т*2006. (Воронеж, 16-18 мая 2006 г.);

- 10-ой международной научно - технической конференции "Системный анализ в проектировании и управлении". (Санкт-Петербург, СПбГПУ, 28 июня - 10 июля 2006 г.).

Основные положения диссертации опубликованы в двух научных журналах, рекомендованных ВАК к публикации:

- Борчук Л.Е., Кузьмин A.A. Оценка времени выполнения запроса в реляционной СУБД на основе асимптотических моделей затрат ресурсов// Наукоемкие технологии. - 2008. - №4. - С. 61-64;

- Борчук Л.Е. Совершенствование процесса настройки запросов пользователей на основе асимптотических оценок затрат ресурсов// Информационные технологии. - 2008. - №6. - С. 6-11. Публикации. По теме диссертации опубликовано 10 печатных работ,

в том числе 6 статей и 4 тезиса докладов. На защиту выносится:

- способ построения модели на основе свойств О-большое асимптотических оценок стоимости выполнения SQL запросов в зависимости от значимых параметров системы;

- рекомендации по применению предложенной модели на основе свойств О-большое асимптотических оценок стоимости, учитывающие особенности предметной области и цели настройки;

- программный комплекс реализации подсистемы тестирования запросов, используя предложенный метод анализа плана выполнения и гипотезу о стабильности поведения системы.

Структура и объем диссертации. Диссертационная работа состоит из списка сокращений, введения, четырех глав, заключения, библиографического списка из 195 наименований и приложений. Общий объем диссертации - 274 страниц машинописного текста, в том числе: 182 страниц основного текста и 92 страницы приложений, 35 рисунков, 11 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

Во введении приведено обоснование актуальности темы работы, постановка задачи и аннотация содержания работы по разделам. Выделена научная новизна и практическая ценность полученных результатов, сформулированы защищаемые положения.

В первой главе проведен анализ способов настройки реляционных систем баз данных. Выявлено, что один из основных методов настройки состоит в решении задачи локальной настройки SQL запроса пользователя. Процесс локальной настройки состоит из нескольких этапов, на которых требуется анализировать стоимость шагов плана выполнения запроса.

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

Во второй главе произведена математическая формализация задачи.

В обобщенном виде существующую модель стоимости можно представить следующим образом.

Компонентами модели являются шаги плана выполнения или реляционные операции над отношениями. Стоимость вычисляется на основе затрат ресурсов компонент СУБД по формуле:

Стоимость = (Количество тактов процессора) х (среднюю стоимость 1 такта) + (Количество чтений с диска) X (среднюю стоимость 1 чтения), (1)

где средняя стоимость 1 такта или 1 чтения - константа, вычисляемая в процессе сбора статистики о системном окружении СУБД; количество тактов процессора или диска - затраты ресурсов. Эндогенными переменными математической модели являются затраты ресурсов на выполнение реляционной операции. Поставим в соответствие каждому учитываемому ресурсу номер, который обозначим как г, (г = 1,2,...). Экзогенными переменными являются математическое ожидание величины затрат ресурсов при обработке одного кортежа реляционного отношения и статистическая количественная информация о хранимых в СУБД отношениях и выполняемых над ними реляционных операциях (компонентах). Поставим в соответствие каждой экзогенной переменной номер, который обозначим как ¿,(1 = 1,2,...). Значения экзогенных и эндогенных переменных конечны.

Зададим множество Р, представляющее собой множество отношений, хранящихся в БД в материализованном виде (на носителе). Обозначим за <2 множество отношений, содержащее множество Р, пока не определяя способ получения его элементов. Определим Л как множество используемых в процессе выполнения запроса реляционных операций Р вида: х -» (); <2 = ((¿.И) - как алгебру реляционных отношений. Из множества Р могут быть получены множества:

<21 = {Ч-Ч = Р^Рг.Рг). Р1.Р2 6 р'р е Ф: д2 = {Ч:ц = РС?!, «ь ?2 еР V Яг, Р* П);

& = {ч- Ч = ^ОЬ. Чг). Чх.Чг 6 Р и ([}%\ ОД Р £ П}. Составим множество @ отношений, являющихся результатом выполнения запросов к исследуемой БД, как (} = Р и (11^1 <?Д Таким образом, заданная в виде (} алгебра реляционных отношений имеет Р

порождающим множеством. Множество Q\P представляет собой множество производных отношений БД, вычисляемых по необходимости с затратами определенных вычислительных ресурсов.

Введем на множестве Q отношение эквивалентности а такое, что выполняется условие стабильности относительно главных операций. На множестве Р два отношения будем считать эквивалентными при совпадении кортежей их именованных типов данных физического представления. На множестве Q\P будем считать, что 2 отношения эквивалентны, если их выражения реляционной алгебры содержат одни и те же элементы порождающего множества и одни и те же реляционные операции над ними. Фактор-множество Q/a обозначим за W, а каноническое отображение Q-*Q/a за w. Эквивалентность а является также и конгруэнцией для алгебры Q, вследствие выполнения условия стабильности относительно главных операций, порождая фактор-систему W — Q/a = {W, SI).

Требуется для каждого типа отношения w 6 W по его формуле найти вектор - функцию D(w) размерности r + t, содержащую t независимых (экзогенных) переменных и г зависимых (эндогенных) переменных затрат ресурсов на получение отношения. Для w Е Р/а D(w) будет задана явно, исходя из характеристик данного отношения, с учетом специфики его хранения на носителе и доступной статистической информации.

Определим способ вычисления вектор - функции D(w~) для отношений, вычисляемых по необходимости с затратами определенных вычислительных ресурсов.

Пусть задана формула получения ответа на запрос пользователя в виде отношения w:

w = F(Wa,Wb), (2)

где w 6 (Q\P)/a - искомое отношение;

А - идентификатор левого операнда операции;

В - идентификатор правого операнда операции;

и/д.м'в - операнд-отношение известного типа.

Предположим, что математическая модель операндов известна. Зададим ресурс г. Для заданного ресурса для V? £ ((ДР)/<т будем

искать в виде:

Яг (иО = ¥„,(*>( »Ш, %(и>)), (3)

где £)(1УЛ) - известный вектор характеристик отношения м?А\

ОК) - известный вектор характеристик отношения мв;

- известный вектор характеристик операции; он содержит статистическую информацию (измеренную, например, С раз при тестовом выполнении запроса пользователя);

Ч'и'.г - вектор-функция затрат ресурсов на выполнение операции.

В общем случае задача вычисления точного значения функции >РИ,Г эквивалентна задаче выполнения запроса пользователя с точностью до последней операции ^ е П, так как до выполнения запроса точные значения и 0(уь>в) могут быть неизвестны.

В работе предложен способ приближенного вычисления функции Ч'и, г с использованием свойств асимптотических оценок.

Асимптотику О затрат ресурсов на получение отношения и/ можно [10] оценить функцией д{.) от количества обработанных кортежей, определяемого на основе значений параметров левого операнда й(и^) и правого операнда С(и>в). Так что верно:

(4)

где С - константа, С 6

Значение константы С в общем случае различно для каждого значения параметров функции #(.). Определим способ вычисления константы С.

Порожденная фактор-система соотносит каждому типу запросов IV несколько различных БС^Ь-выражений д, имеющих сходный план

выполнения. Для некоторых из них затраты ресурсов известны (составим из них вектор X). Минимизируем квадрат ошибки верхней оценки для известных значений затрат ресурсов:

т!псей+ 2((С • дФШ.Нщ)) ~ЪУ • (5)

Выражение (5) задает способ расчета коэффициента С при построении модели затрат ресурсов заданного вида г на выполнение запроса типа IV при наличии статистической информации о выполнении некоторых запросов типа IV.

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

На рис. 1 представлены экспериментальные данные, подтверждающие гипотезу о стабильности поведения системы на примере простейшего запроса

полного сканирования

таблицы. Для

, подтверждения гипотезы в

количество строк таблицы. 0_ч- 1(г

Рис. 1 График фактического и оценочного х°Де эксперимента

количества тактов ЦПУ на выполнение сравнивались фактическое и запроса линейного поиска данных оценочное количество тактов

ЦПУ на выполнение запроса

в зависимости от количества строк таблицы. Эксперимент показал, что результаты моделирования могут быть экстраполированы и на запросы к таблице с количеством строк, превышающим текущее количество не более чем в 6 раз (в этом случае величина относительной ошибки оценки составила не более 5%). При дальнейшем увеличении количества строк величина относительной ошибки резко возрастает, но по рис. 1 видно, что линейный вид графика сохраняется, т.е. количество тактов ЦПУ определяется другим вхождением асимптотической оценки и коэффициент С требует уточнения.

Предложенная математическая модель обладает рядом новых свойств, позволяющих на основании известных свойств асимптотических оценок реляционных операций сформулировать утверждение (полную формулировку и доказательство остальных утверждений см. в диссертации):

Утверждение 5. Если - результат операции над производным отношением и/; и = 0(д1{щ)), то и Т^,,. = 0(^(п()).

Выражение (3) задает рекурсивный способ определения затрат ресурсов, неудобный для использования. Сформулированные на основе новых свойств утверждения позволили определить итерационную процедуру перехода от рекурсивного представления к замкнутому. Продемонстрируем процесс построения модели на примере расчета стоимости (затрат ресурсов) соединения посредством вложенных циклов. На рис. 2 приведен алгоритм соединения таблиц. Он состоит из двух вложенных циклов. Если обозначить стоимости операций А,В,С и Б (см. рис. 2), то точную стоимость можно вычислить по формуле:

Ч'ш.г = ЛГ^В + С + О)). (6).

Формула (6) отражает существующие подходы определения стоимости — вычислить наиболее точно на основе сложных формул. В отличие от существующих подходов в работе предлагается оценить стоимость

//Дано: Отношение внешнего цикла И

// Количество кортежей ^(Я) отношения И

II Отношение внутреннего цикла Б

// Количество кортежей отношения Э,

и участвующие в операции при условии,

// что выбран кортеж ^ отношения К

// Процедура чтения кортежа геасНир1е II

приближенно. Асимптотика О количества действий (или как мы говорим стоимости) алгоритма оценивается функцией Ч^,. = 0(Л/Й х ЛГу). Это означает, что 3 C■.xi^W|r<CxNRNs. Из

For R,=1 to Nr(R) { Rtuple = readJupIe(R,Ri) For S =1 to N5ir,(R) [

Stuple = read_luple(S,Si) If Rtuple = Stuple then ^поместить кортеж в новое отношение»

NR

А

Ns

В

С

D

для текущего количества обрабатываемых кортежей и Что позволяет, используя факт существования С, определить конкретное значение С = '¥ш,г . А

статистики выполнения запроса известно значение стоимости Ч^,

Из

}}

Рис. 2 Алгоритм соединения

посредством вложенных циклов

NrXNS

гипотеза о стабильности поведения системы позволяет использовать значения коэффициента для расчета стоимости не только при текущем количестве кортежей Ыц и но и экстраполируя результат на другое количество.

Формула (6) дает возможность оценить сокращение количества учитываемых параметров модели. В современных СУБД для расчета стоимости (6) используется порядка 15 параметров хранения и распределения данных. В то время как предлагаемая модель позволяет учесть только 2 существенных - количество кортежей отношений-операндов. Однако, в отличие от существующих способов, для доказательства адекватности модели необходима статистика выполнения запроса.

В третьей главе на основании доказанных свойств новой модели стоимости предложена методика построения и анализа стоимости выполнения запроса пользователя. Выделены этапы процессов построения и анализа, дана их краткая характеристика. Определены состав доступных

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

На основе новой замкнутой модели стоимости предложено усовершенствовать решаемые в процессе анализа плана выполнения задачи.

Во-первых, для анализа операций плана выполнения запроса предложено использовать показатель значимых параметров. Для определения значимого параметра среди всех параметров поочередно выбирается исследуемый. Значения параметров, кроме исследуемого, принимаются постоянными. Модель упрощается, как правило, принимая вид линейной функции у = кх + Ъ. Константа Ъ характеризует величину стоимости, на которую не влияет исследуемый параметр. Так что значение константы упрощенной модели является хорошей эвристикой определения степени влияния параметров на стоимость, а минимальное ее значение среди всех упрощенных моделей определяет значимый показатель.

Продемонстрируем показатель на примере. На рис. 3 приведены два варианта запроса на получение одних и тех же данных — номеров страниц, на которых встречаются 3 определенных ключевых слова (страницы и ключевые слова связаны отношение многие ко многим). По планам выполнения этих запросов были построены модели стоимости, учитывающие 3 параметра — количество страниц, ключевых слов и связей «страница-ключевое слово», и для каждой модели определен значимый показатель. Процесс определения показателя приведен в таблице рис. 3. Для рассматриваемых запросов значимые показатели разные, так что, вообще говоря, запросы нельзя сравнивать между собой. В зависимости от размеров таблиц предпочтительнее будет тот или иной вариант.

Решение 2

SELECT. « FROM t_page WHERE page_id IN (SELECT page_id

from (select count(kw_id) AS c, page_id from t_kw_on_page where kv_id IN (select kw_id from t_keyword where keyword='tag J.') or kw_id IN (select kw_id from t_keyword where keyword='tag 2') or kw_id IN (select kw_id from t_keyword where keywocd=,tag 3') GROUP BY page_id) where с > 2)!

Номер решения Модель стоимости Модель nq критерию значимости показателя Значимый показатель Коэффициент при покаэатепе

1 2 + (1.462П ♦ 7400m)"10*S г 90 п:76И.462п"1СГ5 т:16 + 7400т*10 m 7400-Ю'5

2 (49,9411 * 300m)40"5 Г601 П!3+49,94П*10 т:498 ♦ ЗООт'Ю п 49.94'10 s

Рис. 3 Пример анализа плана выполнения двух эквивалентных решений по

критерию значимости статистического показателя

Во-вторых, модели стоимости предложено использовать для исследования поведения запроса при известном прогнозе роста объемов хранимых данных. Для этого известный прогноз выражается в виде функциональной зависимости значений учитываемых параметров от времени, которая подставляется в модель стоимости. Модель упрощается, образуя параметрическую зависимость от времени. На рис. 4 приведен пример исследования поведения запросов рис. 3. Для этого был составлен прогноз роста в виде линейной функции. Получившиеся после подстановки и упрощения параметрические модели стоимости приведены в графике рис. 4. Анализ изменений стоимости показывает, что стоимость решения 2 растет более чем в 9 раз медленнее, чем стоимость решения 1. Но до некоторого момента времени решение 1 будет предпочтительнее решения 2.

Решение 1

select t_page.page_id, t_page.content from t_page

, (select count(kw_id) as cnt, page_id from t_kv_on_page where kw_id in (1,2,3) group BY page_id) T1 where Tl.cnt - 3

AND t_page.page^id = Tl.page_id/

HO.H"OCTDC J0*H4CCKI1> '-TCttltH

количество изменений

Рис. 4 Пример анализа плана выполнения двух эквивалентных решений на основе параметрических моделей стоимости

В четвертой главе изложены принципы построения системы анализа SQL запросов на основе предложенного способа оценки стоимости. В зависимости от характера нагрузки СУБД для анализа используются разные показатели в соответствии с приведенным на рис. 5 алгоритмом. Особенность алгоритма состоит в том, что для систем класса OLTP в качестве основного способа выбора запроса для настройки используется параметрические модели; для систем класса OLAP в качестве основного способа выбора запроса для настройки используются критерии значимых параметров и отношений.

Разработана схема построения программного комплекса нагрузочного тестирования SQL запросов на основе предложенного метода анализа стоимости плана выполнения (рис. 6).

Рис. 5 Алгоритм анализа моделей запросов систем различного типа

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

Отдельные запросы комплекта тестов процедуры тестирования поступают в блок выбора способа выполнения. Если для запроса комплекта теста существует модель стоимости и ее адекватность при текущих объемах хранимых данных не требует проверки, выполнение запроса не происходит, а результаты тестирования

вычисляются блоком реализации модели. В случае необходимости расчета модели либо проверки ее адекватности запрос исполняется обычным образом в блоке

реализации теста. Результаты выполнения используются для построения либо уточнения модели стоимости. Это позволяет проверить гипотезу о стабильности поведения системы и определить, не вышли ли мы за границы области адекватности модели. Исследователь контролирует результаты проверок и определяет их частоту.

Выбор стратегии,составлены* плана Создан*» среды Ра ал »о ацня геста Реал иэация т ас т а Реализацияг«ета Рвалиааци*геста Оценкараэультпо»

Апробация работы производилась на автоматизированной банковской системе ОАО КБ «Севергазбанк». Проверка сокращения сроков настройки на примере одного из отчетов АБС позволила сделать следующие выводы.

Предложенная модель стоимости позволила более полно реализовать стратегию локальной настройки за счет использования показателей анализа для ранжирования параметров и отношений на различных этапах настройки.

На первом этапе использование предложенных моделей стоимости позволило сократить время настройки за счет отказа от средств анализа, использующих алгоритмы перебора (пакет DBMS_SQLTUNE). В результате общее время настройки составило около 30 минут, в то время как настройка с использованием переборных схем может длиться до 3-4 часов.

На втором этапе проверки было проведено исследование поведения системы с ростом объема хранимых данных. Для использования модели в процессе исследования достаточно подтвердить ее адекватность на основе гипотезы о стабильности поведения системы, выполнив проверку при

максимальном значении параметров. Это позволило сократить количество проведенных нагрузочных тестов в процессе исследования с 32 до 1. Общее время исследования поведения системы сократилось со 190 минут до 110 минут.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ И ВЫВОДЫ

Основные результаты диссертационной работы сводятся к следующему.

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

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

3. На основе разработанной модели стоимости с использованием свойств О-большое асимптотик определены:

- показатели значимых параметров и отношений, позволяющие производить ранжирование операций или параметров и тем

самым усовершенствовать метод экспертных оценок за счет отказа от переборных схем анализа;

параметрические модели, позволяющие экстраполировать результаты тестовых испытаний на основе имеющихся данных на прогнозируемые объемы хранимых данных и тем самым усовершенствовать имитационные методы моделирования за счет существенного сокращения количества нагрузочных тестов. Разработаны алгоритмы выбора показателя для анализа плана выполнения SQL-запроса, особенностями которых является учет характера нагрузки СУБД: для запросов систем класса OLTP показатель строится на основе параметрических моделей и свойств затратной неизменности, для запросов систем класса OLAP используется показатель значимых отношений. Предложена и внедрена в рабочую эксплуатацию подсистема тестирования запросов АБС ОАО КБ «СЕВЕРГАЗБАНК» на основе предложенного метода анализа стоимости плана выполнения SQL-запроса и гипотезу о стабильности поведения системы, позволившая за счет совершенствования этапа реализации теста сократить время проведения процедуры тестирования на 42% при сохранении качества оценки соответствия запроса требованиям.

Основные положения диссертации опубликованы в следующих работах:

1. Борчук, JI.E. Проблемы моделирования поведения реляционных СУБД на конечном поле запросов / Л.Е. Борчук // Информационные технологии в производственных, социальных и экономических процессах (ИНФОТЕХ-2004): Сборник трудов участников четвертой международной научно-технической конференции. - Череповец, 2004.-С.120-122.

2. Борчук, Л.Е. Анализ методов решения задач оптимизации выполнения запросов в реляционных СУБД / Л.Е. Борчук // Сборник трудов участников V межвузовской конференции молодых ученых. -Череповец: ЧТУ, 2004. - С. 51-55.

3. Борчук, Л.Е. Учитываемые параметры математической модели семейства SQL - запросов на примере РСУБД Oracle / Л.Е. Борчук // Системный анализ в проектировании и управлении: Труды VII международной научно - технической конференции. - СПб: Издательство "Нестор", 2004. - С. 139-141.

4. Борчук, Л.Е. Математическая формализация глобального плана выполнения запросов реляционной СУБД / Л.Е. Борчук // Вестник ЧТУ. - Череповец, 2004. - С. 84-89.

5. Борчук, Л.Е. О модели асимптотической оценки ресурсоемкости реляционного запроса / Л.Е. Борчук, В.В. Плашенков // Материалы IX международной конференции "Интеллектуальные системы и компьютерные науки" - М: Издательство механико-математического факультета МГУ, 2006. - Т.1.4.2. С. 198-204.

6. Борчук, Л.Е. Асимптотическая модель затрат ресурсов вычислительной системы на выполнение реляционного запроса в СУБД Ingres / Л.Е. Борчук // Системный анализ в проектировании и управлении: Труды X международной научно - технической

конференции. - СПб: Издательство Политех-го университета, 2006. -Т.2. С. 231-235.

7. Борчук, JI.E. Асимптотическая модель затрат ресурсов вычислительной системы на выполнение реляционного запроса в РСУБД System R / Л.Е. Борчук // Кибернетика и высокие технологии XXI века "С&Т*2006": Материалы 7-ой международной научно-технической конференции. - Воронеж: ВГУ, 2006. - С. 363-373.

8. Борчук, JI.E. Анализ адекватности одной математической модели реляционного запроса/ JI.E. Борчук// Моделирование. Теория, методы и средства: материалы VI международной научно-практической конференции. - Новочеркасск: ЮРГТУ, 2006. - С. 50-54.

9. Борчук, JI.E. Оценка времени выполнения запроса в реляционной СУБД на основе асимптотических моделей затрат ресурсов / JI.E. Борчук, A.A. Кузьмин // Наукоемкие технологии. - 2008. - №4. - С. 61-64.

10. Борчук, Л.Е. Совершенствование процесса настройки запросов пользователей на основе асимптотических оценок затрат ресурсов / JI.E. Борчук // Информационные технологии. - 2008. - №6. - С. 6-11.

Соискатель Борчук Л.Е.

Имательский код 55Д(03). Лицензия JIP 021316 от 25.12.98 г. Подписано кпечати 04.11.10. Формат60x84/16. Объем уч.-изд. л. 1. Тираж 100 экз. Заказ № 27. г. Череповец, ул. Горького, 14. РИО ЧТУ.

Перечень условных сокращений.

Перечень условных обозначений.б

Введение.

Глава 1. Анализ факторов, обуславливающих необходимость совершенствования процесса анализа плана выполнения запроса пользователя.

1.1 Задача настройки плана выполнения БСХЪ-запроса.

1.1.1 Самонастраиваемые базы данных.

1.1.2 Метод локальной настройки запросов пользователей.

1.2 Методы анализа плана выполнения запроса.

1.2.1 Методы анализа запросов пользователей на основе моделей плана выполнения.

1.2.3 Имитационные методы анализа запросов пользователей.

1.3 Задачи, решение которых существующими методами затруднено.

1.4 Постановка центрального вопроса исследования. Формулировка научной задачи.

Выводы по главе.

Глава 2. Разработка способа оценки стоимости выполнения запроса пользователя.

2.1 Ограничение синтаксиса анализируемых запросов пользователей.

2.2 Обоснование общих требований к модели, выбор вида модели.

2.3 Формализация способа оценки стоимости выполнения реляционного запроса пользователя.

2.3.1 Выявление свойств и обоснование положений по оценке стоимости выполнения запроса пользователя.

2.3.2 Определение отношения эквивалентности на множестве запросов пользователей.

2.4 Необходимое и достаточное условия адекватности модели стоимости выполнения запроса пользователя.

Выводы по главе.

Глава 3. Разработка методики построения и анализа модели стоимости выполнения запроса пользователя.

3.1 Обоснование методики построения и анализа стоимости выполнения запроса пользователя.

3.2 Разработка математической модели стоимости выполнения реляционной операции.

3.2.1 Разработка методики построения функций асимптотической оценки.

3.2.2 Разработка методики расчета коэффициентов при непредельных значениях параметров.

3.2.3 Расчет коэффициентов и определение области адекватности модели на примере простейших операций на выборку данных. Гипотеза о стабильности поведения системы.

3.3 Разработка математической модели анализа стоимости выполнения запроса.

3.3.1 Выбор методов решения задачи анализа возможности дальнейшей оптимизации запроса.

3.3.2 Определение методов прогнозирования стоимости при изменении объемов данных.

3.4 Пример построения и анализа модели стоимости выполнения запроса пользователя.

Выводы по главе.

Глава 4. Проектирование системы анализа запросов пользователей на основе модели стоимости. Дальнейшие перспективы метода.

4.1 Разработка системы анализа SQL запросов.

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

4.1.2 Разработка алгоритмов сбора информации о параметрах функционирования.

4.1.3 Особенности построения модели запросов пользователей.

4.1.4 Разработка алгоритмов анализа модели стоимости.

4.2 Результаты экспериментальной проверки способа.

4.2.1 Общая характеристика автоматизированной банковской системы

4.2.2 Реализация системы и интерпретация результатов.

4.2.3 Оценка возможности сокращения сроков настройки запросов пользователей.

4.3 Использование полученных результатов в других областях и дальнейшие перспективы способа.

Выводы по главе.

Большинство информационных систем строится на основе реляционных СУБД [98, 99, 122], общение с которыми производится на декларативном языке запросов SQL [1-6]. Объемы хранимой информации ежегодно возрастают (по оценкам экспертов в среднем в два раза) [123,124]. На 2009 год более трети хранилищ систем по объему данных превысили один терабайт. К СУБД, а отсюда и к запросам, предъявляются требования не только реализации функциональных возможностей, но и достаточной производительности (характеризуемой временем ответа). Постоянный рост объема обрабатываемых данных, изменения реляционной модели данных, аппаратного и программного обеспечения, возрастающие требования пользователей к времени ответа системы ставят задачи повышения эффективности обработки данных и своевременных внесений изменений в систему с целью обеспечения требуемого времени ответа.

В 1970-х годах в работах М. Stonebraker, W. Kim, S. Christodoulakis, P. Seiinger, M. Astrahan, D. Chamberlm, S. Finkelstein, M. Blasgen и многих других задача выбора эффективного способа выполнения запроса была рассмотрена в виде задачи комбинаторной оптимизации [64, 97, 105, 135, 150]. Результаты прошли апробацию в рамках проекта по реализации экспериментальной реляционной СУБД System R компании IBM, явившейся прототипом большинства современных коммерческих реляционных СУБД.

Как было отмечено в работах Y. Ioannidis и S. Christodoulakis [175], одной из основных проблем выбора оптимального способа выполнения является обеспечение адекватности оценок стоимости выполнения запроса вследствие так называемого эффекта распространения ошибки. Работы по уточнению оценок стоимости ведутся и по сей день (здесь можно выделить работы V. Markl и Y. Ioannidis [176,177,180,185]), однако универсальность реляционных СУБД и эффект распространения ошибки не позволяет надеяться на всеобъемлющее решение проблемы.

В работах Т. Sellis, U. Chakravarthy, J. Minker, К. Satoh, M. Jarke и др. [70,107,111,121,126,129,131,136,137] была отмечена возможность увеличения эффективности выполнения набора запросов за счет поиска глобального оптимума. Стратегия» поиска может учитывать как историю выполнения запросов (статическая глобальная оптимизация), так и факт их одновременного выполнения (оптимизация набора запросов).

Автоматическая реализация стратегии поиска была положена в основу самонастраиваемых баз данных - развитой системе средств автоматической настройки компонент и структур базы данных, создание которых, в первую очередь, связано с работами М. Stonebraker, S. Chaudhuri, G. Shapiro и V. Markl [187,188,196,197,199]. На сегодняшний день самонастраиваемые базы данных содержат инфраструктуру средств автоматической настройки, средства записи и воспроизведения рабочей нагрузки, средства выработки рекомендаций по построению индексов, материализованных представлений и разбиению на секции по известной рабочей нагрузке, средства автоматического управления сбором статистики и самонастраиваемые гистограммы (оптимизаторы).

Несмотря на то, что удалось достичь значительных результатов с использованием средств автоматической настройки, исчерпывающе решить задачу настройки, как отмечают в своих работах Волкер Маркл и Сураджит Чаудхури, одними автоматическими средствами на сегодняшний день не представляется возможным, так что задача совершенствования неавтоматических средств настройки по-прежнему остается актуальной.

Разработка новых средств настройки осложнена постоянным совершенствованием модели стоимостного оптимизатора путем учета новых параметров, что ведет к усложнению методов анализа модели и появлению новых ограничений на исследуемое поведение системы. В этой связи снова становится актуальным предложенный в 1974 году М. Stonebaker [197] подход использования для настройки внешней по отношению к оптимизатору модели стоимости, позволяющей за счет новых свойств усовершенствовать процесс настройки.

В 2005 году Б. Новиков предложил производить настройку методом локальной настройки запросов, учитывая историю выполнения запросов [50].

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

Цели анализа плана выполнения запроса на каждом из этапов различны.

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

Во-вторых, план выполнения может анализироваться на предмет соответствия его стоимости требованиям при некоторых (возможно, прогнозируемых) объемах данных. В настоящее время такая оценка выполняется на основе отечественных практик тестовых аттестационных испытаний ГОСТ [12-16] или зарубежных рекомендаций проведения нагрузочного тестирования [1-12]. Основной сложностью использования методов тестирования является необходимость получения набора данных для теста. Как правило, в момент анализа запроса требуемых данных в системе нет - они появятся в процессе дальнейшей эксплуатации системы.

Актуальность работы объясняется постоянным ростом объемов обрабатываемых данных, изменениями реляционных моделей данных, аппаратного и программного обеспечения при сохранении требований к времени ответа на запрос пользователя, и недостаточной теоретической исследованностью вопросов анализа плана выполнения запроса в процессе настройки времени ответа системы.

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

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

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

Таким образом, научная задача состоит в разработке метода анализа стоимости выполнения запроса, позволяющего повысить оперативность настройки с обеспечением требуемого качества показателей выполнения 8С>Ь-запросов пользователей.

Объектом исследования является процесс настройки системы баз данных.

Предметом исследования являются стоимость выполнения запроса пользователя.

Целью диссертационной работы является сокращение сроков настройки системы баз данных на основе разработки метода анализа плана выполнения запроса, позволяющего определить стоимость выполнения запроса от параметров системы.

Исходя из цели работы, с учетом анализа проблемы и существующих методов в диссертации решались следующие основные задачи:

- обоснование необходимости совершенствования процесса анализа планов выполнения запросов пользователей;

- анализ доступной статистической информации, выделение значимой для достижения цели исследования;

- построение и анализ свойств модели исполнения системы запросов с учетом статистической информации;

- разработка способов обнаружения значимых с точки зрения используемых ресурсов подмножеств запросов или параметров и прогнозирования стоимости при изменении объема данных;

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

Научная новизна результатов работы состоит в следующем:

- разработан способ построения математической модели на основе свойств 0-болыпое асимптотик стоимости выполнения» SQL запросов в зависимости от значимых параметров системы;

- даны рекомендации по реализации и применению предложенной модели стоимости путем преобразования ее к замкнутому виду и использованию гипотезы о стабильности поведения системы.

Практическая ценность диссертационной работы состоит в том, что:

- даны практические рекомендации по определению адекватности математической модели на основе свойств О-болыпое асимптотических оценок и определению границ области изменения параметров, в которых выполняется предположение о стабильности поведения системы;

- разработана методика построения с использованием свойств О-болыпое асимптотик и анализа модели стоимости выполнения SQL запроса и даны практические рекомендации по расчету коэффициентов модели;

- разработаны алгоритмы выбора показателей для анализа математической модели, учитывающие особенности предметной области и цели настройки.

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

ОАО КБ «СЕВЕРГАЗБАНК», а результаты модернизации- внедрены в эксплуатацию.

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

Достоверность полученных результатов обеспечивается корректным использованием математического аппарата, а также современных методов и алгоритмов, что подтверждается практическими испытаниями. На примере автоматизированной банковской системы (АБС)

ОАО КБ «СЕВЕРГАЗБАНК» усовершенствован процесс настройки системы баз данных путем модернизации подсистемы тестирования запросов, используя предложенный способ оценки стоимости и гипотезу о стабильности поведения системы. Результаты усовершенствования внедрены в рабочую эксплуатацию в АБС ОАО КБ «СЕВЕРГАЗБАНК».

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на конференциях:

- 9-й международной конференции "Интеллектуальные системы и компьютерные науки" (Москва, МГУ, 23-27 октября 2006 г.);

- 7-ой международной научно - технической конференции «Кибернетика и высокие технологии XXI века» С&Т^ООб. (Воронеж, 16-18 мая 2006 г.); ^

- 6-ой международной научно - практической конференции "Моделирование. Теория, методы и средства ". (Новочеркасск, ЮРГТУ, 7 апреля 2006 г.);

- 10-ой международной научно - технической конференции "Системный анализ в проектировании и управлении". (Санкт-Петербург, СПбГПУ, 28 июня - 10 июля 2006 г.).

Основные положения диссертации опубликованы в двух научных журналах, рекомендованных ВАК к публикации:

- Борчук J1.E., Кузьмин A.A. Оценка времени выполнения запроса в реляционной СУБД на основе асимптотических моделей затрат ресурсов// Наукоемкие технологии. - 2008. - №4. - С. 61-64.;

- Борчук JI.E. Совершенствование процесса настройки запросов пользователей на основе асимптотических оценок затрат ресурсов// Информационные технологии. - 2008. - №6. - С. 6-11. Публикации. По теме диссертации опубликовано 10 печатных работ, в том числе 6 статей и 4 тезиса докладов. На защиту выносится:

- способ построения модели на основе свойств О-болыпое асимптотических оценок стоимости выполнения SQL запросов в зависимости от значимых параметров системы;

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

Структура и объем диссертации. Диссертационная работа состоит из списка сокращений, введения, четырех глав, заключения, библиографического списка из 195 наименований и приложений. Общий объем диссертации - 274 страницы машинописного текста, в том числе: 182 страницы основного текста и 92 страницы приложений, 35 рисунков, 11 таблиц.

Последовательность решения поставленных в исследовании задач определила композиционное построение работы.

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

Во второй главе предложен способ построения математической модели стоимости на получение отношения на основе известных асимптотических моделей стоимости выполнения операций. Исследованы свойства модели на основе известных свойств асимптотических оценок и предположения о линейности программной реализации операций, что позволило сформулировать итерационный путь построения модели. Сформулированы необходимое и достаточное условия адекватности модели исходя из особенностей локального метода настройки запросов.

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

В четвертой главе изложены принципы построения системы анализа SQL запросов на основе предложенного метода анализа плана выполнения. В зависимости от характера нагрузки СУБД для анализа могут быть использованы разные показатели в соответствии с приведенным в тексте алгоритмом. Для систем класса OLTP в качестве основного способа выбора запроса для настройки может быть использовано свойство затратной неизменности. Для систем класса OLAP в качестве основного способа выбора запроса для настройки могут быть использованы критерии значимых параметров и отношений. Приведена схема построения программного комплекса нагрузочного тестирования SQL запросов на основе предложенного метода анализа плана выполнения и результаты экспериментального исследования модернизированной подсистемы нагрузочного тестирования АБС ОАО КБ «СЕВЕРГАЗБАНК».

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

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

Выводы по главе

В главе изложены основные принципы построения системы анализа SQL запросов на основе моделей стоимости, используя свойства О-болымос асимптотик. В зависимости от характера нагрузки СУБД для анализа могут быть использованы разные показатели в соответствии с приведенным в тексте алгоритмом. Для систем класса OLTP в качестве основного способа выбора запроса для настройки может быть использовано свойство затратной неизменности. Для систем класса OLAP в качестве основного способа выбора запроса для настройки могут быть использованы критерии значимых параметров и отношений.

Приведена схема построения программного комплекса нагрузочного тестирования SQL запросов на основе предложенной модели стоимости. Использование моделей стоимости в процессе проведения нагрузочного тестирования позволило уменьшить время проведения процедуры за счет сокращения количества исполняемых комплексов тестов. В процессе исполнения отдельные комплекты тестов поступают на предобработку блоку выбора способа выполнения. Если модель существует и ее актуальность в данной точке не требует проверки, выполнение комплекса тестов не происходит, а результаты тестирования вычисляются на основе моделей. Программный комплекс был внедрен в эксплуатацию в ОАО КБ "Севергазбанк", о чем свидетельствует акт внедрения.

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

ЗАКЛЮЧЕНИЕ

Исследование современной ситуации в области настройки систем баз данных и анализ показателей эффективности выполнения запросов позволили выдвинуть гипотезу о новом методе оценки показателей эффективности на основе моделей стоимости, используя свойства О-болыпое асимптотик.

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

Для решения названных задач были предложены и обоснованы следующие положения:

1. В качестве учитываемых параметров модели следует выбирать количественные характеристики объемов обрабатываемых данных, связанные с параметрами предметной области, а не с параметрами хранения данных. Выбор учитываемых параметров можно совместить с итерационной процедурой построения замкнутой модели стоимости и выполнять его в процессе предметной интерпретации операции плана выполнения запроса.

2. Стоимость выполнения операции плана выполнения запроса функционально зависят от количественных характеристик объемов обрабатываемых данных. Для вычисления функции зависимости используются свойства О-болыпое асимптотик и статистика выполнения запроса.

3. Построение замкнутой модели стоимости выполнения запроса состоит в последовательном вычислении функций зависимостей стоимости выполнения операции от учитываемых параметров в порядке следования операций в плане выполнения запроса.

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

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

6. Совершенствование системы нагрузочного тестирования запросов пользователей связано с сокращения количества исполняемых комплектов тестов. В процессе проведения тестирования комплект теста поступает на предобработку блоку выбора способа выполнения. Если модель существует и ее актуальность в данной точке не требует проверки, выполнение комплекса тестов не происходит, а результаты тестирования вычисляются на основе моделей.

Реализуя указанные положения, в диссертационной работе достигнуты следующие основные научные и практические результаты:

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

2. В интересах сокращения количества учитываемых параметров разработан способ построения модели стоимости выполнения запроса с использованием свойств 0-большое асимптотик, отличающийся от известных возможностью перейти от рекурсивного способа вычисления к замкнутому в результате выполнения предлагаемой итерационной процедуры.

3. На основе разработанной модели стоимости с использованием свойств О-болыпое асимптотик определены: показатели значимых параметров и отношений, позволяющие производить ранжирование операций или параметров и тем самым усовершенствовать метод экспертных оценок за счет отказа от переборных схем анализа; параметрические модели, позволяющие экстраполировать результаты тестовых испытаний на основе имеющихся данных на прогнозируемые объемы хранимых данных и тем самым усовершенствовать имитационные методы моделирования за счет существенного сокращения количества нагрузочных тестов.

4. Разработаны алгоритмы выбора показателя для анализа SQL-запроса, особенностями которых является учет характера нагрузки СУБД: для запросов систем класса OLTP показатель строится на основе параметрических моделей и свойств затратной неизменности, для запросов систем класса OLAP используется показатель значимых отношений.

5. Предложена и внедрена в рабочую эксплуатацию подсистема тестирования запросов АБС ОАО КБ «СЕВЕРГАЗБАНК» на основе предложенного метода оценок стоимости выполнения SQL-запросов и гипотезу о стабильности поведения системы, позволившая за счет совершенствования этапа реализации теста сократить время проведения процедуры тестирования на 42% при сохранении качества оценки соответствия запроса требованиям.

Внедрение результатов данной работы на практике позволит сократить сроки настройки плана выполнения БС^Ь-запроса и вместе с тем снизит требования к инженерной квалификации исследователя. Это, в свою очередь, приведет к экономическому эффекту снижения стоимости поддержки существующих систем и снижению стоимости поддержки и сроков создания новых реляционных систем обработки данных за счет более эффективного использования трудовых и аппаратных ресурсов предприятия. Более точное прогнозирование поведения системы позволит снизить время простоя за счет своевременного проведения настройки и регламентных работ по модификации или замене оборудования.

1. 1.O/IEC 9075-1:2008 Information technology - Database languages -SQL - Part 1: Framework (SQL/Framework) Электронный ресурс. // URL: http://www.iso.org (дата обращения: 01.12.2008)

2. ISO/IEC 9075-2:2008 Information technology Database languages -SQL - Part 2: Foundation (SQL/Foundation) Электронный ресурс. // URL: http://www.iso.org (дата обращения: 01.12.2008)

3. ISO/IEC 9075-4:2008 Information technology Database languages -SQL - Part 4: Persistent Stored Modules (SQL/PSM) Электронный ресурс. // URL: http://www.iso.org (дата обращения: 01.12.2008)

4. ISO/IEC 9075-10:2008 Information technology Database languages -SQL - Part 10: Object Language Bindings (SQL/OLB) Электронный ресурс. // URL: http://www.iso.org (дата обращения: 01.12.2008)

5. ISO/IEC 9075-11:2008 Information technology Database languages -SQL - Part 11: Information and Definition Schemas (SQL/Schemata) Электронный ресурс. // URL: http://www.iso.org (дата обращения: 01.12.2008)

6. ISO/IEC 9075-14:2008 Information technology Database languages -SQL - Part 14: XML-Related Specifications (SQL/XML) Электронный ресурс. // URL: http://www.iso.org (дата обращения: 01.12.2008)

7. ТРС Benchmark С Электронный ресурс. // URL: http://www.tpc.org (дата обращения: 01.12.2008)

8. ТРС Benchmark H Электронный ресурс. // URL: http://www.tpc.org (дата обращения: 01.12.2008)

9. BS 7925-1:1998 Software testing. Vocabulary Электронный ресурс. // URL: http://www.testingstandards.co.uk/ (дата обращения: 01.12.2008)

10. BS 7925-2:1998 Software testing. Software component testing Электронный ресурс. // URL: http://www.testingstandards.co.uk/ (дата обращения: 01.12.2008)

11. IEEE 829-1998 standard for software test documentation Электронный ресурс. // URL: http://www.ieee.org / (дата обращения: 01.12.2008)

12. ГОСТ P ИСО/МЭК 9594-8-98 Информационная технология. Взаимосвязь открытых систем. Справочник. Часть 8. Основы аутентификации. М.: Изд-во стандартов, 1998.

13. ГОСТ Р ИСО'МЭК 9646-1-93 Информационная технология. Взаимосвязь открытых систем. Методология и основы аттестационного тестирования. Часть 1. Общие положения. М.: Изд-во стандартов, 1998.

14. ГОСТ Р ИСО'МЭК 9646-2-93 Информационная технология. Взаимосвязь открытых систем. Методология и основы аттестационного тестирования. Часть 2. Спецификация комплекта абстрактных тестов. -М.: Изд-во стандартов, 1998.

15. ГОСТ Р ИСО'МЭК 9646-4-93 Информационная технология. Взаимосвязь открытых систем. Методология и основы аттестационного тестирования. Часть 4. Реализация тестов. — М.: Изд-во стандартов, 1998.

16. Современные проблемы вычислительной математики и математического моделирования: в 2 т. / Ин-т вычисл. математики. -М.: Наука, 2005. Т. 1. : Вычислительная математика / отв. ред. Н.С. Бахвалов, В.В. Воеводин. - 343 с.

17. Аткинсон, М. Манифест систем объектно-ориентированных баз данных / М. Аткинсон и др. // Системы управления базами данных. -1995. №4.

18. Борчук, JI.E. Анализ адекватности одной математической модели реляционного запроса / JI.E. Борчук // Моделирование. Теория, методы и средства: Материалы VI международной научно -практической конференции. Новочеркасск: ЮРГТУ, 2006. - С. 5054.

19. Борчук, JI.E. Анализ методов решения задач оптимизации выполнения запросов в реляционных СУБД / J1.E. Борчук // Сборник трудов участников V межвузовской конференции молодых ученых. -Череповец: ЧГУ, 2004. С. 51-55.

20. Борчук, J1.E. Математическая формализация глобального плана выполнения запросов реляционной СУБД / JI.E. Борчук // Вестник ЧГУ. Череповец, 2004. - С. 84-89.

21. Борчук, JI.E. Оценка времени выполнения запроса в реляционной СУБД на основе асимптотических моделей затрат ресурсов / JI.E. Борчук, A.A. Кузьмин // Наукоемкие технологии. 2008. - №4. - С. 61-64.

22. Борчук, JI.E. Совершенствование процесса настройки запросов пользователей на основе асимптотических оценок затрат ресурсов / JI.E. Борчук // Информационные технологии. 2008. - №6. - С. 6-11.

23. Воеводин, В.В. Параллельные вычисления / В.В. Воеводин, Вл.В. Воеводин. СПб.: БХВ-Петербург, 2002. - 520 с.

24. Вьейра, P. SQL Server 2000. Программирование / P. Вьейра: в 2 т. -M: Бином, 2004. 1544 с.

25. Гарсия, М. Ф. Microsoft SQL Server 2000. Справочник администратора / M. Ф. Гарсия, Дж. Рединг, Э. Уолен, С. А. ДеЛюк. -М: Эком, 2001.-976 с.

26. Гарсиа-Молина, Г. Системы баз данных. Полный курс / Г. Гарсиа-Молина, Д. Ульман, Д. Уидом: пер. с англ. М.: Издательский дом "Вильяме", 2004.

27. Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. М.: Мир, 1982.

28. Дейт, К. Дж. Введение в системы баз данных, 8-е издание / К. Дж. Дейт: пер. с англ. М.: Издательский дом "Вильяме", 2005. — 1327 с.

29. Диго, С. М. Базы данных: проектирование и использование. Учебник / С. М. Диго. М.: Финансы и статистика, 2005.

30. Кайт, Т. Оракл для профессионалов / Т. Кайт: пер. с англ.: в 2 т. -СПб.: ООО "ДиасофтЮП", 2003. 1230 с.

31. Конноли, Т. Базы данных: проектирование, реализация и сопровождение. Теория и практика, 2-е изд / Т. Конноли и др. М.: Издательский дом "Вильяме", 2000. - 1221 с.

32. Кормен, Т. Алгоритмы: построение и анализ / Т. Кормен. М.: МЦНМО, 2004.

33. Кузнецов, С.Д. Базы данных: языки и модели. Учебник / С.Д. Кузнецов. М.: ООО "Бином-Пресс", 2008. - 720 с.

34. Кузнецов, С.Д. Введение в СУБД / С.Д. Кузнецов // Системы управления базами данных. 1995. - №1. - С. 119-127.

35. Кузнецов, С.Д. Введение в СУБД / С.Д. Кузнецов // Системы управления базами данных. 1995. - №1. - С. 116-124.

36. Кузнецов, С.Д. Введение в СУБД / С.Д. Кузнецов // Системы управления базами данных. 1996. - №4. - С. 98-119.

37. Линзенбардт, M. А. Администрирование SQL Server 2000. Полное руководство / M. А. Линзенбардт, М. Ш. Стиглер. М: Издательская группа BHV, 2000. - 400 с.

38. Марков, А.С. Базы данных. Введение в теорию и методологию / А.С. Марков, К.Ю. Лисовский. М.: Финансы и статистика, 2004.

39. Мамаев, Е. Microsoft SQL Server 7 / Е. Мамаев, А. Вишневский. -СПб: Питер, 2000. 896 с.

40. Миллсап, К. Oracle. Оптимизация производительности / К. Миллсап, Д. Хольт: пер. с англ. СПб.: Символ-Плюс, 2006. -464 с.

41. Моисеенко, С.И. Трансляция операторов реляционной алгебры в SQL-операторы / С.И. Моисеенко, В.А. Левченко // Вестник ДГУ. -2005. -№1(23).

42. Новиков, Б.А. Настройка приложений баз данных / Б.А. Новиков, Г.Р. Домбровская. СПб: БХВ-Петербург, 2006. - 240 с.

43. Смирнов, С.Н. Работаем с Oracle: Учебное пособие / С.Н. Смирнов, И.С. Задворьев М.: Гелиос АРВ, 2002. - 496 с.

44. Спирли, Э. Корпоративные хранилища данных. Планирование, разработка, реализация. / Э. Спирли: пер. с англ.: Т. 1. М.: Издательский дом "Вильяме", 2001.

45. Стулов, А. Особенности построения информационных хранилищ / А. Стулов // Открытые системы. 2003. - №4.

46. Тоу, Д. Настройка SQL. Для профессионалов / Д. Тоу. СПб.: Питер, 2004. - 333 с.

47. Хоббс, Л. Oracle 9iR2: Разработка и эксплуатация хранилищ баз данных / Л. Хоббс, С. Хилсон, Ш. Лоуенд: пер. с англ. М.: КУДИЦ-ОБРАЗ, 2004. - 592 с.

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

49. Чемберлин, Д. Анатомия объектно-реляционных баз данных / Д.

50. Чемберлин // Системы управления базами данных. 1998. - №1. 58.Чемберлин, Д. Анатомия объектно-реляционных баз данных / Д.

51. Чемберлин // Системы управления базами данных. 1998. - №2. 59.Чен, П.П. Модель 'сущность-связь' - шаг к единому представлению данных / П.П. Чен // Системы управления базами данных. - 1995. -№3.

52. Шнайдер, Роберт Д. Microsoft SQL Server. Проектирование высокопроизводительных баз данных / Роберт Д. Шнайдер. М: Лори, 1998. - 366 с.

53. Шнитман, В.З. Серверы баз данных: проблемы оценки конфигурации системы / В.З. Шнитман // Системы управления базами данных. 1996. — №5.

54. Шнитман, В.З. Серверы баз данных: проблемы оценки конфигурации системы / В.З. Шнитман // Системы управления базами данных. 1996. - №6.

55. Abitboul, S. DBMSs for Supporting New Applications / S. Abitboul, M. Scholl, G. Gardarin, Simon E. Towards // Proc. 12th Int. Conf. Very Large Data Bases, Kyoto, Japan, Aug. 25-28, 1986. Los Altos, Calif., 1986. pp. 423-435.

56. Astrahan, M.M. Implementation of a structured English query language / M.M. Astrahan, D.S. Chamberlin // Commun. ACM 1975, 10 (Oct.), pp. 580-588.

57. Astrahan, M.M. Counting Unique Values of an Attribute without Sorting / M.M. Astrahan, M. Schkolnick, K.Y. Whang // Inf. Syst.1987. 12, N 1. pp. 11-16.

58. Bell, D.A. Clustering Related Tuples in Databases / D.A. Bell, F.J. McErlean, P.M. Stewart, W.A. Arbuckle // Comput. J. 1988.31, N 3. pp. 253-257.

59. Bergamaschi, S. Choice of the Optimal Number of Blocks for Data Access by an Index / S. Bergamaschi, M.R. Scales // Inf. Syst.1986. 11, N 3. pp. 199-209.

60. Bloom, B.H. Space/Time Trade-offs in Hash Coding with Allowable Errors / B.H. Bloom // Commun. ACM, 1970, 13, N 7, pp. 422-426.

61. Chacravarthy, U.S. Multiple Query Processing in Deductive Databases Using Query Graphs / U.S. Chacravarthy, J. Minker // Proc. 12th Int. Conf. Very Large Data Bases, Kyoto, Japan, Aug. 1986. Los Altos, Calif., 1986. pp. 384-394.

62. Chacravarthy, U.S. Semantic Query Optimization in Expert Systems and Database Systems / U.S. Chakravarthy, D.H. Fishman, J. Minker // Expert Database Syst.: Proc. 1st Int. Workshop, Menlo Park, Calif., Feb. 1986. New York, 1986. pp. 326-341.

63. Chacravarthy, U.S. Semantic Query Optimization: Additional Constraints / U.S. Chacravarthy, J. Grant, J. Minker // Proc. 1st Int. Conf. Expert Database Syst., Charleston, S.C., Apr. 1986. New York, 1986. pp. 259270.

64. Cheiney, J.-P. A Functional Clustering Method for Optimal Access to Complex Domains in a Relational DBMS / J.-P. Cheiney, G. Kierman // Proc. 4th Int. Conf. Data Eng., Los Angeles, Calif., Feb. 1988. Washington, D.C., 1988. pp. 394-401.

65. Christodoulakis, S. Estimating Record Selectivities / S. Christodoulakis // Inf. Syst. 1983. 8, N 2. pp. 105-115.

66. Christodoulakis, S. Estimating Block Selectivities / S. Christodoulakis // Inf. Syst. 1984. 9, N 1. pp. 69-79.

67. Christodoulakis, S. Implication of Certain Assumtions in Database Performance Evaluation / S. Christodoulakis // ACM Trans. Database Syst. 1984. 9, N 2. pp. 163-186.

68. Codd, E.F. Extending the Relational Database Model to Capture More Meaning / E.F. Codd // IBM Research Report RJ2599 (August 6th, 1979). Republished in ACM Transactions on Database Systems 4(4), December 1979.

69. Codd, E.F. A Data Sublanguage Founded on the Relational Calculus / E.F. Codd // IBM Research Report RJ893 (July 26th, 1971). -Republished in Proc. 1971 ACM SIGFIDET Workshop on Data Description, Access and Control, San Diego, November 1971.

70. Codd, E.F. Recent Investigations into Relational Data Base Systems / E.F. Codd // IBM Research Report RJ1385 (April 13rd, 1974). -Republished in Proc. 1974 Congress (Stockholm, 1974). New York, N.Y.: North-Holland, 1974.

71. Codd, E.F. Relational Database: A Practical Foundation for Productivity / E.F. Codd // IBM Research Report RJ3339 (December 21st, 1981). -Republished in CACM 25(2), February 1982.

72. Codd, E.F. A Relational Model of Data for Large Shared Data Banks / E.F. Codd // CACM 13(6), June 1970. Republished in Milestones of Research Selected Papers 1958-1982 (CACM 25th Anniversary Issue), CACM 26(1), January 1983.

73. Codd, E.F. Is Your DBMS Really Relational?; Does Your DBMS Run By The Rules? / E.F. Codd // Computerworld (October 14th, 1985; October 21st, 1985).

74. Codd, E.F. The Relational Model For Database Management Version 2 / E.F. Codd. Reading, Mass.: Addison-Wesley, 1990.

75. Date, C.J. Foundation for Object/Relational Databases: The Third Manifesto (2d edition) / C.J. Date, H. Darwen Reading, Mass.: Addis on-Wesley, 2000.

76. Date, C.J. A Critique of the SQL Database Language / C.J. Date // ACM SIGMOD Record 14, No. 3 (November 1984).

77. Date, C.J. A Guide to the SQL Standard. Fourth edition / C.J. Date, H. Darwen. Addison-Wesley Longman, 1997.

78. Demolombe, R. Estimation of the Number of Tuples Satisfying a Query Expressed in Preducate Calculus Language / R. Demolombe // Proc. 6th Int. Conf. Very Large Data Bases, Montreal, Oct. 1980. New York, 1980. pp. 55-63.

79. Desai, B.C. Composite Index in DDBMS / B.C. Desai, P. Goyal, F. Sardi //J. of Syst. and Software. 1988. 8, N 2. pp. 105-120.

80. DeWitt, D.J. Implementation Techniques for Main Memory Database Systems / D.J. DeWitt, R.H. Katz, F. Olken, L.D. Shapiro, M.R. Stonebraker, D. Wood // Proc. ACM SIGMOD Int. Conf. Manag. Data, Boston, Mass., June 18-21, 1984. New York, 1984, pp. 1-8.

81. DeWitt, D. Multiprocessor Hash-Based Join Algorithms / D. DeWitt, R. Gerber // Proc. 11th Int. Conf. Very Large Data Bases, Stockholm, Sweden, Aug. 1985. Palo Alto, Calif., 1985. pp. 151-164.

82. Fang, M.T. The Idea of De-Clustering and Its Applications / M.T. Fang, R.C.T. Lee, C.C. Chang // Proc. 12th Int. Conf. Very Large Data Bases, Kyoto, Japan, Aug. 25-28, 1986. Los Altos, Calif., 1986. pp. 181-188.

83. Finkelstein, S. Physical Database Design for Relational Databases / S. Finkelstein, M. Schkolnick, P. Tiberio // ACM Trans. Database Syst. 1988. 13, N l.pp. 91-128.

84. Freeze, Wayne S. The SQL Programmer's Reference / Wayne S. Freeze.- Ventana Communications Group Inc., 1998. 298 S.

85. Gotlieb, L. R. Computing joins of relations / L.R. Gotlieb // In Proceedings of the ACM-SIGMOD International Conference on Management of Data (San Jose, Calif., May 14-16). ACM, New York, pp. 55-63.

86. Gray, J. Scientific Data Management in the Coming Decade / Jim Gray, David T. Liu, Maria Nieto-Santisteban h ap. // SIGMOD Record. 2005.- Vol. 34, №4.

87. Gray, J. The Lowell Report / Jim Gray, Hans Schek, Michael Stonebraker, Jeff Ullman // Proceedings of the 2003 ACM SIGMOD International Conference on Management Of Data.

88. Grazzini, E. A Physical Structure for Efficient Processing of Relational Queries / E. Grazzini, R. Pinzani, F. Pippolini // Found. Data Organ. Proc. Int. Conf., Kyoto, May 22-24, 1985. New York; London, 1987. pp. 501-514.

89. Hagmann, R.B. An Observation on Database Buffering Performance Metrics / R.B. Hagmann // Proc. 12th Int.Conf. Very Large Data Bases, Kyoto, Japan, Aug. 1986. Los Altos, Calif., 1986. pp. 289-293.

90. Hsu, M. Concurrent Operations in Extendible Hashing / M. Hsu, W.-P. Yang // Proc. 12th Int. Conf. Very Large Data Bases, Kyoto, Japan, Aug. 25-28, 1986. Los Altos, Calif., 1986. pp. 241-247.

91. Inmon, W. Building the Data Warehouse / W. Inmon. John Willey & Sons, New York, 1992.

92. Ioannidis, Y. The History of Histograms (abridged) / Y. Ioannidis // Proceedings of 29th International Conference on Very Large Data Bases, September 9-12, 2003, Berlin, Germany.

93. Jarke, M. Query Optimization in Database Systems / M. Jarke, J. Koch//Computing Surveys, Vol. 16, No. 2, June 1984.

94. Jarke, M. Range Nesting: A Fast Method to Evaluate Quantified Queries / M. Jarke, J. Koch // Proc. ACM SIGMOD Int. Conf. Manag. Data, San Jose, Calif., May 23-26, 1983. New York, 1983. pp. 198-206.

95. Jarke, M. Common Subexpression Isolation in Multiple Query Optimization / M. Jarke // Query Processing in Database Systems. New York: Springer. 1985. pp. 191-205.

96. Kiessling, W. Access Path Selection in Databases with Intelligent Disc Subsystems / W. Kiessling // Comput. J. 1988. 31, N 1. pp. 41-50.

97. King, J.J. QUIST: A System for Semantic Query Optimization in Relational Databases / J.J. King // Proc. 7th Int. Conf. Very Large Data Bases, Cannes, France, Sept. 3-11, 1981. New York, 1981. pp. 510-517.

98. Kim, W. A New Way to Compute the Product and Join of Relations / W. Kim // Proc. ACM SIGMOD Int. Conf. Manag. Data, New Work, May 1980. New York, 1980, pp. 178-187.

99. Kim, W. Global Optimization of Relational Queries: A First Step / W. Kim // Query Processing in Database Systems. New York: Springer. 1985. pp. 206-216.

100. Kim, W. On Optimizing an SQL-Like Nested Query / W. Kim // ACM Trans. Database Syst. 7, No. 3 (1982).

101. Kim W. Architecture of the ORION Next-Generation Database System / W. Kim, J.F. Garza, N. Ballou, D. Woelk // TKDE 2, No.l (1990).

102. Lee, S. Semantic Query Optimization in Recursive Databases / S. Lee, J. Han // 4th Int. Conf. Data Eng., West Berlin, Sept. 13-15, 1988. New York, 1988. pp. 444-451.

103. Lewis, J. Cost-Based Oracle Fundamentals / J. Lewis Apress, 2006. - 506 S.

104. Lorie, R.A. Supporting Complex Objects in a Relational System for Engineering Databases / R.A. Lorie, W. Kim, D. McNabb, W. Plouffe, A. Meier // Query Processing in Database Systems. New York e.a.: Springer (1985).

105. Luk, W.S. On Estimating Block Accesses in Database Organization / W.S. Luk// Commun. ACM. 1983. 26, N 11. pp. 945-947.

106. Makinouchi, A. The Optimization Strategy for Query Evaluation in RDB/V1 / A. Makinouchi, M. Tezuka, H. Kitakami, S. Adachi // Proc. 7th Int. Conf. Very Large Data Bases, Cannes, France, Sept. 3-11, 1981. New York, 1981. pp. 518-529.

107. Merrett, T.H. Why Sort/Merge Gives the Best Implementation of the Natural Join / T.H. Merrett // ACM SIGMOD Record. 1983, 13, N 2, pp. 40-51.

108. Miyao, J. Optimization of Multiple Queries in Relational Database Systems / J. Miyao, K. Tominaga, T. Kikuno, N. Yoshida // Syst. and Comput. in Japan. 1988. 19, N 4. pp. 56-65.

109. Olofson, Carl W. Worldwide RDBMS Software 2006-2010 Forecast / Carl W. Olofson // Отчеты IDC (International Data Corporation),- W201777.

110. Olofson, Carl W. Worldwide RDBMS 2005 Vendor Shares: Preliminary Results for the Top 5 Vendors Show Continued Growth / Carl W. Olofson // Отчеты IDC (International Data Corporation), W201692

111. Olofson, Carl W. Worldwide Relational Database Management Systems 2005-2009 Forecast: An Initial View / Carl W. Olofson // Отчеты ЮС (International Data Corporation), W33078.

112. Ong, J. Implementation of Data Abstraction in the Relational Database System Ingres / J. Ong, D. Fogg, M. Stonebraker // ACM SIGMOD Record 14, No. 1 (March 1984).

113. Park, J. Using Common Subexpressions to Optimize Multiple Queries / J. Park, A. Segev // 4th Int. Conf. Data Eng., West Berlin, Sept. 13-15, 1988. New York, 1988. pp. 311-319.

114. Piatetski-Shapiro, G. Accurate Estimation of the Number of Tuples Satisfying a Condition / G. Piatetski-Shapiro, C. Connel // ACM SIGMOD Record. 1984. 19, N 2. pp. 256-276.

115. Pramanik, S. Optimizing the Cost of Relational Queries Using Partial Relation Schemes / S. Pramanik, F. Fotouhi // Inf. Syst. 1988. 13, N 1. pp. 71-79.

116. Rosental, A. Anatomy of a Modular Multiple Query Optimizer / A. Rosental, U. Chakravarthy // Proc. 14th Int. Conf. Very Large Data Bases, Los Angeles, Calif., Aug.-Sept. 1988. Los Altos, Calif., 1988. pp. 230-239.

117. Rowe, N.C. Absolute Bounds on Set Intersection and Union Sizes from Distribution Information / N.C. Rowe // IEEE Trans. Software Eng. 1988. 14, N 7. pp. 1033-1048.

118. Satoh, K. Local and Global Query Optimization Mechanisms for Relational Databases / K. Satoh, M. Tsuchida, F. Nakamura, K. Oomachi // Proc. 11th Int. Conf. Very Large Databases, Stockholm, Sweden, Aug. 1985. Los Altos, Calif., 1985. pp. 405-417.

119. Shee, R. Oracle Wait Interface: A Practical Guide to Performance Diagnostics & Tuning / R. Shee, K. Deshpande, K. Gopalakrishnan. -McGraw-Hill/Osborne, 2004. 350 S.

120. Shenoy, S.T. A System for Senantic Query Optimization / S.T. Shenoy, Z.M. Ozsoyoglu // Proc. ACM SIGMOD Int. Conf. Manag. Data, San Francisco, Calif., May 1987. New York, 1987. pp. 181-195.

121. Seiinger, P.G. Access Path Selection in a Relational Database Management System / P.G. Seiinger, M.M. Astrahan, D.D. Chamberlin, R.A. Lorie, T. G. Price. // SIGMOD. 1979. pp. 23-34.

122. Sellis, T. Global Query Optimization / T. Sellis // Proc. ACM SIGMOD Int. Conf. Manag. Data, Washington, D.C., May 28-30, 1986. New York, 1986. pp. 191-205.

123. Sellis, T. Multiple-Query Optimization / T. Sellis // ACM Trans. Database Syst. 1988. 13, N 1. pp. 23-52.

124. Shasha, D. Database tuning: principles, experiments and troubleshooting techniques / D. Shasha, P. Bonnet. Morgan-Kaufmann, San Francisco, CA, 2002.

125. Stockmeyer, L.H. On the Number of Comparisons to Find the Intersection of Two Relations / L.H. Stockmeyer, C.K. Wong // SIAM J. of Comput. 1979.- 8, N 3. pp. 388-404.

126. Stonebraker, M. A Distributed Data Base Version of INGRES / M. Stonebraker, E. Neuhold // Proc. 2nd Berkley Workshop Distrib. Data

127. Manag, and Comput. Networks, Berkley, Calif., May 1977. Berkley, Calif., 1977. pp. 19-36.

128. Stonebraker, M. Introduction to Chapter 1 ("The Roots") Readings in Database Systems (2nd edition) / M. Stonebraker // San Mateo, Calif.: Morgan Kaufmann, 1994.

129. Thom, J.A. A Supeqoin Algorithm for Deductive Databases / J.A. Thom, K. Ramamohanarao, L. Naish // Proc. 12th Int. Conf. Very Large Data Bases, Kyoto, Japan, Aug. 25-28, 1986. Los Altos, Calif., 1986. pp. 189-196.

130. Tindall, P. Developing enterprise applications an impurist's view: Using VB, MTS, IIS, SQL Server, and XML / P. Tindall. - Que, 1999.406 S.

131. Ullmann, J.R. Fast Implementation of Relational Operations Via Inverse Projections / J.R. Ullmann // Comput. J. 1988. 31, N 2. pp. 147154.

132. Valduriez, P. Join Indexes / P. Valduriez // ACM Trans. Database Syst. 1987. 12, N 2. pp. 218-246.

133. Vander Zanden, B.T. Estimating Block Accesses When Attributes Are Correlated / B.T. Vander Zanden, H.M. Taylor, D. Bitton // Proc. 12th Int.Conf. Very Large Data Bases, Kyoto, Japan, Aug. 1986. Los Altos, Calif., 1986. pp. 119-127.

134. Whalen, E. Oracle Performance Tuning and Optimization / Whalen E. Sams Publishing, 2003. - 670 S.

135. Whang, K. Estimating Block Accesses in Database Organizations A Closed Noniterative Formula / K. Whang, G. Wiederhold, D. Sagalowicz // Commun. ACM. 1983. 26, N 11. pp. 940-944.

136. Whang, K.-Y. Index Selection in Relational Databases / K.-Y. Whang // Found. Data Organ. Proc. Int. Conf., Kyoto, Japan, May 22-24, 1985. New York; London, 1987. pp. 487-500.

137. Wong, E. Decomposition A strategy for query processing / E. Wong, K. Youssefi // ACM Trans. Database Syst. 1976, 3 (Sept.), pp. 223-241.

138. Yao, S.B. An Attribute Based Model for Database Access Cost Analyses / S.B. Yao // ACM Trans. Database Syst. 1977. 2, N 1. pp. 4567.

139. Yao, S.B. Approximating Block Acess in Database Organizations / S.B. Yao // Commun. ACM. 1977. 20, N 4. pp. 260-261.

140. Yu, C.T. Adaptive Algorithms for Balanced Multidimensional Clustering / C.T. Yu, T.M. Jiang // Proc. 4th Int. Conf. Data Eng., Los Angeles, Calif., Feb. 1988. Washington, D.C., 1988. pp. 386-391.

141. Zahorjan, J. Estimating Block Transfers When Record Access Probabilities Are Non-Uniform / J. Zahorjan, B.J. Bell, K.C. Sevcik // Inf. Process. Lett. 1983. 16, N 5. pp. 249-252.

142. Cary, M. Why You Should Focus on LIOs Instead of PIOs Электронный ресурс. // URL: http://www.hotsos.com/e-library/ (дата обращения: 01.01.2009)

143. Shallahamer, С. Forecasting Oracle Perfomance / Shallahamer C. -Apress, 2007. 296 S.

144. Mistry, H. Materialized view selection and maintenance using multi-query optimization / Hoshi Mistry , Prasan Roy , S. Sudarshan , Krithi Ramamritham // ACM SIGMOD Record, v.30 n.2, p.307-318, June 2001

145. Kossmann, D. Cache investment: integrating query optimization and distributed data placement / Donald Kossmann, Michael J. Franklin, Gerhard Drasch, Wig Ag // ACM Transactions on Database Systems (TODS), v.25 n.4, p.517-558, Dec. 2000

146. Chen, M. Optimization of Parallel Execution for Multi-Join Queries / Ming-Syan Chen, Philip S. Yu, Kun-Lung Wu // IEEE Transactions on Knowledge and Data Engineering, v.8 n.3, p.416-428, June 1996

147. Dalvi, N. Pipelining in multi-query optimization / Nilesh N. Dalvi, Sumit K. Sanghai, Prasan Roy, S. Sudarshan // Journal of Computer and System Sciences, v.66 n.4, p.728-762, 1 June 2003

148. Theodoratos, D. Constructing search spaces for materialized view selection / Dimitri Theodoratos, Wugang Xu // Proceedings of the 7th ACM international workshop on Data warehousing and OLAP, November 12-13, 2004, Washington, DC, USA

149. Bodorik, P. Correcting execution of distributed queries / P. Bodorik, J. Pyra, J. S. Riordon // Proceedings of the second international symposium on Databases in parallel and distributed systems, p. 192-201, July 02-04, 1990, Dublin, Ireland

150. Bodorik, P. Deciding to Correct Distributed Query Processing / P. Bodorik, J. S. Riordan, J. S. Pyra // IEEE Transactions on Knowledge and Data Engineering, v.4 n.3, p.253-265, June 1992

151. Gupta, H. Selection of Views to Materialize in a Data Warehouse / Himanshu Gupta, Inderpal Singh Mumick // IEEE Transactions on Knowledge and Data Engineering, v. 17 n.l, p.24-43, January 2005

152. Rao, J. Reusing invariants: a new strategy for correlated queries / Jun Rao, Kenneth A. Ross // ACM SIGMOD Record, v.27 n.2, p.37-48, June 1998

153. Subramanian, S. Cost-based optimization of decision support queries using transient-views / Subbu N. Subramanian, Shivakumar Venkataraman // ACM SIGMOD Record, v.27 n.2, p.319-330, June 1998

154. Sellis, T. Coupling Production Systems and Database Systems: A Homogeneous Approach / T. Sellis, C.-C. Lin, L. Raschid // IEEE Transactions on Knowledge and Data Engineering, v.5 n.2, p.240-256, April 1993

155. Kotidis, Y. A case for dynamic view management / Yannis Kotidis, Nick Roussopoulos // ACM Transactions on Database Systems (TODS), v.26 n.4, p.388-423, December 2001

156. Sellis, T. Query Optimization for Nontraditional Database Applications / Timos K. Sellis, Leonard Shapiro // IEEE Transactions on Software Engineering, v. 17 n.l, p.77-86, January 1991

157. Sharaf, M. Algorithms and metrics for processing multiple heterogeneous continuous queries / Mohamed A. Sharaf, Panos K. Chrysanthis, Alexandras Labrinidis, Kirk Pruhs // ACM Transactions on Database Systems (TODS), v.33 n.l, p. 1-44, March 2008

158. Ioannidis, Y. Optimal histograms for limiting worst-case error propagation in the size of join results / Yannis E. Ioannidis, Stavros

159. Christodoulakis // ACM Transactions on Database Systems (TODS), v.18 n.4, p.709-748, Dec. 1993

160. Ioannidis, Y. Balancing histogram optimality and practicality for query result size estimation / Yannis E. Ioannidis, Viswanath Poosala // ACM SIGMOD Record, v.24 n.2, p.233-244, May 1995

161. Cole, R. Optimization of dynamic query evaluation plans / Richard L. Cole, Goetz Graefe // ACM SIGMOD Record, v.23 n.2, p. 150-160, June 1994

162. Poosala, V. Improved histograms for selectivity estimation of range predicates / Viswanath Poosala, Peter J. Haas, Yannis E. Ioannidis, Eugene J. Shekita // ACM SIGMOD Record, v.25 n.2, p.294-305, June 1996

163. Schnaitter, K. Depth estimation for ranking query optimization / Karl Schnaitter, Joshua Spiegel, Neoklis Polyzotis // Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria

164. Fuchs, D. Compressed histograms with arbitrary bucket layouts for selectivity estimation / Dennis Fuchs, Zhen He, Byung Suk Lee, // Information Sciences: an International Journal, v. 177 n.3, p.680-702, February, 2007

165. Markl, V. Consistent selectivity estimation via maximum entropy / V. Markl, P. J. Haas, M. Kutsch, N. Megiddo, U. Srivastava, T. M. Tran // The VLDB Journal — The International Journal on Very Large Data Bases, v.16 n.l, p.55-76, January 2007

166. Schnaitter, K. Depth estimation for ranking query optimization / Karl Schnaitter, Joshua Spiegel, Neoklis Polyzotis // The VLDB Journal — The International Journal on Very Large Data Bases, v.18 n.2, p.521-542, April 2009

167. Markl, V. LEO: An autonomic query optimizer for DB2 / V. Markl, G. M. Lohman, V. Raman // IBM Systems Journal, v.42 n.l, p.98-106, January 2003

168. Stillger, M. LEO DB2's LEarning Optimizer / Michael Stillger, Guy M. Lohman, Volker Markl, Mokhtar Kandil // Proceedings of the 27th International Conference on Very Large Data Bases, p. 19-28, September 11-14, 2001

169. Chen, C. Adaptive selectivity estimation using query feedback / Chungmin Melvin Chen, Nick Roussopoulos // ACM SIGMOD Record, v.23 n.2, p.161-172, June 1994

170. Ziauddin, M. Optimizer plan change management: improved stability and performance in Oracle llg / Mohamed Ziauddin, Dinesh Das, Hong Su, Yali Zhu, Khaled Yagoub // Proceedings of the VLDB Endowment, v. 1 n.2, August 2008

171. Herodotou, H. Automated SQL tuning through trial and (sometimes) error / Herodotos Herodotou, Shivnath Babu // Proceedings of the Second International Workshop on Testing Database Systems, June 29-29, 2009, Providence, Rhode Island

172. Bruno, N. Configuration-parametric query optimization for physical design tuning / Nicolas Bruno, Rimma V. Nehme // Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada

173. Gosalia, A. Automatic plan choice validation using performance statistics / Ashit Gosalia, Xin (Shin) Zhang // Proceedings of the 1st international workshop on Testing database systems, June 13-13, 2008, Vancouver, British Columbia, Canada

174. Benoit, D. Automatic Diagnosis of Performance Problems in Database Management Systems / Darcy G. Benoit // Proceedings of the Second International Conference on Automatic Computing, p.326-327, June 1316, 2005

175. Chaudhuri, S. Self-Tuning Database Systems: A Decade of Progress / Surajit Chaudhuri, Vivek Narasayya // Proceedings of the Second International Conference on Automatic Computing, p.326-327, June 1316, 2005

176. Stonebraker, M. The Choice of Partial Inversions and Combined Indices / M. Stonebraker // International Journal of Computer and Information Sciences, 3(2), June 1974

177. Finkelstein, S. Physical Database Design for Relational Databases / Finkelstein, S., Schkolnick, M., and Tiberio, P. // ACM Trans. On Database Systems, Vol 13, No 1, March 1988

178. Shapiro, G. The Optimal Selection of Secondary Indices is NP-Complete / Shapiro, G.P. // SIGMOD Record 13(2): 72-75 (1983)

179. Agrawal, R. Fast Algorithms for Mining Association Rules in Large Databases / Agrawal, R., Ramakrishnan, S. // In Proceedings of VLDB, 1994

180. Agrawal, S. Automated Selection of Materialized Views and Indexes for SQL Databases / Agrawal, S., Chaudhuri, S., Narasayya, V. // In Proceedings of VLDB, Cairo, Egypt, 2000

181. Bruno, N. Physical Design Refinement. The Merge-Reduce Approach / Bruno, N., Chaudhuri, S. // In Proceedings of ACM SIGMOD conference, 2002

182. Papadomanolakis, S. Autopart: Automating Schema Design for Large Scientific Databases Using Data Partioning / Papadomanolakis, S., Ailamaki, A. //InProceedings of SSDBM, 2004

183. Zilio, S. DB2 Design Advisor: Integrated Automatic Physical Database Design / Zilio et al. // In Proceedings of the VLDB, Toronto, Canada, 2004

184. Dageville, B. Automatic SQL Tuning in Oracle lOg / Dageville, B., Das, D., Dias, K., Yagoub, K., Zait, M., Ziauddin, M. // In Proc. Of the 30 International Conference of VLDB, 2004

185. Lee, A. Closing the query processing loop in Oracle llg / Allison W.Lee, Mohamed Zait // In Proceedings of the VLDB Endowment, 2008

186. El-Helw, A. Collecting and Maintaining just-in-time statistics / El-Helw, A., Ilyas, I., Lau, W., Markl, V., Zusarte, C. // In Proceedings of ICDE, 2007