Введение в системы БД (542480), страница 169
Текст из файла (страница 169)
Прежде всего, К и Б — это отношения, которые должны быть соединены, а С вЂ” их общий атрибут [возможно, составной). Предполагается, что возможен последовательный доступ к кортежам обоих о~ношений К и Б по одному за одну операцию. Эти кортежи в последовательности доступа будут обозначаться как К[1]„ К(2], ..., К[в] и Б[1], Б[2], ..., Б[п) соответственно. Для соединенного кортежа, составленного из атрибутов кортежей К[ 1] и Б[>), будет использова~ься обозначение К[1] * Б[З]. И наконец, переменную- отношение К будем считать внешней, а переменную-отношение Б — внутренней [поскольку они управляют внешним и внутренним циклами просмотра соответственно).
Последовательный просмотр Метод последовательного просмотра или "грубой силы" иногда также называют простым методом. В этом случае рассматриваются все возможные комбинации кортежей [т.е. каждый кортеж отношения К проверяется в сочетании с каждым кортежем отношения Б, как показано на рис. ! 7.4). Замечание. Метод последовательного просмотра часто называют методом вложенных циклов, но это название нельзя считать адекватным, поскольку вложенные циклы используются в реализациях всех названных выше методов. Рис. ! 7.4. Метод последовательного просмотра Давайте проанализируем затраты, связанные с использованием метода последовательного просмотра. 659 Глава 17. Оппгимизаиия Замечание. Здесь мы ограничимся только анализом затрат на выполнение операций ввода-вывода, хотя на практике может потребоваться также учесть другие параметры (например, затраты времени центрального процессора).
Прежде всего, ясно, что для реализации этого метода потребуется всего и * и операций чтения кортежей. А как в отношении операций записи кортежей? Какова кардинальность результата операции соединения? (Количество операций записи кортежа будет равно кардинальности результирующего отношения, если последнее требуется записывать на диск.) ° В частном, но достаточно важном случае соединения типа "многие к одному" (например, соединение типа '"внешний ключ к соответствующему потенциальному ключу") кардинальность результирующего отношения почти всегда точно совпадает с величиной и или п в зависимости от того, какое из отношений, К или Б, расположено на стороне "многие*' рассматриваемого соединения.
° Теперь рассмотрим более общий случай соединения типа "многие ко многим". Пусть бСК вЂ” количество различающихся значений атрибута С отношения К, по которому выполняется соединение, и бСБ имеет тот же смысл, но для отношения Б. Если предположить, что значения атрибутов распределены равномерно (т.е. любое значение атрибута С может быть встречено с той же вероятностью, что и другие значения), то для данного кортежа отношения К существует л/ЙСБ соответствующих кортежей в отношении Б со значением атрибута С, равным значению этого атрибута в рассматриваемом кортеже из отношения К. Таким образом, общее количество кортежей в соединении (т.е. кардинальность результирующего отношения) будет равно (д * и) /г(СБ.
Или, если повторить изложенные рассуждения, начав с кортежа в отношении Б, кардинальность результирующего отношения составит (и * и)/г(СК. Эти две оценки будут различными, если г)СБ ~ ИСК, т,е. если в отношении К существуют значения атрибута С, которые не встречаются в отношении Б, и наоборот. В этом случае следует использовать худшую из оценок, Конечно, как уже отмечалось, на практике подсчитываются операции ввода-вывода страниц, а не кортежей. Поэтому предположим, что в отношениях К и Б на странице помещается соответственно рК и рБ кортежей (т.е. отношения занимают и/рК и и/рБ страниц соответственно).
Теперь легко увидеть, что процедура, псевдокод которой показан на рис. 17.4, выполнит (яг/рК) + (п*п) /рБ операций чтения страниц. Аналогично, если поменять местами роли отношений К и Б (отношение Б считать внешним, а К вЂ” внутренним), количество операций чтения страниц составит (и/рБ) + (п*п)/рК.
/)ля примера предположим, что аг = 100, и = 10 000, рК = 1 и рБ = 10. Тогда результатами вычисления последних двух формул будут значения 100 100 и 1 001 000 операций чтения страниц соответственно. Замечание. В описанном подходе в качестве внешнего отношения желательно использовать меньшее из двух исходных отношений (в данном случае понятие "меньшее" относится к количеству занимаемых им страниц внешней памяти). Завершая краткое обсуждение метода последовательного просмотра, заметим, что этот прием является наихудшим из всех. В нем предполагается, что отношение Б не имеет ни индекса, ни хеш-таблицы для атрибута С, по которому выполняется соединение.
Эксперименты, проведенные Биттоном (Вгпоп) (17.7], показали, что если предполагае- 660 Часть К Дополнительные аспекты мая ситуация (отсутствие индексов и хеш-таблиц) действительно имеет место, то методы обработки можно улучшить, построив нужный индекс или хеш-таблицу динамически и продолжив обработку запроса с помощью методов поиска по индексу или хеш-таблице (см, следующие два подраздела).
Как упоминается в конце следующего раздела, зта идея поддерживается и в [17.37]. Поиск по индексу Теперь рассмотрим ситуацию, в которой для атрибута Я.С внутреннего отношения Б существует индекс Х (рис. 17.5). Преимущество поиска по индексу по сравнению с методом последовательного просмотра состоит в том, что благодаря наличию индекса Х для данного кортежа внешнего отношения К возможен переход непосредственно к соответствующему кортежу внутреннего отношения Я. Общее количество операций чтения кортежей из отношений К и Я будет равно кардинальности результирующего отношения операции соединения. Общее количество операций чтения страниц для отношений К и Б составит (в/рй) + (вл/дСБ) при наихудшем предположении, что каждая операция чтения кортежа из отношения Б требует обращения к отдельной странице.
/* Использование индекса Х по атрибуту Я.С ь/ Йо!: 1 тощ; /* Внешний цикл */ /* Пусть для значения индексированного атрибута К[1].С */ /* существует 1с вхождений индекса: Х[1], ..., Х[К] ь/ до ):= 1 ьо 1с; /е Внутренний цикл */ /* Пусть Я[)] — кортеж из Я, на который указывает индекс Х[1] */ <к результату добавить соединенный кортеж В[Ц * Я[Я>; епд; епд; Рис. /7.5. Лоиск но индексу Если кортежи отношения Я хранятся в порядке значений соединяющего атрибута С, то количество операций чтения страницы уменьшится до значения (д/РК) + (вл/е)СЯ) /рБ.
Воспользовавшись теми же пробными значениями, что и выше (в = 100, л = 10 000, рК = 1, рЯ = 10), и предположив, что бСБ = 100, получим в результате вычисления двух последних формул значения 10 100 и 200 соответственно. Разница между полученными значениями указывает, что кортежи хранимых отношений целесообразно размещать в "подходящей" физической последовательности [17.9]. Однако при оценке затрат следует учитывать и накладные расходы, связанные с выполнением операций чтения в самом индексе.
Наихудшим является предположение, что при поиске соответствующих кортежей в отношении Я для каждого кортежа в отношении К потребуется выполнить "непредвиденный" поиск по индексу, требующий чтения страницы для каждого уровня индекса. Для индекса, обладающего х уровнями, операция поиска добавит к общему количеству операций чтения страницы еще в'х операций. На практике х обычно имеет значение 3 или меньше.
(Более того, весьма вероятно, что верхний уровень индекса иа протяжении всей обработки данных будет находиться в памяти, что значительно сократит количество операций чтения страниц.) 661 Глава 17. Оптимизация Поиск по хеш-таблице Поиск по хеш-таблице аналогичен поиску по индексу, но в качестве "быстрого пути доступа" к значениям атрибута Я.С внутреннего отношения Я змее~о индекса используется хеш-таблица (рис.
17.б). Вывод оценки затрат, связанных с выполнением данного метода, оставлен в качестве упражнения для читателя. Рис. 17.б. 77оискнохеш-таблице Метод слияния В методе слияния предполагается, что кортежи отношений К и Я хранятся во внешней памяти в последовательности значений атрибута С, по которому выполняется соединение. Если данное предположение отвечает действительности, то лва отношения можно будет просматривать в их физической последовательности, причем обе операции просмотра можно синхронизировать, в результате чего соединение может быть выполнено за один проход по данным (это утверждение истинно по крайней мере для соединений типа "один ко многим", но не всегда истинно для соединений типа "многие ко многим"). Несомненно, подобный метод будет оптимальным, так как каждая страница данных считывается всего один раз (рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
