Point in Polygon, etc...

[NedHarding]

I am trying to evaluate the usefulness for DuckDb spatial for business purposes. For reference I am the original designer/author of Alteryx (not affiliated any more) so I have my own way of thinking about spatial that differs from how DBs have done it.

A really common thing I want to do is Point in Polygon. Using DuckDB I can do Contains or Intersects, but they both have issues with points that are on the boundary. When there is a continuous layer (like ZIP codes) I want each point to be in 1 and only 1 polygon (deterministically). With Contains, a point on the edge is in 0 polygons and with Intersects a point on a boundary will be in 2 polygons. I am not seeing an option to be in 1 and only 1.

There are other missing functions like creating a radius (or buffer) with an actual earth based distance instead of having to change projections. Also I'd love to integrate things like Valhalla for drivetime polygon creation so that a join can be done on a drivetime natively.

So presuming I am seeing this correctly:

1. Is there interest in adding other spatial functions that would be on the more unique side of things? Or should I create a plugin just for my use cases.

2. I have a design for a spatial index for a point only layer that outperforms more generic 2D indexes by an order of magnitude - is there any interest in integrating that? If so I would probably need some help in figuring out the DuckDB way of doing things.

[Maxxen]

Hi Ned!

A really common thing I want to do is Point in Polygon. Using DuckDB I can do Contains or Intersects, but they both have issues with points that are on the boundary.

Using ST_Contains and ST_Intersects with the GEOMETRY type should not exhibit this behavior... are you using POINT_2D/POLYGON_2D?

There are other missing functions like creating a radius (or buffer) with an actual earth based distance instead of having to change projections.

Yeah, for filtering purposes you could use ST_DWithinSpheroid, but Im sure that we could add an earth aware point buffering function without too much effort. However when I last looked into creating buffers on the sphere generically for other geometry types it seemed to me like it would be extremely difficult to implement, especially if you want the same semantics regarding self-intersections and convex polygons as GEOS currently provides for us on the plane. Buffering on the plane can already get pretty gnarly, and this is the only reference I've found of someone attempting to do it on the sphere. I think PostGIS just attempts to re-project to a better fitting projection, but still performs the buffering operation in planar space.

That said, if we add a ST_Buffer_Sphere we could just throw a NotImplemented error for non-point inputs.

Also I'd love to integrate things like Valhalla for drivetime polygon creation so that a join can be done on a drivetime natively.

One thing I've realized during my time working on DuckDB is that DuckDB really shines by being able to execute simpler operations on a large set of data in a hot-loop (the whole "vectorized execution" thing). But if you're going to call into an external library on a row-by-row basis that in turn will dominate the runtime with a lot of computation heavy code (as is usually the case in routing-calculations), you're not really gaining a lot by integrating into DuckDB, except for the convenience in being able to interact with it through SQL.

Im not completely against adding new dependencies, but because we want to statically link everything and ship binaries for 10+ platforms, larger dependencies need to be worth their build and maintenance burden. Additionally, spatial is already pretty large and will ideally stick to C++11. Perhaps a Valhalla integration would fit better as a separate extension?

Now, to your questions:

1. Is there interest in adding other spatial functions that would be on the more unique side of things? Or should I create a plugin just for my use cases.

I guess it depends. We generally try to follow along the tradition of PostGIS/Spatialite and the whole SQL/MM OGC world of geospatial SQL functionality, but I also don't want to be too stuck in the past. We're happy to add extra stuff that people find useful as well, but ideally it is implemented natively or makes use of the existing dependencies. If you have think you have a really unusual idea for a new function that no other database has, It's a good idea to first open a discussion so we can see how it would interact with the existing concepts and functionality in the spatial extension.

2. I have a design for a spatial index for a point only layer that outperforms more generic 2D indexes by an order of magnitude - is there any interest in integrating that? If so I would probably need some help in figuring out the DuckDB way of doing things.

Cool! Could you elaborate on how this index works differently than e.g. a R-Tree? Can it be serialized/deserialized/"paged" efficiently to/from disk? Do you have some code or a paper you could share?

Indexing in DuckDB is still very immature and limited, and Indexes in extensions doubly so. There is as of now no API for creating custom indexes, managing storage or having them be used by the query planner, and hacking around it like I've done in spatial requires significant knowledge of DuckDB (unstable) internals. Thankfully using indexes in DuckDB is not as much of a "requirement" as it often is in other databases, and it can often produce worse query times depending on the size and access patterns of your workloads, see e.g. #444 or the section on indexes in the docs. So in general I would not recommend attempting to implement a custom DuckDB index type yet.

so I have my own way of thinking about spatial that differs from how DBs have done it.

I myself is very much from the spatial-SQL world, so I'd be very happy to hear more of your thoughts on spatial and what issues/problems/features you think are important to solve!

[NedHarding]

Hey Maxxen,

Thanks so much for the answer.

1st - some context - I am having former customers asking me for recommendations for replacing Alteryx with open source. So I have a huge bias in how Alteryx works. At Alteryx we made some very practical decisions for processing business data in ways that is generally correct even if its not mathematically perfect.

My issue with pt in poly is that I want a function that any given point is in 1 and only 1 polygon when you have a continuous surface like ZIP codes. And also, each point will always be in the same polygon even if the rest of the surface is different. st_contains and st_intersects don't do that. They do something that is mathematically more correct, but practically speaking kind of wrong. It can of course be done by adding a UNIQUE constraint, but that is a whole set of processing and it would be hard to set up the query so you always got the same answer. Whereas a careful use of <= and < in the pt in poly function it is easy and fast. It is something very subtle that has always frustrated me about spatial DBs.

Generally speaking buffering objects with a local projection is very easy and quick. You just compute the proper meters for the X and Y of the centroid and stick in lat/long space. It works great at less than 75 degrees Lat (i.e. where everyone on the planet lives) and as long as your polygons don't extend more than a few degrees or so in the Y direction. Again, practical decisions that are correct for real world data even if they are wrong mathematically. But for points and radii under 100km its basically always good enough. What DuckDB has now just generates ovals and is worse than useless.

The other feature I would love (but its REALLY hard) is earth aware bounded voronoi polygon generation. I don't think I have it in me to write that one again though.

As far as integrations with things like Valhalla - I thought that would be the answer. But there is a huge convenience of having everything in one process.

As far as a different index - I mostly agree with you. DuckDb is very fast. There are some very specific use cases that Alteryx solves that it would be too slow for, but for almost everything DuckDb is probably already as good or better.

I don't have any code or anything that I own, but since the ideas predated Alteryx, they are mine. Short answer is yes, built around pages and compression so it is very small and fast. Tends to fit each point in about 4 bits on average to 1/1,000,000th degree precision (about a meter) for large data sets Basic idea is sort by X, break into pages, sort each page by Y and then compress each page with some differential compression. Really simple, but really effective and fast.