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

Re: "Big O" notation for postgres?

From: "H(dot) Hall" <hhall1001(at)reedyriver(dot)com>
To: pgsql-performance(at)postgresql(dot)org
Subject: Re: "Big O" notation for postgres?
Date: 2008-05-21 19:14:51
Message-ID: (view raw or whole thread)
Lists: pgsql-performance
PFC wrote:
> On Wed, 21 May 2008 16:10:53 +0200, H. Hall wrote:
>> Does anyone know if there is a source that provides "Big O" notation 
>> for postgres's aggregate functions and operations?  For example is 
>> count(*) = O(1) or O(n)?
>> Do the developers for postgres use Big O when selecting algorithms? 
>> If so, is the info easily available?
>     You can't do any better than O( n rows examined by the aggregate ) 
> except for max() and min() on an indexed expression, which in this 
> case aren't really aggrgates anymore since they are internally 
> rewritten as an index lookup to get the value you want... but stuff 
> like sum() or avg() or count() will always have to see all the rows 
> selected (and some more) unless you use clever hacks like materialized 
> views etc, in which case the thing in the O() will change, or at least 
> the O() constant will change...
Thank you PFC and also Jonah, and Richard for your replies.

It occurs to me that Big O might be a useful way to understand/explain 
what is happening with situations like Albert's earlier today:

I've got a query similar to this:
> >
> > select * from t1, t2 where > 158507 and =;
> >
> > That took > 84 minutes (the query was a bit longer but this is the part
> > that made the difference) after a little change the query took ~1 second:
> >
> > select * from t1, t2 where > 158507 and > 158507 and =
> >;

BTW, anyone reading this and not familiar with Big O notation might want 
to check out these links. All are intro type articles:

   * An informal introduction to O(N) notation:
  * Analysis of Algorithms and Selection of Algorithms:

   * Complexity and Big-O Notation

H. Hall
ReedyRiver Group LLC

In response to

pgsql-performance by date

Next:From: Robins TharakanDate: 2008-05-22 00:54:36
Subject: Re: Varchar pkey instead of integer
Previous:From: Scott MarloweDate: 2008-05-21 18:44:44
Subject: Re: "append" takes a lot of time in a query

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