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

ОПТИМИЗАЦИЯ ПОТОКОВ ПРОСТЫХ ЭОЬ-ЗАПРОСОВ

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

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

Санкт-Петербург 2005

Работа выполнена на кафедре «Вычислительные системы и сети» Государственного образовательного учреждения высшего профессионального образования «Санкт-Петербургский

государственный университет аэрокосмического приборостроения» (ГУАП).

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

кандидат технических наук, доцент Карпова Татьяна Сергеевна

Официальные оппоненты:

доктор технических наук, профессор Охтилев Михаил Юрьевич кандидат технических наук, доцент Костюнина Татьяна Николаевна Ведущая организация: ОАО «Центр компьютерных разработок»

Защита состоится '"/3 " 4 ¿¡¿О Ор Я_2005г. в ^¿Г часов на

заседании диссертационного совета Д 212.233.02 при Государственном образовательном учреждении высшего профессионального образования «Санкт-Петербургский

государственный университет аэрокосмического приборостроения» по адресу: 190000, г.Санкт-Петербург, ул.Б.Морская, 67, ГУАП.

С диссертацией можно ознакомиться в библиотеке ГУАП. Автореферат разослан НОЗ^рЯ 2005г.

Ученый секретарь совета доктор технических наук, профессор ^уГ 'Ы^г^Л.А.Осипов

ЗЛА А—и

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

Актуальность темы. В настоящее время для хранения и обработки данных активно используются реляционные базы данных. Чем больше объем хранимых данных, тем больше уходит времени на поиск нужной информации, т.е. увеличивается время обработки запросов сервером. Кроме того, в последнее время базы данных используются для публикаций данных в интернет. В этом случае количество пользователей базы данных, которые обращаются к ней в данный момент времени, может значительно возрастать. В результате опять же возрастает нагрузка на сервер. С одной стороны эту проблему пытаются решать увеличением производительности компьютеров, на которых находятся системы управления базами данных (СУБД). Однако, простого увеличения производительности компьютеров, конечно же, недостаточно; часто гораздо большего эффекта можно добиться с помощью изменения алгоритмов обработки 8<ЗЬ-запросов. Так, например, использование одноуровневых индексов взамен сканирования таблицы, позволяет добиться логарифмической зависимости скорости выполнения запроса от количества занимаемых страниц данных (при сканировании таблицы зависимость линейная). При использовании индексов в виде сбалансированных деревьев получаемый выигрыш еще больше. В то же время, повышение скорости работы внешней памяти дает лишь линейное увеличение производительности обработки запросов.

Таким образом, хотя работы по оптимизации Б(}1.-запросов ведутся уже не одно десятилетие, в настоящее время они вовсе не потеряли актуальности. Напротив, в связи с увеличением темпов роста объема информации и нагрузки на сервер баз данных, такие работы стали еще более актуальны.

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

компонент СУБД - оптимизатор. При сос

■да//!

■аашмсютоя—еиециальныи

СПе

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

1. Анализ существующих методов оптимизации БС^Ь-запросов и выявление их недостатков, касающихся оптимизации не одиночных запросов, а потоков запросов; выявление классов задач для которых актуально проведение оптимизации потоков запросов и их классификация.

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

3. Разработка модели преобразования потока 8()Ь-запросов. Проведение синтеза сложных 8С)Ь-запросов из множества простых и построение на ее основе системы, предназначенной для выполнения синтеза.

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

систем управления базами данных, теория алгоритмов, метод

системного анализа.

Положения, выносимые на защиту:

1. Модель таблиц с внутренними зависимостями.

2. Модель взаимодействия между приложением и базой данных.

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

4. Алгоритм обработки результатов синтезированных запросов в прикладном приложении.

г 5. Алгоритм синтеза сложных запросов из множества простых.

Практическая ценность. Разработанная на основе предложенного метода программа позволяет выдавать рекомендации по оптимизации потока БС^Ь-запросов, которые пользовательское приложение генерирует для обращения к базе данных. Модификация текста программы с учетом выданных рекомендаций, позволяет существенно повысить эффективность взаимодействия приложения и базы данных. Получаемый выигрыш зависит от множества факторов, описанных в диссертационной работе. Среди таких факторов - размеры отношений в базе данных, наличие на них дополнительных структур, эффективность предикатов 80Ь-запросов, количество уровней вложенности в таблицах, выдаваемых пользователю и т.д. Увеличение выигрыша растет при увеличении этих параметров. В связи с этим затруднительно дать точную оценку получаемого выигрыша. Для проводимых экспериментов время взаимодействия было уменьшено в среднем в 7 раз. Для определенных случаев, выигрыш может быть и существенно больше. В других случаях выполнение синтеза может не дать никакого выигрыша и даже сказаться отрицательно. В таких случаях проводить его нецелесообразно. Соответственно, программа не будет выдавать рекомендаций по его проведению. Получение существенного выигрыша при использовании выдаваемых ? рекомендаций говорит об эффективности предложенного метода для определенных классов задач и параметров базы данных. Внедрение результатов работы. Основные теоретические и ' экспериментальные результаты работы были внедрены в СПб ГУП «Санкт-Петербургский информационно-аналитический центр», Главном Управлении федеральной регистрационной службы по Санкт-Петербургу и Ленинградской области, а также в учебном процессе СПбГУАП. Программная система, разработанная по

результатам выполнения диссертационной работы, была зарегистрирована в отраслевом фонде алгоритмов и программ. Акты о внедрении приведены в приложении 4 к диссертационной работе. Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на 5-ой, 6-ой и 7-ой научных сессиях аспирантов ГУАП в 2002-2004 годах, на пятой международной многопрофильной конференции молодых ученых и студентов «Актуальные проблемы современной науки», а так же на научных семинарах кафедры 44 - вычислительных систем и сетей ГУАП и кафедры прикладной информатики Международного банковского института.

Публикации. Основные положения диссертации изложены в 8 публикациях, в том числе 1 программный продукт, зарегистрированный в фонде алгоритмов и программ ВНТИЦ. Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы, включающего 106 наименований, и четырех приложений. Объем работы - 152 стр., работа содержит 14 таблиц и 24 рисунка.

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

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

В первой главе описывается современное состояние проблемы оптимизации SQL-запросов. Рассматриваются этапы обработки запросов и возможности оптимизации на каждом из них.

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

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

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

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

На этапе построения плана запроса оптимизатор учитывает, что одну реляционную операцию можно выполнить разными способами. Так, например, для выполнения реляционной операции соединения, существует три основньгх алгоритма ~ метод вложенных циклов, соединение слиянием и хэш-соединение. Каждый из этих методов предъявляет свои требования к соединяемым отношениям и имеет несколько подвариантов в зависимости от имеющихся дополнительных структур и распределения данных, содержащихся в этих отношениях. Также имеются различные алгоритмы вычисления агрегатных функций на группах кортежей. Рассматриваются и анализируются следующие способы доступа к данным, используемые оптимизатором запросов: сканирование отношений, поиск по индексу, сканирование индекса, доступ по RID (идентификатору кортежа), поиск по индексу, поиск в хэш-кластере, поиск в кластере, поиск по битовому индексу и поиск по битовому индексу соединения.

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

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

Рассматриваются методы использования материализованных и секционированных представлений. Материализованные

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

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

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

Рассматривается вопрос оптимизации распределенных запросов и вопрос распараллеливания плана выполнения запроса.

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

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

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

влиять на нее, пытаясь расширить, даже если будем представлять себе что именно надо было бы для этого сделать. Кроме того, нет никакой гарантии того, что сам поток запросов оптимален. Т.е. нет гарантии того, что приложение само по себе не генерирует такой поток, который далек от оптимальности. А значит, оптимизация каждого запроса по отдельности не даст большого выигрыша. Глобальная оптимизация (оптимизация наборов запросов), рассмотренная в первой главе, пытается оптимизировать сразу множество запросов, но она невозможна для традиционных реляционных СУБД. Кроме того, это направление сводится к поиску общих частей запросов и вычислению их только один раз. Т.е. происходит разделение сложных запросов на более мелкие части. В обратную сторону оптимизация наборов запросов не проводится. Предлагается проводить оптимизацию генерируемого потока запросов путем замены множества простых запросов на один сложный в случаях, когда это возможно. Деление БС^Ь-запросов на простые и сложные условно. Простые запросы - это запросы, не содержащие соединений отношений. Такие запросы строятся на основе одного отношения. При наличии между отношениями связи типа М:М допускается использование соединения одного из исходных отношений с промежуточным отношением, реализующим эту связь. Сложные запросы - это запросы, строящиеся на основе нескольких отношений.

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

Здесь Тсоед - это время, необходимое на установление соединения с сервером БД; Тп 3 (стадия 5) - время передачи запроса от клиента к серверу; Ткомп (стадия 6) - это время компиляции запроса; Т0 3 с (стадия 7) - время обработки запроса сервером; Тпр (стадия 8) - время передачи результата запроса от сервера к клиенту; Т0 р к (стадия 9) -время обработки результата клиентом. Тсоед включает в себя четыре стадии - создание на клиенте объекта, создающего соединение, и поддерживающего соединение (стадия 1), установление соединения, (стадия 2,4) и установку системных параметров (стадия 3).

Общее время, являющееся критерием оптимизации, можно найти

Т = Т + Т + Т + Т + Т + Т как обш соед пз комп °,с пр орк для одного

Т^Т^ + Щ^ +Ткоип+7озс + Tnf) + Ty запроса и ^ г для потока

запросов, где L - количество запросов в потоке.

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

Пусть имеются отношения и со схемами ~ ^ и

_ (В'С) где А, В и С - подмножества множества атрибутов

R R Д D D ДО D

отношений 1 и 2. Операцией " -сравнения

будем

называть некоторое корректное логическое выражение, включающее в

R В R В

качестве аргументов атрибуты из множеств г и 2 .

R '

Введем отношение г со схемой, эквивалентной схеме

R S — S

отношения 2: R1 1RT и содержащее всего один кортеж, все атрибуты которого имеют неопределенное значение (NULL).

Пусть

отношение

R,=R,[B]\R2[B].

R4=R3[R3.B1=R1.B, &R3.B2=R,.B2 &...&R3.Bk=R,.Bk]R1

где

| g D

'k . Тогда операцией внешнего условного соединения

отношении

й Ri и К2 по условию КуВ 0

и

по условию выполнения

будем называть операции:

результат

R,[R,.B в* R2.B]R2=(R,[R, B в R2.B]R2) uC^®^') Вводим операцию общего соединения:

ЯДЯрВ в" Я2.В]Я2

' И^.В в Я2.В]Я2

я^.в в* я2.в]к2

р р

Пусть между отношениями 1 и 2 существует связь типа 1 :М, или типа М:М, реализуемая введением промежуточного отношения

,д. Если в таблицу, выдаваемую пользователю, выводятся данные из

О Б

1 и 2, то будем это обозначать с помощью следующей операции:

ЯДЯрА в* К2.В]112 =

Я^.А вл 112.В]К2

_(К1[КГА вГ ^.А]^)^.* вл

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

Каскадная таблица, основанная на отношениях

к р р р

1' 2' 3' "' т , получается путем выполнения операции (((К.^.А в* Я2.В] Я2) [ Я2.А в* Л,.В] Я3) ...Я,,.,) [ Яга,.А в* Ят.В] Ял После выполнения указанных соединений, выполняется проецирование на необходимые для вывода столбцы и денормализация. Денормализация выполняется следующим образом:

о

все проекции кортежей отношения 1 (Iе [2..М]), соответствующие

р п

одному набору значений атрибутов отношений • 14 ц

являющиеся полностью идентичными между собой выделяются в группы. Для каждой группы все значения каждого атрибута группируются (объединяются).

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

G2(C0^) = F(G1(Co/)) въ(Со1) = Р(<Эг(Со1))

[Ои(Со1) = Р(Ом^(Со1))

, где ¡-ая группа столбцов таблицы, И -внутренняя прямая

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

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

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

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

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

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

Т Т

сервером ( 030 ) и времени передачи результатов клиенту ( пр ). Эти

Т

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

Для оценки избыточности и времени обработки запросов сервером вводятся следующие параметры:

N. Я

' -кардинальное число отношения ';

^ - размер страницы данных или индекса;

R R

JN] t - эффективность предиката соединения отношений 'и 1;

R,

(oS) - отношение числа кортежей отношения ', таких, что в

соответствии с предикатом соединения им не соответствует ни одного

R R

кортежа из отношения ' к кардинальному числу отношения ';

'•■> - кардинальное число столбца j i-ого отношения;

D R

,J - количество различных значений атрибута] отношения ';

SelJ Л . R,

1 - селективность атрибута j отношения ';

С1а!, „ -------------R,

Я.

iaii _ средний размер кортежа отношения

' - коэффициент отношения между средним размером нужной проекции кортежа и средним размером самого кортежа;

^ - эффективность предиката ограничения;

тип _ коэффициент увеличения производительности операций

ввода/вывода при чтении сразу многих страниц;

р

^'-фактор заполнения;

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

С.

у - размер ссылки в индексных записях;

С

ш _ размер поля по которому построен индекс;

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

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

Показывается, что применение предлагаемого способа оптимизации для описных классов задач, позволяет оптимизатору запросов использовать большую вариативность в построении планов запросов, а значит получать выигрыш во времени обработки запросов. После замены множества простых запросов на один сложный, оптимизатор} становятся доступны такие возможности как возможность использования временных структур (например, временные индексы), возможность изменения порядка реляционных операций, использование различных алгоритмов соединения, изменение ролей отношений при их соединении, изменение порядка соединения, а также увеличиваются возможности по использованию различных способов доступа к данным. Так, например, на рис. 2а) показаны зависимости числа операций ввода/вывода от числа кортежей в одном из отношений для метода вложенных циклов при отсутствии индексов (1) и при построении временного индекса (2). Возможность использования (2) имеется только при проведении предлагаемого метода оптимизации. На рис. 26) показаны зависимости числа операций ввода/вывода от эффективности предиката ограничения одного из отношений для соединения методом вложенных циклов (1) и методом слияния (2). Возможность использования (2) также имеется только при проведении предлагаемого метода оптимизации.

Рис. 2а) Зависимости числа операций ввода/вывода от числа кортежей

с использованием динамических индексов (2) и без них (1); Рис. 26) Зависимости числа операций ввода/вывода от эффективности предиката соединения для соединения методом вложенных циклов (1) и методом слиянием (2)

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

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

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

М = {т ,;...:т\ маршрутов 1 1 1 ' . Под операцией расширения

множества маршрутов М на тип запроса Ъ будем понимать операцию, результатом которой является множество маршрутов М* = {2 + т + т2\...\2 + тп}

Пусть есть маршрут т. Тогда усечением его до к узлов, обозначаемым как 1ей(т,к) будет маршрут, включающий первые к узлов маршрута т.

Пусть теперь есть маршруты ш1 и ш2. Существует некоторое множество М маршрутов, таких, что 1еА(т1,к)=1ей(т2,к), где к-некоторое целое неотрицательное число. Результатом нахождения общей части маршрутов т1 и га2 будет маршрут, обозначаемый как гпЗ=ш1п(ш1, т2), принадлежащий множеству М и имеющий максимальную длину среди всех маршрутов этого множества.

Пусть есть два множества маршрутов ^^-{т^} и Мг-{тг)

-г ,М. ®М, ч г-

Тогда результатом операции их умножения ( 1 2) будет

множество маршрутов, удовлетворяющее условию: МХ®М2 = {тт(щ,т2) | т1еМ1лт2еМ2}

Пусть запрос ^ определяет множество курсоров: Q def МК = {К,-,Кг\К-...\КЛ л, К,

^ 1 1 2 3 *>. Курсор 1 определяет для запроса

^ множество маршрутов, которые можно найти по формуле:

Тут

М0 , = А + ®(Мп ) = А + (Мп ®Мп ®Мп ®...®Мп )

и-*' У 1.1 ^1,2 И1.3

ма

^ - множество маршрутов 1-ого запроса, определяемого курсором

к

1; А - тип запроса, которому он принадлежит. Поскольку

МК = {К.;К2;К3;...;Кт} 0

11 1 * т>, то все множество маршрутов запроса ^

находится как ' . Для отбрасывания

маршрутов являющихся частью других маршрутов и окончательного

формирования множества маршрутов для запроса б используется

формула 7=1 ' , где

: п\ ф т2л ml,mJ е М А т, = ^^, 1еп(т,))}

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

MQ={0, | MQ is null Л | Q , def Q} л MQj is not null)}

Обозначение ™обозначает, что множество маршрутов

запроса не определено в данный момент. Когда для каждого маршрута найдены его маршруты, то произвести синтез не представляет трудностей.

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

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

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

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

4. Разработан способ обработки результатов синтезированных запросов в прикладном приложении.

5. Разработан алгоритм синтеза сложных запросов из множества простых.

6. На основе предложенных алгоритмов разработана программа для выдачи рекомендаций по оптимизации SQL-запросов.

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

1. Зверев Д.Л. Анализ времени выполнения запросов и избыточности данных при проведении оптимизации на стыке баз данных и клиентских приложений И Седьмая научная сессия аспирантов ГУАП: Сб. докл.: В 2 ч. ЧI. Технические науки. - СПб.: СПбГУАП.

- 2004. -С.319-322.

2. Зверев Д.Л. Исследование возможности оптимизации потока БОЬ-запросов // Шестая научная сессия аспирантов ГУАП - Сб. докл.: В 2 ч. Ч I. Технические науки. - СПб.: СПбГУАП. - 2003. - С. 235-237.

3. Зверев Д.Л. Исследование инвариантов в оптимизации потоков 80Ь-запросов // Вестник молодых ученых. 1-ый номер серии «Технические науки». - 2005. - №6

4. Зверев Д.Л. Исследование профилей параллельных вычислений как случайных функций // Третья международная молодежная школа-семинар БИКАМП-01 - Сб. докл. - СПб.: СПбГУАП. - 2001. -СЛ 50-153.

5. Зверев Д.Л. Оптимизация потоков БОЬ-запросов // Вестник экономического научного сообщества студентов и аспирантов, СПб: МБИ. - 2004. - С.60-94.

6. Зверев Д.Л. Расчет выигрыша во времени выполнения запросов при проведении оптимизации потоков запросов // Пятая международная многопрофильная конференция молодых ученых и студентов «Актуальные проблемы современной науки» - Сб. докл.

- Самара: СамГТУ. - С.40-43.

7. Зверев Д.Л. Технология использования материализованных и индексируемых представлений для повышения эффективности 8С>Ь-запросов. // Пятая научная сессия аспирантов ГУАП: Сб. докл.: В 2 ч. ЧI. Техн. науки. - СПб.: СПбГУАП. - 2002. - С.345-349

8. Программа выдачи рекомендаций по оптимизации потоков 8<ЗЬ-запросов // Зверев Д.Л., //№50200400968. Сб. Алгоритмы и программы. М.: ВНТИцентр. - 2004.

Формат 60x84 1\16 .Бумага офсетная. Печать офсетная. _Тираж 100 экз. Заказ № _

Отдел оперативной полиграфии ГОУ ВПО «СПбГУАП» 190000, Санкт-Петербург, ул. Б. Морская , 67

#21767

РНБ Русский фонд

2006-4 21629

Введение.

Глава 1. Современное состояние проблемы оптимизации SQL-запросов.

1.1. Ход обработки запроса.

1.2. Логическая оптимизация.

1.3. Семантическая оптимизация.

1.4. Построение возможных планов выполнения запроса и выбор оптимального из них.

1.5. Выводы.

Глава 2. Разработка метода оптимизации.

2.1. Оптимизация потоков SQL-запросов.

2.2. Критерии оптимизации.

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

2.3.1. Каскадные таблицы.

2.3.2. Таблицы, зависимые только от одного уровня.

2.3.3. Таблицы, имеющие зависимости более чем от одного столбца.

2.3.4. Таблицы, имеющие фильтры и обратные зависимости.

2.3.5.Таблицы смешанного типа.

2.4. Сравнительный анализ предлагаемого метода оптимизации и существующих методов.

2.5. Модель системы, реализующей предлагаемый метод оптимизации.

2.6. Выводы.

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

3.1. Параметры, используемые для оценок.

3.2. Оценка избыточности данных.

3.2.1. Каскадные таблицы.

3.2.2. Таблицы, зависимые только от одного уровня.

3.3. Оценка времени обработки запросов сервером.

3.3.1. Анализ способов доступа к данным.

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

3.3.2.1. Метод вложенных циклов.

3.3.2.2. Метод хэш-соединения.

3.3.2.3. Метод соединения слиянием.

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

3.3.3.1. Использование кластеров.

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

3.3.3.3. Использование битовых индексов соединения.

3.4. Выводы.

Глава 4. Разработка метода синтеза запросов.

4.1. Этапы проведения синтеза.

4.2. Выделение подпотоков запросов, подлежащих оптимизации.

4.3. Преобразование множества простых запросов, составляющих выделенный подпоток, к одному сложному.

4.4. Проверка целесообразности преобразования.

4.5. Выводы.

Актуальность темы. В настоящее время для хранения и обработки данных активно используются реляционные базы данных. Размер баз данных, т.е. объем хранимых данных, может варьироваться в широком диапазоне - от килобайтов до терабайтов. Понятно, что чем больше размер отношений базы данных, тем больше уходит времени на поиск нужной информации, т.е. увеличивается время обработки запросов сервером. Кроме того, в последнее время базы данных используются для публикаций данных в интернет. В этом случае количество пользователей базы данных, которые обращаются к ней в данный момент времени, может значительно возрастать. В результате опять же возрастает нагрузка на сервер. С одной стороны эту проблему пытаются решать увеличением производительности компьютеров, на которых находятся системы управления базами данных (СУБД). Однако, простого увеличения производительности компьютеров, конечно же, недостаточно; часто гораздо большего эффекта можно добиться с помощью изменения алгоритмов обработки SQL-запросов. Так, например, использование одноуровневых индексов взамен сканирования таблицы, позволяет добиться логарифмической зависимости скорости выполнения запроса от количества занимаемых страниц данных (при сканировании таблицы зависимость линейная). При использовании индексов в виде сбалансированных деревьев получаемый выигрыш еще больше. В то же время, повышение скорости работы внешней памяти дает лишь линейное увеличение производительности обработки запросов.

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

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

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

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

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

Задачи исследования:

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

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

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

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

Положения, выносимые на защиту:

1. Модель таблиц с внутренними зависимостями.

2. Модель взаимодействия между приложением и базой данных.

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

4. Алгоритм обработки результатов синтезированных запросов в прикладном приложении.

5. Алгоритм синтеза сложных запросов из множества простых.

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

Внедрение результатов работы. Основные теоретические и экспериментальные результаты работы были внедрены в ГУП «Санкт-Петербургский Информационно-аналитический центр» и в учебном процессе СПбГУАП. Программная система, разработанная по результатам выполнения диссертационной работы, была зарегистрирована в отраслевом фонде алгоритмов и программ, о чем было получено свидетельство № 3763. Акты о внедрении приведены в приложении 4.

Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на 5-ой, 6-ой и 7-ой научных сессиях аспирантов ГУАП в 2002-2004 годах, на пятой международной многопрофильной конференции молодых ученых и студентов «Актуальные проблемы современной науки», а так же на научных семинарах кафедры 44 - вычислительных систем и сетей ГУАП и представлены в публикациях [6, 8, 12, 13, 15, 18].

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

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

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

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

Глава Современное состояние проблемы оптимизации SQL-запросов

На данный момент существует множество способов и подходов к оптимизации SQL-запросов. В [19, 27, 54, 102, 103, 104] описываются многие из этих способов. Рассмотрим основные из них.

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

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

4.5. Выводы

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

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

Заключение

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

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

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

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

4. Разработан способ обработки результатов синтезированных запросов в прикладном приложении.

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

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

1. Величко С.В., Межов Е.В. Современные СУБД для создания единой информационной среды в больших информационных системах. // Вестник воронежского гос. техн. университета. - 2003. - № 3. - С.68-73.

2. Грофф. Джеймс Р., Вафнберг Пол Н. SQL: Полное руководство. СПб.: БХВ-Петербург, 2001. - 814 с.

3. Дейт К. ДЖ., Введение в системы баз данных. СПб.: Издательский дом "Вильяме", 2000. - 848 с.

4. Елманова Н. Введение в Data Mining // КомпьютерПресс, 2003, № 10. - С.165-167.

5. Жарков А.В., Шашков Б.Д. Управление запросами к распределенной базе данных специализированной вычислительной системы. // Научная сессия МИФИ. Сб. научных трудов, т.2. Москва: МИФИ. - 2003. - С.44-47.

6. Зверев Д.Л. Исследование алгоритма Барнса-Хутта как вычислительной нагрузки // Интеллектуальные и многопроцессорные системы Сб. докл., Таганрог-Донецк. - 2001. - С.205-207.

7. Зверев Д.Л. Исследование возможности оптимизации потока SQL-запросов // Шестая научная сессия аспирантов ГУАП Сб. докл.: В 2 ч. Ч I. Технические науки. - СПб.: СПбГУАП. - 2003. - С. 235-237.

8. Зверев Д.Л. Исследование инвариантов в оптимизации потоков SQL-запросов // Вестник молодых ученых. 1-ый номер серии «Технические науки». 2005. - №6

9. Ю.Зверев Д.Л. Исследование профилей параллельных вычислений как случайных функций // Третья международная молодежная школа-семинар БИКАМП-01 -Сб. докл. СПб.: СПбГУАП. - 2001. - С.150-153.

10. П.Зверев Д.Л. Оптимизация потоков SQL-запросов // Вестник экономического научного сообщества студентов и аспирантов, СПб: МБИ. 2004. - С.60-94.

11. Зверев Д.Л. Технология использования материализованных и индексируемых представлений для повышения эффективности SQL-запросов. // Пятая научная сессия аспирантов ГУАП: Сб. докл.: В 2 ч. Ч I. Технические науки. СПб.: СПбГУАП. - 2002. - С. 345-349.

12. Карпова Т.С. Базы данных. Модели, разработка, реализация. Издательский дом «Питер», 2001. - 303 с.

13. Кнут Д. Искусство программирования для ЭВМ. т.З. Сортировка и поиск, 2-е изд. -М.: Издательский дом "Вильяме", 2000. 832 с.

14. Компиляторы языка SQL. Проблемы оптимизации. // http:/zeus.sai.msu.m:7000/database/osbd/glava 89.shtml#6l

15. Коноли Т. И др. Базы данных. М.: Издательский дом «Вильяме», 2000 - 1111 с.

16. Кузнецов С. Методы оптимизации выполнения запросов в реляционных СУБД // http:/www.citforum.aanet.ru/database/articles/art26.shtml

17. Кузнецов С. Д. Основы современных баз данных // http:/www.lcard.ru/~nail/database/osbd/contents.htm

18. Мамаев Е. Microsoft SQL Server 2000. Наиболее полное руководство. СПб.: Издательский дом "Вильяме", 2001. - 1261 с.

19. Мейер Д. Теория реляционных баз данных. М.: Мир, 1987 - 608 с.

20. Сиртюк О.В. Задачи оптимизации проектирования логических структур объектно-ориентированных данных. 2 международная конференция по проблемам управления. Сб. докл. // М.: изд-во ИПУ РАН. 2003. - С.138.

21. Смирнов И.В. Расширение поискового запроса синонимичными словосочетаниями. // 40 всероссийская конференция по проблемам информатики, физики и химии. Секция математики и информатики. Сб. докл. -М.: изд-во РУДН. 2004. - С. 192-194.

22. Сукач Е.И., Еськова О.И., Каморникова Т.Я. Определение характеристик распределенной базы данных с помощью имитационного моделирования. Изд. гомор. унив. 2002. - № 6. - С. 110-112.

23. Тихомиров Ю. Microsoft SQL Server 7.0. Наиболее полное руководство СПб.:• БХВ-Петербург. 1999. - 720 с.

24. Ульман Д. Основы систем баз данных.- М.: Финансы и статистика. 1983. - 335 с.

25. Чаудхари С. Методы оптимизации запросов в реляционных системах. // http://www.osp.ru/dbms/1998/03/22.htm

26. Aho A.V., Sagiv Y., Ullman J.D. Efficient Optimization of a Class of Relational Expressions // ACM Trans. Database System 1979. - № 4. - C.435-454.

27. Bing Yao S. Optimization of Query Evaluation Algorithms // ACM TODS. 1979. -4. - № 2.• 30. Blasgen, Eswaran Relation databases // IBM System 1977. № 4. - C. 25-30

28. Blasgen M., Eswaran K. Storage and Access in Relational Database // IBM Sys. J. -1977. 16.-№4.-C.84-93.

29. Bobrovsky S. Using Materialized views to speed up queries. // Oracle Magazine -1999.-№5.-C.45-49.

30. Bodorik P., Riordon J.S. Distributed Query Processing Optimization Objectives // 4th Int. Conf. Data Eng., West Berlin, Sept. 13-15. New York - 1988. - C.320-329.

31. Bultzingsloewen G. Translating and Optimizing SQL Queries Having Aggregates // Proc. 13th Int. Conf. Very Large Data Bases, Brington, England, Sept. Los Altos, Calif. - 1987. - C.235-244.

32. Ceri S., Gottlob G. Optimizing Joins Between Two Partitioned Relations in• Distributed Databases // J. Parall. and Distrib. Comput.- 1986. 3. - № 2. - C.183-205.

33. Ceri S., Gottlob G. Translating SQL into Relational Algebra: Optimization, Semantics, and Equivalence of SQL Queries // IEEE Trans, on Software Eng. 1985. - 11. - № 4. - C.324-345.

34. Ceri S., Gottlob G., Lavazza L. Translation and Optimization of Logic Queries: The Algebraic Approach // Proc. 12th Int. Conf. Very Large Data Bases. Los Altos, Calif. - 1986. - C.395-402.

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

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

37. Chen J.S.J., Li V.O.K. Optimizing Joins in Fragmented Database Systems on a Broadcast Computer Networks // 7th Int. Conf. Distrib. Comput. Syst., Berlin, Sept. 21-25, 1987. Washington, D.C. - 1987. - C.338-345.

38. Cheng J.M., Loosley C.R., Shibamiya A., Worthington P.S. IBM Database 2 Performance: Design, Implementation, and Tuning // IBM Syst. J.- 1984,- 23. № 2.- C.189-210.

39. Christodoulakis S. Estimating Block Selectivities // Inf. Syst.- 1984,- 9. № 1.• C.69-79.

40. Christodoulakis S. Implication of Certain Assumtions in Database Performance Evaluation // ACM Trans. Database Syst. 1984. - 9. - № 2. - C. 163-186.

41. Christodoulakis S. Estimating Record Selectivities // Inf. Syst. 1983.- 8. - № 2. -C.105-115.

42. Cornell D.W., Yu P.S. A Vertical Partitioning Algorithm for Relational Databases // 3rd Int. Conf. Data Eng., Los Angeles, Ca, Febr. 3-5, 1987. Proc. Washington, D.C.- 1987.-C.30-35

43. Dayal U. Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers // Proc. 13th Int. Conf. Very Large Data Bases, Brington, England, Sept. 1987. Los Altos, Calif. - 1987.• C.197-208.

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

45. Faloutsos C., Christodoulakis S. Design of a Signature File Method that Accounts for Non-Uniform Occurrance and Query Frequencies // Proc. 11th Int. Conf. Very Large Data Bases, Stockholm, Sweden, Aug. 1985. Los Altos, Calif. - 1985. - C.165-170.

46. Freytag J.C., Goodman N. Translating Aggregate Queries into Iterative Programs // Proc. 12th Int. Conf. Very Large Data Bases, Kyoto, Japan, Aug. 1986. Los Altos, Calif. - 1986. -C.138-146.

47. Ganski R.A., Wong H.IC.T. Optimization of Nested SQL Queries Rivisited // Proc.• ACM SIGMOD Int. Conf. Manag. Data, San Francisco, Calif., May 1987. New York. - 1987. -C.23-33.

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

49. Hawthorn P., Stonebraker M.R. Performance Analisys of Relational Data Base Management System // Proc. ACM SIGMOD Int. Conf. Manag. Data, Boston, Mass., May 30 June 1, 1979. - New York. - 1979. - C.l-12.

50. FIiyoshi S., Mizuma M., Watanabe M. Hierarchical Optimization Strategy for Query• Evaluation // NEC Res. and Dev. 1984. - № 12. - C.48-55.

51. Ioanidis Y.E., Ng R.T., Shim K., Sellis Т.К. Parametric Query optimization // Proc 18 Intern. Conf on very large databases. Vancouver, Canada. - 1992.

52. Jarke M., Koch J. Query optimization in Database Systems // ACM Сотр. Surv. -1984. 16.-№ 2.-C.l 11-152.

53. Jhingram A. A Performance Study of Query Optimization Algorithms on a Database System Supporting Procedural Objects // Proc. 14th Int. Conf. Very Large Data Bases, Los Angeles, Calif., Aug.-Sept. 1988. Los Altos, Calif. - 1988. - C.88-99.

54. Kiessling W. Access Path Selection in Databases with Intelligent Disc Subsystems // Comput. J. 1988. - 31. - № 1. - C.41-50.

55. Kim W. On Optimizing an SQL-Like Nested Query // ACM Trans. Database Syst.• 1982.-7. -№3.-C.443-469.

56. Kim W., Reiner D.S., Batory D.S. Query Processing in Database Systems // New York, N.Y.: Springer-Verlag. 1985.

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

58. ICooi R., Frankforth D. Query Optimization in INGRES // IEEE Database Eng. Bull. 1982. - 5.-J6 3.-C.2-5.

59. Krishnamurthy R., Boyal H., Zaniolo C. Optimization of Nonrecursive Queries // Proe. 12th Int. Conf. Very Large Data Bases, Kyoto, Japan, Aug. 1986. Los Altos, Calif. - 1986.-C.128-137.

60. Lee M., Freytag J., Lohman G. Implementing an Interpreter for Functional Rules in a Query Optimizers // Proc. 14th Int. Conf. Very Large Data Bases, Los Angeles, Calif., Aug.-Sept., 1988. Los Altos, Calif. - 1988. - C.218-229.

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

62. Lohman G.M., Daniels D., Haas L.M., Kistler R., Selinger P.G. Optimization of Nested Queries in a Distributed Relational Database // Proc. 10th Int. Conf. Very Large Data Bases, Singapore, Aug. 27-31, 1984. New York. - 1984. - C.403-415.

63. Lohman G.M., Mohan C., Haas L.M., Lindsay B.G., Selinger P.G., Wilms P.F., Daniels D. Query Processing in R* // Query Processing in Database Systems. New York: Springer. - 1985. - C.31-47.

64. Lu H., Carey M. Some Experimental Results on Distributed Join Algorithms in a Local Network // Proc. 11th Int. Conf. Very Large Databases, Stockholm, Sweden, Aug. 1985. Los Altos, Calif. - 1985. - C.425-432.

65. Luk W.S. On Estimating Block Accesses in Database Organization // Commun. ACM. 1983.-26.-№ 11.-C.945-947.

66. Lynch C. Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values // Proc. 14th Int. Conf. Very Large Data Bases, Los Angeles, Ca, Aug.-Sept. 1988. Los Altos, Calif. - 1988. - C.240-251

67. Mackert L., Lohman G. R* Optimizer Validation and Performance Evaluation for Distributed Queries // Proc. 12th Int. Conf. Very Large Data Bases, Kyoto, Japan, Aug. 1986. Los Altos, Calif. - 1986. - C. 149-159.

68. Maclcert L., Lohman G. R* Optimizer Validation and Performance Evaluation for Local Queries // Proc. ACM SIGMOD Int. Conf. Manag. Data, Washington, D.C., May 28-30, 1986. -New York. 1986. - C. 173-180.

69. Merret Т. H. Why sort/Merge gives the best implementation of the natural join // ACM SIGMOD. 1983. - 13. - №2.

70. MS SQL Server 2000 Books Online

71. Piatetslci-Shapiro G., Connel C. Accurate Estimation of the Number of Tuples Satisfying a Condition // ACM SIGMOD Record. 1984,- 19. - № 2. - C.256-276.

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

73. Rosenthal A., Reiner D. An Architecture for Query Optimization // Proc. ACM

74. SIGMOD Int. Conf. Manag. Data, Orlando, Fl., June 2-4, 1982. New York. - 1982. - C.246-255.

75. Rowe L.A., Stonebraker M. The Commercial INGRES Epilogue // The INGRES Papers: The Anatomy of a Relational Database Management System. Reading, Mass.: Addison-Wesley. 1985. - C.121-128.

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

77. Rzeczlcowslci W., Subieta K. Stored Queries A Data Organization for Query Optimization // Data and Knowledge Eng. - 1988. - 3. - № 1. - C.29-48.

78. Sagiv Y., Yannalcalcis M. Equivalences Among Relational Expressions with Union• and Difference Operators // J. ACM. 1980. - 27. - № 4. - C.633-655.

79. Segev A. Optimization of Join Operations in Horizontally Partitioned Database Systems // ACM Trans. Database Syst. 1986. - 11. - № l. - C.48-80.

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

81. Sherhar S., Strivastava J., Dutta S. A Formal Model of Trade-off between Optimization and Execution Costs in Semantic Query Optimization // Proc. 14th Int.

82. Conf. Very Large Data Bases, Los Angeles, Calif., Aug.-Sept. 1988. Los Altos, Calif. - 1988.-C.457-467.

83. Special Issue on Query Optimiztion // IEEE Database Eng. 1982 -5. №3.

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

85. Stonebraker M. Implementation of Integrity Constraints and Views by Query Modification // Proc. ACM SIGMOD Int. Conf. Manag. Data, San Jose, Calif., May 23-26, 1975. New York. - 1975. - C.65-78.

86. Stonebraker M., Neuhold E. A Distributed Data Base Version of INGRES // Proc. 2nd Berkley Workshop Distrib. Data Manag. and Comput. Networks, Berkley, Calif., May 1977. Berkley, Calif. - 1977. - C. 19-36.

87. Stonebraker M.R., Wong E., Kreps P., Held G. The Design and Implementation of INGRES // ACM Trans. Database Syst. 1976. - 1. - № 2. - C. 189-222.

88. Stonebraker M., Woodfil L., Ranstrom J., Murphy M., Meyer M., Allman E. Performance Enhancements to a Relational Database System // ACM Trans. Database Syst. 1983. - 8. - № 2. - C.189-222.

89. Subieta K., Rzeczkowski W. Query Optimization by Stored Queries // Proc. 13th Int. Conf. Very Large Data Bases, Brington, England, Sept. 1987. Los Altos, Calif. -1987.-C.369-380.

90. Talbot S. An Invistigation into Optimization of Relational Query Languages // Comput. J. 1984. - 27. - № 4. - C. 301-309.

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

92. Warren D.H.D. Efficient Processing of Interactive Relational Database Queries Expressed in Logic // Proc. 7th Int. Conf. Very Large Data Bases, Cannes, France, Sept. 3-11, 1981. New York. - 1981. - C.345-352.

93. West V. An Optimizer for a Relational Database Command Language // Software: Pract. andExper.- 1983.- 13. 11. C.1005-1012.

94. Whang K.-Y., Krishnamurthy R. Query optimization in a Memory-Resident Domain Relational Calculus Database System // 1990. 15. - № 1. - C.8-11.

95. Whang К., Wiederhold G., Sagalowicz D. Estimating Block Accesses in Database Organizations A Closed Noniterative Formula // Commun. ACM. - 1983. -26. -№ 11.-C.940-944.

96. Wong E., Youssefi K. Decomposition A Strategy for Query Processing // ACM Trans. Database Syst. - 1976. - 1. - № 3. - C.223-241.

97. Yao S.B. An Attribute Based Model for Database Access Cost Analyses // ACM Trans. Database Syst. 1977. - 2. - № 1. - C.45-67.

98. Yao S.B. Approximating Block Acess in Database Organizations // Commun'. ACM. 1977.-20.-№ 4,-C.260-261.

99. Yao S.B. Optimization of Query Evaluation Algorithms // ACM Trans. Database Syst. 1979. - 4. - № 2. - C.133-155.

100. Yu C.T, Gun K.-C., Zhang W., Templeton M., Brill D., Chen A.L.P. Algorithms to Process Distributed Queries in Fast Local Networks // IEEE Trans. Comput. 1987.- 36.-№ 10. - C.l 153-1164.

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