Re: BUG #4596: information_schema.table_privileges is way too slow

The following bug has been logged online:

Bug reference: 4596
Logged by: Kirill Simonov
Email address: xi(at)gamma(dot)dn(dot)ua
PostgreSQL version: 8.3.5
Operating system: Linux Ubuntu 8.10
Description: information_schema.table_privileges is way too slow
Details:

It takes about 5 minutes to perform the query
SELECT * FROM information_schema.table_privileges
on an empty database (i.e. with system tables only).

postgres=# select * from information_schema.table_privileges;
Time: 296409.513 ms

"Kirill Simonov" <xi(at)gamma(dot)dn(dot)ua> writes:
> It takes about 5 minutes to perform the query
> SELECT * FROM information_schema.table_privileges
> on an empty database (i.e. with system tables only).

Not here. What non-default settings might you be using?

regards, tom lane

Tom Lane wrote:
> "Kirill Simonov" <xi(at)gamma(dot)dn(dot)ua> writes:
>> It takes about 5 minutes to perform the query
>> SELECT * FROM information_schema.table_privileges
>> on an empty database (i.e. with system tables only).
>
> Not here. What non-default settings might you be using?
>

Indeed, it is slow because there are a lot of rows in pg_authid (about
700). Is there a possibility to make table_privileges faster with a
large number of roles?

Thanks,
Kirill

2008/12/25 Kirill Simonov <xi(at)gamma(dot)dn(dot)ua>:
> Tom Lane wrote:
>>
>> "Kirill Simonov" <xi(at)gamma(dot)dn(dot)ua> writes:
>>>
>>> It takes about 5 minutes to perform the query
>>> SELECT * FROM information_schema.table_privileges
>>> on an empty database (i.e. with system tables only).
>>
>> Not here. What non-default settings might you be using?
>>
>
> Indeed, it is slow because there are a lot of rows in pg_authid (about 700).
> Is there a possibility to make table_privileges faster with a large number
> of roles?
>
> Thanks,
> Kirill

two years ago I tested 50000 users without problems. Try to vacuum and
reindex your system tables

regards
Pavel Stehule

>
> --
> Sent via pgsql-bugs mailing list (pgsql-bugs(at)postgresql(dot)org)
> To make changes to your subscription:
> http://www.postgresql.org/mailpref/pgsql-bugs
>

Pavel Stehule wrote:
> 2008/12/25 Kirill Simonov <xi(at)gamma(dot)dn(dot)ua>:
>> Tom Lane wrote:
>>> "Kirill Simonov" <xi(at)gamma(dot)dn(dot)ua> writes:
>>>> It takes about 5 minutes to perform the query
>>>> SELECT * FROM information_schema.table_privileges
>>>> on an empty database (i.e. with system tables only).
>>> Not here. What non-default settings might you be using?
>>>
>> Indeed, it is slow because there are a lot of rows in pg_authid (about 700).
>> Is there a possibility to make table_privileges faster with a large number
>> of roles?
>>
>> Thanks,
>> Kirill
>
> two years ago I tested 50000 users without problems. Try to vacuum and
> reindex your system tables
>

Neither VACUUM nor REINDEX SYSTEM did help. The problem could be
reproduced on a freshly installed Postgres:

-- add a function to generate dummy roles.
create language plpgsql;
create function create_dummy_role(start int, finish int) returns void as $$
begin
for i in start..finish loop
execute 'create role dummy_' || cast(i as text);
end loop;
end;
$$ language plpgsql;

-- no extra roles
select count(*) from information_schema.table_privileges;
>>> Time: 11.467 ms

-- 10 roles
select create_dummy_role(1, 10);
select count(*) from information_schema.table_privileges;
>>> Time: 161.539 ms

-- 100 roles
select create_dummy_role(11, 100);
select count(*) from information_schema.table_privileges;
>>> Time: 7807.675 ms

-- 1000 roles
select create_dummy_role(101, 1000);
select count(*) from information_schema.table_privileges;
>>> Time: 543030.948 ms

Thanks,
Kirill

Really, this view is strange. I'll look on at

Pavel

2008/12/25, Kirill Simonov <xi(at)gamma(dot)dn(dot)ua>:
> Pavel Stehule wrote:
>> 2008/12/25 Kirill Simonov <xi(at)gamma(dot)dn(dot)ua>:
>>> Tom Lane wrote:
>>>> "Kirill Simonov" <xi(at)gamma(dot)dn(dot)ua> writes:
>>>>> It takes about 5 minutes to perform the query
>>>>> SELECT * FROM information_schema.table_privileges
>>>>> on an empty database (i.e. with system tables only).
>>>> Not here. What non-default settings might you be using?
>>>>
>>> Indeed, it is slow because there are a lot of rows in pg_authid (about
>>> 700).
>>> Is there a possibility to make table_privileges faster with a large
>>> number
>>> of roles?
>>>
>>> Thanks,
>>> Kirill
>>
>> two years ago I tested 50000 users without problems. Try to vacuum and
>> reindex your system tables
>>
>
> Neither VACUUM nor REINDEX SYSTEM did help. The problem could be
> reproduced on a freshly installed Postgres:
>
> -- add a function to generate dummy roles.
> create language plpgsql;
> create function create_dummy_role(start int, finish int) returns void as $$
> begin
> for i in start..finish loop
> execute 'create role dummy_' || cast(i as text);
> end loop;
> end;
> $$ language plpgsql;
>
> -- no extra roles
> select count(*) from information_schema.table_privileges;
> >>> Time: 11.467 ms
>
> -- 10 roles
> select create_dummy_role(1, 10);
> select count(*) from information_schema.table_privileges;
> >>> Time: 161.539 ms
>
> -- 100 roles
> select create_dummy_role(11, 100);
> select count(*) from information_schema.table_privileges;
> >>> Time: 7807.675 ms
>
> -- 1000 roles
> select create_dummy_role(101, 1000);
> select count(*) from information_schema.table_privileges;
> >>> Time: 543030.948 ms
>
>
> Thanks,
> Kirill
>

Hello

really it's should be slow, it's cross join pg_class, pg_authid, pg_authid

for fast respond you have to specify minimally table_name and grantor fields.

select * from information_schema.table_privileges where table_name =
'foo' and grantor = 'pavel';

regards
Pavel Stehule

2008/12/25, Kirill Simonov <xi(at)gamma(dot)dn(dot)ua>:
> Pavel Stehule wrote:
>> 2008/12/25 Kirill Simonov <xi(at)gamma(dot)dn(dot)ua>:
>>> Tom Lane wrote:
>>>> "Kirill Simonov" <xi(at)gamma(dot)dn(dot)ua> writes:
>>>>> It takes about 5 minutes to perform the query
>>>>> SELECT * FROM information_schema.table_privileges
>>>>> on an empty database (i.e. with system tables only).
>>>> Not here. What non-default settings might you be using?
>>>>
>>> Indeed, it is slow because there are a lot of rows in pg_authid (about
>>> 700).
>>> Is there a possibility to make table_privileges faster with a large
>>> number
>>> of roles?
>>>
>>> Thanks,
>>> Kirill
>>
>> two years ago I tested 50000 users without problems. Try to vacuum and
>> reindex your system tables
>>
>
> Neither VACUUM nor REINDEX SYSTEM did help. The problem could be
> reproduced on a freshly installed Postgres:
>
> -- add a function to generate dummy roles.
> create language plpgsql;
> create function create_dummy_role(start int, finish int) returns void as $$
> begin
> for i in start..finish loop
> execute 'create role dummy_' || cast(i as text);
> end loop;
> end;
> $$ language plpgsql;
>
> -- no extra roles
> select count(*) from information_schema.table_privileges;
> >>> Time: 11.467 ms
>
> -- 10 roles
> select create_dummy_role(1, 10);
> select count(*) from information_schema.table_privileges;
> >>> Time: 161.539 ms
>
> -- 100 roles
> select create_dummy_role(11, 100);
> select count(*) from information_schema.table_privileges;
> >>> Time: 7807.675 ms
>
> -- 1000 roles
> select create_dummy_role(101, 1000);
> select count(*) from information_schema.table_privileges;
> >>> Time: 543030.948 ms
>
>
> Thanks,
> Kirill
>

Pavel Stehule wrote:
>
> really it's should be slow, it's cross join pg_class, pg_authid, pg_authid
>
> for fast respond you have to specify minimally table_name and grantor fields.
>
> select * from information_schema.table_privileges where table_name =
> 'foo' and grantor = 'pavel';

Yes, I realize why it's slow. I'm introspecting the database schema,
that's why I need the whole contents of "table_privileges". I suppose I
could obtain the same data from "pg_class.relacl", but I hoped to do it
in a portable way.

Thanks,
Kirill

> 2008/12/25, Kirill Simonov <xi(at)gamma(dot)dn(dot)ua>:
>> Pavel Stehule wrote:
>>> 2008/12/25 Kirill Simonov <xi(at)gamma(dot)dn(dot)ua>:
>>>> Tom Lane wrote:
>>>>> "Kirill Simonov" <xi(at)gamma(dot)dn(dot)ua> writes:
>>>>>> It takes about 5 minutes to perform the query
>>>>>> SELECT * FROM information_schema.table_privileges
>>>>>> on an empty database (i.e. with system tables only).
>>>>> Not here. What non-default settings might you be using?
>>>>>
>>>> Indeed, it is slow because there are a lot of rows in pg_authid (about
>>>> 700).
>>>> Is there a possibility to make table_privileges faster with a large
>>>> number
>>>> of roles?
>>>>
>>>> Thanks,
>>>> Kirill
>>> two years ago I tested 50000 users without problems. Try to vacuum and
>>> reindex your system tables
>>>
>> Neither VACUUM nor REINDEX SYSTEM did help. The problem could be
>> reproduced on a freshly installed Postgres:
>>
>> -- add a function to generate dummy roles.
>> create language plpgsql;
>> create function create_dummy_role(start int, finish int) returns void as $$
>> begin
>> for i in start..finish loop
>> execute 'create role dummy_' || cast(i as text);
>> end loop;
>> end;
>> $$ language plpgsql;
>>
>> -- no extra roles
>> select count(*) from information_schema.table_privileges;
>> >>> Time: 11.467 ms
>>
>> -- 10 roles
>> select create_dummy_role(1, 10);
>> select count(*) from information_schema.table_privileges;
>> >>> Time: 161.539 ms
>>
>> -- 100 roles
>> select create_dummy_role(11, 100);
>> select count(*) from information_schema.table_privileges;
>> >>> Time: 7807.675 ms
>>
>> -- 1000 roles
>> select create_dummy_role(101, 1000);
>> select count(*) from information_schema.table_privileges;
>> >>> Time: 543030.948 ms

Kirill Simonov <xi(at)gamma(dot)dn(dot)ua> writes:
> Pavel Stehule wrote:
>> really it's should be slow, it's cross join pg_class, pg_authid, pg_authid

> Yes, I realize why it's slow. I'm introspecting the database schema,
> that's why I need the whole contents of "table_privileges". I suppose I
> could obtain the same data from "pg_class.relacl", but I hoped to do it
> in a portable way.

There's not much to be done about that in the short term. A bit of
profiling says that essentially all the runtime is going into repeated
evaluations of the clause

aclcontains(c.relacl,
makeaclitem(grantee.oid, u_grantor.oid, pr.type, false))

which cannot be applied until we form the join of all four relations
mentioned. This means the runtime is roughly proportional to the square
of the number of userids (since grantee and u_grantor both have a row
per userid). Even though the test itself is reasonably cheap, you can't
avoid getting screwed by the O(N^2) behavior. It doesn't help any that
we have to run the whole thing over again for each possible privilege
type name...

ISTM that if we wanted to really fix this, what'd be appropriate is
to invent a new function on the order of

aclexplode(aclitem[]) returns table(grantee oid, grantor oid, privilege_type text)

and then implement this view as a join between

(select aclexplode(relacl) from pg_class)

and a couple of instances of pg_authid.

More generally, there are a *whole lot* of ridiculous inefficiencies
in our information_schema views; I'm surprised there haven't been
more complaints about them. Sometime someone ought to go through
the whole set and see what other refactorings might be appropriate
to make them work better.

regards, tom lane

On Friday 26 December 2008 01:12:26 Tom Lane wrote:
> More generally, there are a *whole lot* of ridiculous inefficiencies
> in our information_schema views; I'm surprised there haven't been
> more complaints about them. Sometime someone ought to go through
> the whole set and see what other refactorings might be appropriate
> to make them work better.

Added to TODO. Could probably be accomplished for 8.5.