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

17.57.КаЬга N., DeWitt D.J. Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans Proc. 1998 ACM SIGMOD Int. Conf on Management of Data.- Seattle, Wash., June, 1998.

17.58.Gray J. Parallel Database Systems 101 Proc. 1995 ACM SIGMOD Int. Conf. on Management of Data. - San Jose, Calif, May, 1995.

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

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

С разделением оперативной памяти. Сеть позволяет всем процессорам обращаться к общей оперативной памяти.

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

Без разделения. Каждый процессор обладает собственной оперативной и дисковой памятью, но сеть позволяет всем процессорам обмениваться данными между собой.

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

Ниже представлены некоторые способы секционирования данных (data partitioning), т.е. разбиения отношения г на секции или подчиненные отношения и распределение этих секций между п различными процессорами.

Секционирование диапазона (range partitioning). Отношение г делится на непе-ресекаюшиеся секции 1, 2, п на основе значений некоторого подмножества s атрибутов отношения г (концептуально отношение г отсортировано по подмножеству атрибутов S, а результат разделен на п секций равного размера). Секция i при этом соответствует процессору i. Данный подход очень удобен для запросов с выборками на основе условий равенства или соответствия диапазону для подмножества атрибутов отношения s.

Хеш-секционирование (hash partitioning). Каждый кортеж t отношения г соответствует процессору h(t), где h- некоторая хеш-функция. Этот метод прекрасно подходит для запросов с выборками на основе условий равенства для одного или нескольких хеш-атрибутов, а также для запросов с последовательным доступом ко всему отношению г.

Круговое секционирование (round robin partitioning). Концептуально отношение г отсортировано некоторым образом, а i-й кортеж в отсортированном результате соответствует процессору с номером, вычисленным как результат деления i по модулю п. Этот подход прекрасно подходит для запросов с последовательным доступом ко всему отношению г.

Распараллеливание обработки можно применять для выполнения отдельной операции {интраоперационное распараллеливание), для выполнения разных операций внутри одного запроса {межоперационное или интразапросное распараллеливание) и для выполнения разных запросов {межзапросное распараллеливание). Эти варианты рассмотрены в учебных пособиях [17.4], [17.61]; некоторые методы и алгоритмы обсуждаются в [17.59], [17.60]. Следует отметить, что параллельная версия хеш-соединения (см. раздел 17.7) особенно эффективна и широко используется на практике. 17.59.Bitton D., Boral Н., DeWitt D.J., Wilkinson К. Parallel Algorithms for the Execution of Relational Database Algorithms ACM TODS. - September, 1983. - 8, № 3. Здесь описаны алгоритмы реализации операций сортировки, проекции, соединения, обобщения и обновления в многопроцессорных средах. Представлены также общие формулы стоимости, учитывающие операции ввода-вывода, загрузку процессора и обмен сообщениями. Эти формулы можно адаптировать к различным многопроцессорным архитектурам.

17.60.Hasan W., Motwani R. Optimization Algorithms for Exploiting the parallelism-Communication Tradeoff in Pipelined Parallelism Proc. 20th Intern. Conf on Very Large Data Bases. - Santiago, Chile, September, 1994.

17.61.Silberschatz A., Korth H.F., Sudarshan S. Database System Concepts (3rd edition).- New York, N.Y.: McGraw-Hill, 1997.

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

Ответы к некоторым упражнениям

17.1. а- эквивалентны; б- эквивалентны; в- эквивалентны; г- не эквивалентны; д - эквивалентны; е - не эквивалентны (эти выражения будут эквивалентными, если заменить операцию AND операцией OR); ж - не эквивалентны; з - не эквивалентны; и - эквивалентны.

17.2. В демонстрационных целях покажем, что соединение является коммутативным. Соединение А JOIN В отношений А{Х, Y} и B{Y, Z} - это отношение с заголовком {X, Y, Z} и такими кортежами {Х:х, Y:y, Z:z}, что кортеж из значений х (для X) и у (для Y) должен присутствовать в отношении А, а кортеж из значений у (для Y) и Z (для Z) должен присутствовать в отношении В. Это определение абсолютно симметрично относительно А и В. Поэтому А JOIN В тождественно В JOIN А. I

17.3. Для примера покажем ассоциативность операции объединения. Объединение А UNION В двух отношений А и В совместимых типов - это отношение с тем же заголовком, что А и В, и телом из всех кортежей t, принадлежащих отношению А, В или им обоим одновременно. Таким образом, если С - еще одно совместимое по типу отношение, то:

объединение ( А UNION В ) UNION С - это отношение с тем же заголовком и телом, состоящим из всех кортежей t, которые принадлежат отношению А UNION В, отношению С или им обоим одновременно;

объединение А UNION ( В UNION С ) - это отношение с тем же заголовком и телом, состоящим из всех кортежей t, которые принадлежат отношению В UNION С, отношению А или им обоим одновременно.

Эти два отношения имеют одинаковые заголовки, а тело в каждом случае состоит из всех кортежей, принадлежащих хотя бы одному из отношений А, В или С. Поэтому приведенные отношения тождественны. Щ

17.4. Покажем, что объединение распределяется по пересечению.

Ecлиt е А UNION ( В INTERSECT С ),TOtG Aилиt£ В INTERSECT С.

Если t G А, то t G А UNION В и t G А UNION С, и, следовательно, t G (А UNION В ) INTERSECT ( А UNION С ).

Если t G В INTERSECT С, то t G В и t G С. Тогда t G ( А UNION В ) и t G (А UNION С ). Следовательно, t G ( А UNION В ) INTERSECT ( А UNION С ).

И обратно, если t G ( А UNION В ) INTERSECT ( А UNION С ),Tot G ( А UNION В ) и t G (А UNION С ). Из этого следует, что t G А или t принадлежит обоим отношениям, В и С. Следовательно, t G А UNION ( В INTERSECT С ).

17.5. Покажем, что А UNION ( А INTERSECT В ) = А. Если t G А, то ясно, что t G А UNION ( А INTERSECT В ). И обратно, если t G А UNION ( А INTERSECT В ),TOt G Aилиt принадлежит обоим отношениям, А и В. В любом случае получим, что t G А.

17.6. Два случая с условиями уже рассмотрены в разделе 17.4. А случаи без условий достаточно просты. Покажем, что проекция не распределяется по разности на основе следующего обратного примера. Пусть отношения A{X,Y} и B{X,Y} содержат