Comment by sgarland

> Because a workflow typically performs many steps over a long period of time, those step records are widely separated on disk

Clustered indices would be so, so nice for Postgres to have. OrioleDB can’t come quickly enough.

> However, this stamp is applied only to the row itself, not to any indexes referencing the row.

Indices also hold the hint bit LP_DEAD, which is set by any query that follows the index to the heap and finds that it’s invisible to everyone.

I suspect that a combined query that uses pagination rather than LIMIT … OFFSET would be more performant here, and could skip the dead tuple problem.

    DELETE FROM step_outputs
    WHERE ctid = ANY(ARRAY(
        SELECT s.ctid
        FROM step_outputs s
        WHERE (s.created_at, s.id) > (?, ?)
            AND s.created_at < ?
            AND NOT EXISTS (
                SELECT 1 FROM workflow_status w
                WHERE w.workflow_uuid = s.workflow_uuid
            )
        ORDER BY s.created_at, s.id
        LIMIT ?
        ))
   RETURNING created_at, id;

Haven’t tested that, but something of that shape. You’d need a composite index on (created_at, id) as well.