Шпаргалка по "Программированию и компьютерам"

 4. Параллелизм внутри  реляционных операторов. Оптимизация и  обработка запросов  в распределенных  СУБД. 

 Параллелизм внутри реляционных операторов

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

 Рассмотрим  просмотр отношения A, которое было разделено между тремя дисками на фрагменты A0, A1, A2. Этот просмотр можно реализовать с помощью трех операций просмотра, которые направляют свой вывод на вход общей операции слияния (merge operator). Операция слияния производит единый выходной поток данных и посылает его прикладной программе или следующей реляционной операции. Управляющая программа параллельного запроса создает три процесса просмотра, показанные на рис. 8, и предписывает им вводить данные из трех различных последовательных входных потоков (A0, A1, A2). Она также предписывает им послать вывод в общий узел, где происходит слияние вывода. Каждый просмотр может выполняться на отдельном процессоре и диске. Таким образом, первой нуждающейся в распараллеливании операцией является операция слияния, который объединяет несколько параллельных потоков данных в один последовательный поток.

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

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

 Объединение ввода и разделение вывода оператора. Реляционный граф потока данных, показывающий, как входные данные реляционного оператора сливаются в последовательный поток через порт. Вывод оператора разделяется оператором расщепления на несколько независимых потоков. Каждый поток может быть сдублирован или разделен на множество несвязанных потоков. При помощи операторов расщепления и слияния паутина узлов простого последовательного потока данных может быть соединена в параллельный план выполнения.

 В качестве примера рассмотрим два оператора  расщепления (см. Таблицу 1) в связи  с запросом на языке SQL, представленном на рис. 10. Предположим, что три процесса используются для выполнения оператора соединения, а пять других – для выполнения двух операторов просмотра – три просмотра разделов отношения A при двух просмотрах разделов отношения B. В каждом из трех узлов просмотра отношения A будет выполняться одна и та же операция разбиения, посылающая все кортежи со значениями в промежутке "A-H" на порт 1 процесса слияния 0, все кортежи со значениями в промежутке "I-Q" – на порт 1 процесса слияния 1 и все кортежи со значениями в промежутке "R-Z" – на порт 1 процесса слияния 2. Аналогично, а двух узлах просмотра отношения B будет выполняться та же самая операция расщепления с той разницей, что их вывод сливается портом 1 (не портом 0) каждого процесса слияния. Каждый процесс слияния видит последовательный входной поток кортежей A как слитый в порту 0 (левые узлы просмотра) и другой последовательный поток кортежей B как слитый в порту 1 (правые узлы просмотра). В свою очередь, выходные потоки каждого соединения разделяются на три потока в соответствии с критерием разделения отношения C.

 Таблица 1

 Пример  операторов расщепления  

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

 Простой SQL запрос и реляционный граф этого  запроса. Запрос указывает, что необходимо произвести соединение отношения A и отношения B посредством сравнения атрибута x каждого кортежа из отношения A со значением атрибута y каждого кортежа из отношения B. Для каждой пары кортежей, удовлетворяющих заданному предикату, формируется новый кортеж со всеми атрибутами двух исходных кортежей. Полученный кортеж затем добавляется к формируемому отношению C. На логическом графе этого запроса (каким его может создать оптимизатор запроса) показаны три оператора – один для слияния, другой для вставки и третий для просмотра каждого входного отношения.

 Оптимизация и обработка запросов в распределенных СУБД.

 Обработка запроса - это процесс трансляции декларативного определения запроса в операции манипулирования данными низкого уровня. Стандартным языком запросов, поддерживаемым современными СУБД, является SQL. Оптимизация запроса - это процедура выбора "наилучшей" стратегии для реализации запроса из множества альтернатив.

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

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

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

 Исходной  информацией для локализации  данных служит алгебраическое выражение, полученное на этапе декомпозиции запроса. В этом выражении фигурируют глобальные отношения без учета их фрагментации или распределения. Сущность данного шага заключается в том, чтобы локализовать участвующие в запросе данные, используя информацию об их распределении. При этом выявляются фрагменты, реально участвующие в запросе, а запрос преобразуется к форме, где операции применяются уже не к глобальным отношениям, а к фрагментам. Как указано выше, правила фрагментации выражаются посредством реляционных операций (селекции для горизонтальной фрагментации и проекции для вертикальной). Распределенные отношения реконструируются путем применения инверсии правил фрагментации. Это называется программой локализации. Программа локализации для горизонтально/вертикально фрагментированного запроса есть объединение (union)/соединение (join) его фрагментов. Таким образом, на этапе локализации данных запрос заменяется программой локализации; фрагментный запрос затем упрощается и реструктурируется, пока не будет получено "хорошее" выражение. Для упрощения и реструктуризации могут использоваться те же правила, что и на шаге декомпозиции. Как и в шаге декомпозиции, окончательный "хороший" фрагментный запрос может быть еще далек от оптимального; данный процесс лишь исключает "плохие" алгебраические выражения.

 Исходной  информацией для третьего шага является фрагментный запрос, т. е. алгебраическое выражение над фрагментами. Цель глобальной оптимизации - найти стратегию выполнения запроса, близкую к оптимальной. Напомним, что нахождение оптимальной стратегии - вычислительно трудноразрешимая задача. Стратегию выполнения распределенного запроса можно выразить в терминах операций реляционной алгебры и коммуникационных примитивов (операций "послать"/"получить"), описывающих пересылки данных между узлами. На предыдущих этапах запрос уже был в определенной мере оптимизирован, в частности, за счет удаления избыточных выражений. Однако проведенные оптимизации не зависели от характеристик фрагментов, например их мощности. Кроме того, на предыдущих шагах еще не были учтены коммуникационные операции. Путем перестановок операций в рамках фрагментного запроса можно получить множество эквивалентных планов его выполнения. Оптимизация запроса заключается в нахождении "наилучшего" из множества возможных планов, исследованных оптимизатором1).

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

 В распределенной среде функция стоимости, часто  определяемая в единицах времени, оценивает затраты вычислительных ресурсов, таких как дисковое пространство, число обменов с дисками, время CPU, коммуникации и т. д. Обычно это некоторая взвешенная сумма затрат ввода-вывода, CPU и коммуникаций. В распределенных СУБД применяется упрощенный подход, когда в качестве наиболее значимых рассматриваются лишь коммуникационные затраты. Это справедливо для глобальных сетей, где из-за ограниченной пропускной способности линий связи пересылки данных обходятся значительно дороже, чем при локальной обработке. Для того чтобы определить порядок выполнения операций, необходимо оценить вычислительные затраты для множества альтернативных упорядочений. Определение вычислительных затрат до выполнения запроса (статическая оптимизация) основано на статистике фрагментов и на формулах для оценки мощности результатов реляционных операций. Таким образом, решения, принимаемые в ходе оптимизации, зависят от имеющейся статистики фрагментов. Важнейший аспект оптимизации запросов - это порядок выполнения соединений, поскольку его изменение может привести к ускорению до нескольких порядков. Базовая методика для оптимизации последовательности соединений заключается в применении оператора полусоединений (semijoin). Основное преимущество полусоединений в распределенной системе - это сокращение размеров операндов, участвующих в соединениях, и, следовательно, коммуникационных затрат. Однако в более современных методиках, учитывающих также затраты на локальную обработку, полусоединения не используются, поскольку они приводят к увеличению объема локальной обработки. Результатом работы оптимизатора является оптимизированное алгебраическое выражение, включающее коммуникационные операции над фрагментами.

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

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

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