Date: Wed, 21 May 2008 18:27:14 +0200
To: "H. Hall" <hhall1001@reedyriver.com>, pgsql-performance@postgresql.org
Subject: Re: "Big O" notation for postgres?
From: PFC <lists@peufeu.com>
Content-Type: text/plain; format=flowed; delsp=yes; charset=utf-8
MIME-Version: 1.0
References: <48342D6D.1020506@reedyriver.com>
Content-Transfer-Encoding: Quoted-Printable
Message-ID: <op.ubiinoaacigqcu@apollo13.peufeu.com>
In-Reply-To: <48342D6D.1020506@reedyriver.com>
User-Agent: Opera Mail/9.24 (Linux)

On Wed, 21 May 2008 16:10:53 +0200, H. Hall <hhall1001@reedyriver.com>  =

wrote:

> Does anyone know if there is a source that provides "Big O" notation f=
or  =

> postgres's aggregate functions and operations?  For example is count(*=
)  =

> =3D 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 ) exce=
pt  =

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 t=
he  =

thing in the O() will change, or at least the O() constant will change..=
.