Об оценке коммуникационных затрат при обработке фрагментированного отношения для равномерного распределения

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

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

Рассмотрим фрагментированное отношение R . Пусть | R | = m - количество кортежей в R . Пусть отношение R разбито на k фрагментов с помощью функции фрагментации у : R ^ { 0,1, 2,..., k — 1 } . Тогда фрагмент отношения R , хранящийся на j -том узле может быть определен следующим образом:

R j = { r | r e R, ^ (r) = j } .                                 (1)

Лемма 1. Пусть на отношении R задана функция фрагментации у : R ^ { 0,1, 2,..., k — 1 } . Допустим, что существует взаимно-однозначное отображение y : R ^ { 0,1, 2,...,m — 1 } такое, что

Y (r) mod k = ^ (r), M r E R .                               (2)

Тогда размеры фрагментов R 0 , . . . , R _k будут между собой примерно равны , то есть:

Доказательство.	lim ^ R i ! = 1, V i,j €{ 0,1, 2,...,k — 1 } .                             (3) m →∞ | R j | Определим M j = { l | y - 1 (l) € R j , 0 <  l}, j = 0,1,..., k—1,                    (4)
тогда	M 1 = | R j 1 .                                            (5)
Определим	^ (l) = l mod k,                                       (6)

M j = { l | v (l) = j, 0 <  l}, j = 0,1,..., k—1.                       (7)

Покажем, что

M j = M j , V j = 0,1,...,k — 1.

Пусть сначала l ∈ Mj.                                             (8)

Тогда из (4) следует y ^{- 1} (l) € R j • Отсюда, в силу (1) получаем

V⁽Y - 1 ^(l)) = j.

Используя (2), отсюда, в свою очередь, получаем

Y (y^{- 1} (l)) mod k = j,

что эквивалентно l mod k = j. Сопоставляя это с (6), находим V (l) = j. Учитывая (7), отсюда получаем l € Mj, откуда в силу (8) следует Mj C Mj-.                                        (9) Пусть теперь l € Mj.                                          (10) Учитывая (7), отсюда получаем V- (l) = j. Сопоставляя это с (6), находим l mod k = j, что эквивалентно

γ γ ^{- 1} (l) mod k = j.

Используя (2), отсюда, в свою очередь, получаем

ϕ γ ^{- 1} (l) = j.

В силу (1), из последнего равенства следует

γ ^{- 1} (l) ∈ R j .

Тогда из (4) следует l ∈ Mj.

Учитывая (10), отсюда получаем

Mj C Mj, откуда в силу (9) следует

M j = M j .

В сочетании с (5) это дает

| M j | = | R j | , V j e{ 0,1, 2,... ,k — 1 }

Таким образом, утверждение (3) равносильно утверждению lim m→∞

M i

M j

= 1, ∀ i,j ∈ { 0, 1, 2,...,k - 1 } .

Докажем это утверждение. В силу (6) и (7) имеем

M j = { l | l mod k = j, 0 <  l} , j = 0,1,..., k—1.

Отсюда непосредственно следует ¹

[mj <  | M j | < [m]. v j _e{o,i,2,...,k — 1 } .

Тогда

Ш < _Mi гmi ■ M j

Г m 1

< pm j , V i ,j e { 0,1,2,...,k — 1 } .

Имеем

lim m →∞

mk         mk

Г m 1    m lim o _L m j     1-

Вместе с (13) это доказывает справедливость утверждения (12), а вместе с ним и утвержде- ния (3).

Определение 1. Пусть задана функция фрагментации у : R(A1,..., An) ^ {0,1, 2,... ,k—1}.

Будем говорить, что у функционально зависит от атрибута A i (0 < i <  n) , если для любых r, r Е R таких, что n A i (r) = n A i (r) , имеем у (r) = у (r).

Определение 2. Пусть имеется отношение R(. .., A,...) . Пусть D a - множество всех значений атрибута A , присутствующих в R . Обозначим через T (R, A, а) количество кортежей в отношении R , у которых атрибут A принимает значение a . Будем говорить, что значения атрибута A равномерно распределены в R , если для любых a, a Е D a имеем

T (R,A,a) = T (R, A, a).                                (14)

Лемма 2. Пусть значения атрибута А равномерно распределены в R(. .., A,...) , m = | R | кратно V (R, A) ² , а V (R, A) кратно k >  0. Тогда существует функционально зависящая от А функция фрагментации ϕ , которая обеспечивает равномерное распределение кортежей по фрагментам:

lim I R i l = 1, V i,j Е { 0,1, 2,...,k — 1 } .                             (15)

m →∞ | R _j |

Доказательство. Выполним сортировку кортежей R в порядке возрастания значений атрибута A :

R = { r o ,r i , . . . ,r m - 1 } ,                                         (16)

где п а (r i ) <  n A (r i +1 ) для всех i = 0,..., m — 2 .

Здесь п а ( г ) обозначает значение атрибута A в кортеже r . Обозначим через n(r) порядковый номер кортежа r в последовательности (16). По определению 2, для любых d, d ∈ D A имеем:

T (R,A,d) = T (R, A, d).                                (17)

Положим,

m

c = Т

Так как по условию леммы m кратно k , то c ∈ N . Определим на множестве целых неотрицательных чисел функцию

Y (i) =

c ⁱ

+ (i mod c) k,

i ∈ Z ≥ 0 .

Положим,

Y (r) = Y (n (r)), V r Е R.

Покажем, что γ является взаимно-однозначным отображением множества кортежей отношения R в множество {0, . . . ,m—1}. Так как n является взаимно-однозначным отображением множества кортежей отношения R в множество {0, . . . ,m—1}, нам достаточно показать, что ограничение y на множество {0,... ,m—1} является взаимно-однозначным отображением множества {0,... ,m—1} в себя. Сначала покажем, что

0 <  Y (i) <  m — 1, ^ i € { 0,... ,m — 1 } .

Из (19) непосредственно следует min Y (i) = 0.

0 ≤ i

Далее имеем max (y (i)) = max \i/c\ + max((n (r) mod c) k)

0 ≤ i∈R        r∈R

= ^- max n (r) J + k mc R x(n (r) mod c)

- (m — 1) + k (c — 1) = — (m — 1) + k f m — 1) c   mk k — -m

+ m — k = k — 1 + m — k = m — 1.

Таким образом, (21) имеет место.

Теперь для доказательства биективности отображения γ достаточно доказать, что су- ществует обратная функция γ что

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

Y 1 ( y (i)) = i, ^ i € { 0,... ,m — 1 } .

Положим, Y ^{- 1} (j) = j + (j mod k) c . Тогда

Y 1 ⁽Y ⁽ⁱ⁾⁾ = ^^k^J ^{+ (}Y ^{(i) mod k)} c

В силу (19) отсюда получаем

Y 1 ⁽Y ⁽ⁱ⁾⁾ = —

+ (i mod c) k k

J + ^ ( ~ + (i mod c) k) mod k ^ c.

Перегруппировав, получим

Y 1 (Y (i)) = |_“k^ + (i mod c)J + ^^—J mod k ^ c.

Из (18) следует

[U =     .

Поскольку 0 <  i < m , отсюда получаем

_c ⁱ  

откуда, в свою очередь, следует

i

0 <  c < 1. k

В силу этого (23) равносильно

Y ¹ ( y (i)) = (i mod c) +

( [”_l mod k^ c.

По определению операции mod

x mod y = x —

^x y  y.

Используя эту формулу, мы можем преобразовать (25) к виду

Y ^{1 (}Y ⁽ⁱ⁾⁾ = i -

I cl' ■( LJ Y'lY-

В силу (24) имеем

|¥ J=0

Учитывая этот факт, (26) эквивалентно

Y ^{1 (}Y ⁽ⁱ⁾⁾ = i -

c +

i

c

c,

то есть

Y ^{1 (}Y ⁽ⁱ⁾⁾ = i-

Следовательно, обратная функция для γ существует, то есть γ биективно. С учетом (21) отсюда получаем, что ограничение Y на множество { 0,... ,m — 1 } является взаимнооднозначным отображением множества { 0,... ,m — 1 } в себя. А это означает, что y является взаимно-однозначным отображением множества кортежей отношения R в множество { 0,... ,m — 1 } .

Определим

V (r) = Y (r) mod k.                                   (27)

Покажем, что v функционально зависит от A , то есть, если п а (r) = п а (r) , то V (r) = V (r) V r, r G R . Пусть

П а (r) = п а (r) .                                        (28)

По условию леммы V(R, A) кратно k, то есть существует v G N такой, что v = V (R, A) /k.

Сначала разобьем последовательность (16) на подпоследовательности

G o = ^rc , •

.

.’r ( VTmA ) -j ’ •••’G ^V < ^RA > ^{- 1} "I

r ⁽V^(R,A^)-i^)m , . . . , r m - 1

V (R,A)

}

обладающие свойствами:

• 1)    п а (r) = п а (r)   V r, r G G l ;

• 2)    п а (r) = п а (r)   V r G G i , r G G l ;

  
  

• ^{3)    |G} l | = V (R,A) ^;

  для любого и целого l G [0, V(R, A) - 1] .

  Затем разобьем последовательность (16) на следующие подпоследовательности:

  
  

  ^Q 0      ) r 0 , . . . , r ( v • m \ 1 f , . . . , ^Q k —1     ] r ^(V ( ^R , ^A ) Q^m , . . . , r m —1 ?

  (             \ V ( R,A) ) 1)                                 V ^(R,A)                     J

  
  
  
  

  обладающие свойствами:

  
  

  • 1)    V l G [0, V(R, A) — 1] 3 u G [0, k — 1] : G l C Q u ;

  • 2)    Q i = m .

  
  
  
  

  Отметим, что свойство (33) обеспечивается условием (29). Подставляя вместо v правую

  
  

  часть равенства (29) преобразуем (32) к виду:

  
  

  Q o = {r o , . . . ,r( m ) _— 1} , . . .,Q k — 1 = (r (V(R,Ak) - i) ^ m , . . .,r m — 1} •

  
  
  
  

  Более кратко это можно записать следующим образом:

  
  

  Q u = (^r m u , . . .^,r m ( u +1) —1} , ^{u G [0,k-1]} .

  
  
  
  

  Выберем r, r G R такие, что п а (r) = п а (r) . Тогда, в силу (31) имеем r, r G G i для некоторого l G [0, V(R, A) - 1] . По свойству (33), отсюда следует, что r, r G Q u для некоторого u G [0,k - 1] . Положим

  
  

  i = n^(r), j = n ^(r),                                        ⁽³⁶⁾

  
  

  тогда в силу (35) имеем

  
  

  i,j G [um; k

  
  

  m

  — ( u + 1) — 1 , 0 <  u < k. k

  
  
  
  

  Отсюда следует

  
  

  ij m/k^, m/k

  
  

  u; u + 1 —

  
  

  1 m/k

  
  

  0 <  u < k.

  
  

Так как u является целым неотрицательным числом, из предыдущего получаем ij

m/k , m/k

∈

u; u + 1— m/k

0 <  u < k.

Поскольку 0 <  m/k < 1 , то отсюда, в свою очередь, получаем

I -"j lG [u;u], 0 < u

i m/k

m/k

0 < u < k.

В силу (27) имеем

V (r) = Y (r) mod k.

Учитывая (20), это эквивалентно

V (r) = Y (n(r)) mod k.

Используя (36), преобразуем последнее равенство к виду

V (r) = Y (i) m°d k.

Учитывая (19) и (18), отсюда получаем

V ^(r) =

([ m/d⁺ (i ^m°^dm) k)

m°d k.

Второе слагаемое кратно k и по модулю k, поэтому оно будет равно нулю. Следовательно

V (r) =

[m°d k

Аналогичным образом получаем

V (r) =

j., mod k.                                 (40) m/k

С учетом (38), из (39) и (40) следует v (r) = V (r), то есть V функционально зависит от A.

Остается заметить, что функции ϕ и γ удовлетворяют условиям леммы 1, из которой следует, что lim jRl = 1, Vi,j Е {0,1, 2,...,k-1}.

m >^ \Rj |

Определение 3. Пусть имеется отношение R(A, B,...). Пусть Da = {ag, ..., av(R,A)—i} - множество всех значений атрибута A, присутствующих в R. Обозначим RA = CTA=_au (R), u Е {0, ..., V(R, A)-1}. Пусть Db = {bg, ..., bv(R,B)-i} — множество всех значений атрибута B, присутствующих в R. Будем говорить, что значения атрибута B распределены равномерно относительно атрибута A, если для любого b Е Db имеем

T (RA, B, b) = T (RA, B, b) = ... = T (rV(r,a)-i, B, b) . (41)

Теорема. Пусть имеется отношение R(A, B,...), в котором значения атрибута А распределены равномерно, а значения атрибута B, в свою очередь, распределены равномерно относительно атрибута A. Положим m = |R|. Пусть m кратно V(R, A), а V(R, A) кратно k, где k – количество фрагментов, на которое необходимо разбить R (k > 0). Тогда существует функция фрагментации ϕ, функционально зависящая от атрибута А, такая, что для любой функции пересылки ψ , функционально зависящей от атрибута B, количество пересылаемых кортежей равно (1 - 1/k)m.

Доказательство. Выберем в качестве функции фрагментации ϕ такую функцию, функционально зависящую от атрибута А, которая обеспечивает равномерное распределение кортежей по фрагментам. Такая функция существует в силу леммы 2. Обозначим через Rj j -тый фрагмент отношения R:

Rj = {r | r Е R,v (r) = j} .

Пусть Da = {ag, ..., av(R,A)-i} — множество всех значений атрибута A, присутствующих в R. Обозначим RA = ffA=_au (R), и = 0, ..., V(R, A) — 1. Так как по условию теоремы значения атрибута А распределены равномерно в R, имеем

IRAI =               (и = 0, ...,V(R,A) — 1).                     (42)

V ^(R,^A)

Поскольку функция фрагментации ϕ функционально зависит от A, то

Vu E {0, . ..,V (R, A) —1} 3j E {0, ..., k—1} : RA C Rj.

В силу того, что ϕ обеспечивает равномерное распределение кортежей по фрагментам, отсюда следует, что мы можем перенумеровать элементы множества {RA | u = 0, ..., V(R, A) — 1} таким образом, что

• ^A(з+1)-1

Rj =     U     RA       (j = 0,...,k—1).

u=

Причем

V и = v : RA П RA = 0,

V j E{0, ...,k—1} V u E{0, ..., V (R, A) —1} :   |Rj| = V RA |RA|.

Так как по условию теоремы значения атрибута B распределены равномерно относительно атрибута A, то из (41) непосредственно следует, что

• ¹    ^B=b (^RA) ¹= ^B=b (^RA) ¹= ... = ^B=b ^^RV(r,a)-1^^{1 (Vb E}DB) .

Отсюда и из (43)-(45) получаем

^B=b (Ra)l = |^B=b (R1)| = ... = |^B=b (Rk-i)| (Vb E DB) .

Пусть db = {bg, ..., bv(R,B)-i} — множество всех значений атрибута B, присутствующих в R. Так как по условию теоремы функция пересылки ψ функционально зависит от атрибута B, то существует функция ^ : db ^ {0,..., k — 1} такая, что

Vr E R : ^ (r) = ^ (r.B).

Обозначим RB = ^B=b_v(R), v = 0, ..., V(R, B) — 1. Имеем

R = U   RB,

0<v(R,B)

причем

Vv = v: RB П RB = 0.

Имеем

Vr E RB: ^ (r) = ^ (bv).

Это означает, что кортежи множества ffB=bv

(R^(b )) пересылаться не будут. Учитывая (46), заключаем, что из множества RB пересылке не подвергнутся в точности |^B=bv (Rq)| кор- тежей. Используя (48) и (49), отсюда получаем, что количество кортежей из R, которые не подвергнутся пересылке, равно

V (R,B)-1

^   |^B=bv (Ro)| = |R0| • v=0

В силу того, что ϕ обеспечивает равномерное распределение кортежей по фрагментам, имеем |Ro| = mm. Отсюда следует, что количество пересылаемых кортежей равно m-

m = (1 - Г) k V к/

m.

□

Работа выполнена при поддержке гранта РФФИ №12-07-00443-а.