Plan Enumeration.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Plan Enumeration\n",
    "\n",
    "Copyright Immanuel Haffner, Jens Dittrich  [Big Data Analytics Group](https://bigdata.uni-saarland.de/), [CC-BY-SA](https://creativecommons.org/licenses/by-sa/4.0/legalcode)\n",
    "\n",
    "## Set-Up"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from dataclasses import dataclass\n",
    "import graphviz as gv\n",
    "import itertools\n",
    "import math\n",
    "import random as rnd\n",
    "import typing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Define a Join Graph Data Structure\n",
    "\n",
    "A join graph is a collection of named relations and joins of these relations.  The join graph implements certain sanity\n",
    "checks:  (1) No two relations must have the same name.  (2) The selectivity of a join must be in the range 0 to 1\n",
    "(inclusive).  (3)  The relations that a join refers to must be present in the join graph.\n",
    "\n",
    "This class is meant to be used as a single handle to a potentially complex join graph structure."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class JoinGraph:\n",
    "    @dataclass(eq=True, frozen=True)\n",
    "    class Relation:\n",
    "        name: str\n",
    "        size: int\n",
    "\n",
    "    @dataclass(eq=True, frozen=True)\n",
    "    class Join:\n",
    "        selectivity: float\n",
    "        relation_names: typing.Tuple\n",
    "\n",
    "    def __init__(self):\n",
    "        self.named_relations = dict()\n",
    "        self.joins = set()\n",
    "\n",
    "    def add_relation(self, name, size):\n",
    "        if name in self.named_relations:\n",
    "            raise ValueError(f'Name \"{name}\" already taken')\n",
    "        self.named_relations[name] = JoinGraph.Relation(name, size)\n",
    "\n",
    "    def add_join(self, selectivity, *relation_names):\n",
    "        # Make sure, all relations are present\n",
    "        for tn in relation_names:\n",
    "            if not tn in self.named_relations:\n",
    "                raise ValueError(f'No relation with name \"{tn}\"')\n",
    "        if not (0 <= selectivity <= 1):\n",
    "            raise ValueError(f'Illegal selectivity of {selectivity}; must be in the range 0 to 1.')\n",
    "        self.joins.add(JoinGraph.Join(selectivity, relation_names))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Let us define a concrete scenario."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create a new join graph.\n",
    "the_join_graph = JoinGraph()\n",
    "\n",
    "# Add relations to the join graph.\n",
    "the_join_graph.add_relation('A', 4000)\n",
    "the_join_graph.add_relation('B', 1000)\n",
    "the_join_graph.add_relation('C', 2000)\n",
    "the_join_graph.add_relation('D', 3000)\n",
    "\n",
    "# Add joins to the join graph.\n",
    "the_join_graph.add_join(0.025, 'A', 'B')\n",
    "the_join_graph.add_join(0.003, 'A', 'C')\n",
    "the_join_graph.add_join(0.045, 'B', 'C')\n",
    "the_join_graph.add_join(0.370, 'B', 'D')\n",
    "the_join_graph.add_join(0.012, 'C', 'D')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Define a function to draw the join graph with the graphviz tool."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def draw_join_graph(graph):\n",
    "    G = gv.Graph(name='join_graph', comment='The Join Graph')\n",
    "\n",
    "    # Find the minimum and maximum join selectivities in the join graph\n",
    "    sel_min = sel_max = 0\n",
    "    for J in graph.joins:\n",
    "        sel_min = min(sel_min, J.selectivity)\n",
    "        sel_max = max(sel_max, J.selectivity)\n",
    "\n",
    "    # Add the Relations as vertices.\n",
    "    for T in graph.named_relations.values():\n",
    "        G.node(T.name, f'<<B>{T.name}</B><SUB><FONT POINT-SIZE=\"10\">|·|={T.size:,}</FONT></SUB>>')\n",
    "\n",
    "    # Add the joins as edges with their selectivity as label.\n",
    "    for J in graph.joins:\n",
    "        vertices = J.relation_names\n",
    "        for i in range(1, len(vertices)):\n",
    "            x = 1 - (J.selectivity - sel_min) / (sel_max - sel_min)\n",
    "            penwidth = 3.5 * x**5 + 0.4 # compute the stroke width proportionally to the selectivity\n",
    "            G.attr('edge', penwidth=str(penwidth))\n",
    "            G.edge(vertices[i-1], vertices[i], label=f'{J.selectivity:f}')\n",
    "\n",
    "    return G"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Show the join graph for our scenario.\n",
    "\n",
    "**NOTE:** The join graph can be extended where there is no join between two relations.  In that case, the relations can\n",
    "be combined only with a Cartesian product, which is equivalent to a join with a selectivity of 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.47.2 (20210527.0053)\n",
       " -->\n",
       "<!-- Title: join_graph Pages: 1 -->\n",
       "<svg width=\"186pt\" height=\"305pt\"\n",
       " viewBox=\"0.00 0.00 186.05 305.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 301)\">\n",
       "<title>join_graph</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-301 182.05,-301 182.05,4 -4,4\"/>\n",
       "<!-- A -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>A</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"94.05\" cy=\"-279\" rx=\"37.09\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"73.55\" y=\"-276.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">A</text>\n",
       "<text text-anchor=\"start\" x=\"83.55\" y=\"-276.3\" font-family=\"Times,serif\" baseline-shift=\"sub\" font-size=\"10.00\">|·|=4,000</text>\n",
       "</g>\n",
       "<!-- B -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>B</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"55.05\" cy=\"-192\" rx=\"37.09\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"34.55\" y=\"-189.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">B</text>\n",
       "<text text-anchor=\"start\" x=\"44.55\" y=\"-189.3\" font-family=\"Times,serif\" baseline-shift=\"sub\" font-size=\"10.00\">|·|=1,000</text>\n",
       "</g>\n",
       "<!-- A&#45;&#45;B -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>A&#45;&#45;B</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2.87\" d=\"M76.45,-262.8C70.98,-257.14 65.48,-250.3 62.05,-243 57.27,-232.85 55.52,-220.35 54.96,-210.39\"/>\n",
       "<text text-anchor=\"middle\" x=\"88.05\" y=\"-231.8\" font-family=\"Times,serif\" font-size=\"14.00\">0.025000</text>\n",
       "</g>\n",
       "<!-- C -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>C</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"128.05\" cy=\"-105\" rx=\"37.09\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"107.55\" y=\"-102.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">C</text>\n",
       "<text text-anchor=\"start\" x=\"117.55\" y=\"-102.3\" font-family=\"Times,serif\" baseline-shift=\"sub\" font-size=\"10.00\">|·|=2,000</text>\n",
       "</g>\n",
       "<!-- A&#45;&#45;C -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>A&#45;&#45;C</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"3.76\" d=\"M105.31,-261.57C108.67,-255.92 111.99,-249.4 114.05,-243 127.34,-201.57 128.81,-149.8 128.55,-123.34\"/>\n",
       "<text text-anchor=\"middle\" x=\"152.05\" y=\"-188.3\" font-family=\"Times,serif\" font-size=\"14.00\">0.003000</text>\n",
       "</g>\n",
       "<!-- B&#45;&#45;C -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>B&#45;&#45;C</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2.23\" d=\"M53.71,-173.84C53.75,-163.47 55.41,-150.48 62.05,-141 70.53,-128.89 84.55,-120.63 97.49,-115.18\"/>\n",
       "<text text-anchor=\"middle\" x=\"88.05\" y=\"-144.8\" font-family=\"Times,serif\" font-size=\"14.00\">0.045000</text>\n",
       "</g>\n",
       "<!-- D -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>D</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"37.05\" cy=\"-18\" rx=\"37.09\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"16.55\" y=\"-15.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">D</text>\n",
       "<text text-anchor=\"start\" x=\"26.55\" y=\"-15.3\" font-family=\"Times,serif\" baseline-shift=\"sub\" font-size=\"10.00\">|·|=3,000</text>\n",
       "</g>\n",
       "<!-- B&#45;&#45;D -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>B&#45;&#45;D</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"0.4\" d=\"M47.07,-174.42C41.05,-160.92 33.29,-141.2 30.05,-123 24.66,-92.71 29.51,-56.79 33.38,-36.07\"/>\n",
       "<text text-anchor=\"middle\" x=\"56.05\" y=\"-101.3\" font-family=\"Times,serif\" font-size=\"14.00\">0.370000</text>\n",
       "</g>\n",
       "<!-- C&#45;&#45;D -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>C&#45;&#45;D</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"3.37\" d=\"M111.78,-88.8C95.32,-73.43 70,-49.78 53.48,-34.35\"/>\n",
       "<text text-anchor=\"middle\" x=\"113.05\" y=\"-57.8\" font-family=\"Times,serif\" font-size=\"14.00\">0.012000</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Graph at 0x105c376d0>"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "draw_join_graph(the_join_graph)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Computing the Cost of a Query Plan\n",
    "\n",
    "A query plan can be visualized as a tree structure.  The leaves of the tree are the input relations and the inner nodes\n",
    "are joins.  The root of the tree is the final join which yields the result.  Inner nodes, except for the root node, are\n",
    "intermediate results.\n",
    "\n",
    "We will restrict ourselves to query plans in the shape of left-deep trees.  The important property of these query plans\n",
    "is that, at any time, there is at most one intermediate result.  Since we restrict ourselves to left-deep trees, and\n",
    "hence the shape of tree is fixed, we can represent a query plan simply as a sequence of relation names.  Below we will\n",
    "visualize such a left-deep query plan.\n",
    "\n",
    "### Randomly select a query plan.\n",
    "\n",
    "This function selects a random query plan and completely ignores the presence of join predicates."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def select_query_plan_rnd(graph):\n",
    "    query_plan = [T.name for T in graph.named_relations.values()]\n",
    "    rnd.shuffle(query_plan)\n",
    "    return query_plan"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Get a randomly chosen query plan."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['C', 'B', 'D', 'A']\n"
     ]
    }
   ],
   "source": [
    "rnd.seed(42) # use a fixed seed for reproducibility\n",
    "rnd_query_plan = select_query_plan_rnd(the_join_graph)\n",
    "print(rnd_query_plan)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Define a function to draw a left-deep query plan given a sequence of relations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def draw_query_plan(plan):\n",
    "    G = gv.Graph(name='query_plan', comment='The Query Plan')\n",
    "    G.graph_attr['rankdir'] = 'BT'\n",
    "\n",
    "    # Add the Relations as leaves.\n",
    "    for tbl in plan:\n",
    "        G.node(tbl, f'<<B>{tbl}</B>>')\n",
    "\n",
    "    # Add the joins as inner nodes.\n",
    "    left = plan[0]\n",
    "    for i in range(1, len(plan)):\n",
    "        right = plan[i]\n",
    "        G.node(str(i), '⋈')\n",
    "        G.edge(left, str(i))\n",
    "        G.edge(right, str(i))\n",
    "        left = str(i)\n",
    "\n",
    "    return G"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Draw the random query plan"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.47.2 (20210527.0053)\n",
       " -->\n",
       "<!-- Title: query_plan Pages: 1 -->\n",
       "<svg width=\"206pt\" height=\"260pt\"\n",
       " viewBox=\"0.00 0.00 206.00 260.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 256)\">\n",
       "<title>query_plan</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-256 202,-256 202,4 -4,4\"/>\n",
       "<!-- C -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>C</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"22\" y=\"-15.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">C</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"63\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"63\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\">⋈</text>\n",
       "</g>\n",
       "<!-- C&#45;&#45;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>C&#45;&#45;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M35.35,-35.24C41.17,-46.54 48.89,-61.56 54.7,-72.85\"/>\n",
       "</g>\n",
       "<!-- B -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>B</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"94\" y=\"-15.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">B</text>\n",
       "</g>\n",
       "<!-- B&#45;&#45;1 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>B&#45;&#45;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M90.65,-35.24C84.83,-46.54 77.11,-61.56 71.3,-72.85\"/>\n",
       "</g>\n",
       "<!-- D -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>D</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"135\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"130\" y=\"-87.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">D</text>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"99\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">⋈</text>\n",
       "</g>\n",
       "<!-- D&#45;&#45;2 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>D&#45;&#45;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M126.65,-107.24C120.83,-118.54 113.11,-133.56 107.3,-144.85\"/>\n",
       "</g>\n",
       "<!-- A -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>A</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"171\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"166\" y=\"-159.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">A</text>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>3</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"135\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"135\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\">⋈</text>\n",
       "</g>\n",
       "<!-- A&#45;&#45;3 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>A&#45;&#45;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M162.65,-179.24C156.83,-190.54 149.11,-205.56 143.3,-216.85\"/>\n",
       "</g>\n",
       "<!-- 1&#45;&#45;2 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>1&#45;&#45;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M71.35,-107.24C77.17,-118.54 84.89,-133.56 90.7,-144.85\"/>\n",
       "</g>\n",
       "<!-- 2&#45;&#45;3 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>2&#45;&#45;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M107.35,-179.24C113.17,-190.54 120.89,-205.56 126.7,-216.85\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Graph at 0x105bf9eb0>"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "draw_query_plan(rnd_query_plan)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Defining a Cost Model\n",
    "\n",
    "First we need to define a cost function to estimate the cost of a join.  We define a cost function that estimates the\n",
    "cost of a join as the sum of the sizes of the two input relations, called `size_of_inputs`.  (This is similar the the\n",
    "cost model of the running time of a hash join, given $c_1$ and $c_2$ are 1.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "class CostFunctions:\n",
    "    # The cost of a join is equal to the sum of the size of all input relations.\n",
    "    def size_of_inputs(size_left, size_right, selectivity):\n",
    "        return size_left + size_right"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next we define a function to compute the cost of a query plan given the plan, the join graph, and a cost function.\n",
    "\n",
    "**NOTE:** The cost function (of a single join) is a parameter of the `compute_cost` function.  By using different cost\n",
    "functions we are able to compute the cost of a query plan for different cost models.  This allows us to compute the cost\n",
    "of a plan with respect to, e.g., running time, memory consumption, power consumption, etc."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def compute_cost(plan, graph, cost_fn):\n",
    "    # Start with the first relation.\n",
    "    first = plan[0]\n",
    "    joined = set([first])\n",
    "    size_left = graph.named_relations[first].size\n",
    "    cost = 0\n",
    "    # print(f'Start with relation {first} of size {size_left:,}')\n",
    "\n",
    "    # Join each relation one after the other.\n",
    "    for i in range (1, len(plan)):\n",
    "        right = plan[i]\n",
    "\n",
    "        # Combine all join predicates.  If no join predicate is applicable, the selectivity remains 1 and the join\n",
    "        # degenerates to the Cartesian product.\n",
    "        selectivity = 1\n",
    "        for J in graph.joins:\n",
    "            if right in J.relation_names and len(joined.intersection(J.relation_names)) != 0:\n",
    "                selectivity *= J.selectivity\n",
    "\n",
    "        size_right = graph.named_relations[right].size\n",
    "        # print(f'Join {joined} of size {size_left} and {right} of size {size_right} with combined selectivity {selectivity:f}.')\n",
    "        # Add the cost of this join to the total cost.\n",
    "        cost += cost_fn(size_left, size_right, selectivity)\n",
    "        # Compute the size of the new intermediate result.\n",
    "        size_left = round(selectivity * size_left * size_right)\n",
    "        #print(f'  --> Cost = {cost:,}, Size = {size_left:,}')\n",
    "        joined.add(right)\n",
    "\n",
    "    return cost"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us now compute the cost of our randomly chosen plan under the cost function `size_of_inputs`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.47.2 (20210527.0053)\n",
       " -->\n",
       "<!-- Title: query_plan Pages: 1 -->\n",
       "<svg width=\"206pt\" height=\"260pt\"\n",
       " viewBox=\"0.00 0.00 206.00 260.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 256)\">\n",
       "<title>query_plan</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-256 202,-256 202,4 -4,4\"/>\n",
       "<!-- C -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>C</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"22\" y=\"-15.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">C</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"63\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"63\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\">⋈</text>\n",
       "</g>\n",
       "<!-- C&#45;&#45;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>C&#45;&#45;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M35.35,-35.24C41.17,-46.54 48.89,-61.56 54.7,-72.85\"/>\n",
       "</g>\n",
       "<!-- B -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>B</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"94\" y=\"-15.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">B</text>\n",
       "</g>\n",
       "<!-- B&#45;&#45;1 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>B&#45;&#45;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M90.65,-35.24C84.83,-46.54 77.11,-61.56 71.3,-72.85\"/>\n",
       "</g>\n",
       "<!-- D -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>D</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"135\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"130\" y=\"-87.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">D</text>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"99\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">⋈</text>\n",
       "</g>\n",
       "<!-- D&#45;&#45;2 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>D&#45;&#45;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M126.65,-107.24C120.83,-118.54 113.11,-133.56 107.3,-144.85\"/>\n",
       "</g>\n",
       "<!-- A -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>A</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"171\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"166\" y=\"-159.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">A</text>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>3</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"135\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"135\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\">⋈</text>\n",
       "</g>\n",
       "<!-- A&#45;&#45;3 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>A&#45;&#45;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M162.65,-179.24C156.83,-190.54 149.11,-205.56 143.3,-216.85\"/>\n",
       "</g>\n",
       "<!-- 1&#45;&#45;2 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>1&#45;&#45;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M71.35,-107.24C77.17,-118.54 84.89,-133.56 90.7,-144.85\"/>\n",
       "</g>\n",
       "<!-- 2&#45;&#45;3 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>2&#45;&#45;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M107.35,-179.24C113.17,-190.54 120.89,-205.56 126.7,-216.85\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Graph at 0x105bf9970>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The estimated total cost of the query plan is 1,298,800.\n"
     ]
    }
   ],
   "source": [
    "display(draw_query_plan(rnd_query_plan)) # repeated here to be on screen\n",
    "cost = compute_cost(rnd_query_plan, the_join_graph, CostFunctions.size_of_inputs)\n",
    "print(f'The estimated total cost of the query plan is {cost:,}.')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Demonstration\n",
    "\n",
    "### Four randomly chosen query plans and their estimated costs according to the `size_of_inputs` cost function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.47.2 (20210527.0053)\n",
       " -->\n",
       "<!-- Title: query_plan Pages: 1 -->\n",
       "<svg width=\"206pt\" height=\"260pt\"\n",
       " viewBox=\"0.00 0.00 206.00 260.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 256)\">\n",
       "<title>query_plan</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-256 202,-256 202,4 -4,4\"/>\n",
       "<!-- C -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>C</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"22\" y=\"-15.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">C</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"63\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"63\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\">⋈</text>\n",
       "</g>\n",
       "<!-- C&#45;&#45;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>C&#45;&#45;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M35.35,-35.24C41.17,-46.54 48.89,-61.56 54.7,-72.85\"/>\n",
       "</g>\n",
       "<!-- B -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>B</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"94\" y=\"-15.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">B</text>\n",
       "</g>\n",
       "<!-- B&#45;&#45;1 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>B&#45;&#45;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M90.65,-35.24C84.83,-46.54 77.11,-61.56 71.3,-72.85\"/>\n",
       "</g>\n",
       "<!-- D -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>D</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"135\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"130\" y=\"-87.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">D</text>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"99\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">⋈</text>\n",
       "</g>\n",
       "<!-- D&#45;&#45;2 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>D&#45;&#45;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M126.65,-107.24C120.83,-118.54 113.11,-133.56 107.3,-144.85\"/>\n",
       "</g>\n",
       "<!-- A -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>A</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"171\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"166\" y=\"-159.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">A</text>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>3</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"135\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"135\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\">⋈</text>\n",
       "</g>\n",
       "<!-- A&#45;&#45;3 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>A&#45;&#45;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M162.65,-179.24C156.83,-190.54 149.11,-205.56 143.3,-216.85\"/>\n",
       "</g>\n",
       "<!-- 1&#45;&#45;2 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>1&#45;&#45;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M71.35,-107.24C77.17,-118.54 84.89,-133.56 90.7,-144.85\"/>\n",
       "</g>\n",
       "<!-- 2&#45;&#45;3 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>2&#45;&#45;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M107.35,-179.24C113.17,-190.54 120.89,-205.56 126.7,-216.85\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Graph at 0x105c40d00>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Estimated cost: 1,298,800\n",
      "\n",
      "\n"
     ]
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.47.2 (20210527.0053)\n",
       " -->\n",
       "<!-- Title: query_plan Pages: 1 -->\n",
       "<svg width=\"206pt\" height=\"260pt\"\n",
       " viewBox=\"0.00 0.00 206.00 260.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 256)\">\n",
       "<title>query_plan</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-256 202,-256 202,4 -4,4\"/>\n",
       "<!-- D -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>D</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"22\" y=\"-15.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">D</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"63\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"63\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\">⋈</text>\n",
       "</g>\n",
       "<!-- D&#45;&#45;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>D&#45;&#45;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M35.35,-35.24C41.17,-46.54 48.89,-61.56 54.7,-72.85\"/>\n",
       "</g>\n",
       "<!-- C -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>C</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"94\" y=\"-15.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">C</text>\n",
       "</g>\n",
       "<!-- C&#45;&#45;1 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>C&#45;&#45;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M90.65,-35.24C84.83,-46.54 77.11,-61.56 71.3,-72.85\"/>\n",
       "</g>\n",
       "<!-- A -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>A</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"135\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"130\" y=\"-87.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">A</text>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"99\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">⋈</text>\n",
       "</g>\n",
       "<!-- A&#45;&#45;2 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>A&#45;&#45;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M126.65,-107.24C120.83,-118.54 113.11,-133.56 107.3,-144.85\"/>\n",
       "</g>\n",
       "<!-- B -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>B</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"171\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"166\" y=\"-159.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">B</text>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>3</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"135\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"135\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\">⋈</text>\n",
       "</g>\n",
       "<!-- B&#45;&#45;3 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>B&#45;&#45;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M162.65,-179.24C156.83,-190.54 149.11,-205.56 143.3,-216.85\"/>\n",
       "</g>\n",
       "<!-- 1&#45;&#45;2 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>1&#45;&#45;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M71.35,-107.24C77.17,-118.54 84.89,-133.56 90.7,-144.85\"/>\n",
       "</g>\n",
       "<!-- 2&#45;&#45;3 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>2&#45;&#45;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M107.35,-179.24C113.17,-190.54 120.89,-205.56 126.7,-216.85\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Graph at 0x105bf9e80>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Estimated cost: 946,000\n",
      "\n",
      "\n"
     ]
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.47.2 (20210527.0053)\n",
       " -->\n",
       "<!-- Title: query_plan Pages: 1 -->\n",
       "<svg width=\"206pt\" height=\"260pt\"\n",
       " viewBox=\"0.00 0.00 206.00 260.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 256)\">\n",
       "<title>query_plan</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-256 202,-256 202,4 -4,4\"/>\n",
       "<!-- B -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>B</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"22\" y=\"-15.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">B</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"63\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"63\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\">⋈</text>\n",
       "</g>\n",
       "<!-- B&#45;&#45;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>B&#45;&#45;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M35.35,-35.24C41.17,-46.54 48.89,-61.56 54.7,-72.85\"/>\n",
       "</g>\n",
       "<!-- D -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>D</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"94\" y=\"-15.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">D</text>\n",
       "</g>\n",
       "<!-- D&#45;&#45;1 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>D&#45;&#45;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M90.65,-35.24C84.83,-46.54 77.11,-61.56 71.3,-72.85\"/>\n",
       "</g>\n",
       "<!-- C -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>C</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"135\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"130\" y=\"-87.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">C</text>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"99\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">⋈</text>\n",
       "</g>\n",
       "<!-- C&#45;&#45;2 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>C&#45;&#45;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M126.65,-107.24C120.83,-118.54 113.11,-133.56 107.3,-144.85\"/>\n",
       "</g>\n",
       "<!-- A -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>A</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"171\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"166\" y=\"-159.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">A</text>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>3</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"135\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"135\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\">⋈</text>\n",
       "</g>\n",
       "<!-- A&#45;&#45;3 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>A&#45;&#45;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M162.65,-179.24C156.83,-190.54 149.11,-205.56 143.3,-216.85\"/>\n",
       "</g>\n",
       "<!-- 1&#45;&#45;2 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>1&#45;&#45;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M71.35,-107.24C77.17,-118.54 84.89,-133.56 90.7,-144.85\"/>\n",
       "</g>\n",
       "<!-- 2&#45;&#45;3 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>2&#45;&#45;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M107.35,-179.24C113.17,-190.54 120.89,-205.56 126.7,-216.85\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Graph at 0x105bf9e20>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Estimated cost: 2,318,800\n",
      "\n",
      "\n"
     ]
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.47.2 (20210527.0053)\n",
       " -->\n",
       "<!-- Title: query_plan Pages: 1 -->\n",
       "<svg width=\"206pt\" height=\"260pt\"\n",
       " viewBox=\"0.00 0.00 206.00 260.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 256)\">\n",
       "<title>query_plan</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-256 202,-256 202,4 -4,4\"/>\n",
       "<!-- B -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>B</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"22\" y=\"-15.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">B</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"63\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"63\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\">⋈</text>\n",
       "</g>\n",
       "<!-- B&#45;&#45;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>B&#45;&#45;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M35.35,-35.24C41.17,-46.54 48.89,-61.56 54.7,-72.85\"/>\n",
       "</g>\n",
       "<!-- C -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>C</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"94\" y=\"-15.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">C</text>\n",
       "</g>\n",
       "<!-- C&#45;&#45;1 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>C&#45;&#45;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M90.65,-35.24C84.83,-46.54 77.11,-61.56 71.3,-72.85\"/>\n",
       "</g>\n",
       "<!-- A -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>A</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"135\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"130\" y=\"-87.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">A</text>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"99\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">⋈</text>\n",
       "</g>\n",
       "<!-- A&#45;&#45;2 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>A&#45;&#45;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M126.65,-107.24C120.83,-118.54 113.11,-133.56 107.3,-144.85\"/>\n",
       "</g>\n",
       "<!-- D -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>D</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"171\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"166\" y=\"-159.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">D</text>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>3</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"135\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"135\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\">⋈</text>\n",
       "</g>\n",
       "<!-- D&#45;&#45;3 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>D&#45;&#45;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M162.65,-179.24C156.83,-190.54 149.11,-205.56 143.3,-216.85\"/>\n",
       "</g>\n",
       "<!-- 1&#45;&#45;2 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>1&#45;&#45;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M71.35,-107.24C77.17,-118.54 84.89,-133.56 90.7,-144.85\"/>\n",
       "</g>\n",
       "<!-- 2&#45;&#45;3 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>2&#45;&#45;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M107.35,-179.24C113.17,-190.54 120.89,-205.56 126.7,-216.85\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Graph at 0x105bf97f0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Estimated cost: 127,000\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "rnd.seed(42) # fixed seed for reproducible results\n",
    "for i in range(0, 4):\n",
    "    plan = select_query_plan_rnd(the_join_graph)\n",
    "    display(draw_query_plan(plan))\n",
    "    cost = compute_cost(plan, the_join_graph, CostFunctions.size_of_inputs)\n",
    "    print(f'Estimated cost: {cost:,}\\n\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Conclusion\n",
    "\n",
    "We can observe that, although the shape of the query plan is fixed, the order in which the relations are joined already\n",
    "has a big impact on the estimated total cost of the plan.  The best plan in this demonstration with a total cost of\n",
    "`127,000` is already 7.5 times better than the second best plan with total cost `946,000` and 18 times better than the\n",
    "worst plan we randomly chose.\n",
    "\n",
    "This demonstration empirically emphasizes the need for an efficient solution to finding the cheapest plan w.r.t. the\n",
    "cost model.\n",
    "\n",
    "## Finding the Cheapest Plan by Exhaustive Plan Enumeration\n",
    "\n",
    "To find the cheapest plan for a join graph and a cost model, we can exhaustively list all possible plans and compute\n",
    "their estimated costs.  The plan with the smallest cost will be selected.\n",
    "\n",
    "**NOTE:** This solution does not fulfill the criteria of an *efficient* solution and is meant to serve as an\n",
    "introduction with educational purpose."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_cheapest_plan_exhaustive(join_graph, cost_fn):\n",
    "    # Extract the relation names\n",
    "    relations = [R.name for R in join_graph.named_relations.values()]\n",
    "\n",
    "    least_cost = math.inf\n",
    "    cheapest_plan = None\n",
    "\n",
    "    # Consider all possible permutations (of which there are $n!$).\n",
    "    for perm in itertools.permutations(relations):\n",
    "        cost = compute_cost(perm, join_graph, cost_fn)\n",
    "        if cost < least_cost:\n",
    "            least_cost = cost\n",
    "            cheapest_plan = perm\n",
    "\n",
    "    return cheapest_plan"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Find the cheapest plan for our join graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 168 µs, sys: 5 µs, total: 173 µs\n",
      "Wall time: 177 µs\n"
     ]
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.47.2 (20210527.0053)\n",
       " -->\n",
       "<!-- Title: query_plan Pages: 1 -->\n",
       "<svg width=\"206pt\" height=\"260pt\"\n",
       " viewBox=\"0.00 0.00 206.00 260.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 256)\">\n",
       "<title>query_plan</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-256 202,-256 202,4 -4,4\"/>\n",
       "<!-- A -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>A</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"22\" y=\"-15.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">A</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"63\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"63\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\">⋈</text>\n",
       "</g>\n",
       "<!-- A&#45;&#45;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>A&#45;&#45;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M35.35,-35.24C41.17,-46.54 48.89,-61.56 54.7,-72.85\"/>\n",
       "</g>\n",
       "<!-- C -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>C</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"94\" y=\"-15.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">C</text>\n",
       "</g>\n",
       "<!-- C&#45;&#45;1 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>C&#45;&#45;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M90.65,-35.24C84.83,-46.54 77.11,-61.56 71.3,-72.85\"/>\n",
       "</g>\n",
       "<!-- B -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>B</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"135\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"130\" y=\"-87.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">B</text>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"99\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">⋈</text>\n",
       "</g>\n",
       "<!-- B&#45;&#45;2 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>B&#45;&#45;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M126.65,-107.24C120.83,-118.54 113.11,-133.56 107.3,-144.85\"/>\n",
       "</g>\n",
       "<!-- D -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>D</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"171\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"166\" y=\"-159.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">D</text>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>3</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"135\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"135\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\">⋈</text>\n",
       "</g>\n",
       "<!-- D&#45;&#45;3 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>D&#45;&#45;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M162.65,-179.24C156.83,-190.54 149.11,-205.56 143.3,-216.85\"/>\n",
       "</g>\n",
       "<!-- 1&#45;&#45;2 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>1&#45;&#45;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M71.35,-107.24C77.17,-118.54 84.89,-133.56 90.7,-144.85\"/>\n",
       "</g>\n",
       "<!-- 2&#45;&#45;3 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>2&#45;&#45;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M107.35,-179.24C113.17,-190.54 120.89,-205.56 126.7,-216.85\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Graph at 0x105c36c10>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The cheapest plan is ('A', 'C', 'B', 'D') with cost 61,000.\n"
     ]
    }
   ],
   "source": [
    "%time plan = find_cheapest_plan_exhaustive(the_join_graph, CostFunctions.size_of_inputs)\n",
    "display(draw_query_plan(plan))\n",
    "cost = compute_cost(plan, the_join_graph, CostFunctions.size_of_inputs)\n",
    "print(f'The cheapest plan is {plan} with cost {cost:,}.')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### A more complex join graph.\n",
    "\n",
    "This is a join graph for the IMDb data set, extended with the cinemas relation where movies are shown."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.47.2 (20210527.0053)\n",
       " -->\n",
       "<!-- Title: join_graph Pages: 1 -->\n",
       "<svg width=\"543pt\" height=\"566pt\"\n",
       " viewBox=\"0.00 0.00 543.19 566.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 562)\">\n",
       "<title>join_graph</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-562 539.19,-562 539.19,4 -4,4\"/>\n",
       "<!-- genres -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>genres</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"373.79\" cy=\"-540\" rx=\"57.69\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"337.29\" y=\"-537.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">genres</text>\n",
       "<text text-anchor=\"start\" x=\"375.29\" y=\"-537.3\" font-family=\"Times,serif\" baseline-shift=\"sub\" font-size=\"10.00\">|·|=17,352</text>\n",
       "</g>\n",
       "<!-- directors_genres -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>directors_genres</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"310.79\" cy=\"-453\" rx=\"99.38\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"242.29\" y=\"-450.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">directors_genres</text>\n",
       "<text text-anchor=\"start\" x=\"339.29\" y=\"-450.3\" font-family=\"Times,serif\" baseline-shift=\"sub\" font-size=\"10.00\">|·|=251,255</text>\n",
       "</g>\n",
       "<!-- genres&#45;&#45;directors_genres -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>genres&#45;&#45;directors_genres</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"1.46\" d=\"M361.35,-522.21C350.37,-507.4 334.46,-485.93 323.43,-471.05\"/>\n",
       "<text text-anchor=\"middle\" x=\"371.79\" y=\"-492.8\" font-family=\"Times,serif\" font-size=\"14.00\">0.001700</text>\n",
       "</g>\n",
       "<!-- directors -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>directors</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"309.79\" cy=\"-366\" rx=\"66.89\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"266.29\" y=\"-363.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">directors</text>\n",
       "<text text-anchor=\"start\" x=\"318.29\" y=\"-363.3\" font-family=\"Times,serif\" baseline-shift=\"sub\" font-size=\"10.00\">|·|=86,881</text>\n",
       "</g>\n",
       "<!-- directors_genres&#45;&#45;directors -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>directors_genres&#45;&#45;directors</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"3.86\" d=\"M310.59,-434.8C310.42,-420.05 310.17,-398.92 310,-384.18\"/>\n",
       "<text text-anchor=\"middle\" x=\"335.79\" y=\"-405.8\" font-family=\"Times,serif\" font-size=\"14.00\">0.000020</text>\n",
       "</g>\n",
       "<!-- movie_directors -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>movie_directors</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"303.79\" cy=\"-279\" rx=\"97.48\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"236.79\" y=\"-276.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">movie_directors</text>\n",
       "<text text-anchor=\"start\" x=\"330.79\" y=\"-276.3\" font-family=\"Times,serif\" baseline-shift=\"sub\" font-size=\"10.00\">|·|=371,181</text>\n",
       "</g>\n",
       "<!-- directors&#45;&#45;movie_directors -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>directors&#45;&#45;movie_directors</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"3.46\" d=\"M308.58,-347.8C307.54,-333.05 306.05,-311.92 305.01,-297.18\"/>\n",
       "<text text-anchor=\"middle\" x=\"332.79\" y=\"-318.8\" font-family=\"Times,serif\" font-size=\"14.00\">0.000210</text>\n",
       "</g>\n",
       "<!-- movies -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>movies</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"246.79\" cy=\"-192\" rx=\"63.09\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"206.29\" y=\"-189.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">movies</text>\n",
       "<text text-anchor=\"start\" x=\"247.29\" y=\"-189.3\" font-family=\"Times,serif\" baseline-shift=\"sub\" font-size=\"10.00\">|·|=388,270</text>\n",
       "</g>\n",
       "<!-- movie_directors&#45;&#45;movies -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>movie_directors&#45;&#45;movies</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"0.41\" d=\"M292.26,-260.8C282.31,-245.95 268.01,-224.64 258.12,-209.89\"/>\n",
       "<text text-anchor=\"middle\" x=\"303.79\" y=\"-231.8\" font-family=\"Times,serif\" font-size=\"14.00\">0.005500</text>\n",
       "</g>\n",
       "<!-- movie_genres -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>movie_genres</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"446.79\" cy=\"-105\" rx=\"88.28\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"386.79\" y=\"-102.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">movie_genres</text>\n",
       "<text text-anchor=\"start\" x=\"466.79\" y=\"-102.3\" font-family=\"Times,serif\" baseline-shift=\"sub\" font-size=\"10.00\">|·|=395,120</text>\n",
       "</g>\n",
       "<!-- movies&#45;&#45;movie_genres -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>movies&#45;&#45;movie_genres</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"3.83\" d=\"M280.72,-176.58C316.72,-161.28 373.39,-137.2 410.33,-121.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"383.79\" y=\"-144.8\" font-family=\"Times,serif\" font-size=\"14.00\">0.000030</text>\n",
       "</g>\n",
       "<!-- roles -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>roles</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"59.79\" cy=\"-105\" rx=\"58.49\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"22.79\" y=\"-102.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">roles</text>\n",
       "<text text-anchor=\"start\" x=\"50.79\" y=\"-102.3\" font-family=\"Times,serif\" baseline-shift=\"sub\" font-size=\"10.00\">|·|=3,431,967</text>\n",
       "</g>\n",
       "<!-- movies&#45;&#45;roles -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>movies&#45;&#45;roles</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"3.71\" d=\"M214.65,-176.39C180.08,-160.68 125.49,-135.86 91.21,-120.28\"/>\n",
       "<text text-anchor=\"middle\" x=\"190.79\" y=\"-144.8\" font-family=\"Times,serif\" font-size=\"14.00\">0.000090</text>\n",
       "</g>\n",
       "<!-- movie_cinemas -->\n",
       "<g id=\"node9\" class=\"node\">\n",
       "<title>movie_cinemas</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"238.79\" cy=\"-105\" rx=\"102.08\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"168.29\" y=\"-102.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">movie_cinemas</text>\n",
       "<text text-anchor=\"start\" x=\"258.29\" y=\"-102.3\" font-family=\"Times,serif\" baseline-shift=\"sub\" font-size=\"10.00\">|·|=14,134,503</text>\n",
       "</g>\n",
       "<!-- movies&#45;&#45;movie_cinemas -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>movies&#45;&#45;movie_cinemas</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"3.88\" d=\"M245.18,-173.8C243.79,-159.05 241.8,-137.92 240.41,-123.18\"/>\n",
       "<text text-anchor=\"middle\" x=\"268.79\" y=\"-144.8\" font-family=\"Times,serif\" font-size=\"14.00\">0.000010</text>\n",
       "</g>\n",
       "<!-- movie_genres&#45;&#45;genres -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>movie_genres&#45;&#45;genres</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"0.4\" d=\"M443.9,-123.2C441.27,-140.33 437.79,-167.41 437.79,-191 437.79,-454 437.79,-454 437.79,-454 437.79,-482.63 414.33,-507.75 395.82,-523.12\"/>\n",
       "<text text-anchor=\"middle\" x=\"463.79\" y=\"-318.8\" font-family=\"Times,serif\" font-size=\"14.00\">0.008000</text>\n",
       "</g>\n",
       "<!-- actors -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>actors</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"59.79\" cy=\"-18\" rx=\"59.59\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"21.79\" y=\"-15.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">actors</text>\n",
       "<text text-anchor=\"start\" x=\"57.79\" y=\"-15.3\" font-family=\"Times,serif\" baseline-shift=\"sub\" font-size=\"10.00\">|·|=817,719</text>\n",
       "</g>\n",
       "<!-- roles&#45;&#45;actors -->\n",
       "<g id=\"edge10\" class=\"edge\">\n",
       "<title>roles&#45;&#45;actors</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"3.65\" d=\"M59.79,-86.8C59.79,-72.05 59.79,-50.92 59.79,-36.18\"/>\n",
       "<text text-anchor=\"middle\" x=\"85.79\" y=\"-57.8\" font-family=\"Times,serif\" font-size=\"14.00\">0.000120</text>\n",
       "</g>\n",
       "<!-- cinemas -->\n",
       "<g id=\"node10\" class=\"node\">\n",
       "<title>cinemas</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"238.79\" cy=\"-18\" rx=\"67.69\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"194.79\" y=\"-15.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">cinemas</text>\n",
       "<text text-anchor=\"start\" x=\"242.79\" y=\"-15.3\" font-family=\"Times,serif\" baseline-shift=\"sub\" font-size=\"10.00\">|·|=182,019</text>\n",
       "</g>\n",
       "<!-- movie_cinemas&#45;&#45;cinemas -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>movie_cinemas&#45;&#45;cinemas</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"3.81\" d=\"M238.79,-86.8C238.79,-72.05 238.79,-50.92 238.79,-36.18\"/>\n",
       "<text text-anchor=\"middle\" x=\"264.79\" y=\"-57.8\" font-family=\"Times,serif\" font-size=\"14.00\">0.000040</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Graph at 0x105c652b0>"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "imdb_graph = JoinGraph()\n",
    "\n",
    "imdb_graph.add_relation('genres', 17_352)\n",
    "imdb_graph.add_relation('directors_genres', 251_255)\n",
    "imdb_graph.add_relation('directors', 86_881)\n",
    "imdb_graph.add_relation('movie_directors', 371_181)\n",
    "imdb_graph.add_relation('movies', 388_270)\n",
    "imdb_graph.add_relation('movie_genres', 395_120)\n",
    "imdb_graph.add_relation('roles', 3_431_967)\n",
    "imdb_graph.add_relation('actors', 817_719)\n",
    "imdb_graph.add_relation('movie_cinemas', 14_134_503)\n",
    "imdb_graph.add_relation('cinemas', 182_019)\n",
    "\n",
    "imdb_graph.add_join(0.00170,  'genres', 'directors_genres')\n",
    "imdb_graph.add_join(0.00002, 'directors_genres', 'directors')\n",
    "imdb_graph.add_join(0.00021, 'directors', 'movie_directors')\n",
    "imdb_graph.add_join(0.00550, 'movie_directors', 'movies')\n",
    "imdb_graph.add_join(0.00003, 'movies', 'movie_genres')\n",
    "imdb_graph.add_join(0.00800, 'movie_genres', 'genres')\n",
    "imdb_graph.add_join(0.00009, 'movies', 'roles')\n",
    "imdb_graph.add_join(0.00012, 'roles', 'actors')\n",
    "imdb_graph.add_join(0.00001, 'movies', 'movie_cinemas')\n",
    "imdb_graph.add_join(0.00004, 'movie_cinemas', 'cinemas')\n",
    "\n",
    "draw_join_graph(imdb_graph)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Compute the optimal plan using exhaustive plan enumeration.\n",
    "\n",
    "This will take a while.  (On my notebook this took roughly one minute.)  The time for finding the optimal plan is\n",
    "reported using the `%time` magic."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 46.9 s, sys: 42.6 ms, total: 47 s\n",
      "Wall time: 47 s\n"
     ]
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.47.2 (20210527.0053)\n",
       " -->\n",
       "<!-- Title: query_plan Pages: 1 -->\n",
       "<svg width=\"552pt\" height=\"692pt\"\n",
       " viewBox=\"0.00 0.00 551.89 692.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 688)\">\n",
       "<title>query_plan</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-688 547.89,-688 547.89,4 -4,4\"/>\n",
       "<!-- genres -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>genres</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"35.1\" cy=\"-18\" rx=\"35.19\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"16.1\" y=\"-15.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">genres</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node11\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"98.1\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"98.1\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\">⋈</text>\n",
       "</g>\n",
       "<!-- genres&#45;&#45;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>genres&#45;&#45;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M49.08,-34.54C59.66,-46.3 74.12,-62.36 84.59,-73.99\"/>\n",
       "</g>\n",
       "<!-- directors_genres -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>directors_genres</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"162.1\" cy=\"-18\" rx=\"73.39\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"113.6\" y=\"-15.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">directors_genres</text>\n",
       "</g>\n",
       "<!-- directors_genres&#45;&#45;1 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>directors_genres&#45;&#45;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M146.6,-35.95C135.95,-47.6 121.93,-62.93 111.71,-74.11\"/>\n",
       "</g>\n",
       "<!-- directors -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>directors</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"187.1\" cy=\"-90\" rx=\"44.39\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"161.1\" y=\"-87.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">directors</text>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node12\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"142.1\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"142.1\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">⋈</text>\n",
       "</g>\n",
       "<!-- directors&#45;&#45;2 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>directors&#45;&#45;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M176.43,-107.59C169.16,-118.91 159.57,-133.82 152.37,-145.01\"/>\n",
       "</g>\n",
       "<!-- movie_genres -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>movie_genres</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"249.1\" cy=\"-162\" rx=\"62.29\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"209.1\" y=\"-159.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">movie_genres</text>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node13\" class=\"node\">\n",
       "<title>3</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"195.1\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"195.1\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\">⋈</text>\n",
       "</g>\n",
       "<!-- movie_genres&#45;&#45;3 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>movie_genres&#45;&#45;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M236.02,-179.95C227.16,-191.44 215.54,-206.5 206.94,-217.64\"/>\n",
       "</g>\n",
       "<!-- movies -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>movies</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"277.1\" cy=\"-234\" rx=\"37.09\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"256.6\" y=\"-231.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">movies</text>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node14\" class=\"node\">\n",
       "<title>4</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"236.1\" cy=\"-306\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"236.1\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\">⋈</text>\n",
       "</g>\n",
       "<!-- movies&#45;&#45;4 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>movies&#45;&#45;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M267.38,-251.59C260.75,-262.91 252.02,-277.82 245.46,-289.01\"/>\n",
       "</g>\n",
       "<!-- movie_directors -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>movie_directors</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"352.1\" cy=\"-306\" rx=\"71.49\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"305.1\" y=\"-303.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">movie_directors</text>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g id=\"node15\" class=\"node\">\n",
       "<title>5</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"294.1\" cy=\"-378\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"294.1\" y=\"-374.3\" font-family=\"Times,serif\" font-size=\"14.00\">⋈</text>\n",
       "</g>\n",
       "<!-- movie_directors&#45;&#45;5 -->\n",
       "<g id=\"edge10\" class=\"edge\">\n",
       "<title>movie_directors&#45;&#45;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M338.06,-323.95C328.54,-335.44 316.05,-350.5 306.82,-361.64\"/>\n",
       "</g>\n",
       "<!-- movie_cinemas -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>movie_cinemas</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"408.1\" cy=\"-378\" rx=\"68.79\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"363.1\" y=\"-375.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">movie_cinemas</text>\n",
       "</g>\n",
       "<!-- 6 -->\n",
       "<g id=\"node16\" class=\"node\">\n",
       "<title>6</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"351.1\" cy=\"-450\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"351.1\" y=\"-446.3\" font-family=\"Times,serif\" font-size=\"14.00\">⋈</text>\n",
       "</g>\n",
       "<!-- movie_cinemas&#45;&#45;6 -->\n",
       "<g id=\"edge12\" class=\"edge\">\n",
       "<title>movie_cinemas&#45;&#45;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M394.3,-395.95C384.94,-407.44 372.67,-422.5 363.6,-433.64\"/>\n",
       "</g>\n",
       "<!-- cinemas -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>cinemas</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"438.1\" cy=\"-450\" rx=\"41.69\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"414.1\" y=\"-447.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">cinemas</text>\n",
       "</g>\n",
       "<!-- 7 -->\n",
       "<g id=\"node17\" class=\"node\">\n",
       "<title>7</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"394.1\" cy=\"-522\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"394.1\" y=\"-518.3\" font-family=\"Times,serif\" font-size=\"14.00\">⋈</text>\n",
       "</g>\n",
       "<!-- cinemas&#45;&#45;7 -->\n",
       "<g id=\"edge14\" class=\"edge\">\n",
       "<title>cinemas&#45;&#45;7</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M427.67,-467.59C420.55,-478.91 411.18,-493.82 404.15,-505.01\"/>\n",
       "</g>\n",
       "<!-- roles -->\n",
       "<g id=\"node9\" class=\"node\">\n",
       "<title>roles</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"468.1\" cy=\"-522\" rx=\"28.7\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"454.1\" y=\"-519.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">roles</text>\n",
       "</g>\n",
       "<!-- 8 -->\n",
       "<g id=\"node18\" class=\"node\">\n",
       "<title>8</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"431.1\" cy=\"-594\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"431.1\" y=\"-590.3\" font-family=\"Times,serif\" font-size=\"14.00\">⋈</text>\n",
       "</g>\n",
       "<!-- roles&#45;&#45;8 -->\n",
       "<g id=\"edge16\" class=\"edge\">\n",
       "<title>roles&#45;&#45;8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M459.52,-539.24C453.54,-550.54 445.6,-565.56 439.63,-576.85\"/>\n",
       "</g>\n",
       "<!-- actors -->\n",
       "<g id=\"node10\" class=\"node\">\n",
       "<title>actors</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"510.1\" cy=\"-594\" rx=\"33.6\" ry=\"18\"/>\n",
       "<text text-anchor=\"start\" x=\"492.1\" y=\"-591.3\" font-family=\"Times,serif\" font-weight=\"bold\" font-size=\"14.00\">actors</text>\n",
       "</g>\n",
       "<!-- 9 -->\n",
       "<g id=\"node19\" class=\"node\">\n",
       "<title>9</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"470.1\" cy=\"-666\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"470.1\" y=\"-662.3\" font-family=\"Times,serif\" font-size=\"14.00\">⋈</text>\n",
       "</g>\n",
       "<!-- actors&#45;&#45;9 -->\n",
       "<g id=\"edge18\" class=\"edge\">\n",
       "<title>actors&#45;&#45;9</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M500.62,-611.59C494.15,-622.91 485.63,-637.82 479.23,-649.01\"/>\n",
       "</g>\n",
       "<!-- 1&#45;&#45;2 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>1&#45;&#45;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M108.08,-106.88C115.28,-118.34 124.96,-133.74 132.15,-145.18\"/>\n",
       "</g>\n",
       "<!-- 2&#45;&#45;3 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>2&#45;&#45;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M153.86,-178.54C162.64,-190.14 174.59,-205.92 183.37,-217.51\"/>\n",
       "</g>\n",
       "<!-- 3&#45;&#45;4 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>3&#45;&#45;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M204.61,-251.24C211.23,-262.54 220.03,-277.56 226.64,-288.85\"/>\n",
       "</g>\n",
       "<!-- 4&#45;&#45;5 -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>4&#45;&#45;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M248.68,-322.19C258.41,-333.93 271.81,-350.11 281.54,-361.84\"/>\n",
       "</g>\n",
       "<!-- 5&#45;&#45;6 -->\n",
       "<g id=\"edge11\" class=\"edge\">\n",
       "<title>5&#45;&#45;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M306.47,-394.19C316.03,-405.93 329.2,-422.11 338.75,-433.84\"/>\n",
       "</g>\n",
       "<!-- 6&#45;&#45;7 -->\n",
       "<g id=\"edge13\" class=\"edge\">\n",
       "<title>6&#45;&#45;7</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M360.85,-466.88C367.89,-478.34 377.35,-493.74 384.38,-505.18\"/>\n",
       "</g>\n",
       "<!-- 7&#45;&#45;8 -->\n",
       "<g id=\"edge15\" class=\"edge\">\n",
       "<title>7&#45;&#45;8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M402.68,-539.24C408.66,-550.54 416.59,-565.56 422.56,-576.85\"/>\n",
       "</g>\n",
       "<!-- 8&#45;&#45;9 -->\n",
       "<g id=\"edge17\" class=\"edge\">\n",
       "<title>8&#45;&#45;9</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M440.14,-611.24C446.44,-622.54 454.81,-637.56 461.1,-648.85\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Graph at 0x105c67280>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The cheapest plan is ('genres', 'directors_genres', 'directors', 'movie_genres', 'movies', 'movie_directors', 'movie_cinemas', 'cinemas', 'roles', 'actors') with cost 64,856,523,035,553,260.\n"
     ]
    }
   ],
   "source": [
    "%time plan = find_cheapest_plan_exhaustive(imdb_graph, CostFunctions.size_of_inputs)\n",
    "display(draw_query_plan(plan))\n",
    "cost = compute_cost(plan, imdb_graph, CostFunctions.size_of_inputs)\n",
    "print(f'The cheapest plan is {plan} with cost {cost:,}.')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Although this scenario is artificially constructed, join graphs with similar complexity are commonly found in business\n",
    "applications and are not a synthetic problem.  Waiting about one minute just to find the plan before we even start\n",
    "evaluating the query is definitely intolerable.  We must improve the query planning algorithm.\n",
    "\n",
    "## Pruning the Search Space of Plan Enumeration\n",
    "\n",
    "Usually, by defining foreign keys in the schema we already define which relations are meant to be joined.  By explicitly\n",
    "stating join predicates in the query, we also give advice which and how relations should be joined.\n",
    "\n",
    "For example, consider the relation `directors`.  As shown in the join graph, this relation can be joined with the\n",
    "relations `directors_genres` and `movie_directors`.  This means that this join produces presumably less tuples than a\n",
    "Cartesian product, assuming that the selectivity of the join predicate is less than 1.  On the contrary, there is no\n",
    "join predicate to join the `directors` and the `movies` relation; this is visible in the join graph as there is no edge\n",
    "between the two relations.  This means, to combine these two relations directly, a Cartesian product would be necessary,\n",
    "resulting in a quadratic explosion of intermediate result tuples.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.5"
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}