Richard, we're running openacs.org on PG 7.4, and Jeff's example shows that PG 7.4 is capable of executing the current queries very efficiently.
I do NOT understand how "exists()" can run slower than the non "exists()" query. Something very evil is going on. Something very evil that we do NOT see on production systems that are properly set up.
As Jeff says ... run vacuumdb with the proper switches to do an analysis as get rid of dead rows. Your comment that "analyze isn't really necessary for a test system" is false ... no benchmarking without a recent ANALYZE is meaningless. The statistical data directly impacts the plan that is generated. Without stats on a table, PG *will* generate poor plans.
At this point let me summarize our state of knowledge:
1. As Jeff says, the problem with extremely slow permissions queries that you're seeing on your system are not seen by people with properly set-up and recently ANALYZE'd production sites. That doesn't mean that improvements aren't possible, but it does mean that we're going to be suspicious of your numbers because we simply don't see these results in the real world ... where the numbers really count.
2. I'm mystified by the numbers you get, especially with the "exists()" form of the queries. But without a recent ANALYZE on your database the benchmarks aren't very useful.
3. It is possible that you've found a "sour spot" (as opposed to "sweet spot") for the permissions queries with your low number of users and relatively low number of objects, that PG will make bad choices for such a combination. But ... until I see this after you run ANALYZE I'm going to have a hard time believing it ...
