What is best way to batch mutate and avoid node duplication?

Since you are doing an upsert, you would have to query first and then mutate. You can batch these mutates and don’t have to do them one by one.

Yeah, query operation would still be O(1) since it uses indexing which makes it fast.