Оглавление
1. Оптимизация SQL-запросов. 1
1.1. Последовательность
оптимизации запросов и используемые законы реляционной алгебры 1
1.1.1. Основные
шаги оптимизации. 1
1.1.2. Законы
реляционной алгебры.. 1
1.2. Построение
логического плана. 1
1.2.1. Преобразование
запроса в формулу реляционной алгебры.. 1
1.2.2. Оптимизация
формулы реляционной алгебры.. 1
1.2.3. Иллюстрация
логической оптимизации. 1
1.3. Пример
построения логического плана. 1
1.3.1. Оптимизация
запроса. 1
1.3.2. Порядок
выполнения запроса на логическом уровне. 1
1.4. Построение
физического плана. 1
1.4.1. Шаги
построения физического плана. 1
1.4.2. Отличие
физического плана от логического. 1
1.4.3. Методы
выбора записей из исходной таблицы.. 1
1.4.4. Оценка
числа кортежей в промежуточной таблице Q.. 1
1.4.5. Оценка
числа блоков в промежуточной таблице Q.. 1
1.5. Порядок
соединения таблиц. 1
1.5.1. Левостороннее
дерево соединений. 1
1.5.2. Кустовое
дерево соединений. 1
1.5.3. Правостороннее
дерево соединений. 1
1.6. Методы
соединения таблиц. 1
1.6.1. Метод
вложенных циклов (NLJ – Nested Loop Join) 1
1.6.2. Метод
сортировки-слияния (SMJ – Sort Merge Join) 1
1.6.3. Метод
хешированного соединения (HJ – Hash Join) 1
1.6.4. Число
кортежей, блоков и мощности атрибутов в соединении. 1
1.7. Поиск
физического плана с минимальной стоимостью.. 1
1.7.1. Алгоритм
поиска для левостороннего дерева соединений. 1
1.7.2. Формат
экземпляра структуры данных. 1
1.7.3. Спецификации
процедуры AccessPlan. 1
1.7.4. Спецификации
процедуры JoinPlan. 1
1.7.5. Спецификации
процедуры OptPlanReturn. 1
1.8. Пример
построения оптимального физического плана. 1
1.8.1. Логический
план. 1
1.8.2. Алгоритм
поиска оптимального физического плана. 1
1.8.3. Определение
метода выбора записей из исходной таблицы R1. 1
1.8.4. Определение
метода выбора записей из исходной таблицы R2. 1
1.8.5. Оценка
соединения Q1 и Q2 методом NLJ. 1
1.8.6. Оценка
соединения Q1 и Q2 методом SMJ. 1
1.8.7. Выбор
метода соединения Q1 и Q2 и
заполнение структуры.. 1
1.8.8. Оценка
и выбор метода соединения Q2 и Q1. 1
1.8.9. Вывод
физического плана. 1
Поступающий на сервер SQL-запрос подвергается оптимизации с целью уменьшения времени его
выполнения. При этом оптимизатор запросов выполняет следующие шаги:
I. Строит логический план выполнения запроса (дерево логических операций).
II. Строит оптимальный физический план выполнения запроса (дерево физических
операций).
III. Реализует полученный оптимальный физический план выполнения запроса.
Примечание. Оптимизатор называется восходящим, если при
построении оптимального физического плана он просматривает логический план от
листьев к корню. Если логический план просматривается от корня к листьям, то такой
оптимизатор называется нисходящим.
Для построения логического плана выполнения запроса используются законы
реляционной алгебры, некоторые из которых рассмотрены ниже.
1.Закон коммутативности декартова произведения.
Имеет место равенство:
R1 × R2 = R2
× R1 ,
где R1 и R2 – отношения (таблицы).
2. Закон ассоциативности декартова произведения.
Справедливо равенство:
(R1 × R2) × R3 = R1 × (R2 × R3),
где R1, R2 и R3 – отношения (таблицы).
3. Закон каскада проекций.
Если 
, где {a1, …, an} и {b1, …, bm} – некоторые множества атрибутов, то имеет место
следующее равенство:
.
4. Закон каскада селекций.
Если условие F является конъюнкцией нескольких условий, т.е. 
,
то справедливо следующее равенство:
.
5. Закон перестановки проекции и селекции:
1. В условие F входят атрибуты только из множества {a1, …, an}.
Имеет место следующее равенство:
.
2. В условие F входят атрибуты не только из множества {a1, …, an}.
Справежливо следующее равенство:
,
где b1, …, bm – атрибуты таблицы R, которые входят в условие F, но не принадлежат множеству {a1, …, an}.
6. Закон перестановки селекции и декартова произведения.
Если условие f1 включает в себя только атрибуты отношения R1, то имеет место следующее равенство:
.
Следствие. Пусть , причем в f1 входят атрибуты только из отношения R1, а в f2 входят атрибуты только из R2. В этом случае справедливо следующее равенство:
.
7. Закон перестановки селекции и объединения.
Имеет место следующее равенство:
.
Примечание. В языке SQL операция объединения отношений моделируется с помощью операции UNION.
8. Закон перестановки селекции и разности отношений.
Справедливо следующее равенство:
,
где R1 – R2 – множество кортежей, которые принадлежат отношению R1 и не принадлежат R2.
9. Закон перестановки проекции и декартова произведения.
Пусть {b1, …, bn} – некоторые атрибуты из R1, {с1, …, сm} – некоторые атрибуты из R2. Имеет место следующее равенство:
10. Закон перестановки проекции и объединения.
Справедливо следующее равенство:
.
При построении логического плана выполнения SQL-запроса выполняются следующие действия:
1. Запрос преобразуется в формулу реляционной алгебры (явно или
неявно).
2. Выполняется преобразование (оптимизация) этой формулы.
Оператор SELECT языка SQL может быть представлен в виде следующей формулы
реляционной алгебры (здесь не рассматриваются функции агрегирования,
группирования и удаления дубликатов):
π A(σF(R1×
R2 × … ×
Rn)), (5.1)
где R1× R2 × … × Rn – декартово произведение отношений (таблиц), указанных
за ключевым словом FROM;
σF – операция селекции кортежей декартова произведения в
соответствии с условием F, указанным за ключевым словом WHERE;
π A – проекция селекции на множество атрибутов А,
перечисленных за ключевым словом SELECT.
Ниже приведён пример преобразования запроса.
Запрос: "Найти фамилию пользователя с кодом 3".
Оператор SELECT:
SELECT фамилия
FROM пользователь
WHERE код_пользователя = 3;
Формула реляционной алгебры:
При оптимизации формулы используются следующие правила:
1. Если условие F является конъюнкцией нескольких условий (
), то
переместить каждую селекцию 
внутрь декартова
произведения, используя законы 1, 4, 6, 7, 8.
2. Переместить каждую проекцию внутрь декартова произведения, используя
законы 1, 3, 5, 9, 10.
3. После указанных преобразований по возможности скомбинировать каждый
каскад селекций в одиночную селекцию и каждый каскад проекций в одиночную
проекцию. Это позволяет выполнить все операции селекции и проекции за один
проход отношения, полученного после соединения таблиц. Например, 
.
В результате использования правил 1–3 формула реляционной алгебры
(5.1), соответствующая исходному запросу, преобразуется в следующую формулу:
, (5.2)
где
– условие, сформулированное в исходном запросе
SELECT;
f – условие соединения подзапросов {Qi}.
Подчеркнутые в приведённой выше формуле отношения Q1, …, Qn имеют меньшую размерность, чем исходные отношения R1, …, Rn , и потому запрос по формуле (5.2) выполняется быстрее,
чем по формуле (5.1).
По формуле (5.2) можно построить логический план, представленный на рис. 1.1.
Рис. 1.1. Логический план выполнения запроса,
соответствующий формуле (5.2)
1. Выполнение запроса по формуле π A(σF(R1× R2 × … × Rn)), до оптимизации, иллюстрируется рисунком (рис. 1.2).
Рис. 1.2. Выполнение запроса по
формуле (5.1).
2. Выполнение запроса по формуле
, после оптимизации, иллюстрируется рисунком
(рис. 1.3).
Рис. 1.3. Выполнение запроса после
оптимизации по формуле (5.2).
В случае отсутствия оптимизации запроса вначале нужно определить декартово
произведение исходных таблиц R1, …, Rn , затем выполнить селекцию σF и взять проекцию πA. Если таблицы R1, …, Rn имеют большую размерность, то время выполнения запроса
будет достаточно большим. Поэтому запрос по формуле (5.2) выполняется быстрее,
так как отношения Q1, …, Qn имеют меньшую размерность, чем исходные отношения R1, …, Rn .
Примечание. Если исходные таблицы R1, …, Rn размещаются на разных серверах или на одном
суперкомпьютере, то подзапросы Q1, …, Qn могут выполняться параллельно.
Предположим, что на сервер СУБД поступает запрос SELECT. На сервере хранятся две таблицы,
участвующие в запросе (рис. 1.4).
Рис. 1.4. Исходные таблицы на сервере
СУБД.
Предположим, что клиент, связанный с сервером СУБД, выдал следующий
запрос: "Найти значения остатков, большие 1500, на счетах пользователя с
кодом 3". Соответствующий запрос SELECT имеет следующий вид:
SELECT остаток
FROM R2
WHERE остаток > 1500 AND номер_счета IN
(SELECT номер_счета
FROM R1
WHERE код_пользователя = 3);
Этот оператор SELECT преобразуется в формулу реляционной алгебры
(см. п. 1.2.1):
Эта формула подвергается оптимизации. Оптимизатор вначале строит логический
план выполнения запроса, используя законы реляционной алгебры (см. пункты 1.1.2 и 1.2.2, номера законов показаны над равенствами):
Последняя формула – результат оптимизации, здесь подчёркнуты подзапросы.
По этой формуле оптимизатор строит логический план выполнения запроса (рис. 1.5).
Рис. 1.5. Логический план выполнения
запроса в графическом виде.
1. Определение промежуточных таблиц Q1 и Q2 .
На основе полученной формулы
(5.3)
определяются промежуточные таблицы Q1 и Q2 :
1. 
Из таблицы R1 (см. рис. 1.4) получим
Q1: номер_счета
2. 
Из таблицы R2 (см. рис. 1.4) получим
Q2: номер_счета остаток
2. Соединение промежуточных таблиц Q1 и Q2 .
Выполняется соединение промежуточных таблиц Q1 и Q2 и передача результата клиенту. При этом реализуется
формула
:
а) Q = Q1´Q2 :
R1.номер_счета R2.номер_счета R2.остаток
|
102
|
101
|
2000
|
|
102
|
102
|
3000
|
б) Z = sR1.номер_счета=R2.номер_счета(Q):
R1.номер_счета R2.номер_счета R2.остаток
в) pR2.остаток(Z):
остаток
Эта величина остатка посылается клиенту.
Примечание. Если таблицы R1 и R2 хранятся на других различных серверах S1 и S2, то подзапросы Q1 и Q2 преобразуются в запросы SELECT и направляются на серверы S1 и S2, где параллельно выполняются.
Подзапрос Q1 преобразуется к виду:
SELECT номер_счета
FROM R1
WHERE код_пользователя=3;
Подзапрос Q2 преобразуется к виду:
SELECT номер_счета, остаток
FROM R2
WHERE остаток > 1500;
После выполнения запросов SELECT результаты возвращаются на исходный сервер СУБД, и
там выполняется их соединение.
При построении оптимального физического плана выполнения SQL-запроса (дерева физических операций) выполняются
следующие действия:
1. Последовательно строится множество физических планов на основе логического
плана (см. разделы 1.2, 1.3). Физические планы в основном отличаются следующим:
а) методом выбора записей из исходных таблиц (методом реализации подзапросов
);
б) порядком соединения таблиц;
в) методом соединения таблиц (т.е. методом реализации операции естественного
соединения 
).
2. Для каждого физического плана рассчитывается стоимость его выполнения.
Выбирается физический план с наименьшей стоимостью.
Логический план не указывает на то, как должны быть реализованы
операции реляционной алгебры (проекция, селекция, декартово произведение, естественное
соединение). Физический план определяет, как эти операции будут
реализовываться.
Например, логический план может быть реализован с помощью физического
плана, представленного на рис. 1.6.
Рис. 1.6. Логический и физический
планы выполнения запроса.
Физический план выполняется в следующей последовательности.
1. Здесь операции 
реализуются следующим
образом: читается вся таблица R1 (TableScan(R1)) и затем каждая запись проверяется, удовлетворяет
ли она логическому условию F1, и если да, то из нее выделяются атрибуты, входящие в
множество A1 (
). Получившаяся
промежуточная таблица является правым аргументом соединения.
2. Операции 
реализуются следующим образом: с
помощью индекса читаются записи таблицы R2, удовлетворяющие подусловию φ (IndexScan(R2, φ)). Здесь φ – некоторое подусловие
условия F2 по атрибуту, который имеет индекс.
Примеры подусловий φ: a = 5, a > 5, a ≥ 5, a < 5, a ≤ 5 (a – индексированный атрибут таблицы R2).
Считанные записи фильтруются (
).
Получившаяся промежуточная таблица является левым аргументом соединения.
3. Выполняется естественное соединение промежуточных таблиц, полученных
на первом и втором шагах, методом сортировки и слияния (SMJ); тут же из получившегося результата выделяется
множество атрибутов A.
Оптимизатор для каждого физического плана рассчитывает стоимость. Эта
стоимость равна сумме составляющих. Для данного примера имеем:
Каждая из этих составляющих, в свою очередь, включает процессорную составляющую
и составляющую дискового ввода-вывода:
C = CCPU + CI/O .
После перебора нескольких физических планов оптимизатор выбирает план с
минимальной стоимостью.
1. Чтение всех записей таблицы и их
фильтрация.
Схематично эту операцию (TableScan + Filter) можно представить в следующем виде (рис. 1.7, нижние индексы в обозначениях таблиц и условий
поиска будем пока опускать).
Рис. 1.7. Чтение всех записей.
Стоимость работы процессора и дискового ввода-вывода рассчитывается по
формулам:
CCPU = T(R) · Cfilter , (5.4)
CI/O = B(R) · CB ,
где
T(R) – число кортежей (записей) в исходной
таблице R;
B(R) – число физических блоков таблицы R;
Сfilter
– время фильтрации одной записи в ОП;
CB – время чтения/записи одного блока на диск.
2. Чтение записей с помощью индекса и
их фильтрация.
Схема операции (IndexScan + Filter) представлена на рис. 1.8.
Рис. 1.8. Чтение записей с помощью
индекса.
Стоимость работы процессора и подсистемы ввода-вывода определяются
следующими выражениями:
где
T(R) – число записей в таблице R;
B(R) – число блоков таблицы R;
I(R,a) – мощность атрибута "а" в таблице R (число различных значений);
B(Index(R,a)) – число блоков на листовом уровне индекса по атрибуту "а";
Сfilter
– время фильтрации одной записи в ОП;
CB – время чтения/записи одного блока на диск;
k – мощность атрибута "а" в запросе (число различных значений,
указанных в подзапросе φ).
Индекс по атрибуту является кластеризованным, если порядок записей в блоках
таблицы такой же, как и в листовых блоках индекса.
Мощность атрибута в запросе (параметр k) можно оценить с помощью следующих выражений:
(5.6)
Величину 
в
формулах (5.5) можно интерпретировать как вероятность, что запись таблицы R удовлетворяет
условию φ по
атрибуту "а".
Число кортежей оценивается с помощью следующей формулы:
T(Q) = T(R)·p , (5.7)
где
Q=sF(R) – промежуточной таблица, соответствующая подзапросу Q,
T(Q) – оценка числа кортежей в промежуточной
таблице Q,
T(R) – общее число кортежей в исходной
таблице R,
p – вероятность того, что кортеж из R удовлетворяет условию поиска F.
Для расчета вероятности p можно воспользоваться следующими рекурсивными выражениями:
1. Пусть
F = f1 AND f2 . Тогда
p = p1p2 ,
где pi – вероятность того, что запись из R удовлетворяет подусловию fi (i=1,2).
2. Пусть
F = f1 OR f2 . Тогда
p = p1 + p2 – p1p2
.
3. Пусть F = NOT f1 . В этом случае
p = 1 – p1 .
Если в приведенных выше случаях 1–3 fi – подусловие по какому-либо атрибуту "а",
то вероятность pi
рассчитывается по следующей формуле:
,
где k – мощность атрибута в подзапросе (см.
формулу (5.6)),
I(R,a) – мощность атрибута "а" в таблице R.
Ниже приведён пример расчёта числа кортежей в
промежуточной таблице.
Пусть таблица R включает атрибуты (a, b, c). Число кортежей T(R) = 1000. Мощности атрибутов: I(R,a) = 5, I(R,b) = 10, I(R,c) = 2. Для простоты полагаем, что a, b, c – натуральные положительные числа.
Пусть задано условие выбора записей таблицы R:
F = (a < 3 OR b ³ 5) AND c = 2
Требуется оценить число записей, удовлетворяющих условию F.
Решение.
1. f3 = f1 OR f2
2. F = f3 AND f4
– вероятность того, что запись из R удовлетворяет условию F.
3. T(Q) = T(R)·p = 1000·0,38 = 380 – оценка числа записей,
удовлетворяющих условию F.
Число блоков в промежуточной таблице можно оценить при помощи следующей
формулы:
,
где
Q=sF(R) – промежуточной таблица, соответствующая подзапросу Q,
T(Q) - оценка числа кортежей в промежуточной
таблице (см. п. 1.4.4),
LB – длина блока (т.е. число записей в блоке),
- операция округления с избытком.
Существуют три вида деревьев соединений:
1. Левостороннее дерево соединений.
2. Кустовое (ветвящееся) дерево соединений.
3. Правостороннее дерево соединений.
1.5.1. Левостороннее дерево соединений
Рис. 1.9. Левостороннее дерево
соединений.
В данном варианте в каждом соединении правым аргументом является исходная
таблица. Этот порядок соединения имеет следующие преимущества:
·
число
переборов вариантов соединений меньше, чем для кустового дерева (для
левостороннего дерева оно равно n!, где n – число соединяемых
таблиц);
·
для
этого типа дерева достаточно просто организовать каналы обработки.
Канал обработки – это возможность передачи результатов выполнения
одной операции на вход другой операции через оперативную память (без промежуточного
запоминания на диске).
Рассмотрим операции соединений 1 и 2 на рис. 1.9: (R
S)T. Схема выполнения этих операций показана
на рис. 1.10.
Рис. 1.10. Организация каналов
обработки.
В канале только левый аргумент может быть опорным (т.е. храниться в оперативной
памяти). Правый аргумент соединения называется тестируемым и может
располагаться на диске. Если таблица подзапроса R и результат соединения 
(см. рис. 1.10) умещаются в оперативной памяти, то использование
каналов позволяет организовать однопроходной алгоритм соединения таблиц
(исходные таблицы R1, S1, T1 читаются с диска один раз).
Можно отметить следующий недостаток рассмотренного порядка соединения
таблиц: выбирается квазиоптимальный план, так как перебирается ограниченное
число вариантов (n!),
поскольку правый аргумент – это всегда исходная таблица.
Рис. 1.11. Кустовое дерево соединений.
Здесь таблицы могут соединяться в произвольном порядке.
Этот метод обеспечивает поиск оптимального плана, так как перебираются
все возможные варианты соединения таблиц. Но часто полный перебор всех деревьев
соединений занимает много времени. Также при выполнении соединений таблиц
имеются сложности в организации каналов, так как возрастают требования к объёму
оперативной памяти.
Например, для реализации однопроходного алгоритма соединения таблиц,
представленных на рис. 1.11, необходимо, чтобы в оперативной памяти размещались
таблицы R и , T и 
.
Рис. 1.12. Правостороннее дерево соединений.
В данном варианте в каждом соединении левым аргументом является исходная
таблица.
Этот способ практически не используется, так как для реализации однопроходного
алгоритма соединений необходимо, чтобы в ОП размещались (не одновременно)
таблицы T, S, R и результаты промежуточных соединений.
Ниже рассматриваются три метода соединения таблиц:
·
метод
вложенных циклов (NLJ – Nested Loop Join),
·
метод
сортировки-слияния (SMJ – Sort Merge Join),
·
хешированное
соединение (HJ – Hash Join).
При этом методе каждая запись первой таблицы сравнивается с каждой записью
второй таблицы (рис. 1.13, сравнение выполняется по номеру счёта). В общем
случае условие сравнения может быть произвольным.
Рис. 1.13. Метод соединения NLJ.
Формулы оценки стоимости соединения при использовании метода NLJ зависят от:
1) используемого дерева соединений; в дальнейшем будем полагать, что используются
левосторонние деревья и применяются каналы,
2) назначения буферов ввода-вывода (рис. 1.14).
Рис. 1.14. Схема назначения буферов ввода-вывода.
В этом случае формулы для вычисления стоимости соединения NLJ следующий вид:
(5.8)
где
T(Q1), T(Q2) – число кортежей в таблицах подзапросов Q1 и Q2;
B(Q1) – число блоков в таблице Q1;
СI/O(Q2) – время ввода-вывода для получения таблицы Q2;
b – число блоков в буфере для Q1;
Ccomp – время соединения (сравнения) двух кортежей из
таблиц Q1 и Q2 в оперативной памяти (ОП);
- округление с недостатком.
Во второй формуле учитывается возможность многопроходного варианта соединения
таблицы Q2, если таблица Q1 не умещается в "b" блоках буфера оперативной памяти. Округление
берётся с недостатком, так как одно чтение таблиц с диска учитывается в
стоимости выбора записей из исходных таблиц.
Соединение таблиц включает следующие шаги:
1. Соединяемые таблицы сортируются по атрибуту соединения (обозначим
его через "а").
2. Организуется вложенный цикл, где выполняется сравнение значений атрибутов
соединения.
Условием соединения может быть только равенство атрибутов соединения.
Пример выполнения соединения методом сортировки-слияния приведен на рис. 1.15.
Рис. 1.15. Метод соединения SMJ.
Выполняется сравнение записей, на которые указывают указатели таблиц Q1 и Q2 . Перемещение указателей выполняется следующим
образом: если выполняется условие "<", то осуществляется
перемещение указателя Q1 к следующей записи; если выполняется условие
">", то к следующей записи перемещается указатель Q2 ; при "=" указатели не перемещается и
выполняется сравнение со следующей записью таблицы Q2.
Будем полагать, что используются левосторонние деревья и каналы. Схема
назначения буферов приведена на рис. 1.16.
Рис. 1.16. Схема назначения буферов.
Формулы для оценки стоимости соединения SMJ имеют следующий вид.
Здесь
T(Q1), T(Q2) – число кортежей в таблицах Q1 и Q2;
B(Q1), B(Q2) – число блоков в таблицах Q1 и Q2;
I(Q1,a), I(Q2,a) – мощности атрибутов соединения "а" в таблицах Q1 и Q2;
b – число блоков в ОП, отводимых под сортировку таблицы Q1 или Q2;
Ccomp – время соединения двух кортежей из таблиц Q1 и Q2 в ОП;
Cmove – время перемещения одного кортежа в ОП при
сортировке;
CB – время чтения/записи одного блока на диск;
- округление с избытком;
- округление с недостатком;
- не учитывается, если таблицы были уже
отсортированы перед началом соединения.
Некоторые формулы требуют пояснений. Рассмотрим сначала, как выполняется
сортировка записей достаточно большой таблицы.
Блоки 1¸b таблицы R читаются в буфер (рис. 1.17) и записи этих блоков сортируются. Результат
сортировки сохраняется в виде файла. Затем читаются следующие "b" блоков (b¸2b, см. рис. 1.17) и их записи также сортируются, результат сортировки
сохраняется во втором файле и т.д.
Рис. 1.17. Чтение большой таблицы в
буфер из b блоков.
Сохранённые файлы представлены в виде уровня 1 на рис. 1.18.
Известно, что число операций сравнений и перемещений при сортировке
пропорционально величине 
, где 
- число сортируемых записей. 
- это количество файлов уровня 1.
Поэтому для одного файла 
. С учётом числа файлов
получаем первое слагаемое в формуле 3 (см. выражения (5.9)).
Рис. 1.18. Последовательное укрупнение
отсортированных промежуточных файлов.
Далее из 1-го файла уровня 1 записи читаются в 1-й блок буфера, из 2-го
файла уровня 1 записи читаются во 2-й блок и т.д., и из b-го файла уровня 1 записи читаются в b-й блок (рис. 1.19). В каждом блоке записи уже отсортированы на
предыдущем этапе. Поэтому сравниваются первые записи этих блоков по атрибуту
сортировки (b сравнений). Запись с минимальным значением
атрибута перемещается в файл (одно перемещение). Остальные записи
соответствующего блока сдвигаются вверх (блок работает как стек). Затем снова
сравниваются первые записи b блоков по атрибуту сортировки и т.д. Если записи в каком-либо блоке
исчерпаны, то в этот блок подгружаются записи из связанного с ним файла. После
обработки таким способом b файлов уровня 1 будет сформирован файл уровня 2 (см. рис. 1.18), записи в котором отсортированы. Далее в блоки
буфера подгружаются записи следующих b файлов уровня 1 и т.д.
По аналогичной схеме (см. рис. 1.19) объединяются файлы уровня 2 и т.д. В конце концов,
будет сформирован один отсортированный результирующий файл (см. рис. 1.18). Количество уровней L может быть получено из уравнения 
(число файлов на самом нижнем уровне
равно 1), т.е. 
.
Рис. 1.19. Сортировка записей из b промежуточных файлов.
На каждом уровне (кроме последнего) по описанной выше схеме (см. рис. 1.19) обрабатываются все записи таблицы R (их число равно T(R)). Это объясняет второе слагаемое в формуле 3. В файлах каждого уровня
хранятся B(R) блоков. Это объясняет формулу 4. Здесь коэффициент 2
учитывает, что каждый файл каждого уровня записывается на диск, а потом читается.
Чтение блоков таблицы R с диска (см. рис. 1.17) учитывается в стоимости выбора записей из исходной
таблицы.
В формуле 5 первое слагаемое определяет процессорное время сравнения соединяемых
записей. Если 
, то каждая запись из 
(их число равно 
)
сравнивается и соединяется с 
записями из 
(т.е. с числом записей из , приходящихся на одно значение атрибута соединения).
Константа 2 учитывает сравнения записей при перемещении указателей. Второе
слагаемое в формуле 5 связано с холостыми проверками. Количество таких
сравнений равно числу записей в , у которых значение атрибута
соединения отличается от всех значений атрибута "а" в (мощность таких значений атрибута
"а" в равно 
).
В формуле 6 учитывается возможное чтение таблиц и
после сортировки (первые два слагаемых),
а также многопроходной вариант соединения, если не все блоки с одинаковыми значениями атрибута связи
помещаются в буфере из b блоков (третье слагаемое).
При хешированном соединении выполняются следующие шаги:
1. Выбирается хеш-функция h(a).
2. Записи соединяемых таблиц хешируются, т.е. создаются хеш-разделы.
3. Выполняется соединение записей соответствующих разделов по алгоритму
NLJ или SMJ.
Этот метод используется при условии равенства атрибутов соединения для
очень больших соединяемых таблиц.
Пример двух таблиц, соединяемых методом хешированного соединения, приведён
на рис. 1.20.
Рис. 1.20. Соединяемые таблицы.
1) В качестве хеш-функции выбрано деление номера счета по модулю 10.
2) Обозначим хеш-разделы следующим образом:
Ri – множество номеров счетов из R, у которых остаток от деления на 10 равен i;
Si – множество номеров счетов из S, у которых остаток от деления на 10 равен i.
3) Соединение разделов.
Представим процесс соединения в виде следующей таблицы (табл. 1.1).
Табл. 1.1.
Результаты соединения
разделов
|
Si
Ri
|
S0=Ø
|
S1=(31,
1, 1)
|
S2=(2)
|
S3=Ø
|
S4=Ø
|
S5=Ø
|
S6=(26)
|
S7=(27)
|
S8=Ø
|
S9=Ø
|
|
R0=(10, 30)
|
–
|
|
|
|
|
|
|
|
|
|
|
R1=(1)
|
|
1
|
|
|
|
|
|
|
|
|
|
R2=(2)
|
|
|
2
|
|
|
|
|
|
|
|
|
R3=(3)
|
|
|
|
–
|
|
|
|
|
|
|
|
R4= Ø
|
|
|
|
|
–
|
|
|
|
|
|
|
R5=(25)
|
|
|
|
|
|
–
|
|
|
|
|
|
R6= Ø
|
|
|
|
|
|
|
–
|
|
|
|
|
R7= Ø
|
|
|
|
|
|
|
|
–
|
|
|
|
R8= Ø
|
|
|
|
|
|
|
|
|
–
|
|
|
R9= Ø
|
|
|
|
|
|
|
|
|
|
–
|
Соединение выполняется по диагонали, т.е. соединяются записи соответствующих
разделов. При значительных объемах таблиц выигрыш бывает значительным,
поскольку соединяются разделы, размеры которых намного меньше, чем размеры
исходных таблиц.
Возможны два варианта реализации хешированного соединения.
1. Однопроходной вариант (рис. 1.21).
Все разделы Ri хранятся в оперативной памяти. Последовательно читаются
блоки S с диска. Для каждой записи из S выполняется хеш-функция i=h(a) и значение атрибута соединения данной
записи сравнивается со значениями атрибута соединения записей раздела Ri (для краткости будем говорить данная
запись соединяется с записями раздела Ri ).
Рис. 1.21. Распределение памяти в
однопроходном варианте.
2. Двухпроходной вариант (рис. 1.22).
Таблицы R и S хешируются и их разделы {Ri} и {Si} сохраняются на диске. Далее в ОП читается весь
раздел R0 и в буфер последовательно читаются блоки раздела S0. Их записи соединяются с записями раздела R0. Далее в оперативную память читается весь раздел R1 и далее S1 поблочно соединяется с R1 и т.д.
Рис. 1.22. Распределение памяти в
двухпроходном варианте.
Теперь рассмотрим одну интересную особенность хешированного соединения.
В методах NLJ и SMJ соединяемые таблицы уже должны храниться на сервере
перед выполнением соединения. В методе HJ соединение таблиц R и S может выполняться асинхронно, по мере поступления записей этих таблиц с
других серверов (рис. 1.23).
Рис. 1.23. Асинхронное соединение
таблиц.
На рис. 1.23 цифрами обозначены следующие действия:
1 - сравнение поступившей записи с записями
соответствующего противоположного раздела;
2 – вывод соединения двух записей при
успешном сравнении атрибутов соединения;
3 – сохранение поступившей записи в
соответствующем разделе.
Данная особенность позволяет существенно сократить время соединения
таблиц.
Приведенные ниже формулы являются общими для всех рассмотренных выше
методов (NLJ, SMJ и HJ).
1. Число кортежей в соединении.
(5.10)
2. Число блоков.
3. Мощности атрибутов:
а) мощность атрибута соединения ("а") в результирующей
таблице
;
б) мощности остальных атрибутов (b)
Здесь T(Q1), T(Q2) – число кортежей в таблицах Q1 и Q2;
- оценка числа кортежей в таблице,
полученной после соединения;
I(Qi,a) – мощность атрибута "а" в таблице Qi (i=1,2);
LJOIN – число кортежей соединения в одном блоке.
Поясним 1-ую формулу из 3-х, приведённых выше. Пусть 
. В этом случае каждая запись из соединяется в среднем с записями из (считается,
что если 
, то значение атрибута связи в записи из
таблицы совпадёт со значением соответствующего
атрибута какой-либо записи из ).
Для поиска оптимального физического плана используется один из алгоритмов
динамического программирования.
Вход: логический план выполнения SQL-запроса с таблицами R1, …, Rn (см. раздел 1.2).
Выход: квазиоптимальный физический план
выполнения запроса.
//Алгоритм динамического
программирования
ДЛЯ i=1,n
AccessPlan(Ri) //определение 
КОНЕЦ ДЛЯ
ДЛЯ i=2,n
ДЛЯ всех подмножеств
таких, что |P|=i
//
|P| - количество таблиц в P
ДЛЯ всех таблиц
//
определение метода соединения 
, дерево
// соединения
таблиц (P – Qj) уже создано при выполнении
//
предыдущих циклов
JoinPlan(P – Qj,Qj)
КОНЕЦ ДЛЯ
КОНЕЦ ДЛЯ
КОНЕЦ ДЛЯ
OptPlanReturn({Q1, …, Qn}) //вывод оптимального плана
//Конец алгоритма
Алгоритм работает с массивом структур. Экземпляр структуры имеет следующий
формат:
1. W – множество имен таблиц {Qi} таких, что W=XÈY, если |W| > 1, и W – имя таблицы Qi , если |W| = 1.
2. X – подмножество исходных таблиц {Qi}, которые использованы для получения
левого аргумента соединения X
Y.
3. Y – имя таблицы Qi, которая используется в качестве правого
аргумента соединения XY.
Примечание. Если W содержит имя только одной таблицы, т.е. |W| = 1, то X и Y – пустые поля.
4. Z – текущая стоимость выполнения плана,
включающая стоимости выполнения подзапросов и промежуточных соединений, а также
стоимость соединения XY, если |W| > 1, или стоимость выполнения подзапроса, если |W| = 1.
5. ZIO – составляющая ввода-вывода в Z (CI/O).
6. V – опции:
1) T(W) – прогнозируемое число кортежей (записей) в таблице W (т.е. T(XY), если |W| > 1, или T(Qi), если |W| = 1);
2) B(W) – прогнозируемое число блоков в W;
3) {I(W, Ai)}i – мощности атрибутов в W, по которым было выполнено или будет выполняться
соединение;
4) к – идентификатор метода выбора записей из исходной таблицы (если |W| = 1) или метода соединения таблиц (если |W| > 1).
Вход: Ri – имя исходной таблицы.
Выход: заполненный экземпляр структуры str[i].
Алгоритм.
// оценка стоимости
выбора записей из Ri
для различных методов:
// j=1 – чтение всей таблицы, j=2 – использование индекса.
ДЛЯ j=1,2
Cj = CCPUj + CI/Oj
// CCPUj и CI/Oj вычисляются с помощью формул (5.4) (для j=1)
// или с помощью формул (5.5)
и (5.6) (для j=2).
КОНЕЦ ДЛЯ
// определение
оптимального метода выбора записей из таблицы Ri,
// т.е. kÎ{1,2}, заполнение экземпляра структуры str[i] (см. п. 1.7.2)
C=min (C1, C2) // здесь С=Сk
str[i] = {
{Qi},
Ø, Ø, // W, X, Y
C,
CI/O k, // Z, ZIO
{T(Qi),
B(Qi), {min{T(Qi), I(Ri, Aj)}j,
k} // V
// для заполнения полей T(Qi), B(Qi) используются формулы
// пунктов 1.4.4 и 1.4.5
}
Конец алгоритма.
Вход: список имен таблиц R=(P – Qj) и имя таблицы S=Qj (см. основной алгоритм в п. 1.7.1)
Выход: заполненный экземпляр структуры str[n].
Алгоритм.
Поиск в массиве структур
str экземпляров с номерами m1 и m2,
для которых str[m1].W=R и str[m2].W=S .
// Оценка стоимости
соединения для различных методов:
// i=1 – NLJ,
i=2 – SMJ, i=3 – HJ ;
// выбрать оптимальный
метод соединения kÎ(1,2,3).
ДЛЯ i=1,3
Ci =
CCPUi + CI/Oi
// CCPUi и CI/Oi вычисляются с помощью формул (5.8) (для i=1)
// или формул
(5.9) (для i=2); метод i=3 не рассматривается.
// Необходимая
информация для расчета по формулам
// хранится в
полях str[m1].V и str[m2].V.
КОНЕЦ ДЛЯ
C = min(C1, C2) //здесь С=Сk; пока это стоимость соединения R и S
// текущая стоимость
плана, включающая стоимости чтения
// из исходных таблиц и
стоимости промежуточных соединений
С = str[m1].Z + str[m2].Z + C
СI/O = str[m1].ZIO + str[m2].ZIO + CI/O k // дисковая составляющая
Поиск в массиве структур
str экземпляра "n", для которого str[n].W=P. Если экземпляр "n" не найден, то заполнить пустой экземпляр "n". Если экземпляр "n" найден и выполняется неравенство str[n].Z > C, то переписать экземпляр "n". Выражения для заполнения экземпляра "n":
str[n] = {P, R, S, C, CI/O , // W, X, Y, Z, ZIO
{T(P), B(P), {I(P, Ai)}i, k} } // V - см. формулы (5.10)
Конец алгоритма.
Вход: список таблиц Q={Qi}.
Выход: вывод оптимального плана.
Алгоритм.
Поиск в массиве структур
str экземпляра i, где str[i].W=Q
// Вывод шага оптимизации
Печать (Q, "=", str[i].X, "
", str[i].Y, "метод", str[i].V.k)
Если str[i].X пусто, то выйти из алгоритма
// Вывод оптимального
плана для левого аргумента соединения
OptPlanReturn(str[i].X)
// Вывод метода выбора
записей для правого аргумента
// соединения, которым
является исходная таблица.
OptPlanReturn(str[i].Y)
Конец алгоритма.
Построим оптимальный физический план для примера, который был
рассмотрен ранее в разделе 1.3.
В этом примере был построен логический план, представленный на рис.
1.24.
Рис. 1.24. Логический план выполнения
запроса.
Ниже приведены исходные данные для построения физического плана:
1. Количество записей в исходных таблицах:
T(R1)=10000, T(R2)=100000
2. Количество записей в одном блоке таблицы:
LR1= LR2= 100, LJOIN=1000
3. Индексы по атрибутам и число записей в блоке индекса (L):
таблица R1: индекс по атрибуту "код_пользователя" (L=200),
таблица R2: индекс по атрибуту "номер_счета" (L = 200).
Примечание. Записи исходных таблиц могут читаться в
отсортированном виде по своим индексированным атрибутам. Записи в таблице R1 сгруппированы по атрибуту
"код_пользователя" (кластеризованный индекс), записи в таблице R2 не сгруппированы по атрибуту "остаток".
4. Мощности атрибутов в исходных таблицах:
I(R1, код_пользователя) = 5000, I(R1, номер_счета) = 10000,
I(R2, номер_счета) = 100000, I(R2, остаток) – неизвестно.
5. Предполагается, что используются левосторонние деревья для поиска оптимального
плана и применяются каналы.
6. Некоторые параметры:
b = 10 – число блоков в буфере;
Ccomp = Cmove = Cfilter = 0,01 мс;
CB = 10 мс – время чтения/записи блока на
диск.
Для построения оптимального плана воспользуемся алгоритмом динамического
программирования (см. п. 1.7.1).
Ниже приведена
последовательность расчётов.
Определение :
1.Определение метода
выбора записей из исходной таблицы R1
(Пользователь):
AccessPlan(R1) (см. п. 1.7.3).
2. Определение метода
выбора записей из исходной таблицы R2
(Счёт):
AccessPlan(R2) (см. п. 1.7.3).
Определение метода и
порядка соединения :
3. Оценка соединения Q1 и Q2 методом NLJ:
в JoinPlan(Q1, Q2)
(см. п. 1.7.4).
4. Оценка соединения Q1 и Q2 методом SMJ:
в JoinPlan(Q1, Q2) (см. п. 1.7.4).
5. Выбор метода
соединения Q1 и Q2 и заполнение структуры:
в JoinPlan(Q1, Q2) (см. п. 1.7.4).
6. Оценка и выбор метода
соединения Q2 и Q1 (по аналогии с
пунктами 3 - 4),
сравнение вариантов:
JoinPlan(Q2, Q1) (см. п. 1.7.4).
Вывод оптимального
физического плана:
7. Вывод физического
плана:
OptPlanReturn({Q1, Q2}) (см. п. 1.7.5).
8. Представление
физического плана в графическом виде.
Алгоритм AccessPlan (см. п. 1.7.3) для таблицы R1 ("Пользователь"):
1. j = 1 – чтение всей таблицы (формулы (5.4)):
2. j = 2 – использование индекса по атрибуту
"код_пользователя" (формулы (5.5) и (5.6), здесь "а" –
"код_пользователя"):
C = C2 = 0,32 мс – минимальная стоимость.
CI/O = CI/O2 = 0,3 мс – составляющая ввода-вывода.
(п.
1.4.4).
(п. 1.4.5).
При вычислении B(Q1) полагаем, что число записей в блоке проекции πR1.номер_счета в 10 раз больше, чем в блоке таблицы R1 .
Заполнение структуры str[1] (п. 1.7.2):
str[1] = {{Q1}, Ø, Ø, 0.32, 0.3, // W, X, Y, Z, ZIO
{2, 1, {2}, 2} } //
V: {T(Q1), B(Q1), {min(T(Q1),
// I(R1,номер_счёта))}, k }
Алгоритм AccessPlan (см. п. 1.7.3) для таблицы R2 ("Счёт"):
1. j = 1 – чтение всей таблицы (формулы (5.4)):
2. j = 2 – чтения по индексу нет, так как нет индекса по
атрибуту "Остаток" (см. запрос Q2 - п. 1.8.1).
C = C1 = 11000 мс .
CI/O = CI/O1 = 10000 мс .
//При вычислении T(Q2) вероятность принята равной 1/3, поскольку
//мощность атрибута
"Остаток" в таблице R2 неизвестна.
(см.
п. 1.4.4).
(см. п. 1.4.5).
Заполнение структуры str[2] (п. 1.7.2):
str[2] ={{Q2}, Ø, Ø, 11000, 10000, // W, X, Y, Z, ZIO
{33000, 33,
{33000}, 1}} //V:{T(Q2),B(Q2),
//{min(T(Q2),I(R2,номер счёта))},k}
В алгоритме динамического
программирования (см. п. 1.7.1):
n = 2, i = 2, P = (Q1, Q2), Qj = Q2 (параметры трёх вложенных циклов).
В JoinPlan (Q1, Q2)
(см. п. 1.7.4):
R = P – Q2 = Q1, S = Q2 , "а" – атрибут "номер_счета".
Алгоритм:
m1 = 1, m2 = 2 // номера экземпляров в структуре str, т.к.
// str[m1=1].W= Q1
и str[m2=2].W= Q2
// Оценка стоимости
соединения R и S методом NLJ, i=1
// (формулы (5.8), для оценки используются данные из str[1],
// str[2] - см. пункты 1.8.3 и 1.8.4):
Продолжение
алгоритма JoinPlan (Q1, Q2) (см. п. 1.7.4):
// Оценка стоимости
соединения R и S методом SMJ, i=2
// (формулы (5.9),
используются данные из str[1], str[2] - см.
// пункты 1.8.3 и 1.8.4).
// Таблица Q2 уже отсортирована по номеру счета, так как
// имеется индекс по
этому атрибуту.
Продолжение
алгоритма JoinPlan (Q1, Q2) (см. п. 1.7.4):
// Стоимость соединения Q1 и Q2
С = min(С1 ,С2)= min(660, 340) = С2 =340 (мс) // SMJ
// Текущая стоимость
плана
С = str[1].Z + str[2].Z + C = 0,32 + 11000 + 340 @11340 (мс),
// где str[1].Z и str[2].Z – стоимости выбора записей из
// исходных таблиц R1 и R2 (см. пункты 1.8.3 и 1.8.4),
// С (справа) – стоимость
соединения по методу SMJ.
// Стоимость ввода/вывода
СI/O = str[1].ZIO + str[2].ZIO + CI/O 2 = 0,3 + 10000 + 10 ≈ 10010 (мс).
// Значения полей V структуры str[3] (формулы (5.10) в п. 1.6.4):
.
Заполнение структуры str[3] (п. 1.7.2):
str[3] = {{Q1, Q2}, {Q1}, {Q2}, // W, X, Y
11340, 10010, //
Z, ZIO
{2, 1, {2}, 2} } // V - 
, B,
I, k
В алгоритме динамического
программирования (см. п. 1.7.1):
n = 2, i = 2,
P = (Q1, Q2), Qj = Q1 .
В JoinPlan (Q2, Q1)
(см. п. 1.7.4):
R = P – Q1 = Q2, S = Q1 , "а" – атрибут "номер_счета".
Алгоритм:
m1 = 2, m2 = 1 // номера экземпляров в структуре str, т.к.
// str[m1=2].W= Q2
и str[m2=1].W= Q1
// Оценка стоимости
соединения R и S (см. формулы пунктов 1.8.5 и
// 1.8.6)
1. NLJ, i=1
2. SMJ, i=2
// Стоимость соединения Q2 и Q1
С = min(С1,С2) = С2= 340
(мс) // SMJ
// Текущая стоимость
плана
С = str[2].Z + str[1].Z + C = 11340 (мс)
Запись str[3] не
изменяется, так как старое значение str[3].Z совпадает с новым значением (C).
Алгоритм OptPlanReturn (см. п. 1.7.5):
1. 
метод 2 (т.е. SMJ)
2. Q1 = метод 2
(т.е. IndexScan(R1, код_пользователя = 3) +
Filter (реализация проекции по номеру счета)
)
3. Q2
= метод 1
(т.е. TableScan(R2) +
Filter (селекция по
условию остаток > 1500 и реализация
проекции по
остатку и номеру счета)
)
Метод чтения записей из R2 (чтение всех записей) является причиной высокой
стоимости выполнения запроса.
На рис.
1.25
представлен разработанный оптимальный физический план в графическом виде.
Рис. 1.25. Представление физического плана в графическом виде.
