16

I can't get PostGIS 2.1 running on PostgreSQL 9.3.5 to use a spatial index even for the simplest queries. The whole dataset is 8 million points (population count grid from here). The table is created as

CREATE TABLE points (
    population DOUBLE PRECISION NOT NULL,
    location GEOGRAPHY(4326, POINT) NOT NULL
)
CREATE INDEX points_gix ON points USING GIST(location);

The queries are as simple as they get

SELECT SUM(population)
FROM points
WHERE ST_Distance(
    location,
    ST_GeographyFromText('SRID=4326; POINT(0 0)')
) < 1000

PostgreSQL always uses Seq scan for it, I've tried a subset with 10000 points - still Seq scan. Any ideas?

2
  • 3
    You don't use any function that can use the index. Use st_dwithin instead. Then the fuction will first do an index scan. Nov 30, 2014 at 18:39
  • Think about what your query is doing -- compute distance from each point in a table to a fixed point -- and you'll understand why no index can be used. Instead use an operator which can use an index, like ST_DWithin
    – Vince
    Nov 30, 2014 at 18:40

2 Answers 2

24

ST_Distance() actually calculates the distance between all the pairs of points, so, as such, no index could be used. So your query will do a sequence scan and then choose those geometries that are less than the distance you specify away. You are looking for ST_DWithin, which does use an index.

SELECT SUM(population) FROM points 
WHERE ST_DWithin(location, ST_GeographyFromText('SRID=4326; POINT(0 0)'), 1000);

ST_Distance() is more useful for ordering results, often in conjunction with ORDER BY and/or LIMIT, that have been obtained with queries that do use an index.

6
  • 1
    Thanks. I really should read docs before asking questions.
    – synapse
    Dec 1, 2014 at 19:22
  • 1
    WOW! THANK YOU! You just "accelerated" my slow query like 100x fold or more due to changing st_distance to st_dwithin. (I say "accelerated" because this should never have happened in the first place had I been more careful) Dec 30, 2017 at 11:18
  • 1
    @HendyIrawan. You are welcome. It is an easy mistake to make. Dec 30, 2017 at 12:01
  • @JohnPowellakaBarça I added another optimization (although very lossy, I added an answer for my case) but you did point me in the right direction, thanks. Jan 1, 2018 at 16:51
  • The ST_DWithin even not using my GIST index, it is doing Parallel Seq scan Jan 18, 2021 at 7:59
6

As @JohnPowellakaBarça said ST_DWithin() is the way to go when you want correctness.

However in my case I only want a rough estimation so even ST_DWithin() was too expensive (in query cost) for my needs. I used && and ST_Expand(box2d) (don't mistake this with the geometry version) instead. Example:

SELECT * FROM profile
  WHERE
    address_point IS NOT NULL AND
    address_point && CAST(ST_Expand(CAST(ST_GeomFromText(:point) AS box2d), 0.5) AS geometry;

What will be immediately obvious is that we're dealing with degrees instead of meters, and using bounding box instead of circle in a spheroid. For my use case, this cuts down from 24 ms to just 2 ms (locally in SSD). However for my production database in AWS RDS PostgreSQL with concurrent connections and hardly-generous IOPS quotas (100 IOPS), the original ST_DWithin() query spends too much IOPS and can execute over 2000 ms and much worse when IOPS quota is depleted.

This is not for everybody but in case you can sacrifice some accuracy for speed (or to save IOPS), then this approach may be for you. As you can see in the query plans below, ST_DWithin still requires a spatial Filter inside the Bitmap Heap Scan in addition to Recheck Cond, while && on a box geometry does not need a Filter and only uses Recheck Cond.

I also noticed that IS NOT NULL matters, without it you'll be left with worse query plan. It seems the GIST index is not "smart enough" for this. (of course it's not needed if your column is NOT NULL, in my case it's NULLable)

20000 row table, ST_DWithin(geography, geography, 100000, FALSE) on AWS RDS 512 MB RAM with 300 IOPS:

Aggregate  (cost=4.61..4.62 rows=1 width=8) (actual time=2011.358..2011.358 rows=1 loops=1)
  ->  Bitmap Heap Scan on matchprofile  (cost=2.83..4.61 rows=1 width=0) (actual time=1735.025..2010.635 rows=1974 loops=1)
        Recheck Cond: (((address_point IS NOT NULL) AND (address_point && '0101000020E6100000744694F606E75A40D49AE61DA7A81BC0'::geography)) OR ((hometown_point IS NOT NULL) AND (hometown_point && '0101000020E6100000744694F606E75A40D49AE61DA7A81BC0'::geography)))
        Filter: (((status)::text = 'ACTIVE'::text) AND ((gender)::text = 'MALE'::text) AND (((address_point IS NOT NULL) AND (address_point && '0101000020E6100000744694F606E75A40D49AE61DA7A81BC0'::geography) AND ('0101000020E6100000744694F606E75A40D49AE61DA7A81BC0'::geography && _st_expand(address_point, '100000'::double precision)) AND _st_dwithin(address_point, '0101000020E6100000744694F606E75A40D49AE61DA7A81BC0'::geography, '100000'::double precision, false)) OR ((hometown_point IS NOT NULL) AND (hometown_point && '0101000020E6100000744694F606E75A40D49AE61DA7A81BC0'::geography) AND ('0101000020E6100000744694F606E75A40D49AE61DA7A81BC0'::geography && _st_expand(hometown_point, '100000'::double precision)) AND _st_dwithin(hometown_point, '0101000020E6100000744694F606E75A40D49AE61DA7A81BC0'::geography, '100000'::double precision, false))))
        Rows Removed by Filter: 3323
        Heap Blocks: exact=7014
        ->  BitmapOr  (cost=2.83..2.83 rows=1 width=0) (actual time=1716.425..1716.425 rows=0 loops=1)
              ->  Bitmap Index Scan on ik_matchprofile_address_point  (cost=0.00..1.42 rows=1 width=0) (actual time=1167.698..1167.698 rows=16086 loops=1)
                    Index Cond: ((address_point IS NOT NULL) AND (address_point && '0101000020E6100000744694F606E75A40D49AE61DA7A81BC0'::geography))
              ->  Bitmap Index Scan on ik_matchprofile_hometown_point  (cost=0.00..1.42 rows=1 width=0) (actual time=548.723..548.723 rows=7846 loops=1)
                    Index Cond: ((hometown_point IS NOT NULL) AND (hometown_point && '0101000020E6100000744694F606E75A40D49AE61DA7A81BC0'::geography))
Planning time: 47.366 ms
Execution time: 2011.429 ms

20000 row table, && and ST_Expand(box2d) on AWS RDS 512 MB RAM with 300 IOPS:

Aggregate  (cost=3.85..3.86 rows=1 width=8) (actual time=584.346..584.346 rows=1 loops=1)
  ->  Bitmap Heap Scan on matchprofile  (cost=2.83..3.85 rows=1 width=0) (actual time=555.048..584.083 rows=1154 loops=1)
        Recheck Cond: (((address_point IS NOT NULL) AND (address_point && '0103000020E61000000100000005000000744694F606C75A40D49AE61DA7A81DC0744694F606C75A40D49AE61DA7A819C0744694F606075B40D49AE61DA7A819C0744694F606075B40D49AE61DA7A81DC0744694F606C75A40D49AE61DA7A81DC0'::geography)) OR ((hometown_point IS NOT NULL) AND (hometown_point && '0103000020E61000000100000005000000744694F606C75A40D49AE61DA7A81DC0744694F606C75A40D49AE61DA7A819C0744694F606075B40D49AE61DA7A819C0744694F606075B40D49AE61DA7A81DC0744694F606C75A40D49AE61DA7A81DC0'::geography)))
        Filter: (((status)::text = 'ACTIVE'::text) AND ((gender)::text = 'MALE'::text))
        Rows Removed by Filter: 555
        Heap Blocks: exact=3812
        ->  BitmapOr  (cost=2.83..2.83 rows=1 width=0) (actual time=553.091..553.091 rows=0 loops=1)
              ->  Bitmap Index Scan on ik_matchprofile_address_point  (cost=0.00..1.42 rows=1 width=0) (actual time=413.074..413.074 rows=4850 loops=1)
                    Index Cond: ((address_point IS NOT NULL) AND (address_point && '0103000020E61000000100000005000000744694F606C75A40D49AE61DA7A81DC0744694F606C75A40D49AE61DA7A819C0744694F606075B40D49AE61DA7A819C0744694F606075B40D49AE61DA7A81DC0744694F606C75A40D49AE61DA7A81DC0'::geography))
              ->  Bitmap Index Scan on ik_matchprofile_hometown_point  (cost=0.00..1.42 rows=1 width=0) (actual time=140.014..140.014 rows=3100 loops=1)
                    Index Cond: ((hometown_point IS NOT NULL) AND (hometown_point && '0103000020E61000000100000005000000744694F606C75A40D49AE61DA7A81DC0744694F606C75A40D49AE61DA7A819C0744694F606075B40D49AE61DA7A819C0744694F606075B40D49AE61DA7A81DC0744694F606C75A40D49AE61DA7A81DC0'::geography))
Planning time: 0.673 ms
Execution time: 584.386 ms

Again with simpler query:

20000 row table, ST_DWithin(geography, geography, 100000, FALSE) on AWS RDS 512 MB RAM with 300 IOPS:

Aggregate  (cost=4.60..4.61 rows=1 width=8) (actual time=36.448..36.448 rows=1 loops=1)
  ->  Bitmap Heap Scan on matchprofile  (cost=2.83..4.60 rows=1 width=0) (actual time=7.694..35.545 rows=2982 loops=1)
        Recheck Cond: (((address_point IS NOT NULL) AND (address_point && '0101000020E6100000744694F606E75A40D49AE61DA7A81BC0'::geography)) OR ((hometown_point IS NOT NULL) AND (hometown_point && '0101000020E6100000744694F606E75A40D49AE61DA7A81BC0'::geography)))
        Filter: (((address_point IS NOT NULL) AND (address_point && '0101000020E6100000744694F606E75A40D49AE61DA7A81BC0'::geography) AND ('0101000020E6100000744694F606E75A40D49AE61DA7A81BC0'::geography && _st_expand(address_point, '100000'::double precision)) AND _st_dwithin(address_point, '0101000020E6100000744694F606E75A40D49AE61DA7A81BC0'::geography, '100000'::double precision, true)) OR ((hometown_point IS NOT NULL) AND (hometown_point && '0101000020E6100000744694F606E75A40D49AE61DA7A81BC0'::geography) AND ('0101000020E6100000744694F606E75A40D49AE61DA7A81BC0'::geography && _st_expand(hometown_point, '100000'::double precision)) AND _st_dwithin(hometown_point, '0101000020E6100000744694F606E75A40D49AE61DA7A81BC0'::geography, '100000'::double precision, true)))
        Rows Removed by Filter: 2322
        Heap Blocks: exact=2947
        ->  BitmapOr  (cost=2.83..2.83 rows=1 width=0) (actual time=7.197..7.197 rows=0 loops=1)
              ->  Bitmap Index Scan on ik_matchprofile_address_point  (cost=0.00..1.41 rows=1 width=0) (actual time=5.265..5.265 rows=5680 loops=1)
                    Index Cond: ((address_point IS NOT NULL) AND (address_point && '0101000020E6100000744694F606E75A40D49AE61DA7A81BC0'::geography))
              ->  Bitmap Index Scan on ik_matchprofile_hometown_point  (cost=0.00..1.41 rows=1 width=0) (actual time=1.930..1.930 rows=2743 loops=1)
                    Index Cond: ((hometown_point IS NOT NULL) AND (hometown_point && '0101000020E6100000744694F606E75A40D49AE61DA7A81BC0'::geography))
Planning time: 0.479 ms
Execution time: 36.512 ms

20000 row table, && and ST_Expand(box2d) on AWS RDS 512 MB RAM with 300 IOPS:

Aggregate  (cost=3.84..3.85 rows=1 width=8) (actual time=6.263..6.264 rows=1 loops=1)
  ->  Bitmap Heap Scan on matchprofile  (cost=2.83..3.84 rows=1 width=0) (actual time=4.295..5.864 rows=1711 loops=1)
        Recheck Cond: (((address_point IS NOT NULL) AND (address_point && '0103000020E61000000100000005000000744694F606C75A40D49AE61DA7A81DC0744694F606C75A40D49AE61DA7A819C0744694F606075B40D49AE61DA7A819C0744694F606075B40D49AE61DA7A81DC0744694F606C75A40D49AE61DA7A81DC0'::geography)) OR ((hometown_point IS NOT NULL) AND (hometown_point && '0103000020E61000000100000005000000744694F606C75A40D49AE61DA7A81DC0744694F606C75A40D49AE61DA7A819C0744694F606075B40D49AE61DA7A819C0744694F606075B40D49AE61DA7A81DC0744694F606C75A40D49AE61DA7A81DC0'::geography)))
        Heap Blocks: exact=1419
        ->  BitmapOr  (cost=2.83..2.83 rows=1 width=0) (actual time=4.122..4.122 rows=0 loops=1)
              ->  Bitmap Index Scan on ik_matchprofile_address_point  (cost=0.00..1.41 rows=1 width=0) (actual time=3.018..3.018 rows=1693 loops=1)
                    Index Cond: ((address_point IS NOT NULL) AND (address_point && '0103000020E61000000100000005000000744694F606C75A40D49AE61DA7A81DC0744694F606C75A40D49AE61DA7A819C0744694F606075B40D49AE61DA7A819C0744694F606075B40D49AE61DA7A81DC0744694F606C75A40D49AE61DA7A81DC0'::geography))
              ->  Bitmap Index Scan on ik_matchprofile_hometown_point  (cost=0.00..1.41 rows=1 width=0) (actual time=1.102..1.102 rows=980 loops=1)
                    Index Cond: ((hometown_point IS NOT NULL) AND (hometown_point && '0103000020E61000000100000005000000744694F606C75A40D49AE61DA7A81DC0744694F606C75A40D49AE61DA7A819C0744694F606075B40D49AE61DA7A819C0744694F606075B40D49AE61DA7A81DC0744694F606C75A40D49AE61DA7A81DC0'::geography))
Planning time: 0.399 ms
Execution time: 6.306 ms
1
  • 1
    Good write up and interesting. Jan 1, 2018 at 17:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.