Re: "Big O" notation for postgres?

[PFC <lists(at)peufeu(dot)com>]

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...