Метод сортировки слияния (SMJ, Sort Merge Join)

Соединение двух таблиц этим методом выполняется по следующим шагам:

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