How to make a proper complex index?

Question

PostgreSQL

There is a rather large table (200M+) that has three columns of interest:
update_date timestamptz
num_status int
n_flag int

n_flag can be 0..5
num_status 0..20
update_date is when the record was updated.

We need to find the oldest record, where n_flag=0 and num_status>=10.

Query
select * from table1 where n_flag=0 and num_status>=10 order by update_date asc limit 1;
Very long time.

select * from table1 where num_status>=10 order by update_date asc limit 1; - quickly
select * from table1 where n_flag=0 order by update_date asc limit 1; - fast

All three fields have an index.
How to do it right?

Answer 1

We need to find the oldest record, where n_flag=0 and num_status>=10.

btree(update_date) where n_flag=0 and num_status>=10

Answer 2

n_flag can be 0..5
num_status 0..20
...
entry where n_flag=0 and num_status>=10.

The specified conditions with a uniform distribution of values ​​correspond to ~9% of records, i.e. 18 million. Moreover, the selection by n_flag is more selective.
Purely theoretically optimal without using Postgress features will be the index (n_flag, update_date, num_status).
DEMO fiddle . True, I somehow did not dare to generate 200 million records ... but for 1 million records, the query shows 40-50 ms - in my opinion, sane.
PS. The index is called "complex", but composite. In addition, this index is covering, i.e. the server does not need to access the table to process the request.