Обработка запросов

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

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

Основные методы оптимизации основываются на статических показателях накапливаемых для БД (кардинальность отношений, степень отношений,наличие индексов, их число, размер блоков и др.)

Пример: необходимо определить имена всех менеджеров, которые работают в гродненском отделе компании.

SELECT *

FROM Staff, Branch b

WHERE s.bno=b.bno AND

(s.position= ‘Менеджер’ AND b.city= ‘Гродно’);

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

1. используем выборку:

σ(s.position=‘Менеджер’ Ù b.city= ‘Гродно’) ÙStaff.bno Branch.bno(Staff x Branch)

2. эквивалентный вариант:

σ position=‘Менеджер’ Ù b.city= ‘Гродно’

3. (Staff join Staff.bno=Branch.bno Branch);

(σ position=‘Менеджер’ (Staff)) join Staff.bno=Branch.bno

(σcity= ‘Гродно’ (Branch));

в таблице Staff – 1000 кортежей, в Branch – 50.

Предположим, что в таблице Staff 1000 кортежей, «Отделение» - 50.

5 из 50 менеджеров находятся в Гродно. Будем считать, что отношение не имеет индексов и никаких ключей сортировки. Сравнение будет производиться с точки зрения количества операции доступа к диску. Операция произведение потребуется 1000+50 операций для чтения исходных отношений. Затем потребуется 1000*50 операций, для того чтобы проверить заданное условие.

Общая стоимость этого захода будет:

(1000+50)+(1000+50)=1050+2*50000=101650

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

1000+2*(1000+50)=3100

и 3-ий вариант идет вначале выборка 1000 операций. Результирующий набор будет состоять не более чем из 50 строк.

Branch – 50 операций.

Результирующая таблица будет состоять из 5 строк.

Для того чтобы сделать операцию соединения надо: 50+5 операций.

1000+2*50+5+50+5=1160 операций.

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

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

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

		запрос

Время компиляции

Время выполнения

Сгенерирует код

Выражение реляционной алгебры

Системный каталог

Основная БД

Статистика БД

запрос

План выполнения

Фактическое Выполнение запроса

Генерация кода

Декомпозиция запроса

Оптимизация запроса

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

Рассмотрим основные этапы выполнения запроса

Этап декомпозиции.

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

Анализ - проведение лексического и синтаксического анализа. Уточняется присутствуют ли все определения для указанных в запросе отношений и атрибутов.

Например:

SELECT Staff_no – такого поля нет

FROM Staff

WHERE position>10 – не соответствует тип

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

Пример:

SELECT *

FROM staff_s, branch_b

WHERE s.sno=b.bno

AND (s.position= ‘Менеджер’ AND b.city = ‘Гродно’)

Схема

Дерево запроса называется дерево реляционной алгебры.

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

1. конъюнктивная. Это последовательность конъюнкции, связанных между собой операциями конъюнкции AND (Ù). Каждая конъюнкция может содержать один или более терма, соединенных операторами дизъюнкции OR (Ú). Например, (position = ‘инспектор’ Ú salary Ю 200000) Ù s.sno=b.bno

2. дизъюнкция. Это последовательность соединений, связанных между собой операциями дизъюнкции. Каждая дизъюнкция может содержать один или 2 терма, соединенных операторами конъюнкции. Пример, (position = ‘Менеджер’ Ù bno = BS) Ú (salary > 200000 bno=33).

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

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

Position = ‘ Инспектор’Ù Position = ‘Менеджер ’

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

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

Р Ù р = р

Р Ù false=false

P Ù (-p)=false

P Ù true =p

P Ú p=p

P Ú (-p)=true

P Ú false =p

P Ú true=true

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

Дата добавления: 2015-05-09