ex3/main_1.tex

   1 %ex3.1
   2
   3 \begin{enumerate}[label=(\alph*)]
   4         \item\textbf{Compute the communication cost of all strategies from the slides (and listed below)}\\
   5         Query: $ \pi_{name,price}(Users \bowtie_{uid=user} Orders)$
   6
   7         Strategies:
   8         \begin{enumerate}[label=(\roman*)]
   9                 \item\textbf{Send both tables to site 4 and join there.}\\
  10                 40000 * 800 + 900000 * 30 = \underline{\textbf{59 000 000}}
  11
  12                 \item\textbf{Send Users to site 2, join there and send the result to site 4.}\\
  13                 40000 * 800 + (40000 * 900000 / 360000) * 104 = \underline{\textbf{42 400 000}}
  14
  15                 \item\textbf{Symmetrically: Send Orders to site 1, join there and send the result to site 4.}\\
  16                 900000 * 30 + (40000 * 900000 / 360000) * 104 = \underline{\textbf{37 400 000}}
  17
  18                 \item\textbf{Send only the join attributes of Users to site 2, semi join with Orders.}\\
  19                 40000 * 8 + min(40000, (40000 * 900000 / 360000)) * 30 + min(40000, (40000 * 900000 / 360000)) * 104 = \underline{\textbf{5 680 000}}
  20
  21                 \item\textbf{The semi-join strategy in the opposite direction.}\\
  22                 900000 * 8 + min(900000, (40000 * 900000 / 360000)) * 800 + min(900000, (40000 * 900000 / 360000)) * 104 = \underline{\textbf{97 600 000}}
  23         \end{enumerate}
  24
  25         \item[(a*)]\textbf{Vary the strategies above in such a way, that you always project to only the necessary
  26                 columns as early as possible.}\\
  27         Strategies:
  28         \begin{enumerate}[label=(\roman*)]
  29                 \item\textbf{Send both tables to site 4 and join there.}\\
  30                 40000 * 108 + 900000 * 12 = \underline{\textbf{15 120 000}}
  31
  32                 \item\textbf{Send Users to site 2, join there and send the result to site 4.}\\
  33                 40000 * 108 + (40000 * 900000 / 360000) * 104 = \underline{\textbf{14 720 000}}
  34
  35                 \item\textbf{Symmetrically: Send Orders to site 1, join there and send the result to site 4.}\\
  36                 900000 * 12 + (40000 * 900000 / 360000) * 104 = \underline{\textbf{21 200 000}}
  37
  38                 \item\textbf{Send only the join attributes of Users to site 2, semi join with Orders.}\\
  39                 40000 * 8 + min(40000, (40000 * 900000 / 360000)) * 12 + min(40000, (40000 * 900000 / 360000)) * 104 = \underline{\textbf{4 960 000}}
  40
  41                 \item\textbf{The semi-join strategy in the opposite direction.}\\
  42                 900000 * 8 + min(900000, (40000 * 900000 / 360000)) * 108 + min(900000, (40000 * 900000 / 360000)) * 104 = \underline{\textbf{28 400 000}}
  43         \end{enumerate}
  44
  45         \item\textbf{Now consider how to generalize the strategies of task (a*) above to situations with more
  46                 than 2 relations and the strategy with optimal communication cost for Query 2 given below}\\
  47                 Query: $ Products \bowtie_{pid=prod} \pi_{name,price,prod}(Users \bowtie_{uid=user} Orders)$
  48
  49                 Projections:
  50
  51                 Orders: user, price, prod (30 bytes) \\
  52                 Users: uid, name (108 bytes) \\
  53                 Product: everything: (2000 bytes)
  54
  55                 This means using sending only the join attributes from Users (uid) from
  56                 site 1 to Orders on site 2, joining there, and sending the semi-join
  57                 from site 2 back to site 1. \\
  58                 From here on it is handled the same way as above: \\
  59                 The next step is sending the join attributes (prod) from site 1 to site
  60                 3, where Products is joined, the result is sent back to site 1, where
  61                 the full join gets computed. \\
  62                 Site 1 (prod) to site 3: 8*100000 = \underline{\textbf{80 000}} \\
  63                 Join: 100000 * 1500 / 5000 = \underline{\textbf{30 000}} \\
  64                 Data sent back to site 1: 30000*2000 = \underline{\textbf{60 000 000}} \\
  65                 Then the completely assembled full join is sent back to site 4:\\
  66                 Data sent to site 4: 60000000 + 30000*116 = \underline{\textbf{63 480 000}}
  67 \end{enumerate}