Оптимизация потоков простых SQL-запросов тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Зверев, Дмитрий Львович

• Зверев, Дмитрий Львович
• кандидат технических наук
• 2005

Оглавление диссертации кандидат технических наук Зверев, Дмитрий Львович

Введение.

Глава 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-запросы условно делятся на простые и сложные. Простые запросы - это запросы, не содержащие соединений отношений. Такие запросы строятся на основе одного отношения. При наличии между отношениями связи типа М:М допускается использование соединения одного из исходных отношений с промежуточным отношением, реализующим эту связь. Сложные запросы - это запросы, строящиеся на основе нескольких отношений.

Целью работы является разработка и исследование метода оптимизации взаимодействия пользовательских приложений определенных типов и баз данных путем синтеза сложных 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-запросов и корректной обработки его результатов. При этом предполагается сведение различных языков программирования к одному некоторому внутреннему языку, проведение необходимых изменений и выполнение обратного преобразования. Также для дальнейших исследований остается анализ суммарного времени обработки клиентом полученных результатов до и после проведения синтеза.

Список литературы диссертационного исследования кандидат технических наук Зверев, Дмитрий Львович, 2005 год

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.