How to implement an effective ACL/auth in a relational db? We are looking at implementing an ACL that fulfills the following requirements:


Most users have access to an item (access to the item by default), but a few is denied access.
Most users do not have access to an item (no access to the item by default), but a few is granted access.
A user only has access to a few items.
Default is that all users have access to an items.


We are talking about hundreds of thousands of items and tens of thousands of users. They are all stored in a relational DB. We think that having a many-to-many relation between items and users and defining the access in this relation would be ineffective, but are open for comments about this. We also think that access groups are irrelevant here, but we might be wrong. 

What are your thoughts on how to do this?
Your many-many table is a good idea. In this table, the existence of a row can mean "no access" or "has access" depending on your need.

I'd aim to store least data and make "no row" mean the most common state by implication. 

Looking at your requirement 2, I'd have it so that "row exists = has access". However, the opposite can be be read from item 1. Ditto for 3 and 4. So you need to explain this more

I'd also look at grouping users. Do you really permission users individually? Ditto for items: can thes be grouped somehow?