hw4_part3.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "2Sl1sQcJFath"
      },
      "source": [
        "# Homework 4\n",
        "\n",
        "* **Remember: homeworks are to be completed individually**\n",
        "\n",
        "In this part of the problem set, you will examine query plans that PostgreSQL uses to execute queries, and try to understand\n",
        "why it produces the plan it does for a certain query. The data set you will use has the same schema as the `iowa` dataset in HW3."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Gqv1_5w6Fatl"
      },
      "source": [
        "**NOTE: The iowa table is fairly large with lots of rows, so please try not to run too many generic queries like “SELECT * FROM iowa”. They take a long time to execute, and slow down the database for everyone else. Please see Jupyter notification for shutting down queries.**   \n",
        "\n",
        "**EXPLAINs are fine since they don't actually execute the queries. When running a query, always use LIMIT clauses and/or selection filters to reduce the number of rows produced.**"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "lQW61DGuFatm"
      },
      "source": [
        "### Jupyter Notes: _Read these carefully_\n",
        "\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 you run the final cell to submit your results**\n",
        "  * you can press shift+enter to execute to code in the cell that your cursor is in.\n",
        "* When you see `In [*]:` to the left of the cell you are executing, this means that the code / query is _running_. Please wait for the execution to complete\n",
        "    * **If the cell is hanging- i.e. running for too long: you can restart the kernel**\n",
        "    * To restart kernel using the menu bar: \"Kernel >> Restart >> Clear all outputs & restart\"), then re-execute cells from the top\n",
        "* _Have fun!_"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Additional query plan visualizers you may be interested in(unrelated to the assignment, and for your own information):\n",
        "- BigQuery: https://cloud.google.com/spanner/docs/tune-query-with-visualizer\n",
        "- Umbra: https://umbra.db.in.tum.de/interface/\n",
        "- DuckDB: https://duckdb.org/docs/guides/meta/explain\n",
        "- SQLite: https://www.sqlite.org/eqp.html"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GJjygAuSFatp"
      },
      "source": [
        "### Before Starting\n",
        "**Please run the following cells to allow COMPLETE output for EXPLAIN query, and connect to db**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "GK62IX4tF0kS",
        "outputId": "14b96df0-3af5-4dd2-872b-ba144d91153e"
      },
      "outputs": [],
      "source": [
        "!pip3 install sqlalchemy # ORM for databases\n",
        "!pip3 install ipython-sql # SQL magic function"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "6TyrAW5uF2lS"
      },
      "outputs": [],
      "source": [
        "%load_ext sql"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 91
        },
        "id": "CzK05PqjFats",
        "outputId": "e9ed717a-f4a8-44ba-d390-dd34505b289c"
      },
      "outputs": [],
      "source": [
        "%sql postgresql://student:w4111student@w4111.cisxo09blonu.us-east-1.rds.amazonaws.com/w4111"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "zO-uTJKmFatv"
      },
      "source": [
        "In Part III, we have provided you with the following indexes:\n",
        "\n",
        "    Indexes:\n",
        "      \"iowa_cat_btree\" btree (category)\n",
        "      \"iowa_date\" btree (date)\n",
        "      \"iowa_dt_store_item_vendor_tree\" btree (date, store, item, vendor)\n",
        "      \"iowa_store_hash\" hash (store)\n",
        "      \"iowa_store_item_vendor_dt_tree\" btree (store, item, vendor, date)\n",
        "      \"iowa_store_tree\" btree (store)\n",
        "      \"iowa_vendor_hash\" hash (vendor)\n",
        "      \"iowa_vendor_tree\" btree (vendor)\n",
        "      \"iowa_zip_hash\" hash (zipcode)\n",
        "      \"iowa_zip_tree\" btree (zipcode)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "wAWH_NSVIM3e"
      },
      "source": [
        "You can view the indexes of iowa using the following commands:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 290
        },
        "id": "Pr4SN7q9GLdS",
        "outputId": "691c427d-32b6-4d40-8a7f-e9704db6cb50"
      },
      "outputs": [],
      "source": [
        "%%sql\n",
        "select *\n",
        "from pg_indexes\n",
        "where schemaname='public' and tablename='iowa';"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "TZwEY6cgFatw"
      },
      "source": [
        "### A Quick Example\n",
        "\n",
        "To understand what query plan is being used, PostgreSQL includes the `EXPLAIN` command. \n",
        "\n",
        "It prints the plan for a query, including all of the physical operators and access methods being used. \n",
        "For example, the following SQL command displays the query plan for the SELECT:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 162
        },
        "id": "AwyuNBVqFaty",
        "outputId": "77c181a4-87f4-4263-f414-2de3e2210438"
      },
      "outputs": [],
      "source": [
        "%%sql \n",
        "EXPLAIN SELECT * FROM iowa WHERE vendor_no = 0;"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "eeaZpm56Fatz"
      },
      "source": [
        "For example, this is a query plan with no branches. It first runs a Bitmap Index Scan using the index iowa_vendor_tree, which is a Btree index, and the condition vendor_no = 0.  It _estimates_ that there would be 925 rows that match the condition.   \n",
        "\n",
        "The results are then fed into a Bitmap Heap Scan, which gathers all the tuple ids from the index scan together, sorts the tuple ids by the pages the tuples are stored in, and reads the data pages as a single scan while rechecking the vendor condition.\n",
        "\n",
        "Don't worry about the heap scan too much. We mainly care that the query uses the iowa_vendor_tree index. You should also keep in mind that leaves of the BTree index do not store actual tuples (i.e. it is a secondary index, not a primary index).\n",
        "\n",
        "For more details of how to interpret the result, please check https://www.postgresql.org/docs/current/using-explain.html."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ke2RuMfvFatz"
      },
      "source": [
        "**HINT: In some questions it is necessary to provide with some selectivity of information, so you may want to use COUNT function to write some queries from time to time.**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 97
        },
        "id": "FVwCPm7NFat0",
        "outputId": "04930da0-951b-4cd2-a2d3-2c2c126568be"
      },
      "outputs": [],
      "source": [
        "%%sql\n",
        "SELECT COUNT(*) FROM iowa;"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "h9KsSfkpFat0"
      },
      "source": [
        "### Part III\n",
        "\n",
        "**Q1**: Run `EXPLAIN` on the following query and explain in your own words (in a few sentences) the query plan that PostgreSQL picked (we are expecting something similar to the given example above)."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 162
        },
        "id": "b5BR8Ik0Fat1",
        "outputId": "e3e06800-e6b3-4a4e-99eb-12065835d590"
      },
      "outputs": [],
      "source": [
        "%%sql\n",
        "EXPLAIN SELECT * FROM iowa WHERE zipcode = '10027';"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "VIT2XcDpFat3"
      },
      "outputs": [],
      "source": [
        "## please answer between the quotes\n",
        "a1=\"\"\"\n",
        "\n",
        "\"\"\""
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "L7BqPzkUFat3"
      },
      "source": [
        "**Q2**: What did PostgreSQL estimate the number of resulting rows to be and what is the actual number of rows?  \n",
        "   \n",
        "Why is there a difference?\n",
        "_Hint_: Think about how optimizer performs evaluation."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 97
        },
        "id": "c-LSjj-VFat5",
        "outputId": "bd8d215d-9f2f-47cd-c646-9f741f132988"
      },
      "outputs": [],
      "source": [
        "%%sql\n",
        "-- run this query to get actual number returned\n",
        "SELECT COUNT(*) FROM iowa WHERE zipcode = '10027';"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "Y2c9-McBFat7"
      },
      "outputs": [],
      "source": [
        "## please answer between the quotes\n",
        "a2=\"\"\"\n",
        "\n",
        "\"\"\""
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "hqOpqOGuFat7"
      },
      "source": [
        "**Q3**: Run `EXPLAIN` on the slightly different query below.  What index does the query use and why is\n",
        "   it the same or different than the result of Q1?\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 140
        },
        "id": "OerfypAoFat8",
        "outputId": "d90ed1f2-3da3-4dd8-f893-c79d6f8ff0f3"
      },
      "outputs": [],
      "source": [
        "%%sql\n",
        "EXPLAIN SELECT * FROM iowa WHERE zipcode = '10027' LIMIT 1;"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "SklPleZ_Fat9"
      },
      "outputs": [],
      "source": [
        "## please answer between the quotes\n",
        "a3=\"\"\"\n",
        "\n",
        "\"\"\""
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "NINgWAsHFat9"
      },
      "source": [
        "**Q4**: Run `EXPLAIN` on the following slightly different queries.  Why does the database choose those plans? What are the main reasons for different plans?\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 119
        },
        "id": "XPXBiQkfFat9",
        "outputId": "698f3909-d5a1-486a-ad86-1bbc22345a71"
      },
      "outputs": [],
      "source": [
        "%%sql \n",
        "-- Q4A\n",
        "EXPLAIN SELECT * FROM iowa WHERE '50056' < zipcode AND zipcode < '50058';"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 119
        },
        "id": "9ecUBZ7yFat-",
        "outputId": "f83505d5-dd0e-49c2-ebb0-2ee786e5bca7"
      },
      "outputs": [],
      "source": [
        "%%sql\n",
        "-- Q4B\n",
        "EXPLAIN SELECT * FROM iowa WHERE '50056' < zipcode AND zipcode < '52726';"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "29z3fUsUFat-"
      },
      "outputs": [],
      "source": [
        "## please answer between the quotes\n",
        "a4=\"\"\"\n",
        "\n",
        "\"\"\""
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "npffRssUFat_"
      },
      "source": [
        "**Q5**: Try the following two EXPLAIN queries (Q5A, Q5B). Why do they have equivalent query plans despite the fact that Q5B has an equality condition?\n",
        "_Hint_: Think from selectivity and cost statistics yield by `EXPLAIN` query in Q4 and Q5."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 162
        },
        "id": "dEvjiIMuFat_",
        "outputId": "d5edc73a-7245-4bba-dddc-07690eabee86"
      },
      "outputs": [],
      "source": [
        "%%sql\n",
        "--Q5A\n",
        "EXPLAIN SELECT * FROM iowa WHERE 4500 < store AND store < 8000;"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 162
        },
        "id": "g2_LFBabFauA",
        "outputId": "55188ab4-7408-4f0f-d8d2-83a4870560b0"
      },
      "outputs": [],
      "source": [
        "%%sql \n",
        "--Q5B\n",
        "EXPLAIN SELECT * FROM iowa WHERE store = 2633;"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "5fmdI1yHFauB"
      },
      "outputs": [],
      "source": [
        "## please answer between the quotes\n",
        "a5=\"\"\"\n",
        "\n",
        "\"\"\""
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "6IoEMD0SFauB"
      },
      "source": [
        "**Q6**: Consider if we inserted a large batch of new records into the table.  What is the difference in the amount of time it takes change if the table did not contain any indexes, and if the table did contain the indexes?"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "M0FMWeVwFauC"
      },
      "outputs": [],
      "source": [
        "## please answer between the quotes...\n",
        "a6=\"\"\"\n",
        "\n",
        "\"\"\""
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "BFKrYfntFauD"
      },
      "source": [
        "## Part III Submission\n",
        "\n",
        "To submit your answers, please go to Gradescope -> HW4. Copy and paste your answers into the part3 submissions."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "No73ZhbkFauE",
        "outputId": "33fa3203-da6b-4745-a135-811175734fb2"
      },
      "outputs": [],
      "source": [
        "result = {\n",
        "    \"a1\":a1,\n",
        "    \"a2\":a2,\n",
        "    \"a3\":a3,\n",
        "    \"a4\":a4,\n",
        "    \"a5\":a5,\n",
        "    \"a6\":a6,\n",
        "}\n",
        "\n",
        "for key in result:\n",
        "  print(key + \":\", result[key])"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "name": "hw4_part2.ipynb",
      "provenance": []
    },
    "kernelspec": {
      "display_name": "Python 3.7.3 ('base')",
      "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.7.3"
    },
    "vscode": {
      "interpreter": {
        "hash": "ad2bdc8ecc057115af97d19610ffacc2b4e99fae6737bb82f5d7fb13d2f2c186"
      }
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}