В каждом соединении правым аргументом является одна из таблиц.

Преимущества:

• число перебора вариантов меньше, чем для произвольного варианта соединения (если количество соединений n, то вариантов перебора будет n!);

• достаточно просто организивать каналы обработки - возможность передачи результата выполнения одной операции на вход другой через оперативную память (без сохранения на диск);

В канале левый аргумент называется опорным и он должен храниться в оперативной памяти. Правый аргумент называется тестируемым и он может храниться и на диске. При хранении в оперативной памяти не надо читать с диска, потому всё можно выполнить за один проход.

Недостатки:

• путём перебора порядков соединения можно выбрать квазиоптимальный план (потому что на самом деле вариантов перебора больше, чем n!, потому что правый аргумент - всегда таблица).

Кустовое

Тут таблицы могут соединяться в любом порядке.

Так что перебираются все возможные варианты соединения.

Преимущества:

• всегда выбирается оптимальный план.

Недостатки:

• если количество соединяемых таблиц велико, то перебор всех деревьев может занять много времени;

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

Правостороннее

При таком порядке левым аргументом каждого соединения является исходная таблица.

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

Методы соединения таблиц

Методы реализации естественного соединения ⋈.

Три метода:

• вложенных циклов (NLJ - Nested Loop Join);

• сортировки слияния (SMJ - Sort Merge Join);

• хэшированных соединений (Hash Join).

Лекция №12 - Оценки (продолжение)

Оптимизация SQL-запросов

Физический план

Методы соединения таблиц

Метод вложенных циклов (NLJ, Nested Loop Join)

Каждая запись первой соединяемой таблицы сравнивается с каждой записью второй соединяемой таблицы. В общем случае, условие сравнения может быть произвольным.

Зависит от:

• используемого дерева соединения (но мы в дальнейшем всегда будем использовать левосторонние);

• назначения буферов ввода/вывода.

Если на 3 операции блоков будет больше b, то лишние сохраняются на диск.

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

CJOIN=CCPU+CI/O

CCPU=T(Q1)⋅T(Q2)⋅Ccomp

CI/O=CI/O(Q2)⋅⌊B(Q1)b⌋

здесь:

T(Q1), T(Q2) оценка числа записей в таблицах подзапросов Q1 и Q2;

B(Q1) - число блоков ввода/вывода для получения таблицы Q1;

CI/O(Q2) - время ввода/вывода для получения таблицы Q2;

b - число блоков в буферах 1 и 3 (из рисунка выше);

Ccomp - время сравнения двух кортежей из Q1 и Q2 в оперативной памяти;

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

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

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

1. соединяемые таблицы сортируются по атрибуту соединения, будем обозначать его через a;

2. организуется вложенный цикл, где выполняется сравнение значения атрибута соединения в записях таблиц Q1 и Q2. Условием соединения может быть только равенство атрибутов соединения.

Рассмотрим пример реализации второго шага.

Выполняется сравнение записей в таблицах Q1 и Q2, на которые указывают указатели. Перемещение указателей выполняется следующим образом:

• если выполняется условие <, то указатель перемещается в таблицу Q1;

• если выполняется условие >, то указатель перемещается в таблицу Q2;

• если выполняется условие =, то результат соединения перемещается в выходной буфер, указатели не перемещаются и выполняется сравнение со следующей записью из таблицы Q2.

Результат соединения Q1 и Q2 получается уже отсортированным.

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

CCPU=[CSORTCPU(Q1)]+[CSORTCPU(Q2)]+CJOINCPU(Q1,Q2)

CI/O=[CSORTI/O(Q1)]+[CSORTI/O(Q2)]+CJOINI/O(Q1,Q2)

CSORTCPU(R)=T(R)⋅logb(T(R)⌈B(R)/b⌉)⋅(Ccomp+Cmove)+(logbB(R)−1)⋅T(R)⋅(b⋅Ccomp+Cmove)

CSORTI/O(R)=2⋅B(R)⋅CB

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

• CJOINCPU(Q1,Q2)=((T(Q1)I(Q1,a)+2)⋅T(Q2)+T(Q1)⋅(1−I(Q2,a)I(Q1,a)))⋅Ccomp, если I(Q1,a)>I(Q2,a);

• CJOINCPU(Q1,Q2)=((T(Q2)I(Q2,a)+2)⋅T(Q1)+T(Q2)⋅(1−I(Q1,a)I(Q2,a)))⋅Ccomp, если I(Q2,a)>I(Q1,a).

CJOINI/O=[B(Q1)]+[B(Q2)]+(T(Q1)Q2,a⋅⌊B(Q1)I(Q2,a)⋅b⌋⋅b⋅min(I(Q1,a),I(Q2,a))⋅CB

здесь:

T(Q1), T(Q2) - оценка числа записей в таблицах Q1 и Q2;

B(Q1), B(Q2) - оценка числа блоков в этих же таблицах;

I(Q1,a), I(Q2,a) - мощности атрибутов в соединении a тех же таблиц;

b - число блоков в оперативной памяти, отводимое под сортировку этих таблиц, а также для выполнения соединения;

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

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

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

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

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

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

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

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

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

2. в буфер читаются ещё блоки.

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

В буфере из b блоков сравниваются первые записи сохранённых на предыдущем этапе файлов (то есть, b файлов, если все сразу сравнивать не можем, потому что их сильно много). Минимальное среди сравниваемых записей значение пишется в файл следующего уровня, а стек, из которого это значение взяли, поднимается.

На следующем уровне история повторяется, и так до тех пор, пока не получится один итоговый файл. Записи в нём будут идеально отсортированы.

T(R)⌈B(R)/b⌉ - оценка числа записей в одном файле первого уровня.

T(R)⌈B(R)/b⌉⋅log2T(R)⌈B(R)/b⌉ - число операций сравнений и перемещений записей при сортировке одного файла первого уровня. Но таких файлов B(R)b. Перемножая их, получаем общее число операций.

Лекция №13 - Оценки (продолжение)

Оптимизация SQL-запросов

Физический план

Методы соединения таблиц

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

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

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

отсюда l=logbB(R)

T(R)=logbB(R)−1

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

Число уровней: logBb(R)

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

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

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

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

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

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

[B(Q1)] ... T(Q1)I(Q1,a)⋅⌊B(Q1)I(Q2,a)⋅b⌋⋅b⋅min(I(Q1,a),I(Q2,a))

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

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

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

1. Выполняется хеш-функция, где a - атрибут соединяемых таблиц;

2. Записи соединяемых таблицы хешируются, то есть создаются разделы (Ri и Si);

3. Выполняется соединение соответствующих разделов (Ri⋈Si) по алгоритму NLJ или SMJ.

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

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

По шагам:

1)

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

2)

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

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

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

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

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

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

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

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

Алгоритм:

1. читаются блоки таблицы S из внешней записи;

2. для каждой записи из S выполняется хеширование атрибута соединения (i);

3. значение атрибута a сравниваются со значениями атрибута соединения в разделе Ri.

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

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

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

Алгоритм:

1. подбирается хеш-функция;

2. хеширование таблицы;

3. раздел R0 целиком читается в оперативную память;

4. в оперативную память поблочно читается раздел S0;

5. для каждой записи раздела S0 значение атрибута a сравнивается со значением атрибута соединения в разделе R0;

6. считываются следующие разделы (R1, R2 и так далее).

Отличие от методов NLJ и SMJ

Метод хешированного соединения имеет важную особенность. В методах NLJ или SMJ соединяемые таблицы должны уже храниться на сервере перед выполнением соединения. А в этом методе соединение таблиц может выполняться асинхронно, по мере поступления записей с других серверов.

На серверах 1 и 2 выполняются подзапросы, а на сервере 0 выполняется соединение.

Предположим, с сервера 2 на сервер 0 поступила очередная запись из таблицы S. При этом СУБД на сервере 0 выполняет следующие действия:

1. вычисляется хеш-функция для атрибута соединения;

2. значение атрибута соединения сравнивается со значениями атрибутов соединения из раздела R1. Если есть совпадения, то выводятся результаты соединения;

3. запись сохраняется в разделе Si.

4. и так далее.

Лекция №14 - Оценки (продолжение)

Оптимизация SQL-запросов

Физический план

Методы соединения таблиц

Число кортежей, блоков и мощности атрибутов в соединениях

Справедливы для NLJ, SMJ и HJ.