2

I have a table of US mailing addresses with approximately 5 million rows. I want to form clusters of addresses located within about 10km of each other. I have a GIST index on my geometry point column and I have clustered this table.

Following is the migration that defines this table using the Elixir language's Ecto library:

  def change do
    execute "CREATE EXTENSION IF NOT EXISTS postgis"

    create table(:addresses) do
      add :line1, :string, null: false
      add :line2, :string
      add :city_id, references(:cities, on_delete: :delete_all), null: false
      add :zip, :string
      add :geom, :geometry, null: false

      timestamps()
    end

    create unique_index(:addresses, [:line1, :line2, :zip])
    execute "CREATE INDEX adddress_geom_idx ON addresses USING GIST(geom)"
    execute "CLUSTER address_geom_idx ON addresses"
  end
end

I've tried the following queries, but they take pretty long. I waited over an hour for each of them before giving up.

select addresses.id, ST_ClusterDBSCAN(addresses.geom, eps:= 10000, minpoints := 5) 
 over() 
from addresses;

select addresses.id, ST_ClusterDBSCAN(addresses.geom, eps:= 10000, minpoints := 5) 
 over (partition by city_id) 
from addresses;

select addresses.id, ST_ClusterDBSCAN(addresses.geom, eps:= 10000, minpoints := 5) 
 over (partition by city_id) 
from addresses, cities, states 
where addresses.city_id = cities.id 
 and cities.state_id = states.id 
 and states.id = 2;

select ST_ClusterWithin(geom, 10) 
from addresses;

The following query completed in about 8 hours:

geography_dev=# explain analyze select addresses.id, ST_ClusterDBSCAN(addresses.geom, eps:= 10000, minpoints := 5) over (partition by city_id) from addresses;
                                                              QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------
 WindowAgg  (cost=1004336.37..127949983.08 rows=5074781 width=20) (actual time=2366.919..28876253.674 rows=5074781 loops=1)
   ->  Sort  (cost=1004336.37..1017023.32 rows=5074781 width=48) (actual time=2360.696..2897.855 rows=5074781 loops=1)
         Sort Key: city_id
         Sort Method: external merge  Disk: 273144kB
         ->  Seq Scan on addresses  (cost=0.00..126913.81 rows=5074781 width=48) (actual time=150.873..1031.127 rows=5074781 loops=1)
 Planning Time: 9.972 ms
 JIT:
   Functions: 9
   Options: Inlining true, Optimization true, Expressions true, Deforming true
   Timing: Generation 0.809 ms, Inlining 41.420 ms, Optimization 58.698 ms, Emission 48.866 ms, Total 149.793 ms
 Execution Time: 28876638.059 ms
(11 rows)

Are all of these queries ignoring the index? Also, I have no idea about reasonable expectations for completion times for queries like this for tables like this for various dataset sizes. I know that DBSCAN is a slow algorithm, but I have no intuition about how slow that will be for datasets of various sizes. Is 5m an unreasonable number of rows for DBSCAN, or for the ST_ClusterWithin function for that matter?

5
  • 1
    Just to be sure: are those geometries projected (what CRS)?
    – geozelot
    Dec 17, 2021 at 8:27
  • The doc says to run analyze after a cluster command
    – JGH
    Dec 17, 2021 at 14:55
  • @geozelot I'm not well-informed on GIS yet; I think you're asking for the SRID? In that case, it is 4326
    – vaer-k
    Dec 17, 2021 at 16:52
  • @JGH thank you for the tip. I've done so
    – vaer-k
    Dec 17, 2021 at 16:53
  • 1
    That's what I wanted to know. And that's the foremost issue: as with basically all ST functions, whenever they accept a unit parameter, that unit relates to the units of the underlying CRS - so the given 10000 are treated as degrees, thus for each point in that table the algorithm fetches and processes all 5M records! Obviously, no index will be used then. Changing that will help, at least with the speed - I have a more thorough answer half done on scaling DBSCAN, and why you will likely still be disappointed by the results, even with the translated eps distance. But no time.
    – geozelot
    Dec 17, 2021 at 17:40

1 Answer 1

2

ST_ClusterDBSCAN and ST_ClusterWithin are run in-memory. So they don't use a spatial index. And using the Postgres CLUSTER won't affect performance, since the entire dataset is read into memory anyway.

I'm not aware of anything else that can done to improve performance, other than reducing the size of the input (as you have done by partitioning by city).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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