Распределенные и параллельные базы данных
Распределенные базы данных вводят в рассмотрение вопросы стоимости коммуникаций и расширения пространства поиска в связи с возможностью при оптимизации запросов учитывать допустимые перемещения данных и выбор узлов для выполнения промежуточных операций. Хотя в некоторых из ранних работ основной упор делался на сокращение стоимости коммуникаций [1, 3] (например, с использованием полусоединений), результаты System R* показывают доминирующую роль локальной обработки [39] (см. обзор в [38]). Со временем архитектуры распределенных баз данных эволюционизировали к реплицированным базам данных, в которых поддерживается управление физическим распределением данных, и к параллельным базам данных, основной эффект которых состоит в увеличении масштабируемости. В архитектурах, поддерживающих репликацию, важным вопросом является поддержание согласованности реплик, но это находится за пределами темы данной статьи.
В отличие от распределенных систем параллельные базы данных ведут себя как единая система, но используют множественные процессорные элементы для сокращения времени ответа на запросы. Преимущества параллелизма могут быть использованы несколькими способами. Например, физическое распределение данных, когда таблица (в общем случае, поток данных) разделяется или реплицируется между узлами, позволяет процессорам работать над независимыми наборами данных. Параллелизм можно также использовать для выполнения независимых операций или конвейерных операций (путем размещения узла-производителя и узла-потребителя на разных процессорах). Достоинства параллелизма уравновешиваются потребностью в коммуникации процессоров для обмена данными, например, в том случае, когда требуется перераспределение данных после выполнения операции. Кроме того, эффективное планирование выполнения физических операций вносит новое измерение в проблему оптимизации. В проекте XPRS [31, 32] поддерживается двухфазный подход, в котором на первой фазе для генерации плана выполнения используется традиционная однопроцессорная оптимизация.
На второй фазе определяется планирование процессоров. В работе над оптимизацией запросов в XPRS не изучались эффекты межпроцессорных коммуникаций. В работе Хасана [28] было показана важность учета расходов на коммуникацию. Хасан оставил двухфазный подход, использовавшийся в XPRS, но включил в первую фазу учет расходов и доходов от разделения данных с целью определения порядка соединений и используемых методов доступа. Атрибут разделения потока данных рассматривался как физическое свойство потока данных. На выходе первой фазы формировалось дерево операций, раскрывающее ограничения предшествования (например, для сортировки) и конвейерность выполнения. Для второй фазы оптимизации он предложил алгоритмы планирования, учитывающие коммуникационные расходы.
5 В однопроцессорных системах основное внимание уделяется сокращению общего объема работы. При параллельном выполнении стремятся скорее сократить время ответа, а не общую работу. На самом деле, во многих случаях, хотя это не необходимо, параллельное выполнение увеличивает общую работу.
- -
