Spatial support discussion

[czentgr]

A large number of the functionality missing is dominated by the spatial functions.

From a Presto perspective, the Java implementation utilizes the locationtech JTS and ESRI libraries to provide spatial support.
On the C/C++ side there is the libgeos project (https://libgeos.org) which says it is closely linked to JTS. It implements the OGC Simple Features model which is used by most RBMS vendors. ESRI does have a spatial library (SDE) written in C but this is proprietary, afaik.

Adding spatial support would require discussing and designing the following:

• add a third party spatial library to the Velox project
• implement Geometry type - VARBINARY - and the actual data maybe in WKB? - in Java it uses JTS serialize and deserialize for Geometry objects
• implement the various spatial functions (scalar and aggregate) using the library

These are the basic things I can think of. But this needs some discussion on the what and how. Hence I'm creating this discussion item.

[kgpai]

Hi @czentgr ,

Thanks for raising this. Coming to the points you raised:

add a third party spatial library to the Velox project

We have a framework in place to add third party libraries . A recent example is SIMDJSON which you can see example of in the discussions and PRs. (Reach out to me if you want pointers to code etc). Assuming the libraries are open source and have the right license then this shouldnt be a problem.

implement Geometry type - VARBINARY - and the actual data maybe in WKB? - in Java it uses JTS serialize and deserialize for Geometry objects
There is support to add custom types in Velox , though atm this is lot more involved (See Decimal, json etc..).

implement the various spatial functions (scalar and aggregate) using the library
Once the above two are done this would be straightforward enough.

It would be great if you can contribute with these changes to Velox.

[czentgr]

I took a look at the SIMDJSON discussion and associated PR.
The libgeos project uses the LGPL license: https://github.com/libgeos/geos/blob/main/COPYING.
I started the discussion with this proposal. I'm assuming there is some vetting involved and perhaps other people have a different proposal for the underlying functionality. I picked this one because of the close relationship to JTS which is used in Presto.

[majetideepak]

Aligning with Presto semantics and results is a good target. Can you share some insights on how other implementations differ?
Are there any downsides with libgeos?

[czentgr]

Actually, there don't seem to be other implementations of a C/C++ OGC simple Features library. I found GEOS as it mentions it is an C/C++ port of JTS which is used by Presto, and it is the core library around other prominent open source projects using spatial capabilities (e.g. PostGIS). So it seems a natural fit and I didn't really dig much deeper to compare with others prior to proposing GEOS.
A possible downside with GEOS might be the C++ API as it is more unstable than the C API. So when upgrading it might introduce problems.
In addition, presto implements the OGC functions using a mix of ESRI and JTS functions. Not sure as to why, for example, for the

Also, GEOS only provides a subset of the functionality. Lots of functions are implemented using the ESRI Java library and not JTS directly.
AFAIK the ESRI C equivalent implementation is proprietary.

[majetideepak]

@czentgr As @kgpai mentioned, the order would be 1) Adding the third-party dependency, 2) Adding a logical type Geometry backed by Varbinary, and 3) Write Functions for this type.
For adding a logical type, refer to JsonType which is similar: https://github.com/facebookincubator/velox/blob/main/velox/functions/prestosql/types/JsonType.h
It will help if you can share a design document.

[majetideepak]

@czentgr On the Presto Java side, the Geometry type seems to be not built-in. I see prestodb/presto#19449

[czentgr]

@majetideepak Interesting. I was looking at the presto code/implementation and didn't notice that there is no built-in type.
So for an initial implementation, perhaps no type needs to be implemented to match presto. Probably not much of a problem to construct the geometries on the fly via constructors the user calls in their SQL queries. Underlying storage data type would be string (WKT, GEOJSON) and binary (WKB).

[majetideepak]

@czentgr This seems to be a simpler first take for supporting Geometry and aligning with Presto.

[majetideepak]

CC: @mbasmanova

[aditi-pandit]

@tdcmeehan

[wraymo]

I wanted to share an update on the issue regarding the plan for spatial support. Here’s the progress I’ve made so far:

• Added geometry types in Velox.
• Introduced GEOS as a dependency.
• Implemented serialization and deserialization for geometry types using GEOS.
• Added cast operators in both PrestoDB and Velox to convert VARCHAR (WKT) or VARBINARY (WKB) into geometry types.
• Implemented spatial functions such as ST_Point and ST_Contains in Velox.
• Added SpatialJoinNode in Velox to enable spatial joins, implemented using NestedLoopJoinNode.

The cast operator is optional since equivalent functionality can be achieved with ST_GeometryFromText and ST_GeomFromBinary.

Currently, I’m working on performance evaluations of spatial joins. We may come up with better designs later. Additionally, unit tests and docs will be added in a later phase.

Does this plan and progress align with expectations? Looking forward to your feedback and suggestions!

[amitkdutta]

CC: @pedroerp @jagill

[aditi-pandit]

@wraymo : Thanks for the update. Any chance you could share your code in a PR ? Even a rough prototype will do. That would really help us assess the next steps.

[wraymo]

@aditi-pandit Thanks for your reply. Should I include all the changes in a single PR?

[aditi-pandit]

@wraymo : Yes, sure we can use that as a reference.

[wraymo]

@aditi-pandit : I created a draft PR in Velox, which covers the first five tasks.