Slow query to count pending mirror updates

We are seeing slow query on GitLab.com (at about 1,500ms) which seemingly is involved in counting pending mirror updates (see https://gitlab.com/gitlab-com/gl-infra/infrastructure/issues/6678#note_175302706 for context):

SELECT
    COUNT(*)
FROM
    projects
    INNER JOIN project_mirror_data ON project_mirror_data.project_id = projects.id
    INNER JOIN namespaces ON projects.namespace_id = namespaces.id
    LEFT JOIN plans ON namespaces.plan_id = plans.id
WHERE
    projects.mirror = TRUE
    AND project_mirror_data.retry_count <= 14
    AND (projects.visibility_level = 20
        OR plans.name IN ('early_adopter', 'bronze', 'silver', 'gold'))
    AND project_mirror_data.status NOT IN ('scheduled',
        'started')
    AND project_mirror_data.last_update_at >= NOW() - '30 seconds'::interval;

Plan: https://explain.depesz.com/s/SQtT

• It looks like we lack a proper/complete index to satisfy the last_update_at > ? condition.
• Note we cannot answer the status <> ALL(...) from an index. We might want to explicitly enumerate the status values we're interested in here instead.

cc @DouweM