TIL: a partial index is usually the answer

create index ... where country_k is not null indexes only the rows you query, which on a mostly-null column is a fraction of the size and strictly faster.