Главная » SQL, Базы данных » РЕАЛИЗАЦИЯ РЕЛЯЦИОННЫХ ОПЕРАТОРОВ

0

В этом разделе представлено краткое описание некоторых очевидных методов реализации отдельных реляционных операторов, в частности оператора соединения. Включение данного материала в книгу было вызвано стремлением развеять ту "таинственность", которая присуща описанию процесса оптимизации. Обсуждаемые далее методы соответствуют механизмам, которые в разделе 18.3 были названы низкоуровневыми процедурами реализации.

Примечание. Ьолее сложные приемы реализации описаны в аннотациях к определенным работам, ссылки на которые приведены в конце главы. См. также приложение А.

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

1.  Операнд PER вообще не определяет атрибутов ("PER TABLE_DEE").

2.  Операнд PER, по меньшей мере, определяет один атрибут.

Первый вариант достаточно прост. Как правило, в этом случае выполняется просмотр всего отношения, для которого выполняется агрегирование, за исключением варианта, когда агрегируемый атрибут является индексируемым,  поскольку при этом требуемый результат можно вычислить исключительно с помощью индекса, без необходимости обращения к самому отношению. Например, рассмотрим следующее выражение.

SUMMARIZE SP ADD AVG ( QTY ) AS AQ

Для вычисления его результатов достаточно просмотреть индекс по атрибуту QTY (при условии, что такой индекс существует), не затрагивая самой переменной отношения поставок SP. Аналогичное замечание касается того случая, когда функция SUM заменяется функцией COUNT или AVG (причем для функции COUNT  подойдет любой индекс). Что касается функций МАХ и MIN, то результат их выполнения можно получить, применив единственную операцию чтения последней (для функции МАХ) или первой (для функции MIN) записи индекса (опять-таки, при условии, что индекс для соответствующего атрибута уже существует).

В последней части данного раздела предполагается, что в качестве операции агрегирования рассматривается именно операция, описанная в случае 2. Ниже  показан пример операции агрегирования второго типа.

SUMMARIZE SP PER P { Р# } ADD SUM ( QTY ) AS TOTQTY

С точки зрения пользователя  операции проекции,  соединения  и  агрегирования (второго типа), безусловно, абсолютно не похожи одна на другую. Но с точки зрения реализации они имеют некоторое сходство, поскольку в каждом из случаев система должна сгруппировать кортежи на основе общих значений указанных атрибутов. В случае операции

702     Часть V. Дополнительные темы

проекции подобная группировка позволяет системе исключить кортежидубликаты, в случае операции соединения — найти соответствующие друг другу кортежи, а в случае операции агрегирования — вычислить отдельные агрегированные значения для каждой группы. Ниже перечислены

несколько методов подобной группировки ксртежей.

1.          Последовательный просмотр (или метод "грубой силы").

2.          Поиск по индексу.

3.          Поиск с помощью хэш-функции.

4.          Слияние.

5.          Хэширование.

6.          Сочетания методов 1-5.

На     рис.     18.4—18.8     приведены     псевдокоды     процедур                                        реализации перечисленных   методов   для   операции   соединения    (операции   проекции   и агрегирования  оставлены  читателю  в  качестве  упражнения). На  этих рисунках используются следующие обозначения.  Прежде всего,  R  и S —  это отношения, которые   должны   быть   соединены,   а   с   —   их   общий   атрибут   (возможно, составной).   Предполагается,  что  возможен  последовательный  доступ  к  кортежам  обоих  отношений  R  и  s  по  одному  за  одну  операцию.  Эти  кортежи  в последовательности  доступа  буд ут  обозначаться  как  R[  1  ],  R [ 2 ] ,    …, R[ m]  и  S [ l ] ,  S [ 2 ] ,   …,  s  [  n  ],  соответственно.  Для  соединенного  кортежа, составленного  из  атрибутов  кортежей  R[ i ]   и  S[j],   будет   использоваться обозначение  R[i]  *  S [ j ] .   Наконец,  переменную  отношения  R  будем  считать внешней, а переменную отношения S —  внутренней (поскольку они управляют внешним и внутренним циклами просмотра, соответственно).

Последовательный просмотр

Метод последовательного просмотра (или "грубой силы") иногда также  называют простым методом. В этом случае рассматриваются все возможные комбинации кортежей (т.е. каждый кортеж отношения R проверяется в сочетании с каждым кортежем отношения S, как показано на рис. 18.4).

Примечание. Метод последовательного просмотра часто называют методом вложенных циклов, но это название нельзя считать приемлемым, поскольку вложенные циклы используются в реализациях всех названных выше методов.

Рис. 18.4. Метод последовательного просмотра

Проанализируем затраты, связанные с использованием метода  последовательного просмотра.

Примечание. Здесь мы ограничимся только анализом затрат на выполнение операций

ввода-вывода, хотя на практике может потребоваться также учесть другие  параметры

(например, затраты процессорного времени).

Глава 18. Оптимизация     703

Прежде всего, ясно, что для реализации этого метода потребуется всего m + (n * m)

операций чтения кортежей. А как в отношении операций записи кортежей? Иначе говоря, какова кардинальность результата операции соединения? (Количество операций записи кортежа будет равно кардинальности результирующего отношения, если последнее требуется записывать на диск.)

■    В частном, но достаточно важном случае соединения типа "многие к одному" (например, соединение типа "внешний ключ к соответствующему потенциально му ключу") кардинальность результирующего отношения почти всегда точно сов падает с величиной т или п в зависимости от того, какое из отношений, R или S, расположено на стороне внешнего ключа рассматриваемого соединения.

■    Теперь рассмотрим более общий случай соединения типа "многие ко многим".

Пусть dCR — количество различающихся значений атрибута с отношения R, по которому выполняется соединение, a dCS имеет тот же смысл, но для отношения

S. Если предположить, что значения атрибутов распределены равномерно (т.е. любое значение атрибута с может встретиться с той же вероятностью, что и другие значе ния), то для данного кортежа отношения R существует n/dCS соответствующих кортежей в отношении S со значением атрибута с, равным значению этого атрибу та в рассматриваемом кортеже из отношения R. Таким образом, общее количество кортежей в соединении (т.е. кардинальность результирующего отношения) будет равно (т *  n) /dCS. Или, если повторить изложенные рассуждения, начав с кор тежа в отношении S, то кардинальность результирующего отношения составит

(п * m)/dCR. Эти две оценки будут различными, если dCS * dCR, т.е. если в отношении R существуют значения атрибута с, которые не встречаются в отношении s, и наоборот. В этом случае следует использовать меньшую из оценок.

Безусловно, как было отмечено в разделе 18.2, на практике применяются  операции ввода-вывода страниц, а не кортежей. Поэтому предположим, что в отношениях R и S на странице помещается, соответственно, pR и pS кортежей (т.е. отношения занимают m/pR и n/ps страниц, соответственно). Теперь легко увидеть, что процедура, псевдокод которой показан на рис. 18.4, выполнит  (m/pR)  + (m*n) /pS операций чтения страниц. Аналогичным образом, если  поменять ролями отношения R и S (отношение S считать внешним, a R—  внутренним), количество операций чтения страниц составит (n/pS) + (n*m) /pR.

Для примера предположим, что m = 100, п = 10 000, pR = 1 и pS = 10.  Тогда результатами вычисления последних двух формул будут значения 100 1 00и1  001 000 операций чтения страниц, соответственно.

Заключение. В описанном подходе с применением последовательного просмотра в качестве внешнего отношения желательно использовать меньшее из двух  исходных отношений (в данном случае понятие меньшее относится к количеству занимаемых страниц внешней памяти).

Завершая краткое обсуждение метода последовательного просмотра,  заметим,  что этот прием является наихудшим из всех. В нем предполагается, что для отношения S не предусмотрен индекс, и не применяется хэш-функция для доступа к атрибуту соединения с. Эксперименты, проведенные Биттоном (Bitton) и др. [18.6], показали, что если это

предположение (отсутствие индексов и хэш-функции) действительно имеет место, то

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

Поиск по индексу

Теперь рассмотрим ситуацию, в которой для атрибута С внутреннего отношения S существует индекс X (рис. 18.5). Преимущество поиска по индексу по сравнению с методом последовательного просмотра состоит в том, что благодаря наличию индекса X для данного кортежа внешнего отношения R возможен переход непосредственно к соответствующему кортежу внутреннего отношения S. Общее количество операций чтения кортежей из отношений R и s будет равно кардинальности результирующего отношения операции соединения. Общее количество операций чтения страниц для отношений R и S при наихудшем предположении, что каждая операция чтения кортежа из отношения S требует обращения к отдельной странице, составит (m/pR)   +   (mn/dCS).

Но если кортежи отношения S хранятся в порядке значений атрибута соединения С, то  количество  операций  чтения  страницы  сокращается  до  значения  (m/pR)  + (mn/dCS) /pS. Воспользовавшись теми же примерами и значениями, что и выше (т = 100, п = 10 000, pR = 1, pS = 10), и  предположив, что dCS = 100, получим в результате вычисления двух  последних формул значения 10 100 и 1100, соответственно. Разница между полученными значениями показывает, что кортежи хранимых отношений целесообразно размещать в "подходящей" физической последовательности [18.7].

Рис. 18.5. Поиск по индексу

Однако при оценке затрат следует учитывать и издержки, связанные с выполнением операций чтения в самом индексе X. Наихудшим является предположение, что при поиске соответствующих кортежей в отношении S для каждого кортежа в отношении R потребуется выполнить непредвиденный поиск по индексу, требующий чтения страницы для каждого уровня индекса. Для индекса, обладающего х уровнями, операция поиска добавит к общему количеству операций чтения страницы еще m*х операций. На практике х обычно имеет значение 3 или меньше. (Более того, весьма вероятно, что верхний уровень индекса на протяжении всей обработки данных будет находиться в оперативной памяти, что значительно сократит количество операций чтения страниц.)

Глава 18. Оптимизация     705

Поиск с помощью хэш-функции

Поиск с помощью хэш-функции аналогичен поиску по индексу, за исключением того, что в качестве быстрого пути доступа к значениям атрибута соединения S. С внутреннего отношения S вместо индекса используется хэш-функция (рис. 18.6). Определение оценки затрат, связанных с выполнением данного метода, оставляем в качестве упражнения для читателя.

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

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

Рис. 18.6. Поиск c помощью хэш-функции

На основании этого можно сделать приведенные ниже заключения.

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

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

Рис. 18.7. Метод слияния (для соединений типа "многие ко многим")

Хэширование

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

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

Как и в случае метода поиска с помощью хэш-функции, определение оценок затрат,

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

18.1.     РЕЗЮМЕ

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

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

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

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

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

каноническом представлении запроса.

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

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

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

Наконец,  рассматривались  некоторые  методы  реализации  отдельных  реляционных операторов, в частности оператора соединения. Был представлен псевдокод алгоритмов

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

характеристики описанных методов.

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

такие функции рассматриваемых СУБД, которые не позволяют оптимизатору  выполнять свою работу так, как она могла быть выполнена в ином случае (т.е. при отсутствии этих препятствий). К числу таких особенностей, препятствующих оптимизации, можно, например, отнести дубликаты строк (см. [6.6]), трехзначную логику (см. главу 19) и реализацию трехзначной логики в языке SQL (см. [19.6] и [19.10]).

В данной главе задачи оптимизации рассматривались так, как они обычно трактуются и реализуются в СУБД; иными словами, здесь показано, какие  эмпирические подходы в

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

подходов. Вследствие этого многие аспекты общего процесса оптимизации могут  быть упрощены (а в некоторых случаях даже полностью исключены). К ним относятся перечисленные ниже и многие другие аспекты.

■     Применение метода выбора пути доступа с учетом стоимости (стадии 3 и 4 указан ного процесса).

■     Применение индексов и других обычных путей доступа.

■     Осуществление выбора между компиляцией и интерпретацией запросов к базе данных.

■     Применение алгоритмов для реализации реляционных операторов.

Дополнительная информация по этой теме приведена в приложении А.

Источник: Дейт К. Дж., Введение в системы баз данных, 8-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — 1328 с.: ил. — Парал. тит. англ.

По теме:

  • Комментарии