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 \end{enumerate}