Postgresql update performance?

Question

We have a table which stores about 20 million records:

                     Table "public.tbl"
         Column          |            Type             | Modifiers
-------------------------+-----------------------------+-----------
 id                      | uuid                        | not null
 a                       | timestamp without time zone | not null
 b                       | timestamp without time zone | not null
 c                       | timestamp without time zone | not null
 d                       | timestamp without time zone |
 e                       | integer                     |
 f                       | integer                     |
 g                       | uuid                        |
 h                       | timestamp without time zone | not null
 j                       | uuid                        | not null
 k                       | uuid                        | not null
 l                       | character varying(32)       |
 m                       | boolean                     | not null
 n                       | boolean                     |
 o                       | boolean                     |
Indexes:
    "pk_table" PRIMARY KEY, btree (id)
    "idx_table_k" btree k)
    "idx_table_j" btree (j)
Foreign-key constraints:
    "fk_table_k" FOREIGN KEY (k) REFERENCES z(id)
    "fk_table_j" FOREIGN KEY (j) REFERENCES y(id)
Referenced by:
<....>


 select count(*) from tbl;
  count   
----------
 20594896
(1 row)


  oid  | table_schema | table_name | row_estimate | total_bytes | index_bytes | toast_bytes | table_bytes | total |  index  | toast |  table
-------+--------------+------------+--------------+-------------+-------------+-------------+-------------+-------+---------+-------+---------
 16532 | public       | tbl  |  2.09275e+07 | 13775568896 |  5316452352 |             |  8459116544 | 13 GB | 5070 MB |       | 8067 MB

And we wanted to run a single query:

update tbl set o=false where o is null;

On a slow testing Google Cloud Sql Machine (1vcpu, 3.75mb ram, 100gb storage) this query took ~3 hours.

The best we could get to was ~23 minutes by increasing disk throughput. Logs were also full of message like these:

[3091] HINT:  Consider increasing the configuration parameter "max_wal_size".
[3091] LOG:  checkpoints are occurring too frequently (5 seconds apart)
[3091] HINT:  Consider increasing the configuration parameter "max_wal_size".
[3091] LOG:  checkpoints are occurring too frequently (5 seconds apart)
[3091] HINT:  Consider increasing the configuration parameter "max_wal_size".
[3091] LOG:  checkpoints are occurring too frequently (5 seconds apart)
[3091] HINT:  Consider increasing the configuration parameter "max_wal_size".

Since we cannot tune those params on CloudSQL, we've launched a simple Debian based machine (4 vCPUs, 15 GB, 500GB storage) with PG9.6 By setting max_wal_size to 20GB and checkpoint_timeout to 50 min we got down to ~19 minutes

explain analyze update tbl set j=false where j is null;
QUERY PLAN     

 Update on tbl  (cost=0.00..1720212.95 rows=59869756 width=133) (actual time=1193435.444..1193435.444 rows=0 
loops=1)
   ->  Seq Scan on tbl  (cost=0.00..1720212.95 rows=59869756 width=133) (actual time=0.039..69547.781 rows=20
142544 loops=1)
         Filter: (j IS NULL)
         Rows Removed by Filter: 452352
 Planning time: 0.725 ms
 Execution time: 1193435.523 ms
(6 rows)

Looking at top cpu is at ~20% iowait so I guess we are hitting iops or disk throughput limit.

Anyway to improve this, or how to troubleshoot that? Or is this as good as it gets?