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

Глава 
3
Еще больше теории: 
алгоритмы
К настоящему времени внимательным читателям, не пропустившим ни од-
ной главы, возможно, не терпится. Мы уже перешли к третьей главе – и до 
сих пор говорим о теории! Когда же мы будем писать код?
Очень скоро! В этой главе рассматривается последняя часть обработки 
запросов, и в конце у нас будет все необходимое для понимания планов вы-
полнения.
Во второй главе рассказывается о реляционных операциях, и в ней гово-
рится, что для выполнения запросов нужны физические операции, или ал-
горитмы. Сопоставить эти алгоритмы с логическими операциями непросто; 
иногда сложная логическая операция заменяется несколькими физическими 
операциями, или несколько логических операций объединяются в одну фи-
зическую.
В этой главе мы описываем эти алгоритмы, начиная с алгоритмов извлече-
ния данных, а затем переходим к алгоритмам для более сложных операций.
Понимание этих алгоритмов позволит нам вернуться к планам выполне-
ния и лучше понять их компоненты. Таким образом, мы будем всего в одном 
шаге от нашей цели, которая состоит в том, чтобы научиться настраивать 
запросы.
с
тоимостные
 
модели
 
алгоритмов
В первой главе упоминалось несколько способов измерения производитель-
ности системы, включая время отклика, стоимость и удовлетворенность 
пользователей. Эти показатели являются внешними по отношению к базе 
данных, и хотя внешние показатели наиболее ценны, они не доступны оп-
тимизатору запросов.
Вместо этого оптимизатор использует внутренние показатели, основанные 
на объеме вычислительных ресурсов, необходимых для выполнения запроса 
или отдельной физической операции в рамках плана. Наиболее важными 

---

40

Еще больше теории: алгоритмы
ресурсами являются те, что влияют на время выполнения, а именно циклы 
процессора и количество операций ввода-вывода (чтение и запись дисковых 
блоков). Другие ресурсы, такие как память или дисковое пространство, тоже 
косвенно влияют на время выполнения; например, количество доступной 
памяти будет влиять на соотношение циклов процессора и количество опе-
раций ввода-вывода. Распределение памяти контролируется параметрами 
сервера и здесь не рассматривается.
Эти два основных показателя, циклы процессора и количество операций 
ввода-вывода, напрямую не сопоставимы. Однако для сравнения планов вы-
полнения запросов оптимизатор объединяет их в одну функцию стоимости: 
чем ниже стоимость, тем лучше план.
В течение нескольких десятилетий количество операций ввода-вывода 
было доминирующим компонентом стоимости, потому что вращающиеся 
жесткие диски работают на порядки медленнее, чем процессор. Но для со-
временного оборудования это не обязательно так, поэтому оптимизатор дол-
жен быть настроен на использование правильного соотношения. Это также 
контролируется параметрами сервера.
Стоимостная модель физической операции оценивает ресурсы, необходи-
мые для выполнения операции. Как правило, стоимость зависит от таблиц, 
указанных в качестве аргументов операции. Для представления стоимост-
ных моделей мы будем использовать простые формулы со следующими обо-
значениями: для любой таблицы или отношения 
R
символы 
TR
и 
BR
обознача-
ют количество строк в таблице и количество дисковых блоков, занимаемых 
таблицей, соответственно. Дополнительные обозначения будут вводиться по 
мере необходимости.
В следующем разделе обсуждаются физические операции и рассматри-
ваются алгоритмы и стоимостные модели для каждой из них. Поскольку 
относительная скорость процессора и внешнего хранилища может варьиро-
ваться в широких пределах, затраты на процессор и ввод-вывод рассматри-
ваются отдельно. Мы не будем говорить про логические операции проекции 
и фильт рации, которые обсуждали в предыдущей главе. Обычно они объ-
единяются с предшествующей им операцией, потому что могут применяться 
независимо к каждой строке, не завися от других строк в таблице аргумента.