Ю.А. Григорьев, Е.Ю. Ермаков
8
( , ) 1 (1 );
P z
P z
(1)
G
(
z
)=
z
Vk/n
(2)
— производящая функция (ПФ) числа позиций (записей) таблицы
(отношения)
k
-го измерения, обрабатываемых на одном процессоре,
где
V
k
— общее число записей в таблице
k
-го измерения;
n
— число
процессоров в кластере (или в машине);
χ ( , , ) φ ( )φ ( )φ ( )
i
i
m
r
i
D M P
s r m s
s
s
(3)
— ПЛС времени обработки в ресурсах, где
φ ( )
i
D
s
— ПЛС вре-
мени чтения кортежа
i
-го столбца с диска для
k
-го измерения;
( )
i
m
M
s
—ПЛС времени сохранения атрибута в оперативной памяти (ОП) и
его чтения в кэш процессора;
i
– размер атрибута;
m
i
— число опе-
раций чтения/записи в оперативную память, необходимых для про-
верки условия по соответствующему атрибуту
*
;
φ ( )
r
P
s –
ПЛС времени
обработки кортежа столбца в процессоре;
r
— число логических опе-
раций, необходимых для проверки условия по соответствующему ат-
рибуту.
Функция
(
s
,
z
) учитывает, что для
k
-й таблицы измерений читают-
ся кортежи колонок по позициям, удовлетворяющим условиям поиска
по предыдущим атрибутам (процесс поздней материализации, см.
[12, 18]). Эта функция рекуррентно определяется следующим образом:
1 1 1 1
( , )
(1, χ ( , ,
) ( , ));
s z
s r m s z
1
2 2 2 2
1
( , )
(
, χ ( , ,
) ( , ));
s z
P s r m s z
f
,
(4)
1
1 1 ( 1)
( , )
( , χ ( ,
,
)
( , ));
i
i
i
i
s z
P
s r m
s z
i
fi
( , )
( , φ ( ) )),
P
u
s z
P s z
b
fb
где
b
= |
K
FRk
| — мощность подмножества атрибутов отношения, по ко-
торым происходит фильтрация кортежей по условию
|
|
1
FRk
K
i
i
f
для
k
-го
измерения;
*
Будем считать, что кэш процессора — это черная дыра, в которой сохраня-
ются данные процессора, необходимые для вычислений. Из кэша в ОП перемеща-
ются только результирующие материализованные записи, передаваемые по шине
(см. далее
N
(
s
)) процессору, где выполняется сборка.
