Стратегии выполнения соединений в распределенных базах данных

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

Сначала обратимся к проблемам соединений в распределенных базах данных с традиционной организацией (подобных базам данных System R*). В System R* применяются несколько стратегий выполнения соединений удаленных отношений. Мы рассматриваем их в [129] и не будем здесь повторяться. Однако, в [95] на основе опыта использования System R* и анализа заложенных в эту систему предлагаются несколько улучшенных стратегий. Нам кажется полезным описать их.

Рассматривается соединение двух удаленных отношений S и T, расположенных в узлах 1 и 2, соответственно, под управлением предиката эквисоединения S.C1 = T.C2. Результат соединения должен быть получен в узле 1. Предполагается также следующее: Ни одно из отношений не кластеризовано по полям соединения; отсутствуют индексы на полях, отличных от полей соединения; в запросе не требуется проекция (т.е. кортежи результата включают все поля S и T); в запросе отсутствуют предикаты ограничения отношений S и T; отношения S и T хранятся в отдельных блоках внешней памяти (любой блок базы данных, содержащий кортежи S или T, не содержит кортежей других отношений).

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

Второй алгоритм основывается на использовании полусоединений. Оба отношения сортируются в соответствии со значениями полей C1 и C2 с образованием временных отсортированных файлов S' и T'. Производится проекция S' на С1 (уничтожаются дубликаты) и результат посылается в узел 2. В этом узле выполняется полусоединение T' с полученным унарным отсортированным отношением (т.е. выбираются те кортежи T', значение поля C2 которых совпадает с каким-либо значением C1 полученного списка). Полученное промежуточное по-прежнему отсортированное отношение T'' посылается в узел 1, где выполняется соединение S' и T'' методом слияний (оба отношения уже отсортированы) и производится окончательный результат.

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

Наконец, третий альтернативный алгоритм соединения двух отношений, предлагаемый в [95], основан на использовании так называемых фильтров Блюма [28]. В соответствии с этим алгоритмом, если индексы на полях S.C1 и T.C2 не определены, сначала в узле 1 для отношения S по полю C1 строится фильтр Блюма. Фильтр представляет собой битовый массив, инициализированный нулями. Для формирования фильтра производится сканирование отношения S, и к значению поля C1 каждого кортежа применяется хэш-функция, ставящая в соответствие этому значению позицию бита в массиве. Этот бит устанавливается в единицу.

Сформированный фильтр посылается в узел 2. В этом узле производится сканирование отношения T и к значениям поля C2 применяется та же хэш-функция, задающая позицию соответствующего бита в фильтре. Если значение этого бита равно 1, то кортеж отношения S посылается в узел 1 в потоке кортежей T'. В этом узле выполняется соединение S и T' и формируется результат.

Наличие индексов на полях S.C1 и T.C2 позволяет модифицировать алгоритм. В частности, фильтр Блюма для отношения S можно построить в этом случае, сканируя только записи индекса без потребности обращаться к кортежам отношения.

В [95] приводятся оценки для каждого из трех алгоритмов и описываются экспериментальные результаты их использования в System R* в высоко- и среднескоростных сетях. Эти результаты показывают, что альтернативные стратегии выполнения соединений в ряде случаев оказываются более эффективными, чем основные стратегии System R*.

Основным, на наш взгляд, выводом из работы [95], безотносительно к проблемам System R*, является то, что исследования стратегий выполнения удаленных соединений продолжают быть актуальными и приносить полезные результаты даже при традиционной организации распределенных баз данных. Что же касается более сложных организаций, то каких-либо общепринятых решений по части оптимизации соединений пока вообще нет. Большинство работ (например, [97-100]) носят теоретический характер, в них ставятся частные проблемы и предлагаются их некоторые решения, но все это недостаточно систематизировано. Поэтому мы ограничимся тем, что покажем возможные выгоды нетрадиционных организаций и сложности, возникающие в оптимизаторах при их использовании.

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

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

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

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

В более общем случае наличие фрагментов отношения в нескольких узлах сети позволяет распараллелить выполнение соединения. Например, если, как в [33], фрагменты отношения получены в результате применения мультиатрибутного хэширования, то удается достичь очень высокой степени распараллеливания. Заметим, что распределенные системы, ориентированные на параллельное выполнение реляционных операций, обычно строятся на основе аппаратуры высокоскоростных локальных сетей и к ним можно относиться как к машинам баз данных. Вопросы оптимизации в таких системах своеобразны и, вообще говоря, отличны от тех, которые свойственны распределенным системам рассматриваемого нами класса.

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

Заметим для корректности, что вопрос относительно дубликатов так прост только в чистой реляционной алгебре. Как только речь начинает идти о возможности использования встроенных функций таких, как COUNT и AVG, ситуация резко усложняется. Видимо, если бы вертикальное разделение было бы реализовано в System R*, то пришлось бы в подотношениях сохранять дубликаты, что само по себе выглядело бы довольно странно.

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

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

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

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

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