> a) start from the user:
> Search for useroid in pg_auth_members.member
> For each returned role, search for that role in member column
> Repeat until all roles the useroid is in have been found
> [Note: This could possibly be done and stored per-user on
> connection,
> but it would mean we'd have to have a mechanism to update it when
> necessary, possibly instigated by the user, or just force them to
> reconnect ala unix group membership]
> Look through ACL list to see if the useroid has permission
> or if any
> of the roles found do.
>
> b) start from the ACL list:
> Search for each roleoid in pg_auth_members.role
> For each returned member, search for that member in role column
> Upon member == useroid match is found check for permission, if
> granted then stop, otherwise continue processing
> Has the advantage that the search stops once it's been determined
> that permission is there and doesn't require updating.
>

If I may humbly suggest another option:

c) Use tables for users, roles, and user x role as you already have
(Or was a user's roles in an array? I forget)
Add a fourth table (access?) with the PK (user, priv, role).
Whenever a privilege is granted or revoked, for a user or a role,
insert or delete the appropriate rows in the access table.
This pre-loads all of the cost of maintaining the ACL and should
reduce the effort of checking a particular privilege to an index
seek.

With this method, a user can be granted a privilege by more than one role,
and if they are removed from one of those roles, the other still grants
the privilege. The access table can also store the privileges that each
role has by storing the role ID in the user ID column.

I know that it makes for a potentially huge table, but it makes the model
straightforward and reliable.

Examples:

Grant role 'foo' privilege 'bar':
INSERT INTO access (user, priv, role ) VALUES ( 'foo', 'bar', 'foo' );

Grant user 'baz' role 'foo':
INSERT INTO access ( user, priv, role )
SELECT 'baz', priv, role FROM access WHERE user = 'foo';

Remove user 'baz' from role 'foo':
DELETE FROM access WHERE user = 'baz' AND role = 'foo';

Remove privilege 'bar' from role 'foo':
DELETE FROM access WHERE priv = 'bar' AND role = 'foo';
-- Note that this automatically cleaned up all of the users, too.

Grant privilege 'bar' to user 'baz' without a role involved:
INSERT INTO access ( user, priv, role ) VALUES ( 'baz', 'bar', 'baz' );

Grant user 'postgres' privilege 'su' in a hard-to-revoke way:
INSERT INTO access ( user, priv, role ) VALUES ( 'postgres', 'su', '' );

Check to see if user 'baz' has privilege 'bar':
SELECT user, priv, role FROM access WHERE user = 'baz' AND priv = 'bar';
-- This even tells you the role(s) that grant the privilege.

Inheritance from role to role can even be handled by repeating the inserts
or deletes with appropriate roles. (This would even allow a role to inherit
a privilege from multiple parent roles, and work correctly if it is revoked
by one.)