BUG #2872: SELECT from view with OR fast in 8.1, slow in 8.2

The following bug has been logged online:

Bug reference:      2872
Logged by:          Nicholas Vinen
Email address:      hb@pg.x256.org
PostgreSQL version: 8.2.0
Operating system:   Linux (AMD64)
Description:        SELECT from view with OR fast in 8.1, slow in 8.2
Details:

Sorry that I can't provide data, there's some private information in there,
but hopefully this will be easy enough to reproduce.

I have these tables and this view:


        View "public.users_groups"
       Column       |  Type   | Modifiers
--------------------+---------+-----------
 group_id           | integer |
 group_name         | text    |
 group_emailaddress | text    |
 group_disabled     | boolean |
 user_id            | integer |
 user_name          | text    |
 user_display_name  | text    |
 user_emailaddress  | text    |
 user_disabled      | boolean |
View definition:
 SELECT g.id AS group_id, g.name AS group_name, g.emailaddress AS
group_emailaddress, pg.disabled AS group_disabled, u.id AS user_id,
u.realname AS user_name, u.displayname AS user_display_name, u.emailaddress
AS user_emailaddress, pu.disabled AS user_disabled
   FROM groups g
   JOIN principals pg ON pg.objectid = g.id
   JOIN cachedgroupmembers cgm ON cgm.groupid = g.id AND NOT cgm.disabled
   JOIN users u ON u.id = cgm.memberid
   JOIN principals pu ON pu.objectid = u.id;

                                     Table "helpdesk_mirror.users"
        Column         |           Type           |
Modifiers
-----------------------+--------------------------+-------------------------
---------------------------
 id                    | integer                  | not null default
nextval('users_id_seq'::regclass)
 name                  | text                     | not null default
''::text
 password              | text                     |
 comments              | bytea                    |
 signature             | bytea                    |
 emailaddress          | text                     |
 freeformcontactinfo   | text                     |
 organization          | text                     |
 realname              | text                     |
 nickname              | text                     |
 lang                  | text                     |
 emailencoding         | text                     |
 webencoding           | text                     |
 externalcontactinfoid | text                     |
 contactinfosystem     | text                     |
 externalauthid        | text                     |
 authsystem            | text                     |
 gecos                 | text                     |
 homephone             | text                     |
 workphone             | text                     |
 mobilephone           | text                     |
 pagerphone            | text                     |
 address1              | text                     |
 address2              | text                     |
 city                  | text                     |
 state                 | text                     |
 zip                   | text                     |
 country               | text                     |
 timezone              | text                     |
 pgpkey                | text                     |
 creator               | integer                  | not null default 0
 created               | timestamp with time zone |
 lastupdatedby         | integer                  | not null default 0
 lastupdated           | timestamp with time zone |
 focus                 | text                     |
 focuscount            | integer                  |
 focusproblemcount     | integer                  |
 focusprojectcount     | integer                  |
 focusrequestcount     | integer                  |
 focussuggestioncount  | integer                  |
 focusfeedbackcount    | integer                  |
 portraitgeometry      | text                     |
 focusuntypedcount     | integer                  |
 lastloginip           | text                     |
 lastloginhostname     | text                     |
 defaultqueue          | integer                  |
 interface             | text                     |
 default_ownerassignee | text                     |
 flags                 | text                     |
 guid                  | bytea                    |
 displayname           | text                     |
 title                 | text                     |
 department            | text                     |
 emailalias            | text                     |
Indexes:
    "users_pkey" PRIMARY KEY, btree (id)
    "users_name_key" UNIQUE, btree (name)
    "users_emailaddress_idx" btree (emailaddress)
Triggers:
    users_trig_final AFTER INSERT OR DELETE OR UPDATE ON users FOR EACH ROW
EXECUTE PROCEDURE mirror_config.log_changes()

                        Table "helpdesk_mirror.groups"
    Column    |  Type   |                      Modifiers

--------------+---------+---------------------------------------------------
--
 id           | integer | not null default
nextval('groups_id_seq'::regclass)
 name         | text    |
 description  | text    |
 domain       | text    |
 type         | text    |
 instance     | integer |
 emailaddress | text    |
 guid         | bytea   |
Indexes:
    "groups_pkey" PRIMARY KEY, btree (id)
    "groups_domain_idx" btree ("domain")
    "groups_emailaddress_idx" btree (emailaddress)
    "groups_instance_idx" btree (instance)
    "groups_name_idx" btree (name)
    "groups_type_idx" btree ("type")
Triggers:
    groups_trig_final AFTER INSERT OR DELETE OR UPDATE ON groups FOR EACH
ROW EXECUTE PROCEDURE mirror_config.log_changes()

                        Table "helpdesk_mirror.principals"
    Column     |  Type   |                        Modifiers

---------------+---------+--------------------------------------------------
-------
 id            | integer | not null default
nextval('principals_id_seq'::regclass)
 principaltype | text    | not null default ''::text
 objectid      | integer |
 disabled      | boolean | not null default false
Indexes:
    "principals_pkey" PRIMARY KEY, btree (id)
    "principals_objectid_key" UNIQUE, btree (objectid)
    "principals_objectid_idx" btree (objectid)
    "principals_principaltype" btree (principaltype)
Triggers:
    principals_trig_final AFTER INSERT OR DELETE OR UPDATE ON principals FOR
EACH ROW EXECUTE PROCEDURE mirror_config.log_changes()

                      Table "helpdesk_mirror.cachedgroupmembers"
  Column  |  Type   |                            Modifiers

----------+---------+-------------------------------------------------------
----------
 id       | integer | not null default
nextval('cachedgroupmembers_id_seq'::regclass)
 groupid  | integer | not null default 0
 memberid | integer | not null default 0
 disabled | boolean | not null default false
Indexes:
    "cachedgroupmembers_pkey" PRIMARY KEY, btree (id)
    "cachedgroupmembers_groupidmemberid_idx" btree (groupid, memberid)
CLUSTER
    "cachedgroupmembers_memberid_idx" btree (memberid)
Triggers:
    cachedgroupmembers_trig_final AFTER INSERT OR DELETE OR UPDATE ON
cachedgroupmembers FOR EACH ROW EXECUTE PROCEDURE
mirror_config.log_changes()

Here is the problem:

rt3=# explain analyze SELECT * FROM users_groups WHERE user_id = '9752'
UNION SELECT * FROM users_groups WHERE group_id = '9752';

                    QUERY PLAN

----------------------------------------------------------------------------
----------------------------------------------------------------------------
----------------------------------------------------
 Unique  (cost=87.67..87.74 rows=3 width=143) (actual time=6.666..6.741
rows=18 loops=1)
   ->  Sort  (cost=87.67..87.67 rows=3 width=143) (actual time=6.663..6.685
rows=18 loops=1)
         Sort Key: group_id, group_name, group_emailaddress, group_disabled,
user_id, user_name, user_display_name, user_emailaddress, user_disabled
         ->  Append  (cost=0.00..87.64 rows=3 width=143) (actual
time=0.282..6.496 rows=18 loops=1)
               ->  Nested Loop  (cost=0.00..18.32 rows=2 width=143) (actual
time=0.045..0.045 rows=0 loops=1)
                     ->  Nested Loop  (cost=0.00..13.40 rows=2 width=94)
(actual time=0.043..0.043 rows=0 loops=1)
                           ->  Nested Loop  (cost=0.00..8.48 rows=2
width=89) (actual time=0.040..0.040 rows=0 loops=1)
                                 ->  Nested Loop  (cost=0.00..4.81 rows=1
width=85) (actual time=0.037..0.037 rows=0 loops=1)
                                       ->  Index Scan using users_pkey on
users u  (cost=0.00..2.35 rows=1 width=84) (actual time=0.035..0.035 rows=0
loops=1)
                                             Index Cond: (id = 9752)
                                       ->  Index Scan using
principals_objectid_key on principals pu  (cost=0.00..2.36 rows=1 width=5)
(never executed)
                                             Index Cond: (9752 = objectid)
                                 ->  Index Scan using
cachedgroupmembers_memberid_idx on cachedgroupmembers cgm  (cost=0.00..3.47
rows=2 width=8) (never executed)
                                       Index Cond: (9752 = memberid)
                                       Filter: (NOT disabled)
                           ->  Index Scan using principals_objectid_key on
principals pg  (cost=0.00..2.36 rows=1 width=5) (never executed)
                                 Index Cond: (cgm.groupid = pg.objectid)
                     ->  Index Scan using groups_pkey on groups g
(cost=0.00..2.36 rows=1 width=57) (never executed)
                           Index Cond: (pg.objectid = g.id)
               ->  Nested Loop  (cost=0.00..69.02 rows=1 width=143) (actual
time=0.233..6.406 rows=18 loops=1)
                     ->  Nested Loop  (cost=0.00..66.56 rows=1 width=142)
(actual time=0.203..6.186 rows=18 loops=1)
                           ->  Nested Loop  (cost=0.00..64.10 rows=1
width=89) (actual time=0.138..5.929 rows=18 loops=1)
                                 ->  Nested Loop  (cost=0.00..61.64 rows=1
width=92) (actual time=0.085..5.417 rows=18 loops=1)
                                       ->  Index Scan using
cachedgroupmembers_groupidmemberid_idx on cachedgroupmembers cgm
(cost=0.00..25.17 rows=23 width=8) (actual time=0.064..0.129 rows=20
loops=1)
                                             Index Cond: (9752 = groupid)
                                             Filter: (NOT disabled)
                                       ->  Index Scan using users_pkey on
users u  (cost=0.00..1.48 rows=1 width=84) (actual time=0.257..0.259 rows=1
loops=20)
                                             Index Cond: (u.id =
cgm.memberid)
                                 ->  Index Scan using
principals_objectid_key on principals pu  (cost=0.00..2.36 rows=1 width=5)
(actual time=0.022..0.023 rows=1 loops=18)
                                       Index Cond: (pu.objectid = u.id)
                           ->  Index Scan using groups_pkey on groups g
(cost=0.00..2.36 rows=1 width=57) (actual time=0.007..0.009 rows=1
loops=18)
                                 Index Cond: (id = 9752)
                     ->  Index Scan using principals_objectid_key on
principals pg  (cost=0.00..2.36 rows=1 width=5) (actual time=0.005..0.006
rows=1 loops=18)
                           Index Cond: (9752 = objectid)
 Total runtime: 7.112 ms
(35 rows)
rt3=# explain analyze SELECT * FROM users_groups WHERE (group_id = '9752' or
user_id = '9752');

        QUERY PLAN

----------------------------------------------------------------------------
----------------------------------------------------------------------------
-----------------------------
 Nested Loop  (cost=0.00..12442.41 rows=4 width=143) (actual
time=875.204..41218.950 rows=18 loops=1)
   ->  Nested Loop  (cost=0.00..12440.56 rows=4 width=146) (actual
time=875.165..41218.242 rows=18 loops=1)
         ->  Nested Loop  (cost=0.00..12437.27 rows=4 width=149) (actual
time=875.113..41207.734 rows=18 loops=1)
               Join Filter: ((g.id = 9752) OR (u.id = 9752))
               ->  Nested Loop  (cost=0.00..6528.63 rows=6503 width=92)
(actual time=0.094..16219.575 rows=312649 loops=1)
                     ->  Index Scan using users_pkey on users u
(cost=0.00..239.51 rows=1641 width=84) (actual time=0.042..100.580 rows=1642
loops=1)
                     ->  Index Scan using cachedgroupmembers_memberid_idx on
cachedgroupmembers cgm  (cost=0.00..3.42 rows=4 width=8) (actual
time=0.122..9.296 rows=190 loops=1642)
                           Index Cond: (u.id = cgm.memberid)
                           Filter: (NOT disabled)
               ->  Index Scan using groups_pkey on groups g
(cost=0.00..0.80 rows=1 width=57) (actual time=0.074..0.075 rows=1
loops=312649)
                     Index Cond: (cgm.groupid = g.id)
         ->  Index Scan using principals_objectid_key on principals pu
(cost=0.00..0.72 rows=1 width=5) (actual time=0.573..0.575 rows=1 loops=18)
               Index Cond: (pu.objectid = u.id)
   ->  Index Scan using principals_objectid_key on principals pg
(cost=0.00..0.36 rows=1 width=5) (actual time=0.030..0.032 rows=1 loops=18)
         Index Cond: (pg.objectid = g.id)
 Total runtime: 41219.442 ms
(16 rows)

This was never a problem with 8.1.x.



Nicholas