ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
39
Для ПЛС времени выполнения запроса на одном процессоре кла-
стера (или машины) имеем:
1 1 1 1
( )
( ( , , ) ( , )),
s G s r m s z
ϕ
χ
=
Ψ
( ,
( )
( )
( ),
w
w
T
M N
z
P s
s
s
ν
ν
π
ϕ
ϕ
⋅
⋅
= Ω Ψ ⋅
(2)
( , ) 1 (1 ),
P z
P z
Ω = − −
где
G
=
z
V/n
—
производящая функция (ПФ) числа позиций (записей)
таблицы (отношения)
R
,
обрабатываемых на одном процессоре;
V
—
общее число записей в таблице
R
;
n
—
число процессоров в кластере
(
или в машине).
При хорошей хеш-функции таблица равномерно фрагментирует-
ся по ключевому (уникальному) атрибуту с точностью до 0,5 %.
Функция
ψ
1
(
s
,
z
)
учитывает, что читаются кортежи колонок по по-
зициям, которые удовлетворяют условиям поиска по предыдущим ат-
рибутам. Эта функция рекуррентно определяется следующим образом:
(
)
1
1 2 2 2 2
( , )
, ( , ,
) ( , ) ,
f
s z
P s r m s z
χ
Ψ = Ω
Ψ
(3)
...
(
)
1
1 1 ( 1)
( , )
,
( ,
,
)
( , ) ,
i
fi
i
i
i
i
s z
P s r m
s z
χ
+
+ +
+
Ψ = Ω
Ψ
...
(
)
( , )
,
( ) ) ,
u
b
fb P
s z
P s z
ϕ
Ψ = Ω
b
= |
K
F
| — мощность подмножества атрибутов отношения, по кото-
рым происходит фильтрация кортежей по условию
|
|
1
;
F
K
i
i
f
=
∩
1
( )
( ,1, );
F
F
K K
j
j K
s
s m
π
π
χ
+
= +
Ψ =
∏
( , , )
( )
( ) ( );
i
m
r
i
Di
P
M
s r m s
s
s
ν
χ
ϕ
ϕ
ϕ
=
( )
Di
s
ϕ
—
ПЛС времени чтения кортежа
i
-
го столбца с диска;
( )
i
m
M
s
ν
ϕ
—
ПЛС
времени сохранения атрибута в ОП и его чтения в кэш процессора;
ν
i
—
размер атрибута;
m
ν
i
—
число операций чтения/записи в оператив-
ную память, необходимых для проверки условия по соответствующему
атрибуту (для
i
-
го столбца вводится аргумент
m
i
—
см. (2) и (3)).
Считается, что кэш процессора — это «черная дыра», в которой
сохраняются данные процессора, необходимые для вычислений. Из
кэша в ОП перемещаются только результирующие материализован-
ные записи, передаваемые по шине (см. далее
ϕ
N
(
s
))
процессору, где
выполняется сборка.