Slow query with where and index on some fields I'm working on a project with the PostgreSQL 12 database.
I have a table of about 500 MB.
The structure of the table is as follows:
create table table_name
(
    id serial not null
        constraint table_name_pkey
            primary key,
    rejected_at timestamp,
    reserved_until timestamp,
    reserved_id integer,
    deleted_at timestamp,
    accepted_at timestamp
);

For the following query:
select *
from table_name
where rejected_at is null and (
        reserved_until is null or
        reserved_until &lt;= '2021-05-14 14:23:16'
    )
  and deleted_at is null

I defined the indexes:
create index table_name_deleted_at_index
    on table_name (deleted_at);

create index table_name_rejected_at_deleted_at_index
    on table_name (rejected_at, deleted_at);

create index table_name_reserved_until_index
    on table_name (reserved_until);

But it has a very low performance. What can I do to improve performance?
The result of the explain analysis:
Index Scan using table_name_deleted_at_index on table_name  (cost=0.42..3827.19 rows=15697 width=936) (actual time=106.780..261.118 rows=1534 loops=1)
  Index Cond: (deleted_at IS NULL)
  Filter: ((rejected_at IS NULL) AND ((reserved_until IS NULL) OR (reserved_until &lt;= '2021-05-14 14:23:16'::timestamp without time zone)))
  Rows Removed by Filter: 21704
Planning Time: 0.130 ms
Execution Time: 261.333 ms


I created the suggested index:
CREATE INDEX ON table_name (COALESCE(reserved_until, TIMESTAMP '-infinity'));

select *
from table_name
where rejected_at is null and COALESCE(reserved_until, TIMESTAMP '-infinity') &lt;= '2021-05-14 14:23:16'
  and deleted_at is null

but the query plan selects deleted_at index for the updated query:
(development database)
Index Scan using table_name_deleted_at_index on table_name (cost=0.42..3277.19 rows=4845 width=938) (actual time=15.144..15.201 rows=48 loops=1)
  Index Cond: (deleted_at IS NULL)
&quot;  Filter: ((rejected_at IS NULL) AND (COALESCE(reserved_until, '-infinity'::timestamp without time zone) &lt;= '2021-05-14 14:23:16'::timestamp without time zone))&quot;
  Rows Removed by Filter: 18633
Planning Time: 0.209 ms
Execution Time: 15.251 ms
Rewrite the condition on reserved_until to
WHERE COALESCE(reserved_until, TIMESTAMP '-infinity') &lt;= '2021-05-14 14:23:16'

and create an index for it:
CREATE INDEX ON table_name (COALESCE(reserved_until, TIMESTAMP '-infinity'))
   WHERE rejected_at IS NULL AND deleted_at IS NULL;

Then you should gather statistics:
ANALYZE table_name;