The portals rewrite that's in CVS reduces the number of objects. Reducing them further would reduce the flexibility and usefulness of the portal system.
The permission system has nothing to do with acs-rels, so I don't understand the question.
Relational segments and groups do use the acs-rels portion of the datamodel, and I'd agree that there is no need in most (but not all) cases for each row in a relationship to be an object. I wouldn't object to a rewrite of those two features to use non-object private tables to store the party-[group/rel] relationships. Groups and relsegs themselves must be objects so we can use permissions on them to determine who can add or delete members, etc.
If I'd been more ambitious when I added denormalized tables to speed permission checking I might've tackled this myself. However relsegs and groups provide fairly sophisticated functionality and a wide variety of views so a rewrite (including upgrade scripts) might be somewhat ambitious.
An example of when the fact that every row in a relationship is an object, and therefore visible to permissions, would be a general ratings system. Each rating would be a row in acs-rels, and permissions would govern who could edit or delete existing ratings.
So we don't want to toss out acs-rels entirely.
On the other hand, I don't see that the object cost of acs-rels as being a major concern. Though I'd be open to a rewrite of relsegs and groups that doesn't use acs-rels but rather a private relationship system, I don't think there's much bang-for-the-buck to be gained here.
A million rows should be no big deal. This is particularly true in Oracle (Postgres has a fairly high per-row overhead.) Even in PG you're talking 200-300 MB max for this table. Presumably if you're going to support 500,000 users you understand that you need many GB RAM no matter what technology you choose, and that getting rid of acs-objects isn't going to make that need go away.
Now one thing you *can* do is to not join against the acs-objects table unless you actually need the information that is stored there. It is joining not access per se that generates costs that build up. Identifying queries that are slow and optimizing them by various means is where you'll most impact performance IMO.
Back to permissions ... there's evidence posted by Dirk Gomez that makes us think that adding a denormalized hierarchy table that exists in PG but not Oracle would speed performance.
Also getting rid of all these silly foo_read, foo_write private permissions that are children of read and write, and just using read and write directly would help permissions run faster. I just did this recently for the port of the 3.x events package.