> Obvious solutions are "where allowed_user_ids = ... big list" or "where disallowed_user_ids NE ... small list"; the latter not a solution as you can't optimize this query with a normal tree-like index.
This is not exactly an answer but it's worth remembering that the lower the selectivity of a condition is the more likely it'll turn out that brute force and ignorance will actually work out better - loading data in batches and filtering out the ones that are disallowed by a secondary positive index lookup (assuming you've pre-materialised your 'is disallowed' list) could easily turn out to be a better option for a lot of cases than trying to be more clever than that.
The more general question is of course rather more complicated and interesting, but other people already had better answers than I do there in other replies.
This is not exactly an answer but it's worth remembering that the lower the selectivity of a condition is the more likely it'll turn out that brute force and ignorance will actually work out better - loading data in batches and filtering out the ones that are disallowed by a secondary positive index lookup (assuming you've pre-materialised your 'is disallowed' list) could easily turn out to be a better option for a lot of cases than trying to be more clever than that.
The more general question is of course rather more complicated and interesting, but other people already had better answers than I do there in other replies.