МОДИФИКАЦИЯ ДЕРЕВЬЕВ РАЗБОРА ДЛЯ ПАРАЛЛЕЛЬНОГО ИСПОЛНЕНИЯ ЗАПРОСА В СУБД > Полезные советы
Тысяча полезных мелочей    

МОДИФИКАЦИЯ ДЕРЕВЬЕВ РАЗБОРА ДЛЯ ПАРАЛЛЕЛЬНОГО ИСПОЛНЕНИЯ ЗАПРОСА В СУБД

МОДИФИКАЦИЯ ДЕРЕВЬЕВ РАЗБОРА ДЛЯ ПАРАЛЛЕЛЬНОГО ИСПОЛНЕНИЯ ЗАПРОСА В СУБД

Локшин М.В. Статья в формате PDF 115 KB

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

Рассмотрим систему, обеспечивающую работу распределенной СУБД и состоящей из N серверов. Предположим, что пользователь может отправить запрос на языке SQL к любому из N серверов и получить один и тот же ответ от всех серверов (на момент начала исполнения запроса). Такую работу системы можно организовать, к примеру, с использованием одного из методов репликации данных (всей базы, или только части таблиц). В этих условиях возможно создание системы обеспечивающей параллельную обработку SQL запросов, принцип работы которой описан в [1].

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

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

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

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

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

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

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

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

СПИСОК ЛИТЕРАТУРЫ

  1. М. В. Локшин, О.Я. Кравец. Построение систем для параллельной обработки запросов к СУБД. // Телематика´2004: Труды XI Всероссийской научно-методической конференции (7-10 июня 2004). -СПб:ИТМО. 2004. С. 94-95.
  2.  Гарсиа-Молина Г., Ульман Д., Уидом Д. Системы баз данных. Полный курс. -М. «Вильямс», 2003. - 1088 С.


МАТЕМАТИЧЕСКАЯ СТАТИСТИКА (учебное пособие)

МАТЕМАТИЧЕСКАЯ СТАТИСТИКА (учебное пособие) Статья в формате PDF 131 KB...

15 04 2026 4:57:22

ЯЗЫКОВАЯ ПОЛИТИКА ЕВРОПЕЙСКОГО ОБРАЗОВАНИЯ

ЯЗЫКОВАЯ ПОЛИТИКА ЕВРОПЕЙСКОГО ОБРАЗОВАНИЯ Статья в формате PDF 165 KB...

12 04 2026 11:42:10

Анатомия внутренних подвздошных артерий плода

Анатомия внутренних подвздошных артерий плода Статья в формате PDF 112 KB...

09 04 2026 6:25:15

О ЗАКОНЕ АРХИМЕДА

О ЗАКОНЕ АРХИМЕДА Статья в формате PDF 161 KB...

05 04 2026 11:47:46

КЛАССИФИКАЦИЯ БОЛЬНЫХ, СТРАДАЮЩИХ ХРОНИЧЕСКОЙ СЕРДЕЧНОЙ НЕДОСТАТОЧНОСТЬЮ МЕТОДОМ «ДЕРЕВЬЯ КЛАССИФИКАЦИИ»

КЛАССИФИКАЦИЯ БОЛЬНЫХ, СТРАДАЮЩИХ ХРОНИЧЕСКОЙ СЕРДЕЧНОЙ НЕДОСТАТОЧНОСТЬЮ МЕТОДОМ «ДЕРЕВЬЯ КЛАССИФИКАЦИИ» В статье описывается способ диагностики хронической сердечной недостаточности у больных ишемической болезнью сердца с помощью метода дерева классификации, который позволяет с использованием клинических показателей диагностировать функциональный класс со статистической достоверностью. ...

04 04 2026 18:32:55

ПРОГНОЗИРОВАНИЕ ЭКОНОМИЧЕСКОЙ ДЕЯТЕЛЬНОСТЬЮ ПРЕДПРИЯТИЯ И УПРАВЛЕНИЕ ЕГО РАЗВИТИЕМ

ПРОГНОЗИРОВАНИЕ ЭКОНОМИЧЕСКОЙ ДЕЯТЕЛЬНОСТЬЮ ПРЕДПРИЯТИЯ И УПРАВЛЕНИЕ ЕГО РАЗВИТИЕМ На основе системного анализа функционирования экономической деятельности промышленного предприятия введена его теоретическая кривая прогнозирования бизнеса и разработан алгоритм выхода на данную кривую в процессе стратегического управления развитием предприятия. ...

03 04 2026 12:34:39

ПРОБЛЕМА ДУХОВНОГО ОПЫТА ЧЕЛОВЕКА В КОНТЕКСТЕ РЕФЛЕКСИВНОГО АНАЛИЗА

ПРОБЛЕМА ДУХОВНОГО ОПЫТА ЧЕЛОВЕКА В КОНТЕКСТЕ РЕФЛЕКСИВНОГО АНАЛИЗА В данной статье раскрывается содержание таких понятий, как духовность и религиозность. Анализ названных понятий проходит в контексте рассмотрения самопознания в качестве особого вида деятельности человека. Автором также предлагаются критерии, согласно которым человек может определять степень развития своего сознания. ...

01 04 2026 14:38:51

ДИАГНОСТИКА ДЕЯТЕЛЬНОСТИ ПРЕДПРИЯТИЙ АПК

ДИАГНОСТИКА ДЕЯТЕЛЬНОСТИ ПРЕДПРИЯТИЙ АПК Статья в формате PDF 110 KB...

21 03 2026 21:37:24

АНОМАЛЬНЫЕ СТРУКТУРЫ ГЕОХИМИЧЕСКИХ ПОЛЕЙ ЭПИТЕРМАЛЬНОГО ЗОЛОТО-СЕРЕБРЯНОГО ОРУДЕНЕНИЯ ГОРНОГО АЛТАЯ И ГОРНОЙ ШОРИИ

АНОМАЛЬНЫЕ СТРУКТУРЫ ГЕОХИМИЧЕСКИХ ПОЛЕЙ ЭПИТЕРМАЛЬНОГО ЗОЛОТО-СЕРЕБРЯНОГО ОРУДЕНЕНИЯ ГОРНОГО АЛТАЯ И ГОРНОЙ ШОРИИ Приведены аномальные структуры геохимических полей (АСГП) по вторичным ореолам рассеяния месторождений и проявлений эптермального золото-серебряного оруденения. Оруденение в регионах связано с венд-раннекембийскими и среднедевонскими вулканогенными образованиями. Показаны различные наборы аномальных значений химических элементов в зонах ядерного концентрирования, транзита элементов и фронтальных зонах концентрирования. Оценен условный потенциал ионизации в зональных конструкциях АСГП, показывающих кислотно – основной потенциал среды минералообразования. Проведен факторный анализ для всех зон АСГП c показом эллипсоидов изменчивости и факторных нагрузок. ...

17 03 2026 4:40:13

СРАВНИТЕЛЬНЫЕ КОНСТРУКЦИИ ЧЕРЕЗ ПРИЗМУ ГЕНДЕРНЫХ РАЗЛИЧИЙ

СРАВНИТЕЛЬНЫЕ КОНСТРУКЦИИ ЧЕРЕЗ ПРИЗМУ ГЕНДЕРНЫХ РАЗЛИЧИЙ Сравнительные конструкции рассматриваются с позиции гендерного аспекта. Представлены результаты направленного ассоциативного эксперимента, который позволил выявить различия в женском и мужском конструировании, употрeблении и восприятии сравнительных конструкций. ...

14 03 2026 15:45:45

Еще:
Поддержать себя -1 :: Поддержать себя -2 :: Поддержать себя -3 :: Поддержать себя -4 :: Поддержать себя -5 :: Поддержать себя -6 :: Поддержать себя -7 :: Поддержать себя -8 :: Поддержать себя -9 :: Поддержать себя -10 :: Поддержать себя -11 :: Поддержать себя -12 :: Поддержать себя -13 :: Поддержать себя -14 :: Поддержать себя -15 :: Поддержать себя -16 :: Поддержать себя -17 :: Поддержать себя -18 :: Поддержать себя -19 :: Поддержать себя -20 :: Поддержать себя -21 :: Поддержать себя -22 :: Поддержать себя -23 :: Поддержать себя -24 :: Поддержать себя -25 :: Поддержать себя -26 :: Поддержать себя -27 :: Поддержать себя -28 :: Поддержать себя -29 :: Поддержать себя -30 :: Поддержать себя -31 :: Поддержать себя -32 :: Поддержать себя -33 :: Поддержать себя -34 :: Поддержать себя -35 :: Поддержать себя -36 :: Поддержать себя -37 :: Поддержать себя -38 ::