Предисловие переводчика
Хотя у статьи, перевод на русский язык которой предлагается вашему вниманию, присутствует пять авторов, и все они весьма заслуженные и уважаемые в мире баз данных люди, эта статья прочно ассоциируется с именем Патриции Селинджер, поскольку именно она придумала и впервые реализовала соответствующий подход. Статья была написана на завершающем этапе проекта system r, экспериментальной реляционной СУБД компании ibm, на основе которой впоследствии были разработаны известные коммерческие продукты ibm sql/ds и гораздо более известная СУБД db2. На сайте citforum.ru можно прочитать интервью Патриции Селинджер, мой обзор литературы, посвященной system r, а также исключительно интересный материал, посвященный встрече участников проекта system r спустя 25 лет после его начала. Во всех этих публикациях можно, помимо прочего, узнать интересные факты об истории появления данной статьи.
Скорее всего, статья Пат Селинджер, является одной из наиболее часто цитируемых во всем безбрежном пространстве литературы по базам данных. И, конечно, это связано совсем не с выдающимися писательскими достоинствами авторов. Напротив, статья написана предельно скромно и просто. Ее выдающаяся роль в новой истории технологии баз данных состоит в том, что именно она заложила подход к обработке запросов в реляционных системах баз данных, которого придерживаются разработчики всех современных СУБД.
Мотивация и суть подхода состоят в следующем. При формулировке запросов к базам данных на декларативных языках высокого уровня, таких как язык sql, пользователь сообщает системе, какого рода данные его интересуют, но ничего не говорит от том, каким образом система должна обеспечить выборку этих данных. Система должна сама найти пути доступа к этим данным, т.е. сформулировать некоторый процедурный план выполнение запроса, выполнение которого приведет к желаемым результатам. Как правило, для одного sql-запроса можно построить множество таких планов, и проблема состоит в том, что требуется выбрать из этого множества один план, позволяющий достичь результатов наиболее эффективным образом. Понятно, что для такого выбора требуется критерий, и Патриция Селинджер предложила в качестве такого критерия использовать численную оценку стоимости выполнения запроса по данному плану. В статье описывается точный метод получения таких оценок и приводится ряд оценочных формул, используемых при вычислении общей оценки.
Подход Пат Селинджер основывался на нескольких упрощающих предположениях, которые далеко не всегда справедливы для реальных баз данных. В десятках, а может быть, и сотнях статей, появившихся в последующие годы, предпринимались (часто успешные) попытки ослабить и уточнить эти предположения. Эти исследования, в частности, привели к появлению отдельного направления исследований в области баз данных - накоплению, обработки и аппроксимации статистики данных. Эффективная работа современных реляционных СУБД, тем самым, оказалась возможна именно благодаря использованию, развитию и совершенствованию идей и методов Патриции Селинджер и ее коллег.
Я горжусь, что на русском языке эта статья впервые появляется именно в моем переводе. Надеюсь, что эта публикация будет приятна тем, кто, подобно мне, восхищался этой работой 25 лет назад, и будет полезна людям, только начинающим знакомиться с технологией баз данных.
Аннотация
В языке высокого уровня sql, предназначенном для формулировки запросов и манипулирования данными, операторы формулируются в непроцедурной форме, без указания путей доступа. В статье описывается, как в system r выбираются пути доступа как для простых (над одним отношением), так и для сложных запросов (таких как соединения) в соответствии с заданной пользователем спецификацией желаемых данных в виде булевского выражения из предикатов. system r - это экспериментальная система управления базами данных, разработанная для выполнения исследований над реляционной моделью данных. system r проектировалась и строилась членами исследовательской лаборатории ibm в Сан-Хосе.
1. Введение
system r - это экспериментальная система управления базами данных, основанная на реляционной модели данных и разрабатываемая в исследовательской лаборатории ibm в Сан-Хосе с 1975 г. [1]. Программное обеспечение разрабатывалось для выполнения исследований в области реляционных баз данных и не является доступным за пределами исследовательского подразделения ibm.
Предполагается знакомство читателей с терминологией реляционной модели данных, описанной Коддом [7] и Дейтом [8]. Интерфейсом пользователей system r является унифицированный язык запросов, определения данных и манипулирования данными sql [5]. Операторы sql могут выдаваться как из оперативного, ориентированного на случайного пользователя интерфейса, так из языков программирования, таких как pl/1 и cobol.
В system r пользователю не требуется знать, как хранятся кортежи на физическом уровне, и какие существуют пути доступа (например, для каких столбцов имеются индексы). От пользователя не требуется указывать в операторах sql что-либо по поводу путей доступа, которые следует использовать для выборки данных. Пользователь не указывает и порядок выполнения соединений. Оптимизатор system r выбирает как порядок соединений, так и путь доступа для каждой таблицы, указанной в операторе sql. Из многих возможных вариантов оптимизатор выбирает тот, который минимизирует "общую стоимость доступа" для выполнения всего оператора.
В этой статье затрагиваются проблемы выбора путей доступа для запросов. Выборка в операциях манипулирования данными (update, delete) обрабатывается аналогичным образом. В разд. 2 описывается место оптимизатора в процессе обработки оператора sql, а в разд. 3 описываются пути доступа к компоненту хранения, доступные для одиночной физически хранимой таблицы. В разд. 4 вводятся оценочные формулы для запросов над одной таблицей, и в разд. 5 обсуждаются соединения двух или большего числа таблиц и соответствующие оценки стоимости. Разд. 6 посвящен вложенным запросам (запросам в предикатах).
2. Обработка оператора sql
Оператор sql подвергается четырехэтапной обработке. В зависимости от происхождения и содержания оператора эти этапы могут быть отделены произвольными интервалами времени. В system r эти произвольные интервалы времени являются прозрачными для компонентов системы, обрабатывающих оператор sql. Эти механизмы и обработка операторов sql, поступающих из программ и с терминалов, более подробно обсуждаются в [2]. Здесь мы кратко обсудим лишь те шаги обработки, которые имеют отношение к выбору путей доступа.
Четыре этапа обработки оператора - это синтаксический разбор, оптимизация, генерация кода и выполнение. Каждый оператор sql посылается синтаксическому анализатору, который проверяет правильность синтаксиса. Блок запроса представляется списком select, списком from и деревом where, содержащими, соответственно, список элементов, подлежащих выборке; список таблиц, из которых должна производиться выборка; булевскую комбинацию простых предикатов, заданную пользователем. В одном операторе sql может иметься много блоков запросов, поскольку один из операндов предиката сам может являться запросом.
Если синтаксический анализатор не обнаруживает ошибок, вызывается компонент ОПТИМИЗАТОР. ОПТИМИЗАТОР собирает имена столбцов и таблиц, содержащиеся в запросе, и производит их поиск в каталогах system r, чтобы убедиться в их существовании и выбрать информацию о них.
Часть ОПТИМИЗАТОРА, занимающаяся поиском в каталогах, также получает статистические данные об указанных отношениях и данные о путях доступа к каждому из них. Эти данные используются позже при выборе пути доступа. После получения из каталога информации о типе данных и длине каждого столбца ОПТИМИЗАТОР повторно сканирует список select и дерево where для проверки отсутствия семантических ошибок и совместимости типов в выражениях и операциях сравнения в предикатах.
В заключение ОПТИМИЗАТОР производит выбор пути доступа. Прежде всего, он определяет порядок вычисления блоков запросов, содержащихся в операторе. Затем для каждого блока запроса обрабатываются отношения из списка from. Если в блоке имеется более одного отношения, оцениваются перестановки порядка соединений и методы выполнения соединений. План доступа, минимизирующий общую стоимость вычисления блока, выбирается из дерева возможных путей. Результатом является план выполнения, представленный на языке asl (access specification language) [10].
После того, как для каждого блока запроса выбирается план и представляется в дереве синтаксического разбора, вызывается ГЕНЕРАТОР КОДА. ГЕНЕРАТОР КОДА - это табличная программа, которая транслирует asl-деревья в машинный код, который предназначен для выполнения плана, выбранного ОПТИМИЗАТОРОМ. Это делается путем использования относительно небольшого числа шаблонов кода, по одному для каждой разновидности методов выполнения соединений (включая отсутствие соединений). Блоки запросов для вложенных запросов трактуются как "подпрограммы", возвращающие значения в соответствующие предикаты. ГЕНЕРАТОР КОДА подробнее описан в [9].
В течение генерации кода дерево синтаксического разбора заменяется выполняемым машинным кодом и ассоциированными с ним структурами данных. Управление немедленно передается этому коду, или код сохраняется в базе данных для последующего выполнения в зависимости от происхождения оператора (программа или терминал). В любом случае, когда код в конце концов выполняется, он обращается к внутренней системе хранения system r (rss) через интерфейс системы хранения (rsi) для сканирования каждого из физически хранимых отношений, указанных в запросе. Это сканирование производится через пути доступа, выбранные ОПТИМИЗАТОРОМ. Команды rsi, которые могут использоваться в сгенерированном коде, описываются в следующем разделе.
3. Исследовательская система хранения (research storage system)
Исследовательская система хранения (rss) - это подсистема хранения system r. Она отвечает за поддержку физического хранения отношений, путей доступа к этим отношениям, блокировок (в многопользовательской среде), а также средств журнализации и восстановления. rss представляет своим пользователям покортежный интерфейс (rss). Хотя rss может использоваться независимо от system r, здесь нас интересует использование этой подсистемы для выполнения кода, сгенерированного в system r при обработке операторов sql, как это описано в предыдущем разделе. Полное описание rss см. в [1].
Отношения хранятся в rss как коллекции кортежей с физически смежными столбцами. Эти кортежи сохраняются в страницах по 4 Кб; каждый кортеж целиком размещается на одной странице. Станицы образуют логические единицы, называемые сегментами. Сегменты могут содержать более одного отношения, но каждое отношение целиком располагается в одном сегменте. Кортежи из двух или большего числа отношений могут размещаться в одной странице. Каждый кортеж помечается идентификатором отношения, которому он принадлежит.
Основным способом доступа к кортежам отношения является его сканирование через rss. Сканирование возвращает по одному кортежу за одно обращение через заданный путь доступа. Основными командами сканирования являются open, next и close.
В настоящее время для операторов sql доступны два типа сканирования. Первый тип - это сегментное сканирование для нахождения всех кортежей данного отношения. Последовательность команд next при сегментном сканировании просто проверяет все страницы сегмента, содержащие кортежи любого отношения, и возвращает те кортежи, которые принадлежат данному отношению.
Вторым типом сканирования является индексное сканирование. Пользователем system r может быть создан индекс на одном или нескольких столбцах отношения, и для отношения может иметься любое (включая нулевое) число индексов. Эти индексы хранятся в страницах, отделенных от тех, в которых содержатся кортежи отношений. Индексы реализуются как b-деревья
, листьями которых являются страницы, содержащие наборы (ключ, идентификаторы кортежей, содержащих этот ключ). Поэтому последовательность команд next при индексном сканировании производит последовательное чтение листовых страниц индекса, получая идентификаторы кортежей, соответствующих ключу, и используя их для нахождения и возврату пользователю кортежей данных в порядке значений ключа. Листовые страницы индекса связаны в список, так что при выполнении команды next не требуются обращения к страницам индекса более высокого уровня.
При сегментном сканировании затрагиваются все непустые страницы сегмента, независимо от того, содержат ли они кортежи заданного отношения. Однако каждая страница затрагивается только один раз. При просмотре всего отношения через индексное сканирование каждая страница индекса затрагивается только один раз, но страница данных может проверяться более одного раза, если имеются два кортежа, не являющиеся "близкими" в порядке индекса. Если кортежи вставляются в сегмент в порядке индекса, и если эта физическая близость, соответствующая значениям ключа индекса, поддерживается, то мы говорим, что индекс является кластеризованным. У кластеризованного индекса имеется то свойство, что при сканировании через этот индекс будет затрагиваться только один раз не только каждая индексная страница, но и каждая страница данных, содержащая кортеж данного отношения.
Через индекс можно сканировать и не все отношение целиком. Можно указывать стартовое и стоповое значения, чтобы сканировать только те кортежи, ключ которых находится в диапазоне индексных значений. И для индексного, и для сегментного сканирования можно также задавать набор предикатов, называемых аргументами поиска (search arguments, sargs), которые применяются к кортежу, прежде чем он возвращается в программу, обратившуюся к rsi. Если кортеж удовлетворяет предикатам, он возвращается; иначе сканирование продолжается до тех пор, пока либо не будет найден кортеж, удовлетворяющий sargs, либо не исчерпается сегмент или заданный диапазон индексных значений. Это сокращает расходы путем устранения накладных расходов на вызовы rsi для кортежей, которые могут быть разумным образом отвергнуты внутри rss. Не все предикаты находятся в форме, которая может стать sargs. sargable предикат - это предикат, имеющий вид (или приводимый к виду) "ncolumn comparison-operator value". sargs представляются как булевские выражения из таких предикатов в дизъюнктивной нормальной форме.
[b]4. Стоимость путей доступа для одного отношения
В следующих нескольких разделах мы опишем процесс выбора плана выполнения запроса. Сначала мы опишем простейший случай доступа к одному отношению, а затем покажем, как этот подход расширяется и обобщается для случаев соединения двух отношений, соединения n отношений и, наконец, запросов с несколькими блоками запросов (вложенных запросов).
ОПТИМИЗАТОР анализирует предикаты в запросе и пути доступа, доступные для отношений запроса, и формулирует предсказание стоимости каждого плана доступа, используя следующую оценочную формулу:
cost = page fetches + w * (rsi calls)
Эта стоимость является взвешенной мерой ввода-вывода (числа прочитанных страниц) и использования ЦП (числа выполненных команд). w является настаиваемым коэффициентом взвешивания между вводом-выводом и ЦП. rsi calls - это предсказуемое число кортежей, возвращаемых из rss. Поскольку system r большую часть времени проводит в rss, число вызовов rsi является хорошим приближением загрузки ЦП. Таким образом, при выборе пути с наименьшей стоимостью обработки запроса ОПТИМИЗАТОР стремится минимизировать все требуемые ресурсы.
При выполнении проверки совместимости типов и семантической корректности запроса ОПТИМИЗАТОР анализирует дерево предикатов where каждого блока запроса. Считается, что дерево where находится в конъюнктивной нормальной форме, и каждый конъюнкт называется булевским сомножителем (boolean factor). Важность булевских сомножителей состоит в том, что каждый кортеж, возвращаемый пользователю, должен удовлетворять каждому булевскому сомножителю. Говорят, что индекс соответствует булевскому сомножителю, если булевский сомножитель является sargable предикатом, в котором столбец является ключом индекса; например, индекс на столбце salary соответствует предикату 'salary = 20000'. Более точно, мы говорим, что предикат или набор предикатов соответствует индексному пути доступа, если предикаты являются sargable, и столбцы, указанные в предикатах, являются стартовыми подстроками набора столбцов ключа индекса. Например, индекс на столбцах name, location соответствует name = 'smith' and location = 'san jose'. Если индекс соответствует булевскому сомножителю, то доступ с использованием этого индекса является эффективным способом удовлетворения этого булевского сомножителя. sargable булевские сомножители могут также эффективно удовлетворяться, если представляются как аргументы поиска. Заметим, что булевский фактор может являться полным деревом предикатов, связанных через or.
При поиске в каталоге ОПТИМИЗАТОР извлекает статистические данные об отношениях запроса и путях доступа, имеющихся для каждого отношения. Поддерживаются следующие статистические данные.
Для каждого отношения t:
* ncard(t) - мощность отношения t;
* tcard(t) - число страниц в сегменте, к котором хранятся кортежи отношения t;
* p(t) - доля страниц данных в сегменте, хранящих кортежи отношения t.
p(t) = tcard(t) / (число непустых страниц в сегменте).
Для каждого индекса i на отношении t:
* icard(i) - число различных ключей в индексе i;
* nindx(i) - число страниц в индексе i.
Эти статистические данные поддерживаются в каталогах system r и происходят из нескольких источников. Инициализация статистики производится при начальной загрузке отношений и создании индексов. Затем эти данные периодически обновляются через команду update statistics, которая может выполняться любым пользователем. В system r эти статистические данные не обновляются при выполнении каждого оператора insert, delete или update, поскольку для этого потребовались бы дополнительные операции над базой данных, и системные каталоги стали бы узким местом по блокировкам. Динамическое обновление статистики могло бы привести к чисто последовательному выполнению операций, модифицирующих содержимое отношений.
Используя эти статистические данные, ОПТИМИЗАТОР назначает каждому булевскому сомножителю из списка предикатов коэффициент селективности 'f'. Этот коэффициент селективности очень приблизительно соответствует ожидаемой доли кортежей, которые будут удовлетворять предикату. В таб. 1 приводятся коэффициенты селективности для разных видов предикатов. Мы предполагаем, что из отсутствия статистики следует, что отношение имеет небольшой размер, и для него может быть выбран произвольный коэффициент.
column = value
f = 1 / icard(column index), если на столбце имеется индекс
Здесь предполагается равномерное распределение кортежей по значениям ключа индекса
Иначе f = l/10
column1 = column2
f = l/max(icard(columnl index), icard(column2 index))
если имеются индексы и на columnl, и на column2
Здесь предполагается, что для каждого значения ключа в индексе с меньшей мощностью имеется соответствующее значение в другом индексе
f = l/icard(column-i index), если имеется индекс только на column-i
Иначе f = l/10
column > value (или любое другое открытое сравнение)
f = (high key value - value) / (high key value - low key value)
f получается путем линейной интерполяции заданного значения в диапазоне значений ключа, если у столбца арифметический тип, и значение известно во время выбора пути доступа
Иначе f = l/3 (например, тип столбца не является арифметическим)
Последнее число не слишком существенно, за исключением того факта, что оно показывает меньшую селективность, чем у предиката сравнения на равенство, для которого нет индексов, и это число больше 1/2. У нас имеется гипотеза, что лишь в немногих запросах используются предикаты, которым удовлетворяет более половины кортежей.
column between value1 and value2
f = (value1 - value2) / (high key value - low key value)
В качестве коэффициента селективности используется отношение размера диапазона значений between к размеру общего диапазона ключа, если тип столбца является арифметическим, и value1 и value2 известны во время выбора пути доступа
Иначе f = l/4
В последней формуле опять не слишком много смысла за исключением того, что значение находится между коэффициентами по умолчанию для предиката сравнения по равенству и предиката сравнения с открытым неравенством.
column in (список значений)
f = (число элементов в списке) * (коэффициент селективности для column = value)
Здесь допускается значение, большее l/2
columna in subquery
f = (ожидаемая мощность результата подзапроса) / (произведение мощностей всех
отношений из списка from подзапроса)
Вычисление мощности результата запроса будет обсуждаться позже
Эта формула выводится на основе следующих аргументов:
Рассмотрим простейший случай, когда подзапрос имеет вид "select columnb from relationc". Предположим, что множество всех значений columnb в relationc содержит множество всех значений columna. Если подзапрос выбирает все кортежи relationc, то значением предиката всегда является true, и f = 1. Если кортежи подзапроса ограничиваются коэффициентом селективности f', то предположим, что множество уникальных значений в результате подзапроса, которые соответствуют значениям columna, ограничено в той же пропорции, т.е. коэффициентом селективности предиката должно быть f'. f' является произведением всех коэффициентов селективности подзапроса, а именно, (мощность подзапроса) / (мощность всех возможных ответов на подзапрос). При наличии некоторого оптимизма мы можем расширить эти соображения на подзапросы с соединениями и подзапросы, в которых columnb заменяется арифметическим выражением, содержащим имена столбцов. Это приводит к указанной выше формуле.
(pred expression1) or (pred expression2)
f = f(pred1) + f(pred2) - f(pred1) * f(pred2)
(pred1) and (pred2)
f = f(pred1) * f(pred2)
Заметим, что здесь предполагается, что значения столбцов независимы.
not pred
f = 1 - f(pred)
Таблица 1. Коэффициенты селективности
Мощность запроса (qcard) является произведением мощностей всех отношений из списка from блока запроса, умноженным на произведение всех коэффициентов селективности булевских сомножителей этого блока запроса. Число ожидаемых вызовов rsi (rsicard) является произведением мощностей отношений на коэффициенты селективности sargable булевских сомножителей, поскольку sargable булевские сомножители будут помещены в аргументы поиска, которые будут отфильтровывать кортежи без из возврата через интерфейс rss.
Выбор оптимального пути доступа для одного отношения состоит в использовании этих коэффициентов селективности в формулах совместно со статистическими данными по поводу имеющихся путей доступа. Прежде чем описывать этот процесс, требуется ввести определение. Использование индексного пути доступа или сортировка кортежей производят кортежи, упорядоченные в соответствии со значениями ключа индекса или сортировки. Мы называем это порядок кортежей интересным порядком, если именно такой порядок сортировки указан в разделах group by или order by блока запроса.
Для одиночных отношений наиболее дешевый путь доступа получается путем оценки стоимости каждого доступного пути доступа (каждого индекса на отношении плюс сегментное сканирование). Оценки стоимости описываются ниже. Для каждого такого пути доступа вычисляется предсказываемая стоимость, а также оценивается производимая упорядоченность кортежей. Например, сканирование по индексу salary в порядке возрастания породит некоторую оценочную стоимость c и упорядоченность кортежей по salary (в порядке возрастания). Чтобы обнаружить наиболее дешевый путь доступа для запроса над одним отношением, нам нужно всего лишь обследовать самые дешевые пути доступа, которые производят кортежи в каждом "интересном" порядке, и самый дешевый "неупорядоченный" путь доступа. Заметим, что "неупорядоченный" путь доступа в действительности может производить кортежи в некотором порядке, но этот порядок не является "интересным". Если в запросе не содержатся ни раздел group by, ни раздел order by, то "интересный" порядок отсутствует, и выбирается один наиболее дешевый путь доступа. Если имеются разделы group by или order by, то стоимость пути доступа, производящего это "интересное" упорядочивание, сравнивается со стоимостью наиболее дешевого неупорядоченного пути плюс стоимость сортировки qcard кортежей в должном порядке. Самая дешевая альтернатива выбирается в качестве плана для данного блока запроса.
Оценочные формулы для путей доступа к одному отношению приведены в таб. 2. В этих формулах участвуют число обращений к индексным страницам плюс число обращений к страницам данных плюс коэффициент взвешивания, умноженный на число обращений к rsi для выборки кортежей. w - это коэффициент взвешивания между обращениями к страницам и вызовами rsi. В некоторых ситуациях приводится несколько альтернативных формул в зависимости от того, помещается ли весь набор выбранных кортежей в буферном пуле rss (или части пула, выделенной пользователю). Мы предполагаем, что для кластеризованных индексов страница остается в буфере до тех пор, пока из нее не будут выбраны все кортежи. Для некластеризованных индексов предполагается, что отношения, не помещающиеся в буфер, достаточно велики по сравнению с размером буфера, и для каждой выборки кортежа требуется чтение страницы.
5. Выбор пути доступа для соединений
В 1976 г. Блазген и Эсваран [4] исследовали ряд методов выполнения соединений двух отношений. Эффективность каждого из этих методов анализировалась при разных мощностях отношений. Данные авторов показывают, что для любых не слишком мелких отношений один из двух методов соединения всегда является оптимальным или близким к оптимальному. Оптимизатор system r производит выбор одного из этих методов. Сначала мы опишем эти метод, а потом обсудим, как они расширяются для случая соединения n отношений. В заключение мы указываем, как выбирается порядок соединений (порядок, в котором соединяются отношения). Для соединения двух отношений выделяются внешнее отношение, из которого сначала выбирается кортеж, и внутреннее отношение, из которого выбираются кортежи, возможно, в зависимости от значений полученного кортежа внешнего отношения. Предикат, связывающий столбцы двух отношений для порождения соединения, называется предикатом соединения. Столбцы, заданные в предикате соединения, называются столбцами соединения.
В первом методе соединения, называемом методом вложенных циклов, используется сканирование, в любом порядке, внешнего и внутреннего отношений. Открывается сканирование внешнего отношения, и выбирается первый кортеж. Для каждого полученного кортежа внешнего отношения открывается сканирование внутреннего отношения для выборки (по одному за одно обращение к rsi) всех кортежей внутреннего отношения, удовлетворяющих предикату соединения. В результат этого соединения входят составные кортежи, формируемые из пар "кортеж-внешнего-отношения/кортеж-внутреннего-отношения".
Для применения второго метода соединения, называемого сканированием со слиянием, требуется, чтобы внешнее и внутреннее отношения сканировались в порядке столбца соединения. Из этого следует, что наряду со столбцами, указанными в разделах order by и group by, столбцы предикатов эквисоединения (вида table1.columnl = table2.column2) также определяют "интересный" порядок. Если имеется более одного предиката соединения, то один из них используется как предикат соединения, а остальные - как обычные предикаты. Метод сканирования со слиянием применяется только к эквисоединениям, хотя, в принципе, его можно было бы применить и к другим типам соединения. Если у одного или обоих соединяемых отношений отсутствуют индексы на столбце соединения, они должны быть отсортированы и помещены во временный список (list), упорядоченный по столбцу соединения.
В методе сканирования со слиянием свойство упорядоченности по столбцу соединения используется для того, чтобы избежать полного сканирования внутреннего отношения (в поиске соответствующих кортежей) для каждого кортежа внешнего отношения. Это делается путем синхронизации внутреннего и внешнего сканирования за счет поддержания ссылки на соответствующие значения столбца соединения и "запоминания" месторасположения соответствующих групп соединения. Возможна еще большая экономия, если внутреннее отношение кластеризовано по столбцу соединения (например, получено путем сортировки по столбцу соединения). "Кластеризация" по столбцу означает, что кортежи с одинаковым значением этого столбца хранятся физически близко один от другого, так что за одно обращение к странице будет выбираться несколько кортежей.
Соединение n отношений может быть воплощено как последовательность соединений двух отношений. В этом воплощении соединяются два отношения, результирующее отношение соединяется с третьим отношением и т.д. На каждом шаге соединения n отношений можно определить внешнее отношение (как правило, составное) и внутреннее отношение (добавляемое к соединению). Таким образом, описанные выше методы легко обобщаются для соединения n отношений. Однако следует подчеркнуть, что первое соединение двух отношений не обязательно должно быть полностью завершено да начала выполнения второго соединения двух отношений. Как только мы получим составной кортеж для первого соединения двух отношений, он может быть соединен с кортежами третьего отношения, образуя кортежи для соединения с четвертым отношением и т.д. При выполнении одного запроса могут смешиваться методы соединения вложенными циклами и сканированием со слиянием, например, при соединении трех отношений первые два отношения могут соединяться методом сканирования со слиянием, а результирующее отношение может соединяться с третьим отношением методом вложенных циклов. Промежуточные составные отношения физически сохраняются только в тех случаях, когда на следующем шаге соединения требуется сортировка. Если сортировка составного отношения не нужна, оно материализуется по одному кортежу, который немедленно принимает участие в следующем соединении.
Теперь мы рассмотрим порядок, который выбирается для соединения отношений. Следует заметить, что хотя мощность результата соединения n отношений не зависит от порядка выполнения соединений двух отношений, стоимости соединений в разном порядке могут существенно различаться. Если в списке from блока запроса указано n отношений, то существует n! разных порядков выполнения соединений. Пространство поиска можно сократить на основе того наблюдения, что после соединения первых k отношений метод соединения результата с (k+1)-м отношением не зависит от порядка соединения первых k отношений, т.е. применимы одни и те же предикаты, имеется один и тот же набор интересных упорядочиваний, возможны одни и те же методы выполнения соединения и т.д. С использованием этого свойства эффективный способ организации поиска состоит в том, чтобы находить наилучший порядок соединения для последовательно возрастающего поднабора таблиц.
Для сокращения числа рассматриваемых перестановок в порядке соединения используется эвристика. Когда это возможно, поиск ограничивается рассмотрением только тех порядков соединения, для которых имеются предикаты соединения, связывающие внутреннее отношение с другими отношениями, уже участвующими в соединении. Это означает, что при соединении отношений tl, t2,..., tn рассматриваются только те порядки til, ti2,..., tin, в которых для всех j (j=2,..., n) либо (1) для tij имеется, по крайней мере, один предикат соединения с некоторым отношением tik, где k < j, либо (2) для всех k > j для tik отсутствует предикат соединения с til, tit,..., ti(j-1).
Это означает, что все соединения, для которых требуется декартово произведение, выполняются в последовательности соединений как можно позже. Например, если tl, t2, t3 - это три отношения из списка from блока запроса, и имеются предикаты соединения между tl и t2 и между t2 и t3 на других столбцах, чем у соединения tl-t2, то следующие перестановки не рассматриваются:
tl-t3-t2 t3-tl-t2
Для нахождения оптимального плана для соединения n отношений конструируется дерево возможных решений. Как обсуждалось выше, поиск производится путем нахождения наилучшего способа поднабора отношений. Для каждого набора соединяемых отношений оценивается и сохраняется мощность составного отношения. В дополнение к этому, для неупорядоченного соединения и для каждого интересного порядка, полученному путем выполнения соединения до сих пор, сохраняются наиболее дешевое решение для достижения этого порядка и стоимость этого решения. Решение состоит из упорядоченного списка соединяемых отношений, метода, используемого для каждого соединения и плана, показывающего, как будет производиться доступ к каждому отношению. Если либо для внешнего составного отношения, либо для внутреннего отношения требуется сортировка перед выполнением соединения, то это тоже включается в план. Как и в случае одного отношения, "интересными" порядками являются те, которые указываются в разделах group by или order by блока запроса (если эти разделы присутствуют). Кроме того, "интересный" порядок определяется каждым столбцом соединения. Для минимизации числа разных интересных порядков и, следовательно, числа решений в дереве вычисляются классы эквивалентности интересных порядков, и для каждого класса эквивалентности сохраняется только наилучшее решение. Например, если имеются предикат соединения e.dno = d.dno и другой предикат соединения d.dno = f.dno, то все три эти столбца принадлежат одному и тому же классу эквивалентности порядков.
Дерево поиска конструируется путем итерирования по числу отношений, соединенных до сих пор. Прежде всего, находится наилучший способ доступа к каждому одиночному отношению для каждого интересного упорядочивания кортежей и для неупорядоченного случая. Далее находится наилучший способ соединения какого-либо отношения с каждым из имеющегося набора с учетом эвристики для порядка соединений. В результате производятся решения для соединения пар отношений. Затем находится наилучший способ соединения наборов из трех отношений путем рассмотрения всех наборов из двух отношений и их соединения с каждым третьим отношением, допускаемым эвристикой о порядке соединения. Для каждого плана соединения набора отношений порядок составного результата сохраняется в дереве. Это позволяет рассматривать возможность соединения сканированием со слиянием, для которого не требуется сортировка композиции. После нахождения всех полных решений (соединений всех отношений) оптимизатор выбирает наиболее дешевое решение, выдающее требуемый порядок, если таковой был специфицирован. Заметим, что если существует решение с правильным порядком, сортировка для order by или group by не выполняется, если только упорядоченное решение не является более дорогостоящем, чем самое дешевое неупорядоченное решение плюс стоимость сортировки в требуемом порядке.
Число решений, которые требуется сохранять, не превышает 2**n (число подмножеств из n таблиц), умноженное на число интересных порядко результатов. Время вычислений для генерации дерева приблизительно пропорционально тому же числу. Часто это число существенно уменьшается эвристикой порядка соединений. По нашему опыту в типичных слу