Соединение двух таблиц этим методом выполняется по следующим шагам:
- соединяемые таблицы сортируются по атрибуту соединения, будем обозначать его через a;
- организуется вложенный цикл, где выполняется сравнение значения атрибута соединения в записях таблиц Q 1 и Q 2. Условием соединения может быть только равенство атрибутов соединения.
Рассмотрим пример реализации второго шага.
Выполняется сравнение записей в таблицах Q 1 и Q 2, на которые указывают указатели. Перемещение указателей выполняется следующим образом:
- если выполняется условие <, то указатель перемещается в таблицу Q 1;
- если выполняется условие >, то указатель перемещается в таблицу Q 2;
- если выполняется условие =, то результат соединения перемещается в выходной буфер, указатели не перемещаются и выполняется сравнение со следующей записью из таблицы Q 2.
Результат соединения Q 1 и Q 2 получается уже отсортированным.
Формулы оценки стоимости соединения SMJ
CCPU =[ CSORTCPU (Q 1)]+[ CSORTCPU (Q 2)]+ CJOINCPU (Q 1, Q 2)
CI / O =[ CSORTI / O (Q 1)]+[ CSORTI / O (Q 2)]+ CJOINI / O (Q 1, Q 2)
CSORTCPU (R)= T (R)⋅log b (T (R)⌈ B (R)/ b ⌉)⋅(Ccomp + Cmove)+(log bB (R)−1)⋅ T (R)⋅(b ⋅ Ccomp + Cmove)
CSORTI / O (R)=2⋅ B (R)⋅ CB
Далее возможны варианты:
- CJOINCPU (Q 1, Q 2)=((T (Q 1) I (Q 1, a)+2)⋅ T (Q 2)+ T (Q 1)⋅(1− I (Q 2, a) I (Q 1, a)))⋅ Ccomp, если I (Q 1, a)> I (Q 2, a);
- CJOINCPU (Q 1, Q 2)=((T (Q 2) I (Q 2, a)+2)⋅ T (Q 1)+ T (Q 2)⋅(1− I (Q 1, a) I (Q 2, a)))⋅ Ccomp, если I (Q 2, a)> I (Q 1, a).
CJOINI / O =[ B (Q 1)]+[ B (Q 2)]+(T (Q 1) Q 2, a ⋅⌊ B (Q 1) I (Q 2, a)⋅ b ⌋⋅ b ⋅ min (I (Q 1, a), I (Q 2, a))⋅ CB
здесь:
T (Q 1), T (Q 2) - оценка числа записей в таблицах Q 1 и Q 2;
B (Q 1), B (Q 2) - оценка числа блоков в этих же таблицах;
I (Q 1, a), I (Q 2, a) - мощности атрибутов в соединении a тех же таблиц;
b - число блоков в оперативной памяти, отводимое под сортировку этих таблиц, а также для выполнения соединения;
Ccomp - среднее время соединения двух кортежей из записей этих таблиц в оперативной памяти;
Cmove - время перемещения одной записи в оперативной памяти при сортировке;
CB - время чтения/записи одного блока на диск;
верхние неполные квадратные скобки - округление с избытком;
нижние неполные квадратные скобки - округление с недостатком;
обычные квадратные скобки - необязательность, значит уже отсортировано.
Механизм сортировки таблиц
Механизм сортировки таблиц Q 1 и Q 2:
- блоки таблицы R читаются в буфер и там сортируются. Получается файл, который сохраняется на диск;
- в буфер читаются ещё блоки.
Таким образом, на диске будет сохранено несколько файлов, и в каждом записи будут отсортированы. Эти файлы образуют первый уровень. Каждый файл можно рассматривать как стек записей.
В буфере из b блоков сравниваются первые записи сохранённых на предыдущем этапе файлов (то есть, b файлов, если все сразу сравнивать не можем, потому что их сильно много). Минимальное среди сравниваемых записей значение пишется в файл следующего уровня, а стек, из которого это значение взяли, поднимается.
На следующем уровне история повторяется, и так до тех пор, пока не получится один итоговый файл. Записи в нём будут идеально отсортированы.
T (R)⌈ B (R)/ b ⌉ - оценка числа записей в одном файле первого уровня.
T (R)⌈ B (R)/ b ⌉⋅ log 2 T (R)⌈ B (R)/ b ⌉ - число операций сравнений и перемещений записей при сортировке одного файла первого уровня. Но таких файлов B (R) b. Перемножая их, получаем общее число операций.
Лекция №13 - Оценки (продолжение)
Оптимизация SQL-запросов
Физический план
Методы соединения таблиц
Метод сортировки слияния (SMJ, Sort Merge Join)