Сергей Кузнецов
Предисловие переводчика
Хотя у статьи, перевод на русский язык которой предлагается вашему вниманию, присутствует пять авторов, и все они весьма заслуженные и уважаемые в мире баз данных люди, эта статья прочно ассоциируется с именем Патриции Селинджер, поскольку именно она придумала и впервые реализовала соответствующий подход. Статья была написана на завершающем этапе проекта 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-деревья [3], листьями которых являются страницы, содержащие наборы (ключ, идентификаторы кортежей, содержащих этот ключ). Поэтому последовательность команд next при индексном сканировании производит последовательное чтение листовых страниц индекса, получая идентификаторы кортежей, соответствующих ключу, и используя их для нахождения и возврату пользователю кортежей данных в порядке значений ключа. Листовые страницы индекса связаны в список, так что при выполнении команды next не требуются обращения к страницам индекса более высокого уровня.
При сегментном сканировании затрагиваются все непустые страницы сегмента, независимо от того, содержат ли они кортежи заданного отношения. Однако каждая страница затрагивается только один раз. При просмотре всего отношения через индексное сканирование каждая страница индекса затрагивается только один раз, но страница данных может проверяться более одного раза, если имеются два кортежа, не являющиеся "близкими" в порядке индекса. Если кортежи вставляются в сегмент в порядке индекса, и если эта физическая близость, соответствующая значениям ключа индекса, поддерживается, то мы говорим, что индекс является кластеризованным. У кластеризованного индекса имеется то свойство, что при сканировании через этот индекс будет затрагиваться только один раз не только каждая индексная страница, но и каждая страница данных, содержащая кортеж данного отношения.
Через индекс можно сканировать и не все отношение целиком. Можно указывать стартовое и стоповое значения, чтобы сканировать только те кортежи, ключ которых находится в диапазоне индексных значений. И для индексного, и для сегментного сканирования можно также задавать набор предикатов, называемых аргументами поиска (search arguments, sargs), которые применяются к кортежу, прежде чем он возвращается в программу, обратившуюся к rsi. Если кортеж удовлетворяет предикатам, он возвращается; иначе сканирование продолжается до тех пор, пока либо не будет найден кортеж, удовлетворяющий sargs, либо не исчерпается сегмент или заданный диапазон индексных значений. Это сокращает расходы путем устранения накладных расходов на вызовы rsi для кортежей, которые могут быть разумным образом отвергнуты внутри rss. Не все предикаты находятся в форме, которая может стать sargs. sargable предикат - это предикат, имеющий вид (или приводимый к виду) "ncolumn comparison-operator value". sargs представляются как булевские выражения из таких предикатов в дизъюнктивной нормальной форме.
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 таблиц), умноженное на число интересных порядко результатов. Время вычислений для генерации дерева приблизительно пропорционально тому же числу. Часто это число существенно уменьшается эвристикой порядка соединений. По нашему опыту в типичных случаях требуется всего несколько тысяч байт памяти т несколько десятых долей секунды времени ЦП 370/158. Соединения восьми таблиц оптимизируются за несколько секунд.
Вычисление стоимостей
Стоимости для соединений вычисляются на основе стоимостей сканирования каждого отношения и мощностей. Стоимости сканирования каждого отношения вычисляются с использованием оценочных формул для путей доступа к одиночным отношениям, представленным в разд. 4.
Пусть c-outer(path1) обозначает стоимость сканирования внешнего отношения через path1, и n - число кортежей внешнего отношения, удовлетворяющих применимым предикатам. n вычисляется следующим образом:
n = (произведение мощностей всех отношений t, участвовавших в соединении до сих пор) * (произведение коэффициентов селективности всех применимых предикатов)
Пусть c-inner(path2) обозначает стоимость сканирования внутреннего отношения с применением всех применимых предикатов. Заметим, что с случае соединения путем сканирования со слиянием это означает сканирование последовательной группы внутреннего отношения, которая соответствует одному значению столбца соединения во внешнем отношении. Тогда стоимость соединения методом вложенных циклов вычисляется следующим образом:
c-nested-loop-join(pathl,path2) = c-outer(path1) + n * c-inner(path2)
Стоимость соединения путем сканирования со слиянием можно разбить на стоимость выполнения именно слияния плюс стоимость сортировки внешнего или внутреннего отношений, если это требуется. Стоимость выполнения слияния вычисляется следующим образом:
c-merge(pathl,path2)= c-outer(path1) + n * c-inner(path2)
В случае, когда внутреннее отношение отсортировано во временное отношение, не применима ни одна из формул для пути доступа к одиночному отношению из разд. 4. В этом случае внутренее сканирование похоже на сегментное сканирование за исключением того, что в методе сканирования со слиянием используется тот факт, что внутреннее отношение отсортировано, и при поиске соответствия не требуется его полное сканирование. Для этого случая мы используем следующую формулу оценки стоимости внутреннего сканирования:
c-inner(sorted list) = temppages/n + w*rsicard
где temppages - это число страниц, требуемых для сохранения внутреннего отношения. В этой формуле предполагается, что в течение слияния каждая страница внутреннего отношения будет считытваться только один раз. Интересно заметить, что оценочная формула для соединений методом вложенных циклов и оценочная формула для соединения методом сканирования со слиянием являются, по существу, одинаковыми. Причиной того, что сканирование со слиянием в некоторых случаях оказывается лучше вложенных циклов, состоит в том, что стоимость внутреннего сканирования может быть гораздо меньше. После сортировки внутреннее отношение является кластеризованным по столбцу соединения, что ведет к минимизации числа чтений страниц, и не обязательно сканировать все внутренее отношение (в поиске соответствия) для каждого кортежа внешнего отношения.
Стоимость сортировки отношения csort(path) включает стоимость выборки данных с использованием указанного пути доступа, сортировки данных, которая может включать несколько проходов, и помещения результатов во временный список. Заметим, что до сортировки внутренней таблицы могут применяться только локальные предикаты. Кроме того, если требуется сортировать составной результат, то все составное отношение должно быть сохранено во временном отношении до того, как его можно будет сортировать. Стоимость вставки составных кортежей во временное отношение до сортировки включается в c-sort(path).
Рисунок 1. Пример соединения
Рисунок 2. Пути доступа к одиночным отношениям
Пример дерева
Теперь мы покажем, как выполняется поиск для примера соединения на рис.1. Прежде всего, мы находим все разумные пути доступа к одиночным отношениям с применением только локальных предикатов. Результаты для этого примера показаны на рис. 2. Для таблицы emp имеется три пути доступа: индекс на dno, индекс на job и сегментное сканирование. Интересными порядками являются dno и job. Индекс на dno обеспечивает кортежи в порядке dno, и индекс на job обеспечивает кортежи в порядке job. Для наших целей путь доступа через сегментное сканирование считается неупорядоченным. Для этого примера мы предполагаем, что индекс на job является наиболее дешевым путем, поэтому сегментный путь доступа отсекается. Для отношения dept имеется два пути доступа: индекс на dno и сегментное сканирование. Мы предполагаем, что индекс на dno дешевле, поэтому сегментный путь доступа отсекается. Для отношения job имеется два пути доступа: индекс на job и сегментное сканирование. Мы предполагаем, что сегментный путь доступа дешевле, поэтому сохраняются оба пути. Только что описанные результаты сохраняются в дереве поиска, как показано на рис.3. На этих рисунках обозначения c(emp.dno) или c(e.dno) обозначают стоимость сканирования emp через dno с применением всех предикатов, которые применимы, при том, что кортежи из указанных отношений уже прочитаны. Обозначение ni представляет мощности различных частичных результатов.
Рисунок 3. Дерево поиска для одиночных отношений
Далее находятся решения для пар отношений путем присоединения второго отношения к результатам для одиночных отношений, показанных на рис.3. Для каждого одиночного отношения мы находим пути доступа для соединения с каждым вторым отношением, для которого существует предикат, соединяющий его с первым отношением. Сначала мы производим выбор путей доступа для соединений вложенными циклами. В этом примере мы предполагаем, что соединение emp-job является наиболее дешевым при доступе к job через индекс job. Это вполне вероятно, поскольку позволяет прямо считывать кортежи о соответствию job (без потребности в сканировании всего отношения). На практике стоимость соединения оценивается с испрользованием приведенных ранее формул, и выбирается самый дешевый путь. Для соединения отношения emp с отношением dept мы предполагаем, что наиболее дешевым является индекс dno. Налучший путь доступа для каждого отношения второго уровня комбинируется с каждым из планов с рис. 3 для формирования решений с вложенными циклами, показанного на рис.4.
Далее мы генерируем решения с использование метода сканирования со слиянием. Как мы видем в левой части рис. 3, имеется возможность сканирования отношения emp в порядке dno, поэтому существует возможность использовать это сканирование и сканирование по dno отношения dept, чтобы выполнить соединение сканированием со слиянием без какой-либо сортировки. Хотя можно выполнить соединение слиянием без сортировки, может быть дешевле использовать индекс job на emp, отсортировать по dno, а потом выполнить слияние. Заметим, что мы не рассматриваем возможность сортировки таблицы dept, потому что наиболее дешевое сканирование этой таблицы уже обеспечивает упорядоченность по dno.
Для слияния job с emp мы рассматриваем только возможность использования индексв job на emp, потому что это наиболее дешевый путь доступа для emp безотносительно упорядоченности. Используя индекс job на job мы можем выполнить слияние без какой-либо сортировки. Однако может оказаться дешевле отсортировать job, используя сегментное сканирование для обеспечения данных для сортировки, а затем выполнить слияние.
На рис. 3 мы видим, что путем доступа, выбранным для отношения dept, является индекс dno. После доступа к dept через этот индекс мы можем выполнить слияние с emp, используя индекс dno на emp, опять безо всякой сортировки. Однако может оказаться дешевле сначала отсортировать emp, используя индекс job для обеспечения данных для сортировки, а затем произвести слияние. Оба эти случая показаны на Рис. 5.
Когда вычисляют все стоимости, показанные на рис. 5 и 6, они сравниваются с наиболее дешевым эквивалентным решением (те же таблицы и тот же порядок результата), и сохраняется наиболее дешевое решение. После этого отсечения находятся решения для всех трех отношений. Для каждой пары отношений мы находим пути доступа для соединения с оставшимся третьим отношением. Как и ранее, мы расширяем дерево, используя методы вложенных циклов и сканирования со слиянием для соединения третьего отношения. Дерево поиска для трех отношений показано на рис. 6. Заметим, что в одном случае сортируется и составное отношение и добавляемая таблица (job). Заметим также, что в некоторых случаях сортировка вообще не производится. В этих случаях составной результат материализуется по одному кортежу за раз, и промежуточные составные отношения никогда не сохраняются. Как и ранее, по мере вычисления стоимостей он сравниваются с наиболее дешевым решением.
6. Вложенные запросы
Запрос может появляться как операнд предиката в форме "expression operator query". Такой запрос называется Вложенным Запросом, или Подзапросом. Если операция является одной из шести операций скалярного сравнения (=, -=, >, >=, <, <=), то подзапрос должен возвращать единственное значение. Следующий пример с использованием операции "=" был приведен в разд. 2:
select name
from employee
where salary =
(select avg(salary)
from employee)
Если операцией является in или not in, то подзапрос может возвращать множество значений. Например:
select name
from employee
where department_number in
(select department_number
from department
where location='denver')
В обоих примерах подзапрос требуется вычислить только один раз. ОПТИМИЗАТОР организует вычисление подзапроса до вычисления запроса верхнего уровня. Если возвращается единственное значение, оно подставляется в запрос верхнего уровня, как если бы являлось частью исходного оператора запроса; например, если бы avg(sal) в первом примере вычислилось в 15000 во время выполнения, то предикат принял бы вид "salary = 15000". Если подзапрос может возвращать набор значений, они возвращаются в виде временного списка, внутренняя форма которого более эффективна, чем у отношения, но допускает только последовательный доступ. Если во втором примере подзапрос возвращает список (17,24), то предикат вычисляется в манере, аналогичной той, как если бы исходный предикат имел вид department_number in (17,24).
Подзапрос также может содержать предикат с подзапросом, и допускается (теоретически) произвольная глубина вложенности. Если такие подзапросы не ссылаются на столбцы таблиц блоков запросов более высокого уровня, их можно вычислять до вычисления запроса верхнего уровня. В этом случае сначала вычисляются наиболее глубоко вложенные запросы, поскольку любой подзапрос должен быть вычислен раньше, чем может быть вычислен его родительский запрос.
В подзапросе может содержаться ссылка на значение, получаемое из возможного кортежа блока запроса более верхнего уровня (см. ниже пример). Такой запрос называется корреляционным подзапросом. В принципе, корреляционный подзапрос должен вычисляться каждый раз перед тем, как родительский предикат корреляционного запроса может быть проверен для принятия или отклонения возможной строки. В качестве примера рассмотрим следующий запрос:
select name
from employee x
where salary > (select salary
from employee
where employee_number=x.manager)
Здесь выбираются имена служащих, зарабатывающих больше своего менеджера. x идентифицирует блок запроса и отношение, которое предоставляет возможный кортеж для корреляции. Для каждого возможного кортежа блока запроса верхнего уровня для вычисления подзапроса используется значение столбца manager. Результат подзапроса затем возвращается в предикат "salary >" для проверки принятия возможного кортежа.
Если корреляционный подзапрос не находится напрямую под блоком запроса, на который ссылается, а отделен от этого блока одним или несколькими промежуточными блоками, то вычисление корреляционного подзапроса должно быть произведено до вычисления самого высокого из промежуточных блоков. Например:
level 1 select name
from employee x
where salary >
level 2 (select salary
from employee
where employee-number =
level 3 (select manager
from erployee
where employee-number = x.manager))
Здесь выбираются имена служащих, зарабатывающих больше менеджера своего менеджера. Как и раньше, для каждого возможного кортежа блока запроса уровня 1 значение столбца employee.manager используется для вычисления блока запроса уровня 3. В этом случае, поскольку подзапрос уровня 3 ссылается на значение уровня 1, но не ссылается на значения уровня 2, он вычисляется по одному разу для каждого нового возможного кортежа уровня 1, а не для каждого возможного кортежа уровня 2.
Если значение, на которое ссылается корреляционный запрос (x.manager в приведенном примере) не является уникальным во множестве возможных кортежей (например, у нескольких служащих может иметься один и тот же менеджер), описанная выше процедура все равно приведет к повторному вычислению подзапроса для каждого вхождения дублированного значения. Однако, если отношение, на которое ведет ссылка, упорядочено по столбцу, на который ссылается подзапрос, то повторное вычисление может быть условным в зависимости от проверки, не является ли текущее значение тем же самым, что и у предыдущего возможного кортежа. Если они одинаковы, предыдущее вычисленное значение может быть использовано снова. В некоторых случаях может иметь смысл даже специально отсортировать внешнее отношение по соответствующему столбцу, чтобы избежать излишнего вычисления подзапроса. Чтобы определить, являются ли уникальными значения столбца, на который ссылается корреляционный запрос, ОПТИМИЗАТОР может использовать подсказки типа ncard > icard, где ncard - мощность отношения, а icard - мощность индекса на этом столбце.
7. Заключение
Описан выбор путей доступа в system r для запросов над одиночными таблицами, соединений и вложенных запросов. Ведется работа по сравнению выбираемых вариантов с "правильными", результаты будут описаны в будущей статье. Предварительные результаты показывают, что хотя стоимости, предсказываемые оптимизатором, часто бывают неточны в абсолютном измерении, в подавляющем большинстве случаев выбирается действительно оптимальный план. Во многих случаях соотношения между оцененными стоимостями для всех рассмотренных планов являются в точности теми же, что и соотношения между реально измеренными стоимостями.
Кроме того, стоимость выбора пути не является непомерной. Для соединения двух отношений стоимость оптимизации приблизительно эквивалентна стоимости 5-20 выборок из базы данных. Это число становится еще более незначительным, когда выбор пути доступа производится в среде, подобной system r, где единожды скомпилированные прикладные программы выполняются многократно. Стоимость оптимизации окупается многократным выполнением.
Основной новый вклад данной работы над компонентом выбора путей доступа состоит в расширенном использовании статистики (например, мощности индексов), включении загрузки ЦП в оценочные формулы и разработке метода определения порядка соединений. Многие запросы ограничиваются возможностями ЦП, в частности, соединения слиянием, для которых создаются временные отношения и производится сортировка. Понятие "коэффициента селективности" позволяет оптимизатору использовать как можно большее число предикатов в аргументах поиска rss и путях доступа. При запоминании классов эквивалентности "интересного упорядочивания" для соединений и спецификаций order или group оптимизатор учитывает больше информации, чем другие аналогичные программы, но во многих случаях эта дополнительная работа позволяет избежать сохранения и сортировки промежуточных результатов запроса. Методы обрезания дерева и поиска в дереве позволяют эффективно выполнять этот дополнительный учет. Требуется дополнительная работа по валидации оценочных формул оптимизатора, но из нашей предварительной работы мы можем заключить, что в системах управления базами данных могут поддерживаться непроцедурные языки запросов с эффективностью, сравнимой с той, которая поддерживается для современных более процедурных языков.
Ссылки по теме
