Skip site navigation (1) Skip section navigation (2)

very poorly optimised query

From: pgsql-bugs(at)postgresql(dot)org
To: pgsql-bugs(at)postgresql(dot)org
Subject: very poorly optimised query
Date: 2000-09-28 19:08:44
Message-ID: (view raw, whole thread or download thread mbox)
Lists: pgsql-bugs
Orion Henry (orion(at)trustcommerce(dot)com) reports a bug with a severity of 3
The lower the number the more severe it is.

Short Description
very poorly optimised query

Long Description
This is for Postgres 7.0.1 running on x86 linux

While usually impressed with postgres's speed I ran into
a query that ran very very slowly.  The simplified version of
the query is

select count(*) from foo where groupid in (select distinct groupid from foo);

It runs at exactly O(n*n).  Theres were the times I experienced
running it on linux with an Athlon 700.

 1000 rows  0.6 seconds
 5000 rows 14.8 seconds
10000 rows 59.6 seconds

I wrote an equivlent query that uses a temporary table 
and all querys run well under a second. See example code.
I also noted that indexing the groupid makes no difference in time.

Sample Code

drop table foo;
drop sequence fooseq;
create table foo ( groupid int4 );
create sequence fooseq;

insert into foo values (nextval('fooseq'::text));
-- repeate this insert 10,00 times

-- this query is O(n*n);
select count(*) from foo where groupid in (select distinct groupid from foo);

-- this query produces the same results at O(n) or O(n*log(n)) 
-- cant tell too fast
select distinct groupid into temp table tmp from foo;
select count(*) from foo a, tmp b where a.groupid = b.groupid;

No file was uploaded with this report

pgsql-bugs by date

Next:From: pgsql-bugsDate: 2000-09-28 22:01:38
Subject: Subselects lack functionality
Previous:From: pgsql-bugsDate: 2000-09-28 15:19:22
Subject: Inexplicably running wild and freezing with 7.0

Privacy Policy | About PostgreSQL
Copyright © 1996-2017 The PostgreSQL Global Development Group