31:T1165,## GeoArrow memory layout The low-level decisions of how to store coordinates are crucially important to how efficient a memory format can be. > _(This section gets into some gory technical details. Feel free to skip below!)_ Arrow memory, by design, is both zero-copy and has constant-time access. The zero-copy part implies that multiple threads or processes can read the same data without a copy (though this is harder to use in a browser environment). Through use of a smart data layout, the access to any cell of an Arrow table is always possible in constant time. This means that there's no _parsing_ that needs to happen, even for nested data types, to access a value. ### Arrow-native geometry format GeoArrow is able to build upon Arrow's strengths so that geometry coordinates can be accessed with no copy and in constant time. The current version of the specification [defines](https://github.com/geopandas/geo-arrow-spec/blob/f2eb98e7e2f60ed409ed88078015a9c45f469604/format.md#format) a "nested list" layout. This layout should be familiar to anyone who has used GeoJSON. For each geometry type, the levels of nesting corresponds exactly to the GeoJSON coordinate array (with one extra level of nesting because here we have _an array_ of geometries, not just one). For example, a geometry column of 2D points is defined as: ``` FixedSizeList[2] ``` You can think of this as similar to an array of GeoJSON point coordinates ```js [ [longitude1, latitude1], // First point [longitude2, latitude2], // Second point ... ] ``` A geometry column containing 2D polygons is defined as: ``` List[n_dim]>> ``` You can think of this logical layout as: ```js [ // <-- Array of geometries [ // <-- Array of rings within the first polygon [ // <-- Array of coordinates within the first polygon ring [ // <-- Coordinate pair longitude1, latitude1 ], [ longitude2, latitude2 ], ... ] ] ] ``` ### Efficient underlying buffers But the awesome part of this geometry encoding is that it combines the above "logical" representation with a really efficient underlying "physical" representation. And it's possible to access both representations through the Arrow API. For example, a column of point geometries is _stored_ as: ```js [longitude1, latitude1, longitude2, latitude2, longitude3, latitude3, ...] // ^- first coordinate ^- second coordinate ^- third coordinate ``` Since the column is defined as `FixedSizeList<2>`, we know that to access the _n^th_ coordinate, we choose the `n * 2` and `(n * 2) + 1` values in the flat array. A column of polygon geometries is slightly more complex. It's stored as a flat coordinate array _plus_ two arrays of _offsets_ that define where polygons and rings begin. Let's start at the lowest level. There's still an array just like above that contains _all coordinates_ of _all geometries_ in the column: ```js [longitude1, latitude1, longitude2, latitude2, longitude3, latitude3, ...] // ^- first coordinate ^- second coordinate ^- third coordinate ``` Then one level of nesting up, we have the _ring offsets array_. This might look something like: ```js [0, 5, 12, 19, ...] ``` This means that the first ring has 5 coordinate pairs, from index 0 to index 4 (inclusive) of the base coordinate array. Then the second ring has 7 coordinate pairs, from index 5 to index 11 (inclusive) of the base coordinate array. And so on. But this array of ring offsets doesn't tell us where _each polygon_ begins and ends, since a single polygon can contain multiple rings (secondary rings for a single geometry indicate holes within the first ring). This is where the _geometry offsets array_ comes in. This might look something like: ```js [0, 1, 3, ...] ``` This means that the first geometry only has a single ring, from ring index `0` to ring index `1`. The second geometry has two rings, from ring index `1` to ring index `3`. Thus the first geometry includes coordinates from coordinate index `0` through coordinate index `4` (up to but not including index `1` in the ring offsets array), and the second geometry includes coordinates from coordinate index `5` through coordinate index `18` (from index `1` in the ring offsets array to index `3` in the ring offsets array). Together, these offset arrays define the same geometries as the "logical" nested lists that GeoJSON describes.32:T4ba,## GeoArrow and deck.gl deck.gl is designed to leverage the GPU to performantly render large amounts of data. But as data sizes get larger, the main bottleneck is often the _CPU_. For GeoJSON data input, deck.gl has to do various CPU steps, including copying the data into a binary buffer which can be uploaded to the GPU. The deck.gl [performance guide](https://deck.gl/docs/developer-guide/performance) is a gold mine of information for making deck.gl applications faster. One of the [primary suggestions](https://deck.gl/docs/developer-guide/performance#use-binary-data) is to pass binary arrays of data to deck.gl. This allows deck.gl to avoid costly CPU steps and drastically lower memory usage. While this binary API has existed for a while, it can be tricky to construct data input correctly. But luckily for us, GeoArrow overlaps almost exactly with the format that deck.gl expects! So deck.gl can render from GeoArrow's physical representation very efficiently. For point and linestring geometry types, the underlying coordinates array can essentially be copied directly to the GPU with no CPU processing required. For polygon geometries, only polygon tessellation still needs to happen on the CPU.33:T89a,## Demo! For a demo, we'll use data from Microsoft's computer-generated [dataset of building footprints in the U.S.](https://github.com/microsoft/USBuildingFootprints) The entire dataset contains nearly 130 million building polygons, so to keep download size smaller, we'll use just data for Utah. But this portion still includes **1 million building footprints with 7 million total coordinates**! ### Pre-processing Microsoft distributes the data as zipped GeoJSON, so as a pre-processing step we need to convert it to GeoParquet. We can use [`ogr2ogr`](https://gdal.org/programs/ogr2ogr.html#ogr2ogr) (version 3.5 or later) to do this. ```sh wget https://usbuildingdata.blob.core.windows.net/usbuildings-v2/Utah.geojson.zip docker run --rm -it -v $(pwd):/data osgeo/gdal:latest \ ogr2ogr \ /data/Utah.parquet \ /vsizip//data/Utah.geojson.zip \ -dialect SQLite \ -sql "SELECT geometry FROM 'Utah.geojson'" \ -lco COMPRESSION=BROTLI \ -lco GEOMETRY_ENCODING=GEOARROW \ -lco POLYGON_ORIENTATION=COUNTERCLOCKWISE \ -lco ROW_GROUP_SIZE=9999999 ``` Note a few of the options provided ([docs here](https://gdal.org/drivers/vector/parquet.html)): - `GEOMETRY_ENCODING=GEOARROW`: Though GeoParquet and GeoArrow are designed to be used together, the GeoParquet doesn't officially support the GeoArrow _encoding_ yet. This forces writing the Arrow-native geometry encoding, rather than WKB. (Calling this option `GEOARROW` is an unfortunate coincidence. It's important to disambiguate between the memory format at large and the underlying choice of geometry encoding, which I'd rather call "Arrow-native"). - `COUNTERCLOCKWISE` polygon orientation: The GeoParquet spec can [optionally declare](https://github.com/opengeospatial/geoparquet/blob/main/format-specs/geoparquet.md#orientation) that the polygon orientation is known. By enforcing counter-clockwise polygon orientation when writing, deck.gl doesn't need to take CPU time to perform validation steps. - `ROW_GROUP_SIZE`: This is set to a number larger than the number of rows in the dataset to enforce a single row group. This makes rendering slightly easier; streaming rendering of multiple row groups is left for a future demo.34:[] 2f:{"title":"GeoArrow and GeoParquet in deck.gl","cells":[{"id":0,"value":"# GeoArrow and GeoParquet in deck.gl\n## _Easier rendering of large geospatial data_\n\nKyle Barron\n
\nAugust 11, 2022","pinned":false,"hidden":false,"mode":"md"},{"id":495,"value":"_Edits_\n\n> October 16, 2023: This notebook is unchanged for information purposes, but see also a [newer notebook](https://observablehq.com/@developmentseed/geoarrow-deck-gl-polygon-example) that uses the newly-released [`@geoarrow/deck.gl-layers`](https://github.com/geoarrow/deck.gl-layers) for much simpler rendering in deck.gl.","pinned":false,"hidden":false,"mode":"md"},{"id":148,"value":"As I explored in my [last post](https://observablehq.com/@kylebarron/geoparquet-on-the-web), GeoParquet is an exciting new format for browser-based applications. But that post glossed over the details of rendering data in [deck.gl](https://deck.gl/).\n\nIn this post I'll focus more on the _GeoArrow_ side of the equation. At a high level, **GeoArrow makes it easier to get the best rendering performance in deck.gl** because it removes the need for most CPU-based pre-processing before passing the data to the GPU for rendering.\n","pinned":false,"hidden":false,"mode":"md"},{"id":265,"value":"## GeoParquet vs GeoArrow\n\nThere are two related specifications under development — [GeoParquet](https://github.com/opengeospatial/geoparquet) (building on [Apache Parquet](https://parquet.apache.org/)) and [GeoArrow](https://github.com/geopandas/geo-arrow-spec) (building on [Apache Arrow](https://arrow.apache.org/)) — and a common question is when to use which.\n\nIn general, GeoParquet and GeoArrow serve different but intertwined purposes. GeoParquet is a _file format_ while GeoArrow is a _memory format_. GeoParquet is intended to be saved to disk while GeoArrow is the result of deserializing a GeoParquet file into memory.\n\nBoth GeoParquet and GeoArrow are columnar formats — meaning data is laid out by column instead of by row — making it efficient to convert between the two.","pinned":false,"hidden":false,"mode":"md"},{"id":272,"value":"$31","pinned":false,"hidden":false,"mode":"md"},{"id":279,"value":"$32","pinned":false,"hidden":false,"mode":"md"},{"id":157,"value":"$33","pinned":false,"hidden":false,"mode":"md"},{"id":291,"value":"### Loading the data\n\nTo load the GeoParquet file into memory, we'll use [`parquet-wasm`](https://github.com/kylebarron/parquet-wasm), my library that provides WebAssembly bindings to Rust Parquet libraries.","pinned":false,"hidden":false,"mode":"md"},{"id":23,"value":"buildingsUrl = \"https://r2-public-read.kylebarron.dev/observable/2022/geoarrow-deckgl/Utah.parquet\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":378,"value":"We'll start by downloading the GeoParquet file and parsing it to an Arrow table.\nParsing this buffer into Arrow memory takes roughly 3 seconds on my machine, decoding the 44MB Parquet buffer to a 121 MB Arrow table.","pinned":false,"hidden":false,"mode":"md"},{"id":35,"value":"parquetBuffer = fetch(buildingsUrl).then((response) => response.arrayBuffer())","pinned":true,"hidden":false,"mode":"ojs"},{"id":26,"value":"arrowTable = {\n const parquetBytes = new Uint8Array(parquetBuffer);\n const decodedArrowBytes = parquet.readParquet(parquetBytes);\n const arrowTable = arrow.tableFromIPC(decodedArrowBytes);\n return arrowTable;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":322,"value":"This dataset has only a single column, the geometry column, so we'll select that. (The name of the primary geometry column is also contained in GeoArrow metadata, but `parquet-wasm` has a bug and currently drops that metadata.)","pinned":false,"hidden":false,"mode":"md"},{"id":171,"value":"arrowTable.schema.fields[0]","pinned":true,"hidden":false,"mode":"ojs"},{"id":53,"value":"geometryColumn = arrowTable.getChildAt(0)","pinned":true,"hidden":false,"mode":"ojs"},{"id":386,"value":"#### Familiar \"logical\" data layout\n\nGeoArrow's Arrow-native geometry encoding has a familiar logical data layout. In the Arrow JS API you can use `.get()` to access the logical parts of a geometry. This enables a high-level API of looping over coordinates just like GeoJSON.","pinned":false,"hidden":false,"mode":"md"},{"id":388,"value":"{\n const firstGeometry = geometryColumn.get(0);\n const firstRing = firstGeometry.get(0);\n const firstCoord = firstRing.get(0);\n return firstCoord.toArray();\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":430,"value":"Expand this array output to see the inner coordinates:","pinned":false,"hidden":false,"mode":"md"},{"id":400,"value":"// Pretty print the first geometry\n// One ring with five coordinates\n{\n const firstGeom = geometryColumn.get(0);\n const printedGeom = [];\n for (const ring of firstGeom) {\n const printedRing = [];\n for (const coord of ring) {\n const printedCoord = [coord.get(0), coord.get(1)];\n printedRing.push(printedCoord);\n }\n printedGeom.push(printedRing);\n }\n return printedGeom;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":384,"value":"#### Zero-copy access to underlying buffer\n","pinned":false,"hidden":false,"mode":"md"},{"id":455,"value":"Since this is a two-dimensional polygon dataset, the geometry column is stored as\n\n```\nList[2]>>\n```","pinned":false,"hidden":false,"mode":"md"},{"id":332,"value":"At the top level, the `offsets` of the array correspond to indexes _into_ `RingIndices` (the second level of nesting) for the start of each new polygon.","pinned":false,"hidden":false,"mode":"md"},{"id":215,"value":"// Note that `data` here is an array with only one element because this Parquet file only had one row group\n// Otherwise we'd need to do this process for each batch of columnar data\npolygonIndices = geometryColumn.data[0].valueOffsets","pinned":true,"hidden":false,"mode":"ojs"},{"id":343,"value":"At the first level of nesting, the `offsets` correspond to indexes _into_ the coordinate array (the third level of nesting) for the start of each ring.","pinned":false,"hidden":false,"mode":"md"},{"id":199,"value":"ringIndices = geometryColumn.getChildAt(0).data[0].valueOffsets","pinned":true,"hidden":false,"mode":"ojs"},{"id":347,"value":"This means that get an array of indexes where each _polygon_ starts, we need to perform a lookup between these two arrays. Namely, the _i^th_ element of `polygonIndices` tells the index within `ringIndices` where the _i^th_ polygon begins.","pinned":false,"hidden":false,"mode":"md"},{"id":334,"value":"resolvedPolygonIndices = {\n const resolvedIndices = new Int32Array(polygonIndices.length);\n for (let i = 0; i < resolvedIndices.length; ++i) {\n // Perform the lookup into the ringIndices array using the polygonIndices array\n resolvedIndices[i] = ringIndices[polygonIndices[i]]\n }\n return resolvedIndices;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":363,"value":"At the second level of nesting, we have the coordinate array. Each row contains one coordinate pair: a list of size two.","pinned":false,"hidden":false,"mode":"md"},{"id":351,"value":"coordinateVector = geometryColumn.getChildAt(0).getChildAt(0)","pinned":true,"hidden":false,"mode":"ojs"},{"id":369,"value":"At the third level of nesting, we have a flat array of coordinates. The `Float64Array` view onto this buffer (`flatCoordinateArray`) below, is what we'll pass into deck.gl.","pinned":false,"hidden":false,"mode":"md"},{"id":176,"value":"flatCoordinateVector = geometryColumn.getChildAt(0).getChildAt(0).getChildAt(0)","pinned":true,"hidden":false,"mode":"ojs"},{"id":178,"value":"flatCoordinateArray = flatCoordinateVector.data[0].values","pinned":true,"hidden":false,"mode":"ojs"},{"id":371,"value":"Now we're ready to render our data with deck.gl. Since this is a polygon dataset, we'll use the [`SolidPolygonLayer`](https://deck.gl/docs/api-reference/layers/solid-polygon-layer).","pinned":false,"hidden":false,"mode":"md"},{"id":51,"value":"deckglLayer = {\n // Refer to https://deck.gl/docs/api-reference/layers/solid-polygon-layer#use-binary-attributes\n const data = {\n // Number of geometries\n length: arrowTable.numRows,\n // Indices into coordinateArray where each polygon starts\n startIndices: resolvedPolygonIndices,\n // Flat coordinates array\n attributes: {\n getPolygon: { value: flatCoordinateArray, size: 2 }\n }\n };\n const layer = new deck.SolidPolygonLayer({\n // This is an Observable hack - changing the id will force the layer to refresh when the cell reevaluates\n id: `layer-${Date.now()}`,\n data,\n // Skip normalization for binary data\n _normalize: false,\n // Counter-clockwise winding order\n _windingOrder: \"CCW\",\n getFillColor: [0, 100, 60, 160],\n });\n\n deckglMap.setProps({ layers: [layer] });\n\n return layer;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":375,"value":"Voila! 1 million building footprints in Utah rendered at once:","pinned":false,"hidden":false,"mode":"md"},{"id":7,"value":"mapContainer = html`

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":252,"value":"## Future work\n\n- Polygons with holes. This dataset consisted only of simple polygons without holes and it's not clear that deck.gl's binary format can handle polygons with holes today.\n- Handle GeoArrow natively in deck.gl?","pinned":false,"hidden":false,"mode":"md"},{"id":186,"value":"# Acknowledgments\n\nThanks to Avi Bryant for this week at [Gradient Retreat](https://www.gradientretreat.com/). Thanks to Tom MacWright, Brandon Liu, Rachel Binx, and James Tyrwhitt-Drake for feedback. Thanks to Joris Van den Bossche for his [helpful notebook](https://nbviewer.org/gist/jorisvandenbossche/00e5c4a54f7b94375ccc6921c07825a0) outlining the Python GeoArrow API. ","pinned":false,"hidden":false,"mode":"md"},{"id":17,"value":"// Load the parquet-wasm library\nparquet = {\n const parquetModule = await import(\n \"https://unpkg.com/parquet-wasm@0.4.0-beta.3/esm/arrow2.js\"\n );\n // Need to await the default export first to initialize the WebAssembly code\n await parquetModule.default();\n return parquetModule;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":9,"value":"deck = require.alias({\n h3: {}\n})(\"deck.gl@8.8.6/dist.min.js\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":233,"value":"deckglMap = {\n // This is an Observable hack: clear previously generated content\n mapContainer.innerHTML = \"\";\n\n return new deck.DeckGL({\n // The HTML container to render into\n container: mapContainer,\n map: mapboxgl,\n mapStyle:\n \"https://basemaps.cartocdn.com/gl/positron-nolabels-gl-style/style.json\",\n\n // Viewport settings\n initialViewState: {\n longitude: -111.91530172951025,\n latitude: 40.63403641639511,\n zoom: 11,\n pitch: 0,\n bearing: 0\n },\n controller: true\n });\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":235,"value":"mapboxgl = require(\"mapbox-gl@1.6.0/dist/mapbox-gl.js\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":48,"value":"arrow = require(\"apache-arrow\")","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W34","stdlib":"1","titling":"auto"}