From: H. Hall <hhall1001@reedyriver.com>
To: pgsql-performance@postgresql.org
Subject: Re: "Big O" notation for postgres?
Date: Wed, 21 May 2008 15:14:51 -0400
Message-ID: <483474AB.4040807@reedyriver.com> (raw)
In-Reply-To: <op.ubiinoaacigqcu@apollo13.peufeu.com>
References: <48342D6D.1020506@reedyriver.com>
<op.ubiinoaacigqcu@apollo13.peufeu.com>
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 t1.id > 158507 and t1.id = t2.id;
> >
> > 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 t1.id > 158507 and t2.id > 158507 and t1.id =
> > t2.id;
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:
http://www.perlmonks.org/?node_id=227909
* Analysis of Algorithms and Selection of Algorithms:
http://www.cs.utk.edu/~parker/Courses/CS302-Fall06/Notes/complexity.html
* Complexity and Big-O Notation
http://pages.cs.wisc.edu/~hasti/cs367-common/notes/COMPLEXITY.html
--
H. Hall
ReedyRiver Group LLC
http://www.reedyriver.com
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: hhall1001@reedyriver.com
Subject: Re: "Big O" notation for postgres?
In-Reply-To: <483474AB.4040807@reedyriver.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