[postgis-users] Fast bounding box intersection query against many edges

[Tom Kazimiers]

Hello everyone,

I use Postgres 9.4 and PostGIS 2.1 to represent about 13.000.000
vertices in a 3D space (growing). Many points are connected in tree
structures of varying size, often around 5000 nodes per tree. Therefore,
we use single edges to represent them in our table. My aim is to have
very fast queries to get all edges that intersect an arbitrary axis
aligned bounding box.

From what I understand, one option (1) would be the &&& operator to get
all all edges with (axis aligned, I assume) bounding boxes that
intersect with my query bounding box. Or alternatively, (2) use
ST_3DDWithin to get all edges that are within a distance of half my
bounding box height to a polygon in Z that cuts my query bounding box in
half.

Are there other options that I am unaware of? I need to find also edges
that are really within the query bounding box, that do not intersect
with its surface.

I tested both approaches and attached one example query each at the end
of this mail, where I also show the table layout plus indices as well as
the query plans. Is there something I could improve on?

Option (1) is already pretty quick, but I get some false positives (due
to intersecting bounding boxes of edges, not edges themself) that I
would need to remove later (which is okay), but of course it would be
nice to not have them in the first place. But there as well, better
speed would be welcome.

Thanks,
Tom


Table layout: for (1) a n-D index and for (2) a 2-D index was needed
============

          Table "public.treenode_edge"
   Column   |         Type          | Modifiers 
------------+-----------------------+-----------
 id         | bigint                | not null
 project_id | integer               | not null
 edge       | geometry(LineStringZ) | 
Indexes:
    "treenode_edge_pkey" PRIMARY KEY, btree (id)
    "treenode_edge_gix" gist (edge gist_geometry_ops_nd)
    "treenode_edge_gix_2d" gist (edge)
    "treenode_edge_project_id_index" btree (project_id)


Option 1: &&&
=============

-- Returned Nodes: 1327
-- Time: 105 ms (repeated call: 60 ms)
-- Region: 41819.31354090536 81255.64336110713 102850 to 59868.26425961124 88903.95239000155 102900

SELECT te.id
FROM treenode_edge te
WHERE te.edge &&& 'LINESTRINGZ(41819.31354090536 81255.64336110713 102850, 59868.26425961124 88903.95239000155 102900)'

                                                                          QUERY PLAN                                                                           
---------------------------------------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on treenode_edge te  (cost=19.71..1666.64 rows=425 width=8) (actual time=56.202..57.276 rows=1327 loops=1)
   Recheck Cond: (edge &&& '010200008002000000CFEF86086A6BE4402A04354B7AD6F34000000000201CF9407E92D074883BED405B4CFD3C7FB4F54000000000401FF940'::geometry)
   ->  Bitmap Index Scan on treenode_edge_gix  (cost=0.00..19.61 rows=425 width=0) (actual time=56.063..56.063 rows=1327 loops=1)
         Index Cond: (edge &&& '010200008002000000CFEF86086A6BE4402A04354B7AD6F34000000000201CF9407E92D074883BED405B4CFD3C7FB4F54000000000401FF940'::geometry)
 Total runtime: 57.365 ms


Option 2: ST_3DDWithin
======================

-- Returned Nodes: 885
-- Time: 3282 ms (repeated call: 2462 ms)
-- Region: 41819.31354090536 81255.64336110713 102850 to 59868.26425961124 88903.95239000155 102900

SELECT te.id
FROM treenode_edge te
WHERE ST_3DDWithin(te.edge, ST_MakePolygon(ST_GeomFromText('LINESTRING(
   41819.31354090536 81255.64336110713 102825,
   59868.26425961124 81255.64336110713 102925,
   59868.26425961124 88903.95239000155 102925,
   41819.31354090536 88903.95239000155 102825,
   41819.31354090536 81255.64336110713 102825)')), 25);

                                                                                                                                   QUERY PLAN                                                                                                                                                                                                                                                                                                                                      
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on treenode_edge te  (cost=56821.84..583286.09 rows=80687 width=8) (actual time=205.092..2507.810 rows=885 loops=1)
   Recheck Cond: (edge && '01030000800100000005000000CFEF86084A68E4402A04354BEAD4F340000000000019F940CFEF86084A68E4405B4CFD3C0FB6F540000000000019F9407E92D074A83EED405B4CFD3C0FB6F540000000006022F9407E92D074A83EED402A04354BEAD4F340000000006022F940CFEF86084A68E4402A04354BEAD4F340000000000019F940'::geometry)
   Filter: (('01030000800100000005000000CFEF86086A6BE4402A04354B7AD6F34000000000901AF9407E92D074883BED402A04354B7AD6F34000000000D020F9407E92D074883BED405B4CFD3C7FB4F54000000000D020F940CFEF86086A6BE4405B4CFD3C7FB4F54000000000901AF940CFEF86086A6BE4402A04354B7AD6F34000000000901AF940'::geometry && st_expand(edge, 25::double precision)) AND _st_3ddwithin(edge, '01030000800100000005000000CFEF86086A6BE4402A04354B7AD6F34000000000901AF9407E92D074883BED402A04354B7AD6F34000000000D020F9407E92D074883BED405B4CFD3C7FB4F54000000000D020F940CFEF86086A6BE4405B4CFD3C7FB4F54000000000901AF940CFEF86086A6BE4402A04354B7AD6F34000000000901AF940'::geometry, 25::double precision))
   Rows Removed by Filter: 1224193
   ->  Bitmap Index Scan on treenode_edge_gix_2d  (cost=0.00..56801.67 rows=1210300 width=0) (actual time=176.023..176.023 rows=1225078 loops=1)
         Index Cond: (edge && '01030000800100000005000000CFEF86084A68E4402A04354BEAD4F340000000000019F940CFEF86084A68E4405B4CFD3C0FB6F540000000000019F9407E92D074A83EED405B4CFD3C0FB6F540000000006022F9407E92D074A83EED402A04354BEAD4F340000000006022F940CFEF86084A68E4402A04354BEAD4F340000000000019F940'::geometry)
 Total runtime: 2507.927 ms