Slow query, possibly not using index

I have this table:

CREATE TABLE media.block (

id uuid NOT NULL,

"size" int8 NOT NULL,

nrefs int8 NOT NULL DEFAULT 0,

block bytea NOT NULL,

hs256 bytea NOT NULL,

CONSTRAINT block_pkey PRIMARY KEY (id),

CONSTRAINT chk_nrefs CHECK ((nrefs >= 0))

)

WITH (

toast_tuple_target=8160

)

TABLESPACE data_slow

;

alter table media.block alter column block set storage main;

alter table media.block alter column hs256 set storage main;

CREATE INDEX idx_block_unused ON media.block USING btree (id) WHERE (nrefs
= 0);

CREATE UNIQUE INDEX uidx_block_hs256 ON media.block USING btree (hs256);

Number of rows in this table is about 40M, and most of the rows occupy a
full 8K block (in most cases, the "block" field contains 7500 bytes).

The idx_block_unused index should be used to find blocks that are unused,
so they can be deleted at some point.

The idx_block_unused index is less than 400MB:

SELECT i.relname "Table Name",indexrelname "Index Name",

pg_size_pretty(pg_total_relation_size(relid)) As "Total Size",

pg_size_pretty(pg_indexes_size(relid)) as "Total Size of all Indexes",

pg_size_pretty(pg_relation_size(relid)) as "Table Size",

pg_size_pretty(pg_relation_size(indexrelid)) "Index Size",

reltuples::bigint "Estimated table row count"

FROM pg_stat_all_indexes i JOIN pg_class c ON i.relid=c.oid

where i.relid ='media.block'::regclass

Table Name|Index Name |Total Size|Total Size of all Indexes|Table
Size|Index Size|Estimated table row count|
----------+----------------+----------+-------------------------+----------+----------+-------------------------+
block |block_pkey |352 GB |5584 MB |347 GB
|1986 MB | 38958848|
block |uidx_block_hs256|352 GB |5584 MB |347 GB
|3226 MB | 38958848|
block |idx_block_unused|352 GB |5584 MB |347 GB
|372 MB | 38958848|

If I try to select a single unused block this way:

explain analyze select id from media.block b where nrefs =0 limit 1

then it runs for more than 10 minutes (I'm not sure how long, I cancelled
the query after 10 minutes).

If I run this without analyze:

explain select id from media.block b where nrefs =0 limit 1

QUERY PLAN
|
-----------------------------------------------------------------------------------------------+
Limit (cost=0.38..0.76 rows=1 width=16)
|
-> Index Only Scan using idx_block_unused on block b (cost=0.38..869.83
rows=2274 width=16)|

I believe it is not actually using the index, because reading a single
(random?) entry from an index should not run for >10 minutes.

What am I doing wrong?

Thank you,

Laszlo