5 ms·

I've been using PostGIS a bit for a toy project with Elite: Dangerous star system data. It's been a hoot, but I do worry that I'm going to start having trouble

I've been using PostGIS a bit for a toy project with Elite: Dangerous star system data. It's been a hoot, but I do worry that I'm going to start having trouble optimizing my queries. Finding all the systems within say 20 Ly of our sun can take upwards of a few seconds, and I've already added a GIST index on the positions. I also find it a bit strange how 3D feels kinda tacked on, but it makes sense when you realize most maps are in fact 2D. Anyway, my 2-cents of experience. If anyone has some good advise for > million row, 3D spacial optimizations for PostGIS, please let me know.

jhgb 6y ago
> Finding all the systems within say 20 Ly of our sun can take upwards of a few seconds, and I've already added a GIST index on the positions. Doesn't that sound a bit pathological? It should be nowhere near that slow. Try implementing a VP tree over that data.
- nixpulvis 6y ago
  I mean, I'm using the provided GiST-based R-Tree spatial index... Otherwise, I'm not really making any use of PostGIS and might as well look for other spacial DBs or write my own little data-structure like you mention (thanks for the link to VP-trees btw). I was hoping that the performance of PostGIS's features could be improved with some know how.
estsauver 6y ago
The only thing I can recommend off hand is to try and simplify your geometries a bit for searching if they’re complex. Searching along the border of a complicated shape is much harder than searching around a square, it has to do a lot more calculations.
- tpetry 6y ago
  Yes had the same solution ~15 years ago when location based search got popular. Searching for anything within some distance to a defined location with perfect earth projection and a circle radius „did not scale“. Ignoring the earth‘s projection and pretending a flat earth with a rectangle search was much much faster. In the end we used this simplified calculation with added „regions“. So the world was split into 15km*15km squares, so any square being more than x apart could never be in the result set. This could maybe be used with modern postgresql partitioning and partition elimination in a clever way. And without partitioning maybe clever z-ordering the entries physically in the database (clustering) could reduce a lot of random i/o.
  - electrum 6y ago
    The Bing Maps Tile System has a similar projection system: https://docs.microsoft.com/en-us/bingmaps/articles/bing-maps-tile-system https://docs.microsoft.com/en-us/bingmaps/articles/bing-maps...
- nkozyra 6y ago
  MBR is a common optimization shortcut but I have to wonder if PostGIS doesn't already do that as a first pass filter anyway. It's an incredibly smart and performant extension. Sometimes the issue can be tweaked by using intersection versus overlap/contains/contained when possible.
7952 6y ago
You could use a clustered index
- nixpulvis 6y ago
  Interesting, I think I read something about this before... I'll have to make a point to actually give this a go.
yxhuvud 6y ago
Hmm. That sounds like a lot of time. How does your query look like for that?
- nixpulvis 6y ago
  SELECT address, name, position, population, security, government, allegiance, primary_economy, secondary_economy, updated_at FROM systems WHERE ST_3DDWithin(position, $1, $2); With the aforementioned index: "systems_position_idx" gist ("position" gist_geometry_ops_nd)
  - yxhuvud 6y ago
    Ok, I see no obvious ways that is suboptimal. I assume there are no difference if you switch places of position and $1?
nicois 6y ago
Is it possible you haven't added the bounding box for your geometries? The GIST index will use your bounding box to optimise the queries, but only if it finds one. Also make sure your query is actually using the index.
- cwmma 6y ago
  assuming you're using the postgis spatial data types (and not the postgres ones) it'll take care of that automatically.
  - nixpulvis 6y ago
    Yes, I'm currently just using a single PointZ column, which is at least making some use of the index on my relevant 3DDWithin queries.
tcbasche 6y ago
My suggestion might be to a precalculated step to split "the universe" into grid areas divided by geometry complexity (i.e. population density gridding) then process these reference areas in parallel. How you do the latter is probably the interesting part!
- nixpulvis 6y ago
  I'm not sure this is as simple as you make it sound... Neighbors (the one example I gave) can exist across these precomputed grids, which would need to be accounted for. This is essentially what the role of the index is. So it sounds like you have the right idea, just not fully fleshed out. For batch processing once I have a set of independent systems, I actually don't think that's the interesting part of this thread, since I could just package up the needed inputs and ship them off to their own cores for all I care. Most of the questions I care about require the relationships between these positions, i.e. Distance and derived metrics.
gfiorav 6y ago
You can subdivide large geometries. You can decide how much by controlling the amount of vertices a polygon can have before it’s chopped away. Intersections with large polygons will perform faster if subdivided.
- nixpulvis 6y ago
  Perhaps I should have noted in my initial post that the only spacial data stored at the moment is the star system's (x, y, z) position in the game's coordinate system. Unless I'm misunderstanding, there should be nothing to cull from a point (ignoring projections)... right?
cwmma 6y ago
there is a specific command you need to use to create a 3d index CREATE INDEX [indexname] ON [tablename] USING GIST ([geometryfield] gist_geometry_ops_nd); by default postgis just creates 2d ones
- nixpulvis 6y ago
  Indeed. It's definitely working, just not working well enough to satisfy my performance requirements in my current usage.
billfruit 6y ago
What kind of front end do you use. Usually the spatial db is only a part of the solution, and the GIS information needs to displayed and functionality for interaction with maps and objects needs to provided. What framework would pair well with PostGis in the open source world?
- nixpulvis 6y ago
  Yea the front end is kinda an open question. I've been slowly relearning OpenGL (or maybe Vulkan) for building a little 3D scatter plot like map. 2D projections could come as a feature on top of that I guess. Mostly I just want textual information at the moment, viz is just "cool". Like, the primary question is simply, from star A to star Z how many FSD high wake jumps will I need to perform, and how much fuel will it cost. Then the pathfinding is modified to know about star class, and find valid routes with fuel scoopable stars, then the algorithm could be modified again to account for range boosting white dwarf stars, finally, it would be really cool to incorporate the game's market data, since while other third party tools already do all these things, they do not generate good trade loops. I've been very disappointed with what little open source 3D mapping software I've seen. Everything seems highly centered around 2D projected maps. So personally, I've just been using matplotlib and it's various plotting tool with a jupyter notenook with readonly access to my database, allowing me to write %sql ... and get a python object for the resulting rows.
  - billfruit 6y ago
    3d is major disappointment for me as well. Lot of entrenched mindset in GIS field against 3d, I do think there is major scope for innovation in this direction.
    - nixpulvis 6y ago
      I find that somewhat hilarious actually... Like what do GIS people think, we live on a flat earth? Seriously though, if all you ever want to do is draw 2D maps, I can see optimizing these cases. I can even maybe understand how it's best to nail these features down first... However, it just seems like so many of the tools data models are corrupted by a fundamentally mishandling of 2D vs 3D. For example, a library I'm using for WKB encoding/decoding pollutes my 3D points with a bunch of functions for dealing with 2D points that I frankly want nothing to do with. Why should I ever want a function on a 3D point to return a 2D point with an optional third member. I can see how this might help you embed a 2D point inside a 3D space, by treating the null value as 0, or filtering it, or some other user defined or standard logic... but if I have a 3D point, why on earth am I casting it to a partially optional 3D point. That was just an example that's been really bothering me... there's lots of other examples of 2D driven features looking a bit strange in 3D. Not to mention adding an M dimension, or outside PostGIS, any others. The difficulty with this problem is the immense, vast, epic scale of the issue. I want to say you could probably just define the 3D metric space and then build the 2D one of that, but then why stop there. Perhaps I want a 5D space with distance measured as some similarity metric... is this not starting to sound like a more general problem than GIS? And another thing! It would be very interesting to think about what aspects of the spacial reference are useful in 3D. I'm still learning about how the SRIDs are used in PostGIS, but this [1] example makes a lot of sense for lat/long references. [1]: http://www.bostongis.com/blog/index.php?/archives/266-geography-type-is-not-limited-to-earth.html http://www.bostongis.com/blog/index.php?/archives/266-geogra...
fdr 6y ago
Hmm, I think you are looking for SP-GiST (unbalanced space partitioned GiST), unless you meant that implicitly. It can be much faster for...space partitioning.
- nixpulvis 6y ago
  Oh damn, I don't know how I missed that section of the docs. Indeed, though I haven't really profiled this, an SP-GiST index does seem quite a bit faster for me. Thanks for the tip! Still can't plot from Sol to Colonia with a range of 100 Ly (near the very dense center of the galaxy) in under 10 seconds though. But I'm aware of some larger issues in the search algorithm itself that are probably my next task on this journey. The performance of this index feels closer to what I think I was expecting to see on it's own.
  - fdr 6y ago
    If you ever measure the improvement, a brief note/blog post/tweet might instructive to people. Would be curious what kind of different result you get.

jhgb 6y ago

> Finding all the systems within say 20 Ly of our sun can take upwards of a few seconds, and I've already added a GIST index on the positions. Doesn't that sound a bit pathological? It should be nowhere near that slow. Try implementing a VP tree over that data.

nixpulvis 6y ago
I mean, I'm using the provided GiST-based R-Tree spatial index... Otherwise, I'm not really making any use of PostGIS and might as well look for other spacial DBs or write my own little data-structure like you mention (thanks for the link to VP-trees btw). I was hoping that the performance of PostGIS's features could be improved with some know how.

estsauver 6y ago

The only thing I can recommend off hand is to try and simplify your geometries a bit for searching if they’re complex. Searching along the border of a complicated shape is much harder than searching around a square, it has to do a lot more calculations.

tpetry 6y ago
Yes had the same solution ~15 years ago when location based search got popular. Searching for anything within some distance to a defined location with perfect earth projection and a circle radius „did not scale“. Ignoring the earth‘s projection and pretending a flat earth with a rectangle search was much much faster. In the end we used this simplified calculation with added „regions“. So the world was split into 15km*15km squares, so any square being more than x apart could never be in the result set. This could maybe be used with modern postgresql partitioning and partition elimination in a clever way. And without partitioning maybe clever z-ordering the entries physically in the database (clustering) could reduce a lot of random i/o.
- electrum 6y ago
  The Bing Maps Tile System has a similar projection system: https://docs.microsoft.com/en-us/bingmaps/articles/bing-maps-tile-system https://docs.microsoft.com/en-us/bingmaps/articles/bing-maps...
nkozyra 6y ago
MBR is a common optimization shortcut but I have to wonder if PostGIS doesn't already do that as a first pass filter anyway. It's an incredibly smart and performant extension. Sometimes the issue can be tweaked by using intersection versus overlap/contains/contained when possible.

7952 6y ago

You could use a clustered index

nixpulvis 6y ago
Interesting, I think I read something about this before... I'll have to make a point to actually give this a go.

yxhuvud 6y ago

Hmm. That sounds like a lot of time. How does your query look like for that?

nixpulvis 6y ago
SELECT address, name, position, population, security, government, allegiance, primary_economy, secondary_economy, updated_at FROM systems WHERE ST_3DDWithin(position, $1, $2); With the aforementioned index: "systems_position_idx" gist ("position" gist_geometry_ops_nd)
- yxhuvud 6y ago
  Ok, I see no obvious ways that is suboptimal. I assume there are no difference if you switch places of position and $1?

nicois 6y ago

Is it possible you haven't added the bounding box for your geometries? The GIST index will use your bounding box to optimise the queries, but only if it finds one. Also make sure your query is actually using the index.

cwmma 6y ago
assuming you're using the postgis spatial data types (and not the postgres ones) it'll take care of that automatically.
- nixpulvis 6y ago
  Yes, I'm currently just using a single PointZ column, which is at least making some use of the index on my relevant 3DDWithin queries.

tcbasche 6y ago

My suggestion might be to a precalculated step to split "the universe" into grid areas divided by geometry complexity (i.e. population density gridding) then process these reference areas in parallel. How you do the latter is probably the interesting part!

nixpulvis 6y ago
I'm not sure this is as simple as you make it sound... Neighbors (the one example I gave) can exist across these precomputed grids, which would need to be accounted for. This is essentially what the role of the index is. So it sounds like you have the right idea, just not fully fleshed out. For batch processing once I have a set of independent systems, I actually don't think that's the interesting part of this thread, since I could just package up the needed inputs and ship them off to their own cores for all I care. Most of the questions I care about require the relationships between these positions, i.e. Distance and derived metrics.

gfiorav 6y ago

You can subdivide large geometries. You can decide how much by controlling the amount of vertices a polygon can have before it’s chopped away. Intersections with large polygons will perform faster if subdivided.

nixpulvis 6y ago
Perhaps I should have noted in my initial post that the only spacial data stored at the moment is the star system's (x, y, z) position in the game's coordinate system. Unless I'm misunderstanding, there should be nothing to cull from a point (ignoring projections)... right?

cwmma 6y ago

there is a specific command you need to use to create a 3d index CREATE INDEX [indexname] ON [tablename] USING GIST ([geometryfield] gist_geometry_ops_nd); by default postgis just creates 2d ones

nixpulvis 6y ago
Indeed. It's definitely working, just not working well enough to satisfy my performance requirements in my current usage.

billfruit 6y ago

What kind of front end do you use. Usually the spatial db is only a part of the solution, and the GIS information needs to displayed and functionality for interaction with maps and objects needs to provided. What framework would pair well with PostGis in the open source world?

nixpulvis 6y ago
Yea the front end is kinda an open question. I've been slowly relearning OpenGL (or maybe Vulkan) for building a little 3D scatter plot like map. 2D projections could come as a feature on top of that I guess. Mostly I just want textual information at the moment, viz is just "cool". Like, the primary question is simply, from star A to star Z how many FSD high wake jumps will I need to perform, and how much fuel will it cost. Then the pathfinding is modified to know about star class, and find valid routes with fuel scoopable stars, then the algorithm could be modified again to account for range boosting white dwarf stars, finally, it would be really cool to incorporate the game's market data, since while other third party tools already do all these things, they do not generate good trade loops. I've been very disappointed with what little open source 3D mapping software I've seen. Everything seems highly centered around 2D projected maps. So personally, I've just been using matplotlib and it's various plotting tool with a jupyter notenook with readonly access to my database, allowing me to write %sql ... and get a python object for the resulting rows.
- billfruit 6y ago
  3d is major disappointment for me as well. Lot of entrenched mindset in GIS field against 3d, I do think there is major scope for innovation in this direction.
  - nixpulvis 6y ago
    I find that somewhat hilarious actually... Like what do GIS people think, we live on a flat earth? Seriously though, if all you ever want to do is draw 2D maps, I can see optimizing these cases. I can even maybe understand how it's best to nail these features down first... However, it just seems like so many of the tools data models are corrupted by a fundamentally mishandling of 2D vs 3D. For example, a library I'm using for WKB encoding/decoding pollutes my 3D points with a bunch of functions for dealing with 2D points that I frankly want nothing to do with. Why should I ever want a function on a 3D point to return a 2D point with an optional third member. I can see how this might help you embed a 2D point inside a 3D space, by treating the null value as 0, or filtering it, or some other user defined or standard logic... but if I have a 3D point, why on earth am I casting it to a partially optional 3D point. That was just an example that's been really bothering me... there's lots of other examples of 2D driven features looking a bit strange in 3D. Not to mention adding an M dimension, or outside PostGIS, any others. The difficulty with this problem is the immense, vast, epic scale of the issue. I want to say you could probably just define the 3D metric space and then build the 2D one of that, but then why stop there. Perhaps I want a 5D space with distance measured as some similarity metric... is this not starting to sound like a more general problem than GIS? And another thing! It would be very interesting to think about what aspects of the spacial reference are useful in 3D. I'm still learning about how the SRIDs are used in PostGIS, but this [1] example makes a lot of sense for lat/long references. [1]: http://www.bostongis.com/blog/index.php?/archives/266-geography-type-is-not-limited-to-earth.html http://www.bostongis.com/blog/index.php?/archives/266-geogra...

fdr 6y ago

Hmm, I think you are looking for SP-GiST (unbalanced space partitioned GiST), unless you meant that implicitly. It can be much faster for...space partitioning.

nixpulvis 6y ago
Oh damn, I don't know how I missed that section of the docs. Indeed, though I haven't really profiled this, an SP-GiST index does seem quite a bit faster for me. Thanks for the tip! Still can't plot from Sol to Colonia with a range of 100 Ly (near the very dense center of the galaxy) in under 10 seconds though. But I'm aware of some larger issues in the search algorithm itself that are probably my next task on this journey. The performance of this index feels closer to what I think I was expecting to see on it's own.
- fdr 6y ago
  If you ever measure the improvement, a brief note/blog post/tweet might instructive to people. Would be curious what kind of different result you get.