Оценка времени выполнения запросов с коррелированными подзапросами и операциями агрегирования

УДК 004.65

Ю. А. Григорьев, С. П. Остриков

ОЦЕНКА ВРЕМЕНИ ВЫПОЛНЕНИЯ ЗАПРОСОВ С КОРРЕЛИРОВАННЫМИ ПОДЗАПРОСАМИ И ОПЕРАЦИЯМИ АГРЕГИРОВАНИЯ

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

В настоящее время в различных информационных системах (ИС) используются системы управления базами данных (СУБД), поддерживающие реляционную модель данных. Для описания и манипулирования данными применяется стандартный язык SQL, который относится к классу непроцедурных языков. SQL-запрос, поступивший на сервер базы, подвергается оптимизации в целях уменьшения времени его выполнения. Суть оптимизации состоит в генерации нескольких альтернативных планов реализации запроса и выборе плана с наименьшей стоимостью, пропорциональной времени выполнения запроса. В теории реляционных баз данных наибольшее внимание уделяется построению оптимального плана для класса запросов, включающих операции соединения таблиц или имеющих конструкции, которые можно свести к соединению [1, 2]. В теории по существу не рассматривается важный класс запросов с многоуровневыми вложенными коррелированными подзапросами и операциями агрегирования. В некоторых публикациях [3, 4] в основном анализируются запросы с двумя коррелированными подзапросами (один из них внешний) и необоснованно утверждается, что для них оптимальным является план с группированием значений атрибута связи. При этом расчет стоимости и сравнение альтернативных планов не выполняются. Это приводит к тому, что во многих СУБД (Oracle, DB2 и др.) для реализации запросов из указанного класса используются планы, основанные на операции группирования. В результате анализа выявили, что эти планы являются оптимальными только в некоторой области изменения параметров запросов и наполнения базы данных, т.е. часто для реализации запроса в СУБД выбирается неоптимальный план. Поэтому важной является задача генерации альтернативных планов выполнения запросов с многоуровневыми вложенными коррелированными подзапросами и операциями агрегирования, оценки стоимости планов и построения областей их предпочтительного использования.

Преобразование исходного плана выполнения запроса в альтернативный план. На рис. 1 приведено описание исследуемого класса запросов к базе данных. Здесь используются следующие обозначения: Ri (i = 1, n) — таблица i-го подзапроса, из которой читаются записи в процессе выполнения запроса. Некоторые или все таблицы могут совпадать; A10 — атрибут таблицы R1, который является результатом выполнения запроса (A10 может быть подмножеством атрибутов или операций агрегирования); Ail (i = 1, n — 1) — атрибут i-й таблицы, для которого установлено подусловие поиска Ail тi fi+1(Ai+1,2), ri (i = 1, n — 1) — арифметический оператор сравнения (=, >, >=, < и т.д.), fi (i = 2, n) — одна из операций агрегирования (MIN, MAX, SUM, COUNT, AVG и др.). Это может быть и арифметическое выражение, куда входят несколько операций агрегирования; Ai2 (i = 2, n) — атрибут i-й таблицы, являющийся аргументом функции агрегирования fi. Агрегирование значений Ai2 выполняется для тех записей таблицы Ri, которые удовлетворяют условию WHERE i-го вложенного подзапроса. Будем считать, что 1-й вложенный подзапрос — это самый внешний запрос SELECT; Ai3 (i = 1, n — 1) - атрибут i-й таблицы, по которому устанавливается соединение с ^+1)-й таблицей (Ri+1) в (i + 1)-м подзапросе (поэтому подзапрос является коррелированным); Ai4 (i = 2, n) — атрибут i-й таблицы, по которому устанавливается соединение с (i — 1)-й таблицей (Ri-1) в i-м подзапросе.

На рис. 2, а показан результат частичной трансляции описания запроса (см. рис. 1) в дерево выражений реляционной алгебры (п и а — операции проекции и селекции). На каждом i-м уровне вложенности (i = 1, n — 1) введена операция а без индекса, т.е. без условия,

SELECT AlO FROM RI

WHERE Al l Ti

(SELECT Г2(А22) FROM R2

WHERE R1.A13~R2.A24 AND A21 2

(SELECT ß(A32) Г ROM R3

WHERE R2.A23=R3, A34 AND A31T3

(SELECT Г4(А42) FROM R4

AND An-1,1 tn-1

(SELECT fn(An2) FROM Rn

WHERE Rn-l.Aii-l.3-Rn.Aji4

)•••)»

Рис. 1. Описание исследуемого класса запросов

ТСаю

/Ч

<condition>

/ I \

AI 1 xl £2

aAi3=A24 <condition>

I / I \

R2 А21 т2 О

CW2,3=An-l,4

I

Rn-l

I......

<condition>

/ I \

An-1,1 тп-1 fn

I

OAn-l,3=An4

I

Rn

ЯлЮ

I

Ga13=t2 nAllxl q2

X

R1 T(A24 r2, f2(A22) q2) I

CTa23=i3 n A21 x2 q3

^ X ^

R2 ^

^ An-l,3=rn n An-1,1 TQ-1 qn

I

X ^

Rn-1 y

Rn

Рис. 2. Исходный (а) и альтернативный (б) планы выполнения запроса

которая определяет отношение, получаемое после выполнения операции селекции с условием Ail тi fi+1(Ai+1,2) над отношением R1 или aAi-1,3 = Ai4. В процессе физической реализации дерево просматривается сверху вниз. Сначала читаются записи из R1. Для каждой такой записи определяется отношение aA13 = A24 (значение A13 уже определено), далее для каждой записи из этого отношения определяется aA23 = A34 (значение A23 уже определено) и так далее до самого нижнего уровня вложенности. Затем для каждой записи из рассматриваемых отношений aAi _ 1j3 = Ai4 выполняется перемещение снизу вверх, связанное с проверкой условий а (без индекса) и вычислением функций агрегирования fi.

Для построения альтернативного плана необходимо выполнять следующие шаги на каждом уровне вложенности.

1. Селекцию aAi _ 1j3 = Ai4 переместить вверх по дереву за операцию селекции а без индекса, т.е. после ее выполнения.

2. Операцию селекции aAi3 = Ai + 1,4 переместить за операцию селекции а без индекса. На место перемещенной селекции вставить операцию группирования y(Ai+1,4 ri+1, fi+1(Ai+1,2) qi+1). Здесь Ai+1,4 — это атрибут, по которому выполняется группирование. Группируемое

отношение поступает на вход операции 7 после выполнения операций, расположенных по дереву ниже. fi+1(Ai+1,2) — это операция агрегирования атрибута Ai+1,2, которая выполняется для каждой группы. Идентификаторы ri+1 и qi+1 — это псевдонимы значений, указанных слева от них, т.е. Ai+1,4 и fi+1(Ai+1,2) соответственно.

3. Операцию селекции а без индекса и условие «condition» заменить на селекцию aAi1 тiqi+i над декартовым произведением Ri и 7.

4. Каскад селекций aAi3 = Ai + i,4 и aAi1 тiqi+1 заменить на одиночную селекцию aAi3=ri+lnAi1 тiqi+1.

Последовательно применяя процедуру 1-4 для каждого уровня вложенности (i меняется от (n — 1) до 1, селекция aA03 = A14 считается пустой), план (см. рис. 2, а, исходный план) можно преобразовать к дереву, приведенному на рис. 2, б (альтернативный план). Используя законы реляционной алгебры, можно доказать, что преобразования 14 являются корректными, т.е. после выполнения снизу вверх процесса, представленного на рис. 2, б, будет получен правильный результат поиска данных.

В некоторых СУБД, например Oracle, план (см. рис. 2, б) выполняется неэффективно на физическом уровне (здесь соединение aAi3=ri+1nAi1 тiqi+1 реализуется путем фильтрации всех записей уровня i). Далее приведены n SQL-операторов (рис. 3), совокупность которых соответствует плану на рис. 2, б. В каждом запросе выполняется соединение двух таблиц, кроме самого первого. Практически во всех СУБД предусмотрены эффективные методы соединения. Поэтому эти n SQL-операторов часто выполняются быстрее, чем один исходный запрос (см. рис. 1) в соответствии с планом на рис. 2, б.

Оценка времени выполнения запроса для исходного и альтернативного планов. В настоящей работе доказаны приведенные ниже четыре теоремы о производящих функциях (ПФ) числа обработанных записей и преобразованиях Лапласа-Стилтьеса (ПЛС) времени выполнения запроса для исходного и альтернативного планов. Это важно, так как на этапе проектирования ИС конкретные значения полей записей базы данных и некоторые параметры запросов неизвестны, и поэтому можно говорить об их случайном характере.

Исходный план.

Теорема 1. Производящая функция Hj(z) числа записей, обработанных на i-м уровне вложенности и ниже, для каждой записи (i — 1)-го уровня определяется следующей рекуррентной формулой:

Hi(z) = Gi(1 — рг(1 — zHi+i(z))), i = 1, n,

где

Gi(z) = zV

производящая функция числа записей в таблице Лг, V — прогнозируемое число записей в этой таблице,

1, для г = 1;

Рг Н 1 _ ,

—, для г = 2, п,

1г4

/г4 — прогнозируемая мощность атрибута А14 (число разных значений), Яп+1(г) = 1.

Доказательство. Из описания процесса реализации плана (см. рис. 2, а) следует, что число записей, обработанных на г-м уровне вложенности, определяется селекцией аАг4=а, где а — значение атрибута Аг-1,3 записи (г — 1)-го уровня (г = 2, п). Для г = 1 селекция отсутствует. Из работы [2] (см. формулу (2.25)) следует, что вероятность

записи таблицы, удовлетворяющей условию аАг4=а, равна рг = —,

__1г4

г = 2, п; для г = 1 р1 = 1, так как селекция отсутствует.

Используя формулу (2.20) из работы [2], получим, что ПФ Д*(г) числа записей, обработанных только на г-м уровне вложенности для каждой записи (г — 1)-го уровня равна

Н

Используя дополнительное событие [5], ПФ H*(z) можно трактовать как вероятность, что записи, обработанные только на i-м уровне вложенности для каждой записи (i — 1)-го уровня, являются "красными" (вероятность этого дополнительного события равна z). Выражение zHi+i(z) можно интерпретировать как вероятность того, что запись i-го уровня вложенности является "красной" (z) и все связанные с ней записи более нижнего уровня также являются "красными" (H+1(z)). Подставляя zH+1(z) в выражение (4) вместо z, получим вероятность, что записи, обработанные на i-м уровне вложенности и ниже, для каждой записи (i — 1)-го уровня, являются "красными". А эта вероятность и есть H(z), т.е. H(z) = H*(zHi+1(z)).

Выражение (1) доказано.

Следствие 1. Производящая функция числа записей базы данных, обработанных при выполнении запроса в соответствии с исходным планом (см. рис. 2, а), равна

H

Это следует из определения ПФ H1(z) (см. (1)).

Теорема 2. ПЛС T(s) времени обработки записей i-го уровня вложенности и ниже для каждой записи (i — 1)-го уровня равно

T

где Gi(z) и p., определяются выражениями (2) и (3); 5,t(s) — ПЛС-времени поиска/чтения одной записи i-го уровня вложенности из БД; Ct(s) — ПЛС-времени сравнения в соответствии с условием Ai1 Tifi+1(Ai+1,2) для i = 1, n — 1 и/или определения текущего значения функции агрегирования fi(Ai2) при успешном сравнении для i = 2, n (см. рис. 2, а),

Tn+i(s) = 1.

Доказательство. При доказательстве теоремы 1 была получена производящая функция H*(z) числа записей, обработанных только на i-м уровне вложенности для каждой записи (i — 1)-го уровня (см. уравнение (4)). ПЛС-времени обработки такой записи и связанных с ней записей нижних уровней определяется следующим выражением:

T~

Для доказательства (7) воспользуемся методом дополнительного события [5], трактуя ПЛС как вероятность того, что за случайное время не наступит "катастрофы" (s — интенсивность "катастроф"). Тогда вероятность T~(s) равна вероятности того, что "катастрофа" не наступит за время:

1) поиска/чтения записи i-го уровня (4(s));

2) обработки связанных с ней записей нижних уровней (Ti+1(s));

3) сравнения атрибута Ai1 и агрегирования значения атрибута Ai2

(6(s))-

Это доказывает выражение (7). Подставляя (7) в (4) и учитывая свойства ПФ и ПЛС, получим утверждение теоремы, т.е. T(s) = H*(ii(s)Ti+1(s)^i(s)). Выражение (6) доказано.

Следствие 2. ПЛС-времени выполнения запроса в соответствии с исходным планом (см. рис. 2, а) равно

T

Это утверждение следует из определения ПЛС T1(s) (см. формулу (6)).

Альтернативный план (в виде SQL-запросов — см. рис. 3).

Теорема 3. Производящая функция W,(z) числа записей, обработанных при выполнении i-го SQL-запроса, определяется следующей формулой:

W

SELECT An4 as rti, fti(An2) as qn INTO TEMPn

FROM Rh

GROL'P BY An4

Далее необходимо закодировать п-2 SQL-операторов, здесь i изменяется oi п-1 до 2:

SELECT Ai4 as ri. li(Ai2) as qi IN TO TEMPi

FROM Ri, TEMPi+1

WHERE Ri.A23-TEMPil.ril AND Ri.Ail l TEMPi+l.qi+1

GROUP BY Ai4

Затем должен быть выполнен п- й запрос, который имеет номер !:

SELECT AI0

FROM RI, TEMP2

WHERE Rl.A13-TF.MP2.r2 ANDR1.A11 Tl TEMP2.q2

Рис. 3. Запросы SQL, моделирующие альтернативный план

где

Qn+1

Доказательство. Анализ SQL-запросов (см. рис. 3) показывает, что при выполнении каждого i-го запроса, кроме запросов с номерами n и 1, выполняются следующие действия.

1. Читаются записи из таблицы TEMPi+1 (ПФ числа записей равна

Qi+1(z))-

2. Читаются записи из исходной таблицы R (ПФ числа записей равна Gj(z)). Читаются все записи этой таблицы, так как при выполнении операции группирования GROUP BY, определенной в (i + + 1)-м запросе, в таблице TEMPi+1 сохраняются все значения атрибута связи Ai+1,4 и в i-м запросе используется условие соединения Ai3 = TEMPi+1.ri+1, где |ri+1| = |Ai+1,4|.

3. Результат выполнения запроса записывается в таблицу TEMPi (ПФ числа записей равна Qj(z)). Здесь выполняется операция группирования, число записей в таблице TEMPi равно мощности атрибута Ai4, т.е. величине Ji4.

В n-м SQL-запросе (первый запрос, см. рис. 3) поиск и группирование выполняются в одной таблице (таблица TEMPn+1 отсутствует), поэтому Qn+1(z) = 1. В первом SQL-запросе (последний запрос, см. рис. 3) запись данных во временную таблицу не выполняется, поэтому здесь Q1(z) = 1. Величины V и Ji4 — это параметры, задаваемые проектировщиком (случайные величины с одним состоянием). Это доказывает выражения (10) для Q»(z) и Gj(z).

Из определения ПФ Qi+1 (z), G^z), Q»(z) (см. действия 1-3, рассмотренные выше) и свойства производящих функций получаем равенство (9). Теорема доказана.

Следствие 3. ПФ W(z) числа записей, обработанных в процессе выполнения всех n SQL-запросов (см. рис. 3), равна

n

w

i= 1

Выражение (11) следует из (9) и свойств производящих функций.

В общем случае записи таблицы R не упорядочены по атрибуту соединения Ai3, поэтому предположим в дальнейшем, что таблицы R и TEMPi+1 соединяются с использованием метода вложенных циклов NLJ.

Теорема 4. ПЛС Y(s) времени выполнения i-го SQL-запроса определяется следующим выражением:

Y

где ПФ Wi(z) определяется выражением (9); ПФ G,(z), Q(z) определяются выражениями (10);

Qn+1

$*(s) — ПЛС-времени чтения/записи одной записи базы данных в таблице при выполнении i-го запроса; £*(s) — ПЛС-времени сравнения записей в соответствии с условием Ai3 = TEMPi+1.ri+1 AND Ai1 тi TEMPi+1.qi+1 для i = n — 1, 1 и/или определения текущего значения функции агрегирования fi(Ai2) при успешном сравнении для i = n, 2.

Доказательство. Первый сомножитель в выражении (12) равен ПЛС-времени ввода/вывода записей в таблицы базы данных при выполнении i-го SQL-запроса. Второй сомножитель равен ПЛС-времени соединения таблиц R и TEMPi+1 методом NLJ [2], (см. формулу (2.71)) и определения значения функции агрегирования при выполнении i-го запроса. Тогда из свойства ПЛС следует выражение (12). Теорема доказана.

Следствие 4. ПЛС-времени выполнения всех n SQL-запросов, т.е. времени выполнения исходного запроса (см. рис. 1) в соответствии с альтернативным планом (см. рис. 3), равно

n

Y

i=1

Выражение (14) следует из свойства ПЛС.

Если таблицы R, и TEMPi+1 отсортированы по атрибуту соединения, то СУБД может выбрать метод SMJ для соединения этих таблиц.

В этом случае второй сомножитель в выражении (12) следует заменить на

Сравнение времени выполнения запроса для исходного и альтернативного планов. Ранее были получены характеристики времени выполнения запроса с вложенными коррелированными подзапросами и операциями агрегирования (см. рис. 1) для исходного и альтернативного планов (см. рис. 2, а и б). Далее приведено сравнение математических ожиданий времени выполнения запроса для этих двух планов.

Продифференцировав как сложную функцию правую часть выражения (6) по 8 в нуле, получим

Т, = -Т'

где = V — число записей в таблице Л,; рг — вероятность, определяемая формулой (3); 8, — математическое ожидание времени поиска/чтения одной записи г-го уровня вложенности из БД; — математическое ожидание времени сравнения и определения текущего значения функции агрегирования для г-го уровня, Тп+1 = 0.

Из выражения (8) следует, что математическое ожидание времени выполнения запроса, реализуемого в соответствии с исходным планом (см. рис. 2, а), равно

Т = Т1,

где Т1 определяется рекуррентной формулой (15).

Продифференцируем выражение (12) по 8 в нуле:

где

Уг = -Y/

Wifö) = Qi+i

) = ' Ii+1'4

~F* -

Ii+1,4  8i, i = n - 1, 1

0, i = n

Gi(8*) = Vi  8*;

_ 0, i = 1 Qi (8i) = ; _

Ii,4  8i, i = n, 2

Gi = Vi;

Ii+1,4, i = n - 1, 1

Qi+i H ;

1, i = n

8г — математическое ожидание времени чтения/записи одной записи в таблице базы данных при выполнении ¿-го запроса; ёг — математическое ожидание времени сравнения и определения текущего значения функции агрегирования для ¿-го запроса.

Выражение (18) следует из соотношений (9) и (10), а выражение (19) —из (10) и (13).

Используя (14), получим выражение для математического ожидания времени выполнения запроса, реализуемого в соответствии с планом на рис. 3:

Y = -Y'(0) = - Е Y'(°) = Е Witö) + Е G  Qi+1  й

¿+1

i=1 ¿=1 ¿=1

п—1 п—1

= Кг  8П + Е (/,+ 1, 4(8! + 81+1) + К8*) + Кг  ёП + Е К1г+мё* =

г=1 г=1

п— 1 п—1

= Кп(8П+ё П) + Е

(8, +8 г+1) + Е Кг(8* + -

4ёг )

=1 =1

При выводе формулы (20) учитывали выражения (17), (18) и (19). Если таблицы Я! и ТЕМР1+1 соединяются методом SMJ (см. рис. 3), то

в последнем слагаемом выражения (20) величину /г+1,4ёг следует за—*

менить на ёг • Формулы (16) и (20) можно использовать для сравнения математических ожиданий времени выполнения исходного запроса, реализованного в соответствии с разными планами (см. рис. 2).

Далее определен подкласс запросов, задаваемый следующими выражениями:

К = V, 8г = 8г = 8, 6 = ёг = ё г = 1 п;

/4 _

/+1,4 = , г = 2, п - 1, 1 < /4 < К, /24 = -, к

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

Полагая, что 8 » ё и Кё ^ 28, из формул (16) и (20) можно получить выражения для математических ожиданий времени реализации исходного и альтернативного планов для данного подкласса запросов:

1

п т п 1--

Т = к0'5

г=' 1 " 1

ного планов

На рис.4 построены области преимущественного использования этих планов в пространстве (к, I) (для вариантов п и к).

В случае п = 2 времена Т и У не зависят от к. Поэтому область предпочтительного использования альтернативного плана (см. рис.2,б; в форме 5О£-запросов — см. рис.3) соответствует неравенству 1 < I < Ц, при II <1 < V более целесообразно применять исходный план (см. рис. 2, а).

Рассмотрим теперь случай п > 2. Кривая А на рис.4 может быть получена из уравнения Т = У. Кривая А разделяет область (0 < к < n-2V] х [1 < I < V] на две части. Нижняя часть соответствует более предпочтительному использованию альтернативного плана (см. рис. 2, б и 3), верхняя часть — более предпочтительному использованию исходного плана (см. рис. 2, а). Для какого-либо I (см. рис. 4) к может изменяться на отрезке [ктщ, ктах]. На отрезке от точки а до точки Ь целесообразно использовать исходный план, а на отрезке от Ь до с — альтернативный план.

Построенные области преимущественного использования планов справедливы, если для соединения таблиц Я! и ТЕМР1+1 (см. рис. 3) применяется метод вложенных циклов N0. По аналогии можно построить области и для случая использования метода сортировки-слияния SMJ.

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

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

вычислять математические ожидания и моменты более высоких порядков.

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

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

1. G г a e f e G. Query evaluation techniques for large databases // ACM Computing Surveys. - N.Y., 1993. - Vol. 25, № 2. - P. 73-170.

2. Григорьев Ю. А., Плутенко А. Д. Теоретические основы анализа процессов доступа к распределенным базам данных. - Новосибирск: Наука, 2002. - 222 с.

3. Гарсиа-Молина Г., Ульман Дж., Уидом Дж. Системы баз данных. Полный курс. - М.: Издательский дом "Вильямс", 2003. - 1088 с.

4. Ш а ш а Д., Бонне Ф. Оптимизация баз данных: принципы, практика, решение проблем. - М.: КУДИЦ-ОБРАЗ, 2004. - 432 с.

5. Приоритетные системы обслуживания / Б.В. Гнеденко, Э.А. Даниелян, Б.Н. Дмитров и др. - М.: Изд-во МГУ, 1973. - 448 с.

Статья поступила в редакцию 24.01.2005

Сергей Петрович Остриков родился в 1962 г., окончил в 1984 г. Минское высшее инженерное зенитное ракетное училище ПВО. Начальник факультета военного обучения МГТУ им. Н.Э. Баумана. Автор ряда работ в области распределенных информационных систем и сетей.

S.P. Ostrikov (b. 1962) graduated from the Minsk Higher School for Antiaircraft and Rocket Engineering. The chief of military training faculty of the Bauman Moscow State Technical University. The author of a number publications in the field of the distributed information systems and networks.

Юрий Александрович Григорьев родился в 1951г., окончил в 1975г. МВТУ им. Н.Э.Баумана. Д-р техн. наук, профессор кафедры систем обработки информации и управления МГТУ им. Н.Э. Баумана. Автор более 60 работ в области распределенных систем обработки данных.

Jury Aleksandrovich Grigoriev (b.1951), graduated from the Bauman Moscow State Technical University in 1975. D.Sc (Eng), professor of faculty of systems of processing of the information and management of Bauman Moscow State Technical University. The author more than 60 works in the field of the distributed systems of data processing.