# Finding closest line given 2 points using PostGIS?

I have a table t that contains a column `line_positions` which is of type line. Given 2 points I want to find the closest line that is close enough (less than 10km) and that does not pass too close to a point I want to avoid (20km minimum). Currently I use

``````SELECT t.*
FROM path t
WHERE
ST_DWithin(ST_GeographyFromText('Point(69.835 22.596)'), t.line_positions, 10000, FALSE)  AND
ST_DWithin(ST_GeographyFromText('Point(69.856 22.519)'), t.line_positions, 10000, false) AND
NOT ST_DWithin(ST_GeographyFromText('Point(-79.804 9.141)'), t.line_positions, 20000, false)
ORDER BY
ST_Distance(ST_GeographyFromText('Point(69.835 22.576)'), t.line_positions, false) +
ST_Distance(ST_GeographyFromText('Point(69.856 22.519)'), t.line_positions, false)
ASC
LIMIT 1
``````

There is a gist index `ix_path_line_positions` on the line_positions column.

It works but slow, between 3s and 30s for only 100000 rows in t.

explain analyze gives :

``````Limit  (cost=9.95..9.95 rows=1 width=1432) (actual time=21729.253..21729.254 rows=1 loops=1)
->  Sort  (cost=9.95..9.95 rows=1 width=1432) (actual time=21729.251..21729.251 rows=1 loops=1)
Sort Key: ((_st_distance('0101000020E61000003D0AD7A370755140FA7E6ABC74933640'::geography, line_positions, '0'::double precision, false) + _st_distance('0101000020E6100000105839B4C8765140BE9F1A2FDD843640'::geography, line_positions, '0'::double precision, false)))
Sort Method: top-N heapsort  Memory: 26kB"
->  Index Scan using ix_path_line_positions on path t  (cost=0.28..9.94 rows=1 width=1432) (actual time=93.490..21710.562 rows=690 loops=1)
Index Cond: ((line_positions && '0101000020E61000003D0AD7A3707551407F6ABC7493983640'::geography) AND (line_positions && '0101000020E6100000105839B4C8765140BE9F1A2FDD843640'::geography))
Filter: (('0101000020E61000003D0AD7A3707551407F6ABC7493983640'::geography && _st_expand(line_positions, '10000'::double precision)) AND ('0101000020E6100000105839B4C8765140BE9F1A2FDD843640'::geography && _st_expand(line_positions, '10000'::double precision)) AND _st_dwithin('0101000020E61000003D0AD7A3707551407F6ABC7493983640'::geography, line_positions, '10000'::double precision, false) AND _st_dwithin('0101000020E6100000105839B4C8765140BE9F1A2FDD843640'::geography, line_positions, '10000'::double precision, false) AND ((NOT ('0101000020E6100000FA7E6ABC74F353C0D578E92631482240'::geography && _st_expand(line_positions, '20000'::double precision))) OR (NOT (line_positions && '0101000020E6100000FA7E6ABC74F353C0D578E92631482240'::geography)) OR (NOT _st_dwithin('0101000020E6100000FA7E6ABC74F353C0D578E92631482240'::geography, line_positions, '20000'::double precision, false))))
Rows Removed by Filter: 15365
Planning time: 0.491 ms
Execution time: 21729.321 ms
``````

How could I improve it ? Using geometry calculation instead (but my track could span several thousands km, will the computed distances correct) ? Using <-> KNN operator (but since I order on the sum of 2 distances, it does not seem to use the gist index anyway) ?

• You can try to increase work_mem parameter, before executing the code. E.g. `SET work_mem TO '200MB';` Aug 18 '17 at 13:48

Are the two given points always within 10km of each other. If so you could try making the two points a line and performing one ST_DWithin instead of two. That may improve things slightly.

``````SELECT t.*
FROM path t
WHERE
ST_DWithin(ST_GeomFromText('LINESTRING(69.835 22.596,69.856 22.519)'), t.line_positions, 10000, FALSE)
NOT ST_DWithin(ST_GeographyFromText('Point(-79.804 9.141)'), t.line_positions, 20000, false)
ORDER BY
ST_Distance(ST_GeographyFromText('Point(69.835 22.576)'), t.line_positions, false) +
ST_Distance(ST_GeographyFromText('Point(69.856 22.519)'), t.line_positions, false)
ASC
LIMIT 1
``````
• No, the 2 points are not within 10km of each other, they can be thousand km away. The constraint are that both of less than 10km away from the line, but it could really far away because the lines spanned thousand km. Oct 2 '17 at 16:47