Performance issues related to $nin/$ne querying in large database

I am working on a pipeline where multiple microservices(workers) modify and add attributes to documents. Some of them have to make sure the document was already processed by another microservice and/or make sure they don't process a document twice.

I've already tried two different data structures for this: array and object:

{
  ...other_attributes
  worker_history_array: ["worker_1", "worker_2", ...]
  woker_history_object: {"worker_1": true, "worker_2": true, ...}
}

I also created indexes for the 2 fields

{ "worker_history_array": 1 }
{ "worker_history_object.$**": 1 }

Both data structures use the index and work very well when querying for the existence of a worker in the history:

{
  "worker_history_array": "worker_1"
}

{
  "worker_history_object.worker_1": true
}

But I can't seem to find a query that is fast/ hits the index when looking if a worker did not already process this document. All of those queries perform awfully:

{
  "worker_history_array": { $ne: "worker_1" }
}

{
  "worker_history_array": { $nin: ["worker_1"] }
}

{
  "worker_history_object.worker_1": { $exists: false }
}

{
  "worker_history_object.worker_1":{ $not: { $exists: true } }
}

{
  "worker_history_object.worker_1": { $ne: true }
}

Performance is already bad with 500k documents, but the database will grow to millions of documents.

• Is there a way to improve the query performance?
• Can I work around the low selectivity of $ne and $nin?
• Different index?
• Different data structure?

I don't think it matters but I'm using MongoDB Atlas (MongoDB 4.4.1, cluster with read replicas) on Google Cloud and examined the performance of the queries with MongoDB Compass.

Additional Infos/Restrictions:

• Millions of records
• Hundreds of workers
• I don't know all workers beforehand
• Not every worker processes every document (some may only work on documents with type: "x" while others work only on documents with type: "y")
• No worker should have knowledge about the pipeline, only about the worker that directly precedes it.

Any help would be greatly appreciated.