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

Соединение таблиц включает следующие шаги:

1. Соединяемые таблицы сортируются по атрибуту соединения (обозначим его через "а").

2. Организуется вложенный цикл, где выполняется сравнение значений атрибутов соединения.

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

Пример выполнения соединения методом сортировки-слияния приведен на рис. 1.15.

Рис. 1.15. Метод соединения SMJ.

Выполняется сравнение записей, на которые указывают указатели таблиц Q₁ и Q₂ . Перемещение указателей выполняется следующим образом: если выполняется условие "<", то осуществляется перемещение указателя Q₁ к следующей записи; если выполняется условие ">", то к следующей записи перемещается указатель Q₂ ; при "=" указатели не перемещается и выполняется сравнение со следующей записью таблицы Q₂.

Будем полагать, что используются левосторонние деревья и каналы. Схема назначения буферов приведена на рис. 1.16.

Рис. 1.16. Схема назначения буферов.

Формулы для оценки стоимости соединения SMJ имеют следующий вид.

Здесь

T(Q₁), T(Q₂) – число кортежей в таблицах Q₁ и Q₂;

B(Q₁), B(Q₂) – число блоков в таблицах Q₁ и Q₂;

I(Q₁,a), I(Q₂,a) – мощности атрибутов соединения "а" в таблицах Q₁ и Q₂;

b – число блоков в ОП, отводимых под сортировку таблицы Q₁ или Q₂;

C_comp – время соединения двух кортежей из таблиц Q₁ и Q₂ в ОП;

C_move – время перемещения одного кортежа в ОП при сортировке;

C_B – время чтения/записи одного блока на диск;

- округление с избытком;

- округление с недостатком;

- не учитывается, если таблицы были уже отсортированы перед началом соединения.

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

Блоки 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 блоков (третье слагаемое).