Формулы оценки стоимости соединения SMJ

C CPU =[ C SORTCPU (Q 1)]+[ C SORTCPU (Q 2)]+ C JOINCPU (Q 1, Q 2)

C I / O =[ C SORTI / O (Q 1)]+[ C SORTI / O (Q 2)]+ C JOINI / O (Q 1, Q 2)

C SORTCPU (R)= T (R)⋅log b (T (R)⌈ B (R)/ b ⌉)⋅(C comp + C move)+(log b B (R)−1)⋅ T (R)⋅(b ⋅ C comp + C move)

C SORTI / O (R)=2⋅ B (R)⋅ C B

Далее возможны варианты:

• C JOINCPU (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)))⋅ C comp, если I (Q 1, a)> I (Q 2, a);

• C JOINCPU (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)))⋅ C comp, если I (Q 2, a)> I (Q 1, a).

C JOINI / 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))⋅ C B

здесь:

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 - число блоков в оперативной памяти, отводимое под сортировку этих таблиц, а также для выполнения соединения;

C comp - среднее время соединения двух кортежей из записей этих таблиц в оперативной памяти;

C move - время перемещения одной записи в оперативной памяти при сортировке;

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

верхние неполные квадратные скобки - округление с избытком;

нижние неполные квадратные скобки - округление с недостатком;

обычные квадратные скобки - необязательность, значит уже отсортировано.

Механизм сортировки таблиц

Механизм сортировки таблиц Q 1 и Q 2:

1. блоки таблицы R читаются в буфер и там сортируются. Получается файл, который сохраняется на диск;
2. в буфер читаются ещё блоки.

Таким образом, на диске будет сохранено несколько файлов, и в каждом записи будут отсортированы. Эти файлы образуют первый уровень. Каждый файл можно рассматривать как стек записей.

В буфере из 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)

Формулы оценки стоимости соединения

Расчёт числа формул: l = B (R) b l =1,

отсюда l =log b B (R)

T (R)=log b B (R)−1

Для каждой записи нужно выполнить b ⋅ C COMP + C move - это объясняет второе слагаемое.

Число уровней: log B b (R)

Число блоков: B (R). Так как пишем и читаем, то B (R)×2

Теперь разбираемся со следующей формулой:

I (Q 1, a)> I (Q 2, a) - мощность у первого больше.

Смотрим первое слагаемое: (T (Q 1) I (Q 2, a)+2)⋅ T (Q 2) - происходит соединение каждой записи из Q 2 с каждой из Q 1

Смотрим второе слагаемое: T (Q 1) I (Q 2, ar)⋅(I (Q 1, a)− I (Q 2, a))

Следующая формула:

[ B (Q 1)]... T (Q 1) I (Q 1, a)⋅⌊ B (Q 1) I (Q 2, a)⋅ b ⌋⋅ b ⋅ min (I (Q 1, a), I (Q 2, a))

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

Метод хешированных соединений (Hash Join)

Осуществляется по следующим шагам:

1. Выполняется хеш-функция, где a - атрибут соединяемых таблиц;
2. Записи соединяемых таблицы хешируются, то есть создаются разделы (R i и S i);
3. Выполняется соединение соответствующих разделов (R i ⋈ S i) по алгоритму NLJ или SMJ.

Пример хешированного соединения

Предположим, заданы две таблицы (после выполнения подзапросов).

По шагам:

1)

в качестве хеш-функции выберем остаток от деления на 10: h (a)= a mod 10

2)

R i - подмножество номеров счетов из таблицы R, у которых значение хэш-функции равно i =0..9

S i - подмножество номеров счетов из таблицы S, у которых значение хэш-функции равно i =0..9

представим эти разделы в виде таблицы. Будет 9 разделов.

 

Разделы соединяются по диагонали. Потому что если остатки от деления разные, то и номера счетов разные. Остальные смотреть не смысла, потому что разные остатки.

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

Реализация метода может быть различной.

Однопроходной вариант реализации

Разделы опорной таблицы R хранятся в оперативной памяти.

Алгоритм:

1. читаются блоки таблицы S из внешней записи;
2. для каждой записи из S выполняется хеширование атрибута соединения (i);
3. значение атрибута a сравниваются со значениями атрибута соединения в разделе R i.

Двухпроходной вариант реализации

Оперативной памяти может не хватать. Число размеров (точнее, хеш-функция) подбирается так, чтобы максимальный раздел таблицы R помещался в оперативной памяти.

При таком подходе после хеширования таблиц R и S все разделы сохраняются на диске.

Алгоритм: