Jon, thanks for the script. I ran autoanalyze.sql and then re-ran the trace. The new results are available at
http://www.goliath.org/acs/trace-permissions-after-analyze.txt (old results). Here is a summary of the results:
Query Before ANALYZE After Analyze
========================== ================= ==============
1. using IN query 232 rows query 949 rows
2. using JOIN query 335512 rows query 8207 rows
3. using JOIN, not query 561 rows query 311 rows
specifying priv
4. using IN and SELECT 'x' n/a query 950 rows
instead of COUNT(*)
So I see that query 1 using IN got worse, and that queries 2 and 3 using JOIN got much better. However, there is still an order of magnitude difference between using IN and using JOIN (949 vs 8207).