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

0

Как уже упоминалось выше, в конце раздела 18.4, реляционные выражения рекурсивно определяются в терминах подвыражений, что позволяет оптимизатору применять различные стратегии оптимизации по принципу "разделяй и  властвуй". Отметим, что использование подобных стратегий особенно привлекательно в средах, поддерживающих параллельные вычисления, в частности, в распределенных системах, в которых различные части запроса  могут выполняться параллельно на разных процессорах [18.56]— [18.58]. В данном разделе рассматривается одна из подобных стратегий, получившая название декомпозиция запросов. Впервые она била применена в прототипе системы Ingres [18.34], [18.35].

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

6 Напомним, что в языке запросов QUEL системы INGRES используются средства реляционного исчисления.

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

■     Подстановка кортежа — это процесс подстановки значения одной переменной в запросе (один кортеж за одну операцию).

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

Ниже рассмотрен пример декомпозиции (основанный на примере из [18.34]).  Словесное выражение этого запроса имеет следующий вид: "Определить имена поставщиков из Лондона, поставляющих некоторые детали красного цвета весом меньше 25 фунтов в количестве больше 200 штук". Приведем формулировку этого запроса на языке QUEL, на которую далее будем ссылаться, как на формулировку запроса Q0.

Q0: RETRIEVE ( S.SNAME) WHERE S.CITY  = ‘London’ AND  S.S#     = SP.S#

AND  SP.QTY  > 200

AND  SP.P#   = P.P# AND  P.COLOR  = ‘Red’ AND   P.WEIGHT < 25

Здесь переменными области значений являются s, P и SP, причем каждая из них распространяется на всю базовую переменную отношения с тем же именем.

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

Dl: RETRIEVE INTO P’ (P.P#) WHERE Р.COLOR = ‘Red’ AND  P.WEIGHT < 25

Этот запрос с единственной переменной может быть отделен, поскольку в нем присутствует только одна переменная (а именно — переменная Р), совместно используемая с остальной частью запроса. Так как запрос D1 связан с остальной частью исходного запроса через атрибут Р# (в условии сравнения SP. Р# = Р. Р#), атрибут Р# должен входить в кортеж-прототип (см. главу 8) отделенного запроса. Иными словами, отделенный запрос предназначен для выборки номеров только тех деталей красного цвета, которые весят  меньше  25  фунтов.  Отделенный  запрос  обозначим  как запрос  D1,  результатом выполнения которого  является временная переменная отношения р ‘.  (Назначение конструкции INTO состоит в том, чтобы создать новую переменную отношения Р’ с единственным атрибутом Р#. Эта переменная отношения создается автоматически и содержит результат выполнения операции RETRIEVE.) Наконец, заменим ссылки на переменную отношения Р в сокращенной версии запроса Q0 ссылками на переменную отношения р’. Эту новую сокращенную версию исходного запроса обозначим как запрос Q1 (этот запрос приведен ниже).

Ql: RETRIEVE (S.SNAME) WHERE S.CITY =    ‘London’ AND  S.S#  = SP.S#

AND  SP.QTY > 200

AND  SP.P# = P1.P#

Еще раз применим аналогичный прием к запросу Q1, отделив от него запрос, в котором используется единственная переменная SP. Присвоим отделенному запросу имя D2, а оставшуюся после Отделения часть запроса Q1 назовем Q2, как показано ниже.

D2: RETRIEVE INTO SP’ (SP.S#, SP.P#) WHERE SP.QTY > 200

Q2: RETRIEVE (S.SNAME) WHERE S.CITY = ‘London’ AND  S.S#   =

SP’.S# AND   SP’.P#

= P’.P#

Далее тем же способом отделим запрос с единственной переменной S.

D3: RETRIEVE INTO S’ (S.S#, S.SNAME) WHERE S.CITY = ‘London’ Q3: RETRIEVE (S’.SNAME) WHERE S’.S# = SP’.S#

AND  SP’.P# = P’.P#

Наконец, отделим еще один запрос, в котором используются переменные SР’ и Р’.

D4: RETRIEVE INTO SP” (SP’.S#) WHERE SP’.P# = P’.P# Q4: RETRIEVE (S’.SNAME) WHERE S’.S# = SP”.S#

В результате исходный запрос Q0 оказался разбитым на три запроса с одной переменной, Dl, D2 и D3 (каждый из которых является проекцией сокращения), и два запроса с двумя переменными, D4 и Q4 (каждый из которых является  проекцией соединения). Сложившуюся в результате ситуацию можно схематично представить в виде древовидной структуры, показанной на рис. 18.3.

Рис. 18.3. Дерево декомпозиции запроса Q0

Эту схему можно интерпретировать, как описано ниже.

■  В запросах Dl, D2 и D3 в качестве входных данных используются  переменные  отношения Р, SP и S (а точнее, те отношения, которые являются текущими значениями переменных отношения р, SP и S),  соответственно, которые и помещают результат своего выполнения во временные переменные отношения Р’, SP’ и S ‘, соответственно.s

■     Далее выполняется запрос D4, использующий в качестве входных данных времен ные переменные отношения Р’ и SP1 и помещающий результат своего выполне ния во временную переменную отношения SP’ ‘.

■     Наконец, выполняется запрос Q4, использующий в качестве входных данных пе ременные отношения S и SP", результат выполнения которого и является ре зультатом выполнения исходного запроса.

Обратите внимание на то, что запросы Dl, D2 и D3 полностью независимы один от другого и их можно обрабатывать в любом порядке (даже параллельно). Запросы D3 и D4 также можно обрабатывать в любом порядке, но только после получения результатов выполнения запросов D1 и D2. Но запросы D4 и Q4 нельзя подвергнуть дальнейшей декомпозиции, поэтому их следует обрабатывать с  помощью метода подстановки кортежей (что обычно означает необходимость применения последовательного поиска, называемого также подходом, основанном  на  использовании "грубой силы", поиска по индексу или хэшированного поиска—  см. раздел 18.7). В качестве примера рассмотрим выполнение запроса Q4. Обратившись к обычному набору данных, используемых в этой книге в качестве примеров, можно определить, что множество номеров поставщиков в атрибуте SP’ ‘ . s# будет выглядеть так: {SI, S2, S4 }. Каждое из этих трех значений по очереди должно быть подставлено в атрибут SP’ ‘ . s#. В результате запрос Q4 примет такой вид, как будто он был записан следующим образом.

‘ S 2 ‘ OR                                        S’S #     =    ‘S4′

В [18.34] приведены алгоритмы разбиения исходного запроса на меньшие запросы и выбора переменных для подстановки кортежей. Именно от выбора переменных во многом зависят фактические результаты оптимизации; в [18.34]  приведены эвристические подходы для оценки стоимости того или иного варианта (в системе Ingres обычно, но не всегда для подстановки используется  отношение с наименьшей кардинальностью). Основная задача процесса оптимизации — избежать выполнения декартовых произведений и минимизировать количество сканируемых кортежей на каждом этапе вычисления.

В [18.34] не рассматривается оптимизация запросов с одной переменной. Однако информация об этом уровне оптимизации присутствует в общем обзоре системы Ingres [18.11]. По сути, эти методы напоминают аналогичные функции, выполняемые в других системах, поскольку в них используется  статистическая информация, хранящаяся в каталоге, на основе которой  выбирается конкретный путь доступа к требуемым данным (например, на основе хэшированного или простого индекса). В [18.35] представлены некоторые  экспериментальные материалы  (например, результаты измерения  производительности для эталонного набора запросов), позволяющие сделать вывод, что описанные выше методы оптимизации СУБД Ingres дают хорошие результаты и достаточно эффективны при применении на практике. Ниже приведены некоторые выводы, взятые из этой работы.

1.     Метод отделения — это лучшая из методик, которую можно применять на первом этапе оптимизации.

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

3.   Если к одной из переменных в запросе с двумя переменными применялась  подстановка кортежей, то оптимальная тактика заключается в формировании динамически, по мере необходимости, простого или хэшированного индекса по атрибуту соединения, принадлежащему другому отношению (такой метод фактически применяется в СУБД Ingres).

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

По теме:

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