Fairly simple schema:

CREATE TABLE IF NOT EXISTS Queue(
   Id             BIGSERIAL        NOT NULL PRIMARY KEY,
   SendAt         TIMESTAMP(3)     NOT NULL,
   Payload        TEXT             NOT NULL,
   KeyId          BIGINT               NULL
);

CREATE INDEX IF NOT EXISTS Queue_sendAt_ch_idx ON Queue (SendAt, KeyId);

Executing the following sometimes gives me (parallel) sequential table scan, sometimes a nice index scan. What gives?

BEGIN;

INSERT INTO Queue 
(id, sendat, payload, KeyId)
SELECT "id", now()-("id"||'ms')::INTERVAL, 'random payload', ("id" * 0.8)::bigint
FROM generate_series(1,200000) id;

analyze Queue;

EXPLAIN (ANALYZE, buffers)
SELECT Id
       FROM Queue
     WHERE KeyId           = 15
       AND SendAt         <= now()
       ORDER BY SendAt ASC
       LIMIT 1;
ROLLBACK;

(in docker postgres:16.3-bullseye)