From: PFC <lists@peufeu.com>
To: H. Hall <hhall1001@reedyriver.com>
To: pgsql-performance@postgresql.org
Subject: Re: "Big O" notation for postgres?
Date: Wed, 21 May 2008 18:27:14 +0200
Message-ID: <op.ubiinoaacigqcu@apollo13.peufeu.com> (raw)
In-Reply-To: <48342D6D.1020506@reedyriver.com>
References: <48342D6D.1020506@reedyriver.com>
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 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...
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-performance@postgresql.org
Cc: lists@peufeu.com, hhall1001@reedyriver.com
Subject: Re: "Big O" notation for postgres?
In-Reply-To: <op.ubiinoaacigqcu@apollo13.peufeu.com>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox