3-nested-layouts.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "e647f9ee-c146-4fe5-b524-4451b3f8ced1",
   "metadata": {},
   "source": [
    "# Nested layouts\n",
    "\n",
    "* List, List View\n",
    "* Struct\n",
    "* Map\n",
    "* Union\n",
    "\n",
    "In nested types we introduce the concept of **parent** and **child arrays**. They express relationships between physical value arrays in a nested type structure.\n",
    "\n",
    "Nested types depend on one or more other child data types. For instance, List is a nested type (parent) that has one child (the data types of the values in the list)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5f18a33f-ade1-45fe-92c9-e4921566989c",
   "metadata": {},
   "source": [
    "## List\n",
    "\n",
    "The list type enables values of the same type being stacked together in a sequence of values in each column slot. The layout is similar to binary or string type as it has offsets buffer to define where the sequence of values starts and ends with all the values of the column being stored consecutively in a values child array.\n",
    "\n",
    "![image info](./diagrams/var-list-diagram.svg)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bf83d05a-90b2-4ce8-8bd0-cfbf05517464",
   "metadata": {},
   "outputs": [],
   "source": [
    "import nanoarrow as na\n",
    "import numpy as np\n",
    "import pyarrow as pa"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5935e2d3-4c7f-45d2-86c0-8ef3c6de266d",
   "metadata": {},
   "outputs": [],
   "source": [
    "column_1 = pa.array([[12, -7, 25], None, [0, -127, 127, 50], []],\n",
    "                    type=pa.list_(pa.int8()))\n",
    "column_1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ab05bef2-9567-4f27-ac28-effca68b245e",
   "metadata": {},
   "source": [
    "When inspecting a list type column (and all nested data in general) using pyarrow, the `buffers()` method returns all buffers - of the list array itself (validity bitmap buffer and offset buffer) and its child array (validity bitmap buffer and values buffer):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c320308d-56df-4ce8-81db-ce66d060430e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Inspecting buffers using PyArrow and buffers() method\n",
    "column_1.buffers()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "940b7c27-7f59-44d2-889a-c37d9fed2674",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Inspecting buffers using PyArrow and buffers() method and numpy\n",
    "validity_bitmap_buffer = column_1.buffers()[0]\n",
    "np.unpackbits(np.frombuffer(validity_bitmap_buffer, dtype=\"uint8\"), bitorder=\"little\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "964e5faf-597a-4e3b-b90f-4a469d0798e3",
   "metadata": {},
   "outputs": [],
   "source": [
    "offsets_buffer = column_1.buffers()[1]\n",
    "np.frombuffer(offsets_buffer, dtype=\"int32\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "66314414-46e9-4675-86f6-ac6bf04c1d4b",
   "metadata": {},
   "outputs": [],
   "source": [
    "values_validity_bitmap_buffer = column_1.buffers()[2]\n",
    "values_validity_bitmap_buffer is None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a10338fd-aaf0-4511-ad57-0a799623cd0b",
   "metadata": {},
   "outputs": [],
   "source": [
    "values_buffer = column_1.buffers()[3]\n",
    "np.frombuffer(values_buffer, dtype=\"int8\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "42f8571b-03d8-4b97-9599-0dff12622429",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Inspecting buffers using nanoarrow\n",
    "na_column1 = na.array(column_1)\n",
    "na_column1.inspect()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3a1e14a3",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "\n",
    "Create the following example column, inspect the buffers and look for the difference between this and the previous list type column:\n",
    "\n",
    "<details><summary>Hints</summary>\n",
    "\n",
    "* Do you see any offset buffers?\n",
    "* What is the length of the child array?\n",
    "\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b2008bc1",
   "metadata": {},
   "outputs": [],
   "source": [
    "column_1_example = pa.array([[12, -7, 25], None, [50, -127, 127]],\n",
    "                            type=pa.list_(pa.int8(), 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1d709aed-ab97-4316-bf9c-417736d7f980",
   "metadata": {},
   "source": [
    "### Fixed size list\n",
    "\n",
    "**Fixed size list** is a special case of variable-size list where each column slot contains a fixed size sequence meaning all lists are the same size and so the offset buffer is no longer needed.\n",
    "\n",
    "![image info](./diagrams/fixed-list-diagram.svg)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e1020668-d07b-410a-87ec-05142d8ddbd4",
   "metadata": {},
   "outputs": [],
   "source": [
    "column_2 = pa.array([[12, -7], None, [0, None]], type=pa.list_(pa.int16(), 2))\n",
    "na.array(column_2).inspect()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fae3ac47-3a11-4d58-bb1f-90c4de797310",
   "metadata": {},
   "source": [
    "### List and large list comparison\n",
    "\n",
    "In a normal list with variable or fixed size the offsets are `int32` while in the **large** list the offsets are `int64`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "04d85702-5822-4ecf-b06c-31b43270bbdf",
   "metadata": {},
   "outputs": [],
   "source": [
    "column_1 = pa.array([[12, -7, 25], None, [0, -127, 127, 50], []],\n",
    "                    type=pa.list_(pa.int8()))\n",
    "na.array(column_1).inspect()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5e6da58f-da69-4bf8-b062-31898ff77f9c",
   "metadata": {},
   "outputs": [],
   "source": [
    "column_1_large = pa.array([[12, -7, 25], None, [0, -127, 127, 50], []],\n",
    "                          type=pa.large_list(pa.int8()))\n",
    "na.array(column_1_large).inspect()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9e00e22d-e965-4cf8-9749-0b574920a198",
   "metadata": {},
   "source": [
    "### List and large list view\n",
    "\n",
    "List view type allows arrays to specify out-of-order offsets.\n",
    "\n",
    "![image info](./diagrams/var-list-view-diagram.svg)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "25aae35a-8468-46ba-b971-07fef855bc14",
   "metadata": {},
   "outputs": [],
   "source": [
    "column_3 = pa.ListViewArray.from_arrays(offsets=[4, 7, 0, 0, 3],\n",
    "                                        sizes=[3, 0, 4, 0, 2],\n",
    "                                        values=[0, -127, 127, 50, 12, -7, 25],\n",
    "                                        mask=pa.array([False, True, False, False, False]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3112f832-ce44-4a94-a140-2b602b5fa9aa",
   "metadata": {},
   "outputs": [],
   "source": [
    "column_3.buffers()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4865c628-4351-4785-9192-94a20c474d1e",
   "metadata": {},
   "outputs": [],
   "source": [
    "column_3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "22051802-669b-49bc-b0d5-663ccda2362c",
   "metadata": {},
   "outputs": [],
   "source": [
    "values_buffer = column_3.buffers()[4]\n",
    "np.frombuffer(values_buffer, dtype=\"int64\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bbfe277b-27ca-4025-98fd-c7f0d14bd9bf",
   "metadata": {},
   "source": [
    "### Struct\n",
    "\n",
    "A struct is a nested type parameterized by an ordered sequence of types.\n",
    "\n",
    "* one child array for each field\n",
    "* child arrays are independent and need not be adjacent to each other in memory (only need to have the same length)\n",
    "\n",
    "One can think of an individual struct field as a key-value pair where the key is the field name and the child array its values. The field (key) is saved in the schema and the values of a specific field (key) are saved in the child array.\n",
    "\n",
    "![image info](./diagrams/struct-diagram.svg)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6faf802d-edaa-4679-b889-ffa772cc4f41",
   "metadata": {},
   "outputs": [],
   "source": [
    "ty = pa.struct([pa.field('x', pa.string()),\n",
    "                pa.field('y', pa.int8())])\n",
    "column_4 = pa.array([{\"x\": \"joe\", \"y\": 1},\n",
    "                     {\"x\": None, \"y\": 2}, None,\n",
    "                     {\"x\": \"mark\", \"y\": 4},\n",
    "                     {\"x\": \"jane\", \"y\": None}],\n",
    "                    type=ty)\n",
    "column_4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2b5eff92-29d4-4a7a-b5d9-4b32fd5dbf60",
   "metadata": {},
   "outputs": [],
   "source": [
    "column_4.buffers()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "23de1ef2-2695-4311-b074-c2e06191f9e8",
   "metadata": {},
   "outputs": [],
   "source": [
    "na.array(column_4).inspect()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cae3a079",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "\n",
    "Create the following nested example column. How many buffers does the example have? Try to determine the number first before inspecting the buffers using pyarrow or nanoarrow.\n",
    "\n",
    "<details><summary>Hints</summary>\n",
    "\n",
    "* Struct: validity bitmap buffer and a child arrays\n",
    "* List: validity bitmap buffer, offsets buffer and one child array\n",
    "* String: validity bitmap buffer, offsets buffer and data buffer\n",
    "* Fixed size list: validity bitmap buffer and one child array\n",
    "* Uint: validity bitmap buffer and data buffer\n",
    "\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a20d106b",
   "metadata": {},
   "outputs": [],
   "source": [
    "ty = pa.struct([pa.field('x', pa.list_(pa.string())),\n",
    "                pa.field('y', pa.list_(pa.list_(pa.uint8(), 2)))])\n",
    "nested_example = pa.array([{\"x\": [\"joe\"], \"y\": [[1, 2], [2, 1]]},\n",
    "                           {\"x\": None, \"y\": [[2, 3], None]}, None,\n",
    "                           {\"x\": [\"mark\"], \"y\": [[4, None]]},\n",
    "                           {\"x\": [\"jane\", None], \"y\": None}],\n",
    "                           type=ty)\n",
    "ty"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "89334f26-9d38-489b-9de2-4a3c114e2d89",
   "metadata": {},
   "source": [
    "### Map\n",
    "\n",
    "Map type represents nested data where each value is a variable number of key-value pairs. Its physical representation is the same as a list of `{key, value}` structs.\n",
    "\n",
    "The difference between a struct and a map type is that a struct holds the key in the schema therefore needs to be a string, the values are stored in the child arrays, one for each field. There can be multiple keys and therefore multiple child arrays. The map, on the other hand, has one child array holding all the different keys (that thus all need to be of the same type but not necessarily strings) and a second child array holding all the values, those values need to be of the same type (which doesn't have to match the one on the keys).\n",
    "\n",
    "Also, the map stores the struct in a list and needs an offset as the list is variable shape.\n",
    "\n",
    "![image info](./diagrams/map-diagram.svg)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "925d4b90-0318-40de-bb8d-e9e16f3cb197",
   "metadata": {},
   "outputs": [],
   "source": [
    "column_6_data = [{'Dark Knight': 10},\n",
    "                 {'Dark Knight': 8, 'Meet the Parents': 4, 'Superman': 5},\n",
    "                 None,\n",
    "                 {'Meet the Parents': 10, 'Superman': None}]\n",
    "column_6 = pa.array(column_6_data, type=pa.map_(pa.string(), pa.int32()))\n",
    "column_6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "501aec37-6a62-4b3d-9d8b-7067d2879c5a",
   "metadata": {},
   "outputs": [],
   "source": [
    "column_6.buffers()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b18b21f1-4521-4ed9-a003-9610846b3309",
   "metadata": {},
   "outputs": [],
   "source": [
    "column_6.type"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f5d446fd-c5e7-4d0b-8fc9-b2b0413b87a7",
   "metadata": {},
   "outputs": [],
   "source": [
    "na.array(column_6).inspect()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "281a2e94-7394-45ca-a5d8-a090721d6933",
   "metadata": {},
   "source": [
    "### Comparing the conversion of struct and map to python objects\n",
    "\n",
    "Struct converts to a list of dictionaries:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7f6a31a4-3a4b-4bc5-aa25-97592d108040",
   "metadata": {},
   "outputs": [],
   "source": [
    "column_4.to_numpy(zero_copy_only=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "652acfb6-9dab-4810-ab51-eaf837e32933",
   "metadata": {},
   "outputs": [],
   "source": [
    "column_4.to_pylist()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6eba5518-2c9b-4da7-9a00-7e10fdd5fdcd",
   "metadata": {},
   "source": [
    "And map converts to a nested list of tuples by default:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "efa598d8-2c28-40a3-9a77-71ee30446a78",
   "metadata": {},
   "outputs": [],
   "source": [
    "column_6.to_numpy(zero_copy_only=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cac170fc-449d-420b-920e-e776b606a248",
   "metadata": {},
   "source": [
    "Or to dictionary with the use of `maps_as_pydicts` keyword:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4f548af3-d355-41d3-a02c-e7be7c286c82",
   "metadata": {},
   "outputs": [],
   "source": [
    "# maps_as_pydicts can be ‘lossy’ or ‘strict’\n",
    "# This can change the ordering of (key, value) pairs, and will deduplicate multiple keys, resulting in a possible loss of data.\n",
    "\n",
    "# ‘lossy’: warning printed when detected\n",
    "# ‘strict’ exception being raised when deduplicate detected\n",
    "column_6.to_pandas(zero_copy_only=False, maps_as_pydicts=\"lossy\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5a343a97-6410-418e-ab9d-93bfd4cf8d3f",
   "metadata": {},
   "outputs": [],
   "source": [
    "column_6.to_pylist()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.11.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}