How does ST_ClusterWitihin and ST_ClusterDBSCAN scale?

Question

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?

Answer 1

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).