Yes, if you have 500.000 records in your table, ANY plugin will take a long time, not just this one.
This is something I can't improve. My board has 33,800 users with 191,486 posts. That's all I got; that's where I can I test any resource. I don't think anyone with a big board, like you, will borrow their board to make tests, do you ?
A new table will result in a new query everywhere. That, in my POV, is not acceptable and if it can be avoided, I do. Things like that are added on members table because it is already loaded. Plus, a topic with 2, 3, 7 users will work fine... but in a busy board with 100, 200 users in a topic, It will not be a good thing to try.