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

Re: "Big O" notation for postgres?

From: PFC <lists(at)peufeu(dot)com>
To: "H(dot) Hall" <hhall1001(at)reedyriver(dot)com>, pgsql-performance(at)postgresql(dot)org
Subject: Re: "Big O" notation for postgres?
Date: 2008-05-21 16:27:14
Message-ID: op.ubiinoaacigqcu@apollo13.peufeu.com (view raw or flat)
Thread:
Lists: pgsql-performance
On Wed, 21 May 2008 16:10:53 +0200, H. Hall <hhall1001(at)reedyriver(dot)com>  
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...

In response to

Responses

pgsql-performance by date

Next:From: Scott MarloweDate: 2008-05-21 18:44:44
Subject: Re: "append" takes a lot of time in a query
Previous:From: Albert Cervera ArenyDate: 2008-05-21 16:22:42
Subject: Re: Posible planner improvement?

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