Руководство по созданию эффективных запросов

Сортировка слиянием
Еще один алгоритм для естественных соединений, который называют сор-
тировкой слиянием, показан на рис. 3.10.
Рис. 3.10 

Алгоритм сортировки слиянием
На первом этапе алгоритма обе входные таблицы сортируются в порядке 
возрастания по атрибутам соединения.
После того как таблицы правильно упорядочены, на этапе слияния обе 
таблицы сканируются один раз и для каждого значения атрибута соедине-
ния вычисляется декартово произведение строк, содержащих это значение. 
Обратите внимание, что это произведение является необходимой частью 
результата соединения. Новые строки с таким же значением атрибута не 
могут появиться в оставшейся части входных данных, потому что таблицы 
упорядочены.

---

56

Еще больше теории: алгоритмы
Стоимость фазы слияния можно выразить той же формулой, что и для 
соединения хешированием, то есть она пропорциональна сумме размеров 
входных и выходных данных. Фактическая стоимость несколько ниже, по-
тому что нет необходимости в этапе построения хеш-таблицы.
Стоимость сортировки можно оценить следующей формулой:
size(R)*log(size(R)) + size(S)*log(size(S))
Алгоритм сортировки слиянием особенно эффективен, если одна или обе 
входные таблицы уже отсортированы. Это может произойти в серии соеди-
нений по одним и тем же атрибутам.
Сравнение алгоритмов
Как и в случае с алгоритмами доступа к данным, здесь нет заведомых по-
бедителей или проигравших. Любой из алгоритмов может оказаться лучше 
в зависимости от обстоятельств. Алгоритм вложенного цикла более универ-
сален и лучше всего подходит для небольших соединений с использованием 
индексов; сортировка слиянием и хеширование более эффективны для боль-
ших таблиц, если они применимы.
в
ыводы
Рассмотрев стоимостные модели алгоритмов, алгоритмы доступа к данным, 
назначение и структуру индексов и алгоритмы для более сложных опера-
ций вроде соединения, мы наконец-то набрали достаточно строительных 
блоков, чтобы взяться за результат работы планировщика запросов – план 
выполнения.
В следующей главе рассказывается, как читать и понимать планы выпол-
нения и улучшать их.

---