PS3.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "Problem Set 3\n",
    "=======\n",
    "\n",
    "\n",
    "### Instructions / Notes:\n",
    "\n",
    "**_Read these carefully_**\n",
    "\n",
    "* **Please read all the points of the \"Notes\" sections- they're important for this PS!!!**\n",
    "* You **are not required to do any plotting in this PS- only in certain problems to provide the tuples that would generate a plot.**  You can then optionally plot (in the notebook with matplotlib, in Excel, wherever works)\n",
    "* You **may** create new IPython notebook cells to use for e.g. testing, debugging, exploring, etc.- this is encouraged in fact!- **just make sure that your final answer for each question is _in its own cell_ and _clearly indicated_**\n",
    "* **See Piazza for submission instructions**\n",
    "* _Have fun!_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "Problem 1: Double Trouble\n",
    "------------------------\n",
    "**_[25 points total]_**\n",
    "\n",
    "In this problem we'll explore an optimization often referred to as **_double buffering_**, which we'll use to speed up the **external merge sort algorithm** we saw in _Lecture 12_.\n",
    "\n",
    "Although we haven't explicitly modeled it in many of our calculations so far, recall that _sequential IO_ (i.e. involving reading from / writing to consecutive pages) is generally much faster that _random access IO_ (any reading / writing that is not sequential). Additionally, on newer memory technologies like SSD reading data can be faster than writing data (if you want to read more about SSD access patterns look [here](http://codecapsule.com/2014/02/12/coding-for-ssds-part-5-access-patterns-and-system-optimizations/). \n",
    "\n",
    "In other words, for example, if we read 8 consecutive pages from file $A$, this should be much faster than reading 1 page from $A$, then 1 page from file $B$, then the next page from $A$.\n",
    "\n",
    "**In this problem, we will begin to model this, by assuming that 8 sequential _READS_ are \"free\", i.e. the total cost of $8$ sequential reads is $1$ IO. We will also assume that the writes are always twice as expensive as a read. Sequential writes are never free, therefore the cost of $N$ writes is always $2N$.**\n",
    "\n",
    "### Other important notes:\n",
    "* **NO REPACKING:** Consider the external merge sort algorithm using the basic optimizations we present in section 1 of Lecture 12, but do not use the repacking optimization covered in Lecture 12.\n",
    "* **ONE BUFFER PAGE RESERVED FOR OUTPUT:** Assume we use one page for output in a merge, e.g. a $B$-way merge would require $B+1$ buffer pages\n",
    "* **REMEMBER TO ROUND:** Take ceilings (i.e. rounding up to nearest integer values) into account in this problem for full credit!  Note that we have sometimes omitted these (for simplicity) in lecture.\n",
    "* **Consider worst case cost:** In other words, if 2 reads _could happen_ to be sequential, but in general might not be, consider these random IO"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "### Part (a)\n",
    "\n",
    "**_[15 points]_**\n",
    "\n",
    "Consider a modification of the external merge sort algorithm where **reads are always read in 8-page chunks (i.e. 8 pages sequentially at a time)** so as to take advantage of sequential reads. Calculate the cost of performing the external merge sort for a setup having $B+1=40$ buffer pages and an unsorted input file with $320$ pages.\n",
    "\n",
    "Show the steps of your work and make sure to explain your reasoning by writing them as python comments above the final answers.\n",
    "\n",
    "#### Part (a.i)\n",
    "\n",
    "What is the **exact** IO cost of spliting and sorting the files? As is standard we want runs of size $B+1$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "io_split_sort = "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "#### Part (a.ii)\n",
    "\n",
    "After the file is split and sorted, we can merge $n$ runs into 1 using the merge process. What is largest $n$ we could have, given reads are always read in 8-page chunks? Note: this is known as the arity of the merge."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "merge_arity ="
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "#### Part (a.iii)\n",
    "\n",
    "How many passes of merging are required?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "merge_passes = "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "#### Part (a.iv)\n",
    "\n",
    "What is the IO cost of the first pass of merging? Note: the highest arity merge should always be used."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "merge_pass_1 = "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "#### Part (a.v)\n",
    "\n",
    "What is the total IO cost of running this external merge sort algorithm? **Do not forget to add in the remaining passes (if any) of merging.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "total_io ="
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "### Part (b)\n",
    "\n",
    "**_[5 points]_**\n",
    "\n",
    "Now, we'll generalize the reasoning above by writing a python function that computes the _approximate_* cost of performing this version of external merge sort for a setup having $B+1$ buffer pages, a file with $N$ pages, and where we now read in $P$-page chunks (replacing our fixed 8 page chunks in Part (a)).\n",
    "\n",
    "**Note: our approximation will be a small one- for simplicity, we'll assume that each pass of the merge phase has the same IO cost, when actually it can vary slightly... Everything else will be exact given our model!* \n",
    "\n",
    "We'll call this function `external_merge_sort_cost(B,N,P)`, and we'll compute it as the product of the cost of reading in and writing out all the data (which we do each pass), and the number of passes we'll have to do.\n",
    "\n",
    "Even though this is an approximation, **make sure to take care of floor / ceiling operations- i.e. rounding down / up to integer values properly!**\n",
    "\n",
    "**Importantly, to simplify your calculations: Your function will only be evaluated on cases where the following hold:**\n",
    "* **(B + 1) % P == 0** (i.e. the buffer size is divisible by the chunk size)\n",
    "* **N % (B + 1) == 0** (i.e. the file size is divisible by the buffer size)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "#### Part (b.i)\n",
    "\n",
    "First, let's write a python function that computes the **exact** total IO cost to create the initial runs:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "def cost_initial_runs(B, N, P):\n",
    "    # YOUR CODE HERE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "#### Part (b.ii)\n",
    "\n",
    "Next, let's write a python function that computes the _approximate_* total IO cost to read in and then write out all the data during one pass of the merge:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "def cost_per_pass(B, N, P):\n",
    "    # YOUR CODE HERE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "**Note that this is an approximation: when we read in chunks during the merge phase, the cost per pass actually varies slightly due to 'rounding issues'  when the file is split up into runs... but this is a small difference*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "#### Part (b.iii)\n",
    "\n",
    "Next, let's write a python function that computes the **exact** total number of passes we'll need to do"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "def num_passes(B, N, P):\n",
    "    # YOUR CODE HERE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "Finally, our total cost function is:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "def external_merge_sort_cost(B, N, P):\n",
    "    return cost_initial_runs(B,N,P) + cost_per_pass(B,N,P)*num_passes(B,N,P)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "### Part (c)\n",
    "\n",
    "**_[10 points]_**\n",
    "\n",
    "For $B + 1 =100$ and $N=900$, find the optimal $P$ according to your IO cost equation above.  Return both the optimal $P$ value (`P_opt`) and the list of tuples **_for feasible values of $P$_** that would generate a plot of P vs. IO cost, at resolution $=1$(every value of P), stored as `points`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# Save the optimal value here\n",
    "P =\n",
    "\n",
    "# Save a list of tuples of (P, io_cost) here, for all feasible P's\n",
    "points = "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "*Below we provide starter code for using `matplotlib` in the notebook, if you want to generate the graph of P vs. IO cost; however any other software that allows you to visualize the plot (Excel, Google spreadsheets, MATLAB, etc) is fine!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# Shell code for plotting in matplotlib\n",
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "# Plot\n",
    "plt.plot(*zip(*points))\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "Problem 2: IO Cost Models\n",
    "--------------------------------------\n",
    "\n",
    "**_[15 points total]_**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "In this problem we consider different join algorithms when joining relations $R(A,B)$,$S(B,C)$, and $T(C,D)$. We want to investigate the cost of various pairwise join plans and try to determine the best join strategy given some conditions.\n",
    "\n",
    "Specifically, for each part of this question, we are intereseted determining some (or all) of the following variables:\n",
    "\n",
    "* `P_R`: Number of pages of $R$\n",
    "* `P_S`: Number of pages of $S$\n",
    "* `P_RS`: Number of pages of output (and input) $RS$\n",
    "* `P_T`: Number of pages of $T$\n",
    "* `P_RST`: Number of pages of output (and input) $RS$\n",
    "* `B`: Number of pages in buffer\n",
    "* `IO_cost_join1`: Total IO cost of first join\n",
    "* `IO_cost_join2`: Total IO cost of second join\n",
    "\n",
    "#### Note:\n",
    "* ** The output of join1 is always feed as one of the inputs to join 2 ** \n",
    "* **Use the \"vanilla\" versions of the algorithms as presented in lecture, _i.e. without any of the optimizations we mentioned_**\n",
    "* **Again assume we use one page for output, as in lecture!**\n",
    "* ** The abbreviates for the joins used are Sort-Merge Join (SMJ), Hash Join (HJ), and Block Nested Loop Join (BNLJ). **"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "### Part (a)\n",
    "\n",
    "**_[8 points]_**\n",
    "\n",
    "Given:\n",
    "* `P_R`: 20\n",
    "* `P_S`: 200\n",
    "* `P_T`: 2000\n",
    "* `P_RS`: 100\n",
    "* `P_ST`: 1000\n",
    "* `P_RST`: 500\n",
    "* `B`: 32\n",
    "\n",
    "Compute the IO cost for the following query plans:\n",
    "\n",
    "* IO_Cost_HJ_1 where only hash join is used, $join1 = R(a,b),S(b,c)$ and $join2 = join1(a,b,c),T(c,d)$\n",
    "* IO_Cost_HJ_2 where only hash join is used, $join1 = T(c,d),S(b,c)$ and $join2 = join1(b,c,d),R(a,b)$\n",
    "* IO_Cost_SMJ_1 where only sort merge join is used, $join1 = R(a,b),S(b,c)$ and $join2 = join1(a,b,c),T(c,d)$\n",
    "* IO_Cost_SMJ_2 where only sort merge join is used, $join1 = T(c,d),S(b,c)$ and $join2 = join1(b,c,d),R(a,b)$\n",
    "* IO_Cost_BNLJ_1 where only block nested loop join is used, $join1 = R(a,b),S(b,c)$ and $join2 = join1(a,b,c),T(c,d)$\n",
    "* IO_Cost_BNLJ_2 where only block nested loop merge join is used, $join1 = T(c,d),S(b,c)$ and $join2 = join1(b,c,d),R(a,b)$\n",
    "\n",
    "**Note: again, be careful of rounding for this problem. Use ceiling/floors whenever it is necessary.**\n",
    "\n",
    "Include 1-2 sentences (as a python comment) above each answer explaining the performance for each algorithm/query plan."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "IO_Cost_HJ_1 =\n",
    "IO_Cost_HJ_2 = \n",
    "IO_Cost_SMJ_1 = \n",
    "IO_Cost_SMJ_2 =\n",
    "IO_Cost_BNLJ_1 = \n",
    "IO_Cost_BNLJ_2 = "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "### Part (b)\n",
    "\n",
    "For the query plan where $join1 = R(a,b),S(b,c)$ and $join2 = join1(a,b,c),T(c,d)$ find a configuration where using HJ for $join1$ and SMJ for $join2$ is cheaper than SMJ for $join1$ and HJ for $join2$. The output sizes you choose for P_RS and P_RS must be non-zero and feasible (e.g. the maximum output size of $join1$ is P_R*P_S). \n",
    "\n",
    "**_[8 points]_**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "P_R = \n",
    "P_S = \n",
    "P_T = \n",
    "P_RS = \n",
    "P_RST =\n",
    "B =\n",
    "\n",
    "HJ_IO_Cost_join1 = \n",
    "SMJ_IO_Cost_join2 =\n",
    "\n",
    "SMJ_IO_Cost_join1 = \n",
    "HJ_IO_Cost_join2 ="
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "Problem 3: Sequential Flooding\n",
    "-----------------------------\n",
    "\n",
    "**_[10 points total]_**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "def lru_cost(N, M, B):\n",
    "    # YOUR CODE HERE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "**Note: Before doing this question, it is highly recommended that you go through [Activity 15](./Activity-15.ipynb), which covers eviction policies for buffer managers such as LRU, and why _sequential flooding_ can sometimes occurs with LRU.**\n",
    "\n",
    "In the activity accompanying Lecture 15, we saw something called _sequential flooding_ that can occur when a default eviction policy (for example LRU) is used by the buffer manager.  We saw that we can achieve much lower IO cost by using a different eviction policy, MRU (\"most recently used\").\n",
    "\n",
    "**Note that \"Most recently used\" means most recently accessed, either from buffer or disk, consistent with what we showed in Activity-15.**\n",
    "\n",
    "For this problem, we will take a closer look at the IO cost of different eviction policies when reading the pages of a file sequentially multiple times. \n",
    "\n",
    "## Part (a)\n",
    "### Part (a.i)\n",
    "**_[1 point]_**\n",
    "\n",
    "Write a python function `lru_cost(N,M,B)` that computes the IO cost of the LRU eviction policy when reading in all the papges of an $N$-page file sequentially, $M$ times, using a bugger with $B+1$ pages.  Assume that after reading the files, you don't need to write them out (you can just release them, so there is no write IO cost)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "### Part (a.ii)\n",
    "**_[2 points]_**\n",
    "\n",
    "Write a python function `mru_cost(N,M,B)` that computes the IO cost of the MRU eviction policy when reading in all the papges of an $N$-page file sequentially, $M$ times, using a bugger with $B+1$ pages. Assume that after reading the files, you don't need to write them out (you can just release them, so there is no write IO cost)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "def mru_cost(N, M, B):\n",
    "    # YOUR CODE HERE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "### Part (a.iii)\n",
    "**_[2 points]_**\n",
    "\n",
    "Now that you have written these functions, provide the tuples which generate the plot of **M vs. the absolute value of the difference between LRU and MRU in terms of IO cost** for $B=4$, $N=7$, and $M$ between 1 and 20 inclusive (saved as the variable `p3_lru_points`)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "B = 4\n",
    "N = 7\n",
    "M = 20\n",
    "\n",
    "# Provide a list of tuple (m, difference between LRU and MRU in terms of IO cost) here:\n",
    "p3_lru_points = "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "Again, you can optionally plot your answer to check that it seems reasonable- starter code for doing this in the notebook below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# Shell code for plotting in matplotlib\n",
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "# Plot\n",
    "plt.plot(*zip(*p3_lru_points))\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "## Part (b)\n",
    "\n",
    "Recall that the LRU eviction policy removes the least recently used page when the buffer is full and a new page is referenced which is not there in buffer. The basic idea behind LRU is that you timestamp your buffer elements, and use the timestamps to decide when to evict elements. Doing so efficiently, requires some serious book-keeping, this is why in practice many buffer managers try to approximate LRU with other eviction policies that are easier to implement. \n",
    "\n",
    "Here we will focus on the _CLOCK_ or _Second Chance_ policy. In the CLOCK eviction policy, the candidate pages for removal are considered left-to-right in a circular manner(with wraparound), and a page that has been accessed between consecutive considerations will not be replaced. The page replaced is the one that - considered in a circular manner - has not been accessed since its last consideration.\n",
    "\n",
    "In more details the CLOCK policy proceeds maintains a circular list of pages in the buffer and uses an additional _clock (or second chance) bit_ for each page to track how often a page is accessed. The bit is set to 1 whenever a page is referenced. When clock needs to read in a new page in the buffer, it sweeps over existing pages in the buffer looking for one with second chance bit set to 0. It basically replaces pages that have not been referenced for one complete revolution of the clock. \n",
    "\n",
    "A high-level implementation of clock:\n",
    "1. Associate a \"second chance\" bit with each page in the buffer. Initialize all bits to ZERO (0).\n",
    "2. Each time a page is referenced in the buffer, set the \"second chance\" bit to ONE (1). this will give the page a second chance...\n",
    "3. A new page read into a buffer page has the second chance bit set to ZERO (0).\n",
    "4. When you need to find a page for removal, look in left-to-right in a circular manner(with wraparound) in the buffer pages:\n",
    "    - If the second chance bit is ONE, reset its second chance bit (to ZERO) and continue.\n",
    "    - If the second chance bit is ZERO, replace the page in the buffer.\n",
    "    \n",
    "You can find more details on CLOCK [here](http://cseweb.ucsd.edu/classes/wi08/cse221-a/papers/carr81.pdf).\n",
    "\n",
    "\n",
    "### Part (b.i)\n",
    "**_[4 points]_**\n",
    "\n",
    "Write a python function `clock_cost(N,M,B)` that computes the IO cost of the CLOCK eviction policy when reading in all the papges of an $N$-page file sequentially, $M$ times, using a bugger with $B+1$ pages.  Assume that after reading the files, you don't need to write them out (you can just release them, so there is no write IO cost)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "def clock_cost(N, M, B):\n",
    "    # YOUR CODE HERE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "### Part (b.ii)\n",
    "**_[1 point]_**\n",
    "\n",
    "Now that you have written the CLOCK cost function, provide the tuples which generate the plot of **M vs. the absolute value of the difference between LRU and CLOCK in terms of IO cost** for $B=4$, $N=7$, and $M$ between 1 and 20 inclusive (saved as the variable `p3_clock_points`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "B = 4\n",
    "N = 7\n",
    "M = 20\n",
    "p3_clock_points = "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "Does the CLOCK eviction policy prevent sequential flooding? How does it perform against LRU? Write a short explanation in the field below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# EXPLANATION GOES HERE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "Problem 4: Hash Join Madden\n",
    "-----------------------------\n",
    "\n",
    "**_[10 points total]_**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "The NFL season has started strong and Jack Del Rio ([The Oakland Raider's](https://www.youtube.com/watch?v=YXj7I1RzLSE) coach) wants to find out if Joe Flacco is an elite quarterback. He wants to do this by being more of a sabermetrics guy than a numbers guy. As a first step in doing this he wants to find out which are the colleges each NFL teams prefers drafting players from. We have access to two tables: (i) a table named \"teams\" which contains (team, player) pairs, and (ii) a table named \"colleges\" which contains (player, college) pairs. Being all excited about databases you decide that there is no other way but to join the two tables and get the desired results. However, you have no access to a database. Not even a challenge for you who decide to implement your favorite join algorithm on your own. And of course HASH JOIN is the way to go!!!\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "## Load and explore the data\n",
    "\n",
    "The two tables are stored in files which can be loaded into memory as two lists of **named tuples** using the code below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# Load data\n",
    "import nfl\n",
    "from nfl import *\n",
    "teams, colleges = loadData()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "Named tuples are basically lightweight object types and instances of named tuple instances can be referenced using object like variable deferencing or the standard tuple syntax. The following code prints the first 10 tuples from teams and colleges. *Notice how fields of named tuples are accessed inside the loops.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# Print List Entries\n",
    "print 'Table teams contains %d entries in total' % len(teams)\n",
    "print 'Table colleges contains %d entries in total' % len(colleges)\n",
    "print \n",
    "print 'First 10 entries in teams table'\n",
    "for i in range(10):\n",
    "    team = teams[i]\n",
    "    print 'Entry %d' %(i+1),':',team.teamname, '|', team.playername\n",
    "print \n",
    "print 'First 10 entries in college table'\n",
    "for i in range(10):\n",
    "    college = colleges[i]\n",
    "    print 'Entry %d' %(i+1),':',college.collegename, '|', college.playername"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "## Down to business\n",
    "\n",
    "During the lectures we saw that hash joins consist of two phases: The **Partition Phase** where using a hash function $h$ we split the two tables we want to join into $B$ buckets, and the **Matching Phase** where we iterate over each bucket and join the tuples from the two tables that match. Here you will need to implement a hash join in memory.\n",
    "\n",
    "You are determined to implement the most efficient hash join possible! This is why you decide to implement your own hash function that will uniformly partition the entries of a table across $B$ buckets so that all buckets have roughly the same number of entries. You decide to use the following hash function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# Define hash function\n",
    "def h(x,buckets):\n",
    "    rawKey = ord(x[1])\n",
    "    return rawKey % buckets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "You use this hash function to partition the tables. To do so you can use the helper method `partitionTable(table,hashfunction,buckets)` for convenience as shown next:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# Fix the number of buckets to 500\n",
    "buckets = 500\n",
    "# Partition the teams table using hash function h\n",
    "teamsPartition = partitionTable(teams,h,buckets)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "The output of `partitionTable()` is a dictionary with its keys corresponding to bucket numbers in $[0,B-1]$ and its entries to lists of named tuples.\n",
    "\n",
    "## Part (a)\n",
    "### Part (a.i)\n",
    "**_[4 points]_**\n",
    "\n",
    "It's now time to implement your own hash join! You only need to implement the merge phase of the hash join. The output of the method should correspond to the result of a join between teams and colleges over the ***playername*** attribute. The partition phase is implemented. You need to fill in the merge phase.\n",
    "\n",
    "***Note: You should only use the two dictionaries t1Partition and t1Partition provide. No other data structures are allowed.***"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "def hashJoin(table1, table2, hashfunction,buckets):\n",
    "    # Parition phase \n",
    "    t1Partition = partitionTable(table1,hashfunction,buckets)\n",
    "    t2Partition = partitionTable(table2,hashfunction,buckets)\n",
    "    # Merge phase\n",
    "    result = []\n",
    "    \n",
    "    # ANSWER GOES HERE\n",
    "    \n",
    "    # To populate your output you should use the following code(t1Entry and t2Entry are possible var names for tuples)\n",
    "    # result.append((t1Entry.teamname, t1Entry.playername, t2Entry.collegename))\n",
    "    return result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "### Part (a.ii)\n",
    "**_[1 point]_**\n",
    "\n",
    "It time to evaluate your algorithm! The code provided below executes the join between teams and colleges and measures the total execution time. \n",
    "What is the total number of entries output by your algorithm?\n",
    "\n",
    "Does the runtime of your algorithm seem reasonable? Provide a brief explanation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "import time\n",
    "start_time = time.time()\n",
    "res1 = hashJoin(teams, colleges, h, buckets)\n",
    "end_time = time.time()\n",
    "duration = (end_time - start_time)*1000 #in ms\n",
    "print 'The join took %0.2f ms and returned %d tuples in total' % (duration,len(res1))\n",
    "\n",
    "# EXPLANATION GOES HERE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "## Part (b)\n",
    "\n",
    "You decide to investigate the performance of `hashJoin( )` further. Since you implemented the merge phase of  `hashJoin( )` yourself you focus on the partitioning obtained by using the provided hash function `h( )`. \n",
    "In the lectures we saw that a good hash function should partition entries uniformly across buckets. We will now check if `h( )` is indeed a good function.\n",
    "\n",
    "The following code generates a histogram of the bucket sizes for table teams (using the above hash function `h` and 500 buckets) to help figure out what is going wrong. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# Examine if this is a good partition function\n",
    "def histogramPoints(partition):\n",
    "    ids = range(buckets)\n",
    "    items = []\n",
    "    for i in range(buckets):\n",
    "        if i in partition:\n",
    "            items.append(len(partition[i]))\n",
    "        else:\n",
    "            items.append(0)\n",
    "    return ids, items\n",
    "\n",
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "# Plot bucket histogram\n",
    "buckets = 500\n",
    "teamsPartition = partitionTable(teams,h,buckets)\n",
    "ids, counts = histogramPoints(teamsPartition)\n",
    "plt.plot(ids, counts)\n",
    "plt.plot()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "#### Part (b.i)\n",
    "**_[3 points]_**\n",
    "\n",
    "\n",
    "Now find the skew associated with the above histogram. Skew is defined as the standard deviation of the number of entries in the buckets. A uniform hash function produces buckets of equal size, leading to 0 skew, but our candidate hash function h is imperfect so you should observe a positive skew."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# ANSWER\n",
    "# partition- a table partition as returned by method partitionTable\n",
    "# return value - a float representing the skew of hash function (i.e. stdev of chefs assigned to each restaurant)\n",
    "def calculateSkew(partition):\n",
    "    # ANSWER STARTS HERE\n",
    "    skew = \n",
    "    # ANSWER ENDS HERE\n",
    "    return skew\n",
    "\n",
    "print calculateSkew(teamsPartition)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "#### Part (b.ii)\n",
    "\n",
    "**_[1 point]_**\n",
    "\n",
    "Use python's hash function to see if you can produce a better (aka smaller) runtime for hash join. As at the beginning of part b, make a histogram of the bucket sizes (this time using the new hash function and 500 buckets). You can plot your histogram using the same code provided above."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# Design a better hash function and print the skew difference for \n",
    "def hBetter(x,buckets):\n",
    "    rawKey = #ANSWER GOES HERE\n",
    "    return rawKey % buckets\n",
    "\n",
    "# Plot bucket histogram\n",
    "buckets = 500\n",
    "teamsPartition = partitionTable(teams,hBetter,buckets)\n",
    "ids, counts = histogramPoints(teamsPartition)\n",
    "plt.plot(ids, counts)\n",
    "plt.plot()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "#### Part (b.iii)\n",
    "\n",
    "**_[1 point]_**\n",
    "\n",
    "Rerun your hash join algorithm with the new hash function you designed and 500 buckets.\n",
    "Does the algorithm run faster? If so what is the speed-up you are observing?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "start_time = time.time()\n",
    "\n",
    "res1 = # ENTER CODE HERE\n",
    "\n",
    "end_time = time.time()\n",
    "duration = (end_time - start_time)*1000 #in ms\n",
    "print 'The join took %0.2f ms and returned %d tuples in total' % (duration,len(res1))\n",
    "\n",
    "# WRITE DOWN THE SPEED UP"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "## Part (c)\n",
    "**_[0 points]_**\n",
    "\n",
    "For our internal sabermetrics purposes. Is Joe Flacco an elite quarterback? (True for elite, False for not elite)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "flacco_elite = "
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}