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

[Tom Kazimiers]

Hi Sandro,

Thanks for your input!

On Wed, Jul 01, 2015 at 11:06:25AM +0200, Sandro Santilli wrote:
> On Tue, Jun 30, 2015 at 11:18:59PM -0400, Tom Kazimiers wrote:
> > 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.
> 
> The ST_3DDWithin function is currently _not_ using &&& operator.
> It may actually be a good idea to make it do so.
> In any case, you can manually mix the two. What speed do you get then ?
> 
> The query should then be:
> 
> SELECT te.id
> FROM treenode_edge te
> WHERE te.edge &&& 'LINESTRINGZ(41819.31354090536 81255.64336110713 102850, 59868.26425961124 88903.95239000155 102900)
>   AND _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);

I just tried your suggestion and the timing is the same as the &&&
query, with fewer nodes returned (a good thing). So it is indeed the
best of both my initial queries combined. With your query (there is a '
missing at the end of the first WHERE line), I see these results:

Nodes: 884 (compared to &&& alone: 1327, ST_3DDWithin alone: 885)
Time: 106 ms (61 ms) (compared to &&& alone: 105 ms (60 ms),
      ST_3DDWithin alone: 3282 ms (2462 ms))

The query plan is attached to the end of this mail. It looks much
better, without any nested loops, using the n-d index only (I get the
same results with the 2D index dropped). I'll have to test with other
typical queries, but this already is quite an improvement---thanks!

Still, I'd be happy to hear more suggestions if there is more I could
change to improve query time.

Best,
Tom


The query plan of Sandro's query on my server:
                                                                                                                                                                 QUERY PLAN                                                                                                                                                                  
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on treenode_edge te  (cost=19.64..1772.82 rows=142 width=8) (actual time=56.753..59.307 rows=884 loops=1)
   Recheck Cond: (edge &&& '010200008002000000CFEF86086A6BE4402A04354B7AD6F34000000000201CF9407E92D074883BED405B4CFD3C7FB4F54000000000401FF940'::geometry)
   Filter: _st_3ddwithin(edge, '01030000800100000005000000CFEF86086A6BE4402A04354B7AD6F34000000000901AF9407E92D074883BED402A04354B7AD6F34000000000D020F9407E92D074883BED405B4CFD3C7FB4F54000000000D020F940CFEF86086A6BE4405B4CFD3C7FB4F54000000000901AF940CFEF86086A6BE4402A04354B7AD6F34000000000901AF940'::geometry, 25::double precision)
   Rows Removed by Filter: 443
   ->  Bitmap Index Scan on treenode_edge_gix  (cost=0.00..19.61 rows=425 width=0) (actual time=56.579..56.579 rows=1327 loops=1)
         Index Cond: (edge &&& '010200008002000000CFEF86086A6BE4402A04354B7AD6F34000000000201CF9407E92D074883BED405B4CFD3C7FB4F54000000000401FF940'::geometry)
 Total runtime: 59.370 ms


-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 819 bytes
Desc: not available
URL: <http://lists.osgeo.org/pipermail/postgis-users/attachments/20150701/b32cf47c/attachment.pgp>