Поиск ПО хеш-таблице

Поиск по хеш-таблице аналогичен поиску по индексу, но в качестве быстрого пути доступа к значениям атрибута S.C внутреннего отношения S вместо индекса используется хеш-таблица (рис. 17.6). Вывод оценки затрат, связанных с выполнением данного метода, оставлен в качестве упражнения для читателя.

/* Использование хеш-таблицы Н по атрибуту S.C */

do i := 1 to m ; /* Внешний цикл */

к := hash (R[i].C)

/* Пусть имеется h кортежей из S, хранимых в Н[к] */

do j := 1 to h ; /* Внутренний цикл */

if R[i].C = S[j].C then

<K результату добавить соединенный кортеж R[i] * S[j]> ;

end ; end ;

Рис. 17.6. Поиск no хеш-таблице

Метод слияния

в методе слияния предполагается, что кортежи отношений R и S хранятся во внешней памяти в последовательности значений атрибута С, по которому выполняется соединение. Если данное предположение отвечает действительности, то два отношения можно будет просматривать в их физической последовательности, причем обе операции просмотра можно синхронизировать, в результате чего соединение может быть выполнено за один проход по данным (это утверждение истинно по крайней мере для соединений типа один ко многим , но не всегда истинно для соединений типа многие ко многим ). Несомненно, подобный метод будет оптимальным, так как каждая страница данных счи-тывается всего один раз (рис. 17.7). Другими словами, количество операций чтения страниц составит (m/pR) + (n/pS).

Из этого можно сделать следующие заключения.

Физическая кластеризация логически связанных данных является одним из важнейших факторов, влияющих на производительность системы, т.е. в высшей степени желательно проводить кластеризацию данных так, чтобы они соответствовали соединениям, наиболее важным для предприятия [17.9].

Если подобная кластеризация отсутствует, то хорошей идеей может быть сортировка непосредственно во время выполнения запроса какого-то одного или обоих отношений произвольным способом с последующим соединением методом слияния. (Безусловно, назначение подобной сортировки состоит в динамическом создании требуемой кластеризации.) На этот метод обычно ссылаются, что вполне логично, как на метод сортировки-слияния [17.10].

Более подробно эта тема обсуждается в [17.35].

/* Кортежи обоих отношений, R и S, хранятся в последовательности */

/* значений атрибута С. */

/* Здесь приведен код для соединения типа многие ко многим , */

/* пример для соединения типа многие к одному оставлен */

/* в качестве упражнения для читателя. */

г := 1 ; s := 1 ;

do while г < m and s < n ; /* Внешний цикл */

V := R[r].C ;

do j := s by 1 while S[j].C < v ; end ; s := j ;

do j := s by 1 while S[j].C = v ; /* Внутренний цикл */

do i := г by 1 while R[i].C = v ;

<K результату добавить соединенный кортеж R[i] * S[j]> ;

end ; end ; s := j ;

do i := r by 1 while R[i].C = v ; end ; r := i ; end ;

Puc. 17.7. Метод слияния (для соединений типа .многие ко .многим )

Хеширование

Как и метод слияния, метод хеширования позволяет обойтись одним проходом для каждого из двух соединяемых отношений (рис. 17.8). В результате первого прохода строится хеш-таблица для отношения S по значениям атрибута S.C. Записи в этой таблице содержат значение соединяемого атрибута (а также, возможно, значения других атрибутов отношения S) и указатель на соответствующий кортеж. Во время второго прохода сканируются кортежи отношения R и вычисляется та же хеш-функция для значений соединяемого атрибута R.C. Когда по вычисленному для кортежа отношения R значению хеш-функции в хеш-таблице обнаруживается один или несколько соответствующих ему кортежей отношения S, алгоритм проверяет, действительно ли равны значения R.C и S.C, и, если это так, генерируется кортеж (или кортежи) результирующего соединения. Основным преимуществом данного метода по сравнению с методом слияния является то, что отношения R и S можно хранить в произвольной последовательности, а значит, не требуется предварительно сортировать.

Как и в случае метода поиска по хеш-таблице, вывод оценок затрат, связанных с использованием хеширования, оставлен в качестве упражнения для читателя.

17.8. Резюме

Эта глава начинается с утверждения, что для реляционных систем оптимизация является как проблемой, так и благоприятной воз.можностью. Фактически оптимизация является сильной стороной таких систем, причем по целому ряду причин. Реляционная система с хорошим оптимизатором будет функционировать намного лучше, чем не реля-

ционная. Приведенный вступительный пример дает ясное представление о тех поразительных результатах, которых можно достичь благодаря оптимизации (иногда эффективность выполнения запроса повышается в соотношении 10 000:1).

/* Построение хеш-таблицы Н по атрибуту S.C */

do j := 1 to п ; /* Внешний цикл */

к := hash (S[j].C)

<добавить в таблицу Н[к] запись для S[j]> end ;

/* Теперь выполняется поиск по хеш-таблице для */ /* каждого из кортежей отношения R */

Рис. 17.8. Метод хеширования

Процесс оптимизации в обшем случае включает четыре последовательные стадии.

Представление запроса во внутренней форме (обычно это дерево запроса или абстрактное синтаксическое дерево, однако подобные представления вполне можно рассматривать как специфическую внутреннюю форму для выражений реляционной алгебры или реляционного исчисления).

Преобразование в каноническую форму с помощью различных законов преобразования.

Выбор подходящих случаю низкоуровневых процедур реализации различных операторов в каноническом представлении запроса.

Генерация планов запроса и выбор плана с наименьшими затратами, оцениваемыми с помошью формул стоимости и статистических показателей базы данных.

Далее обсуждались общие законы распределения, коммутативности и ассоциативности и их применение к реляционным операторам, таким как соединение. Кроме того, рассматривалось применение этих законов к арифметическим и логическим операторам, а также к операторам сравнения. Затрагивался и другой общий закон - идемпотентности. Затем обсуждались некоторые специальные преобразования операторов проекции и выборки. После этого была представлена идея семантической оптимизации, т.е. преобразования запросов, которое базируется на знании системой установленных ограничений целостности.

В демонстрационных целях был сделан беглый очерк статистических показателей базы данных, используемых в СУБД DB2 и INGRES. Далее обсуждалась одна из стратегий, построенных по принципу разделяй и властвуй , - декомпозиция запросов, впервые реализованная в прототипе системы INGRES. Было также отмечено, что стратегии, построенные по принципу разделяй и властвуй , весьма привлекательны для сред с поддержкой параллельных вычислений и распределенных систем.

И наконец, рассматривались некоторые методы реализации отдельных реляционных операторов, в частности оператора соединения. Был представлен псевдокод алгоритмов для пяти методов выполнения операции соединения: метода последовательного просмотра, поиска по индексу, поиска по хеш-таблице, метода слияния (включая метод сортировки-слияния) и метода хеширования. Также кратко рассматривались стоимостные характеристики описанных методов.