Postgresql simple query on moderately large table is extremely slow

I have a PostgresSQL DB on Google SQL :

4 vCPUS
15 GB RAM
55 GB SSD

The relevant schema is :

postgres=> \d device;
                        Table "public.device"
        Column          |          Type           | Collation | Nullable | Default
-------------------------+-------------------------+-----------+----------+---------
id                      | uuid                    |           | not null |
brand                   | character varying(255)  |           |          |
model                   | character varying(255)  |           |          |
serialnumber            | character varying(255)  |           |          |
[...]
Indexes:
    "device_pkey" PRIMARY KEY, btree (id)
[...]
Referenced by:
    TABLE "application" CONSTRAINT "fk_application_device_id_device" FOREIGN KEY (device_id) REFERENCES device(id) ON DELETE CASCADE
[...]

postgres=> \d application;
                        Table "public.application"
          Column           |          Type          | Collation | Nullable | Default
----------------------------+------------------------+-----------+----------+---------
id                         | uuid                   |           | not null |
device_id                  | uuid                   |           | not null |
packagename                | character varying(255) |           |          |
versionname                | character varying(255) |           |          |
[...]
Indexes:
    "application_pkey" PRIMARY KEY, btree (id)
    "application_device_id_packagename_key" UNIQUE CONSTRAINT, btree (device_id, packagename)
Foreign-key constraints:
    "fk_application_device_id_device" FOREIGN KEY (device_id) REFERENCES device(id) ON DELETE CASCADE
[...]

Volumetry :

device table: 16k rows
application: 3.6M rows

When trying something as simple as:

select count(id) from application;

The query took 900 seconds (sic) to count those 3.6M rows.

Here is the execution plan:

postgres=> explain analyze select count(id) from application;
                                                                            QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------------------------------
Finalize Aggregate  (cost=1245180.18..1245180.19 rows=1 width=8) (actual time=311470.250..311496.933 rows=1 loops=1)
->  Gather  (cost=1245179.96..1245180.17 rows=2 width=8) (actual time=311470.225..311496.919 rows=3 loops=1)
        Workers Planned: 2
        Workers Launched: 2
        ->  Partial Aggregate  (cost=1244179.96..1244179.97 rows=1 width=8) (actual time=311463.287..311463.289 rows=1 loops=3)
            ->  Parallel Seq Scan on application  (cost=0.00..1234885.77 rows=3717677 width=16) (actual time=79.783..311296.505 rows=1202169 loops=3)
Planning Time: 0.083 ms
Execution Time: 311497.021 ms
(8 rows)

It seems like everything (like keys and indexes) is correctly set, so what could be the reason for this simple query to take so long ?

Solution

You have to look deeper to determine the cause:

turn on track_io_timing in the PostgreSQL configuration so that you can see how long I/O takes
use EXPLAIN (ANALYZE, BUFFERS) to see how many 8kB blocks are touched

If there number of blocks is very high, your table is bloated (consists mostly of nothing), and the sequential scan takes so long because it has to read all that empty space. VACUUM (FULL) can help with that.

If the block count is as you would expect, the problem is that your storage is too slow.