46. Методы доступа к данным. Типы соединений таблиц.

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

• Алгоритм соединения вложенными циклами (Nested Loops Join).

• Алгоритм соединения хэшированием (Hash Join).

• Алгоритм соединения слиянием сортированных списков (Sort Merge Join).

select d.dname, e.ename from dept d ,emp e where d.deptno = e.deptno;

Query Plan

-------------------------

SELECT STATEMENT [CHOOSE] Cost=5

NESTED LOOPS

TABLE ACCESS FULL DEPT

TABLE ACCESS FULL EMP

Алгоритм соединения вложенными циклами (Nested Loops Join) состоит из произвольного числа вложенных итераций поиска данных в каждой из соединяемых таблиц.

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

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

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

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

Преимущества:

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

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

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

Недостатки:

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

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

select empno from emp,dept where emp.deptno = dept.deptno;

Query Plan

----------------------------

SELECT STATEMENT [CHOOSE] Cost=3

HASH JOIN

TABLE ACCESS FULL DEPT

TABLE ACCESS FULL EMP

1. На основе системной статистики выбирается таблица с меньшим количествомстрок.

2. Формируется хэш на ключе соединения и отображается в области хеширования.

3. Для каждой строки основного(большого) набора выполняется таже функция хэширования на ключе соединения.

4. Результат работы хэш-функции используется для перехода в соответствующую область хэширования другого набора строк.

5. Выполняется поиск на соответствие в небольшой части области хэширования.

6. Результат успешного поиска возвращается или отправляется на следующее соединение

Преимущества:

• Соединение хэшированием существенно быстрее соединения вложенными циклами. При относительно небольшом размере меньшей таблицы это самый эффективный вид соединения.

Недостатки:

• Условием соединения может быть только равенство.

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

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

Алгоритм соединения слиянием сортированных списков (Sort Merge Join). Входные таблицы должны быть отсортированы по столбцам, участвующим в условии соединения. Соединение осуществляется за одно сканирование (проход по) каждой из входных таблиц. То есть одна и та же строка считывается только один раз, что даёт преимущество перед соединением вложенными циклами. Алгоритм:

select e.deptno,d.deptno from emp e,dept d where e.deptno = d.deptno order by e.deptno,d.deptno;

Query Plan

-------------------------------------

SELECT STATEMENT [CHOOSE] Cost=17

MERGE JOIN

SORT JOIN

TABLE ACCESS FULL EMP

SORT JOIN

TABLE ACCESS FULL DEPT

1. Выполняется выборка набора строк из обеих таблиц

2. Оба набора строк сортируются по ключу соединения

3. Выполняется проверка на соответствие (слияние) отсортированных наборов строк друг с другом

4. Возвращается результат успешного слияния отсортированных наборов строк

Преимущества:

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

• Соединение слиянием в отличие от соединения с использованием хэширования может использоваться при больших размерах соединяемых таблиц.

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

Недостатки:

• Главным недостатком алгоритма является необходимость в предварительной сортировке списков. Накладные расходы на сортировку могут быть неприемлемо высокими.

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

47. Понятие оптимизатора и плана выполнения запросов. Интерпретация плана выполнения запроса.

Оптимизатор запросов или оптимизатор – встроенное в СУБД программное обеспечение, которое определяет наиболее эффективный способ выполнения SQL-выражения.

План выполнения запроса (Query Execution Plan) – последовательность шагов или инструкций СУБД, необходимых для выполнения SQL-выражения.

Стоимость (cost) – это оценка ожидаемого времени выполнения запроса с использованием конкретного плана выполнения. Оптимизатор может учитывать количество необходимых ресурсов памяти, стоимость операций ввода-вывода, времени процессора и оперативной памяти, необходимой для выполнения плана.

Режимы работы оптимизатора:

• Rule-Based Optimizer (RBO) - Логически работу RBO можно представить так: сначала он составляет полный перечень всех возможных вариантов (планов) обработки запроса, потом вычисляет для каждого варианта вес и выбирает наиболее "легкий". (Разумеется, что фактически RBO так безумно не поступает ввиду несметного числа вариантов в общем случае, но фактическая техника - это попытка приблизиться к результату, даваемому именно такой логикой).

• Cost-Based Optimizer (CBO) - CBO пытается оптимизировать затраты ресурсов компьютера на выполнение каждого отдельного запроса. Существуют, по крайней мере, три таких ресурса: процессорное время, расход оперативной памяти и число обращений к диску. Многокритериальная оптимизация не имеет общего решения, и поэтому CBO почти всегда будет вам предлагать какой-то компромисс. Вовсе не факт, что этот компромисс вас устроит, и тогда придется использовать "факторы влияния" в своих корыстных целях.

Задачи оптимизатора:

• Преобразование SQL операторов

• Выбор способа оптимизации - по стоимости или по правилам

• Выбор путей доступа

• Выбор порядка соединений таблиц

• Выбор метода соединений таблиц

• Определение наиболее эффективного плана выполнения

• Вычисление выражений и операций

Оптимизации запроса может быть разделена на следующие фазы:

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

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

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

• выбор техники (техник) для обработки операций соединения – оптимизатор выбирает одну из техник соединения (подробнее в предыдущем вопросе) в зависимости от статистических данных в каждой из таблиц.

Правила интерпретации плана выполнения запроса:

1. Первой выполняется самая внутренняя операция. Операция с самым большим отступом

2. Если операции находятся на одном уровне, порядок их выполнения – сверху вниз

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

select cust.cust_last_name,ord.order_id, ord.order_status from customers cust, щrders ord

where cust.customer_id= ord.customer_id and cust.cust_last_name='Fawcett';

Получеие плана в MSSQL:

SET SHOWPLAN_TEXT { ON | OFF } - приводит к тому, что MЫ SQL Server не выполняет инструкции Transact-SQL. Вместо этого SQL Server возвращает подробные сведения о ходе выполнения инструкций.

SET SHOWPLAN_ALL { ON | OFF } - тоже что SHOWPLAN_TEXT + предоставляет оценку требований к ресурсам для выполнения этих инструкций.